教程目录
阅读:
K-Means聚类分析(K-均值,K-平均)算法详解
根据训练样本中是否包含标签信息,机器学习可以分为监督学习和无监督学习。聚类算法是典型的无监督学习,其训练样本中只包含样本的特征,不包含样本的标签信息。在聚类算法中,利用样本的特征,将具有相似属性的样本划分到同一个类别中。
K-Means 算法,也被称为 K-平均 或 K-均值算法,是一种广泛使用的聚类算法。K-Means 算法是基于相似性的无监督的算法,通过比较样本之间的相似性,将较为相似的样本划分到同一个类别中。由于 K-Means 算法简单、易于实现于特点,K-Means 算法得到了广泛的应用,如在图像分割方面的应用。
通常在机器学习算法中使用到的距离函数主要有:
那么,点 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 模块:
对于 K-Means 算法,假设有 m 个样本 {X(1),X(2),…,X(m)},其中,X(i) 表示第 i 个样本,每一个样本中包含 n 个特征,即:

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

假设有 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 个类别的样本的个数。对于矩阵形式的目标函数,其可以表示为:

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

图 1 聚类数据(包含了 4 个不同的类别)
对于 K-Means 算法,其主要的流程是获取数据集,并对数据进行处理,然后对这些数据计算其聚类中心。首先,为了使得 Python 能够支持中文的注释和利用 numpy,我们需要在 “KMeans.py” 文件的开始加入:
程序的运算过程为:
当运行完成后,最终的聚类结果如图 2 所示。

图 2 K-Means 聚类结果
在图 2 中,“+”代表的是 4 个不同的聚类中心,这 4 个聚类中心的具体值为:
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-Means算法步骤
- 初始化常数 k,随机初始化 k 个聚类中心;
-
重复计算以下过程,直到聚类中心不再改变:
- 计算每个样本与每个聚类中心之间的相似度,将样本划分到最相似的类别中;
- 计算划分到每个类别中的所有样本特征的均值,并将该均值作为每个类新的聚类中心。
- 输出最终的聚类中心以及每个样本所属的类别。
K-Means算法与矩阵分解
以上对 K-Means 算法进行了简单介绍,在 K-Means 算法中,假设训练数据集 X 中有 m 个样本 {X(1) ,X(2),…,X(m)},其中,每一个样本 X(i) 为 n 维的向量。此时样本可以表示为一个 m×n 的矩阵:
K-Means 算法的目标是使得每一个样本 X(i) 被划分到最相似的类别中,利用每个类别中的样本重新计算聚类中心 Ck:

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




由于:




因此,上述的两种形式的目标函数是等价的。
K-Means算法实践
假设有 m 个样本 {X(1),X(2),…,X(m)},如图 1 所示,其中,已知这些数据可以划分成 4 个不同的类别,首先定义 k=4,随机初始化 4 个不同的聚类中心,通过计算每个样本点与聚类中心之间的距离,将样本点划分到不同的类别中。
图 1 聚类数据(包含了 4 个不同的类别)
对于 K-Means 算法,其主要的流程是获取数据集,并对数据进行处理,然后对这些数据计算其聚类中心。首先,为了使得 Python 能够支持中文的注释和利用 numpy,我们需要在 “KMeans.py” 文件的开始加入:
# coding:UTF-8 import numpy as npK-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 算法的主要步骤包括:
- 导入数据;load_data 函数的主要功能是对数据进行预处理并导入;
- 随机初始化 k 个聚类中心,randCent 函数主要完成 k 个聚类中心的初始化;
- 利用 K-Means 算法进行聚类计算,kmeans 函数是 K-Means 算法的核心程序,利用 K-Means 算法计算出聚类中心和每个样本所属的类别;
- 保存每个样本所属的类别到 sub 文件中;
- 保存 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 subCenterkmeans 函数是 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 K-Means 聚类结果
在图 2 中,“+”代表的是 4 个不同的聚类中心,这 4 个聚类中心的具体值为:
