可變精度鄰域區(qū)間值決策表的屬性約簡

徐偉華，李思琪

(西南大學 人工智能學院，重慶 400715)

1965年,Zadeh首次提出了模糊集的概念[1],標志著模糊數學的誕生。 該學科在1995年被ACM列為新興的計算機科學研究領域,如今正在繼續(xù)發(fā)展。 因其建立在分類基礎上,可以有效處理不完整不確定問題，所以在實踐中廣泛應用[2]。同時,區(qū)間值決策表[3-4]作為一個分支,能很好描繪不精確對象的特征,在醫(yī)學、金融、機械制造等領域意義重大。Lin和Hu在Zadeh的知識?；幕A上將鄰域引入粗糙集,以粗糙集理論為基礎,衍生出了鄰域粗糙集理論。 該理論重新定義上下近似,實現了一種全新的近似逼近。 鄰域粗糙集理論已經廣泛應用在決策分析、過程控制以及模式識別等[5-9]領域。

在使用過程中需要對屬性值進行屬性約簡。 屬性約簡是粗糙集理論研究的核心問題之一,決策表中有一些條件屬性,由于其屬性值難以測量或測量這些屬性值花費極高,需要將之刪去。 在保持分類水平不變的情況下,盡力刪除這些冗余屬性,使剩余屬性達到最簡,以降低統(tǒng)計難度。 這就是屬性約簡。 事實上,尋找約簡集合[10-13]是 NP-hard 問題,解決這類問題一般是采用啟發(fā)式搜索以獲得近似解。

然而,屬性約簡后的屬性值不可避免會丟失部分原始數據,導致一定程度的信息缺失,限制了粗糙集的應用范圍,為了解決這個問題,前人用鄰域關系代替等價關系，重新定義上下近似與正域,建立了可變精度鄰域決策表[14-15]及相應的屬性約簡算法。 但是現實生活中,區(qū)間值決策表應用范圍更加廣泛。 如果能將這種方法推廣到區(qū)間值決策表,會得到更廣泛的應用。

為此,本文將經典可變精度鄰域信息決策表推廣到區(qū)間值信息決策表上,定義區(qū)間距離以用于計算鄰域,用可變精度閾值計算出條件的正域,對信息表進行屬性約簡。并以屬性質量度為判斷依據,設計相應啟發(fā)式屬性約簡算法。最后，通過實驗驗證了算法的正確性。

1 基本概念

本節(jié)將介紹可變精度鄰域決策表以及區(qū)間值信息決策表的相關概念。

1.1 可變精度鄰域決策表

一個決策表[2]可表示為二元組DT=〈U，AT∪d〉,其中非空有限集合U={x1,x2,…,xn}為對象集,稱為全域或樣本空間,AT表示一個非空的有限條件屬性集合,用于描述U的實數型特征,d是決策屬性。

?x∈U，?a∈AT,a(x)表示樣本x在屬性a上的取值,而d(x)為樣本x在決策屬性d上的值,U/d={X1,X2,…,Xm}代表U被決策屬性d劃分出的決策類。

給定一個決策表DT=〈U,AT∪d〉,且鄰域半徑δ∈(0,1),則對于?x∈U,鄰域δ(x)定義為

δ(x)={xj|xj∈U,Δ(x,xj)≤δ,δ>0},

其中，Δ(x,xj)代表對象x和xj之間的距離。

給定一個決策表DT= 〈U,AT∪d〉，設集合X?U，集合Y?U，則X關于Y的錯誤分類率可表示為

定義1給定一個鄰域信息決策表NDT=〈U，AT∪d〉，該決策表中有m個等價類U/d={X1,X2,…,Xm}。對于?B?AT，引入可變精度的正確率閾值α(0.5≤α≤1)。則該精度下鄰域信息決策表相對于決策屬性d的上近似為

下近似為

正域為

其中：

傳統(tǒng)意義的鄰域決策表在定義上下近似時并未考慮容錯率,因此對錯誤的分類非常敏感。為了更好地處理不確定關系以及減少噪聲干擾,更常使用具有一定容錯性的可變精度鄰域決策表。

如上文所示,可變精度鄰域粗糙集的上下近似是基于α的容錯劃分,通過增大α的值,使之具有更好的覆蓋率。α越小,正域將擴大,容錯率也變大;相反的,α越大,正域越小,容錯率越小,上下近似越精確。 我們需要選擇一個合適的α,使決策表具有良好辨識性的同時,保證一定容錯率。

1.2 區(qū)間值信息決策表

一個區(qū)間值決策表可以表示為IVDT=〈U， AT∪d,VAT,f〉, 其中， 決策屬性d的取值同經典情況(即單值, 而非區(qū)間值)。Va為任意條件屬性a∈vAT的值域,那么其條件屬性值域VAT=∪a∈ATVa。信息函數f:U×AT→VAT滿足?xi∈U,?a∈AT,且f(xi,a)為一個區(qū)間值。

定義2設有兩個不同的區(qū)間A與B，區(qū)間A=[a-,a+],B=[b-,b+]。則A區(qū)間相對于B區(qū)間的優(yōu)勢度定義為

由該定義易知，

1)PA≥B≠PB≥A；

2) 0≤PA≥B≤1；

3)PA≥B+PB≥A=1；

4)PA≥A=0.5。

即2個對象在條件集AT下的歐氏距離,通過這個關系,可以將區(qū)間值決策表與鄰域可變精度決策表結合到一起。顯然,它滿足如下關系，

1) Δ(x,x)=0;

2) Δ(x,y)=Δ(y,x);

3) Δ(x,z)≤Δ(x,y)+Δ(y,z)。

2 變精度鄰域區(qū)間決策表屬性約簡

本節(jié)將可變精度鄰域粗糙集引入區(qū)間值信息決策表,并提出該決策表的約簡方式。

2.1 屬性質量度

給定一個區(qū)間值鄰域決策表INDT=〈U,

AT∪d〉,其中,?B?AT,?a∈AT-B，且X是由決策屬性d劃分而出的等價類?，F有xi∈PosB∪{a}(d),xj∈PosB(d),則屬性a相對于屬性子集B的平均正確分類率的增量函數定義為

即正域改變前后其內所有樣本正確分類率求和取均值后的增量,顯然有

區(qū)間值鄰域決策表INDT=〈U,AT∪d〉，B?AT，若a∈AT-B,則a相對于屬性子集B關于決策屬性d的正域增量函數，可用正域與全域基數之比的增量表示,即文獻[13]中定義的屬性重要性,其定義為

即增加屬性a前后正域的相對改變量,顯然有

定義4區(qū)間值鄰域決策表INDT=〈U,

AT∪d〉,若?B?AT,?a∈AT-B,則a相對于屬性子集B關于決策屬性d的屬性質量度可以定義如下，

2.2 屬性約簡

給定區(qū)間值鄰域決策表INDT=〈U,AT∪d〉,若red是AT的一個約簡集合,對于?a∈red，red需滿足

1) Posred-{a}(d)

2) Posred(d)=PosAT(d)。

屬性質量度函數是正域增量與正確分類率增量的乘積,因此可以用屬性質量度表示這種正域的變化。 即,若?b∈AT-red,以上關系也可表示為

即red中任意一個屬性都是必不可少的,而red以外任意一個屬性對red都是冗余的。 這與經典集的定義是幾乎一致的,只是增加了數值?；?。 這樣可以保證約簡red與全部條件屬性具有相同的分辨能力的同時達到最精簡。

給定區(qū)間值鄰域決表INDT=〈U,AT∪d〉,若B1,B2,…,Bn是該表的全部約簡集合,則稱∩i≤nBi為此信息決策表的核。

3 案例分析

為了說明上一節(jié)屬性約簡的具體機理,本節(jié)給出一個具體案例以進行詳細分析。

現從一個信息表中中抽取8個數據組成一個小型區(qū)間值信息決策表INDT=〈U,AT∪d〉,U={x1,x2,x3,x4,x5,x6,x7,x8},決策屬性d={Rainfall}(Y代表降雨,N代表未降雨)。條件集AT={Vegetation,Humidity,Airflow Rainfall}。 為方便后續(xù)計算,以首字母簡寫代替。 并對其進行歸一化,將區(qū)間值映射到[0,1],處理后的信息決策表見表1。

表1 關于降雨的影響因素的信息決策表

若選取鄰域為δ=0.3,正確率閾值α=0.8,以此表為實例進行計算。依次計算所有屬性子集的鄰域,如表2所示。

表2 所有屬性子集的鄰域

根據表1,決策屬性Rainfall將論域劃分為2個等價類:X1={x1，x4，x5，x6，x8},X2={x2,x3,x7},初始化約簡集合red=?。

根據前文的定義,首先分別求得3個條件及條件全集的正域，

Pos{V}(R)={x1，x3，x4，x5，x6，x7，x8}，

Pos{H}(R)={x1，x3，x4，x5，x7，x8}，

Pos{A}(R)={x1，x3，x4，x5，x6，x7，x8}，

Pos{AT}(R)={x1，x2，x3，x4，x5，x6，x7，x8}。

進一步可求出3個條件的屬性質量度，

根據計算結果,選取屬性質量度最高的條件V或A,即red1={V},red2={A}。

如果選取red1為約簡集合,再分別計算{V,H}、{V，A}的正域，

Pos{V,H}(R)={x1，x2，x3，x4，x5，x6，x7，x8}；

Pos{V,A}(R)={x1，x3，x4，x5，x6，x7，x8}。

再分別計算條件H與條件A相對與red1的屬性質量度，

說明條件A對于red1是冗余的,選取屬性質量度最大的條件H將其加入到約簡集合red1。

又因Pos{V,H}(R)=PosAT(R),即正域不再發(fā)生變化,所以red1={Vegetation,Humidity}即為約簡集合。

同理,可求出red2={Humidity,Airflow}也是一個約簡集合,2個約簡集合的交集{Humidity}為該信息表的核。結果如表3所示。

表3 約簡集合及核

4 算法設計與數值實驗

4.1 算法設計及時間復雜度分析

具體算法如算法1所示。

算法1關于可變精度鄰域區(qū)間值決策表屬性約簡的啟發(fā)式算法

輸入 區(qū)間鄰域決策表 IVDT= 〈U,AT∪d〉，可變精度閾值α，鄰域取值δ。

輸出 屬性約簡集合 red。

1) begin

2) computeU/d={X1,X2,…,Xm};

3) red←?;Qmax←0; /*初始化約簡集合和屬性質量度*/

4) fora∈AT - red do

5) forx∈Udo

6) computeδ(x);/*計算全體對象在{a}∪red下的鄰域*/

7) end

12) end

13) end

14) ifQmax>0 then

15) red←red ∪{amax}; /*屬性質量度最大的屬性被加入約簡集合*/

16) goto 4;

17) else

18) return red;

19) end

20) end

接下來分析該算法的時間復雜度。在該算法中,循環(huán)體主要應用于求解鄰域與計算條件的屬性質量度中。 假設一共有n個條件,最后得到的約簡集合中條件m個,在此時刻約簡了k個條件。

計算屬性質量度時,求出每個條件的正域需要循環(huán)(n-k)×|U|次,求出各條件的屬性質量度需要循環(huán)(n-k)次,這兩個循環(huán)是線性關系,所以時間復雜度為O(n×|U|)。

將新屬性添加至約簡集合的循環(huán)需要經歷(m+1)次,時間復雜度為O(n)。

綜上,時間復雜度為O(n2×|U|2)。

4.2 實驗數據與實驗環(huán)境

為了驗證算法的正確性,本次實驗選用UCI庫上的4個分類數據集。

首先將非數值型的特征值替換為數值型,對數據使用Min-Max歸一化將值映射到[0,1]區(qū)間,以消除量綱影響,隨后將其按照下列方法轉換為區(qū)間值信息決策表,使用算法對其進行屬性約簡。

此外,為驗證算法有效性,我們對其約簡前后的分類能力做了對比,按照8∶2的比例劃分訓練集和測試集,并且選用支持向量機(SVM)與梯度提升模型(GBDT)對其進行驗證。選用的數據集信息如表4所示。

表4 數據集描述

4.3 實驗結果分析

實驗研究了算法在不同鄰域閾值δ(0.4～0.6)和不同可變精度閾值α(0.6～0.9)下得出的約簡集合以及約簡前后分類預測準確率的變化。比較分類精度變化需要對樣本進行機器學習,此時選取的鄰域和變精度為

σ=0.5,α=0.7

以此判斷約簡集合是否可以近似代表整個系統(tǒng)的信息。

圖1反應了約簡前后的數據集在支持向量機(SVM)和梯度提升決策樹(GBDT)下的分類準確率的變化。表5為在上述參數下約簡前后的準確率。實驗結果表明,約簡后的分類準確率均不小于約簡前的準確率。 說明算法選擇的屬性可以有效地近似數據集的分類能力。

表5 一定條件下約簡前后的分類精度

圖1 4種數據集約簡前后的準確率

表6為4個數據集使用本文的方法得出的約簡集,其中的元素是決策屬性的序號,可見在某些條件下約簡集合不止一個。

表6 數據集的約簡集結果

同時,本文選2兩種約簡算法作為對比算法,分別是來自參考文獻[3]中的RDAR算法和誤分代價算法,比較了3種約簡算法的準確率,結果如圖2所示。可見本文算法在4個數據集上的準確率基本大于另外2種算法。

圖2 3種約簡算法準確率

5 結語

本文在基于可變精度鄰域關系的區(qū)間值決策信息表的模型下,提出區(qū)間距離計算公式,并基于此提出該信息表中上下近似、核和正域的概念。 同時,為了刪除在數據采集過程中存在的一些不必要的條件屬性,本文使用正域以及分類正確率的變化定義了屬性質量度,設計了一種啟發(fā)式屬性約簡算法,并通過實驗驗證了該算法的有效性。實驗結果表明,該算法選擇的屬性可以近似原數據集的分類能力。