基于属性值分类的多层次粗糙集模型  

A Multi-Level Rough Set Model Based on Attribute Value Taxonomies

作　　者：叶明全[1,3] 胡学钢[1] 胡东辉[1] 吴信东[1,2] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009 [2]Department of Computer Science,University of Vermont,Burlington,VT 05405,USA [3]皖南医学院计算机教研室,芜湖241002

出　　处：《模式识别与人工智能》2013年第5期481-491,共11页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.61229301、61273292、61272540);国家973计划项目(No.2013CB329604);国家863计划项目(No.2012AA011005);安徽省自然科学基金项目(No.11040606M138)资助

摘　　要：传统的粗糙集理论主要是针对单层次决策表的属性约简和决策规则获取研究.然而,现实中树型结构的属性值分类是普遍存在的.针对条件属性具有属性值分类的情况,结合全子树泛化模式,提出一种多层次粗糙集模型,分析决策表在不同层次泛化空间下相关性质.结合基于正区域的属性约简理论,提出属性值泛化约简概念讨论二者之间的关系,同时证明求解泛化约简是一个NP-Hard问题.为此,提出一种基于正区域的的启发式泛化约简算法,该算法采用自顶向下逐步细化搜索策略,能够在保持原始决策表正区域不改变的前提下,将决策表所有属性值泛化到最佳层次.理论分析和仿真实验表明,泛化约简方法能提高知识发现的层次和泛化能力.Most traditional studies on rough sets focus on finding attribute reduction and decision rules on the single level decision tables. However, attribute value taxonomies （AVTs） are usually predefined in applications and represented by hierarchy trees. Aiming at the attribute value taxonomies for condition attributes, the classical rough set model is extended to a multi-level rough set （MLRS） model combining with the full-subtree generalization mode. With decision table at different levels of generalization space, some properties of MLRS are obtained. Paralleling with attribute reduction based on positive region, a concept of attribute value generalization reduction in MLRS is introduced and the relations of generalization reduction and attribute reduction are analyzed. The computation of the generalization reduction in MLRS is proved to be a NP-hard problem. Then, a heuristic algorithm of generalization reduction based on the positive region of MLRS is proposed, which utilizes attribute value taxonomies to make top-down refinements. The attribute values are generalized to the optimal levels of their AVTs by the proposed algorithm, while the original positive region of the decision table keeps invariant. Theoretical analysis and simulation experiments illustrate that generalization reduction method improves the level and the generalization ability of knowledge discovery.

关 键 词：多层次粗糙集 属性值分类 泛化约简 属性约简 全子树泛化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]