机器学习系列（八）K均值（kMeans）

Minerva

修改于 2020-05-31 10:58:45

1K0

修改于 2020-05-31 10:58:45

文章被收录于专栏：Python编程和深度学习Python编程和深度学习

机器学习系列（八）K均值（kMeans）

在机器学习中，当我们要处理的数据是无标签的，就是无监督分类问题，如K均值算法。

内容目录

1 K均值算法2 二分K均值算法3 K-means++

1 K均值算法

K均值算法是一种聚类算法，自动的将数据组成聚类。该算法采用距离作为数据之间相似性的评价指标，认为两个数据距离越近，相似度越大。 算法步骤： 1）从数据样本中随机选择K个数据作为聚类的中心（质心），初始化簇。 2）计算每个数据样本到每个质心的距离，并划分到最近质心所在的类里。 3）重新计算划分之后的每个类的质心 4）重复迭代步骤（2）-（3），直到前后两次结果的质心相等或者距离小于给定阈值，结束聚类。 K均值的迭代过程如图，+为质心，经过3次迭代之后数据被分成三类。

度量数据之间距离的方法可以采用欧式距离。假设无标签数据集为X = {x1,x2,…,xn},目标类为k个，C = C1,C2,…,Ck，损失函数为

式中，ui为质心，

优点： 当数据分布是球状密集的，但类之间的区别也比较明显时效果较好，k均值仅限于具有中心（质心）概念的数据。 缺点： 1）K均值算法的初始中心点选择对算法影响较大，随机选择的质心可能导致迭代次数很多或者算法陷入局部最优。 2）在选择质心时k的个数需要基于经验和多次试验进行设置，不同数据k的选择也不一样。 3）K均值算法对噪声比较敏感。 Python代码：

myUtil.py:

# -*- coding:utf-8 -*-
from numpy import *

# 数据文件转矩阵
# path： 数据文件路径
# delimiter: 行内字段分隔符
def file2matrix(path, delimiter):
    fp = open(path, "rb")   # 读取文件内容
    content = fp.read()
    fp.close()
    rowlist = content.splitlines()   # 按行转换为一维表
    # 逐行遍历，结果按分隔符分隔为行向量
    recordlist = [map(eval, row.split(delimiter)) for row in rowlist if row.strip()]
    # 返回转换后的矩阵形式
    return mat(recordlist)

# 随机生成聚类中心
def randCenters(dataSet, k):
    n = shape(dataSet)[1]   # 列数
    clustercents = mat(zeros((k, n)))   # 初始化聚类中心矩阵：k*n
    for col in xrange(n):
        mincol = min(dataSet[:, col])
        maxcol = max(dataSet[:, col])
        # random.rand(k, 1):产生一个0~1之间的随机数向量（k,1表示产生k行1列的随机数）
        clustercents[:, col] = mat(mincol + float(maxcol - mincol) * random.rand(k, 1))   # 按列赋值
    return clustercents

# 欧式距离计算公式
def distEclud(vecA, vecB):
    return linalg.norm(vecA-vecB)

# 绘制散点图
def drawScatter(plt, mydata, size=20, color='blue', mrkr='o'):
    plt.scatter(mydata.T[0], mydata.T[1], s=size, c=color, marker=mrkr)

# 以不同颜色绘制数据集里的点
def color_cluster(dataindx, dataSet, plt):
    datalen = len(dataindx)
    for indx in xrange(datalen):
        if int(dataindx[indx]) == 0:
            plt.scatter(dataSet[indx, 0], dataSet[indx, 1], c='blue', marker='o')
        elif int(dataindx[indx]) == 1:
            plt.scatter(dataSet[indx, 0], dataSet[indx, 1], c='green', marker='o')
        elif int(dataindx[indx]) == 2:
            plt.scatter(dataSet[indx, 0], dataSet[indx, 1], c='red', marker='o')
        elif int(dataindx[indx]) == 3:
            plt.scatter(dataSet[indx, 0], dataSet[indx, 1], c='cyan', marker='o')
kmeans.py:
from myUtil import *

def kMeans(dataSet, k):
    m = shape(dataSet)[0]  # 返回矩阵的行数

    # 本算法核心数据结构:行数与数据集相同
    # 列1：数据集对应的聚类中心,列2:数据集行向量到聚类中心的距离
    ClustDist = mat(zeros((m, 2)))

    # 随机生成一个数据集的聚类中心:本例为4*2的矩阵
    # 确保该聚类中心位于min(dataSet[:,j]),max(dataSet[:,j])之间
    clustercents = randCenters(dataSet, k)  # 随机生成聚类中心

    flag = True  # 初始化标志位,迭代开始
    counter = []  # 计数器

    # 循环迭代直至终止条件为False
    # 算法停止的条件：dataSet的所有向量都能找到某个聚类中心,到此中心的距离均小于其他k-1个中心的距离
    while flag:
        flag = False  # 预置标志位为False

        # ---- 1. 构建ClustDist： 遍历DataSet数据集,计算DataSet每行与聚类的最小欧式距离 ----#
        # 将此结果赋值ClustDist=[minIndex,minDist]
        for i in xrange(m):

            # 遍历k个聚类中心,获取最短距离
            distlist = [distEclud(clustercents[j, :], dataSet[i, :]) for j in range(k)]
            minDist = min(distlist)
            minIndex = distlist.index(minDist)

            if ClustDist[i, 0] != minIndex:  # 找到了一个新聚类中心
                flag = True  # 重置标志位为True，继续迭代

            # 将minIndex和minDist**2赋予ClustDist第i行
            # 含义是数据集i行对应的聚类中心为minIndex,最短距离为minDist
            ClustDist[i, :] = minIndex, minDist

        # ---- 2.如果执行到此处，说明还有需要更新clustercents值: 循环变量为cent(0~k-1)----#
        # 1.用聚类中心cent切分为ClustDist，返回dataSet的行索引
        # 并以此从dataSet中提取对应的行向量构成新的ptsInClust
        # 计算分隔后ptsInClust各列的均值，以此更新聚类中心clustercents的各项值
        for cent in xrange(k):
            # 从ClustDist的第一列中筛选出等于cent值的行下标
            dInx = nonzero(ClustDist[:, 0].A == cent)[0]
            # 从dataSet中提取行下标==dInx构成一个新数据集
            ptsInClust = dataSet[dInx]
            # 计算ptsInClust各列的均值: mean(ptsInClust, axis=0):axis=0 按列计算
            clustercents[cent, :] = mean(ptsInClust, axis=0)
    return clustercents, ClustDist
kmeans_test.py:
# -*- encoding:utf-8 -*-

from kmeans import *
import matplotlib.pyplot as plt

dataMat = file2matrix("testData/4k2_far.txt", "\t")   # 从文件构建的数据集
dataSet = dataMat[:, 1:]   # 提取数据集中的特征列

k = 4   # 外部指定1,2,3...通过观察数据集有4个聚类中心
clustercents, ClustDist = kMeans(dataSet, k)

# 返回计算完成的聚类中心
print "clustercents:\n", clustercents

# 输出生成的ClustDist：对应的聚类中心(列1),到聚类中心的距离(列2),行与dataSet一一对应
color_cluster(ClustDist[:, 0:1], dataSet, plt)
# 绘制聚类中心
drawScatter(plt, clustercents, size=60, color='red', mrkr='D')
plt.show()

结果如下：

2 二分K均值算法

二分k均值（bisecting k-means）算法为解决随机选择质心问题，不太受初始化问题的影响。 算法步骤： 1）将所有数据作为一个簇，k=2进行基本k均值算法，将数据分为两类。 2）迭代选择其中的簇进行k=2的基本k均值算法，使得最大程度降低损失函数值。 3）不断重复步骤（2），直到达到给定的簇数目为止。二分k均值算法的迭代过程如图，每次都进行k=2的基本k均值算法，经过三次迭代将数据分为四类。

Python代码, 来自Peter Harrington《Machine Learing in Action》：

# -- coding: utf-8 --
from numpy import *

def loadDataSet(fileName):
    # 获取数据集
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = map(float,curLine)
        dataMat.append(fltLine)
    return dataMat

def distEclud(vecA, vecB):
    # 根据式()计算vecA, vecB两点间的欧氏距离
    return sqrt(sum(power(vecA - vecB, 2)))

def randCent(dataSet, k):
    # 随机生成k个质心
    n = shape(dataSet)[1]                         # 获取数据集特征数量，即列数
    centroids = mat(zeros((k,n)))                 # 初始化一个k行n列的矩阵，元素为0，用于存储质心
    for j in range(n):
        minJ = min(dataSet[:,j])                  # 获取数据集第j列的最小值
        rangeJ = float(max(dataSet[:,j]) - minJ)  # 计算数据集第j列中，最大值减最小值的差
        # 随机生成k行1列的数组，元素在0到1之间，乘以rangeJ再加上minJ，则可得随机生成的第j列中最小值与最大值之间的一个数
        centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))
return centroids
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    # kMeans函数接受4个输入参数，数据集及簇的数目为必选参数，计算距离默认为欧氏距离，创建初始质心默认为随机生成
    m = shape(dataSet)[0]                         # 获取数据集数量，即行数
    clusterAssment = mat(zeros((m,2)))            # 初始化一个m行2列的矩阵，元素为0，第一列存储当前最近质心，第二列存储数据点与质心的距离平方
    centroids = createCent(dataSet, k)            # 创建k个初始质心
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            # 循环m个数据，寻找距离第i个数据最近的质心
            minIndex = -1                         # 初始化最近质心
            minDist = inf                         # 初始化第i个数据与最近质心的最小距离为无穷大
            for j in range(k):
                # 循环k个质心，寻找离第i个数据最近的质心
                distJI = distMeas(centroids[j,:],dataSet[i,:]) #计算第i行数据与第j个质点的欧氏距离
                if distJI < minDist:
                    minIndex = j                  # 更新最近质心为第j个
                    minDist = distJI              # 更新第i个数据与最近的质心的最小距离
            if clusterAssment[i,0] != minIndex: clusterChanged = True         # 若其中clusterAssment存储的质心与此次结果不一样，则需迭代，直至没有质心的改变
            clusterAssment[i,:] = minIndex,minDist**2    # 更新clusterAssment数据
        for cent in range(k):
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]     # 获取属于第cent个质心的所有数据
            centroids[cent,:] = mean(ptsInClust, axis=0) # 计算属于第cent个质心的所有数据各列的平均值，更新第cent个质心
    return centroids, clusterAssment              # centroids为当前k个质心，clusterAssment为各个数据所属质心及距离该质心的距离平方

def biKmeans(dataSet, k, distMeas=distEclud):
    # biKmeans函数接受3个输入参数，数据集及簇的数目为必选参数，计算距离默认为欧氏距离
    m = shape(dataSet)[0]                         # 获取数据集数量，即行数
    clusterAssment = mat(zeros((m,2)))            # 初始化一个m行2列的矩阵，元素为0，第一列存储当前最近质心，第二列存储数据点与质心的距离平方
    centroid0 = mean(dataSet, axis=0).tolist()[0] # 将所有点作为一个簇，计算数据集各列的平均值，作为初始簇的质心
    centList = [centroid0]                        # centList存储各个质心
    for j in range(m):
        clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2        # 计算初始质心与各数据的距离平方
    while (len(centList) < k):
        # 未达到指定簇的数目，则继续迭代
        lowestSSE = inf
        for i in range(len(centList)):
            # 循环簇的个数，寻找使SSE下降最快的簇的划分
            ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:] # 获取属于第i个质心的所有数据
            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas) # 将第i个簇二分为2个簇
            sseSplit = sum(splitClustAss[:,1])                                 # 计算第i个簇二分为2个簇后的SSE值
            sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) # 计算剩余数据的SSE值
            if (sseSplit + sseNotSplit) < lowestSSE:
                # 若二分后总体SSE值下降，则更新簇的信息
                bestCentToSplit = i
                bestNewCents = centroidMat         # 第i个簇二分后的质心
                bestClustAss = splitClustAss.copy()# 第i个簇二分后的结果
                lowestSSE = sseSplit + sseNotSplit # 更新当前SSE值
        bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList)   # 更新簇的分配结果，将二分后第二个簇分配到新簇
        bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit # 更新簇的分配结果，将二分后第一个簇分配到被划分簇
        centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]              # 更新簇的分配结果，更新未划分簇质心为二分后第一个簇的质心
        centList.append(bestNewCents[1,:].tolist()[0])                         # 更新簇的分配结果，添加新质心为二分后第二个簇的质心
        clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss # 将被划分簇数据更新为划分后簇
    return mat(centList), clusterAssment

3 K-means++

K-means++也改进了K-means算法初始中心点的选取，初始簇中心之间的距离应该越大越好。

算法步骤： 1）在数据样本中随机选择一个数据作为第一个簇的质心C1 2）计算其余数据样本与簇中心的最短距离令

，某样本点被选为下一个簇中心的概率为

概率越大，被选做新聚类中心的概率越大。 3）重复步骤（2）直到达到给定的k个类。当然K均值算法也可以处理带标签的数据，即学习矢量量化（Learning Vector Quantization）算法，这里就不展开了。参考： https://blog.csdn.net/eeeee123456/article/details/80176102 https://www.jianshu.com/p/e4d5a0fbcefe