支 宇,胡 軍

(1.重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,重慶 400065;2.重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400065)

0 引 言

粗糙集[1]是一種刻畫(huà)知識(shí)不確定性的數(shù)據(jù)分析方法,它是波蘭學(xué)者Pawlak在1982年首次提出并成為數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、人工智能等領(lǐng)域的研究熱點(diǎn)[2-4]。經(jīng)典粗糙集模型建立在嚴(yán)格的等價(jià)關(guān)系基礎(chǔ)上,這極大限制了粗糙集理論適用的范圍,而且對(duì)于數(shù)值型數(shù)據(jù)必須進(jìn)行離散化處理,轉(zhuǎn)換過(guò)程中可能會(huì)造成信息的損失。為了解決數(shù)據(jù)離散化帶來(lái)的問(wèn)題,Hu等[5]提出的鄰域粗糙集能夠更直接、有效地處理數(shù)值型數(shù)據(jù)。近些年來(lái),鄰域粗糙集相關(guān)理論和方法被廣泛應(yīng)用在各個(gè)領(lǐng)域[6-9]。

屬性約簡(jiǎn)作為粗糙集理論研究中的核心問(wèn)題之一,受到大量研究人員的關(guān)注。其目的是刪除不相關(guān)、不重要的屬性,降低分類成本,同時(shí)提高系統(tǒng)的分類性能。Min等[10]定義了最小測(cè)試成本,把代價(jià)敏感考慮到屬性約簡(jiǎn)問(wèn)題中;Liu等[11]從樣本出發(fā),將樣本按散列的方式劃分到一系列有序的桶中,基于桶的劃分提出一種快速計(jì)算正域的算法;Jiang等[12]設(shè)計(jì)了一種多粒度屬性選擇器,使用不同粒度下的信息來(lái)評(píng)估和選擇屬性;Fan等[13]關(guān)注邊界域樣本,通過(guò)添加與決策類具有最大交集的樣本來(lái)擴(kuò)大正域;Liu等[14]將傳統(tǒng)鄰域?；醋饕环N無(wú)監(jiān)督的信息?；呗?提出一種考慮標(biāo)簽信息的有監(jiān)督?；椒▉?lái)提升刻畫(huà)不確定性知識(shí)的能力;Hu等[15]認(rèn)為每個(gè)屬性具有不同的權(quán)重,在計(jì)算鄰域之前充分挖掘?qū)傩耘c決策之間的相關(guān)性,并對(duì)相關(guān)性高的屬性賦予更高的權(quán)重,由此提出了一種新的屬性約簡(jiǎn)方法;Qian等[16]考慮每個(gè)實(shí)例對(duì)應(yīng)多個(gè)標(biāo)簽的情況,設(shè)計(jì)了一種新的多標(biāo)簽分類特征選擇算法。

在屬性約簡(jiǎn)中,如何選擇屬性是一個(gè)非常關(guān)鍵的問(wèn)題。在現(xiàn)有研究中常用近似質(zhì)量[17-18]、條件熵[19-20]、鄰域決策錯(cuò)誤率[21]等作為侯選屬性的評(píng)價(jià)標(biāo)準(zhǔn)。其中,近似質(zhì)量通過(guò)正域與論域的基數(shù)比值衡量鄰域決策系統(tǒng)(neighborhood decision system,NDS)的分類能力,一般地,鄰域決策系統(tǒng)的近似質(zhì)量越大,鄰域決策系統(tǒng)的可分辨能力越強(qiáng),在一定程度上也能夠反映當(dāng)前屬性子空間的分類能力。但由于鄰域關(guān)系可能會(huì)產(chǎn)生不一致信息,把確定可分的樣本錯(cuò)誤劃分到邊界域中使得近似質(zhì)量在評(píng)價(jià)候選屬性時(shí),忽略邊界域中存在的確定可分的樣本,導(dǎo)致屬性約簡(jiǎn)結(jié)果的分類性能差。

針對(duì)上述問(wèn)題,本文在鄰域粒中考慮樣本的標(biāo)簽信息,提出監(jiān)督信息鄰域粒距離來(lái)描述邊界域樣本鄰域粒中不同標(biāo)簽之間的分離程度。通過(guò)監(jiān)督信息鄰域粒距離判斷邊界域樣本的可分性,定義了近似正域(approximate positive domain,APOS),來(lái)反映鄰域決策系統(tǒng)的分類能力。進(jìn)而重新定義了近似質(zhì)量,并討論了新定義的近似質(zhì)量的單調(diào)性,基于此設(shè)計(jì)出一種啟發(fā)式屬性約簡(jiǎn)算法。通過(guò)實(shí)驗(yàn)驗(yàn)證了本文提出的屬性約簡(jiǎn)方法的有效性。

1 基本概念

鄰域粗糙集是經(jīng)典粗糙集的擴(kuò)展模型之一,主要是解決經(jīng)典粗糙集模型處理數(shù)值型數(shù)據(jù)會(huì)造成信息丟失的問(wèn)題,本節(jié)主要回顧?quán)徲虼植诩南嚓P(guān)定義。

假設(shè)一個(gè)鄰域信息系統(tǒng)(neighborhood information system,NIS)表示為NNIS=(U,A,V,f,δ),其中,U={x1,x2,…,xn}是一個(gè)非空對(duì)象集合,也稱為論域;A是一個(gè)非空屬性集;V=∪a∈AVa,Va是屬性a的值域;f:U×A→V為一個(gè)映射函數(shù),對(duì)?x∈U,a∈A有f(x,a)∈Va;δ為鄰域半徑;當(dāng)滿足A=C∪D,C和D分別稱作條件屬性集和決策屬性集,鄰域信息系統(tǒng)就被稱作鄰域決策系統(tǒng),表示為NNDS=(U,C∪D,V,f,δ)。

定義1[5]對(duì)于鄰域信息系統(tǒng)NNIS=(U,A,V,f,δ),?B?A,關(guān)于?x∈U在B上的鄰域?yàn)?/p>

δB(x)={xi∈U|dB(x,xi)≤δ}

(1)

關(guān)于B的鄰域關(guān)系(neighborhood relationship, NR)定義為

NNRδ(B)={(x,y)∈U2|dB(x,y)≤δ}

(2)

(2)式中,dB(x,y)表示一種距離度量公式,常用的距離度量公式為歐氏距離,即

(3)

鄰域關(guān)系是一種相似關(guān)系,當(dāng)δ=0時(shí),鄰域關(guān)系則退化為等價(jià)關(guān)系。

定義2[5]對(duì)于鄰域信息系統(tǒng)NNIS=(U,A,V,f,δ),?B?A,?X∈U,關(guān)于X在B上的上、下近似集為

(4)

(5)

由此可得,關(guān)于集合X的正域、負(fù)域和邊界域分別為

(6)

(7)

(8)

正域表示論域U中確定屬于X的對(duì)象集合,負(fù)域表示論域U中確定不屬于X的對(duì)象集合,邊界域表示論域U中可能屬于X的對(duì)象集合。

定義3[5]對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ),U/D={D1,D2,…,Dm}是根據(jù)D得到的U的一個(gè)等價(jià)劃分,對(duì)于?B?C,決策類D關(guān)于B的上近似和下近似為

(9)

(10)

(9)—(10)式中,決策類D關(guān)于B的正域和邊界域分別表示為

(11)

(12)

定義4[5]對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ),對(duì)于?B?C,決策類D關(guān)于B的近似質(zhì)量為

(13)

(13)式中,|X|表示集合X的基數(shù)。

根據(jù)近似質(zhì)量的定義可知,γB(D)為[0,1]。γB(D)表示在論域U中根據(jù)條件屬性子集B,能夠確定為決策屬性D中某一決策類的樣本數(shù)占全體樣本的比率。顯然,近似質(zhì)量越大,決策屬性D對(duì)條件屬性子集B的依賴程度越強(qiáng)。

從粒計(jì)算的角度來(lái)說(shuō),樣本的鄰域可以看作成一個(gè)鄰域信息粒。Chen等[22]提出鄰域粒距離度量方式來(lái)計(jì)算鄰域信息粒的距離,其定義如下。

定義5對(duì)于鄰域信息系統(tǒng)NNIS=(U,A,V,f,δ),?B?A,?x,y∈U,假設(shè)gB(x)=δB(x)和gB(y)=δB(y)是2個(gè)鄰域信息粒,那么它們之間的鄰域粒距離表示為

(14)

(14)式中,|gB(x)⊕gB(y)|=|gB(x)∪gB(y)|-|gB(x)∩gB(y)|。

根據(jù)定義5可知,鄰域粒距離反映不同鄰域信息粒之間的差異性,并用于信息粒的相似性度量。鄰域粒距離D(gB(x),gB(y))滿足以下特性。

①非負(fù)性:D(gB(x),gB(y))≥0;

②對(duì)稱性:D(gB(x),gB(y))=D(gB(y),gB(x));

③三角不等式:D(gB(x),gB(z))+D(gB(z),gB(y))≥D(gB(x),gB(y))。

2 監(jiān)督信息鄰域粒距離

本節(jié)關(guān)注邊界域樣本鄰域的結(jié)構(gòu)信息,定義監(jiān)督信息鄰域粒距離來(lái)判斷邊界域樣本的可分性,將邊界域能夠區(qū)分的樣本近似地劃到正域中,以此提出近似正域的概念,從而更精準(zhǔn)刻畫(huà)鄰域決策信息系統(tǒng)的分類能力。

2.1 鄰域?；木窒扌?/h3>

本文認(rèn)為現(xiàn)有基于近似質(zhì)量的屬性約簡(jiǎn)結(jié)果的分類性能差,主要是由于其忽略了信息?；蟛灰恢聵颖究煞中缘膯?wèn)題,導(dǎo)致不能有效地指導(dǎo)屬性約簡(jiǎn)去除冗余屬性并保持鄰域決策系統(tǒng)的分類能力。

鄰域粗糙集是通過(guò)鄰域粒中樣本的標(biāo)簽一致性來(lái)判斷樣本屬于正域還是邊界域,圖1為鄰域信息?；膶?shí)例,不同顏色的各個(gè)形狀代表不同的類別。圖1中,A1和A3區(qū)域的樣本集合來(lái)說(shuō),這樣的劃分是合理的。而對(duì)于中間A2區(qū)域的邊界域樣本來(lái)說(shuō)則區(qū)分不夠明顯,因?yàn)槲挥贏2區(qū)域邊緣的部分樣本存在一些確定可分的樣本被誤劃分到邊界域中,所以本文認(rèn)為這一部分需要進(jìn)行再劃分。

圖1 鄰域信息?；痆5]Fig.1 Neighborhood information granulation

圖2展示了一個(gè)二維空間下三域的劃分,對(duì)于圖2中樣本x來(lái)說(shuō),直觀地觀察,它并沒(méi)有和決策類不相同的樣本混合,所以在實(shí)際應(yīng)用中,有理由認(rèn)為它是可分的。而在鄰域粗糙集原本正域的定義下,它不會(huì)被劃到正域中,因?yàn)樗泥徲蛑写嬖跇?biāo)簽不一致的樣本。從分類任務(wù)的角度考慮,雖然它的鄰域中有著不同類標(biāo)簽的樣本,但是通過(guò)觀察樣本x的鄰域中各類樣本標(biāo)簽的分布情況,不同類標(biāo)簽的樣本與相同類標(biāo)簽的樣本呈現(xiàn)相互分離的狀態(tài),也就是說(shuō)樣本x被認(rèn)為是可分的樣本是合理的。如果近似地把樣本x歸到正域中,更能精確刻畫(huà)當(dāng)前屬性子集的分辨能力。

圖2 一個(gè)二維空間的示例Fig.2 An example of a two-dimensional space

2.2 監(jiān)督信息鄰域粒距離

為了解決此問(wèn)題,本文通過(guò)分析鄰域粒中樣本的標(biāo)簽信息,尋找一種刻畫(huà)樣本可分性的方式,找出邊界域中存在的可分類樣本。

文中將樣本的監(jiān)督信息考慮到候選屬性評(píng)價(jià)標(biāo)準(zhǔn)中,提出監(jiān)督信息鄰域粒距離來(lái)量化鄰域粒中不同樣本標(biāo)簽的分布情況,并以此描述樣本的可分性。其主要思想是首先通過(guò)樣本x的鄰域中與樣本x具有相同類標(biāo)簽的樣本和不同類標(biāo)簽的樣本分別構(gòu)造出同類鄰域粒和異類鄰域粒,將這2個(gè)鄰域粒統(tǒng)稱為監(jiān)督信息鄰域粒,圖3給出樣本x的監(jiān)督信息鄰域粒的構(gòu)造過(guò)程。然后通過(guò)鄰域粒距離度量方式計(jì)算出這2個(gè)鄰域粒的距離來(lái)刻畫(huà)樣本x的鄰域中包含不同標(biāo)簽之間的差異程度,從而判斷樣本x是否能夠被區(qū)分。由于正域樣本的鄰域只存在一種標(biāo)簽信息,所以監(jiān)督信息鄰域粒距離主要用來(lái)區(qū)分邊界域樣本。

圖3 關(guān)于x的監(jiān)督信息鄰域粒Fig.3 Supervised information neighborhood granular of x

在給出監(jiān)督信息鄰域粒距離定義之前,本文需要采用文獻(xiàn)[23]中構(gòu)造粒球的方法來(lái)確定監(jiān)督信息鄰域粒的中心點(diǎn)和半徑。

定義6對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ),?B?C,關(guān)于?x∈U在B上的監(jiān)督信息鄰域粒的中心和半徑表示為

(15)

(16)

定義7對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ),?B?C,關(guān)于?x∈U在B上的監(jiān)督信息鄰域粒表示為

(17)

(18)

定義8對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ),?B?C,關(guān)于?x∈U在B上的監(jiān)督信息鄰域粒距離為

(19)

定義9對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ,α),?B?C,決策類D關(guān)于B的近似可分集表示為

SB(D)={x|x∈NBNDB(D),D(gs(x),gd(x))≥α}

(20)

(20)式中,α為[0,1]。

定義10對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ,α),?B?C,決策類D關(guān)于B的近似正域表示為

NAPOSB(D)=POSB(D)∪SB(D)

(21)

定義10近似正域并沒(méi)有嚴(yán)格的單調(diào)性,只能大致隨屬性的增加呈遞增的趨勢(shì),這是因?yàn)楸疚乃x的近似正域是根據(jù)樣本鄰域中樣本的標(biāo)簽信息所確定的,而樣本鄰域中的標(biāo)簽信息在每一次迭代中是不確定的。為了在屬性約簡(jiǎn)中更好地描述屬性重要度,本文又進(jìn)一步討論了具有單調(diào)性的近似質(zhì)量度量準(zhǔn)則構(gòu)成方式。

定義11對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ,α),B0=?,Bi=Bi-1∪,b∈C-Bi-1,i=1,2,…,|C|,{B0,B1,…,B|C|}稱為集合C的序列,用I(C)表示。那么決策類D關(guān)于Bi的遞推近似正域表示為

NAPOSBi(D)=NAPOSBi-1(D)∪NPOSBi(D)∪SBi(D)

(22)

(22)式中,i=1,2,…,|C|;i=1時(shí),APOSB0=?。

定義12對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ,α),B∈I(C),決策屬性D關(guān)于條件屬性子集B的近似質(zhì)量表示為

(23)

(23)式中,0≤γB≤1。

定理1假設(shè)有Bi-1,Bi∈I(C)且Bi-1?Bi,γBi-1和γBi分別是遞推近似正域下D關(guān)于Bi-1和Bi的近似質(zhì)量,那么γBi-1≤γBi。

證明:由于近似質(zhì)量的計(jì)算可分為正域和近似可分集2個(gè)部分,所以兩者可以分開(kāi)計(jì)算。

由于Bi-1?Bi,則有SBi-1(D)∪SBi(D)?SBi(D),同理,NPOSBi-1(D)∪NPOSBi(D)?NPOSBi(D)。所以,有NAPOSBi(D)?NAPOSBi-1(D)。

該定理說(shuō)明根據(jù)定義12構(gòu)造的近似質(zhì)量隨著候選屬性子集的增加而增大。

3 屬性約簡(jiǎn)

屬性約簡(jiǎn)的目的是得到一個(gè)滿足約束條件的最小屬性子集。對(duì)于一個(gè)鄰域決策系統(tǒng),有2|C|-1種屬性子集組合方式,所以尋找最優(yōu)約簡(jiǎn)結(jié)果是一個(gè)非確定性多項(xiàng)式(nondeterministic polynomially,NP)問(wèn)題。在實(shí)際應(yīng)用中,條件屬性個(gè)數(shù)往往很多,因而其計(jì)算成本是不可忽略的,故大量研究采用啟發(fā)式算法,尋找一個(gè)較優(yōu)的約簡(jiǎn)結(jié)果。不同的約束條件會(huì)產(chǎn)生不同的屬性約簡(jiǎn),Yao等[24]給出屬性約簡(jiǎn)的一般形式,如下所示。

定義13對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ),?B?C,ρ是一種約束條件,B能被稱為NNDS的一個(gè)約簡(jiǎn),當(dāng)且僅當(dāng):

①B滿足約束條件ρ;

②?B′?B,B′不能滿足約束條件ρ。

本文利用重新定義的近似質(zhì)量來(lái)表示約束條件ρ,并給出相應(yīng)的屬性重要度定義。

定義14對(duì)于鄰域決策系統(tǒng)NNDS=(U,C∪D,V,f,δ,α),B∈I(C),b∈C-B,那么b相對(duì)于B的屬性重要度為

(24)

下面根據(jù)前向增加的策略來(lái)設(shè)計(jì)一種啟發(fā)式屬性約簡(jiǎn)算法,具體實(shí)現(xiàn)過(guò)程如下所示。

算法1基于監(jiān)督信息鄰域粒距離的屬性約簡(jiǎn)

輸入:鄰域決策系統(tǒng)NNDS=(U,C∪D,δ,α);

輸出:約簡(jiǎn)結(jié)果red。

1.B0←φ,i←0;

3.從C-Bi選擇NSIGα(b,Bi,D)最大的屬性b;

6.否則轉(zhuǎn)步驟3;

7.red←Bi;

8.輸出約簡(jiǎn)結(jié)果red。

分析上述算法的總時(shí)間復(fù)雜度:設(shè)|U|表示論域中的樣本總量,|B|表示條件屬性個(gè)數(shù),n表示迭代次數(shù)。計(jì)算樣本鄰域和監(jiān)督信息鄰域粒距離的時(shí)間復(fù)雜度為O(|U|2);每一次選擇屬性這一步驟的時(shí)間復(fù)雜度為O(|B|)。綜上所述,啟發(fā)式算法的總體時(shí)間復(fù)雜度為O(n·|B|·|U|2)。

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

為了驗(yàn)證本文提出的屬性約簡(jiǎn)算法的有效性,本文從UCI數(shù)據(jù)集中選取9組數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn),其中數(shù)據(jù)集名稱、樣本數(shù)量、屬性數(shù)量和決策類數(shù)量的信息如表1所示。實(shí)驗(yàn)測(cè)試的硬件環(huán)境為:CPU Intel Core i7-9700 CPU@3.00GHz,RAM為16GByte;軟件環(huán)境為:Windows 10 OS和Python 3.8。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental data sets

4.1 參數(shù)分析

實(shí)驗(yàn)前對(duì)9組數(shù)據(jù)集的條件屬性值進(jìn)行歸一化處理,使得所有條件屬性值為[0,1]。在本文提出的算法中,包含了鄰域半徑δ和閾值α兩個(gè)輸入?yún)?shù)。由于不同的參數(shù)取值對(duì)約簡(jiǎn)結(jié)果有不同的影響,所以本組實(shí)驗(yàn)連續(xù)等距選取了10個(gè)鄰域半徑和9個(gè)閾值α用于觀察在不同鄰域半徑和不同閾值下的約簡(jiǎn)結(jié)果在KNN和SVM兩個(gè)分類器上的分類精度。圖4為數(shù)據(jù)集在KNN分類器上的分類精度;圖5為數(shù)據(jù)集在SVM分類器上的分類精度。顏色代表相對(duì)分類精度大小,顏色由深藍(lán)色向深紅色變化,表示分類精度隨之變大。

圖4 KNN分類器分類精度Fig.4 KNN classifier classification accuracy

圖5 SVM分類器分類精度Fig.5 SVM classifier classification accuracy

從圖4中觀察分析可得,在閾值α較小和半徑較小的時(shí)候約簡(jiǎn)結(jié)果的分類精度很低,這是因?yàn)檫^(guò)于小的α值,對(duì)于近似正域的劃分過(guò)于寬松,雖然得到的約簡(jiǎn)屬性子集相對(duì)較少,但是容易造成約簡(jiǎn)選擇的屬性子集的表征能力不強(qiáng),進(jìn)而約簡(jiǎn)結(jié)果在分類器上的分類精度較低,而閾值α較大時(shí),大部分的數(shù)據(jù)集上的分類精度比較高,尤其是Wine數(shù)據(jù)集和Wdbc屬性集,在閾值α在0.7和0.8的情況下,分類精度較高,但是在較大的閾值α的情況下,絕大多數(shù)的數(shù)據(jù)集的約簡(jiǎn)刪除的屬性數(shù)量不理想,這與屬性約簡(jiǎn)的目的不符。

圖5展示了SVM分類器下的分類精度,其分類精度有著和KNN分類器類似的情況,閾值α較小或者半徑太小下的約簡(jiǎn)性能都比較差。結(jié)合圖4和圖5還能發(fā)現(xiàn),隨著閾值α的增大,2個(gè)分類器的分類精度大致先呈上升的趨勢(shì),然后又呈一定程度的下降趨勢(shì),所以綜合在不同閾值α下的約簡(jiǎn)結(jié)果以及在KNN分類器和SVM分類器的分類精度,本文建議閾值α的取值為[0.3,0.7]。在下面的對(duì)比實(shí)驗(yàn)中,選擇在所有數(shù)據(jù)集中約簡(jiǎn)結(jié)果都較優(yōu)的閾值α=0.5。

4.2 對(duì)比實(shí)驗(yàn)

對(duì)比實(shí)驗(yàn)將本文設(shè)計(jì)的屬性約簡(jiǎn)算法(supervised information neighborhood granular distance reduction algorithm,SINGD)與NRS[5]、HANDI[25]和WNRS[15]算法作了約簡(jiǎn)結(jié)果和分類精度兩方面的比較。

表2給出約簡(jiǎn)結(jié)果屬性數(shù)量的比較。由于每組數(shù)據(jù)集的數(shù)據(jù)分布情況不同,對(duì)應(yīng)的最優(yōu)半徑也不同,表2的最后一列給出了實(shí)驗(yàn)中每組數(shù)據(jù)集選用的半徑。觀察實(shí)驗(yàn)結(jié)果可知,SINGD算法相對(duì)于原始屬性集大幅度地刪除了冗余屬性。相較于其他算法,在Wdbc數(shù)據(jù)集和Foresttype數(shù)據(jù)集上約簡(jiǎn)的約簡(jiǎn)屬性子集要多于HANDI算法;在Wine數(shù)據(jù)集、Heart數(shù)據(jù)集、Parkisons數(shù)據(jù)集、Ionosphere數(shù)據(jù)集、Sonar數(shù)據(jù)集、Leaf數(shù)據(jù)集和Segment數(shù)據(jù)集上要少于HANDI算法;在所有數(shù)據(jù)集上的約簡(jiǎn)屬性子集都不多于NRS算法;在9組數(shù)據(jù)集上的平均約簡(jiǎn)數(shù)量,SINGD算法要優(yōu)于NRS和HANDI算法。

表2 約簡(jiǎn)屬性數(shù)量比較Tab.2 Number comparison of attribute reduction

WNRS算法在約簡(jiǎn)數(shù)量上比較于本文的算法數(shù)量會(huì)少一些,SINGD算法只有在一部分的數(shù)據(jù)集上要優(yōu)于WNRS算法,這是因?yàn)楸疚乃惴ú捎玫氖恰疤砑印笨刂撇呗詠?lái)設(shè)計(jì)算法,只滿足定義13中第一個(gè)約束條件,這樣做的目的是降低算法的時(shí)間消耗,而WNRS算法采用“添加-刪除”控制策略?？傮w來(lái)說(shuō),在屬性約簡(jiǎn)結(jié)果方面,本文提出的約簡(jiǎn)算法能夠?qū)崿F(xiàn)有效地刪除冗余屬性。

表3和表4具體比較了各算法屬性約簡(jiǎn)結(jié)果在KNN分類器和SVM分類器上的分類精度。本組實(shí)驗(yàn)采用十折交叉驗(yàn)證的方法,分類精度如表3、表4所示。

表3 KNN分類器精度比較Tab.3 Accuracy comparison of KNN classifier

表4 SVM分類器精度比較Tab.4 Accuracy comparison of SVM classifier

通過(guò)表3和表4觀察可得,SINGD算法不管是在KNN分類器還是SVM分類器上都有較高的分類精度,在所選數(shù)據(jù)集上的平均精度比其他算法都要好。在KNN分類器上只有Wdbc數(shù)據(jù)集的分類精度低于原始數(shù)據(jù)集,在SVM分類器上除了Wine數(shù)據(jù)集,其余數(shù)據(jù)集的分類精度都比原始數(shù)據(jù)集高,所以總體上,SINGD算法的約簡(jiǎn)結(jié)果的分類精度要優(yōu)于原始數(shù)據(jù)集的分類精度,說(shuō)明SINGD算法能夠有效地刪除冗余的、無(wú)關(guān)的屬性,并且不會(huì)降低鄰域決策系統(tǒng)原有的分類性能。而在絕大部分?jǐn)?shù)據(jù)集中,SINGD算法在KNN分類器上每個(gè)數(shù)據(jù)集都要比NRS算法的分類精度高,在SVM分類器上只有Iono數(shù)據(jù)集和Wine數(shù)據(jù)集的分類精度比NRS算法低。與HANDI算法相比,在KNN分類器中,SINGD算法分類精度在Sonar數(shù)據(jù)集和Segment數(shù)據(jù)集上要低于HANDI算法,但是在這2組數(shù)據(jù)集中,SINGD算法約簡(jiǎn)屬性數(shù)量要少于HANDI算法,尤其是在Sonar數(shù)據(jù)集上;而在SVM分類器上大部分要優(yōu)于HANDI算法,除了Wine數(shù)據(jù)集。與WNRS算法相比,在KNN分類器上的Parkinsons數(shù)據(jù)集和在SVM分類器上的Heart數(shù)據(jù)集與Foresttype數(shù)據(jù)集表現(xiàn)優(yōu)于SINGD算法,所以結(jié)合表2來(lái)看,WNRS算法雖然約簡(jiǎn)的屬性數(shù)量少,但是可能刪除了某些重要的屬性。本文的算法充分考慮了邊界域的有效信息,更全面地考慮了屬性的分類能力,因此得到的約簡(jiǎn)結(jié)果性能更好。

4.3 比較檢驗(yàn)分析

本文從統(tǒng)計(jì)學(xué)的角度對(duì)本文算法和對(duì)比算法進(jìn)行了性能評(píng)估,利用Friedman檢驗(yàn)和Nemenyi后續(xù)檢驗(yàn)來(lái)發(fā)現(xiàn)算法之間的差異性,結(jié)果如圖6所示。

圖6 不同約簡(jiǎn)算法的Friedman檢驗(yàn)Fig.6 Friedman test for different reduction algorithm

觀察圖6可知,在KNN分類器上,SINGD算法與RAW和HANDI的橫線段無(wú)交疊部分;在SVM分類器上與RAW無(wú)交疊部分,說(shuō)明從統(tǒng)計(jì)學(xué)的角度來(lái)看,與它們具有顯著差別。雖然其他算法都有部分交疊,但是通過(guò)圖6發(fā)現(xiàn)本文算法相對(duì)于所選對(duì)比算法的性能都有一定的顯著性差異,在所選的9個(gè)數(shù)據(jù)集上SINGD算法具有最高的平均rank,說(shuō)明本文算法性能表現(xiàn)更好。

綜上所述,通過(guò)對(duì)閾值α的分析、對(duì)比實(shí)驗(yàn)以及比較檢驗(yàn)實(shí)驗(yàn),說(shuō)明本文所提出的屬性約簡(jiǎn)算法能夠有效地刪除冗余屬性,并提高分類精度,驗(yàn)證了其合理性和有效性。

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

本文把樣本的監(jiān)督信息引入到對(duì)象的鄰域中,提出監(jiān)督信息鄰域粒距離來(lái)描述邊界域樣本鄰域粒中不同標(biāo)簽的分離程度,并基于此定義了近似正域和新的近似質(zhì)量,從而避免了鄰域關(guān)系引起信息不一致的負(fù)面影響,可以更精確地刻畫(huà)鄰域決策系統(tǒng)的分類能力。實(shí)驗(yàn)結(jié)果表明,提出的屬性約簡(jiǎn)方法得到的約簡(jiǎn)結(jié)果與以往的方法相比,有效地刪除了冗余屬性,并提高了約簡(jiǎn)后鄰域系統(tǒng)的分類性能。