亲和传播聚类算法应用（Affinity Propagation）

亲和传播聚类算法应用（Affinity Propagation）

亲和传播（Affinity Propagation，简称 AP）是一种基于“消息传递”的聚类算法，与 K-Means 等传统聚类方法不同，它不需要用户预先指定簇的数量，而是通过在数据点之间传递相似度信息来自动确定簇数。其核心思想是每个数据点都会向其他数据点发送关于是否可以作为簇中心的“责任”信息，同时也会接收来自其他数据点的“可用性”信息，从而在算法迭代中自我调整，最终找到簇中心。

1. 亲和传播的基本思路

亲和传播算法通过两个主要的消息：责任值 $r_{ij} $ 和可用性值 $a_{ij}$，它首先通过相似度矩阵计算数据点之间的相似性，然后通过迭代更新责任值和可用性值，最终根据这些消息选择簇中心并确定每个数据点所属的簇。

1.1 相似度矩阵

首先，计算数据点之间的相似度矩阵 $S$。给定 NN 个数据点 { x 1 , x 2 , … , x N } \{x_1, x_2, \dots, x_N\} {x1​,x2​,…,xN​}，相似度 $S_{ij}$ 表示数据点 $x_i$ 与 $x_j$ 之间的相似度（通常使用欧几里得距离或余弦相似度等）。

对于欧几里得距离的相似度：

$$S_{ij}=-\Vert x_i-x_j{\Vert }^2$$

对于余弦相似度：

$$S_{ij}=\frac{x_i\cdot x_j}{\Vert x_i\Vert \Vert x_j\Vert }$$

1.2 责任值

责任值 $r_{ij}$ 衡量数据点 $x_j$ 对数据点 $x_i$ 作为簇中心的吸引力。它考虑了数据点 $x_j$ 作为簇中心的相似度，并减去其他数据点作为簇中心时的影响。

责任值的更新公式为：
$$r_{ij}=S_{ij}-\underset{k\ne j}{\max }\left(a_{ik}+S_{ik}\right)$$
其中，$a_{ik}$ 是可用性值，表示数据点 $x_k$ 对数据点 $x_i$ 作为簇中心的支持度。

1.3 可用性值

可用性值 $a_{ij}$ 衡量数据点 $x_i$ 是否支持数据点 $x_j$ 作为簇中心。它表示的是数据点 $x_i$ 在选择簇中心时对其他点的支持情况。

可用性值的更新公式为：
$$a_{ij}=\min \left(0,r_{jj}+\sum _{k\ne j}\max (0,r_{kj})\right)$$
其中，$r_{jj}$ 是数据点 $x_j$ 对自己作为簇中心的责任值，其他项为所有其他点对 $x_j$ 作为簇中心的支持。

1.4 簇中心选择

在每次更新责任值和可用性值后，亲和传播算法会根据这些信息为每个数据点选择一个簇中心。簇中心是根据责任值和可用性值之和来确定的。

对于数据点 $x_i$，其簇中心 $c_i$ 是使得责任值与可用性值之和最大化的点：
$$c_i=\arg \underset{j}{\max }\left(r_{ij}+a_{ij}\right)$$
即选择 $r_{ij}+a_{ij}$ 最大的 $j$ 作为数据点 $x_i$ 的簇中心。

1.5 消息传递的迭代更新

亲和传播算法是一个迭代过程，算法不断更新责任值 $r_{ij}$ 和可用性值 $a_{ij}$，直到达到收敛条件。收敛条件通常是责任值和可用性值的变化小于某个阈值，或者达到最大迭代次数。

1.6 簇的形成

每一轮更新后，簇中心被选定为具有最大 $r_{ij}+a_{ij}$ 的点。如果每个点的簇中心没有发生变化，则认为算法已经收敛，完成聚类。

1.7 完整的数学过程

1. 初始化：
   • 计算相似度矩阵 $S_{ij}$。
   • 初始化责任值和可用性值为零：$r_{ij}=0$, $a_{ij}=0$。
2. 迭代更新：
   • 更新责任值： $r_{ij}=S_{ij}-{\max }_{k\ne j}\left(a_{ik}+S_{ik}\right)$。
   • 更新可用性值： a_{ij} = \min \left( 0, r_{jj} + \sum_{k \neq j} \max(0, r_{kj}) \right)$。
3. 簇中心选择：
   • 选择簇中心 $c_i=\arg {\max }_j\left(r_{ij}+a_{ij}\right)$。
4. 收敛检测：
   • 如果责任值和可用性值的变化小于阈值，则算法收敛。

---

2. 参数说明

通过调整这些参数，可以根据实际数据的特点优化亲和传播模型的性能和效果。

from sklearn.cluster import AffinityPropagationap = AffinityPropagation(*,damping=0.5,max_iter=200,convergence_iter=15,copy=True,preference=None,affinity='euclidean',verbose=False,random_state=None,
)

1. damping (float, 默认=0.5):
   • 该参数控制消息更新的平滑度。它帮助防止模型在每次迭代时震荡过大。值的范围是[0.5, 1.0)。
   • 较大的 damping 值可以增强稳定性，但可能使算法收敛较慢。
2. max_iter (int, 默认=200):
   • 该参数控制最大迭代次数。当达到最大迭代次数时，算法会停止运行，无论是否已收敛。
   • 如果数据量较大或收敛较慢，可以增加这个值。
3. convergence_iter (int, 默认=15):
   • 如果相邻的迭代中，簇中心的变化小于某个阈值时，算法就会停止。convergence_iter 控制的是连续多少次迭代簇中心变化小于阈值才认为已经收敛。
   • 增加该值会要求更强的收敛条件，可能导致更长的计算时间。
4. copy (bool, 默认=True):
   • 如果为 True，会对输入的数据进行复制，这样原始数据不会被修改。如果为 False，则会修改原始数据。
   • 通常保持 True，除非你非常确定不需要保留原始数据。
5. preference (array-like, 默认=None):
   • 该参数指定了每个数据点被选为簇中心的偏好值。它的大小应该与数据点数量相等。
   • 如果设置为 None，则默认将所有点的偏好值设置为 -2，即倾向于较小的簇数。调整该值可以影响簇的数量。
6. affinity ({‘euclidean’, ‘manhattan’, ‘cosine’}, 默认=‘euclidean’):
   • 用来计算数据点间相似度的度量方法。常用的度量方法包括：
     • 'euclidean'：欧几里得距离
     • 'manhattan'：曼哈顿距离
     • 'cosine'：余弦相似度
   • 根据数据的特性选择合适的相似度度量。
7. verbose (bool, 默认=False):
   • 如果为 True，则会输出算法运行时的详细信息。对于调试和了解算法的迭代过程有帮助。
8. random_state (int, RandomState instance or None, 默认=None):
   • 控制随机数生成器的种子。如果设置为 None，则使用随机的种子。如果需要重现实验结果，可以设置为一个整数值。

---

3. 注意事项

1. 计算复杂度：亲和传播算法对数据点数目较为敏感，适合中小规模数据（< 1000 个样本）。
2. 结果可解释性：簇数由算法动态决定，但可以通过调整 preference 来影响结果。
3. 内存限制：需要计算完整的相似度矩阵，对于高维或大规模数据可能会占用较多内存。

---

4. 亲和传播聚类样例

4.1 生成样例数据

# 导入必要的库
import numpy as np  # 用于数组和数学运算from sklearn import metrics  # 导入用于评估聚类效果的评估指标
from sklearn.cluster import AffinityPropagation  # 导入亲和传播聚类算法
from sklearn.datasets import make_blobs  # 用于生成测试用的聚类数据集# 设置聚类中心
centers = [[1, 1], [-1, -1], [1, -1]]  # 设置三个聚类的中心点坐标# 生成模拟数据，包含300个样本，数据点以centers为中心分布，标准差为0.5，随机种子设为0
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0.5, random_state=0
)

4.2 计算亲和传播

# 创建亲和传播聚类模型，设置偏好值为-50，并使用随机种子0
af = AffinityPropagation(preference=-50, random_state=0).fit(X)# 获取聚类中心的索引
cluster_centers_indices = af.cluster_centers_indices_# 获取每个数据点的聚类标签
labels = af.labels_# 计算聚类的数量
n_clusters_ = len(cluster_centers_indices)# 打印聚类分析结果
print("估计的聚类数量: %d" % n_clusters_)  # 输出聚类的数量
print("同质性: %0.3f" % metrics.homogeneity_score(labels_true, labels))  # 输出同质性得分
print("完整性: %0.3f" % metrics.completeness_score(labels_true, labels))  # 输出完整性得分
print("V-度量: %0.3f" % metrics.v_measure_score(labels_true, labels))  # 输出V-度量得分
print("调整兰德指数: %0.3f" % metrics.adjusted_rand_score(labels_true, labels))  # 输出调整兰德指数
print("调整互信息: %0.3f"% metrics.adjusted_mutual_info_score(labels_true, labels)
)  # 输出调整互信息得分
print("轮廓系数: %0.3f"% metrics.silhouette_score(X, labels, metric="sqeuclidean")
)  # 输出轮廓系数

估计的聚类数量: 3
同质性: 0.872
完整性: 0.872
V-度量: 0.872
调整兰德指数: 0.912
调整互信息: 0.871
轮廓系数: 0.753

4.3 可视化结果

# 绘图
plt.close("all")  # 关闭所有已打开的图形窗口
plt.figure(1)  # 创建新的图形窗口
plt.clf()  # 清除当前图形中的所有内容# 设置颜色循环，用于不同聚类的颜色
colors = plt.cycler("color", plt.cm.viridis(np.linspace(0, 1, 4)))# 对每个聚类进行可视化
for k, col in zip(range(n_clusters_), colors):class_members = labels == k  # 获取属于当前聚类的数据点cluster_center = X[cluster_centers_indices[k]]  # 获取当前聚类的中心点plt.scatter(X[class_members, 0], X[class_members, 1], color=col["color"], marker="."  # 绘制当前聚类的数据点)plt.scatter(cluster_center[0], cluster_center[1], s=14, color=col["color"], marker="o"  # 绘制聚类中心)# 绘制聚类中心与数据点之间的连线for x in X[class_members]:plt.plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], color=col["color"])# 设置图表标题
plt.title("估计的聚类数量: %d" % n_clusters_)
plt.show()  # 显示图表

---

5. 对鸢尾花数据集进行亲和传播算法聚类

5.1 导入并可视化鸢尾花数据集

import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.decomposition import PCA
from sklearn.datasets import load_iris
import pandas as pd# 设置主题和字体
sns.set_theme(style="darkgrid", palette="Set2", font="SimHei", rc={"axes.unicode_minus": False})  # 加载鸢尾花数据集
iris = load_iris()
X = iris.data
y = iris.target# 进行PCA降维
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X)

# 创建一个包含PCA结果和目标变量的DataFrame
df = pd.DataFrame(X_pca, columns=['主成分1', '主成分2'])
df['类别'] = iris.target_names[y]# 绘制PCD图，修改点的大小、颜色和透明度
plt.figure(figsize=(10, 8))
sns.scatterplot(data=df, x='主成分1', y='主成分2', hue='类别', s=150, marker='o', edgecolor='black', alpha=0.7
)# 设置标题、标签，并美化图表
plt.title('鸢尾花数据集的主成分分析（PCA）', fontsize=16, fontweight='bold')
plt.xlabel('主成分 1', fontsize=14)
plt.ylabel('主成分 2', fontsize=14)
plt.legend(title='类别', title_fontsize='14', loc='best', fontsize='13')# 显示图表
plt.show()

5.2 进行亲和传播聚类

# 进行亲和传播聚类
affinity_propagation = AffinityPropagation(random_state=42)
affinity_propagation.fit(X_pca)# 获取聚类标签
labels = affinity_propagation.labels_# 创建一个包含PCA降维结果和聚类标签的DataFrame
df = pd.DataFrame(X_pca, columns=['主成分1', '主成分2'])
df['聚类集群'] = labels# 绘制二维散点图，使用PCA降维后的主成分
plt.figure(figsize=(10, 8))
sns.scatterplot(data=df, x='主成分1', y='主成分2', hue='聚类集群',palette="Set1", s=100, marker='o', edgecolor='black', alpha=0.7
)# 设置标题、标签，并美化图表
plt.title('鸢尾花数据集的亲和传播聚类（PCA）', fontsize=16, fontweight='bold')
plt.xlabel('主成分 1', fontsize=14)
plt.ylabel('主成分 2', fontsize=14)
plt.legend(title='聚类集群', title_fontsize='13', loc='best', fontsize='12')# 显示图表
plt.show()

5.3 对模型进行改进

# 进行亲和传播聚类
affinity_propagation = AffinityPropagation(preference=-50, # 设置平滑度damping=0.9, 	# 设置偏好值random_state=42
)

5.4 检验模型的准确率

from sklearn.metrics import adjusted_rand_score# 获取真实标签
y = iris.target
# 获取聚类标签
cluster_labels = affinity_propagation.labels_# 计算聚类与真实标签的调整兰德指数（ARI）
ari_score = adjusted_rand_score(y, cluster_labels)
print(f'调整兰德指数（ARI）：{ari_score:.4f}')

调整兰德指数（ARI）：0.7859

---

6. 对于社交网络中用户的社交属性进行强度划分

6.1 生成模拟数据

import networkx as nx
import seaborn as sns
import matplotlib.pyplot as plt
from faker import Faker
import random
from sklearn.manifold import TSNE
from sklearn.cluster import AffinityPropagation
from sklearn.preprocessing import StandardScaler
from sklearn.metrics.pairwise import euclidean_distances
from sklearn.metrics import pairwise_distances
from sklearn.decomposition import PCA
import numpy as np
import pandas as pd
from adjustText import adjust_text# 可视化配置
sns.set_theme(style="whitegrid", font="SimHei", rc={"axes.unicode_minus": False})
plt.rcParams['font.sans-serif'] = ['SimHei']

# 初始化 Faker 实例
fake = Faker('zh_CN')# 创建社交网络图
G = nx.Graph()
num_users = 50# 添加节点
for _ in range(num_users):G.add_node(fake.name())# 创建社交关系（修改为更合理的连接方式）
all_nodes = list(G.nodes)
for node in G.nodes:num_connections = min(len(all_nodes)-1, np.random.poisson(lam=3))  # 泊松分布模拟社交关系friends = random.sample([n for n in all_nodes if n != node], num_connections)G.add_edges_from([(node, friend) for friend in friends])# 可视化社交关系网络
plt.figure(figsize=(12, 12))
pos = nx.spring_layout(G, seed=42)  # 使用 spring 布局来定位节点
nx.draw(G, pos, with_labels=True, node_size=1000, node_color="skyblue", font_size=10, font_weight="bold", edge_color="gray"
)plt.title("社交关系网络图", fontsize=15)
plt.show()

6.2 将NX图转换为指标数据

# 计算中心性指标
centrality_metrics = {'度中心性': nx.degree_centrality(G),'介数中心性': nx.betweenness_centrality(G),'接近中心性': nx.closeness_centrality(G),'特征向量中心性': nx.eigenvector_centrality(G, max_iter=1000)
}# 创建DataFrame
df = pd.DataFrame({'节点': list(G.nodes),**{metric: [values[node] for node in G.nodes] for metric, values in centrality_metrics.items()}
})# 数据标准化
features = ['度中心性', '介数中心性', '接近中心性', '特征向量中心性']
X_scaled = StandardScaler().fit_transform(df[features])

6.3 对数据进行亲和传播聚类

# 亲和传播聚类
ap = AffinityPropagation(affinity='euclidean', random_state=42)
df['聚类标签'] = ap.fit_predict(X_scaled)
n_clusters = len(ap.cluster_centers_indices_)# PCA降维
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X_scaled)
df[['PCA1', 'PCA2']] = X_pca

# 可视化降维后的数据，按聚类标签着色
plt.figure(figsize=(10, 8))
sns.scatterplot(x='PCA1', y='PCA2', hue='聚类标签', data=df, palette='Set1', s=100, marker='o')# # 在每个点上添加名称
# for i in range(df.shape[0]):
#     plt.text(df['PCA1'][i], df['PCA2'][i], df['节点'][i], fontsize=9, ha='right')# 添加标题和标签
plt.title(f'PCA降维后的亲和传播聚类结果（聚类数: {n_clusters}）', fontsize=16)
plt.xlabel('PCA 1', fontsize=12)
plt.ylabel('PCA 2', fontsize=12)# 显示图例
plt.legend(title='聚类标签')# 显示图表
plt.show()

6.4 改进模型参数

# 亲和传播聚类
ap = AffinityPropagation(damping=0.75, 	# 设置平滑度preference=-30, # 设置偏好值affinity='euclidean', random_state=42
)

6.5 对亲和传播聚类的可视化结果进行美化

# 获取聚类中心数据
centers_scaled = X_scaled[ap.cluster_centers_indices_]
centers_pca = pca.transform(centers_scaled)
df_centers = pd.DataFrame({'PCA1': centers_pca[:, 0],'PCA2': centers_pca[:, 1],'聚类标签': range(n_clusters)
})# 可视化配置
plt.figure(figsize=(14, 10))
colors = plt.cm.tab20(np.linspace(0, 1, n_clusters))
marker_size = 300          # 普通节点大小
center_size = 300          # 中心点大小
# edge_width = 0.8           # 边缘线宽
center_marker = 'o'        # 中心点标记符号
alpha = 1                # 透明度# 绘制普通节点
for k, col in zip(range(n_clusters), colors):class_members = df['聚类标签'] == kplt.scatter(df[class_members]['PCA1'], df[class_members]['PCA2'],color=col, marker=".", s=marker_size, edgecolor='w', # linewidth=edge_width, label=f"集群 {k}")# 绘制聚类中心
for k, col in zip(range(n_clusters), colors):center_mask = df_centers['聚类标签'] == kif df_centers[center_mask].shape[0] > 0:plt.scatter(df_centers[center_mask]['PCA1'], df_centers[center_mask]['PCA2'],color=col, marker=center_marker, s=center_size,# edgecolor='k', # linewidth=edge_width*1.5,)# 绘制聚类中心与节点之间的连线
for k, col in zip(range(n_clusters), colors):class_members = df['聚类标签'] == kcenter_mask = df_centers['聚类标签'] == kif df_centers[center_mask].shape[0] > 0:center_pca1 = df_centers[center_mask]['PCA1'].values[0]center_pca2 = df_centers[center_mask]['PCA2'].values[0]for i in df[class_members].index:plt.plot([center_pca1, df.loc[i, 'PCA1']],[center_pca2, df.loc[i, 'PCA2']],color=col, alpha=0.3, linewidth=0.8)# 添加节点标签
texts = []
for _, row in df.iterrows():texts.append(plt.text(row['PCA1'], row['PCA2'], row['节点'],fontsize=10, ha="center", va="center", fontweight='bold', alpha=0.8))# 标签避让处理
adjust_text(texts,arrowprops=dict(arrowstyle='->', color='gray', lw=0.8, alpha=0.6),expand_points=(1.5, 1.5),expand_text=(1.5, 1.5),force_text=(0.5, 0.5))# 设置标题和图例
plt.title(f"社交网络聚类分析 (PCA降维 | 聚类数: {n_clusters}）", fontsize=15)
plt.legend(title="聚类标签", loc="best", fontsize=12)
plt.xlabel("PCA 1", fontsize=12)
plt.ylabel("PCA 2", fontsize=12)
plt.grid(True, linestyle='--', alpha=0.4)
plt.show()

6.6 将聚类结果映射至社交网络图上

# 将聚类标签存入节点的属性中
for node, cluster in zip(G.nodes, df['聚类标签']):G.nodes[node]['集群'] = cluster  # 为每个节点添加 'cluster' 属性# 可视化配置
plt.figure(figsize=(12, 12))
pos = nx.spring_layout(G, seed=42)# 创建颜色映射
color_map = plt.cm.tab20(np.linspace(0, 1, n_clusters))
node_colors = [color_map[G.nodes[node]['集群']] for node in G.nodes]# 绘制网络节点
nx.draw_networkx_nodes(G, pos, node_size=600, node_color=node_colors, edgecolors='black', linewidths=0.8)
nx.draw_networkx_edges(G, pos, edge_color='gray', alpha=0.4)# 智能标签系统
texts = []
for node, (x, y) in pos.items():texts.append(plt.text(x, y, node, fontsize=9, ha='center', va='center',bbox=dict(boxstyle='round', facecolor='white', edgecolor='none',alpha=0.8)))# 调整标签位置
adjust_text(texts, precision=0.8,expand_text=(1.2, 1.2),expand_points=(1.2, 1.2),force_text=(0.3, 0.3),arrowprops=dict(arrowstyle='-', color='gray', lw=0.5, alpha=0.6))# 设置标题
plt.title("基于聚类结果的社交网络可视化", fontsize=15)
plt.axis('off')  # 关闭坐标轴
plt.show()