K-means《机器学习实战》基础整理

主要内容

一般K-means:

• 簇数k是用户给定的，每个簇通过其质心(centroid)，即簇中所有点的中心来描述。

• 首先，随机确定k个初始点作为质心。然后，将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。这一步完成后，每个簇的质心更新为该簇所有点的平均值。

• 方法：(计算质心 - 分配 - 重新计算) - 反复迭代，直到所有数据点的簇分配结果不再改变为止

使用后处理提高聚类性能(《机器学习实战》 - P189)：

• 问题

  • 怎样知道k值的选择是否正确?怎样知道生成的簇比较好呢？

• 怎样评价

  • 在包含簇分配结果的矩阵中包含着每个点的误差，即该点到簇质心的距离平方值，将以此来评价聚类质量

• 原因：

  • K-Means算法收敛但聚类效果交叉的原因是：K-Means收敛到了局部最小值，而非全局最小值(局部最小值结果可以但并非最好结果，全局最小值是可能的最小结果)

• 衡量指标：

  • 一种用于度量聚类效果的指标是SSE(Sum of Squared Error 误差平方和),即每个点距离质心距离的平方和。SSE越小表示数据点越接近质心，聚类效果也越好。
    因为对误差取了平方，因此更加重视那些远离中心的点。增加簇个数能够降低SSE值，但这违背了聚类的目标：在保持簇数目不变情况下提高簇的质量

• 一种方法

  • 对生成后的簇进行处理，将SSE值最大的簇划分为两个簇。具体实现时可以将最大簇包含的点过滤出来，并在这些点上运行k=2的K-means。

二分K-均值算法

为了克服k-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分k-均值(bisecting K-means)的算法。该算法首先将所有点作为一个簇，然后将该簇一分为二，之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，知道得到用户指定的簇数目为止

代码

代码整理自《机器学习实战》

# -*- coding: utf-8 -*-
from numpy import *
import matplotlib.pyplot as plt

def loadDataSet(fileName):
    """
    功能：读取文件，加载数据
    """
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('    ')
        # 注意： python2中map函数直接返回列表，不用list处理
        fltLine = list(map(float,curLine))
        dataMat.append(fltLine)
    return dataMat


def disEclud(vecA,vecB):
    """
    功能： 计算两个向量间的欧氏距离
    """
    return sqrt(sum(power(vecA - vecB, 2)))


def randCent(dataSet, k):
    """
    功能： 为给定数据集构建一个包含k个随机质心的集合(通过找到数据集每一维的最小和最大值来完成)
    """
    # array(dataSet)是自己加的，否则无法进行dataSet[:,j]操作，用mat转成矩阵也不能进行dataSet[:,j]操作
    dataSet = array(dataSet)
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))
    # 构建簇质心
    for j in range(n):
        # 第j维的最小值
        minJ = min(dataSet[:,j])
        # 第j维的最大最小值之差
        rangeJ = float(max(dataSet[:,j]) - minJ)
        # 原代码是: centroids[:,j] = minJ + rangeJ * random.rand(k,1), randoma.rand(k,1)是k行1列的ndarray,且随机产生的每个数字在0-1之间
        temp = random.rand(k,1)
        centroids[:,j] = minJ + rangeJ * temp
    return centroids

def kMeans(dataSet,k,distMeas = disEclud, createCent = randCent):
    """
    功能：kmearns聚类代码
    首先，随机确定k个初始点作为质心。然后，将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。这一步完成后，每个簇的质心更新为该簇所有点的平均值。
    方法：(计算质心 - 分配 - 重新计算) - 反复迭代，直到所有数据点的簇分配结果不再改变为止
    param: dataSet: 数据计划
    param: k: 簇的数量
    param: distMeas: 距离计算方法
    param: createCent: 计算原始的质心
    return: centroids: 最终的质心
    return: clusterAssment: 簇分配结果矩阵，包含两列，一列记录簇索引值，第二列存储误差(指当前点到簇质心的距离，后续会用该误差评价聚类的效果)
    
    """
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroids = createCent(dataSet,k)
    centroids = array(centroids)
    dataSet = array(dataSet)
    # 标识是否继续迭代(如果为True,则继续迭代)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        # 遍历所有样本点，找到距离每个点最近的质心(通过对每个点遍历所有质心并计算点到每个质心的距离来完成)
        for i in range(m):
            minDist = inf
            minIndex = -1
            # 当前样本点便利便利所有的质心
            for j in range(k):
                # 计算第i个样本与第j个质心间的距离
                distJI = distMeas(centroids[j,:], dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
            # 如果当前第i个点的分配结果发生了改变，则更新clusterChanged标识
            if clusterAssment[i,0] != minIndex:
                clusterChanged = True
            # clusterAssment的两列分别存储簇索引值和距离(第i个样本点到质心的距离)
            clusterAssment[i,:] = minIndex, minDist ** 2
        # print (centroids)
        # 遍历所有质心并更新它们的取值
        for cent in range(k):
            # 这一步操作每台明白？？？？？
            pstInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]
            # 在pstInclust的列上计算均值
            centroids[cent,:] = mean(pstInClust, axis = 0)
    return centroids, clusterAssment


def biKmeans(dataSet, k, distMeas = disEclud):
    """
    功能：二分K-均值算法 
    为了克服k-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分k-均值(bisecting K-means)的算法。
    该算法首先将所有点作为一个簇，然后将该簇一分为二，之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于
    对其划分是否可可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，知道得到用户指定的簇数目为止
    param: dataSet: 数据计划
    param: k: 簇的数量
    param: distMeas: 距离计算方法
    return: centroids: 最终的质心
    return: clusterAssment: 簇分配结果矩阵，包含两列，一列记录簇索引值，第二列存储误差
    """
    dataSet = array(dataSet)
    m = shape(dataSet)[0]
    # 创建一个矩阵来存储数据集中每个点的簇分配结果及平方误差，然后计算整个数据集的质心，并使用一个列表来保留所有的质心
    # 得到上述质心后，可以遍历数据集中所有点来计算每个点到质心的误差，这些误差值都将在后续用到
    clusterAssment = mat(zeros((m,2)))
    centroid0 = mean(dataSet,axis=0).tolist()[0]
    cenList = [centroid0]
    for j in range(m):
        clusterAssment[j,1] = distMeas(mat(centroid0),dataSet[j,:]) ** 2
    # while循环汇总会不停地对簇进行划分，直到得到想要的簇数目位置
    while len(cenList) < k:
        # SSE初值设为无穷大
        lowestSSE = inf
        # 遍历簇列表centList中的每一个簇
        for i in range(len(cenList)):
            # 对每一个簇，将该簇中的所有点看称一个小的数据集pstIncurrCluster
            # QUESTION:为什么要选与i相等的？？？
            ptsIncurrCluster = dataSet[nonzero(clusterAssment[:,0].A == i)[0],:]
            # 将pstIncurrCluster输入到函数KMeans()中进行处理(k=2),然后得到2个质心(簇)和每个簇的误差值
            centroidMat, splitClustAss = kMeans(ptsIncurrCluster, 2, distMeas)
            # 上述得到的误差与剩余数据集的误差之和作为本次划分的误差
            sseSplit = sum(splitClustAss[:,1])
            sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A != i)[0],1])
            print ("seeSplit, and notSplit: ", sseSplit, sseNotSplit)
            # 如果划分的SSE值最小，则本次划分被保存
            if (sseSplit + sseNotSplit) < lowestSSE:
                bestCentToSplit = i 
                bestNewCents = centroidMat
                bestClustAss = splitClustAss.copy()
                lowestSSe = sseSplit + sseNotSplit
        """更新簇的分配结果"""
        bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(cenList)
        bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
        print ("the bestCentToSplit is : ", bestCentToSplit)
        print ("the len of bestClustAss is: ", len(bestClustAss))
        cenList[bestCentToSplit] = bestNewCents[0, :]
        cenList.append(bestNewCents[1,:])
        clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:] = bestClustAss
    return mat(cenList), clusterAssment


def show_pic(dataMat):
    dataArr = array(dataMat)
    # 作图方法一
    # plt.scatter(dataArr[:,0], dataArr[:,1], alpha=0.8)  # 绘制散点图，透明度为0.6（这样颜色浅一点，比较好看）
    # plt.show()  
    # 作图方法二
    fig = plt.figure()
    ax = plt.subplot()
    ax.scatter(dataArr[:,0], dataArr[:,1], s=30, alpha=0.8)  # 绘制散点图，面积随机
    plt.show()


if __name__ == '__main__':
    # dataMat = loadDataSet('KMeans_testSet.txt')
    # show_pic(dataMat)
    # centroids, clusterAssment = kMeans(dataMat,4)

    dataMat2 = loadDataSet('KMeans_testSet2.txt')
    # show_pic(dataMat2)
    cenList,myNewAssments = biKmeans(dataMat2,3)
    print (cenList)
    # print (myNewAssments)