规则挖掘是数据挖掘的一项重要内容,传统的基于粗糙集理论的规则挖掘方法是先求决策信息系粒计算的核心思想是对待求解的问题进行粒化,在多个粒度空间对问题进行分析和求解,进而合成原始问题的解,符合人类从多角度分析问题、求解问题的认知规律,并受到了研究者的关注.
本文将属性约简和属性值约简过程合二为一,以知识粒为单位挖掘规则.先对决策信息系统分层粒化,在不同粒度的知识空间下计算粒关系矩阵,并从中获取启发式信息根据启发式信息确定信息粒的属性值约简顺序,在此基础上去除冗余属性,并设定终止条件,实现决策规则的快速挖掘.理论分析和UCI数据集的测试结果表明,该算法能获得所有最简规则.
对决策信息系统挖掘规则的传统方法是先求属性约简,再逐行提取规则,中间包含了很多冗余计算,最后的结果也取决于属性约简结果的好坏,并且随着样本集的增大,算法复杂性将大大增加.对属性约简进行了粒度原理分析并指出,对决策信息系统进行属性约简得到的知识划分空间是极大近似划分空间,但该知识空间的知识粒并不一定是整个知识空间中最“粗”的粒.本文考虑在不同粒度层次的知识空间中挖掘规则.为便于算法说明,先给出符号定义.
3.1符号定义
为了不失一般性,假设决策信息系统有个条件属性,1个决策属性.为条件属性′所含条件属性的个数,表征系统的粒度,1;为粒度下的所有条件属性′,这样的条件属性有个;为中某一条件属性对应的条件粒矩阵;为决策属性对应的决策粒矩阵;×为粒关系矩阵.
3.2算法描述
基于粒计算的最简决策规则挖掘算法.输入:决策信息系统;输出:所有最简决策规则.
1)生成决策粒矩阵并取粒度=1.
2)对中每一个条件属性求条件粒矩阵和粒关系矩阵,计算1、2,保存相应数据并做以下处理:
①寻找是否存在2=1.若存在,则由性质3可知,对应信息粒可以完全区分某一决策类,约简过程中优先考虑,这样可以保证在区分能力不变的情况下得到的规则最少,约简相应的信息粒得到决策规则,否则转②;
②若不存在2=1,则对1值的大小进行比较,1值越大,对应信息粒的区分能力越大,同样可以保证在区分能力不变的情况下得到的规则最少.根据1值的大小确定信息粒的约简顺序,通过约简信息粒得到决策规则,转③;
算法主要考虑如何提高现有算法的计算效率,包括如何减少冗余计算,如何提高搜索效率,如何减少存储空间.按照启发式信息1、2对信息粒进行约简,同时去掉冗余属性,减少了传统先约简属性再约简属性值时的冗余计算.在同一粒度空间下进行搜索时使用启发式算子对不同知识空间进行选择和排序,提高了搜索效率.在最坏的情况下需要搜索2次,而在实际情况中,当数据本身的冗余性很大时,搜索空间要远远小于2,因为在该算法中加入启发式信息,同时设置终止条件,算法收敛更快.本文使用的矩阵是布尔稀疏矩阵。 2100433B
