基因表達數(shù)據(jù)在鄰域關系中的特征選擇

陳玉明，吳克壽，李向軍

(1. 廈門理工學院 計算機科學與技術系，福建 廈門 361024； 2. 南昌大學 計算機科學與技術系，江西 南昌 330031)

美國人類基因組計劃(HGP)把基因組信息學定義為：它是一個學科領域，包含著基因組信息的獲取、處理、存儲、分配、分析和解釋的所有方面?；虮磉_數(shù)據(jù)分析的對象是在不同條件下，全部或部分基因的表達數(shù)據(jù)所構成的數(shù)據(jù)矩陣。通過對該數(shù)據(jù)矩陣的分析，可以回答一些生物學問題。隨著試驗技術及儀器的不斷改進和基因組數(shù)據(jù)的急劇增長，現(xiàn)代DNA微陣列或芯片技術產(chǎn)生的各種基因表達數(shù)據(jù)均規(guī)模龐大、內(nèi)容復雜。如何有效地分析利用這些數(shù)據(jù)成為生物信息學中的挑戰(zhàn)性課題。在基因表達數(shù)據(jù)分析中，基因的數(shù)目成千上萬，但往往只是很少一部分的關鍵基因影響樣本的分類，其他的基因往往是冗余的或者是不重要的。在設計基因表達數(shù)據(jù)分類器之前進行特征選擇，可以有效降低分類器的時間復雜度，提高分類精度。目前最常用的基因表達數(shù)據(jù)特征選擇方法主要有2類：基于過濾算法(filter)的選擇方法[1]與基于wrapper的選擇方法[2]?；趂ilter的基因表達數(shù)據(jù)特征選擇方法使用數(shù)據(jù)本身的內(nèi)在特性作為評價基因的準則，但通過filter選擇出來的若干個基因可能具有較強的相關性。基于wrapper的基因表達數(shù)據(jù)特征選擇方法根據(jù)分類器的某種性能來評價基因或基因子集的重要性，而基于wrapper方法在基因的選擇過程中反復調(diào)用分類算法，往往造成較高的時間復雜度。

粗糙集由波蘭科學家Pawlak于1982年提出[3]，用于處理不確定、不一致、不精確數(shù)據(jù)的數(shù)學理論工具。現(xiàn)已廣泛應用在人工智能、數(shù)據(jù)挖掘、機器學習等領域[4-7]。然而，Pawlak粗糙集只能處理離散化的數(shù)據(jù)，對于現(xiàn)實世界廣泛而大量存在的連續(xù)數(shù)據(jù)卻缺乏有效的處理能力?；虮磉_數(shù)據(jù)也往往都是連續(xù)的，目前大多數(shù)方法是將基因表達數(shù)據(jù)先進行離散化[8]，離散化過程必定會造成某種程度的信息丟失，并影響分類系統(tǒng)的分類精度。

1 鄰域關系

傳統(tǒng)粗糙集理論采用等價類形式化地表示知識分類。然而，等價類是基于離散型的數(shù)據(jù)形成的等價關系劃分而得到的，對于連續(xù)型的數(shù)據(jù)并不能構造合適的等價類。因此，下面引入鄰域關系處理連續(xù)型的基因表達數(shù)據(jù)，用于基因表達數(shù)據(jù)的特征選擇。

定義2 給定鄰域信息系統(tǒng)IS=(U,A,V,f,δ)，對于任一x,y∈U，B?A，B={a1,a2,...,an}，定義B上的距離函數(shù)DB(x,y)滿足：

1)DB(x,y)≥0，非負；

2)DB(x,y)=0，當且僅當x=y；

3)DB(x,y)=DB(y,x)，對稱；

4)DB(x,y)+DB(y,z)≥DB(x,z)。

式中：

DB(x,y)=

當p=1時，稱為曼哈頓距離，當p=2時，稱為歐氏距離。

2 基于鄰域關系的基因選擇方法

基于等價關系的信息熵、互信息、粗糙熵等概念度量了知識的粗細程度，也反映了決策系統(tǒng)中的分類能力大小，但主要處理離散型數(shù)據(jù)的決策系統(tǒng)，對于連續(xù)型的數(shù)據(jù)并不能夠直接處理。下面結合鄰域關系與鄰域類的定義，進一步定義了鄰域特征選擇概念，用于連續(xù)型的基因表達數(shù)據(jù)的特征選擇當中。同時，提出一種基于鄰域關系的啟發(fā)式基因表達數(shù)據(jù)特征選擇算法。

2.1 鄰域特征選擇

定義5 定義DT=(U,C∪D,V,f,δ)為一個鄰域決策表，其中C為條件特征，特征值為連續(xù)型的數(shù)據(jù)，鄰域閾值為δ，其鄰域劃分為U/NRδ(C)={X1,X2,...,Xm}，D為決策特征，決策特征是一些決策分類信息，為離散型的數(shù)據(jù)，以等價關系劃分為U/D={Y1,Y2,...,Yn}。

定義6 設DT=(U,C∪D,V,f,δ)為一個鄰域決策表，?B?C，X?U，記U/NRδ(B)={B1,B2,...,Bi}，則稱B*(X)δ=∪{Bi|Bi∈U/NRδ(B),Bi?X}為X關于B的鄰域下近似集，稱B*(X)δ=∪{Bi|Bi∈U/NRδ(B),Bi∩X≠?}為X關于B的鄰域上近似集。

定義7 設鄰域決策表DT=(U,C∪D,V,f,δ)，其中C為條件特征，特征值為連續(xù)型的數(shù)據(jù)，鄰域閾值為δ，D為決策特征，決策特征是一些決策分類信息，為離散型的數(shù)據(jù)。定義決策特征D對條件特征C的鄰域依賴度為γC(D)δ=|C*(D)δ|/|U|，其中|U|表示集合U的基數(shù)。

定義8 設鄰域決策表DT=(U,C∪D,V,f,δ)，對?b∈B?C，若γB(D)δ=γB-(D)δ，則稱b為B中相對于D是不必要的；否則稱b為B中相對于D是必要的。對?B?C，若B中任一元素相對于D都是必要的，則稱B相對于D獨立。

定義9 設鄰域決策表DT=(U,C∪D,V,f,δ)，若?B?C，γB(D)δ=γC(D)δ且B相對于D是獨立的，則稱B是選取的關鍵特征組，這一特征選取過程稱為鄰域特征選擇。

性質(zhì)1 設鄰域決策表DT=(U,C∪D,V,f,δ)，若B1?B2?...?C，則0≤γB1(D)δ≤γB2(D)δ≤...≤γC(D)δ≤1。

定義10 設鄰域決策表DT=(U,C∪D,V,f,δ)，?a∈C，R?C，定義a相對于R的特征重要度為Sign(a,R,D)=γR∪{a}(D)δ-γR(D)δ。

2.2 基于鄰域關系的基因選擇算法

性質(zhì)1表明鄰域依賴度具有單調(diào)性，因此可以采用刪除法或添加法進行特征選擇，基因表達數(shù)據(jù)可以表示成前面定義的鄰域決策表，依據(jù)上述鄰域特征選擇的定義，可設計如下基于鄰域關系的基因選擇算法。下面以定義10的特征重要度為啟發(fā)式信息設計了一種基于鄰域關系的基因選擇算法。

算法GSNRS(基于鄰域關系的基因選擇算法)

輸入：基因表達數(shù)據(jù)決策表DT=(U,C∪D,V,f,δ)；

輸出：DT的一個鄰域約簡R。

1)計算整個條件特征集C相對于決策特征D的鄰域依賴度為γC(D)δ。

2)R:=C。

3) 當γR(D)δ=γC(D)δ重復：

①對所有的a∈R計算特征重要度Sign(a,R,D);

②在R中選擇特征a滿足特征重要度最小；

③R:=R-{a}。

4) 輸出R。

在算法中，每次選擇特征重要度最小的特征，若去掉它后決策表的鄰域依賴度仍然不變，則可以去掉，否則保留下來，依次進行下去，直到得到一個條件特征子集，在其中去掉任何一個特征，決策表的鄰域依賴度都會改變，則算法結束，該特征子集即為所選取關鍵特征組。

3 實驗結果與分析

下面選用2個標準的基因表達數(shù)據(jù)集來驗證GSNRS算法的有效性。2個標準基因表達數(shù)據(jù)集分別為Lymphoma和Liver cancer。Lymphoma數(shù)據(jù)集包含了96個樣本，4 026個特征基因，其中54個Othertype子類和42個B-celllymphoma子類。Liver cancer數(shù)據(jù)集包含了156個樣本，1 648個基因，其中82個HCCs子類和74個nontumorlivers子類。實驗基因數(shù)據(jù)集如表1所示。

表1 基因表達數(shù)據(jù)集

在Lymphoma和Livercancer基因表達數(shù)據(jù)中分別采用文獻[9]中粗糙集的特征選擇算法TRS與本文鄰域特征選擇算法GSNRS進行比較。首先進行預處理，對于有缺失值的數(shù)據(jù)采用文獻[10]的方法進行完備化?；虮磉_數(shù)據(jù)集是連續(xù)型的數(shù)據(jù)，對于經(jīng)典粗糙集特征選擇算法，需要對其數(shù)據(jù)進行離散化，離散化過程采用文獻[8]中的方法進行。而本文GSNRS特征選擇算法，不需要離散化。設鄰域參數(shù)為δ=0.1，特征選擇結果如表2所示。

表2 基因數(shù)據(jù)集特征選擇結果

由表2可知，TRS算法在Lymphoma數(shù)據(jù)集中選擇出7個關鍵基因，在Liver cancer數(shù)據(jù)集中選擇出6個關鍵基因。GSNRS算法在Lymphoma數(shù)據(jù)集中選擇出6個關鍵基因，在Liver cancer數(shù)據(jù)集中選擇出5個關鍵基因。下面再比較2組基因的分類能力，分別針對選取的關鍵基因采用KNN，C5.0分類器進行分類實驗，并用留一交叉法檢驗分類精確率，實驗結果如表3所示。

表3 基因分類精確率

上述實驗結果表明，基于粗糙集的基因選擇方法和基于鄰域關系的基因選擇方法都能正確提取有效的基因?；卩徲蜿P系的基因選擇方法不需要離散化，而且由于避免了離散化過程的造成的信息丟失，提取的特征基因個數(shù)較少。在分類精度上，基于鄰域關系的基因選擇方法提取的基因優(yōu)于基于粗糙集的基因選擇方法提取的基因。

4 結束語

傳統(tǒng)粗糙集理論中的特征選擇方法往往難以處理連續(xù)性的基因表達數(shù)據(jù)，成為基因表達數(shù)據(jù)研究中的主要缺陷和障礙。本文針對傳統(tǒng)粗糙集理論中難以處理連續(xù)數(shù)據(jù)的缺點，在特征選擇中引入鄰域關系，定義了鄰域依賴度與鄰域特征選擇等概念，提出了一種基于鄰域關系的基因特征選擇方法。該特征方法不用對數(shù)據(jù)進行離散化，避免了信息損失，從而提高了被選擇基因的分類準確率。拓展了粗糙集理論的應用范圍，為基因表達數(shù)據(jù)分析技術提供了一種新的嘗試。

參考文獻:

[1]TIBSHIRANI R, HASTIE T, NARASHIMAN B, et al. Diagnosis of multiple cancer types by shrunken centroids of gene expression[C]//Nat’1 Academy of Sciences. [S.l.], USA, 2002: 6567-6572.

[2]KOHAVI R, JOHN G H. Wrappers for feature subset selection[J]. Artificial Intelligence, 1997, 97(1/2): 273-324.

[3]PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Science, 1982, 11(5): 341-356.

[4]BANERJEE M, MITRA S, BANKA H. Evolutinary-rough feature selection in gene expression data[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Application and Reviews, 2007, 37: 622-632.

[5]YANG Ming, YANG Ping. A novel condensing tree structure for rough set feature selection[J]. Neurocomputing, 2008, 71(4/5/6): 1092-1100.

[6]QIAN Yuhua, LIANG Jiye. Positive approximation: an accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174(9/10): 597-618.

[7]CHEN Yuming, MIAO Duoqian. A rough set approach to feature selection based on power set tree[J]. Knowledge-Based Systems, 2011, 24(2): 275-281.

[8]苗奪謙. Rough set理論中連續(xù)屬性的離散化方法[J]. 自動化學報, 2001, 27(3): 296-302.

MIAO Duoqian. A new method of discretization of continuous attributes in rough sets [J]. Acta Automatica Sinica, 2001, 27(3): 296-302.

[9]王國胤. Rough 集理論與知識獲取[M]. 西安: 西安交通大學出版社, 2001:24-28.

[10]GRZYMALA-BUSSE J W. Handling missing attribute values[M]. [S.l.]: Springer, 2005: 37-57.