AP聚类算法实现系统

资 源 简 介

本系统是基于近邻传播（Affinity Propagation）算法的完整 MATLAB 源码实现，旨在通过数据点之间的消息传递机制自动寻找数据集中的最具代表性的中心点。该算法的核心逻辑在于摒弃了传统聚类算法（如 K-means）需要预先设定聚类数量的限制，而是通过“偏好值”参数来引导聚类结果的产生。 在具体实现中，系统首先计算样本间的相似度矩阵，通常采用负欧式距离作为度量标准。随后，算法进入核心的迭代循环，交替更新责任度矩阵（Responsibility）和可用度矩阵（Availability）。责任度

详 情 说 明

AP 自相似传播聚类 MATLAB 实现系统

项目介绍

本系统是一个基于近邻传播（Affinity Propagation, AP）算法的完整聚类分析工具。不同于传统的 K-means 算法需要预先指定聚类数量，AP 算法通过在数据点之间传递“责任度”和“可用度”两种消息，依靠数据自身的分布特性自动涌现出最具代表性的中心点（Exemplars）。该系统适用于处理具有复杂拓扑结构的数据集，能够有效识别非凸形状的簇，并提供了从数据生成、相似度计算、核心迭代到结果可视化的全流程实现。

功能特性

• 自动发现聚类中心：无需手动输入预期的聚类个数，算法通过内部竞争机制自动确定最佳中心。
• 高斯分布数据模拟：系统内置了生成三组高斯分布随机数据的模块，便于直观测试算法的分类效果。
• 稳定性保障机制：集成了阻尼因子（Damping Factor）处理模块，有效防止在消息传递过程中出现数值震荡，确保算法收敛。
• 双维度收敛判定：采用最大迭代次数限制与聚类中心稳定度双重检查策略，提高计算效率。
• 直观可视化方案：系统自动生成聚类分布图（包含点心连线）以及聚类中心数量随迭代次数变化的收敛曲线。
• 灵活的倾向值设置：使用相似度矩阵的中位数作为偏好值，平衡了聚类的粒度。

系统要求

• 环境版本：MATLAB R2016b 或更高版本。
• 硬件要求：适配主流计算设备，内存需足以支持存储 N×N 的相似度矩阵（本系统默认 N=300）。

使用方法

1. 启动 MATLAB 软件。
2. 将系统源代码所在文件夹设置为当前工作目录。
3. 在命令行窗口输入入口函数指令并回车。
4. 系统将自动开始迭代，并在命令行输出迭代进度、收敛状态以及最终发现的聚类中心索引。
5. 计算完成后，系统会自动弹出可视化窗口展示聚类结果。

功能逻辑与算法实现细节

1. 模拟数据准备 系统首先生成 300 个二维坐标点。这些点被分为三组，每组 100 个点，分别围绕中心点 [5, 5]、[-5, 5] 和 [0, -5] 呈高斯分布（标准正态分布）。这种分布方式为检验算法识别非离散边界能力提供了基础。

2. 相似度矩阵计算 系统计算所有样本点两两之间的负欧式距离平方作为相似度度量（S 矩阵）。

• 公式：S(i,j) = -||data(i) - data(j)||^2。
• 偏好值设置：将 S 矩阵的对角线元素（即 S(i,i)）设置为所有相似度值的中位数。该值直接决定了聚类中心的生成倾向，中位数设置通常能获得适中的簇数量。

3. 消息传递核心迭代 系统交替更新两个核心矩阵，直至满足收敛条件：

• 责任度矩阵（Responsibility, R）：表示点 k 适合作为点 i 聚类中心的程度。更新时不仅考虑 i 与 k 的相似度，还会扣除 i 选择其他点作为中心的最大可能收益。代码中特别处理了最大值与次大值的逻辑，以确保计算准确。
• 可用度矩阵（Availability, A）：表示点 i 选择点 k 作为聚类中心的合适程度。该值由 k 作为中心的自我证据（R(k,k)）以及其他点对 k 的正面评价累加而成。
• 阻尼处理：每一次 R 和 A 的更新都会乘以权重 (1 - damping)，并加上旧值与 damping 的乘积。系统默认 damping 为 0.9，这在处理大规模点集时能显著提升稳定性。

4. 聚类中心识别与分配

• 识别中心：每一轮迭代结束后，系统通过判断 R(i,i) + A(i,i) > 0 的点来确定当前的聚类中心。
• 分配成员：在算法收敛后，系统遍历所有数据点，将其分配给与其相似度最高（负距离平方最大）的已知聚类中心。

5. 收敛检查逻辑 系统维护一个长度为 100 的历史记录滑窗。如果在此时间段内，所有点的聚类中心状态保持恒定且已发现至少一个聚类，算法将提前跳出迭代循环，输出“算法收敛”的提示。

6. 可视化模块

• 分布散点图：使用不同颜色区分不同的簇。每个成员点通过虚线与其对应的聚类中心相连，聚类中心点使用加粗实心圆圈标注，增强了视觉结构感。
• 变化曲线图：展示了从第 1 次到最后一次迭代过程中，系统中聚类中心数量的动态变化，帮助用户观察算法从不稳定到稳定的演变过程。

关键函数与算法参数总结

• 相似度度量：L2 范数平方的负值。
• 迭代参数：最大迭代次数 1000 次，收敛判定周期 100 次。
• 阻尼调节：0.9（支持在 0.5 到 1 之间调整）。
• 数据结构：利用全矩阵运算实现，通过 max 函数配合索引排除法优化消息传递效率。