k近邻算法

发表于   |  

简介

k近邻(KNN)是一种基本的分类算法. 可以多分类. 分类时, 对新的样本, 根据其k个最邻近的训练样本的类别通过投票等规则来进行预测. KNN并没有显示的学习过程, 更像是通过统计来确定实例的类别.

KNN的三个基本要素是: k值的选取, 距离度量, 分类决策规则.

如果训练样本较多, 每当来一个新的样本, 则需要计算新样本与所有训练样本的距离, 然后取k个距离最近的训练样本来进行决策分类. 这种线性的计算在训练样本很大的时候需要花费较多的时间. 因此, 需要考虑快速的进行k近邻搜索.

kd tree

kd树是对k维空间中的样本进行存储以便于对其进行快速检索的数据结构. kd树是二叉树, 表示对k维空间的划分.

kd树的构造





kd树的构造采用递归的方式, 每次抽取样本特征空间中的一维 $x_i$ , 取样本在 $x_i$ 的中位数, 对所有样本进行划分, 则得到了两批子样本, 然后再取特征空间的另一维 $x_j$ , 重复上述步骤, 直到子样本为null. 具体的伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function kdtree(data[][], depth) {
	if(data == null) return null

	n = data.length //sample size
	m = data[0].length //eigenspace dimensions

	axis = depth mod m //select axis based on depth

	median = data[:][axis]; //the median of data[:][axis]

	//create node and construct subtree
	node.location = median
	node.point =
	node.axis = axis
	node.leftChild = kdtree([d in data if d[axis] < median ], depth+1)
	node.rightChild = kdtre([d in data if d[axis] > median ], depth+1)

	return node
}

The worst-case Time Complexity is $O(dn \log n)$, The Space Complexity is $O(dn)$. The $d$ is the depth.

kd树的搜索

首先考虑最邻近的搜索过程, 然后再基于最邻近搜索来实现k邻近的搜索.