基于矩陣方法的區(qū)分度增量式屬性約簡算法

沈 玉 峰

(安徽三聯(lián)學(xué)院計算機(jī)工程學(xué)院 安徽 合肥 230601)

0 引 言

粗糙集[1]是人工智能領(lǐng)域的重要分支，屬性約簡[2]是粗糙集理論的重點研究內(nèi)容。屬性約簡的目的是為了將原始信息系統(tǒng)的冗余屬性進(jìn)行甄別和刪除，從而提高數(shù)據(jù)集的知識發(fā)現(xiàn)性能。然而隨著信息技術(shù)的發(fā)展以及數(shù)據(jù)采集技術(shù)的提高，實際應(yīng)用環(huán)境下的數(shù)據(jù)總是時刻處于動態(tài)更新之中，傳統(tǒng)的各種屬性約簡算法是針對靜態(tài)的數(shù)據(jù)設(shè)計的，而對于動態(tài)的數(shù)據(jù)集，這些算法的處理效率較為低下，不能很好地適應(yīng)實際的工程需求[3-4]。

為了改善動態(tài)數(shù)據(jù)下的屬性約簡性能，學(xué)者們提出了一種改進(jìn)的屬性約簡方法——增量式屬性約簡[5]，增量式屬性約簡的核心思想是增量式學(xué)習(xí)，即在原始屬性約簡的基礎(chǔ)上融入增量式學(xué)習(xí)，當(dāng)信息系統(tǒng)發(fā)生更新時，增量式屬性約簡算法能夠?qū)⒃瓉淼膶傩约s簡結(jié)果加以利用，在其基礎(chǔ)上進(jìn)一步計算出新的屬性約簡結(jié)果。由于增量式屬性約簡的高效性，目前已成為屬性約簡領(lǐng)域的研究熱點[6-7]。

對象的動態(tài)增加和減少是信息系統(tǒng)最為常見的一種動態(tài)更新形式，為此學(xué)者對這類屬性約簡問題進(jìn)行了大量的研究。最早的屬性約簡是基于粗糙集的正區(qū)域來構(gòu)造，Chan[5]研究了正區(qū)域隨信息系統(tǒng)變化時的增量式更新，提出了最早的增量式屬性約簡算法。在Chan的研究思路基礎(chǔ)上，Shu等[8]提出了一種改進(jìn)的增量式屬性約簡，進(jìn)一步提高了動態(tài)數(shù)據(jù)的處理效率。同時，Wei等[9]通過辨析矩陣的視角給出了一種新的增量式屬性約簡算法。信息熵作為一種新的屬性集不確定性度量，是構(gòu)造屬性約簡的一種常用方法[10-12]，因此學(xué)者們在信息熵的基礎(chǔ)上進(jìn)一步地提出了多種的增量式屬性約簡算法。Liang等[13]研究了條件信息熵隨信息系統(tǒng)對象變化時的增量式更新，并基于這種更新機(jī)制提出了條件信息熵的增量式屬性約簡算法。類似于這種增量式更新的方法，趙小龍等[14]提出了數(shù)值型數(shù)據(jù)下條件信息熵的增量式更新，并提出了對應(yīng)的增量式屬性約簡，Jing等[15]采用同樣的推導(dǎo)思路，研究了粒計算中知識粒度隨對象變化時的增量式更新，提出了基于知識粒度的增量式屬性約簡算法。同樣在不完備信息系統(tǒng)中，Xie等[16]基于一致性度量的增量式更新方法設(shè)計了一種類似的增量式屬性約簡算法。綜合已有的研究成果可以看出，對屬性集度量函數(shù)進(jìn)行增量式學(xué)習(xí)的構(gòu)造是目前增量式屬性約簡的研究重點。

信息系統(tǒng)屬性集的區(qū)分度度量是Teng等[17]提出的一種新的度量方法，它通過信息系統(tǒng)的等價類直接進(jìn)行計算，能夠更加精準(zhǔn)地評估出屬性集之間的依賴關(guān)系，并且具有時間復(fù)雜度低的優(yōu)越性，Teng等通過實驗證明了基于區(qū)分度屬性約簡的高效性和優(yōu)越性。然而目前還未有利用區(qū)分度度量進(jìn)行增量式屬性約簡的研究，因此這促使我們進(jìn)行相關(guān)的研究和探索。

研究區(qū)分度的增量式學(xué)習(xí)是設(shè)計區(qū)分度增量式屬性約簡的關(guān)鍵。矩陣是一種重要的數(shù)據(jù)處理工具，由于它在計算方面的可擴(kuò)展性，目前已廣泛地運用于粗糙集的各類增量式學(xué)習(xí)之中[9,18-20]。本文將通過矩陣的方法去構(gòu)造區(qū)分度的增量式學(xué)習(xí)，進(jìn)一步提出相應(yīng)的增量式屬性約簡算法。首先運用矩陣的形式去表示信息系統(tǒng)的區(qū)分度度量，然后在矩陣表示的基礎(chǔ)上，分別研究了信息系統(tǒng)對象增加和減少時區(qū)分度的增量式學(xué)習(xí)，理論分析表明了這種增量式學(xué)習(xí)的高效性，它可以快速地更新出區(qū)分度結(jié)果，最后基于區(qū)分度的增量式學(xué)習(xí)提出對應(yīng)的增量式屬性約簡算法。UCI數(shù)據(jù)集的實驗結(jié)果表明，所提出的增量式屬性約簡算法具有更高的動態(tài)數(shù)據(jù)屬性約簡性能，能夠適應(yīng)數(shù)據(jù)動態(tài)變化時的屬性約簡。

1 基于區(qū)分度的屬性約簡

屬性約簡[1-2]是粗糙集理論的重要應(yīng)用。在屬性約簡中，所討論的數(shù)據(jù)集被描述成信息系統(tǒng)的形式。通常一個信息系統(tǒng)表示為S=(U,AT)，其中U為該信息系統(tǒng)的對象集，即數(shù)據(jù)集所有樣本的集合；AT為該信息系統(tǒng)的屬性集，即數(shù)據(jù)集所有特征的集合。若信息系統(tǒng)包含決策屬性D，即每個對象都有一個類別的標(biāo)記，那么該信息系統(tǒng)又稱為決策信息系統(tǒng)[1]。

對于信息系統(tǒng)S=(U,AT)，設(shè)屬性子集A?AT在論域U×U下確定的等價關(guān)系為：

EU×U(A)={(x,y)|a(x)=a(y),?a∈A,x,y∈U}

(1)

等價關(guān)系EU×U(A)滿足自反性、對稱性和傳遞性。若U={x1,x2,…,xn}，EU×U(A)可以將論域U誘導(dǎo)出一組劃分，表示為U/EU×U(A)={[x1]A,[x2]A,…,[xn]A}，其中[xi]A(1≤i≤n)為對象xi在等價關(guān)系EU×U(A)下的等價類，表示為[xi]A={xj∈U|(xi,xj)∈EU×U(A)}。

通過等價關(guān)系將信息系統(tǒng)的論域進(jìn)行信息?；?，其粒化后的粒子即為等價類，最后基于等價類去誘導(dǎo)粗糙集的上下近似，并且選擇出信息系統(tǒng)的屬性約簡[1-2,10]。在文獻(xiàn)[17]中，Teng等提出了一種基于區(qū)分度的屬性約簡算法。

定義1[17]設(shè)信息系統(tǒng)S=(U,AT)，|U|=n，屬性集A?AT在論域U×U下確定的等價關(guān)系為EU×U(A)，且誘導(dǎo)的劃分為U/EU×U(A)。定義信息系統(tǒng)論域U下屬性集A的區(qū)分度為:

(2)

知識是粗糙集和粒計算的研究核心，在粗糙集理論中，同一個等價類中對象之間不具有知識的區(qū)分性，相反，不同等價類之間則表現(xiàn)出了知識的區(qū)分性。因此在信息系統(tǒng)中，給定屬性集下的知識量可以通過不同等價類之間對象的數(shù)量來表示，即定義1中的區(qū)分度度量[17]。在區(qū)分度的基礎(chǔ)上，Teng等進(jìn)一步提出了一個屬性集相對另一個屬性的知識量，稱之為相對區(qū)分度，具體如定義2所示。

定義2[17]設(shè)信息系統(tǒng)S=(U,AT)，屬性集A1,A2?AT在論域U×U下確定的等價關(guān)系分別為EU×U(A1)和EU×U(A2),對論域U構(gòu)造出的劃分分別為U/EU×U(A1)和U/EU×U(A2)。定義論域U下屬性集A2關(guān)于A1的相對區(qū)分度為：

(3)

定義2中的相對區(qū)分度可以看作是一種屬性集之間關(guān)系程度的度量。因此在文獻(xiàn)[17]中，利用相對區(qū)分度作為評估屬性集的啟發(fā)式函數(shù)，Teng等定義了一種新的屬性約簡方法。

定義3[17]設(shè)決策信息系統(tǒng)S=(U,C∪D),其中C為條件屬性集，D為決策屬性集。若屬性集red?C是該信息系統(tǒng)的一個屬性約簡,那么當(dāng)且僅當(dāng)如下同時成立:

DisU(D|C)=DisU(D|red)

(4)

a∈redDisU(D|C)

(5)

算法1所示的是對應(yīng)的屬性約簡算法。

算法1[17]基于區(qū)分度的屬性約簡算法

輸入：決策信息系統(tǒng)S=(U,C∪D)。

輸出：屬性約簡結(jié)果red。

Step1初始化屬性約簡集red=?;

Step2對于?a∈C-red,計算屬性a的屬性重要度:

sigred(a)=DisU(D|red)-DisU(D|red∪{a})

Step3找出C-red中屬性重要度最大的屬性,記為a′;

Step4若sigred(a′)>0,那么red=red∪{a′},并跳轉(zhuǎn)入Step 2,若sigred(a′)=0,則跳轉(zhuǎn)入Step 5;

Step5返回屬性約簡結(jié)果red。

2 基于矩陣方法的區(qū)分度增量式更新

矩陣是一種重要的數(shù)據(jù)表達(dá)形式，在粗糙集理論中，學(xué)者們通過矩陣對粗糙集中各類計算模型進(jìn)行重構(gòu)，提出了多種形式的模型和算法[9,18-20]。在本節(jié)，將在前人研究的基礎(chǔ)上，通過矩陣的方法去表示區(qū)分度，并進(jìn)一步通過矩陣去構(gòu)造區(qū)分度的增量式更新。

2.1 區(qū)分度的矩陣表達(dá)

定義4[18]設(shè)信息系統(tǒng)S=(U,AT)，|U|=n，屬性集A?AT在論域U×U下確定的等價關(guān)系為EU×U(A)，定義等價關(guān)系EU×U(A)的關(guān)系矩陣為:

(6)

定義4是通過矩陣的形式對等價關(guān)系進(jìn)行表達(dá)，若信息系統(tǒng)論域中對象xi和xj滿足等價關(guān)系，那么區(qū)分度關(guān)系矩陣中第i行第j列元素為1，否則為0。

(7)

(8)

證畢。

(9)

證畢。

定理1展示了區(qū)分度的另一種表示方式，即通過區(qū)分度關(guān)系矩陣的方法來表示，而不必對信息系統(tǒng)中每個對象的等價類進(jìn)行計算。

例1表1所示的是一個信息系統(tǒng)，其中{a,b,c}為該信息系統(tǒng)的屬性集，x1,x2,…,x6為該信息系統(tǒng)的6個對象。

表1 信息系統(tǒng)

令屬性集A={a,b}，對A構(gòu)建等價關(guān)系EU×U(A)，那么可以得到每個對象的等價類為:

[x1]A=[x5]A=[x6]A={x1,x5,x6}

[x2]A=[x4]A={x2,x4} [x3]A={x3}

那么根據(jù)定義1關(guān)于區(qū)分度的定義，可以得到：

36-3×3-2×2-1=22

基于定理1的方法進(jìn)行計算：

對比可以看出兩種計算結(jié)果是一致的。

在定理1的基礎(chǔ)上，接下來將通過矩陣進(jìn)一步表示相對區(qū)分度。

DisU(A2|A1)=DisU(A1)-DisU(A1∪A2)=

(10)

式中：

證明根據(jù)定理1可以直接得到。

類似于定理1，定理2利用矩陣的方法表示相對區(qū)分度。

證畢。

例2設(shè)信息系統(tǒng)如表1所示，令屬性集A1={a,b}，A2={c}，那么：

[x1]A2=[x2]A2=[x3]A2=[x6]A2={x1,x2,x3,x6}

[x4]A2=[x5]A2={x4,x5}

根據(jù)定義2有：

DisU(A2|A1)=14-2-1-1-1-1-2=6

兩種計算結(jié)果是一致的。

2.2 信息系統(tǒng)對象變化時區(qū)分度的增量式更新

由于現(xiàn)實應(yīng)用環(huán)境下，信息系統(tǒng)往往都是不斷動態(tài)變化的。本節(jié)將通過矩陣方法去研究信息系統(tǒng)對象發(fā)生變化時，區(qū)分度的增量式更新，其中包含對象增加時區(qū)分度的增量式更新和對象減少時區(qū)分度的增量式更新。

2.2.1信息系統(tǒng)對象增加時區(qū)分度的增量式更新

設(shè)信息系統(tǒng)S=(U,AT)，其中論域U={x1,x2,…,xn}，屬性集A?AT在論域U下確定的等價關(guān)系記為EU×U(A)，當(dāng)信息系統(tǒng)增加對象集U+={xn+1,xn+2,…,xn+k}后，新的信息系統(tǒng)記為S=(U′=U∪U+,AT)，屬性集A?AT在論域U′下確定的等價關(guān)系記為EU′×U′(A)。

定義5信息系統(tǒng)S=(U,AT)增加對象集U+后更新為S=(U′=U∪U+,AT)。設(shè)對象集U+與論域U在屬性集A?AT下確定的等價關(guān)系記為EU+×U(A)，那么對應(yīng)的關(guān)系矩陣定義為:

1≤i≤k,1≤j≤n

(11)

定義6信息系統(tǒng)S=(U,AT)增加對象集U+后更新為S=(U′=U∪U+,AT) 。設(shè)U+與U+在屬性集A?AT下確定的等價關(guān)系記為EU+×U+(A)，那么對應(yīng)的關(guān)系矩陣定義為：

1≤i,j≤k

(12)

根據(jù)定義5和定義6，接下來可以增量式地得到信息系統(tǒng)S=(U′=U∪U+,AT)下等價關(guān)系EU′×U′(A)所對應(yīng)的關(guān)系矩陣。具體如定理3所示。

(13)

證畢。

在定理3的基礎(chǔ)上，可以得到論域增加對象集后區(qū)分度的增量式更新。

(14)

證畢。

在定理4的基礎(chǔ)上，可以進(jìn)一步得到相對區(qū)分度的增量式更新，具體見定理5。

(15)

證明根據(jù)定理2可以得到：

在定理3中，四個子矩陣是相互獨立的，因此：

證畢。

類似于定理4，對于計算對象增加后的相對區(qū)分度，定理5同樣具有很高的計算效率。

例3設(shè)表1所示的信息系統(tǒng)增加對象集U+={x7,x8,x9}，新信息系統(tǒng)如表2所示。

表2 新的信息系統(tǒng)

設(shè)屬性集A1={a,b},A2={c}。那么：

[x1]A1=[x5]A1=[x6]A1={x1,x5,x6}

[x2]A1=[x4]A1=[x7]A1={x2,x4,x7}

[x3]A1=[x9]A1={x3,x9};[x8]A1={x8}

[x1]A2=[x2]A2=[x3]A2=[x6]A2=

[x7]A2=[x9]A2={x1,x2,x3,x6,x7,x9}

[x4]A2=[x5]A2=[x8]A2={x4,x5,x8}

則：

23-15=8

采用矩陣的方法進(jìn)行增量式計算：

由于DisU(A2|A1)在例2中已經(jīng)計算得出，因此根據(jù)定理5可以得到：

6+6+3-4-3=8

兩種計算結(jié)果是一致的，但是基于矩陣方法進(jìn)行增量式計算，可以在原來計算結(jié)果上進(jìn)行進(jìn)一步計算，大幅度地減少了重復(fù)計算量，具有更高的計算效率。

2.2.2信息系統(tǒng)對象減少時區(qū)分度的增量式更新

在上小節(jié)中，給出了當(dāng)信息系統(tǒng)對象增加時區(qū)分度的增量式更新方法，本節(jié)仿照上節(jié)的研究思路，提出信息系統(tǒng)對象減少時區(qū)分度的增量式更新。

設(shè)信息系統(tǒng)S=(U,AT)，其中論域U={x1,x2,…,xn}，屬性集A?AT在論域U下確定的等價關(guān)系記為EU×U(A)，當(dāng)信息系統(tǒng)減少對象集U-={xt1,xt2,…,xtk}，其中U-?U，新的信息系統(tǒng)記為S=(U′=U-U-,AT)，屬性集A?AT在論域U′下確定的等價關(guān)系記為EU′×U′(A)。

定義7信息系統(tǒng)S=(U,AT)減少對象集U-后更新為S=(U′=U-U-,AT)。對象集U-與論域U在屬性集A?AT下確定的等價關(guān)系記為EU-×U(A)，那么定義關(guān)系矩陣：

1≤i≤k,1≤j≤n

(16)

(17)

證明當(dāng)信息系統(tǒng)減少對象集U-后，那么滿足：

EU-×U(A)?EU×U(A),EU×U-(A)?EU×U(A)

證畢。

(18)

證明根據(jù)定理1，

證畢。

DisU′(A2|A1)=DisU(A2|A1)-

(19)

證明根據(jù)定理2有：

所以DisU′(A2|A1)=DisU(A2|A1)-

證畢。

例4設(shè)表2所示的信息系統(tǒng)減少對象集U-={x7,x8,x9}，那么新信息系統(tǒng)即為表1。

令屬性集A1={a,b}，A2={c}。那么：

根據(jù)例3和定理8可以得到：

DisU′(A2|A1)=8-2·(3-2)=6

與例2的計算結(jié)果是一致的。

3 增量式屬性約簡算法

根據(jù)第2節(jié)提出的區(qū)分度增量式更新方法，在算法1的基礎(chǔ)上，本節(jié)將進(jìn)一步地提出對應(yīng)的區(qū)分度增量式屬性約簡算法，具體如算法2和算法3所示。

算法2信息系統(tǒng)對象增加時基于區(qū)分度的增量式屬性約簡算法

輸入：更新后的信息系統(tǒng)S=(U′=U∪U+,C∪D)，更新前信息系統(tǒng)的約簡集red，相對區(qū)分度DisU(D|red)和DisU(D|C)。

輸出：新的屬性約簡結(jié)果red′。

Step1根據(jù)DisU(D|red)和DisU(D|C)增量式計算DisU′(D|red)和DisU′(D|C)。

Step2

若DisU′(D|red)=DisU′(D|C),則跳轉(zhuǎn)入Step 7；

若DisU′(D|red)>DisU′(D|C),則跳轉(zhuǎn)入Step 5；

若DisU′(D|red)

Step3對于?a∈red，計算a的屬性重要度：

sigred(a)=DisU′(D|red-{a})-DisU′(D|red)

Step4找出red中屬性重要度最大的屬性a′，若sigred(a′)>0，則red=red-{a′}，并跳轉(zhuǎn)入Step 3，若sigred(a′)=0，則跳轉(zhuǎn)入Step 7。

Step5對于?a∈C-red，計算a的屬性重要度：

sigred(a)=DisU′(D|red)-DisU′(D|red∪{a})

Step6找出C-red中屬性重要度最大的屬性a′，若sigred(a′)>0，則red=red∪{a′}，并跳轉(zhuǎn)入Step 5，若sigred(a′)=0，則跳轉(zhuǎn)入Step 7。

Step7red′←red。

Step8返回新的屬性約簡結(jié)果red′。

算法3信息系統(tǒng)對象減少時基于區(qū)分度的增量式屬性約簡算法

輸入：更新后的信息系統(tǒng)S=(U′=U-U-,C∪D)，更新前信息系統(tǒng)的約簡集red，相對區(qū)分度DisU(D|red)和DisU(D|C)。

輸出：新的屬性約簡結(jié)果red′。

Step1根據(jù)DisU(D|red)和DisU(D|C)增量式計算DisU′(D|red)和DisU′(D|C)

Step2

若DisU′(D|red)=DisU′(D|C),則跳轉(zhuǎn)入Step 7；

若DisU′(D|red)>DisU′(D|C),則跳轉(zhuǎn)入Step 5；

若DisU′(D|red)

Step3對于?a∈red，計算a的屬性重要度：

sigred(a)=DisU′(D|red-{a})-DisU′(D|red)

Step4找出red中屬性重要度最大的屬性a′，若sigred(a′)>0，則red=red-{a′}，并跳轉(zhuǎn)入Step 3，若sigred(a′)=0，則跳轉(zhuǎn)入Step 7。

Step5對于?a∈C-red，計算a的屬性重要度：

sigred(a)=DisU′(D|red)-DisU′(D|red∪{a})

Step6找出C-red中屬性重要度最大的屬性a′，若sigred(a′)>0，則red=red∪{a′}，并跳轉(zhuǎn)入Step 5，若sigred(a′)=0，則跳轉(zhuǎn)入Step 7。

Step7red′←red。

Step8返回新的屬性約簡結(jié)果red′。

本文稱算法2和算法3為基于區(qū)分度的增量式屬性約簡算法，那么Teng等[17]提出的算法(算法1)即為基于區(qū)分度的非增量式屬性約簡算法。

觀察算法2和算法3可以看出，它們均在原來信息系統(tǒng)屬性約簡的結(jié)果上進(jìn)行增量式計算，這種增量式的計算可以大幅度減少對原先信息系統(tǒng)中數(shù)據(jù)的重復(fù)計算，從而提高了動態(tài)數(shù)據(jù)的約簡效率。

在算法2和算法3中，設(shè)|U|=n、|U+|=|U-|=k和|C|=c,從red至red′的屬性集大小變化量為r，那么算法2和算法3的時間復(fù)雜度為O(c·r·n·k)。

4 實驗分析

4.1 實驗數(shù)據(jù)與實驗設(shè)計

本實驗采用MATLAB 2014作為實驗平臺進(jìn)行算法的實現(xiàn)和運行，實驗所運行的硬件環(huán)境為Intel i7 4790 3.5 kGHz CPU和16 GB DDR3內(nèi)存。實驗所使用的數(shù)據(jù)集如表3所示，這6個數(shù)據(jù)集均來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集庫，部分?jǐn)?shù)據(jù)集中包含連續(xù)型的屬性值，實驗前需要進(jìn)行離散化處理。

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

表3列舉的數(shù)據(jù)集均為靜態(tài)完整的數(shù)據(jù)集，為了運用文中提出的增量式屬性約簡算法，本實驗采用其他學(xué)者常用的實現(xiàn)方法[13-16]，將數(shù)據(jù)集的論域隨機(jī)分割成多個子數(shù)據(jù)集，本實驗選擇分割的數(shù)量為8個。對于數(shù)據(jù)集對象逐漸增加的情形，實驗中隨機(jī)選擇其中一個子數(shù)據(jù)集作為初始的數(shù)據(jù)集，然后從剩余的子數(shù)據(jù)集中選擇出一個與初始數(shù)據(jù)集進(jìn)行合并，這樣便模擬出了數(shù)據(jù)集對象的一次動態(tài)增加，重復(fù)上述步驟，最后直至完成數(shù)據(jù)集的7次更新。類似地，對于數(shù)據(jù)集對象逐漸減少的情形，實驗中隨機(jī)選擇其中一個子數(shù)據(jù)集，然后從完整數(shù)據(jù)集中刪除該子數(shù)據(jù)集，這樣便模擬出了數(shù)據(jù)集對象的一次動態(tài)減少，重復(fù)進(jìn)行此步驟，便構(gòu)造出了數(shù)據(jù)集對象的7次動態(tài)減少。

將傳統(tǒng)的區(qū)分度屬性約簡算法和本文提出的區(qū)分度增量式屬性約簡算法，分別對數(shù)據(jù)集對象動態(tài)增加的情形和對象動態(tài)減少的情形進(jìn)行屬性約簡。然后通過屬性約簡的效率、屬性約簡集的大小以及屬性約簡結(jié)果的分類性能來比較兩種算法的屬性約簡性能，從而驗證出本文所提出算法的有效性。

4.2 屬性約簡效率比較

圖1為基于區(qū)分度的增量式屬性約簡算法(算法2)與區(qū)分度的非增量式屬性約簡算法(算法1)在各個數(shù)據(jù)集下對象7次增加時的屬性約簡效率比較。其中每個子圖的橫坐標(biāo)表示的是數(shù)據(jù)集的更新次數(shù)，縱坐標(biāo)表示的是算法進(jìn)行屬性約簡時所需的用時。

(a) iono

(b) gcd

(c) tic

(d) td

(e) mgt

(f) ci圖1 各數(shù)據(jù)集對象增加時屬性約簡用時比較

觀察圖1每個數(shù)據(jù)集的實驗結(jié)果可以發(fā)現(xiàn)，隨著數(shù)據(jù)集更新次數(shù)的增加，兩種算法在屬性約簡的用時方面表現(xiàn)出了明顯的差距，其中本文所提出的增量式屬性約簡用時大幅度低于非增量式算法。這主要是由于本文所提出的增量式算法是在原來屬性約簡的結(jié)果上進(jìn)行計算，減少了對原來數(shù)據(jù)的重復(fù)計算，大幅度提高了計算效率。

圖2為基于區(qū)分度的增量式屬性約簡算法(算法3)與區(qū)分度的非增量式屬性約簡算法(算法1)在各個數(shù)據(jù)集下對象7次減少時的屬性約簡效率比較。其中每個子圖的橫坐標(biāo)表示的是數(shù)據(jù)集的更新次數(shù)，縱坐標(biāo)表示的是算法進(jìn)行屬性約簡的用時。

(a) iono

(b) gcd

(c) tic

(d) td

(e) mgt

(f) ci圖2 各數(shù)據(jù)集對象減少時屬性約簡用時比較

觀察圖2同樣可以發(fā)現(xiàn)，隨著數(shù)據(jù)集更新次數(shù)的增加，兩種算法在屬性約簡的用時方面也表現(xiàn)出了明顯的差距，同樣本文所提出的增量式屬性約簡用時大幅度低于已提出的非增量式屬性約簡算法。其原因同樣是由于本文所提出的算法通過增量式計算提高了約簡效率，每次屬性約簡時避免了對舊數(shù)據(jù)的重復(fù)計算。

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

對于實驗中動態(tài)更新的信息系統(tǒng)，屬性約簡算法在信息系統(tǒng)每次更新時都能得到個當(dāng)時對應(yīng)的屬性約簡結(jié)果。將7次屬性約簡結(jié)果的約簡集大小取平均值，這樣就得到了對應(yīng)算法的平均約簡結(jié)果。表4為非增量式屬性約簡算法(算法1)與文中提出的增量式屬性約簡算法(算法2)在各個數(shù)據(jù)集下論域7次動態(tài)增加時的平均約簡結(jié)果。表5為非增量式屬性約簡算法(算法1)與文中提出的增量式屬性約簡算法(算法3)在各個數(shù)據(jù)集下論域7次動態(tài)減少時的平均約簡結(jié)果。

表4 數(shù)據(jù)集對象動態(tài)增加時平均約簡結(jié)果比較

表5 數(shù)據(jù)集對象動態(tài)增加時平均約簡結(jié)果比較

續(xù)表5

觀察表4可以發(fā)現(xiàn)，對于論域逐漸增加的信息系統(tǒng)，本文提出的增量式屬性約簡算法(算法2)在大部分?jǐn)?shù)據(jù)集中具有較小的平均屬性約簡結(jié)果，例如數(shù)據(jù)集iono、gcd、tic、mgt和ci。而對于非增量式屬性約簡算法(算法1)，只在小部分的數(shù)據(jù)集擁有較小的平均屬性約簡結(jié)果，例如數(shù)據(jù)集td。產(chǎn)生這種差異主要是由于增量式屬性約簡算法的約簡機(jī)制導(dǎo)致的，增量式屬性約簡在進(jìn)行約簡時，是根據(jù)原先信息系統(tǒng)的約簡結(jié)果進(jìn)行進(jìn)一步計算，這樣避免了對整個屬性集進(jìn)行重新搜索，從而增量式算法約簡出的屬性更少。觀察表5結(jié)果同樣可以發(fā)現(xiàn)，對于論域逐漸減少的信息系統(tǒng)，文中提出的增量式屬性約簡算法(算法3)具有更小的平均屬性約簡結(jié)果，例如數(shù)據(jù)集iono、gcd、tic和td。

4.4 屬性約簡結(jié)果的分類性能比較

為了測試兩類屬性約簡算法約簡結(jié)果的分類性能，本實驗通過支持向量機(jī)分類器(SVM)與改進(jìn)的決策樹分類器(C4.5)分別對每次更新時的屬性約簡結(jié)果進(jìn)行分類訓(xùn)練，并得到約簡集對應(yīng)的分類精度，最后將所有分類精度取均值，得到對應(yīng)屬性約簡算法的平均分類精度。表6為各個數(shù)據(jù)集論域動態(tài)增加時兩類算法的平均分類精度比較結(jié)果，表7為各個數(shù)據(jù)集論域動態(tài)減少時兩類算法的平均分類精度比較結(jié)果。

表6 數(shù)據(jù)集對象增加時約簡結(jié)果分類精度比較 %

表7 數(shù)據(jù)集對象減少時約簡結(jié)果分類精度比較 %

觀察表6可以發(fā)現(xiàn)，本文所提出的區(qū)分度增量式屬性約簡算法(算法2)在數(shù)據(jù)集tic和mgt下?lián)碛休^高的SVM分類精度，在數(shù)據(jù)集iono、tic、mgt和ci下?lián)碛休^高的C4.5分類精度，基于區(qū)分度的非增量式屬性約簡算法在其他數(shù)據(jù)集擁有較高的分類精度，可以發(fā)現(xiàn)兩類算法的平均分類精度在大部分?jǐn)?shù)據(jù)集上相差不大。觀察表7可以發(fā)現(xiàn)，所提出的區(qū)分度增量式屬性約簡算法(算法3)在數(shù)據(jù)集td、mgt和ci下?lián)碛休^高的SVM分類精度，在數(shù)據(jù)集iono、tic和mgt下?lián)碛休^高的C4.5分類精度，同樣在大部分?jǐn)?shù)據(jù)集下，兩類算法具有相近的平均分類精度。因此表6和表7說明了所提出的區(qū)分度增量式屬性約簡算法同樣能夠得到較優(yōu)的屬性約簡結(jié)果。

4.5 實驗總結(jié)

綜合4.2節(jié)、4.3節(jié)和4.4節(jié)三個部分的實驗比較結(jié)果，說明對于樣本動態(tài)增加或減少的數(shù)據(jù)集，本文提出的區(qū)分度增量式屬性約簡算法具有較高的屬性約簡性能，能夠滿足數(shù)據(jù)變化時屬性約簡的實時需求。同時所提出的增量式屬性約簡算法能夠比非增量式算法選擇出更小的約簡集，并且也能夠保持同樣的分類性能。所以本文提出的區(qū)分度增量式屬性約簡是一種較優(yōu)的動態(tài)數(shù)據(jù)屬性約簡算法。

5 結(jié) 語

屬性約簡是粗糙集理論在機(jī)器學(xué)習(xí)和知識發(fā)現(xiàn)領(lǐng)域中的一項重要應(yīng)用。然而現(xiàn)實環(huán)境下的數(shù)據(jù)總是實時更新的，針對這一數(shù)據(jù)環(huán)境，學(xué)者們在傳統(tǒng)屬性約簡算法的基礎(chǔ)上，將增量式學(xué)習(xí)融入其中，提出了多種增量式屬性約簡算法。區(qū)分度作為一種重要的屬性集評估方法，目前已成為屬性約簡的一種重要的方法，本文針對樣本不斷動態(tài)變化的數(shù)據(jù)集環(huán)境，提出一種基于區(qū)分度的增量式屬性約簡算法。首先通過矩陣方法去表示區(qū)分度，并通過矩陣研究了區(qū)分度的增量式學(xué)習(xí)，然后基于區(qū)分度的增量式更新提出一種增量式屬性約簡算法，最后通過實驗驗證了所提出增量式屬性約簡算法的有效性。由于文中僅針對數(shù)據(jù)集樣本的變化進(jìn)行了研究，因此接下來將進(jìn)一步探索數(shù)據(jù)集屬性變化時屬性約簡的增量式更新。