天天看點
傳回

小瓜講機器學習——聚類算法（一）K-Means算法原理Python代碼實作

K-Means聚類算法

        • 1. K-Means聚類算法
          • 1.1 聚類算法概述
          • 1.2 K-Means算法原理
            • 1.2.1 相似性度量
            • 1.2.2 K-Means算法原理
            • 1.2.3 K-Means算法過程
            • 1.2.4 K-Means存在的問題
          • 1.3 K-Means算法Python代碼實作
          • 附錄：Python源代碼
            • 文章導引清單：
            • 機器學習
            • 資料分析
            • 資料可視化

1. K-Means聚類算法

1.1 聚類算法概述

前面我們介紹的機器學習主要聚焦在分類算法，而且很重要的一個前提條件（或者說輸入）是訓練樣本都是已有類别标簽了，這些需要在已有類别标簽條件下的機器學習一般叫監督學習（Supervised Learning）。

類别标簽往往需要人工标記，那麼有沒有自動标記呢？聚類算法能夠滿足你的需求。

聚類算法僅僅依賴訓練樣本本身的特征資訊，将具有相似屬性的樣本劃分到同一集合中（不需要标記），顯然聚類算法是典型的無監督學習（Unsupervised Learning）。聚類算法可以單獨使用，也可以配合其他學習算法一同使用，典型的是通過聚類算法獲得訓練樣本的分類資訊，然後使用分類算法，建立分類模型預測目标值。

1.2 K-Means算法原理

1.2.1 相似性度量

K-Means算法是基于相似性的聚類算法，那麼首先需要定義的就是相似性該如何度量。

“距離”是一種很好的度量相似性的工具，這是顯而易見的。

例如小王月收入5000，小趙月收入4500，李總月收入100000，小王和小趙的月收入距離（Manhattan distance）=|5000-4500|<<<小王和李總的月收入距離=|100000-5000|，可以推斷小王和小趙是同階層的，小王和李總不同階層。

當然距離定義也有好幾種，在不同問題中可以選擇不同距離定義。但是距離定義都滿足

常用有：

闵可夫斯基距離（）

d ( X ( 1 ) , X ( 2 ) ) = [ ∑ i = 1 n ( x i ( 1 ) − x i ( 2 ) ) p ] 1 / p d(X^{(1)},X^{(2)})=[\sum_{i=1}^n(x_i^{(1)}-x_i^{(2)})^p]^{1/p} d(X(1),X(2))=[i=1∑n​(xi(1)​−xi(2)​)p]1/p

曼哈頓距離（）

d ( X ( 1 ) , X ( 2 ) ) = ∑ i = 1 n ∣ x i ( 1 ) − x i ( 2 ) ∣ d(X^{(1)},X^{(2)})=\sum_{i=1}^n|x_i^{(1)}-x_i^{(2)}| d(X(1),X(2))=i=1∑n​∣xi(1)​−xi(2)​∣

歐幾裡得距離

d ( X ( 1 ) , X ( 2 ) ) = [ ∑ i = 1 n ( x i ( 1 ) − x i ( 2 ) ) 2 ] 1 / 2 d(X^{(1)},X^{(2)})=[\sum_{i=1}^n(x_i^{(1)}-x_i^{(2)})^2]^{1/2} d(X(1),X(2))=[i=1∑n​(xi(1)​−xi(2)​)2]1/2

注不難發現曼哈頓距離和歐式距離都是闵可夫斯基距離的具體形式。

1.2.2 K-Means算法原理

假設訓練樣本為 T = { X ( 1 ) , X ( 2 ) , . . . , X ( m ) } T=\{X^{(1)},X^{(2)},...,X^{(m)}\} T={X(1),X(2),...,X(m)}，其中 X ( i ) = ( x 1 ( i ) , x 2 ( i ) , . . . , x l ( i ) ) X^{(i)}=(x_1^{(i)},x_2^{(i)},...,x_l^{(i)}) X(i)=(x1(i)​,x2(i)​,...,xl(i)​)。假定分類類别總共是 k k k個，為 ( z 1 , z 2 , . . . , z k ) (z_1,z_2,...,z_k) (z1​,z2​,...,zk​)，每一類的中心坐标為 { Ω 1 , Ω 2 , . . . , Ω k } \{\Omega_1,\Omega_2,...,\Omega_k\} {Ω1​,Ω2​,...,Ωk​}，其中 Ω i = ( ω 1 i , ω 2 i , . . . , ω l i ) \Omega_i=(\omega_1^i,\omega_2^i,...,\omega_l^i) Ωi​=(ω1i​,ω2i​,...,ωli​)。

定義下述示性函數

γ i j = { 1 , X ( i ) ∈ z j 0 , X ( i ) ∉ z j \gamma_{ij}= \begin{cases}1,\qquad X^{(i)}\in z_j \\0,\qquad X^{(i)}\notin z_j \end{cases} γij​={1,X(i)∈zj​0,X(i)∈/​zj​​

每一個樣本被分到某一類均可以用上述示性函數表達（此處為非模糊聚類）。

K-Means聚類算法的基本原理是求取一個聚類結果，使得每一個樣本到對應聚類中心得距離之和取到最小，即如下。

min ⁡ ∑ i = 1 m ∑ j = 1 k γ i j ∣ ∣ X ( i ) − Ω j ∣ ∣ 2 2 = min ⁡ J \min \sum_{i=1}^m\sum_{j=1}^k\gamma_{ij}||X^{(i)}-\Omega_j||_2^2=\min J mini=1∑m​j=1∑k​γij​∣∣X(i)−Ωj​∣∣22​=minJ

當 ∂ J ∂ Ω ^ j = 0 \frac{\partial J}{\partial \hat \Omega_j}=0 ∂Ω^j​∂J​=0，即可取到極小值。

∂ J ∂ Ω ^ j = − 2 ∑ i = 1 m ( X ( i ) − Ω j ) ∙ ∂ Ω j ∂ Ω ^ j ( j : X ( i ) ∈ z j ) = 0 ⇒ ∑ i = 1 m X ( i ) γ i j ( j : X ( i ) ∈ z j ) − Ω j ∑ i = 1 m γ i j ( j : X ( i ) ∈ z j ) = 0 \frac{\partial J}{\partial \hat \Omega_j}=-2\sum_{i=1}^m(X^{(i)}-\Omega_j)\bull \frac{\partial \Omega_j}{\partial \hat \Omega_j}(j:X^{(i)}\in z_j)=0\Rightarrow \sum_{i=1}^mX^{(i)}\gamma_{ij}(j:X^{(i)}\in z_j)-\Omega_j\sum_{i=1}^m\gamma_{ij}(j:X^{(i)}\in z_j)=0 ∂Ω^j​∂J​=−2i=1∑m​(X(i)−Ωj​)∙∂Ω^j​∂Ωj​​(j:X(i)∈zj​)=0⇒i=1∑m​X(i)γij​(j:X(i)∈zj​)−Ωj​i=1∑m​γij​(j:X(i)∈zj​)=0

是以 Ω j \Omega_j Ωj​的更新公式如下

Ω j = ∑ i = 1 m X ( i ) γ i j ∑ i = 1 m γ i j ( j : X ( i ) ∈ z j ) \Omega_j=\frac{\sum_{i=1}^mX^{(i)}\gamma_{ij}}{\sum_{i=1}^m\gamma_{ij}}(j:X^{(i)}\in z_j) Ωj​=∑i=1m​γij​∑i=1m​X(i)γij​​(j:X(i)∈zj​)

1.2.3 K-Means算法過程

輸入：

　　　訓練樣本為 T = { X ( 1 ) , X ( 2 ) , . . . , X ( m ) } T=\{X^{(1)},X^{(2)},...,X^{(m)}\} T={X(1),X(2),...,X(m)}，其中 X ( i ) = ( x 1 ( i ) , x 2 ( i ) , . . . , x l ( i ) ) X^{(i)}=(x_1^{(i)},x_2^{(i)},...,x_l^{(i)}) X(i)=(x1(i)​,x2(i)​,...,xl(i)​)，分類類别總共是 k k k個。

過程：

　　　1.随機標明 k k k個樣本為類别的中心，坐标為 { X ( 1 ) , . . . , X ( k ) } \{X^{(1)},...,X^{(k)}\} {X(1),...,X(k)}

　　　2.計算樣本點 X ( i ) X^{(i)} X(i)到聚類中心的距離，選擇距離最小的點作為 X ( i ) X^{(i)} X(i)聚類簇

　　　3.連續執行以下操作

　　　　①.更新中心坐标 { X ‾ ( 1 ) , . . . , X ‾ ( k ) } \{\overline X^{(1)},...,\overline X^{(k)}\} {X(1),...,X(k)}

　　　　②.計算樣本點 X ( i ) X^{(i)} X(i)到聚類中心的距離，選擇距離最小的點作為 X ( i ) X^{(i)} X(i)聚類簇

　　　　③.檢查所有樣本歸屬類别是否有更新，如果沒有則退出，否則繼續

輸出：

　　　最終的類别中心和樣本類别屬性

1.2.4 K-Means存在的問題

K-Means聚類算法簡單易于實作，但存在兩個問題①：需要人工設定聚類類别個數 k k k，有的時候 k k k沒法正确的設定，這導緻K-Means存在很大局限性，②：K-Means算法對于初始中心存在較大的敏感性，不同的初始中心很可能導緻不同的聚類結果，這是我們不想得到的結果。

對于第一個問題，人們開發了其他聚類算法，對于第二個問題，人們補充定義了初始中心的條件，變成了K-Means++算法。

K-Means++算法

K-Means++算法主要特點就是在K-Means算法的初始中心的時候加了條件，在初始中心時要盡可能保證各中心距離最遠。

初始中心：

  • 随機標明第一個類别中心
  • 計算所有樣本到已有聚類中心的最短距離 D ( i ) D(i) D(i)，并以機率選擇新的聚類中心
  • 直到所有聚類中心都標明

在第二步中，将所有的 D ( i ) D(i) D(i)相加， D = ∑ D ( i ) D=\sum D(i) D=∑D(i)，選取 ( 0 , D ] (0, D] (0,D]的随機數 r r r，顯然 D &gt; r D&gt;r D>r，按序彈出 D ( i ) D(i) D(i)，直到 r &gt; D ( i ) r&gt;D(i) r>D(i)，標明該樣本點為聚類中心（輪盤法）。

注采用機率形式取點主要為了盡可能減小噪聲點的幹擾。

1.3 K-Means算法Python代碼實作

計算樣本點 X ( i ) X^{(i)} X(i)到聚類中心的距離列陣，并找到距離最近的聚類中心。

def distance(dataloop, center):
    m = center.shape[0]
    dis = np.zeros((m,1))
    dataloop = np.array(dataloop)
    deltavector = center - dataloop
    
    for loop in range(m):
        dis[loop] = deltavector[loop].dot(deltavector[loop].T)
    return dis

def find(dis):
    return np.argmin(dis)

K-Means主要的部分如下

def kmeans(data, k, inicenter):
    m = int(data.shape[0])
    label = np.ones((m,1))*-1
    center = inicenter
    changed = True
    
    while changed:
        changed = False

        for loopi in range(m):
            dis = distance(data.iloc[loopi], center)
            index = find(dis)
            
            if label[loopi]!=index:
            # label changed
                label[loopi] = index
                changed = True

        if changed:
        # calculate new center if label changed
            for loopj in range(0,k):
                temp = data[label==loopj].mean()
                newcenter = np.array(temp)
                center[loopj] = newcenter
    return label

在K-Means算法對于初始中心位置具有很大的敏感性，不同的初始中心很有可能會得到不同的聚類結果，下圖就是采用不同的初始聚類中心得到的結果

小瓜講機器學習——聚類算法（一）K-Means算法原理Python代碼實作
小瓜講機器學習——聚類算法（一）K-Means算法原理Python代碼實作

　　　inicenter =[[-3.,4.],[4.,4.],[-4.,-4.],[4.,-4.]]　　　　　　inicenter = [[-6.,-6.],[-1.6,-6.9],[2.7,6.9],[7.3,-5.1]]

為了改善這種情況，需要在初始中心的選取上面取一定的政策。K-Mean++方法就是如此，下面采用輪盤法實作K-Means++方法

K-means++

def inicenter(data, k):
    m,n = data.shape
    loop = np.random.randint(0,m)
    center = np.zeros((k, n))
    center[0] = data.iloc[loop]

    for loopi in range(1,k):
        dis_sum = 0
        nearlist = []
        for loopj in range(m):
            dis = distance(data.iloc[loopj], center[0:loopi])
            index = find(dis)
            nearlist.append(np.float(dis[index]))
            dis_sum += np.float(dis[index])
        dis_sum = dis_sum * np.random.random()
        for loopk in range(m):
            dis_sum -= nearlist[loopk]
            if dis_sum<0:
                center[loopi] = np.copy(data.iloc[loopk])
                break

    return center

這樣的話，結果比較穩定，如下

小瓜講機器學習——聚類算法（一）K-Means算法原理Python代碼實作
附錄：Python源代碼 
def inicenter(data, k):
    m,n = data.shape
    loop = np.random.randint(0,m)
    center = np.zeros((k, n))
    center[0] = data.iloc[loop]

    for loopi in range(1,k):
        dis_sum = 0
        nearlist = []
        for loopj in range(m):
            dis = distance(data.iloc[loopj], center[0:loopi])
            index = find(dis)
            nearlist.append(np.float(dis[index]))
            dis_sum += np.float(dis[index])
        dis_sum = dis_sum * np.random.random()
        for loopk in range(m):
            dis_sum -= nearlist[loopk]
            if dis_sum<0:
                center[loopi] = np.copy(data.iloc[loopk])
                break

    return center


def distance(dataloop, center):
    m = center.shape[0]
    dis = np.zeros((m,1))
    dataloop = np.array(dataloop)
    deltavector = center - dataloop
    
    for loop in range(m):
        dis[loop] = deltavector[loop].dot(deltavector[loop].T)
    return dis

def find(dis):
    return np.argmin(dis)


def kmeans(data, k, inicenter):
    m = int(data.shape[0])
    label = np.ones((m,1))*-1
    center = inicenter
    changed = True
    
    while changed:
        changed = False

        for loopi in range(m):
            dis = distance(data.iloc[loopi], center)
            index = find(dis)
            
            if label[loopi]!=index:
            # label changed
                label[loopi] = index
                changed = True

        if changed:
        # calculate new center if label changed
            for loopj in range(0,k):
                temp = data[label==loopj].mean()
                newcenter = np.array(temp)
                center[loopj] = newcenter
    return label


if __name__=='__main__':
    data = []
    with open(r'H:\python dataanalysis\kmean\data.txt') as f:
        for loopi in f.readlines():
            line = loopi.strip().split('\t')
            temp = [float(line[0]), float(line[1])]
            data.append(temp)
    data = pd.DataFrame(data, columns=['x','y'])
    center = inicenter(data,4)
    label = kmeans(data, 4, center)
        colors = ['green', 'red', 'blue','yellow']
    for loopi in range(4):
    	plt.scatter(data[label==loopi].x, data[label==loopi].y, color='green' )
    plt.show()

資料集如下

-2.29693419524775	5.59018489409611
-1.65945644047067	1.24998175001933
-7.11109228594546	6.94390514108144
-1.60636900702686	7.53795273430285
-3.57348527642213	5.75114608400441
-7.31721716500413	6.30418091404833
-6.05051246793066	6.20192727687441
-4.17182936556511	3.74558913673918
-1.29745215195992	5.58834523124290
-1.24578025360506	2.19830681468093
-6.89670842825716	5.94232261613726
-1.20585052767569	1.22282992464194
-1.29983136229938	2.93846089472623
-4.60237045894011	1.32319973441808
-2.39803671777840	1.67992246865093
-7.00679562960949	6.76420479829105
-5.04767102161608	5.86380036083072
-1.58985132367653	3.21969636042602
-2.45454869308312	7.65155434186849
-1.28355301524968	1.24112256352036
4.07121051759479	6.25886941513957
3.67090919965106	2.78566580821488
6.35861751704302	4.54169936165600
6.56639930795944	5.89353705859680
2.30810823188065	7.23632276775059
4.42835077051762	7.71503997643811
4.11910340497630	4.83050870974662
5.52419107077885	1.97037109980075
5.96555381600651	2.04505803891340
6.28280677387653	2.80255777886616
2.93217553899005	6.88502079188564
5.75791873797572	2.77997525280072
5.58568602781689	6.69999378248171
2.13828214636241	2.70467478107493
1.83298377090864	7.50484536231059
4.48854836387500	3.44988636189366
7.71820770961257	2.37616675301846
3.38270008666293	2.75758700583222
5.09687425685844	5.31231273302647
2.56668357643796	4.31302194231911
-5.53838345055902	-6.86472384264730
-2.18419960472596	-2.44000821521265
-3.90315136193093	-5.82149470568637
-4.15193474196202	-4.30026805145651
-1.57964435319133	-6.84045889350153
-5.99912686825739	-3.78612641018854
-2.69959839622495	-6.15920100821899
-2.72389634005053	-3.42144631066252
-5.33687907117250	-3.17549847801995
-4.02524851492345	-2.76293885023403
-7.46901997305856	-4.84620881048252
-7.62234916933375	-7.41325035402147
-4.28441712893719	-6.39716121898227
-2.54582938928592	-1.60663846948831
-1.46192521039572	-6.93335386721544
-7.09065654068389	-2.21928115757317
-4.01823437389465	-4.23160295317960
-4.71426551259256	-1.02705698361180
-7.91668551349131	-7.45277129872771
-5.64014148920783	-4.90125211157188
1.74656939126409	-2.02878217594675
7.73328656598538	-3.64561407960454
1.03243956893847	-5.54333333375410
6.42437325298052	-4.40725322093063
6.72112254457403	-5.18734376373641
7.08086293754457	-7.46823315816411
1.59105091857637	-6.32058692512439
3.79847854369228	-7.13676745615384
2.81909281995458	-6.71264548202308
6.60047936157015	-6.32033232034568
4.01989679224481	-5.07913051640941
7.37453316100666	-7.65241898771981
2.27292919811997	-1.68098723059303
2.84662041565393	-1.38648967194848
2.01877286269302	-4.56395135272344
1.95247991096065	-4.57523153119987
7.08504545348063	-5.63596413125036
5.05793211155899	-1.69962307507637
4.84902141285432	-5.41527253215850
2.01468358756609	-7.22158071294349

文章導引清單：

機器學習

  1. 小瓜講機器學習——分類算法（一）logistic regression(邏輯回歸)算法原理詳解
  2. 小瓜講機器學習——分類算法（二）支援向量機（SVM）算法原理詳解
  3. 小瓜講機器學習——分類算法（三）樸素貝葉斯法（naive Bayes）
  4. 小瓜講機器學習——分類算法（四）K近鄰法算法原理及Python代碼實作
  5. 小瓜講機器學習——分類算法（五）決策樹算法原理及Python代碼實作
  6. 小瓜講機器學習——聚類算法（一）K-Means算法原理Python代碼實作
  7. 小瓜講機器學習——聚類算法（二）Mean Shift算法原理及Python代碼實作
  8. 小瓜講機器學習——聚類算法（三）DBSCAN算法原理及Python代碼實作

資料分析

  1. 小呆學資料分析——使用pandas中的merge函數進行資料集合并
  2. 小呆學資料分析——使用pandas中的concat函數進行資料集堆疊
  3. 小呆學資料分析——pandas中的階層化索引
  4. 小呆學資料分析——使用pandas的pivot進行資料重塑
  5. 小呆學資料分析——用duplicated/drop_duplicates方法進行重複項處理
  6. 小呆學資料分析——缺失值處理（一）
  7. 小呆學資料分析——異常值判定與處理（一）
  8. 小瓜講資料分析——資料清洗

資料可視化

  1. 小瓜講資料分析——資料可視化工程（matplotlib庫使用基礎篇）
  2. 小瓜講matplotlib進階篇——坐标軸設定（坐标軸居中、坐标軸箭頭、刻度設定、辨別設定）
python資料分析 Python 機器學習 k-means k-means++ 聚類
上一篇: mongodb資料庫的簡單增删改查
下一篇: 聚類算法：Mean Shift聚類算法之Mean Shift

繼續閱讀