层次聚类算法地有效性研究.PDFVIP

　第４０卷　第５期 山　东　大　学　学　报　（工　学　版） ２０１０年１０月　 　 　　 Ｖｏｌ．４０　 Ｎｏ．５　　 　ＪＯＵＲＮＡＬＯＦＳＨＡＮＤＯＮＧＵＮＩＶＥＲＳＩＴＹ（ＥＮＧＩＮＥＥＲＩＮＧＳＣＩＥＮＣＥ） Ｄｏｃ．２０１０　 　文章编号：１６７２３９６１（２０１０）０５０００１０５ 层次聚类算法的有效性研究 １ １ ２ 胡晓庆 ，马儒宁 ，钟宝江 （１．南京航空航天大学理学院，江苏 南京２１１１００； ２．苏州大学计算机科学与技术学院，江苏 苏州２１５００６） 摘要：针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的聚类结果，在深入研究聚类有效 性的基础上，通过模糊相似性关系刻画聚类的类内致密性和类间分离性，建立了一个新的聚类有效性函数。在人 工和实际数据集上的实验都表明了该有效性函数具有良好的性能。 关键词：层次聚类；阈值；聚类有效性 中图分类号：Ｏ２３５；ＴＰ３９１　　　文献标志码：Ａ Ｓｔｕｄｙｏｎｖａｌｉｄｉｔｙｏｆｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ １ １ ２ ＨＵＸｉａｏｑｉｎｇ，ＭＡＲｕｎｉｎｇ ，ＺＨＯＮＧＢａｏｊｉａｎｇ （１．ＣｏｌｌｅｇｅｏｆＳｃｉｅｎｃｅ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＡｅｒｏｎａｕｔｉｃｓａｎｄＡｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ２１１１００，Ｃｈｉｎａ； ２．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＳｏｏｚｃｈｏｗＵｎｉｖｅｒｓｉｔｙ，Ｓｕｚｈｏｕ２１５００６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎａｌｌｕｓｉｏｎｔｏｃｈｏｏｓｅｔｈｅｍｏｓｔｓａｔｉｓｆａｃｔｏｒｙｃｌａｓｓｉｆｉｃａｔｉｏｎｆｒｏｍｓｅｖｅｒａｌｐａｒｔｉｔｉｏｎｉｎｇｒｅｓｕｌｔｓｏｆｔｈｅｄａｔａｓｅｔｏｂ ｔｅｉｎｅｄｂｙｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ，ａｆｔｅｒｄｅｅｐｌｙｓｔｕｄｙｉｎｇｃｌｕｓｔｅｒｉｎｇｖａｌｉｄｉｔｙｉｎｄｉｃｅｓ，ａｎｅｗｃｌｕｓｔｅｒｖａｌｉｄｉｔｙｉｎｄｅｘｗａｓｅｓｔａｂ ｌｉｓｈｅｄｖｉａｄｅｓｃｒｉｂｉｎｇｃｏｍｐａｃｔｎｅｓｓａｎｄｓｅｐａｒａｔｉｏｎｕｓｉｎｇｔｈｅｆｕｚｚｙｓｉｍｉｌａｒｉｔｙｍａｔｒｉｘｏｆｔｈｅｄａｔａｓｅｔ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅ ｓｕｌｔｓｏｎｂｏｔｈｓｙｎｔｈｅｔｉｃａｎｄｒｅａｌｗｏｒｌｄｄａｔａｓｅｔｓｈａｖｅｄｅｍｏｎｓｔｒａｔｅｄｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｎｅｗｃｌｕｓｔｅｒｖａｌｉｄｉｔｙｉｎｄｅｘ． Ｋｅｙｗｏｒｄｓ：ｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ；ｔｈｒｅｓｈｏｌｄ；ｃｌｕｓｔｅｒｖａｌｉｄｉｔｙｉｎｄｅｘ 据集的多种分类结果都展现了出来，但是从算法所 ０　引言 得到的各类分类结果中获得用户最满意的分类情况 却成了一个问题。根据模糊集理论，系统树结构的 聚类分析作为无监督模式识别的一个重要分支 每一层是由阈值λ决定的。因此，最优聚类结果的 已经成为现代数据分析的一个重要工具。所谓聚类 选取问题就是最优阈值的选取问题。对于最优阈值 就是把一个没有类别标记的样本集按照某种准则划 的选取问题，使用Ｆ统计量是研究者们比较认可的 分成若干子集（类），使相似的