基于改進(jìn)的K-Means 算法在SNP 選擇中的應(yīng)用?

陸信蓓 周從華 張付全 張 婷 蔣躍明

（1.江蘇大學(xué)計算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）（2.無錫市精神衛(wèi)生中心 無錫 214151）（3.無錫市婦幼保健院 無錫 214002）（4.無錫市第五人民醫(yī)院 無錫 214073）

1 引言

單核苷酸多態(tài)（Single nucleotide polymorphism，SNP）主要是指在基因組水平上由單個核苷酸的變異所引起的DNA 序列多態(tài)性。SNP 數(shù)據(jù)作為重要的基因變異數(shù)據(jù)，是目前生物信息學(xué)領(lǐng)域中的重要課題之一，其具有數(shù)量多、分布廣等特點(diǎn)，適合于對復(fù)雜性狀與疾病的遺傳解剖以及基于群體的基因識別等方面的研究。但SNP 數(shù)量多而存在的SNP 數(shù)據(jù)維度高的特點(diǎn)使得SNP 數(shù)據(jù)中存在較多的冗余和噪聲，這就使得從大量的SNP中選擇具有代表性的SNP 子集即選擇特征SNP 子集勢在必行。

由于SNP 數(shù)據(jù)普遍存在少樣本、高維度的問題，和SNP之間存在連鎖不平衡性使得SNP位點(diǎn)之間存在強(qiáng)相關(guān)性的特點(diǎn)，本文考慮了SNP之間的相關(guān)性，將互信息引入K-Means 算法，提出了一種新的聚類算法——K-MIM。并將其與蟻群算法結(jié)合應(yīng)用于SNP選擇中，提出一種新的SNP選擇方法。

2 相關(guān)工作

2.1 SNP選擇的研究

目前SNP 子集的選擇主要方法包括基于統(tǒng)計的關(guān)聯(lián)研究方法和基于機(jī)器學(xué)習(xí)的特征子集選擇方法。全基因組關(guān)聯(lián)研究（Genome-Wide Association Study，GWAS）通過對比患病組和健康組的SNP 位點(diǎn)，可以發(fā)現(xiàn)與疾病相關(guān)的致病基因，其關(guān)鍵在于提高統(tǒng)計檢驗(yàn)效能，降低假陽性。基于機(jī)器學(xué)習(xí)的特征子集選擇方法主要包括過濾式和包裹式兩種選擇策略。其中過濾式選擇其優(yōu)點(diǎn)在于計算量小可以處理大規(guī)模數(shù)據(jù)，但忽略了遺傳變異之間的相互作用；包裹式選擇是將評價指標(biāo)和學(xué)習(xí)器結(jié)合起來，但其缺點(diǎn)在于計算量大選擇效率較低。目前，研究學(xué)者們基于這兩種方法提出了很多改進(jìn)。文獻(xiàn)［1］提出了一種基于Relief-SVM 的SNP數(shù)據(jù)特征選擇方法，提高了SNP 選擇的分類準(zhǔn)確率。文獻(xiàn)［2］針對傳統(tǒng)的包裹式SNP選擇方法計算量大，時間復(fù)雜度高的問題，提出了基于最大相關(guān)性最小冗余度（MCMR）的信息SNP 選擇方法。文獻(xiàn)［3］提出了一種基于稀疏表示的變量選擇方法，改進(jìn)了傳統(tǒng)系數(shù)回歸模型的變量選擇能力，并將其用于SNP 選擇。文獻(xiàn)［4］采用克隆選擇算法選擇SNP 子集，能夠更快地識別標(biāo)簽SNP。文獻(xiàn)［5］提出了一種基于主變量（PV）方法的無監(jiān)督SNP 選擇方法，通過選擇稱為PV 的原始變量子集來實(shí)現(xiàn)維數(shù)減少，消除冗余的SNP。文獻(xiàn)［6］提出了基于遺傳的特征選擇算法，使特征數(shù)量大大減少。文獻(xiàn)［7］提出了基于條件互信息最大化和支持向量機(jī)特征遞歸消除融合的混合特征選擇方法，取得了較高的預(yù)測準(zhǔn)確度。

2.2 K-Means算法的研究

K-Means 算法是一種基于樣本間相似性度量的間接聚類算法，可以將數(shù)據(jù)集劃分成不同的簇。其具有簡單、快速的特點(diǎn)，是解決聚類問題的一種經(jīng)典算法，可應(yīng)用于較多的領(lǐng)域。但K-Means算法也有聚類個數(shù)難以確定、初始簇中心對聚類效果影響較大等缺陷［8］，因此，研究學(xué)者們基于原始的K-Means算法提出了較多的改進(jìn)。文獻(xiàn)［9］針對分割圖像經(jīng)常被噪聲和強(qiáng)度不均勻等影響的問題，提出了一種基于熵的K-Means（LCK）新型分割算法。文獻(xiàn)［10］針對不良初始化引起的較差的局部最佳值問題，提出了MinMax K-Means算法，該算法依據(jù)方差為簇分配權(quán)重。文獻(xiàn)［11］將遺傳算法與K-Means 算法相結(jié)合，自動確定簇的數(shù)量，并生成高質(zhì)量的初始簇中心。文獻(xiàn)［12］針對K-Means 傾向于收斂于局部最優(yōu)及依賴初始簇中心的問題，將K-Means 與改進(jìn)的CI 結(jié)合起來，提出了一種有效的混和進(jìn)化數(shù)據(jù)聚類算法。文獻(xiàn)［13］研究了基于K-Means聚類算法的猶豫模糊聚類技術(shù)，將層次聚類的結(jié)果作為初始聚類。文獻(xiàn)［14］針對海量數(shù)據(jù)的K均值問題的有效近似，將整個數(shù)據(jù)集劃分為少量子集，每個子集的特征在于其質(zhì)心和權(quán)重，再在局部表示上應(yīng)用加權(quán)版本的K-Means算法，大大減少計算的距離數(shù)量。文獻(xiàn)［15］提出一種新的判別嵌入式K-Means，將多個判別子空間的同步學(xué)習(xí)嵌入到多視圖K-Means 聚類中，構(gòu)建統(tǒng)一框架，自適應(yīng)的控制子空間之間的相互協(xié)調(diào)。

3 基于改進(jìn)的K-Means 算法的SNP選擇方法

3.1 K-Means算法原理

原始的K-Means算法，其目標(biāo)是把數(shù)據(jù)劃分為k 個簇，使得同一個簇中的樣本相似度越高，不同簇之間的樣本相似度越低。其算法思想如下，設(shè)輸入的數(shù)據(jù)集S={x1,x2,…,xn}中有n 個數(shù)據(jù)樣本，確定聚類簇數(shù)k ，從數(shù)據(jù)集S 中選擇k 個樣本作為初始均值向量即初始簇中心{c1,c2,…,cn}，計算剩余每個樣本與各均值向量的距離，將樣本劃入與之最近的一個簇中心點(diǎn)所在的簇，更新均值向量，重復(fù)以上過程，直到目標(biāo)函數(shù)收斂，或簇中心不再改變或改變很小，聚類算法停止。

其中，K-Means算法常用的距離度量為歐式距離，其定義如下：

式中，n 代表樣本的屬性數(shù)目，xi和yi分別為樣本x 和樣本y 的第i 個屬性。

K-Means算法常用的目標(biāo)函數(shù)為平方誤差，其定義如下：

3.2 改進(jìn)的K-Means算法——K-MIM

雖然K-Means算法的原理較為簡單，且收斂速度快，實(shí)現(xiàn)容易，算法的可解釋性強(qiáng)，但是其僅在簇的平均值可被定義的情況下才能使用。而由于SNPs 之間存在連鎖不平衡性而導(dǎo)致的位點(diǎn)之間具有強(qiáng)相關(guān)性的特性，使得傳統(tǒng)的K-Means算法的距離度量方式并不能挖掘出SNPs 之間的內(nèi)在聯(lián)系，忽略了SNP本身的特性。為此，本文提出了一種改進(jìn)的融合互信息的K-Means 算法——K-MIM 算法。

3.2.1 互信息

互信息（Mutual Information）是信息論中衡量兩個隨機(jī)變量之間相關(guān)性的信息度量，兩個特征之間的互信息越高，則這兩個特征之間的相關(guān)性越強(qiáng)。假定兩個特征x 和特征y，則兩個特征之間的互信息可表示為

考慮到SNP位點(diǎn)之間存在強(qiáng)相關(guān)性的特性，本文在歐式距離中引入互信息的概念，則第一輪迭代計算中，每個特征與初始簇中心的距離度量公式表示如下：

其中，‖ ‖xi-μj2表示特征xi與初始簇中心μj的歐式距離；MI(xi,μj)表示特征xi與初始簇中心 μj之間的互信息。

3.2.2 簇中心的更新

傳統(tǒng)的K-Means 在簇中心的更新時取簇中樣本的均值作為下一輪迭代中每個簇的簇中心。但在進(jìn)行SNP聚類分組時，無法計算每個SNP與均值向量的互信息，進(jìn)而無法進(jìn)行后續(xù)迭代，因此，勢必要對簇中心的更新進(jìn)行改進(jìn)。

本文在對歐式距離的實(shí)驗(yàn)中發(fā)現(xiàn)，在一個樣本點(diǎn)的集合中，每個樣本點(diǎn)與其他各點(diǎn)的距離之和和該點(diǎn)到均值點(diǎn)的距離呈近似的增函數(shù)。以樣本點(diǎn)集合dataset1 為例，dataset1 中共包含100 個隨機(jī)樣本點(diǎn)，如圖1 所示。以單個樣本點(diǎn)到其他各點(diǎn)的距離和dsum為縱坐標(biāo)，該點(diǎn)到均值點(diǎn)dxi-μ為橫坐標(biāo)建立二維平面坐標(biāo)系，如圖2 所示，dsum和dxi-μ呈現(xiàn)出近似的增函數(shù)關(guān)系。

圖1 數(shù)據(jù)集dataset1

圖2 dsum 與dxi-μ 關(guān)系圖

由此，本文將上述實(shí)驗(yàn)發(fā)現(xiàn)擴(kuò)展到K-MIM 算法中，對簇中心的更新進(jìn)行改進(jìn)。本文提出將原有的每個簇更新后的均值簇中心用一個簇中心體代替。具體改進(jìn)如下，根據(jù)式（4）在每個簇中取n 個與其他SNP 距離和最小的SNP 作為下一輪迭代的簇中心體。假設(shè)簇中心體的集合C={c1,c2,…,cn}，表示第j 個簇中心體中的第t 個SNP，則在第二輪迭代開始時，每個SNP 與簇中心體cj的距離度量公式表示如下：

3.2.3 算法K-MIM整體步驟

結(jié)合章節(jié)3.2.1 和3.2.2，則算法K-MIM 的整體步驟如算法2所示。

算法2：K-MIM算法

1）從數(shù)據(jù)集S={x1,x2,…,xm}中隨機(jī)選擇k 個特征作為初始均值向量(μ1,μ2,…,μk)

2）for i=1 to m do

3）for j=i to m do

4） 根據(jù)式（1）和式（3）計算(d(xi,yi))2與MI(xi,yi)并存于表中

5）end for

6）end for

7）for i=1 to m do

8）根據(jù)式（4）計算xi與各均值向量的距離

9）將xi劃入與之距離最小的均值向量所對應(yīng)的簇

10）end for

11）repeat

12）根據(jù)式（4）在每個簇中取n 個與其他SNP 距離和最小的SNP作為簇中心體

13）for i=1 to m do

14）根據(jù)式（5）計算xi與各簇中心體的距離

15）將xi劃入與之距離最小的簇中心體所對應(yīng)的簇

16）end for

17）until 算法達(dá)到最大迭代次數(shù)，或簇中心體不再改變或改變很小

3.3 K-MIM算法在SNP選擇中的應(yīng)用

蟻群算法是由意大利學(xué)者M(jìn)arco Dorigo提出的一種概率型算法［16］，用于尋找優(yōu)化路徑。結(jié)合K-MIM 算法和蟻群算法，本文首先利用改進(jìn)的K-MIM 算法將SNPs 進(jìn)行聚類分組，再對每個組中的SNPs 用蟻群算法篩選SNP 子集，將得到的k 個子集合并，得到的子集即為最后的信息SNP子集。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

實(shí)驗(yàn)環(huán)境：編譯工具Python3.6.0，操作系統(tǒng)Windows10，CPU/Intel（R）Core（TM）i5-3230M 雙核處理器，主頻2.6GHz，內(nèi)存8G，硬盤容量1T。

實(shí)驗(yàn)數(shù)據(jù)：本次實(shí)驗(yàn)所使用的數(shù)據(jù)由無錫市精神衛(wèi)生中心提供。數(shù)據(jù)格式為基因型SNP數(shù)據(jù)，每個樣本帶有類標(biāo)記，標(biāo)注樣本患病與否。具體描述如表1所示。

表1 數(shù)據(jù)集描述

4.2 實(shí)驗(yàn)評價指標(biāo)

1）SNP選擇的評價指標(biāo)

本文使用信息SNP 子集對非信息SNP 子集的重構(gòu)準(zhǔn)確度（ACC(I)）作為信息SNP子集的評價指標(biāo)，其定義為對所有非信息SNP位點(diǎn)預(yù)測準(zhǔn)確度的平均值。重構(gòu)度越高，信息SNP 子集對非信息SNP的預(yù)測效果越好。

2）分類效果的評價指標(biāo)

本文使用F1-measure 和預(yù)測準(zhǔn)確率（Acc）來對分類效果進(jìn)行評價。

4.3 實(shí)驗(yàn)結(jié)果及分析

1）信息SNP選擇實(shí)驗(yàn)及分析

在兩個數(shù)據(jù)集上，分別用K-Means、K-MIM 和特征加權(quán)K-Means 算法［17］對給定的聚類數(shù)目k 將SNP 分為k 組，并采用蟻群算法對每組進(jìn)行信息SNPs 進(jìn)行提取，最后采用最近均值分類算法對非信息SNP 子集中的位點(diǎn)進(jìn)行預(yù)測。實(shí)驗(yàn)結(jié)果如圖3和圖4所示。

由圖3 和圖5 可看出，K-MIM/蟻群算法所提取出的信息SNPs對非信息SNP 子集具有更高的重構(gòu)度，且當(dāng)聚類簇數(shù)為7 時，在兩個數(shù)據(jù)集上均取得較好的實(shí)驗(yàn)結(jié)果，在后續(xù)的分類實(shí)驗(yàn)中，將使用簇數(shù)為7時所篩選出的信息SNP子集進(jìn)行實(shí)驗(yàn)。

圖3 Dataset1上每種算法選出的信息SNP對非信息SNP的重構(gòu)度

圖4 Dataset2上每種算法選出的信息SNP對非信息SNP的重構(gòu)度

2）分類實(shí)驗(yàn)及分析

為進(jìn)一步驗(yàn)證所選擇的信息SNP 子集所包含的信息量，在該部分實(shí)驗(yàn)中，本文采用K-Means/蟻群算法、K-MIM/蟻群算法、特征加權(quán)K-Means/蟻群算法、ReliefF 和MCMR 算法進(jìn)行信息SNP 子集的篩選，并選擇了SVM、DT 和Xgboost作為分類模型，進(jìn)行分類實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表2所示。

由表2 可看出，K-Means/蟻群算法和特征加權(quán)K-Means/蟻群算法相比，K-MIM/蟻群算法篩選出的信息SNP 子集具有更好的分類效果。此外，與ReliefF 和MCMR 兩種信息SNP 選擇算法相比，K-MIM/蟻群算法所選擇出的信息SNP 子集在多數(shù)情況下取得了更好的分類效果。實(shí)驗(yàn)結(jié)果說明，K-MIM 算法在考慮SNP 位點(diǎn)之間的關(guān)聯(lián)性進(jìn)行聚類后，在SNP選擇中具有較大的優(yōu)勢。

表2 信息SNP子集在不同分類器下的評價結(jié)果

5 結(jié)語

本文針對SNP數(shù)據(jù)普遍存在的少樣本、高維度的問題，和不同SNP位點(diǎn)之間存在連鎖不平衡導(dǎo)致的位點(diǎn)之間具有強(qiáng)相關(guān)性的特點(diǎn)，提出了一種融合互信息的K-Means聚類算法用于SNP的選擇中，將其與蟻群算法結(jié)合使用進(jìn)行信息SNP 子集的篩選。在信息SNP 選擇實(shí)驗(yàn)和分類實(shí)驗(yàn)的結(jié)果中表明，K-MIM/蟻群算法所篩選出的信息SNP 子集對于非信息SNP 子集的重構(gòu)和分類都具有較大的優(yōu)勢。本文后續(xù)工作在于對蟻群算法進(jìn)行改進(jìn)，使篩選出的信息SNP 子集具有更高的重構(gòu)度和分類準(zhǔn)確度。