盛 魁 卞顯福 董 輝 馬 健

1(亳州職業(yè)技術(shù)學(xué)院信息工程系 安徽 亳州 236800)2(中國科學(xué)技術(shù)大學(xué)軟件學(xué)院 安徽 合肥 230051)

0 引 言

屬性約簡[1]是一種重要的數(shù)據(jù)挖掘方法,它通過對樣本數(shù)據(jù)中的屬性進行選擇,從而達到了知識發(fā)現(xiàn)的效果,同時它也是一種有效的數(shù)據(jù)維度約簡工具,有助于提高機器學(xué)習(xí)等相關(guān)算法的學(xué)習(xí)性能,是目前數(shù)據(jù)分析領(lǐng)域的一個研究熱點。

屬性約簡是粗糙集理論的一個重要應(yīng)用。目前的屬性約簡已經(jīng)適用于離散型[2]、連續(xù)型[3-4]以及混合類型的信息系統(tǒng)[5],其中基于混合信息系統(tǒng)的屬性約簡算法通過鄰域粗糙集模型進行實現(xiàn)。Hu等[5]學(xué)者通過鄰域依賴度在混合信息系統(tǒng)中構(gòu)造屬性約簡算法。Zhao等[6]通過條件熵在混合不完備信息系統(tǒng)構(gòu)造屬性約簡算法。Zhang等[7]利用模糊熵也構(gòu)造出了相應(yīng)的屬性約簡算法。因此，目前基于混合信息系統(tǒng)的屬性約簡方法逐漸受到學(xué)者們的廣泛關(guān)注。

然而,Liang等[8]指出,傳統(tǒng)的屬性約簡通過單一的度量方法不能夠得到更好的屬性約簡結(jié)果,通過多個方法共同評估屬性可以提高屬性約簡算法的性能,因此近年來也提出了一些組合度量的屬性約簡方法[9-10],在這些方法中,很少有對混合信息系統(tǒng)的屬性約簡進行相關(guān)研究,這促使我們在混合信息系統(tǒng)構(gòu)造出基于組合度量的屬性約簡算法。

鄰域依賴度是混合信息系統(tǒng)屬性約簡中一種常用的啟發(fā)式函數(shù)[5,11],知識粒度是描述屬性對信息系統(tǒng)?；芰Φ囊环N常用度量[12]。因此，本文將知識粒度在混合信息系統(tǒng)中進行推廣,提出鄰域知識粒度,然后將鄰域依賴度與鄰域知識粒度進行結(jié)合提出鄰域組合度量,并將該度量方法作為啟發(fā)式函數(shù)來構(gòu)造屬性約簡,最后通過一系列實驗來驗證該算法的性能。

1 基本理論

混合數(shù)據(jù)是一種復(fù)雜的數(shù)據(jù)類型,通常是由離散型和連續(xù)型數(shù)據(jù)共同構(gòu)成的數(shù)據(jù)集,在屬性約簡的研究中,混合數(shù)據(jù)被定義為混合信息系統(tǒng)的形式,混合信息系統(tǒng)可表示為IS=(U,A),其中U為對象集,即該數(shù)據(jù)集的樣本空間,每個樣本稱之為對象,A為屬性集,即該數(shù)據(jù)集的特征集,若屬性集A=C∪D,且C∩D=?,其中，D為數(shù)據(jù)集的類標記特征屬性,那么此信息又被稱為決策信息系統(tǒng),C、D分別稱為條件屬性和決策屬性。

在混合信息系統(tǒng)中,鄰域粗糙集模型是一種常用的處理模型,即通過構(gòu)造鄰域關(guān)系來進行模型計算。

定義1[5]設(shè)混合信息系統(tǒng)IS=(U,A),屬性集B?A,那么B在樣本空間U上確定的δ鄰域關(guān)系為：

(1)

這里的δ稱為鄰域半徑,ΔB(x,y)為廣義的距離度量函數(shù),即對于B={a1,a2,…,am},廣義距離度量ΔB(x,y)可表示為:

(2)

當屬性ai為離散型屬性時:

(3)

當屬性ai為連續(xù)型屬性時:

(4)

(5)

性質(zhì)1[5]對于混合信息系統(tǒng)IS=(U,A),若P?Q?A且0≤δ1≤δ2,那么:

對象的鄰域類相當于該對象在樣本空間中給定鄰域半徑下的相近樣本集。圖1為對象鄰域類的示意圖。

圖1 對象的鄰域類示意圖

(6)

(7)

(8)

鄰域依賴度滿足0≤γB(D)≤1。

鄰域依賴度反映的是混合信息系統(tǒng)中決策類下近似樣本占據(jù)所有樣本的比例,也是描述條件屬性集和決策屬性之間關(guān)系程度的一種度量,因此該度量可作為一種啟發(fā)式函數(shù)來進行混合信息系統(tǒng)的屬性約簡。

2 混合信息系統(tǒng)的鄰域組合度量方法

在文獻[5]中,學(xué)者們通過鄰域依賴度提出了相應(yīng)的屬性約簡算法,均能夠?qū)旌闲畔⑾到y(tǒng)進行有效的維度約簡。Liang等[8]提出,通過單一的度量方法不能夠達到較好的屬性集評估效果,尤其是對于依賴度度量,結(jié)合其他視角的度量方法可以進行更優(yōu)的屬性約簡。

Liang等[8]通過將傳統(tǒng)的依賴度和粒計算視角下的知識粒度進行結(jié)合,提出一種新的粒度屬性集評估方法,并通過實驗驗證了該方法的優(yōu)越性。本節(jié)將這種方法推廣到混合信息系統(tǒng)下,提出一種新的組合度量方法。

在提出組合度量方法之前,首先將粒計算模型中傳統(tǒng)知識粒度在混合信息系統(tǒng)中的鄰域關(guān)系下進行改進與推廣,提出鄰域知識粒度。

(9)

鄰域知識粒度表示的是鄰域關(guān)系對樣本空間中每個對象的粒化能力的一種評估,鄰域知識粒度越大,表明樣本空間中每個對象的鄰域類越小,說明該屬性集對樣本空間的?；芰υ綇?。

NGKδ2(B)≤NGKδ1(B)

(10)

證明當鄰域半徑滿足0≤δ1≤δ2時,根據(jù)定義1中鄰域關(guān)系的定義，對于?x,y∈U,若ΔB(x,y)≤δ1必有ΔB(x,y)≤δ2。因此:

進一步:

即NGKδ2(B)≤NGKδ1(B)。

NGK(P)≤NGK(Q)

(11)

證明當屬性集滿足P?Q?A時,根據(jù)定義1中鄰域關(guān)系的定義，對于?x,y∈U,若ΔQ(x,y)≤δ則ΔP(x,y)≤δ。因此:

進一步:

即NGK(P)≤NGK(Q)。

在鄰域知識粒度的基礎(chǔ)上可以將鄰域依賴度和鄰域知識粒度進行結(jié)合,提出混合信息系統(tǒng)下的鄰域組合度量方法。

NMMB(D)=γB(D)·NGK(B)

(12)

NMMP(D)≤NMMQ(D)

(13)

證明根據(jù)文獻[5],當屬性集滿足P?Q?A,那么鄰域依賴度有:

γP(D)≤γQ(D)

同時根據(jù)性質(zhì)3，有NGK(P)≤NGK(Q)，因此可以得出NMMP(D)≤NMMQ(D)。

性質(zhì)4表明,隨著屬性的逐漸增加,其鄰域組合度量也是逐漸增加的,這滿足了屬性約簡中度量函數(shù)的一個很重要的條件,因此根據(jù)鄰域組合度量作為啟發(fā)式函數(shù),可以構(gòu)造出混合信息系統(tǒng)的屬性約簡算法。

3 啟發(fā)式屬性約簡算法

信息系統(tǒng)的屬性約簡是粗糙集理論在數(shù)據(jù)挖掘領(lǐng)域中的重要應(yīng)用,是降低復(fù)雜數(shù)據(jù)維度的一種重要方法,本節(jié)將第2節(jié)中提出的鄰域組合度量作為啟發(fā)式函數(shù),提出一種混合信息系統(tǒng)的啟發(fā)式屬性約簡算法。

定義7對于混合決策信息系統(tǒng)IS=(U,C∪D),若屬性集B?C是整個條件屬性集C的屬性約簡,那么必須同時滿足：

NMMB(D)=NMMC(D)

(14)

?b∈B,NMMB-(D)

(15)

定義7表示的是基于鄰域組合度量屬性約簡算法的定義,其中:式(14)表明最終屬性約簡結(jié)果必須和整個屬性全集保持一致的鄰域組合度量結(jié)果；式(15)表明這個屬性約簡結(jié)果不能再包含其他冗余的屬性,即對屬性約簡集中剔除任意一個屬性,式(14)都不成立,因此式(15)保證了最終約簡結(jié)果是最精簡的。

根據(jù)定義7中關(guān)于鄰域組合度量屬性約簡的定義,本文按照一般啟發(fā)式屬性約簡的構(gòu)造方法,提出本文的屬性約簡算法。

算法1混合信息系統(tǒng)的鄰域組合度量啟發(fā)式屬性約簡。

輸入：混合信息系統(tǒng)IS=(U,C∪D),鄰域半徑δ。

輸出：屬性約簡結(jié)果red,其中red?C。

1. 初始化red=?,NMMred(D)=1;

2. for ?ai∈C-reddo

3. 計算

sai=NMMred∪{ai}(D)-NMMred(D);

4. end for

8. 返回Step2;

9. else

10. returnred;

4 實驗分析

為了驗證本文所提出的鄰域組合度量啟發(fā)式屬性約簡算法具有更優(yōu)的性能,本節(jié)將通過實驗來比較分析,相關(guān)的實驗主要包括兩個方面,分別為比較算法的屬性約簡效率和比較算法的約簡結(jié)果性能。

4.1 實驗準備

實驗所運用的數(shù)據(jù)集如表1所示,這些數(shù)據(jù)集全部來自于UCI數(shù)據(jù)集,每個數(shù)據(jù)集都為包含離散型屬性和連續(xù)型屬性的混合類型數(shù)據(jù)。本實驗進行比較的算法分別為:(1) 基于鄰域依賴度的混合信息系統(tǒng)屬性約簡[5];(2) 基于最大決策的鄰域粗糙集屬性約簡[13];(3) 基于鄰域區(qū)分度的屬性約簡[14]。所有算法用Java語言編程實現(xiàn),并通過Windows7旗艦版CPU i5 7500 3.2 GHz平臺進行運行。

表1 實驗數(shù)據(jù)集

4.2 參數(shù)設(shè)定

在本文提出的屬性約簡算法中,鄰域半徑是一個輸入?yún)?shù),目前的研究結(jié)果表明[5],鄰域半徑取值不恰當可能會對屬性約簡的結(jié)果產(chǎn)生一定的負面影響,因此，本節(jié)將研究鄰域半徑的設(shè)定問題。

按照其他文獻的研究方法[3-4,9,13],將鄰域半徑選取一系列的值分別進行實驗,這樣每個鄰域半徑下都會得到對應(yīng)的屬性約簡結(jié)果。然后將得到的屬性約簡結(jié)果利用支持向量機(SVM)和樸素貝葉斯(NB)兩種分類器分別進行分類訓(xùn)練,評估出該屬性子集對應(yīng)的分類精度,利用多種分類器進行分類精度評估，使得結(jié)果更具一定說服力，從而驗證實驗結(jié)果的穩(wěn)固性。最后，對每個數(shù)據(jù)集的結(jié)果進行觀察,選擇出屬性約簡結(jié)果較小且分類精度較高的約簡集作為最終的屬性約簡結(jié)果,其對應(yīng)的鄰域半徑作為最佳的屬性約簡鄰域半徑。本實驗設(shè)定鄰域半徑在區(qū)間[0.05，0.5]內(nèi)以0.05為間隔分別取值進行實驗,得到屬性約簡結(jié)果和對應(yīng)的分類精度結(jié)果如圖2所示。

(a) Heart

(b) Hepatitis

(c) Horse

(d) German

(e) Sick圖2 鄰域半徑與屬性約簡分類精度結(jié)果

觀察圖2可以發(fā)現(xiàn),隨著鄰域半徑逐漸增大,其選擇出的約簡集也逐漸增大,這主要是由于隨著鄰域半徑的增大,其每個對象的鄰域類也逐漸增大,這種增大弱化了對屬性的區(qū)分能力,因此約簡后的屬性會逐漸增多。然而，屬性增多的同時,分類精度表現(xiàn)出了另一種變化規(guī)律。一開始分類精度逐漸增大,達到一定值后不再增大或逐漸減小,這主要是由于一開始屬性增多時,進行分類的性能越好,當屬性增加到一定程度時,新加進來的屬性可能會影響數(shù)據(jù)的分類,因此數(shù)據(jù)的分類精度反而降低。所以鄰域半徑選擇過高或過低都不能得到很好的實驗結(jié)果。分析圖2可以看出鄰域半徑選擇為0.2左右最佳,因此本實驗將鄰域半徑設(shè)定為0.2進行實驗。

4.3 屬性約簡效率比較

圖3為三種對比算法和本文算法的屬性約簡效率比較結(jié)果圖,橫軸為實驗數(shù)據(jù)集,縱軸為時間(單位s)。觀察比較結(jié)果可以發(fā)現(xiàn),參與比較的文獻[14]算法具有較大的屬性約簡用時,而文獻[5]算法、文獻[13]算法和本文算法的用時較少一些,其中文獻[13]算法的用時稍高,文獻[5]算法用時稍低,本文算法的用時位于二者之間。這主要是由于文獻[5]算法是基于鄰域依賴度的屬性約簡算法,而本文算法是鄰域組合度量屬性約簡,在文獻[5]算法的基礎(chǔ)上增加了鄰域知識粒度,因此約簡時的計算量會稍高一下,但是整體的差距不是特別大。

圖3 各算法屬性約簡時間比較

4.4 屬性約簡結(jié)果比較

表2所示的是3種對比算法和本文算法的屬性約簡集大小的比較結(jié)果,觀察可以發(fā)現(xiàn),本文的算法得到的約簡集大小整體上比其他3種算法的約簡集要小一些,例如數(shù)據(jù)集Horse、German和Sick。這主要是由于多種度量方法對屬性的選擇方面更加嚴格,同時對屬性的分類性能評估得更加精準,從而使得選擇出的屬性更加的少。

表2 各算法屬性約簡結(jié)果比較

表3為三種對比算法和本文算法的屬性約簡集在SVM和NB兩種分類器下分類性能比較結(jié)果。觀察表3可以發(fā)現(xiàn),在大部分數(shù)據(jù)集中,本文所提出的屬性約簡算法的分類精度提高了2%～3%,例如數(shù)據(jù)集Hepatitis、German和Sick。這主要是由于多種度量方法的組合度量能夠?qū)傩缘母鞣矫婺芰M行性能評估,從而可以對分類更為關(guān)鍵的屬性進行有效的鑒別,因此本文算法得到的約簡結(jié)果具有更高的分類精度。

表3 各算法屬性約簡結(jié)果分類精度比較 %

綜合實驗的各方面比較可以看出,本文所提出的鄰域組合度量方法在混合信息系統(tǒng)中具有更好的屬性約簡效果。

5 結(jié) 語

屬性約簡是一種重要的數(shù)據(jù)挖掘方法,同時也是一種有效的數(shù)據(jù)維度約簡工具。由于現(xiàn)實環(huán)境下數(shù)據(jù)類型復(fù)雜,本文提出一種混合信息系統(tǒng)下的屬性約簡方法。首先在混合信息系統(tǒng)下提出鄰域知識粒度用于對信息系統(tǒng)屬性集粒化性能進行評估,然后將鄰域知識粒度與混合信息系統(tǒng)下的鄰域依賴度進行結(jié)合,提出鄰域組合度量,并將該度量作為啟發(fā)式函數(shù)來構(gòu)造屬性約簡算法。實驗結(jié)果表明,所提出的屬性約簡算法具有更好的屬性約簡效果。