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

层次聚类

　第40卷　第5期2010年10月　山　东　大　学　学　报　(工　学　版)

Vol.40　No.5Oct.2010　JOURNALOFSHANDONGUNIVERSITY(ENGINEERINGSCIENCE)

　文章编号:167223961(2010)0520146204

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

胡晓庆,马儒宁

,钟宝江

(1.南京航空航天大学理学院,江苏南京211100;2.苏州大学计算机科学与技术学院,江苏苏州215006)

摘要:针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的聚类结果,性的基础上,通过模糊相似性关系刻画聚类的类内致密性和类间分离性,。在人关键词:层次聚类;阈值;聚类有效性

中图分类号:O235;TP391　　　文献标志码:A

dityofhierarchicalclustering

HUXiao2qing,MARu2ning

,ZHONGBao2jiang

(1.CollegeofScience,NanjingUniversityofAeronauticsandAstronautics,Nanjing211100,China;

2.SchoolofComputerScienceandTechnology,SoozchowUniversity,Suzhou215006,China)

Abstract:Inallusiontochoosethemostsatisfactoryclassificationfromseveralpartitioningresultsofthedatasetob2tainedbyhierarchicalclustering,andafterdeeplystudyingclusteringvalidityindices,anewcluster2validityindexwasestablishedviadescribingcompactnessandseparationusingthefuzzysimilaritymatrixofthedataset.Theexperimentalresultsonbothsyntheticandreal2worlddatasetsdemonstratedtheeffectivenessofthenewcluster2validityindex.

Keywords:hierarchicalclustering;threshold;cluster2validityindex

0　引言

聚类分析作为无监督模式识别的一个重要分支已经成为现代数据分析的一个重要工具。所谓聚类就是把一个没有类别标记的样本集按照某种准则划分成若干子集(类),使相似的样本尽可能归为一类,而不相似的样本尽量划分到不同的类中。根据聚类形成方式的不同,聚类方法可以分为两大类:层次聚类算法和基于划分的聚类算法。

层次聚类算法,特别是凝聚式算法在计算上简单、快捷,而且能够得到相近的最终结果,所以层次

[122]

聚类算法的应用较为广泛。虽然该类算法把数

收稿日期:2010204223

据集的多种分类结果都展现了出来,但是从算法所

得到的各类分类结果中获得用户最满意的分类情况却成了一个问题。根据模糊集理论,系统树结构的每一层是由阈值λ决定的。因此,最优聚类结果的选取问题就是最优阈值的选取问题。对于最优阈值的选取问题,使用F2统计量是研究者们比较认可的方法。当然随着模糊数学研究的深入,近几年来也有新的解决方法。Nasibov和Ulutagay提出了一个对于噪声更为稳定的FJP(fuzzyjointpoints)算[3]

法。该算法的基本思想是根据样本点与样本点之间的距离计算模糊关系矩阵,对于某一α∈(0,1],建立α2截集和等价类。此时,这些α2等价类决定了模糊聚类的每个α2截集。但并非对每个α∈

基金项目:国家自然科学基金资助项目(60705014);航空科学基金资助项目(2009ZH52069);南京航空航天大学基本科研业务费资助项目

(NS2010196)

作者简介:胡晓庆(19852),山东临沂人,硕士研究生,主要研究方向为模糊聚类分析.E2mail:sd-hxq@163.com

3通讯作者:马儒宁(19762),山东济宁人,博士,副教授,主要研究方向为神经网络、图像处理、聚类分析.E2mail:mrning@nuaa.edu.cn

第1页 下一页