基于粗糙集和遗传算法的数据挖掘方法--浙江大学数学系方建勇-13621847370

收稿日期 : 2008 - 03 - 21 作者简介 :胡启韬 ,男 ,江西南昌人 ,硕士。研究方向 :数据库与数据挖掘。 袁志平 ,男 ,安徽青阳人 ,高级工程师。研究方向 :数据库应用。 周忠海 ,男 ,山东青岛人 ,高级工程师。研究方向 :信息处理。 基于粗糙集和遗传算法的数据挖掘方法 胡启韬 袁志平 周忠海 (江南计算技术研究所 　江苏 无锡 　214083) 　　摘 要 :运用粗糙集和遗传算法的理论 ,为大型的数据挖掘提供了一种新的方法。首先通过粗糙集理论对数据进行 预处理 ,然后对属性简约 ,最后通过遗传算法进行规则提取 ,寻找最优解。 关键词 :粗糙集 遗传算法 数据挖掘 知识发现 中图分类号 : TP36 文献标识码 : A 文章编号 : 123 (2008增 ) - 017 - 03 　　数据挖掘 [ 1 ]又称知识发现 ,是从大量的、不完全的、有 躁声的、模糊的实际数据中 ,提取隐含在其中的、人们事先 不知道的、但又很有用的知识和信息的过程。它的一般步 骤如下 :提出问题 ϖ数据准备 ϖ数据整理 ϖ建立模型 ϖ评 价和解释。它是数据库研究、开发和应用最活跃的一个分 支 ,是多学科的交叉领域 ,涉及数据库技术、人工智能、机器 学习、神经网络、数学、统计学、模式识别、知识库系统、知识 获取、信息提取、高性能计算、并行计算、数据可视化等多方 面的知识。 1　粗糙集与遗传算法的基本概念 粗糙集 (Rough Set, RS) [ 2 ]作为一种全新的数学概念 , 为处理具有不完整、不一致及不确定性特征的信息提供了 新的有效工具 ,它的主要特点之一是无须提供问题所需处 理的数据集合之外的任何先验信息。相对于许多其他处理 不确定知识的方法来说更具客观性 ,并且和其他分析方法 有机结合 ,进一步增强对不确定问题的处理能力。 1. 1　定义 1 信息系统 S可表示为 S = (U, A, V, f) ,其 中 U是对象的非空有限集合 ,称为论域 ; A是属性的非空有 限集合 ; V =∪ a:AV a, V a是属性 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,如果 IND (B ) ≠ IND (B - { a} ) ,则说属性 a是必 要的 ( Ind ispensable) ,否则称 a是不必要的 (D ispensable)。 遗传算法 ( Genetic A lgorithm , GA ) [3 ] 起源于对生物系 统进行的计算机模拟研究 , 是模拟生物在环境中的遗传和 进化过程而形成的一种自适应优化概率搜索算法。它的流 程主要模仿的是生物遗传进化过程中的选择、交叉和变异 操作 ,从而完成对问题最优解的自适应搜索过程。流程主要 包括染色体编码、产生初始群体、计算适应度、进化操作等 几大部分。 遗传算法的搜索过程是从一群初始节点开始搜索 , 而 不是从单一的初始点开始搜索 , 这种机制意味着搜索过程 可以有效地跳出局部极值点。既可以完成极值点领域内解 的求精 ,也可以在整个问题空间实施探索 ,得到问题全局最 优解的概率大大提高。 2　粗糙集与遗传算法在数据挖掘中的应用 粗糙集算法与遗传算法结合 ,能有效地提高挖掘效果 , 具有实际应用的可行性。其基本思想是 :首先通过粗糙集对 ·71· 增刊 2008年 10月 　　　　 江 西 蓝 天 学 院 学 报 JOURNAL OF J IANGX IBLUE SKY UN IVERSITY 　　　　 Supp lement October. 2008 信息表中的数据缺损进行处理 ;然后对于信息表中的数据 , 根据已定义的可辩识距阵 , 通过属性简约算法进行属性简 约和知识发现 ;最后对知识发现的规则通过遗传算法进行 优化 ,找出最主要的规则。主要包括以下几个方面 : 2. 1　数据预处理 数据预处理用于对原始数据的采样、收集、整理 , 对于 不同途径获取来的数据不一定能够得到有效的信息 , 所以 数据的预处理是非常必要的。包括连续属性的离散化和不 完备数据的填补 ,由于粗糙集只能处理离散的数据 ,所以还 必须对连续的数据离散化 , 而属性离散化的关键在于选取 合适的断点对条件属性进行划分 [4 ] , 如可采用基于属性重 要性的离散化算法。由于数据采集的不完整性 ,使数据库中 很大一部分数据都存在缺失 , 因此对输入的数据必须进行 必要的处理如采用均值法、频率统计法等对数据进行补齐。 2. 2　属性简约 粗糙集处理决策表时 ,数据约简是核心内容 ,一般是约 去过剩的条件属性 ,用最少的属性区分不同的决策 ,提供同 样多的信息 ,使决策表的决策属性和条件属性的依赖关系 不发生变化。简约后的属性集称为属性的约简集 ,约简集通 常不唯一 ,找到一个信息表中的约简集不是在一个多项式 时间里能够解决的问题 ,求最小约简集 (含属性个数最少的 约简集 ) 同样是一个困难的问题 , 实际上它是一个 N P - ha rd问题 ,因此根据已定义的可辩识距阵 ,有如下的属性简 约算法 : 2. 2. 1　计算属性表的可辩识距阵。 2. 2. 2　对于可辩识距阵中的所有取值为非空集合的 元素 C ij建立相应的析取逻辑表达式。 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) X1 MBA 一般 会 优秀 雇用 X2 MBA 少 ? 一般 不雇用 X3 无学历 无经验 会 差 不雇用 X4 MSC 多 会 ? 雇用 X5 MSC ? 会 一般 不雇用 X6 ? 多 会 优秀 雇用 X7 MBA 多 不会 良好 雇用 X8 MCE 少 不会 优秀 不雇用 表 1 原始求职表 　　经过数据预处理后 ,对缺失数据进行了填补及属 性离散化后得到了表 2: 学历 ( d) 经验 ( e) 法语 ( f) 仪表 ( a) 结论 ( c) X1 0 1 1 0 1 X2 0 2 1 2 0 X3 3 3 1 3 0 X4 2 0 1 2 1 X5 2 1 1 2 0 X6 2 0 1 0 1 X7 2 0 0 1 1 X8 1 2 0 0 0 表 2 信息表 按属性简约的算法 ,通过决策表的可辩识距阵 ,我们可 以得到算法第 3步后的合取范式为 : ·81· 胡启韬、袁志平、周忠海 :基于粗糙集和遗传算法的数据挖掘方法 (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, P0 , M , Ф, Г,Ψ, T) C表示对个体采用二进制编码 ; E表示个体适应度评价 函数 f ( x) ; P0 表示初始种群随机选取的 8个规则 ; Ф表示采 用轮盘赌按比例选择算子 ; Г表示中间位单点交叉算子 ;Ψ 表示基本位变异算子 ; T表示执行 20代上述遗传算法后停 止。 最后得到最佳个体 00, 01, 01,即学历 MBA,经验水平一 般 ,仪表良好的评判标准 , 凡在此标准附近或高于此标准 的 ,可以考虑录用。 4　结语 在数据挖掘中应用粗糙集和遗传算法 , 粗糙集可以解 决数据不精确、不完整的问题 ,并进行属性简约 , 遗传算法 可以从大量规则中提取出最优的规则 , 提高了分析系统的 效率。将粗糙集和遗传算法在数据挖掘中相结合 ,给出实例 说明该方法的可行性。在今后的研究中还将继续结合其他 的方法进行研究 ,提高对知识的发现能力。 参考文献 : [ 1 ] David HeikkiMannila, Padhraic Smyth. 数据挖掘原理 [M ]. 北京 :机械工业出版社 , 2003. [ 2 ] Pawlak Z. Rough Set[ J ]. International Journal of Information and Computer Science, 1982, 11 (5) : 314 - 356. [ 3 ]高隽. 智能信息处理方法导论 [M ]. 北京 :机械工业出版社 , 2004. [ 4 ]李红梅 ,周桂红 ,王克俭. 基于粗糙集和遗传算法的知识发现方法 [ J ]. 计算机应用 , 2007, 8 (1) : 76 - 78. [ 5 ]胡域 ,张亦军 ,杨冬梅. 粗糙集结合遗传算法在数据挖掘中的应用 [ J ]. 计算机应用 , 2006, 6 (26) : 98 - 99. (责任编辑 :章建华 ) Da ta Extraction Ba sed on Rough Set and Genetic A lgor ithm HU Q i - Tao　 YUAN Zhi - ping　 ZHOU Zhong - ha i (J iangnan Institu te of Com puting Technology, W uxi 214083, China) Abstract: A new app roach for data m ining by using rough set and genetic algorithm is introduced in this article. First of all, we p retreats our data with rough set, and then reduce attributes, finally we extract the best rule through genetic algorithm. KeyWords: Rough Set; Genetic A lgorithm; Data Extration; Knowledge D iscovery ·91· 江西蓝天学院学报 (2008)