AGNES 层次聚类实战：Python 3步实现3种簇间距离计算（附完整代码） AGNES层次聚类实战Python实现与三种簇间距离计算深度解析1. 初识AGNES自底向上的层次聚类艺术想象你面前有一堆散落的乐高积木如何将它们按照颜色、形状或功能进行分类AGNES算法就像一位耐心的乐高分类师从最微小的单元开始逐步构建出层次分明的分类体系。这种自底向上的聚合策略正是层次聚类的核心魅力所在。AGNESAgglomerative Nesting作为层次聚类的经典实现其工作流程如同精心编排的交响乐初始化阶段每个数据点视为独立簇迭代合并计算所有簇间距离合并最近的两个簇终止条件达到预设簇数量或形成单一簇# AGNES算法伪代码示例 def AGNES(D, k): # 初始化每个样本作为独立簇 C [[x] for x in D] while len(C) k: # 找出距离最近的两个簇 i, j find_closest_pair(C) # 合并簇 C[i].extend(C[j]) C.pop(j) return C三种经典簇间距离度量方式对比距离类型计算方式算法别称特点最小距离两簇最近样本距离单链接(Single-linkage)对噪声敏感易形成链式簇最大距离两簇最远样本距离全链接(Complete-linkage)偏好紧凑球形簇计算量较大平均距离两簇所有样本平均距离均链接(Average-linkage)平衡前两者特点常用选择专业提示在生物信息学领域单链接特别适合基因序列聚类而市场营销用户分群更常使用平均距离以获得平衡的群体划分。2. 距离计算实战从数学公式到Python实现理解簇间距离的计算是掌握AGNES的关键。让我们深入三种距离的数学本质及其Python实现。2.1 最小距离敏锐的局部观察者最小距离公式 [ d_{min}(C_i, C_j) \min_{x\in C_i, z\in C_j} \text{dist}(x,z) ]import numpy as np def calc_min_dist(cluster1, cluster2): 计算簇间最小距离单链接 :param cluster1: 簇1样本数组形状(n_samples, n_features) :param cluster2: 簇2样本数组形状(m_samples, n_features) :return: 最小欧氏距离 min_dist np.inf for x in cluster1: for z in cluster2: dist np.linalg.norm(x - z) # 欧氏距离 if dist min_dist: min_dist dist return min_dist性能优化技巧对于高维数据可使用scipy的cdist函数向量化计算from scipy.spatial.distance import cdist def calc_min_dist_vectorized(cluster1, cluster2): dist_matrix cdist(cluster1, cluster2, euclidean) return dist_matrix.min()2.2 最大距离全局视野的守护者最大距离公式 [ d_{max}(C_i, C_j) \max_{x\in C_i, z\in C_j} \text{dist}(x,z) ]def calc_max_dist(cluster1, cluster2): 计算簇间最大距离全链接 :param cluster1: 簇1样本数组 :param cluster2: 簇2样本数组 :return: 最大欧氏距离 max_dist 0 for x in cluster1: for z in cluster2: dist np.linalg.norm(x - z) if dist max_dist: max_dist dist return max_dist2.3 平均距离理性的中庸之道平均距离公式 [ d_{avg}(C_i, C_j) \frac{1}{|C_i||C_j|}\sum_{x\in C_i}\sum_{z\in C_j} \text{dist}(x,z) ]def calc_avg_dist(cluster1, cluster2): 计算簇间平均距离均链接 :param cluster1: 簇1样本数组 :param cluster2: 簇2样本数组 :return: 平均欧氏距离 total_dist 0 count 0 for x in cluster1: for z in cluster2: total_dist np.linalg.norm(x - z) count 1 return total_dist / count if count 0 else 0实际应用陷阱当簇规模差异较大时平均距离可能偏向较大簇的特征高维数据中所有距离会趋于相似维度诅咒解决方案数据标准化或考虑余弦相似度等替代指标3. 完整AGNES实现从理论到生产级代码现在我们将各个模块整合构建完整的AGNES算法实现。这个版本加入了距离矩阵优化和合并策略选择。import numpy as np from scipy.spatial.distance import squareform, pdist class AGNES: def __init__(self, n_clusters3, linkageaverage): :param n_clusters: 目标簇数量 :param linkage: 链接策略可选 min, max, average self.n_clusters n_clusters self.linkage linkage self.clusters [] def _initialize_dist_matrix(self, X): 计算初始距离矩阵 pairwise_dist pdist(X, euclidean) return squareform(pairwise_dist) def _update_dist_matrix(self, dist_matrix, i, j): 合并簇后更新距离矩阵 if self.linkage min: new_dists np.minimum(dist_matrix[i], dist_matrix[j]) elif self.linkage max: new_dists np.maximum(dist_matrix[i], dist_matrix[j]) else: # average size_i len(self.clusters[i]) size_j len(self.clusters[j]) new_dists (dist_matrix[i]*size_i dist_matrix[j]*size_j)/(size_isize_j) # 删除被合并簇的行列 dist_matrix np.delete(dist_matrix, j, axis0) dist_matrix np.delete(dist_matrix, j, axis1) # 更新保留簇的距离 dist_matrix[i] new_dists dist_matrix[:,i] new_dists np.fill_diagonal(dist_matrix, np.inf) return dist_matrix def fit(self, X): 训练AGNES模型 n_samples X.shape[0] self.clusters [[i] for i in range(n_samples)] # 存储样本索引 # 初始化距离矩阵 dist_matrix self._initialize_dist_matrix(X) while len(self.clusters) self.n_clusters: # 找出最小距离对应的簇对 i, j np.unravel_index(np.argmin(dist_matrix), dist_matrix.shape) if i j: # 确保i j i, j j, i # 合并簇 self.clusters[i].extend(self.clusters[j]) self.clusters.pop(j) # 更新距离矩阵 dist_matrix self._update_dist_matrix(dist_matrix, i, j) # 将簇索引转换为实际样本 self.labels_ np.zeros(n_samples, dtypeint) for cluster_idx, cluster in enumerate(self.clusters): for sample_idx in cluster: self.labels_[sample_idx] cluster_idx return self关键优化点分析使用pdist和squareform高效计算初始距离矩阵动态更新距离矩阵而非每次重新计算复杂度从O(n³)降至O(n²)支持三种链接策略的灵活切换内存友好仅存储样本索引而非实际数据工程实践建议当处理超过1万样本时考虑使用近似算法或采样策略。AGNES的O(n³)时间复杂度使其难以扩展到超大规模数据集。4. 实战对比三种距离度量如何影响聚类结果让我们通过一个实际案例直观展示不同链接策略对聚类结果的影响。我们将使用经典的鸢尾花数据集并聚焦于花瓣长度和宽度两个特征以便可视化。import matplotlib.pyplot as plt from sklearn.datasets import load_iris from sklearn.preprocessing import StandardScaler # 数据准备 iris load_iris() X iris.data[:, 2:4] # 只取花瓣长度和宽度 scaler StandardScaler() X_scaled scaler.fit_transform(X) # 创建三种AGNES实例 agnes_min AGNES(n_clusters3, linkagemin) agnes_max AGNES(n_clusters3, linkagemax) agnes_avg AGNES(n_clusters3, linkageaverage) # 训练并获取结果 labels_min agnes_min.fit(X_scaled).labels_ labels_max agnes_max.fit(X_scaled).labels_ labels_avg agnes_avg.fit(X_scaled).labels_ # 可视化函数 def plot_clusters(X, labels, title, ax): scatter ax.scatter(X[:,0], X[:,1], clabels, cmapviridis, s30) ax.set_title(title) ax.set_xlabel(Petal length (standardized)) ax.set_ylabel(Petal width (standardized)) # 绘制对比图 fig, (ax1, ax2, ax3) plt.subplots(1, 3, figsize(18, 5)) plot_clusters(X_scaled, labels_min, Min Linkage (Single), ax1) plot_clusters(X_scaled, labels_max, Max Linkage (Complete), ax2) plot_clusters(X_scaled, labels_avg, Average Linkage, ax3) plt.tight_layout() plt.show()三种策略结果差异解读最小链接单链接形成链式簇结构对噪声敏感可能产生不期望的长条形簇适合发现非球形簇但对离群点抵抗力弱最大链接全链接产生紧凑的球形簇对噪声鲁棒但可能过度分割自然簇偏好大小相近的簇对簇大小差异敏感平均链接平衡前两者的优缺点产生相对均匀的簇大小实际应用中最常用的选择行业应用选择指南生物信息学单链接用于基因序列聚类能发现相似功能基因客户细分平均链接适合大多数营销分析场景图像分割全链接有助于获得均匀的图像区域异常检测单链接可识别离群点最后合并的点5. 高级话题与性能优化5.1 树状图理解聚类过程的X光片树状图Dendrogram是层次聚类的可视化利器能完整展示合并过程和距离变化。使用SciPy可以轻松生成from scipy.cluster.hierarchy import dendrogram, linkage # 计算链接矩阵 Z linkage(X_scaled, methodaverage) # 绘制树状图 plt.figure(figsize(12, 6)) dendrogram(Z, truncate_modelastp, p12, show_leaf_countsTrue) plt.title(Truncated Dendrogram (Average Linkage)) plt.xlabel(Cluster Size) plt.ylabel(Distance) plt.show()树状图解读要点y轴高度表示合并时的簇间距离横轴顺序叶子节点排列顺序影响视觉效果切割高度决定最终簇数量反映聚类松紧度5.2 内存优化策略原始AGNES需要O(n²)内存存储距离矩阵对于大规模数据可考虑以下优化稀疏矩阵技术当许多距离为0或可忽略时批处理磁盘存储将距离矩阵分块存储在磁盘近似算法如BIRCH、CURE等改进算法# 内存友好的距离计算示例 def sparse_agnes(X, n_clusters, batch_size1000): n_samples X.shape[0] clusters [[i] for i in range(n_samples)] while len(clusters) n_clusters: min_dist np.inf best_pair (0, 1) # 分批计算距离矩阵 for i in range(0, len(clusters), batch_size): for j in range(0, len(clusters), batch_size): # 计算批次内簇间距离 pass # 实现省略 # 合并最佳簇对 i, j best_pair clusters[i].extend(clusters[j]) clusters.pop(j) return clusters5.3 并行计算加速利用多核CPU加速距离计算from joblib import Parallel, delayed def parallel_distance_calculation(clusters, n_jobs4): def compute_chunk(start, end): # 计算部分距离矩阵 pass n_clusters len(clusters) chunk_size n_clusters // n_jobs results Parallel(n_jobsn_jobs)( delayed(compute_chunk)(i, min(ichunk_size, n_clusters)) for i in range(0, n_clusters, chunk_size) ) # 合并结果并找出最小距离 return min(results, keylambda x: x[2])6. 真实案例红酒品质聚类分析让我们将AGNES应用于UCI红酒数据集展示完整的数据科学工作流程。import pandas as pd from sklearn.preprocessing import StandardScaler from sklearn.metrics import silhouette_score # 数据加载与预处理 url https://archive.ics.uci.edu/ml/machine-learning-databases/wine-quality/winequality-red.csv data pd.read_csv(url, sep;) X data.drop(quality, axis1) scaler StandardScaler() X_scaled scaler.fit_transform(X) # 寻找最佳簇数 silhouette_scores [] for k in range(2, 9): agnes AGNES(n_clustersk, linkageaverage) labels agnes.fit(X_scaled).labels_ score silhouette_score(X_scaled, labels) silhouette_scores.append(score) # 可视化轮廓系数 plt.plot(range(2,9), silhouette_scores, markero) plt.xlabel(Number of clusters) plt.ylabel(Silhouette Score) plt.title(Finding Optimal Cluster Number) plt.show() # 使用最佳k值训练模型 best_k np.argmax(silhouette_scores) 2 # 2因为从k2开始 final_model AGNES(n_clustersbest_k, linkageaverage) final_labels final_model.fit(X_scaled).labels_ # 分析聚类特征 data[cluster] final_labels cluster_profiles data.groupby(cluster).mean() print(cluster_profiles)分析结果解读轮廓系数建议的最佳簇数为3聚类分析揭示簇0高酒精、低酸度簇1低酒精、高硫酸盐簇2中等酒精、高挥发性酸度业务意义可为不同口味偏好群体定制营销策略7. 常见陷阱与解决方案陷阱1忽略特征缩放症状距离计算被大范围特征主导修复标准化StandardScaler或归一化MinMaxScaler陷阱2高维数据失效症状所有距离趋于相似聚类无意义修复降维PCA或使用余弦相似度陷阱3链式效应单链接症状形成长条形不合理簇修复改用全链接或平均链接陷阱4确定最佳簇数解决方案轮廓系数Silhouette Score肘部法则Within-cluster SSE间隙统计Gap Statistic# 使用间隙统计确定最佳簇数示例 from gap_statistic import OptimalK optimalK OptimalK(parallel_backendjoblib) n_clusters optimalK(X_scaled, cluster_arrayrange(1, 10)) print(fOptimal clusters: {n_clusters})8. AGNES与其他聚类算法对比算法优点缺点适用场景AGNES层次结构可视化多种链接策略O(n³)时间复杂度内存消耗大中小数据集需要层次关系的场景K-Means计算高效线性复杂度需预设k值仅发现球形簇大规模数据已知簇数DBSCAN自动确定簇数发现任意形状对参数敏感高维效果差噪声数据密度变化明显谱聚类能发现复杂结构图理论基础计算复杂度高需相似度矩阵非凸形状图结构数据混合策略建议先用K-Means快速发现初始簇中心对每个K-Means簇应用AGNES获取子结构特别适合大规模数据下的精细聚类需求9. 前沿进展与扩展阅读近年来层次聚类领域的重要发展近似算法FastClusterO(n²)时间复杂度的优化实现HDBSCAN*结合密度聚类的层次方法GPU加速cuMLNVIDIA开发的GPU加速聚类库使用CUDA实现并行距离计算分布式版本Spark上的层次聚类实现基于MapReduce的分治策略推荐阅读材料《数据挖掘概念与技术》第3版聚类分析章节Scikit-learn文档中的AgglomerativeClustering实现论文《A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm》# 使用GPU加速的层次聚类示例需RAPIDS环境 from cuml.cluster import AgglomerativeClustering gpu_model AgglomerativeClustering(n_clusters3, linkagesingle) gpu_labels gpu_model.fit_predict(X_scaled)10. 工程实践建议数据预处理检查清单处理缺失值删除或填充标准化数值特征编码类别变量考虑特征重要性随机森林特征重要性生产环境部署要点实现增量聚类partial_fit添加缓存机制存储距离矩阵监控聚类漂移概念漂移检测结果解释技巧计算每个特征的簇间方差ANOVA可视化平行坐标图构建聚类决策树解释规则# 聚类结果解释工具示例 import seaborn as sns # 平行坐标图 plt.figure(figsize(12,6)) sns.lineplot(datadata.melt(id_varscluster), xvariable, yvalue, huecluster) plt.xticks(rotation45) plt.title(Parallel Coordinates Plot for Cluster Interpretation) plt.show()11. 完整项目示例新闻主题聚类让我们通过一个端到端项目展示AGNES在文本聚类中的应用。我们将使用20 Newsgroups数据集演示从文本到聚类的完整流程。from sklearn.datasets import fetch_20newsgroups from sklearn.feature_extraction.text import TfidfVectorizer from sklearn.decomposition import TruncatedSVD from sklearn.pipeline import make_pipeline from sklearn.preprocessing import Normalizer # 加载数据 categories [sci.space, comp.graphics, rec.sport.baseball] newsgroups fetch_20newsgroups(categoriescategories) X_text newsgroups.data # 文本向量化 vectorizer TfidfVectorizer(max_features10000, stop_wordsenglish) X_tfidf vectorizer.fit_transform(X_text) # 降维 svd TruncatedSVD(100) normalizer Normalizer(copyFalse) pipeline make_pipeline(svd, normalizer) X_reduced pipeline.fit_transform(X_tfidf) # 聚类 agnes AGNES(n_clusters3, linkageaverage) labels agnes.fit(X_reduced).labels_ # 评估 from sklearn.metrics import adjusted_rand_score true_labels newsgroups.target ari adjusted_rand_score(true_labels, labels) print(fAdjusted Rand Index: {ari:.3f}) # 查看每个簇的关键词 def get_top_keywords(cluster_idx, n_keywords10): cluster_mask (labels cluster_idx) cluster_tfidf X_tfidf[cluster_mask] avg_tfidf np.asarray(cluster_tfidf.mean(axis0)).ravel() top_indices avg_tfidf.argsort()[-n_keywords:][::-1] return [vectorizer.get_feature_names_out()[i] for i in top_indices] for i in range(3): print(fCluster {i} keywords:, get_top_keywords(i))项目亮点展示文本数据的特殊处理流程高维稀疏矩阵的降维技巧聚类结果的定量评估ARI关键词提取解释聚类主题12. 算法变体与创新思路基础AGNES的几种改进方向BIRCH算法使用CF树压缩数据适合超大规模数据两阶段微簇生成全局聚类CURE算法每个簇用多个代表点表示对异常值鲁棒能发现非球形簇ROCK算法专为分类数据设计使用链接links而非距离适合市场篮子分析# BIRCH算法示例 from sklearn.cluster import Birch birch Birch(n_clusters3, threshold0.5) birch_labels birch.fit_predict(X_scaled)创新应用思路动态聚类随时间推移更新层次结构半监督聚类结合少量标记数据指导合并过程多视图聚类整合来自不同来源的特征13. 数学深度距离度量的选择艺术除了欧氏距离AGNES可以适配多种距离度量余弦相似度适合文本等高维数据 [ \text{cosine}(x,z) \frac{x \cdot z}{|x||z|} ]马氏距离考虑特征相关性 [ d_M(x,z) \sqrt{(x-z)^T S^{-1}(x-z)} ] 其中S是协方差矩阵动态时间规整时间序列专用# 自定义距离度量示例 def manhattan_distance(cluster1, cluster2): return np.sum(np.abs(cluster1[:, np.newaxis] - cluster2), axis(1,2)).min() class CustomAGNES(AGNES): def __init__(self, n_clusters3, distance_metriceuclidean): self.distance_metric distance_metric super().__init__(n_clusters) def _calc_distance(self, a, b): if self.distance_metric manhattan: return manhattan_distance(a, b) elif self.distance_metric cosine: return cosine_distance(a, b) else: return super()._calc_distance(a, b)距离度量选择指南数据类型推荐距离理由数值型欧氏/马氏保持几何性质文本余弦相似度忽略向量大小专注方向时间序列DTW处理不同长度和相位差分类数据Jaccard处理集合相似度14. 可视化进阶交互式探索工具静态图有时难以充分展示层次结构的复杂性。以下是推荐的交互工具Plotly动态树状图import plotly.figure_factory as ff fig ff.create_dendrogram(X_scaled, orientationleft) fig.update_layout(width800, height800) fig.show()Altair聚类可视化import altair as alt source pd.DataFrame(X_scaled, columns[dim1, dim2]) source[cluster] labels chart alt.Chart(source).mark_circle(size60).encode( xdim1, ydim2, colorcluster:N, tooltip[dim1, dim2, cluster] ).interactive()PyVis网络图 适合展示层次合并过程每个节点代表一个合并事件行业最佳实践使用Tableau/Power BI嵌入聚类结果开发Shiny/Dash交互式探索工具集成到Jupyter Notebook形成可重复分析报告15. 质量评估超越轮廓系数除了常用的轮廓系数层次聚类质量可从多角度评估共表型相关系数CPCC 衡量树状图与原始距离矩阵的一致性 [ \text{CPCC} \frac{\sum_{ij}(d_{ij} - \bar{d})(c_{ij} - \bar{c})}{\sqrt{\sum_{ij}(d_{ij}-\bar{d})^2\sum_{ij}(c_{ij}-\bar{c})^2}} ] 其中d是原始距离c是共表型距离Dunn指数 评估簇分离度和紧密度 [ DI \frac{\min_{1\leq ij\leq k} \delta(C_i,C_j)}{\max_{1\leq l\leq k} \Delta_l} ] δ是簇间距离Δ是簇直径稳定性分析 通过自助采样评估结果一致性# 实现Dunn指数 def dunn_index(X, labels): intra_dists [] for label in np.unique(labels): cluster_points X[labels label] intra_dists.append(np.max(pdist(cluster_points))) max_intra max(intra_dists) inter_dists [] for i in range(len(np.unique(labels))): for j in range(i1, len(np.unique(labels))): ci X[labels i] cj X[labels j] inter_dists.append(np.min(cdist(ci, cj))) min_inter min(inter_dists) return min_inter / max_intra评估策略选择矩阵评估需求推荐指标解读要点簇紧密度轮廓系数接近1最优负值表示错误分配层次质量CPCC0.7表示良好层次结构分离度Dunn指数值越大表示簇分离越好鲁棒性稳定性得分多次运行结果的一致性16. 分布式实现应对海量数据挑战当数据超出单机内存容量时需要分布式AGNES实现。核心思路分块策略将数据划分为多个分区每个worker计算局部距离矩阵协调节点聚合结果MapReduce实现# 伪代码示例 def mapper(cluster_chunk): local_distances compute_pairwise_distances(cluster_chunk) emit(local_distances) def reducer(all_distances): global_matrix merge_distance_matrices(all_distances) find_closest_pair(global_matrix) update_clusters()Spark示例from pyspark.ml.clustering import BisectingKMeans # 近似层次方法 bkm BisectingKMeans(k3, minDivisibleClusterSize2) model bkm.fit(spark_df)实际挑战通信开销合并步骤需要大量数据传输负载均衡后期合并阶段worker利用率下降解决方案考虑近似算法或两阶段先K-Means粗分再局部AGNES17. 时间序列聚类特殊挑战与解决方案时间序列数据对AGNES提出独特要求动态时间规整DTW距离from dtaidistance import dtw def dtw_distance(series1, series2): return dtw.distance(series1, series2)形状特征提取提取统计特征均值、方差使用tsfresh自动生成特征应用小波变换子序列聚类from tslearn.clustering import TimeSeriesKMeans model TimeSeriesKMeans(n_clusters3, metricdtw) labels model.fit_predict(X_timeseries)行业应用物联网设备异常检测股票模式识别心电图分类18. 参数调优网格搜索与贝叶斯优化自动化AGNES参数搜索流程参数空间定义param_grid { n_clusters: range(2, 10), linkage: [min, max, average], affinity: [euclidean, cosine, manhattan] }网格搜索实现from sklearn.model_selection import ParameterGrid best_score -1 best_params {} for params in ParameterGrid(param_grid): model AGNES(**params) labels model.fit(X_scaled).labels_ score silhouette_score(X_scaled, labels) if score best_score: best_score score best_params params贝叶斯优化使用scikit-optimizefrom skopt import BayesSearchCV from sklearn.cluster import AgglomerativeClustering opt BayesSearchCV( AgglomerativeClustering(), { n_clusters: (2, 10), linkage: [single, complete, average], affinity: [euclidean, cosine, l1] }, n_iter32, cv3 ) opt.fit(X_scaled)优化技巧对大数据集使用随机采样评估并行评估不同参数组合记录中间结果避免重复计算19. 生产环境部署模式将AGNES投入生产的几种架构批处理模式定期如每天全量重新聚类适合相对静态的数据分布使用Airflow/Luigi调度增量更新新数据到达时局部调整层次结构实现partial_fit方法挑战可能破坏全局最优性微服务架构from flask import Flask, request import joblib app Flask(__name__) model joblib.load(agnes_model.pkl) app.route(/predict, methods[POST]) def predict(): data request.json[features] cluster model.predict([data])[0] return {cluster: int(cluster)} if __name__ __main__: app.run(host0.0.0.0, port5000)性能考量模型序列化大小pickle协议选择预测延迟优化缓存最近邻监控聚类漂移统计检验分布变化20. 伦理考量与负责任的AI应用聚类技术时的伦理责任偏见检测检查敏感属性在簇中的分布使用公平性指标 demographic parity可解释性提供簇特征描述实现explain_cluster方法示例def explain_cluster(cluster_id, feature_names, n3): cluster_data X[labels cluster_id] means cluster_data.mean(axis0) stds cluster_data.std(axis0) top_features np.argsort(means)[-n:] return { f: {mean: means[i], std: stds[i]} for i, f in zip(top_features, feature_names[top_features]) }隐私保护差分隐私聚类数据匿名化联邦学习架构合规检查清单[ ] 数据使用授权审核[ ] 避免敏感属性直接参与聚类[ ] 结果解释不强化刻板印象[ ] 建立人工复核流程