工作原理

聚類是一種無監(jiān)督的學(xué)習(xí)，它將相似的對象歸到同一個簇中。類似于全自動分類（自動的意思是連類別都是自動構(gòu)建的）。K-均值算法可以發(fā)現(xiàn)k個不同的簇，且每個簇的中心采用簇中所含值的均值計算而成。它的工作流程的偽代碼表示如下：

          
            創(chuàng)建k個點作為起始質(zhì)心
當(dāng)任意一個點的簇分配結(jié)果發(fā)生改變時
    對數(shù)據(jù)集中的每個數(shù)據(jù)點
        對每個質(zhì)心
            計算質(zhì)心與數(shù)據(jù)點之間的距離
        將數(shù)據(jù)點分配到距其最近的簇
    對每一個簇，計算簇中所有點的均值并將均值作為質(zhì)心
    
          
        

python實現(xiàn)

首先是兩個距離函數(shù)，一般采用歐式距離

          
            def distEclud(self, vecA, vecB):
    return np.linalg.norm(vecA - vecB)
def distManh(self, vecA, vecB):
    return np.linalg.norm(vecA - vecB,ord = 1)
          
        

然后是randcent(),該函數(shù)為給點的數(shù)據(jù)集構(gòu)建一個包含k個隨機質(zhì)心的集合

          
            def randCent(self, X, k):
    n = X.shape[1]  # 特征維數(shù)，也就是數(shù)據(jù)集有多少列
    centroids = np.empty((k, n))  # k*n的矩陣，用于存儲每簇的質(zhì)心
    for j in range(n):  # 產(chǎn)生質(zhì)心，一維一維地隨機初始化
        minJ = min(X[:, j])
        rangeJ = float(max(X[:, j]) - minJ)
        centroids[:, j] = (minJ + rangeJ * np.random.rand(k, 1)).flatten()
    return centroids
          
        

對于kMeans和biKmeans的實現(xiàn)，參考了scikit-learn中kMeans的實現(xiàn)，將它們封裝成類。

• n_clusters —— 聚類個數(shù)，也就是k
  
• initCent —— 生成初始質(zhì)心的方法,'random'表示隨機生成，也可以指定一個數(shù)組
• max_iter —— 最大迭代次數(shù)

          
            class kMeans(object):
    def __init__(self, n_clusters=10, initCent='random', max_iter=300):
        if hasattr(initCent, '__array__'):
            n_clusters = initCent.shape[0]
            self.centroids = np.asarray(initCent, dtype=np.float)
        else:
            self.centroids = None
        self.n_clusters = n_clusters
        self.max_iter = max_iter
        self.initCent = initCent
        self.clusterAssment = None
        self.labels = None
        self.sse = None
    # 計算兩個向量的歐式距離
    def distEclud(self, vecA, vecB):
        return np.linalg.norm(vecA - vecB)

    # 計算兩點的曼哈頓距離
    def distManh(self, vecA, vecB):
        return np.linalg.norm(vecA - vecB, ord=1)

    # 為給點的數(shù)據(jù)集構(gòu)建一個包含k個隨機質(zhì)心的集合
    def randCent(self, X, k):
        n = X.shape[1]  # 特征維數(shù)，也就是數(shù)據(jù)集有多少列
        centroids = np.empty((k, n))  # k*n的矩陣，用于存儲每簇的質(zhì)心
        for j in range(n):  # 產(chǎn)生質(zhì)心，一維一維地隨機初始化
            minJ = min(X[:, j])
            rangeJ = float(max(X[:, j]) - minJ)
            centroids[:, j] = (minJ + rangeJ * np.random.rand(k, 1)).flatten()
        return centroids

    def fit(self, X):
    # 聚類函數(shù)
    # 聚類完后將得到質(zhì)心self.centroids,簇分配結(jié)果self.clusterAssment    
        if not isinstance(X, np.ndarray):
            try:
                X = np.asarray(X)
            except:
                raise TypeError("numpy.ndarray required for X")
        m = X.shape[0]  # 樣本數(shù)量
        self.clusterAssment = np.empty((m, 2))  # m*2的矩陣，第一列表示樣本屬于哪一簇，第二列存儲該樣本與質(zhì)心的平方誤差(Squared Error,SE)
        if self.initCent == 'random':   # 可以指定質(zhì)心或者隨機產(chǎn)生質(zhì)心
            self.centroids = self.randCent(X, self.n_clusters)
        clusterChanged = True
        for _ in range(self.max_iter):# 指定最大迭代次數(shù)
            clusterChanged = False
            for i in range(m):  # 將每個樣本分配到離它最近的質(zhì)心所屬的簇
                minDist = np.inf
                minIndex = -1
                for j in range(self.n_clusters):    #遍歷所有數(shù)據(jù)點找到距離每個點最近的質(zhì)心
                    distJI = self.distEclud(self.centroids[j, :], X[i, :])
                    if distJI < minDist:
                        minDist = distJI
                        minIndex = j
                if self.clusterAssment[i, 0] != minIndex:
                    clusterChanged = True
                    self.clusterAssment[i, :] = minIndex, minDist ** 2
            if not clusterChanged:  # 若所有樣本點所屬的簇都不改變,則已收斂，提前結(jié)束迭代
                break
            for i in range(self.n_clusters):  # 將每個簇中的點的均值作為質(zhì)心
                ptsInClust = X[np.nonzero(self.clusterAssment[:, 0] == i)[0]]  # 取出屬于第i個族的所有點
                if(len(ptsInClust) != 0):
                    self.centroids[i, :] = np.mean(ptsInClust, axis=0)

        self.labels = self.clusterAssment[:, 0]
        self.sse = sum(self.clusterAssment[:, 1])   # Sum of Squared Error,SSE
          
        

kMeans的缺點在于——可能收斂到局部最小值。采用SSE(Sum of Squared Error，誤差平方和)來度量聚類的效果。SSE值越小表示數(shù)據(jù)點越接近于它們的質(zhì)心，聚類效果也越好。
為了克服kMeans會收斂于局部最小值的問題，有人提出了一個稱為二分K-均值的算法。該算法偽代碼如下：

          
            將所有點看成一個簇
當(dāng)簇數(shù)目小于k時
對于每個簇
    計算總誤差
    在給定的簇上面進行K-均值聚類(k=2)
    計算將該簇一分為二之后的總誤差
選擇使得誤差最小的那個簇進行劃分操作
          
        

python代碼如下：

          
            class biKMeans(object):
    def __init__(self, n_clusters=5):
        self.n_clusters = n_clusters
        self.centroids = None
        self.clusterAssment = None
        self.labels = None
        self.sse = None
    # 計算兩點的歐式距離
    def distEclud(self, vecA, vecB):
        return np.linalg.norm(vecA - vecB)
    
    # 計算兩點的曼哈頓距離
    def distManh(self, vecA, vecB):
        return np.linalg.norm(vecA - vecB,ord = 1)
    def fit(self, X):
        m = X.shape[0]
        self.clusterAssment = np.zeros((m, 2))
        if(len(X) != 0):
            centroid0 = np.mean(X, axis=0).tolist()
        centList = [centroid0]
        for j in range(m):  # 計算每個樣本點與質(zhì)心之間初始的SE
            self.clusterAssment[j, 1] = self.distEclud(np.asarray(centroid0), X[j, :]) ** 2

        while (len(centList) < self.n_clusters):
            lowestSSE = np.inf
            for i in range(len(centList)):  # 嘗試劃分每一族,選取使得誤差最小的那個族進行劃分
                ptsInCurrCluster = X[np.nonzero(self.clusterAssment[:, 0] == i)[0], :]
                clf = kMeans(n_clusters=2)
                clf.fit(ptsInCurrCluster)
                centroidMat, splitClustAss = clf.centroids, clf.clusterAssment  # 劃分該族后，所得到的質(zhì)心、分配結(jié)果及誤差矩陣
                sseSplit = sum(splitClustAss[:, 1])
                sseNotSplit = sum(self.clusterAssment[np.nonzero(self.clusterAssment[:, 0] != i)[0], 1])
                if (sseSplit + sseNotSplit) < lowestSSE:
                    bestCentToSplit = i
                    bestNewCents = centroidMat
                    bestClustAss = splitClustAss.copy()
                    lowestSSE = sseSplit + sseNotSplit
            # 該族被劃分成兩個子族后,其中一個子族的索引變?yōu)樵宓乃饕硪粋€子族的索引變?yōu)閘en(centList),然后存入centList
            bestClustAss[np.nonzero(bestClustAss[:, 0] == 1)[0], 0] = len(centList)
            bestClustAss[np.nonzero(bestClustAss[:, 0] == 0)[0], 0] = bestCentToSplit
            centList[bestCentToSplit] = bestNewCents[0, :].tolist()
            centList.append(bestNewCents[1, :].tolist())
            self.clusterAssment[np.nonzero(self.clusterAssment[:, 0] == bestCentToSplit)[0], :] = bestClustAss
        self.labels = self.clusterAssment[:, 0]
        self.sse = sum(self.clusterAssment[:, 1])
        self.centroids = np.asarray(centList)
          
        

上述函數(shù)運行多次聚類會收斂到全局最小值，而原始的kMeans()函數(shù)偶爾會陷入局部最小值。

算法實戰(zhàn)

對mnist數(shù)據(jù)集進行聚類

從網(wǎng)上找的數(shù)據(jù)集 data.pkl 。該數(shù)據(jù)集是mnist中選取的1000張圖，用t_sne降維到了二維。

讀取文件的代碼如下：

          
            dataSet, dataLabel = pickle.load(open('data.pkl', 'rb'), encoding='latin1')
    print(type(dataSet))
    print(dataSet.shape)
    print(dataSet)
    print(type(dataLabel))
    print(dataLabel.shape)
    print(dataLabel)
          
        

打印出來結(jié)果如下：

          
            
              
(1000, 2)
[[ -0.48183008 -22.66856528]
 [ 11.5207274   10.62315075]
 [  4.76092787   5.20842437]
 ...
 [ -8.43837464   2.63939773]
 [ 20.28416829   1.93584107]
 [-21.19202119  -4.47293397]]

              
                
(1000,)
[0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0  9 5 5 6 5 0
 9 8 9 8 4 1 7 7 3 5 1 0 0 2 2 7 8 2 0 1 2 6 3 3 7 3 3 4 6 6 6 ...
 3 7 3 3 4 6 6 6 4 9 1 5 0 9 5 2 8 2 0 0 1 7 6 3 2 1 4 6 3 1 3 9 1 7 6 8 4 3]
              
            
          
        

開始使用之前編寫的算法聚類，并多次運行保存sse最小的一次所得到的圖。

          
            def main():
    dataSet, dataLabel = pickle.load(open('data.pkl', 'rb'), encoding='latin1')
    k = 10
    clf = biKMeans(k)
    lowestsse = np.inf
    for i in range(10):
        print(i)
        clf.fit(dataSet)
        cents = clf.centroids
        labels = clf.labels
        sse = clf.sse
        visualization(k, dataSet, dataLabel, cents, labels, sse, lowestsse)
        if(sse < lowestsse):
            lowestsse = sse
if __name__ == '__main__':
    main()
          
        

小結(jié)

聚類是一種無監(jiān)督的學(xué)習(xí)方法。所謂無監(jiān)督學(xué)習(xí)是指事先并不知道要尋找的內(nèi)容，即沒有目標變量。聚類將數(shù)據(jù)點歸到多個簇中，其中相似數(shù)據(jù)點處于同一簇，而不相似數(shù)據(jù)點處于不同簇中。聚類中可以使用多種不同的方法來計算相似度(比如本文是使用距離度量)

K-均值算法是最為廣泛使用聚類算法，其中的k是指用戶指定要創(chuàng)建的簇的數(shù)目。K-均值聚類算法以k個隨機質(zhì)心開始。算法會計算每個點到質(zhì)心的距離。每個點會被分配到距其最近的簇質(zhì)心，然后緊接著基于新分配到簇的點更新簇質(zhì)心。以上過程重復(fù)數(shù)次，直到簇質(zhì)心不再改變。這種方法易于實現(xiàn)，但容易受到初始簇質(zhì)心的影響，并且收斂到局部最優(yōu)解而不是全局最優(yōu)解。

還有一種二分K-均值的算法，可以得到更好的聚類效果。首先將所有點作為一個簇，然后使用K-均值算法(k=2)對其劃分。下一次迭代時，選擇有最大誤差的簇進行劃分。該過程重復(fù)直到k個簇創(chuàng)建成功為止。

附錄

文中代碼及數(shù)據(jù)集：https://github.com/Professorchen/Machine-Learning/tree/master/kMeans