4.1 K近邻算法

• 思想极度简单
• 应用数学知识少
• 可以解释机器学习算法使用过程中的很多细节问题
• 更完整的刻画机器学习的应用流程

  Ｋ近邻算法的本质其实是认为两个样本如果足够相似，就有更高的概率属于同一个类别。两个样本的相似性就是由在空间上两个样本的距离来决定的。</br>
  Ｋ近邻算法可以解决监督学习的分类问题,也可以解决回归问题。

import numpy as np
import matplotlib.pyplot as plt
# 模拟样本数据集
raw_data_x = [[3.423749247, 2.334567896],
              [3.110073483, 1.745697878],
              [1.347946498, 3.368464565],
              [3.582294042, 4.679565478],
              [2.280364646, 2.866699256],
              [7.423454548, 4.696522875],
              [5.745051465, 3.533989946],
              [9.172456464, 2.051111010],
              [7.792783481, 3.424088941],
              [7.939820184, 0.791637231]
            ]
raw_data_y = [0,0,0,0,0,1,1,1,1,1]
X_train = np.array(raw_data_x)
y_train = np.array(raw_data_y)
plt.scatter(X_train[y_train==0, 0], X_train[y_train==0, 1], color='g')
plt.scatter(X_train[y_train==1, 0], X_train[y_train==1, 1], color='r')
plt.show()

image

# 此时来了新的样本
x = np.array([8.093607318, 3.3657315144])
plt.scatter(X_train[y_train==0, 0], X_train[y_train==0, 1], color='g')
plt.scatter(X_train[y_train==1, 0], X_train[y_train==1, 1], color='r')
plt.scatter(x[0], x[1], color='b')
plt.show()

image

由此可以看出新的样本点应该是和红色点是一类。

KNN过程

欧拉距离:

\sqrt{(x^(a)-x^(b))^2 + (y^(a)-y^(b))^2}

\sqrt{(x^(a)-x^(b))^2 + (y^(a)-y^(b))^2 + (z^(a)-z^(b))^2}

\sqrt{(X_1^(a)-X_1^(b))^2 + (X_2^(a)-X_2^(b))^2 + ... + (X_n^(a)-X_n^(b))^2}

\sqrt{\sum_{i=1}^n(X_i^(a)-X_i^(b))^2}

from math import sqrt
distances = []
for x_train in X_train:
    d = sqrt(np.sum((x_train -x)**2))
    distances.append(d)
distances

# 等价于下面这行代码
distances = [sqrt(np.sum((x_train -x)**2)) for x_train in X_train]
distances

运行结果如下：

image

计算完距离之后还不够，因为我们主要想知道距离样本点最近的点。

np.argsort(distances)

运行结果：
array([8, 5, 7, 6, 9, 3, 0, 1, 4, 2])，我们可以看出距离最近的是索引为为８的点，距离第二近的是索引为５的点。

# 设置ｋ值，找出离样本点最近的ｋ个点的ｙ值
k = 6
nearest = np.argsort(distances)
topK_y = [y_train[i] for i in nearest[:k]]

运行结果：[1, 1, 1, 1, 1, 0]我们可以看出，距离样本点最近的６个点中，前５个点的ｙ值均为１．

#　计算不同类的点的个数，统计频数
from collections import Counter
Counter(topK_y)

运行结果：Counter({1: 5, 0: 1})这就表示值为１的元素有５个，值为０的元素只有１个。

# 就像投票一样，我们选出票数最多的一位
votes = Counter(topK_y)
votes.most_common(1)
# 由上面我们得到的是一个列表，但是我们只关心新样本所属的类别，因此只需要取出的类别值即可。
votes.most_common(1)[0][0]

image

由此我们可以看出，新的样本最有可能是１这一类。