第一章 绪论
1.1 课题研究背景及意义
1.1.1 研究背景
随着计算机技术与互联网的飞速发展，高维数据不断涌现，大规模数据的分析与处理成为一种现实的需求与必然趋势，这给相关技术研究带来了巨大的挑战。现实社会中每天都会产生大量的数据，这些数据往往是没有标注信息的，而信息的标注工作又是非常耗时耗力的。因此，无监督的数据处理问题引起了广泛的关注。
数据聚类是无监督学习中研究最多、应用最广的一类任务，也是数据挖掘中最基本的主题之一。数据聚类是将未知标签的数据分为由类似的对象组成的多个不相交的组（每一组称为一个“簇”）的过程。由聚类所生成的簇是一组数据对象的集合，同一簇中的对象彼此相似，不同簇的对象则相异。到目前为止，聚类分析已经有很长的研究历史，它具有能够与其他研究方向相互促进的交叉特性。在过去的几十年里，许多学者提出了多种聚类算法并广泛应用于各个领域，包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等[1]。
面对大规模的复杂数据，传统的聚类方法难以得到令人满意的结果。由于数据聚类是一个无监督的分类问题，没有任何先验知识可用，在进行数据聚类前并不确定将数据分为多少个簇，也不知道该依据何种空间区分规则来定义簇。因此，有效地捕获数据中的复杂结构对于数据准确聚类是至关重要的。研究表明，图论能够有效挖掘潜在的数据结构，因此，将图论与数据聚类任务相结合能够获得更佳的结果。
......................
1.2 国内外研究现状
1.2.1 单视图数据聚类
数据聚类作为一种无监督学习任务，已广泛应用于机器学习、数据挖掘以及计算机视觉等研究领域。目前，聚类算法主要分为如下几种：（1）划分式聚类，这种方法将给定的数据分裂为多个类，使得类内的数据点都足够近，而类间的数据点都足够远。如 1967年由 MacQueen 提出的 k 均值算法（k-means）[2]，该算法的核心思想是找出 k 个聚类中心，使得每一个数据点和与其最近的聚类中心的平方距离和最小化；（2）层次聚类，这类方法分别使用“自顶向下”和“自底向上”的方式，反复地将数据进行层次性的分裂或聚合，直到满足某种条件为止；（3）基于密度的聚类，这类方法与其他方法的一个根本区别在于：它是基于数据样本的密度分布来进行聚类的，而非基于其他各式各样的距离度量；（4）基于网格的聚类，这种方法首先将数据空间划分成有限个单元的网格结构，后续所有的处理都以单个的单元为对象；（5）基于模型的聚类，这类方法给每一个簇假定一个模型，然后寻找数据对给定模型的最佳拟合。
1.2.1 单视图数据聚类
数据聚类作为一种无监督学习任务，已广泛应用于机器学习、数据挖掘以及计算机视觉等研究领域。目前，聚类算法主要分为如下几种：（1）划分式聚类，这种方法将给定的数据分裂为多个类，使得类内的数据点都足够近，而类间的数据点都足够远。如 1967年由 MacQueen 提出的 k 均值算法（k-means）[2]，该算法的核心思想是找出 k 个聚类中心，使得每一个数据点和与其最近的聚类中心的平方距离和最小化；（2）层次聚类，这类方法分别使用“自顶向下”和“自底向上”的方式，反复地将数据进行层次性的分裂或聚合，直到满足某种条件为止；（3）基于密度的聚类，这类方法与其他方法的一个根本区别在于：它是基于数据样本的密度分布来进行聚类的，而非基于其他各式各样的距离度量；（4）基于网格的聚类，这种方法首先将数据空间划分成有限个单元的网格结构，后续所有的处理都以单个的单元为对象；（5）基于模型的聚类，这类方法给每一个簇假定一个模型，然后寻找数据对给定模型的最佳拟合。
由于 k 均值聚类算法的简洁性和高效性，使其成为最常用的聚类算法之一。核 k 均值聚类算法（Kernel K-means，KKM）能够进一步描述现实数据集中固有的非线性结构[3]。此外，一种可以捕捉输入数据的非线性和低维流形结构的聚类方法，即基于图的聚类方法得到了广泛的关注[4]。这种方法是建立在图论中的谱图理论基础上进行数据聚类的，本质是将聚类问题转化为图的最优划分问题。图论中的图是由若干个给定的点及连接两点的边所构成的图形，这种图形用于描述事物之间的某种特定关系。基于图的聚类方法利用图的顶点表示数据点，图的边表示两个数据点之间的相关关系，采用关联矩阵表示数据点间的相似度。由于在聚类模型中利用了数据图和流形信息，基于图的聚类方法（如谱聚类（Spectral Clustering，SC）[5]，比例切割聚类（Ratio Cut，RCut）[6]和归一化切割聚类（Normalized Cut，NCut）[7]等）通常表现出比 k 均值聚类方法更好的性能。与其他的聚类方法相比，基于图的聚类方法在具有复杂结构的数据分区方面具有更强的能力。尽管上述提到的基于图的聚类方法均表现出良好的聚类性能，但是它们都是基于固定的数据图对数据进行划分，使得聚类结果对输入数据图较为敏感，如果图的初始结构质量差，那么得到的聚类结果也将是次优的。此外，这些方法都需要对学习到的图进行后续处理才可以获得最终的聚类结果，例如图切割方法通常使用 k 均值算法对结果进行处理后才可得到聚类标签。因此，这些基于图的方法都需要经历两个独立的过程，首先从数据中构建表示样本间相似度关系的图，然后在该图上调用各种优化算法以完成数据聚类任务。
..........................
第二章 鲁棒的结构化图聚类
2.1 概述
..........................
第二章 鲁棒的结构化图聚类
2.1 概述
为了解决传统的基于图的聚类方法中存在的不足，提高数据聚类性能，本文提出鲁棒的结构化图聚类方法（Robust Structured Graph Clustering，RSGC）。RSGC 方法设计了一种新的联合聚类学习框架，在学习结构化图的同时对样本进行聚类。具体而言，该算法从具有鲁棒性的（可以抵抗噪声和异常值）特征表示中，通过概率邻居分配的方式，自适应地学习表示数据样本相似度关系的结构化图。在此过程中，
RSGC 通过在图的拉普拉斯矩阵上施加秩约束来使得学习到的图具有理论上最优的聚类簇结构。为了优化目标函数，首先将其转换为一种等价且容易求解的形式。然后，使用增广拉格朗日乘子法来迭代地求解该问题。RSGC 算法的主要贡献可归纳如下：
（1）本工作提出了一个联合的聚类学习框架，该框架可以在学习鲁棒的结构化图的同时进行数据聚类。该方法从鲁棒的潜在特征表示中自适应地学习样本相似度图，并且通过对相似度图的拉普拉斯矩阵施加秩约束，使得学习到的图具有理想的聚类结构（即图的连通分量数量恰好等于聚类中簇的数量），且聚类标签直接由图的划分获得，而不需要依赖于其他任何标签离散化策略。
（2）该工作将目标函数转换为更容易求解的等价问题，利用基于增广拉格朗日乘子法的迭代优化方法来求解目标函数，并证明了算法的收敛性。
（3）在真实数据集和合成数据集上的实验结果表明，与最新的聚类技术相比，本文提出的鲁棒的结构化图聚类算法可以获得更加卓越的性能。
...........................
..........................
（1）本工作提出了一个联合的聚类学习框架，该框架可以在学习鲁棒的结构化图的同时进行数据聚类。该方法从鲁棒的潜在特征表示中自适应地学习样本相似度图，并且通过对相似度图的拉普拉斯矩阵施加秩约束，使得学习到的图具有理想的聚类结构（即图的连通分量数量恰好等于聚类中簇的数量），且聚类标签直接由图的划分获得，而不需要依赖于其他任何标签离散化策略。
（2）该工作将目标函数转换为更容易求解的等价问题，利用基于增广拉格朗日乘子法的迭代优化方法来求解目标函数，并证明了算法的收敛性。
（3）在真实数据集和合成数据集上的实验结果表明，与最新的聚类技术相比，本文提出的鲁棒的结构化图聚类算法可以获得更加卓越的性能。
...........................
2.2 模型构建和优化求解
本节将详细介绍鲁棒的结构化图聚类 RSGC 算法，内容共分为五部分。第一部分介绍RSGC 算法所使用的相关符号和问题定义，第二部分详细介绍所提 RSGC 算法的目标函数，第三部分给出求解算法目标函数的优化步骤，第四部分介绍如何确定算法中参数? 的值，第五部分对算法的收敛性和计算复杂性进行了理论分析。
2.2.1 符号和问题定义
本节将详细介绍鲁棒的结构化图聚类 RSGC 算法，内容共分为五部分。第一部分介绍RSGC 算法所使用的相关符号和问题定义，第二部分详细介绍所提 RSGC 算法的目标函数，第三部分给出求解算法目标函数的优化步骤，第四部分介绍如何确定算法中参数? 的值，第五部分对算法的收敛性和计算复杂性进行了理论分析。
2.2.1 符号和问题定义
..........................
第三章 基于动态图特征学习的多视图聚类......................................33
3.1 概述.......................................33
3.2 模型构建和优化求解.................................34
第四章 总结与展望....................................51
4.1 全文总结.................................51
4.2 后续工作展望................................51
第三章 基于动态图特征学习的多视图聚类
3.1 概述
基于图特征学习的多视图聚类方法主要探索多视图数据的相关性和互补性，典型的例子包括边界 Fisher 分析（Margin Fisher Analysis，MFA）[49]，多视图谱嵌入（Multi-view SpectralEmbedding，MSE）和多视图局部线性嵌入（Multi-view Local Linear Embedding，MLLE）等。这些方法通常基于图论完成特征提取，首先构造多个固定的相似度图来分别表示多个视图中样本的相似性。随后，将这些图集成为一个统一的相似度图，并基于该图执行后续的特征提取任务。尽管上述方法均取得了不错的效果，但仍然存在以下问题：（1）图的构建和特征提取是两个独立的过程，容易导致次优的结果；（2）它们均利用固定的样本相似度矩阵来进行特征提取，而真实数据中存在的噪声难以避免会影响图的质量，进而影响后续的特征提取性能；（3）这些方法无法处理训练集中未包含的新数据点（Out-of-sampleproblem）。
基于图特征学习的多视图聚类方法主要探索多视图数据的相关性和互补性，典型的例子包括边界 Fisher 分析（Margin Fisher Analysis，MFA）[49]，多视图谱嵌入（Multi-view SpectralEmbedding，MSE）和多视图局部线性嵌入（Multi-view Local Linear Embedding，MLLE）等。这些方法通常基于图论完成特征提取，首先构造多个固定的相似度图来分别表示多个视图中样本的相似性。随后，将这些图集成为一个统一的相似度图，并基于该图执行后续的特征提取任务。尽管上述方法均取得了不错的效果，但仍然存在以下问题：（1）图的构建和特征提取是两个独立的过程，容易导致次优的结果；（2）它们均利用固定的样本相似度矩阵来进行特征提取，而真实数据中存在的噪声难以避免会影响图的质量，进而影响后续的特征提取性能；（3）这些方法无法处理训练集中未包含的新数据点（Out-of-sampleproblem）。
针对这些挑战，本文提出基于动态图特征学习的多视图聚类方法 MC-DGFL，在不依赖任何预先构建的相似性图的情况下，从原始特征中学习优化的动态图。此外，MC-DGFL通过分配不同的视图权重来衡量不同视图特征对动态图学习的贡献。本文所提 MC-DGFL算法的主要贡献如下所述：
（1）设计了一个联合的基于动态图特征学习的多视图聚类学习框架，该框架能够同时学习特征提取矩阵和动态图。MC-DGFL 学习的特征提取矩阵具有良好的投影能力，能够很好地保留数据间的相关性。此外，学习的动态图可以自适应地建模多视图数据之间的相关关系。
（2）提出一种有效且收敛的优化求解方案，迭代地学习最优视图整合权重、动态图结构以及特征提取矩阵，经过有限次迭代后可以获得最优解。
...............................
（1）设计了一个联合的基于动态图特征学习的多视图聚类学习框架，该框架能够同时学习特征提取矩阵和动态图。MC-DGFL 学习的特征提取矩阵具有良好的投影能力，能够很好地保留数据间的相关性。此外，学习的动态图可以自适应地建模多视图数据之间的相关关系。
（2）提出一种有效且收敛的优化求解方案，迭代地学习最优视图整合权重、动态图结构以及特征提取矩阵，经过有限次迭代后可以获得最优解。
...............................
第四章 总结与展望
4.1 全文总结
本文的第一个工作是提出了一种基于鲁棒结构化图的单视图聚类模型，开发了一个联合学习框架来同时进行图学习和数据聚类。算法首先在潜在的判别表示上动态地学习图，以降低噪声和异常值的影响。此外，为了学习具有适当邻居分配的理想图结构，通过施加秩约束来有效地支持后续的聚类过程。为了求解目标函数，将目标公式转换为可以更容易求解的等价问题，并给出了一种有效的优化解决方案，同时保证了优化算法的收敛性。实验结果表明，与最新的聚类技术相比，该方法具有更好的性能。
本文的第二个工作是提出了一种新的多视图聚类模型，即基于动态图特征学习的多视图聚类方法，为动态图学习和特征学习开发了联合学习框架。动态图的学习可以捕获不同视图间的深层特征相关性，特征提取通过学习一个投影矩阵来将动态调整的样本关系保持到低维特征中。真实基准数据集上的实验结果证明了本文所提基于动态图特征学习的多视图聚类方法的有效性。
4.1 全文总结
本文的第一个工作是提出了一种基于鲁棒结构化图的单视图聚类模型，开发了一个联合学习框架来同时进行图学习和数据聚类。算法首先在潜在的判别表示上动态地学习图，以降低噪声和异常值的影响。此外，为了学习具有适当邻居分配的理想图结构，通过施加秩约束来有效地支持后续的聚类过程。为了求解目标函数，将目标公式转换为可以更容易求解的等价问题，并给出了一种有效的优化解决方案，同时保证了优化算法的收敛性。实验结果表明，与最新的聚类技术相比，该方法具有更好的性能。
本文的第二个工作是提出了一种新的多视图聚类模型，即基于动态图特征学习的多视图聚类方法，为动态图学习和特征学习开发了联合学习框架。动态图的学习可以捕获不同视图间的深层特征相关性，特征提取通过学习一个投影矩阵来将动态调整的样本关系保持到低维特征中。真实基准数据集上的实验结果证明了本文所提基于动态图特征学习的多视图聚类方法的有效性。
参考文献（略）