（应用数学专业论文）改进型遗传算法在多维关联规则挖掘中的应用.pdf

摘要 遗传算法是一种全局优化算法。将遗传算法应用于关联规则挖掘，用户可以 发现比较有用的规则。由于简单遗传算法容易出现早熟现象，其收敛速度不是 很快，本文将简单遗传算法加以改进，通过引入浓度概念，对选择算子进行了 改进，同时通过引入随机数，对交叉和变异算子进行了改进，从而抑制早熟现 象，提高算法的收敛速度，达到更有效的挖掘多维关联规则的目的。 本文的主要内容如下： 1 ) 数据挖掘技术的分析研究：对数据挖掘的定义、国内外研究现状、过程 与功能、方法与分类、应用进行了概述。 2 ) 关联规则的分析研究：介绍了关联规则的定义、分类，对最经典的关联 规则挖掘算法a p r i o d 算法作了详细描述，同时还介绍了该算法的一些改进算法。 3 ) 遗传算法的分析研究：对遗传算法的基本思想、术语和特点进行了概述， 分析了遗传算法的基本实现技术。 4 ) 基于改进型遗传算法的多维关联规则挖掘：对利用遗传算法进行关联规 则挖掘的思想进行了介绍，提出一种基于改进型遗传算法的多维关联规则挖掘 模型。 5 ) 改进型遗传算法在多维关联规则挖掘中的应用：将改进型遗传算法的多 维关联规则挖掘模型应用到我国企业科技工作者的现状分析中。 本文的主要创新点如下： 1 ) 由于轮盘赌法仅取决于适应度，因此可能导致早熟现象。针对这一问题， 本文对选择算子进行了改进，通过引入浓度概念，使得个体的选择概率不仅与 适应度有关，而且与浓度有关，从而有效地避免了早熟现象。 2 ) 简单遗传算法运用固定的交叉概率与变异概率，并不能达到理想的效果。 针对这一问题，本文引入随机数，通过随机动态调节交叉概率和变异概率，使 得交叉概率和变异概率随着适应度的改变而自动改变，从而有效地抑制了早熟 现象，提高了算法的收敛速度。 3 ) 将我们构建的改进型遗传算法进行多维关联规则挖掘模型，应用到我国 企业科技工作者的现状分析中，通过该实例验证了新算法的有效性和可行性。 关键词：数据挖掘，多维关联规则，改进型遗传算法 a b s t r a c t g e n e t i ca l g o r i t h mi sag l o b a lo p t i m i z a t i o na l g o r i t h m u s i n gg e n e t i ca l g o r i t h m f o ra s s o c i a t i o nr u l e sm i n i n gc a nf i n du s e f u lr u l e s g i v e nt h es i m p l eg e n e t i ca l g o r i t h m i se a s yt oa p p e a rt h ep h e n o m e n o no fp r e m a t u r ea n dc o n v e r g e n c es p e e do ft h es i m p l e g e n e t i ca l g o r i t h mi sn o tf a s t ，t h i sp a p e ri m p r o v e ss i m p l eg e n e t i ca l g o r i t h m ，i m p r o v i n g t h es e l e c t i o no p e r a t o rb yi n t r o d u c i n gt h ec o n c e p to fc o n c e n t r a t i o n , i n t r o d u c i n ga r a n d o mn u m b e r , i m p r o v i n gt h ec r o s s o v e ro p e r a t o ra n dm u t a t i o no p e r a t o rt oa v o i dt h e p h e n o m e n o no fp r e m a t u r e ，i m p r o v ec o n v e r g e n c es p e e do ft h ea l g o r i t h ma n dm i n e m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sm o r ee f f i c i e n t l y n 圮m a i nc o n t e n t so ft h i sa r t i c l ea r ea sf o l l o w s ： 1 ) t h ea n a l y s i so fd a t am i n i n g ：t h i sp a p e rs u m m a r i z e st h ed e f i n i t i o no fd a t a m i n i n g ，r e s e a r c ha th o m ea n da b r o a d ，p r o c e s s e s ，f u n c t i o n s ，m e t h o d s ，c l a s s i f i c a t i o n s ， a p p l i c a t i o n s 2 ) t h ea n a l y s i so fa s s o c i a t i o nr u l e s ：t h i sp a p e ri n t r o d u c e st h e d e f i n i t i o no f a s s o c i a t i o nr u l e sa n dc l a s s i f i c a t i o n ，d e s c r i b e st h em o s tc l a s s i ca s s o c i a t i o nr u l e s a l g o r i t l l m a p r i o f ia l g o r i t h mi nd e t a i l ，i n t r o d u c e ss o m ei m p r o v e da l g o r i t h mo f i t 3 ) a n a l y s i so fg e n e t i ca l g o r i t h m s ：t h i sp a p e rs u m m a r i z e st h eb a s i ci d e ao f g e n e t i ca l g o r i t h ma n df e a t u r e s ，a n a l y z e sb a s i ci m p l e m e n t a t i o nt e c h n o l o g yo ft h e g e n e t i ca l g o r i t h m 4 ) m u l t i d i m e n s i o n a la 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 dg e n e t i c a l g o r i t h m ：t h i sp a p e ri n t r o d u c e st h ei d e aw h i c hu s e sg e n e t i ca l g o r i t h mf o ra s s o c i a t i o n r u l e sm i n i n g ，p r o p o s e sam u l t i - d i m e n s i o n a la s s o c i a t i o nr u l e sm i n i n gm o d e lb a s e do n i m p r o v e dg e n e t i ca l g o r i t h m 5 ) a p p l i c a t i o no f m u l t i d i m e n s i o n a la 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 ：t h i sp a p e ra p p l i e st h em u l t i - d i m e n s i o n a la s s o c i a t i o nr u l e sm i n i n g m o d e lb 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 mi nt h ea n a l y s i so fs c i e n t i f i ca n d t e c h n o l o g i c a lw o r k e r si nc h i n e s ee n t e r p r i s e s t h em a i ni n n o v a t i o n so ft h i sp a p e ra r ea sf o l l o w s ： 1 ) t h er o u l e t t ew h e e ls e l e c t i o no p e r a t o ro n l yd e p e n d so nt h ef i t n e s sv a l u e ，w h i c h w i l ll e a dt op h e n o m e n o no fp r e m a t u r e i no r d e rt os o l v et h i sp r o b l e m ，t h ep a p e r i m p r o v e st h es e l e c t i o no p e r a t o r w ei n t r o d u c et h ec o n c e p to fc o n c e n t r a t i o n ，m a k et h e s e l e c t i o np r o b a b i l i t yo fi n d i v i d u a l sh a v i n gr e l a t i o nb o t hw i t ht h e f i t n e s sa n d c o n c e n t r a t i o n ，t h u st h ep h e n o m e n o no fp r e m a t u r ec o n v e r g e n c e i sa v o i d e de f f i c i e n t l y 2 ) t h es i m p l eg e n e t i ca l g o r i t h mu s e saf i x e dc r o s s o v e rp r o b a b i l i t ya n dm u t a t i o n p r o b a b i l i t y , w h i c hc a n n o tg e tag o o dr e s u l t i no r d e r t os o l v et h i sp r o b l e m ，t h i sp a p e r i n t r o d u c e sar a n d o mn u m b e r , u s e sa d a p t i v em e t h o dd y n a m i c a l l ya n ds t o c h a s t i c a l l y s e l e c t i n gc r o s s o v e rp r o b a b i l i t ya n dm u t a t i o np r o b a b i l i t y , m a k e sc r o s s o v e rp r o b a b i l i t y a n dm u t a t i o n p r o b a b i l i t ya u t o m a t i c a l l yc h a n g i n g w i t ht h ef i t n e s s ，t h u st h e p h e n o m e n o no fp r e m a t u r ec o n v e r g e n c ei sa v o i d e de f f e c t i v e l ya n dc o n v e r g e n c es p e e d o ft h ea l g o r i t h mi si m p r o v e d 3 ) t h i sp a p e ra p p l i e st h em u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sm i n i n gm o d e l b 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 mi nt h ea n a l y s i so fs c i e n t i f i ca n dt e c h n o l o g i c a l w o r k e r si nc h i n e s ee n t e r p r i s e s ，w h i c hv a l i d a t e st h ee f f e c t i v e n e s sa n df e a s i b i l i t yo ft h e n e wa l g o r i t h m k e yw o r d s ：d a t am i n i n g ，m u l t i - d i m e n s i o n a la s s o c i a t i o nr u l e s ，i m p r o v e dg e n e t i c a l g o r i t h m 1 1 1 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：缝日期：垒丝丝丝 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：雠 导师( 签名) ： 日期炒卜彤 武汉理工大学硕士学位论文 第1 章绪论 随着知识时代的到来，信息在这样的背景下变得越来越重要，而数据作为信 息的直接表现形态，已经成了现代人类进行组织、管理乃至决策的直接手段。 计算机硬件作为人类数据收集的直接物理设备，它的进步为人类进行数据收集 提供了很大的方便：互联网技术的发展将世界缩成一个同心圆，人们无论何时 都可以进行信息共享，无论何地都可以进行信息交流。在这样一个信息爆炸的 时代，人们希望拥有一种能够将数据转换成对决策有用的信息的技术。数据挖 掘就在这样的背景下产生了。 1 1 数据挖掘概述 1 1 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ，d m ) 是从大量的、不完全的、有噪声的、随机的 实际应用数据中，提取人们事先不知道的、隐含在其中的、但又是潜在有用的 信息的过程i l j 。 这个定义有如下六层含义： 1 ) 我们所选取的数据源必须是大量的、含噪声的数据源； 2 ) 我们所选取的数据源必须是真实可靠的数据源； 3 ) 我们所发现的知识必须是用户感兴趣的知识； 4 ) 我们所发现的知识必须是可以理解的、可以接受的知识； 5 ) 我们所发现的知识必须是可以运用的知识： 6 ) 我们所发现的知识不必是无论在什么情况下都一定适用的知识，只要在 特定情况下能解决特定的问题就可以。 知识发现、数据融合、数据分析等与数据挖掘同义。其中，我们经常用到的 是“知识发现”与“数据挖掘”。知识发现主要用于机器学习与人工智能；数据挖掘 则主要用于数据库、管理信息系统与统计。 武汉理t 大学硕七学位论文 1 1 2 数据挖掘的国内外研究现状 目前，国外对数据挖掘的研究主要是对回归法在数据挖掘中的应用、贝叶斯 方法、数据挖掘与数据库的结合等方法的研究。 世界上比较有影响的数据挖掘产品有s p s s 公司的c l e m e n t i n e ，i b m 公司的 i n t e l l i g e n tm i n e r ，s a s 公司的e n t e r p r i s em i n e r 等。 与国外相比，国内对数据挖掘的研究还比较分散，相对不是很集中。1 9 9 3 年国家自然科学基金首次对数据挖掘领域的研究项目给予了重视和支持。1 9 9 5 年以后，在人工智能与模式识别、计算机研究与发展、软件学报、：计 算机学报等刊物上又发表了一批相关的研究成果1 2 5 1 。研究的内容既有学术研 究，又有实际应用研究。 目前国内许多科研院所和高校也在从事数据挖掘的研究，如北京大学对数据 立方体代数进行了深入的研究；上海交通大学、南京大学等开展了对w e b 数据 挖掘以及非结构化数据挖掘的研究；中科院数学研究所、浙江大学、复旦大学、 华中科技大学等对关联规则挖掘算法的优化进行了深入的研究；北京系统工程 研究所开展了对模糊方法在知识发现中的应用的研究。 1 1 3 数据挖掘的过程与功能 一、数据挖掘的过程 数据挖掘的过程很复杂，其一般步骤是1 4 ，”： 1 ) 理解问题 它的主要目标是通过对问题的理解，从而确定整个操作过程的研究对象和目 标，即研究范畴。 2 ) 理解数据 它的主要目标是对初始数据进行收集。 3 ) 数据准备 它的主要目标是得到质量较高的数据。 4 ) 建立模型 它的主要目标是根据样本数据建立模型。 5 ) 方案评估 它的主要目标是进行检验，确定方案的可行性。 2 武汉理工大学硕士学位论文 6 ) 方案实施 它的主要目标是根据前面建立的模型以及对可行性方案的分析来进行具体 的实施。 二、数据挖掘的功能 数据挖掘的主要功能是从海量数据中挖掘出有价值的知识1 6 ，7 1 。 ( 1 ) 关联分析 关联分析就是为了挖掘出数据库中隐藏的关联规则。 ( 2 ) 分类 分类就是计算测试样本点与已知数据类的相似程度，并将该测试样本点划入 与它相似程度最近的数据类的过程。 ( 3 ) 聚类 聚类就是以组内差异最小、组间差异最大为标准，将数据集划分为不同的类。 ( 4 ) 时间序列分析 时间序列分析主要是对那些横向数据进行分析和预测的过程。 ( 5 ) 孤立点分析 孤立点分析就是对与大多数样本点特性相差很大的样本点进行的分析过程。 1 1 4 数据挖掘的方法与分类 一、数据挖掘的方法 数据挖掘经常用到的方法包括以下几种【8 9 】： ( 1 ) 关联规则挖掘 关联规则挖掘就是为了挖掘出数据库中隐藏的关联规则。 ( 2 ) 决策树方法 决策树原理就是以某种方法计算各属性对样本的区分度，利用区分度高的属 性作为分类依据，从而将样本进行区分。 ( 3 ) 贝叶斯方法 在数据挖掘中，我们主要使用的是朴素贝叶斯方法和贝叶斯网络这两种贝叶 斯方法。 ( 4 ) 神经网络方法 神经网络就是通过模拟人脑细胞的学习过程而建立的一种处理数据集的机 器学习方法。 3 武汉理工大学硕士学位论文 ( 5 ) 遗传算法 遗传算法就是通过选择操作、交叉操作和变异操作，使要解决的问题从随机 产生的初始解一步步逼近问题的最优解。 二、数据挖掘的分类 数据挖掘有以下几种分类： ( 1 ) 按照数据挖掘的应用面可分为： 特定、通用领域的数据挖掘。 ( 2 ) 按照所处理的数据的类型可分为： w e b 、多媒体、时域、空间、文本、关系、面向对象数据挖掘。 ( 3 ) 按照数据挖掘所处理的数据类型可分为： 非结构化、半结构化、结构化数据挖掘。 ( 4 ) 按照数据挖掘所挖掘的规则类型可分为： 关联规则、误差分析规则、分类规则、聚合规则、特征规则、判别规则、进 化规则挖掘。 ( 5 ) 按照数据挖掘所发现的知识的抽象层次可分为： 原始层、多层、一般性知识挖掘。 ( 6 ) 按照所采用的数据挖掘技术可分为： 交互式、验证驱动、发现驱动、自制的知识数据挖掘。 1 1 5 数据挖掘的应用 数据挖掘是一门偏向于应用的学科，在零售、银行、电信等许多领域都得到 了成功的应用。有关数据挖掘的典型应用现列举如下。 ( 1 ) 客户流失预测 通过预测客户可能的流失情况，我们可以找出可能会流失的一些客户，采取 相应的措施，对这些客户进行挽留，不仅能够提高产品收入，而且能够降低营 销成本。客户流失预测可应用于电信、银行、科学研究等领域。 ( 2 ) 异常发现 异常发现就是找出数据中的异常点，它类似于孤立点分析。当今社会，银行 业的竞争日趋加剧，许多银行争相发行信用卡，一些不法分子通过假资料来申 请信用卡，大肆挥霍。因此，对于所有的申请资料，我们可以通过数据挖掘， 对其进行评分，从而发现信用卡欺骗者，以避免不必要的损失。 4 武汉理工大学硕+ 学位论文 ( 3 ) 个性化服务 通过分析每个消费者的购买记录，我们可以发现这些消费者不同的购买习 惯，从而采取相应的措施，对不同的人进行不同的促销或提供不同的服务。在 电子商务中，根据消费者以往的购买记录，针对不同的消费者，网站会给他们 推荐不同的新产品。 ( 4 ) 科学发现 通过分析大量的科学实验数据，我们可以发现许多新的科学知识。通过分析 大量的生物信息数据，我们发现了新的基因和蛋白质折叠；通过分析大量的医 疗数据，我们发现了疾病和药物之间存在的内在关系；通过分析大量的天文数 据，我们发现了新的星球体。 ( 5 ) 预警 通过分析数据的趋势，对将会发生的事故，我们提出预警。在电信业中，通 过分析以前的那些报警数据，我们可以发现那些很可能是重大问题前兆的常规 报警，同时提出预警，以阻止不幸事故的发生。 1 2 本文的研究目的 简单遗传算法在实际应用中会出现早熟收敛现象。针对这一问题，本文将简 单遗传算法加以改进，应用于多维关联规则挖掘。在该算法中，我们通过引入 浓度概念，对选择算子进行了改进，并引入随机数，随机动态选取交叉概率和 变异概率，目的是有效地抑制早熟收敛现象，加快算法的收敛速度。 1 3 本文的组织结构 本文共分六章，内容概要如下： 第l 章：绪论。首先从数据挖掘的定义、数据挖掘的国内外研究现状、数据 挖掘的过程与功能、数据挖掘的方法等几方面对数据挖掘技术作了比较详细的 概述，随后介绍了本文的研究目的和组织结构。 第2 章：关联规则研究。对关联规则的定义、关联规则的分类作了比较详细 的介绍，对最经典的关联规则算法a p r i o r i 算法作了详细描述，同时介绍了a p r i o r i 算法的几种优化算法。 武汉理工大学硕士学位论文 第3 章：遗传算法的基本原理。介绍了遗传算法的基本思想、遗传算法的术 语以及遗传算法特点，重点介绍了遗传算法的基本实现技术，包括编码方法的 选取、适应度函数的构造、遗传算子的设计及遗传算法控制参数的设定，同时 给出了遗传算法的流程图。 第4 章：基于改进型遗传算法的多维关联规则挖掘。介绍了利用遗传算法进 行关联规则挖掘的思想，提出了一种基于改进型遗传算法的多维关联规则挖掘 模型，包括编码方法的选取、适应度函数的构造、改进型遗传算子的设计、规 则的提取及提取关联规则算法描述，并给出了改进型遗传算法提取多维关联规 则的流程图。 第5 章：应用实例高新区企业科技工作者的社会现状分析。将改进型遗 传算法应用于数据挖掘中多维关联规则的挖掘中，并与我国企业科技工作者的 现状相结合，通过实例验证了该算法的有效性和可行性。 第6 章：总结与展望，总结了本文的工作，并指出将来努力的方向。 6 武汉理t 大学硕+ 学位论文 2 1 关联规则概述 第2 章关联规则研究 关联规则挖掘可以挖掘出数据库中隐藏的关联规则。如今，通过对大量数据 不断地收集与存储，对于从他们的数据库中挖掘关联规则，许多业界人士已经 越来越感兴趣。 1 9 9 3 年，a g r a w a l 等在对市场购物篮问题进行分析时，首次提出了关联规则 挖掘算法，以此来发现顾客购买商品的模式。购买模式就是指顾客在同一个购 物篮中所购买的商品之间的联系，通过顾客的购买模式来了解他们的购买习惯， 从而可以更好的制定市场营销策略。 最近几年，在数据挖掘领域，关联规则挖掘受到普遍关注，它已成为数据挖 掘中一个十分重要的方法。我们可以通过关联规则挖掘，发现大量数据之间存 在的关联关系。并且随着数据量的不断增大，关联规则挖掘也越来越广泛的应 用到各个领域【l 州引。 关联规则挖掘不仅可以用于分析市场购物篮问题，而且还可以用于分析宏观 决策支持、工程技术数据分析、互联网、电子商务、网站设计、商业与金融、 医疗财政等问题。 2 2 关联规则的定义 下面将关联规则挖掘中涉及到的相关概念介绍一下。 定义2 2 1 关联规则挖掘的数据集记为d ，d = ，l ，2 9b * g t 。， 称为事务 数据库，t c = 19 i s ，f ，) ，其中t a c - - - l ，2 ，s ) 称为事务，而( z = 1 ，2 ，) 称 为项目。 定义2 2 2 设i = 】i ，乙) 是d 中全体项目组成的集合，的任何子集么称 为d 中的项目集。 定义2 2 3 设r f 和彳分别为d 中的事务和项目集，如果彳量，f ，称事务f c 包含 项目集彳。 7 武汉理t 大学硕士学位论文 定义2 2 4 关联规则是形如ajb 这样的蕴含式，其中aci ，bci ，并且 a n b = 矽。关联规则反映在彳成立的情况下，曰也成立的比例。 定义2 2 5 规则a jb 在数据集d 中成立，具有支持度s ，它是概率只彳u 四。 规则ajb 在数据集d 中具有置信度c ，它是条件概率只召铘。即 s u p p o r t ( a j b ) = p ( a u b ) = s u p p o r t ( a u 曰) n f i d e n c e ( aj 曰) ：p ( b a ) ：s u pp o r t ( a _ u _ b 一) s u pp o r t a 定义2 2 6 同时满足最小支持度( s 晌) 和最小置信度( c 椭) 的规则称为强关联 规则。即 aj b ( & 一毒占) j 晌) ( & - j 口) c 曲) 一般而言，我们认为强关联规则是有用的，而那些具有较低支持度的关联规 则是无用的，因为这些具有较低支持度的关联规则多半是少见的、异常的或者 是噪声。 我们之所以要进行关联规则挖掘，就是为了找出那些具有最小支持度和最小 置信度的强关联规则。若所发现的关联规则的支持度太低，则说明这些规则不 具有一般性；若所发现的关联规则的置信度太低，则说明这些规则的可信程度 差。因此，我们进行关联挖掘，就是为了能发现那些具有一般性的并且可信的 规则。 定义2 2 7 如果一个项目集彳满足最小支持度( s u p p o r t ( a ) ) ，则称它为 频繁项目集，频繁k 项目集的集合记为厶。 定义2 2 8 如果一个项目集彳不满足最小支持度( s u p p o r t ( a ) ) ，则称它 为非频繁项目集。 定义2 2 9 候选项目集是潜在的频繁项目集的集合，是频繁k 项目集的超 集，含有k 项的候选项目集记为q 。 2 3 关联规则的分类 根据不同的标准，关联规则有不同的分类方法： ( 1 ) 根据规则所处理的值的类型可以分为以下两类： a 布尔关联规则 布尔关联规则所处理的值是离散的。例如： b u y s ( y , c o m p u t e r ”) jb u y s ( y , p r i n t e r ”) ( 2 1 ) 8 武汉理工大学硕十学位论文 其中，】，是代表顾客的变量。 b 量化关联规则 量化关联规则描述量化属性之间的关联。例如： i n c o m e ( y , 4 0 0 0 5 0 0 0 ”) jb u y s ( y , h i g h r e s o l u t i o n t v ) ( 2 2 ) 其中，量化属性i n c o m e 己经离散化。 。 ( 2 ) 根据规则所涉及的数据维数可以分为以下两类： a 单维关联规则 在单维关联规则中，关联规则中的属性只涉及一个维。 上面的规则( 2 1 ) 是单维关联规则，因为它只涉及一个维b u y s 。 b 多维关联规则 在多维关联规则中，关联规则中的属性涉及两个或多个维。 上面的规则( 2 2 ) 是多维关联规则，因为它涉及两个维i n c o m e 和b u y s 。 ( 3 ) 根据规则所涉及的抽象层可以分为以下两类： a 单层关联规则 在单层关联规则中，规则挖掘只涉及相同抽象层的属性。例如： b u y s ( y , i b mc o m p u t e r ”) jb u y s ( y , h pp r i n t e r ) ( 2 3 ) 其中，“i b mc o m p u t e r ”和“御p r i n t e r ”属于同一概念层次上的数据。 b 多层关联规则 在多层关联规则中，规则挖掘涉及不同抽象层的属性。例如： b u y s ( y , i b mc o m p u t e r ”) jb u y s ( y ，p r i n t e r ”) ( 2 4 ) 其中，“i b mc o m p u t e r ”和“p r i n t e r ”不属于同一概念层次上的数据。 2 4 关联规则挖掘算法 关联规则挖掘问题般可分为以下两个子问题l i j j ： 1 ) 找出全部的频繁项目集； 2 ) 根据频繁项目集产生强关联规则。 第一个子问题是关联规则挖掘算法比较复杂的问题，目前大多数学者都在研 究这方面的问题，因为它是关联规则挖掘算法的核心，至于第二个子问题，相 对比较简单，发展也比较成熟了。 9 武汉理t 大学硕十学位论文 2 4 1a p r i o r i 算法 a p r i o r i 算法【1 4 , 1 5 1 是最经典的关联规则算法。该算法步骤如下：首先找出频 繁1 项目集厶，然后利用厶来挖掘频繁2 项目集厶，一直循环下去，直至不能 找到频繁k 项目集厶为止【1 6 ，1 7 1 。 a p r i o r i 性质如果项目集彳是频繁项目集，那么其所有非空子集一定是频繁 项目集。 运用a 研嘶性质，通过厶一。找到厶，依次运用连接步和剪枝步来完成。 1 ) 连接步 为了找到厶，我们通过厶一。与自己连接来产生候选k - 项目集的集合g 。设，l 和，2 是厶一。中的项目集。 如果： ( i i 【1 】= 乞 1 】) ( 【2 】= 1 2 1 2 ) a a ( 1 l k - 2 】= 1 2 【七一2 】) ( ，l 【七- 1 】 1 2 k l 】) 其中，z 【刀表示的第- j f 项。并且他们的前( k - 2 ) 个项相同，执行连接厶一。厶一。 连接，1 和，产生的结果是： 【1 m 【2 】，l 【七- 1 2 k - l 】 2 ) 剪枝步 连接之后产生的结果g 是厶的超集，之后扫描事务数据库，然后确定g 的 每一个候选计数，这样就可以确定厶。确定厶之后，我们就可以运用a p r i o r i 性质对g 进行剪枝，把子集不在厶一。中的候选七一项目集从q 中删除。 2 4 2a p r i o r i 算法的优化算法 a p r i o r i 算法在实际应用中可能会存在下面两个问题： 1 ) 该算法需要反复扫描事务数据库。 2 ) 该算法会产生大量候选项目集，不利于生成有效的规则。 因为a p r i o r i 算法存在上述的一些问题，所以为了改善算法的效率，许多学 者对a p r i o r i 算法作出了一些改进，提出了下面一些算法： ( 1 ) 基于散列的算法i l 卅 p a r k 等于1 9 9 5 年提出了基于散列的算法。他在试验中发现，频繁项目集主 要计算是生成厶，所以，他根据这一特性，引进了散列技术，从而达到改进生 成厶的目的。该方法的主要思想是，把扫描的项目放在不同h a s h 桶中，这样测 1 0 武汉理工大学硕士学位论文 试每一个桶中的项目子集，将减少候选项目集生成的代价。 ( 2 ) 基于划分的算法i i 引 s a v a s e r e 等人为了提高算法的并行性，改善算法对内存的需求，于是提出了 基于划分的算法。该算法的主要思想是，把数据库在逻辑上分成几个互不相交 的部分，然后单独考虑每一个部分，并且生成它的频繁项目集，最后将所有频 繁项目集合并，用来产生新的频繁项目集，并且计算它们的支持度。 ( 3 ) 基于采样的算法u j t o i v o n e n 于1 9 9 6 年提出了基于采样的算法，该算法首先对数据集d 进行随 机抽样，得到样本数据集s 。然后找出s 中的频繁项目集r ，这个一般要求设定 比较低的支持度阈值。其次是在数据集d s 中计算r 内每一个元素的支持数。 最后是利用支持度阈值来得到频繁项目集厶。 ( 4 ) 事务压缩算法 不包含任何k 项目集的事务不可能包含任何( 七+ 1 ) 项目集，因而可以将这 些事务删除，以减少扫描的事务集的个数。 ( 5 ) f p g r o w t h ( f r e q u e n t - p a t t e r ng r 0 州h ) 算法1 2 l j 为了避免产生大量的候选频繁项目集和重复地扫描数据集，h a r t 等人于2 0 0 0 年提出了f p 树( 频繁模式树) 的算法。它的主要步骤如下：首先进行第一次扫描， 把提供的频繁项目集数据库压缩到一棵f p 树上。然后把f p 树分割成一些条件 模式。最后对这些条件模式进行挖掘。 2 5 本章小结 本章对关联规则的定义、关联规则的分类进行了阐述，对最经典的关联规则 挖掘算法a p r i 嘶算法作了详细描述，分析了a p d o r i 算法存在的问题。同时还介 绍了a 砸o r i 算法的几种优化算法，包括基于散列的算法、基于划分的算法、基 于采样的算法、事务压缩算法和f p g r o w t h 算法，并分析了这几种优化算法的思 想。 武汉理t 大学硕士学位论文 第3 章遗传算法的基本原理 3 1 遗传算法概述 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 最早由美国密执安大学的h o f l a n d 教授 提出来，它是一种全局优化概率的搜索算法，我们一般将h o f l a n d 提出的遗传算 法称为简单遗传算法。在二十世纪7 0 年代，d ej o n g 在遗传算法的基础上进行 了大量纯数值函数优化计算的实验。二十世纪8 0 年代，g o l d b e r g 在前人的基础 上对遗传算法进行了发展和总结，形成了目前遗传算法的框架2 2 1 。 3 1 1 遗传算法的基本思想 遗传算法的基本思想是【9 1 ： 1 ) 从物种进化理论的遗传和变异两个方面来求问题的解。 2 ) 只有经过反复求解才能得到问题的最优解。 3 1 2 遗传算法的术语 下面我们解释一下一些常用术语j ： ( 1 ) 染色体：算法中的编码串。 ( 2 ) 基因：串中的元素。 ( 3 ) 基因位：基因在染色体中的位置。 ( 4 ) 等位基因：同一基因位可能有的全部基因。 ( 5 ) 基因型：生物个体所特有的基因及其构成形式。 ( 6 ) 表现型：生物个体所表现出来的性状。 ( 7 ) 群体：个体的集合。 ( 8 ) 群体大小：群体中个体的数量。 ( 9 ) 适应度：适应度表示个体对生存环境的适应程度。 1 2 武汉理工大学硕士学位论文 3 1 3 遗传算法的特点 与传统优化算法相比，遗传算法具有以下特点1 2 4 ，2 5 。： ( 1 ) 遗传算法是将决策变量某种形式的编码作为运算对象。 在传统优化算法中，我们进行优化计算通常是直接利用决策变量本身，而在 遗传算法中，我们则是将决策变量某种形式的编码作为运算对象。 ( 2 ) 遗传算法采用的是概率搜索技术。 在传统优化算法中，我们采用的是确定性搜索技术，而在遗传算法中，我们 采用的则是概率搜索技术，其中，选择操作、交叉操作和变异操作这三个遗传 操作都是以概率方式进行的，这样就使得搜索过程更加灵活。 ( 3 ) 遗传算法是直接以目标函数值来确定搜索范围与搜索方向的。 在传统优化算法中，对于搜索范围与搜索方向的进一步确定，我们既要利用 目标函数值，又要利用目标函数导数值这样一些辅助信息才可以，而在遗传算 法中，对于搜索范围与搜索方向的进一步确定，我们则只需要使用由目标函数 值变换成的适应度函数值就可以了。 ( 4 ) 遗传算法是从一个初始群体开始进行迭代搜索的。 在传统优化算法中，我们通常是从一个初始点开始进行迭代搜索，而在遗传 算法中，我们则是从一个初始群体开始进行迭代搜索的，这样可以在很大程度 上提高算法的搜索效率。 3 2 遗传算法的基本实现技术 3 2 1 编码方法 在遗传算法编码中，二进制编码是主要的编码方法，但是二进制编码方法存 在一定的缺点，因为在优化过程中用二进制编码表示问题的解，需要在二进制 和十进制之间进行转换，这势必会存在转换误差。 而采用实数数组编码方法来表示问题的解却可以克服这方面的缺点，因为在 优化过程中，采用实数数组编码方法不需要对参数进行编码和解码，所以就不 存在转换误差的问题。并且，采用实数数组编码方法表示问题的解的数字串比 二进制编码方法要短，所以所需要计算的时间也会相应减少。 总的来说，二进制编码的搜索能力较强，而实数数组编码能够更好地保持群 1 3 武汉理工大学硕七学位论文 体稳定性，所以我们要根据实际优化的问题来选择采用哪种编码方法【2 6 - 2 8 。 3 2 2 适应度函数 在遗传算法中，我们一般要求适应度值非负，并且希望适应度值越大越好。 在实际中，我们通常将优化问题的目标函数f ( x ) 变换成适应度函数f ( x ) 。变换 方法有： ( 1 ) 求最大值问题 对于求最大值问题，适应度函数f ( 力和目标函数厂( 功有如下关系： f ( x ) = f ( x ) + r l ( 3 1 ) 其中，刁可以取目标函数可能的最小负值的相反数。 ( 2 ) 求最小值问题 对于求最小值问题，适应度函数f ( x ) 和目标函数f ( x ) 有如下关系： f ( x ) = o d - f ( x ) ( 3 2 ) 其中，国可以取目标函数可能存在的最大值。 在实际应用中，通常我们需要对适应度函数作一些调整，因为这样可以抑制 早熟收敛现象【2 9 ，3 0 1 。 3 2 3 选择算子 对群体中的个体进行优胜劣汰的操作，遗传算法是通过选择算子来进行的： 适应度较高的那些个体被选入下一代群体中的可能性较大，而一些适应度较低 的个体被选入下一代群体中的可能性则较小。 常用的选择方法有【3 1 1 ： ( 1 ) 轮盘赌法 设群体的大小为m ，个体么，的适应度值为( 彳，) ，则个体彳，被选择的概率 p ( 彳，) 为： p ( 4 ) ：善生 ( 3 - 3 ) 厂( 4 ) j = l ( 2 ) 竞争法 在群体中随机挑选k 个个体，将适应度值最大的个体保存到下一代群体中。 ( 3 ) 最佳个体保存法 将群体中适应度最高的个体直接复制到下一代。 1 4 武汉理工人学硕士学位论文 3 2 4 交叉算子 交叉就是把两个父本的一部分基因进行替换与重组，从而生成新的个体的操 作。 交叉是遗传算法获取新优良个体的非常重要的手段，它使得遗传算法的搜索 能力得到了很大的提高。 在配对库中按一定的交叉概率以随机选取两个个体进行的操作称为交叉操 作。 常用的交叉算子有以下几种： ( 1 ) 单点交叉【3 2 1 随机选取某个基因位，从此位开始交换两父本后面的序列，产生相应的后代， 示例如下： 父代1 - 口1 口2 口3 口4l 口5 瓯口7 口8 单点交叉。子代hq 口2 口3 口4i 尼尾历展 父代2 ：p , p ：屈屈l 肛p 6 p 7 p 8。子代2 - 届2 色。l 口5 口s 口，口l 交叉点 ( 2 ) 两点交叉【3 3 】 交换父本两个基因位间的部分，相应地产生两个后代，示例如下： 父代h 口l 口2 口3 p 4 口s i 口7 两点交叉、子代h 口l 口2 口3 l 反尾i 口6 口7 父代2 ：届殷尾i 尻压i 成岛展子代2 ：届厦屈i 口。口，i p 7 p , 交叉点l 交叉点2 ( 3 ) 均匀交叉【3 4 】 按随机产生的屏蔽字决定子代如何继承父代的相应位基因，示例如下： 父代h 口l 口2 口3 口4 口5 口6 口7 口8均匀交叉( 1 0 11 0 0 1 0 ) ，子代h 口l 殷口3 口4 成风口7 展 父代2 ：届殷尼成，成届风 。子代2 ：p , a ：历屈吼岛口。 3 2 5 变异算子 变异就是按一定的变异概率p 。随机改变群体中个体的某些基因的值。虽然 变异近似于随机搜索，但是它与选择算子、交叉算子相结合，就可以很好地保 证遗传算法的搜索效率。 变异操作是按照一定的变异概率p 。，随机改变个体的某些基因值。在变异 操作中，变异概率不能取得太大3 5 1 。 武汉理工大学硕十学位论文 常用的变异算子有简单变异、均匀变异、倒位变异、基于次序的变异、基于 位置的变异等。 3 2 6 遗传算法控制参数的设定 遗传算法的控制参数主要有编码串长度、群体规模、交叉概率、变异概率和 终止代数等3 4 1