基于Lebesgue和熵度量的不完備鄰域決策系統(tǒng)特征選擇

余 清 侯麗萍

(信陽(yáng)職業(yè)技術(shù)學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 河南 信陽(yáng) 464000) 2(信陽(yáng)農(nóng)林學(xué)院信息工程學(xué)院 河南 信陽(yáng) 464000)

0 引 言

隨著大數(shù)據(jù)處理技術(shù)的發(fā)展,數(shù)據(jù)量呈指數(shù)級(jí)增長(zhǎng),收集到的大量信息中可能含有大量噪聲、冗余或缺失的特征值[1]。因此,在使用海量數(shù)據(jù)之前,有必要對(duì)其進(jìn)行預(yù)處理。特征選擇作為一個(gè)重要的預(yù)處理步驟,其主要目標(biāo)是消除冗余和噪聲特征,并對(duì)其進(jìn)行處理缺失值,對(duì)數(shù)據(jù)進(jìn)行分類,并為數(shù)據(jù)應(yīng)用程序提取有用的信息[2]。

近年來(lái),特征選擇在模式識(shí)別、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘應(yīng)用等領(lǐng)域引起了學(xué)者們的廣泛關(guān)注。傳統(tǒng)的粗糙集模型作為一種流行的屬性約簡(jiǎn)工具,只能處理分類數(shù)據(jù)集,而不適合解決混合數(shù)據(jù)集和不完全數(shù)據(jù)集中數(shù)值數(shù)據(jù)不完整和連續(xù)的問(wèn)題。為了解決數(shù)值數(shù)據(jù)集離散化過(guò)程中的信息丟失問(wèn)題,許多學(xué)者引入鄰域粗糙集來(lái)研究特征選擇。在不完備決策系統(tǒng)中,文獻(xiàn)[3]提出一種基于鄰域容忍條件熵的啟發(fā)式特征選擇算法,文獻(xiàn)[4]基于不完備決策系統(tǒng)中的容忍關(guān)系,構(gòu)造了一種基于正區(qū)域的屬性約簡(jiǎn)方法。文獻(xiàn)[5]在鄰域粗糙集中,通過(guò)增加相似類與某些決策類具有最大交集的樣本來(lái)擴(kuò)大正區(qū)域。但是上述方法存在特征冗余問(wèn)題,并且特征選擇算法在一定程度上處理高維數(shù)據(jù)集時(shí)仍有較高的時(shí)間消耗。

信息熵作為一種重要的不確定性度量在特征選擇及其變體中得到了廣泛的研究,提出一種利用鄰域粗糙集中的條件判別指數(shù)進(jìn)行特征選擇的方法[6]。另外文獻(xiàn)[7]研究了鄰域互信息及其在高光譜波段選擇分類中的應(yīng)用,然而這些不確定性度量的單調(diào)性并不總是成立的,而且這些基于鄰域粗糙集的特征選擇文獻(xiàn)也只是從完備信息系統(tǒng)的信息觀角度進(jìn)行研究集合,許多現(xiàn)有的特征選擇方法通常只基于代數(shù)視圖或信息視圖,對(duì)于大規(guī)模、高維的數(shù)據(jù)集,這些方法仍然是低效的。

為解決上述問(wèn)題,提出一種基于Lebesgue和熵度量的不完備鄰域決策系統(tǒng)特征選擇方法。將鄰域粗糙集與Lebesgue度量相結(jié)合,解決了不完備信息系統(tǒng)中基于鄰域粗糙集的特征選擇方法不能處理無(wú)限集的問(wèn)題,并有效地處理了混合和不完備數(shù)據(jù)集分類問(wèn)題。通過(guò)數(shù)據(jù)集驗(yàn)證了本文方法的有效性。

1 Lebesgue和基于熵的不確定性度量

1.1 基于Lebesgue度量的依賴度

(1)

Lebesgue內(nèi)部度量可以表示為m*(E)=|I|-m*(I-E)。如果m*(E)=m*(E);那么,可以說(shuō)E是可測(cè)量的,寫為m(E)。在本文中,m(X)被統(tǒng)一視為集合X的Lebesgue度量,即|X|。

(2)

性質(zhì)1[8]假設(shè)對(duì)于任何P、Q?C和x∈U,存在具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉;然后,以下屬性條件成立:

m(U)=|U|

定義2假設(shè)對(duì)于任何B?C,x,y∈U,存在一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉;然后,根據(jù)Lebesgue度量,分別定義X?U,X相對(duì)于B的鄰域上近似集和鄰域下近似集,分別為:

(3)

(4)

定義3假設(shè)一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,對(duì)于任意B?C,U/D={d1,d2,…,dl,…},基于Lebesgue度量,D相對(duì)于Β的正區(qū)域定義為:

(5)

式中:POSB為查找函數(shù);dj∈U/D,j=1,2,…,l,…。

命題1假設(shè)存在一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉且任意Q?P?C。然后,POSQ(D)?POSP(D)和m(POSQ(D))≤m(POSP(D))。

定義4假設(shè)對(duì)于任何B?C,存在一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,并且U/D={d1,d2,…,dl,…};然后,基于Lebesgue度量將D相對(duì)于B的依賴程度定義為:

(6)

式中:dj∈U/D,且j=1,2,…,l,…。

命題2假設(shè)一個(gè)不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,具有非空無(wú)限集U和任意Q?P?C,γQ(D)≤γP(D)保持不變。

證明對(duì)于任何Q?P?C,根據(jù)命題1,m(POSQ(

D))≤m(POSP(D))。因此,根據(jù)定義4,可以得到γQ(D)≤γP(D)。

1.2 Lebesgue與鄰域容差熵的不確定性度量

(7)

(8)

命題3假設(shè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,對(duì)于任何Q?P?C,NTEδ(Q)≤NTEδ(P)成立。

(9)

式中:dj∈U/D,且j=1,2,…,l,…。

引理1[9]假設(shè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,對(duì)于任何Q?P?C,NTEδ(Q∪D)≤NTEδ(P∪D)成立。

命題4假設(shè)對(duì)于任何B?C和xi∈U,dj∈U/D={d1,d2,…,dl,…},存在一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,其中j=1,2,…,l,…,則NTEδ(B∪D)≥NTEδ(B)。

證明從定義6和定義7可以立即得出:

NTEδ(B∪D)-NTEδ(B)=

(10)

根據(jù)命題4,鄰域容差聯(lián)合熵的值大于特征子集的鄰域容差熵的值。因此,可以得出結(jié)論,當(dāng)添加新特征時(shí),鄰域容差聯(lián)合熵具有更強(qiáng)的區(qū)分能力。

(11)

式中:dj∈U/D,以及j=1,2,…,l,…。

性質(zhì)2[9]假設(shè)存在具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,并且對(duì)于任何B?C,D對(duì)B的依賴程度為γB(D),B和D的鄰域容差聯(lián)合熵為NTEδ(B∪D),則NTDE(B,D)=γB(D)·NTEδ(B∪D)≥0。

從定義8和性質(zhì)2可以看出,在代數(shù)視圖中,γB(D)是D對(duì)B的依賴程度,而在信息視圖中,NTEδ(B∪D)是B和D的鄰域容差聯(lián)合熵。因此,定義8可以基于Lebesgue和熵度量從代數(shù)視圖和信息視圖分析和測(cè)量不完備鄰域決策系統(tǒng)的不確定性。

2 不完備鄰域決策系統(tǒng)中的特征選擇方法

2.1 基于鄰域容差依賴聯(lián)合熵的特征選擇

命題5假設(shè)對(duì)于任何Q?P?C,U/D={d1,d2,…,dl,…},存在具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,其中dj∈U/D且j=1,2,…,l,…。NTDE(Q,D)≤NTDE(P,D)。

定義9假設(shè)存在一個(gè)不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,并且有一個(gè)非空的無(wú)限集U和B?C;如果NTDE(B,D)=NTDE(C,D),并且對(duì)于任何a∈B,則存在NTDE(B,D)>NTDE(B-{a},D)?？梢哉f(shuō)B是C相對(duì)于D的約簡(jiǎn)。

定義10假設(shè)對(duì)于任何B?C和a∈B,存在具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉。然后,將B中的屬性a相對(duì)于D的內(nèi)部顯著性定義為:

Siginner(a,B,D)=NTDE(B,D)-NTDE(B-{a},D)

(12)

定義11假設(shè)存在一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,B?C;如果任何a∈B的Siginner(a,B,D)>0,則B中的屬性a是必要的;否則,a是不必要的。如果B中的每個(gè)a是必要的,則B是獨(dú)立的。

定義12假設(shè)存在一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,B?C;如果對(duì)于任意a∈C,NTDE(C,D)>NTDE(C-{a},D),即Siginner(a,C,D)>0,則a稱為C相對(duì)于D的核心屬性。

定義13假設(shè)對(duì)于任何B?C和b∈C-B,存在一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉。然后,將屬性b關(guān)于D的外部顯著性定義為:

Sigouter(b,B,D)=NTDE(B∪,D)-NTDE(B,D)

(13)

性質(zhì)3[9]假設(shè)存在一個(gè)具有非空無(wú)限集U和任意B?C的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,然后,可以得到下述特性:

(1) 對(duì)于任意a∈C,0≤Siginner(a,C,D)≤1。

(2) 對(duì)于任意b∈C-B,0≤Sigouter(b,B,D)≤1。

(3) 當(dāng)B=C時(shí),Sigouter(,C,D)=0。

(4) 當(dāng)且僅當(dāng)Sigouter(b,B,D)=0時(shí),任何b∈C-B都是不必要的。

請(qǐng)注意,在具有非空無(wú)限集U和B?C的INDS=〈U,C,D,δ〉中,對(duì)于任何a∈B,在計(jì)算Siginner(a,B,D)時(shí),NTDE(B-{a},D)僅因?yàn)镹TDE(B,D)是一個(gè)常數(shù)而被計(jì)算。同樣,對(duì)于任何b∈C-B,在計(jì)算Sigouter(b,B,D)時(shí),僅需要計(jì)算NTDE(B∪,D)。

2.2 兩種代表性約簡(jiǎn)方法比較分析

命題6假設(shè)存在一個(gè)不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,具有非空無(wú)限集U和任何B?C;如果B是不完備鄰域決策系統(tǒng)中C相對(duì)于D的鄰域容差約簡(jiǎn);那么,在不完備鄰域決策系統(tǒng)中,B是C相對(duì)于D的一個(gè)正區(qū)域約簡(jiǎn)。

給出一個(gè)具有非空無(wú)限集U的不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,任意B?C和D=j5i0abt0b,對(duì)于任意a∈B,提出一種稱為鄰域條件熵約簡(jiǎn)的不完備鄰域決策系統(tǒng)的約簡(jiǎn),如下:如果NTE(D|B)=NTE(D|C)和NTE(D|B-{a})

式中:NTB(xi)和NTD(xi)分別是xi關(guān)于B和D的鄰域容差類,NTD(xi)∈U/D。

命題8假設(shè)存在一個(gè)不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,并且有一個(gè)非空無(wú)限集U和B?C;當(dāng)且僅當(dāng)B是不完備鄰域決策系統(tǒng)中C相對(duì)于D的鄰域條件熵約簡(jiǎn)時(shí),B是不完備鄰域決策系統(tǒng)中C相對(duì)于D的鄰域容差約簡(jiǎn)。

2.3 特征選擇算法

圖1中顯示了用于特征選擇的數(shù)據(jù)分類過(guò)程,其中引入了Fisher評(píng)分方法以初步減少高維數(shù)據(jù)集的維數(shù)。為了支持有效的特征選擇,將基于鄰域容差依賴聯(lián)合熵(FSNTDJE)的特征選擇算法設(shè)計(jì)為算法1。

圖1 用于數(shù)據(jù)分類的特征選擇方法的處理流程

算法1FSNTDJE

輸入:不完備鄰域決策系統(tǒng)INDS=〈U,C,D,δ〉,鄰域參數(shù)δ。

輸出:最優(yōu)屬性子集B。

(1) 初始化B=?,R=?;

(2) 計(jì)算:NTDE(C,D);

(3) Fori=1 to |C| do

(4) 計(jì)算Siginner(ci,C,D);

(5) IfSiginner(ci,C,D)>0

(6)B=B∪{ci};

(7) End if

(8) End for

(9) 令R=C-B;

(10) WhileNTDE(B,D)≠NTDE(C,D)

(11) Forj=1 to |R| do

(12) 計(jì)算NTDE(B∪{aj},D);

(13) 選擇aj使得滿足max{aj∈R|NTDE(B∪{aj},D)},并且如果多個(gè)屬性滿足最大值。然后選擇前者;

(14) End For

(15) 令B=B∪{aj},R=R-{aj},并計(jì)算NTDE(B,D);

(16) End While

(17) Fork=1 to |B| do

(18) 選擇一個(gè)bk∈B;

(19) 計(jì)算NTDE(B-bk,D);

(20) IfNTDE(B-bk,D)>NTDE(B,D)

(21)B=B-bk;

(22) End if

(23) End

(24) 返回最優(yōu)屬性子集B

計(jì)算鄰域容差類的過(guò)程對(duì)特征選擇的時(shí)間復(fù)雜度有很大影響。FSNTDJE的主要計(jì)算涉及兩個(gè)重要方面:獲得鄰域容差類和計(jì)算鄰域容差依賴聯(lián)合熵。首先,為了進(jìn)一步降低鄰域容差類的計(jì)算時(shí)間復(fù)雜度,采用了排序算法。然后,鄰域容差類的時(shí)間復(fù)雜度為O(mn),其中:m是樣本數(shù);n是特征數(shù)。同時(shí),鄰域容差依賴聯(lián)合熵的計(jì)算時(shí)間復(fù)雜度為O(n)。由于O(n)

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

3.1 實(shí)驗(yàn)準(zhǔn)備

為了驗(yàn)證本文方法的分類性能,在15個(gè)公共數(shù)據(jù)集:7個(gè)UCI數(shù)據(jù)集(Nursery、Credit、Mushroom、Wpbc、Soybean、Annealing和Ozone level)和8個(gè)DNA微陣列基因表達(dá)數(shù)據(jù)集(Colon、DLBCL、Brain、Leukemia、Breast、Lung、MLL和Prostate)上獲得了所有對(duì)比算法的綜合結(jié)果并進(jìn)行了分析。表1中詳細(xì)描述了所有數(shù)據(jù)集。

表1 15個(gè)公共數(shù)據(jù)集的描述

實(shí)驗(yàn)是在一臺(tái)運(yùn)行Windows 10的計(jì)算機(jī)上進(jìn)行的,該計(jì)算機(jī)具有3.20 GHz的Intel(R)i5 CPU和4.0 GB內(nèi)存。所有仿真實(shí)驗(yàn)均在MATLAB 2016a中實(shí)現(xiàn),并選擇了4個(gè)分類器,包括Naive Bayes、C4.5、KNN和CART,以說(shuō)明分類結(jié)果。10個(gè)數(shù)據(jù)子集中的每個(gè)子集僅被用作測(cè)試數(shù)據(jù)集一次。交叉驗(yàn)證重復(fù)10次,10個(gè)測(cè)試結(jié)果的平均值是所選特征的數(shù)量和分類精度。

3.2 不同鄰域參數(shù)值的影響

實(shí)驗(yàn)的第二部分重點(diǎn)研究了不同鄰域參數(shù)下的分類精度和約簡(jiǎn)率。為了解釋不同鄰域參數(shù)值的分類精度和約簡(jiǎn)性能,需要一個(gè)約簡(jiǎn)率來(lái)評(píng)估本文方法的特征冗余性能。

定義14數(shù)據(jù)集的約簡(jiǎn)率定義為:

(14)

式中:|C|描述條件屬性的數(shù)量;|R|表示在給定的鄰域參數(shù)下生成的所選特征的數(shù)量。由于較高的約簡(jiǎn)率表明該方法對(duì)數(shù)據(jù)集的約簡(jiǎn)能力較強(qiáng),因此較高的約簡(jiǎn)率意味著冗余度會(huì)降低。

對(duì)于8個(gè)高維基因表達(dá)數(shù)據(jù)集,采用Fisher評(píng)分方法,并基于8個(gè)數(shù)據(jù)集中的所有基因?qū)ζ溥M(jìn)行排序,然后選擇g個(gè)基因形成候選基因子集。獲取以下7個(gè)維度(10、50、100、200、300、400和500)下的分類精度,以便可以選擇適當(dāng)?shù)木S度進(jìn)行特征選擇。圖2顯示了8個(gè)基因表達(dá)數(shù)據(jù)集上分類精度和基因數(shù)量之間的變化趨勢(shì)。可以看出,當(dāng)基因數(shù)量增加時(shí),精度通常會(huì)發(fā)生變化。因此,對(duì)于Colon和MLL數(shù)據(jù)集,可以將基因的維設(shè)置為200維特征,而對(duì)于DLBCL、Lung和Prostate數(shù)據(jù)集,可以設(shè)置為50維特征。對(duì)于Brain數(shù)據(jù)集,可以設(shè)置為400維特征。Leukemia和Breast數(shù)據(jù)集均可設(shè)置為100維特征。

注意,如果所有特征值都是分類的,則鄰域容差關(guān)系將退化為容差關(guān)系。因此,在實(shí)驗(yàn)中,對(duì)于3個(gè)數(shù)據(jù)集(Nursery、Mushroom和Soybean),鄰域參數(shù)將設(shè)置為0。通過(guò)使用具有不同鄰域參數(shù)值的FSNTDJE算法獲得十二個(gè)數(shù)據(jù)集上所選特征的分類精度。在獲得具有不同參數(shù)的特征選擇結(jié)果之后,對(duì)于4個(gè)UCI數(shù)據(jù)集,在Naive Bayes和C4.5分類器下實(shí)現(xiàn)了分類精度。對(duì)于8個(gè)基因表達(dá)數(shù)據(jù)集,在KNN(k=10)和C4.5分類器下評(píng)估分類精度和約簡(jiǎn)率。由于篇幅所限,僅展示Credit數(shù)據(jù)集在不同參數(shù)值下的結(jié)果,如圖3所示,其中水平坐標(biāo)代表間隔0.05時(shí)δ∈[0.05,1]的不同鄰域參數(shù)值,左右垂直坐標(biāo)分別表示精度和約簡(jiǎn)率。

圖3 具有不同鄰域參數(shù)值的12個(gè)數(shù)據(jù)集的分類精度和約簡(jiǎn)率

可以看出,不同的參數(shù)對(duì)FSNTDJE的分類性能有很大的影響。對(duì)于其他數(shù)據(jù)集,也顯示了相類似的結(jié)果。因此,對(duì)于每個(gè)數(shù)據(jù)集,可以根據(jù)結(jié)果圖選擇約簡(jiǎn)率較高且能夠保證兩個(gè)分類器均能有較高分類準(zhǔn)確度的參數(shù)。

3.3 低維UCI數(shù)據(jù)集的分類結(jié)果

對(duì)比算法包括:(1) 基于條件熵的粗糙集特征選擇算法(FSCE)[6];(2) 基于正逼近的粗糙集不完備特征選擇算法(IFSPA)[7];(3) 使用粗糙集模型的基于正區(qū)域的特征選擇算法(FSPR)[8];(4) 基于粗糙集理論的啟發(fā)式SetCover特征選擇算法(SetCover)[9]。通過(guò)使用不同鄰域參數(shù),并且獲得了表2的7個(gè)UCI數(shù)據(jù)集上所選特征的平均數(shù)量和適當(dāng)?shù)泥徲騾?shù),如表2所示。其中,從10倍交叉驗(yàn)證方法中獲得了這5種方法的選定特征子集的平均大小。本文表中粗體字均表示最佳結(jié)果。

表2 5種算法選擇的特征數(shù)

表2列出了5種不同算法使用10倍交叉驗(yàn)證選擇的平均特征數(shù)?？梢钥闯?使用Naive Bayes和C4.5分類器,在大多數(shù)情況下,FSNTDJE選擇的平均特征數(shù)量少于FSCE、IFSPA、FSPR和SetCover。對(duì)于Nursery和Soybean數(shù)據(jù)集,在2個(gè)不同的分類器下,SetCover和FSNTDJE算法獲得了幾乎相同的平均特征數(shù)。但是,它們兩者都比其他3種算法多大約一個(gè)。在Credit和Annealing數(shù)據(jù)集上,FSNTDJE選擇的平均特征數(shù)略低于FSPR,并且在5種算法中均達(dá)到最小值。對(duì)于Mushroom數(shù)據(jù)集,FSNTDJE選擇的平均特征數(shù)為4.2,比其他4種算法的平均特征數(shù)少0.2～3.4。對(duì)于Wpbc數(shù)據(jù)集,在Naive Bayes分類器下FSNTDJE的選定特征數(shù)為4.9,達(dá)到最低值。但是,在C4.5分類器下,FSNTDJE選擇的平均特征數(shù)與Wpbc的SetCover算法幾乎相同。在這兩個(gè)分類器下,FSNTDJE達(dá)到了Ozone level數(shù)據(jù)集上最少特征數(shù)。此外,平均指數(shù)表示所有結(jié)果的平均值。顯然,表2中Naive Bayes分類器下FSNTDJE的平均結(jié)果是最小的。總體而言,就所有數(shù)據(jù)集而言,所提出的FSNTDJE算法在所選特征的平均數(shù)量方面是有效的。

接下來(lái),使用6種方法評(píng)估所選特征的分類性能,說(shuō)明了本文方法的平均分類精度,即通過(guò)10倍交叉驗(yàn)證選擇特征子集;此外,為了獲得客觀的分類結(jié)果并減少隨機(jī)誤差,將所有的比較方法進(jìn)行10次,結(jié)果是10次分類精度評(píng)估的平均值。將FSNTDJE算法與以上4種特征選擇方法(FSCE、IFSPA、FSPR和SetCover)以及原始數(shù)據(jù)處理方法(ODP)進(jìn)行了比較。使用兩個(gè)分類器(Naive Bayes和C4.5)測(cè)試分類性能。在Naive Bayes和C4.5分類器下通過(guò)6種方法選擇的最佳特征的平均分類精度分別顯示在表3和表4中。

表3 Naive Bayes分類器下6種方法的分類精度

表4 C4.5分類器下6種方法的分類精度

從表2中可以看出,在這5種算法選擇的平均特征數(shù)上幾乎沒(méi)有差異,在此基礎(chǔ)上,表3和表4顯示了這6種方法之間的差異。顯然,除了Naive Bayes分類器下的Wpbc和Soybean數(shù)據(jù)集,以及C4.5分類器下的Nursery、Mushroom和Annealing數(shù)據(jù)集之外,大多數(shù)數(shù)據(jù)集上的FSNTDJE算法的分類精度均優(yōu)于其他5種方法。此外,在表3和表4中,FSNTDJE的平均精度得到了提高,且在2種不同的分類器上是最高的。從表3和表4可以看出,在Naive Bayes分類器下,雖然FSNTDJE在所選特征的平均大小上不如FSCE、IFSPA和FSPR,但是FSNTDJE的分類精度比Nursery數(shù)據(jù)集的ODP、FSCE、IFSPA和FSPR高0.024 0～0.052 2;但是,FSNTDJE在Soybean數(shù)據(jù)集上不如SetCover。盡管這5種算法選擇的特征的平均大小存在一些差異,但是FSNTDJE的平均精度在所有數(shù)據(jù)集上均高于其他方法,除了Wpbc和Soybean數(shù)據(jù)集。同樣,從表3和表4中可以看出,在C4.5分類器下,FSNTDJE的平均精度比其他5種方法高0.009 4～0.022 2,并且在所有數(shù)據(jù)集中,FSNTDJE的精度與SetCover的精度幾乎相同。對(duì)于Mushroom數(shù)據(jù)集,FSNTDJE的分類精度比ODP、FSPR和SetCover低0.05。但與其他方法相比,FSNTDJE選擇的特征較少,并且顯示出比FSCE和IFSPA更好的分類性能。綜上所述,就平均精度而言,FSNTDJE算法在Naive Bayes和C4.5中表現(xiàn)出了極大的穩(wěn)定性,而ODP、FSPR和SetCover算法的精度則有些不穩(wěn)定。從表3和表4的結(jié)果可以確定,對(duì)于Naive Bayes下的Nursery數(shù)據(jù)集,以及C4.5下的Mushroom和Annealing數(shù)據(jù)集,FSNTDJE可能會(huì)減少特征選擇過(guò)程中的一些重要特征,結(jié)果降低所選特征子集的分類精度。

在進(jìn)行實(shí)驗(yàn)的過(guò)程中,按時(shí)間復(fù)雜度對(duì)5種特征選擇方法進(jìn)行了粗略排序:O(FSNTDJE)

進(jìn)一步根據(jù)所選特征的數(shù)量及其分類精度,說(shuō)明FSNTDJE算法在所選數(shù)據(jù)集上的分類結(jié)果。這里,比較中使用的4種不完備數(shù)據(jù)集的最新特征選擇方法包括:(1) 基于啟發(fā)式可分辨矩陣的模糊粗糙集特征選擇算法(DMFS)[10];(2) 基于粗糙集的向后屬性約簡(jiǎn)算法(BKAR)[11];(3) 粗糙集中不完備決策系統(tǒng)的具有前向貪婪策略的基于互信息的特征選擇算法(MIFS)[12];(4) 基于可分辨矩陣的優(yōu)勢(shì)粗糙集知識(shí)約簡(jiǎn)算法(DMKR)[13]。應(yīng)當(dāng)注意,為了將FSNTDJE算法與上述4種特征選擇方法和ODP方法進(jìn)行比較,從表1中選擇了Credit和Annealing數(shù)據(jù)集。表5和表6顯示了6種不同方法的實(shí)驗(yàn)結(jié)果,其中,在Naive Bayes和C4.5分類器下可以實(shí)現(xiàn)具有10倍交叉驗(yàn)證的所選特征的平均數(shù)量和10次評(píng)估的平均精度。

表5 6種方法對(duì)所選Credit特征的分類精度

表6 6種方法對(duì)所選Annealing特征的分類精度

如表5所示,FSNTDJE實(shí)現(xiàn)了所選的Credit特征數(shù)量最少,分類精度最高。與其他5種方法相比,該算法選擇的平均特征數(shù)比5種方法要少2.0～4.5。另外無(wú)論哪種分類器,本文方法選擇特征的精度均高于其他5種方法,即在Naive Bayes分類器下,該算法的精度比其他方法高0.052 2～0.089 8,在C4.5分類器下,比它們高0.020 0～0.089 2。因此,FSNTDJE算法可以為Credit數(shù)據(jù)集實(shí)現(xiàn)出色的分類性能。

根據(jù)表6的分類結(jié)果,FSNTDJE算法得到的Annealing特征選擇數(shù)量最少、平均精度最高,并且該算法在Naive Bayes分類器下選擇的特征精度與DMFS、BKAR和DMKR算法的相當(dāng),且分別比ODP和MIFS高0.325 9和0.078 5。此外,FSNTDJE的精度類似于MIFS,并且在C4.5分類器下高于其他4種方法的精度。因此,FSNTDJE算法可以從原始Annealing數(shù)據(jù)集中刪除冗余特征。

從以上所有結(jié)果和分析中可以明顯看出,對(duì)于不同的學(xué)習(xí)任務(wù)和分類器,沒(méi)有一種算法始終比其他算法更好。通常,從表3至表6可以看出,與其他特征選擇方法相比,FSNTDJE算法可以反映特征的決策能力,避免因離散化而導(dǎo)致有用信息的丟失,并解決了不完備鄰域決策系統(tǒng)中的不確定性問(wèn)題和有效提高分類性能。因此,在不完備的低維UCI數(shù)據(jù)集上,FSNTDJE算法優(yōu)于其他相關(guān)的特征選擇方法。

3.4 高維基因表達(dá)數(shù)據(jù)集的分類結(jié)果

進(jìn)一步展示了本文方法在高維基因表達(dá)數(shù)據(jù)集上的分類性能。將FSNTDJE算法與4種最新的特征選擇方法進(jìn)行了比較,包括:(1) 基于粗糙集的相關(guān)特征選擇算法(CFS);(2) 基于快速相關(guān)的粗糙集濾波特征選擇算法(FCBF);(3) 交互特征選擇算法,它可以處理特征交互并有效地選擇相關(guān)特征(INT);(4) 基于信息增益和散度的統(tǒng)計(jì)機(jī)器學(xué)習(xí)特征選擇算法(IG)。從表1中選擇了5個(gè)基因表達(dá)數(shù)據(jù)集,獲得了使用10倍交叉驗(yàn)證和基因表達(dá)數(shù)據(jù)集上的適當(dāng)鄰域參數(shù)選擇的特征子集的平均大小,結(jié)果如表7所示。

表7 5種算法選擇的基因數(shù)量

表7顯示了在Naive Bayes和C4.5分類器下使用10倍交叉驗(yàn)證通過(guò)5種特征選擇算法選擇的平均基因數(shù)。很明顯,在大多數(shù)情況下,FSNTDJE算法優(yōu)于CFS、FCBF和INT算法。但是,對(duì)于Brain數(shù)據(jù)集,FCBF提供了最佳結(jié)果,IG則選擇了DLBCL數(shù)據(jù)集上的最佳基因數(shù)量。FSNTDJE算法為Naive Bayes分類器下的Colon和Prostate數(shù)據(jù)集選擇最小平均基因。對(duì)于Breast數(shù)據(jù)集,在兩個(gè)不同的分類器下,FSNTDJE選擇的基因數(shù)量為7,并且達(dá)到最小值。此外,FSNTDJE選擇的平均基因數(shù)是最好的,在兩個(gè)不同的分類器上比IG分別平均低0.84和0.32?？偠灾?所提出的方法可以為高維基因表達(dá)數(shù)據(jù)集選擇最少的基因。

根據(jù)表7中的結(jié)果,使用Naive Bayes和C4.5分類器評(píng)估5個(gè)基因表達(dá)數(shù)據(jù)集的分類結(jié)果。使用3個(gè)指標(biāo)來(lái)評(píng)估特征選擇的分類性能,包括準(zhǔn)確度(Acc)、真陽(yáng)性率(TPR)和假陽(yáng)性率(FPR)。TPR越高,FPR越低,該方法越好。3個(gè)指標(biāo)的公式分別表示為:

(15)

(16)

(17)

式中:TP表示檢測(cè)為正確的陽(yáng)性樣本數(shù);FP表示檢測(cè)為錯(cuò)誤的陽(yáng)性樣本數(shù);TN表示診斷為正確的陰性實(shí)例數(shù);FN表示診斷為錯(cuò)誤的陰性實(shí)例數(shù)。表8和表9分別顯示了在Naive Bayes和C4.5分類器下用6種方法選擇的基因的Acc、TPR和FPR值。所有比較的方法都執(zhí)行10次,并且將Acc的值評(píng)估為10次分類操作的平均值。

表8 Naive Bayes分類器下6種方法的3個(gè)指標(biāo)

表9 C4.5分類器下6種方法的3個(gè)指標(biāo)

從表7可知,5種算法在所選基因的平均數(shù)目上有很大的不同。根據(jù)表8和表9,除了Naive Bayes分類器下的Colon和Brain數(shù)據(jù)集和C4.5分類器下的Brain數(shù)據(jù)集之外,FSNTDJE的分類準(zhǔn)確性優(yōu)于其他5種方法。此外,FSNTDJE的TPR和FPR值在這5個(gè)數(shù)據(jù)集中的大多數(shù)上都取得了更好的結(jié)果。根據(jù)表8和表9,在Naive Bayes分類器下,明顯可以識(shí)別出這6種方法之間的差異。盡管從DLBCL和Brain數(shù)據(jù)集中選擇的平均基因而言,FSNTDJE的性能不如IG,但在Naive Bayes分類器中的Acc、TPR和FPR平均值最佳。對(duì)于Colon和Brain數(shù)據(jù)集,FSNTDJE的Acc分別比CFS和ODP的Acc低近0.018 8和0.015 8,這是因?yàn)镕SNTDJE算法在約簡(jiǎn)過(guò)程中丟失了Colon和Brain數(shù)據(jù)集的一些重要基因,從而導(dǎo)致分類準(zhǔn)確度降低。對(duì)于Breast數(shù)據(jù)集,FSNTDJE在平均基因數(shù)上達(dá)到最小,在3個(gè)指標(biāo)上獲得最佳結(jié)果。盡管在TPR中,FSNTDJE比Prostate數(shù)據(jù)集的CFS、FCBF和INT低約0.06,比Brain數(shù)據(jù)集的FCBF低約0.09,但Prostate和Brain數(shù)據(jù)集的FPR值最小。同樣,從表8和表9可以看出,在C4.5分類器下,FSNTDJE的Acc平均值比其他五種方法的平均值高出0.082～0.304。與ODP的結(jié)果相比,除Prostate數(shù)據(jù)集外,本文方法的TPR有了顯著提高。此外,關(guān)于FPR,對(duì)于DLBCL和Prostate數(shù)據(jù)集,FSNTDJE的FPR最低;但是,其平均值比ODP的平均值高出近0.064。根據(jù)表7、表8和表9中的結(jié)果,盡管FSNTDJE并未在DLBCL和Brain數(shù)據(jù)集中選擇最少的基因,但FSNTDJE在大多數(shù)基因表達(dá)數(shù)據(jù)集中均達(dá)到了相對(duì)最佳的結(jié)果。總體而言,實(shí)驗(yàn)結(jié)果表明,本文方法可有效消除冗余基因并提高高維基因表達(dá)數(shù)據(jù)集上的Acc和TPR。

與先前對(duì)低維UCI數(shù)據(jù)集的時(shí)間復(fù)雜度分析相似,以上5種方法的比較說(shuō)明了時(shí)間復(fù)雜度的大致順序如下:O(FSNTDJE)

與FSNTDJE相比的4種最新方法描述如下:(1) 基于可分辨矩陣的模糊粗糙集約簡(jiǎn)算法(DMRA)[14];(2) 基于模糊正區(qū)域的粗糙集加速算法(FPRA)[15];(3) 基于模糊粗糙集的邊界區(qū)域特征選擇算法(FRFS)[16];(4) 基于直覺(jué)模糊正區(qū)域的模糊粗糙集基因選擇算法(IFPR)[17]。類似于之前的實(shí)驗(yàn)方法,所有比較方法均運(yùn)行10次,并且在KNN(k=10)和CART分類器下4個(gè)基因表達(dá)數(shù)據(jù)集的平均分類精度是10次評(píng)估的平均值。表10和表11分別顯示了在KNN和CART分類器下這6種方法的分類精度。

表10 KNN分類器下6種方法的分類精度

表11 CART分類器下6種方法的分類精度

可以看出,除了KNN分類器下的Breast數(shù)據(jù)集和CART分類器下的MLL數(shù)據(jù)集,FSNTDJE算法的平均分類精度幾乎在所有數(shù)據(jù)集上都優(yōu)于其他5種方法,且FSNTDJE算法的平均分類精度最高。根據(jù)表10,在KNN分類器下,對(duì)于Colon、Leukemia和MLL數(shù)據(jù)集,FSNTDJE的分類精度最高,分別為0.876 3、0.901 9和0.961 5。但是,對(duì)于Breast數(shù)據(jù)集,FSNTDJE的精度略遜于DMRA的精度。如表11所示,在CART分類器下,FSNTDJE在幾乎所有數(shù)據(jù)集上都達(dá)到了最高的精度。但是,對(duì)于MLL數(shù)據(jù)集,FSNTDJE的平均精度比IFPR低0.062,比其他4種方法高0.026 5～0.099 2。總體而言,就平均精度而言,FSNTDJE算法對(duì)KNN和CART分類器下的4個(gè)高維基因表達(dá)數(shù)據(jù)集表現(xiàn)出更強(qiáng)的穩(wěn)定性,而DMRA、FPRA、FRFS和IFPR算法的分類性能略有不穩(wěn)定。因此,可以證明FSNTDJE算法可以消除冗余基因,顯著提高分類性能,并且優(yōu)于高維基因表達(dá)數(shù)據(jù)集的其他5種相關(guān)特征選擇方法。

為了進(jìn)一步評(píng)估FSNTDJE算法的分類性能,與3種最新的特征選擇方法相比。這些用于對(duì)比的特征選擇方法包括:(1) 動(dòng)態(tài)貝葉斯遺傳特征選擇算法,是通過(guò)在粗糙集中增強(qiáng)貝葉斯遺傳算法的原理而設(shè)計(jì)的(DBAGEL)[18];(2) 基于動(dòng)態(tài)遺傳算法的特征選擇方法,用于選擇重要特征(DGAFS)[19];(3) 通過(guò)選擇重要特征并推算缺失值來(lái)實(shí)現(xiàn)基于粗糙集的特征選擇算法(DGAFS-MI)[20]。從表2中選擇了5個(gè)基因表達(dá)數(shù)據(jù)集(Colon、DLBCL、Breast、Lung和Prostate),使用了Naive Bayes和KNN(k=10)分類器,表12和表13分別詳細(xì)顯示了在2種不同分類器下的5種不同特征選擇方法的實(shí)驗(yàn)結(jié)果。

表12 Naive Bayes分類器下5種方法的分類精度

表13 KNN分類器下5種方法的分類精度

如表12所示,在Naive Bayes分類器下,除Prostate數(shù)據(jù)集外,FSNTDJE的分類精度明顯優(yōu)于其他4種方法,并且在5個(gè)基因表達(dá)數(shù)據(jù)集上,ODP、DBAGEL、DGAFS和DGAFS-MI算法的精度相似。在Prostate數(shù)據(jù)集上,FSNTDJE的精度比DBAGEL的精度低0.082 8,比其他3種方法的精度高0.005 4～0.170 7。這是因?yàn)楫?dāng)FSNTDJE處理基因數(shù)據(jù)集時(shí),Prostate數(shù)據(jù)集仍然存在一些噪聲,因此這種情況會(huì)降低精度。但是,FSNTDJE的平均精度比其他4種方法高0.056 3～0.165 4,并達(dá)到了最高值。從表13中可以看出,在KNN分類器下,FSNTDJE選擇的基因子集的平均分類精度在Colon、DLBCL、Lung和Prostate數(shù)據(jù)集上是最好的。但是,對(duì)于Breast數(shù)據(jù)集,FSNTDJE的精度比DBAGEL的精度低0.035 7,比其他三種方法的精度高0.020 9～0.111 8。原因是FSNTDJE無(wú)法充分消除噪聲基因,這會(huì)削弱所選Breast基因的分類性能。綜上所述,FSNTDJE模型可以有效地減少高維基因表達(dá)數(shù)據(jù)集的維數(shù),并在這些大規(guī)模和高維數(shù)據(jù)集上實(shí)現(xiàn)出色的分類性能。

3.5 統(tǒng)計(jì)分析

為了證明特征選擇結(jié)果的統(tǒng)計(jì)性能,采用了Friedman檢驗(yàn)和Bonferroni-Dunn檢驗(yàn)來(lái)進(jìn)一步研究采用幾種不同方法的每個(gè)分類器的分類精度。Friedman統(tǒng)計(jì)量表示為:

(18)

(19)

式中:s是方法數(shù)量;T是數(shù)據(jù)集數(shù)量;Ra是方法A在所有數(shù)據(jù)集中的平均排名。FF遵循具有s-1和(s-1)·(T-1)自由度的Fisher分布。如果在Friedman檢驗(yàn)后否定了原假設(shè),則可以引入Bonferroni-Dunn檢驗(yàn)以進(jìn)一步檢測(cè)統(tǒng)計(jì)意義上哪些算法不同。如果平均距離水平超過(guò)臨界距離,則兩種算法將有顯著差異。臨界距離表示為:

(20)

式中:qα是檢驗(yàn)的臨界列表值;α是Bonferroni-Dunn檢驗(yàn)的顯著性水平。

對(duì)于表3和表4中的7個(gè)低維UCI數(shù)據(jù)集,將FSNTDJE算法與5種方法:ODP、FSCE、IFSPA、FSPR和SetCover進(jìn)行比較,以進(jìn)行Friedman統(tǒng)計(jì)。開(kāi)發(fā)了2個(gè)Friedman檢驗(yàn)來(lái)調(diào)查這6種特征選擇算法的分類性能是否存在顯著差異。從表4和表5中獲得的分類精度來(lái)看,在Naive Bayes和C4.5分類器下的6種算法的排名結(jié)果分別顯示在表14和表15中。

表14 Naive Bayes分類器下6種算法的排名

表15 C4.5分類器下6種算法的排名

表16 兩個(gè)分類器下6種方法的排名

表17 Naive Bayes分類器下6種特征選擇方法的排名

以下部分致力于所有高維基因表達(dá)數(shù)據(jù)集的統(tǒng)計(jì)分析。根據(jù)表8和表9的分類結(jié)果,在Naive Bayes和C4.5分類器下的6種特征選擇方法的排名結(jié)果顯示在表17和表18中。

表18 C4.5分類器下6種特征選擇方法的排名

表19 KNN分類器下6種方法的排名

表20 CART分類器下6種方法的排名

表21 Naive Bayes分類器下5種方法的排名

表22 KNN分類器下5種方法的排名

4 結(jié) 語(yǔ)

為了能夠處理混合數(shù)據(jù)集和不完全數(shù)據(jù)集,并能同時(shí)保持原始分類信息,提出一種基于Lebesgue和熵度量的不完備鄰域決策系統(tǒng)特征選擇方法。通過(guò)高維與低維多個(gè)數(shù)據(jù)集實(shí)驗(yàn)可以得出如下結(jié)論:

(1) 針對(duì)低維數(shù)據(jù)集,FSNTDJE算法實(shí)現(xiàn)了較低的時(shí)間復(fù)雜度,可以有效地消除冗余特征并優(yōu)化不完備數(shù)據(jù)集的分類性能。

(2) 針對(duì)高維數(shù)據(jù)集,FSNTDJE算法可以消除冗余基因,有效地減少高維基因表達(dá)數(shù)據(jù)集的維數(shù),并在這些大規(guī)模和高維數(shù)據(jù)集上實(shí)現(xiàn)出色的分類性能。

(3) FSNTDJE算法可以反映特征的決策能力,避免因離散化而導(dǎo)致有用信息的丟失,并解決了不完備鄰域決策系統(tǒng)中的不確定性問(wèn)題和有效提高分類性能。

(4) 統(tǒng)計(jì)數(shù)據(jù)進(jìn)一步表明了本文方法相對(duì)于其他方法,能夠更加有效地處理混合數(shù)據(jù)集和不完全數(shù)據(jù)集,并保持較好的分類性能。