模式識別與機器學習(三)
- 2019 年 10 月 3 日
- 筆記
最大最小距離和層次聚類演算法的一個共同特點是某個模式一旦劃分到某一類之後，在後續的演算法過程中就不再改變了，而
為解決該問題，可以採用動態聚類法:
使用動態聚類法的要點：
- 確定模式和聚類的距離測度。當採用歐式距離時，是計算此模式和該類中心的歐式距離；為能反映出類的模式分布結構，可採用馬氏距離。
- 確定評估聚類品質的準則函數。
- 確定模式劃分以及聚類合併或分裂的規則。
基本步驟：
- 建立初始聚類中心，進行初始聚類
- 計算模式和類的距離，調整模式的類別
- 計算各聚類的參數，刪除、合併或分裂一些聚類
- 從初始聚類開始，運用迭代演算法動態地改變模式的類別和聚類的中心使準則函數取得極值或設定的參數達到設計要求時停止
C-均值法
- 條件及約定
設待分類的模式特徵矢量集為：{(vec x_1, vec x_2,…,vec x_N)}，類的數目C是事先取定的。 - 演算法思想
該方法取定C個類別和選取C個初始聚類中心，按最小距離原則將各模式分配到C類中的某一類，之後不斷地計算類心和調整各模式的類別，最終使各模式到其判屬類別中心的距離平方和最小。 - 演算法原理步驟
(1) 任選C個模式特徵矢量作為初始聚類中心：
(vec z_1^{(0)}, vec z_2^{(0)},…,vec z_C^{(0)})，令(k = 0)。
(2) 將待分類的模式特徵矢量集{(vec x_i)}中的模式逐個按最小距離原則分劃給C類中的某一類，於是產生了新的聚類。
(3) 計算重新分類後的各類心
(4) 如果兩次類心重合，則停止迭代，否則轉至(2)
C均值演算法的分類結果受到取定的類別數和初始聚類中心的影響，通常結果只是局部最優的，但其方法簡單，結果尚令人滿意，故應用較多。
C均值演算法優化
類別數C的調整
- 利用先驗知識選取
- 讓類別數遞增重複進行聚類，選取(J-c)曲線曲率變化最大點所對應的類數((J)為準則函數)
初始聚類中心的選取可採用的方式
- 憑經驗選取
- 將模式隨機分為C類計算每類類心
- 按密度大小選取
- 選取相距最遠的C個特徵點
- 隨機地從N個模式中取出部分用譜系聚類法聚成C類，以各類類心作為初始類心
- 由C-1類問題得出C-1個類心，再找出最遠點
進一步的動態聚類可以採用ISODATA演算法，其基本思想是每輪迭代時，樣本重新調整類別之後，計算類內及類間有關參數，通過和門限比較確定兩類的合併或分裂，不斷地「自組織」，在滿足設計參數條件下，使模式到類心的距離平方和最小。
C均值演算法較適用於球狀或團狀分布的樣本。如果我們有類的模式分布的某些先驗知識，可以構造能反映類的模式分布情況的核函數，那麼就以和函數來代表類。如果實際中不能確定核函數或不能用簡單的函數表示核函數時，可以採用近鄰函數法。這種演算法特別適用於類的模式分布是條狀或線狀的情況
近鄰函數法
近鄰函數
對於一個樣本集中的任意兩個樣本(vec x_i)核(vec x_j)，如果(vec x_i)是(vec x_j)的第I個近鄰點，則定義(vec x_i)對(vec x_j)的近鄰係數為I，記為(d(i ,j) = I)
同理，如果(vec x_j)是(vec x_i)的第J個近鄰點，則定義(vec x_j)對(vec x_i)的近鄰係數為J，記為(d(j, i) = J)
於是，(vec x_i)核(vec x_j)之間的近鄰函數值定義為
[ alpha_{ij} = d(i,j) + d(j,i) – 2 = I + J – 2 ]
當(vec x_i)核(vec x_j)互為最近鄰時，有(alpha_{ij} = 0)
顯然，樣本間的近鄰函數值越小，說明它們彼此越近，意味著它們越相似。
如果樣本集包含N個樣本，那麼近鄰係數總是小於或等於N-1，因此，(vec x_i)核(vec x_j)之間的近鄰函數值滿足
[ alpha_{ij} leq 2N – 4 ]
連接損失
在聚類過程中，如果(vec x_i)核(vec x_j)被聚為一類，就稱(vec x_i)與(vec x_j)是互相連接的。
對於每個連接，都應定義一個指標，用以刻劃這兩個樣本是否適於連接，稱其為連接損失。
由兩個樣本的近鄰函數值(alpha_{ij})的定義可知，(alpha_{ij})越小，表明它們越相似。若把它們連接起來，損失也就越小。因此可以將近鄰函數值(alpha_{ij})作為(vec x_i)和(vec x_j)之間的連接損失。
在聚類過程中，當考慮樣本(vec x_i)時，計算它與其它各樣本間的近鄰函數值，如果
[ alpha_{ik} = min_j lfloor alpha_{ij} rfloor ]
則把(vec x_i)和(vec x_k)連接起來，並有連接損失(alpha_{ik})
若把(vec x_i)與(vec x_j)不實際連接，則不存在連接損失，即
[ alpha_{ij} triangleq 0 ]
近鄰聚類準則函數
在定義了兩樣本間的連接損失之後，還要區分出類內連接損失和類間連接損失。
設共有c類：(w(p = 1,2,…,c))，總的類內連接損失定義為:
[ L_w = sum^c_{p=1} sum_{vec x_i in w_p \ vec x_j in w_p} lfloor alpha_{ij} rfloor ]
記(w_j)類的類內最大近鄰函數值：
[ alpha_{p max} = max_{vec x_i in w_p \ vec x_j in w_p} lfloor alpha_{ij} rfloor ]
設聚類(w_p)和(w_q (p,q=1,2,3,….,c;p neq q))的樣本之間的最小近鄰函數值為(gamma_{pq})，即
[ gamma_{pq} = min_{vec x_i in w_p \ vec x_j in w_q} lfloor a_{ij} rfloor ]
設(gamma_{pk})為聚類(w_p)與其它各聚類(w_q)的最小近鄰函數值的最小值，即
[ gamma_{pk} = min_{q \ q neq p} lfloor gamma_{pq} rfloor ]
上式表明，除(w_p)類內樣本外，只有(w_k)中的某一個樣本與(w_p)中某一個樣本最近鄰，近鄰函數值為(gamma_{pk})
(w_p)類與(w_k)類的類間最小連接損失有如下四種情況
- (Beta_p = (alpha_{p max} – gamma_{pk}) + (alpha_{k max} – gamma_{pk})), 若$gamma_{pk} > alpha_{p max} and gamma_{pk} > alpha_{k max} $
該情況：類內最大近鄰函數值小於類間最小近鄰值，說明聚類是合理的，這種情況不應付出代價，(Beta_p) 可賦予負值，即損失函數為負數 - (Beta_p = alpha_{p max} – gamma_{pk})，若(gamma_{pk} leq alpha_{p max} and alpha_{pk} > alpha_{k max})
該情況下：(w_p)類的類內最大近鄰函數值大於類間最小近鄰值，說明這兩類合併應付出代價，(Beta_p)賦予一個正值，即損失為(alpha_{p max} – gamma_{pk}) - (Beta_p = alpha_{k max} – gamma_{pk})，若(gamma_{pk} > alpha_{p max} and alpha_{pk} leq alpha_{k max})
該情況下：(w_p)類的類內最大近鄰函數值大於類間最小近鄰值，說明這兩類合併也應付出代價，(Beta_p)賦予一個正值，即損失為(alpha_{k max} – gamma_{pk}) - (Beta_p = alpha_{p max} + (alpha_{k max} – gamma_{pk})), 若$gamma_{pk} leq alpha_{p max} and gamma_{pk} leq alpha_{k max} $
該情況：(w_p)和(w_k)類內的類內最大近鄰函數值都大於類間最小近鄰值，說明這兩類合併應付出的代價更大，(Beta_p)賦予連接損失為(alpha_{p max} + (alpha_{k max} – gamma_{pk}))
然後，我們可以定義總的類間損失：(L_B = sum_{p=I}^c Beta_p)。
聚類的目標是使各(gamma_{pk})儘可能地大，使各(alpha_{p max})儘可能地小，因而構造聚類的準則函數為
[ J_L = L_W + L_B Rightarrow min ]
近鄰函數法演算法步驟
(1) 對於給定的待分類樣集$x = $ { $ vec x_1, vec x_2, …, vec x_N $ }，計算距離矩陣D，D的陣元為：(D_{ij} = d(vec x_i, vec x_j) (i,j=1,2,…,N))，(d(vec x_i, vec x_j))表示樣本(vec x_i)和(vec x_j)間的距離。
(2) 利用矩陣D，計算近鄰矩陣M，其元素(M_{ij})為樣本(vec x_i)對(vec x_j)的近鄰係數
(3) 生成近鄰函數矩陣L,其陣元為(L_{ij}=M_{ij}+M_{ji}-2)，置矩陣L的主對角線上陣元(L_{ii}=2N)，如果(vec x_i)和(vec x_j)有連接，則(L_{ij})給出它們非零近鄰函數值，即連接損失
(4) 搜索矩陣L，將每個點與和它有最小近鄰函數值的點連接起來，形成初始聚類
(5) 對於(4)所形成的聚類，計算(gamma_{pk},alpha_{pw},alpha_{kw})。若(gamma_{pk})小於或等於(alpha_{pw})或(alpha_{kw})，則合併(w_k)和(w_p)，它們的樣本間建立連接關係，轉至(5)，否則結束
上述迭代過程，最終將使準則函數(J_L)達到極小值。
註：對於鏈狀的模式分布，合併後的類內最大連接損失不應重新計算，而是取(alpha_1 max, alpha_2 max, gamma_{12})的最大值
我的部落格即將同步至騰訊雲+社區，邀請大家一同入駐：https://cloud.tencent.com/developer/support-plan?invite_code=28uqs0ghrj0g0
