目录

利用K-均值聚类算法对未标注数据分组

K-均值聚类算法

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

3 二分K-均值算法

4 示例:对地图上的点进行聚类

4.1 Yahoo!PlaceFinder API

4.2 对地理坐标进行聚类

5 本章小结


本章涉及到的相关代码和数据

利用K-均值聚类算法对未标注数据分组

本章内容:

聚类是一种无监督学习,他将类似的对象归到同一个簇中。有点像全自动分类,聚类算法几乎可以应用于所有对象,簇内的对象越相似,聚类的效果就越好。

K-means算法,可以发现k个不同的簇,且每个簇的中心采用簇中所含值的均值计算而成

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

K-均值聚类算法

K-均值是发现给定数据集的k个簇的算法。簇个数是由用户给定的,每一个簇通过其质心,即簇中所有点的中心来描述。

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

伪代码如下:

一般流程:

from numpy import *

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

# 计算欧氏距离
def distEclud(vecA,vecB):
    return sqrt(sum(power(vecA-vecB,2)))

# 构建一个包含k个随机质心的集合
def randCent(dataSet,k):
    n=shape(dataSet)[1]
    # 初始化矩阵:定义一个k*n的二维全是0的矩阵
    centroids=mat(zeros((k,n)))
    for j in range(n):
        minJ=min(dataSet[:,j])
        rangeJ=float(max(dataSet[:,j])-minJ)
        centroids[:,j]=minJ+rangeJ*random.rand(k,1)
    return centroids

测试以上函数

datMat=mat(loadDataSet('testSet.txt'))
# 测试计算距离函数
print(distEclud(datMat[0],datMat[1]))
# 测试随机质心函数
randCent(datMat,2)

得到的输出结果为:

《机器学习实战》10.K-均值聚类算法-LMLPHP

可以看出上述函数没有问题,接下来写K-means算法的函数以及对结果进行画图的函数

# k-均值聚类算法
        # 数据集,簇的个数 距离计算方式 创建初始质心的方式
def kMeans(dataSet,k,distMeas=distEclud,createCent=randCent):
    # 确定数据集中点的个数
    m=shape(dataSet)[0]
    # 创建一个矩阵存放每个点的簇分配结果(簇索引值、误差:当前点到簇质心的距离),后面会使用误差来评价聚类的效果
    clusterAssment=mat(zeros((m,2)))

    centroids=createCent(dataSet,k)
    clusterChanged=True
    # 循环直到所有点簇的分配结果不再改变为止
    while clusterChanged:
        clusterChanged=False
        for i in range(m):
            minDist=inf
            minIndex=-1
            for j in range(k):
                distJI=distMeas(centroids[j,:],dataSet[i,:])
                if distJI<minDist:
                    minDist=distJI
                    minIndex=j
            if clusterAssment[i,0]!=minIndex:
                clusterChanged=True
            clusterAssment[i,:]=minIndex
            minDist**2
        print(centroids)
        for cent in range(k):
            ptsInClust=dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent,:]=mean(ptsInClust,axis=0)
            # 质心    点分配结果
    # print(clusterAssment)
    return centroids,clusterAssment

import matplotlib.pyplot as plt
# 画图函数
def plotDataKMeans(centroids,clusterAssment):
    numClust,n=shape(centroids)
    fig=plt.figure()
    # 点的类型
    scatterMarkers=['s','o','^','8','p','d','v','h','>','<']
    axprops=dict(xticks=[],yticks=[])
    ax=fig.add_subplot(111)
    for i in range(numClust):
        # nonzero函数得到数组array中非零元素的位置
        ptsInCurrCluster = datMat[nonzero(clusterAssment[:,0].A==i)[0],:]
        markerStyle = scatterMarkers[i % len(scatterMarkers)]
        ax.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], marker=markerStyle, s=90)
    print(centroids)
    ax.scatter(centroids[:,0].flatten().A[0], centroids[:,1].flatten().A[0], marker='+', s=300)
    plt.show()

 测试结果

myCenttroids,clustAssing=kMeans(datMat,4)
# (可视化)
plotDataKMeans(myCenttroids,clustAssing)

得到的输出结果为:

《机器学习实战》10.K-均值聚类算法-LMLPHP

到目前为止,关于聚类的一切都进展顺利,但是事情并不总是如此

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

前面提到,在k-均值聚类中簇的数目k是一个用户预先定义的饿参数,但是k的选择并不一定准确。

考虑到上面的聚类结果,其实点的分配结果并没有那么准确。K-均值算法收敛单聚类效果交叉的原因时,K-均值算法手来能与局部最小值,而非全局最小值。

一种用于度量剧烈效果的指标是SSE(误差平方和)。SSE值越小表示数据集越接近于他们的质心,聚类效果也越好。因为误差取了平方,因此更加中重视那些远离中心的点。一种可以肯定可以降低SSE值的方法是增加簇的个数,但这违背了聚类的目标,聚类的目标是保持粗数目不变的情况下提高簇的质量。

我们可以对生成的簇进行后处理,一种方法是将具有最大SSE值的簇划分为两个簇,具体实现时可以将最大粗包含的点过滤出来并在这些点上运行K-均值聚类算法,其中k设为2为了保持簇总数不变,可以将某两个簇进行合并。

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

3 二分K-均值算法

为了歌赋上述问题,一种二分K-均值算法:该算法首先将所有点作为一个簇,然后将该簇一分为二。之后选择其中一个簇继续进行划分,选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复,直到得到用户的满意为止。

伪代码:

另一种做法是选择SSE最大的簇进行划分,直到簇数目达到用户指定的数目为止。

def bikmeans(dataSet, k, distMeas=distEclud):
    """
    二分K-均值聚类算法
    :param dataSet:数据集
    :param k:质心数量
    :param distMeas:距离计算方法,默认欧氏距离distEclud()
    :return:
    """
    numSamples = dataSet.shape[0]  # 获得数据集的样本数
    
    # 创建一个初始簇
    clusterAssment = mat(zeros((numSamples, 2)))  # 初始化一个元素值0的(numSamples,2)矩阵
    centroid0 = mean(dataSet, axis=0).tolist()[0]  # 列表中的第一个列表元素:即全部数据每个属性
    centList = [centroid0]  # 当前聚类列表为将数据集聚为一类
    for j in range(numSamples):  # 遍历每个数据集样本
        clusterAssment[j, 1] = (distMeas(mat(centroid0), dataSet[j, :])) ** 2  # 计算当前聚为一类时各个数据点距离质心的平方距离

     # 循环,直至二分k-均值达到k类为止
    while len(centList) < k:  
        lowestSSE = inf  # 将当前最小平方误差置为正无穷
        for i in range(len(centList)):  # 遍历当前每个聚类
            # 通过数组过滤筛选出属于第i类的数据集合
            ptsInCurrCluster = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :]
            # 对该类利用二分k-均值算法进行划分,返回划分后结果,及误差
            centroidMat, splitClusAss = kMeans(ptsInCurrCluster, 2, distMeas)
            sseSplit = sum(splitClusAss[:, 1])  # 计算该类划分后两个类的误差平方和
            # 计算数据集中不属于该类的数据的误差平方和
            sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0], 1])
            print("sseSplit,and notSplit:", sseSplit, sseNotSplit)
            if (sseSplit + sseNotSplit) < lowestSSE:  # 划分第i类后总误差小于当前最小总误差
                bestCentToSplit = i  # 第i类作为本次划分类
                bestNewCents = centroidMat  # 第i类划分后得到的两个质心向量
                bestClustAss = splitClusAss.copy()  # 复制第i类中数据点的聚类结果即误差值
                lowestSSE = sseSplit + sseNotSplit  # 将划分第i类后的总误差作为当前最小误差
        # 数组过滤筛选出本次2-均值聚类划分后类编号为1数据点,将这些数据点类编号变为当前类个数+1,作为新的一个聚类
        bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)
        # 同理,将划分数据集中类编号为0的数据点的类编号仍置为被划分的类编号,使类编号连续不出现空缺
        bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit
        print("the bestCentToSplit is:", bestCentToSplit)
        print("the len of bestClustAss is :", len(bestClustAss))
        centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0]  # 更新质心列表中的变化后的质心向量
        centList.append(bestNewCents[1, :].tolist()[0])  # 添加新的类的质心向量
        # 更新clusterAssment列表中参与2-均值聚类数据点变化后的分类编号,及数据该类的误差平方
        clusterAssment[nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :] = bestClustAss
    return mat(centList), clusterAssment

测试函数:

datMat2=mat(loadDataSet("testSet.txt"))
# print(datMat2)
centList,myNewAssments=kMeans(datMat2,4)
plotDataKMeans(centList,myNewAssments)

得到的输出结果为:

《机器学习实战》10.K-均值聚类算法-LMLPHP

《机器学习实战》10.K-均值聚类算法-LMLPHP

4 示例:对地图上的点进行聚类

示例:对于地理数据应用的二分K-均值算法

4.1 Yahoo!PlaceFinder API

书中所提到的API已经不能在使用,我们直接使用已经提供的places.txt文件

4.2 对地理坐标进行聚类

# 球面距离计算
def distSLC(vecA,vecB):
    a=sin(vecA[0,1]*pi/180)*sin(vecB[0,1]*pi/180)
    b=cos(vecA[0,1]*pi/180)*cos(vecB[0,1]*pi/180)*cos(pi*(vecB[0,0]-vecA[0,0])/180)
    # 反三角函数中的反余弦
    return arccos(a+b)*6371.0



import matplotlib.pyplot as plt
def clusterClubs(numClust=5):
    datList=[]
    # 打开文本文件
    for line in open('places.txt').readlines():
        lineArr=line.split('\t')
        # 文本文件的第五列和第四列为坐标
        datList.append([float(lineArr[4]),float(lineArr[3])])
    datMat=mat(datList)
    # 进行聚类:距离计算公式利用球面计算公式
    myCentroids,clustAssing=bikmeans(datMat,numClust,distMeas=distSLC)

    # 画图
    fig=plt.figure()
    # rect=[0.1,0.1,0.8,0.8]
    rect=[1,1,1,1]
    scatterMarkers=['s','o','^','8','p','d','v','h','>','<']
    axprops=dict(xticks=[],yticks=[])
    ax0=fig.add_axes(rect,label='ax0',**axprops)
    imgP=plt.imread("Portland.png")
    ax0.imshow(imgP)
    ax1=fig.add_axes(rect,label='ax1',frameon=False)

    for i in range(numClust):
        # nonzero函数得到数组array中非零元素的位置
        ptsInCurrCluster = datMat[nonzero(clustAssing[:,0].A==i)[0],:]
        markerStyle = scatterMarkers[i % len(scatterMarkers)]
        ax1.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], marker=markerStyle, s=50)
    # print(centroids)
    ax1.scatter(myCentroids[:,0].flatten().A[0], myCentroids[:,1].flatten().A[0], marker='+', s=200)
    plt.show()
 

 测试函数

clusterClubs()

得到的输出结果为:

《机器学习实战》10.K-均值聚类算法-LMLPHP

 《机器学习实战》10.K-均值聚类算法-LMLPHP

5 本章小结

聚类是一种无监督学习。所谓无监督就是事先并不知道要寻找的内容,即没有目标变量。聚类将数据点归到多个簇中,其中相似数据点处于同一簇,而不相似数据点处于不同簇中。聚类中可以使用多种不同方法来计算相似度

一种广泛使用的聚类算法是K-均值算法。其中k是用户指定的要创建的簇的数目。K-均值聚类算法以k个随机质心开始,算法会计算每个点到质心的距离。每个点被分配到距其最近的簇质心,然后紧接着基于新分配到簇的点更新质心。以上过程重复数次,直到簇质心不再改变。这种简单的算法非常有效但是也容易受到初始簇质心的影响。

为了获得更好的效果,可以使用另一种二分K-均值的聚类算法。二分K-均值算法首先将所有点作为一个簇,然后使用K-均值算法(k=2)对其划分。下一次迭代时,选择有最大误差的簇进行划分。该过程重复直到k个簇创建成功为止,效果更好。

11-29 11:40