基于知識?；男畔⑾到y(tǒng)增量式屬性約簡

(四川文理學院 智能制造學院，四川 達州 635000)

屬性約簡是粗糙集理論[1]在機器學習和知識發(fā)現(xiàn)等領(lǐng)域中一種常用的數(shù)據(jù)處理工具，它通過對數(shù)據(jù)中冗余屬性進行刪除從而達到更好的分類性能。在現(xiàn)實的數(shù)據(jù)中，數(shù)據(jù)快速更新，每時每刻都有新的數(shù)加入，而傳統(tǒng)的非增量式屬性約簡在求動態(tài)數(shù)據(jù)的約簡集時需要進行大量的重復計算，這樣消耗了大量的時間和空間，不能很好地滿足實際的需求[2,3]。

增量式屬性約簡[2,3]相對于傳統(tǒng)的屬性約簡，是一種專門針對動態(tài)數(shù)據(jù)集的約簡方法，它能夠在原先約簡集的基礎上進一步導出更新后數(shù)據(jù)集的約簡，因而大大降低了時間的消耗[4]。在數(shù)據(jù)集的動態(tài)變化過程中，屬性的不斷增加是一種常見的形式[5]，對于這類數(shù)據(jù)集的動態(tài)屬性約簡，學者們提出了大量的方法，龍浩等[6]學者運用信息系統(tǒng)的差別矩陣，提出了當信息系統(tǒng)動態(tài)變化后的差別矩陣更新，并利用更新后的差別矩陣來進行增量式屬性約簡。葛浩等[7]學者也利用了差別矩陣構(gòu)造出了類似的增量式屬性約簡算法。馮少榮等[8]學者通過改進的差別矩陣進一步構(gòu)造增量式屬性約簡。吳曉瑛等[9]學者通過區(qū)分矩陣提出了一種維度增量的屬性約簡算法，景運革等[10]學者通過關(guān)系矩陣的增量更新也提出一種增量式屬性約簡，同時運用知識粒度的矩陣形式來進行屬性約簡[11]?？梢?，矩陣方法在增量式屬性約簡中占有很重要的地位，但是矩陣具有時間復雜度和空間復雜度高等缺點[9,11]，因而這些算法在計算效率方面具有一定的不足。

知識粒度是粒計算模型中評估信息系統(tǒng)知識?；潭鹊囊环N度量方法，目前成功的運用于信息系統(tǒng)中不確定性度量、決策分析等領(lǐng)域[12-14]，同時也是構(gòu)造信息系統(tǒng)屬性約簡的一種重要方法[15]，文獻[15]證明了基于知識粒度具有較好的屬性約簡效果，然而這種屬性約簡方法是非增量式的，不能滿足現(xiàn)實環(huán)境下動態(tài)數(shù)據(jù)的處理需求，因此本文在原來知識粒度屬性約簡的基礎上，提出一種針對信息系統(tǒng)屬性不斷增加時的增量式屬性約簡算法。文中首先提出一種當信息系統(tǒng)屬性增加時知識粒度的增量式計算方法，并證明這種計算方式可以大大減少重復計算，然后根據(jù)這種增量式計算提出一種增量式屬性約簡，所提出的增量式屬性約簡算法是在信息系統(tǒng)原先屬性約簡的結(jié)果上進行的進一步計算，避免了對已有數(shù)據(jù)的重復計算，提高了動態(tài)數(shù)據(jù)的處理效率，仿真實驗結(jié)果表明了該算法在約簡結(jié)果和時間效率方面都具有更好的性能。

1 基本理論

在屬性約簡中，數(shù)據(jù)集被描述成信息系統(tǒng)[1]的形式，一個信息系統(tǒng)可表示為IS=(U,A,V)，其中U為非空有限對象集，稱為論域，A為非空有限屬性集，V為屬性集的值域，若屬性集A=C∪D，且C∩D=φ，那么此信息又被稱為決策信息系統(tǒng)，其中C,D被稱為條件屬性和決策屬性。

對于屬性子集B?A可以導出一個等價關(guān)系RB,其定義為

RB={(x,y)∈U|?a∈B,a(x)=a(y)}

通過等價關(guān)系RB可以在論域U上誘導出一個劃分U/RB={X1,X2,…,Xm}，簡單表示為U/B，其中?Xi∈(U/B)稱為x關(guān)于B的等價類。

對于信息系統(tǒng)IS=(U,A,V)，設P,Q?A，由屬性子集P誘導的劃分為U/P={X1,X2,…,Xm}，Q誘導的劃分為U/Q={Y1,Y2,…,Yn}，對于偏序關(guān)系滿足(U/P)?(U/Q)當且僅當?Xi∈(U/P)存在Yj∈(U/P)使得Xi?Yj，也可以稱P比Q更精細。如果(U/P)?(U/Q)且(U/P)≠(U/Q)，稱P比Q更嚴格精細，表示為(U/P)(U/Q)[12-14]。

定義1[12-13]：設信息系統(tǒng)IS=(U,A,V)，對于屬性子集B?A導出的劃分U/B={X1,X2,…,Xm}，那么信息系統(tǒng)基于B的知識粒度定義為

定義1所示的是知識粒度的基本定義，它描述了等價關(guān)系對整個知識空間?；毘潭鹊囊环N評估，是粒計算理論中度量屬性子集分類能力的一種重要方法[12-13]。

定義2[11]：對于信息系統(tǒng)IS=(U,A,V)，若B1,B2?A，那么B2關(guān)于B1的知識粒度定義為

GK(B2|B1)=GK(B1)-GK(B1∪B2)

定義2是從知識粒度的角度，用來度量信息系統(tǒng)中兩個屬性子集之間的關(guān)系程度，這種關(guān)系程度的度量為基于知識粒度的屬性約簡的提出提供了理論基礎。

定義3[11]：設決策信息系統(tǒng)為DIS=(U,C∪D,V)，B?C是該信息系統(tǒng)的一個屬性約簡當且僅當

①GK(D|C)=GK(D|B)

② ?a∈B,GK(D|B-{a})>GK(D|B)

根據(jù)定義3的屬性約簡定義，一種新的屬性約簡算法被提出[15]，具體如算法1[15]所示。

算法1 基于知識粒度的屬性約簡算法

整個算法1的屬性約簡過程可以通過圖1所示的流程圖來表示。其主要過程是通過知識粒度作為啟發(fā)式函數(shù)，對屬性進行啟發(fā)式搜索，每次選擇出屬性重要度最大的屬性添加入屬性約簡結(jié)果中，若剩余屬性中最大的屬性重要度為0，那么此時認為剩余的所有屬性都是冗余的，則直接輸出最終的屬性約簡結(jié)果。

2 知識粒度的增量式屬性約簡

2.1 知識粒度的增量式更新

由于現(xiàn)實數(shù)據(jù)集不斷增量更新，傳統(tǒng)的方法屬性約簡算法面臨著時間和空間復雜度高的挑戰(zhàn)[3]。

圖1 算法1的流程圖

Wang[5]等學者提出了一種信息熵的增量更新方法，對于屬性不斷增加的數(shù)據(jù)集，該方法在屬性約簡的過程中大大地減少了重復計算量，有著較高的約簡效率，因此本文在此基礎上，將該更新方法應用于知識粒度的增量計算中。

由于信息系統(tǒng)增加屬性后，論域的劃分逐漸變的更加精細，因此增加屬性集ΔB后，那么就滿足關(guān)系(U/B′)?(U/B)，并且信息系統(tǒng)增加屬性后，會使得原先部分的等價類發(fā)生進一步的劃分，因此將U/B′中的等價類分成兩大類，第一類Φ表示的是未進行進一步劃分的等價類，而Ψ表示的是U/B中進一步劃分后的等價類。

由于信息系統(tǒng)的知識粒度與論域的劃分直接相關(guān)，而增加屬性集后，論域的劃分逐漸變得越來越精細，根據(jù)知識粒度的變化關(guān)系，因此接下來將等價類的這種變化機制運用于知識粒度的增量更新。

定理1：對于信息系統(tǒng)IS=(U,A,V)，屬性子集B?A在論域U上所誘導的劃分為U/B={X1,X2,…,Xm}，屬性子集B對應的知識粒度為GK(B)，當增加屬性集ΔB后，令B′=B∪ΔB,設U/B′=Φ∪Ψ，其中Φ,Ψ同定義4，那么知識粒度GK(B′)滿足

GK(B′)=GK(B)-Γ1

這里的

根據(jù)定義1知識粒度的定義有

對于上式中的通項

將Θi展開可以得到

即

那么

由于

所以

即

GK(B′)=GK(B)-Γ1

其中

證畢。

定理1指出，當信息系統(tǒng)增加屬性集后，知識粒度是逐漸減小的，并且減小的程度只與發(fā)生進一步劃分的等價類有關(guān)，并且對于新的信息系統(tǒng)知識粒度，可以對進一步劃分后的等價類進行相關(guān)計算就可以得到結(jié)果，這種增量計算方法可以避免重新對整個信息系統(tǒng)的論域進行劃分計算，從而提高了計算效率。

在信息系統(tǒng)知識粒度增量式更新的基礎上，將可以進一步推導出屬性與屬性之間知識粒度的增量更新，具體如定理2所示。

定理2：對于決策信息系統(tǒng)DIS=(U,C∪D,V)，對于B?C,B增加屬性集后為B′,D關(guān)于B的知識粒度為GK(D|B),且U/B={X1,X2,…,Xm},同時U/B′=ΦB′∪ΨB′,U/(B′∪D)=ΦB′∪D∪ΨB′∪D。這里的

ΦB′={Xg1,Xg2,…,Xgp}

ΦB′∪D={Xg1,Xg2,…,Xgr}

那么知識粒度GK(D|B′)滿足

GK(D|B′)=GK(D|B)-Γ2

這里的

證明：由定義2有

GK(D|B′)=GK(B′)-GK(B′∪D)

根據(jù)定理1可得到

GK(B′∪D)=GK(B∪D)-

所以

GK(D|B′)=GK(B′)-GK(B′∪D)

由于

GK(D|B)=GK(B)-GK(B∪D)

所以原式=GK(D|B)-Γ2，Γ2如定理2所示。

證畢。

隨著屬性的增加，論域劃分逐漸變細，這里往往只有部分的等價類發(fā)生了變化。通過定理2可以看出，在已知原先知識粒度的情形下，增加屬性集后，只需要對發(fā)生變化的等價類進行相關(guān)運算便可以得到新的知識粒度值，因而這樣可以減少許多重復的計算，降低了時間的開銷。基于這種變化機制，便可以構(gòu)造出基于知識粒度的信息系統(tǒng)增量式屬性約簡算法。

2.2 增量式屬性約簡算法

令更新前的決策信息系統(tǒng)為DIS=(U,C∪D,V)，約簡集為redC，知識粒度為GK(D|redC)。更新后的信息系統(tǒng)為DIS=(U,C′∪D,V)，新的約簡集為redC′。那么信息系統(tǒng)屬性增加后的知識粒度增量式屬性約簡如算法2所示。

算法2 增量式屬性約簡算法

整個算法2的運行過程可以通過圖2所示的流程圖來表示。當信息系統(tǒng)的屬性發(fā)生增加后，算法2在原來屬性約簡結(jié)果的基礎上，按照定理1和定理2所示的計算方法增量式計算知識粒度，然后觀察新知識粒度與舊知識粒度之間值的關(guān)系，如果值不發(fā)生變化，說明原來的屬性約簡結(jié)果仍然可以作為新信息系統(tǒng)的屬性約簡，此時直接輸出屬性約簡結(jié)果，若發(fā)生了變化，那么需要繼續(xù)搜索屬性，直到滿足知識粒度相等時輸出屬性約簡結(jié)果。正是由于增量式算法是在原來屬性約簡約簡結(jié)果上進行的進一步計算，因此這樣可以減少很多不必要的計算，提高了動態(tài)數(shù)據(jù)的處理效率。

對于算法2，設|C|=c，|C′|=c′，|U|=n，發(fā)生改變的等價類個數(shù)為l，那么算法1的時間復雜度為

O(c′2·n+(c′-c)·l)

3 仿真實驗

在本節(jié)，將進行一系列實驗來驗證本文所提出算法的高效性和優(yōu)越性。首先將本文所提出的知識粒度增量式屬性約簡算法與傳統(tǒng)的知識粒度非增量式屬性約簡算法對同一組數(shù)據(jù)集進行處理，比較兩類算法的屬性約簡效率，從而驗證本文算法的高效性。然后將本文的增量式算法與其他相關(guān)的增量式算法進行對比，從而驗證本文算法的優(yōu)越性。

實驗中所使用的公用數(shù)據(jù)集均從UCI中獲取，詳細信息如表1所示，其中Gas和Musk數(shù)據(jù)集為數(shù)值型的數(shù)據(jù)，因此在進行實驗時需要進行離散化處理。由于本文所提出的是增量式屬性約簡算法，為了對表1中的數(shù)據(jù)集構(gòu)造出動態(tài)變化的形式，本實驗采用目前常用的構(gòu)造方法[16-18]，將表1中每個數(shù)據(jù)集的屬性全集大致分割成6個等份，選擇第一份作為初始時的數(shù)據(jù)集，然后依次將剩余的屬性子集加入數(shù)據(jù)集中，從而模擬出了屬性集的5次動態(tài)增加。本文實驗平臺的硬件環(huán)境為CPU Intel core i3 6100 3.7 GHz和4 GB內(nèi)存，操作系統(tǒng)為Windows 7旗艦版，實驗所運用的編程工具為VC++6.0。

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

3.1 知識粒度的增量式與非增量式屬性約簡效率比較

圖3所示的是每個數(shù)據(jù)集在知識粒度增量式和知識粒度非增量式兩種算法中的屬性約簡時間效率對比圖，其中橫坐標表示屬性的增量次數(shù)，縱坐標表示每次更新信息系統(tǒng)后屬性約簡所需要的時間。觀察圖3每個數(shù)據(jù)集的實驗結(jié)果可以發(fā)現(xiàn)，在初始信息系統(tǒng)的屬性約簡時，兩種算法的約簡用時是一樣的，這是由于增量式的屬性約簡算法剛開始時沒有已知的結(jié)果信息，因此約簡時采用的仍然是非增量式的屬性約簡算法。當信息系統(tǒng)更新后，兩類算法的約簡用時便出現(xiàn)了較大的差距，這主要是由于增量式屬性約簡算法的高效性，當信息系統(tǒng)屬性增加時，信息系統(tǒng)中并不是所有的等價類都發(fā)生變化，新的知識粒度計算只對變化后的等價類進行計算，避免對未變化的等價類進行重復計算，而非增量式屬性約簡算法對未發(fā)生變化的等價類重復的計算了一遍，因而實驗結(jié)果圖中非增量式算法的所需時間要高于增量式算法的時間結(jié)果，部分數(shù)據(jù)集遠高于增量式算法，例如Mushroom、Gas和Musk數(shù)據(jù)集。因此該部分實驗結(jié)果表明本文所提出的增量式屬性約簡算法對屬性動態(tài)增加的信息系統(tǒng)具有較高的屬性約簡性能。

圖3 知識粒度的增量式和非增量式屬性約簡效率比較

3.2 其他增量式屬性約簡的比較

第一部分的實驗結(jié)果表明了本文所提出的知識粒度增量式屬性約簡算法具有一定的高效性，接下來將進行優(yōu)越性的驗證實驗，具體將通過對比目前已提出的增量式屬性約簡算法來比較。這些所對比的算法分別為：

① 基于區(qū)分矩陣的增量式屬性約簡，本實驗記為算法A[9]；

② 基于屬性概化的知識粒度增量式屬性約簡，本實驗記為算法B[15]；

③ 基于屬性增量的條件熵增量式屬性約簡，本實驗記為算法C[5]；

④ 基于屬性增量的聯(lián)合熵增量式屬性約簡，本實驗記為算法D[5]。

⑤ 記本文所提出的增量式屬性約簡為算法E。比較這些算法的增量式屬性約簡性能將通過約簡集大小、約簡集的分類精度以及增量式約簡效率來體現(xiàn)。

3.2.1 各增量式屬性約簡算法的約簡結(jié)果比較

表2所示的是5種增量式屬性約簡算法最終屬性約簡的結(jié)果比較。觀察表2可以發(fā)現(xiàn)，本文所提出的增量式屬性約簡算法在大部分數(shù)據(jù)集中能夠約簡出更少的約簡集，并且對于屬性約簡的平均結(jié)果，可以看出本文所提出的算法是最小的。

表2 增量式屬性約簡結(jié)果比較

表3和表4分別所示的是表2中屬性約簡結(jié)果在支持向量機(SVM)和改進決策樹(C4.5)兩種分類器下的分類精度結(jié)果。觀察兩個表可以發(fā)現(xiàn)，雖然本文所提出的算法不是在所有的數(shù)據(jù)集上都擁有最優(yōu)的結(jié)果，但是本文算法所得到分類精度的平均值是最高的，例如表3所示的SVM分類精度中，本文算法在各個數(shù)據(jù)集上分類精度的平均值為0.8356，表4所示的C4.5分類精度中，本文算法在各個數(shù)據(jù)集上分類精度的平均值為0.8428，這兩個結(jié)果均最高，因此可以看出本文所提出的算法在整體上具有更高的屬性約簡性能。

表3 SVM分類精度比較

表4 C4.5分類精度比較

3.2.2 各增量式屬性約簡算法的約簡效率比較

圖4所示的是這5種增量式屬性約簡算法在各個數(shù)據(jù)集下增量式屬性約簡的用時比較。觀察圖4的每個子圖可以發(fā)現(xiàn)，隨著屬性更新的次數(shù)不斷增加，這5種算法有著不同大小的屬性約簡時間消耗和不同的時間增長速率，算法A的時間消耗最多，這主要是由于算法是基于矩陣方法的增量式屬性約簡，運用矩陣在進行增量式計算時會產(chǎn)生更多的時間開銷。其次時間開銷較多的是算法C和算法D，這主要是由于這兩種算法是基于熵模型構(gòu)造出的增量計算，熵模型的計算具有較高的時間復雜度。最低的時間開銷是算法B和本文所提出的算法E，他們都是基于知識粒度構(gòu)造出的屬性約簡，知識粒度的計算方式比較簡單，時間復雜度低，并且本文所提出的算法E是基于等價類變化的視角來進行增量計算，這種計算方法避免了等價類中不必要的重復計算，最大限度的減小了知識粒度的計算復雜程度，因而算法E具有更低的增量式約簡時耗。

綜合兩部分的實驗結(jié)果分析可以看出，本文所提出的增量式屬性約簡算法具有較高的屬性約簡效率，并且相比較其它算法更具優(yōu)越，應用于屬性增加的信息系統(tǒng)的增量式屬性約簡是適用的。

4 結(jié)束語

現(xiàn)實中很多數(shù)據(jù)的屬性是不斷動態(tài)增加的，如何對其進行增量式屬性約簡是目前知識發(fā)現(xiàn)領(lǐng)域研究的重點。本文在等價關(guān)系誘導劃分的基礎上，研究了當屬性增加時知識粒度的變化機制，并基于此提出了一種高效的增量式屬性約簡算法，仿真實驗結(jié)果表明，該算法相比較于目前同類型的算法具有更好的優(yōu)越性。由于本文所提出的算法基于等價關(guān)系構(gòu)建，因此接下來將探索數(shù)值型以及混合型數(shù)據(jù)的增量式屬性約簡方法。

圖4 5種增量式屬性約簡算法的時間比較