基于粗糙集和遗传算法的数据挖掘方法

收稿日期:2008-03-21作者简介:胡启韬,男,江西南昌人,硕士。

研究方向:数据库与数据挖掘。

袁志平,男,安徽青阳人,高级工程师。

研究方向:数据库应用。

周忠海,男,山东青岛人,高级工程师。

研究方向:信息处理。

基于粗糙集和遗传算法的数据挖掘方法胡启韬袁志平周忠海(江南计算技术研究所 江苏无锡 214083)摘要:运用粗糙集和遗传算法的理论,为大型的数据挖掘提供了一种新的方法。

首先通过粗糙集理论对数据进行预处理,然后对属性简约,最后通过遗传算法进行规则提取,寻找最优解。

关键词:粗糙集遗传算法数据挖掘知识发现中图分类号:TP36文献标识码:A 文章编号:123(2008增)-017-03数据挖掘[1]又称知识发现,是从大量的、不完全的、有躁声的、模糊的实际数据中,提取隐含在其中的、人们事先不知道的、但又很有用的知识和信息的过程。

它的一般步骤如下:提出问题 数据准备 数据整理 建立模型 评价和解释。

它是数据库研究、开发和应用最活跃的一个分支,是多学科的交叉领域,涉及数据库技术、人工智能、机器学习、神经网络、数学、统计学、模式识别、知识库系统、知识获取、信息提取、高性能计算、并行计算、数据可视化等多方面的知识。

1 粗糙集与遗传算法的基本概念粗糙集(R ough Set ,R S)[2]作为一种全新的数学概念,为处理具有不完整、不一致及不确定性特征的信息提供了新的有效工具,它的主要特点之一是无须提供问题所需处理的数据集合之外的任何先验信息。

相对于许多其他处理不确定知识的方法来说更具客观性,并且和其他分析方法有机结合,进一步增强对不确定问题的处理能力。

1.1 定义1信息系统S 可表示为S =(U,A,V,f ),其中U 是对象的非空有限集合,称为论域;A 是属性的非空有限集合;V = a A Va,Va 是属性A 的值域,f:U A !V 是一个信息函数,他为每个对象的每个属性赋予一个信息值。

如果属性集A 可以分为条件属性集C 和决策属性集D,即C D =A ,C ∀D = ,则该信息系统称为决策系统或决策表,其中D 一般只含有一个属性。

1.2 定义2在知识表达系统S 中,对于一属性集P#A,对象x,y #U,二元等价关系IND (P )={(x,y )#U U |所有的a #P,f (x,a)=f (y,a)}称为S 的不可分辨关系。

不可分辨关系是一个等价关系,通过一个不可分辨关系,可以得到一个决策系统的划分。

1.3 定义3给定信息系统S =(U,A ),B #A ,对B中的属性a,如果I ND (B )∃IND (B -{a}),则说属性a 是必要的(Indisp ensab le),否则称a 是不必要的(D isp ensable )。

遗传算法(Genetic A l gor it hm,GA )[3]起源于对生物系统进行的计算机模拟研究,是模拟生物在环境中的遗传和进化过程而形成的一种自适应优化概率搜索算法。

它的流程主要模仿的是生物遗传进化过程中的选择、交叉和变异操作,从而完成对问题最优解的自适应搜索过程。

流程主要包括染色体编码、产生初始群体、计算适应度、进化操作等几大部分。

遗传算法的搜索过程是从一群初始节点开始搜索,而不是从单一的初始点开始搜索,这种机制意味着搜索过程可以有效地跳出局部极值点。

既可以完成极值点领域内解的求精,也可以在整个问题空间实施探索,得到问题全局最优解的概率大大提高。

2 粗糙集与遗传算法在数据挖掘中的应用粗糙集算法与遗传算法结合,能有效地提高挖掘效果,具有实际应用的可行性。

其基本思想是:首先通过粗糙集对%17%增刊2008年10月 江西蓝天学院学报J OURNAL OF JI A NGX I BLUE SKY UN I V ERSI TYSupple m entOctober .2008信息表中的数据缺损进行处理;然后对于信息表中的数据,根据已定义的可辩识距阵,通过属性简约算法进行属性简约和知识发现;最后对知识发现的规则通过遗传算法进行优化,找出最主要的规则。

主要包括以下几个方面:2.1 数据预处理数据预处理用于对原始数据的采样、收集、整理,对于不同途径获取来的数据不一定能够得到有效的信息,所以数据的预处理是非常必要的。

包括连续属性的离散化和不完备数据的填补,由于粗糙集只能处理离散的数据,所以还必须对连续的数据离散化,而属性离散化的关键在于选取合适的断点对条件属性进行划分[4],如可采用基于属性重要性的离散化算法。

由于数据采集的不完整性,使数据库中很大一部分数据都存在缺失,因此对输入的数据必须进行必要的处理如采用均值法、频率统计法等对数据进行补齐。

2.2 属性简约粗糙集处理决策表时,数据约简是核心内容,一般是约去过剩的条件属性,用最少的属性区分不同的决策,提供同样多的信息,使决策表的决策属性和条件属性的依赖关系不发生变化。

简约后的属性集称为属性的约简集,约简集通常不唯一,找到一个信息表中的约简集不是在一个多项式时间里能够解决的问题,求最小约简集(含属性个数最少的约简集)同样是一个困难的问题,实际上它是一个N P-hard问题,因此根据已定义的可辩识距阵,有如下的属性简约算法:2.2.1 计算属性表的可辩识距阵。

2.2.2 对于可辩识距阵中的所有取值为非空集合的元素Cij建立相应的析取逻辑表达式。

2.2.3 将所有析取逻辑表达式进行合取运算,得到一个合取范式。

2.2.4 将合取范式转换为析取范式形式。

2.2.5 输出属性约简结果,其中析取范式中的每个合取项对应一个属性约简的结果,每个合取项中所包含的属性组成的约简后的条件属性集合。

2.3 决策规则提取经过第二步属性简约后,属性个数减少了,但是得出的规则数量依然可能过多,不利于得到用户最想要、最重要的规则,因此,我们会更希望关心具有较多共同特性的规则,必须把简约后生成的规则集里那些具有大量共同特征的规则再次提取出来,面对这种优化问题,遗传算法是个强有力的工具。

其步骤是编码产生原始种群,计算个体适应度,选择个体,交叉,变异操作,然后一代一代进化最后找出最优解。

2.3.1 编码,是进行遗传算法的重要步骤,编码方案的选取很大程度上决定于问题的性质和要求,同时也决定了对随后的遗传算子的设计。

如可以将数据离散化后的属性值定义在2的n次方之间[5],采用二进制编码方法对每个数字编码,像属性值3用编码表示就是0011。

2.3.2 产生初始种群。

随机选取一些个体作为初始种群。

2.3.3 确定评价函数。

数据挖掘的目的是挖掘出具有最多相同特征的规则,因此,评价函数的选取时应当把能够匹配简约表中最多的属性的规则评价为最优规则。

2.3.4 遗传操作。

交叉操作是将规则编码的某几位互相置换,变异操作是将规则编码的某些二进制位按位取反。

这样通过规则集中任意的两两组合会形成新的规则集。

然后经过每个规则的评价函数确定当前的最优规则,这样经历数代遗传之后就可得到相对最优的规则。

3 公司录取情况数据挖掘应用实例下面用一个实例来说明使用的数据挖掘方法。

某公司每年都会收到大量的求职信息表,并从中雇用一定数量的员工,对于员工的雇用,公司以往都是通过面试及给领导的感觉来雇用的,因此,公司希望能够从以前的录用中找出一个大体的评判标准以便于以后录用时作为参考,由于以往几年累计求职的员工太多,情况比较复杂,因此,公司希望这个标准能够简单明了。

通过本文提出的方法,可以很好的解决该公司的需求,以下以该公司求职人员的原始求职表中的一部分作为演示,&?∋代表求职表中该属性没有写明情况,如图1所示:学历(d)经验(e)法语(f)仪表(a)结论(c)X1M BA一般会优秀雇用X2M BA少?一般不雇用X3无学历无经验会差不雇用X4M SC多会?雇用X5M SC?会一般不雇用X6?多会优秀雇用X7M BA多不会良好雇用X8M CE少不会优秀不雇用表1原始求职表经过数据预处理后,对缺失数据进行了填补及属性离散化后得到了表2:学历(d)经验(e)法语(f)仪表(a)结论(c)X101101X202120X333130X420121X521120X620101X720011X812000表2信息表按属性简约的算法,通过决策表的可辩识距阵,我们可以得到算法第3步后的合取范式为:%18%胡启韬、袁志平、周忠海:基于粗糙集和遗传算法的数据挖掘方法(2008)F (d,e ,f,a)=(e (a))(d (e (a ))(d (e))(e (f (a ))(d (e (f ))(d (e (a ))(d (e (a))(d (e (a ))(d (a ))(e))(e (a ))(d (e (f (a ))(d (e (f ))(d (e (f (a ))(d (e (f))(d (e (a )其中每一个析取项对应于可辩识距阵中的一个元素,d,e ,f,a 分别对应属性学历、经验、法语、仪表,按算法第4步简化后可以得到F (d ,e ,f ,a )=(e )a)((e )d )。

由此可见,在原始决策表给出的这部分信息中与决策有关的是d,e ,a 。

通过粗糙集的属性约简,可以得到以往公司录用时真正看重的一些属性,通过这些属性,再用遗传算法找出其中最主要的规则。

例如约简表中某一行在学历、经验、仪表上的值为201,则编码就是10,00,01。

随机选取8个个体作为初始种群,评价函数以能够匹配约简表中最多行属性的规则成为当代的最优规则。

算法定义为一个8元组:SGA =(C,E,P 0,M , , ,!,T )C 表示对个体采用二进制编码;E 表示个体适应度评价函数f (x );P 0表示初始种群随机选取的8个规则; 表示采用轮盘赌按比例选择算子; 表示中间位单点交叉算子;!表示基本位变异算子;T 表示执行20代上述遗传算法后停止。

最后得到最佳个体00,01,01,即学历M BA,经验水平一般,仪表良好的评判标准,凡在此标准附近或高于此标准的,可以考虑录用。

4 结语在数据挖掘中应用粗糙集和遗传算法,粗糙集可以解决数据不精确、不完整的问题,并进行属性简约,遗传算法可以从大量规则中提取出最优的规则,提高了分析系统的效率。

将粗糙集和遗传算法在数据挖掘中相结合,给出实例说明该方法的可行性。

在今后的研究中还将继续结合其他的方法进行研究,提高对知识的发现能力。

参考文献:[1]Dav i d H e i kkiM ann il a ,P adhra ic Smy t h .数据挖掘原理[M ].北京:机械工业出版社,2003.[2]Paw lak Z .R ough Set[J].Internationa l Journa l of Infor m a tion and Computer Sc ience ,1982,11(5):314-356.[3]高隽.智能信息处理方法导论[M ].北京:机械工业出版社,2004.[4]李红梅,周桂红,王克俭.基于粗糙集和遗传算法的知识发现方法[J].计算机应用,2007,8(1):76-78.[5]胡域,张亦军,杨冬梅.粗糙集结合遗传算法在数据挖掘中的应用[J].计算机应用,2006,6(26):98-99.(责任编辑:章建华)D at a Extraction Based on Rough Set and Genetic A lgorit hmH U Q i-T aoYUAN Zhi-p i ngZ H OU Zhong -hai(J iangnan Institute of Computi ng T echnology,W ux i214083,Ch i na)A bstrac t :A new approach for data m i n i ng by usi ng rough set and geneti c a l gor it hm is i ntroduced i n this article .F irst of a l,l w e pretreats our data w ith rough set ,and then reduce attr i butes ,fi nall y w e ex tract t he best ru l e t hrough g enetic algorith m.K ey W ords :R ough Se t ;G ene tic A l gor it hm;D ata Ex tration ;K no w l edg e D iscovery%19%江西蓝天学院学报(2008)。