基于相對知識量重要度的屬性約簡算法

賈俊芳

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

基于相對知識量重要度的屬性約簡算法

賈俊芳

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

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

相對知識量 重要度 屬性約簡

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

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

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

1 相關(guān)概念

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

定義2對于信息系統(tǒng)S＝（U，A，{Va}，f），B?A，X?U，稱＝{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對于給定的決策系統(tǒng)（U，C∪j5i0abt0b），條件屬性集合C的一個(gè)約簡是它的一個(gè)非空子集C′，滿足：

(1)IND（C，j5i0abt0b）＝IND（C′，j5i0abt0b）；

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

2 相對知識量重要度的定義

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

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

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

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à)類，每個(gè)等價(jià)類中元素個(gè)數(shù)為p1，p2，…，pm，則該屬性集合具有的知識量為

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

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

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

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

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

定理4在決策信息系統(tǒng)中，隨著條件屬性集合的單調(diào)增加，屬性集合的相對知識量單調(diào)遞增；當(dāng)屬性增加，出現(xiàn)等價(jià)類的劃分與屬性增加前劃分不一致時(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è)約簡，當(dāng)且僅當(dāng)：

3 相對知識量重要度的屬性約簡算法

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

具體算法如下：

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

輸出：屬性子集RED

算法：

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

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

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

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

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

W（U，A）=41.

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

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

分別計(jì)算其余四個(gè)屬性相對于RED的相對知識量重要度，選擇相對知識量重要度最大的屬性加入到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}為所求的約簡.

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

W(U，mileage)=24，將weight加入RED，分別計(jì)算其余四個(gè)屬性相對于RED的相對知識量重要度，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è)屬性相對于RED={Make_model，weight}的相對知識量重要度，得到SIG(U，power，RED)=1/41，

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

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

5 結(jié)束語

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

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

[2]陳堂敏.基于區(qū)分能力大小的啟發(fā)式約簡算法的研究[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è)，梁春華.一種基于知識量的約簡算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2007，28(11)：1968-1971.

[6]苗奪謙，胡桂榮.知識約簡的一種啟發(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ù)挖掘與人工智能.