任曉霞，薛 凡

REN Xiaoxia1,XUE Fan2，3

1.張家口學(xué)院 理學(xué)院，河北 張家口 075000

2.武漢大學(xué) 計(jì)算機(jī)學(xué)院 軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢 430072

3.黃淮學(xué)院 創(chuàng)新創(chuàng)業(yè)學(xué)院，河南 駐馬店 463000

1.College of Science,Zhangjiakou University,Zhangjiakou,Hebei 075000,China

2.State Key Laboratory of Software Engineering,School of Computer,Wuhan University,Wuhan 430072,China

3.School of Innovation and Entrepreneurship,Huanghuai University,Zhumadian,Henan 463000,China

1 引言

屬性約簡(jiǎn)即特征選擇，是粗糙集理論中一項(xiàng)重要的應(yīng)用[1]，由于現(xiàn)實(shí)中很多的數(shù)據(jù)集存在著大量的冗余屬性，屬性約簡(jiǎn)其主要思想是在保持已有知識(shí)的分類能力不變的情形去消除那些冗余屬性，這樣可以降低數(shù)據(jù)集的規(guī)模，從而提高知識(shí)發(fā)現(xiàn)的效率。目前，如何構(gòu)造出優(yōu)越的啟發(fā)式函數(shù)對(duì)數(shù)據(jù)集中的屬性進(jìn)行重要度評(píng)估是目前屬性約簡(jiǎn)研究的重點(diǎn)[2-5]。

粗糙集理論[1]是波蘭學(xué)者Pawlak提出的一種處理不確定性數(shù)據(jù)的數(shù)學(xué)方法，由于它不需要數(shù)據(jù)之外的任何先驗(yàn)信息，因此目前已廣泛運(yùn)用于數(shù)據(jù)的屬性約簡(jiǎn)[2-5]中。傳統(tǒng)的粗糙集理論建立在等價(jià)關(guān)系基礎(chǔ)上，僅適用于離散型屬性。為了解決這個(gè)問(wèn)題，近年來(lái)，學(xué)者們提出了多種改進(jìn)的模型，使得粗糙集理論可以很好地處理數(shù)值型數(shù)據(jù)。例如，運(yùn)用鄰域關(guān)系取代等價(jià)關(guān)系，鄰域粗糙集模型[6-7]是目前處理數(shù)值型數(shù)據(jù)的一種常用模型，Dubois等[8]學(xué)者將模糊集融入粗糙集理論中，提出了模糊粗糙集模型。這兩種模型都是處理數(shù)值型數(shù)據(jù)常用且有效的方法，基于這兩種模型的屬性約簡(jiǎn)算法也被大量提出。例如，Hu等[3]學(xué)者運(yùn)用屬性依賴度作為啟發(fā)式函數(shù)提出了基于鄰域粗糙集模型的混合屬性約簡(jiǎn)算法。段潔等[9]學(xué)者提出了鄰域粗糙集的多標(biāo)記屬性約簡(jiǎn)。Wang[10-13]等學(xué)者運(yùn)用屬性依賴度提出了基于改進(jìn)模糊粗糙集的特征選擇算法等。對(duì)于目前這些眾多的算法，它們大多是以依賴度為啟發(fā)式函數(shù)來(lái)度量屬性。

在文獻(xiàn)[13]中，Wang將鄰域粗糙集與模糊粗糙集結(jié)合，提出了模糊鄰域粗糙集模型，并根據(jù)依賴度度量構(gòu)造出了相應(yīng)的屬性約簡(jiǎn)算法。徐風(fēng)等[14]學(xué)者證明了模糊鄰域粗糙集模型對(duì)信息系統(tǒng)具有更好的不確定性度量效果。由于依賴度是通過(guò)近似逼近的角度對(duì)屬性進(jìn)行評(píng)估，但是這種方法顯得過(guò)于單一，并不能對(duì)屬性有著更精確的度量。因此本文在此基礎(chǔ)上重新定義了依賴度，并且提出了模糊鄰域粒度的概念，然后將這兩種方法用于屬性重要性的評(píng)估，提出相應(yīng)的屬性約簡(jiǎn)算法。最后進(jìn)行一系列實(shí)驗(yàn)來(lái)比較本文所提出的算法與目前已有算法的屬性約簡(jiǎn)性能，從而驗(yàn)證本文算法的有效性和優(yōu)越性。

2 基本理論

在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域中，結(jié)構(gòu)化的數(shù)據(jù)表示成信息系統(tǒng)IS=(U,AT,V)的形式，其中U被稱為論域，AT為屬性集，V為屬性的值域。若信息系統(tǒng)中屬性集AT=C?D，且C?D=?，其中C,D分別被稱為條件屬性和決策屬性，那么稱這個(gè)信息系統(tǒng)為決策信息系統(tǒng)(DIS)。

模糊集理論[15]是在傳統(tǒng)明確集基礎(chǔ)上的推廣，定義論域U 上的函數(shù)映射(?):U→[0,1]，被稱為U 上的模糊集，(x)稱為對(duì)象x關(guān)于模糊集的模糊隸屬度，U上的所有的模糊集組成的全集表示為F(U)。

設(shè)鄰域信息系統(tǒng)NIS=(U,AT,V)，U為論域，AT為全體屬性集且均為數(shù)值型數(shù)據(jù)，V為屬性的值域。由B?AT在U上誘導(dǎo)的模糊相似關(guān)系R滿足?x∈U，R(x,x)=1 ，并且對(duì)于?a∈AT ，由 a 誘導(dǎo)的模糊相似關(guān)系為，并且 R與之間滿足對(duì)象 x 在 U 上關(guān)于 B 的模糊信息粒定義為 [x](y)=R(x,y)。

定義1[12-13]設(shè)鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，決策屬性劃分為，R是由B在U上誘導(dǎo)的模糊相似關(guān)系，那么?x∈U的模糊決策定義為：

定義2[13-14]設(shè)鄰域信息系統(tǒng)NIS=(U,AT,V,f)，R是由B?AT在U上誘導(dǎo)的模糊相似關(guān)系，?x∈U關(guān)于R的模糊鄰域定義為：

這里的δ被稱為模糊鄰域的鄰域半徑，滿足0≤δ≤1。通過(guò)模糊相似關(guān)系R和鄰域半徑δ就可以確定?x∈U的模糊鄰域。

定義3[13-14]對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C，決策屬性劃分為D2,…,Dm}，其對(duì)應(yīng)的模糊決策為是由B在U上誘導(dǎo)的模糊相似關(guān)系，令鄰域半徑為δ，那么決策類Di關(guān)于R的模糊鄰域粗糙集的下近似和上近似分別定義為：

3 依賴度與模糊鄰域粒度

在粗糙集理論中，屬性依賴度[2-5]是一個(gè)非常重要的概念，它反映了條件屬性與決策屬性之間的關(guān)系程度，是構(gòu)造基于粗糙集理論屬性約簡(jiǎn)算法的關(guān)鍵[3，5]。本文這里定義基于模糊鄰域粗糙集模型的依賴度。

定義4對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C，決策劃分為是由B在U上誘導(dǎo)的模糊相似關(guān)系，設(shè)鄰域半徑δ，那么決策屬性集D關(guān)于B的依賴度定義為：

依賴度表示的是包含在正區(qū)域的對(duì)象占論域?qū)ο蟮谋壤?，因而可以作為條件屬性與決策屬性之間的關(guān)系程度的度量[6]。根據(jù)定義3可以看出，模糊相似關(guān)系RB和鄰域半徑δ對(duì)依賴度有著很重要的影響。

下文中，將適當(dāng)?shù)厥÷脏徲虬霃溅牡臉?biāo)記。

性質(zhì)1對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B1?B2?C ，那么屬性依賴度滿足 DE(D)≤DE(D)。

證明 由于 B1?B2?C ，那么顯然有根據(jù)定義2可以得到，所以根據(jù)定義3可推出滿足，因此，即滿足關(guān)系證畢。

性質(zhì)2對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C ，鄰域半徑 δ1,δ2滿足 δ1≤δ2，那么屬性依賴度滿足

證明 由于 δ1≤δ2，根據(jù)定義2有，所以對(duì)于滿足，因而，即 滿 足 關(guān) 系證畢。

粒計(jì)算理論[16]是智能信息處理中一種很重要的研究方法，其中粒結(jié)構(gòu)模型[17-18]是該理論的一種重要表現(xiàn)形式，同時(shí)也是評(píng)價(jià)信息系統(tǒng)分類能力的一個(gè)重要的指標(biāo)。目前學(xué)者們提出了多種粒結(jié)構(gòu)模型[14，17-18]，本文這里在模糊相似關(guān)系的基礎(chǔ)上提出一種新的粒結(jié)構(gòu)模型。

定義5對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C，鄰域半徑為δ，由U在模糊相似關(guān)系R上誘導(dǎo)的模糊鄰域粒結(jié)構(gòu)定義為：

類似于模糊粗糙集中信息粒度[18]的定義，這里給出基于模糊鄰域粒結(jié)構(gòu)的知識(shí)粒度。

性質(zhì)3對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B1?B2?C，那么模糊鄰域粒度滿足GK(B2)≤GK(B1)。

證明 由于 B1? B2? C ，那么 R? R，根據(jù)定義2可以得到 ?x∈U ，[x]?[x]，所以由定義6可以容易得到GK(B2)≤GK(B1)。證畢。

性質(zhì)4對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C ，鄰域半徑 δ1,δ2滿足 δ1≤δ2，那么模糊鄰域粒度滿足GKδ1(B)≤GKδ2(B)。

證明 由于 δ1≤δ2，根據(jù)定義2有那么由定義6可以容易得到GKδ1(B)≤GKδ2(B)。

在定義4中，依賴度是通過(guò)近似逼近的視角去對(duì)條件屬性集進(jìn)行評(píng)估，而定義6中的模糊鄰域粒度可以體現(xiàn)出條件屬性集對(duì)系統(tǒng)的分類性能，這兩種方法表現(xiàn)出了對(duì)屬性集的不同視角評(píng)估，因此將它們結(jié)合起來(lái)可以更為全面的評(píng)估屬性，達(dá)到更好的屬性重要度度量，同時(shí)可以體現(xiàn)出兩種方法的優(yōu)越性[15，18]。

定義7對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C，R是由B在U上誘導(dǎo)的模糊相似關(guān)系，設(shè)鄰域半徑δ，定義基于模糊鄰域粗糙集的依賴度和知識(shí)粒度混合度量為：

一般情況下，信息系統(tǒng)的論域非空，因此模糊鄰域粒度GKδ(B)≠0。結(jié)合性質(zhì)1～4，可以發(fā)現(xiàn)，當(dāng)鄰域半徑δ不變，隨著屬性集B的逐漸增大，Hδ(B)也是逐漸增大的。當(dāng)屬性集B不變時(shí)，隨著鄰域半徑δ的逐漸增大，Hδ(B)是逐漸減小的。特別的，當(dāng)B=?時(shí)，Hδ(B)=0 。

本文依據(jù)定義7的混合度量給出信息系統(tǒng)的屬性約簡(jiǎn)如定義8所示。

定義8對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，若B?C是該信息系統(tǒng)的一個(gè)屬性約簡(jiǎn)集當(dāng)如下兩點(diǎn)同時(shí)成立：

定義9對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C，R是由B在U上誘導(dǎo)的模糊相似關(guān)系，設(shè)鄰域半徑δ，對(duì)于?a∈B在D下關(guān)于B的第一種屬性重要度定義為：

定義10對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C，R是由B在U上誘導(dǎo)的模糊相似關(guān)系，設(shè)鄰域半徑δ，對(duì)于?a∈C-B在D下關(guān)于B的第二種屬性重要度定義為：

這兩種屬性重要度的定義表示了兩種不同的含義，定義9表示的是屬性子集B中內(nèi)部屬性a關(guān)于B的屬性重要度，而定義10表示的是屬性子集B的外部屬性a關(guān)于B的屬性重要度。

4 啟發(fā)式屬性約簡(jiǎn)算法

屬性約簡(jiǎn)作為粗糙集理論的一個(gè)重要的應(yīng)用而得到學(xué)者的廣泛關(guān)注，如何對(duì)信息系統(tǒng)中屬性進(jìn)行更精準(zhǔn)的重要度評(píng)估一直是該方向的研究重點(diǎn)[2-5]。借助定義9和定義10的兩種屬性重要度作為啟發(fā)式函數(shù)，這里給出一種基于模糊鄰域粗糙集的啟發(fā)式屬性約簡(jiǎn)算法。

對(duì)于鄰域決策信息系統(tǒng)NDIS=(U,C?D,V,f)，B?C，鄰域半徑δ，算法1給出的是模糊鄰域粗糙集的模糊粒度度量計(jì)算方法。

算法1基于模糊鄰域粗糙集的依賴度和模糊鄰域粒度混合度量Hδ(B)。

輸入：NDIS=(U,C?D,V,f)，B?C，鄰域半徑δ。

輸出：Hδ(B)。

步驟5根據(jù)定義7返回結(jié)果Hδ(B)。

算法2基于模糊鄰域粗糙集的啟發(fā)式屬性約簡(jiǎn)算法。

輸入：NDIS=(U,C?D,V,f)，鄰域半徑δ。

輸出：屬性約簡(jiǎn)red。

步驟1初始化red=?，Hδ(?)=0。

步驟2對(duì)于?a∈C-red，根據(jù)定義10計(jì)算每個(gè)屬性重要度，選擇屬性重要度最大的那個(gè)屬性，記為′。

步驟4對(duì)于?a∈red，找出所有使Hδ(red-{a})=Hδ(C)成立的屬性，記Π←?，將這些屬性添加入Π中，如果Π為空集，輸?shù)讲襟E6，否則轉(zhuǎn)到步驟5。

步驟6返回red，算法終止。

步驟2和步驟3通過(guò)屬性重要度函數(shù)對(duì)數(shù)據(jù)集的屬性集進(jìn)行啟發(fā)式搜索，是一個(gè)不斷迭代的過(guò)程，算法剛開(kāi)始時(shí)候，red=?，Hδ(red)=0，然后通過(guò)啟發(fā)式函數(shù)每次迭代選擇出一個(gè)屬性，并將這個(gè)屬性添加入約簡(jiǎn)集red中，根據(jù)定義7，當(dāng)約簡(jiǎn)集red逐漸增大時(shí)，其Hδ(red)的值也是增大的，經(jīng)過(guò)不斷迭代直到滿足Hδ(red)=Hδ(C)，此時(shí)達(dá)到收斂條件。正是由于 Hδ(?)函數(shù)的單調(diào)性，因此算法2肯定是收斂的。在步驟2中，算法每次讓屬性重要度達(dá)到最大的屬性加入red中，這樣就加速了算法2的收斂速度。算法2收斂時(shí)，得到的集合red是全集C的一個(gè)約簡(jiǎn)，但不一定是一個(gè)最優(yōu)的約簡(jiǎn)，因?yàn)榧蟫ed內(nèi)部可能存在屬性之間的依賴導(dǎo)致某些屬性冗余[3]，因此該算法在步驟4中進(jìn)行了進(jìn)一步的屬性剔除，從而得到最終的約簡(jiǎn)結(jié)果，這個(gè)結(jié)果既保持了原度量結(jié)果的收斂性，又保證了約簡(jiǎn)集red的極小性。

根據(jù)算法1的時(shí)間復(fù)雜度和文獻(xiàn)[3]，算法2的時(shí)間復(fù)雜度為 O(c2?n2)。

5 實(shí)驗(yàn)分析

為了驗(yàn)證本文所提出的啟發(fā)式屬性約簡(jiǎn)算法具有一定的優(yōu)越性，本實(shí)驗(yàn)將所提出的算法與其他的相關(guān)算法對(duì)同一組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，然后通過(guò)實(shí)驗(yàn)結(jié)果的約簡(jiǎn)集、約簡(jiǎn)耗時(shí)和約簡(jiǎn)集的分類精度來(lái)比較算法的優(yōu)越性。參與實(shí)驗(yàn)的數(shù)據(jù)集均選取自UCI標(biāo)準(zhǔn)數(shù)據(jù)集庫(kù)，具體信息如表1所示。

表1 UCI數(shù)據(jù)集

實(shí)驗(yàn)中選取參與比較的相關(guān)算法分別為：一種相對(duì)決策熵度量的高效特征選擇算法（算法1）[5]，基于改進(jìn)模糊?；哪：植诩瘜傩约s簡(jiǎn)算法（算法2）[12]，基于鄰域組合測(cè)度的屬性約簡(jiǎn)算法（算法3）[19]，基于改進(jìn)模糊粗糙集的一種模糊條件熵的特征選擇算法（算法4）[20]，基于鄰域?qū)傩詤^(qū)分度量的屬性約簡(jiǎn)算法（算法5）[21]，基于改進(jìn)鄰域?；哪：靥卣鬟x擇算法（算法6）[22]，記本文所提出的算法為算法7。

在這些算法中，算法2、算法4、算法5和算法6是基于單一度量方法對(duì)屬性進(jìn)行度量，而算法1、算法3和算法7是通過(guò)多種方法進(jìn)行組合來(lái)度量屬性。在實(shí)驗(yàn)開(kāi)始之前，為了消除屬性量綱的影響，所有數(shù)據(jù)集的屬性值均被歸一化到[0，1]區(qū)間。算法1是針對(duì)離散型數(shù)據(jù)集的特征選擇算法，因此在運(yùn)用算法1前需將連續(xù)數(shù)據(jù)進(jìn)行離散化處理。在實(shí)驗(yàn)分析過(guò)程中，需要運(yùn)用分類器來(lái)評(píng)估約簡(jiǎn)結(jié)果的優(yōu)劣，本實(shí)驗(yàn)采用支持向量機(jī)（SVM）分類器和分類決策樹(shù)（CART）分類器。各個(gè)算法采用Matlab2014b進(jìn)行編程實(shí)現(xiàn)，實(shí)驗(yàn)運(yùn)行的硬件環(huán)境為Intel i3 7500 3.40 GHz的處理器，內(nèi)存為8 GB的個(gè)人主機(jī)。

對(duì)于本文所提出的屬性約簡(jiǎn)算法，在開(kāi)始之前需要確定鄰域半徑δ的值，并且該值的選取對(duì)最終的屬性約簡(jiǎn)結(jié)果有著很重要的影響，因此為了得到最優(yōu)的實(shí)驗(yàn)結(jié)果，本實(shí)驗(yàn)嘗試通過(guò)取多個(gè)值分別進(jìn)行實(shí)驗(yàn)來(lái)選擇最優(yōu)結(jié)果，即讓鄰域半徑從區(qū)間[0，1]按0.05的間隔分別取值，并對(duì)每個(gè)鄰域半徑分別進(jìn)行實(shí)驗(yàn)，然后運(yùn)用SVM分類器對(duì)每個(gè)鄰域半徑下的屬性約簡(jiǎn)結(jié)果進(jìn)行分類訓(xùn)練，從而得到對(duì)應(yīng)實(shí)驗(yàn)結(jié)果的分類精度，本文所提出的算法最終約簡(jiǎn)結(jié)果選取為分類精度最高的屬性子集。表2所示的是7種算法約簡(jiǎn)結(jié)果集合基數(shù)的大小比較。

表2 7種算法的約簡(jiǎn)集大小比較

觀察表2可以看出，7種算法得到的約簡(jiǎn)結(jié)果均小于原數(shù)據(jù)集的屬性總數(shù)，部分?jǐn)?shù)據(jù)集遠(yuǎn)小于原數(shù)據(jù)集，這說(shuō)明了現(xiàn)實(shí)中很多數(shù)據(jù)集普遍存在著很多的冗余屬性，從而體現(xiàn)出屬性約簡(jiǎn)在數(shù)據(jù)預(yù)處理中的重要性，同時(shí)也說(shuō)明這7種算法的有效性。對(duì)比這7種算法的屬性約簡(jiǎn)結(jié)果，可以看出算法3和本文所提出的算法7約簡(jiǎn)得到的屬性子集大小整體比其他算法要小一些，例如數(shù)據(jù)集wdbc、sonar、move和gerbox。這主要是由于這兩種算法是基于多種度量方法的啟發(fā)式屬性約簡(jiǎn)，在約簡(jiǎn)過(guò)程中對(duì)候選屬性具有更好的度量效果，降低了度量偏差，因此能夠得到更小的約簡(jiǎn)集。這表明，多種度量方法的結(jié)合能對(duì)屬性達(dá)到更好的評(píng)估，從而鑒別出信息系統(tǒng)更為關(guān)鍵的屬性。同時(shí)，本文所提出的算法7在多數(shù)數(shù)據(jù)集具有更小的約簡(jiǎn)結(jié)果，這說(shuō)明了基于模糊集的模糊?；葌鹘y(tǒng)的明確集具有更好的集合隸屬關(guān)系表達(dá)，屬性的度量效果更佳。另外觀察表2還可以發(fā)現(xiàn)，算法1在多數(shù)數(shù)據(jù)集的約簡(jiǎn)結(jié)果較大，這主要是由于算法1在屬性約簡(jiǎn)前數(shù)據(jù)集經(jīng)過(guò)了離散化處理，離散化的過(guò)程可能導(dǎo)致了連續(xù)型數(shù)據(jù)集分類信息的丟失，這樣不利于數(shù)據(jù)集的屬性約簡(jiǎn)。通過(guò)屬性約簡(jiǎn)結(jié)果，證明了組合度量方法具有更好的屬性評(píng)估性能，能夠搜索到更優(yōu)的屬性子集，并且基于模糊集的方法具有更精準(zhǔn)的度量結(jié)果。

接下來(lái)將比較各個(gè)算法所選擇出約簡(jiǎn)集的優(yōu)越性。本實(shí)驗(yàn)利用SVM和CART兩種分類器分別對(duì)7種算法的屬性約簡(jiǎn)結(jié)果運(yùn)用十折交叉的方法對(duì)樣本數(shù)據(jù)進(jìn)行分類學(xué)習(xí)訓(xùn)練，然后計(jì)算出樣本數(shù)據(jù)的分類精度，其結(jié)果如表3和表4所示。

在表3和表4中，用“*”標(biāo)記的分類精度為7種算法中的最大值。觀察表3和表4可以發(fā)現(xiàn)，7種算法的分類精度結(jié)果差別不是很大，均接近原始數(shù)據(jù)集的分類精度，并且有一些算法在部分?jǐn)?shù)據(jù)集的分類精度高于原始數(shù)據(jù)集的分類精度，這便體現(xiàn)了屬性約簡(jiǎn)算法的有效性。仔細(xì)比較分析可以看出，算法1、算法3和算法7約簡(jiǎn)結(jié)果對(duì)應(yīng)的分類精度在整體上同樣比其他算法約簡(jiǎn)結(jié)果的分類精度要高一些，這說(shuō)明了，通過(guò)多種度量方法結(jié)合后約簡(jiǎn)出來(lái)的屬性子集能夠達(dá)到更好的分類效果，從而進(jìn)一步證明了組合度量對(duì)屬性評(píng)估的優(yōu)越性。同時(shí)，算法7在部分?jǐn)?shù)據(jù)集得到的約簡(jiǎn)結(jié)果具有更高的分類精度，說(shuō)明本文所提出的屬性約簡(jiǎn)算法在約簡(jiǎn)結(jié)果方面具有更好的約簡(jiǎn)性能。

表3 7種算法約簡(jiǎn)結(jié)果在SVM下的分類精度比較%

表4 7種算法約簡(jiǎn)結(jié)果在CART下的分類精度比較 %

圖1 算法效率比較

算法的時(shí)間復(fù)雜度是評(píng)估算法優(yōu)劣的一項(xiàng)重要指標(biāo)，因此接下來(lái)將比較7種算法的約簡(jiǎn)效率。在實(shí)驗(yàn)中，為了防止偶然性，讓每種算法分別對(duì)每個(gè)數(shù)據(jù)集重復(fù)約簡(jiǎn)多次，取多次屬性約簡(jiǎn)時(shí)間開(kāi)銷的平均值作為對(duì)應(yīng)數(shù)據(jù)集屬性約簡(jiǎn)的時(shí)間結(jié)果，具體結(jié)果如圖1所示。觀察圖1可以發(fā)現(xiàn)，在各個(gè)數(shù)據(jù)集的屬性約簡(jiǎn)時(shí)間開(kāi)銷結(jié)果中，算法1、算法3和算法7結(jié)果略多于其他算法，這主要是由于這三種算法的評(píng)估函數(shù)是多種方法的結(jié)合，在進(jìn)行計(jì)算方法無(wú)疑會(huì)增加時(shí)間的開(kāi)銷，但是這三種算法都經(jīng)過(guò)了優(yōu)化，多種度量的計(jì)算都避免了重復(fù)計(jì)算，尤其是本文所提出的屬性約簡(jiǎn)算法，其中依賴度和模糊鄰域粒度的計(jì)算都需要計(jì)算出每個(gè)對(duì)象的模糊鄰域粒，因此可以將依賴度和模糊鄰域粒度進(jìn)行同時(shí)計(jì)算，這樣可以大大降低計(jì)算量，因此所提出的算法同樣具有較高的時(shí)間效率。

綜合以上算法的約簡(jiǎn)結(jié)果和算法的運(yùn)行效率，可以看出，本文所提出的算法通過(guò)多個(gè)度量方法可以對(duì)信息系統(tǒng)的屬性達(dá)到更好的度量效果，其約簡(jiǎn)結(jié)果優(yōu)于單一度量的啟發(fā)式屬性約簡(jiǎn)，同時(shí)本文所提出的算法是運(yùn)用模糊集的視角去構(gòu)造兩種度量，同樣具有更佳的評(píng)估效果。此外實(shí)驗(yàn)結(jié)果也表明本文所提出的算法具有較高的約簡(jiǎn)效率。另一方面，本文所提出的算法在進(jìn)行實(shí)驗(yàn)時(shí)，鄰域半徑是一個(gè)需要設(shè)定的參數(shù)，這里是通過(guò)重復(fù)實(shí)驗(yàn)多次才能得到最優(yōu)的結(jié)果，很難直接快速地得到合適的鄰域半徑取值，因此這也是本文所提出算法的一個(gè)的不足之處。

由于鄰域半徑δ對(duì)實(shí)驗(yàn)結(jié)果有著很重要的影響，因此接下來(lái)將探究鄰域半徑δ對(duì)實(shí)驗(yàn)結(jié)果是如何影響的，并且分析其取值問(wèn)題，為以后的研究提供參考。圖2給出了數(shù)據(jù)集屬性約簡(jiǎn)集大小、SVM分類精度和鄰域半徑之間的關(guān)系。觀察可以發(fā)現(xiàn)，隨著鄰域半徑的逐漸增大，算法約簡(jiǎn)出的屬性子集大小是逐漸增大的，而分類精度剛開(kāi)始逐漸增大，但是當(dāng)鄰域半徑達(dá)到0.2～0.3時(shí)，其分類精度開(kāi)始趨于穩(wěn)定或略有降低，這主要是由于，剛開(kāi)始時(shí)候約簡(jiǎn)集較小，未能達(dá)到最佳的分類效果，所以分類精度較低，但是當(dāng)屬性子集較大時(shí)，較多的屬性可能會(huì)帶來(lái)噪聲數(shù)據(jù)的干擾，反而會(huì)不利于數(shù)據(jù)的分類，從而出現(xiàn)了分類精度降低的情形。根據(jù)圖2的實(shí)驗(yàn)結(jié)果，本文所提出的屬性約簡(jiǎn)算法中鄰域半徑可以取[0.2，0.3]之間較為適宜。

6 結(jié)語(yǔ)

屬性約簡(jiǎn)是一項(xiàng)重要的數(shù)據(jù)預(yù)處理技術(shù)，如何構(gòu)造有效的屬性評(píng)估方法一直是目前研究的重點(diǎn)，在基于粗糙集理論的屬性約簡(jiǎn)算法中，本文針對(duì)目前屬性評(píng)估單一性的問(wèn)題，在模糊鄰域粗糙集模型中定義屬性依賴度的概念，并基于此提出了模糊鄰域粒度度量，由于依賴度和模糊鄰域粒度是兩種不同視角的屬性評(píng)估方法，因此本文將兩種方法結(jié)合提出一種新的啟發(fā)式屬性約簡(jiǎn)算法。最后UCI實(shí)驗(yàn)結(jié)果證明了所提出算法的適用性和優(yōu)越性。由于本文提出的算法只適用于數(shù)值型數(shù)據(jù)，因此接下來(lái)探索可以適用混合型數(shù)據(jù)的屬性約簡(jiǎn)算法。

圖2 各個(gè)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

參考文獻(xiàn)：

[1]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11（5）：341-356.

[2]Shao Mingwen，Li Kewen.Attribute reduction in generalized one-sided formal contexts[J].Information Sciences，2016，378：317-327.

[3]Hu Qinghua，Yu Daren，Liu Jinfu，et al.Neighborhood rough set based heterogeneous feature subset selection[J].Information Sciences，2008，178（18）：3577-3594.

[4]陳昊，楊俊安，莊鎮(zhèn)泉，等.變精度粗糙集的屬性核和最小屬性約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（5）：1011-1017.

[5]Jiang Feng，Sui Yuefei，Zhou Lin.A relative decision entropy-based feature selection approach[J].Pattern Recognition，2015，48（7）：2151-2163.

[6]D’Eer L，Restrepo M，Cornelis C，et al.Neighborhood operators for covering-based rough sets[J].Information Sciences，2016，336：21-44.

[7]徐怡，楊宏健，紀(jì)霞.基于雙重?；瘻?zhǔn)則的鄰域多粒度粗糙集模型[J].控制與決策，2015，30（8）：1469-1478.

[8]Dubois D，Prade H.Rough fuzzy sets and fuzzy rough sets[J].International Journal of General Systems，1990，17（2/3）：191-208.

[9]段潔，胡清華，張靈均，等.基于鄰域粗糙集的多標(biāo)記分類特征選擇算法[J].計(jì)算機(jī)研究與發(fā)展，2015，52（1）：56-65.

[10]Wang Changzhong，Cui Xinhua，Bao Wenying，et al.Attribute reduction of decision table based on similar relation[C]//2012 International Conference on Machine Learning and Cybernetics，2012.

[11]Wang Changzhong，Qi Yali，He Qian.Attribute reduction using distance-based fuzzy rough sets[C]//International Conference on Machine Learning and Cybernetics，Guangzhou，2015：860-865.

[12]Wang Changzhong，Qi Yali，Shao Minweng，et al.A fitting model for feature selection with fuzzy rough sets[J].IEEE Transactions on Fuzzy Systems，2016：1-13.

[13]Wang Changzhong，Shao Minweng，He Qian，et al.Feature subset selection based on fuzzy neighborhood rough sets[J].Knowledge-Based Systems，2016，111：173-179.

[14]徐風(fēng)，姚晟，紀(jì)霞，等.基于模糊鄰域粗糙集的信息系統(tǒng)不確定性度量方法[J].南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2017，53（5）：926-936.

[15]Zadeh L A.Fuzzy sets[J].Information&Control，1965，8（3）：338-353.

[16]Zadeh L A.Some reflections on soft computing，granular computing and their roles in the conception，design and utilization of information/intelligent systems[J].Soft Computing，1998，2（1）：23-25.

[17]Pedrycz W，Succi G，Sillitti A，et al.Data description：A general framework of information granules[J].Knowledge-Based Systems，2015，80：98-108.

[18]Zhang Xianyong，Miao Duoqian.Three-layer granular structures and three-way informational measures of a decision table[J].Information Sciences，2017，412：67-86.

[19]何松華，康嬋娟，魯敏，等.基于鄰域組合測(cè)度的屬性約簡(jiǎn)方法[J].控制與決策，2016，31（7）：1225-1230.

[20]Zhang Xiao，Mei Changlin，Chen Degang et al.Feature selection in mixed data：A method using a novel fuzzy rough set-based information entropy[J].Pattern Recognition，2016，56（1）：1-15.

[21]Wang Changzhong，Hu Qinghua，Wang Xizhao，et al.Feature selection based on neighborhood discrimination index[J].IEEE Transactions on Neural Networks and Learning Systems，2017（99）：1-14.

[22]姚晟，徐風(fēng)，趙鵬，等.基于改進(jìn)鄰域粒的模糊熵特征選擇算法[J].南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2017，53（4）：802-814.