概述

k-means算法对于异常值十分敏感，因为具有极大值的对象可能会产生严重扭曲的数据分布。因此我们可以使用k-medoids算法，它是集群中位于最中心的对象，而不是将集群中的平均值作为参考点。因此，分区的方法仍然可以基于最小化每个对象与其参考点之间的不相似程度之和的原理来进行。这构成了k-medoids方法的基础。聚类算法可以将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”(cluster)，通过这样的划分，每个簇可能对应于一些潜在的概念或类别。也可以对数据进行数据归约，即在尽可能保证数据完整的前提下，减少数据的量级，以便后续处理。也可以对聚类数据结果直接应用或分析。聚类算法可以被分为那么几种，比如基于划分方法的、基于层次方法的、基于密度方法的、基于网格方法的、基于模型方法的；K-mediods算法就是基于划分方法的一种聚类算法，确切的说，是对K-means算法的一种改进算法。本章节将会介绍K-mediods算法。关于K 中心点算法（ K-medoids ）正好能解决 k-means 算法中的 “噪声”敏感这个问题。解决过程如下：我们得介绍下 k-means 算法为什么会对“噪声”敏感。K-means 寻找质点的过程中，对某类簇中所有的样本点维度求平均值，即获得该类簇质点的维度。当聚类的样本点中有“噪声”（离群点）时，在计算类簇质点的过程中会受到噪声异常维度的干扰，造成所得质点和实际质点位置偏差过大，从而使类簇发生“畸变”。例子如下：

此时可能造成了类簇𝐶1C1质点的偏移，在下一轮迭代重新划分样本点的时候，将大量不属于类簇 C1 的样本点纳入，因此得到不准确的聚类结果。为了解决该问题， K 中心点算法（ K-medoids ）提出了新的质点选取方式，而不是简单像 k-means 算法采用均值计算法。在 K 中心点算法中，每次迭代后的质点都是从聚类的样本点中选取，而选取的标准就是当该样本点成为新的质点后能提高类簇的聚类质量，使得类簇更紧凑。该算法使用绝对误差标准来定义一个类簇的紧凑程度。K-medoids对噪声和孤立点不敏感，但是事情都具有两面性，这种聚类准确性的提高是牺牲聚类时间来实现的，不难看出K-medoids需要不断的找出每个点到其他所有点的距离的最小值来修正聚类中心，这大大加大了聚类收敛的时间。但K-medoids对于大规模数据聚类就显得力不从心，只能适应较小规模的数值聚类。

K-mediods算法处理过程

实验步骤

1 安装并导入所需要的库

!pip install numpy==1.16.0
!pip install pandas==0.25.0
!pip install scikit-learn==0.22.1
!pip install matplotlib==3.1.0
!pip install treelib
!pip install pyclust

from sklearn.datasets import make_blobs
from matplotlib import pyplot
import numpy as np
import random

2 定义一个k-medoid类

定义一个k-medoid类，init方法定义参数

2.1 创建测试数据并画图表示

2.2 定义欧式距离的计算

2.3 K-mediods算法

@ param func_of_dis ：距离公式。

2.4 画图分类比较

获取数据并画图展示开始未分类的图，展示分类后的图。

class KMediod():
    def __init__(self, n_points, k_num_center):
        self.n_points = n_points
        self.k_num_center = k_num_center
        self.data = None
    def get_test_data(self):
        self.data, target = make_blobs(n_samples=self.n_points, n_features=2, centers=self.n_points)
        np.put(self.data, [self.n_points, 0], 500, mode='clip')
        np.put(self.data, [self.n_points, 1], 500, mode='clip')
        pyplot.scatter(self.data[:, 0], self.data[:, 1], c=target)
    # 画图
        pyplot.show()
    def ou_distance(self,x, y):
        return np.sqrt(sum(np.square(x - y)))
    def run_k_center(self,func_of_dis):
        print('初始化', self.k_num_center, '个中心点')
        indexs = list(range(len(self.data)))
        random.shuffle(indexs)         # 随机选择质心
        init_centroids_index = indexs[:self.k_num_center]
        centroids = self.data[init_centroids_index, :]      # 初始中心点

        levels = list(range(self.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 self.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) # 统计，方便迭代完成后重新计算中间点

            # 重新划分质心
            for i in range(self.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
        print('结束')
        return sample_target
    def run(self):
        self.get_test_data()
        predict = self.run_k_center(self.ou_distance)
        pyplot.scatter(self.data[:, 0], self.data[:, 1], c=predict)
        pyplot.show()

test=KMediod(n_points=1000, k_num_center=3)
test.run()

3 sklearn实现K-Medoids算法

3.1 引入所需要的库

from pyclust import KMedoids
import numpy as np
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt

3.2 构造示例数据集（加入少量脏数据）

data1 = np.random.normal(0,0.9,(1000,10))
data2 = np.random.normal(1,0.9,(1000,10))
data3 = np.random.normal(2,0.9,(1000,10))
data4 = np.random.normal(3,0.9,(1000,10))
data5 = np.random.normal(50,0.9,(50,10))
data = np.concatenate((data1,data2,data3,data4,data5))

3.3 准备可视化需要的降维数据

data_TSNE = TSNE(learning_rate=100).fit_transform(data)

3.4 对不同的k进行试探性K-medoids聚类并可视化

plt.figure(figsize=(12,8))
for i in range(2,6):
    k = KMedoids(n_clusters=i,distance='euclidean',max_iter=1000).fit_predict(data)
    colors = ([['red','blue','black','yellow','green'][i] for i in k])
    plt.subplot(219+i)
    plt.scatter(data_TSNE[:,0],data_TSNE[:,1],c=colors,s=10)
    plt.title('K-medoids Resul of '.format(str(i)))

k-meams 和 k-medoids 比较

K-mediods算法优缺点