用于微陣列數據分類的子空間融合演化超網絡

王 進,劉 彬,張 軍,陳喬松,鄧 欣

(重慶郵電大學計算智能重慶市重點實驗室，重慶 400065)

?

用于微陣列數據分類的子空間融合演化超網絡

王 進,劉 彬,張 軍,陳喬松,鄧 欣

(重慶郵電大學計算智能重慶市重點實驗室，重慶 400065)

針對傳統(tǒng)模式識別方法在學習具有小樣本特性的DNA微陣列數據時存在的過擬合問題,本文提出了一種子空間融合演化超網絡模型.該模型通過子空間劃分、超邊全覆蓋和子空間融合三種方法降低模型對初始化的依賴,減少了對數據空間的擬合誤差,提高了演化超網絡的泛化能力.對四個DNA微陣列數據集的實驗結果表明,子空間融合演化超網絡的識別率和在小樣本訓練集下的泛化能力均優(yōu)于參與對比的其他傳統(tǒng)模式識別方法.

模式識別；微陣列數據分類；演化超網絡；子空間；過擬合

1 引言

DNA微陣列技術的出現為從分子水平研究疾病的發(fā)病機理和臨床診斷提供了強有力的手段,特別是在臨床診斷白血病[1]、結腸癌[2]等惡性腫瘤上具有較高的應用價值.與傳統(tǒng)基于形態(tài)學信息的癌癥診斷方法相比,基于DNA微陣列技術獲得的基因表達譜的癌癥診斷方法具有更高的準確率和可信度[1].

傳統(tǒng)的模式識別方法在學習具有小樣本特性的DNA微陣列數據時存在過擬合問題[3],這導致模型分類的泛化能力下降.同時DNA微陣列數據包含著不同基因之間龐大而復雜的并行交互作用,這些基因間的交互作用對我們研究癌癥的復雜發(fā)展機制有著重要意義.傳統(tǒng)模式識別方法[4～7]雖然取得了較好的分類效果,卻難以深度挖掘基因之間的相互作用.

超網絡(Hypernetwork,HN)是受生物分子網絡啟發(fā)而建立的一種基于超圖(Hypergraph)的認知學習模型[8,9].通過演化學習,超網絡可以有效獲取與分類相關的關鍵特征,擬合輸入模式空間中數據的分布概率,從而表達復雜數據的內在結構和相互之間的關系.因能有效挖掘與癌癥分類相關的基因以及基因間的相互作用,演化超網絡模型已成功用于DNA微陣列數據分類[10,11],然而該模型的分類效果與泛化能力受超邊庫初始化質量的影響較大.

針對上述問題,本文將子空間概念引入到演化超網絡模型中,提出了一種子空間融合演化超網絡(Evolutionary Hypernetworks with Subspace Fusion,SF-HN).通過子空間超邊覆蓋,弱化模型對超邊初始化過程的依賴,提升其在小樣本訓練集下的泛化能力.為驗證子空間融合演化超網絡的性能,本文根據部分替代整體思想提出了一種分類器泛化能力評價方法.通過對四個DNA微陣列數據集進行試驗,證明了該模型具有更優(yōu)的準確性和泛化能力.

2 演化超網絡

超網絡是一種由大量超邊組成的概率圖模型,通過超邊表達模式空間中數據的分布概率[8].超邊所連接的頂點數稱為超邊的階數(Order),所有超邊階數都為k的超網絡稱為k階超網絡[12].超網絡演化學習通過調整超邊庫,提高模型與數據在模式空間概率分布的擬合度.超邊替代法[11]和梯度下降法[12]是常用的演化學習方法.在分類模式下,超網絡通過輸入樣本X與輸出類別Y的聯(lián)合概率P(X,Y)以及X的分布概率P(X),得到最終的決策輸出：

(1)

細粒度演化超網絡(Fine-Grain Evolutionary Hypernetwork,FG-HN)[11]將最優(yōu)類別信息離散化(Optimal Class-Dependent Discretization,OCDD)算法與超網絡結合,采用多位二進制來表述特征屬性,降低了數據離散化過程中的信息損失.然而FG-HN仍無法解決在學習具有小樣本特性的DNA微陣列數據時存在的過擬合問題.

3 子空間融合演化超網絡

傳統(tǒng)演化超網絡只對輸入模式中的訓練樣本集進行學習,處理小樣本數據時,其泛化性將受到影響.為了提高模型的泛化能力,本文在FG-HN[11]的基礎上提出了一種子空間融合演化超網絡.

令S=A1×A2×…×AD表示D維數據空間,Aj(j=1,…,D)表示S中的一個屬性域,k維空間Pi=Ai1×Ai2×…Aik(ik≤D)為S的一個子空間.S=P1∪P2∪…∪Pi∪…為空間S的一個子空間劃分.在分類過程中,X=A1×A2×…×AD表示特征屬性空間,Y表示類別標簽空間.對于空間X的數據進行離散化處理,特征Aj的離散區(qū)間數為mj,則子空間Pi包含的總數據點為m=mi1×mi2×…×mik,m也稱為Pi的秩,空間中的數據點也稱為單元格.超邊所包含的特征空間可表示為Ei=Ai1×Ai2×…×Aik.將超邊看作輸入模式空間的子空間,超邊庫表示特征屬性空間X的一個劃分X=E1∪E2∪…∪E|L|,其中|L|表示超邊總數.

偏斜度SOD(T,P)[13]是衡量子空間劃分效果的評價指標,其定義如下：

(2)

其中,N為訓練集T的樣本數,P為子空間，pi為訓練集T投影在子空間P的第i個單元格上的樣本數,m是子空間的秩,μ=N/m表示平均分布在單元格上的數據點數.SOD(T,P)的取值范圍為[0,1],其值越小,數據點的分布越均勻;反之,則分布越集中.

在SF-HN中,首先進行子空間劃分,選擇樣本分布均勻的子空間集合;其次,生成超邊并把超邊決策范圍覆蓋到整個子空間;接著融合子超邊簇,生成初始化模型；最終通過梯度下降方法對模型進行演化學習,提高模型對輸入數據的擬合精度.子空間融合演化超網絡流程如圖1所示,其中超網絡中的每種連線代表一條超邊(例如實線表示一條包含頂點A4,A1和A6的3階超邊).3.1 子空間劃分算法

超網絡是對輸入模式空間數據分布概率的擬合,當數據散列分布時,其覆蓋的數據空間廣,擬合時的誤差小.因此在子空間劃分算法中，采用訓練集在子空間上的偏斜度對子空間的優(yōu)劣進行評價,并選取樣本分布信息較多的子空間集合.

算法1 子空間劃分算法

輸入：訓練集T,超邊階數k;子空間數sn,冗余倍數d,閾值tsod.

輸出：劃分的子空間集合E.

步驟1num←sn,E←Φ,計算tsod.

步驟2 初始化num*d條階數為k的超邊.

步驟3 將T向每條超邊對應的子空間EEi投影,并計算SOD(T,EEi).

步驟4 將所有子空間按SOD值升序排序.

步驟5 若選擇前num個子空間的SOD值均小于tsod,則將前num個子空間加入E;否則將滿足SOD(T,EEi)

步驟6 若tsum>0,num←tsum,轉入步驟2;否則轉入步驟7.

步驟7 返回E.

3.2 子空間超邊生成算法

子空間超邊生成算法通過產生由訓練樣本映射得到的與訓練集完全擬合的映射超邊和通過映射超邊信息確定類別的預測超邊,加入樣本關聯(lián)信息,擴展超邊的決策范圍,對子空間進行超邊全覆蓋.

子空間超邊生成算法的流程為：將子空間Ei中對應的單元格轉化為超邊加入到子超邊簇LSi中,此時超邊不包含類別信息;將訓練集T在子超邊簇LSi上投影,并確定至少有一個樣本映射到對應單元格的超邊類別;最后對剩余未知類別信息的超邊進行類別預測.由于輸入模式空間數據為連續(xù)分布,因此對模式空間中的數據點,其類別可由其相鄰數據點的類別確定.故對每條未知類別超邊,統(tǒng)計其相鄰超邊的類別,并將包含超邊最多的類別賦給待預測類別超邊;若不同類別包含的超邊數相等,則此超邊處在類別分界線上,不對其類別賦值.當無新確定類別的超邊時,算法終止.

算法2 子空間超邊生成算法

輸入：訓練集T,子空間Ei.

輸出：子超邊簇LSi.

步驟1LSi←Φ.

步驟2 子空間Ei中每個單元格fj轉化為超邊lj并加入到子超邊簇LSi,其中超邊的類別標簽為空.

步驟3 將訓練集T在子超邊簇LSi上投影.

步驟4 遍歷每條超邊lj對應的單元格fj,若至少有一個樣本映射到fj,則將該超邊類別賦為映射到相應單元格中數量最多的樣本類別.

步驟5 統(tǒng)計未知類別超邊的數量ln,lt←ln.

步驟6 統(tǒng)計每條未知類別超邊的相鄰超邊類別,若不同類別超邊數量不等,則將包含超邊數量最多的類別賦給該超邊.

步驟7 統(tǒng)計未知類別的超邊數量ln,若lt≠ln,轉入步驟5;否則轉入步驟8.

步驟8 返回LSi.

3.3 子空間融合算法

覆蓋子空間的子超邊簇既包含由訓練集映射而成的超邊,也包含由映射超邊對未知類別超邊進行預測擴展而成的超邊.子超邊簇中由訓練集映射而成的超邊是對訓練集樣本分布的零誤差擬合,而經預測擴展而成的超邊則存在擬合誤差,并且不同子空間中預測超邊的擬合誤差不同.子空間融合算法通過融合不同子空間上的子超邊簇,降低預測超邊的擬合誤差,進而提高模型對訓練集的擬合精度.由于偏斜度低的子空間生成的超邊簇具有更優(yōu)的擬合效果,在融合時采用加權集成的方式,將1-SOD(T,Ei)作為子空間對應超邊簇的權重.

算法3 子空間融合算法

輸入：訓練集T,超邊簇集合LS.

輸出：超邊庫L.

步驟1L←Φ.

步驟2 遍歷每個子超邊簇,根據T在每個子超邊簇LSi對應子空間Ei的投影,計算SOD(T,Ei),并將LSi中每個超邊的權重設為1-SOD(T,Ei).

步驟3 將賦予權重的超邊簇加入到L中.

步驟4 返回L.

3.4 子空間融合超網絡的演化學習

SF-HN通過將子超邊簇融合為一個超邊庫,擬合模式空間的數據分布.因模型對子空間進行了超邊全覆蓋操作,無需替代操作,故采用梯度下降演化學習方法[12],通過訓練集來控制超邊權重的調整方向,調整模型結構,降低融合后模型對未知樣本的預測誤差.權重變化值Δwj計算公式為：

(3)

其中,P(y*|xi)和P*(y*|xi)分別表示樣本xi屬于類別y*的實際概率和目標概率,y*是超網絡對樣本xi的分類結果,y是樣本xi的真實類別,η是學習速率.I為匹配函數,當超邊lj與樣本xi匹配時值為1;否則值為0.子空間融合超網絡的分類方法與傳統(tǒng)超網絡的流程[11]相似,唯一的區(qū)別在于估計概率時統(tǒng)計超邊權重之和而不是數量之和.

算法4 子空間融合超網絡演化學習算法

輸入：訓練集T,子空間數sn;超邊階數k;梯度下降演化代數iternum.

輸出：超邊庫L.

步驟1 根據子空間劃分算法,生產包含sn個子空間的子空間集合E.

步驟2 對每個子空間Ei,利用子空間超邊生成算法,生成子超邊簇LSi.最終得到包含sn個子超邊簇的超邊簇集合LS.

步驟3 對超邊簇LS,利用子空間融合算法,得到初始超邊庫L.

步驟4t←0.

步驟5 用當前子空間融合超網絡模型對訓練集分類.

步驟6 對每個錯分樣本xi,更新與xi匹配的超邊lj的權重wj=wj+Δwj,其中通過式(3)計算Δwj.

步驟7t++,若t

步驟8 返回L.

4 實驗結果與分析

為驗證子空間融合演化超網絡的分類準確性和泛化性,本文采用結腸癌[2]、急性白血病[1]、肺癌[14]、前列腺癌[15]四個DNA微陣列數據集進行實驗驗證.數據集的具體信息如表1所示.

4.1 分類性能測試

本文采用OCDD算法[16]對輸入數據進行離散化處理,采用信噪比特征基因選擇方法[1]對數據進行降維處理.為了驗證SF-HN的分類效果,將其與其他文獻方法(GSVM-RFE[5],NN[4],Bagging[7])、傳統(tǒng)分類方法(C4.5決策樹、樸素貝葉斯(Nave Bayes,NB)、支持向量機(Support Vector Machine,SVM))以及HN和FG-HN進行對比.本文的所有實驗結果為20次實驗的平均值.SF-HN的參數通過訓練集5折交叉驗證來確定,其參數設置如表2所示.HN和FG-HN采用文獻[11]中的實驗參數設定,分類算法C4.5、NB、SVM采用Weka機器學習開源項目提供的算法(http://www.cs.waikato.ac.nz/ml/weka/),其輸入數據的特征維度與FG-HN相同.此外,本文通過t-檢驗來測試SF-HN在統(tǒng)計學上是否顯著優(yōu)于C4.5、NB、SVM、HN和FG-HN方法.

通過對完整的訓練集進行學習,然后對獨立測試集進行測試,所得結果如表3所示.在表3中,“·”表示SF-HN在p<0.01的水平下顯著優(yōu)于對比方法.相對于其它對比分類算法,SF-HN具有較好的分類性能和顯著性優(yōu)勢.這主要是由于SF-HN在空間中進行超邊覆蓋,增加了模型的信息熵,從而更有效地擬合輸入模式空間中的數據分布.

表1 數據集信息表

表2 SF-HN的參數設置

表3 不同方法對4個DNA微陣列數據集的測試集分類結果

4.2 泛化性能測試

泛化能力表示分類器通過對訓練集的學習,對未知樣本的預測能力[17].但在據作者所知的文獻中,還缺乏公認的對分類器泛化性能評價的定量指標.機器學習領域通常認為泛化性能好的算法在小樣本訓練集下仍可獲得較高的分類精度.本文采用部分替代整體思想進行泛化性能測試的實驗設計,通過拆分原始訓練集獲得小樣本訓練集,進而驗證不同分類方法在小樣本訓練集下的泛化性能.泛化性測試的主要流程為：首先是將訓練集按原正負類別的比例平均分為n份;之后利用拆分后的每一份數據分別訓練分類器并對獨立測試集進行測試.對得到的n個獨立測試集測試結果求取平均,作為分類器泛化能力評價指標.在本文中,訓練集平均劃分為n份以n-bt表示.

泛化性能測試中對訓練集進行拆分后,訓練集中樣本數量減少,離散區(qū)間數過大將導致數據中同類別樣本間的關聯(lián)概率降低;而階數過大的超邊很難與樣本進行匹配.因此對四個數據集,特征選擇數設為32,特征最大離散區(qū)間數為設為3,HN、FG-HN和SF-HN的階數分別設定為5、4、3.對每個數據集,采取2-bt、3-bt、4-bt、5-bt泛化性能實驗.

泛化性測試結果如表4～7所示.相對于其他方法,在3-bt、4-bt、5-bt設定下SF-HN具有更高的泛化性能.這是因為在分類器的學習過程中,SF-HN通過對超邊類別的預測,對子空間進行超邊覆蓋,在本質上類似于虛擬樣本生成,通過增加樣本的數量,實現了對數據分布的更優(yōu)擬合.而在2-bt時,由于某些數據集中正負類別的界限較寬,SVM能夠發(fā)揮更優(yōu)的性能.當n-bt中的n增大時,所有方法對獨立測試集的識別率隨之降低.這是因為隨著訓練集樣本數的減少,關于模式空間描述的信息量相應減少,從而導致分類器對模式空間的描述可信度降低.然而相對其它方法,SF-HN下降趨勢最緩慢.這是因為SF-HN通過子超邊簇對子空間進行全覆蓋,增加了超邊對未知樣本的匹配概率,避免了超邊對其生成樣本的過度依賴,不會出現對訓練集的過擬合,在小樣本數據中具有較高的優(yōu)勢.

表4 結腸癌數據集不同分類器泛化性能測試結果

表5 急性白血病數據集不同分類器泛化性能測試結果

表6 肺癌數據集不同分類器泛化性能測試結果

表7 前列腺癌數據集不同分類器泛化性能測試結果

5 結論

本文提出了一種子空間融合演化超網絡模型.通過將子空間概念引入到演化超網絡中,把超邊包含的特征看作是輸入模式空間的子空間,在子空間進行超邊覆蓋,減弱了模型對超網絡初始化效果的依賴;同時通過超邊子空間覆蓋和子空間融合,加入樣本間的關聯(lián)信息,提高了模型對未知樣本的分類效果和泛化性能.本文根據部分替代整體思想設計了分類器泛化性能測試實驗,并提出了評價分類器泛化性能的方法.通過四個DNA微陣列數據集下的對比實驗表明,本文方法的識別率和在小樣本訓練集下的泛化能力均優(yōu)于其他傳統(tǒng)模式識別方法.

[1]Golub T R,Slonim D K,Tamayo P,et al.Molecular classification of cancer:class discovery and class prediction by gene expression monitoring[J].Science,1999,286(5439):531-537.

[2]Alon U,Barkai N,Notterman D,et al.Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays[J].Proceedings of the National Academy of Sciences,1999,96(12):6745-6750.

[3]Reunanen J.Overfitting in making comparisons between variable selection methods[J].Journal of Machine Learning Research,2003,3:1371-1382.

[4]Cho S B,Won H.Cancer classification using ensemble of neural networks with multiple significant gene subsets[J].Applied Intelligence,2007,26(3):243-250.

[5]Mundra P A,Rajapakse J C.SVM-RFE with MRMR filter for gene selection[J].IEEE Transactions on Nanobioscience,2010,9(1):31-37.

[6]Prasartvit T,Banharnsakun A,Kaewkamnerdpong B,et al.Reducing bioinformatics data dimension with ABC-kNN[J].Neurocomputing,2013,116:367-381.

[7]Tan A C,Gilbert D.Ensemble machine learning on gene expression data for cancer classification[J].Applied Bioinformatics,2003,2(3 suppl):75-83.

[8]Zhang B T.Hypernetworks:a molecular evolutionary architecture for cognitive learning and memory[J].IEEE Computational Intelligence Magazine,2008,3(3):49-63.

[9]Kim S J,Ha J W,Zhang B T.Bayesian evolutionary hypergraph learning for predicting cancer clinical outcomes[J].Journal of Biomedical Informatics,2014,49(6):101-111.

[10]Park C H,Kim S J,Kim S,et al.Use of evolutionary hypernetworks for mining prostate cancer data[A].Proceedings of the 8th International Symposium on Advanced Intelligent Systems[C].Springer,2007.702-706.

[11]王進,張軍,胡白帆.結合最優(yōu)類別信息離散的細粒度超網絡微陣列數據分類[J].上海交通大學學報,2013,47(12):1856-1862.

Wang Jin,Zhang Jun,Hu Bai-fan.Optimal class-dependent discretization-based fine-grain hypernetworks for classification of microarray data[J].Journal of Shanghai Jiaotong University,2013,47(12):1856-1862.(in Chinese)

[12]Wang J,Huang P L,Sun K W,et al.Ensemble of cost-sensitive hypernetwork for class-imbalance learning[A].Proceedings of IEEE International Conference on Systems,Man,and Cybernetics[C].IEEE,2013.1883-1888.

[13]孫煥良,鮑玉斌,于戈.一種基于劃分的孤立點檢測算法[J].軟件學報,2006,17(5):1009-1016.

Sun Huan-liang,Bao Yu-bin,Yu Ge.An algorithm based on partition for outlier detection[J].Journal of Software,2006,17(5):1009-1016.(in Chinese)

[14]Gordon G J,Jensen R V,Hsiao L L,et al.Translation of microarray data into clinically relevant cancer diagnostic tests using gene expression ratios in lung cancer and mesothelioma[J].Cancer research,2002,62(17):4963-4967.

[15]Singh D,Febbo P G,Ross K,et al.Gene expression correlates of clinical prostate cancer behavior[J].Cancer Cell,2002,1(2):203-209.

[16]Liu L,Wong K C,Wang Y.A global optimal algorithm for class-dependent discretization of continuous data[J].Intelligent Data Analysis,2004,8(2):151-170.

[17]張海,徐宗本.學習理論綜述(I):穩(wěn)定性與泛化性[J].工程數學學報,2008,25(1):1-9.

Zhang Hai,Xu Zong-ben.A survey on learning theory (I):stability and generalization[J].Chinese Journal of Engineering Mathematics,2008,25(1):1-9.(in Chinese)

王 進 男,1979年1月出生于重慶，教授.主要研究方向為數據挖掘、機器學習.

E-mail:wangjin@cqupt.edu.cn

劉 彬(通信作者) 男,1989年11月出生于河北保定,碩士研究生.主要研究方向為數據挖掘.

E-mail:nanfeizhilu@163.com

Classification of Microarray Data Using Evolutionary Hypernetworks with Subspace Fusion

WANG Jin,LIU Bin,ZHANG Jun,CHEN Qiao-song,DENG Xin

(ChongqingKeyLaboratoryofComputationalIntelligence,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

In order to solve the over-fitting problem of the traditional pattern recognition approaches under the DNA microarray data with small train samples,a subspace fusion-based evolutionary hypernetwork model is proposed in this paper.With the methods of subspace division,hyperedge coverage,and subspace fusion,the proposed scheme reduces the dependence on the initialization,decreases the fitting error of the data space,and enhances the generalization ability of the evolutionary hypernetwork.The experimental results on four DNA microarray datasets show that the proposed model achieves higher classification accuracy and stronger generalization ability than other compared traditional pattern recognition method.

pattern recognition;microarray data classification;evolutionary hypernetwork;subspace;over-fitting

2015-03-11;

2015-06-30;責任編輯:李勇鋒

國家自然科學基金(No.61203308，No.61403054);重慶教委科學技術研究項目(自然科學類)(No.KJ1400436);重慶市基礎與前沿研究計劃項目(No.cstc2014jcyjA40001)

TP39

A

0372-2112 (2016)10-2308-06

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.004