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

賈俊芳

(山西大同大學數學與計算機科學學院，山西大同 037009）

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

賈俊芳

(山西大同大學數學與計算機科學學院，山西大同 037009）

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

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

Pawlak等人提出的粗糙集理論，作為一種處理模糊概念和不確定性知識的數據推理方法，已在實際生活中得到了廣泛的應用.涉及了人工智能，模式識別，機器學習，專家系統等有關領域.

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

文中從知識區分事物的能力出發，在文獻[1]提出的知識量定義的基礎上，給出了屬性相對知識重要度的度量方法.提出了一種新的屬性約簡算法，并通過實例驗證了該算法的有效性.

1 相關概念

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

定義2對于信息系統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負域，bnB（X）＝－成為X的B邊界域.

定義3對于給定的決策系統（U，C∪g0gggggg），條件屬性集合C的一個約簡是它的一個非空子集C′，滿足：

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

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

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

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

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

定義1 給定信息系統S＝（U，A，{Va}，f），屬性集合P能夠將論域U劃分為m個等價類，每個等價類中元素的個數為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個等價類，每個等價類中元素個數為p1，p2，…，pm，則該屬性集合具有的知識量為

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

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

定義3給定四元組決策信息系統S＝（U，A，{Va}，f），如果某屬性集合P∪{Q}能夠將論域U劃分為m個等價類，每個等價類中元素的個數為p1，p2，…，pm，決策屬性集合P能夠將論域U劃分為n個等價類，每個等價類中元素個數為d1，d2，…，dn，則屬性集合Q相對于屬性集合P的相對知識量重要度為：

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

定理3[5]在信息表中，隨著屬性集合的單調增加，屬性集合的知識量單調遞增；當屬性增加，出現等價類的劃分與屬性增加前不一樣時，屬性集合的知識量嚴格單調遞增.

定理4在決策信息系統中，隨著條件屬性集合的單調增加，屬性集合的相對知識量單調遞增；當屬性增加，出現等價類的劃分與屬性增加前劃分不一致時，屬性集合的相對知識量嚴格單調遞增.

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

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

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

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

具體算法如下：

輸入：信息系統S＝（U，A，{Va}，f），

輸出：屬性子集RED

算法：

4 算法分析和實例

下面分析上述算法的時間復雜度

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

表1 數據表

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

W（U，A）=41.

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

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

分別計算其余四個屬性相對于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，計算W(U，RED) =41，即RED={Make_model，weight}為所求的約簡.

如果在實際的采集數據中出現了誤差，得到的數據在元素2和comp數據出現了誤差得到值為light，此時的知識量計算變化為

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

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

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

5 結束語

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

[1]徐燕，懷進鵬，王兆其.基于區分能力大小的啟發式約簡算法及其應用[J].計算機學報，2003，26(1)：97-103.

[2]陳堂敏.基于區分能力大小的啟發式約簡算法的研究[J].計算機學報，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].北京：科學出版社，2001.

[5]張海云，梁吉業，梁春華.一種基于知識量的約簡算法[J].小型微型計算機系統，2007，28(11)：1968-1971.

[6]苗奪謙，胡桂榮.知識約簡的一種啟發式算法[J].計算機研究與發展，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-)，女，山西左云人，在讀碩士，講師，研究方向：數據挖掘與人工智能.