基于粒计算的信息系统规则提取方法

陈志恩，马 旭

(宁夏师范学院 数学与计算机科学系,宁夏 固原 756000)

0 引言

数据挖掘技术始于20世纪80年代，是数据库技术的进一步扩展，它是从大型数据库或数据仓库中储存的大量、不完整、有噪声的数据中发现潜在有用的、新颖的、最终能被用户理解的知识过程.目前，数据挖掘已经成为智能信息处理研究领域的热点，并应用于许多科学与工程领域[1].然而，从复杂数据中获取的知识在很大程度上都是以规则的形式给出，因而，规则获取方法的研究成为数据挖掘领域的重要课题之一.

在决策信息系统规则提取过程中，用粗糙集理论[2]挖掘规则的关键在于属性约简，即去掉决策表中相对于决策属性而言的冗余条件属性和属性值.从粒计算的角度来看，属性约简的目的就是在条件属性集中寻找一个属性子集，该子集对论域形成的划分空间是在保持某种属性重要度不变的前提下粒度最粗的划分空间.不管哪种属性约简方法，其实质就是删除冗余属性.典型的约简算法有：基于布尔推理的最小决策算法[3]、基于正区域和基于区分矩阵的属性约简算法[4-5]、利用信息熵作为启发式信息来获取最小约简或相对约简[6]等.本文借助关系的粒矩阵表示和矩阵运算简便直观的特点，首先在粒关系包含度矩阵中获得给定阈值的初始决策规则集，然后以该决策规则集合中所包含的元素个数作为启发式信息对决策信息系统进行属性约简，最后在约简的属性集上提取适应性和应用价值较高的决策规则.与传统的决策规则提取算法相比较，该算法通过构造合理的属性重要度函数进行属性约简，在一定程度上降低了算法的复杂度，提高了算法的效率.

1 基本概念

若A=C∪D且C∩D=∅,D≠∅，则称该信息系统为决策信息系统，有时也称为决策表,其中：C是条件属性集，D是决策属性集，决策信息系统中的每一行代表一条决策规则.

对任意条件属性C′⊆C,定义一个U上的不可分辨关系：

其中IND(C′)是U上的等价关系，所有等价类的集合记为U/IND(C′).

定义1[7]设S=(U,A,V,f)是一决策信息系统，若条件属性C′(C′⊂C)和决策属性D对论域U的划分为：

则称等价类Xi,Xj为信息粒.分别用一个长度为l的二进制向量表示，即有

定义1将原始以个体为单位的决策信息系统转换为以信息粒(等价类)为单位的决策信息系统，系统的知识粒度变粗.

定义3[6]定义粒矩阵MGr={Xm×l,Ys×l}，其中

称矩阵X为条件粒矩阵(条件信息粒)，称矩阵Y为决策粒矩阵(决策信息粒).

定义4[9]设S=(U,C∪D,V,f)为一决策信息系统，矩阵X,Y分别为S的条件粒矩阵与决策粒矩阵，记

则MC称为矩阵X与Y的粒关系包含度矩阵.

注1:公式(7)中，元素

2 基于粒计算的属性约简

根据定义4，对给定的阈值α，令集合

定义6[9]在一个决策信息系统S=(U,C∪D,V,f)中，如果P⊆C，若P中的每一个r都是P中相对于决策属性D不可省略的，则称P相对于决策属性D是独立的，简称P是独立的.

定义7[9]给定决策信息系统S=(U,A,V,f)，对任意B⊆C,若B满足下列条件：

( i )POSB(D)=POSC(D);

( ii )B相对于D是独立的.

则称B是该决策信息系统的一个相对约简.

3 基于粒计算的决策信息系统规则提取

属性约简和规则提取是知识获取的两个主要阶段，不同的研究者从不同的角度得到约简的决策规则，在文中第2节属性约简的基础上，给出一种决策信息系统的规则提取方法.

证明分两种情况：

下面举例说明定理2的规则提取方法.

例1设决策信息系统S=(U,C∪D,V,f)如表1所示，其中{c1,c2,c2}为条件属性，{d}为决策属性.

表1 决策信息系统

由表1计算得到决策属性{d}的粒矩阵为

条件属性P={c1,c2,c3}的粒矩阵X为

条件属性P1={c2,c3}的粒矩阵XP1为

条件属性P2={c1,c3}的粒矩阵XP2为

条件属性P3={c1,c2}的粒矩阵XP3为

由公式(7)计算可得粒矩阵X与Y的粒关系包含度矩阵为

同理，粒矩阵XP1,XP2,XP3分别与Y的粒关系包含度矩阵为

例1表明，在决策信息系统中，随着阈值α的减小，决策规则个数会逐渐增多，同时决策规则覆盖的范围会扩大;另外,借助粒矩阵这一代数运算能够有效降低决策规则提取的复杂度,提高算法的效率.

4 算法描述

下面给出基于上述粒计算的决策信息系统规则获取算法描述.

1)求核算法

输入：决策信息系统S=(U,C∪D,V,f)，C为条件属性，D为决策属性.

输出：属性集C的核CORE(C).

第1步.设CORE(C)=∅;

2)属性约简算法

输入：决策信息系统S=(U,C∪D,V,f).

输出：属性集C的约简RED(C).

第1步.依照求核算法求出决策信息系统S的核CORE(C)；

第5步.输出B∈RED(C)，算法结束.

3)规则提取算法

输入：决策信息系统S=(U,C∪D,V,f).

输出：决策信息系统S的决策规则.

第1步.依照属性约简算法求出属性集C的相对约简B=RED(C)；

该算法的复杂度主要在求核算法和属性约简算法，求核算法中信息粒的粒化过程的算法复杂度为O(n),属性约简算法中计算粒关系包含度矩阵的算法复杂度均为O(n2).因此，整个规则提取过程的算法复杂度为O(n2).

5 结束语

运用关系粒矩阵的代数运算，在粒关系包含度矩阵中挖掘隐含的信息作为启发式算子对决策信息系统进行属性约简，然后在约简属性集的基础上提取相应的决策规则.与传统的决策规则提取算法相比，该算法借助粒矩阵计算这一代数工具，通过构造合理的属性重要度函数进行属性约简，在一定程度上降低了算法计算的复杂度，提高了算法的效率.另外，该算法容易在计算机上实现，这为借助矩阵工具研究信息系统规则提取提供了一种新的思路.