寫在前面

當前是人工智能的時代磕昼，各種機器學習的算法層出不窮服傍，各種各樣的AI不但在自我快速迭代發(fā)展钱雷，也在深刻地影響和改變著人們的生活。最近筆者在上一門機器學習的研究生課程吹零，在完成課程presentation的過程中閱讀了一篇文章罩抗，覺得文中的算法十分有趣，花了三天時間用python做了簡單實現(xiàn)灿椅，現(xiàn)在把其中的一些有意思的點寫在這里與各位讀者分享套蒂。先給出這篇文章的地址Sc3-consensus clustering of single-cell RNA-Seq data

聚類的簡要介紹

聚類算法是一類“無監(jiān)督學習”方法，即訓練樣本中本身不帶有標記信息茫蛹，通過模型的訓練來揭示數(shù)據(jù)內(nèi)部的規(guī)律和性質(zhì)泣懊。聚類試圖將數(shù)據(jù)集中的樣本劃分為若干個通常是不想交的子集，每個子集稱為一個“簇”（cluster）麻惶，通過這種劃分馍刮，每個簇可能對應于一些潛在的概念，當然這些概念對于聚類算法而言是實現(xiàn)未知的窃蹋，聚類的過程僅能自動形成簇的結(jié)構(gòu)卡啰，簇所對應的概念語義需要使用者自己來把握静稻。

本文中所涉及的聚類算法主要是K-Means算法，在后期還運用到了一些層次聚類匈辱，在這里就略去不說振湾。K-Means聚類只一種原型聚類算法，其中的K意為所要聚成的類的個數(shù)亡脸，這個數(shù)值是需要使用者給出的押搪，這也是該算法比較受爭議的一點，因為人們在得到聚類結(jié)果之前往往并不知道數(shù)據(jù)集中所包含的類的個數(shù)浅碾。

如同上文所說的大州，K-Means算法首先需要使用者傳入所要聚類的個數(shù)，記為k垂谢。接著厦画，算法會在傳入的數(shù)據(jù)集中隨機的選取k個樣本作為k個類的均值向量，隨后再遍歷所有的樣本滥朱，對于每個樣本都分別計算它們與k個均值向量的“距離”根暑，在這里“距離”可以使用歐氏距離，皮爾森相關(guān)系數(shù)等等衡量指標徙邻。在得到某一個樣本與全部k個均值向量的距離后排嫌，找出最小的距離所對應的均值向量，則該向量就歸類于這個均值向量所對應的類缰犁，將數(shù)據(jù)集中全部樣本都歸類完成后淳地，重新計算個各類的均值向量，然后再重復上述過程民鼓，直到全部k個均值向量都不再更新為止。

數(shù)據(jù)預處理

通常我們在得到數(shù)據(jù)后并不是直接進行聚類蓬抄，首先要做的是對數(shù)據(jù)進行預處理丰嘉，這是因為原始的數(shù)據(jù)集中往往會有很多數(shù)據(jù)噪聲，這些噪聲會對算法造成很大的影響嚷缭。在這里介紹一種文中會用到的預處理方法饮亏，這種方法叫做主成分分析法（Principal Component Analysis），簡稱PCA阅爽。PCA是一種非常常用的降維方法路幸，也能有效地去除數(shù)據(jù)中的噪聲。該方法的目的是要將原始數(shù)據(jù)向更低的維度進行投影變化付翁，從而達到降低數(shù)據(jù)維度的目的简肴。PCA算法在具體實施的過程中其實是在求一個優(yōu)化問題。

假設投影矩陣為W百侧，該矩陣中的元素為新坐標系的標準正交基向量砰识，即任意兩個向量的內(nèi)積為0能扒。則優(yōu)化目標可以寫成如下形式：

圖1

使用拉格朗日乘子法可得到該問題的對偶問題，并可求解此問題：

圖2

從上式的形式可以看出辫狼，所求的標準正交基向量即為原數(shù)據(jù)集協(xié)方差矩陣的特征向量初斑。若要降到的維度為d，則取前d個特征值所對應的特征向量即能夠成最終的投影矩陣膨处，最后把中心化后的數(shù)據(jù)集叉乘投影矩陣即能得到降維后的矩陣见秤。

在這里舉一個例子來說明PCA在聚類中的應用。首先我們選取一個測試用的數(shù)據(jù)集真椿，這個數(shù)據(jù)集是一個由150個4維向量構(gòu)成的鹃答，如下圖所示：

圖3

該組數(shù)據(jù)由于是四維的我們并不能直觀地表示它，因此我們使用PCA將其降成二維瀑粥，得到的數(shù)據(jù)如下圖所示：

圖4

如上圖所示挣跋，現(xiàn)在得到了150組2維的數(shù)據(jù)，我們直觀地表示一下這個數(shù)據(jù)集：

圖5

可以看到狞换，降維處理后的數(shù)據(jù)呈現(xiàn)出了非常明顯的類別特征避咆，我們可以據(jù)此確定聚類的類別數(shù)。

算法簡述

現(xiàn)在來簡要介紹一下文章開頭所提到的那篇文獻的算法修噪。這篇文獻所論述的SC3聚類算法是應用在生物信息處理上的查库，作者根據(jù)細胞的基因表達情況來對細胞進行分類，而細胞分類在之前一直是生物信息處理的一個難題黄琼。眾所周知樊销，構(gòu)成生物的基礎(chǔ)就是細胞，而細胞又是基因表達的產(chǎn)物脏款，目前的生物技術(shù)已經(jīng)能夠得到一個特定細胞的基因表達围苫，不同種類的細胞往往是不一樣的，這即是聚類算法能夠應用在這類問題上的前提撤师。

圖6

上圖顯示了該文中方法的大致流程剂府。這篇文獻所用到的數(shù)據(jù)集包含了420個細胞中20000余個基因的表達信息，全部的信息量高達八百余萬剃盾，直接進行聚類耗時過長且由于數(shù)據(jù)噪聲過大會導致效果不佳腺占。算法的第一步首先要進行基因過濾，文中將表達率低于6%和高于94%的基因都從數(shù)據(jù)集中去除痒谴，將數(shù)據(jù)集的規(guī)模減少了50%衰伯。緊接著，計算細胞與細胞之間的“距離”积蔚，為了算法的普適性意鲸，這里一共計算了三種距離，分別是歐氏距離，皮爾森相關(guān)系數(shù)與斯皮爾曼相關(guān)系數(shù)临扮，最終得到了三個420維的距離方陣论矾，筆者在算法實現(xiàn)的過程中圖方便只計算了歐氏距離和皮爾森距離兩個距離矩陣，如下圖所示：

圖7

然后杆勇，作者對三個距離矩陣使用PCA算法和拉普拉斯變化進行降維處理贪壳，在這里有一個值得關(guān)注的問題就是如何選擇降維的目標維數(shù)，作者對此進行了充分地實驗蚜退，結(jié)果如下圖所示：

圖8

可以看到三種距離矩陣均是在PCA和拉普拉斯處理后降為原向量維數(shù)的4%-7%（作者給出的數(shù)據(jù)）時ARI指數(shù)出現(xiàn)高點闰靴，這說明原向量維數(shù)的4%-7%是一個比較合適的目標維數(shù)。作者在這里對三個距離矩陣都降為420維的4%-7%钻注，即17維-30維蚂且。筆者在實現(xiàn)時由于還未搞懂拉普拉斯變化是一個什么樣的過程，因此只使用的PCA算法對兩個目標矩陣進行了降維處理幅恋，每個距離矩陣都得到了17-30維的14個降維后的矩陣杏死。

在完成了降維操作后即開始進行K-Means聚類，基于文中的信息捆交，將目標維數(shù)定為9淑翼。這樣，最終我們可以得到28個聚類結(jié)果品追，我們需要在28聚類結(jié)果中求得一個期望玄括。在這里我們使用CSPA算法，該算法最終需要得到一個共識矩陣肉瓦，即A與B同屬一類遭京，則共識矩陣相應點上置1，否則置0泞莉。對每一個聚類結(jié)果都計算出相應的共識矩陣哪雕，再將得到的所有共識矩陣相加并取平均，就得到了最終的共識矩陣鲫趁。該共識矩陣每一個元素反映了對應兩個細胞所屬同一類可能性的大小斯嚎，若兩個細胞所對應的共識矩陣元素為1，則說明在所有聚類結(jié)果中這兩個細胞均被分為一類饮寞，則我們可以據(jù)此推斷這兩個細胞屬于同一類孝扛。

最后列吼，筆者在這里給出文中作者所得到的結(jié)果幽崩，作者使用3個距離矩陣分別進行PCA和拉普拉斯降維，最后一共得到14*6個聚類矩陣寞钥，作者所得到的結(jié)果是非常好的：

圖9

該圖中紅色越深說明該區(qū)域所對應的細胞屬于一類的概率越大慌申，數(shù)據(jù)所繪制的圖形噪聲非常少，聚類的結(jié)果也十分明顯，可以說是很成功的蹄溉。筆者由于在實驗的過程中簡化了許多計算過程咨油，效果就不如原文作者的好：

圖10

可以看到，筆者結(jié)果的圖形中“毛刺”非常多柒爵，說明數(shù)據(jù)存在較大的噪聲役电，這可能是樣本量較少導致的，當然也可能是其他的原因造成的棉胀。

在得到共識矩陣后法瑟，最后一步處理便是對該共識矩陣進行一次層次聚類，最終就能得到聚類結(jié)果唁奢，模型也即訓練完成霎挟。

這就是該篇文章的大致內(nèi)容了，筆者的算法實現(xiàn)也即到此為止麻掸。當然酥夭，本來還有一些評價指標例如ARI指數(shù)等等需要計算，但在這里就略去不表脊奋。哈哈熬北，雖說最后結(jié)果有些不顯著，但是感覺這幾天的工作還是沒有白費狂魔，筆者針對此算法的源代碼已經(jīng)在github上開源蒜埋，有興趣的小伙伴可以移步去看看。

https://github.com/yhswjtuILMARE/SC3-Algorithm

2017年11月3日