許 明，鄭鷺斌，謝彥麒，陳玉明

(廈門理工學院計算機與信息工程學院，福建 廈門 361024)

0 引言

隨著基因微陣列技術的提高，基因表達數(shù)據(jù)快速增長，基因數(shù)據(jù)分析與處理技術已引起學者的廣泛關注[1-3]. 然而，基因表達數(shù)據(jù)集呈現(xiàn)高維、小樣本和不確定性的特點，已經(jīng)成為基因分析與處理技術的發(fā)展瓶頸，如何從高維基因數(shù)據(jù)中選取有效且區(qū)分度高的少量基因，是基于基因表達數(shù)據(jù)進行癌癥腫瘤分類的科學問題之一. 通過基因選擇，剔除與腫瘤分類無關的冗余基因，獲得精簡的基因子集，不僅降低分類器設計的計算復雜度，還可以提高分類器的分類精度.

基因選擇也稱特征基因子集選擇，是指從全部基因中選取一個特征基因子集，使構造出來的分類模型更優(yōu)[4]. 依據(jù)評價函數(shù)的不同，常見的基因選擇算法主要包括Filter方法和Wrapper方法兩大類[5]. 其中Filter方法依據(jù)度量評價函數(shù)，篩選出高區(qū)分度的特征基因. 其算法運行速度較快，在不同分類算法之間的推廣能力較強，但評估函數(shù)與學習算法的性能偏差較大. 篩選評估函數(shù)主要有相關系數(shù)[6]、距離度量[7]、信息熵度量[8]等. 而Wrapper方法的特點是采用具體的分類算法，選取分類精度最大的特征基因[9]. 該方法分類準確率較高，選擇的基因子集規(guī)模較小，但計算復雜度高，不利于大數(shù)據(jù)集，而且存在過擬合的現(xiàn)象.

依據(jù)搜索策略的不同，基因選擇算法主要分為完全搜索、啟發(fā)式搜索和隨機搜索. 完全搜索策略不具備可行性，只適應于非常小的數(shù)據(jù)集. 因此，大部分算法采用啟發(fā)式的搜索策略. 啟發(fā)式的方法搜索速度快，適用于高維大數(shù)據(jù)集，卻易陷入局部解. 隨機搜索方法主要包括模擬退火[10]、遺傳算法[1]、蟻群優(yōu)化算法[11]等. 蟻群算法[12]是在20世紀90年代初，由意大利學者Dorigo提出的一種群智能算法. 它具有分布性、正反饋、健壯性及全局尋優(yōu)等特點[13-15]. 波蘭數(shù)學家Pawlak[16]提出了粗糙集理論，能夠處理不一致、不精確、不確定數(shù)據(jù). 粗糙集理論已經(jīng)在基因選擇、機器學習、數(shù)據(jù)挖掘、圖形圖像、大數(shù)據(jù)、天氣預測等諸多領域得到廣泛應用[17-18]. 粗糙集中的特征選擇涉及特征重要度的計算，主要的度量特征工具有信息熵[19]、粗糙熵[20]與知識粒度[21]. 然而，這些度量大都基于離散型的數(shù)據(jù)集，對于連續(xù)型的基因數(shù)據(jù)集并不適用.

為此，針對基因數(shù)據(jù)集的高維、連續(xù)及不確定性特點，提出融合Filter方法與Wrapper方法的混合基因選擇方法. 該方法采用鄰域粗糙集?；驍?shù)據(jù)，定義鄰域熵構造Filter篩選函數(shù)，對基因進行預選擇，然后采用鄰域粗糙集對預選擇的基因進行特征選擇，同時引入蟻群優(yōu)化算法，獲取個數(shù)最小的特征基因子集. 最后，對選取的特征子集采用經(jīng)典分類算法測試其分類效果.

1 鄰域粗糙集模型與基因選擇

Pawlak粗糙集模型主要處理離散型的數(shù)據(jù)集，利用等價關系對對象集合進行劃分，形成等價類知識. 針對連續(xù)型的基因表達數(shù)據(jù)集，需要預先進行離散化，而離散化過程不可避免降低了分類精度. 為此，針對連續(xù)型的基因數(shù)據(jù)，采用鄰域粗糙集模型[22]進行鄰域?；?，構造參數(shù)化的鄰域類，用于基因子集選擇.

定義2給定基因信息系統(tǒng)S=(U,A,V,f,δ)，對于任一樣本x,y∈U, 基因子集B?A,B={a1,a2, …,an}，定義B上的距離度量函數(shù)DB(x,y)為：

其中: 當p=1時，稱為曼哈頓距離； 當p=2時，稱為歐氏距離.

定義4設S=(U,A,V,f,δ)為一基因信息系統(tǒng)，δ為鄰域參數(shù)，在基因子集B?A上定義鄰域關系NRδ(B)：

U/NRδ(B)稱為論域U的一個鄰域覆蓋.

定義5定義T=(U,C∪D,V,f,δ)為一個基因分類表，其中U表示病人樣本集；C表示基因集，C值為連續(xù)型的基因表達數(shù)據(jù)； 鄰域參數(shù)為δ∈[0, 1]，其鄰域覆蓋為U/NRδ(C)={X1,X2, …,Xm}；D是腫瘤分類特征，其為離散型的分類數(shù)據(jù)，腫瘤分類特征表示癌癥腫瘤的分類信息，其等價類劃分為U/D={Y1,Y2, …,Yn}.

定義6設T=(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的鄰域上近似集.

鄰域上、下近似集組成的序對〈B*(X)δ,B*(X)δ〉用來逼近X確定集合，稱為X的鄰域粗糙集.

定義8設基因分類表T=(U,C∪D,V,f,δ)，?b∈B?C，γB(D)δ=γB-(D)δ，則b是B中冗余的基因； 否則b為B中必要的基因. ?B?C，若?b∈B都是必要的基因，則稱B相對于D是獨立的.

定義9設基因分類表T=(U,C∪D,V,f,δ)，?B?C，γB(D)δ=γC(D)δ且B相對于D是獨立的，則稱B是C相對于D的特征基因組.

特征基因組是區(qū)分度較高的基因組成的集合，基因選擇的過程就是尋找特征基因組的過程. 在一個基因分類系統(tǒng)中，特征基因組存在多個，其中基因個數(shù)最小的特征基因組稱為最小特征基因組.

2 基于鄰域熵與蟻群優(yōu)化的屬性約簡

在鄰域?；蟮幕驍?shù)據(jù)集中引入鄰域熵的定義，度量基因數(shù)據(jù)的不確定性，并證明鄰域熵的單調性，用于基于鄰域粗糙集模型的基因選擇當中. 以鄰域熵作為啟發(fā)式信息，引入蟻群優(yōu)化算法，進一步設計了基于鄰域熵與蟻群優(yōu)化的基因選擇算法.

2.1 鄰域熵的定義及單調性原理

其中: |·|表示集合當中元素的個數(shù).

定理2設S=(U,A,V,f,δ)為一個基因信息系統(tǒng)，若Q?P?A，則Hδ(Q)≥Hδ(P).

由

可知

由

可知

因此，Hδ(Q)≥Hδ(P)成立.

定理2表明鄰域熵具有單調性，隨著基因的增加單調遞減，因此可用來度量基因信息系統(tǒng)的不確定性.

2.2 基于鄰域熵的基因預選擇

通過基因陣列技術得到大量基因的表達值，基因個數(shù)成千上萬，其中多數(shù)基因與腫瘤分類相關性不大，對腫瘤的分類貢獻也小. 定理2證明了基因個數(shù)的增減與鄰域熵的大小存在著單調遞減的關系. 鄰域熵越小，其不確定增大，該基因則更重要. 由此，先采用基于鄰域熵的過濾法對基因進行預選擇，該方法按照鄰域熵從小到大進行排序，選擇前面n個鄰域熵最小的基因作為預選特征基因組. 然后，提出基于蟻群優(yōu)化的鄰域粗糙集基因選擇方法，對預選擇的n個基因進行最小特征基因組的選取. 考慮到后續(xù)基因選擇的算法運行時間，實驗中n取值為100，即選擇前面100個鄰域熵最小的基因作為預選特征基因組.

2.3 基于蟻群優(yōu)化的基因選擇

科學家通過對螞蟻覓食行為的觀察與研究，發(fā)現(xiàn)螞蟻在覓食過程中會釋放信息素，當螞蟻經(jīng)過一條路徑時，其信息素和螞蟻的數(shù)量成正比，后面尾隨的螞蟻選擇該路徑的概率就更大，最后收斂到最短路徑. Jensen[23]將蟻群優(yōu)化算法用于求解特征選擇問題. 為了加快搜索的速度，在蟻群的搜索過程中增加啟發(fā)式信息.

1) 基于鄰域熵的啟發(fā)式信息. 下面定義基于鄰域熵與分類精度加權的特征基因重要度概念，并在基于蟻群優(yōu)化的基因選擇過程中作為啟發(fā)式信息.

定義11設基因分類表T=(U,C∪D,V,f,δ)，?a∈C，R?C，設t時刻，某只螞蟻已選擇了基因組R(處于i基因位置)，接下去按照啟發(fā)信息選擇a基因(處于j基因位置)，定義啟發(fā)信息為a相對于基因組R的特征基因重要度，表示為：

ηij(t)=|MR∪{a}(D)δ|-|MR(D)δ|

其中:MR(D)δ=γR(D)δ·(1-Hδ(R))； |·|表示集合當中元素的個數(shù).

2) 信息素的計算. 當某只螞蟻經(jīng)過一條路徑時，其信息素隨著螞蟻的數(shù)量而增強. 設t時刻(第t次迭代)，共有n只螞蟻經(jīng)過基因i到基因j上的路徑，則該路徑上的信息素計算如下：

其中:q為常數(shù)；R(t)表示t時刻已選取的基因組(暫時的全局最優(yōu)解).

3) 局部解的求解 . 在蟻群優(yōu)化算法中，每只螞蟻分別構建一個局部解，然后根據(jù)蟻群的正反饋機制獲得全局最優(yōu)解. 最初螞蟻隨機初始化選擇某個基因，而后根據(jù)計算的概率選擇基因，其概率計算公式定義為：

其中:k表示某只螞蟻，t表示某次迭代；τij和ηij分別表示基因i到基因j路徑上的信息素和啟發(fā)信息，以特征基因重要度作為啟發(fā)信息； 參數(shù)α>0和β>0分別表示信息素和啟發(fā)信息的重要性程度. 信息素體現(xiàn)全局搜索的信息，啟發(fā)式信息體現(xiàn)局部搜索的信息. 參數(shù)α和β取值范圍為0～1，其中α=1-β. 若α>β，則螞蟻選擇基因路徑時主要考慮全局因素，那么收斂的時間較長，更容易獲得全局解； 反之，則主要考慮局部因素，收斂的速度快，但可能更容易陷入局部解； allowedk表示可供選擇的基因.

4) 信息素更新規(guī)則. 當所有的螞蟻都分頭搜索到一個局部解后，則一次迭代完成，相鄰接基因邊的信息素需要更新，其更新規(guī)則為:

τij(t+1)=ρτij(t)+Δτij(t)

其中:t表示迭代次數(shù)，τij(t)表示t時刻基因i到基因j邊的信息素；ρ(0<ρ<1)為常量，代表信息素的揮發(fā)程度； Δτij(t)表示新增加的揮發(fā)信息素總量.

5) 搜索停止條件. 螞蟻搜索過程停止的條件為：

a) 當γRk(D)δ=γC(D)δ，則找到了一個局部解，Rk為表示某個基因子集.

b) 若某只螞蟻找的局部集的基數(shù)大于全局最優(yōu)解基因子集的基數(shù)，則該螞蟻就停止搜索，否則，該基因子集作為暫時的全局最優(yōu)解.

c) 當達到最大迭代次數(shù)或所有的螞蟻搜索都停止后，則算法終止，輸出全局最優(yōu)解； 否則，更新信息素，開始下次迭代.

2.4 基于鄰域熵與蟻群優(yōu)化的基因選擇算法

以鄰域熵為啟發(fā)信息，根據(jù)蟻群優(yōu)化的原理，設計基于鄰域熵與蟻群優(yōu)化的基因選擇算法，其算法步驟描述如下：

算法1. NEACOGS(neighborhood entropy and ACO based gene selection).

輸入：經(jīng)過預選擇后的基因分類系統(tǒng)T′=(U,C∪D,V,f,δ)，最大迭代次數(shù)maxcycle，參數(shù)α.

輸出：最小特征基因組Gmin和其基數(shù)Lmin.

步驟1 系統(tǒng)初始化Gmin=C，Lmin=|C|.

步驟2 計算基因分類系統(tǒng)的分類精度γC(D)δ|POSC(D)δ|/|U|.

步驟3 若t

步驟3.1 構造k只螞蟻，Gk=Φ；

步驟3.2 初始化k只螞蟻，讓其隨機選擇某個基因ak，Gk=Gk∪ak；

步驟3.3 每只螞蟻分布循環(huán)執(zhí)行步驟3.3.1-3.3.2：

步驟3.3.2 若γGk(D)δ=γC(D)δ或者|Gk|≥Lmin，則第k只螞蟻停止搜索；

步驟3.4 若γGk(D)δ=γC(D)δ并且|Gk|≥Lmin，則Gmin=Gk，Lmin=|Gk|；

步驟3.5 根據(jù)公式τij(t+1)=ρτij(t)+Δτij(t)更新信息素.

步驟4 輸出最優(yōu)基因子組Gmin和其基數(shù)Lmin.

蟻群優(yōu)化搜索策略具有很好的全局尋優(yōu)能力，該算法雖然不能保證找到最小特征基因組，但大部分情況下能夠找到最小特征基因組. 算法NEACOGS的時間復雜度主要涉及鄰域類的計算，文獻[24]采用桶裝排序將鄰域類的計算降為線性，有效降低了算法的時間復雜度. 除了鄰域類的計算之外，外層循環(huán)還有迭代次數(shù)和螞蟻個數(shù). 因此，算法NEACOGS的時間復雜度為O(k×t×m×n). 其中，k為螞蟻數(shù)；t為迭代次數(shù)；m為基因個數(shù)；n為樣本個數(shù).

3 實驗分析

為驗證該算法的有效性，實驗中采用兩個基因數(shù)據(jù)集，分別為Lymphoma和Liver cancer. 數(shù)據(jù)集Lymphoma有96個樣本，4 026個基因. 其中, B-celllymphoma類別的樣本42個，Other type類別的樣本54個. 數(shù)據(jù)集Liver cancer有156個樣本，1 648個基因. 其中, HCCs類別的樣本82個，Nontumor livers類別的樣本74個. 基因數(shù)據(jù)集的具體信息描述如表1所示.

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

3.1 數(shù)據(jù)預處理與預選擇

數(shù)據(jù)預處理主要是對缺失數(shù)據(jù)的補齊和對原始數(shù)據(jù)的標準化. 對于原始數(shù)據(jù)中存在缺失的情況，實驗中采用均值補齊缺失的數(shù)據(jù)，并采用如下公式對原始基因數(shù)據(jù)進行標準化，將數(shù)據(jù)標準化為[0, 1]區(qū)間：

其中:gij表示編號為i的病人樣本在第j個基因上的基因表達值； max(gj)、min(gj)分別表示第j個基因上的最大、最小表達值. 基因數(shù)據(jù)經(jīng)過標準化后，為[0, 1]區(qū)間連續(xù)型的數(shù)據(jù). 基因個數(shù)龐大，往往成千上萬. 實驗中先進行預選擇，計算每個基因的鄰域熵值，并按照鄰域熵值從小到大排序，選取前面100個基因做為預選擇后的基因組.

3.2 實驗結果與分析

實驗過程采用文獻[25]中基于粗糙集的特征選擇算法TRS、文獻[26]中基于鄰域的特征選擇算法NRS以及本研究算法NEACOGS進行比較. 對于經(jīng)典粗糙集特征選擇算法TRS的離散化過程采用文獻[27]中的方法，而基于鄰域的特征選擇算法NRS與算法NEACOGS，不需要離散化，但需給定鄰域參數(shù)，實驗中設鄰域參數(shù)為δ=0.1. 本研究算法實驗中螞蟻個數(shù)設定為預選擇基因組中基因個數(shù)的三分之一，為k=33，最大迭代次數(shù)maxcycle=100，權重參數(shù)α=0.3. 兩個基因數(shù)據(jù)集經(jīng)過預選擇后，都保留了100個基因，在此基礎上采用3種不同的特征選擇算法進行基因選擇，實驗結果如表2所示.

表2 基因選擇實驗結果

由表2可知，TRS算法在Lymphoma數(shù)據(jù)集中選擇的基因子集含有7個基因，在Liver cancer數(shù)據(jù)集中選擇基因子集含有6個基因. NRS算法在Lymphoma數(shù)據(jù)集中選擇的基因子集包括了6個基因，在Liver cancer數(shù)據(jù)集中選擇的基因子集包括5個基因. 而本研究算法在Lymphoma數(shù)據(jù)集中選擇出5個特征基因，在Liver cancer數(shù)據(jù)集中也選擇出5個特征基因. 從時間上比較，可知NRS算法與TRS算法比較接近，TRS略好于NRS. 這兩個算法都是采用啟發(fā)式搜索一遍，找到次優(yōu)解. 而蟻群算法是多次迭代，因此NEACOGS算法的時間復雜度較高，但是更容易找到最優(yōu)解.

下面再比較被選基因子集的分類能力，分別采用KNN、C5.0分類器進行分類實驗，并用留一交叉法檢驗分類正確率，實驗結果如表3所示.

表3 基因分類精度

上述實驗結果表明，基于經(jīng)典粗糙集的基因選擇方法(TRS)、基于鄰域關系的基因選擇方法(NRS)和基于鄰域熵與蟻群優(yōu)化的基因選擇方法(NEACOGS)都能正確提取有效的基因子集. 在NRS和NEACOGS算法中不需要離散化，由于避免了離散化過程造成的信息丟失，提取的特征基因個數(shù)較少. 而NEACOGS算法進一步采用了蟻群優(yōu)化的搜索策略，得到了更小的基因子集. 通過在三種算法選取的基因子集上分別進行分類實驗，實驗結果表明都取得了較好的分類精度，而且分類精度相差較小，主要是因為三種算法都采用了基于鄰域熵篩選后的數(shù)據(jù)集.

4 結論

本研究重點分析了基因分類中的關鍵問題——基因選擇方法，提出了基于鄰域熵與蟻群優(yōu)化的基因選擇方法，并在2個基因表達數(shù)據(jù)集上進行了實驗. 首先，針對傳統(tǒng)粗糙集特征選擇方法難以處理連續(xù)型基因數(shù)據(jù)的缺點，引入鄰域粗糙集模型，定義鄰域熵度量數(shù)據(jù)的不確定性，對高維基因數(shù)據(jù)集進行篩選，大量減少基因個數(shù). 然后，在鄰域粗糙集基因選擇理論的框架中引入蟻群優(yōu)化搜索策略，提出基于鄰域熵與蟻群優(yōu)化的基因選擇，并給出了適用于特征基因選擇的具體算法. 該算法充分利用鄰域熵度量不確定性數(shù)據(jù)方面的優(yōu)勢，定義基于鄰域熵的特征基因重要度作為啟發(fā)式信息，加速算法收斂過程，并發(fā)揮蟻群優(yōu)化算法的全局尋優(yōu)性能，獲取最優(yōu)基因子集. 目前，采用蟻群優(yōu)化與鄰域粗糙集融合的方法進行特征基因選擇的研究還很少見，本研究拓展了粗糙集理論研究的應用范圍，為基因選擇研究提供了一條新的途徑.

[1] LI S T, WU X X, HU X Y. Gene selection using genetic algorithm and support vectors machines[J]. Soft Computing, 2008, 12(7): 693-698.

[3] 張軍英, WANG Y J, KHAN J, 等. 基于類別空間的基因選擇[J]. 中國科學(E 輯), 2003, 33(12): 1 125-1 137.

[4] DASH M, LIU H. Feature selection forclassification[J]. Intelligent Data Analysis, 1997, 1 (1): 131-156.

[5] SAEYS Y, INZA I, LARRANAGA P. A review of feature selection techniques inbioinformatics[J]. Bioinformatics, 2007, 23(19): 2 507-2 517.

[6] GUYON I, ELISSEEFF A. An introduction to variable and featureselection[J]. Journal of Machine Learning Research, 2003, 3(6): 1 157-1 182.

[7] KIRA K, RENDELL L A. The feature selection problem: traditional methods and a new algorithm[C]//Proceedings of the Tenth National Conference on Artificial Intelligence. San Jose: AAAI, 1992: 129-134.

[8] MIAO D Q, HOU L. A comparison of rough set methods and representative inductive learningalgorithms[J]. Fundamenta Informaticae, 2004, 59 (2/3): 203-219.

[9] KOHAVI R. Feature subset selection using the wrapper method: overfitting and dynamic search space topology[C]//Proceedings of the First International Conference on Knowledge Discovery and Data Mining. Montreal: AAAI, 1994: 109-113.

[10] LIN S W, LEE Z J, CHEN S C,etal. Parameter determination of support vector machine and feature selection using simulated annealing approach[J]. Applied Soft Computing, 2008, 8(4): 1 505-1 512.

[11] CHEN Y M, MIAO D Q, WANG R Z. A rough set approach to feature selection based on ant colonyoptimization[J]. Pattern Recognition Letters, 2010, 31(3): 226-233.

[12] DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperatingagents[J]. IEEE Trans Syst Man Cybernetics-Part B, 1996, 26(1): 29-41.

[13] ZHANG X L, CHEN X F, HE Z J. An ACO-based algorithm for parameter optimization of support vectormachines[J]. Expert Systems with Applications, 2010, 37(9): 6 618-6 628.

[14] LIAO T J, THOMAS S, MARCO A,etal. A unified ant colony optimization algorithm for continuous optimization[J]. European Journal of Operational Research, 2014, 234(3): 597-609.

[15] JUNIOR L, NEDJAH N, MOURELLE L. Routing for applications inNoC using ACO-based algorithms[J]. Applied Soft Computing, 2013, 13(5): 2 224-2 231.

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

[17] JENSEN R, SHEN Q. Finding rough setreducts with ant colony optimization[C]//Proceedings of the UK Workshop on Computational Intelligence. Bristol: [s.n.], 2003: 15-22.

[18] TABAKHI S, MORADI P, AKHLAGHIAN F. An unsupervised feature selection algorithm based on ant colony optimization[J]. Engineering Applications of Artificial Intelligence, 2014, 32: 112-123.

[19] 苗奪謙, 王玨. 粗糙集理論中概念與運算的信息表示[J]. 軟件學報, 1999, 10 (2) : 113-116.

[20] PALSANKAR K, UMASHANKAR B, PABITRA M. Granular computing, rough tropy and objectextraction[J]. Pattern Recognition Letters, 2004, 26(16): 2 509-2 517.

[21] 苗奪謙, 范世棟. 知識的粒度計算及其應用[J]. 系統(tǒng)工程理論與實踐, 2002, 22(1): 48-56.

[22] HU Q H, YU D R, XIE Z X. Neighborhood classifiers[J]. Expert Systems with Applications, 2008, 34(2): 866-876.

[23] JENSEN R. Combining rough and fuzzy sets for feature selection[D]. Edinburgh: The University of Edinburgh, 2005.

[24] LIU Y, HUANG W L, JIANG Y,etal. Quick attribute reduct algorithm for neighborhood rough set mode[J]. Information Sciences, 2014, 271(7): 65-81.

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

[26] HU Q H, YU D R, LIU J F,etal. Neighborhood rough set based heterogeneous feature subset selection[J]. Information Sciences, 2008, 178(18): 3 577-3 594.

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