基于粗集的最小规则集提取算法研究

鲍松堂

(五邑大学 信息学院，广东 江门 529020)

粗集理论是由波兰华沙理工大学PAWLAK Z教授[1-2]于1982年提出的，主要研究不完整数据、不精确知识的表达、学习、归纳等方法。从新的视角对知识进行了定义，将知识看作是关于论域的划分，并引入代数中的等价关系来讨论知识，为智能信息处理提供了有效的处理技术。目前已经在人工智能、机器学习与知识发现、模型识别、分类、故障诊断等方面得到了较成功的应用。

属性约简和规则提取是粗集研究的重要内容。基于粗集方法的规则抽取过程是规则简化的过程，以这样的方法决策可使用条件属性的最小集合来确定。由于冗余属性往往会降低数据挖掘结果的精度和解释能力，属性约简是为了去除信息表中的冗余条件属性，并为得到一个较好的规则集做准备。由于目前算法所生成的规则过多(包含许多无用规则)，不利于决策。参考文献[4]介绍了一种基于粗集的最小规则集提取算法，但其无法导出包含所有实例的有效性规则。参考文献[5]是一种改进的规则集提取算法，然而算法过程繁琐，在添加原子时太过单一。所以本文借用参考文献[3]中支持子集的选取方法选出规则，并且在此基础上提出了新的最小规则集提取算法。

1 准备知识

设U为非空的论域，R是U上的等价关系。参考文献[6]中将R称为不可区分关系，因而在U上产生一个分 类 U/R={Y1，Y2，… ，Ym}，Y1，Y2， … ，Ym是 通 过 等 价 关系R产生的等价关系类，也是关系R上的元素集。

对于任何X⊆U，通过关系R的元素集和上、下近似来描述X。

对于决策表 S=(U，C，D，f，V)，A=C∪D， 对于每个u∈U，定义一个函数r:θ→φ。r称为决策表S中的决策规则，θ和φ分别为决策规则θ→φ的因和果。定义原子条件集 M，表示为 M={(a，v)|∀a∈C，∀v∈Va}。用 C 来表示单一的原子条件，∀C∈M。则θ可以表示为多个C的交集，φ为对应的决策取值。

2个属性 a，b∈U，需要计算论域 U的下面分类U/ab：2个对象 u，v∈U在同一类当且仅当 a(u)=a(v)且b(u)=b(v)。对于属性集 X⊆A，按下面定义论域 U的分类：2个对象 a，b∈U在同一类当且仅当对每个 a∈X有a(u)=a(v)。

令W⊆U是U的子集，对于条件属性集X⊆C，定义W 的下近似为(X)=∪V∈U/X，V⊆WV；子集(X)称为 W 关于X的支持子集，sptX(W)=|(X)|/|U|称为W关于 X的支持度；定义 W 的上近似为(X)=∪V∈U/X，V∩W≠φV。

2 最小规则集提取算法

输入：输入决策表 S=(U，C，D，f，V)，U={u1，u2，…，un}，C={a1，a2，… ，am}是 条件属 性集 ，D 是决 策属 性集，U/D={Y1，Y2，…，Yk}。

输出：决策表 S的最小规则集。决策类Y1，Y2，…，Yk对应的决策属性 d的属性值分别为 v1，v2，…，vk；R为规则集，C表示原子条件，[C]表示决策表中该原子条件所覆盖的实例集合。

令 β=[C1]∩[C2]∩…∩[Ci]∩U′⊆Yj，

选取 1组元素最多的|β|(如果元素最多的不止 1组，则选取最先出现的进行计算)。

3 实例分析

决策表 如 表 1 所 示 ， 条 件 属 性 集 C={a1，a2，a3，a4，a5}，决策属性集 D={d}。

算法在实例中的运行过程如下：

表1 决策表

出的规则为：

如在算法中加入输出规则覆盖的实例和支持度，与上述规则对应的实例和支持度则分别为：

{覆盖实例：1，3，6，8，12。 支持度：31.25%}{覆盖实例 ：7，14。 支 持 度 ：12.5%}{覆 盖 实 例 ：15。 支 持 度 ：6.25%}{覆盖实例：10。支持度：6.25%}{覆盖实例：2,4,9,13,16。支持度：31.25%}{覆盖实例：5，11。支持度：12.5%}

本文通过分析粗集中支持子集的计算，结合最小规则集的提取过程，提出一种新的最小规则集提取算法。算法相对参考文献[4-5]，过程简单，规则提取完毕后不用再进行约简，通过实例证明了，在其协调决策系统中最小规则提取运行的有效性。

[1]PAWLAK Z.Rough sets[J].International Jounal of Information and Computer Science，1982(5):341-356.

[2]PAWLAK Z.Rough sets and intelligent data analysis[J].Information Science， 2002，147(1/4):1-12.

[3]张文修.粗糙集理论与方法[M].北京：科学出版社，2000.

[4]STEFANOWSKI J.On rough sets based approaches to induction of decision rules[A].Rough sets in knowledge discovery[C].Heidelbery:Physica Verlag.1998:500-529.

[5]吴顺祥.基于粗集理论的一种规则提取方法[J].厦门大学学报，2004(9):64-66.

[6]PAWLAK Z.Rough sets:Theoretical aspects of reasoning about data[M].Boston:Kluwer Academic Publishers，1991.