一种基于层次距离计算的聚类算法  

A Hierarchy Distance Computing Based Clustering Algorithm

作　　者：彭京[1] 唐常杰[2] 程温泉[3] 石葆梅[3] 乔少杰[2] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]四川大学计算机学院,成都610065 [3]成都市公安局科技处,成都610017

出　　处：《计算机学报》2007年第5期786-795,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(60473071;60473051;60503037);中国博士后科学基金(20060400002);四川省青年科技基金(07ZQ026-055);国家"八六三"高技术研究发展计划项目基金(2006AA01Z230);北京市自然科学基金(4062018)资助.

摘　　要：针对广泛存在的层次编码型数据类型,提出了层次距离的新概念,证明了相关的数学性质,并在此基础上提出并实现了新的基于层次距离计算的聚类算法HDCA(Hierarchy Distance Computing based clustering Algo-rithm).新方法克服了传统聚类算法标称型计算的缺陷,提高了聚类精度.针对聚类算法的中心点问题,提出了相应的层次编码型数据的快速处理算法,并从理论上证明了算法的正确性.实验表明,对比朴素处理算法,HDCA的性能明显提高.新算法已经应用到警用流动人口分析当中,取得了良好效果.To deal with the hierarchy coding data structure widely existed in application, this paper proposes a new conception of hierarchy distance and proves its mathematical properties. It also proposes and implements a new clustering algorithm-HDCA （Hierarchy Distance Computing based clustering Algorithm） based on hierarchy distance. The new algorithm overcomes the shortage of traditional algorithm and improves the precision. The paper also proposes a fast algorithm to compute the median of a hierarchy coding data set, and gives a clear proof of the algorithm. Extensive experiments demonstrate that HDCA is much faster than the naive algorithm to compute the median of hierarchy coding data. The new algorithm has been applied in the data analysis of transient population for public security successfully.

关 键 词：聚类 层次距离 层次编码变量 k-中心 数据挖掘 

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