（计算机系统结构专业论文）并行遗传算法在k中心数据挖掘的应用研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 数据挖掘是随着信息技术不断发展而形成的一门新学科。它帮助人们在信息 海洋中发现有用的知识和信息。数据挖掘按照其任务主要可以分为4 种：聚类、 分类、关联规则、序列模式。其中聚类是最重要的一种。在数据挖掘中，效率和 准确性一直是人们所关注的问题。为了提高数据挖掘的准确性和效率，人们将许 多的算法应用到数据挖掘当中来。这些算法包括：遗传算法，神经网络，模糊理 论，粗糙集理论等等。本论文将并行遗传算法应用到k 一中心聚类数据挖掘中，从 而来提高k 珥，心数据挖掘的效率和聚类的准确性。 遗传算法是一种解决组合优化的一种有效方法，它是基于自然选择和自然进 化的搜索算法。但大量模拟实验表明，对于中小规模的应用问题，遗传一般能够 在许可的时间范围内获得满意解。对于大规模或超大规模的求解任务，简单的串 行遗传算法则力不从心。另外，简单串行遗传算法在应用过程中一个比较突出的 问题是它容易产生早熟现象，这将严重地影响遗传算法的应用。因此，人们利用 遗传算法固有的并行特性，将并行技术与传统的遗传算法相结合，从而来提高遗 传算法的效率和减少遗传算法早熟现象的产生。k 中心方法是基于划分的聚类方 法。它在目前的聚类分析中应用很广泛。但是该算法的缺点是易陷入局部最优， 效率不高。而且中心点个数k 的确定，在一般的情况下，是依据经验来确定的， 但是这样做往往是不准确的。针对k _ 中心聚类的这些不足，将遗传算法应用到k - 中心聚类数据挖掘中，必然会使k 中心聚类的效率和准确性得以提高。本论文为 了将遗传算法应用到k 中心聚类中去，提出了相应的编码方案和适度函数以及并 行计算模型和相应的迁移策略。实验证明，用并行遗传算法来求解k 中心聚类问 题，其效率和准确性都得到了提高。 本论文用p v m 将p c 机组织在一起，构成了一个并行计算环境，所用的操作 系统为l i n u x 。并行计算时所选用的模型为粗粒度的主从模型。在计算过程中，将 初始个体分别分配得各台s l a v e 机器上，然后s l a v e 机就开始计算，在s l a v e 机计算 到一定的时间以后，依据一定的迁移策略，向m a s t e r 迁移个体，然后再从m a s t e r 机上取回其它机器的个体继续运算，直到满足中止条件为止。 晟后，对实验得到的数据进行了比较，分析，并得出了相应的加速比。 关键n - 并行遗传算法，聚类，k - 中心聚类，p v m ，并行计算 重壅查堂堡圭兰垡堡苎 墼i ! ! l a b s t r a c t d a t am i n i n gh a sf o u ri m p o r t a n tt a s k s ：c l u s t e r i n g ，c l a s s f i c a f i o n ，a s s o c i a t i o nr u l e ， s e q u e n c e p a t t e m a n do f a l lt h e s et a s k sc l u s t e r i n gi st h em o s ti m p o r t a n to n e ，e f f i c i e n c y a n dv e r a c i t ya r ec a r e di nd a t am i n i n g ，t oi n c r e a s et h ee f f i c i e n c ya n dv e r a c i t y , a l o to f a l g o r i t h m sa r eu s e ds u c ha sn e u r a ln e t w o r k s ，f u z z y t h e o r y , r o u g hs e tt h e o r ya n ds o o n ，i nt h i sp a p e r ，p a r a l l e lg e n e t i ca l g o r i t h m i sa p p l i e dt oe n h a n c et h ee f f i c i e n c ya n d v e r a c i t yo f k - m e d i a n s d a t a m i i l i n ga l g o r i t h m g a ( g e n e t i ca l g o r i t h m ) i sa ne f f e c t i v ea p p r o a c h t os o l v ec o m b i n a t i o n o p t i m i z a t i o n p r o b l e m s i t sas e a r c h i n ga l g o r i t h mb a s e do nn a t u r a ls e l e c t i o na n de v o l u t i o n m a n y s i m u l a t i o ne x p e r i m e n t si n d i c a t et h a tg ac a no f t e ng e n e r a t es a t i s f a c t o r ys o l u t i o nf o r m i d d l eo rs m a l l s c a l ea p p l i c a t i o n sw i t h i np e r m i s s i v et i m e b u tt ol a r g eo rs u p e r - l a r g e s c a l et a s k st h e s i m p l es e r i a lg a t a k e sl e s se f f e c t a no u t s t a n d i n gp r o b l e mo f s i m p l eg a t h a tw i l lh i n d e ri tf r o mb e i n ga p p l i e di s i t s p r o m a t u r i t y i n a p p l i c a t i o np r o c e s s t h e r e f o r e ，p a r a l l e lt e c h n o l o g y a n dt r a d i t i o n a lg aa r ec o m b i n e dt o i m p r o v eg a s e f f i c i e n c ya n d r e d u c et h ep r e - m a t u r i t yb yu t i l i z i n gt h ei n h e r e n tp a r a l l e lc h a r a c t e r i s t i co f g a k m e d i a n si sac l u s t e r i n ga l g o r i t h mb a s e do np a r t i t i o nw h i c hi sw i l d l yu s e di n c u r r e n tc l u s t e r i n ga n a l y z i n g t h es h o r t c o m i n go fk - m e d i a n si st h a ti tw i l le a s i l yg e ti n l o c a lo p t i m i z a t i o n ，h e n c el o we f f i c i e n c y t h ea m o u n tko fm e d i a np o i n ti su s u a l l y d e t e r m i n e d a c c o r d i n g t o e x p e r i e n c e ，t h u s n o te x a c t a i m i n ga tt h e s ed e f i c i e n c i e s ， a p p l y i n g g at ok - m e d i a n s c l u s t e r i n g d a t a m i n i n g w i l l n e c e s s a r i l y e n h a n c et h e e f f i c i e n c ya n dv e r a c i t yo f k m e d i a n sc l u s t e r i n g i no r d e rt oa p p l yg at ok m e d i a n s ， c o r r e s p o n d i n gc o d i n gs c h e m e ，f l m e s sf u n c t i o na n dp a r a l l e lc o m p u t i n g m o d e la sw e l la s r e l e v a n tm i g r a t i o n p o l i c y a r e p u tf o r w a r d i nt h i sa r t i c l e t h ee x p e r i m e n tt e s t i f i e st h a tt h e e f f i c i e n c y a n dv e r a c i t ya r ei m p r o v e db yu s i n gp a r a l l e lg at os o l v ek m e d i a n s c l u s t e r i n gp r o b l e m s p v mi su s e dt oo r g a n i z es o m ep c s t o g e t h e ra n d c o n s t i t u t et h e p a r a l l e lc o m p u t i n g e n v i r o n m e n to nl i n u x w eu s e dm a s t e r s l a v em o d e lo fc o a r s eg r a i na st h ep a r a l l e l c o m p u t i n gm o d e ld u r i n gc o m p u t i n g t h ew h o l ec o m p u t i n gp r o c e s si s d e s c r i b e da s f o l l o w i n g ： a tf i r s tt h em a s t e rm a c h i n es e n dt h ei n d i v i d u a l st oe v e r ys l a v em a c h i n e ，t h e ns l a v e m a c h i n e sb e ：g i nc o m p u t i n g ，a f t e rt h es l a v em a c h i n e sf i n i s hc o m p u t i n ga ti n t e r v a l s ，t h e y w i l lm i g r a t ei n d i v i d u a l st ot h em a s t e rm a c h i n e b ys o l n em i g r a t o r yp o l i c y a tt h es a l t l e 重庆大学硕士学位论文英文摘要 t i m e ，o n es l a v em a c h i n ew i l lc a r r yb a c ka n o t h e rs l a v em a c h i n e si n d i v i d u a lw h i c hh a s a l s os e n dt ot h em a s t e rm a c h i n ea n dc o n t i n u ec o m p u t i n g w h e nh a l t i n gc o n d i t i o ni s s a t i s f i e d ，s l a v em a c h i n e w i l ls t o pt oc o m p u t e a tl a s t ，t h ea u t h o ra n a l y s et h ed a t ao f e x p e r i m e n ta n dc o m p a r et os i m p l eg e n e t i c a l g o r i t h m a n dg e t s p e e d u p o f c o m p u t i n g k e y w o r d s ：p a r a l l e lg e n e t i ca l g o r i t h m ，c l u s t e r i n g ，k - m e d i a n ，p v m ，p a r a l l e l c o m p u t i n g 【 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 论文的研究背景及选题的意义 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，成千上 万的数据库被用于商业管理、政府办公、科学研究和工程开发等等，并且这一势 头仍将持续发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆炸的 时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所 淹没，从中及时发现有用的知识，提高信息利用率呢? 只有使数据真正成为一个公 司的资源，并且充分利用它为公司自身的业务决策和战略发展服务才行，否则大 量的数据可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥 饿于知识”的挑战，数据挖掘和知识发现( d m x d ) 技术应运而生，并得以蓬勃发展， 越来越显示出其强大的生命力。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程。还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、 数据分析、数据融台( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是形成 知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系数据库 中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络 上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的：可以是演绎 的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、 过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门很广义的交叉 学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视 化、并行计算等方面的学者和工程技术人员。 数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单 检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合 和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的 数据对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新的电话 收费和管理办法，制定既有利于公司又有利于客户的优惠政策。这样一来，就把 人们对数据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决 策支持。这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这里所 说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自 然科学定理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对 重庆大学硕士学位论文 1 绪论 的，是有特定前提和约束条件、面向特定领域的。 从挖掘的任务可以把数据挖掘分为：聚类、分类发现、和关联规则等三大类。 聚类是把一组个体按照相似性归成若干类别，即”物以类聚”。它的目的是使 得属于同一类别的个体之间的距离尽可能的小，而不同类别的个体间的距离尽可 能的大。在目前聚类算法的研究中，把聚类方法分成了如下的几类：( 1 ) 划分方法 ( 2 ) 层次的方法( 3 ) 基于密度的方法( 4 ) 基于网格的方法( 5 ) 基于模型的方法。在聚类 数据挖掘中，所面临的最大问题就是效率不高与准确性低。 基于划分的聚类方法是最简单、最常用的一种方法。它是在给定n 个对象的 条件下，将这i 1 个对象划分成n 个类，使得各人类之间的相似度很低，类问的相 似度很高。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实 际上，绝大多数应用采用以下两种方法：( 1 ) k - m e a n s 算法，( 2 ) k 中心算法。当给 定的数据中存在噪音和孤立点时，k 中心算法比k - m e a n s 算法更加健壮。但是对 于k 一中心算法来说，当对象个数n 和中心点个数k 都较大时，计算代价是相当高。 遗传算法是基于生物进化的概念设计了一系列过程来达到优化的目的【4 。这 些过程包括：基因组合、交叉、变异、自然选择。在这些过程中，通过优胜劣汰” 的原则来淘汰掉解较差的基因，使得解朝着好的方向发展。遗传算法从一组初始 可行解出发在不需要除目标函数外的其它信息的条件下实现对可行域的全局高效 搜索并以概率1 收敛到全局最优解，这种良好的特性使遗传算法成为组合优化和 函数优化的有利工具，并成为计算智能领域的研究热点【4 ”。 为了提高数据挖掘研究率和准确性，许多研究人员将遗传算法运用到数据挖 掘中去。比如：应用到基于k i t l e a r l s 的聚类算法中【柏1 ，应用到关联规则中【4 6 【4 ”， 并出得了一些成果。但是，它也有些缺点，如：( 1 ) 未成熟收敛，( 2 ) 局部搜索能 力弱，( 3 ) 对个体编码在有些实际问题中很难，( 4 ) 对适度函数的确定难度较大等等。 因此对遗传算法进行了很多的改进，比如：( 1 ) 用并行化的思想，( 2 ) j j l ) k 其它的算 法( 如模拟退火) 等等。本论文将遗传算法应用于k 中心聚类，从而来提高k - 中心聚 类的效率和准确性，并在应用的过程中，提出了新的编码方案和新的适度函数。为 了防止在做遗传操作的过程中出现未成熟收敛，本论文采用了并行遗传算法。针 对该并行遗传算法，提出了一种新并行模型。因此，本课题具有实用价值和理论 意义。 1 2 国内外现状综述 遗传算法是种基于生物自然选择与遗传机理的随机搜索算法。其基本思想 是基于d a r w i n 的进化论和m e n d e l 的遗传学说。该算法由密执安大学教授 h o l l a n d 及其学生于1 9 7 5 年创建。与传统搜索算法不同，遗传算法从一组随机产 2 重庆大学硕士学位论文 l 绪论 生的初始解，称为种群( p o p u l a t i o n ) ，开始搜索过程。种群中的每个个体是问题的 一个解，称为染色体( c h r o m o s o m e ) 。染色体是一串符号，例如一个二进制字符串。 这些染色体在后续迭代中不断进化，称为遗传。在每一代中用适应度( f i t n e s s ) 来衡 量染色体的好坏，生成下一代染色体，称为后代( o f f s p r i n g ) 。后代是由前一代染 色体通过交叉( c r o s s o v e r ) 或变异( m u t a t i o n ) 运算形成。根据适应度大小选择部分后 代，淘汰部分后代，从而保持种群大小是常数。适应度高的染色体被选中的概率 高。这样，经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最 优解或次优解。遗传算法在机器学习、过程控制、经济预测、工程优化等方面取 得的成功，已引起了数学、物理学、化学、生物学、计算机科学、社会学、经济 学以及工程应用等领域专家的极大兴趣。 遗传算法的主要特点是【3 9 1 ： ( 1 ) 对变量的二进制编码进行操作，而不是对变量本身操作。表示变量的每 一位二进制量0 或1 相当于一个基因，经编码的位串相当于染色体。 ( 2 ) 对神群进行的优化操作，实现了全局并行操作，即用较少的串操作可实现 较大区域的搜索，称这种特性为隐含并行性。 ( 3 ) g a 中使用的算子是随机的，如交叉、变异和繁殖等算子不受确定性规则 的控制；但这种搜索也不是盲目的，而是向全局最优解方向前进。 ( 4 ) 直接使用适值函数进行适值计算，而不需要求优化函数的导数，使得一些 不可求导的优化函数也可用g a 优化，这显示了g a 适应性强的特点。 ( 5 ) 同时搜索解空间的多个点，从而使之收敛于全局最优解，而不至于陷入局 部最优解，这说明g a 具有较强的鲁棒性。 除以上两个方面外，还出现一些其它高级算子，如倒位算子、本地算子、显 性算子、隔离算子、移位算子、迁居算子、近亲繁殖限制、单亲遗传和基于小生 境的遗传算法等。 遗传算法固有的并行性和大规模并行机的快速发展，促使许多研究者开始研 究遗传算法的并行化问题，研制数量更加接近自然物种的群体将成为可能。遗传 算法与并行计算机的结合，大大促使了并行遗传算法的发展。文献 3 5 3 6 4 4 3 4 】 3 3 【将并行遗传算法分别应用到不同的领域，并取得了较好的效 果。在并行遗传算法中，最重要的两个问题是：并行模型和迁移策略。这两个因 素将直接影响到遗传算法的效果。并行模型的类型很多，比如：文献 3 1 给出超 立方体模型，文献 3 2 提到的三角锥模型，文献 4 4 】的网格模型等等。 同时在数据挖掘中，面临的一个主要问题就是性能问题和效率问题。也就是 说，对于大量的信息，数据挖掘算法的运行时间必须是可以预计的和可以接受的。 因此，人们自然就想到把遗传算法用于数据挖掘中，来提高数据挖掘的效率。比 重庆大学硕士学位论文 1 绪论 如说：在文献【4 6 】中，将遗传算法应用到基于关联规则的数据挖掘中，在文献 3 7 3 8 中，将遗传算法应用到基于分类预钡4 的数据挖掘中，在文献 4 9 1 中，作者将遗传 算法与多维数据挖掘相结合。但是到目前为此，将并行遗传算法应用于聚类数据 挖掘的研究还很少，文献 1 是一篇将并行遗传算法应用到聚类数据挖掘的经典文 章，这篇文章主要观点是将并行遗传算法同k - - m e a n s 算法结合，来提高 k - - m e a n s 算法的效率。在这篇文章中，有两个地方比较有新意： ( 1 ) 作者把k - - m e a n s 算法求解过程看作是一个“标记分配问题( l a b e l a s s i g n m e n tp r o b l e m ) ，也类似于图论中的对点着色问题。也就是说把要分成的每 个类看成是一种标识( 或颜色) ，每一个标识用一个二进制串表示，例如k = 1 0 ，这 时就可以用 k - r - 1 0 9 2 1 0 n - - 4 ( 注：对1 0 求对数并向上取整) 位二进制位来表示。比如说1 0 1 1 就可表示一个聚类中心点，那么属于这个中心点的所有其它点可以表这个串来表 示。这样以此类推，如果需要聚类的点有n ，则整个问题就可以n k 个b i t 来表示。 如果n 较大且需要分的类比较多时，这实际上是一个很庞大的数字串。 ( 2 ) 遗传算法的并行模型：作者采用的是粗粒度模型。也即是根据处理机的个 数p 将解空间分成p 个组，然后将每个组交到一个处理机上去串行地执行k - m e a n s 算法，在程序运行的过程中，各个处理机之间不进行数据交换，当某个处理机p 完成计算后，就交给主处理机保存结果，等到最后一个处理机计算完成之后，主 处理机( m a s t e r ) 再将得到的所有结果作串行的k m e a n s 算法，从而得到需要的结 果。 并行遗传算法在求解优化问题上表现出了良好的性能，因此，它被得到了日 益广泛的研究和应用，尤其是在并行模型和迁移策略上。k - 中心聚类数据挖掘是 数据挖掘的一个非常重要的分支，在各个领域得到了广泛的应用。比如：入侵检 测、图形处理、商业数据分析等等。但是k 中心聚类数据挖掘的一个重要的缺点 就是效率低。因此，将并行遗传算法应用到k - 中心聚类数据挖掘，必然会提高它的 效率。 1 3 论文研究的内容及组织 本论文研究的内容有以下几个方面： ( 1 ) 对k - 中心问题进行编码，使遗传算法能够对其求解，它将直接影响聚类的效 率和结果。本论文采用了一种新的编码方案。该编码采用的是二进制编码，其结 构简单，便于进行交配、变异等操作。同时在h o l l a n d 在建立模式定理时已经证明 了遗传算法采用二进制编码时，效率最高。 ( 2 ) 确定新的适度函数。适度函数是用来判定每个个体的好坏，然后根据某种 4 重庆大学硕士学位论文 1 绪论 策略，使好的个体得以保留，差的个体被淘汰。因此，适度函数对于选择哪两个 个体进行交配很重要，本论文提出了一种新适度函数： f ( 足) = 厂弋( 其中k 为聚类中心 西( k ) l d i s t ( p i ) i i = 1 数，d i s t ( p i ) 表示第i 个簇中所有非中心点到中心点的距离和，o ( k ) 为惩罚函数) 。 ( 3 ) 确定了并行遗传算法的并行模型和相应的迁移策略。并行模型和相应的迁 移策略将会影响并行遗传算法的效率和求解效果，在并行遗传算法中其模型主要 有三种：主从模型( m a s t e r c l i e n t ) 、细粒度模型、粗粒度模型。主从模型是将遗传操 作放在主处理机上而将适应度的值并行地交给从处理机执行，当从处理机完成计算 后就交给主处理机，这时主处理机再执行串行的遗传算法，这样易造成瓶颈和大的 通信延迟，同时还造成负载不平衡【3 】，使得效率不高。细粒度模型一般只运行于大 规模的s i m d 并行计算机1 3 。粗粒度模型是应用得最广的一种模型。由于通信开销 较小，可获得接近线性的加速比，而且非常适合运行在通信带宽较低的集群系统 中州，所以粗粒度模型已被成功地用于解决许多的难题，并取得了很好的效果。比 如货郎担问题1 2 】等等，并行遗传算法的计算模型有很多。 ( 4 ) 搭建并行环境，采用不同的数据对算法进行测试。改变结点机的数目，得 到不同的程序的执行时间，比较聚类的效果，计算出并行遗传算法实际执行的加 速比。从运行的结果对并行遗传进行评价。 ( 5 ) 用本论文提到的算法和并行模型对医药公司的销售数据进行聚类，并得给 出了聚类的结果。 重庆大学硕士学位论文 2 数据挖掘与遗传算法技术 2 数据挖掘与遗传算法技术 2 1 数据挖掘技术简介 2 1 1 数据挖掘的定义 i t 技术的迅速发展，使数据库的规模不断扩大产生了巨大的数据洪流。为给决 策者提供一个统一的全局视角，在许多领域建立了数据仓库。大量的数据往往使 人们无法辨别隐藏在数据中的、能对决策提供支持的信息，而传统的查询、报表 工具无法满足发掘这些信息的需求，因此需要一种新的数据分析技术来处理大量 数据，从中抽取有价值的潜在信息，数据挖掘技术由此应运而生。 数据挖掘( d a t a m i n i n g ) 。 从技术基础的角度来看：知识发现的技术及算法的发展，使得数据挖掘工具 的功能和实用性得到提高j o h nh o p f i e l d 在神经元网络方面。b r i e m a n 、f r i e d m a n o l s h e n 和s t o n e 等人在决策树方面以及h o l l a n d 和g o l d b e r g i s l 等人在遗传算法方面 所进行的开创性工作大大推进了数据挖掘技术的实际应用。目前在国外已有许多 领域成功采用了数据挖掘这一工具辅助决策，如市场营销、零售业、金融、医疗 保险、政府部门及科学研究等，已充分显示了这一信息技术的优越性，这也促进 了应用和研究的进一步发展。 2 1 2 数据挖掘的任务 数据挖掘的任务常见的有4 1 t o t 5 类型： 分类：用于预测事件所属的类别。其中样本数据中包含标识样本事件所属类别 的数据项，类别是已知的，由数据挖掘根据样本数据构建对这些类别的模式的描 述，再利用所发现的模式，参照新的数据的特征变量，将其映射入已知类别中。 如在医疗应用中，可根据患者的各种特征进行疾病诊断等。 聚类：用于描述和发现数据库中以前未知的数据类别。其中样本数据中不包 含类别变量，数据挖掘将具有共同趋势和模式的数据元组聚集为一类，使类中各 元组相似程度最高，类间差异最大。常用于市场细分。可根据已有顾客的数据， 利用聚类技术将市场按顾客的消费模式的相似性分为若干细分市场，以进行有针 对性的市场营销。 关联：用于发现给定事件或纪录中经常一起发生的项目，由此推断事件间潜 在的关联，识别有可能重复发生的模式。关联分析的典型例子是市场篮子分析， 描述顾客的购买行为。如尿布与啤酒的故事就属于关联分析，可帮助零售商决定 商品的摆放和捆绑销售策略。 序列一模式：与关联分析类似，只是扩展为一段时间的项目集间的关系，常把 6 重庆大学硕士学位论文 2 数据挖掘与遗传算法技术 序列模式看作由时间变量连接起来的关联。序列分析可分析长时期的相关纪录， 发现经常发生的模式。 2 1 3 数据挖掘的常用方法 数据挖掘的技术基础是人工智能，它利用了人工智能中一些已经成熟的算 法和技术，例如：遗传算法( g e n e t i ca l g o r i t h m s ) 、人工神经网络( n e u r a ln e t w o r k ) 、 决策树( d e c i s i o nt r e e s ) 、邻近搜索方法( n e a r e s tn e i g h b o rm e t h o d ) 、规则推薹l ( r u l e l n d u c t i o n ) 、模糊逻辑( f u z z yl o g i c ) 等，但问题的复杂度和难度却比人工智能降低 了许多，下面是数据挖掘技术中的常用算法： ( 1 ) 遗传算法。 遗传算法是模拟生物进化过程的算法，由三个基本算子组成【5 0 】： 繁殖( 选择) ，即从一个旧群体( 父代) 选出一个生命力强的个体，产生新的 种群( 后代1 的过程。 交叉( 重组) ，即选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成新 个体的过程。 变异( 突变) ，即对某些个体的某些基因进行变异( 0 变1 、1 变0 ) ，形成新个 体的过程。 这种遗传算法可起到优良后代的作用。这些后代需满足适应值，经过若干代 的遗传，将得到满足要求的后代( 即问题的解) 。遗传算法已在优化计算和分类机 器学习方面发挥了显著作用。 ( 2 ) 人工神经网络。人工神经元网络方法模拟人脑神经元结构，以m p 模型 和h e b b 学习规则为基础，一般分为三种网络模型【站l ： 前馈型网络。一般前馈型网络无反馈的特征，这类网络能够串联地连接起 来以建立多层网络，在这样的网络中，一层的输出是下一层的输入。输入输出节 点可与外界相联，可直接受外界环境的影响，所以可称为可见层，而其中层间与 外间无直接联系，所以称为隐含层。节点有输入、计算单元和输出三类。每一计 算单元可以有任意个输入但只有个输出，其输出可以耦合到任意多个其他节点 的输入。两层的前馈网络只有单层计算单元，这实际上就是网络最简单的形式 感知器。前馈型网络以感知器、反向传播模型、函数型网络为代表，可用于预测、 模式识别等方面。 反馈型网络。反馈型网络所有节点都是计算单元，同时既可接受输入，又 可向外界输出。通过网络神经元状态的变迁而最终稳定于某一状态，从而得到联 想存储或者神经计算的结果。它以离散型h o p f i e l d 神经元网络和连续模型为代表， 分别用于联想记忆和优化计算。 自组织网络。它以a r t 模型、k o h o l o n 模型为代表，用于聚类分析等方 重鏖盔堂堡主堂篁堡垄 ! 茎塑丝塑兰望堡簦鎏垫查 面。 人工神经网络的知识体现在网络连接的权值上，是一个分布式矩阵结构，起 学习体现在网络权值的逐步计算上。 ( 3 ) 决策树。决策树是通过一系列规则对数据进行分类的过程。采用决策树， 可将数据规则可视化，也不需要长时间的构造过程，输出结果容易理解，精度较 高，因此决策树在知识发现系统中应用较广。然而，采用决策树方法也有其缺点。 决策树方法很难基于多个变量组合发现规则。不同决策树分支之间的分裂也不平 滑。 ( 4 ) 公式发现。即在工程和科学数据库( 由实验数据组成) 中对若干数据项( 变 量1 进行一定的数学运算，求得相应的数学公式。 ( 5 ) 统计分析方法。利用统计学中的数学原理对数据库进行分析，有如下方 法【5 1 】 5 2 】： 相关分析和回归分析。相关分析是用相关技术来度量变量间的相关程度； 回归分析是用数学方程来表示变量间的数量关系，方法有线性回归和非线性回归。 差异分析。从样本统计量的值得出的差异来确定总体参数之闻是否存在差 异( 假设检验) 。典型的方法为方差分析，它是通过分析实验数据中不同来源的变 异对总体变异的贡献大小，从而确定实验中的可控因素( 自变量) 是否对实验结果 ( 因变量) 有重要的影响。 因子分析。它是用较少的综合变量来表达多个观察变量，根据相关性大小 把变量分组，使得同组变量之间相关性较高，不同变量间的相关较低。 ( 6 ) 其他技术。 模糊论方法。模糊论在数据挖掘的主要应用是聚类分析，称为模糊聚类。 传统的聚类分析是一种硬划分，也就是说类的划分的界限是分明的，而实际上大 多数对象并没有严格的属性，它们的类属和性态存在着中介性，因此适合于软划 分。模糊集理论的提出为这种划分提供了有力的工具。模糊聚类不但可以从原始 数据中直接提取特征，还可以对特征进行优选和降维操作。模糊聚类既可以提供 最近邻原型分类器，还可以用来进行特征空间划分和模糊规则提取【6 1 。 粗糙集技术。粗糙集理论作为一种全新的数学概念，为处理具有不完整、 不一致及不确定性特征的信息提供了新的有效工具。它由波兰学者p a w l a kz 在1 9 8 2 年首次提出，1 9 9 1 年，p a w l a k 教授出版了专著，全面系统地阐述了r s 理论【l ”。目前有关粗糙集的研究日益受到国内外学术界的重视。在数据挖掘领 域，粗糙集最初主要用于分类，数据的归约，时间序列的数据挖掘。 可视化技术。可视化数据分析技术拓宽了传统的图表功能，使用户对数据 的剖析更清楚。例如把数据库中多维的数据变成多种图形，这对揭示数据中的状 重庆大学硕士学位论文 2 数据挖掘与遗传算法技术 况、内在本质及其规律性都起到了很强的作用。 总的来说，应该根据不同的问题环境和应用层面来选择合适的方法，并且灵 活应用来解决数据挖掘中遇到的难题。 2 1 4 数据挖掘的应用 目前，数据挖掘的应用领域包括以下八个方面，而每个领域又都有自己的应 用领域和应用背景【1 2 1 ”1 。 ( 1 ) 金融。金融事务需要收集和处理大量的数据，通过对这些数据进行分析， 发现其数据模式及特征，然后可能发现某个客户、消费群体或组织的金融和商业 兴趣，也可观察金融市场的变化趋势。数据挖掘在金融领域的应用广泛，包括数 据清理、金融市场分析预测、用户分类、信用评估等。 ( 2 1 医疗保健。医疗保健业有大量的数据需要处理，但这个行业的数据由不同的 信息管理系统管理，数据以不同的格式保存，从总体看，数据是无组织的。在这 个行业中，数据挖掘的关键任务是进行数据清理、预测医疗保健的费用。例如g t e 实验室开发的k e f i r ，它能进行多维分析，用于分析g t e 的医疗保健数据，对 比数据和预测数据，在定量范围内解释偏差，生成超文本报表。2 】。 ( 3 ) 市场业。市场业应用数据挖掘技术进行市场定位、消费者分析、辅助制 定市场营销策略等。 ( 4 ) 零售业。零售业是最早运用数据挖掘技术的行业。目前，主要运用于销 售预测、库存需求、零售点的选择、价格分析等。 ( 5 ) 制造业。制造业应用数据挖掘技术进行零部件故障诊断、资源优化、生 产过程分析等。 ( 6 ) 司法。数据挖掘也可应用于案件调查、诈骗检测、犯罪行为分析等方面， 这些都可以给司法工作带来巨大的利益。 ( 7 ) 工程和科学。在信息量极为庞大的天文、气象、生物技术等领域中，所 获得的大量实验和观察数据用靠传统的数据分析工具难以应付，因此对功能强大 的智能化自动分析工具要求迫切，这种需求推动了d m 技术在科学研究领域的应 用发展，目前已获得了一些重要的研究成果，例如：j e t p r o p u l s i o n 实验室利用决 策树方法对上百万天体数据进行分析。帮助天文学家发现了1 6 个星的星体，效果 要比人工更快，更准确。 ( 8 ) 保险业。对受险人员的分类将有助于确定适当的保险金额度。通过数据 挖掘可以得到对不同行业、不同年龄段、不同社会层次的人，他们的险金应该如 何确定。另外，还可进行险种关联分析，分析购买了某种保险的人是否又同时购 买另一种保险，也可预测什么样的顾客将会购买新险种。 9 重庆大学硕士学位论文2 数据挖掘与遗传算法技术 2 2 遗传算法与k 一中心聚类 2 2 1 遗传算法的定义 遗传算法( g e n e t i ca l g o r i t h m g a ) 是一类借鉴生物界自然选择和自然遗传机 制的随机化搜索算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程模型， 它是由美国密歇根大学h o l l a n d 等人在七十年代首次提出并建立了它的数学框 架。该方法一经提出便受到了关注，到8 0 年代中期其研究开始进入高潮。g o l d b e r g 和m i c h a l e w i c z 进行了大量的研究工作，并成功地将它应用到各种领域的优化问 题。 生命科学与工程科学的相互交叉、相互渗透和相互促进是近代科学技术发展 的一个显著特点，而遗传算法的蓬勃发展正体现了科学发展的这一特征和趋势， 遗传算法的早期应用主要围绕组合优化问题求解，如煤气管道的最优控制，旅行 商( t s p ) 问题等，近年来迅速扩展到机器学习、设计规划、神经网络优化、核反应 堆控制、喷气发动机设计、通信网络设计、人工生命等领域，显示了遗传算法应 用的巨大潜力。遗传算法是多学科相互结合与渗透的产物，它已发展成一种自组 织、自适应的综合技术，广泛应用于计算机科学、工程技术、管理科学和社会科 学等领域。目前，遗传算法作为一种基于统计理论的优化和搜索技术，在计算机 视觉领域中的应用也正日益受到重视，如：特征提取、图像匹配、图像分割中的 应用。 2 2 2 自然进化与遗传算法 遗传算法是一种基于自然选择原理和自然遗传机制的寻优搜索算法，模拟自 然界中的生命进化机制，在人工系统中实现特定参数目标的优化。 遗传算法中所用到的进化理论的基本特性为： ( 1 ) 生物进化是一个对于染色体、而不是对生物体本身进行操作的过程 ( 2 ) 自然选择的过程联系着染色体和它们的各基因串的性能，各个子串性能越 好的染色体越容易生存下来 ( 3 ) 有性生殖的过程保证其后代的基因混合、基因重组和基因突变，以产生适 应力更强的后代 ( 4 ) 生物进化无记忆。有关产生生物体的信息包含在生物体所携带的染色体的 集合以及染色体编码的结构之中，这些生物体会很好地适应它们的环境。 遗传算法是利用某种编码技术来作用于被称为染色体的二进制数串，其基本 思想是模拟由这些串组成的群体的进化过程。遗传算法通过有组织，但又是随机 地信息交换来重新组合那些适应性好的串，在每一代中，利用上一代串结构中适 应性好的位和段来生成一个新的串的群体；另外，偶尔也要在串结构中尝试用新 的位和段来替代原来的部分。遗传算法是一类随机算法，但它不是简单的随机搜 1 0 重庆大学硕士学位论文 2 数据挖掘与遗传算法技术 索，而是有效地利用已有的信息来搜寻。它是利用随机化技术来指导对一个被编 码空间进行高效搜索的方法。与自然界相似，遗传算法对求解问题的本身一无所 知，它所需要的仅是对算法所产生的每个染色体进行评价，并通过适度值来选择 染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。遗传算法 利用简单的编码技术和繁殖机制来表现复杂的现象，从而解决非常困难的问题。 特别是由于它不受搜索空间的限制性假设的约束，不必要求诸如连续性、导数存 在和单峰等假设，以及其固有的并行性，遗传算法目前已经在最优化、机器学习 和并行处理等领域得到了越来越广泛的应用。 2 2 _ 3 遗传算法的描述 在自然界的演化过程中，生物体通过遗传、变异来适应外界环境，一代又一 代地优胜劣汰，发展进化。遗传则模拟了上述进化现象。它把搜索空间( 欲求解问 题的解空间) 映射为遗传空间，即把每一个可能的解编码为一个向量f 二进制或十 进制数字串) ，称为一个染色体，向量的每一个元素称为基因。所有染色体组成群 体，并按预定的目标函数( 或某种评价指标) 对每个染色体进行评价，根据其结果 给出一个适应度的值。算法开始时先随机地产生一些染色体( 欲求问题的候选解) ， 计算其适应度，根据适应度对各染色体进行选择复制、交叉、变异等遗传操作， 剔除适应度低( 性能不佳) 的染色体，留下适应度高( 性能优良) 的染色体，从而得到 新的群体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优良形态， 因而明显优于上一代。遗传算法就这样反复迭代，向着更优解的方向进化，直至 满足某种预定的优化指标。 在应用遗传算法求解问题时，主要步骤如下图： 重庆大学硕士学位论文 2 数据挖掘与遗传算法技术 对实际问题进行编码，使之能用于遣传算法 确定日标函数，用于计算个体的适度值。 初始种群1 使用目标函数计算初始群体中所有个体的适度值。 是l - - 匪圈 臣固 臣圈 产生新的个体 f 图2 1 f i g 2 1 2 2 3 1 编码 编码是把具体问题的搜索空间中每个可能的点表示为确定长度的特征串。这 是用遗传算法求解具体问题的第一步。一般来讲，由于遗传算法的鲁棒性，它对 编码的要求并不苛亥8 。但是编码策略与交叉策略是相互依存的。恰当的设置编码 对于充分发挥遗传算法的功能是十分