鄰域系統(tǒng)中對(duì)象變化的動(dòng)態(tài)屬性約簡(jiǎn)算法

向 偉

(四川文理學(xué)院智能制造學(xué)院 四川 達(dá)州 635006)

0 引 言

屬性約簡(jiǎn)是數(shù)據(jù)挖掘領(lǐng)域中研究的熱點(diǎn)之一，它能夠在保持信息系統(tǒng)分類能力不變的情況下，剔除冗余的屬性。粗糙集[1]作為一種智能信息處理技術(shù)，自1982年提出以來，已經(jīng)在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識(shí)別等[2-5]領(lǐng)域得到了廣泛應(yīng)用，以粗糙集為工具可以對(duì)信息系統(tǒng)進(jìn)行有效屬性約簡(jiǎn)。

目前，從實(shí)際生產(chǎn)、生活中獲取的數(shù)據(jù)呈現(xiàn)多樣化，使得信息系統(tǒng)中的數(shù)據(jù)不僅僅是離散型的，同時(shí)擁有離散型和數(shù)值型數(shù)據(jù)的混合信息系統(tǒng)也很常見，此類系統(tǒng)稱為鄰域信息系統(tǒng)。為了對(duì)鄰域系統(tǒng)進(jìn)行屬性約簡(jiǎn)，李少年等[6]提出了基于鄰域信息熵度量數(shù)值屬性快速約簡(jiǎn)算法;何松華等[7]提出了基于鄰域組合測(cè)度的屬性約簡(jiǎn)方法；吳克壽等[8]提出了基于鄰域關(guān)系的決策表約簡(jiǎn)算法。但是這些算法沒有考慮到當(dāng)信息系統(tǒng)中對(duì)象增加或者減少時(shí)，如何高效地對(duì)信息進(jìn)行屬性約簡(jiǎn)。文獻(xiàn)[9]提出了不完備決策信息系統(tǒng)中的動(dòng)態(tài)屬性約簡(jiǎn)算法；文獻(xiàn)[10]提出了集值信息系統(tǒng)中的動(dòng)態(tài)屬性約簡(jiǎn)算法。但是這些算法不能有效處理鄰域信息系統(tǒng)，只適合處理靜態(tài)的數(shù)據(jù)。然而，實(shí)際應(yīng)用中，數(shù)據(jù)的動(dòng)態(tài)變化是時(shí)有發(fā)生的，比如對(duì)于一個(gè)公司的員工考察信息表，隨著新員工的加入，信息表中的對(duì)象就會(huì)增加，隨著一些員工的辭職，信息表中的對(duì)象就會(huì)減少。

為了對(duì)對(duì)象變化的鄰域系統(tǒng)進(jìn)行動(dòng)態(tài)屬性約簡(jiǎn)，本文介紹了鄰域系統(tǒng)中的差異度概念。當(dāng)系統(tǒng)中的對(duì)象增加或減少時(shí)，分析了差異度的變化機(jī)制。在此基礎(chǔ)上，提出了鄰域系統(tǒng)中對(duì)象變化的動(dòng)態(tài)屬性約簡(jiǎn)算法，實(shí)驗(yàn)驗(yàn)證了所提算法的可行性與高效性。

1 相關(guān)概念

定義2設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，屬性子集B?C，定義B上的δ鄰域關(guān)系為：

NRδ(B)={(x,y)∈U×U|DB(x,y)≤δ}

(1)

式中：DB(x,y)表示在屬性子集B上對(duì)象x和y之間的距離。

為了可以處理同時(shí)有離散型和數(shù)值型的不完備鄰域信息系統(tǒng)，本文中的距離采用文獻(xiàn)[7]中的距離函數(shù)。設(shè)B={a1,a2,…,an}，距離度量為：

(2)

式中：1≤l≤n。

(3)

定義3設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，?x∈U，B上x的鄰域?yàn)椋?/p>

(4)

定義4設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，對(duì)象集X?U關(guān)于屬性子集B?C的上、下近似和邊界域分別定義如下：

(1)X的上近似：

(2)X的下近似：

(3)X的邊界域：

定義5設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，對(duì)于B?C，D關(guān)于B的正域定義為：

(5)

定義6設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，對(duì)于?B?C，若滿足下列條件，則稱B為C的一個(gè)正域?qū)傩约s簡(jiǎn)。基于正域不變來定義屬性約簡(jiǎn)是一個(gè)較為常見的方法[7,11-13]。

1)POSB(D)=POSC(D)；

2) ?a∈B，滿足POSB-{a}(D)≠POSC(D)。

2 鄰域系統(tǒng)中基于差異度的屬性約簡(jiǎn)

本節(jié)給出了鄰域系統(tǒng)中差異度的概念，基于差異度提出了啟發(fā)式屬性約簡(jiǎn)算法。

定理1給定鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，對(duì)于屬性子集B?C,有：

(6)

由定義7易計(jì)算出B上的差異對(duì)象集合，又由于屬性集合B上的差異度等于B上的差異對(duì)象集合的大小，所以B上的差異度也較容易得到。

定義9給定鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，對(duì)于?B?C,若滿足下列條件，則稱B為C的一個(gè)差異度屬性約簡(jiǎn)。

1) ?δ(B)=?δ(C)；

2) ?a∈B滿足?δ(B-{a})≠?δ(C)。

定理2給定鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，對(duì)于?B?C,B為C的一個(gè)差異度屬性約簡(jiǎn)與B為C的一個(gè)正域?qū)傩约s簡(jiǎn)是等價(jià)的。

定義10給定鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，?B?C，對(duì)于a∈C-B的基于差異度的屬性重要度為：

SGFouter(B,a,D)=

?(B)-?(B-{a})=

對(duì)于a∈B的基于差異度的屬性重要度為：

SGFinner(B,a,D)=

?(B-{a})-?(B)=

定義10可以用來對(duì)屬性的重要度大小進(jìn)行度量，屬性重要度越大，表示此屬性越重要。

根據(jù)以上關(guān)于差異度的定理與定義，本文給出基于差異度的啟發(fā)式屬性約簡(jiǎn)算法，見算法1。

算法1基于差異度的啟發(fā)式屬性約簡(jiǎn)算法(HARADD)

輸入：一個(gè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)；

輸出：屬性約簡(jiǎn)集合RED。

Step1初始化RED=?；

Step2Fori=1 to |C|

IfSGFinner(ai,C,D)≠0

RED=RED∪{ai}

End If

End For

Step3while ?(RED)≠?(C)

對(duì)于?aj=C-RED

計(jì)算SGFouter(aj,RED,D)，

If

SGFouter(a′,RED,D)=max{SGFouter(aj,RED,D)}，

RED=RED∪{a′}

End If

Step4輸出RED。

算法時(shí)間復(fù)雜度分析：Step2的時(shí)間復(fù)雜度為O(|C|2|U|2)，Step3的時(shí)間復(fù)雜度為O(|C-RED|·|RED|·|U|2)，所以算法1的時(shí)間復(fù)雜度為O(|C|2|U|2)。

3 鄰域系統(tǒng)中對(duì)象變化的動(dòng)態(tài)屬性約簡(jiǎn)

第2節(jié)提出了一個(gè)基于差異度的啟發(fā)式屬性約簡(jiǎn)算法，而實(shí)際應(yīng)用中，信息系統(tǒng)中的數(shù)據(jù)常常是變化的，其中一個(gè)重要的變化就是對(duì)象的變化，包括對(duì)象的增加或者減少。本節(jié)討論對(duì)象動(dòng)態(tài)變化的鄰域系統(tǒng)中的屬性約簡(jiǎn)問題。

在算法1中，差異度是通過計(jì)算鄰域得到的，對(duì)于對(duì)象變化的鄰域信息系統(tǒng)，更高效地更新鄰域是最為關(guān)鍵的一步。

(1) 當(dāng)增加對(duì)象集合△U+，有：

(2) 當(dāng)減少對(duì)象集合△U-，有：

定理4說明了當(dāng)鄰域信息系統(tǒng)中的對(duì)象變化之后，更新對(duì)象鄰域的過程。

定理5給定動(dòng)態(tài)鄰域信息系統(tǒng)NIS+1=(NIS,△NI)，對(duì)于?B?C，差異度為：

?δ,NIS+1(B)=

定理5說明了當(dāng)鄰域信息系統(tǒng)中的對(duì)象變化之后，差異度的更新過程。

對(duì)于對(duì)象變化的動(dòng)態(tài)鄰域信息系統(tǒng)，基于以上鄰域和差異度更新的機(jī)制，提出鄰域信息系統(tǒng)中對(duì)象變化的動(dòng)態(tài)屬性約簡(jiǎn)算法，見算法2。

算法2鄰域信息系統(tǒng)中對(duì)象變化的動(dòng)態(tài)屬性約簡(jiǎn)算法(DARAOC)

輸入：動(dòng)態(tài)鄰域信息系統(tǒng)NIS+1=(NIS,△NI)，原始屬性約簡(jiǎn)集為REDS，原始差異度為?δ,NIS(C)；

輸出：新的屬性約簡(jiǎn)集REDS+1。

Step1初始化REDS+1=REDS；

Step2while ?δ,NIS+1(REDS+1)≠?δ,NIS+1(C)

對(duì)于?ai∈C-REDS

計(jì)算SGFouter(ai,REDS+1,D)，

If

SGFouter(a′,REDS+1,D)=max{SGFouter(a,REDS+1,D)}

REDS+1=REDS+1∪{a′}，

更新?δ,NIS+1(REDS+1)；

End If

Step3對(duì)于?a∈REDS+1

計(jì)算SGFinner(ai,REDS+1,D)，

IfSGFinner(ai,REDS+1,D)=0

REDS+1=REDS+1-{a}，

更新?δ,NIS+1(REDS+1)；

End If

Step4輸出REDS+1。

算法時(shí)間復(fù)雜度分析：Step2的時(shí)間復(fù)雜度為O(|C-REDS+1|·|C|·|U|·|△U|)，Step3的時(shí)間復(fù)雜度為O(|REDS+1|2·|U+△U|2)，所以算法2的時(shí)間復(fù)雜度為O(|C-REDS+1|·|C|·|U|·|△U|+|REDS+1|2·|U+△U|2)。如果用算法1重新對(duì)對(duì)象變化的鄰域信息系統(tǒng)進(jìn)行屬性約簡(jiǎn)，時(shí)間復(fù)雜度為O(|C|2·|U+△U|2)。顯然，算法2的屬性約簡(jiǎn)效率優(yōu)于算法1。

4 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文所提算法的可行性與高效性，將算法DARAOC與HARADD、鄰域系統(tǒng)中正域?qū)傩约s簡(jiǎn)算法(PDARA)[8]進(jìn)行比較。

從UCI學(xué)習(xí)庫[14]中選4個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的具體信息的如表1所示。本次實(shí)驗(yàn)用MATLAB語言實(shí)現(xiàn)，硬件環(huán)境為Intel處理器3.7 GHz，內(nèi)存4 GB。

表1 UCI中的四個(gè)數(shù)據(jù)集

對(duì)于每個(gè)數(shù)據(jù)集，以20%為遞增量，依次選取整個(gè)對(duì)象集合的20%、40%、60%、80%和100%的對(duì)象進(jìn)行屬性約簡(jiǎn)，選取鄰域參數(shù)δ=0.5。實(shí)驗(yàn)結(jié)果如圖1所示。

選擇對(duì)象的比率/%(a) Zoo

選擇對(duì)象的比率/%(b) Hepatitis

選擇對(duì)象的比率/%(c) Soybean

選擇對(duì)象的比率/%(d) Mushroom圖1 三種約簡(jiǎn)算法實(shí)驗(yàn)結(jié)果對(duì)比

由圖1可以看出，在所有數(shù)據(jù)集上，本文算法HARADD的運(yùn)行時(shí)間都低于算法PDARA，但運(yùn)行時(shí)間較為接近，效率優(yōu)勢(shì)并不明顯。這是因?yàn)閮煞N算法都不能動(dòng)態(tài)地進(jìn)行屬性約簡(jiǎn)，當(dāng)系統(tǒng)中的對(duì)象動(dòng)態(tài)變化時(shí)，算法PDARA基于正域不變來重新對(duì)新系統(tǒng)進(jìn)行屬性約簡(jiǎn)，算法HARADD基于差異度不變來重新對(duì)新系統(tǒng)進(jìn)行屬性約簡(jiǎn)，因此算法效率都不高。

算法DARAOC的運(yùn)行時(shí)間都低于HARADD、PDARA，并且效率優(yōu)勢(shì)較為明顯。此外，隨著數(shù)據(jù)集中的對(duì)象增加，算法DARAOC相比較于HARADD、PDARA運(yùn)行時(shí)間增加的較慢?？梢?，在處理較大數(shù)據(jù)集時(shí)，算法DARAOC效率優(yōu)勢(shì)更大。

5 結(jié) 語

由于現(xiàn)有的數(shù)據(jù)集常常同時(shí)有離散型和數(shù)值型的數(shù)據(jù)，并且可能存在數(shù)據(jù)的缺失，因此鄰域信息系統(tǒng)成為一個(gè)研究熱點(diǎn)。為了對(duì)鄰域信息系統(tǒng)進(jìn)行約簡(jiǎn)，本文提出了差異度的定義，并給出了基于差異度的屬性約簡(jiǎn)算法?？紤]到鄰域信息系統(tǒng)中存在對(duì)象變化的情況，給出了鄰域信息系統(tǒng)中對(duì)象變化的動(dòng)態(tài)屬性約簡(jiǎn)算法。該算法可以更高效地對(duì)對(duì)象變化的鄰域信息系統(tǒng)進(jìn)行屬性約簡(jiǎn)。