基于概念格的不完备信息系统最简规则提取算法

概念格是以概念为元素的偏序集,通常可以对形式背景描述的完备信息系统进行分析和处理,然而在多数情况下信息系统是不完备的,粗糙集理论是一种刻画不完整、不确定性问题的有效方法.针对此问题,从粗糙集的角度出发,基于概念格理论定义一种描述不完备信息系统的增广形式背景,在此基础上,定义并讨论极概念和极概念格及其相关性质,进而提出增广形式背景的极概念生成算法.为了获得更加简洁的决策规则,同时提出一种新的无冗余属性的决策规则获取算法.通过实例计算和UCI数据集的对比实验,表明了所提出算法的可行性和有效性,特别地,当信息系统完备时极概念将退化为经典的概念.

Concise rule extraction algorithm of incomplete information system based on concept lattice

Concept lattice is a partial order set of concept elements, which can be used to analyze and process the complete information system described by a formal context. However, in most cases, the information system is incomplete. The rough set theory is an effective mathematical tool to deal with incompleteness and uncertainty. From the perspective of rough sets, an augmented formal context is defined to describe an incomplete information system. Then, the extreme concept and the extreme concept lattice are respectively defined on the basis of the concept lattice theory, and their properties are discussed. Furthermore, an extreme concept generating algorithm from the augmented formal context is proposed. In order to obtain a more concise decision rule, a new decision rule obtaining algorithm without redundant attributes is also proposed. Finally, calculation example and comparition of UCI dataset verify the feasibility and effectiveness of the proposed algorithm, particularly, when the incomplete information system becomes complete, the extreme concept degenerates into the classical concept.