一种带控制节点的最小生成树聚类方法

英文篇名：A MST Based Clustering Method with Controlling Vertexes
中文刊名：中国图象图形学报
英文刊名：Journal of Image and Graphics
作者：汪闽 ; 周成虎 ; 裴韬 ; 韩志军 ; 秦承志 ; 蔡强
英文作者：WANG Min ; ZHOU Cheng-hu ; PEI Tao ; HAN Zhi-jun ; QIN Cheng-zhi ; CAI Qiang (State Key Laboratory of Resources and Environment Information System ; Chinese Academy of Sciences ; Beijing 100101)
中文关键词：聚类 ; 控制节点 ; 最小生成树
英文关键词：Clustering ; Controlling vertex ; Minimum cost spanning tree
出版日期：2002-08-25
机构：中国科学院资源与环境信息系统国家重点实验室,中国科学院资源与环境信息系统国家重点实验室,中国科学院资源与环境信息系统国家重点实验室,中国科学院资源与环境信息系统国家重点实验室,中国科学院资源与环境信息系统国家重点实验室,中国科学院资源与环境信息系统国家重点实验室北京100101 ,北京100101 ,北京100101 ,北京100101 ,北京100101 ,北京100101
年：2002
期：08
出版单位：中国图象图形学报

摘要

综合考虑对象间相对距离和高等级对象对低等级对象的集聚效应这两种聚类影响因素 ,提出了一种带控制节点的最小生成树聚类方法 .该方法用聚类对象间距离为权构建一棵最小生成树 ,将树中高等级节点作为分割最小树时选取被打断边的控制因素 ,使本次分割而成的两子树都包含控制节点 ,且被打断的边是在此条件下的最长边 ,最终使每棵子树包含且仅包含一个控制节点 .检验自构建数据和地震数据的聚类结果证明 ,该方法在某些情况下能够较好地揭示数据分布的真实规律 .
Taking into consideration the two clustering factors, the mutual distance between clustering objects and the centralizing effects of the higher level objects on the lower, a new clustering method based on minimum cost span tree with control vertexes is proposed. The MST is built based on the power of the clustering objects' mutual distance, and the selecting standard of the splitted edges is controlled by the higher level vertexes. Each splitted edge should be the longest edge under the condition that the two descendant trees must include at least one controlling vertex, and each descendant tree would include one and only one controlling vertex by the end of the algorithm. It has been verified by clustering the data built by ourselves and the earthquake data that this method, with simple input and little intervention, can discover better the true law of data distribution in some cases. To fulfill the needs of data mining, the selecting standard of the controlling vertexes, the 'inconsistent edges' and the efficiency of the algorithm should be improved.

引文

1　AnilK Jain,RichardC Dubes.Algorithms for clustering data[M].NewJersey:Prentice-HallInc,1996:55.
    2　AnthonyK H Tung,JeanHou,JiaweiHan.Spatial clustering inthe presence of obstacles[EB/OL].URL:http:// dbs.cs.sfu.ca,2001-6-5.
    3　吴开统,焦远碧,吕培苓等.地震序列概论[M].北京:北京大学出版社,1990:2.
    4　沈清,汤霖.模式识别导论[M].长沙:国防科技大学出版社,1991:120～121.
    5　严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997:173～176.
    6　王光荣,顾乃杰.在消息传递并行机上的高效的最小生成树算法[J].软件学报,2000,11(7):889～898.
    7　CharlesT Zahn.Graph-theoretical methods for detecting anddescribing gestalt clusters[J].IEEE Transactions onComputers,1971,C-20(1):68～86.
    8　JohnF ehlauer,BruceA Eisenstein.Structural editing by a pointdensity function[J].IEEE Transactions onSystems,Man andCybernetics.1978,sm c-8(5):362～370.
    9　KoontzW L G,NarendraP M,FukunagaK.A graph-theoreticapproach to nonparam etric cluster analysis[J].IEEETransactions onComputers.1976,C-25(9):936～944.
    10RhchiroMizoguchi,MasamichiShimura.A nonparametricalgorithm for detecting clusters using hierarchical structure[J].IEEEE Transactions onPatternAnalysis andMachineIntelligence.1980,Pam1-2(4):292～300.
    11傅征祥.中国大陆地震活动性力学研究[M].北京:地震出版社,1997:5～7.
    12国家地震局.中国地震烈度区划图(1990)概论[M].北京:地震出版社,1996:26～27.
    13裴韬.中国及邻区大型地震数据库时空特征分析及其方法研究[博士后出站报告][R].北京:中科院地理所,2000:23.