决策表的一种知识约简与规则获取方法

rough set 的作用rough set（粗糙集）是一种数据分析和知识发现的方法，它能够从不完全和不确定的数据中提取出有用的信息，用于决策支持和预测分析。

它的作用主要体现在以下几个方面：1. 数据约简与特征选择rough set可以通过数据约简的方法，从大量的数据中提取出最为关键和有用的特征。

在实际应用中，数据往往存在大量的冗余和不必要的特征，这些特征会影响到数据分析和模型建立的效果。

通过rough set的特征选择方法，可以减少数据的维度，降低计算复杂度，提高模型的精度和泛化能力。

2. 决策规则的挖掘rough set可以根据数据的属性和决策类别，通过构建决策表和决策规则，挖掘出数据中隐含的规律和知识。

决策规则是一种以IF-THEN形式表示的知识表达方式，可以帮助人们理解和解释数据中的规律，并用于决策支持和预测分析。

通过rough set的决策规则挖掘方法，可以从大规模的数据中抽取出有用的知识，提高决策的准确性和效率。

3. 数据分类与预测rough set可以根据已有的数据样本，通过构建决策模型和分类器，对未知样本进行分类和预测。

在实际应用中，往往需要根据已有的数据样本，对新的数据进行分类和预测。

通过rough set的数据分类和预测方法，可以根据数据的属性和决策类别，构建分类模型，并将其应用于未知数据的分类和预测，从而实现对未知问题的解决。

4. 知识发现与智能决策rough set可以帮助人们从大量的数据中发现隐藏的知识和规律，提供决策支持和智能决策的能力。

在现代社会，数据量呈指数级增长，如何从海量的数据中发现有用的知识和规律，成为了一个重要的挑战。

通过rough set的知识发现方法，可以从复杂的数据中提取出有用的信息和知识，帮助人们做出更加准确和智能的决策。

rough set作为一种数据分析和知识发现的方法，具有数据约简与特征选择、决策规则的挖掘、数据分类与预测以及知识发现与智能决策等作用。

第21卷第8期V ol.21N o.8　控　制　与　决　策Contr ol andDecision 　2006年8月 Aug.2006 收稿日期:2005-06-06;修回日期:2005-08-15. 基金项目:国家自然科学基金(天元)项目(A 0324638). 作者简介:李凡(1972—),男,江苏南通人,博士生,从事Ro ug h 集理论、智能信息处理等研究;杨国纬(1939—),男,重庆人,教授,博士生导师,从事人工智能、计算机网络等研究. 文章编号:1001-0920(2006)08-0857-06不一致决策表的知识约简方法研究李　凡,刘启和,叶　茂,杨国纬(电子科技大学计算机科学与工程学院,成都610054)摘　要:目前计算不一致决策表的分布约简、最大分布约简和分配约简的方法均基于可辨识属性矩阵,在大数据集下耗时较多.为此,提出转化算法,将计算原不一致决策表的上述3种约简转化为计算3种一致决策表的P awlak 约简.通过应用针对后者的高效启发式算法,有效地减少了计算时间.此外,引入 -约简的概念,通过调节 的值,能得到一族反映决策矢量不同水平相似程度的知识约简.该方法降低了分布约简对决策表区分能力的过高要求,较上述3种约简更为灵活.关键词:Ro ugh 集;知识约简;不一致决策表;Fuzzy 相似关系中图分类号:T P18 文献标识码:AApproaches to Knowledge Reductions in Inconsistent Decision TablesLI Fan ,L I U Qi -he ,YE M ao ,YA N G Guo -w ei(College o f Co mput er Science a nd Eng ineer ing,U niver sity of Elect ro nic Science and T echnolog y ,Cheng du 610054,China.Cor respondent :L I F an,E-mail:lifan987@to )Abstract :Ex isting ,appr oaches t o kno wledge reduct ions for t he distr ibut ion reduct ,the m aximum distr ibutio n reduct and the assignment r educt o f an inconsistent decision table ar e based o n discer nibility matrix es,w hich are ver y time-consuming when the dataset is lar ge.T o ov ercome this sho rt co ming ,an appro ach is pro po sed to conv ert the co mput atio n fo r t he t hree ty pes of r educts of the or ig inal inco nsistent decision table int o the computatio n fo r the Paw lak r educt of t hr ee types of derived co nsist ent decisio n t ables .T hus ,efficient heur istic kno wledg e reductio n alg or ithms fo r t he P aw lak reduct can be used t o reduce computational costs.F urther mor e,the -r educt,a new ty pe of r educts,is intr o duced.By tuning the par ameter ,a set o f reducts can be o bt ained,each o f w hich r eflects the differ ent level of similar it ies of decisio n v ector s .T he -r educt eliminat es the harsh r equir ement s of the distr ibutio nreduct a nd is mo re flexible than the thr ee types of r educts .Key words :R ough sets;Know ledg e reductio n;Inconsistent decision table ;Fuzzy similar ity relation1　引 言 知识约简(属性约简)是Rough 集理论的核心问题之一[1,2].所谓知识约简,就是在信息系统的分类或决策能力保持不变的前提下,删除其中不相关或不重要的属性.通过知识约简,可以在不丢失基本信息的前提下得到更简明的分类或决策规则.目前,学者们已提出了一些有效的知识约简算法[1～4],但这些研究大多集中于讨论决策表的Paw lak 约简,即决策表的正区域在约简前后保持不变.然而,为了从复杂的不一致决策表中获取符合实际需要的不确定性命题规则,必须从更多侧面研究不一致决策表的知识约简问题.为此,文献[5]讨论了不一致决策表5种形式的知识约简,指出只有分布约简(DR )和分配约简(AR )是基本约简形式,其他几种约简都与二者之一等价.文献[6,7]在此基础上提出另一种知识约简的概念,即最大分布约简(M DR ),并讨论了DR,M DR和AR之间的关系,给出了这3种知识约简相应的可辨识属性矩阵,从而得到了计算这3种知识约简的方法.本文在以上研究的基础上,继续讨论不一致决策表的知识约简问题.首先,基于可辨识属性矩阵的方法虽然可以求出所有的约简,但在决策表较大的情况下将消耗大量计算时间,因而对大数据集或计算时间有严格要求的应用而言,这种方法并不适合.为此,本文提出了针对DR,M DR和AR的转化算法,将计算原不一致决策表的这3种约简转化为计算3种一致决策表的Paw lak约简(PR),通过应用针对PR的高效启发式知识约简算法[3,4],可以有效减少计算时间的消耗.其次,DR对决策表的区分能力有严格的要求,因而对噪声数据较为敏感.MDR和AR虽然从不同侧面降低了对决策表区分能力的要求,但与DR 一样,仍然属于确定性约简,对于特定的应用,往往缺乏必要的灵活性.在以往的研究中,许多学者从不同侧面提出了利用参数来调节约简精度的思路[8,9].通过调节参数,引入一定程度的分类误差,即可按实际需要将信息系统的辨识能力控制在合适的水平.实践证明,这种处理方式能有效提高新出现个体的分类准确度.本文采用了这一思想,提出了一种新的不一致决策表知识约简的概念,即 -约简.通过定义个体间决策近似度,得到Fuzzy相似关系,并进一步转化为Fuzzy等价关系.通过计算其 截关系所对应的 -决策表的PR,即得到 -约简.通过调节参数 的值,能够得到一族平滑过渡的知识约简,其中的每个约简反映决策矢量间不同水平的相似程度,从而不仅降低了对决策表区分能力的要求,而且能更好地满足实际应用的需要.2　Rough集理论的基本概念 下面简要介绍Rough集理论的基本概念,详细内容参见考文献[1,2].定义1(信息系统)　一个信息系统可以表示为三元组:T=〈U,A,f〉.其中U,A均是非空有限集, U包含论域中所有个体,A包含所有的属性, a∈A,f a:U→V a,V a表示属性a的值域.如果属性集A 可以分为条件属性集C和决策属性集D,即C∪D =A,C∩D= ,则该信息系统也称为决策表,表示为DT=〈U,C∪D,f〉.在信息系统中,对于每个属性子集B A,可以定义不可区分关系IND(B): IND(B)={(x,y)∈U×U b∈B,b(x)= b(y)}.显然IND(B)是U上的等价关系,对象x在属性集B上的等价类记为[x]IND(B),[x]IN D(B)={y y ∈U,(x,y)∈IND(B)},在不产生混淆的情况下一般用B代替IND(B).定义2(集合近似)　在信息系统T=〈U,A,f〉中,对于论域个体子集X U和属性子集R A,定义两个集合R-X=∪{Y∈U/R Y X},(1)R-X=∪{Y∈U/R Y∩X≠ },(2)分别称为X的R下近似集和R上近似集.定义3(正区域)　在信息系统T=〈U,A,f〉中,若P A,Q A,定义Q的P正区域为POS P Q=∪X∈U/QP-X.(3) 定义4(一致决策表和不一致决策表)　在决策表DT=〈U,C∪D,f〉中,如果POS C D=U,则称DT为一致决策表,否则称DT为不一致决策表.一致决策表意味着IND(C) IND(D).一致决策表产生确定性命题,不一致决策表则产生不确定性命题. 3　不一致决策表知识约简的基本概念 定义5(决策矢量)　在不一致决策表DT=〈U,C∪D,f〉中,U/D={D1,D2,…,D n}, x∈U,定义其决策矢量为B(x)=(D(D1[x]B),D(D2[x]B),…,D(D n[x]B)),(4)其中D(D i[x]B)=D i∩[x]B[x]B ,i∈{1,2,…,n}.进一步记B(x)={D k D(D k[x]B)=m axj≤nD(D j[x]B)},(5) B(x)={D k D(D k/[x]B)>0}.(6) B(x)是由x最有可能被划分到的决策等价类组成,而 B(x)由x可能被划分到的决策等价类组成.定义6(不一致决策表的约简)[5～7]　在不一致决策表DT=〈U,C∪D,f〉中,B C.1)若POS B(D)=POS C(D),且B的所有真子集均不满足此条件,则称B为决策表DT的Pawlak 约简(PR). 2)若 x∈U,有 B(x)= C(x),且B的所有真子集均不满足此条件,则称B为决策表DT的分布约简(DR). 3)若 x∈U,有 B(x)= C(x),且B的所有真子集均不满足此条件,则称B为决策表DT的最大分布约简(M DR). 4)若 x∈U,有 B(x)= C(x),且B的所有真子集均不满足此条件,则称B为决策表DT的分配约简(AR). 由以上定义可知,PR保证约简前后决策表的858控 制 与 决 策第21卷正区域不变;DR 保证约简前后决策表中的个体在每个决策类上的隶属程度不变;M DR 保证约简前后决策表中的个体的最大分布决策类不发生变化;而AR 保证约简前后决策表中的个体的可能决策类不发生变化.4　针对分布约简、最大分布约简及分配约简的高效知识约简方法4.1　决策表转化算法若决策表DT =〈U ,C ∪D ,f 〉是一致决策表,则定义6中的4种知识约简是等价的,但在不一致决策表的情况下则有所不同.文献[6,7]研究了DR,M DR 和AR 之间的关系,提出了相应的判定定理和可辨识属性矩阵.由可辨识属性矩阵可以导出相应的辨识公式,通过求解其极小析取范式可求得所有的约简.但是,这种方法在决策表较大的情况下将消耗大量计算时间,因而对大数据集或计算时间有严格要求的应用并不适合.另一方面,通过长期的研究和实践,许多学者都提出了针对PR,特别是一致决策表PR 的高效启发式算法[3,4].因此,如果能将DR,M DR 和AR 的计算转化为计算相应的一致决策表的PR,则可以利用现有的高效启发式算法提高计算效率. 定理1　在不一致决策表DT =〈U ,C ∪D ,f 〉中,U /D ={D 1,D 2,…,D n },B C ,以下结论成立:1) x ∈U , B (x )= C (x )当且仅当 y ∈[x ]B , C (y )= C (x );2) x ∈U , B (x )= C (x )当且仅当 y ∈[x ]B , C (y )= C (x );3) x ∈U , B (x )= C (x )当且仅当 y ∈[x ]B , C (y )= C (x );证明　由B C ,不妨设[x ]B =∪mi =1[y i]C.1)必要性: y ∈[x ]B ,由题设,有 B (y )= C (y )及 B (x )= C (x ).而由 B (y )的定义,有 B (y )= B (x ),因此可得 C (y )= C (x )成立.充分性: D i ∈U /D ,有D (D i [x ]B )= D i ∩[x ]B[x ]B=∑mj =1D i ∩[y j ]C [y j ]C [y j ]C[x ]B,y j ∈[x ]B ,1≤j ≤m .由题设,有 C (y j )= C (x ),即D i ∩[y j ]C [y j ]C = D i ∩[x ]C[x ]C.所以D (D i [x ]B )= D i ∩[x ]C [x ]C ∑mj =1 [y j ]C [x ]B= D i ∩[x ]C [x ]C =D (D i[x ]C ).故有 B (x )= C (x ).2)必要性:类似1)的必要性成立的证明.充分性: y j ∈[x ]B ,1≤j ≤m ,不妨设 C (y j )= C (x )={D k }, D i ∈U /D ,可得D (D i [x ]B )= D i ∩[x ]B[x ]B≤ D k ∩[x ]C [x ]C ∑mj =1 [y j ]C [x ]B =D (D k[x ]C ),仅当i =k 等号成立,故有 B (x )= C (x ).3)必要性:类似1)的必要性成立的证明.充分性: D k ∈ B (x ),D (D k /[x ]B )>0,即 D k ∩[x ]B[x ]B = D k ∩[x ]C [x ]C ∑mj =1 [y ]j ]C [x ]B >0.故有D k ∩[x ]C[x ]C>0,因此D k ∈ C (x ).则 B (x )C (x ).另一方面,由于B C ,显然有 C (x ) B (x ).综上所述,有 B (x )= C (x ).□定义7(导出决策表)　将 C , C 和 C 作为决策属性,由不一致决策表DT =〈U ,C ∪D ,f 〉可导出3个决策表DT =〈U ,C ∪{ C },f ′〉,DT =〈U ,C ∪{ C },f ′〉,DT =〈U ,C ∪{ C },f ′〉.(7)其中f ′仅在个体的决策属性到决策属性值的映射上与f 不相同.对于决策属性,f ′ C(x )= C (x ),f′C(x )= C (x ),及f ′C (x )= C (x ),易证以上3个导出决策表均为一致决策表.定理2　在不一致决策表DT =〈U ,C ∪D ,f 〉中,B C ,以下结论成立:1)B 是DT 的PR 当且仅当B 是DT 的DR;2)B 是DT 的PR 当且仅当B 是DT 的M DR;3)B 是DT 的PR 当且仅当B 是DT 的AR.证明　仅证1),2)和3)类似可证.充分性:假设U /{ C }={D 1,D 2,…,D n }, D k∈U /{ C },假设[x ]C D k .因为B 是DT 的DR,故B (x )=C (x ),因此[x ]BD k .另一方面,由定理1, y ∈[x ]B , C (y )= C (x )成立,由此可得[y ]C D k ,从而易知C -(D k )=B -(D k ).这意味着POS C { c }=POS B { c },显然B 的任何真子集均不满足此条件,因此B 是DT 的PR.类似可证明必要性成立.□利用定理2,可以得到计算DR,M DR 和AR 的859第8期李凡等:不一致决策表的知识约简方法研究算法,描述如下:输入:不一致决策表DT=〈U,C∪D,f〉.输出:DT的DR(或M DR,AR)集RED.Step1:计算决策表DT的 C(或 C, C),从而得到DT (或DT ,DT );Setp2:应用高效启发式算法计算DT (或DT , DT )的PR,得到RED.根据定理2,算法最后得到的结果一定是一个DR(或M DR,AR),即本算法是完备的.4.2　算法复杂度分析下面分析算法的时间复杂度.Setp1首先应求出条件属性集C的等价类.如果Step2计算PR时采用基于排序的启发式算法[3],则求解条件属性的等价类是计算PR中的一步,不必单独统计其计算时间.此时只需考察每个条件等价类中的个体的决策属性取值情况,即可得到每个条件等价类与每个决策等价类交集的基数,继而得到 C(或 C, C),因而这种情况下时间复杂度是O( D U );如果Step2计算PR时采用基于数据库技术的算法[4],则必须单独用一步计算求出各条件等价类,采用文献[3]提出的算法,其时间复杂度为O( C U log U ),然后考察每个条件等价类中决策属性取值的情况,故总的时间复杂度为O( C U log U )+O( D U ).一般说,决策属性集D中一般只含有一个属性,则两种情况下Setp1的时间复杂度分别为O( U )和O( C U log U ).Setp2的时间复杂度取决于计算PR所用的算法.同样假定决策属性集D中只含有一个属性,若采用文献[3]提出的算法,时间复杂度为O( C 2 U lo g U ),而采用基于数据库技术的算法[4],时间复杂度进一步降为O( C U ).综上所述,视计算PR采用的算法的不同,求解DR,　M DR或AR的时间复杂度为O( C 2 U lo g U )或O( C U log U ).在数据量较大时,无论哪种情况,本算法均较基于可辨识属性矩阵的算法更为有效.5 -约简 由定义6可知,DR保证约简前后决策表中每个个体在每个决策类上的隶属程度保持不变,约简后能最大限度地保持原决策表的信息.然而,在实际应用中,如果论域中两个个体的决策矢量原本相等,但由于数据受噪声的影响产生了微小差异,根据定理2,DR也必须区分这两个决策矢量,此时就对决策表的区分能力提出了不必要的要求.即使此时数据并没有受噪声影响,为提高新出现个体的分类准确程度,在很多应用中也并不需要精确区分两个较接近的决策矢量,因此需要定义一种约简,以避免这种对决策表区分能力的过高要求.为此,首先定义决策近似度,以此作为两个决策矢量是否视为相似的依据.定义8(决策近似度)　令 x,y∈U, A(x)= (x1,x2,…,x n), A(y)=(y1,y2,…,y n).x,y间的决策近似度定义为S(x,y)=∑ni=1x i y i∑ni=1x2i∑ni=1y2i.(8) 显然,S(x,y)是x与y的决策矢量间的夹角余弦值,这是一种常用的衡量二矢量是否接近的指标.从另一个侧面讲,S是U×U→[0,1]的一个映射,因此是U上的一个Fuzzy关系,并具有以下性质:性质1　对于不一致决策表DT=〈U,C∪D, f〉,S是U中的Fuzzy相似关系.证明 x,y∈U,由定义8易知S(x,x)=1及S(x,y)=S(y,x),即S满足自反性和对称性,因此是U上的Fuzzy相似关系.□因为S是U上的Fuzzy相似关系,所以S的 截关系是U上的相似关系.但在决策表中,要求决策属性构成对U的划分,而相似关系往往只能得到U的某个覆盖,因此S并不适合作为决策属性.为此需将S改造为某种Fuzzy等价关系,这可以通过求其传递闭包的方式进行处理.定理3　对于不一致决策表DT=〈U,C∪D, f〉中,S的传递闭包为[11]T S=S k,(9)其中k≥ U .TS为U上的Fuzzy等价关系,可以相应得到其 截关系T S 为如下形式:T S ={(x,y)∈U×U T S(x,y)≥ },(10)其中0≤ ≤1.T S 是U上的一个等价关系,可以构成对U的划分,记为U/TS , x∈U,包含x的等价类记为[x] .每个等价类中各元素间决策近似度大于等于 .进一步,将T S 看作原决策表的决策属性,则可以得到一个新的决策表.定义9( -决策表)　由不一致决策表DT=〈U,C∪D,f〉,可以导出 -决策表DT =〈U,C∪{T S },f　′〉.其中f　′仅在个体的决策属性到决策属性值的映射上与f不相同,对于决策属性,有f′TS(x)=[x] .易证DT 是一致决策表,相应定义原决策表DT的 -约简为:860控 制 与 决 策第21卷定义10( -约简)　决策表DT 的PR 称为决策表DT 的 -约简.显然,如果 =1,则DT 的 -约简即是DT 的DR.通过引入可调节参数 ,可以得到决策矢量在不同水平相似程度下的约简,即相当于对DR 引入程度可调的不一致,因而降低了DR 对决策表区分能力的苛刻要求.在实际应用中,得到T S 后即可进行 值的选择.选择的主要依据是用户的使用要求和数据中所含噪声数据的情况.如果不需要严格区分相近的决策矢量,或已知决策表中数据受噪声影响较大,则选择较小的 值,反之则选取较大的 值.此外,如果可估计某些数据受到噪声影响情况,则可以在S 矩阵中相应增大或减小相应的矩阵元素值.由此可见,这样处理不仅能得到符合实际需要的约简结果,而且能有效降低噪声数据对约简结果的影响,这样的处理方式相对于M DR 和AR 更为灵活.-约简的计算可分为两步,第1步需要计算T S 矩阵,继而求出TS .第2步构造DT 并计算约简.易知总的时间复杂度取决于计算TS 矩阵,其值为O ( U 3[lo g U ]),[x ]表示x 的整数部分.6　实例计算分析 下面通过一个实例来说明本文提出的计算不一致决策表约简的方法.决策表如表1所示,DT =〈U ,C ∪D ,f 〉.其中,U ={t 1,t 2,…,t 18},C ={a ,b ,c ,e ,f ,g },D ={d }.易得U /C ={{t 1},{t 2,t 3,t 14,t 15},{t 4,t 5,t 6},{t 7,t 8,t 9},{t 10,t 11,t 17,t 18},{t 12,t 13,t 16}}={C 1,C 2,C 3,C 4,C 5,C 6};U /D ={{t 1,t 2,t 12},{t 3,t 4,t 6,t 9,t 10,t 14,t 16,t 17,t 18},{t 5,t 7,t 8,t 11,t 13,t 15}}={D 1,D 2,D 3}.表1　实例决策表ab c e f g d t 10000000t 21000000t 31000001t 40111111t 50111112t 60111111t 70001002t 80001002t 90001001t 100111011t 110111012t 120011000t 130011002t 141000001t 151000002t 160011001t 170111011t 1811111 由定义7,可得到由表1导出的DT ,DT 和DT ,如表2所示(条件属性均为{a ,b ,c ,e ,f ,g },决策属性分别为{ C },{ C },{ C }).采用基于排序的启发式算法[3],由表2可分别计算出DR,MDR 和AR;由表1可直接计算出PR.计算结果如表3所示.表2　由表1导出的各种决策表a b c e f g C C C C 1000000(1,0,0) 1 1C 2100000(1/4,1/2,1/4) 2 2C 3011111(0,2/3,1/3) 3 3C 4000100(0,1/3,2/3) 4 4C 5011101(0,3/4,1/4) 5 5C 611(1/3,1/3,1/3)66表3　实例决策表4种约简的计算结果分布约简最大分布约简分配约简Pawlak 约简{a ,b ,c ,e ,f }{a ,b ,c ,e }{a ,b ,c ,e }{a ,e } 表2中: 1={D 1}, 2={D 2}, 3={D 2}, 4={D 3}, 5={D 2}, 6={D 1,D 2,D 3}; 1={D 1}, 2={D 1,D 2,D 3}, 3={D 2,D 3}, 4={D 2,D 3}, 5={D 2,D 3}, 6={D 1,D 2,D 3}.下面计算表1所示实例决策表的 -约简.由表2可求得Fuzzy 相似关系S 和Fuzzy 等价关系T S 为S =10.4080000.5780.40810.9130.7300.9040.94300.91310.80.9900.77500.7300.810.7070.77500.9040.9900.70710.7310.5780.9430.7750.7750.7311,T S =10.5780.5780.5780.5780.5780.57810.9130.80.9130.9430.5780.91310.80.9900.9130.5780.80.810.80.80.5780.9130.9900.810.9130.5780.9430.9130.80.9131.则在 = 1.0, =0.99, =0.943, =0.913和 =0.8时,可分别得到U /TS 1.0={{C 1},{C 2},{C 3},{C 4},{C 5},{C 6}},U /TS 0.99={{C 1},{C 2},{C 3,C 5},{C 4},{C 6}},U /TS 0.943={{C 1},{C 2,C 6},{C 3,C 5},{C 4}},U /TS 0.913={{C 1},{C 2,C 3,C 5,C 6},{C 4}},U /TS 0.8={{C 1},{C 2,C 3C 4C 5,C 6}}. 采用基于排序的启发式算法[3],可以分别求得在这个水平下表1所示实例决策表的 -约简,如表4　不同 水平下实例决策表的 -约简10.990.9430.9130.8861第8期李凡等:不一致决策表的知识约简方法研究表4所示: 从表4可见,通过调节 的值,由 -约简可以得到一族平滑过渡的知识约简,并且其中包括了实例决策表的DR,MDR,AR以及PR.7　结 论 在实际应用中,由于数据获取或数据处理方面的原因,决策表往往是不一致的.为了从中得到简洁的不确定性命题规则,必须对其进行知识约简.本文从以下两个方面对这个问题进行了探讨.首先,对不一致决策表的DR,M DR和AR,目前的约简方法是通过构造可辨识属性矩阵和相应的辨识公式求解约简.这样的方法在决策表很大或对计算时间有严格要求的场合并不适用.为此,本文提出了针对这3种约简的转化算法,将计算原不一致决策表的这3种约简转化为计算3种一致决策表的PR,进而通过应用针对PR的高效启发式算法,可以有效地减少计算时间的消耗.其次,DR对信息系统区分能力的要求比较苛刻,针对实际应用而言,这种约简不仅缺乏灵活性,而且易受到噪音数据的影响.针对这些缺点,本文提出了一种新的不一致决策表知识约简的概念,即 -约简.通过调节参数 的值,对原决策表引入可调节的额外不一致,从而可以得到一族平滑过渡的知识约简,其中的每个约简反映决策矢量间不同水平的相似程度.相对于上述3种约简, -约简有更好的灵活性,因此能更好地满足实际应用的需要.参考文献(References)[1]P aw lak Z,G rzymala-Busse J,Slow inski R,et al.R ough Sets[J].Communication of the A CM,1995,38(11):89-95.[2]P aw lak Z.So me Issues on R ough Set s[J].T r ans onR ough Sets I,L N CS3100,2004:1-58.[3]刘少辉,盛秋戬,吴斌,等.Roug h集高效算法研究[J].计算机学报,2003,26(5):524-529.(L iu S H,Sheng Q J,W u B,et al.R esear ch on Efficient A lg or ithms for R ough Set M ethods[J].Chinese J of Comp uter,2003,26(5):524-529.)[4]Han J C,Hu X H,L in T Y.A New Com putationM o del for Roug h Set T heor y Based on Database Systems[A].DaW aK2003,L N CS2737[C].Ber lin: Spr ing er-Ver lag Heidelber g,2003:381-390.[5]K ry szkiew icz M.Co mparative Study o f A lt ernativeT y pes o f Kno wledge R eductio n in Inco nsist ent Systems [J].I nt J of I ntellig ent Sy stems,2001,16(1):105-120.[6]Zhang W X,M i J S,W u W Z.A ppro aches t oK no wledge Reduct ions in Inconsistent Infor mation Systems[J].I nt J of I ntelligent S y stems,2003,18(9): 989-1000.[7]张文修,米据生,吴伟志.不协调目标信息系统的知识约简[J].计算机学报,2003,26(1):12-18.(Zhang W X,M i J S,Wu W Z.Ko nwledg e Reductions in I nco nsistent Infor matio n Systems[J].Chinese J of Comp uter,2003,26(1):12-18.)[8]Ziar ko W.V ar iable P recisio n R oug h Set M o del[J].Jof Comp uter Sy stems and Science,1993,46(1):39-59.[9]N guyen H S,Slezak D.A ppr ox im atio n Reducts andA sso ciatio n Rules Cor respondence and Co mplex it yResults[A].Pr oc of RSF DGr C'99,L N A I1711[C].Ber lin:Spring er-V erlag Heidelberg,1999:137-145.[10]L i F,L iu Q H,Y ang G W.A Heur istic A lg or ithm forA ttr ibute Reductio n in Inco mplete Infor mationSy st ems[A].Pr oc of I S I CA2005[C].W uhan:China U niver sity o f Geo sciences of P ress,2005:574-580. [11]杨纶标,高英仪.模糊数学原理及应用[M].广州:华南理工大学出版社,2000:112-125.(Y ang L B,Gao Y Y.Fuz z y M ath T heor y andA p p lications[M].G uang zhou:South ChinaU niver sity o f T echnolog y o f Pr ess,2000:112-125.) (上接第847页)[39]Rofer T,J ng el M.V isio n-based F ast a nd R eact ive M onte-car lo L ocalizatio n[A].Pr oc of the I E EE I nt Conf on Robotics and A utomation(I CRA-2003)[C].T aipei,2003:856-861.[40]Bo gdan K.Finding L ocat ion U sing a P art icle F ilterand Histo g ram M atching[A].P roc of A r tif icialI ntelligence and Sof t Comp uting[C].P oland:Spr ing er,2004:786-791.[41]A ndr ew H,Sa jid S.A n Ex perimental Study ofL o calization U sing Wir eless Ether net[A].Pr oc of theI nt Conf on Field and Serv ice Robotics[C].L akeY amanaka,2003:201-206.[42]M eneg atti E,P rett o A,Pag ello E.A N ew Omni-dir ectio nal V ision Senso r for M onte-car lo L o ca lization[A].Pr oc of the8th RoboCup I nt Sy mp osium[C].Berlin:Spr inger,2005:97-109.862控 制 与 决 策第21卷。