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

l j 东! j r ：j 范人学坝i j 学位论文 基于遗传算法的k - m e a n s 聚类算法分析研究 摘要 近年来，随着信息技术的发展，信息资源的经济和社会价值越来越重要。通 过数据挖掘，从大量的数据资料中发现有价值的、人们感兴趣的信息或知识，可 以达到为科学决策提供支持的目的。聚类分析是数据挖掘的一项基本任务，是一 种无监督的分类方法。聚类的目标是把一个无类别标记的数据集按某种准则划分 成不同的簇，使相同簇中数据的相似性尽可能小，而不同簇问数据相似性尽可能 大。聚类的应用非常广泛，无论是在商务领域，还是在w e b 文档分类、图像处理 等其它领域，都得到有效的应用。目前聚类算法大体上分为基于划分的方法、基 于层次的方法、基于模型的方法、基于网格的方法、基于密度的方法等。 k m e a n s 算法是聚类分析的主要算法之一，是一种基于划分的聚类算法。该 算法随机选取k 个点作为初始聚类中心，通过一个迭代过程完成聚类。该算法有 它固有的不足：它容易陷入局部极小值而得不到全局最优解；算法在进行聚类时 要求有固定的k 值，这对于没有经验的用户来说很困难；初始中心的选择对聚类 结果有很大影响；一般的聚类算法对孤立点数据和噪声比较敏感。 遗传算法是一种通过模拟自然进化过程搜索最优解的算法f 它通过基因组合、 交叉、变异、自然选择等一系列过程达到优化的目的。在这些过程中，通过“优 胜劣汰的原则淘汰掉解较差的基因，使得解朝着好的方向发展。它从一组初始 可行解出发在只需要目标函数这一信息的条件下实现对可行域的全局高效搜索并 以概率1 收敛到全局最优解，具有隐含并行性和对全局信息的有效利用能力的显 著特点，这种良好的特性使得遗传算法成为函数优化和组合优化的有力工具。因 此，将遗传算法和k m e a n s 算法有效结合，充分发挥遗传算法的全局寻优能力和 k m e a n s 算法的局部搜索能力，可以更好地提高聚类质量。 针对传统遗传算法和聚类算法存在的缺陷，本文提出了一种改进的遗传k 均 值算法，该算法的改进之处：在遗传算法中采用自识别交叉算子和自适应变异算 子，自识别交叉算子可以保证群体的优良模式遗传到下一代，加快了算法收敛速 度，自适应变异算子扩大了搜索范围，增强了算法跳离局部最优解的能力；优化 k m e a n s 聚类算法的初始中心，避免初始中心选择的随机性；根据适应度函数动 态地确定合适的聚类数k 值；使用了基于加权的k 平均的方法计算类中心，减小 k - m e a n s 算法对噪声和孤立点数据的敏感性。该文实验采用标准数据集来测试改 进算法的有效性，设计了三套实验方案对改进算法和其它算法进行测试，并以图 表和表格的形式对实验结果进行比较说明，得出了改进算法优于其它算法的结论。 i l l 山东帅范人学顾1 j 学位论文 关键词：数据挖掘；k m e a n s 聚类算法；遗传算法 中图分类号：t p 3 0 1 6 i v 山东帅i 。岜人学硕f j 学位论文 _ _ _ 一- _ _ - ，i - - - ，_ _ - _ - - - _ - - - - _ 。- _ - 一_ - i _ 。- _ 一。_ 。_ h - - _ - 。- - _ 。_ - 一 a n a l y s i sa n dr e s e a r c ho fk - m e a n sa l g o r i t h mb a s e do ng e n e t i c a l g o r i t h m a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n o l o g yi nr e c e n ty e a r s ，t h e e c o n o m i c a la n ds o c i a lv a l u eo fi n f o r m a t i o nr e s o u r c ei sm o r ea n dm o r ei m p o r t a n t b y d a t am i n i n g ，t h ev a l u a b l ea n di n t e r e s t i n gi n f o r m a t i o no rk n o w l e d g ei sd i s c o v e r e df r o m n u m e r o u sd a t ai no r d e rt os 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 i n ga n a l y s i si sab a s i c a s s i g n m e n to ft h ed a t am i n i n ga n da nu n s u p e r v i s e dc l a s s i f y i n gm e t h o d t h eg o a lo f c l u s t e r i n gi s t o p a r t i t i o nd a t aw i t h o u ta n yc a t e g o r yt a g s s e ti n t os u c hc l u s t e r st h a t o b j e c t sw i t h i nac l u s t e rh a v eh i g hs i m i l a r i t y , b u to b j e c t sb e t w e e nc l u s t e r sa r ev e r y d i s s i m i l a r c l u s t e r i n gh a sb e e nu s e di nv a r i o u sw a y si nc o m m e r c e , w e bc l a s s if i c a t i o n ， a n di m a g ep r o c e s s i n ga n ds oo n s of a r , c l u s t e r i n ga l g o r i t h m si n c l u d et h ep a r t i t i o n i n g , h i e r a r c h i c a l ，m o d e l - b a s e d ，鲥d b a s e d ，d e n s i t y - b a s e da l g o r i t h m k m e a n sa l g o r i t h mi so n eo ft h em a j o ra l g o r i t h m so fc l u s t e r i n ga n a l y s i sa n dak i n d 0 5c l u s t e r i n ga l g o r i t h mb a s e d o np a r t i t i o n i n gt h ea l g o r i t h mr a n d o m l yc h o o s e s kp o i n t s a st h ei n i t i a lc l u s t e r i n gc e n t e r s ；a c h i e v et h ep r o c e s so fc l u s t e r i n gt h r o u g hi t e r a t i o n i t h a si t so w ni n h e r e n td e f i c i e n c y ：i ta l w a y sc a m a o tg e tt h eg l o b a lo p t i m u mv a l u eb e c a u s e o fr u n n i n gi n t oal o c a lo p t i m u me a s i l y t h en u m b e ro fkn e e d st ob ek n o w nb e f o r e c l u s t e r i n g ，t h et a s ki ss od i f f i c u l tf o rt h en oe x p e r i e n c e du s e r s t h ec h o i c eo ft h ei n i t i a l c e n t e rh a sag r e a ti m p a c to nt h ec l u s t e r i n gr e s u l t s o m e t i m e sk m e a n sa l g o r i t h mi s s e n s i t i v et ot h ei s o l a t e dp o i n t sa n dn o i s e g e n e t i ca l g o r i t h mi sa na l g o r i t h mo fs e a r c h i n gt h eo p t i m a ls o l u t i o nb ys i m u l a t i n g t h en a t u r a le v o l u t i o np r o c e s s i td e s i g n sas e r i e so fp r o c e s si n c l u d i n gg e n ec o m b i n a t i o n ， c r o s s o v e r , v a r i a t i o n n a t u r a ls e l e c t i o nt oo p t i m i z et h es o l u t i o n h at h e s ep r o c e d u r e s ，t h e b a dg e n ei se l i m i n a t e dt h r o u g ht h ep r i n c i p l eo f “s u r v i v a lo ft h ef i t t e s t a n dt h es o l u t i o n d e v e l o p st o w a r d st h eb e t t e rd i r e c t i o n g e n e t i ca l g o r i t h mb e g i n sw i t hag r o u po fi n i t i a l f e a s i b l es o l u t i o n s ，a c h i e v e st h eg l o b a le f f e c t i v es e a r c h i n go ft h ef e a s i b l ef i e l dw i t ht h e o b j e c t i v ef u n c t i o na n dc o n v e r g e st ot h eg l o b a lo p t i m a lv a l u e w i t ht h ep r o b a b i l i t y1 i t h a sad i s t i n c t i v ef e a t u r eo fi m p l i c i tp a r a l l e l i s ma n de f f e c t i v eu t i l i z a t i o nc a p a c i t yo ft h e o v e r a l li n f o r m a t i o n t h ek i n do fn i c e rc h a r a c t e r i s t i cm d k e st h eg e n e t i ca l g o r i t h ma u s e f u lt o o lf o rf u n c t i o na n dc o m b i n a t i o no p t i m i z a t i o n s ot h ee f f e c t i v ei n t e g r a t i o no f v 山东帅范人学顾i j 学位论文 g e n e t i ca l g o r i t h ma n dk - m e a n sa l g o r i t h mf u l l yb r i n gi n t op l a yt h eg l o b a lo p t i m i z e d a b i l i t yo ft h eg e n e t i ca l g o r i t h ma n dt h el o c a ls e a r c h i n gc a p a b i l i t yo fk m e a n sa l g o r i t h m i no r d e rt oi m p r o v et h ec l u s t e r i n gq u a l i t ye f f e c t i v e l y a i m i n gt h ed e f e c t se x i s t i n gi nt h et r a d i t i o n a lg e n e t i ca n dc l u s t e r i n ga l g o r i t h m s ，a n i m p r o v e dg e n e t i ck - m e a n sa l g o r i t h mi sp u tf o r w a r d t h ea l g o r i t h mh a st h ef o l l o w i n g i m p r o v e m e n t s ：t h es e l f - i d e n t i f yc r o s s o v e ra n dm u t a t i o no p e r a t o r sa lea d o p t e d t h e c r o s s o v e ro p e r a t o rs p e e d su pt h ec o n v e r g e n c er a t eb yg i v i n gf i n ep a r e mh e r e d i t yo ft h e f a t h e rg e n e r a t i o nt on e x tg e n e r a t i o n a d a p t i v em u t a t i o no p e r a t o rc a l le x p a n ds e a r c h i n g s c o p ea n de n h a n c et h ec a p a b i l i t yo ft h ea l g o r i t h mt oa v o i da p p r o a c h i n gt h eb e s tl o c a l s o l u t i o n ；o p t i m i z i n gt h ei n i t i a lc e n t e r so fk m e a n sa l g o r i t h mi no r d e rt oa v o i dt h e r a n d o ms e l e c t i o n ；d y n a m i c a l l yf i x i n gt h ev a l u eo fka c c o r d i n gt ot h ef i t n e s sf u n c t i o n ； u s i n gak m e a n sc l u s t e r i n gm e t h o db a s e do nw e i g h t st oc a l c u l a t ec l u s t e a i n gc e n t e r si n o r d e rt or e d u c et h es e n s i t i v i t yo fk m e a n sa l g o r i t h mt oi s o l a t e dp o i n t sa n dn o i s e t h e e x p e r i m e n tu s e ss t a n d a r dd a t a b a s et o t e s tt h ee f f e c t i v e n e s so ft h ei m p r o v e da l g o r i t h m ， a n dd e s i g n st h r e es e t so fe x p e r i m e n t a lp r o g r a mt ot e s tt h ei m p r o v e da l g o r i t h ma n do t h e r a l g o r i t h m s ，a n dt h e ne x p l a i n st h ee x p e r i m e n t a lr e s u l t si nf o r mo fc h a r t sa n dt a b l e s ，t h u s d r a w sac o n c l u s i o nt h a tt h ei m p r o v e da l g o r i t h mi sb e t t e rt h a no t h e ra l g o r i t h m s ， k e y w o r d s ：d a t am i n i n g ；k - m e a n sc l u s t e r i n ga l g o r i t h m ；g e n e t i ca l g o r i t h m c j a s s i 6 c a t i o n ：t p 301 6 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声明的， 本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 硷秀破目 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂撞可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者虢孙篇娟 导师签 签字日期：2 0 0 9 年，月7 卵签字日期：2 0 0 9 年 腾日 d l 尔师地人学顾i 。学位论文 第一章绪论 本章首先阐明了本文所选课题的研究背景及所具有的研究价值，对聚类数据 挖掘的基本概念进行了简要介绍，然后着重阐述了目前该领域的研究状况，最后 综述了本文的主要研究工作和创新点。 1 1 研究背景及选题意义 随着计算机技术和信息技术的发展，人们可以方便地获取和存储大量的数据， 同时也造成了巨量的数据堆积。面对这些海量的数据，传统的数据分析方法远远 不能满足现实的需求。因为传统的数据分析工具只能进行一些统计查询等操作， 而不能获得数据之间的内在关系和隐含信息。为了从大量的数据中获得有价值的 知识和信息，人们提出一种去卡h 存精、去伪存真的数据挖掘技术。它的目的在于 提取海量数据中隐藏着的模式，从而发现人们感兴趣的知识。从挖掘的任务可以 把数据挖掘分为：聚类、关联规则和分类发现等三大类l lj 。 聚类是一种重要的数据分析技术，搜索并识别一个有限的种类集合或簇集合， 从而描述数据。聚类分析作为统计学的一个分支，已经被广泛研究了许多年。而 且，聚类分析也已经广泛地应用到诸多领域中，包括模式识别、数据分析、图像 处理以及市场研究【2 】。通过聚类，人们能够识别密集的和稀疏的区域，因而发现 全局的分布模式，以及数据属性之间的有趣的相互关系。聚类的用途是很广泛的， 在生物学中，它可以被用来辅助研究动、植物的分类，可以对具有相似功能的基 因进行分类，还可以用来发现人群中的一些潜在的结构。在商业上，聚类可以帮 助市场分析人员从他们的消费者数据库中区分出不同的消费群体，并概括出每一 类消费者的消费模式，可以从保险公司的数据库中发现汽车保险中具有较高索赔 概率的群体等等；聚类还可以用来从地理数据库中识别出具有相似土地用途的区 域。除此之外，聚类分析也可以作为其它算法( 如关联分析和分类) 的预处理步 骤，这些算法再在生成的类上进行处理。这样可以大大提高这些算法的执行效率。 因此聚类分析已经成为数据挖掘领域中一个非常活跃的研究课题。 k m e a l l s 算法是种经典的聚类分析方法，用k m e a n s 算法来聚类时，当结 果簇是密集的，而簇与簇之间区别明显时，它的聚类效果较好。该算法的缺点是： 它要求用户必须事先给出簇的数目k 值；其次，它对初始聚类中心敏感，并且容 易陷入局部最优；此外，它对于噪声和孤立点数据是敏感的。由此可见，聚类算 法存在很多不完善的地方，对它的进一步优化研究就显得尤为迫切和必要。这不 仅有助于算法理论的完善，更有助于算法的推广和应用。 遗传算法【3 】是一种通过模拟自然进化过程搜索最优解的方法，其显著特点是 山东j i i i 地人学帧l j 学位论文 隐含并行性和对全局信息的有效利用能力，只需少量结果就可反映探索空问较大 的区域，便于实时处理，而且具有较强的稳健性，可避免陷入局部最优。 针对k m e a l $ 算法存在的缺陷，在对该算法本身进行改进的同时，将遗传算 法应用到k m e 觚s 算法中，能在很大程度上提高k - m e a n s 算法效率和聚类质量。 所以，本课题研究不仅具有重要的科学理论意义，而且还具有重要的使用价值。 1 2 国内外研究概况 1 2 1遗传算法的研究现状 遗传算法【4 】是模拟生物进化过程的计算模型，是自然遗传学和计算机相互结 合、相互渗透而形成的一种自组织、自适应的综合技术，广泛应用在计算机科学、 社会科学和工程技术等领域，成为一个多学科、多领域的重要研究方向。遗传算 法的研究主要集中在以下几个方面： ( 1 ) 优化搜索方法的研究 优化问题【6 】的求解在遗传算法中占有很大的比重。尽管遗传算法比其它搜索 算法有更强的鲁棒性，但它更擅长全局搜索，局部搜索能力差。研究发现，遗传 算法能以极快的速度达到问题最优解的9 5 左右，但要找到问题的最优解，则需 要花费很长的时间。一些实验还表明，如果考虑解的质量和收敛速度两个指标， 遗传算法未必比其它搜索算法优越。因此，除了进一步改进遗传算法的基本理论 外，还要采用和模拟退火、聚类算法相结合的策略，以提高遗传算法的局部搜索 能力，从而进一步改善解的质量和收敛速度。 ( 2 ) 进化算法 模拟自然进化过程可以产生鲁棒的计算机算法一进化算、法【。7 1 。遗传算法是其 三种典型的算法之一，其余两种算法是进化规划和进化策略，这三种算法是彼此 独立发展起来的。进化规划最早由美国的l j f o g d 、a j o w e n 和m j w a l s h 提出； 进化策略则由德国的i r e c h e n b e r g 和h p s c h w e f e 建立。 ( 3 ) 分布并行遗传算法 遗传算法在操作上具有高度的并行性，许多研究人员都在探索在并行机和分 布式系统上高效执行遗传算法的策略。对分布并行遗传算法的研究表明，只要通 过保持多个群体和恰当控制群体间的相互作用来模拟并行执行过程，即使不使用 并行计算机，也能提高算法的执行效率。 ( 4 ) 基础理论 包括进一步发展遗传算法的数学基础，从理论和试验研究它们的计算复杂性。 在遗传算法中，群体规模和遗传算子的控制参数的选取非常困难，但它们又是必 2 山东帅范人学坝i ：学位论文 不可少的试验参数。在这方面，已有一些具有指导性的试验结果。遗传算法还有 一个过早收敛的问题，怎样防止过早收敛也是人们j 下在研究的问题之一。 ( 5 ) 人工生命与遗传算法的研究 目前对人工生命中所涉及的生命现象包括有生命的起源、自我增殖、自适应、 遗传进化和免疫等。现有不少学者用遗传算法对生态系统的演变、食物链的维持 以及免疫系统的进化做出了生动的模拟。但是，实现人工生命的手段很多，遗传 算法在实现人工生命中的基本地位和能力如何，还是值得研究的课题。 ( 6 ) 遗传神经网络 遗传算法与神经网络相结合，已成功地用于从时间序列分析来进行财政预算。 在这些系统中，训练信号是模糊的，数据是有噪声的，一般很难正确给出定量评 价。如果采用遗传算法来学习，就能克服这些困难，提高系统性能。 1 2 2 聚类的研究现状 聚类是数据挖掘技术中重要的组成部分，它能从潜在的数据中发现人们感兴 趣的数据分布模式。它的主要目的是将数据空间中的数据点划分到若干类中，相 同类中的数据点距离较近，不同类中的数据点距离较远。聚类是在无监督的情况 下根据定的相似性或距离函数自动地将数据集分成若干类的。 目前，人们研究的聚类方法大体可以划分为以下几类【8 j ： ( 1 ) 基于划分的方法：给定一个包含n 个数据对象的数据集，首先创建k 个划 分，每个划分表示一个类，并且k n 。然后采用一个划分准则将对象从一个划分 移到另个划分来帮助改善划分质量，以便在同一个簇中的对象是“相似的”，在 不同簇中的对象是“相异的”。典型的划分方法包括k m e a n s 、k m e d i c s 、 c l a r a n s 、c l a r a 、f c m 。k m e a n s 算法是应用最广泛的一种基于目标函数的 划分聚类方法，缺点是容易陷入局部极小值。但当结果簇密集并且各簇之间的区 别明显时，采用该算法效果较好。 ( 2 ) 基于层次的方法：层次的算法对给定的数据对象集合进行层次化的分解。 根据层次分解的方向不同，层次方法可分为自底向上的凝聚法和自顶向下的分裂 法。凝聚法一开始将每个数据对象作为单独一个类，然后相继地合并相近的数据 对象或类，直到所有的类合并为一个( 最顶层) 或者达到某个终止条件。分裂法 一开始将所有数据对象置于一个类中，在迭代过程中，将类分为更小的类，直到 每个数据对象各自单属一个类或者达到某个终止条件。 ( 3 ) 基于密度的方法：大多数算法都使用距离来描述数据对象之间的相似性， 但基于对象之间的距离进行聚类的划分方法只能发现球状的簇，而不易发现任意 形状的簇。因此提出了另一种基于密度的聚类方法。其主要思想是：从数据对象 3 山东师托， ：学坝i 学位论；【： 的分布密度出发，只要临近区域的密度( 对象或数据点的数目) 超过某个阈值就 继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中至少 包含某个数目的点。这样的方法能从含有“噪声 的空间数据库中发现任意形状 的簇。常见的基于密度的聚类算法有d b s c a n 、d e n c l u e 、o p t i c s 等。 ( 4 ) 基于网格的方法：基于网格的方法把数据空间量划分为有限单元的网格结 构，所有的聚类操作都在网格结构( 即量化空间) 上进行。这种方法的主要优点 是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一 维的单元数目有关。缺点是只能发现边界是水平或垂直的聚类，而不能检测到斜 边界。网格单元的大小决定了聚类精度。在该算法中，网格单元的数目随维数的 增加而成指数增长，所以不适用于高维情况。基于网格的聚类算法有代表性的包 括c l i q u e 、s t i n g 、w a v ec l u s t e r 等。 ( 5 ) 基于模型的方法：基于模型的方法建立在数据符合潜在的概率分布这一假 设基础上，该方法为每个簇假定了一个模型，寻找数据对此模型的最佳拟合。该 模型可能是数据点在空间中的密度分布函数或其它。考虑“噪声”数据和孤立点， 从而产生健壮的聚类方法。通常有两种方法：统计的方法和神经网络的方法。 聚类是一个富有挑战性的研究领域，它的研究工作集中在为大型数据库的实 际和有效的聚类分析寻求适当的方法，目前的研究方向包括下列几个方面： ( 1 ) 算法的可伸缩性：可伸缩性指算法能有效处理海量数据的数据库对象。当 数据对象小于2 0 0 个时，算法的鲁棒性很好；而对于包含几百万个数据对象的大 规模数据库进行聚类时，将会导致有不同的偏差结果，这就需要聚类算法具有高 度的可伸缩性，时间复杂度不能太高，最好是多项式时间的算法。 ( 2 ) 处理不同类型属性的能力：很多算法是用于聚类数值类型的数据，但在实 际应用中可能还要求具备处理其他类型数据的能力，如分类标称类型，序数型， 布尔型，或者这些数据类型的混合。 ( 3 ) 发现任意形状的聚类：许多聚类算法是基于欧几里德距离或者曼哈坦距离 的相似性度量方法，趋向于发现具有相近密度和大小的球状簇。但现实数据库中 的聚类可能是任意形状的，所以提出能发现任意形状簇的算法非常重要。 ( 4 ) 输入参数对领域知识的弱依赖性：在聚类分析中，许多聚类算法要求用户 输入一定的参数，如需要发现的聚类数目。聚类结果对于输入参数很敏感，对于 高维数据，输入参数是很难确定的。这就加重了用户负担，使得分析结果难以控 制。一个高效的聚类算法，应该针对这个问题，提出一个好的解决方案。 ( 5 ) 初始值的敏感性：初始值的选择以及输入顺序对聚类算法的最终结果影响 很大。在数据挖掘领域中可采取的措施：可以用多组不同的初始值并进行多次迭 代，最终选取其中最佳者作为计算结果，但是不能保证一定达到全局最优解。 ( 6 ) 处理噪声数据的能力：在现实应用中，绝大多数的数据都包含了异常数据、 4 山东帅他j ：学坝l 学位论文 未知数据、数掘空缺或者错误的数据。有些聚类算法可能对这些数据敏感，从而 导致质量较低的聚类结果。 ( 7 ) 高维性：一个数据库可能含有若干维。很多聚类算法在处理低维数据集时 表现很好，一般只涉及两到三维。通常在两、三维的情况下，人们能够很好地判 断聚类结果的质量。但聚类数据对象在高维空间是很有挑战性的，尤其是考虑到 高维数据分布可能非常稀疏，而且形状极其不规则。 ( 8 ) 基于约束的聚类：在实际应用中有可能需要在各种约束条件下进行聚类。 我们希望聚类算法在考虑这些限制的条件下，仍然能获得高质量的聚类结果。 ( 9 ) 可解释性和可用性：聚类结果最终是要面向用户的，所以聚类结果应该是 可解释的，可理解的和可用的。因此，应用目标如何影响聚类分析算法的设计也 是一项重要的研究课题。 1 2 3 混合算法的研究现状 混合算法的主要研究成果有：将模拟退火算法应用到聚类处理之中【9 】，采用 模拟退火算法对k m e a n s 算法的分类矩阵进行退火优化运算，模拟退火算法采用 随机搜索的方式，易于找到全局最优解；基于遗传算法的k m e a n s 聚类方法，用 遗传算法指导聚类问趔1 0 一3 1 。分组遗传算法( g r o u p i n gg e n e t i c a l g o r i t h m ，g g a ) 1 4 】， 致力于设计适当的染色体表达来获取问题的编码，并应用于各种分组、分割以及 聚类问题；用k m e a n s 算子代替遗传算法中的交叉算子【”】，设计出一种混合遗传 算法，并根据g u t t e r 入的有限状态齐次马尔可夫链方法证明了该方法以概率1 收 敛到全局最优点。例如傅景广等人在基于遗传算法的聚类分析【i6 】一文中，提 出了一种基于遗传算法的聚类分析方法，该算法采用二进制编码方式对聚类的中 心进行编码，用特征量与相应聚类中心的欧氏距离之和来判断聚类划分的质量； 张伟等在一种基于遗传算法的聚类新方法 1 7 l 。文中，也提出了一种改进的遗 传算法，并用来解决聚类问题：还有k r i s h n ak 等人于1 9 9 9 年在i e e e 上发表的 文章( ( g e n e t i ck m e a n sa l g o r i t h m ) ) 1 8 1 也是一种遗传k m e a n s 聚类算法。由于基 于人工模拟、遗传算法、进化策略、进化规划等随机的最优化算法可以避免收敛 到局部最优解，能找到一个全局最优解，于是这些随机的算法可以弥补传统的爬 山式聚类方法的缺点。 1 3 论文的内容安排 本论文共分六章，内容安排如下： 第一章：绪论部分。主要概述了课题的研究背景及选题意义、算法的国内外 研究情况和文章的结构安排。 山东帅范人学坝j 学位论义 第二章：数据挖掘部分。主要介绍了数据挖掘的基本概念、目的、分类、功 能以及数据挖掘的应用、影响和意义。 第三章：聚类分析部分。介绍了聚类的定义、聚类数据结构、聚类相似度度 量方法以及聚类准则函数，并详细介绍了聚类分析方法和聚类结果的评估。 第四章：基于遗传算法的改进k m e a n s 聚类分析部分。介绍了遗传算法和 k - m e a n s 算法的思想、特点以及面临的问题及解决方法。讨论了遗传聚类问题的 编码方式和适应度函数的构造方案，分析了改进的遗传算子和改进的聚类参数对 遗传聚类效果的影响。 第五章：仿真实验的结果与评价部分。主要设计了三个实验方案，比较了本 文改进算法和其它算法的性能，验证了改进算子和改进参数的有效性。 第六章：总结与展望。 6 山1 ：帅他人学坝! ：学位论文 第二章数据挖掘 2 1数据挖掘的基本概念 数据挖掘【1 9 】( d a t am i n i n g ) 就是从大量的、不完全的、模糊的、有噪声的随 机数据中，提取人们感兴趣的知识和信息的过程。这些信息和知识是隐含的、人 们事先不知道的、潜在有用的。其挖掘的流程图如图2 1 所示。 l 数据 图2 - l 数据挖蒯过程 人们将数据看作形成知识的源泉，原始数据可以是结构化的，如关系数据库 中的数据；也可以是半结构化及非结构化的，如图像数据、文本；甚至是分布在 网络上的异构数据。发现知识的方法可以是数学的、非数学的、归纳的和演绎的。 发现的知识可以用于查询优化、信息管理、决策支持和过程控制等，还可以进行 数据自身的维护。它把人们对数据的应用从低层次的简单查询提升到从数据库中 挖掘知识，提供决策支持。 2 2 数据挖掘的目的 数据挖掘并不专用于某些特定领域，它需要使用各种技术寻找可能隐藏在数 7 山东师范人学硕i ：学位沦义 据中的知识。一般情况下，应用数据挖掘技术是为了实现以下三种目的： ( 1 ) 发现知识：知识发现的目标是从数据库存储的数据中发现隐藏的关系、模 式和关联。例如，在商业应用中数据挖掘可用于发现分割、分类、关联、喜好四 种知识。发现分割知识可以将客户记录分组，策划为客户度身定做的推销活动。 发现分类知识可以将输入的数据分配到预定义的类别中，发现和理解趋势以及对 文本文档进行分类等。发现关联知识可以帮助我们发现交叉销售的机会。发现大 部分客户的喜好知识，也可以投其所好，促进商品的销售。 ( 2 ) 使数据可视化：分析人员需要搞清楚数据库中存储的大量信息的含义。在 做任何分析之前，需要先将待处理的数据人性化，并寻找显示数据的好方法。 ( 3 ) 纠j 下数据：在大型的数据库中，数据库的数据通常是不完整的，而且一般 包含错误和自相矛盾的信息。数据挖掘需要以最稳定的方法识别和纠f 这些问题。 2 3 数据挖掘的分类 数据挖掘是- - f l 交叉学科，受多个学科的影响，包括数据库系统、统计学、 机器学习、可视化和信息科学等。此外数据挖掘方法使用了大量其他学科的技术， 如神经网络、模糊逻辑、粗集理论、知识表示、归纳逻辑程序设计或高性能计算 等。 由于数据挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不同 类型数据挖掘系统。这样就需要对数据挖掘系统给出一个清楚的分类。这种分类 可以帮助用户区分数据挖掘系统，确定最适合其需要的数据挖掘系统。根据不同 的标准，数据挖掘系统可以分类如下： ( 1 ) 根据数据库类型分类 数据挖掘所基于的数据库类型有：关系型、事务型、面向对象型、推论型 ( d e d u c t i v e ) 、空间型、时序型、多媒体型、异质型( h e t e r o g e n e o u s ) 、主动型( a c t i v e ) 、 遗留型( 1 e g a c y ) 、文本挖掘和基于网络信息的挖掘掣2 0 j 。 ( 2 ) 根据得到的知识分类 包括关联规则、特征规则、分类规则、判另t ( d i s c r i m i n a t e ) 规则等的挖掘和聚类、 演变( e v o l u t i o n ) 分析、偏差( d e v i a t i o n ) 分析、孤立点分析和相似性分析等，此外根 据所挖掘的知识的抽象层次进行划分，可以包括原始层知识( 在原始数据层) 、多层 次知识和高层次知识的数据挖掘。 ( 3 ) 根据所采用的技术分类 人工神经网络【2 i 】：它从结构上模仿生物神经网络，是一种通过训练来学习的 非线性预测模型。可以完成分类、聚类和特征挖掘等任务。 决策树：用树型结构来表示决策集合。这些决策集合通过对数据集的分类产 8 山东帅范人学顾i j 学何论文 生规则，典型的决策树方法有分类回归树( c a r t ) 、c 4 5 等，其典型应用为分类 规则的挖掘。 遗传算法：是一种新的优化技术，基于生物进化概念设计了系列的过程来 达到优化的目的。这些过程有基因组合、交叉、变异和自然选择等。遗传算法易 于并行计算，并且已经应用于分类和其他优化问题。 粗集理论瞄】：它是一种研究不确定性问题的数学工具，作为集合论的扩展， 主要用于研究不完全和不完整信息描述的数据挖掘技术。可以用于分类，进行特 征归约和最小属性子集归约。 最近邻技术：通过k 个与之相近的历史记录的组合来辨别新的记录，也称为 k 最近邻技术。主要应用于分类、聚类和偏差分析等。 可视化：采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策者， 决策者可以通过可视化技术交互式的分析数据关系。 2 4 数据挖掘的功能 数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要实现以下六 方面功能，这六方面功能并不是相互独立的，有的数据挖掘项目，你很难将其归 属于哪个具体方面。如分析信用卡欺诈，一面可以说是异常检测问题，另一方面 也可以说是分类问题。 ( 1 ) 概念描述【2 3 之4 】 数据库中通常存放大量的细节数据。对含有大量数据的数据集合进行概述性 的总结并以简明准确的描述形式观察汇总的数据集。这种描述就称为概念描述。 获得概念描述的方法主要有两种：一是利用更为广义的属性，对所分析数据进行 概要总结；二是对两类所分析的数据特点进行对比，并对对比结果给出概要性总 结。此外，用户希望方便、灵活地从不同的角度和以不同的粒度描述数据集。 ( 2 ) 关联分析【2 弛6 】 关联分析就是从给定的数据集中发现频繁出现的项集模式知识的一类重要方 法。若两个或多个数据项的取值重复出现且概率很高时，就存在某种关联，然后 可以在它们之间建立关联规则。随着大量数据不停地收集和存储，许多业界人士 对于从数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的 关联模式，可有助于商务决策的制定。例如：买面包的顾客有9 0 的人还买牛奶， 如果商店将面包和牛奶放在一块，将会大大提高它们的销售量。这就是利用关联 规则解决商务问题的一个应用。 ( 3 ) 分类和预测【2 7 2 8 】 分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或预 9 山东帅范人学坝l j 学位论义 测数据未来的趋势。分类就是找出一组能够描述数据集合典型特征的模型( 或函 数) ，以便能够分类识别未知数据的归属或类别。分类模型( 或函数) 可以通过分 类挖掘算法从一组训练样本数据( 其类别归属已知) 中学习获得。分类挖掘可采 用多种形式描述输出所获得的分类模型，其中主要的表示方法有：分类规则 ( i f t h e n ) 、决策树( d e c i s i o nt r e e s ) 、神经网络和数学公式。分类通常用于预测有限 离散值，但在一些情况下，需要预测某数值属性的值( 连续数值) ，这样的分类称为 预测。分类和预测的应用十分广泛，例如，可以建立一个分类模型，对银行的贷 款客户进行分类，以降低贷款的风险；也可以通过建立分类模型，对工厂的机器 运转情况进行分类，用来预测机器故障的发生。 ( 4 ) 聚类分析 聚类分析与分类预测方法明显不同之处在于，后者所学习获取分类预测模型 所使用的数据是以知类别归属，属于有类别监督学习方法；而聚类分析所处理的 数据均是无类别归属，类别归属标志在聚类分析处理的数据集中是不存在的。 根据最大化类内相似性、最小化类间相似性的原则进行聚类，使得在同一个 类中的对象具有很高的相似性，而与其它类中的对象很不相似。每一个聚类分析 所获得的类可以视为是一个同类别归属的数据对象集合，更进一步从这些同类别 数据集中又可以通过分类学习相应的分类预测模型。此外，通过反复不断地对所 获得的聚类组进行聚类分析，还可获得初始数据集合的一个层次结构模型。 ( 5 ) 孤立点分析【2 9 3 0 】 数据库中可能包含一些数据对象，它们与数据的般行为或模式不一致。这 些数据对象就是孤立点。许多数据挖掘算法试图使孤立点的影响最小化，或者排 除它们。但在一些应用中孤立点本身可能是非常重要的信息。例如在欺诈探测中， 孤立点可能预示着欺诈行为。 ( 6 ) 演变分析l 引。3 2 j 数据演变分析描述行为随时间变化的规律和趋势，并对其建模。可以从股票 交易数据中挖掘出整个股票市场和特定公司的股票演变规律，以帮助预测股票市 场的未来走向，帮助对股票投资做出决策。 2 5 数据挖掘的应用、影响及意义 数据挖掘在金融分析、商务智能、生物医学等众多领域都存在着广泛的应用， 它对商务过程、自然科学及社会科学等都有着不同程度的影响【3 3 j 。 首先，在商务领域，数据挖掘往往被集成到企业决策支持系统中，作为商务 智能的重要环节，为企业高层决策提供更多参考。与此同时，它也有利于发现商 务过程中的各种弊端，为客户们带来更加优质的服务。由此可知，数据挖掘