基于高斯过程的约束谱聚类CVPR08算法复现

资 源 简 介

本项目完整实现了Lu Zhengdong在CVPR 2008发表的关于利用高斯过程进行约束谱聚类的算法（Constrained Spectral Clustering via Gaussian Processes）。该项目的主要功能是解决半监督学习场景下的聚类问题，即在仅有少量成对约束（Must-link和Cannot-link）作为先验知识的情况下，如何提高聚类的准确性。算法的核心思想是将约束信息的传播建模为一个高斯过程问题，通过高斯过程将稀疏的标签约束平滑地扩散到整个数据集，从而动态调整数据点之间的相似度矩阵（Affinity Matrix）。经过约束传播修正后的相似度矩阵被送入标准的谱聚类流程中，通过求解拉普拉斯矩阵的特征向量来获得最终的划分结果。项目中包含了核心算法的MATLAB源代码以及两个可直接运行的演示脚本（Demo），这些Demo直观地展示了算法在处理带有约束数据时的有效性，并对比了加入约束前后聚类结果的差异，适用于模式识别、计算机视觉中的图像分割以及数据挖掘等领域的研究与验证。

详 情 说 明

基于高斯过程的约束谱聚类算法 (CVPR 2008复现)

项目介绍

本项目是对 Lu Zhengdong 在 CVPR 2008 发表的论文 "Constrained Spectral Clustering via Gaussian Processes" 的代码复现与实现。该项目针对半监督学习场景，旨在解决仅包含少量成对约束（Must-link 和 Cannot-link）作为先验知识的聚类问题。

程序通过高斯过程（Gaussian Processes）将稀疏的约束信息在数据集上进行平滑传播，从而修正数据点之间的相似度矩阵（Affinity Matrix）。修正后的矩阵被送入标准的谱聚类算法中，能够显著提高聚类准确率。本实现包含在一个完整的 MATLAB 脚本中，集成了数据生成、算法核心、评估指标及可视化的全流程。

关键功能特性

• 双月数据集生成：内置非线性“双月”分布（Two-moons）数据生成器，支持自定义样本数量和噪声水平，用于验证算法处理非凸数据集的能力。
• 成对约束模拟：能够基于真实标签随机生成指定数量的 Must-link (同类) 和 Cannot-link (异类) 约束。
• 高斯过程约束传播：实现了论文的核心思想，利用矩阵运算高效地将稀疏约束矩阵通过基础核矩阵扩散，生成约束场并修正相似度。
• 对比实验框架：同时执行“无约束谱聚类”与“基于GP的约束谱聚类”，直观对比引入约束前后的效果。
• 自动化评估与对齐：通过标签对齐算法解决聚类结果的标签置换（Label Switch）问题，自动计算聚类准确率（Accuracy）和约束满足率（CSR）。
• 多维可视化：提供包含原始数据、约束连线、聚类结果对比、相似度矩阵热力图及约束势场差分图的综合可视化界面。

系统要求

• MATLAB R2016b 或更高版本
• Statistics and Machine Learning Toolbox (需要使用 kmeans, pdist2, gscatter 等函数)

使用方法

由于本项目将所有逻辑封装在单个文件中，使用非常简便：

1. 直接在 MATLAB 中打开并运行主程序。
2. 程序会自动生成数据、执行算法并在控制台输出统计结果。
3. 运行结束后会弹出一个综合图形窗口，展示聚类效果和矩阵变化。

核心算法与实现细节

本项目完全基于提供的源代码实现，具体逻辑流程如下：

1. 参数初始化

程序首先固定随机数种子（Seed=42）以保证结果的可复现性。预设了样本总数（300）、噪声水平（0.05）、聚类数（2）、高斯核宽（0.5）以及约束传播权重（10.0）等关键超参数。

2. 构建基础相似度矩阵

使用欧氏距离的平方计算距离矩阵，并采用径向基函数（RBF Kernel）构建基础相似度矩阵 $W_{base}$。代码中显式地将对角线元素置零，消除自相关影响。

3. 先验约束生成

通过 generate_constraints 函数随机采样点对。利用真实标签判断关系：若两点同类则标记为 +1 (Must-link)，若异类则标记为 -1 (Cannot-link)，无约束为 0。该过程生成了一个稀疏的约束矩阵 $T$。

4. 基于高斯过程的约束传播 (GP Constraint Propagation)

这是算法的核心部分。代码并未调用复杂的优化求解器，而是依据论文推导的简化形式，通过矩阵乘法实现约束传播： $Q = W_{base} times T times W_{base}$ 其中 $Q$ 代表传播后的约束信息。 最终的修正相似度矩阵结合了原始相似度和传播后的约束项： $W_{constrained} = W_{base} + alpha times Q$ 随后，代码对修正后的矩阵进行了非负截断和对称化处理，确保满足谱聚类对输入矩阵的要求。

5. 谱聚类实现 (Spectral Clustering)

采用标准化的切图（Normalized Cut）谱聚类算法：

• 计算度矩阵 $D$。
• 构建对称归一化拉普拉斯矩阵 $L_{sym} = I - D^{-1/2} W D^{-1/2}$。
• 通过 eigs 函数求解最小的 $K$ 个特征值对应的特征向量。
• 对特征向量进行行归一化。
• 使用 K-Means 算法对特征空间中的点进行聚类（包含多次重复以保证稳定性）。

6. 结果评估

• 准确率 (Accuracy)：为了解决无监督聚类输出标签与真实标签不对应的问题，实现了 align_labels 函数，在二分类情况下通过简单的翻转逻辑匹配真实标签，计算最终准确率。
• 约束满足率 (CSR)：通过 check_constraint_satisfaction 函数遍历所有生成的约束，统计聚类结果中满足 Must-link（聚为同类）和 Cannot-link（聚为异类）的比例。

结果可视化说明

运行程序后生成的图形窗口包含以下内容：

1. Ground Truth & Constraints：展示带有噪声的双月数据真实分布，并用绿线连接 Must-link 约束点对，用黑虚线连接 Cannot-link 约束点对。
2. Unconstrained SC / GP-Constrained SC：左右并列展示未加约束和加入约束后的聚类结果散点图，标题处附带准确率。
3. Original Affinity / Propagated Affinity：对比原始相似度矩阵和约束传播后的相似度矩阵的热力图，展示数据流形结构的改变。
4. Constraint Field Propagation：展示前后两个矩阵的差值（Delta W），直观呈现高斯过程是如何将稀疏的约束信息扩散到整个数据空间的。