基于模态代表点的聚类评价方法

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (8): 1997-2002.

基于模态代表点的聚类评价方法

吕宗磊¹, 王建东², 徐涛³

1. 中国民航大学计算机科学与技术学院, 天津, 300100;
2. 南京航空航天大学信息科学与技术学院, 江苏, 南京, 210016

收稿日期:2008-03-13 修回日期:2008-09-05 出版日期:2009-08-20 发布日期:2010-01-03
作者简介:吕宗磊(1981- ),男,讲师,博士,主要研究方向为机器学习与知识工程.E-mail:z.ray@163.com
基金资助:
国家高技术研究发展计划(863计划)(2006AA12A106)资助课题

New clustering validity index based on modal representatives

LÜ Zong-lei¹, WANG Jian-dong², XU Tao³

1. Coll. of Computer Science and Technology, Civil Aviation Univ. of China, Tianjin 300100, China;
2. Coll. of Information Science and Technology, Nanjing Univ. of Aeronautics and Astronautics, Nanjing 210016, China

Received:2008-03-13 Revised:2008-09-05 Online:2009-08-20 Published:2010-01-03

摘要/Abstract

摘要： 提出了一种新的聚类评价方法,该方法以聚类的代表点表示法为基础,在经典方法上做出了改进.首先将聚类结果对应于模态逻辑中Kripke结构;然后利用模态逻辑中语法与语义之间的对应性选取了相应的公理系统.通过公式之间的蕴涵关系,选择一组极少的数据点来表示聚类结果的各种信息,形成聚类的模态代表点.在此基础上,给出了相应的聚类评价方法.这种方法除了可以评价聚类结果的优劣,还可以分析出簇的形态.实验表明,与一些常用聚类评价指标相比,这种评价方法更具通用性.

Abstract: A new clustering validity index based on the improved classic method of representatives is presented.First of all,the clustering result is corresponding to the Kripke structure.The relevant system of axioms is chosen by the correspondence between the syntax and semantics of modal logic.Furthermore,a minimal data set which can describe all clustering information is constructed by the implication during formulas.Finally,the validity index is calculated based on the above set.In addition to the validity of a clustering result,this method can also show the structure information of each cluster.Experiments show that this new index has more universal than the current clustering validity indexes.

中图分类号:

TP18

吕宗磊, 王建东, 徐涛. 基于模态代表点的聚类评价方法 [J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 1997-2002.

LÜ Zong-lei, WANG Jian-dong, XU Tao. New clustering validity index based on modal representatives [J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 1997-2002.

参考文献

[1] Yang Xulei,Song Qing.Cao Aize.A new cluster validity for data clustering[J].Neural Processing Letters,2006,23(3):325-344.
[2] Lu Zonglei.Wang Jiandong,Zai Yunfeng.A new technology for combining small samples based on clustering and its applications[C]//Proc.of the International Symposium on Knowledge Acquisition and Modeling.Wuhan,China:IEEE CS Press,2008:735-740.
[3] Lu Zonglei,Wang Jiandong,Zheng Guansheng.A new method to alarm large scale of flights delay based on machine learning[C]//Proc.of the International Symposium on Knowledge Acquisition and Modeling.Wuhan,China:IEEE CS Press,2008:589-592.
[4] Kovacs Ferenc,Legany Csaba,Babos Attila.Cluster validity measurement techniques[C]//Proc.of the 6th International Symposium of Hungarian Researchers on Computational Intelligence,2005.
[5] 张惟皎,刘春煌,李芳玉.聚类质量的评价方法[J].计算机工程,2005,31(20):10-12.
[6] Greene Derek,Cunningham Padraig.Producing accurate interpretable clusters from high-dimensional data[R].Department of Computer Science,Trinity College Dublin,2005.
[7] Guha Sudipto,Rastogi Rajeev,Shim Kyuseok.CURE:an efficient clustering algorithm for large databases[C]//Proc.of ACM SIGMOD International Conference on Management of Data.New York,1998:73-84.
[8] Hughes G E,Cresswell M J.A new introduction to modal logic[M].Routledge,London and New York,1996.
[9] Witten I H,Frank E.Data mining:practical machine learning tools and techniques[M].San Francisco:Morgan Kaufmann,2005.
[10] 吕宗磊,王建东,李莹,等.一种基于模态逻辑的聚类评价方法[J].计算机研究与发展,2008,45(9):1477-1486.
[11] Dunn J C.Well separated clusters and optimal fuzzy partitions[J].Journal of Cybernetica,1974,4(1):95-104.
[12] Davies D L,Bouldin D W.A cluster separation measure[J].IEEE Trans.on Pattern Analysis and Machine Intelligence,1979,1(4):224-227.
[13] Chou C H,Su M C,Lai E.A new cluster validity measure and its application to image compression[J].Pattern Analysis and Applications,2004,7(2):205-220.
[14] Bezdek J C.Cluster validity with fuzzy sets[J].Journalof Cybernetics,1974,3(3):58-72.
[15] 吕宗磊,王建东.一种基于多维空间超球体的快速聚类算法[J].南京航空航天大学学报,2006,38(6):706-711.