一种新的决策表约简算法.pdfVIP

计算机科学2004Vo1.31N0.10A 一种新的决策表约简算法 ANewReductionAlgorithmofDecisionTable 李海博 、林 和 张 娟 刘永兵 李永礼 (兰州大学信息科学与工程学院计算机系 兰州730000) AbstractThispaperismainlyaboutareductionalgorithmofdecisiontablebasedongranulartheory.Thereduc- tionalgorithmneedsnotbedividedintotwosteps(attributereductionandvaluereduction).Itcouldnotalwaysget thesimplestrules,butthealgorithmwillbeefficient. KeywordsGranularcomputing,Roughsets,Decisiontable,Knowledgereduction 粒度计算是基于对论域上的元素分类的思想提 [x]。为包含x的ind(C)等价类)。 出来的，已经在知识发现领域有了广泛的应用，并且 2.3 决策表约简 引起了人们广泛的关注。 给定决策表信息系统S=(U,CU(d},D)，设X cu是一组对象，BCC是一组属性。决策属性D相 1 引言 对于B的正域是:POSB(D)=U(B_(X)IXEU/ind 当人们处理问题或者做出一个决定时往往需要 (D)}。 完整的、确定的信息。但是由于种种原因，得到的信 决策属性D相对于B的正域代表了BCC对决 息往往不完整、不确定甚至是模糊的。这时候将很难 策属性的近似质量。约简是在保持近似质量不变的 清楚地把元素与元素区分开，因此只能在某个粒度 情况下的最小属性子集。通常一个信息系统可能有 上解决问题。有些时候，能够得到足够的信息，但是 很多种约简。决策表的约简一般可分三步: 由于信息量过于庞大而难于处理，或者处理的问题 (1)条件属性约简 并不需要很高精确度。这类问题同样需要在某个粒 (2)属性值的约简 度上解决。因此有一些学者认为;信息粒度对人们认 (3)决策算法最小化 识问题、解决问题是十分基本的，因此它对于设计和 本文以下只讨论一致决策表的约简。 构建智能信息系统的影响很大。 3本文算法的基本思想与步骤 2粗糙集的基本概念 3.1本文算法的基本思想 2.1 不可分辨关系 总的说来，先确定一个对论域划分的粒度，若粒 可以用一个具有非空论域U和非空属性集A 度不够 “细”，再在粒度需要更细的部分采用更细的 的知识表示系统S=(U,A)描述不可分辨关系，把 粒度，在粒度已经足够的部分保持粒度不变。 任意的属性aEA映射到论域U上，用V。表示属性 决策表条件属性的属性核COREC=C，对应于 a所对应的属性值的集合，按照属性集C=A可以 一个等价关系簇，这个等价关系簇可以看作对论域 对论域进行分类，使得各类中的元素按照C是不可 划分的最“粗”的粒度，但是这个粒度是不是足够呢? 分辨的。 在一致决策表中就要判断POSCORE(D)是否等于U, 令函数Inf,(x)=((a,a(x))卜EC,a(x)EV,}, 如果相等，则说明这个属性核对应的划分己经 对x,YEU，当Inf,(x)二Inf,(y)时，称x,y是C一不