基因表達數據在鄰域關系中的特征選擇

陳玉明，吳克壽，李向軍

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

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

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

1 鄰域關系

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

定義2 給定鄰域信息系統IS=(U,A,V,f,δ)，對于任一x,y∈U，B?A，B={a1,a2,...,an}，定義B上的距離函數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 基于鄰域關系的基因選擇方法

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

2.1 鄰域特征選擇

定義5 定義DT=(U,C∪D,V,f,δ)為一個鄰域決策表，其中C為條件特征，特征值為連續型的數據，鄰域閾值為δ，其鄰域劃分為U/NRδ(C)={X1,X2,...,Xm}，D為決策特征，決策特征是一些決策分類信息，為離散型的數據，以等價關系劃分為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為條件特征，特征值為連續型的數據，鄰域閾值為δ，D為決策特征，決策特征是一些決策分類信息，為離散型的數據。定義決策特征D對條件特征C的鄰域依賴度為γC(D)δ=|C*(D)δ|/|U|，其中|U|表示集合U的基數。

定義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是選取的關鍵特征組，這一特征選取過程稱為鄰域特征選擇。

性質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 基于鄰域關系的基因選擇算法

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

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

輸入：基因表達數據決策表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滿足特征重要度最?。?/p>

③R:=R-{a}。

4) 輸出R。

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

3 實驗結果與分析

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

表1 基因表達數據集

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

表2 基因數據集特征選擇結果

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

表3 基因分類精確率

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

4 結束語

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

參考文獻:

[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理論中連續屬性的離散化方法[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.