一种基于层次距离计算的聚类算法_彭京论述.pdf

第 30 卷 　第 5 期 计 　　算 　　机 　　学 　　报 Vo l. 30 N o. 5 2007 年 5 月 CH IN ESE JOU RNA L OF COM PUTE RS M ay 2007 　 一种基于层次距离计算的聚类算法 1), 2), 3) 2) 3) 3) 2) 彭 　京 　唐常杰 　程温泉 　石葆梅 　乔少杰 1)(北京大学信息科学技术学院 　北京 　100871) 2)(四川大学计算机学院　成都 　610065) 3)(成都市公安局科技处　成都 　610017) 摘　要 　针对广泛存在的层次编码型数据类型 , 提出了层 次距离的新概念 , 证明了 相关的数学 性质 , 并在此基础 上 提出并实??了新的基 于层 次 距离 计算 的 聚类 算 法 HDCA(Hierarchy Distance Computing based clustering A lg o- rithm). 新方法克服了传统聚类算法标称型计算的缺陷 , 提高了聚类精度. 针对聚 类算法的中心点问题 , 提出了相 应 的层次编码型数据的快速处理算法 , 并从理论上 证明了算法的 正确性. 实验表 明 , 对比朴 素处理算 法 , HDCA 的 性 能明显提高. 新算法已经应用到警用流动人口分 析当中 , 取得了良好效果. 关键词 　聚类 ;层次距离 ;层次编码变量 ;k-中心 ;数据挖掘 中图法分类号 T P 311 A Hierarchy Distance Computing Based Clustering Algorithm PENG Jing1), 2), 3) 　TANG Chang-Jie2) 　CH ENG Wen-Quan3) 　SH I Bao-Mei3) 　Q IAO Shao-Jie2) 1)(S chool o f E lectronics Eng ineerin g and Comp uter S cience , Peking Un iversity , Beijing 　100871) 2)(S chool o f Comp uter S cience , S ich uan Un iversity , Cheng du 　610065) 3)(Dep artment o f S cience and Technolog y , Chen gd u Municipa l Public S ecurity B ureau , Cheng du 　610017) Abstract 　 To deal w ith the hierarchy coding data structure w idely e xisted in applicatio n , this pa- per proposes a new conception of hierarchy distance and pro ves its m athematical pro perties. It al- so proposes and implem ents a new clustering algo rithm-H DCA (H ierarchy Distance Co mputing based clustering Alg orithm) based