论文部分内容阅读
社团检测即机器学习中的聚类问题一直是机器学习的一大热点问题。随着数据规模日渐庞大,数据结构也变得纷繁复杂,传统的聚类方法由于对某种特定结构的数据有强依赖性而导致普适性偏低。谱聚类算法(Spectral clustering,SC)将降维的思想与k-means算法相结合,特别是对于高维数据(如文本数据)来说,谱聚类算法比k-means算法计算复杂度要小,聚类准确率更高。目前,谱聚类算法已经成为了机器学习、通信等领域最为流行的聚类算法之一。谱方法因为其易于实现,适用范围广的优点受到了学者们的广泛关注。然而,大量的实验结果表明:如果数据集中存在噪声,那么谱方法往往不能给出令人满意的聚类结果。与此同时,现实世界中的数据又不可避免地存在有噪声,因此如何减小噪声对谱方法的影响是谱方法在真实数据集上应用的关键,也是本文的研究重点。针对这一问题,本文从谱方法的核心——特征谱的研究入手来构建模型,本篇论文的主要工作包括以下三个方面:1)模型框架;鉴于正则化的方法能够有效地提高算法的抗噪性。本文在传统的正则化谱聚类框架之上,通过引入信息熵的概念构建出了基于熵扰动的正则化谱聚类模型,该模型不仅解放了正则化参数固定的问题,同时还提高了谱聚类算法的抗噪性能。2)理论推导;本文算法是基于矩阵扰动理论提出的一类正则方法,通过矩阵扰动分析以及Davis-Kahan理论,笔者推导出了本文算法在扰动迭代过程中的理论阈值,提高了算法的普适性,完善了算法的理论基础。3)重叠社团检测;在本文最后,笔者将所提出的算法应用于重叠社团检测,在DBLP、Youtube等数据集上的实验结果证明了本文算法的有效性。