一惨险、基本原理

聚類(clustering)是一種無(wú)監(jiān)督學(xué)習(xí)(unsupervised learning)倍宾，即沒有標(biāo)記信息消约，通過對(duì)無(wú)標(biāo)記訓(xùn)練樣本的學(xué)習(xí)發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在性質(zhì)和規(guī)律趋惨。
對(duì)于樣本集，聚類算法需要將樣本劃分為個(gè)互不相交的簇. 算法針對(duì)聚類所得簇最小化平方誤差： 其中為簇均值向量酷宵。E在一定程度上刻畫了簇內(nèi)樣本圍繞簇均值向量的緊密程度捞挥，E越小相似度越高。
簡(jiǎn)單來說忧吟，算法主要分為兩個(gè)步驟：
第一步：簇分配砌函，隨機(jī)選個(gè)點(diǎn)作為中心，計(jì)算到這個(gè)點(diǎn)的距離溜族，分為個(gè)簇讹俊。
第二步：移動(dòng)聚類中心：重新計(jì)算每個(gè)簇的中心，移動(dòng)中心煌抒，重復(fù)以上步驟仍劈。

k-means算法

二、算法實(shí)現(xiàn)

算法過程比較簡(jiǎn)單明晰寡壮，以下為其實(shí)現(xiàn)過程：

1. 所需要的庫(kù)

import numpy as np
import scipy.io as spio
import imageio
import matplotlib.pyplot as plt

2. 主體過程贩疙，返回聚類中心的位置和各點(diǎn)的歸屬

def KMeans(X,init_centroids,max_iters,plot_process):
    m,n = X.shape
    K = init_centroids.shape[0]
    centriods = init_centroids
    pre_centroids = centriods
    
    for i in range(max_iters):
        if plot_process:
            ax = plotProcess(X,centriods,pre_centroids)
            pre_centroids = centriods
        idx = calcDistance(X,centriods)
        centriods = calcCentroids(X,idx,K)
    if plot_process:
        ax.show()
    return centriods,idx

3. 計(jì)算各點(diǎn)到聚類中心的位置，并據(jù)此將其分屬不同類

def calcDistance(X,init_centroids):
    m = X.shape[0]
    K = init_centroids.shape[0]
    dis = np.zeros((m,K))
    idx = np.zeros((m,1))
    
    for i in range(m):
        for j in range(K):
            dis[i,j] = np.dot((X[i,:]-init_centroids[j,:]).reshape(1,-1),(X[i,:]-init_centroids[j,:]).reshape(-1,1))
    
    dummy, idx = np.where(dis==np.min(dis,axis=1).reshape(-1,1))
    return idx[0:m]

4. 計(jì)算聚類中心况既，即均值向量

def calcCentroids(X,idx,K):
    n = X.shape[1]
    centroids = np.zeros((K,n))
    for i in range(K):
        centroids[i,:] = np.mean(X[np.ravel(idx==i),:],axis=0).reshape(1,-1)
        
    return centroids

5. 輔助函數(shù)这溅，繪圖及初始化聚類中心位置

def plotProcess(X,centriods,pre_centroids):
    plt.scatter(X[:,0],X[:,1])
    plt.plot(pre_centroids[:,0],pre_centroids[:,1],'r*',markersize=10,linewidth=5)
    plt.plot(centriods[:,0],centriods[:,1],'r*',markersize=10,linewidth=5)
    for j in range(centriods.shape[0]):
        p1 = centriods[j,:]
        p2 = pre_centroids[j,:]
        plt.plot([p1[0],p2[0]],[p1[1],p2[1]],'->',linewidth=2)
    return plt

def initCentroids(X,K):
    m = X.shape[0]
    m_arr = np.arange(0,m)
    centroids = np.zeros((K,X.shape[1]))
    np.random.shuffle(m_arr)
    rand_indices = m_arr[:K]
    centroids = X[rand_indices,:]
    return centroids

6. 主函數(shù)

def main():
    data = spio.loadmat('data.mat')
    X = data['X']
    K = 3 
   # init_centroids = np.array([[3,3],[0,2],[7,5]])
    init_centroids = initCentroids(X,K)
    max_iters = 10
    KMeans(X,init_centroids,max_iters,True)
if __name__=='__main__':
    main()

下圖為聚類的結(jié)果，形象展示了聚類中心及其移動(dòng)過程棒仍。

聚類中心及其移動(dòng)過程

聚類算法可用于圖片的壓縮悲靴，將圖片的像素分為若干類，然后用這個(gè)類代替原來的像素值莫其，以下為其實(shí)現(xiàn)過程及結(jié)果：

def imageCompression():
    img_data = imageio.imread('bird.png')
    img_data = img_data/255.0
    img_size =img_data.shape
    X = img_data.reshape(img_size[0]*img_size[1],3)
    
    K = 10
    max_iters = 10
    init_centroids = initCentroids(X,K)
    centroids,idx = KMeans(X,init_centroids,max_iters,False)
    idx = calcDistance(X,centroids)
    X_recovered = centroids[idx,:]
    X_recovered = X_recovered.reshape(img_size[0],img_size[1],3)
    
    plt.subplot(1,2,1)
    plt.imshow(img_data)
    plt.subplot(1,2,2)
    plt.imshow(X_recovered)
    plt.show()
    
if __name__=='__main__':
    imageCompression()    

原圖及壓縮后的結(jié)果

另外可以通過mglearn庫(kù)展示聚類過程和分類邊界癞尚。

import mglearn

mglearn.plots.plot_kmeans_algorithm()
mglearn.plots.plot_kmeans_boundaries()

聚類過程及分類邊界

三、問題探討

3.1乱陡、性能度量

聚類性能度量大致有兩類：一類是外部指標(biāo)浇揩，就是將聚類結(jié)果與某個(gè)“參考模型”比較；另一類是內(nèi)部指標(biāo)憨颠，即直接考察聚類結(jié)果而不利用任何參考模型胳徽。
外部指標(biāo)：

• Jaccard系數(shù)（Jaccard Coefficient, JC）
  
• FM指數(shù)（Fowlkes and Mallows Index, FMI）
  
• Rand指數(shù)（Rand Index, RI）
  
  上述指標(biāo)的結(jié)果值均在[0,1]之間，值越大越好。
  其中
  
  
  
  
  表示參考模型膜廊。

內(nèi)部指標(biāo)：

• DB指數(shù)（Davies-Bouldin Index, DBI）
  
• Dunn指數(shù)（Dunn Index, DI）
  
  DBI的值越小越好，DI值越大越好淫茵。
  其中
  
  
  
  

3.2爪瓜、距離度量

距離度量是機(jī)器學(xué)習(xí)中一個(gè)非常常用的概念，反映了兩點(diǎn)之間的相似程度匙瘪，具有非負(fù)性铆铆、同一性、對(duì)稱性和三角不等式性質(zhì)丹喻。最常用的表示方法是閔可夫斯基距離(Minkowski distance)

當(dāng)時(shí)薄货，即歐氏距離(Euclidean distance)

當(dāng)時(shí)，即曼哈頓距離(Manhattan distance)

另外碍论，聚類算法還包括密度聚類（如DBSCAN）谅猾、層次聚類（如AGNES）等，在此不予詳述鳍悠。

參考資料

[1] https://github.com/lawlite19/MachineLearning_Python
[2] 周志華 著. 機(jī)器學(xué)習(xí). 北京:清華大學(xué)出版社,2016
[3] 李航 著. 統(tǒng)計(jì)學(xué)習(xí)方法. 北京:清華大學(xué)出版社,2012
[4] 史春奇等 著. 機(jī)器學(xué)習(xí)算法背后的理論與優(yōu)化. 北京:清華大學(xué)出版社,2019
[5] Peter Harrington 著. 李銳等 譯. 機(jī)器學(xué)習(xí)實(shí)戰(zhàn). 北京:人民郵電出版社,2013

人生如逆旅税娜，我亦是行人 ——蘇軾《臨江仙·送錢穆父》