第3卷第6期 智能系统学报 Vol.3 No.6 2008年12月 CAAI Transactions on Intelligent Systems Dec.2008 规则分层约简算法 尹林子12，阳春华，柱卫华，李勇刚 (1.中南大学信息科学与工程学院，湖南长沙410083：2.中南大学物理科学与技术学院，湖南长沙410083) 摘要：针对传统粗糙集方法处理问题时所遇到的离散化以及属性约简的NP难题，将粗糙集中下近似概念与分层 思想相结合，提出一种新的粗糙集数据处理方法一规则分层约简算法HRR.该算法直接从决策表中提取规则，利 用对规则进行约简来代替属性约简，以避开NP推题，同时针对传统离散化算法对不同离散化区间采取不同编码的 局限，实现了不同区间的聚类编码，并在此基础上提出等价决策表的概念.实例表明，HRR算法在计算量以及性能上 具有非常明显的优势， 关键词：全局启发；规则约简：粗糙集；等价决策表 中图分类号：TP18文献标识码：A文章编号：1673-4785(2008)06049206 Hierarchical reduction of rules YIN Lin-zi2,YANG Chun-hua',GUI Wei-hua',LI Yong-gang (1.School of Information Science and Engineering,Central South University,Changsha 410083,China;2.School of Physics Science and Technology,Central South University,Changsha 410083,China) Abstract:In order to resolve the NP-hard problem in the discretization,or reduction process,using traditional rough set theory,a new data processing approach for the rough set process-hierarchical reduction of rule (HRR) was formulated.It integrates the low approximation of the rough set and the hierarchical methods.Rules are extrac- ted directly from decision tables and rule reduction is used to replace attribute reduction for evading the NP-hard problem.Also,the same clustering code is used for different segments,while the traditional method must use dif- ferent codes for different clustering segments.An equivalent decision table is also put forward.Some examples il- lustrate its obvious advantage in computational time and performance. Keywords:whole heuristic;reduction of rules;rough set;equivalent decision table 粗糙集理论是20世纪80年代由波兰的Pawlak性.首先，连续属性的最优离散化问题是一个NP 教授提出的一种新型的处理模糊性和不确定性知识(non-deterministic polynomial)难题3)]，因此对具有 的数学工具，并且具有不需要外界信息和先验知 丰富样本的信息系统而言，求得最优离散化结果的 识的独特优势[2].目前，粗糙集理论同神经网络、模 时间开销将是令人无法忍受的；其次，Wong和Ziar 糊理论、专家系统、遗传算法和证据理论等结合已被 ko已经证明找出一个决策表的最小约简也是NP难 应用于知识获取、数据挖掘、信息融合、决策分析和 题41；第三，通过传统算法得到的规则是一种被动 决策支持、模式识别、机器学习、故障诊断和控制算 的规则，它完全取决于离散化以及属性约简过程，而 法获取等各种应用领域.粗糙集对数据处理的流程 这些过程的处理目标往往又不是针对最简的规则， 如下：先把数据离散化、编码、形成决策表、约简决策 因此传统算法得到的规则有可能不是最简的. 表之后再提取规则.思想在于利用最简的决策表来 为了解决属性约简的P难题，很多学者展开 提取最简的规则.但是这种传统的方法有一些局限 了相关的研究，采用启发式算法以避免NP难题，主 收稿日期：2008-03-17. 要包括矩阵类方法、属性重要度方法以及分层约简 基金项目：国家自然科学重点基金资助项目(60634020)：国家自然科 方法等.如文献[5]基于二进制可辩识矩阵进行属 学基金资助项目(60874069). 通信作者：尹林子.E-mail:nihaoylz@126.com 性约简，取得了良好的效果；文献[6]分析属性约简