机器学习实战-09-K均值（K-means）

一、K-means聚类介绍

聚类是一种无监督的学习，它将相似的对象归到同一个簇中。它有点像全自动分类 。聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。之所以称之为K-均值是因为它可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成。

假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是些什么。聚类与分类的最大不同在于，分类的目标事先已知，而聚类则不一样。因为其产生的结果与分类相同，而只是类别没有预先定义，聚类有时也被称为无监督分类（unsupervisedclassification）。

K-均值算法的工作流程是这样的。首先，随机确定k个初始点作为质心。然后将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。这一步完成之后，每个簇的质心更新为该簇所有点的平均值。算法伪代码如下：

上面提到“最近”质心的说法，意味着需要进行某种距离计算。读者可以使用所喜欢的任意距离度量方法。数据集上K-均值算法的性能会受到所选距离计算方法的影响。

二、算法实现

贴上全文全部代码：

from numpy import *
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans


def load_data_set(file_name):
    """
        Function:
            加载数据
        Parameters:
            file_name - 文件名
        Returns:
            data_mat - 数据矩阵
        Modify:
            2018-11-15
    """
    data_mat = []
    fr = open(file_name)
    for line in fr.readlines():
        cur_line = line.strip().split('\t')
        flt_line = list(map(float, cur_line))
        data_mat.append(flt_line)
    return data_mat


def dist_eclud(vec_a, vec_b):
    """
        Function:
            计算两个向量的欧式距离
        Parameters:
            vec_a - 向量a
            vec_b - 向量b
        Returns:
            欧式距离
        Modify:
            2018-11-15
    """
    return sqrt(sum(power(vec_a - vec_b, 2)))


def rand_cent(data_set, k):
    """
        Function:
            构建一个包含k个随机质心的集合
        Parameters:
            data_set - 数据集
            k - 质心个数
        Returns:
            centroids - 随机质心集合
        Modify:
            2018-11-15
    """
    n = shape(data_set)[1]
    # 初始化为一个(k,n)的矩阵
    centroids = mat(zeros((k, n)))
    # 遍历数据集的每一维度，每维先后选出k个值构成质心
    for j in range(n):
        # 得到该列数据的最小值
        min_j = min(data_set[:, j])
        # 得到该列数据的范围(最大值-最小值)
        range_j = float(max(data_set[:, j] - min_j))
        # rand函数根据给定维度生成[0, 1)之间的数据
        # k个质心向量的第j维数据值随机为位于(最小值，最大值)内的某一值
        centroids[:, j] = min_j + range_j * random.rand(k, 1)
    return centroids


def k_means(data_set, k, dist_meas=dist_eclud, create_cent=rand_cent):
    """
        Function:
            K-均值算法
        Parameters:
            data_set - 数据集
            k - 指定的k个类
            dist_meas - 距离计算方法，默认欧氏距离dist_eclud()
            create_cent - 获得k个质心的方法，默认随机获取rand_cent()
        Returns:
            centroids - k个聚类结果
            cluster_assment - 聚类误差
        Modify:
            2018-11-15
    """
    m = shape(data_set)[0]
    # 初始化一个(m,2)的矩阵
    cluster_assment = mat(zeros((m, 2)))
    # 创建初始的k个质心向量
    centroids = create_cent(data_set, k)
    # 聚类结果是否发生变化的布尔类型
    cluster_changed = True
    # 只要聚类结果一直发生变化，就一直执行聚类算法，直至所有数据点聚类结果不变化
    while cluster_changed:
        cluster_changed = False
        # 遍历数据集每一个样本向量
        for i in range(m):
            # 初始化最小距离最正无穷；最小距离对应索引为-1
            min_dist = inf
            min_index = -1
            # 循环k个类的质心
            for j in range(k):
                # 计算数据点到质心的欧氏距离
                dist_j_i = dist_meas(centroids[j, :], data_set[i, :])
                # 如果距离小于当前最小距离
                if dist_j_i < min_dist:
                    # 当前距离定为当前最小距离
                    min_dist = dist_j_i
                    # 最小距离对应索引对应为j(第j个类)
                    min_index = j
            # 当前聚类结果中第i个样本的聚类结果发生变化：布尔类型置为true，继续聚类算法
            if cluster_assment[i, 0] != min_index:
                cluster_changed = True
            # 更新当前变化样本的聚类结果和平方误差
            cluster_assment[i, :] = min_index, min_dist ** 2
        # print(centroids)
        # 遍历每一个质心
        for cent in range(k):
            # 将数据集中所有属于当前质心类的样本通过条件过滤筛选出来
            pts_in_clust = data_set[nonzero(cluster_assment[:, 0].A == cent)[0]]
            # 计算这些数据的均值（axis=0：求列的均值），作为该类质心向量
            centroids[cent, :] = mean(pts_in_clust, axis=0)
    return centroids, cluster_assment


def plot_cluster(data_set, k, centroids, cluster_assment):
    """
        Function:
            绘制聚类结果
        Parameters:
            data_set - 数据集
            k - 指定的k个类
            centroids - 质心集合
            cluster_assment - 聚类误差
        Returns:
            无
        Modify:
            2018-11-16
    """
    figure = plt.figure()
    ax = figure.add_subplot(111)
    ax.scatter(centroids[:, 0].tolist(), centroids[:, 1].tolist(), marker='+', s=60, c='black')
    markers = ['o', 's', 'v', '*'];
    colors = ['blue', 'green', 'yellow', 'red']
    for i in range(k):
        # data_class = data_set[nonzero(cluster_assment[:, 0].A == i)[0]]
        # KMeans().fit().labels_返回的是一维numpy.ndarray，绘制KMeans是用下面这行
        data_class = data_set[cluster_assment == i]
        ax.scatter(data_class[:, 0].tolist(), data_class[:, 1].tolist(), marker=markers[i], c=colors[i], s=20,
                   alpha=0.5)
    plt.show()


def bi_k_means(data_set, k, dist_meas=dist_eclud):
    """
        Function:
            K-均值算法
        Parameters:
            data_set - 数据集
            k - 指定的k个类
            dist_meas - 距离计算方法，默认欧氏距离dist_eclud()
        Returns:
            centroids - k个聚类结果
            cluster_assment - 聚类误差
        Modify:
            2018-11-24
    """
    m = shape(data_set)[0]
    # 将所有的点看成是一个簇
    # cluster_assment存储（所属的中心编号，距中心的距离）的列表
    cluster_assment = mat(zeros((m, 2)))
    # 获取数据集每一列数据的均值，组成一个长为列数的列表
    centroids_0 = mean(data_set, axis=0).tolist()[0]
    # cent_list存储聚类中心
    cent_list = [centroids_0]
    # 计算当前聚为一类时各个数据点距离质心的平方距离
    for j in range(m):
        cluster_assment[j, 1] = dist_meas(mat(centroids_0), data_set[j, :]) ** 2
    # 当簇小于数目k时
    while (len(cent_list) < k):
        lowest_ees = inf
        # 遍历当前每个聚类
        for i in range(len(cent_list)):
            # 通过数组过滤筛选出属于第i类的数据集合
            # nonzero函数是numpy中用于得到数组array中非零元素的位置（数组索引）的函数
            # matrix矩阵名.A矩阵转化为array数组类型
            pts_in_curr_cluster = data_set[nonzero(cluster_assment[:, 0].A == i)[0], :]
            # 对该类利用二分k-均值算法进行划分，返回划分后结果，及误差
            centroid_mat, split_cluster_ass = k_means(pts_in_curr_cluster, 2, dist_meas)
            # 计算该类划分后两个类的误差平方和
            sse_split = sum(split_cluster_ass[:, 1])
            # 计算数据集中不属于该类的数据的误差平方和
            sse_not_split = sum(cluster_assment[nonzero(cluster_assment[:, 0].A != i)[0], 1])
            # 打印这两项误差值
            print('sse_split, and sse_not_split:', sse_split, sse_not_split)
            # 选择使得误差最小的那个簇进行划分
            if (sse_split + sse_not_split) < lowest_ees:
                # 第i类作为本次划分类
                best_cent_to_split = i
                # 第i类划分后得到的两个质心向量
                best_new_cents = centroid_mat
                # 复制第i类中数据点的聚类结果即误差值
                best_clust_ass = split_cluster_ass.copy()
                # 将划分第i类后的总误差作为当前最小误差
                lowest_ees = sse_split + sse_not_split
        # 数组过滤筛选出本次2-均值聚类划分后类编号为1数据点，将这些数据点类编号变为当前类个数+1，作为新的一个聚类
        best_clust_ass[nonzero(best_clust_ass[:, 0].A == 1)[0], 0] = len(cent_list)
        # 将划分数据集中类编号为0的数据点的类编号仍置为被划分的类编号，使类编号连续不出现空缺
        best_clust_ass[nonzero(best_clust_ass[:, 0].A == 0)[0], 0] = best_cent_to_split
        print('the best_cent_to_split is:', best_cent_to_split)
        print('the len of best_clust_ass is:', len(best_clust_ass))
        # 更新质心列表中的变化后的质心向量
        cent_list[best_cent_to_split] = best_new_cents[0, :].tolist()[0]
        # 添加新的类的质心向量
        cent_list.append(best_new_cents[1, :].tolist()[0])
        # 更新cluster_assment列表中参与2-均值聚类数据点变化后的分类编号，及数据该类的误差平方
        cluster_assment[nonzero(cluster_assment[:, 0].A == best_cent_to_split)[0], :] = best_clust_ass
    return mat(cent_list), cluster_assment


def dist_s_l_c(vec_a, vec_b):
    """
        Function:
            计算地球表面两点之间的距离
        Parameters:
            vec_a - 数据集
            vec_b - 指定的k个类
        Returns:
            地球表面两点之间的距离，单位英里
        Modify:
            2018-11-24
    """
    # sin()和cos()以弧度未输入，将float角度数值转为弧度，即*pi/180
    a = sin(vec_a[0, 1] * pi / 180) * sin(vec_b[0, 1] * pi / 180)
    b = cos(vec_a[0, 1] * pi / 180) * cos(vec_b[0, 1] * pi / 180) * cos(pi * (vec_b[0, 0] - vec_a[0, 0]) / 180)
    return arccos(a + b) * 6371.0


def cluster_clubs(num_clust=5):
    """
        Function:
            簇绘图函数
        Parameters:
            num_clust - 指定簇的个数，默认5个
        Returns:
            无
        Modify:
            2018-11-24
    """
    data_list = []
    for line in open('./machinelearninginaction/Ch10/places.txt').readlines():
        line_arr = line.split('\t')
        data_list.append([float(line_arr[4]), float(line_arr[3])])
    data_mat = mat(data_list)
    # 利用2-均值聚类算法进行聚类
    my_centroids, clust_assing = bi_k_means(data_mat, num_clust, dist_meas=dist_s_l_c)
    # 对聚类结果进行绘图
    fig = plt.figure()
    rect = [0.1, 0.1, 0.8, 0.8]
    scatter_markers = ['s', 'o', '^', '8', 'p', 'd', 'v', 'h', '>', '<']
    axprops = dict(xticks=[], yticks=[])
    # 创建一幅图
    ax0 = fig.add_axes(rect, label='ax0', **axprops)
    img_p = plt.imread('./machinelearninginaction/Ch10/Portland.png')
    ax0.imshow(img_p)
    # 创建矩形
    ax1 = fig.add_axes(rect, label='ax1', frameon=False)
    for i in range(num_clust):
        pts_in_cruu_cluster = data_mat[nonzero(clust_assing[:, 0].A == i)[0], :]
        marker_style = scatter_markers[i % len(scatter_markers)]
        ax1.scatter(pts_in_cruu_cluster[:, 0].flatten().A[0], pts_in_cruu_cluster[:, 1].flatten().A[0],
                    marker=marker_style, s=90)
    ax1.scatter(my_centroids[:, 0].flatten().A[0], my_centroids[:, 1].flatten().A[0], marker='+', s=300)
    plt.show()


if __name__ == '__main__':
    # data_mat = mat(load_data_set('./machinelearninginaction/Ch10/testSet.txt'))
    # # 测试k个随机质心集合
    # t = rand_cent(data_mat, 2)
    # # 测试距离计算方法
    # m = dist_eclud(data_mat[0], data_mat[1])
    # print('k个随机质心集合：', t)
    # print('距离计算：', m)

    # data_mat = mat(load_data_set('./machinelearninginaction/Ch10/testSet.txt'))
    # my_centroids, clust_assing = k_means(data_mat, 4)
    # print(my_centroids)
    #
    # plot_cluster(data_mat, 4, my_centroids, clust_assing)

    # data_mat = mat(load_data_set('./machinelearninginaction/Ch10/testSet2.txt'))
    # my_centroids, clust_assing = bi_k_means(data_mat, 3)
    # print(my_centroids)
    # print(clust_assing)
    #
    # plot_cluster(data_mat, 3, my_centroids, clust_assing)

    # cluster_clubs(5)

    data_mat = mat(load_data_set('./machinelearninginaction/Ch10/testSet2.txt'))
    k = 3
    y_pred = KMeans(n_clusters=k).fit(data_mat)
    centroids = y_pred.cluster_centers_
    clust_assing = y_pred.labels_
    print(clust_assing)
    print(centroids)
    plot_cluster(data_mat, k, centroids, clust_assing)

下面用这个数据来测试实现

选取出来的质心和聚类结果：

2.1 使用后处理来提高聚类性能

有时候当我们观察聚类的结果图时，发现聚类的效果没有那么好，如上图所示，K-means算法在k值选取为3时的聚类结果，我们发现，算法能够收敛但效果较差。显然，这种情况的原因是，算法收敛到了局部最小值，而并不是全局最小值，局部最小值显然没有全局最小值的结果好。既然知道了算法已经陷入了局部最小值，如何才能够进一步提升K-means算法的效果呢？

一种用于度量聚类效果的指标是SSE，即误差平方和， 为所有簇中的全部数据点到簇中心的误差距离的平方累加和。SSE的值如果越小，表示数据点越接近于它们的簇中心，即质心，聚类效果也越好。因为，对误差取平方后，就会更加重视那些远离中心的数据点。

显然，一种改善聚类效果的做法就是降低SSE，那么如何在保持簇数目不变的情况下提高簇的质量呢？

一种方法是：我们可以将具有最大SSE值得簇划分为两个簇（因为，SSE最大的簇一般情况下，意味着簇内的数据点距离簇中心较远），具体地，可以将最大簇包含的点过滤出来并在这些点上运行K-means算法，其中k设为2。同时，当把最大的簇(上图中的下半部分)分为两个簇之后，为了保证簇的数目是不变的，我们可以再合并两个簇。

合并两个簇有两种可以量化的办法：合并最近的质心，或者合并两个使得SSE增幅最小的质心。第一种思路通过计算所有质心之间的距离，然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述处理过程，直到找到合并最佳的两个簇为止。这样，就可以满足簇的数目不变。

上面，是对已经聚类完成的结果进行改善的方法，在不改变k值的情况下，上述方法能够起到一定的作用，会使得聚类效果得到一定的改善。我们可以用二分k-均值克服算法收敛于局部最小值问题的K-means算法。

2.2 二分 K-均值算法

二分K-均值（bisecting K-means）算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。

当然，也可以选择SSE最大的簇进行划分，知道簇数目达到用户指定的数目为止。下面就来看一下该算法的实际效果。

通过上述算法，之前陷入局部最小值的的这些数据，经过二分K-means算法多次划分后，逐渐收敛到全局最小值，从而达到了令人满意的聚类效果。

三、示例：对地图上的点进行聚类

现在有一个存有70个地址、城市名、对应经纬度的文本数据，而没有这些地点的距离信息。因为在北极每走几米的经度变化可能达到数十度，而沿着赤道附近走相同的距离，带来的经度变化可能是零，所以我们使用球面余弦定理来计算两个经纬度之间的实际距离。想要对这些地点进行聚类，找到每个簇的质心地点，从而可以安排合理的行程，即质心之间选择交通工具抵达，而位于每个质心附近的地点就可以采取步行的方法抵达。显然，K-means算法可以为我们找到一种更加经济而且高效的出行方式。

四、应用scikit-learn构建KMeans聚类器

数据使用上面用过的testSet2.txt数据集。

从图中看出，scikit-learn的KMeans聚类效果和二分 K-均值聚类效果基本一样。

五，小结

聚类是一种无监督的学习方法。聚类区别于分类，即事先不知道要寻找的内容，没有预先设定好的目标变量。

聚类将数据点归到多个簇中，其中相似的数据点归为同一簇，而不相似的点归为不同的簇。相似度的计算方法有很多，具体的应用选择合适的相似度计算方法。

K-means聚类算法，是一种广泛使用的聚类算法，其中k是需要指定的参数，即需要创建的簇的数目，K-means算法中的k个簇的质心可以通过随机的方式获得，但是这些点需要位于数据范围内。在算法中，计算每个点到质心得距离，选择距离最小的质心对应的簇作为该数据点的划分，然后再基于该分配过程后更新簇的质心。重复上述过程，直至各个簇的质心不再变化为止。

K-means算法虽然有效，但是容易受到初始簇质心的情况而影响，有可能陷入局部最优解。为了解决这个问题，可以使用另外一种称为二分K-means的聚类算法。二分K-means算法首先将所有数据点分为一个簇；然后使用K-means（k=2）对其进行划分；下一次迭代时，选择使得SSE下降程度最大的簇进行划分；重复该过程，直至簇的个数达到指定的数目为止。实验表明，二分K-means算法的聚类效果要好于普通的K-means聚类算法。