第 31 卷第 3 期 2012 年3 期 煤 炭 技 术 Coal Technology Vol.31,No.03 March,2012 基于属性重要性的启发式属性约简算法 李 菊 （常熟理工学院 计算机科学与工程学院，江苏 常熟 215500） 摘 要:针对粗糙集理论中的属性约简问题做了探讨研究。从寻找属性约简的角度，首先描述了决策表中的属性的 重要性,并利用已求得的正区域使处理数据的范围不断缩小，约简集中的属性从核集开始, 通过向属性核添加重要 性最大的属性，得到属性的最小相对约简。从而减少求约简的时间。最后进行实证, 该算法同传统的算法相比，在 计算量减少的同时能得到更简约的结果，证明了该算法的正确性和可行性。 关键词:粗糙集；属性约简；正区域；启发式算法 中图分类号:TP311 文章编号:1008-8725（2012）03-0201-03 文献标识码:A Heuristic Reduction Algorithm Based on Attribute Importance （(School of Computer Science and Engineering, Changshu Institute of Technology, Changshu 215500, China） LI Ju rough set Abstract:This article has done the research on attribute reduction of theory. This looking for attribute reduction, This paper first described the paper is from the perspective of properties importance in the decision-making table and use the positive region which has been obtained, narrowed the scope of data processing, attribute reduction begin with core set, through adding the attributes which are the most important to properties nuclear, get the smallest relative reduction of properties. Thereby it reduced the time of demanding reduction. Finally, an example of a complete demonstration of the algorithm with the traditional method, in calculating the amount of the reduction at the same time can be more simple result The results proved that the correctness and feasibility of the algorithmis. Key words:rough set; attribute reduction; positive region; heuristic algorithm the method, confirmed that 0 引言 粗糙集（Rough Set，简写为 RS）是波兰学者 Z. Pawlak 为开发自动规则生成系统及研究软计算问题 于 1982 年提出的[1]。粗糙集的核心问题是属性约简 [2-3]和规则约简[4]。最早的属性约简方法是文献[1]给 出的理论方法，是在等价关系下讨论了属性取有限 个数值的信息系统的约简。文中通过对各类属性重 要性算法的研究，提出了一种改进的属性约简算法， 就是利用已求得的正区域使处理数据的范围不断缩 小从而减少求解约简的时间，实验结果证实了该算 法的可行性。 1 粗糙集的约简和核值 粗糙集理论是用来描述不完整和不确定性的． 粗糙集理论从新的角度对知识进行了定义，粗糙集 理论的思想是把知识看作是关于论域的划分，并且 认为知识是有粒度的。在保持信息系统分类能力不 变的前提下，利用已知的知识库，把不精确或不确定 的知识用知识库中已知的知识来近似刻画，通过知 识的补充、约简，导出问题的决策或分类规则[5-6]。 定义 1 信息系统 信息系统被定义为如下的四元组：S= U,A,V,R 其中 S 为知识表达系统，U= x1 ,x2 ,…,xn 空有限集合，也称论域；A= a1 ,a2 ,…,am R R Rf 。 R为对象的非 R为属性的非 a∈ A 空有限集合；V 为属性值域，V= ∪Va；f：U×A→V 为 一信息函数，表示对每一个 a∈A,x∈U,f x,R Ra ∈Va。 当信息系统中属性 A=C∪D，其中 C 为条件属性集， D 为决策属性集时，信息系统也称为决策系统。决策 系统是最为常见的信息系统。信息系统的数据以关 系表的形式表示，关系表的行对应要研究的对象，列 对应对象的属性，对象的信息是通过指定对象的各 属性值来表达。容易看出，一个属性对应一个等价关 系，一个表可以看作是定义的一族等价关系，即知识 库。 定义 2 近似集包含在 X 中的最大可定义集称 为 X 的 R 下近似： R R RX = x∈U| → →x R 哿 R RX 收稿日期:2011-07-28;修订日期:2012-01-07 作者简介:李菊（1981-），女，江苏常熟人，讲师，研究方向：粗糙集与图形学。 中国煤炭期刊网 www.chinacaj.net

·202· 煤 炭 技 术 第 31 卷 包含 X 的最小可定义集称为 X 的 R 上近似：R軍 ∪ 軍 軍X = x∈U| ∈ ∈x R ∩X≠ ∪准 集合的下近似与上近似也可以用下面的等式来 ∪X , R軍 ∪ 哿X =∪ ∪ 表 示 ， 即 R ∪ 軍X =∪ Y∈U/R|Y哿 ∪ Y哿U/R|Y∩X≠ ∪准 定义 3 等价类 设有决策系统 S= U,C∪D,V, ∪ 軍f ，其中 C，D 分别 表示条件属性和决策属性，则决策属性在条件属性 C ∪ 軍X ，POSC 下的正区域可定义为 POSC （D）表明根据 C 的知识所进行的划分 U/C，能够确切 地划入 U/D 类的对象集合。 （D）= ∪ X∈U1 /D 令 R 为一等价关系族，且 r∈R，当 IND ∪ 軍R = 軍，称 r 为 R 中可省略，否则 r 为 R 中不 IND R- ∪∪r∪ 可省略的。 当对于任一 r∈R，若 R 不可省略，则族 R 为独 立的。 定义 4 属性的重要性 在决策系统 S= U,C∪D,V, ∪ 軍f 中，a∈C，的属性 重要性定义为 σ C,∪ 軍D ∪ 軍a = γC ∪ 軍D -γC-∪∪a ∪ 軍D =1- γC-∪∪a ∪ 軍D γC ∪ 軍D γC ∪ 軍D ∪ 在决策系统 S= U,C∪D,V, 軍f 中，P哿C 的属性重 要性定义为 σ C,∪ 軍D ∪ 軍P = γC ∪ 軍D -γC-∪∪P ∪ 軍D =1- γC ∪ 軍D 定义 5 在知识表达系统 S= U,C∪D,V, U1哿U，U1≡空集，则限制在 U1 U1 SIG C ∪ 軍D = ∪ X∈U1 /D C_ ∪ 軍X ，简称为在 U1 γC-∪∪P ∪ 軍D γC ∪ 軍D ∪ 軍f 中, 上的 D 的 C 正域为 上的限制正 域。 ∪ 定理：设 S= U,C∪D,V, 軍f 是个知识表达系统， C∩D=空集，C 为条件属性集，D 为决策属性集，令 P奂C，a∈C-P，则通过添加属性 a 到 p 使得 P∪ ∪ ∪a 在 U 上所形成的 D 正域满足：POS p ∪ 軍D P∪∪∪a =POS U u ∪POS U1 P∪∪∪a ∪ 軍D ，其中 U1=U-POSp ∪ 軍D 由本定理可知：求一个属性集合 P 添加一个属 性 a 后所形成的新的 POSP∪∪∪a ∪ 軍D 时，只需在子对 象集合 U-POSp ∪ 軍D 上求解限制正域，所以可以大大 缩短了求正域的时间。 2 最简规则获取算法 在决策系统中，每一条记录都可以得到一条决 策规则，而得到的这些决策规则集因为太长了，需要 进行简化，也就是说对于每一个决策类所决定的决 策规则能用最少的属性来表达。 本文算法主要思想是该算法利用已求得的正区 性。如表 1： 论域 表 1 算法验证实例 条件属性 决策属性 域与限制正域的概念使处理数据的范围不断缩小， 从而减少求解约简的时间，以属性核为起点并结合 算子，通过向属性核添加重要性最大的属性，得到属 性的最小相对约简。 算法的步骤如下： 步骤 1 计算决策属性 D 的 C 正域 POSc ∪ 軍D ; 令 COREX ∪ 軍C =空集，计算每个属性 c∈C 在 C 中对 D 的重要性 SIGX C ∪ 軍C ≠0，则 COREX ∪ 軍C =COREX ∪ 軍C ∪ ∪ ∪c ，最后得到 COREX ∪ 軍C 为 C 相对于 D 的相对核。令 A=COREX ∪ 軍C C ∪ 軍C ，若 SIGX 步骤 2 若 POSA ∪ 軍D =POSC ∪ 軍D ，则终止计算。 这时 COREX ∪ 軍C 为 C 相对于 D 的一个相对约简；否 则，执行步骤 3。 步骤 3 令 I=1 时，有 U1=U-POSA ∪ 軍D 。 步骤 4 从 I=1 开始对条件属性子集 C-A 重复 执行： （1）对每个属性 c∈C-A，计算属性 c 添加到 A 后在 UI 上的正域 POS 都为 0，则输出约简； U1 A∪∪∪c ∪ 軍D POS U1 A∪∪∪c ∪ 軍D （2）找出 U1 POS A∪∪∪c ∪ 軍D 最大的属性 c 所成的 集合 T； （3）对 T 中每一个属性 q 进行分支计算，A=A∪ ∪ ∪q ； （4）I=I+1，计算 POSA ∪ 軍D 和 U I =U I-1 -POS UI -1 A ∪ 軍D ； IF（POSA ∪ 軍D =POSC ∪ 軍D ）{输出 C 相对于 D 的某 个约简，并且 T=T- ∪ ∪q ；如果 T 不为空，转（3）；否则 转步骤 5 ELSE 转（1） 步骤 5 最后得到所有相对约简。 3 实证分析 文中通过一个实例来分析改进后的算法的优越 a 0 0 0 1 1 b 0 0 0 1 1 c 2 0 3 0 0 d 1 0 0 1 0 1 2 3 4 5 步骤 1 U/C={{1}，{2}，{3}，{4，5}}，U/D={{2，3，5}， {1，4} }，POS （ C）（D）={{1}，{2}，{3}}；U/（C- ∪ ∪a ）={{1}， {2}，{3}，{4，5}}，U/（C - ∪ ∪b ）={{1}，{2}，{3}，{4，5}}，U/ （C - ∪ ∪c ）={{1，2，3}，{4，5}}，U/D ={{1，4}，{2，3，5}}， POS（C- ∪ ∪a ）（D）=POS（C- ∪ ∪b ）（D）=POS（C）（D）= {{1}，{2}，{3}}，POS ∪ ∪c （D）=准。 因 为 SIG C ∪ 軍C = D 中国煤炭期刊网 www.chinacaj.net

第 31 卷第 3 期 2012 年3 期 煤 炭 技 术 Coal Technology Vol.31,No.03 March,2012 采用蚁群算法及移动 Agent 的网格服务发现设计 付 雯，李 响 （重庆电子工程职业学院，重庆 401331） 摘 要:网格技术是未来最有发展前途的网络技术之一，网格资源的发现相比于一般的网络管理更为复杂，研究了 基于移动 Agent 的网格服务发现，以及蚁群算法在网格服务资源调度中的运用。 关键词:网格服务；发现；蚁群算法；移动 Agent 中图分类号:TP393 文章编号:1008-8725（2012）03-0203-03 文献标识码:A Discovery Design on Ant Colony Algorithm and Mobile Agent Grid Service （Chongqing College of Electrontc Engineering, Chongqing 401331, China） FU Wen, LI Xiang the most promising one of network technology, Abstract:The grid technology is discovery compared with general network management grid services based on mobile agent scheduling service the application. Key words:grid services; discovery; ant colony algorithm; mobile agent resource this paper studied the findings, and ant colony algorithm in the grid resources is more complex, D D POSC D -POSC-c D ，所以 SIG =0，SIG C a =SIG C c ≠0 所以得 A=CORED C = c ； 步骤 2 U/A=U/ c ={{2，4，5}，{1}，{3}},POSA {{1}，{3}}≠POS（ C）（D）,所以，A 不是最小约简。 （D）= 步骤 3 使 I=1，UI=U-POSA 步骤 4 C-A= a， b ， （1） UI/D={{2，5}，{4}},UI/A∪ a ={{1}，{2}，{3}， （D）={{2}，{4}，{5}}； {4，5}}，UI/A∪ b ={{1}，{2}，{3}，{4，5}}，POS A∪a D A∪b D ={{1}，{2}，{3}},所以 a ， b 的重要性 U1 U1 =POS 程度是一样的，取 T= a, b 。 U1 （2）首先考虑 a，A=A∪ a = a, c ，POS A D = {{2}，{4，5}}，U/A =U/（C -b）,POS A D =POS C-b D = POS（C）（D）,所以，RED1= a, c 是其中的一个约简。 （3）其次考虑 b，A=A∪ b = b, c ，POS={{2}， {4，5}}，U/A =U/（C -a）,POS A D =POS C-a D =POS （C）（D）,所以，RED2= b, c 也是其中的一个约简。 通过以上的分析可以看出，文中提出的新的算 法在搜索最优或次优约简上优于传统的算法。 4 结语 D C b 属性约简能够简化信息系统，约简是最有必要 且最少的信息。该文提出了一种由核属性向多属性 逐渐扩张的获取最简规则知识的方法，综合考虑正 区域和边界域，提出了一种基于属性重要性的度量 U1 A∪c D ，实验证明，该算法优于 方法，构造了 POS 仅以正区域为启发信息的约简算法。为寻找最小条 件属性约简的算法，减少了搜索的空间，在理论及应 用上都是很有意义的。 参考文献： [1] Pawlak Z. Rough sets: Theoretical aspects of reasoning about data[M]. Boston: Kluwer Academic Publishers,1991. [2] 常犁云.粗糙集属性约简与算法的研究及其应用[D].重庆:重庆邮 电学院，1999. [3] 支天云，苗夺谦.二进制可辨别矩阵的变换及高效属性约简算法 的构造.计算机科学，2002（2）:140-142. [4] Karno Bozi. Core searching on rough sets[C]. Proceedings of the 23rd Int Conf Information Technology Interface.Pula,Croatia: IEEE Press,2001:217-222. [5] Pawlak Z. Rough sets.Int.J.comput[J].Inf.Sci.,1982(11):341-356. [6] Pawlak Z. Rough classification. Int.J. Man[J]. Mach. Stud.，1984 (20):469-483. （责任编辑 张欣） 收稿日期:2011-09-06;修订日期:2012-01-08 作者简介:付雯（1981－），女,重庆人，讲师，硕士，从事应用软件、网格计算、云计算等问题研究。 中国煤炭期刊网 www.chinacaj.net