引入共享近邻加权图的Chameleon算法_薛文娟

《引入共享近邻加权图的Chameleon算法_薛文娟》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、JournalofComputerApplicationsISSN1001-90812012-10-01计算机应用，2012，32(10):2884－2887CODENJYIIDUhttp://www．joca．cn文章编号:1001－9081(2012)10－2884－04doi:10．3724/SP．J．1087．2012．02884引入共享近邻加权图的Chameleon算法1，2*1，21，2薛文娟，刘培玉，刘栋(1．山东师范大学信息科学与工程学院，济南250014;2．山东省分布式计算机软件新技术重点实验室，济南250014)(*通信作者电子邮箱xwj

2、198734@163．com)摘要:针对Chameleon算法中采用距离函数度量数据点间的相似度，导致距离相近的两个点可能仅拥有很少的共同特征，最小二分实际操作困难，合并时需要人工指定阈值以及一旦合并完成后不能撤销的问题，对Chameleon算法进行改进，提出一种引入共享近邻加权图(WSnnG)的Chameleon算法。该算法以数据对象间的共享近邻数来衡量相似度，进一步构造WSnnG，再利用网络模块性评价函数指导最小二分，然后以结构等价相似度作为合并的依据，最后通过引入内聚度度量函数解决合并后不能撤销的问题。在UCI数据集及4个二维人造数据集上的实验结果表明，

3、该算法在聚类精度和运行时间方面具有更好的效果。关键词:共享近邻加权图;最小二分;网络模块性评价函数;结构等价相似度;内聚度度量函数中图分类号:TP18;TP309文献标志码:AImprovedChameleonalgorithmusingweightednearestneighborsgraph1，2*1，21，2XUEWen-juan，LIUPei-yu，LIUDong(1．SchoolofInformationScienceandEngineering，ShandongNormalUniversity，JinanShandong250014，China;2

4、．ShandongProvincialKeyLaboratoryforDistributedComputerSoftwareNovelTechnology，JinanShandong250014，China)Abstract:FortheChameleonalgorithmusingdistancefunctiontomeasurethesimilarityofdatapoints，resultinginthatthetwoproximatepointsmayonlyhaveafewcommoncharacteristics，minimumhalfhaspra

5、cticaldifficulties，themergerneedsartificialspecifiedthresholdvalue，andcannotberevokedoncethemergeriscompleted．Therefore，theauthorsimprovedChameleonalgorithmandproposedanewChameleonalgorithmusingWeightedSharednearestneighborsGraph(WSnnG)．Firstly，itmeasuredthesimilaritybyusingthenumbe

6、rofsharednearestneighbors，furtherconstructedtheWSnnG．Secondly，itresolvedminimumhalfthroughtheintroductionofthenetworkmoduleevaluationfunction，thenaccordingtothestructuralequivalencesimilaritydegreeasabasisformerger．Finally，anewcohesionmeasurewasdiscussedtosolveproblemsthatcannotbere

7、vokedafterthemerger．TheexperimentalresultsonUCIdatasetsandfourtwo-dimensionalartificialdatasetsshowthattheimprovedChameleonalgorithmusingWSnnGhasgreatlyimprovedinclusteringaccuracyandrunningtime．Keywords:WeightedSharednearestneighborsGraph(WSnnG);minimumhalf;networkmoduleevaluationf

8、unction;structurale