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

黃　金　石永昆

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

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

中圖分類號TP311.132.3文獻標識碼A文章編號：1002-2422(2007)03-0050-02

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

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

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

基因表達數(shù)據(jù)是通過基因芯片實驗獲得的。通?；虮磉_數(shù)據(jù)以矩陣形式保存，矩陣第i行對應(yīng)于第i個基因，第i列對應(yīng)于第j個實驗樣本，而矩陣的每個元素aij記錄了第i個基因在第j個樣品中的表達水平。

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

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

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

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

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

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

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

3實驗結(jié)果

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

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

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

4結(jié)束語

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