信息系統(tǒng)的最大可能約簡(jiǎn)算法

詹婉榮，于 海

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

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

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

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

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

AT可進(jìn)一步劃分為2個(gè)集合: 條件屬性集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)}.

對(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(約簡(jiǎn))設(shè)S=(U,AT,V,f)為一信息系統(tǒng)，如果滿足以下兩個(gè)條件，那么屬性集R?AT被稱為一個(gè)約簡(jiǎn).

(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)，以下我們?cè)O(shè)

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

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

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

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

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

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

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

2 最大可能約簡(jiǎn)算法

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

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

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

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

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

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

在構(gòu)建屬性重要度之前，我們先分析約簡(jiǎn)產(chǎn)生的過(guò)程.

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

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

(2)?a∈R,?i,j, 使得

Mij≠?，(R-{a})∩Mij≠?.

由定理1可知，一個(gè)約簡(jiǎn)和區(qū)分矩陣中每個(gè)非空屬性集的交都不能為空.也就是說(shuō)，約簡(jiǎn)中的屬性取自于且只能取自于區(qū)分矩陣中這些非空屬性集.

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

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

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

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

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

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

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

(1)

(2)

對(duì)于約簡(jiǎn)中的核有下面定理.

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

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

于是

=0.

證畢.

注1:

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

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

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

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

這樣得到的約簡(jiǎn)，我們稱之為最大可能約簡(jiǎn).接下來(lái)我們給出一個(gè)尋找最大可能約簡(jiǎn)的算法.

算法(最大可能約簡(jiǎn)算法):

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

輸出: 最大可能約簡(jiǎn)R

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

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

步驟3 R=?；

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

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

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

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

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

注2:

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

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

3 實(shí)例分析

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

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

表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)式計(jì)算每個(gè)屬性的概率:

按照最大可能約簡(jiǎn)算法，先將屬性a添加到約簡(jiǎn)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的元素，此時(shí)，MS=?，則得到最大可能約簡(jiǎn)為R={a,d,e}.

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

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

表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)式計(jì)算每個(gè)屬性的概率:

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

由此例可以看出:

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

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

4 結(jié)語(yǔ)

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