机器学习之k近邻

核心思想

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

机器学习之k近邻

常用距离

  • 欧氏距离
    d(x,y)=ni=1(xiyi)2
  • 曼哈顿距离
    d(x,y)=ni=1|(xiyi)|
  • 切比雪夫距离
    d(x,y)=max(|xiyi|)

机器学习之k近邻

k值的影响

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

机器学习之k近邻

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

算法实现

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

线性扫描

KNN的最简单朴素的方法即直接线性扫描,大致步骤如下:
1. 计算待预测数据与各训练样本之间的距离;
2. 按照距离递增排序;
3. 选择距离最小的k个点;
4. 计算这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()

机器学习之k近邻

kd树

线性扫描非常耗时,为了减少计算距离的次数提高效率,使用kd树方法,它能快速地找到查询点近邻。

可以通过将搜索空间进行层次划分建立索引树以加快检索速度。

对于二维空间,它最终要划分的空间类似如下,

机器学习之k近邻

决定在哪个维度上进行分割是由所有数据在各个维度的方差决定的,方差越大说明该维度上的数据波动越大,更应该再该维度上对点进行划分。例如x维度方差较大,所以以x维度方向划分。

分割时一般取分割维度上的所有值的中值的点,比如下图,第一次计算方差较大的维度为x维度,中值点为A,以x=Ax分割,接着对分割后的点分别又继续分割,计算方差并寻找中值,以y=Cy、y=By分割,以此类推。

机器学习之k近邻

kd树查找

从根节点开始查找,直到叶子节点,整个过程将最短距离d和相应的点记录下来。

回溯,通过计算待预测的点到分割平面的距离l与最短距离d比较,看是否要进入节点的相邻空间去查找。回溯的过程是为了确认是否有必要进入相邻子空间去搜索,当待预测点到最近点的距离d大于待预测点到分割面的距离l时,则需要到相邻子空间查找,否则则没必要,直接往上一层回溯。

========广告时间========

鄙人的新书《Tomcat内核设计剖析》已经在京东销售了,有需要的朋友可以到 https://item.jd.com/12185360.html 进行预定。感谢各位朋友。

为什么写《Tomcat内核设计剖析》

=========================
欢迎关注:

机器学习之k近邻