机器学习-3-k近邻法

Posted on | Post modified: | In
Words count in article: 4.1k

$k$近邻算法

$k$近邻法是一种基本分类与回归方法。以分类为例，$k$近邻的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。

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

算法：$k$近邻算法

输入：训练数据集$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$，其中$x_{i} \in \mathcal{X}=\mathbf{R}^{n}$为实例的特征向量，$y_{i} \in \mathcal{Y}=\{c_1,c_2,\dots,c_K\}$为实例的类别，$ i=1,2, \cdots, N$；实例特征向量$x$。

输出：实例$x$所属的类$y$。

（1）根据给定的距离度量，在训练集中找出与$x$最邻近的$k$个点，涵盖着$k$个点的$x$的邻域记作$N_k(x)$；

（2）在$N_k(x)$中根据分类决策规则（如多数表决）决定$x$的类别$y$：

式中，$I$为指示函数，即当$y_i=c_j$时$I$为1，否则$I$为0。

$k$近邻法的特殊情况是$k=1$的情形，称为最近邻算法。对于输入的实例点（特征向量）$x$，最近邻法将训练数据集中与$x$最邻近点的类作为$x$的类。$k$近邻没有显示的学习过程。

$k$近邻模型

模型

当训练集、距离度量、$k$值及分类决策规则确定后，对于任何一个新的输入实例，它所属的类唯一地确定，这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。

特征空间中，对每一个训练实例点$x_i$，距离该点比其他点更近的所有点组成一个区域，叫作单元。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。一般使用的是欧式距离，也可以是更一般的$L_p$距离。

设特征空间$\mathcal{X}$是$n$维实数向量空间$\mathbf{R}^n$，$x_{i}, x_{j} \in \mathcal{X}, \quad x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{\mathrm{T}}, \quad x_{j}=\left(x_{j}^{(1)}, x_{j}^{(2)}, \cdots, x_{j}^{(n)}\right)^{\mathrm{T}}$，$x_i, x_j$的$L_p$距离定义为：

当$p=2$时，称为欧式距离；当$p=1$时，称为曼哈顿距离。

$k$值的选择

$k$值的选择会对$k$近邻法的结果产生重大影响。

（1）较小的$k$值：相当于用较小的邻域中的训练实例进行预测。”学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是”学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。$k$值的减小意味着整体模型变得复杂，容易发生过拟合。

（2）较大的$k$值：相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。$k$值的增大意味着整体的模型变得简单。

如果$k=N$，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类，这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的的。

在实际应用中，$k$值一般取一个比较小的数值，通常可以采用交叉验证来选取最优的$k$值。

分类决策规则

$k$近邻法中的分类决策规则往往是多数表决，即由输入实例的$k$个邻近的训练实例中的多数类决定输入实例的类。

多数表决规则：如果分类的损失函数为0-1损失函数，分类函数为

那么误分类的概率是

对给定的实例$x \in \mathcal{X}$,其最近邻的$k$个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$的区域的类别是$c_j$，那么误分类率是

要使误分类率最小即经验风险最小，就要使$ \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right)$最大，所以多数表决规则等价于经验风险最小化。

$k$近邻法的实现：$kd$树

实现$k$近邻法时，主要的问题是如何对训练数据进行快速$k$近邻搜索。

$k$近邻法最简单的实现方法是线性扫描，这时要计算输入实例与每一个训练实例的距离，当训练集很大时，计算非常耗时，这种方法是不可行的。

为了提高$k$近邻搜索的效率，考虑使用特殊的结构存储训练数据，以减少计算距离的次数，如$kd$树方法。

构造$kd$树

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

构造$kd$树：构造根结点，使根结点对应于$k$维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对$k$维空间进行切分，生成子结
点。在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。

通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数为切分点，这样得到的$kd$树是平衡的。平衡的$kd$树搜索时的效率未必是最优的.

算法：构造平衡$kd$树

输入：k维空间数据集$T=\{x_1,x_2,\dots,x_N\}$，其中$x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(k)}\right)^{\mathrm{T}}, \quad i=1,2, \cdots, N$。

输出：$kd$树。

（1）开始：构造根结点，使根结点对应于$k$维空间中包含所有实例点的超矩形区域；

选择$x^{(1)}$为坐标轴，以$T$中所有实例的$x^{(1)}$坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域，切分由通过切分点并于坐标轴$x^{(1)}$垂直的超平面实现。

由根结点生成深度为1的左、右子结点：左子结点对应于坐标$x^{(1)}$小于切分点的子区域，右子结点对应于坐标$x^{(1)}$大于切分点的子区域。

将落在切分超平面的实例点保存在根结点。

（2）重复：对深度为$j$的结点，选择$x^{(j)}$为切分的坐标轴，$l=j(mod ~k)+1$，以该结点的区域中所有实例的$x^{(j)}$坐标的中位数为且分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并于坐标轴$x^{(j)}$垂直的超平面实现。

由该结点生成深度为$j+1$的左、右子结点：左子结点对应于坐标$x^{(j)}$小于切分点的子区域，右子结点对应于坐标$x^{(j)}$大于切分点的子区域。

将落在切分超平面的实例点保存在该结点。

（3）直到两个子区域没有实例点存在时停止，从而形成$kd$树的区域划分。

搜索$kd$树

利用$kd$树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

给定一个目标点，搜索其最近邻。首先找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父结点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高。

算法：用$kd$树的最近邻搜索

输入：已构造的$kd$树；目标点$x$；

输出：$x$的最近邻。

（1） 在$kd$树中找出包含目标点$x$的叶结点：从根结点出发，递归地向下访问$kd$树。若目标点$x$当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。

（2）以此叶结点为“当前最近点”。

（3）递归地向上回退，在每个结点进行以下操作:

​ （a） 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点“。

​ （b）当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索。如果不相交，向上回退。

（4）当回退到根结点时，搜索结束最后的“当前最近点”即为$x$的最近邻点。

如果实例点是随机分布的，$kd$树搜索的平均计算复杂度是$O(log N)$，这里$N$是训练实例数。$kd$树更适用于训练实例数远大于空间维数时的$k$近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

$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
class KNN:
    def __init__(self, X_train, y_train, n_neighbors = 3, p = 2):
        self.n = n_neighbors
        self.p = p
        self.X_train = X_train
        self.y_train = y_train

    def predict(self, X):
        # 初始化取出N个点放到结果列表里
        knn_list = []
        for i in range(self.n):
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            knn_list.append((dist, self.y_train[i]))

        # 对剩余的点计算距离:
        # 每次取出距离最大的点, 如果当前点距离更小, 则替换
        # 最后的结果列表中保存的是距离最小的N个点
        for i in range(self.n, len(self.X_train)):
            max_index = knn_list.index(max(knn_list, key=lambda x:x[0]))
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            if knn_list[max_index][0] > dist:
                knn_list[max_index] = (dist, self.y_train[i])

        # 对结果列表进行多数表决，返回多数类
        knn = [k[-1] for k in knn_list]
        count_pairs = Counter(knn)
        max_count = sorted(count_pairs.items(), key=lambda x:x[1])[-1][0]
        return max_count

    def score(self, X_test, y_test):
        right_count = 0
        for X, y in zip(X_test, y_test):
            label = self.predict(X)
            if label == y:
                right_count += 1
        return right_count / len(X_test)

if __name__ == '__main__':
    import numpy as np
    import pandas as pd
    import matplotlib.pylab as plt

    from sklearn.datasets import load_iris
    from sklearn.model_selection import train_test_split
    from collections import Counter

    iris = load_iris()
    df = pd.DataFrame(iris.data, columns= iris.feature_names)
    df['label'] = iris.target
    df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']

    # 原始数据选取二维画图
    plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
    plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
    plt.xlabel('sepal length')
    plt.ylabel('sepal width')
    plt.legend()
    plt.show()

    # 选取前两维+label->data
    data = np.array(df.iloc[:100,[0,1,-1]])
    X, y = data[:, :-1], data[:, -1]
    X_train, X_test, y_train, y_test = train_test_split(X,y, test_size=0.3)

    model = KNN(X_train, y_train)
    score = model.score(X_test, y_test)
    print(score)

    # sklearn实现
    from sklearn.neighbors import KNeighborsClassifier
    clf_sk = KNeighborsClassifier()
    clf_sk.fit(X_train, y_train)
    score_sk = clf_sk.score(X_test, y_test)
    print(score_sk)

$kd$树的实现

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
108
109
110
111
112
113
114
115
116
117
118

# kd_tree每个结点中主要包含的数据结构如下
class KdNode(object):
    def __init__(self, dom_elt, split, left, right):
        self.dom_elt = dom_elt # k维空间向量结点
        self.split = split # 整数(进行分割维度的序号)
        self.left = left # 该结点分割超平面子空间构成的kd-tree
        self.right = right # 该结点分割超平面右子空间构成kd-tree

class KdTree(object):
    def __init__(self, data):
        k = len(data[0]) # 数据维度

        # 按split维划分数据集创建KdNode
        def CreateNode(split, data_set):
            if not data_set:
                return None
            data_set.sort(key = lambda x: x[split])
            split_pos = len(data_set) // 2
            median = data_set[split_pos]
            split_next = (split + 1) % k
            return KdNode(median,
                          split,
                          CreateNode(split_next, data_set[:split_pos]),
                          CreateNode(split_next, data_set[split_pos+1:]))
        self.root = CreateNode(0, data)

# KDTree的前序遍历
def preorder(root):
    print(root.dom_elt)
    if root.left:
        preorder(root.left)
    if root.right:
        preorder(root.right)

# 对构建好的kd树进行搜索，寻找与目标点最近的样本点
from math import sqrt
from collections import namedtuple

# 定义一个namedtuple，分别存放最近坐标点、最近距离和访问过的结点树
result = namedtuple("Result_tuple", "nearest_point nearest_dist nodes_visited")

def find_nearest(tree, point):
    k = len(point) # 数据维度

    def travel(kd_node, target, max_dist):
        if not kd_node:
            return result([0] * k, float("inf"), 0)
        nodes_visited = 1
        s = kd_node.split # 进行分割的维度
        pivot = kd_node.dom_elt # 进行分割的轴

        if target[s] <= pivot[s]: # 如果目标点第s维小于分割轴的对应值（目标离左子树更近）
            nearer_node = kd_node.left # 下一个访问结点为左子树根节点
            further_node = kd_node.right # 同时记录下右子树
        else: # 目标离右子树更近
            nearer_node = kd_node.right
            further_node = kd_node.left

        temp1 = travel(nearer_node, target, max_dist) # 进行遍历找到包含目标点的区域

        nearest = temp1.nearest_point # 进行遍历找到包含目标点的区域
        dist = temp1.nearest_dist # 更新最近距离

        nodes_visited += temp1.nodes_visited

        if dist < max_dist:
            max_dist = dist # 最近点将在目标点为球心，max_dist为半径的超球体内

        temp_dist = abs(pivot[s] - target[s]) # 第s维上目标点与分割超平面的距离
        if max_dist < temp_dist: # 判断超球面是否与超平面相交
            return result(nearest, dist, nodes_visited) # 不想交则直接可以返回

        # 计算目标点与分割点的欧式距离
        temp_dist = sqrt(sum((p1-p2)**2 for p1, p2 in zip(pivot, target)))

        if temp_dist < dist: # 如果更近
            nearest = pivot
            dist = temp_dist
            max_dist = dist

        # 检查另一个子结点对应的区域是否有更近的点
        temp2 = travel(further_node, target, max_dist)

        nodes_visited += temp2.nodes_visited
        if temp2.nearest_dist < dist: # 如果另一个子结点内存在更近距离
            nearest = temp2.nearest_point # 更新最近点
            dist = temp2.nearest_dist # 更新最近距离

        return result(nearest, dist, nodes_visited)

    return travel(tree.root, point, float("inf"))


if __name__ == '__main__':
    data = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]
    kd = KdTree(data)
    preorder(kd.root)

    # 寻找[3,4.5]最近邻的点
    res = find_nearest(kd, [3, 4.5])
    print(res)

    from random import  random

    # 产生一个k维随机变量，每维分量值在0~1之间
    def random_point(k):
        return [random() for _ in range(k)]

    # 产生n个k维随机向量
    def random_points(k, n):
        return [random_point(k) for _ in range(n)]
	# 构建包含四十万个3维空间样本点的kd树
    N = int(4e5)
    kd2 = KdTree(random_points(3, N))
    #  四十万个样本点中寻找离目标最近的点
    res2 = find_nearest(kd2, [0.1, 0.5, 0.8])
    print(res2)

参考文献
统计学习方法. 李航
https://github.com/fengdu78/lihang-code/blob/master/%E7%AC%AC03%E7%AB%A0%20k%E8%BF%91%E9%82%BB%E6%B3%95/3.KNearestNeighbors.ipynb

Donate comment here
------------The End------------
0%