基于关系积的属性约简算法.pdf_大学文库

D0I:10.13374/1.issnl00103.2008.06.024 第30卷第6期北京科技大学学报 Vol.30 No.6 2008年6月 Journal of University of Science and Technology Beijing Jun.2008 基于关系积的属性约简算法焦吉成2)高学东) 邓君堂)鄂旭) 1)北京科技大学经济与管理学院，北京1000832)济南钢铁集团总公司技术中心，济南250101 3)辽宁工学院计算机系，锦州121001 摘要粗糙集的属性约简是一个NP难问题，目前尚无高效的算法，基于集合理论，提出了关系积概念和基于关系积的属性约简算法，把决策表的属性约简过程转化为关系积的运算，减小了对决策表的扫描次数，提高了属性约简的效率：算法采用自底向上和宽度优先的搜索策略，可确保找到最小属性约简集.结合实例，给出了算法的具体实现关键词约简算法：关系积；属性；集合理论：粗糙集分类号TP182 Attribute reduction algorithm based on attribute union JIAO Jicheng),GAO Xuedong )DENG Juntang?),E Xu3) 1)School of Economics and Management.University of Science and Technology Beijing Beijing 100083.China 2)Technology Center,Jinan Iron and Steel Group Corporation,Jinan 250101.China 3)Department of Computer Science.Liaoning Institute of Technology,Jinzhou 121001,China ABSTRACT Attribute reduction of rough sets is an NP hard problem,but there is not a popular efficient algorithm presently.The attribute union concept based on the set theory and the attribute reduced algorithm based on this concept were presented.The algo- rithm translates the attribute reduction to find the attribute union,reducing the number of scanning the decision table and improving the reduced efficiency.The scanning strategy from bottom to top and with width priority can insure to find the minimal reduction. Also.an example was presented to describe the algorithm KEY WORDS reduction algorithm:attribute union:attribute:set theory:rough set 粗糙集理论是]由波兰华沙理工大学Pawlak 先验信息.属性集的约简(attribute reduction)②是教授等一批科学家于1982年提出的，是一种新型的粗集理论中关键的问题之一，所谓约简是属性集的处理模糊和不确定知识的数学工具，这门理论建构子集，它与原属性集具有同样的分辨能力·约简反在经典集合论基础之上，借助分类手段对数据进行映了一个信息系统的本质信息，求解一个信息系统处理，可以有效地进行信息处理，提取有用信息，简的全部约简或计算出最佳约简都是NP难问化决策规则，提高分类效率。近几年来，该理论在机题3].当数据量很大时，应用粗糙集理论算法十器学习、数据挖掘和模式识别等领域得到了广泛分耗时，甚至不可行应用· 现有的属性约简算法分为三类：(l)Pawlak约粗糙集理论的主要思想是在保持分类能力不变简算法可.这种方法按照约简的定义进行求解，需的前提下，通过属性约简，导出问题的决策或分类规要对条件属性集的幂集中所有元素进行考察，每次则，应用粗糙集理论处理不确定性问题的最显著特考察都需对决策进行扫描，该算法的理论指导意义点是不需提供问题所需处理的数据集合之外的任何大于其实际应用效果，但其计算速度慢，且不易于计算机实现，故其实际应用的局限性较大，(2) 收稿日期：2007-04-06修回日期：2007-05-30 Skowron算法[（也称可辩识矩阵和逻辑运算的约基金项目：中国博士后科学基金资助项目(N。,2005038319) 简算法)，是Skowron教授于1992年提出，该算法作者简介：焦吉成(1968一)，男，高级工程师，博士研究生：高学东(1963一)，男，教授，博士生导师，首先根据信息系统构造一个相关的可辩识矩阵；其 E-mail:gaoxuedong@manage.ustb.edu.en 次，利用可辩识矩阵中的非空元素构造区分函数（析

基于关系积的属性约简算法焦吉成12）高学东1）邓君堂2）鄂旭3） 1）北京科技大学经济与管理学院北京100083 2）济南钢铁集团总公司技术中心济南250101 3）辽宁工学院计算机系锦州121001 摘要粗糙集的属性约简是一个 NP 难问题目前尚无高效的算法．基于集合理论提出了关系积概念和基于关系积的属性约简算法把决策表的属性约简过程转化为关系积的运算减小了对决策表的扫描次数提高了属性约简的效率；算法采用自底向上和宽度优先的搜索策略可确保找到最小属性约简集．结合实例给出了算法的具体实现．关键词约简算法；关系积；属性；集合理论；粗糙集分类号 TP182 Attribute reduction algorithm based on attribute union JIA O Jicheng 12）GA O Xuedong 1）DENG Juntang 2）E Xu 3） 1） School of Economics and ManagementUniversity of Science and Technology BeijingBeijing100083China 2） Technology CenterJinan Iron and Steel Group CorporationJinan250101China 3） Department of Computer ScienceLiaoning Institute of TechnologyJinzhou121001China ABSTRACT Attribute reduction of rough sets is an NP hard problembut there is not a popular efficient algorithm presently．T he attribute union concept based on the set theory and the attribute reduced algorithm based on this concept were presented．T he algorithm translates the attribute reduction to find the attribute unionreducing the number of scanning the decision table and improving the reduced efficiency．T he scanning strategy from bottom to top and with width priority can insure to find the minimal reduction． Alsoan example was presented to describe the algorithm． KEY WORDS reduction algorithm；attribute union；attribute；set theory；rough set 收稿日期：2007-04-06 修回日期：2007-05-30 基金项目：中国博士后科学基金资助项目（No．2005038319）作者简介：焦吉成（1968—）男高级工程师博士研究生；高学东（1963—）男教授博士生导师 E-mail：gaoxuedong＠manage．ustb．edu．cn 粗糙集理论是［1］由波兰华沙理工大学 Pawlak 教授等一批科学家于1982年提出的是一种新型的处理模糊和不确定知识的数学工具．这门理论建构在经典集合论基础之上借助分类手段对数据进行处理可以有效地进行信息处理提取有用信息简化决策规则提高分类效率．近几年来该理论在机器学习、数据挖掘和模式识别等领域得到了广泛应用．粗糙集理论的主要思想是在保持分类能力不变的前提下通过属性约简导出问题的决策或分类规则．应用粗糙集理论处理不确定性问题的最显著特点是不需提供问题所需处理的数据集合之外的任何先验信息．属性集的约简（attribute reduction）［2］是粗集理论中关键的问题之一．所谓约简是属性集的子集它与原属性集具有同样的分辨能力．约简反映了一个信息系统的本质信息求解一个信息系统的全部约简或计算出最佳约简都是 NP 难问题［3—4］．当数据量很大时应用粗糙集理论算法十分耗时甚至不可行．现有的属性约简算法分为三类：（1） Pawlak 约简算法［5］．这种方法按照约简的定义进行求解需要对条件属性集的幂集中所有元素进行考察每次考察都需对决策进行扫描该算法的理论指导意义大于其实际应用效果但其计算速度慢且不易于计算机实现故其实际应用的局限性较大．（2） Skowron 算法［6］（也称可辩识矩阵和逻辑运算的约简算法）是 Skowron 教授于1992年提出．该算法首先根据信息系统构造一个相关的可辩识矩阵；其次利用可辩识矩阵中的非空元素构造区分函数（析第30卷第6期 2008年 6月北京科技大学学报 Journal of University of Science and Technology Beijing Vol．30No．6 Jun．2008 DOI:10．13374／j．issn1001－053x．2008．06．024

第6期焦吉成等：基于关系积的属性约简算法 .695 取式)；最后，把析取式转化为合取式，求解区分函单一的决策属性，从数据库的角度来看，决策系统数，每一个合取子式对应一种约简，该算法可获得信就是一张表，其中U是记录集合，A是字段集合，息系统的所有约简，该算法实际上是将对属性组合每一个对象对应一条纪录，这样决策系统又可称为情况的搜索演变成逻辑公式的化简，从而简化了问决策表. 题，该算法的缺点在于：①对于大规模的信息系统，在决策系统SU,CU{d)中，对于B三C, 该算法需存储一个较大的区分矩阵，占用了大量的则B在U上的不可分辨关系定义为：IND(B)= 计算机内存；②区分函数的求解是一个组合问题， (x,y)(x,y)∈U2,Vb∈B(b(x)=b(y), 会出现组合爆炸问题，计算过程中数据溢出现象严IND(B)把U划分为k个等价类X1,X2,,X, 重，因此，该算法在处理海量信息系统的约简问题 UIND(B)表示等价关系IND(B)的所有等价类组上不是非常有效的.(3)各种启发式算法，根据属成的等价类族，即有UIND(B){X1,X2,,Xk}. 性重要度、信息熵或可辩识矩阵中属性出现次数等对于对象集X三U,属性集B二A,X的下近似启发信息来寻求信息系统的约简，如文献[7]把区 B-(x)和上近似B(x)分别定义如下：分矩阵中属性出现次数作为启发信息，文献[8]是基 B-(x)=U1Y:I(Y:∈UlIND(B)AY∈X), 于信息熵的遗传顺序约简算法，文献[9]把属性重要 B(x)=UiY:l(Y:∈UlIND(B)AY:∩X≠O). 度作为启发式信息，这类算法主要优点是采用多项在信息系统SU,CU{d)中，对属性集C的子式时间进行求解，且可以对大规模数据集进行处理，集B,属性a∈B三C是B中必要的，当且仅当启发式算法的缺点在于利用这类算法所求得的约简 IND(B)≠IND(B一{a);否则，属性a在B中是不能保证是最小属性约简，有些算法所求得的约简冗余或可省略的，属性集B的约简是一个集合B'三甚至是不完备的 B,当且仅当满足：①B是独立的：②IND(B)= 1粗糙集及关系积的基本概念 IND(B),属性集B三C的所有约简族的交集称为属性集B的核，记为CORE(B),有CORE(B)= 知识表达系统又称为信息系统，可表示为S= ∩RED(B)· 〈U,A,V,D,其中U为对象的非空有限集合，A 根据需要，首先提出如下三个关键概念，为属性的非空有限集合，V为属性的值域集，∫为定义1在决策系统S=U,CU{d)中，设信息函数，f:UXA→V.如果A=CUD,C∩ IND(B1)和IND(B2)分别为B1三C和B2=C对U D=O,C为条件属性集，D为决策属性集，则把信导出的等价类，则由B12=B1∩B2所导出的等价类息系统S=(U,A,V,称为决策系统，用S= IND(B1∩B2)称为IND(B1)和IND(B2)的关系积， (U,CU1d)或s只U,CUD来表示，其中d为记为IND(B1·B2),如图1所示， XOr Xnr Y or xOY OxOY Y Xnr XnY 图1关系积.(a)IND(B1):(b)IND(B2):(c)IND(B1·B2) Fig.1 Concept of attribute union:(a)IND(B1);(b)IND(B2);(c)IND(B1.B2) 关系积概念的实质是两种划分对集合的联合划 IND(B1·B2,Bm)称为m元关系积分，与集合的交不同，集合的交取的是两个集合的公定义3在决策系统S=(U,CU{d)中，令共部分，而关系积只是对集合的一次重新划分.很 Q=决策属性集={d},条件属性C={B1,B2,…, 容易证明关系积运算满足交换率和结合率. Bm{,如果POSe(Q)=U,则称论域U是C上相对定义2在决策系统S=(U,CU1d)中，条于Q一致的，也即决策表是确定的决策表，决策表件属性C=iB1,B2,,Bm,IND(B1·B2)称为二中不包含不一致的信息（样本）元关系积，IND(B1·B2·B3)称为三元关系积，对于不确定的决策表，根据决策表产生不确定

取式）；最后把析取式转化为合取式求解区分函数每一个合取子式对应一种约简该算法可获得信息系统的所有约简．该算法实际上是将对属性组合情况的搜索演变成逻辑公式的化简从而简化了问题．该算法的缺点在于：①对于大规模的信息系统该算法需存储一个较大的区分矩阵占用了大量的计算机内存；②区分函数的求解是一个组合问题会出现组合爆炸问题计算过程中数据溢出现象严重．因此该算法在处理海量信息系统的约简问题上不是非常有效的．（3）各种启发式算法．根据属性重要度、信息熵或可辩识矩阵中属性出现次数等启发信息来寻求信息系统的约简．如文献［7］把区分矩阵中属性出现次数作为启发信息文献［8］是基于信息熵的遗传顺序约简算法文献［9］把属性重要度作为启发式信息．这类算法主要优点是采用多项式时间进行求解且可以对大规模数据集进行处理．启发式算法的缺点在于利用这类算法所求得的约简不能保证是最小属性约简有些算法所求得的约简甚至是不完备的． 1 粗糙集及关系积的基本概念知识表达系统又称为信息系统可表示为 S＝〈UAV f〉其中 U 为对象的非空有限集合A 为属性的非空有限集合V 为属性的值域集f 为信息函数f∶U × A → V ．如果 A ＝ C ∪ DC∩ D＝∅C 为条件属性集D 为决策属性集则把信息系统 S ＝〈UAV f〉称为决策系统用 S ＝〈UC∪｛d｝〉或 S＝〈UC∪ D〉来表示其中 d 为单一的决策属性．从数据库的角度来看决策系统就是一张表其中 U 是记录集合A 是字段集合每一个对象对应一条纪录这样决策系统又可称为决策表．在决策系统 S＝〈UC∪｛d｝〉中对于 B⊆ C 则 B 在 U 上的不可分辨关系定义为：IND（ B）＝｛（xy）｜（ xy）∈ U 2V b∈ B（ b （ x ）＝ b （ y））｝ IND（B）把 U 划分为 k 个等价类 X1X2…Xk U｜IND（B）表示等价关系 IND（B）的所有等价类组成的等价类族即有 U｜IND（B）∶｛X1X2…Xk｝．对于对象集 X⊆ U属性集 B⊆ AX 的下近似 B—（ x）和上近似 B —（ x）分别定义如下： B—（ x）＝∪｛Y i｜（ Y i∈ U｜IND（B）∧ Y i⊆X）｝ B —（x）＝∪｛Y｜i （Yi∈U｜IND（B）∧Yi∩X≠∅）｝．在信息系统 S＝〈UC∪｛d｝〉中对属性集 C 的子集 B属性 a∈ B ⊆ C 是 B 中必要的当且仅当 IND（B）≠IND（ B—｛a｝）；否则属性 a 在 B 中是冗余或可省略的．属性集 B 的约简是一个集合B′⊆ B当且仅当满足：① B 是独立的；② IND（ B′）＝ IND（B）．属性集 B⊆ C 的所有约简族的交集称为属性集 B 的核记为 CORE （ B）有CORE（B）＝ ∩RED（B）．根据需要首先提出如下三个关键概念．定义1 在决策系统 S＝〈UC∪｛d｝〉中设 IND（B1）和 IND（B2）分别为 B1⊆C 和 B2⊆C 对 U 导出的等价类则由 B12＝B1∩B2 所导出的等价类 IND（B1∩B2）称为 IND（B1）和 IND（B2）的关系积记为 IND（B1·B2）如图1所示．图1 关系积．（a） IND（ B1）；（b） IND（ B2）；（c） IND（ B1·B2） Fig．1 Concept of attribute union：（a） IND（ B1）；（b） IND（ B2）；（c） IND（ B1·B2）关系积概念的实质是两种划分对集合的联合划分与集合的交不同集合的交取的是两个集合的公共部分而关系积只是对集合的一次重新划分．很容易证明关系积运算满足交换率和结合率．定义2 在决策系统 S＝〈UC∪｛d｝〉中条件属性 C＝｛B1B2…Bm｝IND（ B1·B2）称为二元关系积IND （ B1·B2·B3）称为三元关系积 IND（B1·B2…Bm）称为 m 元关系积．定义3 在决策系统 S＝〈UC∪｛d｝〉中令 Q＝决策属性集＝｛d｝条件属性 C＝｛B1B2… Bm｝如果 POSc（ Q）＝ U则称论域 U 是 C 上相对于 Q 一致的也即决策表是确定的决策表决策表中不包含不一致的信息（样本）．对于不确定的决策表根据决策表产生不确定第6期焦吉成等：基于关系积的属性约简算法 ·695·

.696 北京科技大学学报第30卷性的原因，对决策表进行相关的处理 CacNo=CacNo+l; 2关系积约简算法 End Step5输出CacNo元关系积的约简属性： Pawlak约简算法是从全部的条件属性集开始， Step6输出核COREo(P)=∩REDo(P) 逐步去掉对决策属性不必要的条件属性获得最小约 Function CheckRed(IND(B),IND(d)) 简属性的，可以称为一种自顶向下的约简算法，这 Begin 种方法每去掉一个属性，需要对决策表重新进行组 If POSIND(B)(d)=U then return True else re- 合，生成新的决策表，根据新的决策表判断是否获得 turn False; 了最小约简，因此，需要反复地对决策表进行操作， End 需要占用大量的计算资源，也降低了算法的效率：事其中，Card函数用于计算各划分的集合数量.子程实上，完全可以根据决策表提供的各属性等价关系序Check Red用于检查约简后的决策表表达式属性及其它们的关系积对属性进行约简，从而获得最小是否与原有决策表的属性有相同的分类能力，如达约简属性，由于高元关系积可由次元关系积和一元到则算法结束，这样，由于本算法采用自底向上的关系积的集合运算生成，不需要对决策表重新进行约简，如果在某元关系积上找到最小的属性约简，则组织和扫描，把对表扫描转化为集合运算，节省了大没有必要搜索大于或包含它的上级关系积.由于本量I/0开销，极大地提高了算法的效率. 算法对同元关系积进行全部计算后，才检验是否找 [算法]：RedAttrBU(reducing attribute based on 到最小约简，所以本算法可以找到所有的最小属性 union) 约简集输入：决策系统SU,CU{d),C为条件属如前所述，关系积运算满足交换率和结合率，因性集，{d为单一决策属性集此在生成N元关系积时，只需对N一1元关系积一输出：条件属性集C的约简及核半进行关系积运算就可，算法步骤： 3算法示例 Step0检验决策表是否是确定的决策表，如不是则退出：结合文献[2]提供的一个关于气象信息的决策 Step1对条件属性集中所有属性和决策属表（表1），说明以上约简算法性，计算一元关系积，即IND(B)和IND(d),令表1气象信息的决策表 CacNo=1,C=; Table 1 Decision table about weat her information Step2检验是否获得属性的最小约简，f 条件属性决策 U Check Red(IND(BCaeNo),IND(d))then goto step 5; 天气(a1)气温(a2)温度(s)风(a4) 属性(d) Step 3 CacNo=CacNo+1; 晴热感无风不适合 Step4 while(CacNo<>属性集数目)do 2 晴热高有风不适合 Begin 多云热高无风适合 ∥对属性集中所有属性，计算 4 ⑧ 适中高无风适合 CacNo元关系积， 5 雨血正常有风不适合 for i=l to Card(IND(BCaeNo-1))do 6 雨血正常有风不适合 for j=i to Card(IND(B1))do 多云冷正常有风适合 IND(BCaeNo)=IND(BCaeNo-1) 适中高无风不适合 (i)∩IND(B1(Uj): 9 晴冷正常无风适合 ∥检查是否获得约简集，如是则 10 雨适中正常有风适合记录下约简集属性，寻找过程结束，之晴适中正常有风适合 12 多云适中令有风适合 for i=1 to Card(IND(BcaeNo))do 13 多云热正常无风适合 If CheckRed (IND BCaeNo (i)) 14 适中高有风不适合 IND(d))then C=C+IND(BcaeN(i)); If (Card(C)0)then goto Step 令Q=决策属性集=d},P=条件属性全集= 5: {a,2,a3,a4},则：

性的原因对决策表进行相关的处理． 2 关系积约简算法 Pawlak 约简算法是从全部的条件属性集开始逐步去掉对决策属性不必要的条件属性获得最小约简属性的可以称为一种自顶向下的约简算法．这种方法每去掉一个属性需要对决策表重新进行组合生成新的决策表根据新的决策表判断是否获得了最小约简．因此需要反复地对决策表进行操作需要占用大量的计算资源也降低了算法的效率；事实上完全可以根据决策表提供的各属性等价关系及其它们的关系积对属性进行约简从而获得最小约简属性．由于高元关系积可由次元关系积和一元关系积的集合运算生成不需要对决策表重新进行组织和扫描把对表扫描转化为集合运算节省了大量 I／O 开销极大地提高了算法的效率．［算法］：RedAttrBU（reducing attribute based on union）输入：决策系统 S＝〈UC∪｛d｝〉C 为条件属性集｛d｝为单一决策属性集．输出：条件属性集 C 的约简及核．算法步骤： Step0 检验决策表是否是确定的决策表如不是则退出； Step1 对条件属性集中所有属性和决策属性计算一元关系积即 IND（ B）和 IND（ d）令 CacNo＝1C＝｛｝； Step2 检验是否获得属性的最小约简if CheckRed（IND（BCacNo）IND（ d）） then goto step5； Step3 CacNo＝CacNo＋1； Step4 while（CacNo＜＞属性集数目） do Begin ∥ 对属性集中所有属性计算 CacNo 元关系积． for i＝1to Card（IND（BCacNo—1）） do for j＝ i to Card（IND（B1）） do IND（ BCacNo）＝IND（ BCacNo—1）（ i）∩IND（B1（ j））； ∥检查是否获得约简集如是则记录下约简集属性寻找过程结束． for i＝1to Card（IND（BCacNo）） do If CheckRed （IND （ BCacNo （ i）） IND（d）） then C＝C＋IND（BCacNo（i））； If （Card（ C）＜＞0） then goto Step 5； CacNo＝CacNo＋1； End Step5 输出 CacNo 元关系积的约简属性； Step6 输出核 COREQ（P）＝∩REDQ（P） Function CheckRed（IND（B）IND（ d）） Begin If POSIND（B）（ d）＝ U then return True else return False； End 其中Card 函数用于计算各划分的集合数量．子程序 CheckRed 用于检查约简后的决策表表达式属性是否与原有决策表的属性有相同的分类能力如达到则算法结束．这样由于本算法采用自底向上的约简如果在某元关系积上找到最小的属性约简则没有必要搜索大于或包含它的上级关系积．由于本算法对同元关系积进行全部计算后才检验是否找到最小约简所以本算法可以找到所有的最小属性约简集．如前所述关系积运算满足交换率和结合率因此在生成 N 元关系积时只需对 N—1元关系积一半进行关系积运算就可． 3 算法示例结合文献［2］提供的一个关于气象信息的决策表（表1）说明以上约简算法．表1 气象信息的决策表 Table1 Decision table about weather information U 条件属性天气（ a1）气温（ a2）温度（ a3）风（ a4）决策属性（ d） 1 晴热高无风不适合 2 晴热高有风不适合 3 多云热高无风适合 4 雨适中高无风适合 5 雨冷正常有风不适合 6 雨冷正常有风不适合 7 多云冷正常有风适合 8 晴适中高无风不适合 9 晴冷正常无风适合 10 雨适中正常有风适合 11 晴适中正常有风适合 12 多云适中高有风适合 13 多云热正常无风适合 14 雨适中高有风不适合令 Q＝决策属性集＝｛d｝P＝条件属性全集＝｛a1a2a3a4｝则： ·696· 北京科技大学学报第30卷

IND（P）＝｛｛1｝｛2｝｛3｝｛4｝｛5｝｛6｝｛7｝｛8｝｛9｝｛10｝｛11｝｛12｝｛13｝｛14｝｝ IND（ Q）＝｛｛126814｝｛3457910111213｝｝ POSp（ Q）＝ U．各条件属性的等价关系如下： IND（ a1）＝｛｛128911｝｛371213｝｛4561014｝｝ IND（ a2）＝｛｛12313｝｛4810111214｝｛5679｝｝ IND（ a3）＝｛｛123481214｝｛5679101113｝｝ IND（ a4）＝｛｛1345891013｝｛267111214｝｝．因为 POSIND（ a i ）（ Q）≠ Ui＝12…4故一元关系积不能构成最小约简． IND（ a1·a2）＝｛｛12｝｛811｝｛9｝｛313｝｛12｝｛7｝｛41014｝｛56｝｝ IND（ a1·a3）＝｛｛128｝｛911｝｛312｝｛713｝｛414｝｛5610｝｝ IND（ a1·a4）＝｛｛189｝｛211｝｛313｝｛712｝｛4510｝｛614｝｝ IND（ a2·a3）＝｛｛123｝｛13｝｛481214｝｛1011｝｛5679｝｝ IND（ a2·a4）＝｛｛1313｝｛2｝｛4810｝｛111214｝｛59｝｛67｝｝ IND（ a3·a4）＝｛｛1348｝｛21214｝｛591013｝｛6711｝｝．检查 POSIND（ a i·a j ）（ Q）≠ Uij ＝12…4 i≠ j故二元关系积也不构成最小约简． IND（ a1·a2·a3）＝｛｛12｝｛8｝｛11｝｛9｝｛3｝｛13｝｛12｝｛7｝｛414｝｛10｝｛56｝｝ IND（ a1·a2·a4）＝｛｛1｝｛2｝｛8｝｛11｝｛9｝｛313｝｛12｝｛7｝｛410｝｛14｝｛5｝｛6｝｝ IND（ a1·a4·a3）＝｛｛18｝｛9｝｛2｝｛11｝｛3｝｛13｝｛7｝｛12｝｛4｝｛510｝｛6｝｛14｝｝ IND（ a4·a2·a3）＝｛｛13｝｛13｝｛2｝｛48｝｛10｝｛59｝｛11｝｛1214｝｛67｝｝．检查： POSIND（ a1·a2·a3 ）（ Q）＝｛12378910111213｝≠ U POSIND（ a1·a2·a4 ）（ Q）＝｛1234567891011121314｝＝ U POSIND（ a1·a4·a3 ）（ Q）＝｛1234567891011121314｝＝ U POSIND（ a2·a3·a4）（ Q）＝｛259101113｝≠ U．所以属性 a1a2a4 和 a1a3a4 构成了决策表的最小约简集其核为： COREQ（P）＝∩REDQ（P）＝｛a1a2a4｝∩｛a1a3a4｝＝｛a1a4｝． 4 结束语本文从关系积的概念出发把对决策表的扫描转化为集合的运算只对决策表扫描一次就可生成所有的最小约简属性集避免了对决策表的频繁操作．但在生成各阶关系积时仍存在属性组合的爆炸问题根据关系积的特点提出一些启发式算法从而降低关系积运算的次数．参考文献［1］ Pawlak Z．Rough Sets-theoretical Aspects of Reasoning about Data．Poland：Warsaw1991 ［2］ Zhang W XWu W ZLiang J Yet al．Rough Set Theory and App roaches．Beijing：Science Press2001：35 （张文修吴伟志梁吉业等．粗糙集理论与方法．北京：科学出版社2001：35）［3］ John G HKohavi RPfloger K．Irrelevant features and the subset selection problem ∥ Proceedings on Machine Learning’94． Vancouver：Morgan Kouffmann Publishers1994：121 ［4］ E XGao X DYu B．A method for attributes reduction based on scan vector．J Univ Sci Technol Beijing200628（6）：604 （鄂旭高学东喻斌．基于扫描向量的属性约简方法．北京科技大学学报200628（6）：604）［5］ Wang G Y．Rough Set Theory and Knowledge Acquisition．Xi’ an：Xi’an Jiaotong University Press2001 （王国胤．Rough 集理论与知识获取．西安：西安交通大学出版社2001）［6］ Skowron APolkowski L．Synthesis of decision systems from data tables∥ Rough Sets and Data Mining：A nalysis for Imp recise Data．Boston：Kluwer Academic Publishers1997：259 ［7］ Hu K YDiao L LLu Y Cet al．A heuristic optimal reduct algorithm∥ Proceedings of 2nd International Conference on Intelligent Data Engineering and A utomated Learning．Hong Kong 2000 ［8］ Slezak DWrobewski J．Order based genetic algorithms for the search of approximate entropy reduces∥ Proceedings of the 9th International Conference on Rough SetFuzz y SetsData Miningand Granular Computing．Chongqing2003 ［9］ Li K WWu M DZhang X M．A heuristic algorithm for reduction．Comput Eng Sci200426（1）：92 （李克文吴孟达张雄明．约简的一种启发式算法．计算机工程与科学200426（1）：92）第6期焦吉成等：基于关系积的属性约简算法 ·697·