从PAM到BanditPAM：k-Medoids聚类算法的演进、优化与实战选型指南

1. 为什么需要k-Medoids算法k-Means算法大家应该都不陌生它简单高效是很多数据科学项目的入门首选。但我在实际项目中经常遇到这样的情况当数据集中存在异常值或噪声点时k-Means的表现就会大打折扣。这是因为k-Means使用均值作为簇中心而均值对异常值非常敏感。举个例子假设我们要对电商平台的用户消费行为进行聚类分析。大多数用户每月消费在1000-3000元之间但有少数高净值用户每月消费高达10万元。如果用k-Means算法这些异常值会显著拉高簇中心的位置导致聚类结果失真。这时候k-Medoids就派上用场了——它选择实际存在的样本点作为簇中心medoids而不是计算均值因此对异常值更加鲁棒。k-Medoids的核心思想可以用一个简单的公式表示medoid(C) : argmin_{x_i∈C} ∑_{x_j∈C} d(x_i,x_j)这个公式的意思是在簇C中选择那个到其他所有点距离之和最小的点作为中心点。这种基于实际样本点的选择方式使得k-Medoids特别适合以下场景数据包含噪声或异常值距离度量不是欧式距离比如文本相似度需要更具解释性的簇中心比如在推荐系统中medoids代表典型用户画像2. PAM算法k-Medoids的经典实现2.1 PAM的基本原理Partitioning Around Medoids (PAM)是最经典的k-Medoids实现我把它称为暴力美学的代表。它的工作流程分为两个阶段BUILD阶段贪心地选择初始medoids第一个medoid选择到所有点距离之和最小的点后续每个medoid选择能最大程度减少总距离的点时间复杂度O(n²k)SWAP阶段迭代优化medoids尝试用非medoid点替换当前medoid如果总距离减小则接受替换每次迭代复杂度O(k(n-k)²)我在实际使用中发现PAM虽然效果稳定但当数据量超过1万条时运行时间就会变得难以接受。比如在一个包含5万条用户行为记录的数据集上完成聚类需要近8小时。2.2 PAM的优化技巧经过多次实践我总结出几个加速PAM的实用技巧距离矩阵预计算提前计算好所有点对之间的距离并缓存可以避免重复计算from sklearn.metrics import pairwise_distances distance_matrix pairwise_distances(X, metriccosine)最近邻缓存为每个点维护最近和次近的medoid信息可以减少SWAP阶段的计算量# 维护每个点的最近和次近medoid nearest np.argsort(distance_matrix[:, medoids], axis1)[:, :2]早期终止当连续多次SWAP没有改善时提前终止迭代这些优化可以将PAM的速度提升3-5倍但本质上还是无法突破O(n²)的时间复杂度瓶颈。这也是后来CLARA、CLARANS等算法被提出的原因。3. 大规模数据解决方案CLARA与CLARANS3.1 CLARA采样为王Clustering LARge Applications (CLARA)的核心思想很简单既然全量数据计算太慢那就对数据进行采样。具体步骤是多次随机采样通常采样量s402k对每个采样子集运行PAM从所有候选medoids中选择最佳组合我在一个百万级数据集上测试过CLARA设置采样次数n5采样大小s1000时聚类时间从PAM的预计30天降到了2小时。但采样也带来了新问题——当数据分布不均匀时小样本可能无法代表整体特征。3.2 CLARANS随机搜索的艺术CLARANS (Clustering Large Applications based on RANdomized Search)采用了不同的思路它不固定采样集而是在全量数据上进行随机化的局部搜索。算法流程如下随机选择k个初始medoids随机尝试替换一个medoid如果总距离减小则接受替换重复直到达到停止条件CLARANS有两个关键参数maxneighbor连续失败尝试次数阈值numlocal随机重启次数我的经验是对于中等规模数据n10万设置maxneighbor50numlocal5通常能得到不错的结果。CLARANS的优点是能探索更大的解空间缺点是随机性导致结果不稳定可能需要多次运行取最佳。4. 现代优化算法Trimed与BanditPAM4.1 Trimed数学剪枝的智慧Trimed算法利用了距离度量的三角不等式性质来进行剪枝。它的核心不等式是E(j) ≥ |E(i) - dist(x(i),x(j))|其中E(i)是点i到其他所有点的平均距离。这个不等式允许我们在计算过程中排除那些不可能成为medoid的点。我曾在一个人脸特征聚类任务中对比过Trimed和PAM数据集10万张人脸嵌入向量128维PAM耗时6小时Trimed耗时45分钟聚类质量轮廓系数两者相当Trimed的局限在于随着数据维度升高剪枝效果会下降。当维度超过50时加速比就不太明显了。4.2 BanditPAM强化学习的跨界应用BanditPAM是我近年来最喜欢的k-Medoids算法它将多臂老虎机(UCB)算法引入到PAM中。其创新点在于用采样估计代替精确计算使用UCB平衡探索与利用理论保证O(nlogn)时间复杂度实际测试表明在保持相同聚类质量的前提下万级数据比PAM快100倍十万级数据比PAM快1000倍Python实现示例from banditpam import KMedoids kmed KMedoids(n_medoids5, algorithmBanditPAM) kmed.fit(data)BanditPAM的一个小缺点是需要调整超参数如置信区间宽度但作者提供的默认值在大多数情况下表现良好。5. 实战选型指南根据我的项目经验不同场景下的算法选择建议如下场景特征推荐算法原因说明小数据(n1万)PAM结果精确无需复杂优化大数据均匀分布CLARA采样效率高结果稳定大数据非均匀分布CLARANS全局搜索能力强高维数据精确需求Trimed维度不高时剪枝效果显著超大数据快速迭代BanditPAM速度极快适合生产环境对于非对称距离的情况比如KL散度可以采用双中心策略# 非对称距离聚类示例 v_i argmin_z ∑_x d(x,z) # 入度中心 w_i argmin_y ∑_x d(y,x) # 出度中心最后分享一个实际案例在为某零售企业做客户分群时我们先用BanditPAM快速筛选出10个种子客户群体再对每个群体用PAM进行精细划分。这种粗筛精修的策略既保证了效率又确保了质量客户满意度提升了30%。