賈俊芳

(山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同 037009）

基于相對(duì)知識(shí)量重要度的屬性約簡(jiǎn)算法

賈俊芳

(山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同 037009）

在有效處理噪聲數(shù)據(jù)的基于區(qū)分能力大小的啟發(fā)式算法的基礎(chǔ)上，引入了屬性的相對(duì)知識(shí)量重要度的概念.以屬性相對(duì)知識(shí)量重要度為啟發(fā)式信息，提出了一種屬性約簡(jiǎn)算法，通過(guò)實(shí)例證明了該算法的有效性.

相對(duì)知識(shí)量 重要度 屬性約簡(jiǎn)

Pawlak等人提出的粗糙集理論，作為一種處理模糊概念和不確定性知識(shí)的數(shù)據(jù)推理方法，已在實(shí)際生活中得到了廣泛的應(yīng)用.涉及了人工智能，模式識(shí)別，機(jī)器學(xué)習(xí)，專(zhuān)家系統(tǒng)等有關(guān)領(lǐng)域.

粗糙集理論認(rèn)為知識(shí)是區(qū)分事物的能力，相同的等價(jià)類(lèi)區(qū)分事物的能力相同，就具有相同的知識(shí)量.如果論域中的所有的元素只能劃分為同一個(gè)等價(jià)類(lèi)，那么這時(shí)具有的知識(shí)量為最少.數(shù)據(jù)庫(kù)中的屬性其重要度不同，尤其是在現(xiàn)實(shí)生活中，采集到的數(shù)據(jù)必然存在誤差，甚至出現(xiàn)缺省值的數(shù)據(jù)，常表現(xiàn)為噪聲數(shù)據(jù)和缺省值數(shù)據(jù)，這兩種屬性都會(huì)出現(xiàn)分類(lèi)誤差，直接影響約簡(jiǎn)的結(jié)果.對(duì)于第一種屬性，有允許一定范圍誤分類(lèi)率的可變精度粗糙集模型等方法來(lái)解決；對(duì)于第二種屬性，多出現(xiàn)在不完備信息系統(tǒng)中，通過(guò)為缺省值增加屬性值的方法來(lái)解決.

文中從知識(shí)區(qū)分事物的能力出發(fā)，在文獻(xiàn)[1]提出的知識(shí)量定義的基礎(chǔ)上，給出了屬性相對(duì)知識(shí)重要度的度量方法.提出了一種新的屬性約簡(jiǎn)算法，并通過(guò)實(shí)例驗(yàn)證了該算法的有效性.

1 相關(guān)概念

定義1信息系統(tǒng)S＝（U，A，{Va}，f）是一個(gè)四元組，其中U是非空有限集合，稱(chēng)為論域；A是非空有限集合，稱(chēng)為屬性集合；Va是屬性a∈A的值域；f∶U→Va為一單射，使論域U中的任一元素取屬性a在Va中的某一唯一值.A由條件屬性集合C和決策屬性集合D組成，C和D滿(mǎn)足C∪D＝A，C∩ D＝φ，則稱(chēng)S為決策系統(tǒng)，用（U，C∪D）表示.當(dāng)決策屬性集合只有一個(gè)元素時(shí)也常用（U，C∪ccakgms）表示.若B?C，?x，y∈U，x≠y稱(chēng)二元關(guān)系IND（B，m00uuog）＝{（x，y）∈U×U｜d（x）＝d（y）或者a∈B，a（x）＝a（y）}為不可分辨關(guān)系.

定義2對(duì)于信息系統(tǒng)S＝（U，A，{Va}，f），B?A，X?U，稱(chēng)＝{x∈U｜[x]IND(B）?X}，＝{x∈U｜[x]IND(B）∩X≠φ}分別為X的B下近似集和B上近似集.posB＝成為X的B正域，negB＝U－成為X的B負(fù)域，bnB（X）＝－成為X的B邊界域.

定義3對(duì)于給定的決策系統(tǒng)（U，C∪e0qqms0），條件屬性集合C的一個(gè)約簡(jiǎn)是它的一個(gè)非空子集C′，滿(mǎn)足：

(1)IND（C，k80iu0o）＝IND（C′，igqok0o）；

(2)不存在C″?C′，使得IND（C″，q040m0w）＝IND（C′，gco0giy）；C的所有約簡(jiǎn)的集合為SREC（C），C的所有約簡(jiǎn)的交集為SCORE（C），且滿(mǎn)足SCORE（C）＝∩SREC（C）.

2 相對(duì)知識(shí)量重要度的定義

屬性約簡(jiǎn)的目的是在保持現(xiàn)有屬性分類(lèi)能力不變的前提下，去除冗余的屬性，尋找最優(yōu)的子集.通常用到的方法為屬性依賴(lài)度，屬性的重要度等.但屬性的重要度究竟該如何度量，沒(méi)有一個(gè)準(zhǔn)確的概念.本文提出了一種新的基于相對(duì)知識(shí)量重要度的度量方法，根據(jù)相對(duì)知識(shí)量重要度提出了屬性約簡(jiǎn)的方法.

文獻(xiàn)[1]中提出了知識(shí)量的定義：知識(shí)量是一種能夠區(qū)分事物的能力，用以下表達(dá)式來(lái)描述：

定義1 給定信息系統(tǒng)S＝（U，A，{Va}，f），屬性集合P能夠?qū)⒄撚騏劃分為m個(gè)等價(jià)類(lèi)，每個(gè)等價(jià)類(lèi)中元素的個(gè)數(shù)為n1，n2，…nm，那么該屬性具有的知識(shí)量記作WU，P＝W（n1，n2，…，nm），它滿(mǎn)足：

1.W（n）＝0；

2.W（n1，…；ni，…；nj，…；nm）＝W（n1，…；nj，…；ni，…；nm）；

3.W（n1，n2，…，nm）＝W（n1，n2，…，nm）+W（n2，…，nm）；

4.W（n1，n2+n3）＝W（n1，n2）+W（n1，n3）.

定理1[3]如果某屬性集合將論域U劃分成m個(gè)等價(jià)類(lèi)，每個(gè)等價(jià)類(lèi)中元素個(gè)數(shù)為p1，p2，…，pm，則該屬性集合具有的知識(shí)量為

上述定義的知識(shí)量是基于粗糙集理論認(rèn)為知識(shí)是能夠區(qū)分事物的能力而的得到的，是一種對(duì)事物的絕對(duì)化度量方法，借鑒上面概念我們給出相對(duì)知識(shí)量的定義：

定義2[4]給定四元組信息系統(tǒng)S＝（U，A，{Va}，f），P是信息表中某些屬性的集合，Q是信息表中另一屬性集合，則屬性集合Q相對(duì)于屬性集合P的相對(duì)知識(shí)量為：

定義3給定四元組決策信息系統(tǒng)S＝（U，A，{Va}，f），如果某屬性集合P∪{Q}能夠?qū)⒄撚騏劃分為m個(gè)等價(jià)類(lèi)，每個(gè)等價(jià)類(lèi)中元素的個(gè)數(shù)為p1，p2，…，pm，決策屬性集合P能夠?qū)⒄撚騏劃分為n個(gè)等價(jià)類(lèi)，每個(gè)等價(jià)類(lèi)中元素個(gè)數(shù)為d1，d2，…，dn，則屬性集合Q相對(duì)于屬性集合P的相對(duì)知識(shí)量重要度為：

上述定義表明SIG（U，Q，P）＞0，它表明屬性集合P中加入屬性Q后，知識(shí)量發(fā)生了變化.通過(guò)Q引起的相對(duì)知識(shí)量的大小來(lái)度量屬性Q相對(duì)于P的重要度.相對(duì)知識(shí)量越大，屬性Q也就越重要.本文以屬性的相對(duì)知識(shí)量重要度作為約簡(jiǎn)的啟發(fā)式信息，以減少搜索空間.

定理3[5]在信息表中，隨著屬性集合的單調(diào)增加，屬性集合的知識(shí)量單調(diào)遞增；當(dāng)屬性增加，出現(xiàn)等價(jià)類(lèi)的劃分與屬性增加前不一樣時(shí)，屬性集合的知識(shí)量嚴(yán)格單調(diào)遞增.

定理4在決策信息系統(tǒng)中，隨著條件屬性集合的單調(diào)增加，屬性集合的相對(duì)知識(shí)量單調(diào)遞增；當(dāng)屬性增加，出現(xiàn)等價(jià)類(lèi)的劃分與屬性增加前劃分不一致時(shí)，屬性集合的相對(duì)知識(shí)量嚴(yán)格單調(diào)遞增.

定理5設(shè)給定決策信息系統(tǒng)S＝（U，A，{Va}，f），P，Q?A，若U／Q?U／P，則W(U，Q）＞W(wǎng)(U，P）.

定理8[6]設(shè)給定決策信息系統(tǒng)S＝（U，A，{Va}，f），P是信息系統(tǒng)中所有條件屬性的集合，Q是信息系統(tǒng)中某些屬性的集合，q是Q中任意一個(gè)屬性，q∈Q，Q是P的一個(gè)約簡(jiǎn)，當(dāng)且僅當(dāng)：

3 相對(duì)知識(shí)量重要度的屬性約簡(jiǎn)算法

給定四元組信息系統(tǒng)S＝（U，A，{Va}，f），從A中找出最優(yōu)約簡(jiǎn)RED.根據(jù)本算法，先計(jì)算系統(tǒng)的知識(shí)量W0，對(duì)于所有的屬性，求出知識(shí)量最大的屬性，加入RED，計(jì)算RED的知識(shí)量并與決W0進(jìn)行比較.若相等，輸出RED；否則，分別計(jì)算其余每個(gè)屬性關(guān)于RED的相對(duì)知識(shí)量重要度，選出最重要的屬性加入RED，重新計(jì)算其知識(shí)量并與W0進(jìn)行比較，判斷其分類(lèi)能力之和是否與原來(lái)相同.若相同，即為所求子集；若不同，依照上述方法依次增加相對(duì)知識(shí)量重要度大的屬性，最后的到得就RED是要找到得屬性子集.

具體算法如下：

輸入：信息系統(tǒng)S＝（U，A，{Va}，f），

輸出：屬性子集RED

算法：

4 算法分析和實(shí)例

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

舉一個(gè)簡(jiǎn)單的實(shí)例來(lái)分析說(shuō)明算法，以及消除噪音的處理過(guò)程.取信息表[1]，表中有5個(gè)屬性，10個(gè)元素，見(jiàn)表1：

表1 數(shù)據(jù)表

所有的屬性集合將10個(gè)元素分成6個(gè)等價(jià)類(lèi)，{1，4}，{2，5}，{3}，{6，9}，{7，10}，{8}.等價(jià)類(lèi)的數(shù)目分別記為n1=2，n2=2，n3=1，n4=2，n5=2，n6=1，其知識(shí)量為

W（U，A）=41.

分別計(jì)算每個(gè)屬性的知識(shí)量，W(U，Make_model) =25，W(U，weight)=32，W(U，power)=17，W(U，comp)= 16，

W(U，mileage)=24.weight的知識(shí)量最大，將weight加入RED集中.

分別計(jì)算其余四個(gè)屬性相對(duì)于RED的相對(duì)知識(shí)量重要度，選擇相對(duì)知識(shí)量重要度最大的屬性加入到RED中.SIG(U，Make_model，RED)=9/32，

SIG(U，power，RED)=4/32，

SIG(U，comp，RED)=4/32，SIG(U，mileage，RED) =8/32，將Make_model加入RED，計(jì)算W(U，RED) =41，即RED={Make_model，weight}為所求的約簡(jiǎn).

如果在實(shí)際的采集數(shù)據(jù)中出現(xiàn)了誤差，得到的數(shù)據(jù)在元素2和comp數(shù)據(jù)出現(xiàn)了誤差得到值為light，此時(shí)的知識(shí)量計(jì)算變化為

W(U，mileage)=24，將weight加入RED，分別計(jì)算其余四個(gè)屬性相對(duì)于RED的相對(duì)知識(shí)量重要度，SIG(U，Make_model，RED)=9/32，

SIG(U，Power，RED)=4/32，

SIG(U，comp，RED)=5/32，

SIG(U，mileage，RED)=8/32分別計(jì)算其余三個(gè)屬性相對(duì)于RED={Make_model，weight}的相對(duì)知識(shí)量重要度，得到SIG(U，power，RED)=1/41，

SIG(U，comp，RED)=1/41，SIG(U，mileage，RED) =0，計(jì)算此時(shí)的約簡(jiǎn)為{Make_model，weight，Power}和 {Make_model，weight，comp}，由于power相對(duì)與{Make_model，weight}的相對(duì)知識(shí)量重要度為1/41，對(duì)屬性的分類(lèi)影響非常小，可以設(shè)定一個(gè)β閾值將其去掉，去掉power以后，對(duì)屬性約簡(jiǎn)的分類(lèi)能力影響變化非常?。煌?，可以將comp去掉.

一般由噪音引起的誤差分類(lèi)有兩種：第一種是采集到的數(shù)據(jù)與正確值偏差較小，即誤差較小，這時(shí)可以引入一個(gè)精度加以解決；第二種是采集到的數(shù)據(jù)與正確值偏差較遠(yuǎn)，誤差較大，這類(lèi)誤差通常取何種精度，都不能很好的處理，但這類(lèi)誤差可以由本文給出的方法解決.

5 結(jié)束語(yǔ)

本文在基于知識(shí)是區(qū)分事物能力的基礎(chǔ)上，利用屬性的相對(duì)知識(shí)量重要度為啟發(fā)式信息，提出了一種基于相對(duì)知識(shí)量重要度的屬性約簡(jiǎn)算法，并通過(guò)實(shí)例證明了該算法的有效性.

[1]徐燕，懷進(jìn)鵬，王兆其.基于區(qū)分能力大小的啟發(fā)式約簡(jiǎn)算法及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2003，26(1)：97-103.

[2]陳堂敏.基于區(qū)分能力大小的啟發(fā)式約簡(jiǎn)算法的研究[J].計(jì)算機(jī)學(xué)報(bào)，2006，29(3)：480-487.

[3]Starzyk J，Nelson D E，Sturtz K.Reducts.A mathematical foundation for improved reduct generation in information systems[J].Journal of Knowledge and Information Systems，2000，2(2)：131-146.

[4]張文修.粗糙集理論與方法[M].北京：科學(xué)出版社，2001.

[5]張海云，梁吉業(yè)，梁春華.一種基于知識(shí)量的約簡(jiǎn)算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2007，28(11)：1968-1971.

[6]苗奪謙，胡桂榮.知識(shí)約簡(jiǎn)的一種啟發(fā)式算法[J].計(jì)算機(jī)研究與發(fā)展，1999，36(6)：681-684.

A ttribute R eduction A lgorithm b ased on the R elative I mportance D egree

JIA Jun-f ang
(Departmentof Mathematic and Computer Science，S hanxi D atong U niversity，D atong S hanxi，037009)

Based on Xu Yan who can effectively dealwith noise data based on the ability to distinguish the size of the heuristic algorithm is introduced on the basis of relative attribute，which is an important concept，is an importantattribute relative heuristic information，this paper puts forward a kind of attribute reduction algorithm，through the examples show ing the effectiveness of the proposed algorithm.

relative knowledge quantity；importance degree；attribute reduction

TP311

A

〔編輯 高海〕

1674-0874(2010)01-0017-03

2009-10-13

賈俊芳(1976-)，女，山西左云人，在讀碩士，講師，研究方向：數(shù)據(jù)挖掘與人工智能.