K-Means++算法详解（Python实现）

由于 K-Means 算法简单且易于实现，因此 K-Means 算法得到了很多的应用，但是 K-Means 算法的实现过程发现，算法中聚类中心的个数 k 需要事先指定，这一点对于一些未知数据存在很大的局限性。

其次，在利用 K-Means 算法进行聚类之前，需要初始化 k 个聚类中心，在上述的 K-Means 算法的过程中，使用的是在数据集中随机选择最大值和最小值之间的数作为其初始的聚类中心，但是聚类中心选择不好，对于 K-Means 算法有很大的影响，如选取的 k 个聚类中心为： 此时，得到最终的聚类中心为： 最终的聚类效果如图 1 所示。
为了解决因为初始化的问题带来 K-Means 算法的问题，改进的 K-Means 算法即 K-Means++算法被提出，K-Means++ 算法主要是为了能够在聚类中心的选择过程中选择较优的聚类中心。

K-Means++ 算法的基本思路

K-Means++ 算法在聚类中心的初始化过程中的基本原则是使得初始的聚类中心之间的相互距离尽可能远，这样可以避免出现上述的问题。

K-Means++ 算法的初始化过程如下：

1. 在数据集中随机选择一个样本点作为第一个初始化的聚类中心；
2. 选择出其余的聚类中心：
   • 计算样本中的每一个样本点与已经初始化的聚类中心之间的距离，并选择其中最短的距离，记为 d_i；
   • 以概率选择距离最大的样本作为新的聚类中心，重复上述过程，直到 k 个聚类中心都被确定。
3. 对 k 个初始化的聚类中心，利用 K-Means 算法计算最终的聚类中心。

在上述的 K-Means++ 算法中可知 K-Means++ 算法与 K-Means 算法最本质的区别是 k 个聚类中心的初始化过程，K-Means++ 算法的具体实现如下程序所示：

def get_centroids(points, k):
    '''KMeans++的初始化聚类中心的方法
    input:  points(mat):样本
            k(int):聚类中心的个数
    output: cluster_centers(mat):初始化后的聚类中心
    '''
    m, n = np.shape(points)
    cluster_centers = np.mat(np.zeros((k , n)))
    # 1、随机选择一个样本点为第一个聚类中心
    index = np.random.randint(0, m)
    cluster_centers[0, ] = np.copy(points[index, ])
    # 2、初始化一个距离的序列
    d = [0.0 for _ in xrange(m)]

    for i in xrange(1, k):
        sum_all = 0
        for j in xrange(m):
            # 3、对每一个样本找到最近的聚类中心点
            d[j] = nearest(points[j, ], cluster_centers[0:i, ])
            # 4、将所有的最短距离相加
            sum_all += d[j]
        # 5、取得sum_all之间的随机值
        sum_all *= random()
        # 6、获得距离最远的样本点作为聚类中心点
        for j, di in enumerate(d):
            sum_all -= di
            if sum_all > 0:
                continue
            cluster_centers[i] = np.copy(points[j, ])
            break
    return cluster_centers

程序中，函数 get_centroids 实现了 K-Means++ 算法的 k 个聚类中心的初始化，在初始化的过程中，其具体过程为：

• 随机从样本中选择出一个样本作为第 1 个聚类中心；
• 初始化一个距离序列 d，用于保存每个样本点到已初始化的聚类中心之间的最短距离；
• 对每个样本找到其最近的聚类中心，并将距离保存到距离序列 d 中，函数 nearest 实现了最短距离的计算；
• 为选择出与当前的所有聚类中心距离最远的样本点，需要计算当前的所有距离之和 sum_all；
• 随机选择所有和 sum_all 之间的随机数；
• 找到最大的距离，并将其作为新的聚类中心。

其中，nearest 函数具体的实现如下程序所示：

def nearest(point, cluster_centers):
    '''计算point和cluster_centers之间的最小距离
    input:  point(mat):当前的样本点
            cluster_centers(mat):当前已经初始化的聚类中心
    output: min_dist(float):点point和当前的聚类中心之间的最短距离
    '''
    min_dist = FLOAT_MAX
    m = np.shape(cluster_centers)[0]  # 当前已经初始化的聚类中心的个数
    for i in xrange(m):
        # 计算point与每个聚类中心之间的距离
        d = distance(point, cluster_centers[i, ])
        # 选择最短距离
        if min_dist > d:
            min_dist = d
    return min_dist

K-Means++算法的过程和最终效果

由上述可知 K-Means++ 算法与 K-Means 算法唯一的不同是两者在聚类中心的初始化过程。为了使得 Python 能够支持中文的注释和利用 numpy，我们需要在“KMeanspp.py”文件的开始加入：

# coding:UTF-8
import numpy as np

在 K-Means++ 算法中还需要使用到 random 模块中的 random 方法，同时，还需要使用到“KMeans.py”文件中的 load_data 函数、kmeans 函数、distance 函数和 save_result 函数，因此，在文件“KMeanspp.py”中需要分别导入：

from random import random
from KMeans import load_data, kmeans, distance, save_result

K-Means++ 算法的主函数如下程序所示：

if __name__ == "__main__":
    k = 4#聚类中心的个数
    file_path = "data.txt"
    # 1、导入数据
    print "---------- 1.load data ------------"
    data = load_data(file_path)
    # 2、KMeans++的聚类中心初始化方法
    print "---------- 2.K-Means++ generate centers ------------"
    centroids = get_centroids(data, k)
    # 3、聚类计算
    print "---------- 3.kmeans ------------"
    subCenter = kmeans(data, k, centroids)
    # 4、保存所属的类别文件
    print "---------- 4.save subCenter ------------"
    save_result("sub_pp", subCenter)
    # 5、保存聚类中心
    print "---------- 5.save centroids ------------"
    save_result("center_pp", centroids)

其运行过程为：

最终的聚类中心为：

计算出来的最终的聚类中心与K-Means在正常情况下计算出来的聚类中心一致。最终的聚类效果如图 2 所示。