机器学习之 k 近邻

核心思想

KNN算法假设给定的训练集中的实例都已经分好类了，对于新的实例，根据离它近的k个训练实例的类别来预测它的类别。即这k个实例大多数属于某个类别则该实例就属于某个类别。比如k为5，离新实例a近的5个样本的情况为，3个样本属于A类，1个样本属于B类，一个样本属于C类，那么新实例a属于A类。

常用距离

欧氏距离
曼哈顿距离
切比雪夫距离

k值的影响

k值的选取可能会影响到分类结果，如下图，k=3和k=5时的分类结果是不同的。

k值小可能会导致预测结果对近邻的样本点敏感，如果刚好是噪音则会导致预测结果出错，容易发生过拟合。近似误差小，估计误差大。
k值大可能会导致较远的样本也影响预测，也可能会导致预测错误。近似误差大，估计误差小。
k值一般先取较小的数，再用交叉验证方法选择优k值。

算法实现

两种方式：线性扫描和kd树。

线性扫描

KNN的简单朴素的方法即直接线性扫描，大致步骤如下：

计算待预测数据与各训练样本之间的距离；
按照距离递增排序；
选择距离小的k个点；
计算这k个点类别的频率，高的即为待预测数据的类别。

代码实现

from numpy import *
import pylab as pl

dataSet = array([[11, 12], [12, 12], [11, 11], [11, 16], [12, 16], [17, 11], [17, 12]])
classes = ['A', 'A', 'A', 'B', 'B', 'C', 'C']
k = 3
dot = [13, 13]
type
r = 0
dataSize = dataSet.shape[0]
diff = tile(dot, (dataSize, 1)) - dataSet
sqdiff = diff ** 2
squareDist = sum(sqdiff, axis=1)
dist = squareDist ** 0.5
sortedDistIndex = argsort(dist)
classCount = {}
for i in range(k):
    label = classes[sortedDistIndex[i]]
    classCount[label] = classCount.get(label,0) + 1
    if dist[i] > r:
        r = dist[i]
maxCount = 0
for key, value in classCount.items():
    if value > maxCount:
        maxCount = value
        type = key
pl.plot(dot[0], dot[1], 'ok')
circle = [i*pi/180 for i in range(0,360)]
x = cos(circle)*r+dot[0]
y = sin(circle)*r+dot[1]
pl.plot(x, y, 'r')
pl.plot([point[0] for point in dataSet[0:3]], [point[1] for point in dataSet[0:3]], 'og')
pl.plot([point[0] for point in dataSet[3:5]], [point[1] for point in dataSet[3:5]], 'or')
pl.plot([point[0] for point in dataSet[5:7]], [point[1] for point in dataSet[5:7]], 'oy')
pl.show()复制代码