一起读《机器学习算法与实现 —— Python编程与应用实例》- 第5章 k均值聚类算法

硬核王同学

一起读《机器学习算法与实现 —— Python编程与应用实例》- 第5章 k均值聚类算法 [复制链接]

上一章的k最近邻算法是一种分类方法，是监督学习的一种；而k均值聚类算法是一种聚类算法，是无监督学习的一种。通俗的讲，k最近邻算法的类别是已知的（即分类），而k均值聚类算法是未知的（即聚类）。

一、无监督学习思想

监督学习是指当训练集有明确的答案时，需要寻找问题与答案之间关系的学习方式。

无监督学习只需要数据，即没有明确的答案，也可以挖掘数据之间的关系。

聚类的行为本源来自人类天生具备的归纳和总结能力。

二、k均值聚类原理

书上讲的有点绕，这里我讲下我自己的理解：

 

在上方这幅图中，很容易看出有三种类型，分别是黄圈、绿圈、红圈。

当我们使用k均值聚类算法时，并不知道当前一共有多少种类型，所以只能假设有k个类型（这个k一定大于1且小于总样本数）。

假设我们的k为3，可以随机选择3个点来作为3个类别的中心点，并划分这3个中心点附近的样本属于哪一类。

此时求每个类别中样本的平均值，这个平均值就当成下一次分类的中心点，并再次划分这3个中心点附近的样本属于哪一类。

重复上述过程，直到中心点不再发生显著变化或达到预设的迭代次数或样本划分属于哪一类不再发生变化。

此时就找到了k个类型的k个中心点，即达到k均值聚类算法的最优点。

三、k均值聚类算法

这里引用下布树辉老师的讲义：

 

 

四、算法过程演示

这里也是直接看布树辉老师的讲义就行了，重点是自己将k均值聚类算法编程实现！

https://gitee.com/pi-lab/machinelearning_notebook/blob/master/3_kmeans/1-k-means.ipynb

 

五、k均值聚类算法实现

先使用模拟生成的满足高斯分布的随机数据作为数据集来演示算法。

%matplotlib inline

# import librarys
import numpy as np
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import random

# 生成数据
centers = [(7, 0), (0, 0), (5, 5)]
n_samples = 500

X, y = make_blobs(n_samples=n_samples, n_features=2, 
                  cluster_std=1.0, centers=centers, 
                  shuffle=True, random_state=42)

# 画出数据
plt.figure(figsize=(15, 9))

marksamples = ['or', 'ob', 'og', 'ok', '^r', '^b', '<g']  # 样本图形标记
for i in range(len(X)):
    markindex = y[i]
    plt.plot(X[i, 0], X[i, 1], marksamples[markindex], markersize=10)
       
plt.savefig("fig-res-k-means_data.pdf")
plt.show()

绘制原始数据，特征分布如图所示

 

有了原始数据，就可以着手实现k均值聚类算法，初始化聚类过程通过随机选择样本的方式实现。

# k-means

def calc_distance(v1, v2):
    """
    计算两个样本的特征距离
    
    v1 - 样本1的特征向量
    v2 - 样本2的特征向量
    """
    return np.sum(np.square(v1-v2))

def rand_cluster_cents(X, k):
    """
    初始化聚类中心：通过在区间范围随机产生的值作为新的中心点
    
    X - 样本数据 （n x D）
    k - 聚类个数
    """

    # 样本数
    n=np.shape(X)[0]
    
    # 生成随机下标列表
    dataIndex=list(range(n))
    random.shuffle(dataIndex)
    centroidsIndex = dataIndex[:k]
    
    # 返回随机的聚类中心
    return X[centroidsIndex, :]

def kmeans(X, k):
    """
    kMeans算法
    
    X - 样本数据 （n x D）
    k - 聚类个数
    """
    # 样本总数
    n = np.shape(X)[0]
    
    # 分配样本到最近的簇：存[簇序号,距离的平方] (n行 x 2列)
    clusterAssment = np.zeros((n, 2))

    # step1: 通过随机产生的样本点初始化聚类中心
    centroids = rand_cluster_cents(X, k)
    print('最初的中心=', centroids)

    iterN = 0
    
    while True:   
        clusterChanged = False
    
        # step2:分配到最近的聚类中心对应的簇中
        for i in range(n):
            minDist = np.inf;
            minIndex = -1
            for j in range(k):
                # 计算第i个样本到第j个中心点的距离
                distJI = calc_distance(centroids[j, :], X[i, :])
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
                    
            # 样本上次分配结果跟本次不一样，标志位clusterChanged置True
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist ** 2  # 分配样本到最近的簇
            
        iterN += 1
        sse = sum(clusterAssment[:, 1])
        print('the SSE of %d' % iterN + 'th iteration is %f' % sse)
        
        # step3:更新聚类中心
        for cent in range(k):  # 样本分配结束后，重新计算聚类中心
            ptsInClust = X[clusterAssment[:, 0] == cent, :]
            centroids[cent, :] = np.mean(ptsInClust, axis=0)
        
        # 如果聚类重心没有发生改变，则退出迭代
        if not clusterChanged:
            break
            
    return centroids, clusterAssment
    
# 进行k-means聚类
k = 3  # 用户定义聚类数
mycentroids, clusterAssment = kmeans(X, k)

通过rand_cluster_cents()函数生成初始聚类中心。

在上述程序中，打乱样本下标后，选择前k个样本作为初始聚类中心。k均值主函数kmeans()主要分为3个步骤：

步骤1，调用函数rand_cluster_cents()，通过随机产生的样本点初始化聚类中心。

步骤2，计算每个样本到每个聚类中心的距离，将距离最近的聚类中心更新为新值。

步骤3，根据每个样本所属的聚类关系计算新的聚类中心。

 

当给定k=3时，输出为：

最初的中心= [[4.95053629 5.67481949]
 [0.48100923 0.22388402]
 [7.51503527 0.51378595]]
the SSE of 1th iteration is 4874.740134
the SSE of 2th iteration is 3505.099431
the SSE of 3th iteration is 3502.239035

用以下程序将聚类结果可视化：

def datashow(dataSet, k, centroids, clusterAssment, fnFig=None):  # 二维空间显示聚类结果
    from matplotlib import pyplot as plt
    num, dim = np.shape(dataSet)  # 样本数num ,维数dim

    if dim != 2:
        print('sorry,the dimension of your dataset is not 2!')
        return 1
    marksamples = ['or', 'ob', 'og', 'ok', '^r', '^b', '<g']  # 样本图形标记
    if k > len(marksamples):
        print('sorry,your k is too large,please add length of the marksample!')
        return 1
        # 绘所有样本
    for i in range(num):
        markindex = int(clusterAssment[i, 0])  # 矩阵形式转为int值, 簇序号
        # 特征维对应坐标轴x,y；样本图形标记及大小
        plt.plot(dataSet[i, 0], dataSet[i, 1], marksamples[markindex], markersize=6)

    # 绘中心点
    markcentroids = ['o', '*', '^']  # 聚类中心图形标记
    label = ['0', '1', '2']
    c = ['yellow', 'pink', 'red']
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], markcentroids[i], markersize=15, label=label[i], c=c[i])
        #plt.legend(loc='upper left')  #图例
    plt.xlabel('feature 1')
    plt.ylabel('feature 2')

    plt.title('k-means cluster result')  # 标题
    if fnFig != None: plt.savefig(fnFig)
    plt.show()
    
    
# 画出实际图像
def trgartshow(dataSet, k, labels, fnFig=None):
    from matplotlib import pyplot as plt

    num, dim = np.shape(dataSet)
    label = ['0', '1', '2']
    marksamples = ['ob', 'or', 'og', 'ok', '^r', '^b', '<g']
    # 通过循环的方式，完成分组散点图的绘制
    for i in range(num):
        plt.plot(dataSet[i, 0], dataSet[i, 1], marksamples[int(labels[i])], markersize=6)

    
    # 添加轴标签和标题
    plt.xlabel('feature 1')
    plt.ylabel('feature 2')
    plt.title('true result')  # 标题

    # 显示图形
    if fnFig != None: plt.savefig(fnFig)
    plt.show()
    # label=labels.iat[i,0]
    
# 绘图显示
datashow(X, k, mycentroids, clusterAssment, "fig-res-k-means_predict.pdf")
trgartshow(X, 3, y, "fig-res-k-means_groundtruth.pdf")

数据的真值如下所示

 

k均值聚类结果如下所示

 

本章后三节还讲了使用sklearn进行聚类、评估聚类性能和一个k均值图像压缩的例子，想深入了解这个算法的可以自行看书再实现下，我们暂时只需要大致了解下这个算法的实现，在真正需要用的到的情况下再深入研究！

 

总结

本章讲述了k均值聚类算法的原理和实现，还通过一个图像压缩的例子展示该算法的实际使用之处，有很大的借鉴意义。通过学习，我们了解该算法是通过k最近邻算法的基础上，增加了循环迭代来获取最优结果的，且体验从监督学习算法切换到无监督学习算法，深刻理解了这两种不同算法的不同之处。

 

freebsder

其实是用“距离”这个概念，对应到集合的测度