C语言k近邻算法及例题,K近邻算法的理解及KD树的构建

K近邻算法

给定一个数据集,对于新的输入实例,在训练集中找到与该实例最邻近的k个实例,这k个实例的大多数属于一个类,该实例就归为这一类.

输入: 训练数据集T${(x_1,y_1),(x_2, y_2),...,(x_n,y_n)}$,其中$x_i\in \chi \subseteq R^n$为实例的特征向量,$y_i\in \gamma=\{c_1, c_2,...,c_k\}$. i=1, 2,...,N. 实例特征向量x;

输出: 实例x所属的类别y

根据指定的距离度量,在训练集T中找到与实例x最邻近的k个点, 涵盖这k个点的x的领域记作$N_k(x)$;

在$N_K(x)$中根据分类决策规则决定x的类别y:

$$y = argmax_{c_j}\sum_{x_i\in N_k(x)}{I(y_i=c_i)},i\in\{1,2,...,N\}, j\in\{1,2,...,K\} \tag{1}$$

式1中,I为指示函数, 但$y_i=c_i$时为1,否则为0.

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

K近邻模型

K近邻算法使用的模型实际上对应于特征空间的划分.模型由三个基本要素-距离度量、K值的选择和分类决策规则决定。

模型

K近邻法当训练集、距离度量(如欧氏距离)、k值及分类决策规则(如多数表决))确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。如下图所示。

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是n维实数向量空间$R^n$。使用的距离是欧氏距离，但也可以是其他距离，如更一般的$L_p$距离或Minkowski距离

设特征空间x是n维实数向量空间$R^n;x_i,x_j\in \chi ,x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)})^T$,$x_i,x_j$的$L_p$距离定义为

$$L_p(x_i, x_j)=(\sum_{l=1}^N|(x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p}\tag{2}$$

这里p>0。当p=2时，$L_p$距离为欧式距离。

当p=1时，$L_p$距离为曼哈顿距离。

$$L_p(x_i, x_j)=\sum_{l=1}^N|(x_i^{(l)}-x_j^{(l)}|\tag{3}$$

当p=$\infty$时，它是各个坐标距离的最大值，即

$$L_p(x_i, x_j)=max_{(l)}|(x_i^{(l)}-x_j^{(l)}|\tag{4}$$

如下图给出了二维空间中p取不同值时，与原点的$L_p$距离为1($L_p$＝1)的点的图形。

k值的选择

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

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

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

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

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

分类决策规则

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

多数表决规则(majority voting rule)有如下解释：如果分类的损失函数为0-1损失函数，分类函数为

$$f:R^n \rightarrow \{c_1,c_2,...,c_k\}$$

那么误分类的概率为

$$P(Y\neq f(X))=1-P(Y=f(X))\tag{5}$$

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

$$\frac{1}{k}\sum_{x_i\in N_k(x)}=1-\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i=c_j)\tag{6}$$

要使误分类率最小即经验风险最小，就要使$\sum_{x_i\in N_k(x)}I(y_i=c_j)$最大，所以多数表决规则等价于经验风险最小化

K近邻法的代码实现

class Knn:

def __init__(self, x_train, y_train, k=3):

self.k = k

self.x_train = x_train

self.y_train = y_train

def predict(self, x, y_test=None):

assert len(x.shape) == 2, 'dimension of x must be equal with 2'

# 计算距离矩阵

dis = (self.x_train[:, None, :] - x) ** 2

dis = dis.sum(-1)

# 按照距离升序排序，取出前k个样本的索引

n_k_idx = dis.argsort(0)[:self.k]

# n_k_labels = [self.y_train[n_k_idx[:, i]] for i in range(n_k_idx.shape[1])]

# 根据索引获取label

n_k_label = self.y_train[n_k_idx]

# 得到出现次数最多的标签作为最终结果

y_pred = np.array([np.argmax(np.bincount(n_k_label[:, i])) for i in range(n_k_label.shape[1])])

# 如果y_test不为空，计算预测得分

if y_test is not None:

self.score = self._score(y_pred, y_test)

return res

def _score(self, y_pred, y_test):

return np.count_nonzero(y_test==y_pred) / len(y_pred)

这里使用鸢尾花数据作为演示

data = load_iris()

X, y = data['data'], data['target']

x_train, x_test, y_train, y_test = train_test_split(X, y, random_state=20190303, shuffle=True, test_size=0.1)

net = Knn(x_train, y_train)

net.predict(x_test, y_test)

# 输出：0.9333333333333333

print(net.score)

使用sklearn中的knn分类器

from sklearn.neighbors import NeighborsClassifier

net1 = NeighborsClassifier()

net1.fit(x_train, y_train)

# 输出：0.9333333333333333

net1.score(x_test, y_test)

K近邻法的实现：kd树

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

为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。下面介绍kd树(kd tree)算法

构建kd树

构造kd树的算法如下

输入：k维空间数据集$T=\{x_1,x_2,...,x_N\}$,其中$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)})^T,i=1,2,...,N$；

输出：kd树

开始：构造根结点，根结点对应于包含T的k维空间的超矩形区域。选择$x^{(1)}$为坐标轴，以T中所有实例的$x^{(1)}$坐标的中位数为切分点(如果数据集的个数为偶数，则选择中位坐标或右边的树作为切分点，并不影响)，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。

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

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

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

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

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

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

给定一个二维空间的数据集：

$$T=\{(2, 3)^T,(5, 4)^T,(9, 6)^T,(4, 7)^T,(8, 1)^T,(7, 2)^T\}$$

构建一个平衡kd树

首先构建根节点，$x^{(1)}$坐标的中位数为7(如果数据的个数为偶数，则取中位数左边和右边都可以，这里取右边作为切割点)，以平面$x^{(1)}=7$将空间划分为左、右两个子矩形(节点)；$x^{(1)}$小于7的划到左边，$x^{(1)}$大于7的划到右边。

接着，左矩形以$x^{(2)}=4$分为2个子矩形(节点).如此递归，最后得到如下图所示的kd树。

kd树构建的代码如下

class Node:

def __init__(self, x0):

self.left = None

self.right = None

self.x0 = x0

self.split = None

def create_node(data, depth=0):

n, f = data.shape

if n == 0:

return

if n == 1:

node = Node(data[0])

node.split = depth % f

return node

# 构建根节点

feat = data[:, depth % f]

sorted_feat = feat.argsort()

x0 = data[sorted_feat[int(n / 2)]]

node = Node(x0)

node.split =depth % f

node.left = create_node(data[sorted_feat[:int(len(feat) / 2)]], depth+1)

node.right = create_node(data[sorted_feat[int(len(feat) / 2) + 1:]], depth+1)

return node

# 树的前序遍历

def preorder(node):

if node is not None:

print(node.x0)

preorder(node.left)

preorder(node.right)

class KDTree:

def __init__(self, data):

self.root = create_node(data)

kd搜索树

下面介绍如何利用kd树进行k近邻搜索

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

现在上图构建的kd树的基础上，找到$[3, 4.5]^T$的3个近邻。

设L为包含目标点的k个近邻的列表。

首先找到包含目标点的叶子结点，从根节点出发，将根节点作为当前结点，比较当前结点和目标点在当前结点的切割维度上的大小，由于3<7, 移动到根节点的左边。

将(5, 4)作为当前结点，由于4.5>4, 所以转向(5, 4)的右边 ， 即(4, 7).

将(4, 7)作为当前结点，由于(4, 7)已经没有子节点，而且L的长度小于3，将(4， 7)添加到L中。

回到(4, 7)的根节点(5, 4)，将(5, 4)作为当前结点。如果L的长度小于3则将(5, 4)添加到L中，转向当前结点的另一个子节点。如果L的长度等于3， 计算当前结点与目标点的距离，如果距离大于L中的最大距离，则说明当前结点的另一个分支与目标点的超球体没有交点(另一个分支不会有更近的点)。

由于L的长度为2， 小于3， 转到结点(2, 3)，将其作为当前结点， 添加到L中，由于当前结点没有子节点， 于是退到父节点(5， 4)。

由于父节点已经访问过，继续退到父节点，到了结点(7， 2), 将(7, 2)作为当前结点。由于L的长度为3， 此时计算当前结点与目标点的距离，计算的距离大于L中的最大距离。

结束搜索过程，返回L。

搜索代码如下所示：

def travel(node, target, L, k=3):

"""

Params:

node(Node): 当前结点

L(dict): k，即对应的距离。{'nearest':[], 'dist': [], 'max_dist': float('inf')}

k(integer): 指定搜索临近点的数目

"""

if node is None:

return

# 当前节点的分割维度

s = node.split

# 当前节点的值

pivot = node.x0

# 如果目标节点分割维度的值小于当前节点

# 目标点离左子树更近

if target[s] < pivot[s]:

nearest_mode = node.left

furthre_mode = node.right

# 目标点离右子树更近

else:

nearest_mode = node.right

furthre_mode = node.left

# 递归找到目标点所在的区域

travel(nearest_mode, target, L)

# 计算欧式距离

temp_dist = sqrt(sum((p1 - p2)**2 for p1, p2 in zip(pivot, target)))

# 如果L的长度小于k，直接添加

if len(L['nearest']) < k:

L['nearest'].append(pivot)

L['dist'].append(temp_dist)

L['max_dist'] = max(L['dist'])

else:

# 如果当前结点与目标结点的距离大于L的最大距离，跳出

if temp_dist > L['max_dist']:

return

# 如果当前结点与目标结点的距离小于L的最大距离，替换

if len(L['nearest']) == 3 and temp_dist < L['max_dist']:

idx = L['dist'].index(L['max_dist'])

L['nearest'][idx] = pivot

L['dist'][idx] = temp_dist

L['max_dist'] = max(L['dist'])

# 检查另外一个节点是否有更近的点

travel(furthre_mode, target, L)

return

def find_k_nearest(tree, target, k=3):

nearest = {'nearest':[], 'dist': [], 'max_dist': float('inf')}

travel(tree.root, target, nearest, k)

return nearest

基于创建好的kd树执行搜索

a = np.array([[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]])

tree = KDTree(a)

find_k_nearest(tree, [3, 4.5])

运行结果：

在400000样本点中找目标点的3个近邻点，看一下kd树的效率

from pprint import pprint

N = 400000

t0 = time()

# 构建包含N个3维空间样本点的kd树

kd2 = KDTree(np.random.randn(N, 3))

# 在N个样本点中寻找离目标最近的k个点

ret2 = find_k_nearest(kd2, [0.1,0.5,0.8])

t1 = time()

print ("time: ",t1-t0, "s")

pprint (ret2)

运行结果：

总结

1．k近邻法是基本且简单的分类与回归方法。k近邻法的基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的k个最近邻训练实例点，然后利用这k个训练实例点的类的多数来预测输入实例点的类。

2．k近邻法三要素：距离度量、k值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的$p_L$距离。k值小时，k近邻模型更复杂；k值大时，k近邻模型更简单。k值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的k。常用的分类决策规则是多数表决，对应于经验风险最小化。

3．kd树是一种便于对k维空间中的数据进行快速检索的数据结构，如果实例点是随机分布的，kd树搜索的平均计算复杂度是O(logN)，这里N是训练实例数。kd树更适用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

哎，kd树这部分的代码写的有点乱，只能勉强用了。

Reference

李航-《统计学习方法》