数据处理: 亲和聚类

Affinity Propagation（亲和传播）是一种基于"消息传递"概念的聚类算法，由Brendan Frey和Delbert Dueck于2007年提出。与K-Means等需要预先指定簇数量的算法不同，Affinity Propagation能够自动确定最佳簇的数量，这使得它在许多实际应用中非常有用。

1. 原理

通过数据点之间交换两种消息来进行聚类：

1. 责任度(Responsibility)消息(r(i,k))：

   • 表示数据点i适合选择数据点k作为其"代表点"(exemplar)的程度

   • 从点i发送到候选代表点k

2. 可用度(Availability)消息(a(i,k))：

   • 表示数据点k适合作为数据点i的"代表点"的程度

   • 从候选代表点k发送回点i

算法步骤

1. 初始化相似度矩阵：计算所有数据点之间的相似度(通常使用负欧氏距离)

2. 设置偏向参数：对角线元素设置为相同的值(控制产生多少聚类)

3. 迭代更新消息：

   • 更新责任度消息

   • 更新可用度消息

4. 确定代表点：当消息收敛后，选择代表点并分配聚类

数学表达

• 相似度矩阵：s(i,k) = -||xᵢ - xₖ||²

• 责任度更新：r(i,k) = s(i,k) - max{a(i,k') + s(i,k')} (k'≠k)

• 可用度更新：

  • 对于k≠i：a(i,k) = min{0, r(k,k) + Σmax{0,r(i',k)}} (i'∉{i,k})

  • 对角线元素：a(k,k) = Σmax{0,r(i',k)} (i'≠k)

2. 特点

优点

• 不需要预先指定簇的数量

• 能够发现数据中自然存在的簇结构

• 对初始条件不敏感

• 可以处理非球形簇

缺点

• 时间复杂度较高(O(N²T)，N是样本数，T是迭代次数)

• 内存消耗大(需要存储N×N的相似度矩阵)

• 对偏向参数(Preference)的选择敏感

3. Python实现

from sklearn.cluster import AffinityPropagation
from sklearn import metrics
from sklearn.datasets import make_blobs
import numpy as np
import matplotlib.pyplot as plt# 生成样本数据
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0.5, random_state=0)# 计算相似度矩阵(负欧氏距离)
similarities = -np.sum((X[:, np.newaxis, :] - X[np.newaxis, :, :]) ** 2, axis=2)# 运行Affinity Propagation
af = AffinityPropagation(affinity='precomputed', random_state=0).fit(similarities)
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_n_clusters_ = len(cluster_centers_indices)print('Estimated number of clusters:', n_clusters_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))# 绘制结果
plt.figure(figsize=(10, 6))
colors = plt.cm.Spectral(np.linspace(0, 1, len(set(labels))))for k, col in zip(range(n_clusters_), colors):class_members = labels == kcluster_center = X[cluster_centers_indices[k]]plt.plot(X[class_members, 0], X[class_members, 1], 'o', markerfacecolor=col,markeredgecolor='k', markersize=8)plt.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,markeredgecolor='k', markersize=14)plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()

关键参数说明

1. damping (阻尼系数，默认0.5)：

   • 控制消息传递的阻尼程度(0.5-1)

   • 较高的值可以防止数值振荡，但会减慢收敛速度

2. preference (偏向参数)：

   • 控制产生多少聚类

   • 通常设置为相似度的中位数

   • 值越大，产生的聚类越多

3. affinity (相似度计算方式)：

   • 'euclidean'：使用负欧氏距离

   • 'precomputed'：使用预先计算的相似度矩阵

4. max_iter (最大迭代次数，默认200)：

   • 算法运行的最大迭代次数

5. convergence_iter (收敛迭代次数，默认15)：

   • 连续多少次迭代没有变化就认为收敛

4. 实际应用案例

案例1：文档聚类

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.cluster import AffinityPropagation
import pandas as pd# 示例文档
documents = ["机器学习是人工智能的一个分支","深度学习使用神经网络","Python是一种编程语言","Java也是一种编程语言","监督学习需要标签数据","无监督学习发现数据中的模式"
]# 将文档转换为TF-IDF特征向量
vectorizer = TfidfVectorizer(stop_words='english')
X = vectorizer.fit_transform(documents)# 运行Affinity Propagation
af = AffinityPropagation(affinity='cosine', damping=0.7).fit(X.toarray())# 输出聚类结果
df = pd.DataFrame({'Document': documents,'Cluster': af.labels_
})
print(df.sort_values('Cluster'))

案例2：图像聚类

from sklearn.cluster import AffinityPropagation
from sklearn.datasets import load_sample_image
from sklearn.feature_extraction.image import extract_patches_2d
import numpy as np# 加载示例图像
china = load_sample_image("china.jpg")# 将图像转换为2D数组(高度×宽度, RGB)
X = china.reshape((-1, 3))# 随机采样部分像素点(减少计算量)
np.random.seed(0)
indices = np.random.choice(X.shape[0], 1000, replace=False)
X_sample = X[indices]# 运行Affinity Propagation
af = AffinityPropagation(damping=0.75, preference=-20000).fit(X_sample)# 可视化聚类中心(代表颜色)
import matplotlib.pyplot as plt
plt.figure(figsize=(10, 5))
for i, color in enumerate(af.cluster_centers_):plt.subplot(1, len(af.cluster_centers_), i+1)plt.imshow(color.reshape(1, 1, 3))plt.axis('off')
plt.show()

5. 参数调优

• 通过网格搜索寻找最佳damping和preference参数
• 使用轮廓系数等指标评估聚类质量
• 对于高维数据，考虑使用余弦相似度
• 可以稀疏化相似度矩阵(只保留每个点的最近邻)

6. 总结

与其他聚类算法的比较

特性	Affinity Propagation	K-Means	DBSCAN	层次聚类
需要指定簇数	否	是	否	是/否
簇形状适应性	任意	球形	任意	任意
处理噪声数据	中等	差	好	中等
时间复杂度	O(N²)	O(NKT)	O(N²)	O(N³)
内存消耗	高	低	中等	高
适合数据规模	小到中等	大	中等	小

Affinity Propagation是一种强大的聚类算法，对于中小规模数据集能够提供非常有价值的聚类结果。特别适用于以下场景：

• 不知道数据中应该有多少个簇

• 数据中存在非球形的簇结构

• 需要找到最具代表性的数据点(exemplars)

在实际应用中的建议：

1. 对数据进行适当的预处理和标准化

2. 尝试不同的preference和damping参数

3. 使用评估指标验证聚类质量

4. 对于大规模数据，考虑使用近似算法或降维技术