（计算机软件与理论专业论文）基于遗传算法的聚类方法研究.pdf

摘要 摘要 近年来数据挖掘引起了信息产业界的广泛关注，其主要原因是存在大量的可用数据， 并且迫切需要将这些数据转换成有用的信息和知识。通过数据挖掘，可以将知识发现的研 究成果应用于实际数据处理中，为科学决策提供支持。聚类分析是数据挖掘的一项基本任 务，是一个无监督的学习过程，聚类的目标是在没有任何先验知识的前提下，将数据聚集 成不同的簇，使得相同簇中的元素尽可能相似，不同簇中的元素差别尽可能大。通过聚类， 人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的 相互关系。 在聚类分析中，k - m e a n s 算法可以说是应用较为广泛的一种算法，但它的一个致命弱 点是对初始化非常敏感而容易陷入局部极小值，而遗传算法是一种通过模拟自然进化过程 搜索最优解的方法，其显著特点是隐含并行性和对全局信息的有效利用能力，因此，借鉴 k - m e a n s 算法，用遗传算法来解决聚类问题，既能发挥遗传算法的全局寻优能力，又能兼 顾k - m e a n s 算法的局部搜索能力，从而更好地解决聚类问题。本文就是提出了新的混合遗 传算法，并以此来解决聚类问题。 本文对遗传算法和经典的聚类算法做了深刻地分析、研究，提出了一种改进的基于模 拟退火机制的多种群并行遗传算法，利用该混合遗传算法解决聚类问题，并通过实验验证 算法的有效性。主要工作包括： 1 一介绍分析了聚类算法以及遗传算法。 介绍了数据挖掘的相关概念、任务、方法，然后介绍了聚类分析的概念、常见算法以 及遗传算法的基本概念、研究现状等，并进行了相应的分析。 2 提出了一种改进的基于模拟退火机制的多种群并行遗传算法。 提出的混合遗传算法利用模拟退火遗传算法，并对其进行了改进( 采用动态调节近邻 子集大小的方式) ，再结合多种群并行遗传算法的思想，同时加入小生境技术，从而有效 地克服基本遗传算法的早熟收敛等缺陷。 3 将改进的基于模拟退火机制的多种群并行遗传算法用于聚类分析。 借鉴了k - m e a n s 算法，并采用基于聚类中心的浮点编码方式，同时考虑到聚类数目k 的值通常在事前不能很好地确定，往往根据经验来定，所以本文分别提出了固定聚类数目 k 值的聚类算法以及可以动态确定恰当的聚类数目k 值的相应算法，使得聚类算法具有更 普遍的意义。 4 测试本文提出算法的有效性。 为了测试本文提出的聚类算法的性能，本文采用两组实验数据，分别针对固定聚类数 目k 的聚类算法以及动态确定聚类数目k 的聚类算法进行实验，并与其它的聚类算法，即 k - m e a n s 算法以及基于遗传算法的聚类算法进行效果比较，实验结果显示本文算法有效地 解决了聚类问题。 由于人们面对的数据是海量的，所以要求聚类算法能够快速准确地解决实际问题。本 摘要 文提出的算法利用多种群并行遗传算法的思想，可以将较大的任务划分成若干较小的任 务，由不同的计算机来并行处理，这样就提高了算法执行的效率。并且，在每个种群中加 入模拟退火操作以及小生境技术，借助模拟退火算法具有较强的局部搜索能力，并能使搜 索过程避免陷入局部最优解，而小生境技术通过维护群体中小规模低适应度物种的生存， 保持了物种多样性，避免进化过程中出现过早收敛和陷入局部最优，从而有效地克服基本 遗传算法的缺陷，使得本文提出的算法能够更准确地进行聚类划分。 关键词：数据挖掘；聚类；遗传算法；模拟退火遗传算法；小生境技术；多种群 a b s t r a c t a b s t r a c t t h em a j o rr e a s o nt h a td a t am i n i n gh a sa t t r a c t e dag r e a td e a lo fa t t e n t i o ni nt h ei n f o r m a t i o n i n d u s t r yi nr e c e n ty e a r si sd u e t ot h ew i d ea v a i l a b i l i t yo fh l l g ea m o u n t so fd a t aa n dt h ei m m i n e n t n e e df o rt u r n i n gs u c hd a t ai n t ou s e f u li n f o r m a t i o na n dk n o w l e d g e p e o p l ec a na p p l yt h er e s e a r c h r e s u l to fk n o w l e d g ed i s c o v e r yt ot h ed a t ap r o c e s st h a tc a ns u p p o r tt h es c i e n c ed e c i s i o n c l u s t e r a n a l y s i si sab a s i ca s s i g n m e n to fd a t am i n i n ga n dak i n do fu n s u p e r v i s e dl e a r n i n g t h eg o a lo f c l u s t e r i n g i st op a r t i t i o nd a t as e ti n t os u c hc l u s t e r st h a to b j e c t sw i t h i nac l u s t e rh a v eh i g h s i m i l a r i t yi nc o m p a r i s o nt oo n ea n o t h e r , b u ta r ev e r yd i s s i m i l a rt oo b j e c t si no t h e rc l u s t e r s w i t h o u ta n yp r i o rk n o w l e d g e b yc l u s t e r i n g ，o n ec a ni d e n t i t yd e n s ea n ds p a r s er e g i o n s ，t h e r e f o r e ， d i s c o v e ro v e r a i ld i s t r i b u t i o np a t t e r n sa n di n t e r e s t i n gc o r r e l a t i o n sa m o n gd a t aa t t r i b u t e s k - m e a n sa l g o r i t h mi st h em o s tw i d e s p r e a di nc l u s t e ra n a l y s i s h o w e v e ri t sv i t a l s h o r t c o m i n gi st h es e n s i b i l i t yt oi n i t i a lv a l u e ，i ti se a s yt oi n ni n t oal o c a lo p t i m u m g e n e t i c a l g o r i t h mi sac o m p u t a t i o n a lm o d e lo ft h eh u m a ne v o l u t i o n ，w i t hi m p l i c i tp a r a l l e l i s ma n d c a p a c i t yo fu s i n ge f f e c t i v eg l o b a li n f o r m a t i o n s ou s i n gg a w i t hk - m e a n sa l g o r i t h mt os o l v e c l u s t e r i n gp r o b l e m w ew i l lg e tah y b r i da l g o r i t h mw h i c hh a sg o o dg l o b a la n dl o c a ls e a r c h c a p a b i l i t y i tc a ns o l v ec l u s t e r i n gp r o b l e me f f e c t i v e l y t h i sp a p e rp r e s e n t san e wh y b r i dg e n e t i c a l g o r i t h mt os o l v ec l u s t e r i n gp r o b l e m t h i sp a p e ra n a l y s e sa n ds t u d i e sg e n e t i ca l g o r i t h ma n dc l a s s i c a lc l u s t e r i n ga l g o r i t h m s ，a n d t h e np r e s e n t sa ni m p r o v e dm u l t i g r o u pp a r a l l e lg e n e t i ca l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n g ， a n du s e st h i sa l g o r i t h mt os o l v ec l u s t e r i n g t h ep e r f o r m a n c eo ft h ea l g o r i t h mi st e s t e d t h em a i n w o r ki n c l u d e s ： 1 i n t r o d u c i n ga n da n a l y z i n gc l u s t e r i n ga l g o r i t h m sa n dg e n e t i ca 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 eb a s i cc o n c e p t ，t a s k sa n dc o r r e l a t i v em a t u r em e t h o d so fd a t a m i n i n g ，a n dt h e ni n t r o d u c e sa n da n a l y s e sg e n e t i ca l g o r i t h ma n dt h eb a s i cc o n c e p ta n df a m i l i a r a l g o r i t h m so fc l u s t e ra n a l y s i s 2 p r e s e n t i n ga ni m p r o v e dm u l t i g r o u pp a r a l l e lg e n e t i ca l g o r i t h mb a s e do ns i m u l a t e d a n n e a l i n g t h eh y b r i dg e n e t i ca l g o r i t h mt h a t t h i sp a p e rp r e s e n t e dc o m b i n e st h ei m p r o v e ds i m u l a t e d a n n e a l i n gg e n e t i ca l g o r i t h ma n dm u l t i g r o u pp a r a l l e lg e n e t i ca l g o r i t h m ，a n dt h e na f f i l i a t e sn i c h e t e c h n i q u e t h i sa l g o r i t h mr e s t r a i n sp r e m a t u r ec o n v e r g e n c eo fs i m p l eg e n e t i ca l g o r i t h m e f f e c t i v e l y 3 t h ei m p r o v e dm u l t i g r o u pp a r a l l e lg e n e t i ca l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n gi su s e d t oc l u s t e ra n a l y s i s k - m e a n sa l g o r i t h mi sc o n s u l t e d ，a n dak i n do fc l u s t e r - c e n t e r - b a s e df l o a t i n gp o i n te n c o d i n g m o d ei su s e d m e a n w h i l e ，b e c a u s et h ep a r a m e t e rk i sh a r d l yc o n f i r m e db e f o r ee x p e r i m e n t ，t h i s i a b s t r a c t p a p e rp r e s e n t st w oc l u s t e r i n ga l g o r i t h m s ，o n ei si n v a r i a b l ep a r a m e t e rk a n dt h eo t h e ri sd y n a m i c s e l e c t i n gp r o p e rp a r a m e t e rk s oa l g o r i t h m sh a v eu n i v e r s a lm e a n i n g 4 t e s t i n gt h ep e r f o r m a n c eo ft h ea l g o r i t h r a s f o rt e s t i n gt h ep e r f o r m a n c eo ft h e s ec l u s t e r i n ga l g o r i t h m s ，t h i sp a p e ru s e st w og r o u p so f d a t at ot e s tt h et w oc l u s t e r i n ga l g o r i t h m s ，a n dc o m p a r e sw i t ht h eo t h e rc l u s t e r i n ga l g o r i t h m s ， s u c ha sk - m e a n sa l g o r i t h ma n dc l u s t e r i n ga l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m e x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h a tt h em e t h o d sc a ns o l v ec l u s t e r i n ge f f e c t i v e l y b e c a u s ep e o p l ef a c eam a s so fd a t a ，r e q u i r ec l u s t e r i n ga l g o r i t h mc a ns o l v ea c t u a lp r o b l e m s w e l la n d t r u l y t h ea l g o r i t h m so ft h i sp a p e r c a ns e p a r a t el a r g ea s s i g n m e n ti n t os m a l la s s i g n m e n t s b yt h ei d e ao fm u l t i g r o u pp a r a l l e lg e n e t i ca l g o r i t h m ，a n dt h e nt h e s es m a l la s s i g n m e n t sc a nb e p e r f o r m e dp a r a l l e l l yb yd i f f e r e n tc o m p u t e r s ，s ot h ee f f i c i e n c yo ft h ea l g o r i t h m sa r ei m p r o v e d m e a n t i m e ，a d di ns i m u l a t e da n n e a l i n ga n dn i c h et e c h n i q u ei ne v e r yp o p u l a t i o n s ，r e s t r a i n d i s a d v a n t a g e so fs i m p l eg e n e t i ca l g o r i t h ma n dc a np a r t i t i o nd a t a s e te x a c t l yb yt h el o c a l s e a r c h i n gc a p a b i l i t yo f s i m u l a t e da n n e a l i n ga n dn i c h et e c h n i q u ew h i c hm a i n t a i n st h ed i v e r s i t yo f i n d i v i d u a l si np o p u l a t i o n s k e y w o r d s ：d a t am i n i n g ；c l u s t e r i n g ；g e n e t i ca l g o r i t h m ；s i m u l a t e da n n e a l i n gg e n e t i c a l g o r i t h m ；n i c h e ；m u l t i g r o u p ； 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名 竞b 慧 导师签字 学位论文版权使用授权书 本学位论文作者完全了解堂蕉有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 查t 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：武农薏 导师签字姚 签字日期：2 0 0 年5 月f 7 日 签字日期：2 0 06 年明声 山东师范大学硕士学位论文 第一章绪论 1 1 数据挖掘产生的背景及基本概念 1 1 1 数据挖掘产生的背景 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越 多。激增的数据背后隐藏着许多重要信息，吸取隐藏在这些数据后面的有用知识并利用这 些知识的能力变得愈加重要。与日趋成熟的数据管理技术和软件工具相比，人们所依赖的 数据分析工具功能，却无法有效地为决策者提供其决策支持所需要的相关知识。因此，如 何对数据与信息快速有效地进行分析、加工、提炼以获取所需知识，就成为计算机及信息 技术领域的重要研究课题。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。数据挖掘作为一个新 兴的多学科交叉应用领域，正在各行各业的决策活动中扮演着越来越重要的角色。目前， 在很多重要的领域，数据挖掘都可以发挥积极促进的作用，尤其是在银行、电信、保险、 交通、零售等商业应用领域。数据挖掘能够帮助解决很多典型的商业问题，包括：数据库 营销、客户群体划分、背景分析、交叉销售等市场分析行为，以及客户流失性分析、客户 信用评分、欺诈发现等等。 国际上第一次关于数据挖掘与知识发现的研讨会于1 9 8 9 年8 月在美国底特律召开， k d d 词是在此学术会议上正式形成的，当时仅有数十人参加，此后发展很快。1 9 9 5 年 提升为国际学术大会( i n t e r n a t i o n a lc o n f e r e n c eo nd a t am i n i n g k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ) ，即在加拿大召开的第一届知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e k d d ) 和 数据挖掘( d a t a m i n i n g - d m ，也称数据开采) 国际学术会议。此后，“数据挖掘”开始流行， 它是“知识发现”概念的深化。 1 1 2 数据挖掘的基本概念 数据挖掘( d a t a m i n i n g ) ，也可以称为数据库中的知识发现( k d d ，k n o w l e d g e d i s c o v e r y i nd a t a b a s e ) ，是指从大量的原始数据中，提取用户感兴趣的知识的过程，这些知识是有价 值的、隐含的、事先未知的、潜在有用的。 数据挖掘的对象可以是数据库或数据仓库内容，也可以是其它数据源内容。数据挖掘 是一种决策支持过程，它主要基于人工智能、机器学习、统计学技术，高度自动化地分析 企业原有的数据，做出归纳性的推理，从中挖掘出潜在模式，预测客户的行为，帮助企业 的决策者调整市场策略以减少风险，作出正确的决策。 山东师范大学硕士学位论文 1 1 3 数据挖掘的处理过程 整个知识发现( k d d ) 过程是由若干挖掘步骤组成，而数据挖掘只是其中的一个主要 步骤。知识发现过程可以粗略的分为三个步骤：数据准备、数据挖掘以及结果的解释评估 1 1 1 。 数据准备 数据准备又可分为三个子步骤：数据选取，数据预处理和数据变换。数据选取的目的 是确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始数据库中抽取的一 组数据。数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、完成数 据类型转换等。数据变换的主要目的是消减数据维数或降维，即从初始特征中找出真正有 用的特征以减少数据开采时要考虑的特征或变量个数。 数据挖掘 数据挖掘阶段首先要确定开采的任务或目的是什么，如分类、聚类、关联规则发现或 序列模式发现等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。同样的任务可以 用不同的算法来实现，选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因 此需要用与之相关的算法来解决；二是用户或实际运行系统的要求。 结果解释和评价 数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在冗余或无关的模式， 这时需要将其剔除：若模式不满足用户的要求，这时则需要将整个发现过程退回到发现阶 段之前。另外，也可能要对发现的模式进行转化，如进行可视化处理或将结果转化为用户 易懂的表示方式。 数据挖掘仅仅是知识发现的一个重要步骤，但目前很多领域都广义地使用“数据挖掘” 一词来表示整个知识发现过程，即数据挖掘就是一个从数据库、数据仓库或其它信息资源 库的大量数据中挖掘出有趣知识的过程。 1 1 4 数据挖掘的任务 按照挖掘的具体任务以及所能够挖掘的知识类型，可将数据挖掘的任务主要划分为以 下几类： 分类 分类是数据挖掘中一项非常重要的任务，属于有教师监督学习。分类的目的是提出一 个分类函数或分类模型( 也称作分类器) ，该模型能把数据库中的数据项映像到给定类别 中的某一个。分类模型可以通过分类挖掘算法从一组训练样本数据( 其类别归属已知) 中 学习获得。 分类器的构造方法有统计方法、机器学习方法、神经网络方法和粗糙集等等。统计方 法包括贝叶斯法和非参数法，对应知识的表示则为判别函数和原型事例。机器学习方法包 2 山东师范大学硕士学位论文 括决策树法和规则归纳法，前者对应的表示为决策树或判别树，后者则一般为产生式规则。 神经网络方法主要是b p 算法，粗糙集的知识表示是产生式规则。 聚类分析 聚类分析属于无教师监督学习方法，根据“各聚集内部数据对象间的相似度最大化和 各聚集对象间相似度最小化”的基本聚类分析原则，以及度量数据对象之间相似度的计算 公式。将聚类分析的数据对象划分为若干组。聚类分析已被应用到许多领域，其中包括： 模式识别、数据分析、图像处理和市场分析等。通过聚类，可以辨识出空旷和拥挤的区域， 进而发现整个的分布模式，以及数据属性之间所存在有价值的相关联系。 关联规则挖掘 关联规则是数据挖掘的主要任务之一，是在无指导学习系统中挖掘本地模式的最普通 形式。关联规则就是从给定的数据集中发现频繁出现的项集模式知识，而挖掘关联规则的 基本任务就是从数据库中发现那些置信度和支持度都大于给定阈值的强规则。设 ，= 五，t z ， 是一组物品集，w 是一组事务集。w 中的每个事务t 是一组物品，t c ，。 假设有一个物品集a ，一个事务t ，如果a c t ，则称事务t 支持物品集a 。定义：关联规 则是如下形式的逻辑蕴涵：a j b ，其中a ，b 是项集，4 j ，b j ，且a n b = m 。 目前，已经从单一概念层次关联规则的发现发展到多个概念层次的关联规则的发现。 经典的关联规则挖掘算法有a p r i o r 算法、抽样算法、d i c 算法等等。 序列模式 一个序列组是按照交易时间排列的交易，每项交易是一个项的集合，序列模式要解决 的问题是要发现不小于最小支持阈值的序列模式。序列模式的发现方法与关联规则的挖掘 方法类似。但是关联规则描述的是交易内部项集间的关联，而序列模式则是交易之间的关 联。 1 1 5 数据挖掘的成熟方法和技术 数据挖掘利用了一些已经成熟的方法，例如：遗传算法，人工神经网络，决策树，规 则归纳，模糊集，粗糙集等。数据挖掘成熟的方法主要包括： ( 1 ) 统计方法 常用的统计方法包括： 传统方法：如回归分析、判别分析等统计方法； 模糊集：是表示和处理不确定性数据的重要方法； 支持向量机( s u p p o r t v e c t o rm a c h i n e ，s v m ) ：是建立在计算学习理论的结构风 险最小化原则之上。其主要思想是针对两类分类问题，在高维空间中寻找个 超平面作为两类的分割，以保证最小的分类错误率。 粗糙集：它是一种新的数学工具，用于处理含糊性和不确定性的信息，在数据 挖掘中发挥重要作用。目前，有关粗糙集的研究日益受到国内外学术界的重视。 山东师范大学硕士学位论文 ( 2 ) 人工神经网络 人工神经网络方法模拟人脑神经网络的结构和某些工作机制而建立的一种计算模型， 可以分为四种类型，即前馈型、反馈型、随机型和自组织竞争型。在神经网络的结构确定 后，关键问题就是设计一个学习速度快、收敛性好的学习算法。神经网络的学习问题就是 网络的权值调整问题。 从学习过程的组织和管理而言分为监督学习与无监督学习。有监督学习的网络输出有 一个评价的标准，网络将实际输出和评价标准进行比较，由其误差信号决定连接权值的调 整。评价标准是由外界提示给网络的，相当于有一位知道正确结果的教师示教给网络，故 这种学习又称为有教师学习。无监督学习是一种自组织学习，此时网络的学习完全是一种 自我调整的过程，不存在外部环境的示教，也不存在来自外部环境的反馈来指示网络期望 输出什么或者当前输出是否正确，故又称为无教师学习。无监督学习可以实现主分量分析、 聚类、编码以及特征映像的功能。 ( 3 ) 机器学习 常用的机器学习方法： 遗传算法：是模拟生物进化过程的算法，通过选择，交叉和变异操作，产生新的 较优良个体，经过若干代的遗传，最终得到满足条件的子代，即问题的解。 规则归纳：规则反映数据项中某些属性或数据集中某些数据项之间的统计相关性。 决策树：决策树的每一个非终端节点表示所考虑的数据项的测试或决策。一个确 定分支的选择取决于测试的结果。决策树也可以解释为特定形式的规则集，以规 则的层次组织为特征。 贝叶斯网络：贝叶斯网络是概率分布的图表示。 ( 4 ) 可视化技术 可视化是把数据、信息和知识转化为可视的表示形式的过程。使用有效的可视化接口， 可以快速高效地与大量数据打交道，已发现其中隐藏的特征、关系、模式和趋势等。可视 化具有广泛而重要的影响，它可以引导出新的预见和更高效的决策。 1 2 聚类分析 1 2 1 聚类分析的基本概念 数据挖掘中的聚类分析方法是一个无监督的学习过程，是指按照事物的某些属性，把 事物聚集成类，使类问相似性尽量小，类内相似性尽量大。一个聚类分析系统的输入是一 组样本和一个度量两个样本间相似度( 或相异度)