Python机器学习算法实践——二分k-均值算法

深碍√TFBOYSˉ_ 2022-05-16 05:52 170阅读 0赞

## 二分k-均值算法步骤： ##

首先将所有点作为一个属，然后将该簇-分为二，之 后选择其中-个簇进续进行划分，选择哪一个簇进行划取决于对其划分是否可以最大程度降低SSE的值，上述基于SSE的别分过程不断重复，直到得到用户指定的属数目为止，  
将所有点看成一个簇  
当簇数目小于k时  
对于每一个簇:  
计算总误差  
在给定的簇上面进行K-均值聚类(k=2)计算将该簇一分为二后的总误差  
选择使得误差最小的那个簇进行划分操作  
另一种做法选择S正最大的簇进行划分，直到簇数目达到用户指定的数目为止。

## Python实现 ##

# -*- coding: utf-8 -*-
    """
    Created on Thu Aug 16 11:09:04 2018
    
    @author: wjw
    """
    
    from numpy import  *
    
    def loadDataSet(fileName):
        dataMat=[]
        fr=open(fileName)
        for line in fr.readlines():
            arr=line.strip().split('\t')
            #map (回调函数，列表)-》循环列表中的每个值，调用回归函数得到结果，存到map -》 list
            l=list(map(float,arr))#float 强制类型转换
            dataMat.append(l)
        return dataMat
        
    dataMat=loadDataSet('dataset/testSet.txt')
    #print(dataMat[0:5])
        
    #距离 度量方式：
    #1.欧氏距离
    def disEuclid(vecA,vecB):
        return sqrt(sum(power((vecA-vecB),2)))
    
    #初始质心选取
    def randCenter(dataSet,k):
        n=shape(dataSet)[1]#n=..列
        centers=mat(zeros((k,n)))
        #print(centers)
        for j in range(n): #每循环一次，产生的一个特征值
            #当前第j列的最小值，与最大值，求范围
            minJ=min(dataSet[:,j])
            #print('minJ:',minJ)
            maxJ=max(dataSet[:,j])
            rangeJ=float(maxJ-minJ)
            #生成随机数 ，k行（代表k个中心点）#0-1
            centers[:,j]=minJ+rangeJ*random.rand(k,1)#random.rand(k,1)->k行一列的数据 randej标量
            print(centers[:,j])
        return centers
        
    def myKMeans(dataSet,k,disMea=disEuclid,initCenter=randCenter):
        '''
        
        '''
        m=shape(dataSet)[0]
        #这个zeros是一个m行2列的数据（记录这个点所属的簇的索引，，记录这个点到其质心的距离）
        clusterAssment=mat(zeros((m,2)))
        
        #生成随机质心
        centers=initCenter(dataSet,k)
        
        clusterChanged=True
        while clusterChanged:
            clusterChanged=False
            #循环每个点，计算他与每个质心的位置
            for i in range (m):
                #这个点到某质心的最小距离及质心所在的索引
                minDist=inf #某个点距离质心点的最小距离 inf 无穷大
                minIndex=-1#有最小距离的质心的索引——知道这个簇了
                for j in range(k):
                    distJI=disMea(centers[j,:],dataSet[i,:])#算距离
                    #print('===:',centers[j,:])
                    #print(']][][[][]]',dataSet[i,:])
                    #print('================================================================')
                    if distJI < minDist:
                        minDist=distJI
                        minIndex=j
                    #for I in   range(m)循环完，表明已经找到了第i个数据点所属的簇，且计算出了距离         
                if clusterAssment[i,0]!=minIndex:
                    clusterChanged=True
                    #更新这个点到质心的索引及误差
                clusterAssment[i,:]=minIndex,minDist**2
                
                #============以上的循环个更新每个点的簇======================================================================
                
            #遍历所有的簇，重新找质心
            for cent in range(k):
                flag=clusterAssment[:,0].A==cent #查找这个 cent 簇所有的点
                #print('flag:',flag)
                pointsInCluster=dataSet[nonzero(flag)[0]]#第cent个簇所有点
                #print('pointsInCluster:',pointsInCluster)
                centers[cent,:]=mean(pointsInCluster,axis=0)#对于这个簇中每个点的列取均值，更新中心点centers[cent]
        return centers,clusterAssment
        
        
    dataMat=mat(loadDataSet('dataset/testSet.txt'))
    centers,clusterAssment=myKMeans(dataMat,4)
    print(centers)
    print(clusterAssment)#第一个列为簇的编号，第二列是当前点到这个簇的质心的距离
        
    def biKmeans(dataSet,k,distMea=disEuclid):
        #1.将所有点看成一个簇
        #2.取出这个簇的中心点
        #3.计算这个簇中每个点到中心点的距离
        #4.这个zeros是一个m行2列的数据（记录这个点所属的簇的索引，，记录这个点到其质心的距离）
        #clusterAssment=mat(zeros((m,2)))
        #存所有的中心点
        
        m=shape(dataSet)[0]
        #这个zeros是一个m行2列的数据（记录这个点所属的簇的索引，，记录这个点到其质心的距离）
        clusterAssment=mat(zeros((m,2)))
        center0=mean(dataSet,axis=0).tolist()[0]
        print('第一个中心点：',center0)
        centList=[center0]
        for j in range(m):
            clusterAssment[j,1]=distMea(mat(center0),dataSet[j,:])**2
        #循环来产生质心
        
        while(len(centList)<k):#当簇数目小于k时
            lowestSSE=inf #初始化最小 误差平方和
            #循环每个簇
            for i in range (len(centList)):
                #到dataset中筛选出属于第i个簇的数据样本
                pointsInCluster=dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
                #对这个簇中的样本进行一次k=2的聚类
                centroidMat,splitClustAss=myKMeans(pointsInCluster,2,distMea)
                sseSplit=sum(splitClustAss[:,1])
                #剩余的数据集的误差
                #sseSplit=sum(splitClustAss[:,1])-sseSplit
                sseNotSplit=sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
                #总误差
                totalSplit=sseSplit+sseNotSplit
                if totalSplit<lowestSSE:
                    bestCentToSplit=i#最好的质心索引
                    bestNewCent=centroidMat
                    bestClustAss=splitClustAss.copy()
                    lowestSSE=totalSplit
            #2分k聚类返回系数0或1，需要把1换成当前簇数目，以免造成重复
            bestClustAss[ nonzero(bestClustAss[:,0].A==1)[0],0 ]=len(centList)
            #返回的是第几行第几行
            #把0换成别切分的簇，或者与上面的交换赋值也可以
            bestClustAss[ nonzero(bestClustAss[:,0].A==0)[0],0]=bestCentToSplit
            #print('===:',bestCentToSplit)
            #将centlist指定位置上的质心换成分割后的质心
            centList[bestCentToSplit]=bestNewCent[0,:].tolist()[0]
            #将另一个质心添加上去
            centList.append(bestNewCent[1,:].tolist()[0])
            #将划分后的新质点及点分布赋值给结果矩阵
            clusterAssment[nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:]=bestClustAss
        return mat(centList),clusterAssment
    
    datMat=mat(loadDataSet('dataset/testSet.txt'))
    centList,clusterAssment=biKmeans(dataMat,4)
    print(centList)

注：biKmeans 函数就是二分k-均值算法

可借助spyder的debug模式进行调试，帮助理解代码，如果spyder版本太低可以如下命令进行升级

conda update spyder