基于遗传算法的数据挖掘技术的研究.doc

基于遗传算法的数据挖掘技术的研究施建强, 刘晓平(南京工程学院仿真部, 江苏 南京210013)摘 要: 文章首先对数据挖掘进行了概述, 阐明了什么是数据挖掘, 为什么要数据挖掘, 如何进行数据挖掘以及数据挖掘的主要过程。接着介绍了数据挖掘中的一个重要 算法 遗传算法。 文章对遗传算法的产生与发展以及主要理论等进行了简要的介 绍, 提出了基于遗传算法的关联规则的提取方法。文章还结合作者单位的智能型学生管理系统, 给出了用遗传算法进行关联规则挖掘的实例, 并讨论了遗传算法所面临的 问题与挑战。关键词: 数据挖掘; 遗传算法; 关联规则A bstra ct: F ir st ly, th is p ap er comm en t s da ta m in ing, exp la in s w h a t is da ta m in ing, w h y and how to do it, th e m a in p rocess of da ta m in ing and so on 1Second ly, an im po r tan t m ethod genet ic a lgo r ithm s ( GA ) in da ta m in ing is in t roduced, and th e o r ig in , developm en t, m a in th eo ry and so on a re b r ief ly d iscr ibed1O n th is ba sis, th is p ap er b r ing s fo rw a rd th e a lgo r ithm s ba sed on th e genet ic a lgo r ithm s of a ssocia t ion ru les1A ssocia ted w ith th e S tuden t A dm in ist ra t ion Sy stem , th is p ap er g ives th e a lgo r ithm s and p rog ram of m in ing a ssocia t ion ru le ba sed on genet ic a lgo r ithm s1L a st ly, th is p ap er po in t s ou t ch a llenges of da ta m in ing, summ a r izes th e w o rk of th is p ap er and th e w o rk in th e fu tu re1Key words: D a ta M in ing; Genet ic A lgo r ithm s; a ssocia t ion ru le味着在一些事实或观察数据的集合中寻找模式的决策支持过程。112 数据挖掘使用的方法现实生活中的很多技术都可以用于数据 挖掘。 模式识别、人工智能等领域的技术、方 法经过改进, 大都可以应用于数据挖掘。常用 的数据挖掘方法有决策树和遗传算法等。(1) 决策树方法 利用信息论中的信息增益寻找数据库中具有最大信息量的字段, 建立决策树的一个 结点, 再根据字段的不同取值建立树的分支; 在每个分支子集中重复建树的下层结点和分支的过程, 即可建立决策树。数据挖掘概述1111 数据挖掘定义数据挖掘是从大量的数据中抽取出潜在 的、不为人知的有用信息、模式和趋势。 数据 挖掘的目的是提高市场决策能力和检测异常 模式, 在过去的经验基础上预言未来趋势等。数据挖掘就是通过分析已经存在于数据库中 的数据来解决问题。 数据挖掘被定义成发现 数据模式的过程, 这个过程必须是自动化的 或者 (通常) 是半自动化的。 被挖掘出来的规 则应该意味着在某些方面有优势, 特别是经济方面的优势。更广义的说法是: 数据挖掘意收稿日期: 2002 10 10作者简介: 施建强 ( 1971 ) , 男, 工程师, 在职硕士, 主要研究方向为数据库系统设计和网络技术; 刘晓平 ( 1947 ) , 男, 副教授, 硕士, 主要研究方向为光纤通信和软、硬件工程开发等。电脑与信息技术2003 年第 1 期9(2) 遗传算法这是模拟生物进化过程的算法, 由三个 算子组成:式搜索、知识表示以及知识评价等。遗传算法2a1 繁殖 ( 选择)这是一个从旧种群 ( 父211 遗传算法遗 传算法 (Genet ic A lgo r ithm , GA ) 是近 几年发展起来的一种崭新的全局优化算法,它借用了生物遗传学的观点, 通过自然选择、 遗传、变异等作用机制, 实现各个体适应性的提高。用遗传算法解决问题时, 先要对待解决 问题的模型结构和参数进行编码, 一般用字 符串表示, 这个过程将问题符号化、离散化 了。一个 串 行 运 算 的 遗 传 算 法 ( Seguen t ia lGenet ic A lgo r itm , SGA ) 按以下过程进行: (1) 对待解决问题进行编码;本) 中选出生命力强的个体, 产生新种群 ( 后代) 的过程。b1 交叉 (重组)选择两个不同个体 ( 染色体) 的部分 (基因) 进行交换, 形成新个体。c1 变异 ( 突变)对某些个体的某些基因进行变异 (1 变 0、0 变 1)。113数据挖掘处理过程目前人们对整个处理过程并没有给出非 常清楚的划分, 数据挖掘的一般过程如图 1流程图所示:( 2) 随机初始化群体 X ( 0) : (x1 , x 2 ,xn ) ;(3) 对当前群体 X ( t) 中每个个体 x i 计算其 适应度 F (x i) , 适应度表示了该个体性能 的好坏;(4) 应用选择算子产生中间代 X r ( t) ;( 5) 对 X r ( t) 应用其它的算子, 产生新一 代 群体 X ( t + 1) , 这些算子的目的在于扩展有限个体的覆盖面, 体现全局搜索的思想;(6) t: = t+ 1; 如果不满足终止条件继续(3)。212基本遗传算法理论在 遗 传 算 法 中, 我 们 将 N 维 决 策 向 量图 1数据挖掘的一般过程从系统工程和方法学的角度对数据挖掘 进行研究是数据挖掘的一个研究方向。 从工程角度讲, 数据挖掘是一个需要经过多次反 复的多处理过程, 如同软件开发的宏观研究 内容是软件工程, 数据挖掘的宏观研究内容 是处理过程模型。 合理的处理过程模型能将 各个处理阶段有机地结合在一起, 指导人们更好地开发及使用数据挖掘系统。 数据挖掘是根据对数据的分析建立对数据的特性以及数据之间关系描述的模式过 程。在这个描述中, 数据是一系列事实的集合( 例如数据库中的实例) , 而模式是使用某种 语言对数据集合一个子集的描述。 过程是在 数据挖掘中包含的步骤, 如数据的预处理、模, xn T 用 n 个 记 号 X i ( I= 1,X =2, x 1 , x2 , n ) 所组成的符号串 X 来表示:X = X 1 , X 2 , X n, xn TX = x 1 , x2 ,把每一个 X i 看作一个遗传基因, 它的所有可能取值称为等位基因, 这样, X 就可看作 是由 n 个遗传基因所组成的一个染色体。 一般情况下, 染色体的长度 n 是固定的, 但对一些问题 n 也可以是变化的。根据不同的情况,这里的等位基因可以是一组整数, 也可以是 一组范围内的实数值, 或者是纯粹的一个记号。 最简单的等位基因是由 0 和 1 这两个整数组成的相应的染色体, 可表示为一个二进制符号串。这种编码所形成的排列形式 X 是 个体的基因型, 与它对应的 X 值是个体的表 现型。 通常个体的表现型和其基因型是一一 对应的, 但有时也允许基因型和表现型是多 对一的关系。 染色体 X 也称为个体 X , 对于 每一个个体 X , 要按照一定的规则确定出其 适应度。 个体的适应度与其对应的个体表现 型 X 的目标函数值相关联, X 越接近于目标 函数的最优点, 其适应度越大; 反之, 其适应 度越小。遗传算法中的决策变量 X 组成了问题 的空间解。 对问题的最优解的搜索是通过对 染色体 X 的搜索过程来进行的, 从而由所有 的染色体 X 组成了问题的搜索空间。群体。步骤五 变异运算 将变异算子作用于 群体。群体 P ( t) 经过选择、交叉、变异运算后 得到下一代群体 P ( t+ 1)。步骤六终止条件判断若 t T , 则以进化过程=中所得到的具有最大适应度的个体作为最优解输出, 终止运算。遗传算法与数据挖掘3遗传算法是数据挖掘的主要算法之一。数据挖掘的研究大致可分为 3 大领域: 数据收集和预处理、挖掘、评价和知识呈现。 数据 收集和预处理领域主要研究数据库和数据仓库。 数据仓库就是为某一挖掘主题而汇集的数据集, 以及由数据仓库延伸出来的挖掘工 具 联机分析处理 OLA P。 挖掘领域主要 是对各种算法的研究, 是目前 KDD 研究最 多的地方, 此外还有并行机、高性能计算机研遗传算法的运算过程遗传算法的运算过程如图 2 所示:213究。评价和知识呈现领域主要研究人机界面、可视化问题等。 由此可见数据挖掘技术是一门多学科的综合技术, 涉及到人工智能、数据 库等众多领域的知识。 如何从大型数据库中提取人们感兴趣的知识是数据挖掘的一个重 要方面。遗传算法作为一种有效的全局并行优化 搜索工具早已被众多应用领域所接受, 它在数据挖掘方面的应用也得到了极大的重视。图 2遗传算法的运算过程该算法的运算过程使用了上述三种遗传 算子 ( 即选择算子、交叉算子、变异算子) , 主 要运算过程如下:步骤一初始化设置进化代数计数器遗传算法应用于决策树、分类器和模糊规则的获取等方面的文献不断涌现, 因此遗传算 法是数据挖掘领域的一个重要研究课题。遗传算法由于其解决问题以混沌、随机 和非线性为典型特征, 为其它科学技术无法解决或难以解决的复杂问题提供了新的计算 模型。对于大量数据的嘈杂无序的特征, 遗传 算法是有效解决此类问题的方法之一。遗传算法模拟自然进化的通用全局搜索 算 法, 避 免 了 搜 索 过 程 中 的 局 部 最 优 解,用在规则发现方面有希望发现真正有用的规 则。t; 设置最大进化代数 T ; 随机生成M作为初始群体 P (0)。个个体步 骤二个体评价各个个体的适应度。计算群体 P ( t) 中步骤三群体。 步骤四选择运算将选择算子作用于交叉运算将交叉算子作用于11电脑与信息技术2003 年第 1 期反映出关联规则的重要性。挖掘关联规则挖掘关联规则是指在数据库中挖掘出具 有这种形式的规则: 由于某些事件的发生而 引起另外一些事件的发生。 它在决策支持系 统、专家系统和智能信息系统等各个方面起 着重要的作用。随着数据库应用的普及, 数据 挖掘的应用越来越广, 在近几年内倍受人们 的关注。411关联规则的形式及定义4关联规则的 A pr ior i 算法现 有 的 关 联 规 则 的 挖 掘 算 法 主 要 是R 1A g raw a l 等人提出的 A p r io r i 算法, 该算法 将关联规则的发现分为两步。 第一步是识别 所有的频繁项目集 (f requen t item s, 也称作最 大项目集 la rge item s) , 即支持度不低于用户 支持度的项目集。 第二步是从频繁集中构造 其信任度不低于用户最低信任的规则, 其中 的核心问题是发现最大项目集。 发现最大项 目集的过程其实就是全局的搜索过程, 遗传 算法是一种全局优化算法, 因此它避免了搜 索过程中的局部最优。 将遗传算法用在规则 的发现和提取方面能够发现真正有用的规 则。412设 I= i1 , i2 , Im 是 m 个不同项目的集合, 即项目集。D 为事务数据库, 其中每个事务 T 是一个项目子集, 我们说事务 T 包含 项目集 X。如果 XA T , 关联规则是形如 X Y的逻辑蕴含式, 其中, X T , Y 0 则保留该 规则进入下一代, 否则删除, 并计算保留下来的个体数M ;步骤三如果M N , 则随机生成 (N -M ) 个个体, 否则跳过步骤三;步骤四初始化交配池M 和后代 OM = O = 步骤五复制fo r = 1 to v do将当前种群中的所有个体都复制到交配池,M = M #A13电脑与信息技术2003 年第 1 期步骤六交叉fo r = 1 to v2 do随机 地 从 交 配 池 M 中 选 择 个 体 A 和A ”, 按照交叉概率 P c 进行交叉, M = M - A , A ”O = O # A , A ”按照概率 P c 交 叉的后代步骤七变异在当前种群中按照变异概率选择M 个个体进行变异操作;步骤八 终止条件判定 同终止代数进 行对比, 如果达到终止条件则终止, 并输出结 果; 否则转步骤二;步骤九进行规则提取。 根据以上算法, 我们在学员资料数据库中发现部分关联规则如下:值长的培训成绩在 80 分到 89 分之间的 可信度为 89% , 支持度为 6% , 也就是说: 大 部分值长的学习成绩为良好。同样, 比较可信 度和支持度, 可知大部分司机的成绩比司机助手的成绩好; 大部分司炉的成绩比司炉助 手的成绩好; 大部分电气主值的成绩比电气 助手的成绩好; 学历较高的比学历较低的成 绩好。通过同样的方法, 我们还可以对不同内容的学生资料数据库进行关联规则的发现, 希望发现有用的知识, 并把它们应用到学员 的培养和教育上去。爆炸, 属性值之间的关系变得更加复杂, 比如表现为层次结构。 这些因素导致搜索知识代 价极高。 目前的研究发展到利用并行处理或抽 样 (Sam p ling) 的方法处理大规模数据, 从 而获得较高的计算效率。 根据问题的定义或相关知识可以选出需要的属性, 从而减低维 数。而处理属性之间的复杂关系, 往往还需要 一些背景知识, 比如不同层次的概念所构成的概念树。( 2) 数据丢失问题 这个问题在商业领 域表现得尤为突出。可以想像, 如果某数据库 不是为知识发现而定做的, 它就可能会存在 一些重要数据或属性丢失的问题。 目前主要利用统计, 甚至不确定性的理论与方法来确 定隐含变量及依赖关系。( 3) 多种形式的输入数据 目前数据挖 掘工具能处理的数据形式有限, 一般可以处 理数值型的结构化数据, 但大多不能对文本、图形、数学公式、图像或 WWW 资料等这些 半结构、无结构的数据形式进行挖掘操作。另外的挑战是数据本身存在缺损或噪声, 特别 是在商业数据库中。( 4) 网络与分布式环境的 KDD 问题 随着 In ternet 的不断发展, 网络资源的日益丰富, 技术人员各自独立的处理分离数据库的工作方式应是可协作的, 因此考虑到适应 分布式与网络环境的工具、技术及系统也是必然的。 当前人工智能中关于多 A gen t 系统 的研究将为 D a ta M in ing 与 KDD 研究提供理论基础与有效的工具。数据挖掘面临的问题与挑战虽然数据挖掘技术已经在各方面都得到 了广泛的应用, 但是, 数据挖掘技术的研究还 不是很成熟, 其应用还有很大的局限性。正是 由于这些局限性, 促使数据挖掘的研究进一 步发展, 下面列出数据挖掘在应用中所面临 的一些挑战:(1) 挖掘的对象 更大型的数据库、更高 的维数和属性之间更复杂的关系。 数据挖掘 要处理的数据量通常是十分巨大的, 成百上 千的表, 上百万条记录, 数据库容量达到若干 GB (109) 字节, 甚至 TB ( 1012) 字节。 更多的 属性意味着高维的探索空间, 从而导致组合6结束语本文介绍了数据挖掘的概念及 发 展 概 况, 并对数据挖掘中使用的技术进行了总结, 提出了基于遗传算法的关联规则的提取方 法, 介绍了数据挖掘中的一个重要算法 遗传算法。 文中对遗传算法的产生与发展以 及其主要理论都进行了简要的介绍。 本文仅 对遗传算法在关联规则提取方面的应用进行7了初步的研究, 尚有(下转第 36 页)性后, 通过通用数据接口 GD I 等待数据库服务器的回应。 数据库服务器回应并认可通信 后, W eb 服务器与数据库服务器之间通过数据管道进行数据交换。对数据通用接口, 我们采用 ODBC 接口技术实现。W eb 服务器与数结束语目前, 中国互联网的高速发展, 其用户已 超过 4 500 万, 居全球第三。如何利用当今最 先进的网络技术, 特别是 In ternet 技术构建 高性能的商业服务系统, 是一个非常有现实 意义的课题。本文探讨了 B S 模式在构建网 上电力客户服务系统中的应用。B S 模式结 构作为新兴的网络技术必将在网上的商务运 作中起到不可替代的重要作用。参考文献:3据库服务器之间以标准的 SQ L信规范。语言作为通安全认证服务器与 W eb 服务器和数据库服务器通过 SC I 连接, SC I 采用 J ava 专用 程序实现。 安全认证服务器中主要有三个功能模块: 用户请求模块、加密生成模块和认证 确认模块, 这三个模块相互配合, 共同完成系 统的数据访问安全工作。 是否要进行安全认证, 主要由系统管理员根据规定和用户类型 决定。数据库服务器上的通用数据接口接收来徐宝民, 蒋 理, 等 1 基于 B row serServer 模式的新型 企 业 M IS 的 研 究 与 设 计 1 计 算 机 工 程 与 应 用,1999 ( 6) :柳瑞禹, 等 1 基于 A SP 技术的W eb 应用 1 电脑与信 息技术, 2000 ( 2) :夏骄雄, 陆菊康, 施振夏