聚类评价的研究与应用

《聚类评价的研究与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京航空航天大学硕士学位论文聚类评价的研究与应用姓名：宰云峰申请学位级别：硕士专业：计算机软件与理论指导教师：王建东20081201南京航空航天大学硕士学位论文摘要聚类是数据挖掘中一项重要的研究课题，在数据挖掘、模式识别、统计数据分析、自然语言理解等领域都有广泛的应用前景。聚类评价指标对衡量一个聚类的优劣有着重要作用，聚类评价可以检测聚类的结果是否符合“同组数据相似，不同组数据不相似”的要求。现有的聚类评价指标通常都基于统计理论或模糊理论。受到基础理论的限制，在一些特殊场合，这些指标不能对聚类进行正

2、确的评估。本文提出了一个通用的聚类评价指标。通过把相似性定义成数据集上的二元关系，聚类被描述成Kripke结构。用原子公式表示每个簇，聚类的结果可以用一组逻辑公式来表示。根据最小描述长度原则，聚类评价指标由这种表示方式的准确性和复杂性构成。由于这种新的评价指标对相似性没有任何附加的限制，它较之现有的评价指标更为通用，因为那些指标往往都默认了某种相似性度量方式。本文还通过实验对新旧指标进行了对比。实验结果表明，这种新的评价指标在一般情况下与大多数评价指标一致，而在一些类似“双环”的特殊情况下比现有评价

3、方式更有效。航班延误一直是困扰航空公司和旅客的一大难题。航班延误预警近年来成为研究的热点。每个航班的记录可以看成是一个样本，估算各个样本的概率分布函数对于航班延误预警很重要。根据数据挖掘基本理论，样本不能太小，然而在实际应用中很难获得足够大的样本。有时太严格的收集样本条件会导致存在许多相似的小样本，如果放宽收集样本的条件，这些相似的小样本就可能被合并。因此，从两个根据相似性来将数据分组的过程开始，合并小样本的过程实际上就是聚类过程。为了合并样本，本文使用一个基于k-平均的独立于相似性的聚类算法。由于

4、k-平均算法需要输入参数即聚类数目k，本文使用上述的通用聚类评价指标对一些聚类参数下的聚类结果进行评价，并且从中选择一个局部最优的结果。最后使用该聚类算法将1516个航班样本记录合并为4个大样本。实验表明合并对于得到样本的概率分布是有效的，合并样本得到的先验概率可以被用来对航班延误预警。关键词：数据挖掘，机器学习，聚类，聚类评价，相似性，小样本合并I聚类评价的研究与应用AbstractClusteringisanimportantresearchtopicindatamining.Ithaswide

5、applicationprospectindatamining,patternanalysis,statisticaldataanalysis,naturallanguageunderstanding.Theclustervalidityindicesplayanimportantroleinmeasuringtheeffectofclustering.Theclustervalidityindexes,whichareusedtocheckwhethertheresultofclusterings

6、atisfiestherequirementthat"similarinsamegroup,dissimilarindifferentgroup",arerequiredtomeasureclusteringresults.Mostofcurrentindexesarebasedonstatisticaltheoryandfuzzytheory.Limitedbythebasictheories,theseindexeswouldgivesomeincorrectindicationinsomesp

7、ecialcases.Inthispaper,anewindexofclusteringvalidityindexwhichisbasedonthetheoryofmodallogicispresented.TheclusteringisdescribedbyKripkestructures,wherethesimilarityisdefinedasabinaryrelationonthedataset.Eachclusterisrepresentedbyapropositionalsentence

8、sothattheresultofclusteringcanberepresentedbylogicalformulas.Accordingtominimumdescriptionlengthprinciple,theclusteringvalidityindexisbuiltbyveracityandcomplexityoftherepresentation.Sincethisnewindeximposesnoadditionalrestrictiveconditi