笔记|统计学习方法：k近邻算法

发表于 更新于 Valine： 本文字数： 4.6k 估计阅读时长 ≈ 4 分钟

k近邻算法(k-NN)是一种基本分类与回归方法，它有三个基本要素，本文将介绍k近邻算法的模型与kd树。

k近邻算法

给定一个训练数据集，对于新输入的实例，在训练数据集中找到与该实例最临近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

数学实现

输入:训练数据集

其中， ,为实例的类别,;实例特征向量 输出：实例x所属的类y。

  • 1.根据给定的距离度量，在训练集中找出与最近邻的个点，涵盖这个点的的领域记作。
  • 2.在中根据分类决策规则(如多数表决)决定的类别。

式中为指示函数，即当时为，否则为0. 在时称为最近邻算法，k近邻法没有显式的学习过程。

模型建立

模型三要素为：距离度量，的大小和分类规则。

距离度量

  • 闵可夫斯基距离(Minkowski Distance) 其中。
  • 当时，是欧式距离。
  • 当时，是曼哈顿距离。

的选择

的选择会对结果产生重大影响。

  • 的值过小，极端情况下，测试实例只和最接近的一个样本有关，训练误差很小，但是如果这个样本恰好是噪点，预测就会出错，即产生了过拟合。
  • 如果值过大，极端情况，则会产生欠拟合。

姑通常采用交叉验证法来选取合适的。

分类规则

近邻的分类决策通常是多数表决：由测试样本的个临近样本的多数类决定测试样本的类别。有如下规则： 给定测试样本，其最临近的个训练示例构成的集合，分类损失函数为型损失，如果涵盖区域的类别为，则分类误差率为：

要使得分类误差率最小，就是要使最大，所以多数表决规则等价于误分类绿最小。

实现：树

树算法有三步：

  1. 构造树
  2. 搜索近邻
  3. 预测

树的构建

  • 选取为坐标轴，以训练集中的所有数据坐标中的中位数作为切分点，将超矩形区域切割成两个子区域。将该切分点作为根结点，由根结点生出深度为1的左右子结点，左节点对应坐标小于切分点，右结点对应坐标大于切分点。
  • 对深度为的结点，选择为切分坐标轴，，以该结点区域中训练数据坐标的中位数作为切分点，将区域分为两个子区域，且生成深度为的左、右子结点。左节点对应坐标小于切分点，右结点对应坐标大于切分点
  • 重复2，直到两个子区域没有数据时停止。
实例参考KNN算法和kd树详解（例子+图示）

的搜索

输入：已构造的树，目标点 输出：的最近邻

  1. 在kd树中找出包含目标点的叶结点；从根结点，递归地向下访问kd树，若目标点当前纬的坐标小于分切点，则移动到左子结点，直到子结点为叶子结点为止。
  2. 此叶子结点为"当前最近点"。
  3. 递归地向上回退，在每个结点都进行如下操作：
1
2
3
4
5
6
(a)如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”

(b)当前最近点一定存在于该结点一个子结点对应的区域，检查该子结点的父结点的另一个子结点对应的区域是否有更近的点。具体的，检查另一子结点对应的区域是否与以目标点为球心，以目标点与“当前最近点”间的距离为半径的超球体相交。

(c)如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；如果不相交，则向上退回。

  1. 当退回到根结点时，搜索结束。最后一个“当前最近点”即为的最近邻点。
实例参考KNN算法和kd树详解（例子+图示）

Python代码实现

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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 = self.sort(dataSet, axis) #进行排序
            node = Node(sortedDataSet[midIndex]) #将节点数据域设置为中位数，具体参考下书本
            # print sortedDataSet[midIndex]
            leftDataSet = sortedDataSet[: midIndex] #将中位数的左边创建2改副本
            rightDataSet = sortedDataSet[midIndex+1 :]
            print(leftDataSet)
            print(rightDataSet)
            node.lchild = self.create(leftDataSet, depth+1) #将中位数左边样本传入来递归创建树
            node.rchild = self.create(rightDataSet, depth+1)
            return node
        else:
            return None

    def sort(self, dataSet, axis):  #采用冒泡排序，利用aixs作为轴进行划分
        sortDataSet = dataSet[:]    #由于不能破坏原样本，此处建立一个副本
        m, n = np.shape(sortDataSet)
        for i in range(m):
            for j in range(0, m - i - 1):
                if (sortDataSet[j][axis] > sortDataSet[j+1][axis]):
                    temp = sortDataSet[j]
                    sortDataSet[j] = sortDataSet[j+1]
                    sortDataSet[j+1] = temp
        print(sortDataSet)
        return sortDataSet

    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):
    #     node = tree
    #     depth = 0
    #     while (node != None):
    #         print node.data
    #         n = len(x)  #特征数
    #         axis = depth % n
    #         if x[axis] < node.data[axis]:
    #             node = node.lchild
    #         else:
    #             node = node.rchild
    #         depth += 1
    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))