詹婉榮，于 海

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

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

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

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

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

定義1信息系統(tǒng)S是一個(gè)四元組：S=(U,AT,V,f)，其中U表示對(duì)象的非空有限集合，稱為論域；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)}.

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

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

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

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

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

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

定義4所有約簡(jiǎn)的交集稱為核，記作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ū)分矩陣是一個(gè)n×n的矩陣M=(Mij)，其中Mij對(duì)應(yīng)對(duì)象(ui,uj)，定義為

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

Mij是由能區(qū)分對(duì)象ui和uj的屬性組成的集合.如果Mij≠φ，那么對(duì)象ui和uj是可區(qū)分的.另外，區(qū)分矩陣M是對(duì)稱的，即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ī)劃的最小屬性約簡(jiǎn)算法

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

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

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

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

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

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

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

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

為了容易求得約簡(jiǎn)，我們把區(qū)分矩陣中的重復(fù)元素刪去，同時(shí)也去掉空集，引入極小區(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ū)分集.

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

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

R?AT，則R為一個(gè)約簡(jiǎn)的充要條件是：

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

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

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

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

由定理2，可將計(jì)算最小屬性約簡(jiǎn)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中屬性的個(gè)數(shù).

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

定理3R為信息系統(tǒng)S的最小屬性約簡(jiǎn)當(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)等價(jià).

(ⅰ)設(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=φ不成立，其等價(jià)于?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)解.

(ⅱ)反過來(lái)，設(shè)R*為(1)的最優(yōu)解，易知R*為(2)的可行解.又因?yàn)镽*滿足條件?a∈R*, ?k∈{1, 2, …,l}, (R*-{a})∩Sk=φ，則R*去掉任意一個(gè)屬性，(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可知，計(jì)算信息系統(tǒng)的最小屬性約簡(jiǎn)可轉(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等均能直接求解.

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

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

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

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

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

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

3 實(shí)例分析

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

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

表1 信息系統(tǒng)

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

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

計(jì)算得到矩陣P為

計(jì)算0-1規(guī)劃

mincTx

s.t.Px≥q

xj=0或1.

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

4 結(jié)語(yǔ)

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