首页 > 编程笔记 > Python笔记 阅读：18

k-中心点聚类算法(k-medoids)详解（Python实现）

medoid 在英文中的意思为“中心点”，所以 k-medoids 算法又叫 k-中心点聚类算法。

与 k-means 有所不同的是，k-medoids 算法不采用簇中对象的平均值作为参照点，而是选用簇中位置最中心的对象，即中心点作为参照点。

k-medoids算法的基本思想

对于给定聚类数目 k，首先随机选择 k 个代表对象作为初始聚类中心，计算各剩余对象与代表对象的距离并将其分配给最近的一个簇，产生相应的聚类结果。

然后开始迭代过程：对于每一次迭代，将随机选择的一个非中心点替代原始中心点中的一个，重新计算聚类结果。如果聚类效果有所提高，保留此次替换，否则恢复原中心点。当替换对聚类效果不再有所提高时，迭代停止。

用代价函数来衡量聚类结果的质量，该函数用来度量对象与中心点之间的平均相异度，具体定义如下：


其中，p 是空间中的点，即为给定对象，oi 代表簇 Ci 的中心点，E 则表示数据集中所有对象的离差平方和。

在进行新一轮中心点替换后，以 newCi，i=1，2，…，k 表示新中心集划分的簇，以 oldCi，i=1，2，…，k 代表原来的簇，它们的聚类评价函数分别为 Enew，Eold，则：


由 Enew，Eold 定义中心替换的代价函数为：Cost=Enew-Eold。

聚类所要达到的目标是使得簇内各个对象之间的差异尽可能小，因此，如果要判定一个非代表对象 orandom 是否是对当前中心点 oi 的更优替换点，对于每一个非中心点对象 p，每当重新分配时，平方-误差：


产生的差别会对代价函数产生影响，替换所产生的总代价是所有非中心点对象的代价之和。如果总代价的值小于零，即实际平方-误差减小，表明经过替换后，簇内对象之间的差异变得更小了，此时，可用 orandom 替换 oi 作为新的中心点对象。反之，如果替换所产生的总代价一直大于或等于零，则未能产生一个有效的替换，此时算法收敛。

k-medoids聚类算法步骤

k-medoids 聚类算法的基本思想为：
k-medoids 聚类算法的具体步骤为：
  1. 在 n 个数据对象中随机选择 k 个点，作为初始中心集。
  2. 计算每个非代表对象到各中心点的距离，将其分配给离其最近的簇中。
  3. 对于每个非中心对象，依次执行以下过程：用当前点替换其中一个中心点，并计算替换所产生的代价函数，若为负，则替换，否则不替换且还原中心点。
  4. 得到一个最终的较优 k 个中心点集合，根据最小距离原则重新将所有对象划分到离其最近的簇中。

k-medoids 聚类初始中心的选择仍可采用最大距离法、最大最小距离法和 Huffman 树。

k-medoids算法的实现

上面对 k-medoids 算法的基本思想及步骤进行了介绍，下面通过一个实例来演示 kmedoids 算法的应用。

【实例】利用 k-medoids 算法对随机数据点进行聚类。 
from sklearn.datasets import make_blobs
from matplotlib import pyplot
import numpy as np
import random

class KMediod():
    """
    实现简单的 k-medoid 算法
    """
    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):
        """
        产生测试数据，n_samples 表示多少个点，n_features 表示几维，centers 得到的 data 是 n 个点的各自坐标;target 是每个坐标的分类
        target 长度为 n,范围为 0-3,主要是画图颜色区别
        :return: none
        """
        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 = ou_distance):
        """
        选定好距离公式开始训练
        """
        print('初始化', self.k_num_center, '个中心点')
        indexes = list(range(len(self.data)))
        random.shuffle(indexes)  # 随机选择质心
        init_centroids_index = indexes[: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(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(p_1, centroids[i]) for point_1 in classify_points[i]]
                # 首先计算出现在中心点和其他所有点的距离总和
                now_distances = sum(distances)
                for point in classify_points[i]:
                    distances = [func(p_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):
        """
        先获得数据,由传入参数得到杂乱的 n 个点,然后由这 n 个点,分为 m 个类
        """
        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_one = KMediod(n_points=1000, k_num_center=3)
test_one.run()
运行程序，得到聚类效果如下图所示：


图 4 k-medoids聚类效果

相关文章