基于Ｐ－ｔｒｅｅ的多決策樹基因表達(dá)數(shù)據(jù)分類

黃　金　石永昆

摘要：提出基于P-tree的多決策樹分類基因表達(dá)數(shù)據(jù)方法PTMDT(P-tree multi-decision tree)。

關(guān)鍵詞：基因表達(dá)分類P-tree

中圖分類號(hào)TP311.132.3文獻(xiàn)標(biāo)識(shí)碼A文章編號(hào)：1002-2422(2007)03-0050-02

使用The Peano Count Tree(P-tree)結(jié)構(gòu)和的邏輯運(yùn)算操作，快速地構(gòu)造出基因表達(dá)數(shù)據(jù)的決策樹，用于基因表達(dá)數(shù)據(jù)的分類。實(shí)驗(yàn)結(jié)果表明PTMDT方法不但可以取得良好的分類精確度，而且在計(jì)算速度方面遠(yuǎn)遠(yuǎn)好于其它方法。

1基因表達(dá)數(shù)據(jù)的裁減和離散化

1．1基因表達(dá)數(shù)據(jù)的裁減

基因表達(dá)數(shù)據(jù)是通過基因芯片實(shí)驗(yàn)獲得的。通常基因表達(dá)數(shù)據(jù)以矩陣形式保存，矩陣第i行對(duì)應(yīng)于第i個(gè)基因，第i列對(duì)應(yīng)于第j個(gè)實(shí)驗(yàn)樣本，而矩陣的每個(gè)元素aij記錄了第i個(gè)基因在第j個(gè)樣品中的表達(dá)水平。

在基因數(shù)據(jù)中，有一部分基因表現(xiàn)的特征在不同類別中差別不明顯，被稱為不相關(guān)基因，因?yàn)椴幌嚓P(guān)基因?qū)Ψ诸惒黄鹱饔茫钥梢圆脺p掉這些不相關(guān)基因。具體裁減方法是：先把一個(gè)基因的表達(dá)數(shù)據(jù)按照已知類別分組，分別計(jì)算每組數(shù)據(jù)的期望和方差。然后計(jì)算期望的最大值和最小值的差值，如果這個(gè)基因各個(gè)類別的方差值都小于這個(gè)差值，那么認(rèn)為這個(gè)基因的特征表現(xiàn)在不同類別下是明顯的，要保留這個(gè)基因，否則認(rèn)為是不相關(guān)基因，把它裁減掉。

1．2離散基因表達(dá)數(shù)據(jù)

為了利用P-tree結(jié)構(gòu)建立決策樹，首先需要對(duì)給定的基因表達(dá)數(shù)據(jù)進(jìn)行離散化處理。例如基因表達(dá)數(shù)據(jù)，根據(jù)對(duì)數(shù)據(jù)大小范圍的觀測(cè)，把它們離散成I_o、l₁、I₂、I₃四個(gè)部分，I_o=[0，1]、I₁=[1，2]、1₂=[2，3]、1₃=[3，4]，每一部分用一個(gè)二進(jìn)制比特串表示，設(shè)I_o=00，I₁=01，I₁=10，I₃=11。通過這樣的離散化處理，表l中的基因表達(dá)數(shù)據(jù)轉(zhuǎn)變成表2中的形式，這樣就可使用P-tree結(jié)構(gòu)表示基因表達(dá)數(shù)據(jù)了。

PTMDT方法基于P-tree結(jié)構(gòu)，結(jié)合決策樹實(shí)現(xiàn)了對(duì)基因表達(dá)數(shù)據(jù)的分類。使用P-tree結(jié)構(gòu)的目的主要有兩點(diǎn)。第一，使用P-tree結(jié)構(gòu)計(jì)算信息增益時(shí)只需使用P-tree的AND操作，AND操作速度快，減少了建立決策樹的時(shí)間；第二，在使用P-tree結(jié)構(gòu)建立決策樹的過程中，不需要重復(fù)掃描數(shù)據(jù)集獲得決策樹中間結(jié)點(diǎn)包括的子數(shù)據(jù)集，這是因?yàn)楹蜆渲薪Y(jié)點(diǎn)相對(duì)應(yīng)的P-tree就表示了這個(gè)結(jié)點(diǎn)包含的數(shù)據(jù)集，即P-tree中表示為1比特的位置對(duì)應(yīng)的數(shù)據(jù)就是被該結(jié)點(diǎn)包含的數(shù)據(jù)。

決策樹是數(shù)據(jù)挖掘分類常用的一種方法，決策樹中的每個(gè)非葉結(jié)點(diǎn)選擇具有最大信息增益的屬性作為測(cè)試屬性。使用P-tree表示的數(shù)據(jù)，可以通過如下方法計(jì)算一個(gè)屬性的信息增益值。假設(shè)B_o是類別屬性，B₁,B₂,B₃是非類別屬性．決策樹中的每個(gè)結(jié)點(diǎn)都存儲(chǔ)相應(yīng)的決策路徑信息，即存儲(chǔ)從樹根結(jié)點(diǎn)到本結(jié)點(diǎn)所經(jīng)過的決策屬性和相應(yīng)的屬性值，如圖l中結(jié)點(diǎn)N09的決策路徑是“B₂,,0011,B₃,1000”。使用RC表示P-tree根結(jié)點(diǎn)的數(shù)值。對(duì)于給定決策路徑B[1]，V[l]，B[2]，V[2]，…，B[t]，V[t]的結(jié)點(diǎn)N，結(jié)點(diǎn)N對(duì)應(yīng)的P-tree使用下面的公式計(jì)算結(jié)點(diǎn)N的I(P)

在構(gòu)造決策樹時(shí)，首先計(jì)算每個(gè)基因的信息增益值，選擇具有最大信息增益的基因作為決策樹根結(jié)點(diǎn)的測(cè)試屬性。根據(jù)這個(gè)基因所有的屬性值，把結(jié)點(diǎn)劃分為多個(gè)孩子結(jié)點(diǎn)，然后遞歸地計(jì)算每個(gè)孩子結(jié)點(diǎn)。

針對(duì)單決策樹分類精度低的問題，PTMDT方法采用了多決策樹分類方法。構(gòu)建多棵決策樹時(shí)對(duì)樹根結(jié)點(diǎn)決策基因的選擇是依照從最優(yōu)逐漸遞減的原則，即第一棵決策樹選擇信息增益最大的基因作為根結(jié)點(diǎn)的決策基因，第二棵決策樹選擇信息增益第二大的基因作為根結(jié)點(diǎn)的決策基因，以此類推。不同的決策樹對(duì)同一測(cè)試數(shù)據(jù)可能得到不同的分類結(jié)果，取出現(xiàn)次數(shù)最多的類型作為測(cè)試數(shù)據(jù)的分類結(jié)果。

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

為了驗(yàn)證PTMDT方法的有效性，實(shí)驗(yàn)應(yīng)用small roundrole-cell tumors(SRBCT)數(shù)據(jù)集進(jìn)行，其中包含63個(gè)訓(xùn)練樣本和25個(gè)測(cè)試樣本，每個(gè)樣本包含2303個(gè)基因表達(dá)值，分成四個(gè)類別：EWS(23)，RMS(20)，NB(12)，BL(8)。

對(duì)63個(gè)訓(xùn)練樣本，PTMDT方法的訓(xùn)練精度是100％。表3是用PTMDT方法對(duì)20個(gè)測(cè)試樣本進(jìn)行多決策樹分類的時(shí)間和精確度，其中運(yùn)行時(shí)間是指PTMDT方法開始運(yùn)行直到得到最終分類結(jié)果總共花費(fèi)的時(shí)間。

給出了PTMDT方法與基于SVM的OVA方法、TSS方法的運(yùn)行時(shí)間和分類精確度的比較。從比較結(jié)果可知PTMDT算法在運(yùn)行時(shí)間方面明顯優(yōu)于OVA和TSS方法，在精確度方面接近TSS方法，略高于OVA方法。

4結(jié)束語

文中提出了一個(gè)基因表達(dá)數(shù)據(jù)分類方法PTMDT。利用p-tree結(jié)構(gòu)，使得構(gòu)建決策樹的時(shí)間大大縮短，并結(jié)合多決策樹技術(shù)，提高了分類的精確度。從實(shí)驗(yàn)結(jié)果可看出，PT-MDT方法與目前已知優(yōu)秀分類基因表達(dá)數(shù)據(jù)方法相比，具有良好的分類精確度，并且運(yùn)行速率較快。