基于改進的K-Means 算法在SNP 選擇中的應用?

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

（1.江蘇大學計算機科學與通信工程學院 鎮江 212013）（2.無錫市精神衛生中心 無錫 214151）（3.無錫市婦幼保健院 無錫 214002）（4.無錫市第五人民醫院 無錫 214073）

1 引言

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

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

2 相關工作

2.1 SNP選擇的研究

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

2.2 K-Means算法的研究

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

3 基于改進的K-Means 算法的SNP選擇方法

3.1 K-Means算法原理

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

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

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

K-Means算法常用的目標函數為平方誤差，其定義如下：

3.2 改進的K-Means算法——K-MIM

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

3.2.1 互信息

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

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

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

3.2.2 簇中心的更新

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

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

圖1 數據集dataset1

圖2 dsum 與dxi-μ 關系圖

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

3.2.3 算法K-MIM整體步驟

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

算法2：K-MIM算法

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

2）for i=1 to m do

3）for j=i to m do

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

5）end for

6）end for

7）for i=1 to m do

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

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

10）end for

11）repeat

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

13）for i=1 to m do

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

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

16）end for

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

3.3 K-MIM算法在SNP選擇中的應用

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

4 實驗

4.1 實驗環境及數據

實驗環境：編譯工具Python3.6.0，操作系統Windows10，CPU/Intel（R）Core（TM）i5-3230M 雙核處理器，主頻2.6GHz，內存8G，硬盤容量1T。

實驗數據：本次實驗所使用的數據由無錫市精神衛生中心提供。數據格式為基因型SNP數據，每個樣本帶有類標記，標注樣本患病與否。具體描述如表1所示。

表1 數據集描述

4.2 實驗評價指標

1）SNP選擇的評價指標

本文使用信息SNP 子集對非信息SNP 子集的重構準確度（ACC(I)）作為信息SNP子集的評價指標，其定義為對所有非信息SNP位點預測準確度的平均值。重構度越高，信息SNP 子集對非信息SNP的預測效果越好。

2）分類效果的評價指標

本文使用F1-measure 和預測準確率（Acc）來對分類效果進行評價。

4.3 實驗結果及分析

1）信息SNP選擇實驗及分析

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

由圖3 和圖5 可看出，K-MIM/蟻群算法所提取出的信息SNPs對非信息SNP 子集具有更高的重構度，且當聚類簇數為7 時，在兩個數據集上均取得較好的實驗結果，在后續的分類實驗中，將使用簇數為7時所篩選出的信息SNP子集進行實驗。

圖3 Dataset1上每種算法選出的信息SNP對非信息SNP的重構度

圖4 Dataset2上每種算法選出的信息SNP對非信息SNP的重構度

2）分類實驗及分析

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

由表2 可看出，K-Means/蟻群算法和特征加權K-Means/蟻群算法相比，K-MIM/蟻群算法篩選出的信息SNP 子集具有更好的分類效果。此外，與ReliefF 和MCMR 兩種信息SNP 選擇算法相比，K-MIM/蟻群算法所選擇出的信息SNP 子集在多數情況下取得了更好的分類效果。實驗結果說明，K-MIM 算法在考慮SNP 位點之間的關聯性進行聚類后，在SNP選擇中具有較大的優勢。

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

5 結語

本文針對SNP數據普遍存在的少樣本、高維度的問題，和不同SNP位點之間存在連鎖不平衡導致的位點之間具有強相關性的特點，提出了一種融合互信息的K-Means聚類算法用于SNP的選擇中，將其與蟻群算法結合使用進行信息SNP 子集的篩選。在信息SNP 選擇實驗和分類實驗的結果中表明，K-MIM/蟻群算法所篩選出的信息SNP 子集對于非信息SNP 子集的重構和分類都具有較大的優勢。本文后續工作在于對蟻群算法進行改進，使篩選出的信息SNP 子集具有更高的重構度和分類準確度。