K Nearest Neighbor有关问题的解决——KD-TREE Implementation

K Nearest Neighbor问题的解决——KD-TREE Implementation
命题一：
已知的1000个整数的数组，给定一个整数，要求查证是否在数组中出现？

命题二：
已知1000个整数的数组，给定一个整数，要求查找数组中与之最接近的数字？

命题三：
已知1000个Point（包含X与Y坐标）结构的数组，给定一个Point，要求查找数组中与之最接近（比如：欧氏距离最短）的点。

命题四：
已知1,000,000个向量，每个向量为128维；给定一个向量，要求查找数组中与之最接近的K个向量

对于命题一，如果不考虑桶式、哈希等方式，常用的方法应该是排序后，使用折半查找。对于命题二，与命题一类似，比较折半查找得出的结果，以及附近的各一个元素，即可。整个过程相当于是把这个包含1000个数组的数据结构做成一颗二叉树，最后只需比较叶子节点与其父节点即可。对于命题三、四其中命题三和四就是所谓的Nearest Neighbor问题。一种近似解决的方法就是KD-TREE

高维向量的KNN检索问题，在图像等多媒体内容搜索中是相当关键的。关于高维向量的讨论，网上资料比较少；在此，我将一些心得分享给大家。
与二叉树相比，KD-TREE也采用类似的划分方式，只不过树中的各节点均是高维向量，因此划分的方式，采用随机或指定的方式选取一个维度，在该指定维度上进行划分；整体的思想就是采用多个超平面对数据集空间进行两两切分，这一点，有点类似于数据挖掘中的决策树。

一个运用KD-TREE分割二维平面的DEMO如下：



KD-Tree build的代码如下：

使用KD-TREE，经过一次二分查找可以获得Query的KNN（最近邻）贪心解，代码如下：


可以用如下代码进行测试：
public static void main(String args[]){    Clusterable clusters[] = new Clusterable[10];    clusters[0] = new Point(0,0);    clusters[1] = new Point(1,2);    clusters[2] = new Point(2,3);    clusters[3] = new Point(1,5);    clusters[4] = new Point(2,5);    clusters[5] = new Point(1,1);    clusters[6] = new Point(3,3);    clusters[7] = new Point(0,2);    clusters[8] = new Point(4,4);    clusters[9] = new Point(5,5);    ClusterKDTree tree = new ClusterKDTree(clusters,true);    //tree.print();    Clusterable c = tree.restrictedNearestNeighbor(new Point(4,4),1000);    System.out.println(c);}