引言
上一篇博客介绍了k-means聚类算法，该算法虽然高效快速，但却受异常点的影响严重，如果样本中存在异常点，则聚类结果会产生极大的偏差。针对异常点对聚类结果的影响，本文介绍k-medoids聚类算法，k-medoids算法能有效削弱异常点的影响。
k-medoids算法
k-mediods每次选取的中心点，必须是样本点，而 k-means每次选取的中心点可以是样本点之外的点，就好比中位数和平均值的区别；
k-medoids算法步骤：
1.任意选取k个初始中心点medoids；
2.按照与medoids最近的原则，将剩余点分配到当前最佳的medoids代表的类中;
3.在每一类中，计算每个样本点与其他点的距离之和，选取距离之和最小的点作为新的medoids;
4.重复2-3的过程，直到所有的medoids点不再发生变化，或已达到设定的最大迭代次数;
k-medoids算法选取簇中心点的准则函数是:当前簇中所有其他点到该中心点的距离之和最小，所以需要遍历簇中所有点；
算法总结
1）基于“代表对象”的聚类方法；
2）数据变量为数值型的聚类算法；
3）异常点不会严重影响聚类结果；
4）时间复杂度高于k-means算法。
python实现
#加载所需模块
import numpy as np
from numpy import *
import sys
from sklearn import metrics
from sklearn.preprocessing import StandardScaler
import pandas as pd
import matplotlib.pyplot as plt
# 定义欧式距离的计算
def func_of_dis(x, y):
return np.sqrt(sum(np.square(x - y)))
#k-medoids算法实现
def KMedoids(df, k_num_center):
"""
选定好距离公式开始进行训练
:param df:样本数据，pd.DataFrame类型
:param k_num_center:类别数
"""
print('初始化',k_num_center, '个中心点')
data = df.values
#data = StandardScaler().fit_transform(df) #数据标准化
indexs = list(range(len(data)))
random.shuffle(indexs) # 随机选择质心
init_centroids_index = indexs[:k_num_center]
centroids = data[init_centroids_index, :] # 初始中心点
# 确定类别编号
levels = list(range(k_num_center))
print('开始迭代')
#sample_target = [] #样本类别结果
if_stop = False
while(not if_stop):
if_stop = True
classify_points = [[centroid] for centroid in centroids] #初始中心点转换为列表
sample_target = [] #样本类别结果
# 遍历数据
for sample in data:
# 计算距离，由距离该数据最近的核心，确定该点所属类别
distances = [func_of_dis(sample, centroid) for centroid in centroids] #计算所有样本到初始中心点的距离
cur_level = np.argmin(distances) #每个样本到中心点的距离最小所对应的中心点的位置
sample_target.append(cur_level)
# 统计，方便迭代完成后重新计算中间点
classify_points[cur_level].append(sample) #将样本和最近的中心点归为一类
# 重新划分质心
distances_res = [] #每个簇内各点到中心点的距离值之和列表，k个类别对应k个值
for i in range(k_num_center): # 几类中分别寻找一个最优点
distances = [func_of_dis(point_1, centroids[i]) for point_1 in classify_points[i]] #计算之前被归为一类的样本中每个点和中心点的距离
now_distances = sum(distances) # 首先计算出现在中心点和其他所有点的距离总和
for point in classify_points[i]:
distances = [func_of_dis(point_1, point) for point_1 in classify_points[i]] #计算簇中每个点和其他点的距离
new_distance = sum(distances)
# 计算出该聚簇中各个点与其他所有点的总和，若是有小于当前中心点的距离总和的，中心点去掉
if new_distance < now_distances:
now_distances = new_distance
centroids[i] = point # 换成该点
if_stop = False
distances_res.append(now_distances)
return(sample_target,distances_res)
#确定k值
def k_value_sse(k_value_list):
#利用SSE选择k
SSE = [] # 存放每次结果的误差平方和
sse_df = pd.DataFrame()
for i in k_value_list:
estimator = KMedoids(df,i) # 构造聚类器
distances_res = estimator[1]
dist_sum = sum(distances_res)
SSE.append(dist_sum)
return(k_value_list,SSE)
不同的k值与SSE值得对应关系，最终画出一条曲线，这条曲线相当于人的手肘，而肘部对应的点就是最佳的k取值点，即曲线的拐点。
#确定最佳的k值后
best_model = KMedoids(data,k)
#模型评价,计算轮廓系数
labels = KMedoids(data,k)[0]
score = silhouette_score(data,labels,metric='euclidean')
