1. 引言
属性约简和值约简是粗糙集理论研究中的两个重要内容,属性约简是在保持与原有的数据库决策能力相同的情况下,选择问题最小属性子集,剔除数据中的没有利用价值成分的过程。在现实世界的问题中,由于噪音、误导和不相关属性的存在,使得属性约仅是在一定程度上去除了决策表中的冗余属性,但并没有完全去掉决策表中的不必要的信息。为此,还需要对决策表进行更深层次的处理,即对决策表进行值约简。值约简是去掉多余的属性值,用最少的条件属性值来区分每一个决策类,在不改变决策能力的基础上得到更加简化的规则集。值约简的研究方法有很多,比如一般的值约简算法、启发式值约简算法、基于决策矩阵的值约简算法、归纳值约简算法和Skowron算法等。本文主要研究基于归纳的值约简算法,并对算法的执行效果进行了实验验证,以及与启发式值约简算法进行了比较。
2. 粗糙集基本概念
粗糙集理论是一种对不确定性数据进行分析的理论,它的主要思想就是在保持信息系统分类能力不变的条件下,通过知识约简剔除数据中冗余的信息,从而得到问题的正确决策或数据分类。
2.1. 信息表和决策表
为一个信息表 [1] ,其中U为论域,是一非空有限对象集,即
;
是非空有限的属性集合;Va是属性a的值域,即
,
成为信息函数,使得对每一
,
,有
。在粗糙集理论中,信息表可简化
或
。
在信息表S中,如果属性集A由条件属性集C和决策属性集D组成,并且满足
,
,则称S为决策表,记为
。在决策表S中,若存在两行信息,其全部条件属性值相同,而决策属性值不相同,则称S为不相容决策表,否则为相容决策表。这里仅考虑相容决策表。
2.2. 知识和不可分辨关系
定义1:(知识和知识库)给定论域U和其对应的一个等价关系R,在等价关系R下对论域U的划分,称为知识,记为U/R。U上的一簇划分称为关于U的一个知识库。
设R是U上的一个等价关系,U/R表示R的所有等价类(或者U上的分类)构成的集合,[x]R表示包含元素
的R等价类。一个知识库就是一个关系系统
,其中R是论域U上的一簇等价关系。若
,且
,则∩P(P中所有等价关系的交集)也是一个等价关系,称为P上的不可分辨关系,记为ind(P),且有
。不可分辨关系ind(P)是U上的等价关系,它是粗糙集理论中最基本的概念,若
,则称对象x与y是P不可分辨的,即x,y存在于不可分辨关系ind(P)的同一个等价类中,依据等价关系簇P形成的分类知识,x与y无法分辨。
2.3. 约简和核
知识约简是粗糙集理论中的核心内容之一。所谓知识约简,就是在保证知识库分类能力不变的条件下,删除不相关或不重要的知识,它涉及的两个基础概念就是约简和核。
令A为一属性集,
,如果
,则称a为A中不必要的;否则a为A中必要的。
如果
都为A中必要的,则称A是独立的;否则称A是依赖的。
定理1:如果A是独立的,
,则P也是独立的。
设
,如果Q是独立的,且
,则称Q为P的一个约简。显然,P可以由多个约简。P中所有的必要属性组成的集合称为P的核,记作core(P)。
定理2:
。其中,red(P)表示P的所有约简的集合。
由上述定理可以看出,核这个概念的用处包含两个方面:一方面,核能够作为计算所有约简的基础,这是因为所有约简都包含它的核;另一方面,核可解释为在属性约简中不能去除的知识特征部分的集合。
定义2:相容决策信息系统
,对决策规则dx有
。如果对于
,有
,则属性a为决策规则dx的核值属性,a为dx中不可省略的;如果
,则属性a为决策规则dx的非核值属性,a为dx中可以省略的。
如图1所示,对于第一条决策规则
,
,去掉属性a,得
,所以属性a为该规则的非核值属性;去掉属性b,得
,所以属性b为该规则的核值属性。即对于这条决策规则,属性a可以省略,属性b不可以省略。
Figure 1. An instance of core attributes based decision rule
图1. 一个关于决策规则核值属性的例子
2.4. 值约简相关概念
对于一个决策表而言,它的约简主要有两方面:属性约简和值约简。属性约简是删除决策表中的不必要的条件属性,而值约简的目的在于删除论域中各条记录的多余属性值,也就是删除与决策规则不相关的条件属性的值,进一步简化决策表。
定义3:令
表示论域U上有决策属性划分的决策类集,对每一个决策等价类,定义决策规则类DRC为
,
其中des(Xi)表示对等价类Xi的描述,即等价类Xi对于各条件属性值的特定取值。
用core(y),
表示决策类y的核值属性集,core(dx)表示决策规则dx的核值属性集,则有
,,且
。
集合的幂集就是集合所有子集组成的集合。
定义4:令T(OA)为集合OA的幂子集,T1(OA)为集合OA的一阶幂集,给T1(OA)中元素赋以权值,有
,
,
。按
大小对T1(OA)中的元素进行排序,得到一阶有序幂子集OT1(OA)。
同理,Ti(OA)为集合OA的i阶幂集(
),给Ti(OA)中元素赋以权值,有
,
,
。按
大小对Ti(OA)中的元素进行排序,得到一阶有序幂子集OTi(OA)。
3. 归纳值约简算法的实现
值约简算法很多学者都在研究,比如文献 [2] - [10] ,这里主要实现归纳值约简算法。归纳值约简算法采用求解知识表达系统决策表的最小决策算法来求其约简,它可以通过分别求解各个决策规则类的最小决策算法来实现。对于每个决策规则类中的规则,首先计算其核值属性,然后判断核值属性是否能够决定该规则,如果能够决定,则输出规则并删除其等价规则;否则逐渐加入非核值属性,直到能够决定该规则,然后输出规则并删除其等价规则。具体实现方法如下:
步骤1:任意;
步骤2:如果
,则输出决策规则
,
,转步骤9;
其中,
,表示从
中删除规则dx':
,这里
。
步骤3:令
,
,在测度函数
下对A1,A2中的元素排序,得有序集OA1,OA2,则有序集
,且
,OA的m个有序幂子集分别为
,相应的元素个数为
;
步骤4:
;
步骤5:
;
步骤6:令
,如果
,输出
,转步骤9;
步骤7:
,如果
,转(6);
步骤8:
,如果
,转(5);
步骤9:如果
,转(1);
步骤10:结束。
通过以上步骤,可以求得各个决策规则类的最小决策算法,进而得到整个决策表的最小决策算法,达到对决策表进一步约简的目的。
系统流程图如图2所示。
Figure 2. Flow chart of induction value reduction algorithm
图2. 归纳值约简算法
归纳值约简算法的核心内容是最小决策算法。求解知识表达系统的最小决策算法,可以通过分别求解各个决策规则类的最小决策算法来实现。对于每个决策规则类中的规则,首先计算其核值属性,然后判断核值属性是否能够决定该规则,如果能够决定,则输出规则并删除其等价规则;否则,逐渐加入非核值属性,直到能够决定该规则,然后输出规则并删除其等价规则。流程图如图3所示。
Figure 3. Flow chart of minimum decision algorithm
图3. 最小决策算法流程图
由于本算法只考虑相容决策表,即不存在两条规则,条件属性值都相等而决策属性值不同,所以决策规则类DRC(y)可由U/D得到。
4. 结果分析
4.1. 简单例子
测试一个较为简单的例子,数据如图2所示。算出规则等价类DRC(y)。
所以7条规则划分为3个规则等价类,分别为:
1) 对于第一个规则等价类
选取第一条规则
,经计算其核值属性为b,由于
,即其核值属性不能决定该规则,需要进行进一步约简。
由于
的核值属性为a,所以等价类y1的核值属性
,则
,
,
,
,
,
,
,
则
。
令
,
,则输出规则:
,将该规则从规则等价类中删除。又
,将第2条规则从规则等价类中删除,该规则等价类约简完毕。
约简结果为:
2) 对于第二个规则等价类
选取第一条规则
,经计算其核值属性为a,由于
,即核值属性可以决定该规则,则输出规则:
,将该规则从规则等价类中删除。
选取第二条规则
,经计算其核值属性为b和d,由于
,即核值属性可以决定该规则,则输出规则:
,将该规则从规则等价类中删除。
该规则等价类约简完毕,约简结果为:
,
3) 对于第三个规则等价类
选取第一条规则
,经计算其核值属性为d,由于
,即核值属性可以决定该规则,则输出规则
,将该规则从规则等价类中删除。又
,将第5,6条规则从规则等价类中删除。
该规则等价类约简完毕,约简结果为:
然后计算每条规则覆盖的记录数:规则
,覆盖记录1、2,覆盖记录数为2;规则
,覆盖记录3,覆盖记录数为1;规则
,覆盖记录4,覆盖记录数为1;规则
,覆盖记录4、5和6,覆盖记录数为3。
约简结果如表1所示。
程序运行结果如图4所示,和预期结果一致。
表1. 约简结果
其中:×表示可为任意值,不影响结果
4.2. 性能分析
表2记录了测试的情况,包括约简前的条件属性数和记录数,以及约简后的规则数和约简时间。
由测试记录可知,约简时间与条件属性数和记录数都有关系。约简时间随着记录数的增加而增加,为了清楚地展现其增加趋势,绘制了随着记录数的增加,约简时间的变化的折线图图5。
由图5可知,随着记录数的增加,约简时间大致呈平方增加。分析其约简过程,发现删除重复记录的函数时间复杂度为O(n2),程序主算法最小约简算法的时间复杂度也是O(n2),所以,该程序的时间复杂度为O(n2) (其中n指约简前的记录条数)。
4.3. 对比分析
现在用相同的数据测试归纳值约简和启发式值约简,对比约简结果,验证结果是否正确。
分别使用两种算法对几个不同的数据集进行约简,结果对比如表3所示。
Figure 5. The tendency of reduction time
图5. 约简时间趋势图
表2. 测试时间分析
Table 3. The comparison of two reduction algorithms results
表3. 两种算法约简结果对比
由上面的结果可知:归纳值约简和启发式值约简只是约简方法不同,但是约简结果是大致一致的。为了对比两种算法的时间效率,分别用两种算法计算同样的数据,记录数和约简时间如表4所示(其中这些数据的条件属性数为6)。
为了更直观地反映其随着记录数增加,约简时间的变化趋势,绘制了图6所示折线图。
由图6可知:记录较少时两种算法所用时间差不多;随着记录数量的增加,归纳值约简的约简时间优于启发式值约简。
Figure 6. The time tendency comparison of two reduction algorithms
图6. 两种约简算法的时间趋势对比图
Table 4. The comparison of two reduction algorithms time
表4. 两种算法约简时间对比
5. 总结与展望
本文研究并实现了基础的基于归纳的值约简算法,它可以有效的去掉多余的属性值,在不改变决策能力的基础上得到更加简化的规则集,如此可以提高挖掘的效率,并帮助企业及用户更有效的挖掘需要的数据。
基金项目
本项目得到网络文化与数字传播北京市重点实验室开放课题资助;2017实培计划(毕设)项目资助。