Clustering by passing messages between data points

资 源 简 介

Clustering by passing messages between data points

详 情 说 明

紧邻传播算法（Affinity Propagation）是一种基于数据点间消息传递的聚类算法，由Brendan J. Frey和Delbert Dueck于2007年发表在《Science》杂志上。该算法的核心思想是通过数据点之间交换两类消息（责任值和可用性值）来自动确定聚类中心和聚类结构，无需预先指定聚类数量。

### 算法原理 相似度矩阵：算法首先计算所有数据点之间的相似度，通常使用负欧氏距离或其他距离度量作为相似度指标。 消息传递：每个数据点通过两类消息与其余点通信： 责任值（Responsibility）：表示点A向点B发送的消息，反映点B作为点A的聚类中心的适合程度。 可用性值（Availability）：表示点B向点A发送的消息，反映点B作为聚类中心的累积证据。 迭代更新：算法通过交替更新责任值和可用性值，逐步收敛到稳定的聚类中心。 聚类确定：最终，数据点被分配到使其责任值与可用性值之和最大的聚类中心。

### 算法特点 无需预设聚类数：与K-means等算法不同，紧邻传播算法不需要预先指定聚类数量，而是通过数据驱动的方式自动确定。 适应复杂结构：适用于非球形分布或大小不一的簇，对初始条件不敏感。 计算复杂度较高：由于涉及全连接相似度矩阵和迭代消息传递，算法的时间和空间复杂度较高，适合中小规模数据集。

### 应用场景 紧邻传播算法广泛应用于生物信息学、图像分割、社交网络分析等领域，尤其适合数据内在聚类结构不明确的情况。通过自动识别代表性数据点（聚类中心），该算法为无监督学习提供了一种强大的工具。