基于贝叶斯理论的粗糙集规则提取

丁卓平,丁加明

(1.湖南理工学院 计算机学院,湖南 岳阳 414006;2.湖南省交通厅 交通建设造价管理站,长沙 410011；3.清华大学 土木水利学院,北京 100084)

基于贝叶斯理论的粗糙集规则提取

丁卓平1,丁加明2,3

(1.湖南理工学院 计算机学院,湖南 岳阳 414006;2.湖南省交通厅 交通建设造价管理站,长沙 410011；3.清华大学 土木水利学院,北京 100084)

提出采用贝叶斯理论提取信息不相容和不完备的试验数据规则.首先以试验数据汇总表的确定性(可信度)为先验概率、试验数据的样本数(支持度)为后验概率,然后计算组合规则的条件概率,提取条件概率大于某一阈值的规则,最后通过逻辑合取与析取归并提炼规则.实例计算和应用分析表明,采用贝叶斯理论提取规则的算法概念明确,计算过程简单,便于编制计算机程序,最大限度避免了规则提取中的知识失真和规则丢失.

相容;完备;贝叶斯;规则提取

引言

在大量的原始数据信息中,隐藏着许多包含知识、规律等方面的有用信息,从这些原始数据信息中发现有用的规律信息叫做知识获取.通过对这些数据进行分析、分类、推理,从中发现隐含的知识、揭示潜在的规律,是知识获取的一种重要研究方法[1].而粗糙集理论可以通过借助信息表对数据进行分类、约简、知识获取直至形成规则.因此,规则提取是粗糙集理论的一个重要应用[2].

但在实践工作中,由于研究目的不同,同类试验的内容和指标存在着一定差异.如果不能将已有试验数据最大限度地加以利用,所有数据都要重新通过试验获得必将会造成极大的浪费.而将这些试验数据汇总到一起时,又会出现一些试验指标的缺项等问题.另外,由于各指标离散区间的选择还可能导致一些试验数据出现互相矛盾的情况.因此在利用粗糙集进行规则提取时会存在数据信息的不相容或不完备,对规则提取带来困难.针对传统规则提取的方法在处理不相容或不完备信息时容易导致的知识失真等不足,本文指出,采用贝叶斯理论可以较好地解决这一问题.

1 数据信息不相容和不完备时的规则提取

1.1 数据不相容时的规则提取

如果系统中有一个规则的可信度 0 ＜μ(Xi,Yj)＜1时,说明此规则是不确定的,知识表达系统是不相容系统.如果按试验指标等价类 des(Xi)有两个分类des(Yj)(j= 1,2),则此规则的可信度为0.5.但如果规则des(Xi)→des(Y1)包含有 99个试样,而des (Xi)→des(Y2)只有一个试样时,规则 des(Xi)→des(Y1)也不能被归入下近似集中,从而失去形成确定规则的机会.而那个“与众不同”的试样很可能是个特例,或许是由操作不当引起的.

对于不相容系统的规则提取,常用的办法有将不相容的规则删除,只计算相容的规则.显然,这样做会使原始数据和要提取的评判规则失真,使规则提取丧失意义.有的算法是将包含试样数小的规则去掉,减少噪声参数对规则提取的影响.但有的规则样本数虽少但可信度却很高,而且样本数和试验次数有关.还有的算法是计算每一个规则的可信度和支持度,设定两个阈值[3].当这个规则的可信度和支持度均大于其对应的阈值时,规则成立.这对可信度大而支持度小或者可信度小而支持度大的规则而言,有意义规则的丧失是不可避免的.因此这种双阈值的规则提取也是不合适的.

1.2 信息不完备时的规则提取

如果至少有一个试验指标a∈AT使得Va含有空值,则称试验汇总表(DT)为一个不完备信息系统.不完备信息系统的通常处理方法是采用某种手段使信息系统完备化[4].常见的数据完备化的方法有删除法和补齐法.删除法就是忽略或删除具有不完备性的元组,但当信息数据有限、不完备信息对象数量较多时,就不能采用这种方法了；补齐法就是根据粗糙集中不可分辨关系对不完备信息系统的补齐,但空缺的属性到底如何取值难以确定.因此,这两种方法都可能导致正确规则无法提取,知识获取存在不同程度失真的情况.

2 采用贝叶斯理论提取规则的算法

用贝叶斯条件概率[5]的计算可以较好地解决数据信息不相容和不完备.把充分地表达了分类系统本身固有信息的确定性(可信度)看作先验概率P(Nj),把试验过程中得到的样本数(支持度)当作反映的P(Nj)下的后验概率P(Z|Nj).应用贝叶斯公式计算条件概率

然后再通过单阈值筛选确定需要保留的规则.这种既考虑了决策表信息,又考虑了试验样本个数的计算可以有效地解决信息不相容引起的规则冲突和规则丢失.对于不完备的信息,可以将该空缺属性所有可能的值进行补齐,补齐后每个属性的样本数仍对应为该信息的样本数.由于规则组合中涉及该空缺属性时的每条规则只可能有一个取值,所以该信息不会重复计算.

具体算法如下：

1)约简.互相关联的属性被约简后,具有相同样本值的样本数应累加到一起；

2)列出所有属性组合,按每个组合计算规则；

3)计算每条规则的可信度、支持度和条件概率；

4)设定某一阈值,提取大于这一阈值的规则；

5)通过逻辑合取与析取提炼已提取的规则.

3 计算实例

假设在200组试验中,有4个样本值,3个属性,1个结果,每个属性和结果都对应“0”、“1”两个值,并且不同的样本值对应着不同的样本数.如表1所示,可知表中A1与A2不相容,样本值A4的属性f1缺省.由于样本值A4的属性f1缺省,可以分别赋予A4的属性f1“0”、“1”值参与计算,但A4的属性f1每次取定 “0”或者“1”时,其对应的样本个数仍为50.如表1中第5和第6行所示.

表1 试验指标及结果离散化数值

限于篇幅,表2中不考虑各属性的组合,仅以单个属性分别取以“0”、“1”时提取规则.由于规则提取的计算思路清晰,过程明确,对每一条规则的条件属性提取计算都是遍历的,即使规则提取计算量随属性个数和取值数的增加而呈指数增长,也容易通过计算机程序实现.文献[6,7]表明,采用本办法分别计算膨胀土试验数据不相容和不完备时的分类规则与工程实践较为吻合.

表2 规则提取计算

4 结语

由以上讨论,可以得到下面的两个结论:

1)条件概率的计算可以有效地解决试验数据汇总表中的信息不相容和不完备的问题.

2)采用贝叶斯理论提取规则的算法概念明确,计算过程简单,便于编制计算机程序,可最大限度避免信息不相容或不完备系统中规则提取时容易发生的知识失真和规则丢失.

[1]张文修,吴伟志,梁吉业,等.粗糙集理论与方法[M].北京：科学出版社,2001

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

[3]马 力,焦李成.一种基于粗集理论的知识发现系统的研究与设计[J].微电子学与计算机,2003,3:8～12

[4]曾黄麟.智能计算[M].重庆：重庆大学出版社,2004

[5]刘柏刚,丁加明.贝叶斯决策在确定复合标底报价中的应用 [J].铁路工程造价管理,2002,5:5～7

[6]丁加明,王永和,丁力行.基于粗集不相容系统决策挖掘的膨胀土分类规则提取[J].中南大学学报(自然科学版),2006,37(2):396～400

[7]丁加明,王永和,丁力行.基于粗糙集信息不完备系统的膨胀土分类规则提取[J].铁道科学与工程学报(自然科学版),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

国家自然科学基金资助项目(50808179)

丁卓平(1961− ),男,湖南岳阳人,湖南理工学院计算机学院副教授.主要研究方向:非经典数学方法和计算机编程在工程领域中的应用