基于粗糙集的属性值约简算法研究

1、141科技资讯 科技资讯SCIENCE&TECHNOLOGYINFORMATION 2007NO.34学术论坛1引言粗糙集(Roughset 1理论是一种处理模 糊和不确定信息的新型数据分析工具,目前已 成为信息科学最活跃的研究领域之一。基于 粗糙集的属性值约简是利用决策逻辑消去决 策算法中每条决策规则的不必要条件。它是 针对每条决策规则, 去掉表达该规则的冗余 值,以便进一步使决策算法最小化。属性值约简与属性约简的原理都是删除 冗余信息过程,采用的手段都是通过求得核(核 值、 约简(约简值得到的。 将粗糙集理论应用 到数据挖掘技术上,利用粗糙集的知识约简, 精简数据挖掘出的各类规则,

2、对复杂系统的策 略研究具有广泛的意义。本文应用粗糙集理论,分析基于粗糙集的 常用属性值约简算法和相应的算法的复杂度, 并结合一种新约简算法实例分析研究,说明这 一算法的有效性。2传统的属性值约简算法定义 1 信息系统 S=(U,A,V,F 是一个 决策表, 其中 U 为非空有限集合, 称为全域。 全域 U 的元素被称为对象或者实例; A =C D,C 为条件属性集,即对象的特征;D=d为 决策属性集, 称为对象的分类, C D =; V 是属性值的集合。设 a 是任一属性,x i 是任一 个对象,则 f(x i ,a表示x i 在 a属性的取值。 信 息系统可简化表示为 S=(U,A。属性值约

3、简的思想是:决策表中每一行代 表一条决策规则,即计算每一条决策规则的条 件属性的核值。可以采用先将该行中一个条 件属性的值从表中删去,然后检查剩下的该行 中条件属性值是否可以唯一确定此行中的决 策属性,若果不是,那么删去的条件属性值就 是该行决策规则的核值。在求出所有的决策 规则的核值后的基础上,通过添加一些条件属性值到核值中,并保证每个条件属性是不可省 的 。常用的属性值约简算法有数据分析法和 区 分 矩 阵 法 。 2.1数据分析法其基本思想:在信息系统的决策表中,逐 一将属性集 A 中的属性删除,每删除一个属性 就检查决策表。如果没有出现新的不一致,则 删除该属性,否则该属性不能被删除。

4、若决策 表可以表示成 R 1 d 1,R 2 d 2,当 d 1 d 2时 有 R 1 R 2,那么决策表就是一致的,如果存在 d 1 d 2而 R 1=R 2,那么决策表就是不一致的。 每次删除测试是否还保持原决策表的一致性 可以转化为检查正区域是否被改变。计算正区域的时间复杂度为O(|A|U|Log |U|,共有|A|次计算正区域,所以算法复杂度 就是O(|A|2|U|Log|U|。 |A|为属性数,|U|为对 象数。基于粗糙集的属性值约简算法研究 赵慧娟骆解民(上海水产大学信息学院上海200090摘 要:规则提取是数据挖掘的核心步骤, 在分析常用属性值约简算法思想的基础上, 给出基于不可

5、分辨矩阵的属性值约简算法描述。实 验结果表明, 这种方法是可行的。关键词:数据挖掘粗糙集属性值约简 中图分类号:G 64文献标识码:A 文章编号:1672-3791(200712(a-0141-02的结构和机能达到一定的发达程度,同时要善 于充分发挥大脑的机能。 根据大脑半球不对称原理, 左脑是理性、 知识的脑,通过分析思维和集中思维来进行智 力开发,而右脑则是感知、创造的脑,通过想 象力、直觉思维、扩散思维来进行创造力开 发。通过对发明发现过程的研究分析, 创造 学家们普遍认为, 由右脑所获得的形象、直 觉、对整体的感知等是人们进行创造性活动 的源泉, 也是创造性地解决问题的关键。科 学史上

6、大量事例可以佐证这一成果。但是, 进行创造性活动不仅需要充分开发利用右脑 的功能,也需要积极调动左脑的功能,只有两 者有效地相互配合激发,才能有效地实现创造 性活动, 得到创造性活动的产品。 2.2创造性思维的实现 从以上对创造性活动微观机制的讨论中, 可以看到要实现创造性思维,关键在于如何把 人的创造能量由基态转到激发态,以及如何诱 导人的创造性活动由低级向高级发展。 2.2.1 创造性思维的激发 创造性思维的激发可分为外部激发和内 部激发两种,外部激发又可分为直接和间接之 分。譬如讨论交流激发了创造性思维就是一 种外部直接的激发。而解除了阻碍激发创造 性思维的不良的外在条件,也是一种外部间

7、接 的激发。如果由于依靠自身的能动性激发了 创造性思维则认为是一种内部的激发。 卓越的科学家爱因斯坦在谈及自己的创 造活动时总是说,我不过是抱着孩子般的好奇 心去接触问题而已。这就说明好奇心将会激 发创造性思维,因为强烈的好奇心将在体内产 生强大的“内驱力” , 这“内驱力”激发了 创造因子,破坏了原来的创造体的稳定结构, 使得创造因子高速运动和大量碰撞,并同时又 可能打碎创造核而释放其固有能量,大大提高 了非稳态的创造体的重组效率,形成了高值的 创造能, 导致了创造性思维的实现。 许多事例向我们表明,处于逆境之中,或 处于不令人满意的状态中,或在面临着困难和 难题的时候, 往往会激发一个人的

8、创造性思 维。因为处于这种状态的个人由于感受到一 种心理上的压迫,而为了消除或摆脱,反抗或 解决就产生一种 “作用力” ,这种 “作用力” 达 到了一定的“阀值” ,就犹如前述的“内驱力” 一样,会激发创造因子,产生创造性思维。并 且,这个时候,坚强的意志对创造性思维的产 生也起着异常重要的作用。 古希腊哲学和逻辑学家苏格拉底曾指出, 可以通过提出问题来激发创造性思维。因为 每个人都或强或弱具有一种要求解决问题而 “自我实现”的欲望, 这一欲望, 就会因为提 出了问题而又为了解决问题而产生一种“原 动力” , 这一原动力正如“内驱力”那样会 激励创造能, 导致创造性思维的实现。 2.2.2 影

9、响创造性思维的诸因素 一个人的个性品质、心理素质、能力高 低和环境气氛等都对创造性思维的产生或多 或少有着重要的影响。托兰斯总结了许多研 究成果,曾列出 84项可导致产生创造性思维 的人格特征,其中最主要的前九项是:容忍 无秩序;甘愿冒险;勇于承担过于困难的工作;渴望优越;不满、发现缺陷;有情绪 感受性; 不怕被人看作为“怪人” ; 好奇心强; 喜欢孤独。同时一个人的自信心、 自尊心的大小, 思想观念的灵活性、意志的 强弱、是否勇敢、大胆和不迷信权威, 是否 善于怀疑、具有批判精神都对创造性思维的 产生有着很重要的影响。 此外一个人的想象能力、坚持能力、自 制能力、表达能力、 质疑能力、 洞察

10、能力、 交 际能力、 以及超越束缚的能力、 摆脱习惯的能 力、 普遍联系的能力、 发现问题的能力等等对 创造性思维的产生有着决定性的作用。 3结语 创造性思维是一种非常重要的思维方式, 是对人们原有的思维方式和内容的超越。要学会和掌握创造性思维方式,人们必须自觉地 培养和训练,才能逐步具备良好的思维功底和 思维品质、积累丰富的知识经验和智慧,才能 “厚积薄发” 、 获得灵感、 实现思维的飞跃、 产生新观点和新办法, 从而创造出新成果。 参考文献 1 王玉琳,王诤诤.创造性思维的系统分析J. 系统辩证学报,2002,10(3:13-16. 2 柴建芳.创造性思维系统特征初探J.山西 高等学校社会

11、科学学报,2007,19(1:13-18.3程名,周昌乐.创造性思维计算模型研究综 述J.心理科学,2007,30(1:136-138. 上海水产大学青年科研基金(6690606093142科技资讯 科技资讯SCIENCE&TECHNOLOGYINFORMATION2007NO.34SCIENCE&TECHNOLOGYINFORMATION学术论坛表1汽车驾驶安全表表 2约简C 2,C 3规则表示2.2区分矩阵法定义2区分矩阵是一个对称|U|×|U|矩 阵,矩阵的每一项 Cij 定义为:使 用 区 分 矩 阵 的 属 性 值 约 简 算 法 有 Z1ark0和 Sha

12、n 的属性值约简算法 1。基本思想:首先构造区分矩阵,该矩阵用 来分辨不同分类值下条件属性取值间的差 异。针对每一个决策属性值 V d , 将决策表中 的记录分为两部分,一个是属于 V d 的,另外一 部分是不属于 V d 的, 通过比较这两部分记录 集间条件属性取值的不同,构造出区分矩阵。 在该矩阵的基础上求出区分函数,然后应用吸 收律化简区分函数,得到析取范式,则每个主 蕴含式均为规则约简。计算区分矩阵的代价是O(|A|U|2,合并和 排序区分矩阵的时间复杂度为 O(2|U|2|Log |U|;遍历区分矩阵并生成约简的时间复杂度 是O(|A|U|2。 整个算法的时间复杂度的上限 是O(2(

13、|A|+Log|U|U|2。通过以上分析,可以发现,如果条件属性 的个数较大, 测试属性组合的代价是比较大 的, 需要一种相对高效的属性值约简算法。3基于不可分辨矩阵的属性值约简算法3.1算法的基本思想对每个条件属性进行等价类划分,如果一 个等价内的多个实例都在一个分类属性的等 价类里,那么就可以由该条件属性值确定地推 导出此分类属性。 3.2不可分辨矩阵定义 3决策系统 S的不可分辨矩阵定义如其中 ind(a i 表示条件属性 a 等价类的个 数,a i,j 表示条件属性 a i 的第 j 个等价类。规则的属性值约简,要同时考虑条件属性 值的等价类和条件属性值的等价类是否在一 个分类属性值所

14、在的等价类中,所以需要将条 件属性不可分辨矩阵 Ea i,j 按照分类属性值的 不同区别开来。 3.2算法Input:信息系统S(U,A d,其中A = ai,i=1,nOutput;化简后的规则集 R Procedure:1.R 置为空集2.计算S中所有属性的等价类和不可分 辨矩阵E3.对E中每个 e 的元素根据等价类进行 分类4.WHILE(E不为空集 5.对于E中的每个 e 6. B E G I N 7.if(e值为1 8. E =E -e 9. R =R +e10.if(U为空集break 11.else12. U =U -e 的规则号13.ENDIF 14. E N D15.对R进行

15、同分类属性值的合并 16.IF(E不为空集17.E=非同一条件属性项 18. E N D W H I L E 19. R E T U R N R计算等价类的代价与计算区分矩阵的代 价都在O(|A|U|2|内,计算不可区分矩阵的代价 为O(|A|U|2|内。 最坏情况下,每个属性的不 可区分矩阵有|U|项,分类属性等价类也是|U|项,那么对等价类按照分类属性值进行整理最 坏程度就是 O(|A|U|2|。最坏情况下每一条 规则的条件属性值都不能省,while 就要循环 属性个数|A|次,内部E的大小最多为|U|,所以 代价为O(|A|U|。 总的属性值约简的代价为O(|A|U|2+O(|A|U|2

16、+O(|A|U|,即O(|A|U|2。 明显小于区分矩阵的属性值约简算法的 O (2(|A|+LogU|U|2。 3.3实验表1是一个约简后的关于汽车驾驶安全 的信息系统,其中 U =1,2,8,条件属性 集为 C =是否会驾驶, 饮酒程度, 是否出车 祸,决策属性为 D =是否出车祸.以上面的数据集为例, 分析规则提取过 程。假设该数据集含有 8个记录,属性数为 4, 其中第一个属性是记录编号,因此可以删除。 第 4个属性是决策属性, 有效条件属性为 2个。根据不可区分矩阵启发式属性约简算 法,对约简C2,C3进行规则提取,得到的规 则有 5条,如表 2所示。可以验证,表 2中所 有的规则都

17、是正确的。可以看到,从约简中得到的规则,经过属 性值约简算法,可以用更为简洁的规则形式表 达, 且简单表达形式能完全代表约简中的规则。假如在约简集的基础上再增加一个冗余 属 r,因为冗余属性 r 的存在,可能会产生一个 简化规则与这个冗余属性 r 有关,那么就把约 简中的一部分规则归入到冗余属性r的简化规 则中,从而影响真正约简属性的规则形式和规 则数目,所以简化规则的个数和形式是要发生 改 变 的 。4结语基于粗糙集的数据挖掘方法的显著的特 点之一就是它具有显式的知识表达形式,属性 值约简是基于粗糙集理论的规则泛化步骤之 一。属性值约简一般是在属性约简的基础上 进行的。在分析常用属性值约简算法思想的 基础上,给出基于不可分辨矩阵的属性值约简 算法。该算法能够抽取出最简单的规则。经 过实验分析, 该方法是可行的。参考文献1PawlakZ.RoughsettheoryanditsapplicationstodataanalysisJ.Cyber-