鄰域系統中對象變化的動態屬性約簡算法

向 偉

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

0 引 言

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

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

為了對對象變化的鄰域系統進行動態屬性約簡，本文介紹了鄰域系統中的差異度概念。當系統中的對象增加或減少時，分析了差異度的變化機制。在此基礎上，提出了鄰域系統中對象變化的動態屬性約簡算法，實驗驗證了所提算法的可行性與高效性。

1 相關概念

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

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

(1)

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

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

(2)

式中：1≤l≤n。

(3)

定義3設鄰域信息系統NI=(U,A,V,f,δ)，?x∈U，B上x的鄰域為：

(4)

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

(1)X的上近似：

(2)X的下近似：

(3)X的邊界域：

定義5設鄰域信息系統NI=(U,A,V,f,δ)，對于B?C，D關于B的正域定義為：

(5)

定義6設鄰域信息系統NI=(U,A,V,f,δ)，對于?B?C，若滿足下列條件，則稱B為C的一個正域屬性約簡。基于正域不變來定義屬性約簡是一個較為常見的方法[7,11-13]。

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

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

2 鄰域系統中基于差異度的屬性約簡

本節給出了鄰域系統中差異度的概念，基于差異度提出了啟發式屬性約簡算法。

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

(6)

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

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

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

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

定理2給定鄰域信息系統NI=(U,A,V,f,δ)，對于?B?C,B為C的一個差異度屬性約簡與B為C的一個正域屬性約簡是等價的。

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

SGFouter(B,a,D)=

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

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

SGFinner(B,a,D)=

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

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

根據以上關于差異度的定理與定義，本文給出基于差異度的啟發式屬性約簡算法，見算法1。

算法1基于差異度的啟發式屬性約簡算法(HARADD)

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

輸出：屬性約簡集合RED。

Step1初始化RED=?；

Step2Fori=1 to |C|

IfSGFinner(ai,C,D)≠0

RED=RED∪{ai}

End If

End For

Step3while ?(RED)≠?(C)

對于?aj=C-RED

計算SGFouter(aj,RED,D)，

If

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

RED=RED∪{a′}

End If

Step4輸出RED。

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

3 鄰域系統中對象變化的動態屬性約簡

第2節提出了一個基于差異度的啟發式屬性約簡算法，而實際應用中，信息系統中的數據常常是變化的，其中一個重要的變化就是對象的變化，包括對象的增加或者減少。本節討論對象動態變化的鄰域系統中的屬性約簡問題。

在算法1中，差異度是通過計算鄰域得到的，對于對象變化的鄰域信息系統，更高效地更新鄰域是最為關鍵的一步。

(1) 當增加對象集合△U+，有：

(2) 當減少對象集合△U-，有：

定理4說明了當鄰域信息系統中的對象變化之后，更新對象鄰域的過程。

定理5給定動態鄰域信息系統NIS+1=(NIS,△NI)，對于?B?C，差異度為：

?δ,NIS+1(B)=

定理5說明了當鄰域信息系統中的對象變化之后，差異度的更新過程。

對于對象變化的動態鄰域信息系統，基于以上鄰域和差異度更新的機制，提出鄰域信息系統中對象變化的動態屬性約簡算法，見算法2。

算法2鄰域信息系統中對象變化的動態屬性約簡算法(DARAOC)

輸入：動態鄰域信息系統NIS+1=(NIS,△NI)，原始屬性約簡集為REDS，原始差異度為?δ,NIS(C)；

輸出：新的屬性約簡集REDS+1。

Step1初始化REDS+1=REDS；

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

對于?ai∈C-REDS

計算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對于?a∈REDS+1

計算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。

算法時間復雜度分析：Step2的時間復雜度為O(|C-REDS+1|·|C|·|U|·|△U|)，Step3的時間復雜度為O(|REDS+1|2·|U+△U|2)，所以算法2的時間復雜度為O(|C-REDS+1|·|C|·|U|·|△U|+|REDS+1|2·|U+△U|2)。如果用算法1重新對對象變化的鄰域信息系統進行屬性約簡，時間復雜度為O(|C|2·|U+△U|2)。顯然，算法2的屬性約簡效率優于算法1。

4 實驗結果分析

為了驗證本文所提算法的可行性與高效性，將算法DARAOC與HARADD、鄰域系統中正域屬性約簡算法(PDARA)[8]進行比較。

從UCI學習庫[14]中選4個數據集進行實驗，數據集的具體信息的如表1所示。本次實驗用MATLAB語言實現，硬件環境為Intel處理器3.7 GHz，內存4 GB。

表1 UCI中的四個數據集

對于每個數據集，以20%為遞增量，依次選取整個對象集合的20%、40%、60%、80%和100%的對象進行屬性約簡，選取鄰域參數δ=0.5。實驗結果如圖1所示。

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

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

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

選擇對象的比率/%(d) Mushroom圖1 三種約簡算法實驗結果對比

由圖1可以看出，在所有數據集上，本文算法HARADD的運行時間都低于算法PDARA，但運行時間較為接近，效率優勢并不明顯。這是因為兩種算法都不能動態地進行屬性約簡，當系統中的對象動態變化時，算法PDARA基于正域不變來重新對新系統進行屬性約簡，算法HARADD基于差異度不變來重新對新系統進行屬性約簡，因此算法效率都不高。

算法DARAOC的運行時間都低于HARADD、PDARA，并且效率優勢較為明顯。此外，隨著數據集中的對象增加，算法DARAOC相比較于HARADD、PDARA運行時間增加的較慢。可見，在處理較大數據集時，算法DARAOC效率優勢更大。

5 結 語

由于現有的數據集常常同時有離散型和數值型的數據，并且可能存在數據的缺失，因此鄰域信息系統成為一個研究熱點。為了對鄰域信息系統進行約簡，本文提出了差異度的定義，并給出了基于差異度的屬性約簡算法。考慮到鄰域信息系統中存在對象變化的情況，給出了鄰域信息系統中對象變化的動態屬性約簡算法。該算法可以更高效地對對象變化的鄰域信息系統進行屬性約簡。