谱聚类优化算法的研究
近年来随着科技的不断发展,数据资源的重要性愈发突显。因为它记录了客观事物各方面的性质和特点。通过对数据的探索和分析,可以挖掘出数据潜在的大量价值,这些价值都能更好的改善生活的方方面面。为此,各行各业都存储了大量的数据,如生物医学领域的疾病数据,计算机视觉领域的图像数据,自然语言处理的文本数据等。为了能够更好的挖掘数据潜在的价值,许多数据挖掘技术成为了近几年来的研究热点,如:聚类,分类和推荐算法等。大规模的数据可以更加全面地刻画事物的客观规律,但是处理大规模数据也成为了数据挖掘研究中的难点,“大数据”一词因此应运而生。大数据下,数据的分析存在这样的问题:1)样本的维度高,2)大量数据缺乏标注。处理大规模数据的难点在谱聚类算法中变得尤为突显。虽然在过去几十年中提出了许多谱聚类算法,但是由于算法的时间复杂度很高导致这些算法很难应用到大数据中。并且,其中有大部分谱聚类算法都是通过两阶段求解,这就有可能导致最后求得的解跟原问题的解不一致。本文提出了三种新的谱聚类优化算法。首先本文提出了直接归一化切割优化算法。该算法通过直接求解目标函数的方法一定程度上可以避免以上问题。进而,为了进一步解决大数据处理难点,本文提出了快速的归一化切割优化算法。该算法寻找一批具有代表性的锚点,通过计算锚点和数据点构造相似度矩阵的方法,能够大大降低时间复杂度和空间复杂度。最后,为了解决数据类别模糊问题,提出了自适应的谱聚类算法。本文完成的创新工作如下:1)提出了直接归一化切割优化算法(DNC算法)。该算法使用一步优化的方法直接求解目标函数,一定程度上可以优化谱聚类算法的聚类效果。2)为优化谱聚类算法的时间复杂度和空间复杂度,我们提出了快速的归一化切割优化算法(FNC算法)。该算法通过构建一个规模较小且根据代表性的相似度矩阵,在这个低维的相似度矩阵上求解目标函数,从而实现算法降低时间复杂度和空间复杂度,使得谱聚类算法能够应用于较大的数据集中。3)前面提出的两种算法都是硬聚类算法,而现实生活中存在一些数据点的类别比较模糊,故提出一种自适应的谱聚类算法(ANC算法),通过引入平衡参数μ平衡了目标函数和归一化项两部分,并且将聚类目标Y连续化,从而解决一些类别模糊的样本的归属问题。使得算法能够在更多数据集中有好的聚类效果。4)在基准数据集中,分析了各个参数对算法性能的影响、数据及的标注情况以及选择的锚点数对聚类评价指标的影响,并将提出的三种谱聚类优化算法与近年的谱聚类算法进行了对比并验证了算法的优越性。
- 作者：
- 洪伟俊
- 学位授予单位：
- 深圳大学
- 授予学位：
- 硕士
- 学位年度：
- 2020年
- 导师姓名：
- 陈小军
- 中图分类号：
- TP311.13
- 关键词：
- 聚类；大数据；归一化切
-