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

K-means clustering algorithm based on k-d tree

作　　者：孙总参[1] 陶兰[1] 齐建东[2] 王保迎[1] 

机构地区：[1]中国农业大学信息与电气工程学院,北京100083 [2]北京林业大学信息学院,北京100083

出　　处：《计算机工程与设计》2004年第11期2054-2057,共4页Computer Engineering and Design

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

关 键 词：K-D树 K-MEANS算法 候选集 K-MEANS聚类 对象组 结点 递归 类方 根结 方法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP181[自动化与计算机技术—计算机科学与技术]