基于谱聚类的社区发现算法实现研究(4)
时间:2018-05-06 19:54 来源:毕业论文 作者:毕业论文 点击:次
2、可能过滤离群点 3、簇是处于稠密区域的，但是被对象空间中的低密度区域所分隔 基于网格的方法 1、使用一种多分辨率网格数据结构 2、快速处理 表1.3.2-1 聚类方法的分类 1.4 论文章节安排 本文划分了五个章节，如下： 第一章 绪论。首先讲述了基于聚类的社区发现，以及实现该算法研究课题的背景与提出。然后介绍了目前使用聚类算法进行社区划分在国内外研究的现状及主要方法等。最后简要介绍了本论文的内容分布情况。 第二章 论文的核心技术。详细介绍了本系统涉及到的理论内容与技术，包括Laplacian矩阵，K-Means算法以及谱聚类算法。 第三章 设计与实现。主要是有关本课题的设计思路、实现算法以及功能的描述。 第四章 实验结果与分析。讲述了实验环境、实验过程和最终实验结果分析。 第五章 总结。 2. 论文的核心技术 本章将详细介绍论文的核心技术，本系统涉及到的理论内容与算法，包括拉普拉斯矩阵，K均值算法以及谱聚类算法。 2.1 Laplacian矩阵 Laplacian矩阵是图的矩阵在数学领域中的表示，又被称为导纳矩阵，吉尔霍夫矩阵或离散拉普拉斯，拉普拉斯矩阵结合吉尔霍夫理论可以用来计算图的最小生成树的个数[10]。拉普拉斯矩阵是两个矩阵的差：一是将图中每个顶点的度都包含其中的对角矩阵，二是其邻接矩阵。值得一提的是，在面对待处理对象为有向图时，需要依据实际情况对入度或是出度进行选择。Laplacian矩阵也能够发现图的另外性质：如谱图理论spectral graph theory。谱图理论的核心本质或者说是在其算法应用中最重要的一点即是拉普拉斯矩阵离散模型，其中也包括了黎曼几何中的Cheeger不等式等重要知识。在用此方法确定图的最小割过程当中，所采用的核心方法就是计算拉普拉斯矩阵的第二特征值。 Laplacian矩阵有以下属性： (1).拉普拉斯矩阵是半正定矩阵。 (2).特征值中0出现的次数就是图连通区域的个数。 (3).最小特征值总是0。 (4).最小的非0特征值被称为谱隙spectral gap. (5).最小的非0特征值是图的代数连通度。 (责任编辑：qin) |