機器學習實戰-第10章利用K-均值聚類算法對未标注資料分組

聚類：無監督學習，将相似的對象歸到同一個簇中

K-均值聚類算法：

僞代碼如下：

建立k個點作為起始軸心

當任意一個點的簇分類配置設定結果發生改變時

對資料集中的每個資料點

對每個質心

計算質心與資料點之間的距離

将資料點配置設定到距其最近的簇

對每一個簇，計算簇中所有點的均值并将均值作為質心

import numpy as np

def loadDataSet(fileName):
    dataMat = {}
    fr = open(fileName)
    for line in fr.readline():
        curLine = line.strip().split('\t')
        fltLine = map(float,curLine)
        dataMat.append(fltLine)
    return dataMat


#計算兩個向量的歐式距離
def distEclud(vecA, vecB):
    return np.sqrt(sum(np.power(vecA - vecB, 2)))

#為給定資料集建構一個包含k個随機質心的集合
def randCent(dataSet, k):
    n = np.shape(dataSet)[1]
    centroids = np.mat(np.zeros((k,n)))
    for j in range(n):
        minJ = min(dataSet[:j])
        rangeJ = float(max(dataSet[:,j]) - minJ)
        #生成0到1之間的随機數并通過取值範圍和最小值，以便確定随機點在資料的邊界之内
        centroids[:,j] = minJ + rangeJ + np.random.rand(k,1)
    return centroids
           

K-均值聚類算法

def KMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    #确定資料集中資料點的總數
    m=np.shape(dataSet)[0] 
    #一列記錄簇索引值，第二列存儲誤差，誤差是指目前點到簇質心的距離
    clusterAssment = np.mat(np.zeros((m,2)))
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            minDist = np.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 #任意簇發配置設定結果發生改變，更新clusterChanged的值
            clusterAssment[i,:] = minIndex,minDist**2
        print(centroids)
        #周遊所有質心
        for cent in range(k):
            ptsInClust = dataSet[np.nonzero(clusterAssment[:,0].A==cent)[0]] #通過數組過濾來獲得給定簇的所有點
            centroids[cent,:] = np.mean(ptsInClust, axis=0) #計算所有點的均值，給定列方向進行均值運算
    return  centroids,clusterAssment #傳回所有的類質心與點配置設定結果
           

度量聚類效果的名額SSE（誤差平方和），對應clusterAssment矩陣的第一列之和。SSE越小表示資料點越接近于它們的質心，聚類效果也越好，聚類的目标是保持簇數目不變的情況下提高簇的品質

二分K-均值算法：

首先将所有點作為一個簇，然後将該簇一分為2，之後選擇其中一個簇繼續進行劃分，選擇哪一個簇進行劃分取決于對其劃分是否可以最大程度降低SSE的值，上述基于SSE的劃分過程不斷重複，直到得到使用者指定的簇數目為止。

另一種做法是選擇SSE最大的簇進行劃分，直到簇數目達到使用者指定的數目為止

實作算法如下：

def biKmeans(dataSet, k, distMeas=distEclud):
    m = np.shape(dataSet)[0]
    clusterAssment = np.mat(np.zeros((m, 2))) #矩陣存儲資料集中每個點的簇配置設定結果及平方誤差
    centroid0 = np.mean(dataSet, axis=0).tolist()[0] #計算整個資料集的質心
    centList = [centroid0] #使用一個清單來保留所有的質心
    for j in range(m):
        clusterAssment[j,1] = distMeas(np.mat(centroid0), dataSet[j,:]**2)
        while(len(centList) < k):
            lowestSSE = np.inf #一開始将最小SSE設為無窮大
            #周遊簇清單centList中的每一個簇
            for i in range(len(centList)):
                #将簇中所有點看成一個小的資料集ptsCurrCluster
                ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:,0].A==i)[0],:]
                #生成兩個質心（簇），同時給出每個簇的誤內插補點
                centroidMat, splitClutserAss = KMeans(ptsInCurrCluster, 2 , distMeas)
                #本次資料集的誤差
                sseSplit = sum(splitClutserAss[:,1])
                #剩餘資料集的誤差
                sseNotSplit = sum(clusterAssment[np.nonzero(clusterAssment[:,0].A!=i)[0],1])
                print("seeSplit, and notSplit:",sseSplit,sseNotSplit)
                #誤差與剩餘資料集的誤差之和作為本次劃分的誤差
                if(sseSplit + sseNotSplit) < lowestSSE:
                    bestCentToSplit = i
                    bestNewCents = centroidMat #更新簇
                    bestClustAss = splitClutserAss.copy() #将簇中所有點的配置設定結果進行修改
                    lowestSSE = sseSplit + sseNotSplit #更新lowestSSE
            #會得到兩個編号分别為0和1的結果簇，将簇編号修改為劃分簇及新加簇的編号
            bestClustAss[np.nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList)
            bestClustAss[np.nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
            print('the bestCentTosplit is:',bestCentToSplit)
            print('the len of bestClustAss is:',len(bestCentToSplit))
            centList[bestCentToSplit] = bestNewCents[0,:]
            centList.append(bestNewCents[1,:])
            clusterAssment[np.nonzero(clusterAssment[:,0].A ==bestCentToSplit)[0],:] = bestClustAss
        return np.mat(centList), clusterAssment