[[279087]]

MLK，即Machine Learning Knowledge，本專欄在于對機器學習的重點知識做一次梳理，便于日后溫習，內容主要來自于《百面機器學習》一書，結合自己的經驗與思考做的一些總結與歸納。本次主要講解的內容是機器學習里的非監(jiān)督學習經典原理與算法，非監(jiān)督，也就是沒有target(標簽)的算法模型。

Index

• K-Mean聚類算法
• 高斯混合模型
• 自組織映射神經網絡
• 聚類算法的評估指標
• 常見聚類算法對比
• 常見聚類算法的Python實現(xiàn)

在機器學習中存在一種問題，那就是模型是沒有target的，給機器輸入大量的特征數(shù)據(jù)，期望機器可以學習出當中的共性或者結構又或者是關聯(lián)，并不需要像監(jiān)督學習那樣輸出某個預測值。

K-Mean聚類算法

K-Mean的基本思想就是通過迭代的方式尋找K個簇(Cluster)的一種劃分方案，使得聚類結果對應的Cost Function最小，一般K-Mean的Cost Function為各個樣本距離所屬簇中心點的誤差平方和，公式為：

 

其中Xi代表第i個樣本，Ci是Xi所屬的簇，μci代表簇對應的中心點，M是樣本總數(shù)。

首先先來看一下K-Mean算法的具體步驟描述：

1)數(shù)據(jù)預處理，如歸一化、異常值處理;

2)隨機抽取K個簇(K由人工設定);

3)定義Cost Function：

 

4)不斷迭代下面👇步驟，直到CF收斂：

• 對于每個樣本Xi，將其分配到距離最近的簇：

 

• 對于每個簇，重新計算簇中心：

 

K-Mean的優(yōu)點

1)對于大數(shù)據(jù)集，算法還是相對高效的，計算復雜度為O(NKt)，其中N為樣本數(shù)，K為聚類數(shù)，t為迭代的論數(shù);

2)一般情況下都可以滿足聚類的需求。

K-Mean的缺點

1)需要人工確定K值，人工對大數(shù)據(jù)的K值預判有的時候不太好;

2)K-Mean很容易局部最優(yōu)，所以效果很受一開始的初始值影響;

3)容易受到異常值，噪點的影響。

K-Mean調優(yōu)思路

1)數(shù)據(jù)歸一化和異常值處理。

因為K-Mean本質上是基于歐式距離度量的數(shù)據(jù)聚類方法，所以少量的極端值會影響聚類效果的，而且不同量綱的數(shù)據(jù)也會有不一樣的影響，所以需要做一下預處理。

2)合理選擇K值。

K值并不是拍腦袋拍出來的，需要用科學的辦法去確定。一般可以通過多次試驗結果決定，如采用手肘法：

 

其中，橫軸為K的取值，縱軸為誤差平方和所定義的Loss Function。

可以看出，K值越大，距離和越小，我們看到當K=3的時候，曲線出現(xiàn)"拐點"，因此一般我們選擇這個點作為我們的K值。

此外，這里還介紹一個GS(Gap Statistic)方法，可參考：

https://blog.csdn.net/baidu_1...

3)采用核函數(shù)。

傳統(tǒng)的歐式距離度量方式使得K-Mean算法本質上是假設各個簇的數(shù)據(jù)具有一樣的先驗概率，并呈現(xiàn)球形或者高維球形分布，但這種分布在現(xiàn)實中不太常見，這個時候我們引入一個核K-Mean算法，主要面對非凸的數(shù)據(jù)分布。

這類核聚類方法主要是通過一個非線性映射，將輸入控件中的數(shù)據(jù)點映射到高位的特征空間中，并在新的特征空間中進行聚類，非線性映射增加了數(shù)據(jù)點線性可分的概率，從而達到更高精度的聚類結果。

再說說兩種算法

1)K-Mean++算法

這個從名字上看，就是K-Mean的改良版，主要是在初始值的選取上作了改進。原先的K-Mean是隨機選擇初始值，而K-Mean++算法則是：

• 第1個聚類中心也是隨機;
• 接下來的聚類中心，也就是第2個，按照距離當前聚類中心越遠越好;
• 按照上述思想，選擇了k個初始的聚類中心;
• 初始值選取完畢后，后續(xù)的流程和K-Mean是一樣的。

2)ISODATA算法

當K值的大小不確定的時候，可以使用ISODATA算法，全稱叫迭代自組織數(shù)據(jù)分析法。ISODATA算法在K-Mean算法的基礎上增加了兩個操作：

• 分裂操作，對應著增加聚類中心數(shù)
• 合并操作，對應著減少聚類中心數(shù)

ISODATA的應用也是比較復雜的，需要填比較多的參數(shù)：

• 預期的聚類中心數(shù)據(jù)K0：在ISODATA運行過程中聚類中心數(shù)可以自動變化，這里的K0只是一個參考值;
• 每個類所要求的的最少樣本數(shù)Nmin：如果分裂后會導致某個子類別所包含的樣本數(shù)量少于該閾值，會拒絕本次分裂操作;
• 最大方差Sigma：用于控制某個類別中樣本的分散程度，當樣本的分散程度超過某個閾值時，且分裂后滿足第一條要求，則進行分裂操作;
• 兩個聚類中心之間所允許的最小距離Dmin：如果兩個簇靠得很近，就會被進行合并操作。

高斯混合模型

高斯模型，對應著高斯分布，高斯分布也就是我們平時常說的正態(tài)分布，高斯混合模型(Gaussian Mixed Model，GMM)也是一種聚類算法，和K-Mean算法類似，都是用了EM算法進行迭代計算。高斯混合模型是假設每個簇的數(shù)據(jù)都符合正態(tài)分布，當前數(shù)據(jù)呈現(xiàn)的分布則是每個正態(tài)分布的混合結果。

 

高斯混合模型的核心思想，每個單獨的分模型都是標準高斯分布模型，其均值和方差都是待估計的參數(shù)，還有一個參數(shù)π，可以理解為權重(or 生成數(shù)據(jù)的概率)，其公式為：

 

它是一個生成式模型，并且通過EM算法框架來求解，具體的迭代過程如下：

首先，初始隨機選擇各個參數(shù)的值(總共3個參數(shù)，均值、方差和權重)，然后迭代下面兩步，直到收斂：

1)E步驟：根據(jù)當前的參數(shù)，計算每個點由某個分模型生成的概率。

2)M步驟：使用E步驟估計出來的概率，來改進每個分模型的均值、方差和權重。

高斯混合模型與K-Mean算法的相同點：

1)他們都是用于聚類的算法，都需要指定K值;

2)都是使用EM算法來求解;

3)往往都是得到局部最優(yōu)。

而它相比于K-Mean算法的優(yōu)點，就是它還可以用于概率密度的估計，而且可以用于生成新的樣本點。

生成式模型(Generative Model)：對聯(lián)合分布概率p(x,y)進行建模，常見生成式

模型有：隱馬爾可夫模型HMM、樸素貝葉斯模型、高斯混合模型GMM、LDA

等。

判別式模型(Discriminative Model)：直接對條件概率p(y|x)進行建模，常見判

別模型有：線性回歸、決策樹、支持向量機SVM、k近鄰、神經網絡等。

自組織映射神經網絡

自組織映射神經網絡(Self-Organizing Map，SOM)是無監(jiān)督學習方法中的一類重要方法，可以用于聚類、高維可視化、數(shù)據(jù)壓縮、特征提取等等用途，因為提出者是Teuvo Kohonen教授，因此也被稱為Kohonen網絡。

講SOM之前，先科普一些生物學研究：

1)在人腦的感知通道上，神經元組織是有序排列的;

2)大腦皮層會對外界特定的信息在特定的區(qū)域產生興奮;

3)在生物神經系統(tǒng)中存在著一種側抑制現(xiàn)象，即一個神經細胞興奮后，會對周圍其他神經細胞產生抑制作用，這種抑制作用會使得神經細胞之間出現(xiàn)競爭，其結果是某些獲勝，某些失敗，表現(xiàn)則為獲勝細胞興奮，失敗細胞抑制。

而我們的SOM就是對以上的生物神經系統(tǒng)功能的一種人工神經網絡模型。

SOM本質上是一個兩層神經網絡，包含輸入層和輸出層。輸入層模擬感知外界輸入信息，輸出層模擬做出響應的大腦皮層。

1)輸出層中，神經元的個數(shù)就是聚類的個數(shù);

2)訓練時采用"競爭學習"的方式，每個輸入的樣本，都會在輸出層中找到與之最為匹配的節(jié)點，這個節(jié)點被稱之為"激活節(jié)點"(winning neuron);

3)緊接著采用隨機梯度下降法更新激活節(jié)點的參數(shù)，同時適當?shù)馗录せ罟?jié)點附近的節(jié)點(會根據(jù)距離遠近選擇更新的"力度");

4)上面說到的"競爭學習"，可以通過神經元之間的橫向抑制連接(負反饋路徑)來實現(xiàn)。

一般，SOM模型的常見網絡結構有兩種，分別是一維和二維的：

 

SOM的自組織學習過程，可以歸納為下面幾個子過程：

1)初始化：所有連接權重都用小的隨機值進行初始化。

2)競爭：神經元計算每一個輸入模式各自的判別函數(shù)值，并宣布具有最小判別函數(shù)值的特定神經元為勝利者，每個神經元j的判別函數(shù)為：

 

3)合作：獲勝的神經元決定了興奮神經元拓撲鄰域的空間位置，確定了激活節(jié)點后，更新臨近的節(jié)點。

4)適應：適當調整相關興奮神經元的連接權重，使得獲勝神經元對相似輸入模式的后續(xù)應用的響應增強。

5)迭代第2-4步，直到特征映射趨于穩(wěn)定。

等到最后迭代結束之后，每個樣本所激活的神經元就是它對應的類別。

SOM與K-Mean算法的區(qū)別：

1)K-Mean算法需要事先確定好K值，而SOM不需要;

2)K-Mean算法為每個輸入數(shù)據(jù)找到一個最相似的類，只更新這個類的參數(shù);而SOM則會更新臨近的節(jié)點，所以，K-Mean算法受噪聲影響比較大，SOM則可能準確性方面會差一些;

3)SOM的可視化很好，有優(yōu)雅的拓撲關系圖。

如何訓練參數(shù)

1)設定輸出層神經元的數(shù)量：如果不清楚，可以盡可能設定較多的節(jié)點數(shù)。

2)設計輸出節(jié)點的排列：對于不同的問題，事先選擇好模式。

3)初始化權值。

4)設計拓撲鄰域：拓撲鄰域的設計原則是使得鄰域不斷縮小，從而輸出平面上相鄰神經元對應的權向量既有區(qū)別又有相當?shù)南嗨贫?，從而保證獲勝節(jié)點對某一類模式產生最大響應時，其鄰域節(jié)點也產生較大響應。

5)設計學習率：學習率是一個遞減函數(shù)，可以結合拓撲鄰域一起考慮。在訓練開始時，可以選擇較大的值，這樣子比較快下降，后面慢慢減少。

聚類算法的評估指標

聚類算法不像有監(jiān)督學習有一個target，更多的都是沒有目標的，所以評估指標也是不一樣的，下面介紹幾種常用的評估指標：

1)輪廓系數(shù)(Silhouette Coefficient)

silhouette 是一個衡量一個結點與它屬聚類相較于其它聚類的相似程度，取值范圍-1到1，值越大表明這個結點更匹配其屬聚類而不與相鄰的聚類匹配。如果大多數(shù)結點都有很高的silhouette value，那么聚類適當。若許多點都有低或者負的值，說明分類過多或者過少。

定義

輪廓系數(shù)結合了凝聚度和分離度，其計算步驟如下：

對于第i個對象，計算它到所屬簇中所有其他對象的平均距離，記為ai(體現(xiàn)凝聚度)

對于第i個對象和不包含該對象的任意簇，記為bi(體現(xiàn)分離度)

第i個對象的輪廓系數(shù)為si=(bi-ai)/max(ai,bi)

2)Calinski-Harabaz指數(shù)

如果標簽是未知的，sklearn.metrics.calinski_harabaz_score則可以使用Calinski-Harabaz指數(shù)來評估模型，其中較高的Calinski-Harabaz分數(shù)與具有更好定義的聚類的模型相關。

優(yōu)點:

• 當集群密集且分離好時，分數(shù)更高，這與集群的標準概念有關。
• 得分快速計算

缺點:

• 凸群的Calinski-Harabaz指數(shù)通常高于簇的其他概念，例如通過DBSCAN獲得的基于密度的集群。

3)Adjusted Rand index(調整后蘭德指數(shù))

該指標是衡量兩個賦值相似度的函數(shù)，忽略排列組合

優(yōu)點：

• 隨機(統(tǒng)一)標簽分配 對于任何值的ARI分數(shù)接近0.0n_clusters，n_samples(對于原始的蘭德指數(shù)或V度量，情況不是這樣)。
• 有界范圍[-1,1]：負值是壞的(獨立標注)，相似的聚類具有正的ARI，1.0是完美的匹配得分。
• 對集群結構沒有作出任何假設：可以用于比較聚類算法，例如k-means，其假設各向同性斑點形狀與可以找到具有“折疊”形狀的聚類的頻譜聚類算法的結果。

缺點：

• 與慣性相反，ARI需要對地面真相類的知識，而在實踐中幾乎不可用，或者需要人工注釋者的人工分配(如在受監(jiān)督的學習環(huán)境中)。
• 然而，ARI也可以在純無人監(jiān)控的設置中用作可用于聚類模型選擇(TODO)的共識索引的構建塊。

4)Mutual Information based scores(基于相互信息的分數(shù))

鑒于labels_true相同樣本的基本真實類分配和我們的聚類算法分配的知識labels_pred， 互信息是衡量兩個分配的一致性的函數(shù)，忽略排列。這種措施的兩個不同的標準化版本是可用的，歸一化互信息(NMI)和調整的相互信息(AMI)。文獻中經常使用NMI，而最近提出了AMI，并針對機會進行歸一化：

優(yōu)點：

• 隨機的(均勻的)標簽指定具有AMI得分接近0.0 為任何值n_clusters和n_samples(其不是生互信息或V-措施例如的情況下)。
• 有界范圍[0，1]：接近零的值表示兩個主要獨立的標簽分配，而接近1的值表示重要的一致性。此外，恰好為0的值表示純獨立的標簽分配，并且恰好為1的AMI表示兩個標簽分配是相等的(有或沒有排列)。
• 對集群結構沒有作出任何假設：可以用于比較聚類算法，例如k-means，其假設各向同性斑點形狀與可以找到具有“折疊”形狀的聚類的頻譜聚類算法的結果。

缺點：

• 與慣性相反，基于MI的措施需要了解地面真相類，而在實踐中幾乎不可用，或需要人為注釋者的人工分配(如在受監(jiān)督的學習環(huán)境中)。 然而，基于MI的措施也可用于純粹無監(jiān)督的設置，作為可用于聚類模型選擇的共識索引的構建塊。

常見聚類算法對比

下面一張圖介紹幾種Scikit learn的常用聚類算法的比較：

 

常見聚類算法的Python實現(xiàn)

上面說了這么多聚類算法，還是在最后面，把算法的Python實現(xiàn)代碼給大家貼一下：

1)K-Means聚類

 

2)分層聚類(Hierarchical clustering)

 

3)t-SNE聚類

 

4)DBSCAN聚類

5)MiniBatchKMeans

 

6)Affinity Propagation(近鄰傳播)

 

Reference

《百面機器學習》——chapter5