第11卷第1期 智能系统学报 Vol.11 No.1 2016年2月 CAAI Transactions on Intelligent Systems Feh.2016 D0I:10.11992/is.201506029 网络出版地址：htp:/www.cmki.net/kcms/detail/23.1538.TP.20151229.0837.020.html 基于知识粒度的不完备决策表的属性约简算法 乔丽娟，2，徐章艳2，谢小军12，朱金虎，2，陈晓飞2，李娟 (1.广西师范大学广西多源信息挖掘与安全重点实验室，广西桂林541004：2.广西师范大学计算机科学与信息工 程学院，广西桂林541004) 摘要：知识粒度是属性约简的有效方法，但对于大型的决策表，计算知识粒度过于费时，算法效率不高。在引入粒 度差别矩阵后，设计了一个计算粒度差别矩阵中条件属性出现频率的函数，有效地降低粒度差别矩阵的存储空间， 根据此函数设计了一个高效属性约简算法。新算法使得时间复杂度与空间复杂度都降为O(K1C1IU1)(其中 K=max{ITc(x)I,xeU}和O(IU1)。最后通过实例仿真说明了此算法的高效性和可行性。 关键词：属性约简：知识粒度：不完全决策表：条件属性频率：差别矩阵：启发信息 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)01-0129-07 中文引用格式：乔丽娟，徐章艳，谢小军，等.基于知识粒度的不完备决策表的属性约简算法[J].智能系统学报，2016,11(1)：129 135. 英文引用格式：QIAO Lijuan,XU Zhangyan,XIE Xiaojun,etal.Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation[J].CAAI Transactions on Intelligent Systems,2016,11(1):129-135. Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation QIAO Lijuan'.2,XU Zhangyan'.2,XIE Xiaojun'.2,ZHU Jinhu'.2,CHEN Xiaofei2,LI Juan 2 (1.Guangxi Key Laboratory of Multi-source Information Mining Security,Guangxi Normal University,Guilin 541004,China; 2.College of Computer Science and Information Technology,Guangxi Normal University,Guilin 541004,China) Abstract:The use of knowledge granularity is an effective attribute reduction approach.But for a large decision ta- ble,computing knowledge granularity is so time-consuming that the algorithm is not efficient for practical use.After the introduction of the discernibility matrix of granularity,a function was designed for calculating the occurrence frequency of condition attributes in the matrix.In this paper,we design an efficient attribute reduction algorithm based on the granularity discernibility matrix.The new algorithm reduces the time and space complexities to 0(KI CIIUI)(K=maxTe(x)1,U)and 0(IUI),respectively.The results from our simulation example verify that the proposed algorithm is feasible and highly efficient. Keywords:attribute reduction;knowledge granularity;incomplete decision table;condition attribute frequency; discernibility matrix;heuristic information 波兰的数学家Pawlak在20世纪80年代提出 粗糙集理论的重要研究内容，已被广大学者所研究， 的粗糙集是一种新型的用来处理不完全、不精确与 提出了围绕完备决策表的属性约简算法，但是现实 不相容的数学工具和理论2]。经过了30多年的研 生活中的数据往往存在误差，缺失及多源等特征。 究和发展，粗糙集理论已在知识发现、数据挖掘、模 如何对不完备决策表进行直接处理，已成为粗糙集 式识别等领域得到了大量应用34。属性约简作为 理论的一个研究热点[4。近年来针对不完备决策 表的研究也取得了显著的进步，已有学者提出很多 收稿日期：2015-06-16.网络出版日期：2015-12-29. 基金项目：国家自然科学基金资助项目(61262004,61363034,60963008)： 有效的不完备决策表属性约简算法[s。知识粒 广西自然科学基金资助项目(2011 GXNSFA018163):大学生 创新资助项目(201410602099). 度[2]作为粗糙集理论中度量属性约简的重要方 通信作者：乔丽娟.E-mail:347671379@qg-com. 法之一，被广泛运用于不完备属性约简算法。文献
第 １１ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．１ ２０１６ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０６０２９ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５１２２９．０８３７．０２０．ｈｔｍｌ 基于知识粒度的不完备决策表的属性约简算法 乔丽娟１， ２ ，徐章艳１， ２ ，谢小军１， ２ ，朱金虎１， ２ ，陈晓飞２ ，李娟２ （１．广西师范大学 广西多源信息挖掘与安全重点实验室，广西 桂林 ５４１００４； ２．广西师范大学 计算机科学与信息工 程学院，广西 桂林 ５４１００４） 摘 要：知识粒度是属性约简的有效方法，但对于大型的决策表，计算知识粒度过于费时，算法效率不高。 在引入粒 度差别矩阵后，设计了一个计算粒度差别矩阵中条件属性出现频率的函数，有效地降低粒度差别矩阵的存储空间， 根据此函数设计了一个高效属性约简算法。 新算法使得时间复杂度与空间复杂度都降为 Ｏ（Ｋ ｜ Ｃ ｜ ｜ Ｕ ｜ ） （其中 Ｋ＝ｍａｘ｛ ｜ Ｔｃ（ｘｉ） ｜ ， ｘｉ∈Ｕ｝和 Ｏ（ ｜Ｕ｜ ）。 最后通过实例仿真说明了此算法的高效性和可行性。 关键词：属性约简；知识粒度；不完全决策表；条件属性频率；差别矩阵；启发信息 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０１⁃０１２９⁃０７ 中文引用格式：乔丽娟，徐章艳，谢小军，等．基于知识粒度的不完备决策表的属性约简算法［ Ｊ］． 智能系统学报， ２０１６， １１（１）： １２９⁃ １３５． 英文引用格式：ＱＩＡＯ Ｌｉｊｕａｎ， ＸＵ Ｚｈａｎｇｙａｎ， ＸＩＥ Ｘｉａｏｊｕｎ，ｅｔ ａｌ． Ｅｆｆｉｃｉｅｎｔ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ｂａｓｅｄ ｏｎ ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕｌａｔｉｏｎ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（１）： １２９⁃１３５． Ｅｆｆｉｃｉｅｎｔ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ｂａｓｅｄ ｏｎ ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕｌａｔｉｏｎ ＱＩＡＯ Ｌｉｊｕａｎ １， ２ ， ＸＵ Ｚｈａｎｇｙａｎ １， ２ ， ＸＩＥ Ｘｉａｏｊｕｎ １， ２ ， ＺＨＵ Ｊｉｎｈｕ １， ２ ， ＣＨＥＮ Ｘｉａｏｆｅｉ ２ ， ＬＩ Ｊｕａｎ ２ （１．Ｇｕａｎｇｘｉ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｍｕｌｔｉ⁃ｓｏｕｒｃｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｍｉｎｉｎｇ ＆ Ｓｅｃｕｒｉｔｙ， Ｇｕａｎｇｘｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｇｕｉｌｉｎ ５４１００４， Ｃｈｉｎａ； ２． Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｇｕａｎｇｘｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｇｕｉｌｉｎ ５４１００４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｕｓｅ ｏｆ ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕｌａｒｉｔｙ ｉｓ ａｎ ｅｆｆｅｃｔｉｖｅ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｐｐｒｏａｃｈ． Ｂｕｔ ｆｏｒ ａ ｌａｒｇｅ ｄｅｃｉｓｉｏｎ ｔａ⁃ ｂｌｅ， ｃｏｍｐｕｔｉｎｇ ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕｌａｒｉｔｙ ｉｓ ｓｏ ｔｉｍｅ⁃ｃｏｎｓｕｍｉｎｇ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｎｏｔ ｅｆｆｉｃｉｅｎｔ ｆｏｒ ｐｒａｃｔｉｃａｌ ｕｓｅ．Ａｆｔｅｒ ｔｈｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ ｔｈｅ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ ｏｆ ｇｒａｎｕｌａｒｉｔｙ， ａ ｆｕｎｃｔｉｏｎ ｗａｓ ｄｅｓｉｇｎｅｄ ｆｏｒ ｃａｌｃｕｌａｔｉｎｇ ｔｈｅ ｏｃｃｕｒｒｅｎｃｅ ｆｒｅｑｕｅｎｃｙ ｏｆ ｃｏｎｄｉｔｉｏｎ ａｔｔｒｉｂｕｔｅｓ ｉｎ ｔｈｅ ｍａｔｒｉｘ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｄｅｓｉｇｎ ａｎ ｅｆｆｉｃｉｅｎｔ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｇｒａｎｕｌａｒｉｔｙ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ． Ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｒｅｄｕｃｅｓ ｔｈｅ ｔｉｍｅ ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｉｅｓ ｔｏ Ｏ（Ｋ ｜ Ｃ ｜ ｜Ｕ｜ ） （Ｋ ＝ｍａｘ｛ ｜ Ｔｃ（ｘｉ） ｜ ， ｘｉ∈Ｕ｝） ａｎｄ Ｏ（ ｜Ｕ｜ ）， ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｔｈｅ ｒｅｓｕｌｔｓ ｆｒｏｍ ｏｕｒ ｓｉｍｕｌａｔｉｏｎ ｅｘａｍｐｌｅ ｖｅｒｉｆｙ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｓ ｆｅａｓｉｂｌｅ ａｎｄ ｈｉｇｈｌｙ ｅｆｆｉｃｉｅｎｔ． Ｋｅｙｗｏｒｄｓ：ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ； ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕｌａｒｉｔｙ； ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ； ｃｏｎｄｉｔｉｏｎ ａｔｔｒｉｂｕｔｅ ｆｒｅｑｕｅｎｃｙ； ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ； ｈｅｕｒｉｓｔｉｃ ｉｎｆｏｒｍａｔｉｏｎ 收稿日期：２０１５⁃０６⁃１６． 网络出版日期：２０１５⁃１２⁃２９． 基金项目：国家自然科学基金资助项目（６１２６２００４，６１３６３０３４，６０９６３００８）； 广西自然科学基金资助项目（ ２０１１ＧＸＮＳＦＡ０１８１６３）；大学生 创新资助项目（２０１４１０６０２０９９）． 通信作者：乔丽娟． Ｅ⁃ｍａｉｌ：３４７６７１３７９＠ ｑｑ．ｃｏｍ． 波兰的数学家 Ｐａｗｌａｋ 在 ２０ 世纪 ８０ 年代提出 的粗糙集是一种新型的用来处理不完全、不精确与 不相容的数学工具和理论［１⁃２］ 。 经过了 ３０ 多年的研 究和发展，粗糙集理论已在知识发现、数据挖掘、模 式识别等领域得到了大量应用［３⁃４］ 。 属性约简作为 粗糙集理论的重要研究内容，已被广大学者所研究， 提出了围绕完备决策表的属性约简算法，但是现实 生活中的数据往往存在误差，缺失及多源等特征。 如何对不完备决策表进行直接处理，已成为粗糙集 理论的一个研究热点［４］ 。 近年来针对不完备决策 表的研究也取得了显著的进步，已有学者提出很多 有效的不完备决策表属性约简算法［５⁃１１］ 。 知识粒 度［１２⁃１３］作为粗糙集理论中度量属性约简的重要方 法之一，被广泛运用于不完备属性约简算法。 文献
·130· 智能系统学报 第11卷 [5]以属性重要性为启发信息，设计了一个基于知 定义316在不完备决策表S=(U,C,D,V,f) 识粒度的属性约简算法[)：文献[6]通过不断向核 中，知识BCC的知识粒度定义为GD(B)= 属性集中添加属性的方法，设计出一种基于相对知 识粒度的不完备决策表属性约简算法[6]：文献[7] ∑1T(x)1.其中U={x1,x…,x,1KI表 定义了一个粒度差别矩阵，进而设计了基于知识粒 示集合X的基数.显然有CD(☑)=0。 度的不完备决策表的属性约简算法[)，其时间复杂 性质16]设S=(U,C,D,V,)是一个不完备 度为max{O(1C121U11UI),0(1K11C1U1)},其 信息系统，知识BCC的知识粒度定义为GD(B),则 中K=max{ITc(x:)1,x:∈U},其空间复杂度为 1/IU川≤GD(B)≤1。 max{O(1C11U11UI),O(1U1)};文献[8]给出了 性质21]设S=(U,C,D,V,)是一个不完备 一个计算条件属性频率的公式，设计一个基于知识 信息系统，其中P,QCC,如果Hi∈{1,2，…，IU1} 粒度的属性约简算法[8)；文献[9]设计了一种基于 有T(x:)CT(x),则GD(P)≤GD(Q)。 对象矩阵的属性约简算法[9]：文献[11]提出简化差 知识粒度可以描述知识的区分能力，知识粒度 别矩阵定义，设计了一种快速的属性约简算法[川： 越小，其区分能力越强，反之区分能力越弱) 文献[12]中根据区分对象对集的思想，设计了基于 定义4)在不完备决策表S=(U,C,D,V,f) 正区域的属性约简算法[四：文献[13]根据粒计算的 中，知识B(BCC)是C关于D的一个知识粒度的 思想构建了粒矩阵，在此基础上，设计了属性约简算 属性约简，当且仅当B满足条件： 法。文献[14]在粒计算属性约简算法的基础上进 1)GD(B)=GD(C); 行了改进，得到一个新的算法。上述算法大多因为 2)Hb∈B→GD((B-{b}))≠GD(C). 要多次计算知识粒度，导致计算效率都不太理想，为 定义51在不完备决策表S=(U,C,D,V,f) 此设计出基于知识粒度的高效属性约简算法具有非 中，HBCC,U/D={D1,D2,…,Dx}表示由决策属性 常重要的现实意义[]。 集D对论域U的划分，称POSc(D)=UC_(D:) D:EU/D 差别矩阵作为粗糙集理论的重要技术之一，被 为C关于D的正区域，设条件属性对论域的划分为 广泛应用，但是求解差别矩阵费时，本文引入了基于 U/C=I[xa]e,[x2],,[x],U=xI[x]. 粒度的差别矩阵，利用条件属性在区分对象时出现 POSc(D),U=U- 频率的属性约简思想，设计一个基于粒度差别矩阵 计算属性频率的启发函数。 2粒度差别矩阵相关概念 1粗糙集基本概念 定义6 设在一个不完备决策表 S=(U,C,D,V)中，U=UUUes,定义粒度差别矩 定义1)五元组S=(U,C,D,V,)是一个不 阵M=(m(i,),其元素定义如下： 完备决策表，其中U={x1,x2,…,xn}表示对象的非 [{cIc}eC,fx,c)≠*Af八x,c)≠*A 空有限集合，称为论域；C={c1,C2,…,cm}表示条件 f(x:,c)≠fx,c)fx,D)≠f八x,D) 属性的非空有限集合：D表示决策属性的非空有限 集合，且CnD=O;V=UV.,V.是属性a的值域； 且x:和x一个在U,一个在U中； m(i,j)= acCUD f:UXCUD-→V是一个信息函数，它对一个对象的每 f(x,c)≠*Afx,c)≠*A 一个属性赋予一个信息值，即VaeCUD,xeU,有 f(x,c)≠f八，ce)且x:,x在U中} fx,a)∈Vao 0:其他 在五元组中，如果至少有一个属性a∈C,使得 式中：k=1,2,…,ro V。包含空值（用*表示），即至少有一个属性a∈U, 定义7】设M=(m(i,j))为不完备决策表 存在一个a∈U,使得f(x,a)=*,称之为不完备决 S=(U,C,D,V,f)的粒度差别矩阵，HBCC,若B满 策表。 足： 定义2)在不完备决策表s=(U,C,D,V,) 1)H☑≠m(i,j)∈M,有Bnm(i,j)≠0： 中，令BCC,定义U上的容差关系T(B)为 2)Ha∈B,B'=B-a均不满足(1)。 T(B)=(x,y)EUXUIYbEBI ,f(x,b)=f(y,b)V 则称B是C关于D的一个属性约简，此约简记 f(x,b)=*Vf八y,b)=*}。用T(x)表示在B中与 为基于粒度差别矩阵的属性约简。 x具有容差关系的全体对象集{y∈UI(x,y)∈ 定理1在不完备决策表S=(U,C,D,V,f)中， T(B)}。 有Rc=UR1alo
［５］以属性重要性为启发信息，设计了一个基于知 识粒度的属性约简算法［５］ ；文献［６］通过不断向核 属性集中添加属性的方法，设计出一种基于相对知 识粒度的不完备决策表属性约简算法［６］ ；文献［７］ 定义了一个粒度差别矩阵，进而设计了基于知识粒 度的不完备决策表的属性约简算法［７］ ，其时间复杂 度为 ｍａｘ｛Ｏ（ ｜ Ｃ ｜ ２ ｜ Ｕ ｜ ｜ Ｕｐｏｓ ｜ ），Ｏ（ ｜ Ｋ ｜ ｜ Ｃ ｜ Ｕ ｜ ）｝，其 中 Ｋ ＝ ｍａｘ ｛ ｜ ＴＣ （ ｘｉ ） ｜ ， ｘｉ ∈Ｕ｝，其空间复杂度为 ｍａｘ｛Ｏ（ ｜ Ｃ ｜ ｜Ｕ｜ ｜Ｕｐｏｓ ｜ ），Ｏ（ ｜ Ｕ｜ ）｝；文献［８］给出了 一个计算条件属性频率的公式，设计一个基于知识 粒度的属性约简算法［８］ ；文献［９］ 设计了一种基于 对象矩阵的属性约简算法［９］ ；文献［１１］提出简化差 别矩阵定义，设计了一种快速的属性约简算法［１１］ ； 文献［１２］中根据区分对象对集的思想，设计了基于 正区域的属性约简算法［１２］ ；文献［１３］根据粒计算的 思想构建了粒矩阵，在此基础上，设计了属性约简算 法。 文献［１４］在粒计算属性约简算法的基础上进 行了改进，得到一个新的算法。 上述算法大多因为 要多次计算知识粒度，导致计算效率都不太理想，为 此设计出基于知识粒度的高效属性约简算法具有非 常重要的现实意义［５］ 。 差别矩阵作为粗糙集理论的重要技术之一，被 广泛应用，但是求解差别矩阵费时，本文引入了基于 粒度的差别矩阵，利用条件属性在区分对象时出现 频率的属性约简思想，设计一个基于粒度差别矩阵 计算属性频率的启发函数。 １ 粗糙集基本概念 定义 １ ［３］ 五元组 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ）是一个不 完备决策表，其中 Ｕ ＝ ｛ ｘ１ ，ｘ２ ，…，ｘｎ ｝表示对象的非 空有限集合，称为论域；Ｃ ＝ ｛ｃ１ ，ｃ２ ，…，ｃｍ ｝表示条件 属性的非空有限集合；Ｄ 表示决策属性的非空有限 集合，且 Ｃ∩Ｄ＝⌀；Ｖ ＝ ∪ａ∈Ｃ∪Ｄ Ｖａ ，Ｖａ 是属性 ａ 的值域； ｆ：Ｕ×Ｃ∪Ｄ→Ｖ 是一个信息函数，它对一个对象的每 一个属性赋予一个信息值，即∀ａ∈Ｃ∪Ｄ，ｘ∈Ｕ，有 ｆ（ｘ，ａ）∈Ｖａ 。 在五元组中，如果至少有一个属性 ａ∈Ｃ，使得 Ｖａ 包含空值（用∗表示），即至少有一个属性 ａ∈Ｕ， 存在一个 ａ∈Ｕ，使得 ｆ（ ｘ，ａ） ＝ ∗，称之为不完备决 策表。 定义 ２ ［３］ 在不完备决策表 ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ） 中， 令 Ｂ ⊆ Ｃ， 定 义 Ｕ 上 的 容 差 关 系 Ｔ （ Ｂ） 为 Ｔ（Ｂ）＝ ｛（ｘ，ｙ）∈Ｕ×Ｕ｜ ∀ｂ∈Ｂ｝，ｆ（ｘ，ｂ）＝ ｆ（ｙ，ｂ）∨ ｆ（ｘ，ｂ）＝ ∗∨ｆ（ｙ，ｂ）＝ ∗｝。 用 ＴＢ（ｘ）表示在 Ｂ 中与 ｘ 具有容差关系的全体对象集 ｛ ｙ ∈ Ｕ ｜ （ ｘ， ｙ） ∈ Ｔ（Ｂ）｝。 定义 ３ ［１６］ 在不完备决策表 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ） 中 ， 知 识 Ｂ ⊆ Ｃ 的 知 识 粒 度 定 义 为 ＧＤ（Ｂ） ＝ １ ｜ Ｕ ｜ ２∑ ｎ ｉ ＝ １ ｜ ＴＢ（ｘｉ） ｜ ． 其中 Ｕ＝ ｛ｘ１ ，ｘ２ ，…，ｘｎ ｝， ｜ Ｘ ｜表 示集合 Ｘ 的基数． 显然有 ＣＤ（⌀）＝ ０。 性质 １ ［１６］ 设 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ）是一个不完备 信息系统，知识 Ｂ⊆Ｃ 的知识粒度定义为 ＧＤ（Ｂ），则 １ ／ ｜Ｕ｜≤ＧＤ（Ｂ）≤１。 性质 ２ ［１６］ 设 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ）是一个不完备 信息系统，其中 Ｐ，Ｑ⊆Ｃ，如果∀ｉ∈｛１，２，…， ｜Ｕ｜ ｝ 有 ＴＰ（ｘｉ）⊆ＴＱ（ｘｉ），则 ＧＤ（Ｐ）≤ＧＤ（Ｑ）。 知识粒度可以描述知识的区分能力，知识粒度 越小，其区分能力越强，反之区分能力越弱［５］ 。 定义 ４ ［５］ 在不完备决策表 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ） 中 ， 知识 Ｂ（Ｂ⊆Ｃ） 是 Ｃ 关于 Ｄ 的一个知识粒度的 属性约简，当且仅当 Ｂ 满足条件： １）ＧＤ（Ｂ）＝ ＧＤ（Ｃ）； ２）∀ｂ∈Ｂ⇒ＧＤ（（Ｂ－｛ｂ｝））≠ＧＤ（Ｃ）。 定义 ５ ［７］ 在不完备决策表 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ） 中，∀Ｂ⊆Ｃ，Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，…，ＤＫ ｝表示由决策属性 集 Ｄ 对论域 Ｕ 的划分， 称 ＰＯＳＣ（Ｄ） ＝ ∪Ｄｉ∈Ｕ／ Ｄ Ｃ＿（Ｄｉ） 为 Ｃ 关于 Ｄ 的正区域，设条件属性对论域的划分为 Ｕ／ Ｃ ＝ ｛［ｘｉ１ ］ｃ，［ｘｉ２ ］ｃ，…，［ｘｉｋ］ｃ｝，Ｕｐｏｓ ＝ ｛ｘｉｊ ｜ ［ｘｉｊ］ｃ⊆ ＰＯＳＣ（Ｄ）｝，Ｕｎｅｇ ＝Ｕ－Ｕｐｏｓ。 ２ 粒度差别矩阵相关概念 定 义 ６ ［１１］ 设 在 一 个 不 完 备 决 策 表 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ）中，Ｕ＝Ｕｐｏｓ∪Ｕｎｅｇ，定义粒度差别矩 阵 Ｍ＝ （ｍ（ｉ，ｊ）），其元素定义如下： ｍ（ｉ，ｊ） ＝ ｛ｃｋ ｜ ｃｋ｝∈ Ｃ， ｆ（ｘｉ，ｃｋ） ≠ ∗∧ ｆ（ｘｊ，ｃｋ） ≠∗∧ ｆ（ｘｉ，ｃｋ） ≠ ｆ（ｘｊ，ｃｋ），ｆ（ｘｉ，Ｄ） ≠ ｆ（ｘｊ，Ｄ） 且 ｘｉ 和 ｘｊ 一个在 Ｕｐｏｓ，一个在 Ｕｎｅｇ 中； ｆ（ｘｉ，ｃｋ） ≠ ∗ ∧ ｆ（ｘｊ，ｃｋ） ≠ ∗ ∧ ｆ（ｘｉ，ｃｋ） ≠ ｆ（ｘｊ，ｃｋ） 且 ｘｉ，ｘｊ 在 Ｕｐｏｓ 中｝ ⌀；其他 ì î í ï ï ï ï ï ï ï ï 式中：ｋ ＝ １，２，…，ｒ。 定义 ７ ［７］ 设 Ｍ ＝ （ｍ（ ｉ，ｊ）） 为不完备决策表 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ）的粒度差别矩阵，∀Ｂ⊆Ｃ，若 Ｂ 满 足： １）∀⌀≠ｍ（ｉ，ｊ）∈Ｍ，有 Ｂ∩ｍ（ｉ，ｊ）≠⌀； ２）∀ａ∈Ｂ，Ｂ′＝Ｂ－｛ａ｝均不满足（１）。 则称 Ｂ 是 Ｃ 关于 Ｄ 的一个属性约简，此约简记 为基于粒度差别矩阵的属性约简。 定理 １ 在不完备决策表Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ）中， 有 ＲＣ ＝ ∪ａ∈Ｃ Ｒ｛ａ｝ 。 ·１３０· 智 能 系 统 学 报 第 １１ 卷
第1期 乔丽娟，等：基于知识粒度的不完备决策表的属性约简算法 ·131· 证明由定义1知：命题显然成立。 证明由粒度差别矩阵的定义知，计算A,/a} 定理2】基于知识粒度的属性约简定义与基 ={A1,A2,…,At}产生的条件属性频率，可分两部 于粒度差别矩阵的属性约简定义是等价的。 分计算，一种是对象都在U中；另一种是一个在 定理2说明基于知识粒度的属性约简可以转化 U中，而另一个在U中的。 到粒度差别矩阵上进行。 1)若两个对象都在U中，由划分的定义知，在 针对不完备决策表，文献[7]中给出了一个基 同一个划分集合里的两个对象值相等，即只有不同 于粒度差别矩阵的属性约简算法，其时间复杂度为 划分集合里才有可能产生有效区分对象的条件属 max{O(IC121UIIU1),O(K1U1ICI)}。算法对 性。则只有不同划分集合的U之间才能产生条件 粒度差别矩阵进行遍历，若只包含一个条件属性就 属性频率；若两个对象都在U中，产生的条件属性 将其放入属性约简中，并去掉差别矩阵中任何含有 该条件属性的差别元素，直至差别矩阵为空。该算 频率为N,二，品，Pos,Po,任意两个划分集合都可 产生，因为在正域之间产生的差别矩阵的元素是对 法虽然有效降低了时间复杂度，但是构造粒度差别 称的，故条件属性频率为2N1。 矩阵仍然需要占用大量的空间，对于处理大型数据 2)若一个对象在U中，另一个对象在U中， 集仍然具有一定的难度。 由划分的定义知，同属一个集合里的两个对象值相 经分析，算法中在粒度差别矩阵中出现的条件 等，即只有不同划分集合里才有可能产生条件属性 属性才是能区分对象的条件属性，由于构造粒度差 别矩阵耗费空间，参考文献[16]的方法，设计一种 频率，且U和U之间要求决策值不同，故需要对 计算粒度差别矩阵中含有的条件属性频率的函数， 每个划分集合里属于U的集合对D划分，同时属 于U的集合也对D划分。所以，Neg/D划分集合 然后给出计算该函数的快速算法，无须构造粒度差 别矩阵就可以将其中能有效区分对象的条件属性找 里每个集合与pos,/D划分集合里对于决策属性在 不同划分集合里就能产生条件属性频率。 出，以降低算法的时间和空间复杂度。 为了方便叙述，假设将A:{b}所有集合中属于 3计算属性频率的启发函数 正域的所有集合对D划分pos,/D存放在一个矩阵 中，矩阵的行表示每一个非空集合对D的划分，矩 定理3在决策表S=(U,C,D,V,)中，BCC, 阵的列表示决策值相同的集合，生成的矩阵为 U/B={A1,A2,…,A},A/{a}={Aa,A2,…,A法}， Ag=pos,UNeg,U=UUU,其中pos,=AgnU Du Du DiDm Neg=Ag∩pos,/D={Da,Da,…,Dn},Neg/D= D2 …Dg…Dm 1D,D,,D。令=lps/D1=是m1D,1 D= Da (4) Ipos,I,则所有集合中属于正域的集合对D划分 D Dap pos/D总和为S=,三S=,名1posl,所有集合中属 于正域的所有集合对D划分pos,/D中决策值相同 Da Da DADA 集合总数为T=,品D。 同理，将A:{b}所有集合中属于负域的所有集 合对D划分Neg/D存放在另一个矩阵中，生成的 根据定义6，粒度差别矩阵中包含的条件属性 可由两部分产生，设对象都在U里产生的条件属 矩阵为 性的个数为N,则 D DD N,=∑pos;pos9 (1) 1i<j运k Da D2D 两个对象一个在U中，另一个在U中，产生 D= (5) 的条件属性频率为N2,则 D … D Da V2= D(S-S:-T;+Di) (2) 1写i≤k,1写0 计算条件属性的频率函数1F(U,a)1如下： D… Dy … Fa(U,a)=￡(2N+W) 从这两个矩阵中可以看出，D:只能与式(4)矩 即Fs(U,a)=-∑(2∑Pos,Pos,+ 阵中与其不同行不同列的集合产生条件属性频率， 为了求得所有条件属性频率且不重复计算，在式 ∑D,(s-S-T,+Dg) (3) (4)矩阵中，定义任一行的和，即S=Ipos,/D1=
证明 由定义 １ 知：命题显然成立。 定理 ２ ［７］ 基于知识粒度的属性约简定义与基 于粒度差别矩阵的属性约简定义是等价的。 定理 ２ 说明基于知识粒度的属性约简可以转化 到粒度差别矩阵上进行。 针对不完备决策表，文献［７］ 中给出了一个基 于粒度差别矩阵的属性约简算法，其时间复杂度为 ｍａｘ｛Ｏ（ ｜ Ｃ ｜ ２ ｜ Ｕｐｏｓ ｜ ｜ Ｕ ｜ ），Ｏ（Ｋ ｜ Ｕ ｜ ｜ Ｃ ｜ ）｝。 算法对 粒度差别矩阵进行遍历，若只包含一个条件属性就 将其放入属性约简中，并去掉差别矩阵中任何含有 该条件属性的差别元素，直至差别矩阵为空。 该算 法虽然有效降低了时间复杂度，但是构造粒度差别 矩阵仍然需要占用大量的空间，对于处理大型数据 集仍然具有一定的难度。 经分析，算法中在粒度差别矩阵中出现的条件 属性才是能区分对象的条件属性，由于构造粒度差 别矩阵耗费空间，参考文献［１６］ 的方法，设计一种 计算粒度差别矩阵中含有的条件属性频率的函数， 然后给出计算该函数的快速算法，无须构造粒度差 别矩阵就可以将其中能有效区分对象的条件属性找 出，以降低算法的时间和空间复杂度。 ３ 计算属性频率的启发函数 定理 ３ 在决策表 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ）中，Ｂ⊆Ｃ， Ｕ／ Ｂ ＝ ｛ Ａ１ ，Ａ２ ，…，Ａｌ ｝，Ａｉ ／ ｛ ａ｝ ＝ ｛ Ａｉ１ ，Ａｉ２ ，…，Ａｉｋ ｝， Ａｉｊ ＝ ｐｏｓｉ∪Ｎｅｇｊ，Ｕ ＝ Ｕｐｏｓ∪Ｕｎｅｇ，其中 ｐｏｓｉ ＝ Ａｉｊ∩Ｕｐｏｓ， Ｎｅｇｊ ＝ Ａｉｊ∩Ｕｎｅｇ，ｐｏｓｉ ／ Ｄ＝ ｛Ｄｉ１ ，Ｄｉ２ ，…，ＤｉＤ ｝，Ｎｅｇｊ ／ Ｄ＝ ｛Ｄ － ｊ１ ，Ｄ － ｊ２ ，…，Ｄ － ｊＤ ｝。 令 ｓｉ ＝ ｜ ｐｏｓｉ ／ Ｄ｜ ＝ ∑１≤ｊ≤｜ Ｄ｜ ｜ Ｄｉｊ ｜ ＝ ｜ ｐｏｓｉ ｜ ，则所有集合中属于正域的集合对 Ｄ 划分 ｐｏｓｉ ／ Ｄ 总和为 Ｓ ＝ ∑１≤ｉ≤ｋ Ｓ ＝ ∑１≤ｉ≤ｋ ｜ ｐｏｓｉ ｜ ，所有集合中属 于正域的所有集合对 Ｄ 划分 ｐｏｓｉ ／ Ｄ 中决策值相同 集合总数为 Ｔｊ ＝ ∑１≤ｉ≤ｋ Ｄｉｊ。 根据定义 ６，粒度差别矩阵中包含的条件属性 可由两部分产生，设对象都在 Ｕｐｏｓ里产生的条件属 性的个数为 Ｎ１ ，则 Ｎ１ ＝ １≤∑ｉ ＜ ｊ≤ｋ ｐｏｓｉｐｏｓｊ （１） 两个对象一个在 Ｕｐｏｓ中，另一个在 Ｕｎｅｇ中，产生 的条件属性频率为 Ｎ２ ，则 Ｎ２ ＝ １≤ｉ≤∑ｋ，１≤ｊ≤｜ Ｄ｜ Ｄ － ｉｊ（Ｓ － Ｓｉ － Ｔｊ ＋ Ｄｉｊ） （２） 计算条件属性的频率函数｜ ＦＢ（Ｕ，ａ） ｜如下： ＦＢ（Ｕ，ａ）＝ ∑１≤ｉ≤ｌ （２Ｎ１ ＋Ｎ２ ）， 即 ＦＢ（Ｕ，ａ） ＝ １∑≤ｉ≤ｌ （２ １≤∑ｉ≤ｊ≤ｋ ＰｏｓｉＰｏｓｊ ＋ １≤ｉ≤∑ｋ，１≤ｊ≤｜ Ｄ｜ Ｄ － ｉｊ（Ｓ － Ｓｉ － Ｔｊ ＋ Ｄｉｊ）） （３） 证明 由粒度差别矩阵的定义知，计算 Ａｉ ／ ｛ａ｝ ＝ ｛Ａｉ１ ，Ａｉ２ ，…，Ａｉｋ ｝产生的条件属性频率，可分两部 分计算，一种是对象都在 Ｕｐｏｓ 中；另一种是一个在 Ｕｐｏｓ中，而另一个在 Ｕｎｅｇ中的。 １）若两个对象都在 Ｕｐｏｓ中，由划分的定义知，在 同一个划分集合里的两个对象值相等，即只有不同 划分集合里才有可能产生有效区分对象的条件属 性。 则只有不同划分集合的 Ｕｐｏｓ之间才能产生条件 属性频率；若两个对象都在 Ｕｐｏｓ中，产生的条件属性 频率为 Ｎ１ ＝ ∑１≤ｉ＜ｊ≤ｋ ｐｏｓｉｐｏｓｊ，任意两个划分集合都可 产生，因为在正域之间产生的差别矩阵的元素是对 称的，故条件属性频率为 ２Ｎ１ 。 ２）若一个对象在 Ｕｐｏｓ中，另一个对象在 Ｕｎｅｇ中， 由划分的定义知，同属一个集合里的两个对象值相 等，即只有不同划分集合里才有可能产生条件属性 频率，且 Ｕｐｏｓ和 Ｕｎｅｇ之间要求决策值不同，故需要对 每个划分集合里属于 Ｕｐｏｓ的集合对 Ｄ 划分，同时属 于 Ｕｎｅｇ的集合也对 Ｄ 划分。 所以，Ｎｅｇｊ ／ Ｄ 划分集合 里每个集合与 ｐｏｓｉ ／ Ｄ 划分集合里对于决策属性在 不同划分集合里就能产生条件属性频率。 为了方便叙述，假设将 Ａｉ ｛ ｂ｝所有集合中属于 正域的所有集合对 Ｄ 划分 ｐｏｓｉ ／ Ｄ 存放在一个矩阵 中，矩阵的行表示每一个非空集合对 Ｄ 的划分，矩 阵的列表示决策值相同的集合，生成的矩阵为 Ｄ ＝ Ｄ１１ … Ｄ１ｊ … Ｄ１｜ Ｄ｜ Ｄ２１ … Ｄ２ｊ … Ｄ２｜ Ｄ｜ ︙ ︙ Ｄｉ１ … Ｄｉｊ … Ｄｉ｜ Ｄ｜ ︙ ︙ Ｄｋ１ … Ｄｋｊ … Ｄｋ｜ Ｄ｜ é ë ê ê ê ê ê ê ê êê ù û ú ú ú ú ú ú ú úú （４） 同理，将 Ａｉ ｛ ｂ｝所有集合中属于负域的所有集 合对 Ｄ 划分 Ｎｅｇｊ ／ Ｄ 存放在另一个矩阵中，生成的 矩阵为 Ｄ ＝ Ｄ － １１ … Ｄ － １ｊ … Ｄ － １｜ Ｄ｜ Ｄ － ２１ … Ｄ － ２ｊ … Ｄ － ２｜ Ｄ｜ ︙ ︙ Ｄ － ｉ１ … Ｄ － ｉｊ … Ｄ － ｉ｜ Ｄ｜ ︙ ︙ Ｄ － ｋ１ … Ｄ － ｋｊ … Ｄ － ｋ｜ Ｄ｜ é ë ê ê ê ê ê ê ê ê ê ê ù û ú ú ú ú ú ú ú ú ú ú （５） 从这两个矩阵中可以看出，Ｄ － ｉｊ只能与式（４）矩 阵中与其不同行不同列的集合产生条件属性频率， 为了求得所有条件属性频率且不重复计算，在式 （４） 矩阵中，定义任一行的和，即 Ｓｉ ＝ ｜ ｐｏｓｉ ／ Ｄ ｜ ＝ 第 １ 期 乔丽娟，等：基于知识粒度的不完备决策表的属性约简算法 ·１３１·
.132. 智能系统学报 第11卷 1名D,=osl,则所有行的总和S=品S。 Neg(i=1,2,…,k)中。并计算两个对象都在U中 定义任一列的和：T=,∑D 写k 产生的条件属性频率X,则N,,品Pos,Po。 则若两个对象一个在U中，另一个在U中， b)计算每个非空队列中pos/D={D1,D2,…, 产生的条件属性颜率=1ee品D(S-S,-了+ Dn},Neg/D={D,D2,…,D},则在正域矩阵 D,)。故F。(U,a)=,三，(2N+W,)表示简化决策表 中S=pos/D1=1名mD,l,S=AS,所有集合中 110川 属于正域的所有集合对D划分pOs/D中决策值相 中所有对象相对于条件属性集B产生的条件属性 频率的总个数，证明完毕。 同集合总数为T=,品D。一个对象在U中，一个 根据定义6可知，只有属性值不同且不为缺省 在U,中，产生的条件属性总率为N16e品 值的才能包含条件属性，所以在本文的所有算法中， D(S-S:-T+D,),产生的条件属性总频率为 对象U对属性a的划分，将含有缺省值的放在划分 IF (U,b)I=2N+N2; 的最后一个集合里，不予处理。 3)输出U/(AU{b}),条件属性总频率数 4属性约简算法 1F,(U.b)I。 算法时间空间复杂度分析：算法2中1)的时间 首先，对不完备决策系统中的对象进行划分。 复杂度忽略不计，2)①的时间复杂度为O(1A:I),设 算法1论域U对属性a的划分 pos:/1b}={A,A2,…,Ak},则2)②a时间复杂度 输入不完备决策表S=(U,C,D,V,f),C= 为0(A)(j=1,2,…,k),2)②b时间复杂度为0 {a1,a2,…,am},U={x1,x2,…,x1u} (A:),即2)②时间复杂度为0(1A,I),2)时间复杂 输出U/a={A1,A2,…,A,} 度0(1AI)+0(1A21)+…+0(1A:I)≤0(1U1)。故 1)t=1;A,={x:}; 算法2的最坏时间复杂度为O(1U1),同理可得最坏 2)for(j=2:j<lU1+1:j++)。 空间复杂度为O(1U1)。 若任一条件属性a∈C(i=1,2,…,1C1)均有 算法3以条件属性的频率为启发信息的属性 f(x:,a:)=f(,a:)≠*，则A,=A,U{x};否则t= 约简算法 t+1;A,={x};(其中在此求划分时*单独放到 输入不完备决策表S=(U,C,D,V,f),C= 一块)。 (c1,C2,…,cm）,U={x1,x2,…,xn}; 3)输出U/a={A1,A2,…,A,}。 输出属性约简Red(C)。 算法1中，1)、3)时间复杂度忽略不计，2)的时 1)由文献[11]求出容差类T.(x:)(x:∈U), 间复杂度为O(1U1),则算法2的时间复杂度是0 (1U1),空间复杂度为O(1U川) U,U计算知识粒度1GD(c)1=店1T.(x)1/ 算法2求条件属性频率的函数 1U12,令IKI=GD(c:): 输入U/A={A1,A2,…,A,},条件属性的最大 2)将K按从小到大运用快速排序方法得到 值和最小值分别标记为M。,m6; 1Kal≤1K2l≤…≤IKmI,它们对应的属性为c, 输出U/(AU{b}),条件属性频率函数IF ca,…,cm令Red(C)={ca}; (U,b)1; 3)for(k=2,k<m+1;k++) 1)IF(U,b)I=0,U/(AU{b})=O: 由算法3计算；lF(U,c-))川 2)对VA:={x1,x2,…,x}∈U/A,以静态链表为 i(IFa(U,c-n)I≠0) 存储空间，依次放入对象x1,x2,…,x;令表头指针 Red(C)=Red(C)UCi(-1); 指向x; 4)输出属性约简Red(C)。 ①建立M。-m,+2空队列，令front[k]和end[k] 算法正确性分析：若1Fa(U,c-)1=0,即当 (k=0,1,2,…,M。-m6+1)分别为第k个队列的头指 前属性不能将两个对象区分开，则RRdu1e4=RRd, 针和尾指针，将链表中的对象x∈A,按链表中的次 则由算法3知，当输出约简Red(C)时，有Rc=Rdo 序分配到第f(x,b)-m,个队列中去，将链表中的对 由定理2知，算法3求出的属性约简就是基于知识 象值为*的对象分配到*队列中。 粒度的属性约简。 ②对除*队列的每个非空队列作如下处理： 算法时间复杂度分析：算法3的1)由文献[11] a)将非空队列中属于U的对象放入 知时间复杂度为O(K1CI1U1)(其中K= pos,(i=0,1,2,…,k)中，属于U的对象放入 max{1T.(x:)1,x:∈U}),空间复杂度为0(101)
∑１≤ｊ≤｜ Ｄ｜ ｜Ｄｉｊ ｜ ＝ ｜ ｐｏｓｉ ｜ ，则所有行的总和 Ｓ ＝ ∑１≤ｉ≤ｋ Ｓｉ。 定义任一列的和：Ｔｊ ＝ ∑１≤ｉ≤ｋ Ｄｉｊ。 则若两个对象一个在 Ｕｐｏｓ中，另一个在 Ｕｎｅｇ中， 产生的条件属性频率 Ｎ２ ＝ ∑ １≤ｉ≤｜ Ｄ｜ ，１≤ｊ≤ｋ Ｄ － （ Ｓ－Ｓｉ －Ｔｊ ＋ Ｄｉｊ）。 故 ＦＢ（Ｕ，ａ）＝ ∑１≤ｉ≤ｌ （２Ｎ１ ＋Ｎ２ ）表示简化决策表 中所有对象相对于条件属性集 Ｂ 产生的条件属性 频率的总个数，证明完毕。 根据定义 ６ 可知，只有属性值不同且不为缺省 值的才能包含条件属性，所以在本文的所有算法中， 对象 Ｕ 对属性 ａ 的划分，将含有缺省值的放在划分 的最后一个集合里，不予处理。 ４ 属性约简算法 首先，对不完备决策系统中的对象进行划分。 算法 １ 论域 Ｕ 对属性 ａ 的划分 输入 不完备决策表 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ），Ｃ ＝ ｛ａ１ ，ａ２ ，…，ａｍ ｝，Ｕ＝ ｛ｘ１ ，ｘ２ ，…，ｘ ｜ Ｕ｜ ｝ 输出 Ｕ／ ａ ＝ ｛Ａ１ ，Ａ２ ，…，Ａｔ｝ １）ｔ ＝ １；Ａｔ ＝ ｛ｘｉ｝； ２）ｆｏｒ（ｊ ＝ ２；ｊ＜ ｜Ｕ｜ ＋１；ｊ＋＋）。 若任一条件属性 ａｉ∈Ｃ（ ｉ ＝ １，２，…， ｜ Ｃ ｜ ） 均有 ｆ（ｘｉ，ａｉ）＝ ｆ （ ｘｊ， ａｉ ） ≠ ∗，则 Ａｔ ＝ Ａｔ∪｛ｘｊ｝；否则 ｔ ＝ ｔ＋１；Ａｔ ＝ ｛ ｘｊ ｝； （ 其中在此求划分时 ∗ 单独放到 一块）。 ３）输出 Ｕ／ ａ ＝ ｛Ａ１ ，Ａ２ ，…，Ａｔ｝。 算法 １ 中，１）、３）时间复杂度忽略不计，２）的时 间复杂度为 Ｏ（ ｜ Ｕ ｜ ），则算法 ２ 的时间复杂度是 Ｏ （ ｜Ｕ｜ ），空间复杂度为 Ｏ（ ｜Ｕ｜ ）。 算法 ２ 求条件属性频率的函数 输入 Ｕ／ Ａ ＝ ｛Ａ１ ，Ａ２ ，…，Ａｔ｝，条件属性的最大 值和最小值分别标记为 Ｍｂ，ｍｂ； 输出 Ｕ／ （ Ａ∪｛ ｂ｝），条件属性频率函数 ｜ Ｆａ （Ｕ，ｂ） ｜ ； １） ｜ ＦＡ（Ｕ，ｂ） ｜ ＝ ０，Ｕ／ （Ａ∪｛ｂ｝）＝ ⌀； ２）对∀Ａｉ ＝ ｛ｘ１ ，ｘ２ ，…，ｘｊ｝∈Ｕ／ Ａ，以静态链表为 存储空间，依次放入对象 ｘ１ ，ｘ２ ，…，ｘｊ；令表头指针 指向 ｘｉ； ①建立 Ｍｂ －ｍｂ ＋２ 空队列，令 ｆｒｏｎｔ［ｋ］和 ｅｎｄ［ｋ］ （ｋ ＝ ０，１，２，…，Ｍｂ －ｍｂ ＋１）分别为第 ｋ 个队列的头指 针和尾指针，将链表中的对象 ｘ∈Ａｉ 按链表中的次 序分配到第 ｆ（ｘ，ｂ） －ｍｂ 个队列中去，将链表中的对 象值为∗的对象分配到∗队列中。 ②对除∗队列的每个非空队列作如下处理： ａ） 将 非 空 队 列 中 属 于 Ｕｐｏｓ 的 对 象 放 入 ｐｏｓｉ（ｉ ＝ ０，１，２，…，ｋ） 中， 属 于 Ｕｎｅｇ 的 对 象 放 入 Ｎｅｇｉ（ｉ ＝ １，２，…，ｋ）中。 并计算两个对象都在 Ｕｐｏｓ中 产生的条件属性频率 Ｎ１ ，则 Ｎ１ ＝ ∑１≤ｉ＜ｊ≤ｋ ｐｏｓｉｐｏｓｊ。 ｂ）计算每个非空队列中 ｐｏｓｊ ／ Ｄ ＝ ｛Ｄｊ１ ，Ｄｊ２ ，…， Ｄｊ ｜ Ｄ｜ ｝，Ｎｅｇｊ ／ Ｄ ＝ ｛Ｄｊ１ ，Ｄｊ２ ，…，Ｄｊ ｜ Ｄ｜ ｝，则在正域矩阵 中 Ｓｉ ＝ ｜ ｐｏｓｉ ／ Ｄ｜ ＝ ∑１≤ｊ≤｜ Ｄ｜ ｜ Ｄｉｊ ｜ ，Ｓ ＝ ∑１≤ｉ≤ｋ Ｓｉ 所有集合中 属于正域的所有集合对 Ｄ 划分 ｐｏｓｊ ／ Ｄ 中决策值相 同集合总数为 Ｔｊ ＝ ∑１≤ｉ≤ｋ Ｄｉｊ。 一个对象在 Ｕｐｏｓ中，一个 在 Ｕｎｅｇ中，产生的条件属性总频率为 Ｎ２ ＝ ∑ １≤ｉ≤｜ Ｄ｜ ，１≤ｊ≤ｋ Ｄ － ｉｊ （ Ｓ － Ｓｉ － Ｔｊ ＋ Ｄｉｊ ）， 产 生 的 条 件 属 性 总 频 率 为 ｜ ＦＡ （Ｕ，ｂ） ｜ ＝ ２Ｎ１ ＋Ｎ２ ； ３） 输 出 Ｕ／ （ Ａ ∪ ｛ ｂ｝）， 条 件 属 性 总 频 率 数 ｜ ＦＡ（Ｕ，ｂ） ｜ 。 算法时间空间复杂度分析：算法 ２ 中 １）的时间 复杂度忽略不计，２）①的时间复杂度为 Ｏ（ ｜ Ａｉ ｜ ），设 ｐｏｓｉ ／ ｛ｂ｝ ＝ ｛ Ａｉ１ ，Ａｉ２ ，…，Ａｉｋ ｝，则 ２） ②ａ 时间复杂度 为Ｏ（Ａｉｊ） （ ｊ ＝ １，２，…，ｋ），２） ②ｂ 时间复杂度为 Ｏ （Ａｉｊ），即 ２）②时间复杂度为 Ｏ（ ｜ Ａｉ ｜ ），２）时间复杂 度 Ｏ（ ｜ Ａｉ ｜ ）＋Ｏ（ ｜ Ａ２ ｜ ） ＋…＋Ｏ（ ｜ Ａｉ ｜ ）≤Ｏ（ ｜ Ｕ｜ ）。 故 算法 ２ 的最坏时间复杂度为Ｏ（ ｜Ｕ｜ ），同理可得最坏 空间复杂度为 Ｏ（ ｜Ｕ｜ ）。 算法 ３ 以条件属性的频率为启发信息的属性 约简算法 输入 不完备决策表 Ｓ ＝ （Ｕ，Ｃ，Ｄ，Ｖ，ｆ），Ｃ ＝ （ｃ１ ，ｃ２ ，…，ｃｍ ），Ｕ＝ ｛ｘ１ ，ｘ２ ，…，ｘｎ ｝； 输出 属性约简 Ｒｅｄ（Ｃ）。 １）由文献［１１］ 求出容差类 Ｔｃｉ （ ｘｉ ） （ ｘｉ ∈Ｕ）， Ｕｐｏｓ，Ｕｎｅｇ计算知识粒度 ｜ ＧＤ（ ｃｉ ） ｜ ＝ ∑ ｎ ｉ ＝ １ ｜ Ｔｃｉ （ ｘｉ ） ｜ ／ ｜Ｕ｜ ２ ，令｜ Ｋｉ ｜ ＝ＧＤ（ｃｉ）； ２）将 Ｋｉ 按从小到大运用快速排序方法得到 ｜ Ｋｉ１ ｜≤｜ Ｋｉ２ ｜ ≤…≤ ｜ Ｋｉｍ ｜ ，它们对应的属性为 ｃｉ１ ， ｃｉ２ ，…，ｃｉｍ令 Ｒｅｄ（Ｃ）＝ ｛ｃｉ１ ｝； ３）ｆｏｒ（ｋ ＝ ２，ｋ＜ｍ＋１；ｋ＋＋） 由算法 ３ 计算； ｜ Ｆｒｅｄ（Ｕ，ｃｉ（ｋ－１） ） ｜ ｉｆ（｜ ＦＲｅｄ（Ｕ，ｃｉ（ｋ－１） ）） ｜ ≠ ０） Ｒｅｄ（Ｃ） ＝ Ｒｅｄ（Ｃ） ∪ ｛ｃｉ（ｋ－１） ｝； ４）输出属性约简 Ｒｅｄ（Ｃ）。 算法正确性分析：若 ｜ ＦＲｅｄ（Ｕ，ｃｉ（ｋ－１） ） ｜ ＝ ０，即当 前属性不能将两个对象区分开，则 ＲＲｅｄ∪｛ｃｉｋ ｝ ＝ ＲＲｅｄ ， 则由算法 ３ 知，当输出约简 Ｒｅｄ（Ｃ）时，有 ＲＣ ＝ ＲＲｅｄ 。 由定理 ２ 知，算法 ３ 求出的属性约简就是基于知识 粒度的属性约简。 算法时间复杂度分析：算法 ３ 的 １）由文献［１１］ 知时 间 复 杂 度 为 Ｏ （ Ｋ ｜ Ｃ ｜ ｜ Ｕ ｜ ） （ 其 中 Ｋ ＝ ｍａｘ｛ ｜ Ｔｃ（ｘｉ） ｜ ，ｘｉ ∈Ｕ｝），空间复杂度为 Ｏ（ ｜ Ｕ ｜ ）。 ·１３２· 智 能 系 统 学 报 第 １１ 卷
第1期 乔丽娟，等：基于知识粒度的不完备决策表的属性约简算法 ·133· 2)的时间复杂度为0(1C1)+0(1U1),空间复杂度 S,=lpos1/D1=∑1DI=2+0+0=2 为O(1U1)(由算法1的复杂度分析可得)。3)的时 16i≤3 间复杂度为0(1C11U1),空间复杂度为0(1U1)。 S2=pos,/D1=∑1D11=0+1+0=1 1i3 故算法3的时间复杂度为O(KIC1IU1)(其中K= S=∑S,=S,+S2=2+1=3 max{ITc(x:)1,x:∈U},空间复杂度为O(1U1)。 1运k T,=∑Dg=2+0=2 5实例分析 1i3,1j2 T2=∑D,=0+1=1 为了证明算法的可行性，以文献[16]中的不完 1≤i3,1对j≤2 备决策表1为例子进行相应说明。 T3=∑D=0+0=0 1i3,1对j2 表1不完备决策表 每个非空队列中的Neg,/D: Table 1 The table of incomplete decision D1=0,D2=0,Dg=0, car price mileage size max-speed conclusion D={x4},D2=0,Da={xs} high high full low 800d 「200 D=010 「000 X2 low full low good 米 D-山0 1 compact high poor high full high good N=1e盖sD,(S-S,-T)+D,)=0*(3-2-2+2)+0* (3-2-1+1)+0*(3-2-0+0)+1*(3-1-2+0)+0* full high excel low full (3-1-1+1)+1*(3-1-0+0)=1*2=2 X6 high good 对A,={x6},因A.不能区分对象，故无需 为方便计算，将属性值从左至右简记为P、M、 计算。 S、X,则该表的条件属性为C={P,M,S,X}。 故1Fa(U,X)1=2N1+N2=2*2+2=6, 由算法31)求得各属性的知识粒度分别是： 求IFx(U,S)I。 1K1=GD(P)=(4+4+6+4+6+4)/36=28/36: 输入U/(X)={{x1,x2},{x3,x4,x5}} 1K2I=GD(M)=(6+6+6+6+6+6)/36=36/36: 由算法22)的①对A1={x1,x2}求得front[1] 1K,1=GD(S)=(5+5+5+5+5+1)/36=26/36: →x,→x2→end[1]; 1K3I=GD(X)=(3+3+4+4+4+6)/36=24/36: 对其划分有pos1={x1,x2},Neg1=: Um={x1,x2,x3},U={x4,5,x6} 易知，IFx(U,S)l1=0, 由2)排序1K,I≤|K,I≤IKI≤IK21,他们对应 对A2={x3,x4,x}求得 的属性为X、S、P、M,则有Red(C)={X},Rc=O。 front[1]→x3→+end[1]; 由3)计算1Fa(U,X)1=6,计算的1Fx(U,S)I front[2]→x,→x,→end[2]; =6,计算的1Fx.(U,P)1=1,计算的1Fxsm{U,M1= 对第1个非空队列有pos,={x3},Neg1=☑； 0,算法结束，输出约简Red(C)={X,S,P}。 对第2个非空队列pos2=☑，Neg2={x4,xs} 由算法2求IF(X)I。 输入U/☑={x1,x2,3,x4,x5,x6} 则N,∑pOs,pog,=1*0=0,对决策属性划分后得 1i<j 由算法2,2)的2)①对A1={x1,x2,x3,x4,x5 D=[011D= 000 x6}求得： 0001 101 front[1]→x,→x2→end[1]; 易知N2=0+0+0+1*3+0+1*3=6 front[2]→xg→x4→xs→end[2]; 1Fx(U,S)12=2N1+N2=0+6=6 front[*]x6→end[*]: IFx(U,S)I=IFx(U,S)I+IFx(U,S)12=6 对第1个非空队列有pos,={x1,x2},Ng1=☑； 输入U/(XU({S})={{x1,x2},{x3},{x4, 对第2个非空队列pos2={x3},Ng2={x4,x5}, x5}由算法2的2)①对A1={x1,x2}求得 则N=1名，os,Po=lp0s,1*lpo,1=2*1=2。 front[1]→x,→end[1]; front[2]→x2→end[2]; 由算法2,2)的②计算每个非空队列中的 对第1个非空队列有pos,={x,},Ng1=: Pos,/D。 对第2个非空队列pos2={x2},Ng2=☑。 D1={x1,x2},D12=,D3=0, D21=0,D2={x3},D3=☑，则 则N,=∑p0s,po9,=1*1=1易知N2=0
２）的时间复杂度为 Ｏ（ ｜ Ｃ ｜ ） ＋Ｏ（ ｜ Ｕ ｜ ），空间复杂度 为 Ｏ（ ｜Ｕ｜ ）（由算法 １ 的复杂度分析可得）。 ３）的时 间复杂度为 Ｏ（ ｜ Ｃ ｜ ｜ Ｕ ｜ ），空间复杂度为 Ｏ（ ｜ Ｕ ｜ ）。 故算法 ３ 的时间复杂度为 Ｏ（Ｋ ｜ Ｃ ｜ ｜ Ｕ ｜ ） （其中 Ｋ ＝ ｍａｘ｛ ｜ ＴＣ（ｘｉ） ｜ ，ｘｉ∈Ｕ｝，空间复杂度为Ｏ（ ｜Ｕ｜ ）。 ５ 实例分析 为了证明算法的可行性，以文献［１６］中的不完 备决策表 １ 为例子进行相应说明。 表 １ 不完备决策表 Ｔａｂｌｅ １ Ｔｈｅ ｔａｂｌｅ ｏｆ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｃａｒ ｐｒｉｃｅ ｍｉｌｅａｇｅ ｓｉｚｅ ｍａｘ⁃ｓｐｅｅｄ ｃｏｎｃｌｕｓｉｏｎ ｘ１ ｈｉｇｈ ｈｉｇｈ ｆｕｌｌ ｌｏｗ ｇｏｏｄ ｘ２ ｌｏｗ ∗ ｆｕｌｌ ｌｏｗ ｇｏｏｄ ｘ３ ∗ ∗ ｃｏｍｐａｃｔ ｈｉｇｈ ｐｏｏｒ ｘ４ ｈｉｇｈ ∗ ｆｕｌｌ ｈｉｇｈ ｇｏｏｄ ｘ５ ∗ ∗ ｆｕｌｌ ｈｉｇｈ ｅｘｃｅｌ ｘ６ ｌｏｗ ｈｉｇｈ ｆｕｌｌ ∗ ｇｏｏｄ 为方便计算，将属性值从左至右简记为 Ｐ、Ｍ、 Ｓ、Ｘ，则该表的条件属性为 Ｃ ＝ ｛Ｐ，Ｍ，Ｓ，Ｘ｝。 由算法 ３ １）求得各属性的知识粒度分别是： ｜ Ｋ１ ｜ ＝ＧＤ（Ｐ）＝ （４＋４＋６＋４＋６＋４） ／ ３６ ＝ ２８ ／ ３６； ｜ Ｋ２ ｜ ＝ＧＤ（Ｍ）＝ （６＋６＋６＋６＋６＋６） ／ ３６ ＝ ３６ ／ ３６； ｜ Ｋ３ ｜ ＝ＧＤ（Ｓ）＝ （５＋５＋５＋５＋５＋１） ／ ３６ ＝ ２６ ／ ３６； ｜ Ｋ３ ｜ ＝ＧＤ（Ｘ）＝ （３＋３＋４＋４＋４＋６） ／ ３６ ＝ ２４ ／ ３６； Ｕｐｏｓ ＝ ｛ｘ１ ，ｘ２ ，ｘ３ ｝，Ｕｎｅｇ ＝ ｛ｘ４ ，ｘ５ ，ｘ６ ｝ 由 ２）排序｜ Ｋ４ ｜≤｜ Ｋ３ ｜≤｜ Ｋ１ ｜≤｜ Ｋ２ ｜ ，他们对应 的属性为 Ｘ、Ｓ、Ｐ、Ｍ，则有 Ｒｅｄ（Ｃ）＝ ｛Ｘ｝，ＲＣ ＝⌀。 由 ３）计算 ｜ Ｆ⌀（Ｕ，Ｘ） ｜ ＝ ６，计算的 ｜ ＦＸ（Ｕ，Ｓ） ｜ ＝ ６，计算的｜Ｆ｛Ｘ，Ｓ｝ （Ｕ，Ｐ） ｜ ＝ １，计算的｜Ｆ｛Ｘ，Ｓ，Ｐ｝ ｛Ｕ，Ｍ｝ ｜ ＝ ０，算法结束，输出约简 Ｒｅｄ（Ｃ）＝ ｛Ｘ，Ｓ，Ｐ｝。 由算法 ２ 求｜ ＦＲｅｄ（Ｘ） ｜ 。 输入 Ｕ／ ⌀＝ ｛ｘ１ ，ｘ２ ，ｘ３ ，ｘ４ ，ｘ５ ，ｘ６ ｝ 由算法 ２，２） 的 ２） ①对 Ａ１ ＝ ｛ ｘ１ ，ｘ２ ，ｘ３ ，ｘ４ ，ｘ５ ， ｘ６ ｝求得： ｆｒｏｎｔ［１］→ｘ１→ｘ２→ｅｎｄ［１］； ｆｒｏｎｔ［２］→ｘ３→ｘ４→ｘ５→ｅｎｄ［２］； ｆｒｏｎｔ［∗］→ｘ６→ｅｎｄ［∗］； 对第 １ 个非空队列有 ｐｏｓ１ ＝ ｛ｘ１ ，ｘ２ ｝，Ｎｅｇ１ ＝⌀； 对第 ２ 个非空队列 ｐｏｓ２ ＝ ｛ｘ３ ｝，Ｎｅｇ２ ＝ ｛ｘ４ ，ｘ５ ｝， 则 Ｎ１ ＝ ∑１≤ｉ≤ｊ≤２ ｐｏｓｉｐｏｓｊ ＝ ｜ ｐｏｓ１ ｜∗｜ ｐｏｓ２ ｜ ＝ ２∗１ ＝ ２。 由算法 ２， ２ ） 的 ② 计 算 每 个 非 空 队 列 中 的 ｐｏｓｉ ／ Ｄ。 Ｄ１１ ＝ ｛ｘ１ ，ｘ２ ｝，Ｄ１２ ＝ ⌀，Ｄ１３ ＝ ⌀， Ｄ２１ ＝ ⌀，Ｄ２２ ＝ ｛ｘ３ ｝，Ｄ２３ ＝ ⌀，则 Ｓ１ ＝｜ ｐｏｓ１ ／ Ｄ ｜ ＝ １∑≤ｉ≤３ ｜ Ｄｉ１ ｜ ＝ ２ ＋ ０ ＋ ０ ＝ ２ Ｓ２ ＝｜ ｐｏｓ２ ／ Ｄ ｜ ＝ １∑≤ｉ≤３ ｜ Ｄｉ１ ｜ ＝ ０ ＋ １ ＋ ０ ＝ １ Ｓ ＝ １∑≤ｉ≤ｋ Ｓｉ ＝ Ｓ１ ＋ Ｓ２ ＝ ２ ＋ １ ＝ ３ Ｔ１ ＝ １≤ｉ≤∑３，１≤ｊ≤２ Ｄｉｊ ＝ ２ ＋ ０ ＝ ２ Ｔ２ ＝ １≤ｉ≤∑３，１≤ｊ≤２ Ｄｉｊ ＝ ０ ＋ １ ＝ １ Ｔ３ ＝ １≤ｉ≤∑３，１≤ｊ≤２ Ｄｉｊ ＝ ０ ＋ ０ ＝ ０ 每个非空队列中的 Ｎｅｇｉ ／ Ｄ： Ｄ － １１ ＝ ⌀，Ｄ － １２ ＝ ⌀，Ｄ － １３ ＝ ⌀， Ｄ － ２１ ＝ ｛ｘ４ ｝，Ｄ － ２２ ＝ ⌀，Ｄ － ２３ ＝ ｛ｘ５ ｝ Ｄ ＝ ２ ０ ０ ０ １ ０ é ë ê ê ù û ú ú ，Ｄ － ＝ ０ ０ ０ １ ０ １ é ë ê ê ù û ú ú Ｎ２ ＝ ∑ １≤ｉ≤３，１≤ｊ≤２ Ｄ － ｉｊ（Ｓ－Ｓｉ －Ｔｊ ＋Ｄｉｊ）＝ ０∗（３－２－２＋２）＋０∗ （３－２－１＋１） ＋０∗（３－２－０＋０） ＋１∗（３－１－２＋０） ＋０∗ （３－１－１＋１）＋１∗（３－１－０＋０）＝ １∗２＝ ２ 对 Ａ∗ ＝ ｛ ｘ６ ｝， 因 Ａ∗ 不能区分对象， 故无需 计算。 故｜ Ｆ⌀（Ｕ，Ｘ） ｜ ＝ ２Ｎ１ ＋Ｎ２ ＝ ２∗２＋２ ＝ ６， 求｜ ＦＸ（Ｕ，Ｓ） ｜ 。 输入 Ｕ／ （Ｘ）＝ ｛｛ｘ１ ，ｘ２ ｝，｛ｘ３ ，ｘ４ ，ｘ５ ｝｝ 由算法 ２ ２）的①对 Ａ１ ＝ ｛ ｘ１ ，ｘ２ ｝求得 ｆｒｏｎｔ［１］ →ｘ１→ｘ２→ｅｎｄ［１］； 对其划分有 ｐｏｓ１ ＝ ｛ｘ１ ，ｘ２ ｝，Ｎｅｇ１ ＝⌀； 易知， ｜ ＦＸ（Ｕ，Ｓ） ｜ １ ＝ ０， 对 Ａ２ ＝ ｛ｘ３ ，ｘ４ ，ｘ５ ｝求得 ｆｒｏｎｔ［１］→ｘ３→ｅｎｄ［１］； ｆｒｏｎｔ［２］→ｘ４→ｘ５→ｅｎｄ［２］； 对第 １ 个非空队列有 ｐｏｓ１ ＝ ｛ｘ３ ｝，Ｎｅｇ１ ＝⌀； 对第 ２ 个非空队列 ｐｏｓ２ ＝⌀，Ｎｅｇ２ ＝ ｛ｘ４ ，ｘ５ ｝， 则 Ｎ１ １≤∑ｉ ＜ ｊ≤２ ｐｏｓｉｐｏｓｊ ＝ １∗０ ＝ ０，对决策属性划分后得 Ｄ ＝ ０ １ ０ ０ ０ ０ é ë ê ê ù û ú ú ，Ｄ － ＝ ０ ０ ０ １ ０ １ é ë ê ê ù û ú ú 易知 Ｎ２ ＝ ０＋０＋０＋１∗３＋０＋１∗３ ＝ ６ ｜ ＦＸ（Ｕ，Ｓ） ｜ ２ ＝ ２Ｎ１ ＋Ｎ２ ＝ ０＋６ ＝ ６ ｜ＦＸ（Ｕ，Ｓ） ｜ ＝ ｜ＦＸ（Ｕ，Ｓ） ｜ １ ＋｜ＦＸ（Ｕ，Ｓ） ｜ ２ ＝６ 输入 Ｕ／ （Ｘ∪（｛ Ｓ｝） ＝ ｛｛ ｘ１ ，ｘ２ ｝，｛ ｘ３ ｝，｛ ｘ４ ， ｘ５ ｝由算法 ２ 的 ２）①对 Ａ１ ＝ ｛ｘ１ ，ｘ２ ｝求得 ｆｒｏｎｔ［１］→ｘ１→ｅｎｄ［１］； ｆｒｏｎｔ［２］→ｘ２→ｅｎｄ［２］； 对第 １ 个非空队列有 ｐｏｓ１ ＝ ｛ｘ１ ｝，Ｎｅｇ１ ＝⌀； 对第 ２ 个非空队列 ｐｏｓ２ ＝ ｛ｘ２ ｝，Ｎｅｇ２ ＝⌀。 则 Ｎ１ ＝ １≤∑ｉ≤ｊ≤２ ｐｏｓｉｐｏｓｊ ＝ １∗１ ＝ １ 易知 Ｎ２ ＝ ０， 第 １ 期 乔丽娟，等：基于知识粒度的不完备决策表的属性约简算法 ·１３３·
.134. 智能系统学报 第11卷 故1Fx,(U,P)l=l。 45 对A2={x3}求 front[1]→x3→end[1]; 3 5 易知，1F1x.(U,P)l2=0 对A3={x4,x}求得 0505 front[l]→x,→end[1]; 10 5 front[*]→x,→end[*]; 易知，1Fx.(U,P)I3=0, win Hepatitis Vote Soybean-large Gredit Car I Fix.s(U,P)I=I Fix.st(U,P)11+ 图1UCI数据集对比 I Fix.s(U,P)12 +I Fix.s](U,P)13=1 Fig.1 The comparison of UCI data sets 输入U/({X,S}U{P})={x},{x2},{x4}} 从表2中的实验数据可以看出，对于小的数据 求得1Fx,s.(U,M)I=0。 集({Hepatitis,15,199},{Wine,14,178})上，对比 实例说明，该约简与文献[5]相同。新算法不 的4种算法的运行时间相差不大。但是对于较大的 仅通俗易懂，且在粒度差别矩阵的基础上大大减少 数据集，运行时间就相差很大，而且随着数据集的扩 存储空间，且大大提高了算法收敛的时间速度，即新 大，新算法的运行时间相对于其他3种算法的增长 算法是一个高效可行的属性约简算法。 幅度小得多，表明新算法具有较好的可扩展性。 6实验对比 7结束语 为了更好地说明新算法比其他同类算法更具有 在决策表中，知识粒度是有效进行属性约简的 有效性和实用性，选用UCI机器学习数据库中的6 方法，以往的属性约简算法由于计算知识粒度浪费 个数据集：Credit、Car、Hepatitis、Soybean-large、Vote 了大量时间，算法效率不高。因此，本文设计一个基 和Wime进行实验。选取比较新的算法进行对比， 于知识粒度的计算条件属性频率的启发函数，以知 考察新算法的高效性，分别与文献[17]、文献[18]、 识粒度为启发信息，提出新的属性约简算法，大大降 文献[11]进行对比，文献[17]是在差别矩阵的基础 低了算法的时间复杂度。在以后的研究中，可以将 上提出的属性约简算法，文献[17]算法运行时间记 计算属性频率的思想利用到其他属性约简的方法 为(，文献[18]是基于冲突域的属性约简算法，算 中，如相容矩阵、差别矩阵等，也可进一步应用到规 法运行时间记为t2,文献[11]算法运行时间记为3， 则获取中。 本文算法运行时间记为t,对比结果见表2。为了增 强实验结果的可靠性，本文所取的最终时间为7次实 参考文献： 验结果的平均值。实验运行的环境为：CPU为AMD, [1]PAWLAK Z,GRZYMALA-BUSSE J,SLOWINSKI R. 2.00GB内存，在Visual Stdio2010平台。 Rough sets[J].Communications of the ACM,1995,8 表2UCI数据集信息 (1):89-95 Table 2 The information of UCI data sets [2]PAWLAK Z.Rough set theory and its applications to data a- nalysis[J].Cybernetics and systems:an international, 数据集 完备 1C1 IUI 1998,29(7):661-668. Car 是 6 1700 [3]KRYSZKIEWICZ M.Rough set approach to incomplete in- formation systems[J].Information sciences,1998,112 (1- Hepatitis 否 15 199 4):39-49. Vote 否 [4]钱文彬，杨炳儒，徐章艳，等.基于不完备决策表的容 16 435 差类高效求解算法[J].小型微型计算机系统，2013,34 Credit 否 15 690 (2):345-350. QIAN Wenbin,YANG Bingru,XU Zhangyan,et al.Effi- Soybean-large 否 35 351 cient algorithm for computing tolerance classes of incomplete Wine 是 14 decision table[J].Journal of Chinese computer systems, 178 2013.34(2)：345-350. 表2中的数据集，IC1代表条件属性个数，IU川 [5]李秀红，史开泉.一种基于知识粒度的不完备信息系统 代表对象个数。 的属性约简算法[J].计算机科学，2006,33(11)：169 170.199
故｜ Ｆ｛Ｘ，Ｓ｝（Ｕ，Ｐ） ｜ １ ＝ １。 对 Ａ２ ＝ ｛ｘ３ ｝求 ｆｒｏｎｔ［１］→ｘ３→ｅｎｄ［１］； 易知， ｜ Ｆ｛Ｘ，Ｓ｝（Ｕ，Ｐ） ｜ ２ ＝ ０ 对 Ａ３ ＝ ｛ｘ４ ，ｘ５ ｝求得 ｆｒｏｎｔ［１］→ｘ４→ｅｎｄ［１］； ｆｒｏｎｔ［∗］→ｘ５→ｅｎｄ［∗］； 易知， ｜ Ｆ｛Ｘ，Ｓ｝（Ｕ，Ｐ） ｜ ３ ＝ ０， ｜ Ｆ｛Ｘ，Ｓ｝（Ｕ，Ｐ） ｜ ＝｜ Ｆ｛Ｘ，Ｓ｝（Ｕ，Ｐ） ｜ １ ＋ ｜ Ｆ｛Ｘ，Ｓ｝（Ｕ，Ｐ） ｜ ２ ＋｜ Ｆ｛Ｘ，Ｓ｝（Ｕ，Ｐ） ｜ ３ ＝ １ 输入 Ｕ／ （｛Ｘ，Ｓ｝∪｛Ｐ｝）＝ ｛｛ｘ１ ｝，｛ｘ２ ｝，｛ｘ４ ｝｝ 求得｜ Ｆ｛Ｘ，Ｓ，Ｐ｝（Ｕ，Ｍ） ｜ ＝ ０。 实例说明，该约简与文献［５］ 相同。 新算法不 仅通俗易懂，且在粒度差别矩阵的基础上大大减少 存储空间，且大大提高了算法收敛的时间速度，即新 算法是一个高效可行的属性约简算法。 ６ 实验对比 为了更好地说明新算法比其他同类算法更具有 有效性和实用性，选用 ＵＣＩ 机器学习数据库中的 ６ 个数据集：Ｃｒｅｄｉｔ、Ｃａｒ、Ｈｅｐａｔｉｔｉｓ、 Ｓｏｙｂｅａｎ⁃ｌａｒｇｅ、Ｖｏｔｅ 和 Ｗｉｎｅ 进行实验。 选取比较新的算法进行对比， 考察新算法的高效性，分别与文献［１７］、文献［１８］、 文献［１１］进行对比，文献［１７］是在差别矩阵的基础 上提出的属性约简算法，文献［１７］算法运行时间记 为 ｔ １ ，文献［１８］是基于冲突域的属性约简算法，算 法运行时间记为 ｔ ２ ，文献［１１］ 算法运行时间记为ｔ ３， 本文算法运行时间记为ｔ ｎｅｗ，对比结果见表 ２。 为了增 强实验结果的可靠性，本文所取的最终时间为 ７ 次实 验结果的平均值。 实验运行的环境为：ＣＰＵ 为 ＡＭＤ， ２．００ ＧＢ内存，在 Ｖｉｓｕａｌ Ｓｔｄｉｏ２０１０ 平台。 表 ２ ＵＣＩ 数据集信息 Ｔａｂｌｅ ２ Ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ＵＣＩ ｄａｔａ ｓｅｔｓ 数据集 完备 ｜ Ｃ｜ ｜Ｕ｜ Ｃａｒ 是 ６ １ ７００ Ｈｅｐａｔｉｔｉｓ 否 １５ １９９ Ｖｏｔｅ 否 １６ ４３５ Ｃｒｅｄｉｔ 否 １５ ６９０ Ｓｏｙｂｅａｎ⁃ｌａｒｇｅ 否 ３５ ３５１ Ｗｉｎｅ 是 １４ １７８ 表 ２ 中的数据集， ｜ Ｃ ｜ 代表条件属性个数， ｜ Ｕ ｜ 代表对象个数。 图 １ ＵＣＩ 数据集对比 Ｆｉｇ．１ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＵＣＩ ｄａｔａ ｓｅｔｓ 从表 ２ 中的实验数据可以看出，对于小的数据 集（｛Ｈｅｐａｔｉｔｉｓ，１５，１９９｝，｛ Ｗｉｎｅ，１４，１７８｝） 上，对比 的 ４ 种算法的运行时间相差不大。 但是对于较大的 数据集，运行时间就相差很大，而且随着数据集的扩 大，新算法的运行时间相对于其他 ３ 种算法的增长 幅度小得多，表明新算法具有较好的可扩展性。 ７ 结束语 在决策表中，知识粒度是有效进行属性约简的 方法，以往的属性约简算法由于计算知识粒度浪费 了大量时间，算法效率不高。 因此，本文设计一个基 于知识粒度的计算条件属性频率的启发函数，以知 识粒度为启发信息，提出新的属性约简算法，大大降 低了算法的时间复杂度。 在以后的研究中，可以将 计算属性频率的思想利用到其他属性约简的方法 中，如相容矩阵、差别矩阵等，也可进一步应用到规 则获取中。 参考文献： ［ １ ］ ＰＡＷＬＡＫ Ｚ， ＧＲＺＹＭＡＬＡ⁃ＢＵＳＳＥ Ｊ， ＳＬＯＷＩＮＳＫＩ Ｒ． Ｒｏｕｇｈ ｓｅｔｓ ［ Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ， １９９５， ８ （１）： ８９⁃９５． ［２］ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｄａｔａ ａ⁃ ｎａｌｙｓｉｓ ［ Ｊ ］． Ｃｙｂｅｒｎｅｔｉｃｓ ａｎｄ ｓｙｓｔｅｍｓ： ａｎ ｉｎｔｅｒｎａｔｉｏｎａｌ， １９９８， ２９（７）： ６６１⁃６６８． ［３］ＫＲＹＳＺＫＩＥＷＩＣＺ Ｍ． Ｒｏｕｇｈ ｓｅｔ ａｐｐｒｏａｃｈ ｔｏ ｉｎｃｏｍｐｌｅｔｅ ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， １９９８， １１２ （１⁃ ４）： ３９⁃４９． ［４］钱文彬， 杨炳儒， 徐章艳， 等． 基于不完备决策表的容 差类高效求解算法［Ｊ］． 小型微型计算机系统， ２０１３， ３４ （２）： ３４５⁃３５０． ＱＩＡＮ Ｗｅｎｂｉｎ， ＹＡＮＧ Ｂｉｎｇｒｕ， ＸＵ Ｚｈａｎｇｙａｎ， ｅｔ ａｌ． Ｅｆｆｉ⁃ ｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｏｍｐｕｔｉｎｇ ｔｏｌｅｒａｎｃｅ ｃｌａｓｓｅｓ ｏｆ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０１３， ３４（２）： ３４５⁃３５０． ［５］李秀红， 史开泉． 一种基于知识粒度的不完备信息系统 的属性约简算法［Ｊ］． 计算机科学， ２００６， ３３（１１）： １６９⁃ １７０， １９９． ·１３４· 智 能 系 统 学 报 第 １１ 卷
第1期 乔丽娟，等：基于知识粒度的不完备决策表的属性约简算法 ·135. LI Xiuhong,SHI Kaiquan.A knowledge granulation-based ZHONG Luo,MEI Lei,GUO Cuicui,et al.Heuristic algo- algorithm for attribute reduction under incomplete informa- rithm for attribute reduction on granular matrix[].Journal tion systems[J].Computer science,2006,33(11):169- of Chinese computer systems,2011,32(3):516-520. 170.199 [14]唐孝，舒兰.基于粒计算的属性约简改进算法[J].计 [6]史先红，史进玲.一种基于相对粒度的不完备决策表约 算机科学，2014,41(11A):313-315,346. 简算法[J].河南师范大学学报：自然科学版，2010,38 TANG Xiao,SHU Lan.Improved algorithm of attribute re- (4):51-53,84. duction based on granular computing[J].Computer sci- SHI Xianhong,SHI Jinling.A reduction algorithm based on ence,2014,41(11A):313-315,346 relative granularity in incomplete decision tables[].Journal [15]张清国，郑雪峰.相容矩阵的高效属性约简算法[J] of Henan normal university:natural science,2010,38(4): 小型微型计算机系统，2012,33(9)：1944-1947. 51-53.84 ZHANG Qingguo,ZHENG Xuefeng.An efficiency attribute [7]张清国，郑雪峰.基于知识粒度的不完备决策表的属性 reduction algorithm of tolerance matrix[J].Journal of 约简的矩阵算法[J].计算机科学，2012,39(2)：209- Chiese computer systems,2012,33(9):1944-1947. 211.243 [16]梁吉业，李德玉.信息系统中的不确定性与知识获取 ZHANG Qingguo,ZHENG Xuefeng.Discernibility matrix [M.北京：科学出版社，2005：1-70. algorithm of attribute reduction based on knowledge granu- [17]王炜，徐章艳，李晓瑜不完备决策表中基于对象矩阵 laion in incomplete decision table[J].Computer science, 属性约简算法[J].计算机科学，2012,39(4)：201- 2012,39(2):209-211,243. 204. [8]张伟，徐章艳，王晓宇.一种结合概率启发信息和知识 WANG Wei,XU Zhangyan,LI Xiaoyu.Attribute reduction 粒度的属性约简算法[J].计算机应用与软件，2013,30 algorithm based on object matrix in incomplete decision ta- (7):43-45,50. ble[J].Computer science,2012,39(4):201-204. ZHANG Wei,XU Zhangyan,WANG Xiaoyu.An attribute [18]周建华，徐章艳，章晨光.一种基于冲突域的不完备决 reduction algorithm combining probability heuristic informa- 策表属性约简算法[J].计算机应用与软件，2014,31 tion and knowledge granularity[].Computer applications (3):239-241,255. and software,2013,30(7):43-45,50. ZHOU Jianhua,XU Zhangyan,ZHANG Chenguang.An [9]PAWLAK Z.Rough sets and intelligent data analysis[J]. incomplete decision table attribute reduction algorithm Information sciences,2002,147(1-4):1-12. based on conflict region[J].Computer applications and [10]王炜，徐章艳，李晓瑜.不完备决策表中基于对象矩阵 software,2014,31(3):239-241,255 属性约简算法[J].计算机科学，2012,39(4)：201- 作者简介： 204. 乔丽娟，女，1988年生，硕士研究 WANG Wei,XU Zhangyan,LI Xiaoyu.Attribute reduction 生，主要研究方向为数据挖掘及粗糙集 algorithm based on object matrix in incomplete decision ta- 理论。 ble[J].Computer science,2012,39(4):201-204. [11]舒文豪，徐章艳，钱文彬，等.一种快速的不完备决策 表属性约简算法[J].小型微型计算机系统，2011,32 (9):1867-1871 SHU Wenhao,XU Zhangyan,QIAN Wenbin,et al.Quick 徐章艳，男，1972年生，教授，博士， attribution reduction algorithm based on incomplete deci- 主要研究方向为数据挖掘、模糊集、粗 sion table [J].Journal of Chinese computer systems, 糙集理论。主持国家自然科学基金项 2011,32(9):1867-1871. 目1项，参与国家自然科学基金项目2 [12]韩智东，王志良，高静.用差别矩阵思想设计的基于正 项，主持省部级科研项目1项：厅局级 区域的高效属性约简算法[J].小型微型计算机系统， 项目2项：主持校级项目2项。发表学 2011.32(2):299-304. 术论文被SCI检索3篇，被EI检索5篇。 HAN Zhidong,WANG Zhiliang,GAO Jing.Efficient at- tribute reduction algorithm based on the idea of discern- 谢小军，男，1990年生，硕士研究 ibility object pair set[].Journal of Chinese computer sys- 生，主要研究方向为数据挖掘及粗糙集 tems,2011,32(2):299-304. 理论。 [13]钟珞，梅磊，郭翠翠，等.粒矩阵属性约简的启发式算 法[J].小型微型计算机系统，2011,32(3)：516-520
ＬＩ Ｘｉｕｈｏｎｇ， ＳＨＩ Ｋａｉｑｕａｎ． Ａ ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕｌａｔｉｏｎ－ｂａｓｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｕｎｄｅｒ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａ⁃ ｔｉｏｎ ｓｙｓｔｅｍｓ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２００６， ３３（ １１）： １６９⁃ １７０， １９９． ［６］史先红， 史进玲． 一种基于相对粒度的不完备决策表约 简算法［Ｊ］． 河南师范大学学报：自然科学版， ２０１０， ３８ （４）： ５１⁃５３， ８４． ＳＨＩ Ｘｉａｎｈｏｎｇ， ＳＨＩ Ｊｉｎｌｉｎｇ． Ａ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｒｅｌａｔｉｖｅ ｇｒａｎｕｌａｒｉｔｙ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｈｅｎａｎ ｎｏｒｍａｌ ｕｎｉｖｅｒｓｉｔｙ：ｎａｔｕｒａｌ ｓｃｉｅｎｃｅ， ２０１０， ３８（４）： ５１⁃５３， ８４． ［７］张清国， 郑雪峰． 基于知识粒度的不完备决策表的属性 约简的矩阵算法［ Ｊ］． 计算机科学， ２０１２， ３９（ ２）： ２０９⁃ ２１１， ２４３． ＺＨＡＮＧ Ｑｉｎｇｇｕｏ， ＺＨＥＮＧ Ｘｕｅｆｅｎｇ． Ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ ａｌｇｏｒｉｔｈｍ ｏｆ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕ⁃ ｌａｉｏｎ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１２， ３９（２）： ２０９⁃２１１， ２４３． ［８］张伟， 徐章艳， 王晓宇． 一种结合概率启发信息和知识 粒度的属性约简算法［Ｊ］． 计算机应用与软件， ２０１３， ３０ （７）： ４３⁃４５， ５０． ＺＨＡＮＧ Ｗｅｉ， ＸＵ Ｚｈａｎｇｙａｎ， ＷＡＮＧ Ｘｉａｏｙｕ． Ａｎ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｃｏｍｂｉｎｉｎｇ ｐｒｏｂａｂｉｌｉｔｙ ｈｅｕｒｉｓｔｉｃ ｉｎｆｏｒｍａ⁃ ｔｉｏｎ ａｎｄ ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕｌａｒｉｔｙ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ ｓｏｆｔｗａｒｅ， ２０１３， ３０（７）： ４３⁃４５， ５０． ［９］ ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ ａｎｄ ｉｎｔｅｌｌｉｇｅｎｔ ｄａｔａ ａｎａｌｙｓｉｓ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２００２， １４７（１⁃４）： １⁃１２． ［１０］王炜， 徐章艳， 李晓瑜． 不完备决策表中基于对象矩阵 属性约简算法［ Ｊ］． 计算机科学， ２０１２， ３９ （ ４）： ２０１⁃ ２０４． ＷＡＮＧ Ｗｅｉ， ＸＵ Ｚｈａｎｇｙａｎ， ＬＩ Ｘｉａｏｙｕ． Ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｏｂｊｅｃｔ ｍａｔｒｉｘ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａ⁃ ｂｌｅ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１２， ３９（４）： ２０１⁃２０４． ［１１］舒文豪， 徐章艳， 钱文彬， 等． 一种快速的不完备决策 表属性约简算法［ Ｊ］． 小型微型计算机系统， ２０１１， ３２ （９）： １８６７⁃１８７１． ＳＨＵ Ｗｅｎｈａｏ， ＸＵ Ｚｈａｎｇｙａｎ， ＱＩＡＮ Ｗｅｎｂｉｎ， ｅｔ ａｌ． Ｑｕｉｃｋ ａｔｔｒｉｂｕｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉ⁃ ｓｉｏｎ ｔａｂｌｅ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０１１， ３２（９）： １８６７⁃１８７１． ［１２］韩智东， 王志良， 高静． 用差别矩阵思想设计的基于正 区域的高效属性约简算法［ Ｊ］． 小型微型计算机系统， ２０１１， ３２（２）： ２９９⁃３０４． ＨＡＮ Ｚｈｉｄｏｎｇ， ＷＡＮＧ Ｚｈｉｌｉａｎｇ， ＧＡＯ Ｊｉｎｇ． Ｅｆｆｉｃｉｅｎｔ ａｔ⁃ ｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｉｄｅａ ｏｆ ｄｉｓｃｅｒｎ⁃ ｉｂｉｌｉｔｙ ｏｂｊｅｃｔ ｐａｉｒ ｓｅｔ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓ⁃ ｔｅｍｓ， ２０１１， ３２（２）： ２９９⁃３０４． ［１３］钟珞， 梅磊， 郭翠翠， 等． 粒矩阵属性约简的启发式算 法［Ｊ］． 小型微型计算机系统， ２０１１， ３２（３）： ５１６⁃５２０． ＺＨＯＮＧ Ｌｕｏ， ＭＥＩ Ｌｅｉ， ＧＵＯ Ｃｕｉｃｕｉ， ｅｔ ａｌ． Ｈｅｕｒｉｓｔｉｃ ａｌｇｏ⁃ ｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｏｎ ｇｒａｎｕｌａｒ ｍａｔｒｉｘ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０１１， ３２（３）： ５１６⁃５２０． ［１４］唐孝， 舒兰． 基于粒计算的属性约简改进算法［ Ｊ］． 计 算机科学， ２０１４， ４１（１１Ａ）： ３１３⁃３１５， ３４６． ＴＡＮＧ Ｘｉａｏ， ＳＨＵ Ｌａｎ． Ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ ａｔｔｒｉｂｕｔｅ ｒｅ⁃ ｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｇｒａｎｕｌａｒ ｃｏｍｐｕｔｉｎｇ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉ⁃ ｅｎｃｅ， ２０１４， ４１（１１Ａ）： ３１３⁃３１５， ３４６． ［１５］张清国， 郑雪峰． 相容矩阵的高效属性约简算法［ Ｊ］． 小型微型计算机系统， ２０１２， ３３（９）： １９４４⁃１９４７． ＺＨＡＮＧ Ｑｉｎｇｇｕｏ， ＺＨＥＮＧ Ｘｕｅｆｅｎｇ． Ａｎ ｅｆｆｉｃｉｅｎｃｙ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｏｌｅｒａｎｃｅ ｍａｔｒｉｘ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０１２， ３３（９）： １９４４⁃１９４７． ［１６］梁吉业， 李德玉． 信息系统中的不确定性与知识获取 ［Ｍ］． 北京： 科学出版社， ２００５： １⁃７０． ［１７］王炜， 徐章艳， 李晓瑜．不完备决策表中基于对象矩阵 属性约简算法［ Ｊ］． 计算机科学， ２０１２， ３９ （ ４）： ２０１⁃ ２０４． ＷＡＮＧ Ｗｅｉ， ＸＵ Ｚｈａｎｇｙａｎ， ＬＩ Ｘｉａｏｙｕ． Ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｏｂｊｅｃｔ ｍａｔｒｉｘ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａ⁃ ｂｌｅ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１２， ３９（４）： ２０１⁃２０４． ［１８］周建华， 徐章艳， 章晨光． 一种基于冲突域的不完备决 策表属性约简算法［ Ｊ］． 计算机应用与软件， ２０１４， ３１ （３）： ２３９⁃２４１， ２５５． ＺＨＯＵ Ｊｉａｎｈｕａ， ＸＵ Ｚｈａｎｇｙａｎ， ＺＨＡＮＧ Ｃｈｅｎｇｕａｎｇ． Ａｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｎｆｌｉｃｔ ｒｅｇｉｏｎ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ ｓｏｆｔｗａｒｅ， ２０１４， ３１（３）： ２３９⁃２４１， ２５５． 作者简介： 乔丽娟，女，１９８８ 年生，硕士研究 生，主要研究方向为数据挖掘及粗糙集 理论。 徐章艳，男，１９７２ 年生，教授，博士， 主要研究方向为数据挖掘、模糊集、粗 糙集理论。 主持国家自然科学基金项 目 １ 项，参与国家自然科学基金项目 ２ 项，主持省部级科研项目 １ 项；厅局级 项目 ２ 项；主持校级项目 ２ 项。 发表学 术论文被 ＳＣＩ 检索 ３ 篇，被 ＥＩ 检索 ５ 篇。 谢小军，男，１９９０ 年生，硕士研究 生，主要研究方向为数据挖掘及粗糙集 理论。 第 １ 期 乔丽娟，等：基于知识粒度的不完备决策表的属性约简算法 ·１３５·