（管理科学与工程专业论文）基于改进遗传算法的Web关联规则挖掘的研究.pdf

原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成 果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得由鏊直太堂及其他教育机构的学位或证二传而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：丝鲣指导教师签名： 日 期：磁：么，改日 期： 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期间取得的研究成果( 含计算机软件、程序) 属于 内蒙古大学计算机学院。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内 蒙古大学计算机学院就读期间导师的同意：若用于发表论文，版权单位必须署名为内蒙古大 学计算机学院方可投稿或公开发表。 学位论文作者签名：必指导教师签名： 日期：塑丝左。壁日期： y 内蒙古大学硕一f ：学位论文 基于改进遗传算法的w e b 关联规则挖掘的研究 摘要 近几十年来，万维网的迅速发展使其成为世界上规模最大的公共数据源。 面对信息时代海量数据的出现，如何有效地利用大量的原始数据分析现状以预 测未来，己经成为人类面临的一大挑战。由此，w e b 数据挖掘技术应运而生并 得以迅猛发展。目前，w e b 数据挖掘无论是在理论研究方面还是在应用研究方 面都已经成为了十分热门的课题。很多学者开始寻求用遗传算法来求解w e b 数 据挖掘问题。但遗传算法在求解w e b 数据挖掘问题时还存在一些缺陷。 本文首先介绍了典型遗传算法的算法思想和步骤，在分析遗传算法性能瓶 颈的基础上提出一种基于改进遗传算法的w e b 关联规则挖掘算法，从编码方法、 适应度函数的构造、交叉算子和变异算子的设计等方面进行了详细的讨论和分 析。其次，在这一过程中详细讨论了遗传算法早熟问题产生的原因，并采用模 拟退火算法的b o l t z m a n 生存机制和建立自适应交叉概率等技术来有效的解决典 型遗传算法的早熟问题，同时使用m a t l a b 环境编写程序对该模型进行求解和模 拟遗传算法搜索过程。实验研究结果显示，将改进遗传算法应用在w e b 的关联 规则挖掘上，无论是在求得关联规则数目、准确率、还是在算法消耗时间上都 有着明显的优势。 关键词：遗传算法，w e b 数据挖掘，关联规则，模拟退火算法 基于改进遗传算法的w e b 关联规则挖掘的研究 w e ba s s o c i a t i o nr u l e sm i n i n gb a s e do ni m p r o v e d g e n e t i ca l g o r i t h m a b s t r a c t i nr e c e n td e c a d e s ，w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t ，w o r l dw i d ew e bh a s b e c o m et h ew o r l d sl a r g e s tp u b l i cd a t as o u r c e s i nt h ef a c eo fn u m e r o u sh u g eo r i g i n a l d a t a ，h o wt h ei n v e s t o r su t i l i z et h i sd a t at oa n a l y s i st h ec u r r e n ts i t u a t i o na n dp r e d i c t t h ef u t u r ee f f e c t i v e l yh a v ea l r e a d yb e c o m eg r e a tc h a l l e n g e sw h i c ht h em a n k i n dh a s f a c e d t h e r e f o r et h ew e bd a t am i n i n gt e c h n o l o g ya r o s ea tt h eh i s t o r i cm o m e n ta n d c a nb ed e v e l o p e dr a p i d l y r e c e n t l y , w e bd a t am i n i n gh a sb e e no n eo fh o tt o p i cb o t h i nt h e o r e t i c a lr e s e a r c ha n da p p l i e dr e s e a r c h m a n ys c h o l a r sb e g a nt ou s eg e n e t i c a l g o r i t h m st os o l v et h ei s s u eo fw e b d a t am i n i n g h o w e v e r , i th a ss o m e p r o b l e m st h a t u s i n gg e n e t i ca l g o r i t h m st os o l v et h et o p i co fw e b d a t am i n i n g f i r s t l y , t h i sp a p e ri n t r o d u c e st h et y p i c a lg e n e t i ca l g o r i t h mi d e aa n d t h es t e p s i t p r o p o s e sa ni m p r o v e dg e n e t i ca l g o r i t h mb a s e do na n a l y z i n gt h eg e n e t i ca l g o r i t h m p e r f o r m a n c eb o t t l e n e c k s aw e bm i n i n gm e t h o do fa s s o c i a t i o nr o l e sb a s e do nt h i s i m p r o v e dg e n e t i ca l g o r i t h mw a sp r o p o s e d i td i s c u s s e sa n da n a l y s e s t h eg e n e t i c a l g o r i t h m s i nd e t a i lf r o mc o d i n gm e t h o d ，f i t n e s sf u n c t i o n ，c r o s s o v e ro p e r a t o r s ， s e l e c t i o no p e r a t o r s ，m u t a t i o no p e r a t o r sa n do t h e ra s p e c t s s e c o n d l y , i nt h i sp r o c e s s ，i t d i s c u s s e st h ep r o b l e m so fe a r l y m a t u r i n gt y p i c a lg e n e t i ca l g o r i t h mi n d e t a i l b o l t z m a ns u r v i v a lm e c h a n i s mb a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h ma n dt h e e s t a b l i s h m e n to fs e l f - a d a p t i v ec r o s s o v e rp r o b a b i l i t yc a nb eu s e dt oe f f e c t i v e l ys o l v e t h i ss i t u a t i o n m a t l a be n v i r o n m e n ti su s e dt oc o m p i l ep r o g r a m m i n gf o rs o l v i n gt h e m o d e la n ds i m u l a t i n gg e n e t i ca l g o r i t h ms e a r c hp r o c e s s r e s e a r c hr e s u l t ss h o wt h a t t h ew e bm i n i n gm e t h o d so fa s s o c i a t i o nr u l e sb a s e do ni m p r o v e dg e n e t i ca l g o r i t h m i i i i i 基于改进遗传算法的w e b 关联规则挖掘的研究 t 内蒙古大学硕十学位论文 目录 摘要i a b s t r a c t i i f ；l录、， 图表目录v i i 第一章绪论1 1 1w e a 挖掘的产牛与发展现状1 1 2 遗传算法的产生与发展现状2 1 3 遗传算法与w e b 挖掘4 1 4 本文的研究内容和结构4 、 1 5 本文的研究方法5 1 6 可能的创新点5 第二章基于遗传算法的w e b 挖掘技术7 2 1 遗传算法7 2 1 1 遗传算法的描述7 2 1 2 遗传算法的理论基础：8 2 1 3 遗传算法的基本操作1 1 2 1 4 遗传算法的运算过程1 2 2 1 5 遗传算法的关键参数1 3 2 1 6 遗传算法的特点1 4 2 1 7 遗传算法的“早熟 问题1 5 2 2w e b 挖掘技术16 2 2 1 w 曲挖掘的定义1 6 2 2 2w e b 数据挖掘的分类1 7 2 2 3w e b 数据挖掘的步骤1 9 2 2 4w e b 数据挖掘中的关键技术2 0 2 3 小结2 2 第三章基于w e b 的关联规则挖掘2 3 v 基于改进遗传算法的w e b 关联规则挖掘的研究 3 1 关联规则2 3 3 2 关联规则挖掘算法及其改进2 4 3 3 适用于w e b 关联规则的增量挖掘算法2 7 3 4 小结3 2 第四章基于改进遗传算法的w e b 关联规则挖掘的设计与实现3 3 4 1 改进遗传算法的设计与实现3 3 4 1 1 改进遗传算法的编码方法3 4 4 1 2 改进遗传算法适应度函数的构造3 6 4 1 3 遗传算子的改进3 8 4 2 基于改进遗传算法的w e b 关联规则挖掘的模型求解与实现4 l 4 3 实验模拟4 5 4 3 1 实验数据4 5 4 3 2 实验结果与分析4 6 4 4d 、结4 8 第五章总结与展望4 9 5 1 论文总结4 9 5 2 进一步展望4 9 参考文献5 0 致谢：5 2 v i 内蒙占大学硕斗：学位论文 图表目录 图2 1 基本遗传算法的流程图1 3 图2 2w e b 数据挖掘的分类图18 图2 3w e b 数据挖掘的步骤19 图3 1 网站连接关系图2 8 图3 2 数据库更新后的网站连接关系图2 8 图4 1 遗传关联规则挖掘体系图3 3 图4 2 改进遗传算法的挖掘流程图3 4 图4 3 基于改进遗传算法的w e b 关联规则挖掘流程图4 2 图4 4 模拟退火过程的流程图4 4 图4 5 改进遗传算法和原始遗传算法产生的关联规则的数目比较4 6 图4 6 改进遗传算法和原始遗传算法产生的关联规则准确率的比较4 6 图4 7 同一数据库下改进遗传算法和原始遗传算法执行时间的比较4 7 表4 1 算法对比表4 7 表4 2 遗传算法和改进遗传算法的比较4 8 v i i 基于改进遗传算法的w e b 关联规则挖掘的研究 v i 内蒙古大学硕i ：学位论文 1 1w e b 挖掘的产生与发展现状 第一章绪论 近年来，随着互联网技术的快速普及和迅猛发展，使各种信息可以以非常低的成本在网 络上获得，同时由于瓦联网在全球范围内的互连互通，使海量数据不断产牛。随之而来的问 题是面对浩如烟海的数据，如何能够在最短的时间内找到最适合自己的信息；如何从数据海 洋中挖掘出客户的活动信息，让用广可以得到个性化的服务，已经成为人们关注的焦点。w e b 数据挖掘技术也正是伴随着这种需求应运而生的，它能够从海量数据中，及时发现有用的知 识，提高信息的利用率。随着w e b 信息的迅速增长，对w e b 数据进行挖掘就必然成为数据挖 掘的一个前沿研究方向。 所谓w e b 挖掘 i 一钉，是数据挖掘技术在w e b 环境下的应用，是从大量的w e b 文档集合和 在站点内进行浏览的相关数据中发现蕴涵的、未知的、有潜在应用价值的、非平凡的模式的 过程【2 1 。它以在w e b 上挖掘有用知识为目标，以数据挖掘、文本挖掘、多媒体挖掘为基础， 并综合运用计算机网络、数据库与数据仓库、人工智能、信息检索、可视化、自然语言理解 等技术。w e b 挖掘将传统的数据挖掘技术与w e b 技术结合起来，在很多方面都优于传统的数 据挖掘。 目前，国际上对w e b 挖掘的研究主要集中在【2 3 】【5 卅：搜索引擎的设计、文件自动分类技 术、关键词的自动提取、半结构化信息的提取以及w e b 上新型应用的研究等方面。w e b 挖掘 还可以在很多应用领域发挥作用，如对搜索引擎的结构进行挖掘，确定权威页面，w e b 文档 分类，w e bl o g 挖掘、智能查询、建立m e t a - - w e b 数据仓库、使用文本信息挖掘工具和采用 用户访问模式挖掘工具等。 国内互联网是从1 9 9 7 年开始迅速蓬勃地发展起来的。直到1 9 9 9 年，国内互联网用户达 到一定数量以后，国内学者才开始关注w 曲数据挖掘，相比之下起步较晚。陈宁【7 j 1 9 9 9 年综 述了国外应用数据挖掘技术解决i n t e m e t 应用问题的做法，比如对w e b 新闻服务、用户访问 行为的假定。周斌等也介绍了采用e o e m 模型【8 】，并用5 个用户访问模式做训练数据集，尝 试着进行了关联规则挖掘。可见，w e b 数据挖掘在国内已经逐渐引起人们的关注，但是国内 的研究力量和研究水平与国外尚有一定的差距，还需要国内学者努力探索。 w e b 上的数据的最大特点是半结构化。由于w e b 挖掘的对象是大量半结构化、动态、杂 基于改进遗传算法的w e b 关联规则挖掘的研究 乱的w e b 数据，并且w e b 页面的复杂程度远远超过普通文本格式，因此其特性决定了w e b 挖掘无法直接应用传统的数据库领域的挖掘技术和模型。在众多的研究课题中，对半结构化 数据结构的研究是一个非常重要的方向，半结构化数据模型和半结构化数据模型抽取技术是 面向w e b 的数据挖掘技术实施的前提，是当今数据挖掘研究领域的热点之一。 w e b 挖掘是一个完整的技术体系，各个部分之间有着密切的关系。从w e b 用户的行为描 述上来说，用户对与某一个站点的访问行为方式是与时间有关系的，用户通过一段时间的访 问，对这个网站熟悉以后，他的访问行为可能会处于一种稳定状态，过一段时间( 如一个月或 者更长的时间) ，他的兴趣爱好可能会由于个性发展发生改变，象这样一种过程实际上是用户 对网站的一种适应、学习过程，也是个人自身个性的发展过程。w e b 用户的行为的这种发展 变化过程像极了人工智能中的学习过程，因此采用人工智能算法进行w 曲挖掘得到的知识应 比一般挖掘算法得到的知识更具有智能性、预见性和准确性。目前，将人工智能算法在w 曲 关联规则挖掘上己成为w e b 挖掘的研究热点之一。 总之，w e b 数据挖掘已经是当今世界上的热门研究领域之一，其研究具有广阔的应用前 景和巨大的现实意义。目前国内的w e b 数据挖掘尚处于学习、跟踪和探索阶段。w e b 数据挖 掘中有许多问题有待于进一步的研究和深化，本文将在前人研究的基础上，尝试将人工智能 算法应用到w e b 关联规则挖掘，提出了采用改进遗传算法提取w e b 关联规则的方法。在这一 研究过程中，提出了采用模拟退火算法b o l t z m a n 生存机制和建立自适应交叉概率等技术来解 决遗传算法的早熟问题。并讨论了遗传算法的编码方法、遗传算子、交叉算予、变异算子的 改进设计。最后结合m a t l a b 进行仿真实验，实验结果表明将改进遗传算法应用于w e b 关 联规则的提取，极大地提高了挖掘效率。 1 2 遗传算法的产生与发展现状 遗传算法g a 9 1 2 1 ( g e n e t i c a l g o r i t h m s ) 是模拟自然界生物进化过程的随机搜索算法，由美 国j h o l l a n d 教授于1 9 7 5 年提出的。它通过一定编码方案将问题解表示成遗传空间的一个基 因型串结构数据个体，将目标函数值转换成适应值，用来评价个体的优劣，并作为遗传操作 的依据。其实现主要通过初始种群确定、选择、交又、变异、评价筛选这几个步骤进行。与 传统优化方法相比，遗传算法使用了群体搜索策略，在群体的个体之间进行信息交换，其搜 索不依赖于梯度信息，具有不依赖于问题模型、适于并行处理、适于处理传统搜索方法难以 解决的复杂和非线性问题、鲁棒性强等特点。目前遗传算法已经在优化、机器学习和并行处 2 塑鐾查奎堂堡：! 兰垡笙苎 理等领域得到了越来越广泛的应用。 从六十年代开始，密切根大学教授j h o l l a n d 开始研究自然和人工系统地自适应行为，在 这些研究中，他试图发展一种用于创造通用程序和机器的理论，通用程序和机器具有适应任 意环境的能力，他意识到用群体方法搜索以及选择、杂交等操作策略的重要性。在六十年代 中期至七十年代末期，基于语言智z h 匕l - , 和逻辑数学智能的传统人工智能十分兴盛，而基于自然 进化的思想则遭到怀疑和反对。j h o l l a n d 及数位博士牛仍坚持了这一方向的研究。b a g l e y 1 3 】 发明了“遗传算法”一词并发表了第一篇有关遗传算法应用的论文，在他开创性的博士论文 中采用双倍体编码，发展了与目前类似的复制、交换、突变、显性、倒位等基因操作。他还 敏锐地察觉到防止早熟收敛，并发展了自组织遗传算法的概念。与此同时，r o s e n b e r g m 】在他 的博士论文中进行了单细胞牛物群体的计算机仿真研究，对以后函数优化的研究有很大的肩 发，并发展了自适应交换策略。c a v i c c h i o 于1 9 7 0 年研究了基于遗传算法的子程序选择和模 式识别问题，在模式识别问题上，采用整数编码，检索空间很大，他提出了以预选择策略保 证群体多样性，对遗传算法参数进行中心控制的方法。1 9 6 8 年至1 9 7 1 年，j h o l l a n d 提出了 重要的模式理论，建议采用二进制编码。与前面几位博士不同，j h o l l a n d 首次采用二迸制编 码来研究函数优化问题，并指出了运用二进制编码的一些优点，他研究了从生物系统引申各 种不同的选择和配对策略。1 9 7 5 年树立了遗传算法发展史上的两块里程碑，一是j h o l l a n d 出版了经典著作“a d a p t a t i o ni nn a t u r ea n d a r t i f i c i a ls y s t e m ”【9 】，该书是j h o l l a n d 十几年间许 多思想及其实现的结晶，详细阐述了遗传算法的理论，并为其奠定了数学基础，发展了一整 套模拟生物自适应系统的理论；二是d e j o n g 完成了其具有指导意义的博士论文a na n a l y s i so f t h eb e h a v i o ro f ac l a s so f g e n e t i ca d a p t i v es y s t e m s ”1 1 5 ，他深入领会了模式定理并做了严格的 计算实验，给出了明确的结论，他还建立了著名的d e j o n g 五函数测试平台，定义了性能评价 标准，并以函数优化为例，对遗传算法的六种方案的性能及机理进行了详细实验和分析，他 的工作成为后继者的范例并为以后的广泛应用奠定了坚实的基础。 进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、 机器学习和遗传算法等牛物系统底层模拟智能的研究重新复活并获得繁荣。g o l d b e r g 1 6 】在遗 传算法研究中起着继往开来的作用，他在1 9 8 3 年的博士论文中第一次把遗传算法用于实际的 工程系统一煤气管道的优化，从此，遗传算法的理论研究更为深入和丰富，应用研究更为广 泛和完善。 进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科学方 式得到学术界普遍认同，如广义进化综合理论，由于遗传算法能有效地求解属于n p 类型的 3 基于改进遗传算法的w e b 关联规则挖捌的研究 组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科地广泛重视，一 些学者也认识到求解复杂问题最优解是不现实的，故而寻求近似解，而遗传算法是最佳工具 之一，牛物进化的历史比任何数学证明都更加强有力。遗传算法在吸收遗传学、进化论及分 子生物学最新成果和在实验得到证明和证伪的同时本身也在进化。 进入新世纪以来，目前，对遗传算法的研究丰要集中在数学基础、各环节的实现方式以 及与其他算法的结合方面。其中，尤以遗传算法与其他算法相结合方面的研究最为引人关注。 由于遗传算法具有开放式的结构，与问题的关联性不大，很容易和其他算法进行结合，所以 融合了其他的算法思想和遗传算法思想的混合遗传算法成了目前改进遗传算法研究的一个重 要方向。 1 3遗传算法与w e b 挖掘 w e b 数据挖掘是一门新兴的数据挖掘技术，它涉及到计算机网络、数据库技术、人工智 能、机器学习等学科。其中如何从万维网中提取出用户感兴趣的信息是w e b 数据挖掘的一个 重要方面。遗传算法作为一种模拟自然进化思想的启发式全局寻优算法，是进化计算的杰出 代表，也是机器学习的重要方法。目前应用于w e b 数据挖掘的算法有许多种，遗传算法由于 其解决问题以混沌、随机和非线性为典型特征，它为其它科学技术无法解决或难以解决的复 杂问题提供了新的计算模型，特别是对于以大量的无序的数据为特征的问题，遗传算法是有效 解决的方法之一。因此将遗传算法引入到w 曲数据挖掘领域越来越引起学术界的重视，国外 己经有不少成功的范例，如：遗传算法与数据挖掘的聚类算法进行整合，发挥遗传算法启发 式全局寻优、和并行模式处理的计算优势，寻求最优聚类；将遗传算法与关联规则挖掘算法 相结合，挖掘关联规则并且对关联规则进行优化、预测；将遗传算法应用于由产生式规则构 成的知识树的优化等。随着w e b 数据挖掘应用领域的不断拓展，i b mi n d i ar e s e a r c hl a b 【r 7 】 和m i c h i g a ns t a t eu n i v e r s i t y 1 8 首- - 度将遗传算法引入到基于w 曲的数据挖掘上，为w 曲数据挖 掘提供了一个崭新的思考模式，虽然i b m 和m i c h i g a n 并未给出具体的技术细节，但是仍然 给人们对于处理复杂的w e b 的数据挖掘问题时指出了一个新的研究方向。 1 4 本文的研究内容和结构 本文将遗传算法应用到w e b 关联规则挖掘的方面，提出了采用改进遗传算法提取w e b 关 联规则的方法，并讨论了遗传算法的编码方法、遗传算子、交叉算子、变异算子的改进设计。 4 内蒙占大学硕士学位论文 最后结合m a t l a b 进行仿真实验，给出了基于改进遗传算法的w e b 关联规则的提取算法。 本文共包括五部分： 第一章绪论中丰要介绍了课题的研究背景及意义、国内外研究w e b 挖掘和遗传算法的现 状，并列出了本文的研究内容、研究方法和论文的结构，以及可能存在的创新点。 第二章介绍了遗传算法的基本原理主要包括遗传算法的理论基础、运算过程以及遗传算 法的主要特点，在以上介绍的基础上详细分析和探讨了遗传算法的早熟问题。同时详细描述 了w e b 挖掘的相关技术，对w e b 挖掘进行了详细的分类，探讨了w e b 挖掘的任务、方法、 对象及数据挖掘的创新等方面。最后，总结出w e b 挖掘的详细流程和目标。 第三章在研究关联规则基本概念的基础上，对其核心算法一a p r i o r i 算法进行了分析并且介 绍了一种改进的a p r i o r i 算法。同时在对w e b 上的关联规则进行详细分析与研究的基础上， 本文对w 曲关联规则的挖掘采用了增量挖掘技术。 第四章针对原有遗传算法存在的不足，提出了采用改进遗传算法来对w e b 关联规则进行 挖掘，并讨论了遗传算法的编码方法、遗传算子、交叉算子、变异算子的改进设计。在此基 础上提出了一种基于改进遗传算法的w e b 关联规则挖掘模型，并给出了该模型的实现技术和 算法。通过实例验证了算法的有效性和可行性，取得了良好的效果。 第五章结论与展望，对全文进行总结，并分析了今后的研究方向。 1 5 本文的研究方法 本文以改进经典遗传算法的早熟问题为理论目标，以提高w e b 关联规则的挖掘效率为应 用目标。在具体研究过程中，理论研究与应用研究相结合，将理论研究的成果应用到具体实 践应用中，为后续的研究者提供一定的理论借鉴和实践指导。 本文采用定性分析与定量分析相结合的方法，运用人工智能算法的基础知识，实现定性 模型的研究。运用遗传算法，利用m a t l a b 软件，实现定量模型的研究。 1 6 可能的创新点 本文可能存在的创新点包括以下两方面： 第一，本文主要从理论上对经典遗传算法进行详细的研究与分析。针对经典遗传算法容 易产生“早熟”解的特点，采用模拟退火算法b o l t z m a n 生存机制和建立自适应交叉概率等方 法来对经典遗传算法进行改进。实验结果表明，改进的遗传算法能有效的抑制早熟现象地发 5 基于改进遗传算法的w e b 关联规则挖掘的研究 生，和经典遗传算法相比，改进遗传算法无论在算法运行速度和正确率上都有了明显的提高。 第二，本文成功地将改进遗传算法应用于w e b 关联规则挖掘的实际应用当中。在这一过 程中讨论了改进遗传算法的编码方法、遗传算子、交叉算子、变异算子的改进设计，在此基 础上提出了一种基于改进遗传算法的w e b 关联规则挖掘模型，并给出了该模型的实现技术和 算法，并使用m a t l a b 环境编写程序对该模型进行求解和模拟遗传算法搜索过程。实证研究表 明，该方法具有一定的合理性与科学性。 6 内蒙古大学硕 ：学位论文 第二章基于遗传算法的w e b 挖掘技术 本章主要介绍了遗传算法的基本概念、理论基础、算法步骤、关键参数和特点，在以上 介绍的基础上探讨了遗传算法的早熟问题。同时详细描述了w e b 挖掘的相关技术，对w e b 挖掘进行了详细的分类，探讨了w e b 挖掘的任务、方法、对象及数据挖掘的创新等方面，最 后，总结出w e b 挖掘的详细流程和目标。 2 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 自2 0 世纪6 0 年代发明以来得到了广泛的关注， 尤其是模式定理的建立为遗传算法奠定了坚实的理论基础。遗传算法是借鉴自然界生物的自 然选择和遗传进化过程而开发出的一种全局优化自适应概率搜索算法。遗传算法【1 9 】【2 0 】使用群 体搜索技术，它通过对当前群体施加选择、交叉、变异等一些列遗传操作，从而产生新一代 的群体，并逐渐使群体进化到包含或接近最优解的状态。由于其思想简单，易于实现、应用 效果明显等优点而被众多应用领域所采用，并在自适应控制、组合优化、模式识别、机器学 习、人工生命、管理决策等领域得到广泛的应用。遗传算法为我们提供了一种求解非线性、 多模型、多目标等复杂系统优化问题的通用框架。遗传算法还是一类具有鲁棒性的优化算法， 特别对于一些大型的、复杂的非线性系统，它更体现出比其他传统优化算法更加独特的和优 越的性能。隐含并行性和全局搜索特点是遗传算法的两大显著特点。 2 1 1 遗传算法的描述 生物的进化过程丰要是通过染色体之间的交叉和变异来完成的。基于对自然界中生物遗 传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码( c o d i n g ) 方法来表示 问题的可行解，开发出了许多种不同的编码方式来模仿不同环境下的生物遗传特性。这样， 由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。遗传算法是模仿自然界 生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗 传学说。它本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有 关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作使用适者生存的 原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在遗传算法的每一代中，根 7 基于改进遗传算法的w e b 关联规则挖掘的研究 据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个 新的近似解。这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境，就像 自然界中的改造一样。 2 1 2 遗传算法的理论基础 遗传算法模拟的是自然界生物优胜劣汰的进化过程。但是，作为一种智能搜索算法，它 的木质内涵是什么? 更具体地讲，遗传算法的基因操作，即选择、交叉和变异算子何以能使 遗传算法体现出其它优化算法所没有的鲁棒性、自适应性和全局优化等，遗传算法的内在的 运行机理便是模式理论【l o 】所要阐述的问题。 由于遗传算法要处理一些具有相似编码结构的模板个体，这就需要引入一个描述这种相 似模板的新概念模式( s c h e m a ) 。 定义1 模式( s c h e m a ) 表示一些相似的模块，它描述了在某些位置上具有相似结构特征的 个体编码串的一个子集。 定义2 模式阶( s c h e m ao r d e r ) 亦称模式位数，在模式h 中确定基因值的位置数目称为该 模式的阶，记作o ( h ) 。 定义3 模式定义长度( s c h e m ad e f i n i n gl e n g t h ) 亦称模式距，它表示模式中的第一个确定基 因的位置和最后一个确定基因位置之间的距离，记为万( h ) 。 在引入模式的概念以后，遗传算法的实质可以看作是对模式的一种运算。对于基本遗传 算法而言，也就是某一模式h 的各种样本经过选择运算、交叉运算、变异运算之后，得到一 些新的样本和新的模式。 在这里我们假设在进化到第t 代时，当前群体a ( t ) 中能与模式h 匹配的个体数记为m ( h ，t ) ， 下一代群体a ( t + 1 ) 中能与模式h 匹配的个体数记为m ( h ，t + 1 ) 。下面对基本遗传算在选择算子、 交叉算子、变异算子的连续作用下，对模式h 的样本数m ( h ，t ) 讨论得到以下结论： 1 选择算子的作用 在选择过程中，群体a ( t ) 中任意一位串a i = f i e f ( a ；) ( f i 代表4 的适应度函数值， f 其他类同) 有放回被选中的并进行复制，并且假设种群的规模不变。 则在t + l 代，特定模式的数量为 m ( h ，f + 1 ) = m ( h ，f ) 毒f ( h ，t ) l f ( t ) ( 2 1 ) 8 内蒙占大学硕叶：学位沦文 在该式中f ( h ，f ) 是第t 代群体中模式h 所隐含个体的平均适应度；f ( t ) = f ( t ) m 是第t 代的群体的平均适应度。 若再假设模式h 的平均适应度总高出群体的平均适应度的c 倍，则上可改写为： m ( m ，t + 1 ) = m ( h ，t ) 宰( 1 + c )( 2 - 2 ) 由此可见，m ( h ，t ) 为一等比级数，其通项公式为： m ( n ，t + 1 ) = m ( h ，0 ) 幸( 1 + c ) ( 2 3 ) 由式( 2 3 ) 可知： 若c 0 ，则m ( h ，t ) 呈指数级增长； 若c m i n _ s u p ) r e t u r nl = u kk ) l k ； 内蒙占大学硕上学位论文 p r o c e d u r ea p r i o r i _ g e n ( l k 1 ，r a i n _ s u p ) f o re a c hi t e m s e ti i l k f o re a c hi t e m s e t1 2 l k - 2 i f ( ( i i 1 = 1 2 1 】n i i k - 2 = 1 2 k - 2 】厂、i i k - - 1 】 1 2 【k 一1 ) ) t h e n c = 1 1u1 2 ；将两个项集连接到一起 i fh a s _ i n f r e q u e n t _ s u b s e t ( c , ，l k1 ) d e l e t ec ；除去能产生频繁项集的候选 ) e l s ec k = c k u c ) r e t u r nc k ) p r o c e d u r eh a s _ i n f r e q u e n t _ s u b s e t ( c ，l k _ 1 ) f o re a c h ( k 一1 ) s u b s e tso f c i f s 旺l k 一1 ， r e t u r nt r u e ； e l s e r e t u r nf a l s e ； ) 影响a p r i o f i 算法计算复杂度的因素有两个：一个是候选项集的牛成，另一个为计算候选 项集的支持度而对事务数据库的扫描。虽然通过a p r i o r i 性质大幅度压缩了候选项集的大小， 但是有两种开销不能忽视：一种是可能产生大量的候选项，另一种是可能需要重复扫描事务 数据库，通过模式匹配检查一个很大的候选集合。对于挖掘长模式需要次数更多，很多研究 人员对如何提高a p r i o r i 算法的性能进行了相关的研究陟3 。 下面引入了一种改进的a p r i o r i 算法，主要从候选项集减少和事务数据库的压缩两方面来 考虑。 改进后的a p r i o r i 算法【3 0 】 基于改进遗传算法的w e b 关联规则挖掘的研究 输入：事务集合( d ) ，最小支持度( m i n