下载文档原格式
基于属性重要性的逐步约简算法
杜金莲;迟忠先;翟巍
【期刊名称】《小型微型计算机系统》
【年(卷),期】2003(024)006
【摘要】粗糙集理论研究的重要内容之一是知识约简的有效性计算问题,目前求解知识约简的算法主要有两种:一种是利用辨识矩阵构造区分函数,另外一种是基于属性重要性的启发式算法.这两种算法均能求得决策系统的最小或次小约简,但由于计算的复杂度高,所以当数据量增大时这些算法的计算性能是不能令人满意的.本文在对后一种算法充分研究的基础上设计了基于属性重要性的逐步约简算法,利用在决策系统中已获得的正区域逐步缩小数据处理范围,减少求解时间.本文将该算法与基于属性重要性的算法进行了实验比较并对结果进行了分析.
【总页数】3页(P976-978)
【作者】杜金莲;迟忠先;翟巍
【作者单位】大连理工大学,计算机系,软件工程研究室,辽宁,大连,116024;大连理工大学,计算机系,软件工程研究室,辽宁,大连,116024;大连理工大学,计算机系,软件工程研究室,辽宁,大连,116024
【正文语种】中文
【中图分类】TP181
【相关文献】
1.决策表中基于属性重要性的属性约简算法研究 [J], 汤伟;徐甜
2.基于区分矩阵和属性重要性的约简算法 [J], 王爱平;刘娟
3.一种新的基于属性重要性的粗糙集值约简算法 [J], 刘甲伟;栾爽
4.基于属性重要性的属性约简算法 [J], 吴静;邹海
5.基于属性重要性的相对属性约简算法 [J], 黄楠
因版权原因，仅展示原文概要，查看原文内容请购买。
基于属性关联度的启发式约简算法王杨【期刊名称】《计算机与数字工程》【年(卷),期】2012(040)004【摘要】属性约简是知识发现中的关键问题之一.为了有效地获取最小相对约简,该文基于Hu的区分矩阵,即以属性核为起点,通过向属性核不断添加重要程度最大的属性,同时利用属性之间的关联度,使处理数据的范围不断缩小来减少求约简的时间.该算法在计算量减少的同时能得到更简的结果并能得到所有相对约简,实例分析也验证了该算法的有效性.%Reduction of attributes is one of the key problems in the knowledge discovery. In order to achieve the minimal relative reduction, the paper appends the most significance of attributes to core of attributes from original set of core attributes based on the discemibili- ty matrix. And the paper can save some time of acquiring the least reduction making use of the association degree of attributes. The algorithm can obtain the more reductive result requiring less computing and get all of the relative reductions. Finally, the experimental results show that this algorithm is effective.【总页数】3页(P17-18,31)【作者】王杨【作者单位】辽宁石油化工大学计算机与通信工程学院抚顺 113001【正文语种】中文【中图分类】TP311【相关文献】1.基于模糊邻域粗糙集的启发式属性约简算法 [J], 任晓霞;薛凡2.一种基于知识粒度的启发式属性约简算法 [J], 马福民;张腾飞3.基于链表结构的启发式属性约简算法 [J], 梁宝华4.基于相容矩阵的启发式属性约简算法研究 [J], 赵天奇5.一种基于属性重要性的属性约简启发式算法 [J], 叶明全;胡学钢因版权原因，仅展示原文概要，查看原文内容请购买。
龙源期刊网 一种基于粗糙熵的信息系统属性约简算法作者：史进玲来源：《电脑知识与技术》2012年第24期摘要：在信息系统中，研究了知识的粗糙性，定义了一种粗糙熵度量方法，并证明了知识的粗糙熵随着划分的增大而单调增加的结论，给出了属性的重要性度量方法，在此基础上提出了一种基于粗糙熵的启发式属性约简算法。
实例验证表明，该算法能有效地从信息系统中获取最优属性约简。
关键词：信息系统；粗糙熵；属性重要度；属性约简中图分类号：TP312文献标识码：A文章编号：1009-3044(2012)24-5872-03An Attribute Reduction Algorithm Based on Rough Entropy in Information SystemSHI Jin-ling(International School of Education, Xuchang University, Xuchang 461000, China)Abstract：In information system, a rough entropy is defined by studying roughness of knowledge, then knowledge rough entropy’s mo? notonous increasing property with the increase of partition is proved. On this basis, attribute significance measure method is given and a heuristic reduction algorithm based on rough entropy is proposed. A detailed example is shown that the algorithm can effectively extract op? timal reduction.Key words: information system; rough entropy; attribute significance; attribute reduction粗糙集理论(Rough Set )是一种有效的从不精确、不完备与不一致数据的知识库中获取知识的数学理论[1-2]。
一种改进的启发式最优相对属性约简算法陶加云;李英顺;赵玉鑫【摘要】An improved heuristic optimal relative attribute reduction algorithm was put forward to solve the problem which had low reduction efficiency caused by the need of calculate distinguishable matrix and positive region in the rela?tive attribute reduction algorithm based on rough set theory. The decisive condition of relative attribute reduction was giv?en by introducing the definition of relative classification ability in attribute set. The improved relative attribute reduction algorithm of which was exported by the method as above not only can guarantee the conditional attributes are best, but al?so can improve the reduction efficiency. The results of the practical examples and the comparison experiments show high efficiency of this algorithm.%针对在传统的粗糙集理论相对属性约简算法中因需计算可区别矩阵和正区域而导致的约简效率低下这一问题,提出一种改进的启发式最优相对属性约简算法加以解决.通过引入属性集的相对分类能力的定义给出相对属性约简的判定条件,在此基础上导出的改进相对属性约简算法既能保证约简过后的条件属性是最优的,又能提高约简效率.实际算例结果以及对比实验体现了该算法的高效性.【期刊名称】《宜宾学院学报》【年(卷),期】2015(015)012【总页数】4页(P32-35)【关键词】粗糙集理论;改进最优相对属性约简;判定条件【作者】陶加云;李英顺;赵玉鑫【作者单位】沈阳工业大学信息科学与工程学院,辽宁沈阳110870;沈阳工业大学化工过程自动化学院,辽宁辽阳111003;沈阳工业大学化工过程自动化学院,辽宁辽阳111003【正文语种】中文【中图分类】TP18粗糙集理论诞生于20世纪80年代初期，是一种能有效分析和处理不精确、不完整信息的数据分析工具[1].该理论在近十多年来日益受到国内外专家学者的重视，对其研究也在不断加深，并且已经成功运用在机器学习、人工智能与知识工程、故障诊断、信息系统决策支持等领域[2-4].约简是粗糙集理论的核心内容之一，是粗糙集理论能否成功运用到工程实践中的关键，其主要内容是在保持知识库分类能力不变的前提下导出决策规则.对决策系统属性集的约简称为属性约简，而寻求到所有约简后的属性已被证明是一个NP-hard问题[5].高效的属性约简算法是粗糙集理论完成数据约简的基础和保障.文献[6]利用传统的基于可区别矩阵的相对属性约简算法对综合传动装置的故障数据进行约简，算例的结果中出现了两个约简值，虽然都能导出决策规则，但是可信度却受到影响，并且计算量大.文献[7]提出了一种改进的基于属性频率度的约简算法，该算法使得约简的计算量有所减少，但是不能保证求得的约简后的属性个数是最少的.在实际运用中所需要属性个数往往是越少越好，且计算量越小越好，这样便于得到精简的规则集，从而提高解决问题的效率.因此，文章通过引入属性集的相对分类能力的定义来给出相对属性约简的判定条件，在此基础上定义属性重要度，并将它作为改进的最优相对属性约简算法的启发式信息，以便于减小搜索空间，提高相对属性约简效率.实际算例结果证实了该算法不仅高效，而且能够保证约简后的属性个数是最少、最优的.定义1 设四元组信息表达系统其中U代表包含所有对象的非空有限集，被称为论域；R代表属性集，R=( ) r1,r2,r3,…,rm= C⋃D,C⋂D≠∅,C代表条件属性集，U代表决策属性集；V=⋃r∈RVr，Vr代表属性r的值域；f∶U×R→V为一全函数，它赋予每一对象对应的每一属性一个信息值.此时，称上述信息表达系统S为决策表.定义2 设信息表达系统A为属性集R的一个子集，亦即A⊆R,定义一不可分辨关系ind(A),且：定义3 设S中的集合U上任意一个不可分辨关系和任意一个子集X,定义X关于Q 的下、上近似集分别为：定义4 设P和T为定义在论域U上的两个等价关系簇，T的P正域记为POSP(T)，此时，定义5 设Ω和Θ为定义在论域U上的两个等价关系簇，设G⊆Ω,G为Ω的Θ约简当且仅当G为Ω的Θ独立子簇，并且满足POSG(Θ)= POSΩ(Θ)时，就称Ω的Θ约简为相对约简.2.1 属性集相对分类能力的引入粗糙集理论是在等价关系的基础上建立的，这些等价关系[8]对特定的数据空间进行划分.划分准则可以看作一种粗糙的知识，知识的粒度越大越粗糙，可用度相对而言也就越小，反之就越大.以下就等价关系分类能力这一观点，给出定义等价关系相对分类能力的表达方式.定义6 给定一相容决策系统，则条件属性集C相对于决策属性集D的分类能力记为M(U,C/D),且性质1：给定相容决策系统∀R⊆C,则POSC(U,D)=POSR(U,D)成立的充要条件为证明：因为 DS是相容决策系统，所以从而有 M(U,R)= M(U,R⋃D),亦即根据可得M(U,R)= M(U,R⋃D).因此,得证POSC(U,D)=POSR(U,D)成立的充要条件为设R⊆C,r∈R,结合上述定义6及其性质可推导出属性集R是条件属性集C关于决策属性集D的一个相对约简的充要条件是：①②对于任意的r∈R，都有证明：由R是条件属性集C关于决策属性集的一个约简可知假定存在r∈R,使得由上述性质可得：POSC(U,D)=POSR-{r}(U,D)这与R是条件属性集C关于决策属性集D的一个约简矛盾.因此，得证：对于∀r∈R,有：根据以及上述性质可得：POSC(U,D)=POSR(U,D)又由∀r∈R有可推导出∀r∈R有亦即∀r∈R有POSC(U ,D )≠POSR-{r}(U ,D).因此，得证：R是条件属性集C关于决策属性集D的一个相对约简.上述证明的充要条件即为相对属性约简的判定条件，是最优属性约简算法的基础.2.2 改进最优属性约简算法描述在传统的启发式相对属性约简算法的基础上引入了相对分类能力和属性重要度的定义，既可在一定的程度上减小计算量，又能保证约简过后的属性集是最精简的.算法的主要内容如下：输入：相容决策系统输出：相容决策系统DS的一个最优相对属性约简集.对算法中出现的部分符号的说明：（Ⅰ）Red：算法的输出结果；（Ⅱ） Div ||Red：论域U的划分，亦即（Ⅲ）Div：论域U的划分；（Ⅳ）SGF(a,S,D)：属性重要度.步骤1：步骤2：对于每一个c∈C，计算步骤3：设属性a∈S,S为C中的某一属性集，S⊆C, U1=U，将a按SGF(a,S,D)升序排列，并将排列结果记为步骤4：Fork=1;k＜|c|+1;k++；①若则有 Red=否则转向步骤4；②③若则转向步骤5；步骤5：令Div={U1}，其中U1=U；步骤6：对于属性集Red,从后往前对每个属性a进行判断，看它们是否可省，具体说明如下：①若则有Red=Red-{r}；②步骤7：输出最终的Red.2.3 算法的时间复杂度分析首先给出并证明如下性质：设一论域U,若则有证明：任意的且∀x,y∈P,有f(x ,S⋃T)=f(y ,S⋃T),因此又有 f(x,S)= f(y,S)和f(x,T)=f(y,T),即存在 Si⋂Tj使得P⊆Si⋂Tj.又知，有 f(x,Si⋃Tj)=f(y,Si⋃Tj),因此可得出P=Si⋂Tj.同理，对于任意的Si⋂Tj,存在使得 Si⋂Tj=P.综上可得证由上述改进最优属性约简算法可知，其步骤1-5的时间复杂度为O(|C ||U|2)，又由如上性质可以求得步骤6的时间复杂度为O(|C ||U|2)，因此，改进最优相对属性约简算法的总的时间复杂度为：O(|C ||U|2).本文以客户关系管理情况评价表的相关数据为例来对算法进行分析.选择30个比较典型的评价数据来作为样本数据，建立如表1所示的客户评价数据表.其中，条件属性C={c 1,c2,c3,c4,c5}={产品能力认知，管理水平评价，服务质量，客户情感，责任感表现} ，决策属性D为客户满意度.条件属性值1-5分别代表“差”“一般”“好”“很好”“最好”，决策属性值A-C分别代表“高”“较高”和“一般”.选用机器学习数据库中的客户评价数据集，分别利用改进最优相对属性约简算法和传统的启发式相对属性约简算法对表1中的数据进行了25次实验，本文所提算法的约简结果如表2所示.传统的启发式相对属性约简结果如表3所示.实验结果比较情况如表4所示.从表4中的数据可以明显看出，采用改进最优相对属性约简算法比统的启发式相对属性约简算法在快4.7s的同时，约简集较之也减少了一个.结果分析：由表2可以更直观地看出“服务质量”和“客服情感”都对“客户满意度”有重大影响，两者不可或缺，因此，这已是最精简的最优属性集.通过表2能够更快地完成数据分析，表明企业需要把“服务质量”和“客服情感”放在重要地位，体现了该算法在决策信息系统上的优点和适用性.由表3可以看出，传统的启发式相对属性约简算法得到的约简集中含有“产品认知能力”这一属性，然而从数据可以看出，该属性并不对客户满意度产生多少影响，换句话说，得到的相对属性约简集不是最优的.由表4可以看出，本文所提算法能够保证约简效率高于传统算法，体现了该算法约简效率高的优点.为保证相对属性约简的最优性和高效性，在导出相对属性约简判定条件的基础上定义了属性重要度，提出了一种启发式最优相对属性约简算法.该算法克服了传统的相对属性约简算法需要计算可区别矩阵、正区域以及析取合取计算量大的问题.实验证明，算法能够在相对较小的时间内完成相对属性约简，挖掘出有效信息，从而更好地反映知识表达系统的特性.【相关文献】[1]PAWLAKZ.Roughsets[J].InternationalJournalofComputerand InformationSciences,1982,11（11）:341-356.[2]裴小兵.粗糙集的知识约简研究[D].武汉：华中科技大学，2006. [3]成新文，陈国超，李琦.关于粗糙集的理论及应用研究[J].煤炭技术，2010（10）:198-200.[4]WONGSKM,ZIARKOW.Onoptimaldecisionrulesindecisiontable[J].BulletinofPolishAcademyofSciences,1985,33（11-12）: 693-696.[5]柳炽伟，景玉军，郭美华.基于故障树的DCT故障诊断专家系统的研究[J].机床与液压，2014,42（1）:169-172.[6]李英顺，姜双双，佟维妍，等.基于RST及FTA的综合传动装置故障诊断专家系统的应用研究[J].组合机床与自动化加工技术，2014（4）:60-63.[7]夏侯振宇，段隆振，衷尔英，等.一种改进的粗糙集约简算法及其应用[J].江西科学，2008,26（3）:379-382.[8]李玉龙，张亚光，毕聪聪.一种基于改进遗传算法的粗糙集属性约简算法[J].计算机与数字工程，2014（10）:1831-1834.。
一种新的启发式粗集决策表属性约简算法沈玮;赵佳宝【摘要】粗集理论通过对原始决策表的约简从而获取规则知识,其核心部分是属性约简.经过约简后的数据更有价值,更能准确地获取知识.文中提出了一种新的启发式属性约简算法,并给出了算法的详细步骤和具体的实验示例.该算法通过不一致计数和互信息增量的计算来衡量属性的重要性,避免了对属性之间随机组合情况的搜索,可以提高求解速度.实验结果表明,相比较于动态约简算法和标准遗传算法,所提出的算法获得的约简属性集更加简洁和高效.【期刊名称】《计算机技术与发展》【年(卷),期】2010(020)010【总页数】5页(P16-20)【关键词】粗集;属性约简;启发式【作者】沈玮;赵佳宝【作者单位】南京大学,工程管理学院,控制理论与系统工程系,江苏,南京,210093;南京大学,工程管理学院,控制理论与系统工程系,江苏,南京,210093【正文语种】中文【中图分类】TP301.60 引言波兰数学家Pawlak Z提出的Rough Set是一种新的处理不精确、不完全与不相容知识的数学方法[1,2]。
其目前正被广泛应用于人工智能、模式识别与智能信息处理等领域,并取得了一定的成果[3]。
属性约简是粗糙集理论及应用研究的重要内容之一[4],也是知识获取的关键步骤。
基于粗糙集的属性约简算法备受研究者的关注并已经取得了一定的成果[5～7]。
最简单有效的方法是对于包含强相关属性的离散属性数据集进行属性核的计算,得到的约简包含一个核和另外一些弱相关的属性,从而最后得到满意的属性约简结果。
从所有的属性子集里寻找最优的属性约简集是十分困难的任务,实际上,Wong S K 和Ziarko W已证明了寻找决策表的最小属性约简是NP-hard问题[8],而属性的组合爆炸是导致NP-hard的主要原因[9]。
为了得到决策信息系统中最合适的属性约简集合,文中提出了一个新的启发式属性约简算法。
1 粗糙集相关概念简介粗糙集理论的要点是将分类和知识联系在一起,并用等价类关系形式化表示分类。
概念格属性约简的启发式算法
吕跃进;李金海
【期刊名称】《计算机工程与应用》
【年(卷),期】2009(45)2
【摘要】概念格是知识处理与分析的一个有力的工具,在知识约简和数据挖掘方面有着重要的应用.该文首先从概念外延的角度·研究了合理刻画属性重要性的指标,并给出了概念格属性约简的判定定理,然后以这些指标作为启发式信息设计了一种新颖的概念格启发式属性约简算法,最后通过实例表明了该约简算法的可行性与有效性.
【总页数】4页(P154-157)
【作者】吕跃进;李金海
【作者单位】广西大学,数学与信息科学学院,南宁,530004;广西大学,数学与信息科学学院,南宁,530004
【正文语种】中文
【中图分类】TP301
【相关文献】
1.概念格的贴近度及基于贴近度的概念格属性约简算法 [J], 孟慧丽
2.基于矩阵的模糊-经典概念格属性约简 [J], 林艺东; 李进金; 张呈玲
3.面向对象概念格的属性约简方法 [J], 汪秋分; 李进金; 卞洪亚
4.基于OE-概念格的形式背景属性约简 [J], 张呈玲;李进金;林艺东
5.对象导出三支概念格的熵属性约简 [J], 吴荣;张文娟;李进金
因版权原因，仅展示原文概要，查看原文内容请购买。
一种广义决策保持的快速启发式属性约简算法
赵昱德
【期刊名称】《计算机科学与应用》
【年(卷),期】2024(14)2
【摘要】属性约简是粗糙集理论的重要概念之一,旨在获得一个可以保持原始信息系统分类能力的最小属性子集。
广义决策保持约简是粗糙集中的属性约简方法之一,其目标为维护决策系统中的决策结果,确保在约简过程中不丢失原始决策。
这意味着约简后的系统仍可正确地进行决策,而决策规则的有效性和决策能力得以保持。
传统的广义决策保持启发式属性约简算法注重算法的有效性,而算法的效率有待优化。
传统算法在计算广义决策保持相似度时需多次遍历每个对象的等价类与决策类,存在大量的重复计算。
为了克服这个问题,我们通过引入哈希表来存储每个对象的等价类与其广义决策,使得计算广义决策保持相似度时可针对计算对象直接得出结果而不是依次遍历,由此提出了广义决策保持的快速启发式属性约简算法。
最后,通过6组UCI数据集验证了本文提出算法的有效性与高效性。
【总页数】8页(P260-267)
【作者】赵昱德
【作者单位】烟台大学计算机与控制工程学院烟台
【正文语种】中文
【中图分类】TP3
【相关文献】
1.一种新的决策粗糙集启发式属性约简算法
2.决策域分布保持的启发式属性约简方法
3.一种新的启发式粗集决策表属性约简算法
4.一种序决策信息系统中的快速属性约简算法
因版权原因，仅展示原文概要，查看原文内容请购买。
一种新的启发式粗集决策表属性约简算法
沈玮;赵佳宝
【期刊名称】《计算机技术与发展》
【年(卷),期】2010(20)10
【摘要】粗集理论通过对原始决策表的约简从而获取规则知识,其核心部分是属性约简.经过约简后的数据更有价值,更能准确地获取知识.文中提出了一种新的启发式属性约简算法,并给出了算法的详细步骤和具体的实验示例.该算法通过不一致计数和互信息增量的计算来衡量属性的重要性,避免了对属性之间随机组合情况的搜索,可以提高求解速度.实验结果表明,相比较于动态约简算法和标准遗传算法,所提出的算法获得的约简属性集更加简洁和高效.
【总页数】5页(P16-20)
【作者】沈玮;赵佳宝
【作者单位】南京大学,工程管理学院,控制理论与系统工程系,江苏,南京,210093;南京大学,工程管理学院,控制理论与系统工程系,江苏,南京,210093
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.改进的粗集属性约简的启发式算法 [J], 李珊;肖怀铁;付强
2.基于布尔矩阵表示的粗集属性约简启发式算法 [J], 李龙星;运士伟;杨炳儒
3.一种新的决策粗糙集启发式属性约简算法 [J], 常红岩;蒙祖强
4.决策表最优特征子集的选择--基于粗集理论的启发式算法 [J], 潘韬;赵卫东;盛昭瀚
5.有约束指导的粗集决策表属性约简算法 [J], 郭庆强;李歧强;丁然
因版权原因，仅展示原文概要，查看原文内容请购买。
以准核为起点的启发式属性约简 陈红星;魏巍 【摘 要】核是属性约简中的必不可少的部分。通过对核中属性重要程度的差异进行分析，可以发现一些核属性相对于决策的重要度很小，这些属性一定程度上影响了基于约简结果构造的分类器的分类精度。通过将核中一些对决策贡献很小的属性去除，提出了准核的定义，并基于准核构造了一种新的启发式属性约简算法，利用该算法获得的约简中属性数量更少，基于这种约简构造的分类器分类精度更高，实验结果表明了算法的有效性。%Core is an essential component of attribute reduction. Though analyzing the significancy of every attribute in core, it is found that the significanfy of every attribute is different. The attributes with less siginicancy can affect the accuracy of classifier. Therefore, in this paper, Quasi-core is proposed by deleting the attributes with less significancy than most of attributes in core, and a new heuristic attribute reduction algorithm is designed based on the Quasi-core. Experimental result shows that the reduct with less attributes are obtained by the algorithm, and classifier constructed based the reduct has higher classifier accuracy.
ｌ 匐 化 属性重要性的启发式属性约简算法 Ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｔｈｅ ｈｅｕｒｉｓｔｉｃ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｐｒｏｐｅｒｔｉｅｓ 何英‘，何丹 ＨＥ Ｙｉｎｇ’．ＨＥ Ｄａｎ （１．南昌航空大学现代教育技术中心，南昌３３００６３；２．南昌航空大学信息中心，南昌３３００６３） 摘要：属性约简是Ｒｏｕｇｈ集理论的核心问题之一，为了更好地获得属性约简，本文构造了一种属性重 要性的度量公式，并在此基础上提出了一种以属性重要性为启发式信息的二进制可辨矩阵的 属性约简算法，解决了当二进制可辨识矩阵的属性频率相同的情况下的属性选取问题。最后 用实例表明，此方法是一种获得属性约简的简单而有效的方法。 关键词：属性约简；属性重要性；二进制可辨矩阵；Ｒｏｕｇｈ集 中图分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１ ００９—０１ ３４（２０１ １）２（上）一０１ ７３—０２ Ｄｏｉ：１ ０．３９６９／ｊ． ．１ ． １．２（）．＿ｉｓｓｎ ００９－０１ ３４ ２０１ Ｉ－５５
０引言 Ｒｏｕｇｈ集理论自８０年代初由波兰学者ｚ．Ｐａｗｌａｋ 提出以来，是一种迅速发展的既有理论又有应 用的研究领域…。粗糙集理论 是Ｐａｗｌａｋ等人提 出的一种处理不精确、不完全信息的新型数学工 具。由于二进制的可实现性，很多学者将其引入 属性约简算法中，文献【５，６］用二进制可辨矩阵设 计了基于正域的属性约简算法，但都没有解决当 二进制可辨矩阵列的属性频率出现次数相同的情 况下选取加入到约简中的顺序问题。本文在文献 ［５—７］的基础上，提出了以属性频率和属性关于Ｕ／Ｄ 正域之和为启发式信息的二进制可辨识矩阵列的 属性约简算法，解决了当二进制可辨识矩阵列的 属性频率相同的情况下的属性选取问题。 １属性约简基本概念 定义１一个信息系统ｓ，表示为ｓ＝（ｕ，Ａ，Ｖ，ｆ）， 其中Ｕ＝｛Ｘ ，Ｘ ，…，Ｘ ）是论域；Ａ是属性集合； Ｖ＝Ｕ ｖ ，ａ∈Ａ，Ｖａ表示属性的值域；ｆ－ＵｘＡ—Ｖ 是一个信息函数，对ｘ∈Ｕ，ａ∈Ａ，有ｆ（ｘ，ａ）∈ｖ。。 若Ａ可分为条件属性集Ｃ和决策属性集Ｄ，即Ａ ＝ＣＵＤ，ＣｎＤ＝ ，则该信息系统称为决策表。 定义２设Ｒ是一个等价关系族，ｒ∈Ｒ，如果 ＩＮＤ（Ｒ）＝ＩＮＤ（Ｒ一｛ｒ｝），则称ｒ在Ｒ中是可被约去的知 识：如果Ｐ＝Ｒ－Ｉｒ｝是独立的，则Ｐ是Ｒ中的一个约简。 定义３在信息系统Ｓ中，若Ｐ，Ｑ∈Ａ，则Ｑ的Ｐ正 域ＰＯＳＰ（Ｑ）定义为：
ＰＯＳＰ（Ｑ） ｘ 一
ｘ
其中Ｐ＿Ｘ为ｘ的Ｐ下近似。Ｑ的Ｐ正域是Ｕ中所有 根据分类Ｕ／Ｐ的信息可以准确地划分到关系Ｑ的等 价类中去的对象集合。 ２二进制可辨矩阵 】 定义４设决策表为Ｔ＝（Ｕ，Ｃ，Ｄ，Ｖ，ｆ），其中 Ｕ＝｛ｕｌ，ｕ２，…，ｕｎｌ，Ｃ＝｛ｃｌ，ｃ２，…，ｃｍ｝，Ｄ＝｛ｄ）则决策 表Ｔ相应的二进制可辨矩阵Ｍ 构造为：矩阵的每一 列对应一个条件属性，共有ｍ列，每一行对应一对 论域中的对象（ｕ ，ｕ ），有ｎ（ｎ一１）／２行。设矩阵中一元 素ｍ（（ｐＩｑ）－ｉＪ所在行对应的应对象对（ｕｐ，ｕ ），所在列对 应条件属Ｃｉ，则 ｝Ｊ女口果Ｃｉ（ ）≠ｃ （ｇ／ ） １ 则 一
这样得到的一个矩阵，称之为相应于决策表 Ｔ＝（Ｕ，Ｃ，Ｄ，Ｖ，ｆ）的二进制可辨矩阵。 命题ｌ若二进制可辨矩阵中某一行只有一个元 素为１其余元素均为０，则元素１所在列对应某个属 性，所有这样的属性构成信息系统的核或决策表的 相对核。若没有这样的行，则核或相对核为空。 ３属性重要性的度量方法 对于决策表Ｔ＝（Ｕ，Ｃ，Ｄ，Ｖ，ｆ）：用Ｐ（ｃ ｉ） （ｃｉ∈Ｃ，１≤ｉ≤ＩＣＩ）表示ｃｊ在二进制可辨识矩阵中的 属性频率；用ＭＡＸ（Ｐ（ｃ））表示二进制可辨识矩阵中 属性ｃ出现的最大频率；用ＮＭＡｘ表示二进制可辨
收稿日期：２０１０－－０８－２０ 基金项目：江西省省级教改课题项目（ＪＸＪＧ一１０—７—２７） 作者简介：何英（１９７７一），女，江西东乡人，讲师，硕士，研究方向为粗糙集，数据库。
第３３卷第２期２０１ １－２（上） ［１７３］ 务ｌ 訇 似 识矩阵中属性出现的频率等于最大频率的属性总 数，ＮＭＡＸ＝ｌ（ｃｉＩＰ（ｃｉ）＝ＭＡｘ（Ｐ（ｃ）），１≤ｉ≤ＩＣ…；条件 属性Ｃ ∈Ｃ（１≤ｉ ＩＣ１）的重要性可以用Ｃ 的属性频 率Ｐ（ｃｉ）和Ｕ／｛ｃｉ｝关于Ｕ／ＤｉＥＪ￥￣ＰＯＳＵ／｛ｃｉ｝（Ｕ／Ｄ）来度量， 用Ｇｃ 表示，则Ｇｃ 可通过公式１给出，如下所示。
￣Ｐ（ｃｉ）￣ＭＡＸ（Ｐ（ｃ）） … Ｇｏ，＝
｛１ 如果Ｐ（ｃｆ）＝＾ （Ｐ（ｃ））ｆＩＮＭＡｘ＝ｌ
【Ｉ＋ＰＯＳｕ／ｔｃ，Ｉ（Ｕ／Ｄ）如果尸（ｃ ）＝ＭＡＸ（Ｐ（ｃ））且ⅣＭ ≥２
４属性重要性的启发式属性约简算法 在二进制可辨矩阵中，对于那些只有一个元 素为１其余元素均为０的行，元素１所在列的属性一 定属于核，而对于那些有多个元素为１的行，在这 些元素为１所在的列中，那些所含１的个数最多的 列对应的属性虽未必是核属性，但具有很强的分 辨能力，因此这样的属性在形成约简，尤其是最 小约简的过程中具有重要地位。 算法二进制可辨矩阵属性重要性的启发式属 性约简。 输入：决策表Ｔ＝（ｕ，ｃ，Ｄ，Ｖ，ｆ） 输出：决策表Ｔ属性约简 １）根据给定的决策表Ｔ＝（ｕ，Ｃ，Ｄ，Ｖ，ｆ）产生二进 制可辨矩阵Ｍ，将Ｍ中全为１和０的行删除，得到新 的Ｍ 。 。置矩阵ＭＡ—Ｍ 。 ，用Ｒｅｄｕｃｔｉｏｎ表示属性 约简，初始值为Ｒｅｄｕｃｔｉｏｎ＝ 。 ２）对每一行，若该行只有一个元素为１，则 将该元素所对应的属性为核属性，并将该属性加 入到Ｒｅｄｕｃｔｉｏｎ，即Ｒｅｄｕｃｔｉｏｎ—Ｒｅｄｕｃｔｉｏｎ Ｕ｛Ｃｉ｝， 其中Ｃｊ∈Ｃ，１ ｉ≤ｌＣＩ。 ３）从ＭＡ中删除各行只有一个元素为１的行及 该行元素１所对应的列值为１的行，将得到的新矩 阵ＭＡ 再赋给ＭＡ。如果ＭＡ＝ ，则转到７），否 则到４）。 ４）将ＭＡ的各列纵向相加，并将结果存入相 应ｃｏｌ［ｃｉ】中，其中Ｃｉ∈Ｃ，１≤ｉ≤ｌＣｌ。 ５）用一维数组Ｇ【ＩｃＩ】表示属性的重要性， 初始值为Ｇ［ｃｉ］＝０，其中Ｃｉ∈Ｃ，１≤ｉ ＩＣＩ。根据 公式１计算属性重要性；在ＭＡ中将属性重要 性最大的属性Ｃ；列及ｃ 列上值为１的元素所对应 的行去掉：将得到的新矩阵再赋给ＭＡ，并将 Ｒｅｄｕｃｔｉｏｎ－－－Ｒｅｄｕｃｔｉｏｎ Ｕ｛Ｃｉ）。 ６）将ＭＡ中行全为１和０的行删除，将得到的 新矩阵再赋给ＭＡ。如果ＭＡ≠ ，则转到４）。
Ｋ１７４１ 第３３卷第２期２０１１－２（上）
４）输出一个约简Ｒｅｄｕｃｔｉｏｎ。 ５实例分析 表１中Ｃ＝｛ａ，ｂ，Ｃ，ｄ｝为条件属性，Ｄ＝｛ｅ）为决策 属性，Ａ＝Ｃ Ｕ Ｄ，对表１建立二进制可辨矩阵如表２ 所示。 表１决策表Ｔ＝（Ｕ，Ｃ，Ｄ，ｖ，０ Ｃ Ｄ Ｃ Ｄ （， Ｕ ｂ ｄ ６
１ ａｏ ｂｌ Ｃｏ ｄ１ ｅｏ ５ ａＩ ｂｌ Ｃｏ ｄｌ ｅｌ ２ ａｌ ｂ０ Ｃｏ ｄｌ ｅｌ ６ ａｌ ｂｌ ｅｌ ｄ０ ｅｏ ３ ａｏ ｂ０ ＣＩ ｄｏ ｅ０ ７ ａｏ ｂｌ Ｃｌ ｄｌ ｅＯ ４ ａｉ ｂ０ Ｃｌ ｄｌ ｅ２ 表２决策表Ｔ的二进制可辨矩阵 （Ｕｐ，Ｕｑ）ｌＡ ｂ （Ｕｐ，“口 ｌＡ ６ （ｕｐ，Ｕｑ）ｌＡ ６ （Ｉ，２） １ ｌ Ｏ ０ （２．４） ０ ０ １ ０ （３，７） ０ １ ０ （１，３） ０ ｌ ｌ １ （２．５） ０ ｌ ０ １ （４，５） ０ １ ｌ （１．４） １ ｌ ｌ ０ （２，６） Ｏ ｌ 】 ｌ （４，６） ０ ｌ ０ （Ｉ，５） ｌ ０ Ｏ ｌ （２．７） １ Ｉ ｌ ０ （４，７） １ ｌ Ｏ （１，６） ｌ ０ ｌ １ （３，４） １ ０ ０ １ （５，６） ０ ０ ｌ （１，７） Ｏ ０ ｌ Ｏ （３，５） ｌ ｌ ｌ ０ （５，７） ｌ ０ ｌ （２，３） ｌ ０ １ ｌ ｐ，６） ｌ ｌ ０ ０ （６，７） １ Ｏ ０
将表２中去掉（１，７）、（２，４）及（５，６）三行，并将属 性Ｃ中为１的行去掉，得表３。 表３化简后的二进制可辨矩阵 （ｕｐ，ｕｑ）￣Ａ ａ ６ ｄ （Ｕｐ．ｕｑ）ＩＡ ａ ６ （１，２） １ １ Ｏ （３．７） ０ １ （１，５） １ ０ １ （４，６） Ｏ １ （２，５） ０ １ １ （４，７） １ １ （３．４） １ ０ １ （６，７） １ Ｏ （３，６） １ １ ０
表３中ａ，ｂ，ｄ各列的属性频率都为６，根据公式 （１）计算属性的重要性，计算过程如下： Ｕ／｛ｅ｝＝｛Ｙｌ，Ｙ２，Ｙ３），ＹＩ＝（１，３，６，７），ＹＺ－－（２，５），Ｙ３＝＝《＿４）；Ｕ／ ｛ａ｝＝｛Ｘｌａ，Ｘ２ａ｝，Ｘｌａ＝（１，３，７），Ｘ２ａ＝（２，４，５，６） Ｕ／｛ｂ｝＝｛Ｘｌｂ，Ｘ２ｂ｝，Ｘｌｂ＝（１，５，６，７），Ｘ２ｂ＝（２，３，４）； Ｕ／｛ｄ｝＝｛Ｘｌｄ，Ｘ２ｄ｝，Ｘ１ｄ＝（１，２，４，５，７），Ｘ２ｄ＝（３，６） 由以上公式可得：Ｇ［ａ］＝１＋３／４＝１．７５，Ｇ［ｂ］＝１＋０＝ １，Ｇ［ｄ］＝ｌ＋２／４＝１．５。可知ａ的属性的重要性最大， ￣Ｒｅｄｕｃｔｉｏｎ＝｛ａ，Ｃ｝。将表３中ａ列及ａ列值为１的行去 掉，再将行都为１的行删除，得到的表为空，因此 Ｒｅｄｕｃｔｉｏｎ＝｛ａ，ｃ）为最后这个决策表的约简集。
６复杂度分析 设决策表中有ｍ个条件属性，ｎ个对象，在最 坏情况下，构造二进制可辨矩阵需要比较ｍｎ（ｎ． １）／２次，复杂度为Ｏ（ｍｎ ）；根据文献【９】的计算正域
