拟阵约束下最大化子模函数的模型及其算法的 一种熵聚类方法

《拟阵约束下最大化子模函数的模型及其算法的 一种熵聚类方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerScienceandApplication计算机科学与应用,2017,7(10),994-1001 PublishedOnlineOctober2017inHans.http://www.hanspub.org/journal/csa https://doi.org/10.12677/csa.2017.710112AnEntropyClusteringMethodfortheModel andItsAlgorithmoftheMaximizinga SubmodularFunctionSubjecttoaMa

2、troidConstraintGuohongLiang1,2,YingLi1,MengYe3,BingjieLi21SchoolofComputerScience,NorthwesternPolytechnicalUniversity,Xi’anShaanxi 2SchoolofScience,AirForceEngineeringUniversity,Xi’anShaanxi 3The94826thMilitaryForces,ShanghaiReceived:Oct.6th,2017;accepted:Oct.19th,

3、2017;published:Oct.24th,2017AbstractThispaperproposesanewclusteringobjectivefunctionwithinformationentropy,whichiscom- posedofentropyrateofrandompathbasedongraphtheoryandbalanceitem.Entropyrateis conducivetocompactanduniformclustering,thebalancefunctionencouragesob

4、jectswithhigh similaritytocluster,andpunishesthoseobjectswithlowsimilarity.First,theweightedundirected graphassociatedwithdataisconstructed,anditisfoundthatthisstructureinducesamatroid,a combinationofthestructureoflinearindependentconceptinvectorspace.Then,themodel

5、of whichismaximizingasubmodularfunctionundertheconstraintsofthematroidisobtained.Fi- nally,accordingtothemonotonicity,incrementandsubmodularoftheobjectivefunction,aneffi- cientgreedyalgorithmisdevelopedanditsperformanceguaranteeisdiscussed.KeywordsClustering,GraphT

6、heory,InformationTheory,SubmodularFunction,DiscreteOptimization拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法梁国宏1,2，李映1，叶萌3，李炳杰21西北工业大学计算机学院，陕西西安 2空军工程大学理学院，陕西西安 394826部队，上海文章引用:梁国宏,李映,叶萌,李炳杰.拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法[J].计算机 科学与应用,2017,7(10):994-1001.DOI:10.12677/csa.2017.710112梁国宏

7、等收稿日期：2017年10月6日；录用日期：2017年10月19日；发布日期：2017年10月24日摘要本文提出了一个新的带有信息熵的聚类目标函数，它是由基于图论的随机路径的熵率和平衡项两部分组 成。熵率有利于形成紧凑和均匀的聚类，平衡函数鼓励相似度比较高的对象才能聚类，并惩罚那些相似度比较低的对象。首先构造了与数据关联的赋权无向图，并发现这种构造诱导出一个拟阵，它是一个组 合在向量空间中推广线性独立概念的结构。接着得到了拟阵约束下最大化子模函数的模型。最后根据目 标函数的单调性、递增性和下模性，开发了一个高效的贪婪算法并讨

8、论了它的性能保证。最后根据数值实验，与已有的算法做了比较，说明了该算法的有效性。关键词聚类，图理论，信息理论，子模函数，离散优化Copyright©2017byauthorsandHansPublishersInc.ThisworkislicensedundertheCreativeCom