基于属性扩展图的k-means聚类算法的研究

《基于属性扩展图的k-means聚类算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP301单位代码：10110学号：s20090522中北大学硕硕士士学学位位论论文文基于基于属性扩展图的K-means属性扩聚类算法的研究展图的K-means聚类算法的研究硕士研究生_______任巍英__________指导教师_________高媛________中北学科专业_____计算机软件与理论____大学2012年6月3日图书分类号TP301密级非密UDC硕士学位论文基于属性扩展图的K-means聚类算法的研究任巍英指导教师（姓名、职称）高媛副教授申请学位级别工学硕士专业名称计算机软件与理论

2、论文提交日期2012年4月24日论文答辩日期2012年6月3日学位授予日期________年______月______日论文评阅人张继福李德玉答辩委员会主席李德玉2012年6月3日原创性声明本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名：日期：关于学位论文使用权的说明本人完全了解中北大学有关保

3、管、使用学位论文的规定，其中包括：①学校有权保管、并向有关部门送交学位论文的原件与复印件；②学校可以采用影印、缩印或其它复制手段复制并保存学位论文；③学校可允许学位论文被查阅或借阅；④学校可以学术交流为目的，复制赠送和交换学位论文；⑤学校可以公布学位论文的全部或部分内容（保密学位论文在解密后遵守此规定）。签名：日期：导师签名：日期：基于属性扩展图的K-means聚类算法的研究摘要社团结构是社会网络普遍存在的拓扑特性之一，发现社会网络中的社团结构是复杂网络研究的基础性问题。聚类算法是发现社团结构的一种重要的方法。聚

4、类分析技术在过去的许多年中得到了广泛的研究，其中K-means聚类算法是众多聚类算法中比较经典的一个。K-means聚类算法由于思想简单、时间复杂度小而被广泛的进行了研究与运用，尤其在对大规模数据进行挖掘中，K-means聚类算法具有高效性及可伸缩性。真实网络中，除了数据之间存在的拓扑结构以外，其数据本身存在着各种特殊属性。现存的许多聚类算法仅仅依靠数据间的拓扑结构进行聚类，而很大程度的忽略了数据所具有的特有属性在聚类分析中的作用。本文在分析聚类算法中节点的拓扑结构及特有属性的作用之后，对K-means聚类算法进

5、行改进，提出了一种新的聚类算法-SAK聚类算法。本文的主要研究成果如下：（1）将真实网络用图的模型表示，并根据现实网络的实用性，将节点的属性特性作为节点添加到图中，并根据节点与属性的关系添加相应的边，从而构成属性扩展图。在属性扩展图的基础上，使用随机行走模型对节点的结构及属性相似性进行统一的测量。（2）提出了一种自动更新权重值的方法，在聚类算法不断迭代的过程中，节点边的权重会随之发生变化，随着权重的改变节点间的相似度也会随之改变，这样，不同的属性将会在聚类算法中起到不同的作用。这种改变将会使节点间相似度的测量更加

6、趋于实际，趋于准确。（3）提出基于属性扩展图的K-means聚类算法（SAK），该算法改变K-means算法随机选取初始聚类中心的方法，采用密度函数的方法进行初始聚类中心的选取。并运用两个真实的社会网络对本文所提出的SAK聚类算法进行了验证。关键字：K-means聚类算法，属性扩展图，邻接随机行走距离ResearchontheK-meansClusteringAlgorithmBasedonAttributeAugumentedGraphAbstractCommunitystructureisoneoftheco

7、mmontopologicalcharacteristicsofsocialnetworks.Communitydetectionhasbecomeafundamentalproblemintheresearchfieldofsocialnetworks.Theclusteringalgorithmisanimportantwaytofindcommunitystructure.Theclusteringanalysistechniquehasbeenwidelystudiedinthepastmanyyears

8、,oneoftheclusteringalgorithmisk-menasclusteringalgorithm,whichisthemostclassical.Becauseofsimplethinkingandshorttimecomplexity,k-meansiswidestudiedandapplied.Especiallythek-meansalgorithm