K Nearest Neighbour Cluster Algorithm - kd tree

上一节的朴素搜索复杂度为$O(N)$,代码甚至可以精炼为:

import numpy as np
# x is the data to be classified.
# X is the train data
# p is the norm parameter
KNN=sorted(X,key=lambda xi:np.linalg.norm(x-xi,p))[:k]

kd树

k近邻最简单的方式是线性扫描，然而对于大量数据效率低，下面介绍kd tree: 注意区别于下一节介绍的决策树！

输入: $T = {x_{1},x_{2},\cdots,x_{n}}$，其中$x_{i}=(x_{i1},x_{i2},\cdots,x_{ik})^{T}, \ i=1,2,\cdots,n$
输出: kd tree

(1)构造根节点（包含T的k维空间超矩形区域），选择$x_{i,1}$为坐标轴，以T空间中所有$x_{i,1}$的中位数为切分点，将超矩形区域分成两个子区域。
(2)由根节点生成深度为1的左右两个子节点（即新生成的两个子区域）
(3)对深度为j的节点，选择$x_{i,l}$为切分坐标轴，$l=j(mod\ k)+1$，直到分出的子区域不再存在实例时停止。

kd树的构建

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

(1)以所有$x_{i1}$为坐标轴，所有$x_{i1}$从小到大组成集合${(2,3)^{T},(4,7)^{T},(5,4)^{T},(7,2)^{T},(8,1)^{T},(9,6)^{T}}$，此时中位数为6 （取$x_{i1}=7$为切分点）
(2)此时左子节点${(2,3)^{T},(5,4)^{T},(4,7)^{T}}$，右子节点${ (8,1)^{T},(9,6)^{T} }$
(3)$l=j(mod\ k)+1 = 2 \ within\ j=1, k=2$,所以左右子节点对$x_{i2}$进行切分
(3)左子节点按$x_{i2}$进行排序组成集合${(2,3)^{T},(5,4)^{T},(4,7)^{T}}$，中位数为4，此时产生深度为2的上下子节点，上节点${(4,7)^{T}}$，下节点${(2,3)^{T}}$，深度为2的上下子节点又可以按照$x_{i1}$切分，此时实例均在切分线上，左侧区域切分结束。
(4)同理，(2)中右子节点也可进行划分

最后产生的kd树为
$$
x_{i1} \ \ (7,2) \ \ \
\ \ \ \swarrow \ \searrow \
x_{i2} \ \ \ (5,4) \ \ \ (9,6) \
\ \ \ \swarrow \ \searrow \ \ \ \ \searrow \
x_{i1} \ (2,3) \ \ \ (4,7) \ \ \ \ \ (8,1)
$$

kd树的最近邻搜索

复杂度: $O(\log N) $ (有序序列)
输入:已构造的kd树，目标点x
输出:x的最近邻

(1)从根节点出发，递归向下访问kd树，找到包含目标点x的叶节点，此时该节点为近似最近邻
(2)以S为圆心，通过(1)中叶节点的圆内部一定存在真正最近邻。

以电影分类为例 用kd树分类