詹婉榮，于 海

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

粗糙集理論由波蘭數(shù)學(xué)家Pawlak于1982年提出，它是一種新型的處理模糊和不確定知識的數(shù)學(xué)工具，其主要思想就是在保持分類能力不變的前提下，通過知識約簡，導(dǎo)出問題的決策或分類規(guī)則.經(jīng)過多年的發(fā)展，該理論已被成功地用于機器學(xué)習(xí)、決策分析、過程控制、模式識別和數(shù)據(jù)挖掘等領(lǐng)域[1].

屬性約簡是粗糙集理論中的核心研究內(nèi)容之一[2-3].數(shù)據(jù)庫中的屬性并不是同等重要的, 甚至其中某些知識是冗余的，通過屬性約簡, 可以去除數(shù)據(jù)庫中的冗余、無用的成分, 從而揭示數(shù)據(jù)中隱含的規(guī)律.從粗糙集理論的角度看, 在一個信息系統(tǒng)中, 有些屬性對于分類來說是多余的, 去掉這些屬性后，信息系統(tǒng)的分類能力不會改變, 所以屬性約簡后仍然會反映一個信息系統(tǒng)的本質(zhì)信息.然而，在一個信息系統(tǒng)中尋找所有約簡或最優(yōu)屬性約簡會面臨NP-hard問題.目前解決這一問題通常考慮啟發(fā)式算法，大多數(shù)啟發(fā)式算法都是以屬性重要性作為衡量指標(biāo)對屬性進(jìn)行篩選，最終求得最優(yōu)或次優(yōu)的約簡組合.根據(jù)屬性重要性度量方法的不同，目前算法主要分為三大類: 基于屬性在區(qū)分矩陣中出現(xiàn)的頻率的方法[4-7]、基于屬性依賴度的方法[8-9]以及基于信息熵的方法[10-11].

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

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

AT可進(jìn)一步劃分為2個集合: 條件屬性集C和決策屬性集D，并滿足AT=C∪D且C∩D=φ, 則S被稱為決策系統(tǒng).

定義2(不可區(qū)分關(guān)系)設(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)，以下我們設(shè)

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

定義5(區(qū)分矩陣)設(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的含義為:Mij是由能區(qū)分對象ui和uj的屬性組成的集合.如果Mij≠φ，那么對象ui和uj是可區(qū)分的.另外，區(qū)分矩陣M是對稱的，即Mij=Mji，且Mii=φ.所以，只需給出區(qū)分矩陣的下三角矩陣即可.

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

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

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

2 最大可能約簡算法

雖然利用定義6中的區(qū)分函數(shù)可以求出所有的約簡，但尋找信息系統(tǒng)的所有約簡是NP完全問題，而且在實際應(yīng)用中，我們不必找出所有約簡，有時找到一個約簡就能滿足需要.本文中，我們不去尋找所有約簡，而是尋找發(fā)生的可能性最大的約簡.

依據(jù)區(qū)分矩陣的定義可知，某個屬性在區(qū)分矩陣中出現(xiàn)的頻率越高，該屬性可區(qū)分的對象數(shù)就越多，進(jìn)而表明它的重要性就越大.另外如果Mij中只有一個屬性，該屬性一定在約簡中.進(jìn)一步分析可知，區(qū)分矩陣中某項的屬性個數(shù)越小，該項對分類所起的作用就越大.

由于尋找所有約簡是NP完全問題，目前幾乎所有的約簡算法都是基于啟發(fā)式的，其策略依賴于屬性重要性的定義，因此對屬性重要性的定義是一個關(guān)鍵問題.基于上面的分析，本文構(gòu)建的屬性重要度必須滿足以下3條規(guī)則:

(1)區(qū)分矩陣中某些屬性出現(xiàn)的越頻繁，該屬性就越重要；

(2))區(qū)分矩陣中某項若只有一個屬性, 則該屬性的重要性最大；

(3)區(qū)分矩陣某項中屬性個數(shù)越小，該項中屬性的重要性越大.

在構(gòu)建屬性重要度之前，我們先分析約簡產(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ū)分矩陣中這些非空屬性集.

令MS={Mij|Mij≠?, 1≤j

進(jìn)一步分析可知，如果R?AT是一個約簡，由定理1可得到如下結(jié)論:

(1)?a∈R,a必取自于MS中一個或多個屬性集.

(2)?Si∈MS，一定有R中的屬性取自于Si.

約簡總是存在的且不唯一，我們要得到一個約簡，必須從S=i中取一個屬性.本文在Si中，優(yōu)先選取概率較大的屬性.

以下我們計算一個屬性出現(xiàn)在約簡中的概率.

MS={S1,S2, …,Sl},不失一般性，不妨設(shè)

(1)

(2)

對于約簡中的核有下面定理.

定理2若屬性ai是核，即ai∈Core(S)，則ai出現(xiàn)在約簡中的概率P(Bi)=1.

證明若屬性ai是核，則ai在MS中一定以單屬性集的形式出現(xiàn)，即{ai}∈MS.設(shè){ai}在MS中排第k位.則由(1)式可得

于是

=0.

證畢.

注1:

(1)由以上分析可知，屬性ai出現(xiàn)在約簡中的概率P(Bi)滿足上面提到的屬性重要性的3條規(guī)則.因此我們把P(Bi)作為屬性ai的重要度是合理的.

(2)文獻(xiàn)[4]和文獻(xiàn)[5]以屬性在區(qū)分矩陣出現(xiàn)的次數(shù)或頻率作為屬性的重要度，而我們是以屬性出現(xiàn)在約簡中的概率作為屬性的重要度的.

P(Bi)越大，表示屬性ai出現(xiàn)在約簡中的可能性越大.下面我們以P(Bi)為屬性ai的重要度給出最大可能約簡的定義, 并構(gòu)造最大可能約簡算法.

定義7(最大可能約簡)以空集作為初始約簡集，將屬性出現(xiàn)在約簡中的概率作為屬性的重要度，依次選擇屬性重要度較大的屬性添加到約簡集中，直至得到一個約簡為止.

這樣得到的約簡，我們稱之為最大可能約簡.接下來我們給出一個尋找最大可能約簡的算法.

算法(最大可能約簡算法):

輸入:S=(U,AT,V,f)

輸出: 最大可能約簡R

步驟1 由定義5求區(qū)分矩陣M，計算集合MS；

步驟2 由(2)式計算各個屬性出現(xiàn)在約簡中的概率P(Bi)；

步驟3 R=?；

步驟4 計算A=∪MS，并選取A中概率最大的屬性a(如果有多個，就任選一個)，R=R∪{a}；

步驟5 刪除MS中含屬性a的元素，即

MS=MS-MS+(a)，(其中MS+(a)表示MS中含有屬性a的元素組成的集合)；

步驟6 若MS≠?，轉(zhuǎn)步驟4，否則算法結(jié)束，輸出最大可能約簡R.

下面給出上述算法的時間復(fù)雜度分析.

注2:

(1)由定理2可知，核屬性出現(xiàn)在約簡中的概率為100%，因此核一定優(yōu)先選入約簡中.

(2)最大可能約簡總是存在的，但不唯一.

3 實例分析

為了進(jìn)一步說明本文提出的最大可能約簡算法，下面給出兩個實例.

例1以表1給出的信息系統(tǒng)為例，說明最大可能約簡算法的可行性和有效性.

表1中信息系統(tǒng)的區(qū)分矩陣M為

M=

表1 信息系統(tǒng)

由此可得MS為：

MS={{a,d},{a,b,c,e},{a,c},{d,e},

{b,e},{b,c,d,e},{a,c,d},{a,d,e},{a,b,d,e},{a,b,c,e},{a,b,c,d},

{a,c},{a,c,d,e},{a,b,c,e},{b,d}}

于是A={a,b,c,e}，根據(jù)(2)和(1)式計算每個屬性的概率:

按照最大可能約簡算法，先將屬性a添加到約簡R中，在MS中刪去含有a的元素，得

MS={{d,e,},{b,e},{b,c,d,e},{b,d}}，

A=∪MS={b,c,d,e}.接著將屬性d加入到R中，刪去MS中含有d的元素，MS={{b,e}},A=∪MS={be}，再將屬性e加入R中，刪去e的元素，此時，MS=?，則得到最大可能約簡為R={a,d,e}.

從此例可以看出，盡管屬性c出現(xiàn)在約簡中的概率和屬性e出現(xiàn)在約簡中的概率相等，但在將屬性a,d加入約簡R的過程中被刪去.故在最大可能約簡R中并不含有c.

例2 表2給出一個信息系統(tǒng)，我們來求該信息系統(tǒng)的最大可能約簡.以此說明核屬性出現(xiàn)在約簡中的概率為1，以及最大可能約簡不是唯一的.

表2 信息系統(tǒng)

表2中信息系統(tǒng)的區(qū)分矩陣為:

MS={{a,b,c},{a,b,c},{a,c},{a,b,c},{b,c},{a,b},,{a,b,c},{b,c},{a,b}}.

而A={a,b,c}，根據(jù)(2)式和(1)式計算每個屬性的概率:

按照最大可能約簡算法，先將屬性b添加到約簡R中，在MS中刪去含有b的元素，MS={{a,c}},A={a,c}，這時，屬性a和屬性c的概率一樣，如果將屬性a加入到R中，刪去MS中含有a的元素，此時，MS=?，于是得到最大可能約簡為R={b,a}.如果將屬性c加入到R中，則得到最大可能約簡為R={b,c}.

由此例可以看出:

(1)在區(qū)分矩陣中，屬性b是單屬性集，即屬性b是核，它出現(xiàn)在約簡中的概率P(b)=P(B2)=1；

(2)最大可能約簡是不唯一的.

4 結(jié)語

屬性約簡是粗糙集理論的核心內(nèi)容.因為尋找信息系統(tǒng)的所有約簡是NP完全問題,所以本文在區(qū)分矩陣的基礎(chǔ)上提出了最大可能約簡算法，為粗糙集的屬性約簡提供了新的方法.該算法在區(qū)分矩陣的基礎(chǔ)上，計算每個屬性出現(xiàn)在約簡中的概率，并根據(jù)概率的大小，對屬性進(jìn)行排序，將概率大的屬性優(yōu)先添加到約簡中，直到得到一個約簡.本文提出的最大可能約簡是粗糙集理論在實際應(yīng)用中的探索.理論分析結(jié)果表明，本文的算法是有效可行的.