机器学习--K-means算法

小鱼儿 2022-05-09 03:04 92阅读 0赞

### 概述 ###

聚类（K-mean）是一种典型的无监督学习。

采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。

该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。

### 核心思想 ###

通过**迭代**寻找k个类簇的一种划分方案，使得用这k个类簇的均值来代表相应各类样本时所得的总体误差最小。

k个聚类具有以下特点：**各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。**

k-means算法的基础是***最小误差平方和准则**,***

其代价函数是：

![1110462-20170713163435540-887498636.png][]

式中，μc(i)表示第i个聚类的均值。

各类簇内的样本越相似，其与该类均值间的误差平方越小，对所有类所得到的误差平方求和，即可验证分为k类时，各聚类是否是最优的。

上式的代价函数无法用解析的方法最小化，只能有迭代的方法。

### 实践 ###

第一步，为了测试，使用脚本生成1000个数据的数据集。

import numpy as np
    
    #x = np.random.uniform(-6,6,2)
    #print(str(x[0])+'\t'+str(x[1]))
    
    with open('data.txt', 'w') as f:  # 以写的方式打开文件
        for i in range(250):
            x1 = 2*np.random.randn(2)
            x2 = 2 * np.random.randn(2)
            x3 = 2 * np.random.randn(2)
            x4 = 2 * np.random.randn(2)
            strr1 = str(x1[0]+6)+'\t'+str(x1[1]+6)+'\n'
            strr2 = str(x2[0] + 6) + '\t' + str(x2[1] - 6) + '\n'
            strr3 = str(x3[0] - 6) + '\t' + str(x3[1] + 6) + '\n'
            strr4 = str(x4[0] - 6) + '\t' + str(x4[1] - 6) + '\n'
            strr = strr1+strr2+strr3+strr4
            f.write(strr)

查看data.txt里面的数据：

![70][]

第二步K-means算法：（解释都在注释中）

from numpy import *
    import numpy as np
    import matplotlib.pyplot as plt
    import time
    from threading import Thread
    #加载数据
    
    plt.ion() #开启interactive mode
    
    def loadDataSet(fileName):#解析文件，按tab分割字符，得到一个浮点数字类型的矩阵
        dataMat = []#文件的最后一个字段是类别标签
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float,curLine))#将每个元素转成float类型
            dataMat.append(fltLine)
        dataMat = np.array(dataMat)
        return dataMat
    
    def distEclud(vecA,vecB):
        return sqrt(sum(power(vecA - vecB,2)))#求两个向量之间的距离
    
    #构建聚簇中心，取k个（此例中为4）随机质心
    def randCent(dataSet,k):
        n = shape(dataSet)[1]
        centroids = mat(zeros((k,n)))#每个质心有n个坐标值，总共k个质心
        for j in range(n):
            minJ = min(dataSet[:,j])
            maxJ = max(dataSet[:,j])
            rangeJ = float(maxJ-minJ)
            centroids[:,j] = minJ + rangeJ * random.rand(k,1)
        return centroids
    
    #k-means聚类算法
    def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent):
        m = shape(dataSet)[0]#获取总数据量
        clusterAssment = mat(zeros((m,2)))#用于存放该样本属于哪类及质心距离
        #clusterAssment第一列存放该数据所属的中心点，第二列是该数据到中心点的距离
        centroids = createCent(dataSet,k)#创建k个中心点
        clusterChanged = True#用来判断聚类是否收敛
        while clusterChanged:
            clusterChanged = False
            for i in range(m):#把每个数据点划分到离它最近的中心点
                minDist = inf;minIndex = -1;#inf为无穷，minIndex为质心的代号
                for j in range(k):#分别计算各个点离k个质心的距离
                    distJI = distMeans(centroids[j,:],dataSet[i,:])
                    if distJI < minDist:#找到离这个点最近的质心
                        minDist = distJI;minIndex = j
                if clusterAssment[i,0] != minIndex: #只要有一个数据点发生变化，就说明分类还没收敛，还要继续
                    clusterChanged = True
    
                clusterAssment[i,:] = minIndex,minDist**2 #并将第i个数据点的分配情况存入字典
            print(centroids)
            for cent in range(k):
                ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]]  # 取第一列等于cent的点
                centroids[cent, :] = mean(ptsInClust, axis=0)  # 算出这些数据的中心点，及当前更新后的质点
    
            ii = 0
            for cent in clusterAssment:
                #print(cent[0,0])
                if cent[0,0] == 0:
                    x,y = dataSet[ii,0],dataSet[ii,1]
                    plt.scatter(x, y, c='y')
                elif cent[0, 0] == 1:
                    x, y = dataSet[ii, 0], dataSet[ii, 1]
                    plt.scatter(x, y, c='r')
    
                elif cent[0, 0] == 2:
                    x, y = dataSet[ii, 0], dataSet[ii, 1]
                    plt.scatter(x, y, c='b')
    
                elif cent[0, 0] == 3:
                    x, y = dataSet[ii, 0], dataSet[ii, 1]
                    plt.scatter(x, y, c='g')
                ii = ii + 1
    
            plt.pause(1)
            plt.close()
    
    
        return centroids, clusterAssment
    
    datMat = mat(loadDataSet('data.txt'))
    myCentroids,clustAssing = kMeans(datMat,4)
    print(myCentroids)
    #print(clustAssing)

数据集比较简单，数据很快就收敛。（数据集越复杂，越大，收敛会越慢）

![70 1][]![70 2][]

可以看到最终得到的四个聚类的中心都在（+-6，+-6）附近，符合题设。

参考：[https://www.cnblogs.com/ahu-lichang/p/7161613.html][https_www.cnblogs.com_ahu-lichang_p_7161613.html]

[1110462-20170713163435540-887498636.png]: /images/20220509/d1c92ecad77c45b593a5a0634e904253.png
[70]: /images/20220509/b8f3cc9e848b4cebba1abeb80d645cdf.png
[70 1]: https://img-blog.csdn.net/20181008183546654?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDA0MDA3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: /images/20220509/e907a027057d4fe0890af1ae02f40374.png
[https_www.cnblogs.com_ahu-lichang_p_7161613.html]: https://www.cnblogs.com/ahu-lichang/p/7161613.html