人工智能中文网
  • 主页
  • 线代考研视频
  • 线性代数
  • Python机器学习与算法
  • 大数据与机器学习
  • Python基础入门教程
  • 人工智能中文网
    教程目录
    阅读:

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

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

    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 之间的标准化的欧式距离可以定义为:


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

    现在我们利用 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(1),X(2),…,X(m)},其中,X(i) 表示第 i 个样本,每一个样本中包含 n 个特征,即:


     
    首先随机初始化 k 个聚类中心,通过每个样本与 k 个聚类中心之间的相似度,确定每个样本所属的类别,再通过每个类别中的样本重新计算每个类的聚类中心,重复这样的过程,直到聚类中心不再改变,最终确定每个样本所属的类别以及每个类的聚类中心。

    K-Means算法步骤

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

    K-Means算法与矩阵分解

    以上对 K-Means 算法进行了简单介绍,在 K-Means 算法中,假设训练数据集 X 中有 m 个样本 {X(1) ,X(2),…,X(m)},其中,每一个样本 X(i) 为 n 维的向量。此时样本可以表示为一个 m×n 的矩阵:


     
    假设有 k 个类,分别为 {C1,…,Ck}。在 K-Means 算法中,利用欧氏距离计算每一个样本 X(i) 与 k 个聚类中心之间的相似度,并将样本 X(i) 划分到最相似的类别中,再利用划分到每个类别中的样本重新计算 k 个聚类中心。重复以上的过程,直到质心不再改变为止。

    K-Means 算法的目标是使得每一个样本 X(i) 被划分到最相似的类别中,利用每个类别中的样本重新计算聚类中心 Ck


     
    其中,ΣX(i)∈CKX(i) 表示的是所有 Ck 类中的所有的样本的特征向量的和,#(X(i)∈Ck) 表示的是类别 Ck 中的样本的个数。

    K-Means 算法的停止条件是最终的聚类中心不再改变,此时,所有样本被划分到了最近的聚类中心所属的类别中,即:


     
    其中,样本 X(i) 是数据集 Xm×n的第 i 行。Cj 表示的是第 j 个类别的聚类中心。假设 Mk×n 为 k 个聚类中心构成的矩阵。矩阵 Zm×k 是由 zij 构成的 0-1 矩阵,zij 为:


     
    对于上述的优化目标函数,其与如下的矩阵形式等价:


     
    其中,对于非矩阵形式的目标函数,可以表示为:


     

    由于:


     
    即每一个样本 X(i) 只能属于一个类别,则:


     
    其中,mj 表示的是属于第 j 个类别的样本的个数。对于矩阵形式的目标函数,其可以表示为:


     
    其中:


    因此,上述的两种形式的目标函数是等价的。

    K-Means算法实践

    假设有 m 个样本 {X(1),X(2),…,X(m)},如图 1 所示,其中,已知这些数据可以划分成 4 个不同的类别,首先定义 k=4,随机初始化 4 个不同的聚类中心,通过计算每个样本点与聚类中心之间的距离,将样本点划分到不同的类别中。

    聚类数据(包含了4个不同的类别)
    图 1 聚类数据(包含了 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 所示。

    K-Means聚类结果
    图 2 K-Means 聚类结果

    在图 2 中,“+”代表的是 4 个不同的聚类中心,这 4 个聚类中心的具体值为:

    < 上一篇:没有了 下一篇:K-Means++算法 >