（计算机应用技术专业论文）基于粒子群优化的数据流挖掘的聚类算法分析.pdf

摘要 随着计算机及其应用技术的迅猛发展，人类获取数据的能力得到很大程度的 提高，数据流( d a t as t r e a m s ) 己成为重要的数据来源之一， 因此有关数据流的挖掘 算法也已成为一个重要的前沿课题。数据流聚类是数据流挖掘的一个重要的分支， 其主要目的是从数据流中发现新的知识模式和隐藏的新规律。 数据流是一个由不断到达的数据所组成的动态变化增长的数据集，要从有限 的数据处理分析过渡到无限的数据处理分析，人们面临着新的严峻的挑战，需要 寻求新的聚类算法。最为经典的数据流聚类算法是c l u s t r e a m 算法，c l u s t r e a m 算 法包括在线聚类部分和离线部分两部分，本文主要的研究工作是基于两层模型， 对数据流的离线部分做优化处理。 本文的主要研究工作包括以下几个方面： ( 1 ) 分析了粒子群算法与遗传算法优缺点，并结合两者的优点，对基于质心的 k m e a n s 算法的聚类中心做优化，使得k m e a n s 的聚类算法产生更好的聚类效果。 实验数据表明：采用基于交换技术的混合i g a & p s o 的聚类算法比单一的k m e a n s 算法性能更好。 ( 2 ) p s o 作为一种智能优化算法，有时也会因为早熟而陷入局部最优解。为了 解决局部最优的问题，利用捕食被捕食的粒子群优化( p p p s o ) 作优化，在p p p s o 中，捕食者追逐被捕食者的中心，而被捕食者逃离捕食者，这是一种防止局部最 优者出现且找到全局最优者的一种有效的方法。本文提出了一种使用p p p s o 来优 化模糊均值的聚类方法。 ( 3 ) 在高维数据流空间罩，为了解决多余特征对数据流聚类质量的影响，提出了 一种基于粒子群与特征选择的数据流聚类算法。此算法具有自动探测、移除多余 不重要特征等功能。实验结果表示，基于特征选择的数据流聚类算法( d s c f c ) ， 在对有多余特征的数据流聚类时，比c l u s t e a m 算法更有效，聚类质量更好。 ( 4 ) 在数据流挖掘中，要快速地挖掘出数据流中的任意有趣模式，如果只利用 现有的基于频繁项集算法直接进行复杂模式挖掘是困难的。为解决此问题，一种 基于频繁项集的条件模式挖掘被提出。从频繁项集出发，去挖掘那些不能从项集 中立即发现的任意模式，即条件模式挖掘。把任意模式条件挖掘与数据聚类分析 结合起来，能更快速有效地挖掘数据库中任意的有趣的规则。 关键词：数据流挖掘；聚类分析；粒子群优化；捕食一被捕食；条件模式 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e ra n di t sa p p l i c a t i o nt e c h n o l o g y , p e o p l e s a b i l i t yo fg e t t i n gd a t ai n c r e a s e dt os u c hal a r g ee x t e n ta n dd a t as t r e a m sh a sb e c o m e o n eo fi m p o r t a n td a t as o u r c e ，t h a tt h ed a t as t r e a mm i n i n ga l g o r i t h m sh a v eb e c o m ea n i m p o r t a n tc u t t i n g e d g et o p i c s c l u s t e r i n gd a t as t r e a m si sa ni m p o r t a n tb r a n c ho fd a t a s t r e a mm i n i n g ，i t sm a i np u r p o s eo fi st od i s c o v e r yt h en e wk n o w l e d g em o d e la n d h i d d e nn e wr u l e s d a t as t r e a mi sad y n a m i cg r o w i n gd a t as e t ，w l r i c hc o n s i s t so fc o n t i n u o u sa r r i v i n g d a t a f r o mal i m i t e dd a t ap r o c e s s i n ga n da n a l y s i st oa nu n l i m i t e d ，p e o p l ea r ef a c e d w i t hn e wc h a l l e n g e sa n dn e e dt of i n dan e wc l u s t e r i n ga l g o r i t h m t h ec l u s t r e a mi st h e m o s tc l a s s i cd a t as t r e a mc l u s t e r i n ga l g o r i t h m ，c l u s t r e a mc l u s t e r i n ga l g o r i t h mi n c l u d e s o n l i n ea n do f f i i n et w op a r t s ，a n di nt h i sa r t i c l et h em a i nw o r ki sd oo f f i i n e o p t i m i z a t i o nt ot h ed a t as t r e a mb a s e do nt h i sm o d e l t h em a j o rw o r ko ft h i sp a p e rw a ss h o wa sf o l l o w i n g ： ( 1 ) t h ea d v a n t a g e sa n dd i s a d v a n t a g e so fp a r t i c l es w a r ma l g o r i t h ma n dg e n e t i c a l g o r i t h ma r ea n a l y z e da n dc o m b i n e dw i t ht h ea d v a n t a g e so f b o t ht oo p t i m i z et h e c e n t r o i d b a s e dk m e a n sc l u s t e r i n g ，m a k i n gt h ek m e a n s c l u s t e r i n ga l g o r i t h mt o p r o d u c eb e t t e rc l u s t e r i n gr e s u l t s ，a n d “t h ed a t am o r es i m i l a r i t yw i t h i nt h ec l u s t e r , t h e d a t em o r ed i s s i m i l a r i t yb e t w e e nt h ec l u s t e r ”t h ee x p e r i m e n t a ld a t as h o w st h a t ：t h e h y b r i dc l u s t e r i n ga l g o r i t h mb a s e do ni g aa n dp s ow h i c hu s i n gs w i t c h i n gt e c h n o l o g y h a sb e t t e rp e r f o r m a n c et h a nt h es i m p l ek - m e a n sa l g o r i t h m ( 2 ) a so n eo fo p t i m i z a t i o na l g o r i t h m s ，p s oa l g o r i t h ms o m e t i m e sr e a c h e st ol o c a l o p t i m u mb e c a u s eo fp r e m a t u r i t y i no r d e rt os o l v et h ep r o b l e mo fl o c a lo p t i m u m ，t h e p r e d a t o r p r e yp a r t i c l es w a r mo p t i m i z a t i o n ( p p p s o ) w a si n t r o d u c e dt os o l v et h e p r o b l e m i nt h ep p p s oa l g o r i t h m ，t h ep r e d a t o r sc h a s e st h ec e n t e ro fp r e y , a n dt h e p r e y st r yt oe s c a p et h ep r e d a t o r s ；t h i si sa ne f f e c t i v ew a y t op r e v e n tl o c a lo p t i m u ma n d t of i n dt h eg l o b a lo p t i m u m t h i sp a p e rp r e s e n t sac l u s t e r i n gw h i c hu s i n gp p p s ot o o p t i m i z et h ef u z z ym e a nm e t h o d ( 3 ) i nt h es p a c eo fh i g hd i m e n s i o n a ld a t as t r e a m s ，i no r d e rt os o l v et h ea f f e c to f e x t r af e a t u r e so nt h eq u a l i t yo ft h ed a t ac l u s t e r i n g ，ad a t as t r e a mc l u s t e r i n ga l g o r i t h m b a s e do nf e a t u r es e l e c t i o nw a sp r o p o s e d t h i sa l g o r i t h mh a st h ec h a r a c t e r i s t i c so f a u t o m a t i cd e t e c t i o no fe x c e s su n i m p o r t a n tf e a t u r e sa n dr e m o v e di t t h ee x p e r i m e n t a l r e s u l t si n d i c a t e dt h a td s c f c a l g o r i t h mc a nd e t e c tt h eh i d d e nr e d u n d a n tf e a t u r e si n i i d a t as t r e a ma n dr e m o v et h e m i ti sm o r ee f c t i v ea n dh a sb e t t e rr e s u l tt h a nc l u s t e a m a l g o r i t h m ( 4 ) i nt h ed a t as t r e a mm i n i n g ，i no r d e rt om i n ea n yi n t e r e s t i n gd a t as t r e a mm o d e l f u l l ya n dq u i c k l y , i fo n l yu s i n gt h ee x i s t i n ga l g o r i t h m sb a s e do nf r e q u e n ti t e m s e t m i n i n gc o m p l e xm o d e l sd i r e c t l yi sd i f f i c u l t t os o l v et h i sp r o b l e m ，c o n d i t i o nm o d a l m i n i n gb a s e do nf r e q u e n ti t e m s e tp a t t e r nw a sp r o p o s e d s t a r t i n gf r o mt h ef r e q u e n t i t e m s e t s ，t od i ga n ym o d ew h i c hc a nn o tb ei m m e d i a t e l yf o n df r o mi t e m s e t ，t h a ti s ， c o n d i t i o n sp a t t e r nm i n i n g c o m b i n e da n yc o n d i t i o n sp a t t e r nm i n i n gw i t hc l u s t e r i n g c a nm o r eq u i c k l ya n dm o r ee f f i c i e n t l yd i ga n yi n t e r e s t i n gr u l e si nd a t a b a s ea n d d i s c o v e rn e wk n o w l e d g ea n dn e wl a w s k e yw o r d s ：d a t as t r e a mm i n i n g ；c l u s t e ra n a l y s i s ；p a r t i c l es w a r mo p t i m i z a t i o n ； p r e d a t o r p r e y ；c o n d i t i o n a lp a t t e r n i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名： 易溯札 日期：州。年瑚f 夕日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密圈。 ( 请在以上相应方框内打“4 ”) 作者签名：三7 动巾卜 日期：p l 。年j 月i 夕日 导师签名：罗可日期：l 口年b 月z 日 1 1 研究的背景和意义 第一章绪论 数据挖掘1 ( d a t am i n i n g ，简称d m ) 是一个具有广泛应用前景的研究领域。它 不但可以帮助人们从海量数据中提取感兴趣的模式，而且还可以进一步预测趋势， 数据挖掘的出现为智能地把海量数据转化为感兴趣的知识提供了强有力的手段。 聚类模式的数据挖掘作为数据挖掘的一个重要研究分支，特别在股票交易所的股 票信息、大型超市交易记录数据、网络检测数据、银行卡交易流等部门的记录数 据都基于流数据模型的数据集。这些数据流( d a t as t r e a m s ) 具有数据量大、动态 速度、连续有序的等特点。数据流作为重要的数据来源之一，有关数据流的挖掘算 法已成为一个重要的前沿课题。传统数据挖掘主要的算法有分类模式、聚类模式 分析、关联规则、决策树、神经网络算法、时间序列模式等。其中数据流的聚类 模式有基于距离、基于密度、基于网格、基于特征选择等模式。聚类模式的数据 挖掘作为数据流挖掘的一个重要的研究分支之一，最近几年来，大量有关的数据 流聚类算法呈现，特别是a g r a w a l 等人提出c 1 u s t r e a m 算法心，后来很多算法都基 于此模型，即在线部分一次扫描贮存数据概要信息，离线部分再聚类的两层模型 结构。 网页搜索目前已形成了一种朝阳的产业。2 0 0 8 年，中国搜索引擎市场经历了 高速增长一年，到2 0 0 8 年底，中国搜索引擎市场规模达到5 1 5 亿元人民币，同比 2 0 0 7 年增长了7 7 1 。这些快速增长的页面搜索请求为网络搜索公司带来了巨大 网络流量，同时为社会带来巨大的经济效益。如何对这些搜索的数据流进行实时 分析处理，以便带来更为强大的搜索功能和更好的用户体验，是每个网络搜索公 司梦寐以求的理想。 在金融领域中，面对大量的金融数据，如何从中发现极少量的、极隐蔽的具 有洗钱特征的数据成为金融数据挖掘的一个重要问题。据估计，目前全球至少6 0 0 0 亿美元的“洗钱”已经占到全世界国内生产总值的2 至5 。2 0 0 8 年，中国人民银 行协助调查涉嫌洗钱案件8 9 9 起，是上年协查案件数的2 7 倍，涉及金额折合人民 币2 5 1 3 亿1 。2 0 0 9 年7 1 1 月，中国人民银行南京中心支行接收人民币大额现金 “可疑 存取报备2 9 9 0 1 5 笔、涉及金额4 8 3 亿元人民币。 上述各种应用场景的共同特点是海量无限的数据的实时、有序、动态快速到 达，学术界把具有这种特征的新兴数据集称为数据流。数据流相对于传统数据库 己成为种新兴且日益成为主流的数据形式。人们迫切需要从这些海量的数据流 中提取有趣的、有价值的知识。所以，数据流的挖掘日益成为一个热点与迫切的 课题。 传统数据聚类已经在图像处理、空间数据分析、模式识别、市场分析等领域 取得了广泛的应用1 5 1 。在数据流环境下，数据聚类同样是一种重要的数据挖掘技 术，从有限的数据到无限的数据处理能力，计算机方面的科研工作者们面临着新的 挑战。在数据流挖掘中，数据流聚类分析是数据流挖掘的一个重要的工具，如何对 数据流进行有效的聚类，对从大量数据中提取有价值的信息具有很大的意义，对 有效的节省存储空间具有深远的理论价值和重要的应用价值，对信息决策者进行 决策及网络的实时检测等都具有重大的现实意义。 1 2 数据流挖掘概述 1 2 1 数据流挖掘的发展背景 数据流挖掘一个重要特点是对动态的数据集进行一遍扫描，对数据集以较少 的扫描遍数来完成计算可追溯到早期的自动机理论研究。在1 9 7 3 年k n u t h 就在其 著作( ( t h ea r to fc o m p u t e rp r o g r a m m i n g ) ) 第3 卷中对单遍或者较少扫描遍数的排 序算法进行了深入的研究。学界公认的最早的数据流算法是m u n r o 等人在1 9 8 0 所提出的单遍扫描近似分位数算法旧1 。他们证明仅用o ( n l p ) 的空间复杂度，就可 利用p 次遍历来精确地获取分位数的结果。 数据流模型最早的定义是h e n z i n g e r 等人在l9 9 6 年提出的。他们将数据流正 式定义为允许单遍( 或多遍) 扫描的模型1 7 1 ，并提出了期望可测的计算理论复杂度。 对于数据流系统来说，从研究向实际应用转化的标志性成果是j o a nf e i g e n b a u m 与 a t & t 的研究人员一起合作研发出的网络交通数据管理系统。19 9 9 年，p h i l g i b b o n s 等人对各种利用小空间为大规模数据集提供近似的数据结构进行了分析 和综述扭，并将提出数据流的概要数据结构( s y n o p s i sd a t as t r u c t u r e s ) 。这些研究 工作为后来的数据流挖掘研究奠定了坚实的基础。 近几年来，随着计算机网络应用的普及使得数据流研究课题真正成为学术界 广泛的关注。比如，2 0 0 0 年的k d d ( 知识发现与数据挖掘1 国际会议上，最佳论文 就是研究一种用于支持数据流处理的扩展c 语言。特别是在2 0 0 2 年，国际上几个 最高级别学术会议都提出了有关数据流问题的研究成果，在s i g m o d 和v l d b ( 国 际超大型数据会议) 都对数据流研究进行过专门的综述旧1 ；v a r g h e s e 在 s i g c o m m ( 计算机网络最高级别会议) 会议上提出有关于网路链路层的一个简单 数据流模型；s i g m e t r i c s ( 性能分析最高级别会议) 综述了s p r i n t 实验室在i p 包 监测方面的工作n 。 数据流的广泛应用吸引了众多学者对数据流算法的深入研究。由于数据流本 身无限性、动态性、有序性等特点使得传统的算法不能直接应用于数据流。由于 内存或缓存等存储空间的有限性，只能对数据进行一次顺序扫描，采用动态的增 量式的算法来处理数据流。再者由于数据流到来的速度很快，多数应用要求在数 据到来的同时就应该进行分析决策，因此算法对时间复杂度提出了更高的要求。 在文献 1 1 】中提出了有关于数据流的算法的一般标准，简要概括如下： ( 1 ) 每个数据流项的处理分析必须在很小的一段时间内。 2 ( 2 ) 数据流处理分析过程中对内存的使用必须是有严格的限制，般来说，与 算法处理数据记录量无关。 ( 3 ) 由于数据流是连续的，并且到来的速度也很快，故只能对数据流进行单次 扫描。 ( 4 ) 要求能在任何的一个处理阶段输出一个可对数据进行描述的模型。 ( 5 ) 数据流模型要实时地反映数据流的变化。 ( 6 ) 要求能在用户需要的时候进行必要的演化分析。 其中最为重要并且最难做到的是最前面两个标准，因为传统数据聚类的算法 都面临着可扩展性和效率的挑战。这些算法的内存需求量是随数据流的增加而快 速的递增，并且计算复杂性呈非线性增长，在算法运行的某一时刻，内存将会耗 尽，即使不出现这种情况，也会出现数据处理速度将落后于数据的到来的速度， 这样将导致聚类算法的失效。所以这些传统的算法是无法适用于数据流领域的处 理分析的，人们开始致力于研究新的适用于数据流模型的聚类算法。 1 2 2 数据流挖掘的研究现状 数据流的概念在19 9 6 年被提出以来，一直就成为研究的热点问题。在国外， 形成了两个特别著名的数据流研究小组，一个是s t a n d f o r d 大学的r m o t w a n i 教授 领导的研究小组，另一个是u i u c 大学的j h a n 教授领导的研究小组。他们在开发 多个数据流研究项目和系统原型，涉及到数据流的管理、查询、挖掘等数据流处 理与分析的各方面的内容。 国际数据流方面的会议已经举办了多次，探讨了数据流领域中的各方面问题。 特别在s i g m o d 和v l d b 会议上，都对数据流研究进行过专门的综述一】。己有的 数据流预处理技术包括抽样、直方图、小波分析、滑动窗口及一些统计技术等， 这些技术都基于这点，即利用有限的概要信息去近似表示无限数据流信息，这也 是数据流挖掘与传统数据挖掘不同之处。当今社会，相对于如此丰富的信息数据， 而我们从中发现有价值的知识却显得相当的“贫乏 。整个社会在呼唤一种高效的 数据流挖掘方法，能从海量数据流中挖掘出有价值的知识，幸运的是，我们科研 工作总是在人们的需要的强大动力下推动着前行。在数据流挖掘算法方面，人们 取得了系列的研究成果。比如，数据流聚类【1 2 ，1 3 ，1 4 ，2 ，15 1 ，数据流关联规则挖掘 1 6 , 1 7 , 1 8 , 1 9 】，数据流分类 2 0 , 2 1 , 2 2 】等。 在国内，数据流挖掘方面研究也得到长足的发展，主要是复旦大学周傲英等 人在数据流分析方面取得不错的成绩【18 , 2 3 】；中山大学朱蔚恒等人针对非凸形的数 据聚类效果不好等问题，提出了种采用空间分割、组合以及按密度聚类的 a c l u s t r e a m 算法【2 4 】；哈尔滨工业大学李建中等人在数据流的存储、查询等方面取 得些成果【z 引。 数据流挖掘是一个新兴的研究领域，其中有很多有趣的问题值得探索，例如， 对于高维数据如何降维处理来进行数据流挖掘，如何对混合型数据进行聚类分析， 怎样把传统挖掘算法移植到数据流中，如何优化数据聚类结果，如何在对演化的 数据进行数据挖掘，如何在数据挖掘过程中引入时间权值等。 数据流挖掘技术的研究还在探索阶段，最大的问题就是数据流的无限性与内 存有限性的矛盾，智能有效的交互式挖掘与成功案例应用等方面都是今后大家需 要解决的研究课题。 1 3 粒子群算法概述 1 3 1 粒子群算法简介 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是由k e n n e d y 和 e b e r h a r t 于1 9 9 5 年提出的一种基于群体智能的计算模型【2 6 1 。他们是在研究鸟群 和鱼群在群体觅食活动中所表现出来的一种智能行为的基础上，提出的一种群体 智能算法，其理论思想的来源于演化计算和仿生学的理论，通过模仿鸟群飞行觅 食行为，通过鸟群之间信息交换与协作使群体行为到达最优。 p s o 是进化计算的一个重要的研究分支，它是一种基于迭代的优化算法，系统 初始化特别简单，即为任意一组随机解，通过有限次的迭代搜寻最优值。在寻优 的过程中，p s o 算法中每个粒子受到自身和种群中最优个体的影响不断调整自身的 速率和位置并飞向全局最优解。与遗传算法相比，p s o 算法具有更智能的背景、参 数简单，实现起来也简单。目前，p s o 算法已经引起了进化计算、优化及其它领域 的广泛关注 27 1 。对于p s o 算法的改进，也产生了一些p s o 算法和遗传算法的混合算 法【2 8 1 。p s o 算法：具有实现简单，收敛快，但是易陷入局部极小值，种群数量少 等特征。 1 3 2 粒子群算法研究现状 从1 9 9 5 年k e n n e d y 和e b e r h a r t 在基于群体智能的基础上提出经典p s o 算法【2 叫 以来，粒子群优化算法研究得到很大发展与广泛的应用。现在人们广泛使用标准 p s o 算法，是由s h i 等人于1 9 9 8 年对经典p s o 算法进行了修改而成【2 9 1 。 标准的粒子群算法步骤如下： s t e p l ：( 初始化) 整个搜索空间随机产生粒子群的位置和速度。评价每个粒子在 当前位置x ；处的适应度值。 。 s t e p 2 ：对所有粒子，如果适应度值大于个体极值，则个体极值更新为x ；处的适应值， 否则不改变个体极值。 s t e p 3 ：将所有粒子的个体极值p ；与全局极值g ；比较，如果个体极值大于全局极值， 则全局极值更新为x ；处的个体极值，否则不改变全局极值。 s t e p 4 ：根据下式子对每一个粒子进行更新速度与位置。 v i d = 6 0v i d + c l r l ( p i d x i d ) + c 2 r 2 ( g i d x i d ) x i d = x i d +v i d 其中d = l ，2 ，d ，d 为空间维数；d 为惯性权重系数；c ，c 。为加速度系 数；而r 。，r ：为 0 ，1 区间内均匀分布的独立的随机数；如果第d 维空间 变化范围定义为 一m a x d ，m a x d ，采用一般约束的v 。的最大速度：v 。= k 4 m a x d ，而k 0 1 ，0 2 。 s t e p 5 ：检验是否符合终止条件；迭代次数或者是最小误差等条件。产生最优问题 解。 1 9 9 9 年，c l e r c 和k e n n e d y 提出了个自适应p s o 模型，引入了收缩因子来 减小粒子振荡幅度以加速粒子收敛速度 3 0 l 。 2 0 0 0 年，e o ( e x t r e m a lo p t i m i z a t i o n ) 由b o e t t c h e r 和p e r c u s 提出，它反 映了生态系统中的自组织临界性( s o c s e l f - o r g a n i z e dc r i t i c a l i t y ) ，在该模型 中的进化是由过程来驱动，该过程就是对种群中最弱种类连同其最近邻居进行强 制变异【”】。将p s o 与e o 结合可以避免p s o 算法的局部最优收敛，p s o 的快速收敛 和e o 的强局部搜索能力有机结合可以有效地改善算法性能。 2 0 0 4 年，s u n j 等人根据测不准原理( u n e e r t a i n t yp r i n c i p l e ) ，粒子的位 置和速度是不能同时被决定的，提出量子粒子群优化算法q p s o 3 2 _ 3 1 ，引入波函数， 后来，s u n j 等人又将变异操作引入量子粒子群优化算法，从而提出了有变异的量 子粒子群优化算法1 34 1 。 目前各种优化算法应用的重要领域是多目标优化，在粒子群算法被提出后， 不少科研工作者开始尝试使用p s o 算法来求解多目标优化问题。2 0 0 5 年，l e t i e i a c a g n i n a 等人提出一个简单多目标粒子群优化器( s i m p l em u l t i o b j e c t iv e p a r ticle s w a r mo p ti m iz e r w s m o p s o ) 3 5 1 ， 2 0 0 6 年，雷开友等人提出了具有团队协作精神的惯性权重策略粒子群算法 【3 6 1 ，在算法中引入s u g e n o 或y a g e r 模糊补算子函数、惯性权重曲线等，从而使 算法在全局搜索能力和局部搜索能力达到良好平衡，既可以达到快速收敛、又能 避免局部最优的问题。使得算法在求解质量和求解速度两方面都得到很好的平衡。 2 0 0 6 年，b y u n g - 1lk o h 等人，为了解决负载不平衡问题，提出了并行异步 粒子群优化算法( p a r a l l e la s y n c h r o n o u sp a r t i c l es w a r mo p t i m i z a t i o n p a p s 0 ) 【3 7 】。使用异步方法的并行优化算法是解决负载不平衡问题一个比较好的算法。 2 0 0 7 年，朱小六等人提出的动态自适应惯性权重改变方法，在算法中引入两 个变量，一个是粒子进化度，另外是一个粒子聚合度，这样加强了全局搜索能力 与粒子收敛的精度【3 8 1 2 0 0 8 年，d a s 等人将差分进化( d e ) 引入p s o 速度更新公式中，提出p s o d v 算法【3 9 】。 其他与粒子群算法融合算法相当地多，比如p s o 算法与育种算法、p s o 算法与 蚁群算法，p s o 算法与捕食一被捕食融合等等。 1 3 3 数据流挖掘存在的问题与研究方向 在数据流挖掘的这一个新兴的领域里，其中有很多有趣的问题值得我们研究 与分析，例如，如何进行高维数据的“降维处理而又不影响数据流挖掘的质量， 如何对混合型数据进行聚类分析，如何把传统挖掘算法移植到数据流中，如何优 化数据聚类结果，如何在对演化的数据进行数据挖掘，如何在数据挖掘过程中引 入时间的权值等。数据流挖掘技术的研究还处在探索的研究阶段，最大的问题就 是数据流的无限性与内存有限性的矛盾，智能有效的交互式挖掘与成功案例应用 等方面都是今后大家需要解决的研究课题。 g a b e r 等人【4 0 】对数据流挖掘进行回顾，并指出了数据流挖掘今后所面临的主 要问题和最新的研究方向： ( 1 ) 数据流预处理技术。数据流的预处理过程对数据流挖掘来说是相当重要 的，虽然预处理非常的重要，但是又不能花费很高的时问与空间代价操作来完成 预处理，这是因为数据流处理速度是有严格的要求。所以，在数据流环境下，我 们应当使用一些比较轻量级的预处理方法，以达到数据预处理的目的。 ( 2 ) 为了很好地满足用户的需求，交互式挖掘环境在数据流挖掘中被使用。 是必须的。因为满足用户的需求是人们进行科学研究的一个最重要的动机之一， 同时这也是数据流挖掘必须面向的应用研究领域的要求。 ( 3 ) 要实现数据流挖掘算法同数据流管理系统的集成。只有将储存、查询和 挖掘技术结合起来才能实现数据流管理系统的真正实际应用。 ( 4 ) 数据流模型的“过拟合”( o v e r f i t t i n g ) 问题。为了避免“过拟合 人们 常采用交叉验证技术，但是此技术在数据流环境下所需要的代价过高并且效率低 下。所以需要设计一些特别适用数据流环境的新算法来避免模型的“过拟合”问 题。而目前在数据流挖掘中关于“过拟合”问题研究还是很相当的欠缺。 ( 5 ) 与数据流挖掘自身相关的技术问题。如何进行数据抽出，概要，近似等。 并行处理算法与适合并行算法的硬件设计等。如何设计新的硬与软件件解决方案 等。 ( 6 ) 目前，数据流挖掘实际成功应用的案例很少，数据流挖掘研究还处在理 论研究阶段，还需要更多的成功应用案例。 ( 7 ) 对数据流准确性实时评价的形式化处理。用户需要一种评价机制来知晓 当前有效资源量的准确性，并能根据当前的有效的资源来调整准确性机制。 ( 8 ) 数据流计算理论的形式化处理，这种形式化处理工作将有助于今后数据 流挖掘研究的数学模型的建立。 上述八个方面概括了今后数据流挖掘研究主要的发展方向。对数据流的研究 主要集中在这几个方面： ( 1 ) 对数据流工作模型的建立。 ( 2 ) 对数据流查询的响应分析。 ( 3 ) 如何关于管理数据流的研究。 ( 4 ) 如何对数据流进行挖掘处理分析等。 特别地，对于数据流挖掘的一个重要研究分支的数据流聚类研究来说，同样 在传统的聚类算法基础上，也面临着新的问题。比如， ( 1 ) 在数据流中，新型的簇表示法应具有时问特性，以适应数据流的动态变 化。 ( 2 ) 在传统的数据聚类中，数据的簇与“奇异点 是非常确定的，一般都不 会随时间的变化而变化，而数据流的“奇异点”却有可能成长为新的簇类，所以 如何快速而有效地消除真正的“奇异点”就成数据流聚类算法的严峻挑战。 6 ( 3 ) 在实际应用中，由于计算机技术与通信网络技术的同新月异，数据流往 往是以分布式形式出现，而且这些数据流又具有不完整性、重叠性、噪声性等， 面对如此形式数据流聚类，则需要人们提供一种模糊系统下软聚类算法来实现。 ( 4 ) 海量的动态的数据流快速的到达，这要求数据流的聚类算法具有快速的 增量处理能力。在数据流中，如何完美地统一数据流的无限性与计算机资源的有 限性，这是人们在进行数据流聚类分析时必须考虑的问题，同时也是一个比较难 达到的要求。 在本文中，为了解决海量的数据与内存的有限性问题，聚类算法采用 c 1 u s t r e a m 算法的双层模型，在线部分抽取数据概要信息，离线部分对概要信息进 行聚类，以求得更为精确的结果。在本文的第四章，提出一种基于粒子群优化与 捕食一被捕食的模糊聚类算法，以解决数据流聚类中数据的不完整性，模糊性等方 面的要求。 1 4 本文的工作 本文的主要工作在四个方面； ( 1 ) 分析了粒子群算法与改进的遗传算法优缺点，并结合此两算法的优点， 并对基于质心的k - m e a n s 的聚类中心做优化，使得k - m e a n s 的聚类算法产生的簇 类能很好地满足聚类算法的一条重要性质，即“簇内相似性与簇间相异性尽可能 的高”。从实验的数据表明：采用基于交换技术的混合i g a & p s o 的聚类算法比单一 的k m e a n s 聚类算法性能更好。 ( 2 ) p s o 作为一种智能算法，有时也会因为早熟陷入局部最优。为了解决局部 最优的问题，h i g s h i t a m i 等提出捕食一被捕食的粒子群优化( p p p s o ) 。在p p p s o 中，捕食者追逐被捕食者的中心，而被捕食者逃离捕食者，这是一种防止局部最 优出现且找到全局最优的一种有效方法。在本文中，提出了一种使用p p p s o 来优 化模糊均值聚类的方法。 ( 3 ) 在高维数据流空间里，各数据点常出现等距情形，而且有些多余特征既不 利于聚类，又会影响相邻数据的聚类质量。因此，移除这些特征能提高聚类质量 而产生更好的聚类数据。为解决此问题，提出了一种基于特征选择的数据流聚类 算法，它是在一趟聚类算法中利用特征选择技术，并提出了基于紧致性与分离性 对特征排序、特征的等级评分、自动探测多余不重要的特征、使用特征移除算法 移除多余不重要特征等。实验结果表示，d s c f c 算法具有：探测数据流中隐含的多 余特征并移除多余特征；在对有多余特征的数据流聚类时， = t c l u s t e a m 算法更有 效，聚类质量更好等优点。 ( 4 ) 在数据流挖掘中，要充分地快速地挖掘出数据流中的任意有趣模式，而 现实数据挖掘查询等这种任意合成模式是特别复杂。如果只利用现有的基于频繁 项集算法直接进行复杂模式挖掘是困难的。为解决此问题，一种基于频繁项集的 条件模式挖掘被提出。关联规则挖掘问题的解决分为两步：第一步，找出所有的 频繁项集，即频繁项集挖掘。第二步，由频繁项集产生强关联规则。从频繁项集 出发，去挖掘那些不能从项集中立即发现的任意模式，即条件模式挖掘。把这种 任意模式条件挖掘与数据聚类分析结合起来，能更快速更有效地挖掘数据库中任 7 意的有趣的规则，以发现新知识新规律。 1 5 本文的组织 第一章阐述了数据流挖掘的研究意义和背景，介绍了数据流挖掘的发展及其 国内外对数据流挖掘研究现状及存在的问题，同时也简单介绍粒子群算法研究现 状，最后对本论文的主要研究内容进行了简单的介绍。 第二章介绍了数据流聚类算法研究现状及存在的问题，总结了数据流聚类的 基本思想，分析了经典的数据聚类算法与进化的数据流聚类算法。 第三章主要提出了一种基于交换技术的粒子群优化与改进遗传算法的混合聚 类算法。首先介绍改标准粒子群算法、改进遗传算法、k - m e a n s 聚类算法，再把交 换技术应用到p s o & i g a 算法中。由实验测试验证：此算法能结合两者的优点，能 很好的平衡聚类速度与聚类效果。 第四章主要提出一种基于粒子群优化与捕食一被捕食模糊聚类算法。首先描述 了捕食一被捕食问题，其次介绍采用密度函数的模糊c 一均值聚类算法等。重点研究 了基于捕食一被捕食粒子群优化的模糊聚类。最后是算法比较分析等。 第五章主要提出了基于粒子群与特征选择的聚类算法。首先介绍了特征选择 数据流聚类算法概述，引入性能指标的更新，特征等级的评定算法等，最后通过 实验测试进行算法比较分析，表明此算法能很好探测数据流的冗余，并且提高数 据聚类纯度等。 第六章为了更好满足用户需求，在数据流聚类过程中，特别是在离线部分， 需要有效地对聚类数据模式进行任意模式挖掘，以约简数据来提高聚类质量。在 本章中，提出了任意条件模式数据挖掘，介绍了条件模式定义与相关的性质，并 详细阐明了条件模式挖掘的算法设计等。 第七章总结了本文的主要的研究工作，阐明研究得难点和创新点，并提出今 后进一步研究的方向。 第二章经典的数据流聚类算法 聚类分析作为数据流挖掘的一个重要研究分支，这个研究领域很具有挑战性。 随着知识不断的更新，整个社会产生信息数据量越来越多，传统的数据挖掘算法 对聚类的典型要求有：能处理不同数据，数据处理具有可伸缩性，对于数据流到 来的顺序不敏感，能够识别噪声，输出结果具有可理解性，能发现任意数据形状 的聚类等。但是，由于数据流本身动态性、无限性的特点，使得传统的聚类算法 不能直接应用于数据流聚类。所以数据流聚类算法除了上面的要求外，还需要更 为严格的要求，例如，一次扫描数据集，有限的内存空间与储存空间，数据更新 的实时动态性，新簇的动态性表示，“奇异点”的动态的删除与否等。 2 1 数据流聚类算法研究现状 在数据流挖掘方面，特别在数据流聚类研究方面，吸引了广大数据挖掘的科研 工作者的注意。2 0 0 0 年，g u h a 等人提出针对数据流聚类的l o c a l s e a r c h 算法 【1 3 】，此算法中，将数据流聚类问题作为“大型数据库 聚类问题的一个特例，算 法的基本思想是基于分治策略，使用一个迭代过程对数据流进行k - m e a n s 聚类。 0 c a l l a g h a n 继承并发展了l o c a l s e a r c h 的思想，在2 0 0 2 年，他提出了并 移植到数据流环境的s t r e a m 算法【4 。s t r e a m 算法基本思想是采用批处理方式、分 级聚类的方法。此算法首先确定样本大小，每当数据块大小超过先前计算出来的 样本大小时，就采用l o c a l s e r a c h 算子进行聚类获取质心，最后采用 l o c a l s e r a c h 算子对质心进行聚类以获得最终结果。在使用的s t r e a m 算法就是 转化了问题域，采用分而治之的思想。s t r e a m 算法必须事前指定k ，聚类的数目 k 不能随意得变动，由于s t r e a m 算法是基于距离的，且只保留了中心点信息的数 据流聚类算法，所以对非球形状等复杂形状的聚类也无能为力，同时也造成很多 有价值的信息丢失。此算法在框架结构上属于经典单层算法结构，算法只能提供 对当前数据流的一种描述不能反映数据流的变化情况，与数据流聚类算法标准中 第5 条相违背【i 。 s t r e a m 算法是把数据流的动态模式转化为传统的静态模式，从而能够使用传 统的成熟方法解决数据流的问题。数据流聚类算法研究的重点必须突破传统算法 的模式，使之能够很好的适