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

（1.中國計(jì)量學(xué)院信息工程學(xué)院 杭州 310018；2.中國計(jì)量學(xué)院機(jī)電工程學(xué)院 杭州 310018）

1 引言

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

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

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

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

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

2 互信息與基因篩選

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

熵用來表示任何一種能量在空間中分布的均勻程度，其大小跟能量分布均勻程度有關(guān)，能量越不確定且分布越均勻，熵就越大[12]。信息論中的“信息熵”是香農(nóng)[13]在進(jìn)行信息處理時提出的概念。在互信息最大化方法中，信息熵主要用來衡量一個隨機(jī)變量取值的重要性程度，以特征能夠?yàn)榉诸悗矶嗌傩畔楹饬繕?biāo)準(zhǔn)，帶來的信息越多，該特征越重要。

假設(shè)X來自于一個集合S，且X是一個離散隨機(jī)變量。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)定義為：

在基因篩選過程中，互信息通常用來表示計(jì)算特征與特征之間的關(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相互獨(dú)立。

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

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

則最大互信息量為：

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

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

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

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

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

圖1 MapReduce工作過程

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

圖2 服務(wù)器之間相互通信的過程

HBase則對應(yīng)于Google的BigTable。

Hadoop的特點(diǎn)介紹如下。

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

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

·擴(kuò)容能力：能非常容易地增添計(jì)算存儲資源。

·效率高。

3.2 基于MapReduce的特征過濾

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

5 結(jié)束語

本文將傳統(tǒng)的特征提取方法同云計(jì)算平臺相結(jié)合，提出了一種基于云平臺的互信息最大化的特征提取方法，構(gòu)建了一個基于云平臺的特征過濾模型。該模型通過設(shè)置平臺中map任務(wù)的個數(shù)、劃分特征集的大小讓云平臺自動對基因數(shù)據(jù)集進(jìn)行特征的篩選提取，提取后的特征用于訓(xùn)練與測試。與普通單個PC相比，該模型在保證較高的分類精度的情況下，速度快，易于實(shí)現(xiàn)。實(shí)驗(yà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ù)特征選擇．計(jì)算機(jī)應(yīng)用,2006，26(6)：1403~1405

3 裘國永，王娜，汪萬紫．基于互信息和遺傳算法的兩階段特征選擇方法．計(jì)算機(jī)應(yīng)用研究,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 王凌，陳震，危水根等．基于改進(jìn)最大互信息法的MR切片圖像配準(zhǔn)．生物醫(yī)學(xué)工程學(xué)雜志，2012，29(2)：201~205

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

8 張彾衛(wèi)，萬文強(qiáng)．基于云計(jì)算平臺的代價敏感集成學(xué)習(xí)算法研究．山東大學(xué)學(xué)報（工學(xué)版），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朱杰．云計(jì)算在基于貝葉斯分類的垃圾短信過濾中的研究與應(yīng)用．電子科技大學(xué)碩士學(xué)位論文，2010

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

12劉慶和，梁正友．一種基于信息增益的特征優(yōu)化選擇方法．計(jì)算機(jī)工程與應(yīng)用，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戴元順．云計(jì)算技術(shù)簡述．信息通信技術(shù)，2010(2)