数据处理: 亲和聚类-EW帮帮网

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

1. 原理

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

责任度(Responsibility)消息(r(i,k))：
- 表示数据点i适合选择数据点k作为其"代表点"(exemplar)的程度
- 从点i发送到候选代表点k
可用度(Availability)消息(a(i,k))：
- 表示数据点k适合作为数据点i的"代表点"的程度
- 从候选代表点k发送回点i

算法步骤

初始化相似度矩阵：计算所有数据点之间的相似度(通常使用负欧氏距离)
设置偏向参数：对角线元素设置为相同的值(控制产生多少聚类)
迭代更新消息：
- 更新责任度消息
- 更新可用度消息
确定代表点：当消息收敛后，选择代表点并分配聚类

数学表达

相似度矩阵：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 == k
    cluster_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()

关键参数说明

damping (阻尼系数，默认0.5)：
- 控制消息传递的阻尼程度(0.5-1)
- 较高的值可以防止数值振荡，但会减慢收敛速度
preference (偏向参数)：
- 控制产生多少聚类
- 通常设置为相似度的中位数
- 值越大，产生的聚类越多
affinity (相似度计算方式)：
- 'euclidean'：使用负欧氏距离
- 'precomputed'：使用预先计算的相似度矩阵
max_iter (最大迭代次数，默认200)：
- 算法运行的最大迭代次数
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)

在实际应用中的建议：

对数据进行适当的预处理和标准化
尝试不同的preference和damping参数
使用评估指标验证聚类质量
对于大规模数据，考虑使用近似算法或降维技术

数据处理: 亲和聚类