文章目录

• kNN算法思想与步骤
• 实例分析与代码实现

kNN算法思想与步骤

kNN算法的基本思想如下：
假设样本集共有n个样本，它们在m个特征上具有区分度，它们分别属于0或1中的一类。假设第i个样本的特征向量为 （ a i 1 , a i 2 , ⋯   , a i m ） （a_{i1},a_{i2},\cdots,a_{im}） （ai1​,ai2​,⋯,aim​）。现有一待归类对象，设它的特征向量为 ( b 1 , b 2 , ⋯   , b m ) (b_1,b_2,\cdots,b_m) (b1​,b2​,⋯,bm​)。计算此待归类对象与n个样本在特征空间中的欧氏距离，即对每个i(i=1,2, ⋯ \cdots ⋯,n)，计算 ∑ j = 1 m ( a i j − b j ) 2 \sqrt{\sum_{j=1}^m (a_{ij}-b_j)^2} ∑j=1m​(aij​−bj​)2 ​，在n个样本中找出与待归类对象距离最近的k个样本，统计这k个样本中属于0类的个数与1类的个数，kNN算法将把待归类对象归入个数较多的那一类。

实例分析与代码实现

我们以有样本集数目为10，特征个数为2的问题为例，介绍如何利用python写kNN算法。
首先导入所需库：

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter

其中matplotlib是方便我们观察结果
然后定义样本集：

X_train = np.array([[1.2,2.8],
                    [1.9,3.7],
                    [2.5,3.8],
                    [4.8,7.9],
                    [9.7,2.6],
                    [5.6,7.8],
                    [10.8,2.7],
                    [13.7,22.7],
                    [5.48,14.82],
                    [11.23,17.16]])
Y_train = np.array([1,1,1,1,0,1,0,0,0,0])

我们先来观看一下样本集的分布：

图中红色点为1类，绿色点为0类
接下来输入待归类对象：

x = np.array([6.653,10.849])

计算距离：

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

下面对距离列表ditance元素排序，选出最小的k个，但是需要注意的是，我们对于距离本身的大小并不关心，我们关心的是这k个最小距离对应的是样本集中的哪k个样本，从而判断k个样本有多少属于0类，有多少属于1类，因此我们下一步使用numpy中的argsort函数，它返回的是索引值。

out = np.argsort(distance)

从而out列表存放了距离从小到大排序所对应的样本序号，下一步选出前k个判断属于哪一类即可。

k = 4

topK_y = [Y_train[i] for i in out[:k]]
r = Counter(topK_y)
s = r.most_common(1)[0][0]
print(s)

列表topK_y存放的是样本集Y_train中这k个索引对应的类别，Counter函数帮我们统计了列表中每个元素有多少个，most_common（t）函数会返回最多的t个二元组，此时我们需要的是最多的那个类别，因此t=1，并且返回[0][0]即可

输出结果：
最终输出的结果为1，这说明算法将此对象归入1类，我们观察下图像：

蓝色点为新点，故其被归入红色点集

完整代码如下：

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter

#定义训练集：
X_train = np.array([[1.2,2.8],
                    [1.9,3.7],
                    [2.5,3.8],
                    [4.8,7.9],
                    [9.7,2.6],
                    [5.6,7.8],
                    [10.8,2.7],
                    [13.7,22.7],
                    [5.48,14.82],
                    [11.23,17.16]])
Y_train = np.array([1,1,1,1,0,1,0,0,0,0])

#需判断样本：
x = np.array([6.653,10.849])

#计算距离：
distance = []
for x_train in X_train:
    d = np.sqrt(np.sum((x-x_train)**2))
    distance.append(d)

out = np.argsort(distance)

#定义k值：
k = 4

topK_y = [Y_train[i] for i in out[:k]]
r = Counter(topK_y)
s = r.most_common(1)[0][0]
print(s)

plt.scatter(X_train[Y_train==0,0],X_train[Y_train==0,1],c='g')
plt.scatter(X_train[Y_train==1,0],X_train[Y_train==1,1],c='r')
plt.scatter(x[0],x[1],c='b')
plt.show()

需要指出的是，k值具体取多少并不是随意的，需要根据不同情况加以确定。