基于貝葉斯理論的粗糙集規(guī)則提取

丁卓平,丁加明

(1.湖南理工學(xué)院 計(jì)算機(jī)學(xué)院,湖南 岳陽 414006;2.湖南省交通廳 交通建設(shè)造價(jià)管理站,長沙 410011；3.清華大學(xué) 土木水利學(xué)院,北京 100084)

基于貝葉斯理論的粗糙集規(guī)則提取

丁卓平1,丁加明2,3

(1.湖南理工學(xué)院 計(jì)算機(jī)學(xué)院,湖南 岳陽 414006;2.湖南省交通廳 交通建設(shè)造價(jià)管理站,長沙 410011；3.清華大學(xué) 土木水利學(xué)院,北京 100084)

提出采用貝葉斯理論提取信息不相容和不完備的試驗(yàn)數(shù)據(jù)規(guī)則.首先以試驗(yàn)數(shù)據(jù)匯總表的確定性(可信度)為先驗(yàn)概率、試驗(yàn)數(shù)據(jù)的樣本數(shù)(支持度)為后驗(yàn)概率,然后計(jì)算組合規(guī)則的條件概率,提取條件概率大于某一閾值的規(guī)則,最后通過邏輯合取與析取歸并提煉規(guī)則.實(shí)例計(jì)算和應(yīng)用分析表明,采用貝葉斯理論提取規(guī)則的算法概念明確,計(jì)算過程簡單,便于編制計(jì)算機(jī)程序,最大限度避免了規(guī)則提取中的知識失真和規(guī)則丟失.

相容;完備;貝葉斯;規(guī)則提取

引言

在大量的原始數(shù)據(jù)信息中,隱藏著許多包含知識、規(guī)律等方面的有用信息,從這些原始數(shù)據(jù)信息中發(fā)現(xiàn)有用的規(guī)律信息叫做知識獲取.通過對這些數(shù)據(jù)進(jìn)行分析、分類、推理,從中發(fā)現(xiàn)隱含的知識、揭示潛在的規(guī)律,是知識獲取的一種重要研究方法[1].而粗糙集理論可以通過借助信息表對數(shù)據(jù)進(jìn)行分類、約簡、知識獲取直至形成規(guī)則.因此,規(guī)則提取是粗糙集理論的一個(gè)重要應(yīng)用[2].

但在實(shí)踐工作中,由于研究目的不同,同類試驗(yàn)的內(nèi)容和指標(biāo)存在著一定差異.如果不能將已有試驗(yàn)數(shù)據(jù)最大限度地加以利用,所有數(shù)據(jù)都要重新通過試驗(yàn)獲得必將會造成極大的浪費(fèi).而將這些試驗(yàn)數(shù)據(jù)匯總到一起時(shí),又會出現(xiàn)一些試驗(yàn)指標(biāo)的缺項(xiàng)等問題.另外,由于各指標(biāo)離散區(qū)間的選擇還可能導(dǎo)致一些試驗(yàn)數(shù)據(jù)出現(xiàn)互相矛盾的情況.因此在利用粗糙集進(jìn)行規(guī)則提取時(shí)會存在數(shù)據(jù)信息的不相容或不完備,對規(guī)則提取帶來困難.針對傳統(tǒng)規(guī)則提取的方法在處理不相容或不完備信息時(shí)容易導(dǎo)致的知識失真等不足,本文指出,采用貝葉斯理論可以較好地解決這一問題.

1 數(shù)據(jù)信息不相容和不完備時(shí)的規(guī)則提取

1.1 數(shù)據(jù)不相容時(shí)的規(guī)則提取

如果系統(tǒng)中有一個(gè)規(guī)則的可信度 0 ＜μ(Xi,Yj)＜1時(shí),說明此規(guī)則是不確定的,知識表達(dá)系統(tǒng)是不相容系統(tǒng).如果按試驗(yàn)指標(biāo)等價(jià)類 des(Xi)有兩個(gè)分類des(Yj)(j= 1,2),則此規(guī)則的可信度為0.5.但如果規(guī)則des(Xi)→des(Y1)包含有 99個(gè)試樣,而des (Xi)→des(Y2)只有一個(gè)試樣時(shí),規(guī)則 des(Xi)→des(Y1)也不能被歸入下近似集中,從而失去形成確定規(guī)則的機(jī)會.而那個(gè)“與眾不同”的試樣很可能是個(gè)特例,或許是由操作不當(dāng)引起的.

對于不相容系統(tǒng)的規(guī)則提取,常用的辦法有將不相容的規(guī)則刪除,只計(jì)算相容的規(guī)則.顯然,這樣做會使原始數(shù)據(jù)和要提取的評判規(guī)則失真,使規(guī)則提取喪失意義.有的算法是將包含試樣數(shù)小的規(guī)則去掉,減少噪聲參數(shù)對規(guī)則提取的影響.但有的規(guī)則樣本數(shù)雖少但可信度卻很高,而且樣本數(shù)和試驗(yàn)次數(shù)有關(guān).還有的算法是計(jì)算每一個(gè)規(guī)則的可信度和支持度,設(shè)定兩個(gè)閾值[3].當(dāng)這個(gè)規(guī)則的可信度和支持度均大于其對應(yīng)的閾值時(shí),規(guī)則成立.這對可信度大而支持度小或者可信度小而支持度大的規(guī)則而言,有意義規(guī)則的喪失是不可避免的.因此這種雙閾值的規(guī)則提取也是不合適的.

1.2 信息不完備時(shí)的規(guī)則提取

如果至少有一個(gè)試驗(yàn)指標(biāo)a∈AT使得Va含有空值,則稱試驗(yàn)匯總表(DT)為一個(gè)不完備信息系統(tǒng).不完備信息系統(tǒng)的通常處理方法是采用某種手段使信息系統(tǒng)完備化[4].常見的數(shù)據(jù)完備化的方法有刪除法和補(bǔ)齊法.刪除法就是忽略或刪除具有不完備性的元組,但當(dāng)信息數(shù)據(jù)有限、不完備信息對象數(shù)量較多時(shí),就不能采用這種方法了；補(bǔ)齊法就是根據(jù)粗糙集中不可分辨關(guān)系對不完備信息系統(tǒng)的補(bǔ)齊,但空缺的屬性到底如何取值難以確定.因此,這兩種方法都可能導(dǎo)致正確規(guī)則無法提取,知識獲取存在不同程度失真的情況.

2 采用貝葉斯理論提取規(guī)則的算法

用貝葉斯條件概率[5]的計(jì)算可以較好地解決數(shù)據(jù)信息不相容和不完備.把充分地表達(dá)了分類系統(tǒng)本身固有信息的確定性(可信度)看作先驗(yàn)概率P(Nj),把試驗(yàn)過程中得到的樣本數(shù)(支持度)當(dāng)作反映的P(Nj)下的后驗(yàn)概率P(Z|Nj).應(yīng)用貝葉斯公式計(jì)算條件概率

然后再通過單閾值篩選確定需要保留的規(guī)則.這種既考慮了決策表信息,又考慮了試驗(yàn)樣本個(gè)數(shù)的計(jì)算可以有效地解決信息不相容引起的規(guī)則沖突和規(guī)則丟失.對于不完備的信息,可以將該空缺屬性所有可能的值進(jìn)行補(bǔ)齊,補(bǔ)齊后每個(gè)屬性的樣本數(shù)仍對應(yīng)為該信息的樣本數(shù).由于規(guī)則組合中涉及該空缺屬性時(shí)的每條規(guī)則只可能有一個(gè)取值,所以該信息不會重復(fù)計(jì)算.

具體算法如下：

1)約簡.互相關(guān)聯(lián)的屬性被約簡后,具有相同樣本值的樣本數(shù)應(yīng)累加到一起；

2)列出所有屬性組合,按每個(gè)組合計(jì)算規(guī)則；

3)計(jì)算每條規(guī)則的可信度、支持度和條件概率；

4)設(shè)定某一閾值,提取大于這一閾值的規(guī)則；

5)通過邏輯合取與析取提煉已提取的規(guī)則.

3 計(jì)算實(shí)例

假設(shè)在200組試驗(yàn)中,有4個(gè)樣本值,3個(gè)屬性,1個(gè)結(jié)果,每個(gè)屬性和結(jié)果都對應(yīng)“0”、“1”兩個(gè)值,并且不同的樣本值對應(yīng)著不同的樣本數(shù).如表1所示,可知表中A1與A2不相容,樣本值A(chǔ)4的屬性f1缺省.由于樣本值A(chǔ)4的屬性f1缺省,可以分別賦予A4的屬性f1“0”、“1”值參與計(jì)算,但A4的屬性f1每次取定 “0”或者“1”時(shí),其對應(yīng)的樣本個(gè)數(shù)仍為50.如表1中第5和第6行所示.

表1 試驗(yàn)指標(biāo)及結(jié)果離散化數(shù)值

限于篇幅,表2中不考慮各屬性的組合,僅以單個(gè)屬性分別取以“0”、“1”時(shí)提取規(guī)則.由于規(guī)則提取的計(jì)算思路清晰,過程明確,對每一條規(guī)則的條件屬性提取計(jì)算都是遍歷的,即使規(guī)則提取計(jì)算量隨屬性個(gè)數(shù)和取值數(shù)的增加而呈指數(shù)增長,也容易通過計(jì)算機(jī)程序?qū)崿F(xiàn).文獻(xiàn)[6,7]表明,采用本辦法分別計(jì)算膨脹土試驗(yàn)數(shù)據(jù)不相容和不完備時(shí)的分類規(guī)則與工程實(shí)踐較為吻合.

表2 規(guī)則提取計(jì)算

4 結(jié)語

由以上討論,可以得到下面的兩個(gè)結(jié)論:

1)條件概率的計(jì)算可以有效地解決試驗(yàn)數(shù)據(jù)匯總表中的信息不相容和不完備的問題.

2)采用貝葉斯理論提取規(guī)則的算法概念明確,計(jì)算過程簡單,便于編制計(jì)算機(jī)程序,可最大限度避免信息不相容或不完備系統(tǒng)中規(guī)則提取時(shí)容易發(fā)生的知識失真和規(guī)則丟失.

[1]張文修,吳偉志,梁吉業(yè),等.粗糙集理論與方法[M].北京：科學(xué)出版社,2001

[2]Pawlak Z.Decisions rules and flow networks[J].European Journal of Operational Research,2004,154 (1):184～190

[3]馬 力,焦李成.一種基于粗集理論的知識發(fā)現(xiàn)系統(tǒng)的研究與設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī),2003,3:8～12

[4]曾黃麟.智能計(jì)算[M].重慶：重慶大學(xué)出版社,2004

[5]劉柏剛,丁加明.貝葉斯決策在確定復(fù)合標(biāo)底報(bào)價(jià)中的應(yīng)用 [J].鐵路工程造價(jià)管理,2002,5:5～7

[6]丁加明,王永和,丁力行.基于粗集不相容系統(tǒng)決策挖掘的膨脹土分類規(guī)則提取[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,37(2):396～400

[7]丁加明,王永和,丁力行.基于粗糙集信息不完備系統(tǒng)的膨脹土分類規(guī)則提取[J].鐵道科學(xué)與工程學(xué)報(bào)(自然科學(xué)版),2005,2(4):1～5

Rough Sets Rule Generating Based on Bayesian Theory

DING Zhuo-ping1,DING Jia-ming2,3
(1.College of Computer Science,Hunan Institute of Science and Technology,Yueyang 414006,China 2.Traffic Construction Cost Management Station of Hunan Province,Changsha 410011,China；3.School of Civil Engineering,Tsinghua University,Beijing 100084,China)

The generating rule method is presented for incompatible and incomplete information of test data based on Bayesian theory.Firstly,the rule’s conditional probability is calculated when the certainty (reliability)of the test data is the prior probability and the samples (supportability)is posterior probability.Then,those rules whose conditional probability is bigger than a given threshold value should be preserved.Lastly,the rule is generated by logic conjunction and disjunction of all the preserved rules.The example and application analysis indicate that the algorithm is clear,the calculating process is simple and it can be easily applied to computer programs,moreover,this method can avoid the knowledge distortion and the rule losing to the maximum for generating rule.

compatible;complete;Bayesian;generating rule

TP301.6

A

1672-5298(2011)01-0031-03

2010-11-10

國家自然科學(xué)基金資助項(xiàng)目(50808179)

丁卓平(1961? ),男,湖南岳陽人,湖南理工學(xué)院計(jì)算機(jī)學(xué)院副教授.主要研究方向:非經(jīng)典數(shù)學(xué)方法和計(jì)算機(jī)編程在工程領(lǐng)域中的應(yīng)用