[[279087]]

MLK，即Machine Learning Knowledge，本專欄在于對(duì)機(jī)器學(xué)習(xí)的重點(diǎn)知識(shí)做一次梳理，便于日后溫習(xí)，內(nèi)容主要來(lái)自于《百面機(jī)器學(xué)習(xí)》一書，結(jié)合自己的經(jīng)驗(yàn)與思考做的一些總結(jié)與歸納。本次主要講解的內(nèi)容是機(jī)器學(xué)習(xí)里的非監(jiān)督學(xué)習(xí)經(jīng)典原理與算法，非監(jiān)督，也就是沒(méi)有target(標(biāo)簽)的算法模型。

Index

• K-Mean聚類算法
• 高斯混合模型
• 自組織映射神經(jīng)網(wǎng)絡(luò)
• 聚類算法的評(píng)估指標(biāo)
• 常見(jiàn)聚類算法對(duì)比
• 常見(jiàn)聚類算法的Python實(shí)現(xiàn)

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

K-Mean聚類算法

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

 

其中Xi代表第i個(gè)樣本，Ci是Xi所屬的簇，μci代表簇對(duì)應(yīng)的中心點(diǎn)，M是樣本總數(shù)。

首先先來(lái)看一下K-Mean算法的具體步驟描述：

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

2)隨機(jī)抽取K個(gè)簇(K由人工設(shè)定);

3)定義Cost Function：

 

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

• 對(duì)于每個(gè)樣本Xi，將其分配到距離最近的簇：

 

• 對(duì)于每個(gè)簇，重新計(jì)算簇中心：

 

K-Mean的優(yōu)點(diǎn)

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

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

K-Mean的缺點(diǎn)

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

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

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

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

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

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

2)合理選擇K值。

K值并不是拍腦袋拍出來(lái)的，需要用科學(xué)的辦法去確定。一般可以通過(guò)多次試驗(yàn)結(jié)果決定，如采用手肘法：

 

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

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

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

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

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

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

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

再說(shuō)說(shuō)兩種算法

1)K-Mean++算法

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

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

2)ISODATA算法

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

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

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

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

高斯混合模型

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

 

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

 

它是一個(gè)生成式模型，并且通過(guò)EM算法框架來(lái)求解，具體的迭代過(guò)程如下：

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

1)E步驟：根據(jù)當(dāng)前的參數(shù)，計(jì)算每個(gè)點(diǎn)由某個(gè)分模型生成的概率。

2)M步驟：使用E步驟估計(jì)出來(lái)的概率，來(lái)改進(jìn)每個(gè)分模型的均值、方差和權(quán)重。

高斯混合模型與K-Mean算法的相同點(diǎn)：

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

2)都是使用EM算法來(lái)求解;

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

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

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

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

等。

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

別模型有：線性回歸、決策樹(shù)、支持向量機(jī)SVM、k近鄰、神經(jīng)網(wǎng)絡(luò)等。

自組織映射神經(jīng)網(wǎng)絡(luò)

自組織映射神經(jīng)網(wǎng)絡(luò)(Self-Organizing Map，SOM)是無(wú)監(jiān)督學(xué)習(xí)方法中的一類重要方法，可以用于聚類、高維可視化、數(shù)據(jù)壓縮、特征提取等等用途，因?yàn)樘岢稣呤荰euvo Kohonen教授，因此也被稱為Kohonen網(wǎng)絡(luò)。

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

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

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

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

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

SOM本質(zhì)上是一個(gè)兩層神經(jīng)網(wǎng)絡(luò)，包含輸入層和輸出層。輸入層模擬感知外界輸入信息，輸出層模擬做出響應(yīng)的大腦皮層。

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

2)訓(xùn)練時(shí)采用"競(jìng)爭(zhēng)學(xué)習(xí)"的方式，每個(gè)輸入的樣本，都會(huì)在輸出層中找到與之最為匹配的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)被稱之為"激活節(jié)點(diǎn)"(winning neuron);

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

4)上面說(shuō)到的"競(jìng)爭(zhēng)學(xué)習(xí)"，可以通過(guò)神經(jīng)元之間的橫向抑制連接(負(fù)反饋路徑)來(lái)實(shí)現(xiàn)。

一般，SOM模型的常見(jiàn)網(wǎng)絡(luò)結(jié)構(gòu)有兩種，分別是一維和二維的：

 

SOM的自組織學(xué)習(xí)過(guò)程，可以歸納為下面幾個(gè)子過(guò)程：

1)初始化：所有連接權(quán)重都用小的隨機(jī)值進(jìn)行初始化。

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

 

3)合作：獲勝的神經(jīng)元決定了興奮神經(jīng)元拓?fù)溧徲虻目臻g位置，確定了激活節(jié)點(diǎn)后，更新臨近的節(jié)點(diǎn)。

4)適應(yīng)：適當(dāng)調(diào)整相關(guān)興奮神經(jīng)元的連接權(quán)重，使得獲勝神經(jīng)元對(duì)相似輸入模式的后續(xù)應(yīng)用的響應(yīng)增強(qiáng)。

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

等到最后迭代結(jié)束之后，每個(gè)樣本所激活的神經(jīng)元就是它對(duì)應(yīng)的類別。

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

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

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

3)SOM的可視化很好，有優(yōu)雅的拓?fù)潢P(guān)系圖。

如何訓(xùn)練參數(shù)

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

2)設(shè)計(jì)輸出節(jié)點(diǎn)的排列：對(duì)于不同的問(wèn)題，事先選擇好模式。

3)初始化權(quán)值。

4)設(shè)計(jì)拓?fù)溧徲颍和負(fù)溧徲虻脑O(shè)計(jì)原則是使得鄰域不斷縮小，從而輸出平面上相鄰神經(jīng)元對(duì)應(yīng)的權(quán)向量既有區(qū)別又有相當(dāng)?shù)南嗨贫?，從而保證獲勝節(jié)點(diǎn)對(duì)某一類模式產(chǎn)生最大響應(yīng)時(shí)，其鄰域節(jié)點(diǎn)也產(chǎn)生較大響應(yīng)。

5)設(shè)計(jì)學(xué)習(xí)率：學(xué)習(xí)率是一個(gè)遞減函數(shù)，可以結(jié)合拓?fù)溧徲蛞黄鹂紤]。在訓(xùn)練開(kāi)始時(shí)，可以選擇較大的值，這樣子比較快下降，后面慢慢減少。

聚類算法的評(píng)估指標(biāo)

聚類算法不像有監(jiān)督學(xué)習(xí)有一個(gè)target，更多的都是沒(méi)有目標(biāo)的，所以評(píng)估指標(biāo)也是不一樣的，下面介紹幾種常用的評(píng)估指標(biāo)：

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

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

定義

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

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

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

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

2)Calinski-Harabaz指數(shù)

如果標(biāo)簽是未知的，sklearn.metrics.calinski_harabaz_score則可以使用Calinski-Harabaz指數(shù)來(lái)評(píng)估模型，其中較高的Calinski-Harabaz分?jǐn)?shù)與具有更好定義的聚類的模型相關(guān)。

優(yōu)點(diǎn):

• 當(dāng)集群密集且分離好時(shí)，分?jǐn)?shù)更高，這與集群的標(biāo)準(zhǔn)概念有關(guān)。
• 得分快速計(jì)算

缺點(diǎn):

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

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

該指標(biāo)是衡量?jī)蓚€(gè)賦值相似度的函數(shù)，忽略排列組合

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

4)Mutual Information based scores(基于相互信息的分?jǐn)?shù))

鑒于labels_true相同樣本的基本真實(shí)類分配和我們的聚類算法分配的知識(shí)labels_pred， 互信息是衡量?jī)蓚€(gè)分配的一致性的函數(shù)，忽略排列。這種措施的兩個(gè)不同的標(biāo)準(zhǔn)化版本是可用的，歸一化互信息(NMI)和調(diào)整的相互信息(AMI)。文獻(xiàn)中經(jīng)常使用NMI，而最近提出了AMI，并針對(duì)機(jī)會(huì)進(jìn)行歸一化：

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

常見(jiàn)聚類算法對(duì)比

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

 

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

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

1)K-Means聚類

 

2)分層聚類(Hierarchical clustering)

 

3)t-SNE聚類

 

4)DBSCAN聚類

5)MiniBatchKMeans

 

6)Affinity Propagation(近鄰傳播)

 

Reference

《百面機(jī)器學(xué)習(xí)》——chapter5