一種基于模糊粗糙集的快速特征選擇算法

張 曉 楊燕燕

（1.西安理工大學(xué)應(yīng)用數(shù)學(xué)系，西安，710048；2.清華大學(xué)自動(dòng)化系，北京，100084）

引 言

經(jīng)典的粗糙集理論[1]是由波蘭數(shù)學(xué)家Pawlak在1982年提出的,它是一種處理數(shù)據(jù)中的不確定性的有效工具,然而經(jīng)典粗糙集只能處理符號(hào)值(名義值)的數(shù)據(jù)。模糊粗糙集[2]作為經(jīng)典粗糙集的最重要的推廣之一,可以用來(lái)處理實(shí)數(shù)值甚至是混合值的數(shù)據(jù)。目前,模糊粗糙集已經(jīng)成功應(yīng)用于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域[3],其最受人們關(guān)注的應(yīng)用之一就是特征選擇(屬性約簡(jiǎn))。關(guān)于模糊粗糙集特征選擇的研究工作已存在不少[4-10],但其快速的特征選擇算法的研究還很少,據(jù)作者所知,僅文獻(xiàn)[11]在特征選擇算法迭代步驟提供了加速策略，從而減少了算法的計(jì)算時(shí)間。

實(shí)際中的數(shù)據(jù)一般包含信息量較低的樣例或噪聲點(diǎn),如果對(duì)樣例進(jìn)行篩選,利用篩選得到的樣例進(jìn)行挖掘知識(shí)將會(huì)減少計(jì)算的復(fù)雜度。文獻(xiàn)[12]提供了3種樣例選擇的啟發(fā)式算法,其中之一的算法思想即選擇隸屬模糊正域的值不小于給定閾值的那些樣例。文獻(xiàn)[13]使用一種模糊粗糙度量來(lái)刻畫(huà)樣例的質(zhì)量并給出了wrapper式的樣例選擇方法。文獻(xiàn)[14]針對(duì)k-最近鄰分類規(guī)則提出了一種加權(quán)抽樣技術(shù)來(lái)篩選代表樣例。事實(shí)上,特征選擇和樣例選擇是相對(duì)獨(dú)立的工作,也有一些文獻(xiàn)基于模糊粗糙集研究特征和樣例同時(shí)選擇的方法[15-18]。例如,文獻(xiàn)[18]給出了一個(gè)基于頻率的啟發(fā)式算法來(lái)交替選取特征和樣例,以達(dá)到特征和樣例同時(shí)被選取的目的。

由于現(xiàn)有的基于模糊粗糙集的特征選擇算法的復(fù)雜度一般是O(n2m2),其中n為數(shù)據(jù)集中的樣例個(gè)數(shù),m為特征個(gè)數(shù)。當(dāng)數(shù)據(jù)集中有較多的樣例時(shí),現(xiàn)有的特征選擇算法會(huì)消耗大量的計(jì)算時(shí)間和存儲(chǔ)空間。注意到特征選擇和樣例選擇還有另外一個(gè)結(jié)合點(diǎn),即是先對(duì)數(shù)據(jù)進(jìn)行樣例選擇,然后利用篩選的代表樣例進(jìn)行特征選擇,從而減少特征選擇算法的計(jì)算時(shí)間。因此,本文是對(duì)數(shù)據(jù)集篩選代表樣例進(jìn)行特征選擇達(dá)到加速計(jì)算的目的,不同于文獻(xiàn)[11]在特征選擇算法迭代步驟進(jìn)行加速的策略,這也為特征選擇的快速算法提供了一種新的思路。

基于文獻(xiàn)[12]中樣例選擇的思想,本文先對(duì)樣例進(jìn)行篩選,即篩選那些模糊下近似值不低于給定閾值的那些樣例,然后在文獻(xiàn)[7]的基于模糊粗糙集構(gòu)造信息熵進(jìn)行特征選擇的工作基礎(chǔ)上,只利用篩選樣例的信息熵進(jìn)行特征選擇以降低算法的復(fù)雜度,從而提供了一種快速的特征選擇算法。數(shù)值試驗(yàn)表明該算法具有有效性,且對(duì)篩選樣例多少的關(guān)鍵參數(shù)給出了合理的建議。

1 預(yù)備知識(shí)

1.1 模糊粗糙集

設(shè)U是一個(gè)論域,F(U×U)為U×U上的模糊冪集。如果R∈F(U×U),R稱為一個(gè)在U×U上的模糊關(guān)系。如果對(duì)任意的x∈U有R(x,x)=1,R稱為是自反的;如果對(duì)任意的x,y∈U有R(x,y)=R(y,x),R稱為是對(duì)稱的;如果對(duì)任意的x,y,z∈U有R(x,y)≥T(R(x,z),R(z,y)),則R稱為是T-傳遞的,其中T為三角范數(shù)。另外,如果R是自反、對(duì)稱和T-傳遞的,則稱R是U上的一個(gè)模糊T-相似關(guān)系。

文獻(xiàn)[2]在模糊T-相似關(guān)系R上給出了模糊集X∈F(U)的一對(duì)下、上近似算子：對(duì)任意的x∈U

式(1)和式(2)是模糊粗糙集最初的一對(duì)下、上近似算子,后來(lái)也有不少文獻(xiàn)對(duì)其進(jìn)行了推廣,而式(1)和式(2)是應(yīng)用最為廣泛的一對(duì)近似算子,故本文的研究工作也是在其基礎(chǔ)之上展開(kāi)的。

1.2 模糊信息系統(tǒng)和模糊決策系統(tǒng)

一個(gè)模糊信息系統(tǒng)是一個(gè)二元組(U,A),其中U={x1,x2,…,xn}為論域,xi為對(duì)象(樣例);A={a1,a2,…,am}是一個(gè)有限非空的屬性(特征)集;對(duì)于每個(gè)a∈A,有一個(gè)映射a：U→Va,Va稱為屬性a的值域,且每個(gè)屬性a都可定義一個(gè)模糊關(guān)系R{a}。由任意的屬性子集B?A可定義一個(gè)模糊關(guān)系。

一個(gè)模糊決策系統(tǒng)是一個(gè)二元組(U,A∪D),A∩D=?,其中(U,A)是一個(gè)模糊信息系統(tǒng),A稱為條件屬性集,D=j5i0abt0b稱為決策屬性集,d是符號(hào)值的屬性,成立一個(gè)映射d：U→Vd,且Vd={d(x)：x∈U}稱為決策屬性d的值域。

在決策屬性集D上定義一個(gè)等價(jià)關(guān)系,即

則RD產(chǎn)生U的一族劃分

式中[xi]D={xj∈U：(xi,xj)∈RD}稱作是對(duì)象xi所屬的決策類。需要指出的是,分明決策類[xi]D的特征函數(shù)為

定義1[5]設(shè)(U,A∪D)是一個(gè)模糊決策系統(tǒng),U={x1,x2,…,xn},F(U)是U上的模糊冪集。模糊集X∈F(U)的基數(shù)定義為

1.3 λ-信息熵

定義2[7]設(shè)(U,A∪D)是一個(gè)模糊決策系統(tǒng),U={x1,x2,…,xn},B?A。決策屬性集D相對(duì)于條件屬性集B的λ-條件熵定義為

式中

是對(duì)象xi關(guān)于B的模糊粒,。

注釋1[7]如果,在這種情況下,定義

定理1[7]設(shè)(U,A∪D)是一個(gè)模糊決策系統(tǒng),U={x1,x2,…,xn},C?B?A,則

由定理1知,λ-條件熵關(guān)于屬性子集是單調(diào)的。

2 基于模糊決策系統(tǒng)篩選樣例的特征選擇算法

本節(jié)利用文獻(xiàn)[12]的樣例選擇思想,先對(duì)模糊決策系統(tǒng)的樣例進(jìn)行篩選,然后利用篩選樣例構(gòu)造新的λ-信息熵,并給出相應(yīng)的特征選擇算法。

設(shè)(U,A∪D)是一個(gè)模糊決策系統(tǒng),U={x1,x2,…,xn},屬性子集B?A。對(duì)U中每一個(gè)對(duì)象(樣例)xi(i=1,2,…,n),計(jì)算對(duì)象xi隸屬其所在決策類[xi]D的下近似值。已知度量了對(duì)象xi隸屬[xi]D的確定程度,因此的值越小,對(duì)象xi隸屬[xi]D的確定程度越低,這也說(shuō)明了對(duì)象xi包含的不確定信息越多。在實(shí)際中,邊界點(diǎn)和噪聲點(diǎn)包含更多的不確定信息,故隸屬其所在的決策類的下近似值可能會(huì)很小。如果在數(shù)據(jù)挖掘過(guò)程中忽略掉這些有較小下近似值的樣例,那么會(huì)減少計(jì)算時(shí)間。給定閾值α∈[0,1],記

為由參數(shù)α確定的(U,A∪D)的篩選樣例集。

利用篩選樣例集來(lái)完成數(shù)據(jù)挖掘的任務(wù)要使最終的結(jié)果不能和完整的數(shù)據(jù)集所得的結(jié)果相差太大,因此閾值α要合理地選取。α取值大小直接決定了篩選樣例的多少。如果篩選樣例過(guò)多，從而不能有效地減少計(jì)算時(shí)間；而篩選樣例過(guò)少又會(huì)損失較多的信息,具體的α取值建議將在數(shù)值試驗(yàn)部分給出。

定義3設(shè)(U,A∪D)是一個(gè)模糊決策系統(tǒng),U={x1,x2,…,xn},B?A,Uα是篩選樣例集。決策屬性集D相對(duì)于條件屬性集B的Uα-λ-條件熵定義為

式中|Uα|為Uα的基數(shù)。

由定義3易知Uα-λ-條件熵可以看作是λ-條件熵的一種推廣,不同之處在于Uα-λ-條件熵只考慮篩選樣例的信息熵,而λ-條件熵考慮所有樣例的信息熵。因而由定理1知Uα-λ-條件熵也是單調(diào)的,即對(duì)C?B?A有。應(yīng)該指出的是注釋1對(duì)定義3同樣成立,且由文獻(xiàn)[7]定理3易知恒成立。

定理2設(shè)(U,A∪D)是一個(gè)模糊決策系統(tǒng),U={x1,x2,…,xn},B?A,Uα是篩選樣例集,則的最大值為|Uα|/e。

證明：由文獻(xiàn)[7]定理5易證。

定理3設(shè)(U,A∪D)是一個(gè)模糊決策系統(tǒng),U={x1,x2,…,xn},B?A,Uα是篩選樣例集,則當(dāng)且僅當(dāng)對(duì)任意的xi∈Uα成立。

證明：由文獻(xiàn)[7]定理6易證。

如果一個(gè)新的條件屬性添加到條件屬性子集,則Uα-λ-條件熵就會(huì)單調(diào)地減少,從而Uα-λ-條件熵減少的值就反映了添加的屬性相對(duì)條件屬性子集的重要程度。

定義4設(shè)(U,A∪D)是一個(gè)模糊決策系統(tǒng),B?A,Uα是篩選樣例集。對(duì)任意的條件屬性a∈AB,a相對(duì)于D對(duì)B的Uα-重要性定義為

利用Uα-重要性度量,給出相應(yīng)的特征選擇算法。

算法1基于模糊決策系統(tǒng)篩選樣例的特征選擇算法

輸入：模糊決策系統(tǒng)(U,A∪D),U={x1,x2,…,xn},閾值α;

輸出：屬性子集B

① 初始化Uα=?。對(duì)每一個(gè)對(duì)象xi∈U,根據(jù)式(1)計(jì)算。如果λi≥α,添加xi到Uα;

③對(duì)每個(gè)條件屬性aj∈AB,計(jì)算;

⑤輸出B并終止算法。

該算法的時(shí)間復(fù)雜度是多項(xiàng)式級(jí)的。實(shí)際上,該算法第1步的時(shí)間復(fù)雜度為O(|U|2|A|),第3步的時(shí)間復(fù)雜度至多為O(|Uα||U||A|)。另外,第3步至多迭代|A|次,第4步的時(shí)間復(fù)雜度為O(|A|)。綜上,算法1的時(shí)間復(fù)雜度為O(|U||A|(|U|+|Uα||A|))。

3 數(shù)值試驗(yàn)

本節(jié)通過(guò)一些數(shù)值試驗(yàn)對(duì)算法1的有效性進(jìn)行評(píng)估。試驗(yàn)主要使用算法1搜索1個(gè)特征子集,評(píng)估參數(shù)α對(duì)特征選擇在特征個(gè)數(shù)、計(jì)算時(shí)間及獲取精度等方面的影響。為了達(dá)到目的,從UCI數(shù)據(jù)庫(kù)下載了8個(gè)數(shù)據(jù)集,關(guān)于數(shù)據(jù)集的描述如表1所示。

表1 數(shù)據(jù)集描述Tab.1 Description of data sets

3.1 數(shù)據(jù)預(yù)處理和試驗(yàn)設(shè)計(jì)

對(duì)每個(gè)數(shù)據(jù)集,分別用U，A和D標(biāo)記論域、條件屬性集和決策屬性集。如果其中存在一些實(shí)數(shù)值的條件屬性,則對(duì)這些屬性的屬性值先進(jìn)行標(biāo)準(zhǔn)化,即對(duì)實(shí)數(shù)值的屬性a∈A有

于是對(duì)任意的xi∈U，有。這里為了符號(hào)的簡(jiǎn)單,仍然用a標(biāo)記標(biāo)準(zhǔn)化的條件屬性。

試驗(yàn)設(shè)計(jì)如下：給定一個(gè)預(yù)處理過(guò)的數(shù)據(jù)集,用十折交叉驗(yàn)證方法得到試驗(yàn)結(jié)果。具體地,所有樣例被平均等分為10份,每一份輪流作為測(cè)試集,剩下的9份作為訓(xùn)練集。對(duì)任意一個(gè)訓(xùn)練集中的標(biāo)準(zhǔn)化條件屬性a，定義一個(gè)模糊關(guān)系

式中xi和xj為該訓(xùn)練集中的對(duì)象(樣例);若該訓(xùn)練集中有符號(hào)值的條件屬性a，則定義

由此每一個(gè)訓(xùn)練集都轉(zhuǎn)化為一個(gè)模糊決策系統(tǒng)。利用算法1在該訓(xùn)練集上對(duì)給定的閾值α選取樣例進(jìn)而選擇特征子集。選擇的樣例和特征子集用來(lái)構(gòu)造k-最近鄰分類器(其中k=1,即1NN)和線性支撐向量機(jī)(LSVM)，其中分類器的參數(shù)均為默認(rèn)設(shè)置。構(gòu)造好的分類器用來(lái)對(duì)測(cè)試集獲取分類精度(測(cè)試精度)以檢驗(yàn)算法1的有效性。這個(gè)過(guò)程對(duì)每一對(duì)訓(xùn)練集和測(cè)試集都執(zhí)行一次,因而最終報(bào)告的試驗(yàn)結(jié)果是10次試驗(yàn)結(jié)果的平均值。

再令篩選樣例的閾值α取值范圍設(shè)置為0到1,步長(zhǎng)為0.05。對(duì)模糊下近似值進(jìn)行標(biāo)準(zhǔn)化的原因是需要對(duì)所有數(shù)據(jù)集的α取值統(tǒng)一標(biāo)準(zhǔn)。

3.2 試驗(yàn)結(jié)果

圖1 不同閾值α下篩選樣例的平均個(gè)數(shù)Fig.1 Average number of selected instances with different threshold valuesα

圖2 不同閾值α下選擇特征的平均個(gè)數(shù)Fig.2 Average number of selected features with different threshold valuesα

圖3 不同閾值α下特征選擇過(guò)程的平均運(yùn)行時(shí)間Fig.3 Average running time of feature selection process with different threshold valuesα

圖1—4分別描述了各個(gè)數(shù)據(jù)集在不同的閾值α下選擇的樣例的平均個(gè)數(shù)、選擇的特征的平均個(gè)數(shù)、特征選擇的平均時(shí)間和獲取的平均分類精度。由圖1和圖2很容易看到隨著α值的增加,算法1選擇的樣例和特征的平均個(gè)數(shù)都單調(diào)地減少。此外,實(shí)數(shù)值的數(shù)據(jù)集Wine，WDBC，Libras，Steel和CTG隨著α趨于1,選取的樣例或特征的平均個(gè)數(shù)也趨于0;而對(duì)另外3個(gè)混合數(shù)據(jù)集Heart，Horse和Credit來(lái)說(shuō),當(dāng)α趨于1時(shí)選取的樣例或特征依然比較多,這也說(shuō)明了實(shí)數(shù)值樣例的標(biāo)準(zhǔn)化模糊下近似值大多小于1而混合值樣例的標(biāo)準(zhǔn)化模糊下近似值大多等于1,這主要由本文針對(duì)實(shí)數(shù)值和符號(hào)值的條件屬性所定義的模糊關(guān)系決定。由圖3也容易看到隨著α值的增加,特征選擇過(guò)程的平均運(yùn)行時(shí)間也大致地單調(diào)減少,尤其對(duì)實(shí)數(shù)值的數(shù)據(jù)集Wine，WDBC，Libras，Steel和CTG而言,運(yùn)行時(shí)間在α大致對(duì)應(yīng)的區(qū)間(0,0.5)上減少得最快。由圖4可以看到,當(dāng)α趨于1時(shí),實(shí)數(shù)值的數(shù)據(jù)集Wine，WDBC，Libras，Steel和CTG獲取的分類精度急劇地減少,這是由于α趨于1造成選取的樣例和特征過(guò)少而導(dǎo)致分類器擬合不足;對(duì)于混合數(shù)據(jù)集Heart，Horse和Credit,閾值α的變化對(duì)獲取的精度并沒(méi)有太大影響,這是因?yàn)樽兓摩潦沟眠x取的樣例和特征仍然比較多，從而仍能較好地訓(xùn)練分類器。

圖4 不同閾值α下獲取的平均分類精度Fig.4 Average classification accuracy obtained by different threshold valuesα

表2 1NN所對(duì)應(yīng)的最佳閾值α及相應(yīng)的試驗(yàn)結(jié)果Tab.2 Best threshold and the related experimental results obtained by 1NN

表3 LSVM所對(duì)應(yīng)的最佳閾值α及相應(yīng)的試驗(yàn)結(jié)果Tab.3 Best threshold and the related experimental results obtained by LSVM

從試驗(yàn)結(jié)果來(lái)看,閾值α的選取至關(guān)重要。表2和表3中分別列出在1NN和LSVM下每個(gè)數(shù)據(jù)集所對(duì)應(yīng)的最佳閾值及其相應(yīng)的試驗(yàn)結(jié)果。需要指出的是，這里的最佳閾值是獲取的分類精度不會(huì)顯著低于α=0時(shí)所獲取的分類精度的最大閾值。這里,采用Paired-t檢驗(yàn)來(lái)驗(yàn)證分類精度的顯著不同,其中顯著性水平設(shè)為0.05。另外,表2和表3的最后一列指的是最佳閾值下的特征選擇時(shí)間占α=0時(shí)特征選擇時(shí)間的比例,其值越小則意味著節(jié)約的計(jì)算時(shí)間越多。

綜合表2和表3可以看出,對(duì)幾乎所有數(shù)據(jù)集而言,最佳閾值α能有效地減少特征選擇的計(jì)算時(shí)間而且對(duì)最終獲取的分類精度沒(méi)有顯著影響。進(jìn)一步地,對(duì)于實(shí)數(shù)值的數(shù)據(jù)集,合理的閾值α大概在區(qū)間[0.1,0.3]附近選取;對(duì)于混合數(shù)據(jù)集,閾值α可取為1。

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

本文提出了一種基于模糊粗糙集的快速特征選擇算法,其思想是對(duì)樣例先進(jìn)行篩選，然后在篩選樣例上進(jìn)行特征選擇。具體地,基于文獻(xiàn)[12]的樣例選擇的思想,本文對(duì)模糊決策系統(tǒng)先進(jìn)行樣例篩選,即選擇模糊下近似值不低于給定閾值α的那些樣例,然后定義了篩選樣例的單調(diào)信息熵用來(lái)作為特征選擇的評(píng)估度量,并給出了相應(yīng)的特征選擇算法。試驗(yàn)結(jié)果表明本文提出的特征選擇算法能有效減少計(jì)算時(shí)間且不會(huì)明顯降低特征子集所得的精度,另外也分別針對(duì)實(shí)數(shù)值的數(shù)據(jù)集和混合數(shù)據(jù)集給出了控制篩選樣例個(gè)數(shù)的閾值α的建議。