基于粗糙理論的屬性約簡(jiǎn)在決策樹中的應(yīng)用

劉遠(yuǎn)峰 楊碧華

（1.暨南大學(xué)信息技術(shù)研究所，廣東廣州510075；2.暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣東廣州510632）

1.引言

粗糙集理論[1-4]是一種處理不確定和不精確性問(wèn)題的新的數(shù)學(xué)工具，它是波蘭華沙理工大學(xué)科學(xué)家帕克拉克（Paw lak）于1982年提出的，該理論具有很強(qiáng)的定性分析能力，能夠有效地表達(dá)不確定的或不精確的知識(shí)，善于從數(shù)據(jù)中獲取知識(shí)，并能利用不定性、不完整的經(jīng)驗(yàn)知識(shí)進(jìn)行推理等。粗糙集理論中對(duì)象的隸屬函數(shù)值依賴于知識(shí)庫(kù)，它可以從所需處理的數(shù)據(jù)中直接得到，無(wú)需外界的任何信息，所以用它來(lái)反映知識(shí)的模糊性是比較客觀的。

1.1 粗糙集理論的基本概念

定義1知識(shí)庫(kù)K=(U,R)，對(duì)于每個(gè)子集

XU?U和一個(gè)等價(jià)關(guān)系R，定義兩個(gè)子集：下近似集和上近似集

1.2 知識(shí)約簡(jiǎn)

粗糙集知識(shí)約簡(jiǎn)[5-7]，就是在保持知識(shí)庫(kù)的分類和決策能力不變的條件下，刪除其中不相關(guān)或不重要的知識(shí)。

定義2設(shè)P和Q是U中的等價(jià)關(guān)系族，R∈P，如果POSP(Q)=POS(P-{R})(Q)，則稱R為P中Q不必要的；否則稱R為P中Q必要的。如果P中每個(gè)R都是Q必要的，則稱P為Q獨(dú)立的；否則稱為依賴的。

定義3給定一個(gè)知識(shí)庫(kù)K=（U，S）和知識(shí)庫(kù)上的兩個(gè)等價(jià)關(guān)系簇P，Q屬于S，對(duì)任意的G屬于P，若G滿足以下兩條：

(1)G是Q獨(dú)立的，即G是P的Q獨(dú)立子集

(2)PosG(Q)=POSP(Q)

則稱G是P的一個(gè)Q約簡(jiǎn)。

2.知識(shí)約簡(jiǎn)的應(yīng)用

以下的例子是基于知識(shí)約簡(jiǎn)在病人是否得了流感的簡(jiǎn)單應(yīng)用。

條件屬性決策屬性病人頭痛肌肉痛體溫流感e1是是正常否e2是是高是e3是是很高是e4否是正常否e5否否高否e6否是很高是e7否否高是e8否是很高否

U={e1,e2,e3,e4,e5,e6,e7,e8},C={頭痛,肌肉痛,體溫},D={流感}，設(shè)C1=頭痛,C2=肌肉痛,C3=體溫。

3.問(wèn)題的提出

如果屬性約簡(jiǎn)的結(jié)果只有一個(gè)相對(duì)約簡(jiǎn)，例如上面的例子只有一個(gè)相對(duì)約簡(jiǎn)，那么決策表屬性的約簡(jiǎn)結(jié)果就是這個(gè)相對(duì)約簡(jiǎn)；但是如果約簡(jiǎn)的結(jié)果出現(xiàn)多個(gè)相對(duì)約簡(jiǎn)的情況，那么如何在這些約簡(jiǎn)中進(jìn)行選擇，就是一個(gè)問(wèn)題。因?yàn)楦鶕?jù)決策樹自身的特點(diǎn)，不同的屬性選擇結(jié)果會(huì)直接影響決策樹的構(gòu)建和最終的決策規(guī)則。而決策樹屬性的選取的傳統(tǒng)方法是主成分分析，那么由此方法得到啟發(fā)，從而作了這樣的設(shè)想，對(duì)每個(gè)屬性約簡(jiǎn)所包含的每個(gè)屬性進(jìn)行逐一的重要屬性計(jì)算，從中選取屬性綜合重要性大的那個(gè)約簡(jiǎn)作為決策樹最后的條件屬性。而屬性重要性的基本思想是，在決策表中,不同的屬性可能具有不同的重要性,為了找出某些屬性(或?qū)傩约?的重要性,可以從表中去掉一些屬性,再來(lái)考察沒(méi)有該屬性后分類會(huì)怎樣變化。若去掉該屬性相應(yīng)分類變化較大,則說(shuō)明該屬性的強(qiáng)度大,即重要性高;反之,說(shuō)明該屬性的強(qiáng)度小,即重要性低。不過(guò)這種設(shè)想是否可行仍還在研究中。

計(jì)算每個(gè)約簡(jiǎn)中屬性子集的重要性，屬性子集C'?C關(guān)于D的重要性如下：

4.結(jié)論

本文是基于粗糙理論的屬性約簡(jiǎn)在決策樹中的應(yīng)用，從而能去掉決策屬性中一些冗余的屬性，得到最高的分類準(zhǔn)確率，而不依賴人的主觀知識(shí)和經(jīng)驗(yàn)，使決策樹的構(gòu)架更準(zhǔn)確；同時(shí)提出了如何選取相對(duì)約簡(jiǎn)的問(wèn)題，該問(wèn)題仍在探討中。

[1] Paw lak Z.A treatiseon rough sets.In:Peters JF,Skowron A,des.Proc.of the Trans.on Rough Sets IV.LNCS 3700,Belin,Heiderberg:Springer-Verlag,2005.1-17.

[2] 陳波,周明天.粒度粗糙理論研究[J].軟件學(xué)報(bào),2008,03:565-583.

[3] Chen B,Zhou MT.A lesniewski mereological analysis on roughness theory.Computer Science,2006,33(7):171-175.

[4] Radzikowska AM,Kerre EE.A comparative study of fuzzy Sets and Systems,2002,126(2):137-155.

[5] 苗奪謙,胡桂榮.知識(shí)簡(jiǎn)約的一種啟發(fā)式算法[J].計(jì)算機(jī)研究與發(fā)展,1999,06:42-45.

[6] Wei-Hua Gui,Chun-Hua Yang,Jing Teng.Intelligent fault diagnosis in lead-zinc smelting process[J].International of Automation and Computing,2007,4(2).

[7] Daniel Merkle,Martin Midderndorf.Ant Colony Optimization with Global Pheromone Evaluation for Scheduling a Single Machine[J].Applied Intelligence,2003,18(1).