一种带线性约束的最小生成树聚类方法
|
摘要
提出了一种带线性约束的最小生成树聚类方法,目标是聚合在空间上大致呈线性密集分布的对象.方法的基本过程是,用线性率阈值约束最小生成树打断边的选取,尽可能使每次打断都能割取出一个满足线性率大于该阈值的子树(类),直至所有合适子树都被割取,残余子树则被抛弃.对自构建数据和真实世界中地震数据的聚类实验证明了该方法的有效性和实用性.
In this paper, a MST based clustering method with linear constraint is proposed, whose aim is to clustering the objects distributing densely and linearly in space. The algorithm restricts the selection of the splitting edges of the MST with linear threshold, which tries to cut off one sub-tree whose linear rate exceeds the threshold every splitting. The algorithm will stop when all the suitable sub-trees are cut off, and the remaining sub-trees are discarded. The effectiveness and practicality of our methods are validated by clustering the constructed data and the earthquake data.
In this paper, a MST based clustering method with linear constraint is proposed, whose aim is to clustering the objects distributing densely and linearly in space. The algorithm restricts the selection of the splitting edges of the MST with linear threshold, which tries to cut off one sub-tree whose linear rate exceeds the threshold every splitting. The algorithm will stop when all the suitable sub-trees are cut off, and the remaining sub-trees are discarded. The effectiveness and practicality of our methods are validated by clustering the constructed data and the earthquake data.
引文
[1] Jain A K, Dubes R C. Algorithms for Clustering Data. New Jersey: Prentice-Hall Inc, 1996
[2] Ester M, Kriegel H P, Sander J, Xu X W. Clustering for Mining in Large Spatial Databases. Knstliche Intelligenz, 1998, 12(1) : 18-24
[3] 国家地震局.中国地震烈度区划图(1990) 概论.北京:地震出版社.1996
[4] Zahn C T. Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters. IEEE Trans on Computers, 1971, C-20(1) : 68-86
[5] Tung A K H, Han J W, Lakeshmanan L V S, Ng R T. Constraint-Based Clustering in Large Databases. http://www.cs.sfu.ca/pub/cs/techreports/2000/CMPT2000-05． pdf
[6] 沈清,汤霖.模式识别导论.长沙:国防科技大学出版社,1991
[7] 严蔚敏,吴伟民.数据结构.北京:清华大学出版社,1997
[8] 王光荣,顾乃杰.在消息传递并行机上的高效的最小生成树算法.软件学报,2000,11(7) :889-898
[9] Fehlauer J, Eisenstein B A. Structural Editing by a Point Density Function. IEEE Trans on Systems, Man and Cybernetics, 1978, SMC-8(5) : 362-370
[10] Koontz W L G, Narendra P M, Fukunaga K. A Graph-Theoretic Approach to Nonparametric Cluster Analysis. IEEE Trans on Computers, 1976, C-25(9) : 936-944
[11] Mizoguchi R, Shimura M. A Nonparametric Algorithm for Detecting Clusters Using Hierarchical Structure. IEEE Trans on Pattern Analysis and Machine Intelligence, 1980, Paml-2(4) : 292-300
[12] 裴韬.中国及邻区大型地震数据库时空特征分析及其方法研究博士后出站报告,中国科学院地理所,2000
[2] Ester M, Kriegel H P, Sander J, Xu X W. Clustering for Mining in Large Spatial Databases. Knstliche Intelligenz, 1998, 12(1) : 18-24
[3] 国家地震局.中国地震烈度区划图(1990) 概论.北京:地震出版社.1996
[4] Zahn C T. Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters. IEEE Trans on Computers, 1971, C-20(1) : 68-86
[5] Tung A K H, Han J W, Lakeshmanan L V S, Ng R T. Constraint-Based Clustering in Large Databases. http://www.cs.sfu.ca/pub/cs/techreports/2000/CMPT2000-05． pdf
[6] 沈清,汤霖.模式识别导论.长沙:国防科技大学出版社,1991
[7] 严蔚敏,吴伟民.数据结构.北京:清华大学出版社,1997
[8] 王光荣,顾乃杰.在消息传递并行机上的高效的最小生成树算法.软件学报,2000,11(7) :889-898
[9] Fehlauer J, Eisenstein B A. Structural Editing by a Point Density Function. IEEE Trans on Systems, Man and Cybernetics, 1978, SMC-8(5) : 362-370
[10] Koontz W L G, Narendra P M, Fukunaga K. A Graph-Theoretic Approach to Nonparametric Cluster Analysis. IEEE Trans on Computers, 1976, C-25(9) : 936-944
[11] Mizoguchi R, Shimura M. A Nonparametric Algorithm for Detecting Clusters Using Hierarchical Structure. IEEE Trans on Pattern Analysis and Machine Intelligence, 1980, Paml-2(4) : 292-300
[12] 裴韬.中国及邻区大型地震数据库时空特征分析及其方法研究博士后出站报告,中国科学院地理所,2000
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心