基于图着色理论的聚类算法研究

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

1、声明本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或集体己经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名：堡趟础日期：型!墨：么：呈关于学位论文使用权的说明本人完全了解太原理工大学有关保管、使用学位论文的规定，其中包括：①学校有权保管、并向有关部门送交学位论文的原件与复印件；②学校可以采用影印、缩印或其它子复制手段复制并保存学位论文；③学校可允许学位论文被查阅或借阅；④学校可以学术交流为目

2、的，复制赠送和交换学位论文；⑤学校可以公布学位论文的全部或部分内容(保密学位论文在解密后遵守此规定)。作者签名：盛地址日期：迎!三，z：g导师签名：丝2旦差隅伊『弓-占，8太原理工大学硕士研究生学位论文基于图着色理论的聚类算法研究删摘要现实世界中存在着诸多复杂的网络结构，为了揭示隐藏在复杂结构中有价值的信息，网络结构图的思想引起了研究人员的注意。图是网络结构建模的方法，现实生活中很多实体都可以抽象为图的节点，而实体间的关系抽象为边，这样，对复杂网络结构的分析就转化为对图结构的分析。图聚类作为图数据挖掘的一种重要的分析技术，目的是在复杂的图中寻找出关联紧密的

3、子图，使得子图内的节点之间相似性较大，而子图与子图之间的节点具有较弱的相似性。目前图聚类的算法研究有很多，如Kemi曲an—LiIl算法、基于L印lace矩阵的传统谱平分法、GN算法(GiⅣaIl和Ne、砌an提出的基于边阶数的聚类算法)及Ne、釉an算法等，但是这些算法都存在一些缺陷，Kemi曲an—Lin算法和基于L印lace矩阵的传统谱平分法只有在图能很明显地分成两个子图的情况下才有效；GN算法是它在反复去边的过程中，一直到没有剩余的边才停止，这样下来，没有直接给出聚类的最终结果，还需再做进一步的分析和判断才能得到最终的聚类结果。总之，现有的图聚类算

4、法存在以下问题：(1)当数据量很大时，图的规模会非常大，在相似性度量方面，计算量会很大，导致运行时间会非常长；(2)图结构本身的复杂性影响聚类效果。基于以上问题，本文将图着色理论应用到图聚类中。图着色问题是一个被广泛研究的组合优化问题，它在对行政区域的划分、资源分配、离散I^＼太原理工大学硕士研究生学位论文规划、网络的自动检测等方面有着广泛的应用。解决图着色问题有很多种方法，如盲目搜索、启发式算法以及贪心算法等。本文采用的是贪心算法，这是因为在处理海量数据时，贪心算法相比其它算法，运行时间几乎以毫秒为单位，这样，算法的时间复杂度就在某种程度上就大大降低了。

5、本文首次将图着色理论应用到图聚类中，首先采用贪心算法的图着色理论进行初步聚类，得到初步聚类结果；然后通过对贪心算法的图着色理论进行改进，目的是对初步着色结果进行重新调整，使结果更加符合聚类要求，从而达到更好的聚类效果。论文的主要工作包括以下几个方面：(1)通过系统介绍现阶段图聚类技术的研究现状，总结了图聚类技术的特点、现实意义以及目前研究面临的问题。(2)分析了图着色理论应用的领域，总结了图着色问题的三种定义，分别为图的顶点着色、图的边着色和图的全着色，其中后两种都可以转化为图的顶点着色来分析。本文主要对图的顶点着色进行重点描述。(3)采用贪心算法的图着色

6、理论，聚类后的结果并不是唯一的。因此，本文引入评价聚类结果好坏的指标DuIlnG，然后将DullllG进行扩展，又提出一种新的评价指标Distinc缸1ess，与DunllG结合起来衡量聚类效果的好坏。(4)算法选取UCI数据集中不同类型的六种数据进行实验验证，实验结果与经典算法k—means方法以及改进前的算法进行比较，证明本文改进后的算法可以达到较高的聚类质量。关键字：图聚类分析，图着色理论，贪心算法，质量评价指标太原理工大学硕士研究生学位论文RESEARCHONCLUSTERINGALGORITHMBASED0NGRAPHCOLORINGTHEORY

7、ABSTRACTInordertorevealthevaluablei11f0瑚ationwhichhiddeniIl也ecomplicatedstmcture，researchersputfo刑ard也ethou出ofne撕orl(s仃uctIlre．Fig吡eisamethodofnetworks臼mcturemodeling．Inafigure，enti锣isseenasIlodesofthe孕印h，andtherelationshipbetweentheentitiesisseenast11eedge，then，theanalysisofmes饥l

8、cmreofcomplexnet、№rksistraIlsf．on