林莉媛1，陳曉云1，簡彩仁2

　　（1.福州大學 數學與計算機科學學院,福建 福州 350116；2. 廈門大學 嘉庚學院，福建 漳州 363105）

       摘要：有效分類基因表達數據有助于癌癥的診斷，而基因表達數據的高維數、小樣本特點使基因表達數據分類困難。針對這個問題，在最小二乘回歸子空間分割算法中考慮距離信息，提出融入距離信息的最小二乘回歸子空間分割算法。融入距離信息的最小二乘回歸子空間分割模型除了考慮數據之間的相關性，還考慮了數據之間的距離信息。在基因表達數據集上的實驗結果表明，所提出的算法是有效的聚類方法。

　　關鍵詞：基因表達數據；聚類；距離；子空間分割

0引言

　　基因表達數據的研究有助于準確識別癌癥［1］，因此有效處理基因表達數據尤為重要。但基因表達數據小樣本、高維數［2］的特點令這項工作困難重重。近幾十年來，很多分類和聚類方法成功應用在基因表達數據上，如凸非負矩陣分解（Convex Nonnegative Matrix Factorization，C_NMF）、半非負矩陣分解（Seminonnegative Matrix Factorization，S_NMF）［3］、基因數據分析半監督學習［2］以及根據基因表達數據特點改進的譜聚類算法［4］等。基因表達數據的聚類分為基因聚類、樣本聚類和雙向聚類［5］，本文對腫瘤基因表達數據樣本聚類。

　　子空間分割方法是近年流行的方法［6］，如稀疏子空間聚類SSC［7］、低秩表示子空間聚類LRR［8］、最小二乘回歸子空間聚類LSR［9］等，并成功用于圖像分割、圖像壓縮以及混合系統鑒定等領域［6］。子空間分割方法可使高維數據有效聚類，這適用于基因表達數據，因此本文將提出新的用于基因表達數據聚類的子空間分割方法。LSR使同類相關性強的樣本聚集，但沒考慮距離信息，針對這點，本文對LSR進行改進，融入距離信息，并將改進后的模型應用在基因表達數據中，通過與其他用于基因表達數據的聚類方法以及子空間分割算法進行實驗比較，證明本文方法是有效的。

1子空間分割

　　子空間聚類又稱子空間分割［6］，目標是尋找多個低維子空間，將數據歸到相應子空間中，數學定義為［6］：設{xi∈Rd}ni=1是從k≥1個維數未知的子空間或仿射空間{Si}ki=1中采樣獲得的點集，各子空間維數為mi,0<mi<d，i=1,…,k。子空間描述為Si={x∈Rd:x=ui+Uiy},i=1,…,k,ui∈Rd是子空間Si的任意點（線性空間ui=0)，Ui∈Rd×mi是Si的一個基，y∈Rmi是x的低維表示。子空間聚類是找子空間個數k、維數{mi}ki=1、基{Ui}ki=1、點{ui}ki=1，并將點集分割到子空間中。

　　LSR［9］是基于譜聚類的子空間聚類方法，與其他基于譜聚類的方法一樣，先構造仿射矩陣，再將譜聚類方法應用在仿射矩陣上，模型為：

　　minZZF，s.t.X=XZ

　　噪聲的擴展模型為：

　　minZX－XZ2F+λZ2F(1)

　　其中，λ>0，·F是F范數，參考文獻［9］給出式(1)的計算方法，并證明LSR有聚集性，是高效、魯棒的方法。

2融入距離信息的最小二乘回歸子空間分割

　　2.1樣本數據點的距離信息

　　由參考文獻［10］可知彼此間距離近的數據點更可能來自同一子空間，因此本文假設彼此間距離近的數據點可分配到更大的權重系數。設樣本集為{x1,x2,...,xn}，X∈Rd×n，xi∈Rd×1。根據上述假設，對于任意樣本xi，希望：

　　min∑nj=1xi－xj2zij

　　其中，zi∈Rn×1，zij是zi的第j個元素，矩陣形式為：

　　min Tr(ZΤD)(2)

　　其中，D為距離矩陣，xi－xj2是D的第i行的第j個元素，Z={z1,z2,…,zn}。

　　2.2融入距離信息的最小二乘回歸子空間分割模型

　　將式(2)與最小二乘回歸子空間分割模型相結合，得到融入距離信息的最小二乘回歸子空間分割模型為：

　　minZ12X－XZ2F+λ2Z2F+βTr(ZΤD)(3)

　　其中，λ>0、β>0是兩個可調節的參數,·F表示F范數，Tr(·)表示跡。令：

　　對L(Z)求導,并令其導數為0，即L=－XΤX+XΤXZ+λZ+βD=0，可得到式（3）的最優解：Z*=(XTX+λI)－1(XTX－βD)。

　　通過(|Z*|+|(Z*)T|)/2構造仿射矩陣，再用標準聚類方法（Normalized Cuts, Ncut）［11］分割彷射矩陣。融入距離信息的最小二乘回歸子空間分割(Subspace Segmentation via Least Squares Regression including Information about Distance, DLSR)算法如下：

　　輸入：數據矩陣X，類別數為k，參數β、λ

　　（1）解決問題式（3）得到解Z*；

　　（2）通過(|Z*|+|(Z*)T|)/2計算仿射矩陣；

　　（3）應用Ncut方法將數據分成k個子空間。

　　輸出：聚類結果

3實驗

　　本節在基因表達數據集上用聚類準確率驗證提出的DLSR，與本文方法比較的現有方法為：傳統聚類方法kmeans和層次聚類（Hierarchical Clustering, HC），子空間分割方法LRR［8］和LSR［9］，非負矩陣分解擴展方法C_NMF和S_NMF［3］。

　　3.1數據集

　　實驗使用公開基因表達數據集: 9_Tumor［12］、Brain_Tumor［13］、Leukemia［14］、Leukemia［13］、Leukemia［15］、DLBCL［13］，數據集信息如表1所示。表1數據集信息數據集診斷內容樣本個數基因個數類別數9_Tumor人類腫瘤605 7269Brain_Tumor1腦癌1905 9205Leukemia白血病727 1292DLBCL彌漫性大B細胞淋巴瘤和

　　濾泡性淋巴瘤775 4692Leukemia1白血病1725 3273Leukemia2白血病28311 2253

　　3.2實驗結果與分析

　　準確率計算公式為：

　　其中，ri是得到的類標簽；si是樣本本身的類標簽；n為樣本數；map(ri)是將ri映射成與si等價的類標簽；δ(x,y)是一個函數，δ(x,y)=1x=y

　　0x≠y。

　　實驗中，DLSR、LSR、LRR都需設置參數，本文的參數選擇方法是讓參數取多個不同的值，實驗時遍歷這些值，最后取使結果最好的值。DLSR還有另一個參數β，取值策略與λ相同。實驗時，HC運行一次，其余算法運行10次，取準確率的平均值，結果如表2所示。

　　6個數據集上的實驗表明，除Leukemia外，DLSR與其他方法相比，都取得較優準確率。kmeans雖然在Leukemia中準確率最高，但在其余數據集中的結果并不都好。總的來說，DLSR還是優于kmeans。因此，本文算法對基因表達數據的聚類更有效。

　　值得注意的是，DLSR優于LSR，因此在LSR中融入距離信息，可以提供一定的額外信息，有利于提高算法聚類能力。

　　3.3參數選擇

　　DLSR模型有兩個參數β和λ。本節設置參數β的變化范圍為{0.002,0.004,0.01,0.04,0.6,0.7,1,100,10 000, 100 000}，參數λ的變化范圍為{0.005,0.01,0.05, 0.1,0.5,1,10,100,1 000}。圖1描述了這兩個參數變化對聚類準確率的影響。平穩的地方說明參數取在那部分時準確率變化較穩定。可看出DLSR對參數β和λ的選取都較敏感，聚類準確率隨參數變化呈現出一定波動。總體上看，參數β選在0.002~0.6范圍內可找到較理想的聚類準確率，參數λ選在0.05~10范圍內可找到較好的聚類準確率。

　　4結論

　　本文在最小二乘回歸子空間分割模型的基礎上，考慮距離信息，提出融入距離信息的最小二乘回歸子空間分割模型，并應用在基因表達數據上。實驗表明，對于給出的基因表達數據集，DLSR與子空間分割算法LRR、LSR以及原先用于基因表達數據的方法相比更有效。而且，在LSR的基礎上融入了距離信息，確實可提高聚類能力，對LSR有一定的優化。但是介于參數的選取對實驗結果較為敏感，如何高效地選取參數是今后要研究的問題。

參考文獻

　　［1］ 黃德雙. 基因表達譜數據挖掘方法研究［M］.北京：科學出版社, 2009.

　　［2］ 劉德山, 孫麗, 閆德勤. 一種基因數據分析的半監督學習算法［J］. 微型機與應用, 2014, 33(12): 4447.

　　［3］ DING C, Li Tao, JORDAN M. Convex and seminonnegative matrix factorizations［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(1): 4555.

　　［4］ 王俊生, 王年, 郭秀麗, 等. 基于 Normalized Cut 的基因表達數據聚類［J］. 安徽大學學報(自然科學版),2012, 36(4): 6872.

　　［5］ Jiang Daxin, Tang Chun, Zhang Aidong. Cluster analysis for gene expression data: a survey［J］. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11): 13701386.

　　［6］ VIDAL R. A tutorial on subspace clustering［J］. IEEE Signal Processing Magazine, 2010, 28(2): 5268.

　　［7］ ELHAMIFAR E, VIDAL R. Sparse subspace clustering［C］. IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2009, IEEE, 2009: 27902797.

　　［8］ Liu Guangcan, Lin Zhouchen, Yu Yong. Robust subspace segmentation by lowrank representation［C］. Proceedings of the 27th International Conference on Machine Learning (ICML10), 2010: 663670.

　　［9］ Lu Canyi, Min Hai, Zhao Zhongqiu, et al. Robust and efficient subspace segmentation via least squares regression［C］. European Conference on Computer Vision, ECCV 2012, 2012,7578(1): 347360.

　　［10］ Nie Feiping, Wang Xiaoqian, Huang Heng. Clustering and projected clustering with adaptive neighbors［C］. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2014: 977986.

　　［11］ Shi Jianbo, MALIK J. Normalized cuts and image segmentation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888905.

　　［12］ STAUNTON J E, SLONIM D K, COLLER H A, et al. Chemosensitivity prediction by transcriptional profiling［J］. Proceedings of the National Academy of Sciences, 2001, 98(19): 1078710792.