K-Means聚类分析(K-均值，K-平均)算法详解

根据训练样本中是否包含标签信息，机器学习可以分为监督学习和无监督学习。聚类算法是典型的无监督学习，其训练样本中只包含样本的特征，不包含样本的标签信息。在聚类算法中，利用样本的特征，将具有相似属性的样本划分到同一个类别中。

K-Means 算法，也被称为 K-平均 或 K-均值算法，是一种广泛使用的聚类算法。K-Means 算法是基于相似性的无监督的算法，通过比较样本之间的相似性，将较为相似的样本划分到同一个类别中。由于 K-Means 算法简单、易于实现于特点，K-Means 算法得到了广泛的应用，如在图像分割方面的应用。

相似性的度量

在 K-Means 算法中，通过某种相似性度量的方法，将较为相似的个体划分到同一个类别中。对于不同的应用场景，有着不同的相似性度量的方法，为了度量样本 X 和样本 Y 之间的相似性，一般定义一个距离函数 d(X,Y)，利用 d(X,Y) 来表示样本 X 和样本 Y 之间的相似性。

通常在机器学习算法中使用到的距离函数主要有：

• 闵可夫斯基距离（Minkowski Distance）；
• 曼哈顿距离（Manhattan Distance）；
• 欧氏距离（Euclidean Distance）；

闵可夫斯基距离

假设有两个点，分别为点 P 和点 Q，其对应的坐标分别为：

那么，点 P 和点 Q 之间的闵可夫斯基距离可以定义为：

曼哈顿距离

对于上述的点 P 和点 Q 之间的曼哈顿距离可以定义为：

欧氏距离

对于上述的点 P 和点 Q 之间的欧氏距离可以定义为：
由曼哈顿距离和欧式距离的定义可知，曼哈顿距离和欧式距离是闵可夫斯基距离的具体形式，即在闵可夫斯基距离中，当 p=1 时，闵可夫斯基距离即为曼哈顿距离，当 p=2 时，闵可夫斯基距离即为欧式距离。

若在样本中，特征之间的单位不一致时，利用基本的欧式距离作为相似性的度量方法会存在问题，如样本的形式为（身高，体重）。身高的度量单位是 cm，范围通常为（150，190），而体重的度量单位是  kg，范围通常为（50，80）。假设此时有 3 个样本，分别为：（160，50），（170，60），（180，80）。此时可以利用标准化的欧氏距离。

对于上述点 P 和点 Q 之间的标准化的欧式距离可以定义为：

其中，s_i 表示的是第 i 维的标准差。在本文的 K-Means 算法中使用欧氏距离作为相似性的度量，在实现的过程中使用的是欧氏距离的平方 d(P,Q)²。

现在我们利用 Python 实现欧式距离的平方，在欧式距离的计算中，需要用到矩阵的相关计算，因此，我们需要导入 numpy 模块：

import numpy as np

欧式距离的平方的具体实现如下所示：

def distance(vecA, vecB):
    '''计算vecA与vecB之间的欧式距离的平方
    input:  vecA(mat)A点坐标
            vecB(mat)B点坐标
    output: dist[0, 0](float)A点与B点距离的平方
    '''
    dist = (vecA - vecB) * (vecA - vecB).T
    return dist[0, 0]

K-Means算法原理

K-Means算法的基本原理

K-Means 算法是基于数据划分的无监督聚类算法，首先定义常数 k，常数 k 表示的是最终的聚类的类别数，在确定了类别数 k 后，随即初始化 k 个类的聚类中心，通过计算每一个样本与聚类中心之间的相似度，将样本点划分到最相似的类别中。

对于 K-Means 算法，假设有 m 个样本 {X⁽¹⁾,X⁽²⁾,…,X^(m)}，其中，X⁽ⁱ⁾ 表示第 i 个样本，每一个样本中包含 n 个特征，即： 首先随机初始化 k 个聚类中心，通过每个样本与 k 个聚类中心之间的相似度，确定每个样本所属的类别，再通过每个类别中的样本重新计算每个类的聚类中心，重复这样的过程，直到聚类中心不再改变，最终确定每个样本所属的类别以及每个类的聚类中心。

K-Means算法步骤

1. 初始化常数 k，随机初始化 k 个聚类中心；
2. 重复计算以下过程，直到聚类中心不再改变：
   • 计算每个样本与每个聚类中心之间的相似度，将样本划分到最相似的类别中；
   • 计算划分到每个类别中的所有样本特征的均值，并将该均值作为每个类新的聚类中心。
3. 输出最终的聚类中心以及每个样本所属的类别。

K-Means算法与矩阵分解

以上对 K-Means 算法进行了简单介绍，在 K-Means 算法中，假设训练数据集 X 中有 m 个样本 {X⁽¹⁾ ,X⁽²⁾,…,X^(m)}，其中，每一个样本 X⁽ⁱ⁾ 为 n 维的向量。此时样本可以表示为一个 m×n 的矩阵： 假设有 k 个类，分别为 {C₁，…，C_k}。在 K-Means 算法中，利用欧氏距离计算每一个样本 X⁽ⁱ⁾ 与 k 个聚类中心之间的相似度，并将样本 X⁽ⁱ⁾ 划分到最相似的类别中，再利用划分到每个类别中的样本重新计算 k 个聚类中心。重复以上的过程，直到质心不再改变为止。

K-Means 算法的目标是使得每一个样本 X⁽ⁱ⁾ 被划分到最相似的类别中，利用每个类别中的样本重新计算聚类中心 C_k： 其中，Σ_{X⁽ⁱ⁾∈CK}X⁽ⁱ⁾ 表示的是所有 C_k 类中的所有的样本的特征向量的和，#(X⁽ⁱ⁾∈C_k) 表示的是类别 C_k 中的样本的个数。

K-Means 算法的停止条件是最终的聚类中心不再改变，此时，所有样本被划分到了最近的聚类中心所属的类别中，即： 其中，样本 X⁽ⁱ⁾ 是数据集 X_m×n的第 i 行。C_j 表示的是第 j 个类别的聚类中心。假设 M_k×n 为 k 个聚类中心构成的矩阵。矩阵 Z_m×k 是由 z_ij 构成的 0-1 矩阵，z_ij 为： 对于上述的优化目标函数，其与如下的矩阵形式等价： 其中，对于非矩阵形式的目标函数，可以表示为：
由于： 即每一个样本 X⁽ⁱ⁾ 只能属于一个类别，则： 其中，m_j 表示的是属于第 j 个类别的样本的个数。对于矩阵形式的目标函数，其可以表示为： 其中：
因此，上述的两种形式的目标函数是等价的。

K-Means算法实践

假设有 m 个样本 {X⁽¹⁾,X⁽²⁾,…,X^(m)}，如图 1 所示，其中，已知这些数据可以划分成 4 个不同的类别，首先定义 k=4，随机初始化 4 个不同的聚类中心，通过计算每个样本点与聚类中心之间的距离，将样本点划分到不同的类别中。
对于 K-Means 算法，其主要的流程是获取数据集，并对数据进行处理，然后对这些数据计算其聚类中心。首先，为了使得 Python 能够支持中文的注释和利用 numpy，我们需要在 “KMeans.py” 文件的开始加入：

# coding:UTF-8
import numpy as np

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

if __name__ == "__main__":
    k = 4  # 聚类中心的个数
    file_path = "data.txt"
    # 1、导入数据
    print "---------- 1.load data ------------"
    data = load_data(file_path)
    # 2、随机初始化k个聚类中心 
    print "---------- 2.random center ------------"
    centroids = randCent(data, k)
    # 3、聚类计算 
    print "---------- 3.kmeans ------------"
    subCenter = kmeans(data, k, centroids) 
    # 4、保存所属的类别文件
    print "---------- 4.save subCenter ------------"
    save_result("sub", subCenter)
    # 5、保存聚类中心
    print "---------- 5.save centroids ------------"
    save_result("center", centroids)

程序中，K-Means 算法的主要步骤包括：

1. 导入数据；load_data 函数的主要功能是对数据进行预处理并导入；
2. 随机初始化 k 个聚类中心，randCent 函数主要完成 k 个聚类中心的初始化；
3. 利用 K-Means 算法进行聚类计算，kmeans 函数是 K-Means 算法的核心程序，利用 K-Means 算法计算出聚类中心和每个样本所属的类别；
4. 保存每个样本所属的类别到 sub 文件中；
5. 保存 k 个聚类中心到 center 文件中，其中 save_result 函数将最终的结果写回到对应的文件中。

导入数据

在利用 K-Means 算法对数据进行聚类运算之前，首先需要导入数据，导入数据的程序代码如下程序所示：

def load_data(file_path):
    '''导入数据
    input:  file_path(string):文件的存储位置
    output: data(mat):数据
    '''
    f = open(file_path)
    data = []
    for line in f.readlines():
        row = []  # 记录每一行
        lines = line.strip().split("	")
        for x in lines:
            row.append(float(x)) # 将文本中的特征转换成浮点数
        data.append(row)
    f.close()
    return np.mat(data)

程序中，load_data 函数用于对指定文件中的数据进行预处理，并将处理完的数据导入到一个矩阵中。

初始化聚类中心

在 K-Means 算法中，需要先指定聚类中心的个数k，并在利用 K-Means 算法进行聚类之前，随机初始化 k 个聚类中心。初始化 k 个聚类中心的过程如下程序所示：

def randCent(data, k):
    '''随机初始化聚类中心
    input:  data(mat):训练数据
            k(int):类别个数
    output: centroids(mat):聚类中心
    '''
    n = np.shape(data)[1]  # 属性的个数
    centroids = np.mat(np.zeros((k, n)))  # 初始化k个聚类中心
    for j in xrange(n):  # 初始化聚类中心每一维的坐标
        minJ = np.min(data[:, j])
        rangeJ = np.max(data[:, j]) - minJ
        # 在最大值和最小值之间随机初始化
        centroids[:, j] = minJ * np.mat(np.ones((k , 1))) 
                        + np.random.rand(k, 1) * rangeJ
    return centroids

程序中，函数 randCent 用于随机初始化 k 个聚类中的方法，假设样本维数是 2，初始化聚类中心的方法为：找到每一维数据上的最小值 min 和最大值 max，生成在此区间范围内的随机值，生成随机值的公式如下所示：

聚类过程

在 K-Means 算法中，聚类的核心实现部分是 kmeans 函数，如下程序所示：

def kmeans(data, k, centroids):
    '''根据KMeans算法求解聚类中心
    input:  data(mat):训练数据
            k(int):类别个数
            centroids(mat):随机初始化的聚类中心
    output: centroids(mat):训练完成的聚类中心
            subCenter(mat):每一个样本所属的类别
    '''
    m, n = np.shape(data) # m：样本的个数，n：特征的维度
    subCenter = np.mat(np.zeros((m, 2)))  # 初始化每一个样本所属的类别
    change = True  # 判断是否需要重新计算聚类中心
    while change == True:
        change = False  # 重置
        for i in xrange(m):
            minDist = np.inf  # 设置样本与聚类中心之间的最小的距离，初始值为正无穷
            minIndex = 0  # 所属的类别
            for j in xrange(k):
                # 计算i和每个聚类中心之间的距离
                dist = distance(data[i, ], centroids[j, ])
                if dist < minDist:
                    minDist = dist
                    minIndex = j
            # 判断是否需要改变
            if subCenter[i, 0] <> minIndex:  # 需要改变
                change = True
                subCenter[i, ] = np.mat([minIndex, minDist])
        # 重新计算聚类中心
        for j in xrange(k):
            sum_all = np.mat(np.zeros((1, n)))
            r = 0  # 每个类别中的样本的个数
            for i in xrange(m):
                if subCenter[i, 0] == j:  # 计算第j个类别
                    sum_all += data[i, ]
                    r += 1
            for z in xrange(n):
                try:
                    centroids[j, z] = sum_all[0, z] / r
                except:
                    print " r is zero"  
    return subCenter

kmeans 函数是 K-Means 算法的核心程序，程序的输入是训练数据，聚类中心的个数 k 和初始化的 k 个聚类中心，其输出是最终的 k 个聚类中心和每个样本所属的类别。

最终的聚类结果

最终的结果需要保存到对应的文件中，需要保存的结果有每个样本所属的类别和所有的聚类中心，保存文件的 save_result 函数如下程序所示：

def save_result(file_name, source):
    '''保存source中的结果到file_name文件中
    input:  file_name(string):文件名
            source(mat):需要保存的数据
    output:
    '''
    m, n = np.shape(source)
    f = open(file_name, "w")
    for i in xrange(m):
        tmp = []
        for j in xrange(n):
            tmp.append(str(source[i, j]))
        f.write(" ".join(tmp) + " ")
    f.close()

该函数的输入为数据保存的文件名 file_name 和所需要保存的数据 source，最终将 source 中的数据写入到 file_name 文件中。

程序的运算过程为：

当运行完成后，最终的聚类结果如图 2 所示。
在图 2 中，“+”代表的是 4 个不同的聚类中心，这 4 个聚类中心的具体值为：