基于成对约束的半监督近邻传播聚类算法SSAP

资 源 简 介

本项目实现了一种增强型的近邻传播（Affinity Propagation, AP）聚类算法，旨在结合无监督聚类的灵活性与半监督学习的先验知识引导能力。传统的AP算法通过在数据点之间传递“责任度”和“可用度”消息来自动确定聚类中心和簇的数量，但在复杂数据分布下容易陷入局部最优或产生不符合物理意义的聚类。本项目通过引入成对约束（Pairwise Constraints）机制来改进这一过程，具体功能包括：1. 数据预处理与相似度矩阵构建，计算样本间的负欧氏距离或其他相似性度量；2. 约束集成，处理“必须连接”（Must-Link, ML）和“不能连接”（Cannot-Link, CL）两类约束，通过调整相似度矩阵中特定元素的值（如将ML对的相似度设为最大值，将CL对的相似度设为最小值）或在消息传递迭代公式中增加约束项，强制算法在聚类时遵循这些先验规则；3. 执行改进的消息传递循环，迭代更新R矩阵和A矩阵，直至满足收敛条件；4. 结果解析与可视化，输出识别出的聚类中心（Exemplars）及所有样本的归属标签，并提供聚类结果的散点图可视化（针对低维数据）以便于评估算法性能。该算法特别适用于具有少量标记数据或领域专家知识的场景，如医学图像分割、基因表达数据分析等。

详 情 说 明

Semi-supervised Affinity Propagation Clustering (SSAP)

项目简介

本项目基于 MATLAB 实现了一种半监督近邻传播（Semi-supervised Affinity Propagation, SSAP）聚类算法。该算法在经典的近邻传播（AP）聚类基础上，引入了成对约束（Pairwise Constraints）机制，通过利用少量的先验知识（必须连接 Must-Link 和不能连接 Cannot-Link）来引导聚类过程，从而提高算法在复杂数据分布下的聚类准确性和鲁棒性。

项目包含完整的数据生成、约束构建、核心算法实现、性能评估以及结果可视化流程。

功能特性

• 合成数据生成：自动生成具有特定分布规律（高斯混合模型）的二维合成数据集，用于算法演示和测试。
• 半监督约束集成：支持通过调整相似度矩阵的方式集成“必须连接”（Must-Link）和“不能连接”（Cannot-Link）约束。
• 增强型 AP 核心：实现了包含阻尼因子和平滑更新机制的消息传递步骤，防止数值震荡。
• 自动收敛检测：通过监控聚类中心（Exemplar）在连续迭代中的稳定性来自动判定算法收敛。
• 结果评估：内置基于贪心策略的最佳匹配算法，计算聚类结果相对于真实标签的准确率（Accuracy）。
• 可视化分析：提供多图表可视化界面，展示原始数据分布、约束连接情况以及最终的聚类结果。

系统要求

• MATLAB R2016a 或更高版本
• Statistics and Machine Learning Toolbox（用于 pdist2 和 gscatter 等函数）

使用方法

直接运行主函数即可启动完整流程。程序将自动完成以下步骤：

1. 生成包含 3 个簇的二维样本数据。
2. 基于真实标签随机生成指定数量的 Must-Link 和 Cannot-Link 约束。
3. 执行 SSAP 聚类算法。
4. 在控制台输出聚类簇数量和准确率。
5. 弹出图形窗口显示可视化结果。

核心算法与实现细节

本项目的主要逻辑封装在单文件中，具体实现逻辑如下：

1. 数据与约束生成

程序首先设定随机种子以保证结果可复现，生成3个服从高斯分布的数据簇。随后，依据样本的真实标签（Ground Truth），随机抽取样本对生成约束：

• Must-Link (ML)：属于同一类的样本对，算法应尽量将其聚为一类。
• Cannot-Link (CL)：属于不同类的样本对，算法应避免将其聚为一类。

2. 半监督近邻传播 (SSAP) 核心逻辑

算法核心函数 ss_affinity_propagation 执行了以下关键步骤：

• 相似度矩阵构建：计算所有样本点之间的负欧氏距离平方作为基础相似度矩阵。
• 偏好参数 (Preference) 设置：采用相似度矩阵中非零元素的中位数（Median）作为对角线元素，该参数控制算法生成簇的倾向数量。
• 约束集成策略：

* 对于 ML 约束：将对应样本对的相似度设为略高于当前矩阵最大值的值（Max + 0.1 * Range），强行增加它们成为彼此聚类中心的可能性。 * 对于 CL 约束：将对应样本对的相似度设为极小值（Min - 10 * Range），在物理上切断它们之间的消息传递路径。

• 消息传递迭代：

* 更新责任度 (R)：计算样本 $i$ 选择样本 $k$ 作为聚类中心的适宜程度。代码通过矩阵掩码操作优化了“最大值与次大值”的查找过程。 * 更新可用度 (A)：计算样本 $k$ 适合作为样本 $i$ 的聚类中心的程度。实现了标准的 AP 累加逻辑，并包含对角线元素的特殊处理。 * 阻尼更新：引入阻尼因子（默认为 0.9），通过加权平均当前值与新值（old * lambda + new * (1-lambda)）来更新 R 和 A 矩阵，有效避免震荡。

• 收敛检测：通过维持一个滑动窗口记录最近数十次迭代的聚类中心索引，一旦这些索引完全保持不变，即判定算法收敛并提前退出循环。
• 一致性修正：在确定最终聚类中心后，代码包含一个后处理步骤，确保所有样本指向的最终归属点本身也是自我代表的 Exemplar，解决了潜在的链式依赖问题。

3. 结果评估

由于无监督聚类的标签 ID 与真实标签 ID 并不直接对应，程序实现了一个 calculate_accuracy 函数。该函数首先构建混淆矩阵，计算预测簇与真实簇的重叠数量，然后采用贪心策略（近似匈牙利算法）在混淆矩阵中寻找最佳匹配路径，从而计算整体分类准确率。

4. 结果可视化

可视化模块 visualize_results 创建一个包含多个子图的窗口：

• 原始数据与约束图：使用散点图展示原始数据分布，颜色代表真实标签。同时，使用蓝色实线连接 Must-Link 样本对，使用红色虚线连接 Cannot-Link 样本对，直观展示先验知识的分布。
• 聚类结果图：根据算法输出的标签对样本进行着色，并绘制样本与其归属聚类中心（Exemplar）的连接线（可视化代码逻辑包含此意图）。