基于k-d树的k-means聚类方法

在直接k-means算法的基础上提出了一种新的基于k-d树的聚类方法。通过把所有的对象组织在一棵k-d树中，可以高效地发现给定原型的所有最近邻对象。利用的主要思想是：在根结点，所有的聚类中心(或称为候选原型)都是所有对象的最近邻候选集合，对于根结点的子结点，通过简单几何约束来剪枝该候选集，这种方法可以被递归使用。使用基于k-d树的方法可以使直接k-means算法的总体性能提高一到两个数量级。

K-means clustering algorithm based on k-d tree

A novel algorithm for performing direct k-means clustering is presented based on k-d tree. It organizes all the patterns in a k-d tree that all the patterns can be found which are closest to a given prototype efficiently. The main idea behind this approach is as follows. All the prototypes are potential candidates for the closest prototype at the root level. For the children of the root node, pruning the candidate set by using simple geometrical constraints, this approach can be applied recursively. The algorithm based on k-d tree can improve the overall performance of direct k-means clustering algorithm by an order to two orders of magnitude.