基于0-1規(guī)劃的最小屬性約簡算法

詹婉榮，于 海

(洛陽師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院, 河南 洛陽 471934)

粗糙集理論是波蘭數(shù)學(xué)家Pawlak于1982年提出的，它是一種新型的處理模糊和不確定知識的數(shù)學(xué)工具，其主要思想就是在保持分類能力不變的前提下，通過知識約簡，導(dǎo)出問題的決策或分類規(guī)則[1]. 屬性約簡是粗糙集理論中的核心內(nèi)容之一.數(shù)據(jù)庫中的屬性并不是同等重要的, 甚至其中某些知識是冗余的，通過屬性約簡, 可以去除數(shù)據(jù)庫中的冗余、無用的成分, 揭示數(shù)據(jù)中隱含的規(guī)律.從粗糙集理論的角度來理解, 在一個信息系統(tǒng)中, 有些屬性對于分類來說是多余的, 去掉這些屬性后，信息系統(tǒng)的分類能力不會改變, 所以屬性約簡后仍然反映了一個信息系統(tǒng)的本質(zhì)信息[2-6].一般來講，一個信息系統(tǒng)的屬性約簡不是唯一的，通常人們希望能夠找到一個屬性個數(shù)最小的屬性約簡，該屬性約簡稱為最小屬性約簡.對任一給定信息系統(tǒng)，若屬性約簡算法能確保找到其最小屬性約簡，則該算法稱為最小屬性約簡的完備算法.

然而，Wong和Zlarko已經(jīng)證明了尋找一個信息系統(tǒng)的最小約簡是NP-hard 問題[7].導(dǎo)致NP-hard 問題的主要原因是屬性的組合爆炸問題.傳統(tǒng)的屬性約簡算法大都屬于啟發(fā)式的搜索算法，它們的優(yōu)點(diǎn)是易于實(shí)現(xiàn)，且計算速度快，但求出的不一定是最小屬性約簡.因此在本文中，我們將最小屬性約簡問題轉(zhuǎn)化為一個優(yōu)化問題，進(jìn)而轉(zhuǎn)化為0-1規(guī)劃.通過求解該0-1規(guī)劃，得到了信息系統(tǒng)的最小屬性約簡.在此基礎(chǔ)上給出了基于0-1規(guī)劃的最小屬性約簡算法，并且該算法是最小屬性約簡的完備算法.

1 信息系統(tǒng)及其屬性約簡

本小節(jié)僅介紹與本文有關(guān)的主要概念，其他概念可參見文獻(xiàn)[8-9].

定義1信息系統(tǒng)S是一個四元組：S=(U,AT,V,f)，其中U表示對象的非空有限集合，稱為論域；AT表示屬性的非空有限集合；V是屬性的值域集；f是信息函數(shù)，f:U×AT→V.

定義2設(shè)A?AT，不可區(qū)分關(guān)系ind(A)?U×U定義如下

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

f(x,a)=f(y,a)}.

對任意兩個對象x,y∈U，若xind(A)y，則基于屬性集A，x和y是不可區(qū)分的.

根據(jù)不可區(qū)分關(guān)系的定義，Pawlak將信息系統(tǒng)的約簡定義為保持不可區(qū)分關(guān)系ind(AT)不變的極小屬性集.

定義3設(shè)S=(U,AT,V,f)為一信息系統(tǒng)，屬性集R?AT稱為一個約簡，如果滿足以下兩個條件：

(1)ind(R)=ind(AT)；

(2) ?a∈R，ind(R-{a})≠ind(AT).

一般情況下，信息系統(tǒng)的約簡不唯一，所有約簡之集記作Red(S).

定義4所有約簡的交集稱為核，記作Core(S).

設(shè)S=(U,AT,V,f)為信息系統(tǒng)，其中

U={u1,u2, …,un}，AT={a1,a2, …,am}.

定義5設(shè)S=(U,AT,V,f)為信息系統(tǒng)，|U|=n，S的區(qū)分矩陣是一個n×n的矩陣M=(Mij)，其中Mij對應(yīng)對象(ui,uj)，定義為

Mij={a∈AT|f(ui,a)≠f(uj,a)}.

Mij是由能區(qū)分對象ui和uj的屬性組成的集合.如果Mij≠φ，那么對象ui和uj是可區(qū)分的.另外，區(qū)分矩陣M是對稱的，即Mij=Mji，且Mii=φ.所以，只需給出區(qū)分矩陣的下三角矩陣即可.

定義6區(qū)分矩陣M的區(qū)分函數(shù)定義為

f(M)=∧{∨Mij|Mij≠φ, 1≤i,j≤n}.

其中∨Mij表示Mij中的屬性的析取，∧{∨Mij}表示∨Mij的合取.

2 基于0-1規(guī)劃的最小屬性約簡算法

雖然利用定義6中的區(qū)分函數(shù)可以求出所有的約簡，但在實(shí)際應(yīng)用中，有時只需找到一個約簡即可.于是人們?nèi)ふ易钚〖s簡(即約簡中屬性的個數(shù)最小).

在給出基于0-1規(guī)劃的最小約簡算法之前，我們先分析約簡產(chǎn)生的過程.

定理1設(shè)S=(U,AT,V,f)是一個信息系統(tǒng)，M為S的區(qū)分矩陣，R?AT為S的一個約簡當(dāng)且僅當(dāng)以下兩個條件成立.

(1) ?1≤i,j≤n，Mij≠φ?R∩Mij≠φ;

(2) ?a∈R, ?i,j, 使得Mij≠φ，滿足

(R-{a})∩Mij=φ.

由定理1可知，一個約簡和區(qū)分矩陣中每個非空元素的交都不能為空.也就是說，約簡中的屬性取自區(qū)分矩陣中這些非空元素，但是這些元素之間存在“重復(fù)”現(xiàn)象.

定義7設(shè)X,Y為區(qū)分矩陣M中的2個元素，若X?Y，即X中的屬性都是Y中的屬性，稱Y為X的重復(fù)元素.

為了容易求得約簡，我們把區(qū)分矩陣中的重復(fù)元素刪去，同時也去掉空集，引入極小區(qū)分集的概念.

定義8設(shè)MS={S1,S2, …,Sl}滿足以下條件:

(1) ?Sk∈MS，存在區(qū)分矩陣元素Mij，使得

Mij≠φ，Sk=Mij;

(2) ?i,j∈{1, 2, …,n}，

k∈{1, 2, …,l}，Mij≠φ，

若Mij?Sk，則Sk=Mij.

則稱MS為信息系統(tǒng)S=(U,AT,V,f)的極小區(qū)分集.

由定義8可知，極小區(qū)分集實(shí)際上是由區(qū)分矩陣中非空元素的極小元組成的.換句話說，在區(qū)分矩陣中，刪去所有重復(fù)元素和空集就得到了極小區(qū)分集.

在得到約簡的過程中，極小區(qū)分集與區(qū)分矩陣起到相同的作用，可以代替區(qū)分矩陣.

定理2設(shè)MS為信息系統(tǒng)S的極小區(qū)分集，

R?AT，則R為一個約簡的充要條件是：

(1)R∩Si≠φ，i=1, 2, …,l；

(2) ?a∈R, ?k∈{1, 2, …,l}，

(R-{a})∩Sk=φ.

證明由定理1和定義8容易得證.

由定理2，可將計算最小屬性約簡R轉(zhuǎn)化為如下的優(yōu)化問題：

min|R|

(1)

s.t.R∩Si≠φ，i=1, 2, …,l，

?a∈R, ?k∈{1, 2, …,l},

(R-{a})∩Sk=φ,

其中|R|表示R中屬性的個數(shù).

經(jīng)過分析，可將上述的優(yōu)化問題的第二個條件去掉，得到如下定理.

定理3R為信息系統(tǒng)S的最小屬性約簡當(dāng)且僅當(dāng)R為下面的優(yōu)化問題的最優(yōu)解.

min|R|

(2)

s.t.R∩Si≠φ，i=1, 2, …,l.

證明只需證明優(yōu)化問題(2)和優(yōu)化問題(1)等價.

(ⅰ)設(shè)R*為(2)的最優(yōu)解，為了證明R*為(1)的最優(yōu)解，只需證明R*滿足?a∈R*, ?k∈{1, 2, …,l}，(R*-{a})∩Sk=φ即可.

用反證法，假設(shè)?a∈R*, ?k∈{1, 2, …,l}，(R*-{a})∩Sk=φ不成立，其等價于?a∈R*,

?k∈{1, 2, …,l}，(R*-{a})∩Sk≠φ.令R′=R*-{a}，則?i∈{1, 2, …,l}，

(R′)∩Si≠φ，R′為(2)的可行解.

但|R′|<|R*|，這與R*為(2)的最優(yōu)解相矛盾.因此R*滿足?a∈R*, ?k∈{1, 2, …,l}，(R*-{a})∩Sk=φ，即證R*為(1)的最優(yōu)解.

(ⅱ)反過來，設(shè)R*為(1)的最優(yōu)解，易知R*為(2)的可行解.又因?yàn)镽*滿足條件?a∈R*, ?k∈{1, 2, …,l}, (R*-{a})∩Sk=φ，則R*去掉任意一個屬性，(2)的約束條件就不再成立，由此說明R*為(2)的最優(yōu)解.

下面將優(yōu)化問題(2)轉(zhuǎn)化為0-1規(guī)劃.

j=1, 2, …,m.同樣容易驗(yàn)證

(3)

xj=0或1.

以下將0-1規(guī)劃(3)改寫為矩陣形式.

mincTx

(4)

s.t.Px≥q

xj=0或1.

由定理3可知，計算信息系統(tǒng)的最小屬性約簡可轉(zhuǎn)化為求解0-1規(guī)劃(4).而解決0-1規(guī)劃問題通常采用隱枚舉法，隱枚舉法只需比較目標(biāo)函數(shù)在一小部分組合點(diǎn)上的取值大小就能求得最優(yōu)解，從而大大減少了工作量.而且0-1規(guī)劃是常見的優(yōu)化方法，在生產(chǎn)、生活中有著廣泛的應(yīng)用.目前常見的數(shù)學(xué)軟件如MATLAB、LINGO等均能直接求解.

本文將計算信息系統(tǒng)的最小屬性約簡轉(zhuǎn)化為求解0-1規(guī)劃問題，求得的約簡必定是最小屬性約簡，所以本文中提出的基于0-1規(guī)劃的最小屬性約簡算法是完備的.

接下來我們給出基于0-1規(guī)劃的最小屬性約簡算法.

步驟1 由定義5求區(qū)分矩陣M；

步驟2 計算極小區(qū)分集MS={S1,S2, …,Sl}；

步驟3 由極小區(qū)分集MS計算矩陣P=(pij)，其中

步驟4 求解0-1規(guī)劃(4) ，得到一個最小屬性約簡.

3 實(shí)例分析

為了進(jìn)一步說明本文提出的基于0-1規(guī)劃的最小屬性約簡算法，下面給出一個實(shí)例.

例1 給定一個信息系統(tǒng)如表1所示，其中U={x1,x2, …,x8}為對象集，AT={a1,a2, …,a6}為屬性集.下面給出求表1所示信息系統(tǒng)的最小屬性約簡的過程.

表1 信息系統(tǒng)

為了方便，我們將屬性a1,a2, …,a6分別用1, 2, …, 6表示. 按照定義5計算得到信息系統(tǒng)的區(qū)分矩陣M為

MS={{1, 4, 6}, {2, 4, 6}, {4, 5}, {3}, {1, 2}, {1, 5, 6}}.

計算得到矩陣P為

計算0-1規(guī)劃

mincTx

s.t.Px≥q

xj=0或1.

得到最優(yōu)解為x=(1, 0, 1, 1, 0, 0)T，于是信息系統(tǒng)的最小屬性約簡為R={a1,a3,a4}.

4 結(jié)語

屬性約簡是粗糙集理論的核心內(nèi)容之一.由于尋找信息系統(tǒng)的所有約簡是NP完全問題，因此本文研究了信息系統(tǒng)的最小屬性約簡問題. 將最小屬性約簡問題轉(zhuǎn)化為0-1規(guī)劃問題，從而提出了基于0-1規(guī)劃的最小屬性約簡算法.本文中的屬性約簡方法為粗糙集的屬性約簡提供了新的方法.實(shí)例分析表明，本文的算法是有效可行的.