【MachineLearning】之 K-近邻算法实现

一、步骤

---

1. 数据准备：通过数据清洗，数据处理，将每条数据整理成向量。
2. 计算距离：计算测试数据与训练数据之间的距离。
3. 寻找邻居：找到与测试数据距离最近的 K 个训练数据样本。
4. 决策分类：根据决策规则，从 K 个邻居得到测试数据的类别。

下面尝试一个KNN分类流程

（1）数据生成

"""生成示例数据
"""
import numpy as np


def create_data():
    features = np.array(
        [[2.88, 3.05], [3.1, 2.45], [3.05, 2.8], [2.9, 2.7], [2.75, 3.4],
         [3.23, 2.9], [3.2, 3.75], [3.5, 2.9], [3.65, 3.6], [3.35, 3.3]])
    labels = ['A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B']
    return features, labels

"""打印示例数据
"""
features, labels = create_data()
print('features: \n', features)
print('labels: \n', labels)

"""示例数据绘图
"""
from matplotlib import pyplot as plt
%matplotlib inline

plt.figure(figsize=(5, 5))
plt.xlim((2.4, 3.8))
plt.ylim((2.4, 3.8))
x_feature = list(map(lambda x: x[0], features))  # 返回每个数据的x特征值
y_feature = list(map(lambda y: y[1], features))
plt.scatter(x_feature[:5], y_feature[:5], c="b")  # 在画布上绘画出"A"类标签的数据点
plt.scatter(x_feature[5:], y_feature[5:], c="g")
plt.scatter([3.18], [3.15], c="r", marker="x")  # 待测试点的坐标为 [3.1，3.2]

标签标注：
标签为 A （蓝色圆点） 的数据在左下角的位置。
标签为 B （绿色圆点） 的数据在右上角的位置。
红色 × 点 即表示本次实验需预测类别的测试数据。

（2）算法实现

1. 距离计算：欧式距离
2. 分类的决策规则：多数表决法

• test_data：用于分类的输入向量。
• train_data：输入的训练样本集。
• labels：样本数据的类标签向量。
• k：用于选择最近邻居的数目。

"""KNN 方法完整实现
"""


def knn_classify(test_data, train_data, labels, k):
    distances = np.array([])  # 创建一个空的数组用于存放距离

    for each_data in train_data:  # 使用欧式距离计算数据相似度
        d = d_euc(test_data, each_data)
        distances = np.append(distances, d)

    sorted_distance_index = distances.argsort()  # 获取按距离大小排序后的索引
    sorted_distance = np.sort(distances)
    r = (sorted_distance[k]+sorted_distance[k-1])/2  # 计算

    class_count = {}
    for i in range(k):  # 多数表决
        vote_label = labels[sorted_distance_index[i]]
        class_count[vote_label] = class_count.get(vote_label, 0) + 1

    final_label = majority_voting(class_count)
    return final_label, r

分类预测

对未知数据 [3.18, 3.15] 开始分类，初识设定 K值 为 5

test_data = np.array([3.18, 3.15])
final_label, r = knn_classify(test_data, features, labels, 5)
final_label

画图方式 形象化 展示 KNN 算法决策方式。

def circle(r, a, b):  # 为了画出圆，这里采用极坐标的方式对圆进行表示 ：x=r*cosθ，y=r*sinθ。
    theta = np.arange(0, 2*np.pi, 0.01)
    x = a+r * np.cos(theta)
    y = b+r * np.sin(theta)
    return x, y


k_circle_x, k_circle_y = circle(r, 3.18, 3.15)

plt.figure(figsize=(5, 5))
plt.xlim((2.4, 3.8))
plt.ylim((2.4, 3.8))
x_feature = list(map(lambda x: x[0], features))  # 返回每个数据的x特征值
y_feature = list(map(lambda y: y[1], features))
plt.scatter(x_feature[:5], y_feature[:5], c="b")  # 在画布上绘画出"A"类标签的数据点
plt.scatter(x_feature[5:], y_feature[5:], c="g")
plt.scatter([3.18], [3.15], c="r", marker="x")  # 待测试点的坐标为 [3.1，3.2]
plt.plot(k_circle_x, k_circle_y)

当 K 值为 5 时，与测试样本距离最近的 5 个训练数据（如蓝色圆圈所示）中属于 B 类的有 3 个，属于 A 类的有 2 个，根据多数表决法决策出测试样本的数据为 B 类。

在 KNN 算法中，K 值得选择对数据的最终决策有很大的影响，引入 ipywidgets 模块更加清晰的反映 K 的选择对预测结果影响。其中 ipywidgets 模块是 jupyter 中的一个交互式模块，可以通过下拉菜单选择不同的 K 值进行判断并预测未知点最后的种类。

from ipywidgets import interact, fixed


def change_k(test_data, features, k):
    final_label, r = knn_classify(test_data, features, labels, k)
    k_circle_x, k_circle_y = circle(r, 3.18, 3.15)
    plt.figure(figsize=(5, 5))
    plt.xlim((2.4, 3.8))
    plt.ylim((2.4, 3.8))
    x_feature = list(map(lambda x: x[0], features))  # 返回每个数据的x特征值
    y_feature = list(map(lambda y: y[1], features))
    plt.scatter(x_feature[:5], y_feature[:5], c="b")  # 在画布上绘画出"A"类标签的数据点
    plt.scatter(x_feature[5:], y_feature[5:], c="g")
    plt.scatter([3.18], [3.15], c="r", marker="x")  # 待测试点的坐标为 [3.1，3.2]
    plt.plot(k_circle_x, k_circle_y)


interact(change_k, test_data=fixed(test_data),
         features=fixed(features), k=[3, 5, 7, 9])