k近邻算法

工作原理

  • 存在一个样本数据集合，称作训练样本集，并且样本集中每个数据都存在标签，即知道样本集中每个数据与所述分类的对应关系

  • 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签

  • 一般来说，只选择样本数据集中前N个最相似的数据。k一般不大于20，最后选择k个中出现次数最多的分类，作为新数据的分类。k=1时，称为最近邻算法

    from统计学习方法

三要素

距离度量

LpL_p距离：Lp(xi,xj)=(∑l=1n∣xi(l)−xj(l)∣p)1pL_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}

当p=1时，称为曼哈顿距离；当p=2时，称为欧式距离；当p=∞\infty时，称为L∞L_\infty距离

三种距离

k值的选择

如果选择较小的k值

  • 近似误差减小，估计误差增大
  • 对噪声敏感
  • k值的减小意味着整体模型变得复杂，容易发生过拟合

如果选择较大的k值

  • 估计误差减小，近似误差增大
  • k值的增大意味着整体模型变得简单

分类决策规则

多数表决规则（等价于经验风险最小化）

kd树实现

对于每次输入样本，都要和已有的训练样本计算距离。若训练样本数量很多，那么时间复杂度会很高。为了提升效率，先将样本存储在树结构中，方便查找，减少计算次数

  • kd树是一种对K维空间中的实例点进行存储以便对其进行快速检索的树形数据结构
  • kd树是二叉树，表示对K维空间的一个划分（partition).构造kd树相 当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
# 参考了github上的一个代码
import numpy as np
class Node: #定义树的结构
    def __init__(self, data, lchild = None, rchild = None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild

class KdTree:
    def __init__(self):
        self.kdTree = None

    def create(self, dataSet, depth):   #创建kd树，返回根结点
        if (len(dataSet) > 0):
            m, n = np.shape(dataSet)    #求出样本行，列
            midIndex = int(m / 2) #中间数的索引位置
            axis = depth % n    #判断以哪个轴划分数据
            sortedDataSet = sorted(dataSet,key = lambda x:x[axis])# 按当前axis轴的数值对数据集排序
            node = Node(sortedDataSet[midIndex]) #将节点数据域设置为中位数，以样本位置为划分
            leftDataSet = sortedDataSet[: midIndex] #将中位数的左边创建2改副本
            rightDataSet = sortedDataSet[midIndex+1 :]
            node.lchild = self.create(leftDataSet, depth+1) #将中位数左边样本传入来递归创建树
            node.rchild = self.create(rightDataSet, depth+1)
            return node
        else:
            return None

    def preOrder(self, node):
        if node != None:
            print("tttt->%s" % node.data)
            self.preOrder(node.lchild)
            self.preOrder(node.rchild)
            
    def search(self, tree, x):
        self.nearestPoint = None    #保存最近的点
        self.nearestValue = 0   #保存最近的值
        def travel(node, depth = 0):    #递归搜索
            if node != None:    #递归终止条件
                n = len(x)  #特征数
                axis = depth % n    #计算轴
                if x[axis] < node.data[axis]:   #如果数据小于结点，则往左结点找
                    travel(node.lchild, depth+1)
                else:
                    travel(node.rchild, depth+1)

                #以下是递归完毕后，往父结点方向回朔
                distNodeAndX = self.dist(x, node.data)  #目标和节点的距离判断
                if (self.nearestPoint == None): #确定当前点，更新最近的点和最近的值
                    self.nearestPoint = node.data
                    self.nearestValue = distNodeAndX
                elif (self.nearestValue > distNodeAndX):
                    self.nearestPoint = node.data
                    self.nearestValue = distNodeAndX

                print(node.data, depth, self.nearestValue, node.data[axis], x[axis])
                if (abs(x[axis] - node.data[axis]) <= self.nearestValue):  #确定是否需要去子节点的区域去找（圆的判断）
                    if x[axis] < node.data[axis]:
                        travel(node.rchild, depth+1)
                    else:
                        travel(node.lchild, depth + 1)
        travel(tree)
        return self.nearestPoint

    def dist(self, x1, x2): #欧式距离的计算
        return ((np.array(x1) - np.array(x2)) ** 2).sum() ** 0.5

dataSet = [[2, 3],
           [5, 4],
           [9, 6],
           [4, 7],
           [8, 1],
           [7, 2]]
x = [5, 3]
kdtree = KdTree()
tree = kdtree.create(dataSet, 0)
kdtree.preOrder(tree)
print(kdtree.search(tree, x))