Python机器学习算法实践_自定义实现kmeans

冷不防 2022-05-16 04:16 200阅读 0赞

## k-means算法步骤： ##

*  1.随机选取k个质心（k值取决于你想聚成几类）
 *  2.计算样本到质心的距离，距离质心距离近的归为一类，分为k类
 *  3.求出分类后的每类的新质心
 *  4.判断新旧质心是否相同，如果相同就代表已经聚类成功，如果没有就循环2-3直到相同

## Python实现 ##

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')

#距离 度量方式：
    #1.欧氏距离
    def disEuclid(vecA,vecB):
        return sqrt(sum(power((vecA-vecB),2)))
    #测试
    vecA=[1.658985,4.285136]
    vecB=[-3.453687,3.424321]
    disEuclid(mat(vecA),mat(vecB))
    #2.余弦距离
    def disCos(x,y):
        dist1 = 1-dot(x,y.T)/(linalg.norm(x)*linalg.norm(y))
        return dist1
    #测试
    vecA=[1.658985,4.285136]
    vecB=[-3.453687,3.424321]
    disCos(mat(vecA),mat(vecB))

#初始质心选取
    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
    
    #测试初始质心的范围
    dataMat=mat(dataMat)
    centers=randCenter(dataMat,2)
    print(centers)
    
    #测试这个质心是否在数据集范围
    print('最小值：',min(dataMat[:,0]))
    print('最大值：',max(dataMat[:,0]))
    print('最小值：',min(dataMat[:,1]))
    print('最大值：',max(dataMat[:,1]))

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 #某个点距离质心点的最小距离
                minIndex=-1#有最小距离的质心的索引——知道这个簇了
                for j in range(k):
                    distJI=disMea(centers[j,:],dataSet[i,:])
                    #print('===:',centers[j,:])
                    #print(']][][[][]]',dataSet[i,:])
                    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]]
                #print('pointsInCluster:',pointsInCluster)
                centers[cent,:]=mean(pointsInCluster,axis=0)#对于这个簇中每个点的列取均值，更新中心点
        return centers,clusterAssment
    #测试
    dataMat=mat(loadDataSet('dataset/testSet.txt'))
    centers,clusterAssment=myKMeans(dataMat,4)
    print(centers)
    print(clusterAssment)#第一个列为簇的编号，第二列是当前点到这个簇的质心的距离

# **testSet.txt内容如下：** #

1.658985 4.285136  
\-3.453687 3.424321  
4.838138 -1.151539  
\-5.379713 -3.362104  
0.972564 2.924086  
\-3.567919 1.531611  
0.450614 -3.302219  
\-3.487105 -1.724432  
2.668759 1.594842  
\-3.156485 3.191137  
3.165506 -3.999838  
\-2.786837 -3.099354  
4.208187 2.984927  
\-2.123337 2.943366  
0.704199 -0.479481  
\-0.392370 -3.963704  
2.831667 1.574018  
\-0.790153 3.343144  
2.943496 -3.357075  
\-3.195883 -2.283926  
2.336445 2.875106  
\-1.786345 2.554248  
2.190101 -1.906020  
\-3.403367 -2.778288  
1.778124 3.880832  
\-1.688346 2.230267  
2.592976 -2.054368  
\-4.007257 -3.207066  
2.257734 3.387564  
\-2.679011 0.785119  
0.939512 -4.023563  
\-3.674424 -2.261084  
2.046259 2.735279  
\-3.189470 1.780269  
4.372646 -0.822248  
\-2.579316 -3.497576  
1.889034 5.190400  
\-0.798747 2.185588  
2.836520 -2.658556  
\-3.837877 -3.253815  
2.096701 3.886007  
\-2.709034 2.923887  
3.367037 -3.184789  
\-2.121479 -4.232586  
2.329546 3.179764  
\-3.284816 3.273099  
3.091414 -3.815232  
\-3.762093 -2.432191  
3.542056 2.778832  
\-1.736822 4.241041  
2.127073 -2.983680  
\-4.323818 -3.938116  
3.792121 5.135768  
\-4.786473 3.358547  
2.624081 -3.260715  
\-4.009299 -2.978115  
2.493525 1.963710  
\-2.513661 2.642162  
1.864375 -3.176309  
\-3.171184 -3.572452  
2.894220 2.489128  
\-2.562539 2.884438  
3.491078 -3.947487  
\-2.565729 -2.012114  
3.332948 3.983102  
\-1.616805 3.573188  
2.280615 -2.559444  
\-2.651229 -3.103198  
2.321395 3.154987  
\-1.685703 2.939697  
3.031012 -3.620252  
\-4.599622 -2.185829  
4.196223 1.126677  
\-2.133863 3.093686  
4.668892 -2.562705  
\-2.793241 -2.149706  
2.884105 3.043438  
\-2.967647 2.848696  
4.479332 -1.764772  
\-4.905566 -2.911070