层次聚类算法的有效性研究

《层次聚类算法的有效性研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第４０卷第５期山东大学学报（工学版）２０１０年１０月Ｖｏｌ．４０Ｎｏ．５ＪＯＵＲＮＡＬＯＦＳＨＡＮＤＯＮＧＵＮＩＶＥＲＳＩＴＹ（ＥＮＧＩＮＥＥＲＩＮＧＳＣＩＥＮＣＥ）Ｄｏｃ．２０１０文章编号：１６７２３９６１（２０１０）０５０００１０５层次聚类算法的有效性研究１１２胡晓庆，马儒宁，钟宝江（１．南京航空航天大学理学院，江苏南京２１１１００；２．苏州大学计算机科学与技术学院，江苏苏州２１５００６）摘要：针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的聚类结果，在深入研究聚类有效性的基础上，通过模糊相似性关系刻画聚类

2、的类内致密性和类间分离性，建立了一个新的聚类有效性函数。在人工和实际数据集上的实验都表明了该有效性函数具有良好的性能。关键词：层次聚类；阈值；聚类有效性中图分类号：Ｏ２３５；ＴＰ３９１文献标志码：ＡＳｔｕｄｙｏｎｖａｌｉｄｉｔｙｏｆｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ１１２ＨＵＸｉａｏｑｉｎｇ，ＭＡＲｕｎｉｎｇ，ＺＨＯＮＧＢａｏｊｉａｎｇ（１．ＣｏｌｌｅｇｅｏｆＳｃｉｅｎｃｅ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＡｅｒｏｎａｕｔｉｃｓａｎｄＡｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ２１１１００，Ｃｈｉｎａ；２．Ｓｃｈｏ

3、ｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＳｏｏｚｃｈｏｗＵｎｉｖｅｒｓｉｔｙ，Ｓｕｚｈｏｕ２１５００６，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｉｎａｌｌｕｓｉｏｎｔｏｃｈｏｏｓｅｔｈｅｍｏｓｔｓａｔｉｓｆａｃｔｏｒｙｃｌａｓｓｉｆｉｃａｔｉｏｎｆｒｏｍｓｅｖｅｒａｌｐａｒｔｉｔｉｏｎｉｎｇｒｅｓｕｌｔｓｏｆｔｈｅｄａｔａｓｅｔｏｂｔｅｉｎｅｄｂｙｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ，ａｆｔｅｒｄｅｅｐｌｙｓｔｕｄｙｉｎｇｃｌｕｓｔｅｒｉｎｇｖａｌｉｄｉｔｙｉｎｄｉｃｅｓ，ａｎｅｗｃｌｕｓｔｅｒｖａｌｉｄｉ

4、ｔｙｉｎｄｅｘｗａｓｅｓｔａｂｌｉｓｈｅｄｖｉａｄｅｓｃｒｉｂｉｎｇｃｏｍｐａｃｔｎｅｓｓａｎｄｓｅｐａｒａｔｉｏｎｕｓｉｎｇｔｈｅｆｕｚｚｙｓｉｍｉｌａｒｉｔｙｍａｔｒｉｘｏｆｔｈｅｄａｔａｓｅｔ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎｂｏｔｈｓｙｎｔｈｅｔｉｃａｎｄｒｅａｌｗｏｒｌｄｄａｔａｓｅｔｓｈａｖｅｄｅｍｏｎｓｔｒａｔｅｄｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｎｅｗｃｌｕｓｔｅｒｖａｌｉｄｉｔｙｉｎｄｅｘ．Ｋｅｙｗｏｒｄｓ：ｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ；ｔｈｒｅｓｈｏｌｄ；ｃｌｕｓｔｅ

5、ｒｖａｌｉｄｉｔｙｉｎｄｅｘ据集的多种分类结果都展现了出来，但是从算法所０引言得到的各类分类结果中获得用户最满意的分类情况却成了一个问题。根据模糊集理论，系统树结构的聚类分析作为无监督模式识别的一个重要分支每一层是由阈值λ决定的。因此，最优聚类结果的已经成为现代数据分析的一个重要工具。所谓聚类选取问题就是最优阈值的选取问题。对于最优阈值就是把一个没有类别标记的样本集按照某种准则划的选取问题，使用Ｆ统计量是研究者们比较认可的分成若干子集（类），使相似的样本尽可能归为一方法。当然随着对模糊数学研究的深入，近几年来类，而不相似的样本尽量

6、划分到不同的类中。根据也有新的解决方法。Ｎａｓｉｂｏｖ和Ｕｌｕｔａｇａｙ提出了一聚类形成方式的不同，聚类方法可以分为两大类：层个对于噪声更为稳定的ＦＪＰ（ｆｕｚｚｙｊｏｉｎｔｐｏｉｎｔｓ）算［３］次聚类算法和基于划分的聚类算法。法。该算法的基本思想是根据样本点与样本点层次聚类算法，特别是凝聚式算法在计算上简之间的距离计算模糊关系矩阵，对于某一α∈（０，单、快捷，而且能够得到相近的最终结果，所以层次１］，建立α截集和等价类。此时，这些α等价类决［１２］聚类算法的应用较为广泛。虽然该类算法把数定了模糊聚类的每个α截集。但并非对每个

7、α∈收稿日期：２０１００４２３基金项目：国家自然科学基金资助项目（６０７０５０１４）；航空科学基金资助项目（２００９ＺＨ５２０６９）作者简介：胡晓庆（１９８５），山东临沂人，硕士研究生，主要研究方向为模糊聚类分析．Ｅｍａｉｌ：ｓｄ－ｈｘｑ＠１６３．ｃｏｍ通讯作者：马儒宁（１９７６），山东济宁人，博士，副教授，主要研究方向为神经网络，图像处理，聚类分析．Ｅｍａｉｌ：ｍｒｎｉｎｇ＠ｎｕａａ．ｅｄｕ．ｃｎ２山东大学学报（工学版）第４０卷（０，１］都计算α截集，而是只计算影响聚类个数的两类，第二步中分成三类，这样一直进行下去直

8、到最α对应的α截集。最终的截集是由α取值区间上的后一步分成ｎ类。在每一步中选择一个使得相异程最大值确定的。ＦＪＰ算法已被证明能成功检测团装度最小的分裂。运用这种方法，可以得到一个相反数据集及流形状数据集，既使添加噪声点