陳玉明，吳克壽，李向軍

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

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

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

1 鄰域關(guān)系

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

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

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

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

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

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

式中：

DB(x,y)=

當(dāng)p=1時(shí)，稱為曼哈頓距離，當(dāng)p=2時(shí)，稱為歐氏距離。

2 基于鄰域關(guān)系的基因選擇方法

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

2.1 鄰域特征選擇

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

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

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

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

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

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

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

2.2 基于鄰域關(guān)系的基因選擇算法

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

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

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

輸出：DT的一個(gè)鄰域約簡(jiǎn)R。

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

2)R:=C。

3) 當(dāng)γR(D)δ=γC(D)δ重復(fù)：

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

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

③R:=R-{a}。

4) 輸出R。

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

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

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

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

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

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

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

表3 基因分類精確率

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn):

[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]. 自動(dòng)化學(xué)報(bào), 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]王國(guó)胤. Rough 集理論與知識(shí)獲取[M]. 西安: 西安交通大學(xué)出版社, 2001:24-28.

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