基于云平臺的互信息最大化特征提取方法研究*

魏莎莎 ，陸慧娟 ，金 偉 ，李 超

（1.中國計量學院信息工程學院 杭州 310018；2.中國計量學院機電工程學院 杭州 310018）

1 引言

基因芯片技術(shù)是隨著人類基因組計劃發(fā)展起來的一項新技術(shù)，大規(guī)模基因芯片（DNA微陣列）技術(shù)的應用是現(xiàn)在功能基因組以及腫瘤診斷等研究中的重要監(jiān)測手段[1]，可廣泛用于基因序列分析、基因突變檢測、疾病診斷等諸多領(lǐng)域?；诨虮磉_數(shù)據(jù)維數(shù)高、樣本小的特點，直接對其進行學習的生物學分析成本較高，并且有些基因只在特定實驗條件下表達，為了降低機器學習的時間及空間復雜度，需要對其進行特征選擇，選取與分類緊密關(guān)聯(lián)的基因，同時提高分類精度[2]。特征選擇是根據(jù)各個特征的重要程度，剔除特征中不相關(guān)的冗余特征后，挑選出對分類有意義的某些特征，以降低特征空間維數(shù)。在模式識別、數(shù)據(jù)挖掘以及機器學習中，特征選擇都非常關(guān)鍵[3]。特征選擇方法從研究之初到現(xiàn)在，已經(jīng)有了很多成熟的方法，2005年，Peng[4]和Ding[5]在處理連續(xù)特征時，分別使用 F-Statistic和Pearson相關(guān)系數(shù)度量相關(guān)性程度進行特征選擇。這為本文利用兩個特征之間互信息最大化的方法進行特征過濾提供了思路與基礎(chǔ)。

互信息是信息論中的一個重要概念，通常用于描述兩個隨機變量間的統(tǒng)計相關(guān)性，用一個變量中包含另一個變量的信息多少表示兩個隨機變量之間的依賴程度，一般用熵表示[6]。在統(tǒng)計學上，同一分類系統(tǒng)的基因并非獨立而是相關(guān)的，確定基因之間的互信息就是要定義相似性測度尋找變換關(guān)系，使得基因間的相似性達到最大，從而確定該基因在分類系統(tǒng)中的重要程度。其中，當信息量達到最佳配準時，即實現(xiàn)互信息最大化。在醫(yī)學領(lǐng)域中，利用互信息最大化法進行多模醫(yī)學圖像配準包括CT掃描以及核磁共振等成為醫(yī)學圖像處理方面的熱點[7]，它能夠很快地排除很大數(shù)量的非關(guān)鍵性的噪聲和無關(guān)基因，是特征選擇中一種基于相關(guān)性的過濾方法。但在數(shù)據(jù)量較大的情況下，對服務器性能要求高，計算效率低，而云計算的出現(xiàn)為解決這個問題提供了新的契機[8]。

云計算是傳統(tǒng)計算機技術(shù)發(fā)展融合的產(chǎn)物，是一種基于互聯(lián)網(wǎng)的計算方式，通過這種方式，共享的軟硬件資源和信息可以按需提供給計算機和其他設(shè)備[9]。云是網(wǎng)絡、互聯(lián)網(wǎng)的一種比喻說法，一般來說包括IaaS、PaaS和SaaS3個層次。

目前，將云計算與分類問題結(jié)合，參考文獻[8]等提出了基于云計算平臺的代價敏感集成學習算法，參考文獻[10]提出了云計算在貝葉斯分類中的應用，但還沒有相關(guān)文獻討論如何在云計算平臺環(huán)境下對數(shù)據(jù)特征進行過濾。為了能夠快速、準確、高效地處理基因數(shù)據(jù)特征提取問題，本文提出了一種基于云計算平臺的Filter型基因選擇算法——CMI-Selection。

本文對算法的實現(xiàn)進行了仿真模擬，在CMI-Selection中，實驗室用5臺PC搭建了Hadoop云計算平臺，首先利用隨機函數(shù)將數(shù)據(jù)集隨機分為5個部分，每個部分遵循互信息算法進行篩選計算，然后將結(jié)果返回到客戶機端用于測試及分類。為了評估算法在云平臺下的性能，實驗用ELM（極限學習機）對提取后的特征進行訓練和學習，結(jié)果表明，在分類精度與普通PC端相近的情況下，CMI-Selection速度更快。

2 互信息與基因篩選

在進行基因選擇和基因降維之前，首先要進行基因篩選。在基因表達數(shù)據(jù)特征提取的前期過程中，基因篩選能夠提高計算效率，是選出具有代表性的精簡的基因子集的有效方法[11]。

熵用來表示任何一種能量在空間中分布的均勻程度，其大小跟能量分布均勻程度有關(guān)，能量越不確定且分布越均勻，熵就越大[12]。信息論中的“信息熵”是香農(nóng)[13]在進行信息處理時提出的概念。在互信息最大化方法中，信息熵主要用來衡量一個隨機變量取值的重要性程度，以特征能夠為分類帶來多少信息為衡量標準，帶來的信息越多，該特征越重要。

假設(shè)X來自于一個集合S，且X是一個離散隨機變量。X的概率密度分布函數(shù)表示為p(x)，則X的信息熵定義如下：

已知一個來自于集合T的變量Y，P(x|y)表示Y取值為y、X取值為x的概率，X的不確定性用 H(X|Y)衡量，如式（2）所示：

P(x,y)用來表示X、Y的聯(lián)合概率密度，則它們的互信息量I(X;Y)定義為：

在基因篩選過程中，互信息通常用來表示計算特征與特征之間的關(guān)系。在上述式子中，假設(shè)考慮特征t與類c的分布，N為基因總數(shù)，A為類c中出現(xiàn)特征t的基因數(shù)，B為非類c中出現(xiàn)特征t的基因數(shù)，C為類c中不出現(xiàn)特征t的基因數(shù)，特征t與類c之間的互信息定義為：

如果I(t;c)=0，那么特征t與類c相互獨立。

在式（5）中提供關(guān)于類別信息的加權(quán)平均值來衡量一個特征在全局特征選擇中的重要性：

特征選擇后，盡可能多地保留關(guān)于類別的信息，即達到互信息最大化：

則最大互信息量為：

用互信息最大化方法進行特征選擇后，選出來的特征集合應該盡可能多地提供關(guān)于某個類別的信息。兩個隨機變量之間共有的信息量越大，則兩個變量之間的相關(guān)程度越高，互信息量越大；如果兩個隨機變量完全不相關(guān)，則兩個變量之間不相關(guān)，互信息量為0?；バ畔⒆畲蠡沁x擇相關(guān)程度最高的兩個變量進行循環(huán)迭代，得出每次信息量中相關(guān)程度最高的變量。

3 基于云計算平臺的特征選擇系統(tǒng)

云計算[14]描述了一種基于互聯(lián)網(wǎng)的新的IT服務增加、使用和交付模式，通常涉及互聯(lián)網(wǎng)提供動態(tài)易擴展而且經(jīng)常是虛擬化的資源，意味著計算能力也可以作為一種商品進行流通。云是網(wǎng)絡、互聯(lián)網(wǎng)的一種比喻說法。典型的云計算提供商往往提供通用的網(wǎng)絡業(yè)務應用，軟件和數(shù)據(jù)都存儲在服務器上（即云端），用戶可以通過瀏覽器或者其他Web服務訪問。

3.1 Hadoop云計算平臺的體系結(jié)構(gòu)

Hadoop是Lucene子項目Nutch的一部分，是由Apache SoftwareFoundation開源組織提出的一個分布式計算開源框架，它不是一個縮寫字，而是一個虛構(gòu)的名字。Hadoop的核心是MapReduce和分布式文件系統(tǒng) （Hadoopdistributedfile system，HDFS）及后來加入的 HBase。MapReduce就是任務的分解與匯總（規(guī)約），如圖1所示，它是一種簡化的并行計算編程模型，其中map主要是把任務分解成多個任務，而reduce則把分解后的多任務處理匯總起來。

圖1 MapReduce工作過程

HDFS用來存儲分布式計算的數(shù)據(jù)，采用mater/slave架構(gòu)，由若干個數(shù)據(jù)節(jié)點和一個名稱節(jié)點組成。服務器間相互通信的過程如圖2所示。

圖2 服務器之間相互通信的過程

HBase則對應于Google的BigTable。

Hadoop的特點介紹如下。

·構(gòu)建成本低：Hadoop框架對硬件環(huán)境沒有任何限制，無需昂貴的服務器，普通的PC即可實現(xiàn)。在軟件使用方面，由于部署目標平臺 Linux是開源的，不存在軟件授權(quán)費等方面的問題。

·可靠性：在實現(xiàn)時，由于Hadoop認為所有節(jié)點都有可能會發(fā)生計算或者存儲失敗，故其在節(jié)點群中維護了很多工作副本，一定程度上保證了系統(tǒng)的備份恢復機制和分布式處理的可靠性。

·擴容能力：能非常容易地增添計算存儲資源。

·效率高。

3.2 基于MapReduce的特征過濾

MapReduce由兩個動詞組成，分別控制任務的分解和匯總，從技術(shù)創(chuàng)新角度來講，MapReduce也并不是創(chuàng)新技術(shù)，分布式并行計算程序的編寫也十分簡單，Hadoop中Streaming工具使用起來方便快捷，一般編程技術(shù)就可以開發(fā)出一個分布式并行程序，用于海量數(shù)據(jù)的并行計算。

在對基因表達數(shù)據(jù)進行特征過濾中，步驟如下。

（1）隨機函數(shù)對基因數(shù)據(jù)集進行隨機分塊。為了仿真模擬，實驗用5臺PC組成一個Hadoop云計算平臺。

（2）map函數(shù)對分塊的特征集進行信息熵的計算。這里的map函數(shù)被定義為互信息最大化算法。通過設(shè)置map任務的特征數(shù)量的大小，讓云平臺自動對t時刻到達的特征集進行劃分，每塊數(shù)據(jù)對應一個map任務，每個map任務計算各自特征集的信息熵，同一時刻不同map之間進行并行計算，得到t時刻所有特征的信息熵。

（3）執(zhí)行reduce任務，包括特征提取和特征集成兩個階段。其中特征提取按照互信息最大化算法的標準進行。

4 實驗結(jié)果

在理論分析的基礎(chǔ)上，本節(jié)選取4組基因表達數(shù)據(jù)集對 CMI-Selection進行性能測試，其中 Breast、Colon、Heart為兩類數(shù)據(jù)，Leukemia為多類數(shù)據(jù)。數(shù)據(jù)集信息見表1。

表1 數(shù)據(jù)集信息

在特征提取之前，先將基因表達矩陣中的元素進行對數(shù)轉(zhuǎn)換，實現(xiàn)標準化：

本文用Breast數(shù)據(jù)集作為實驗例子進行分析與研究，首先用隨機函數(shù)對數(shù)據(jù)集進行分塊，在云平臺上有4臺PC部署數(shù)據(jù)節(jié)點和任務服務器端，即每部分得到6120個特征。每塊特征數(shù)據(jù)對應一個map任務，每個map任務計算各自特征集的信息熵，利用互信息最大化方法得出特征集額互信息，隨后開始執(zhí)行reduce步驟。在reduce步驟中，對上一步得到的互信息進行排序，篩選特征，得到排名前1224個特征。最后進行匯總，運送到客戶機，在客戶機端用ELM對獲得的基因特征進行訓練和測試。實驗結(jié)果如圖3、圖4所示。

從圖3可以看出，在云平臺環(huán)境下，通過互信息對特征進行篩選后，將特征和標簽分別作為ELM的輸入和輸出進行訓練與測試，采用5折交叉驗證，獲得的精度最高可以達到93%，與在普通PC環(huán)境中相同特征數(shù)量的前提下進行比較可以發(fā)現(xiàn)其分類精度大致相同，說明CMI-Selection算法在分類精度方面具有可行性與有效性，它能夠保證提取的特征是有效的，具有較高的分類精度。

圖3 ELM在不同環(huán)境下的不同數(shù)據(jù)集上的分類精度

圖4 不同環(huán)境下的特征基因提取時間

從圖4中可以看出，由于云平臺的并行計算性能，其在保證較高分類精度的同時，相比于普通PC速度提高了4倍左右，并且這種提速會隨著服務器數(shù)量的增加變得更加明顯，從而為大數(shù)據(jù)學習節(jié)省了時間資源，說明了云平臺的高度并行化。

5 結(jié)束語

本文將傳統(tǒng)的特征提取方法同云計算平臺相結(jié)合，提出了一種基于云平臺的互信息最大化的特征提取方法，構(gòu)建了一個基于云平臺的特征過濾模型。該模型通過設(shè)置平臺中map任務的個數(shù)、劃分特征集的大小讓云平臺自動對基因數(shù)據(jù)集進行特征的篩選提取，提取后的特征用于訓練與測試。與普通單個PC相比，該模型在保證較高的分類精度的情況下，速度快，易于實現(xiàn)。實驗結(jié)果表明，基于云平臺的互信息最大化特征提取方法是正確、可行的，能夠快速提取特征，節(jié)省大量時間資源，是一種高效的基因特征提取系統(tǒng)。

1 Kang H N，Chen I M，Wilson C S．Gene expression classifiers for relapse-free survival and minimal residual disease improve risk classification and outcome prediction in pediatric B-precursor acute lymphoblastic leukemia.Blood,2010(115):1394~1405

2 任江濤，黃煥宇，孫婧昊．基于相關(guān)性分析及遺傳算法的高維數(shù)據(jù)特征選擇．計算機應用,2006，26(6)：1403~1405

3 裘國永，王娜，汪萬紫．基于互信息和遺傳算法的兩階段特征選擇方法．計算機應用研究,2012，29(8)：2903~2905

4 Peng H H,Long F H,Ding C.Feature selection based on mutual information:criteria of max-dependency,max-relevance,and min-redundancy.IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(8):1226~1238

5 Ding C,Peng H.Minimum redundancy feature selection from microarray gene expression data.Journals of Bioinformatics and Computational Biology,2005,3(2):185~205

6 王凌，陳震，危水根等．基于改進最大互信息法的MR切片圖像配準．生物醫(yī)學工程學雜志，2012，29(2)：201~205

7 楊虎，馬斌榮，任海萍等．基于最大互信息的人腦MR-PET圖像配準方法．北京生物醫(yī)學工程，2001，20(4)：246~251

8 張彾衛(wèi)，萬文強．基于云計算平臺的代價敏感集成學習算法研究．山東大學學報（工學版），2012,42(4)：19~23

9 Vouk M A．Cloud computing-issues,research and implem entations.Proceedings of ITI 2008,Dubrovnik，2008：79~120

10朱杰．云計算在基于貝葉斯分類的垃圾短信過濾中的研究與應用．電子科技大學碩士學位論文，2010

11王明怡．微陣列數(shù)據(jù)挖掘技術(shù)的研究．浙江大學博士學位論文，2004

12劉慶和，梁正友．一種基于信息增益的特征優(yōu)化選擇方法．計算機工程與應用，2011，47(12)

13 Hu Y， Loizou P C．Speech enhancement based on wavelet thresholding the multitaper spectrum．IEEE Transactions on Speech and Audio Processing，2004，12(1)：59~67

14戴元順．云計算技術(shù)簡述．信息通信技術(shù)，2010(2)