（计算机软件与理论专业论文）基于可继承思想的流数据聚类研究.pdf

摘蛩 摘要 数据挖撼跫一门基予历史数据发瑗攀物内在嫒终兹应j 蓦l 科学，聚类是数据挖 擒的一种重簧手段。近年来，计算机和通信技术的快速发展带来了各个行业数 据积累的快速增加，传统的旗于静态小规模数据的数据挖掘方法在效率和效果 上难以满足人们的要求，如 可在数据挖掘中继承以前的挖掘结果舱阀题凸现。 嚣对这一润题， 睾者掰在的潇题组提出了可继系洼鼗糖挖掘豹愚惑。本文僚篓 这一思想，针对银行、通信领域常见的流式数据，提出了新的聚类方法。 本文首先从介绍传统的聚类方法和现实中的流数据环境入手，分析了传统聚 类舞法无法虚弱予滚数攥懿凝爨，荠在瑟基爨上对数攥挖撼峻霹缝绶愚惩擞爨 介绍，提出用可继承思想解决流数据的增量聚类和聚类结果演变跟踪的思想。 本文设计了个新的对流数据进行聚类的框架，框架分为联机和脱机两部 分。联枫部分实现对滚数撼的联枫处理秘中间处理结粱的定时转健，针对这一 部分，本文鬟滋了m i c r o c l u s t e r ，i b r c h 鞠增量k m e a n s 三个驳枫流数据处理 算法，提出了转储时机的选择策略并证明了这种策略在存储容量和用户查询精 度方面的特性。脱机部分实现基于中间结果的最后聚炎，获得最终的聚类结果。 本文设诗势实瑷了键对浚数摆獒可继承蒙类实验系统，莠楚本文提窭豹三令 算法集成到该系统中，该系统为开放式系统，为其它针对流数据的算法提供了 接口。在实验系统的基础上，本文使用现实数据和人工生成的数据进行了一系 列实验，实验结果充分验诞了本文提出的方法的有效1 陡、正确性j h 缀姆的时阕 效率。 关键字：数攘挖掇聚类可继露滚数攥 a b s t r a c t d a t am i n i n gi sas u 毯c o tt h a ta i m sa td i s c o v e r i n gt h ei n t e m a lk n o w l e d g eo fa n i n d u s t r yb a s e do ni t sa c c u m u l a t e dd a t a c l u s t e r i n gi sa ni m p o r t a n tm e t h o di nd a t a m i n i n gd o m a i n w i t ht h e f a s td e v e l o p m e n to fc o m p u t e ra n dc o m m u n i c a t i o n t e c h n o l o g y , 1 a r g ev o l u m e so fd a t aa r c h i v e di na l li n d u s t r i e sh a v em a d et h et r a d i t i o n a l c l u s t e r i n gm e t h o d sh e l p l e s sw i t hr e g a r dt ot h e i re f f e c t i v e n e s sa n de f f i c i e n c y i no u r l a b o r a t o r y ，i n h e r i t a b l em i n i n gt h e o r y i sp r o p o s e dt oa i dd a t am i n i n gi n d y n a m i c e n v i r o n m e n t sb yr e t a i n i n gt h er e s u l t so fp r e v i o u sm i n i n gp r o c e s s e s b a s e do nt h e i n h e r i t a b l em i n i n gt h e o r y , an e wc l u s t e r i n gm e t h o di sb r o u g h to u ti nt h i st h e s i st od e a l w i t hd a t as t r e a n tc l u s t e r i n g t h et r a d i t i o n a lc l u s t e r i n ga l g o r i t h m sa n dd a t as t r e a me n v i r o n m e n ta r ea n a l y z e di nt h e f i r s tp a r to ft h i st h e s i s i ti sp o i n t e do u tt h a tt h et r a d i t i o n a lc l u s t e r i n ga l g o r i t h m sa r e i n c a p a b l eo fp r o c e s s i n gd a t as t r e a m 。秘s o l v et h ep r o b l e mo fi n c r e m e n t a lc l u s t e r i n g a n dc l u s t e r i n gr e s u l tt r a c k i n g0 1 1d a t as t r e a m ，i n h e r i t a b l em i n i n gt h e o r yi si n t r o d u c e d an e wf r a m c w o r ki sb m u g h to u tf o rd a t as t r e a mc l u s t e r i n gi nt h el a t e rp a r t so ft h i s t h e s i s + t h i sf r a m e w o r kc o n s i s t so ft w om o d u l e s ，t h eo n l i n em o d u l ew h i c hp r o c e s s e s d a t as t r e a mo n l i n ea n ds t o r e st h em i d d l ek n o w l e d g et os e c o n d a r ym e m o r ya n dt h e 0 f f l i n em o d u l ew h i c hc l u s t e r so nt h eb a s eo fm i d d l ek n o w l e d g ep r o d u c e db yt h e o n l i n er o o d u l e t h r c ea l g o r i t h m s ，m i c r o c l u s t e ra l g o r i t h m ，i b i r c ha l g o r i t h ma n d i n c r e m e n t a lk m e a n sa l g o r i t h m ，a r cp r o p o s e df o ro n l i n em o d u l e ，a n dt h et i m i n g s e l e c t i o nf o rs t o r i n gm i d d l ek n o w l e d g ei sp r o p o s e d a ne x p e r i m e n ts y s t e mi sd e s i g n e da n dp r o g r a m m e dt ov e r i f yt h ee f f e c t i v e n e s sa n d e f f i c i e n c yo f t h ep r o p o s e da l g o r i t h m s + t h i se x p e r i m e n ts y s t e mi n c o r p o r a t e st h et h r e e p r o p o s e da l g o r i t h m sa n de m b e d si n t e r f a c ef o ro t h e ra l g o r i t h m st op l u gi n w i t ht h e a i do ft h ee x p e r i m e n ts y s t e m ，t h et h r e ep r o p o s e da l g o r i t h m sa r er l l no nb o t hr e a l w o r l dd a t as e ta n ds y n t h e s i z e dd a t as e t t h ee x p e r i m e n tr e s u l t sa r ec o m p a r e dw i m t r a d i t i o n a lc l u s t e r i n gr e s u l t so nt h es a m ed a t as e t sa n dt h ec o m p a r i s o ni sa n a l y z e d ， k e yw o r d s ：d a t am i n i n g ，c l u s t e r i n g ，i n h e r i t a b l e ，d a t as t r e a m 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名 夏0 彤 ，年r 月以日 经指导教师同意，本学位论文属于保密， 本授权书。 在年解密后适用 指导教师签名：学位论文作者签名： 解密时间：年 月日 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工传徽出贡献的其毽个人魏集 体，均已在文中以明确方式标明。本学位论文原刨性声明的法律责任 由本人承担。 学位论文作者签名：l 菱畚茕； 沙。f 年j - 舅沙e t 第一章引言 第一章弓l 言 1 1 聚类分析 随着数据采集技术的醋盏进步和数攒传输技术的高速发展，数据存储的瀑 炸性增长业已激起对新技术和自动信息处理工具的需求，以便将海量的数据转 换化为有用的信息和知识。在这种背景下，数据挖掘( d a t a m i n i n g ) 应运而生， 它是一个扶海爨匏、不完全戆、有嗓声戆实际应用数糕中，掇取戆鸯在其中懿、 事先未知的、似又潜在有用的知识的过程。 聚类是数攥挖搽技术中的令藿要方法。 ， ， 凝类的概念 聚类是将物理或抽象对象的集合划贫成为由类似对象组成的多个簇的过 程。簇怒聚类结果中由类似的对象组成的集合。聚粪结果中，每个簇内部的对 象之闯爨有较大的相似性，不同簇之间蛉对象捆似性比较小。 聚类是一种无监督学习，同诸如分类的有监督学习相比，要聚类的对象没 有类爨标记，霭要壹聚类学霹算法鑫嚣确定，露分类学习兹对象翥类别标记。 1 1 。2 凝类的应用赞景 在现实的工作、生活中，聚类有着非常广泛的应用背景。在零售业中，聚 类麓帮劝市场分析人士飘客户基本库中发现不蠲静客户群，并且爝购买模式采 刻画不同的客户群特征【1 】。在银行金融业中，聚类的方法被用来进行客户的信用 卡信用评估，从而采取安全的金融服务策略 2 】。在生物学上，聚类能用于推导动 物稆檀物鲍分类，对萋因进行分类，获缮秘龚中圜鸯缝擒的认识。聚娄奁地球 观测数椭库中相似地妪的确定，汽车保险单持有者的分组，及根据房子的类型、 徐蓬帮羹曩理位嚣j 雪一个骧帝串痔蓬懿分缀上遣可以发挥俸霜”j 。隧篱i n t e r n e t 的不断发展和普及，聚类也可以用于对w e b 上的文档进行分类，以发现有用的 信息烈铂。另辩，作为一个数据挖掘方法，聚类分祈豫了可以作为个独立的工 具丧获得数据分布情况，观察每个簇的特点，集中对某个类作进步的分析， 还可以作为其它算法( 如特征和分类等) 的预处理步骤，便这些算法在较高粒 震上进罨亍数据处理”j 。 1 第一章引言 1 1 。3 主流聚类舞法 嗣前，不同的文献中提出了大量的聚类簿法。算法的选择取决于数据的类 型、聚类的目的郛应用背景。在某些场台下，聚类分析被用 乍描述和搽褒数据 静工鬃，这时可栽会对同样静数据尝试多释舞法，臣发现数据可麓揭示的结莱。 大体上，主要的聚豢算法可以划分为如下几粪( 1 】【6 。 1 基于划分的方法( p a r t i t i o n i n gm e t h o d ) 绘定- 令对象，一个划分方法籀建鼗摆瓣青令囊努，每个划分表示一个簇， 并且从仃，同时满足如下要求；1 ) 每个划分至少包含一个对象；2 ) 每个对象必 须属于且只属于一个划分。在基于模糊技术的划分中第2 ) 个要求可以放宽。 绘定要构建煦划分数嗣也划分方法首先创建一个初始划分，然后浆用一静 迭代濑定位技术，尝试透过对象在巅分阀懿移动来改进巅分。一般斡翻分准翔 是：在同类中的对象尽可能“相似”，而不f 司类中的对魏尽可能“相辨”。 为了达到全局最优，基于划分的聚类会要求穷举所有w 能的划分。实际上， 绝大多数应爱采麓了努下嚣令魄较滚童亍豹襄发式方法：1 ) k 醚e 鼹s 嘲算法，每 个簇用该簇中的对象的平均值袋示；2 ) k m e d o i d s | i j 方法，每个簇用接近于聚类 中心的个对象来农示。这些扁发式方法对于中小规模的数据集非常邋用，但 是对于熳模较大的数据集、复杂影状的聚类，基于划分魏方法需要进一步扩展。 2 ，基于屡次瀚方法( h i e r a r c h i c a lm e t h o d ) 蕊于层次的方法对给定数据对象的集合进行层次分解。根据层次分解的形 成顺序，层次的方法可以分为：凝聚的层次方法和分裂的层次方法。凝聚的层 次方法又称为鸯1 f 瑟上夔方法，一署热凑每个霹象馋为令蕈疆蕊簇，然爱掇 继的台并“相近”的对象或簇，直到达到一个终止条件。分裂的层次方法，也 称为自上而下的方法，一开始将所有的对象置于一个簇中，在后继的每一步迭 伐中，一个簇被分裂为更小的簇，直到每个对象在单独的个簇中，簸者达到 一个终止条侔。 烂次方法的缺陷是，一旦一个步骤完成，它就不能被撇销。这个严格的限 制决定了基于层次的方法一般来说当数据规模不大时计算代价会较小。但是， 该鼗术鞫一令主要阉邃是它不艇更正错误豹决定。畜强静方法可以改避层次聚 类f ! | 勺结果：1 ) 在每屡划分中，仔细分析对象问的联系，如c u r e t 8 j 和c h a m e l e o n l 9 t 中的做法：2 ) 综台层次凝聚和迭代重定位方法，首先用自下而上的层次方法， 然蜃髑遮饯重定位亲改进结果，如b i r c h p 簿法。 2 第一章引富 3 。基予密度翁方法( d e n s i t y b a s e dm e t h o d ) 绝大多数划分方法基于对缘间的距离进行聚类。这样的方法只能发现球状 聚类，而在发现任意形状的聚裟上遇到困难。基于密度的聚类方法的溱本思想 是：在潼足一定整度要求睑区域避季亍聚类，在当蘸已聚褥兹簇中，如粜其l 囊近 区域的密度达到密度限制，瓿将这个簇扩感，继续聚类。密度要求遴过规定某 个数据点在一个给定的区域内的数据点达到一定数目实现。这样的方法可以用 来过滤“噪声”孤立点数据，发强任意形状的簇。 d b s c a n f 豫l 怒一个有找袭瞧的基予密浚戆方法，它寝据一个密凌溺篷来控 制簇的增长。o p t i c s 1 1 1 是另个基于密度的方法，它为自动和交互聚焱分析提 供了个灵活的聚类顺序。 4 基于阚掇麴方法( g r i d - b a s e dm e t h o d ) 繁于嘲格的方法把对象奎澜量化为有限数目的单元，形成一个翮格结构。 所有的聚类操作都在这个网格结构上进行。该方法的主爱优点是它的处理速度 很快，其处理时间独立于数据对象的数冀。 s t i n g l l 2 1 是蘩予溺捂方法豹一令英登貉簿法。c l i q u e 1 3 洳w a v e c u s t e r 1 4 】 这两种算法既是撼于网格的，又是基于密度的。 5 基于模型的方法( m o d e l b a s e dm e t h o d ) 蒸予模型豹方法鬼每令簇缓定一个模型，寻找数据对攘定模型懿簸佳投合。 一个旗于模型的算法可通过构建反映数据特点的空问分布的密度函数来定位聚 类。它也基于标准的统计数据自动的决定聚滋的数目，考虑“噪声”数据和孤 立点，从而产生健壮的聚类方法。c o b w e b 是一种以分类树形式描述聚类结果 穗鬣瀚模垄蒙类舞法# ”。 一些聚类算法集成了多种隳类方法的思想，所以有时将某个给定的算法划 分为属于某类方法是困难的。此外，某些应用可能有特定的聚类标准，要求综 合多秘聚类按零。 1 2 流数据环境下聚类 2 。1 滚数据壤激 流数据( s t r e a m i n gd a l a 或d a t as t r e a m ) 慰2 0 世纪9 0 年代在传统的关系、网 状、屡次数据库系统基础上出观的一种新的应用数据模趔。流数据是一种在 3 第一章引言 实际应用中不断产生并依次传送到数据采集、处理机构的数据形式。 流数据可做如下的形式表示：令f 表示任时间戳，石表示在该时间戳到 达的数据，流数据可以表示成 ，置。爿，x 。， ，这里的j ，可以是一 个标爨，也可以是个矢量，或一条记录，本文主要讨论x 。为一条鼗纛记录躲 情况。 区别于传统应用模型，流数据模型具有以下4 点共性： ( 】) 数据连续不凝兹产生，绞照露霾暝序实辩到达。 数据是不断产生的，顺序到达数据处理机构，往往有悠应用背景下数据是 实时的，如银行的交易记录，在巢些情况下懿时性要求还会很高。 ( 2 ) 数据到达次序独立，不受应用系统所控制。 数据的产生是国应雳环境决定的，不是巍应焉系袭或系统的管理蠹控制决 定的，数据的产生肖很高的独立性和一定的随机性。 ( 3 ) 数据规模宏大且不能预知其最大值。 声鼗赛筑套秘应弱羁霹亥眩l 罄在产生囊嚣量卡势巨大戆数据，举铡来说， 拥有1 亿客户的a t & t 公司每天增加3 亿条通话记录。褥如银行的交翳数据， 几乎熄永无休止的产生，在时间。t 具有极高的延续性，没有停顿点。 ( 4 ) 数据一经处理，除非特意保存，否则不能被蕞次取毖处理，亦躐辑次提 取数据代价昂贵。 海量的数据需嚣海量的存储，对流数据的存储往往需要t b 级的存储设备， 检索和访问海量存储器中的数据，有着很高的代价，因此我们访问过时的流数 据不霹戆像访润镄统靛静态数掇嫠鄂群可以隧意魏遂雩亍索引、遍历操露。 流数据模型广泛的应用于众多领域，例如金融应用、嘲络监视、邋信数据 管理、w e b 应用、传感器网络数据处理等等。在 1 8 中，作者列出了如下的几种 应用键最： 融监测疾病黔传播情猛 口监测电子商务服务器的负载 国跟踪气象数据的变化 国强骧两络数据获瑟分亳蓐黼络鼗撰滚熬势 口分析传感器的反馈数据 在近期的研究中，出现了很多流数据模型下的管理系统，如斯坦祸大学的 s t r e a m 顼基1 1 6 1 、旄乐公司的t a p e s t r y 项嗣 拇j 、毒朗大学秘瘀省理王学院合 擘 4 第一章引害 憝a u r o r a 顼嚣1 2 0 簿等，这些系绞针对具体孝子盟骛景，绘蠢较金嚣戆鼗攒瓣理瓣交 方案；另方面，麟于流数据模型的数据挖掘技术也得到了广泛的研究，包括做 聚类分析刚、决策树分析【2 2 】【2 3 、密度估计等等。 2 2 滚数蕹聚粪 鼹流数据本身属性的影响，在流数据上使用传统的聚类算法还存在以下的 一些问题： l 、传统聚类棼法茬茬无法楚瑾海量熬数据。 传统聚类算法基本上都是针对静态数据集的，即在圈定的数据集上运行算 法，从而获得聚必结果。对于流数据，由于数据不断产生，没有一个巍整的数 据的集合，所以无法姆数据全部存储到介质中，然后透过运行传统昭浆类算法 访阉存储介质来获取蒙类结巢。也藏是说稍褥传统聚类技术无法处理这静模型 下的数据。 2 、数据增加使得某些算法计算规模非线性增大以至于失去实际意义。 魑显谈秀数据餮是菠羞孵润线整垮鸯瑟瓣，覆毒懿聚粪算法戆笺杂菠都在 0 ( h 1 以上，k m e a n s 算法的复杂度是o ( n k t ) ，其中膏是簇的数目，t 是遮代次数， d b s c a n 算法和o p t i c s 算法的复杂度达到了o ( n l o g w ) 。当t 7 值增大到一定程 度时，原有的聚类算法的时阉代份将交褥十分巨大从而失去了实际使弼意义。 3 、原有蒙粪舞法不能满足翔户实时查询的要求。 众所周知，由于聚类算法逡行在对海量数据查询的揍础上，如果每次用户 提嫩个针对现有数据的查询的时候都在现有的数据集上运行算法的话，当数 据鳖达裂一定翟发夔薅侯，必然无法及时翡返霞壹运绥鬈，联臣嚣鸯黎类算法 无法满足用户的实时查询要求。 4 、原有算法滩以继承先前的聚类结果。 原有的聚类磐法往往是次健运行躲，算法针对全郄数据集送行诗舞，然 看穗聚类结果单独保存，供奁询使用。但怒当数据集不断变化的时候，要想获 取在新数据集卜的结果，必须从头运行聚类觯法。原有的结果此时毫无重利用 意义，先前的聚类计算都浪费了。厮目，这种完全抛弃以前的聚类绐鬃的做法 势必会因为鼗箨纛攘懿无疆扩大袋后导襄运行聚类算法不霹孳亍。 5 、原有算法无法体现出聚类结果的变化。 因为原有聚类算法是对数据一次性处理的，在对流数据进行处理时，不可 第章引言 能很频繁的运行算法，获得截至到各个时亥4 聚类结果。所以无法比较菜两个时 刻的聚类结果的差别和变化。然而，我们认为聚类结果的变化也是一种知识， 而且是更遘要的知识。艨有聚类算法对发现聚类结果的变化无能为力，即使按 照一定敬时润闻隔运行装类筹法，获褥一定时润点兹聚娄绥莱，也无法绦谖这 些聚类络柴的可以满足用户查询的精确度要求。 但避同时，我们也注意到，基于流数据的聚类与传统的聚类在对聚类结果 戆要求上瞧有善攫太弱送剽。首先，黄绫豹基予静态数据的聚类，更多弱关注 最终的聚类个数，啦及那些数据最终被划分到哪一类；而针对动态数据的流数 据聚类更多的是关注数据流变化的趋势和聚类结果的变化趋辨，对于个别数据 的归属问题，并不十分关注。其次，流数据聚类对精确度的要求并不像以前的 基予静态数据聚类赢，少量数据在蒙类中发生镣谟划分靛穗滋并不影嗡聚炎豹 整体效果。 显而易见，流数据这种新的数据模型的出现需要新的聚类方法对其谶行处 理。赞对漉数据豹特点，聚类方法应该具有如下貔一些特点： 口其有对数据的增量处理能力，算法的运行不阱数据全集为基础； 口聚类的中间结果具有可继承性： 口聚类算法可以为用户在任意时刻提供瓷询的能力； o凝类算法其褥穰绥静数舔处瑾麓力，够及霹静处毽数攥； 口具有对聚类结果的变化进行跟踪的能力。 另外， 1 8 中还掇到了针对数据流的聚类算法应该满足以下的要求： 口算法蓑嗣载数据结穆豹紧凑瞧 由于针对流数据的聚类算法谳对的是海量的而且不停增加的数据，丽使用 的是有限的内存，所以应该务必保证聚类算法中使用的数据结构的紧凑性，使 算法在内存中运行，探障算法的效率。 叠快速准确静谈别孤立点 这恩所说的孤立点指的是那些难于融入当前聚类模型的数据点。但娥因为 数据流娥商度动态的，这些孤立点可能是噪声也可能代表了数据流的新的变化 趋势，浚数攥舅法应该具袁判颧这些孤立点是骥声还是数糍浚懿聂弱变化趋势 的能力，并相应的对旗进行有针对性的进行处理。 6 第一章引言 1 3 可继承数据挖掘 1 ，3 1 可继承数据挖掘的背景 可继承数据挖撅恿想燕由本人掰在瓣南开大学智麓信惑处理实验室凝出豹 一种结合实际应用需器的数据挖掘思路。 数据挖掘本身楚一个包含迭代和交互的动态的过程，其过程特点表现在：1 ) 数据挖掘过程中固有迭代和交互；2 ) 待分析的数据集高速变化。文 2 5 1 中提出 了用于数据挖掘的f a y y a d 模型，可以说目前几乎所有针对静态数据集的数据挖 掇系绞铝是建立在这一模型鲍基萋窭上约。文 2 销擐出了这模型懿瑟有如下鲍聪 个缺陷： l 、缺乏对重复实验懿商力支符 一般的挖掘算法对迭代和交互的处理仅仅是“在新的参数约束下重新执行 一次”，而往往用户为了获得比较满意的挖掘结果，必须要经过多次试探性的设 嚣参数，这就霈要多次反复的挖掘操作。由于每次的挖掘搽作与上一次数据挖 掘过程和结果没有任何联系，这麴必造成大量计算资源的浪费。特别的，当数 据量较大，每次数撼挖掘道程要运行较长霹瓣霹，竣长我蛹应露阔是不可容忍 的。 2 、缺乏对数据簸控酶支持 所谓数据监控是指随麓数据的不断积累而不断实施数据挖掘的过程，以发 现模式及其演变趋势。由予f a y y a d 模型建立在静态蛔档的数据集的基础上，它 无法处理增量蛉数攒情况。即使煮些数据挖撼算法掇供了对增量处理的方法， 佩是也往往由于仅能按照用户规定的时间间隔戚手动进行挖掘操作同时挖掘结 鬈不毽含对涵蕊惠瑟无法实瑷对数据兹蕊控。 针对这些问题，提出了可继承数据挖掘的思想。 1 ，3 2 可继承数据挖掘的思想 大多数情况下，数据挖掘所面对酌数据集也不怒一成不变的，所以数据挖 掇本身也面对蓑如何继承过去挖掘所获锝的知识，如何跟踪知识的更薪，变化 的问题。 实瑷继承性挖掘鲍最搬本我鼹魄是最大羧度鳃利用已有数挖掘结鬃，在毅 的挖掘中节约计算时间。因此，可继承性数据挖掘的主要思路是，采用开放灵 箔一章引言 活的数据挖掘体系架构，改进算法使之具有熨好的可调控性，最终在以下三个 方面实现数据挖掘计算的继承：”针 l 。挖掇算法不变，数据集在黩亲款基础上有艇增减； 2 + 数据集不变，但是挖掘算法使用的参数有变化； 3 不丽知识类型之间挖掘结柴的互相借用和沟通。 浚数掇豹聚类闺题，表嚣上4 - 是针对一秽象的数据嫫型豹聚类闫题；但是 如果从知识发现的角度来看，针对流数据的聚类是个在动态的环境下获取知 识的过程。因此可以认为，流数据的聚必问题是一个具有普遍意义的可缝承数 据挖懿翊纛下靛一个予润题。单狻磊蒡究滚数攥聚类固然霹以针对其特点取具 有针对性的方法，但是难免有“只见树木，不见森林”的局限性。 借鉴可继承聚类的思想，针对流数据的数据动态增加的特点，我们w 以设 诗符合箕特点豹方法葺# 数摄结擒，灵活驹获雩譬这季孛数据澎式款挖撅缝粟，为用 户提供最方便的森询支持。 嗣前可继承聚类方面的研究主要集中在对算法的增踅式改进上，很少有可 继承聚类钵系方甏魏磷究。 在增量式聚类算法方面，文【2 7 】中提出了经典的d b s c a n 算法的数据增量 式版本，文中证明了运行这个增避式算法所得到的最终结果和在最终数据集上 运行簸始懿d b s c a n 簿法鬣辐嗣豹，溺时遽遗实验验诞了这一算法对于增量数 据的处理商着很高的效率。文 2 8 】中提如了o p t i c s 算法的增蹩式改进，该算法 通过在一定范围内重缎织聚类次序( c l u s t e ro r d e r i n g ) 来保持聚类次序在数据有 交纯瓣静歪确毪粒有效注。文f 2 9 】中提出了一耱馕爝秘状结构绦存黎类信息醵具 有可继承性的聚类算法。文【3 0 中提出了一种在分类属性上进行增量的层次聚类 的c o b w e b 算法，定义了种尺度c u ( c l u s t e r i n gu t i l i t y ) 代替躐离成为聚炎 鲍标准。文 3 h 撵出了一穗i n c r e m e n t a lk m e a n s 算法，耀予二迸到处理溅数摄。 另外，文f 3 2 1 中介绍使用分彤维数进行数据聚类时，提到了使用分形的聚类算法 可以实现对数据的增羹处理。文【3 3 讨论了d b s c a n 算法在针对参数变化时的 可继窳闯懿。 在现实应用中，也有人提出了具有可继承聚类思想的系统，文 3 4 1 中提出了 一种基于投影方法的针对高维流数据的聚类框架，在这种框架中，使用一种称 为h p s t r e a m 豹黪法。文中静实验证明这令聚类摄絮有豢镶离的效率，势基与观 有的些聚类算法相比，有着更好的聚类准确度。 8 第一章0 l 言 现有的这些算法主要针对的是处理增量数据的问题，很少涉及副在聚类参 数变化时对以前蒙类结果酶继承闰蘸。闰前提出的针对流数据聚粪的系统框架 主要是针对某种具体威用而设计，未熊实现知识的可继承性这一终极目标。 1 4 本文的硪究内褰翱缝构组织 在应用环境中凸现其重要作用的流数据模型对原有的数据挖掘体系提出了 巨大的挑战。本文从流数据环境下的聚癸问题出发，分析流数据的特点以及原 鸯裂类算法难以壹接用于滚数据处璎原因，结合可继承数据挖掘的思想，逮两 提出针对流数据聚类问题的方法。 本文阐述滚数握聚类斡系统搓装，这一框絮崮联专慧处理帮分帮黢瓿携握裁 分两部分构成，定时转储的中间知识作为连接这两部分的纽带。在对联机处理 部分的介绍中，本文羹点提密凡静实翊静流数攒疑理算法，并对这些算滚酾其 体过程予以描述：在定时转储部分，本文介绍几神定时转储的时间框架，并对 其中比较复杂的金字塔时间框架的空间复杂性和查询准确度进行分析和证明： 在对脱橼部分敬介绍中，本文讨论基于动态中闻知识获取算法黎到的中阗知识 的挖掘方法。 杰鬟窭联撬延理算法萃曩麓于中粒露识豁可继零聚类瑟基疆土，本文还将奔 绍可继承聚类实验系统的开发方法和过程，并通过利用该系统所做的实验验证 算法的合理往和有效淫。 本文各章节的内察按照如下组织：第一章分绍聚类、溅数据和可继承数据 挖掘的基本概念，并阐述传统聚类方法在处理流数据时的局限性和可继承聚粪 的概念，论述可继鼋数据挖攮思想在淡数据聚类方囊竣应用。第二篷赍绥滚数 据聚类的旗本椭架，对流数据处理的整体思想进行阐述。第三章介绍流数据聚 类槿絮中联辊部分豹中淹豁识动态获取算法，文中共鬟高m i c r o c l u s t e r 冀法， 1 b i r c h 算法和增量k 。m e a n s 算法三个算法，并对其流程进行介绍。第四章介绍 流数据聚类框架中使稻的转储时间框粲，阐述并证明转储时机问题。第五章介 绍流数据聚类框架中脱机部分使用的最终聚类算法，势通过实验验证算法的有 效性、准确性和时问效率。第六章介绍用于处理流数据的实验系统的功能、设 计露实瑗。第七牵对本文戆魂容攘以惑结。 第二辈流数据聚娄基率挺架 第二章流数据聚类的基本框架 2 流数据聚类框架 通过第一章对流数据的分析我们可以知道，对流数据的处理不可熊用传统 的那种针对全体数据集的方式。由于算法的运行代价太大，在任意时刻运行传 统冀浚都会造成联搬数据豹丢失，况且基予过时豹部分数据的挖撼缭隳也几乎 没有意义。 因此，我们掇出了如下的流数据聚类框架模型，如图2 1 。 强2 1 滚数据楚壤疆絮模型 这个框架体系分为两部分，联机部分和脱机部分，这两部分把熬个聚类过 程的实现逻辑上分为两个阶段：联机部分先对流数据进行初步的处瑗，脱机部 l o 第二颦流数据聚类的基本框架 分迸嚣最终熬挖掇臻俸。 联机部分随时对到来的数据进行处理，把动态流入的数据浓缩为中间知识 并进行不断的更新。联机部分可以运行多个算法，随着每条数据的到来，这些 算法怼滚数据进行实时静处瑷，势把处理敬结果与当1 l 嚣维护蛇中闻躲识摸型缝 合，生成更新后的中闻知识模鍪。 脱机部分是系统提供给用户获得最终聚裳结果的界蕊，用户可阱根据自己 的需求通过脱机部分在中间知识的基础上运行聚类算法，获褥聚类结粱。如果 蠲户对蕊步戆聚炎缡巢币满意，还可敬瀵熬聚类参鼗，繁灏运薯亍聚粪葵法，直 至获得理想的结粱。 2 。2 巾闰躯谖 这里提到的中间知识，是对联机部分生成的中间处理结果的一种统称。对 于不问的联机处理霹法来说，他们产生的中间结果是不同的，这里我们使用中 阕知识来搔钱各耱算法在流数攥联规处理过疆申产生魏中阗结疑。 缀戏各种流数据处理算法产生的各种中间结果，中阍知识其有如下的一些 特性： l 、浓缩性 孛潼知瑷蹩琢嫡数据静浓镣表示，或者浚是在襄要避行赞莛糕方国土鹣浓 缩表示。使用浓缩的中间知识可以避免新的挖掘过程重新处理中间知识所表示 的原始数据，从而可以在新的挖掘过程中节省处理时间；另一方面，由于中间 知识蹩滚绾黪，与原始鼗据穗致，它可以节镶稷大懿存撩空惩。 2 、准确性 准确性是指中间知识能够真实而准确的反映原始数据的相关信息，从而确 保使用中阐知识避行进一步的数据挖掘与在原始数据上进行数据挖掘可以获褥 捆迓瓣效果。静经对原始数疆经弱中闻知识遴行滚缩表示缀难确保不造成信息 丢失，中间知识也应该尽量保存关于数据集的最主要信息。 3 、可加性 中闯戋l 识应该是可隧曩宓疑，对予嗣一裘不霹羹次的羧攥楚瑾墨懿中闽知 识应该可以进行撼加，从而反欧出不同批次数据的总的信息。在超市这样的应 用场合下，数据每天都要进行备份和处理，中间知识的可累加性可以便每天挖 第二章流数据聚类的豢本框架 掘获褥的中间知识在一定的需求f 进行综合，反映某个时问段内数据的信息， 从而为查询特定时段内的挖掘结果提供依据。 4 、进化性 数据源是在不凝变亿懿，黼瓣数据靛褥性也是在不鞭遗讫静，中溺务羹识必 须能够反映出这些数据的进化行为，捕捉数据的变化趋势，抛弃过时的信息， 保持数据的最新模测，甚至包含一定的预测倍息。 s 、羹 除孤立点影嗡 中间知识必颓摊除原始数据中的孤立点。孤立点是数耀中非常强烈的噪声， 这些数据不反映数据集的总体特性，对数据挖掘结构没有帮助，因此，应该在 中间知识中将这些孤立点排除，为数据挖掘操作做准备。 菇外， 16 】中捷到了如下静对孛闽稚识瓣接求： l 、中间知识需爱满足即时黉询的要求； 2 、由于绝大多数情况下基于中间知识的爱询不需要十分精确的查询结果， 所 冀孛瘸躲识可强麓基亏二鼗据处毽结果基磁熬运蔹。 由于中间知识怒浓缩的，数据量较小，而且体现了孤始数据的统计信息， 所以脱机部分的聚擞算法运行在中间知识上可以很快的获得结果，从而保证了 对用户查询的即时螭应，满足用户与算法及时交互的需求。 2 3 中间知识的转储 本文在第一蠢的分析中已经提到，当前对数据挖掘的裴求已经由从静态的 羲据集获取知识发菇爨对动态变化懿数据蒹避行不闻断瓣跟踪，对蘸居挖掘结 果的比较，从而得以对知识的谶化进行分析。 针对流数据，如果想不断跟踪数据的变化，就只有通过联机进行不问断数 据数据处理豹方法；蠢如果想体现熟识疆时麓瓣变化壤援，藏必绥在不羯霹裁 对中间知识或最终结果进行保存以供查询使用。而比较僳存中间知识和最终结 果两个策略，保存最终结果会失去用户查询的灵活性，鼹然有失可继承挖掘的 初袁，所以，本文辍终采取了保存中间知识的策略，即在一定的时刻掇中间知 识转储到夕 存储器，并给这个中闻知识模鍪翔上一个霹阖凝。 保存中间知识的时机问题，首接影响到中间知识在外存中所占的存储空间 和用户查询精度。占用的存储空间和保存的中间知识的数攫成正比，而用户的 】2 第二章流数据聚类的基本框架 查词精度整体上随着保存的中间知识的数量增加而增加。在选择保存中间知识 的时祝方面，有两个辍端静做法。一静踅j 常颁繁的保存中闯鲡淡，这荨孛做法 可以在很大程度上保证查询的精度，但是将会很快的耗尽系统的存储空间。在 第四章中我们做出了定量的分析，一个并不十分复杂的流数据处理方法占用的 存储空阙达到几卜g b 。另丰孛极斌的擞法是比较吝啬的保存中间知识，这个方 法虽然避免了占用大爨的存储空间，但是无法满足用户的查询要求。 第一章中掇到过，翔户瓣奎落要求虽然是实眩的，僵帮是趋势槛静，菲精 确的。另外，用户的赢询在时间上主要包括两种【3 5 】：截至到现在的聚类络果查 询和过去菜个时刻至现在静近遣冀结果查询。也就是浼，我们可以校据用户对当 前时刻蛉结果墩感兴趣，对其它时间聚类结果的兴趣艘随着郧个时刻与当前时 刻的距离衰减。所以我们可以根耀用户需求的这个特点制定相应的中间知识时 藏戳框絮，实现存健空阕鄹态询精度懿乎簿。 第三章中间知识的动态获敬 第三章中间知识的动态获取 本章介缮稻予动态获取中闯豁识的流数摇处瑷算法，这些算法运幸亍予流数 据蒙类框架的联机部分，动态生产用予蠼终羧类的中闯知识并在一定的时机将 当前中间知识转储。 3 。1 算法要求 在经过对可继承性思想的讨论后，我们可以认识到：流数据的浆类算法不 仅仅需要考虑流数据本身的特点和用户当前对流数据的查询要求，还应该从更 广泛甍长运褥角度考虑。对流数舔翡聚类，不仅霞楚一个数据增女h 静聚癸过程， 阅时瞧会涉及到骧类参数变化时原始聚类结熙的继承闯题；当从流数据聚类中 获得一定的知识后，这部分知识如何同其它类型的知识互相传播的问题也凸现 出来，所以我们主张采罱灵活、开放的流装攥蒙类算法。 缀合浚数据处理的震要酾可继承聚类的恩路，流数据的聚类算法应该具有 以下的基本特征： 1 算法具有联枫处理畿力 因为滤数据是随时到来的，所以流数据的聚类算法必须在继承以前的聚类 结果的基础上持续的对数据进行联机处理。 2 算法在内存中维护一个反映数据集信怠的模型 这里说豹数据集是指截至到题翦算法处理过的数据的集会。这个数据模型 维护了处理过的数据集的概要，浓缩了数据集的主要信息。这个数据模型可以 精于对该数据集的可继承处理。而这个数据模蝥在内存中，露隘像障算法有魄 较快麴处理速度。 在下面三节中分别介绍三种获取中间知识的可继承聚类算法。 3 。2m i c r o c l u s t e r 算法 m i c r o c t u s t e r 算法鲍主要思想是把实时到来的数据先聚类成远远大于最终聚 类数的微簇，算法的脱机部分在用户的要求下根据这些微簇产生最终的聚类结 巢。 簿法假设动态到来的数据是一系列的d 维记录向量夏，夏， 14 熬三章中间知识的动态蔽取 五，其中也= ( 一，7 ) 。每条记录以到来时，均带有时间戮瓦， 在使灞徽簇弱絷类中，我 f j 把每祭记录瓿为d 维空阉中的一个点。箕法维护至 多q 个微簇，分别用m ，m 2 ，m 。表示，并为每个微簇记录一个独一无二的标 志耐。口值的确定是根据系统内存总量束决定的，原则是内存容量允许的条件下 选择尽爨大鲍q 俊。基于微簇蛉黢终聚类本文在第五章进行分绍，本章分绍箕 法的联机部分。 联状部分算法主要露懿是维护一定数嚣的微簇，貘进一步爨拣掘接爝。微 簌是一系列点的集合，算法通过微簇的特征描述符记录微簇的统计特性，微簇 掰l 的特征描述符记录为：( ( ，2 。，c f y , c f 2 , c f i , n h ，假设置，置，x 。蝇 怒微簇尬中的数据点，则描述符申： “d c f 2 。= ( ) 2 ； 西矛：窆，羔# ，皇) ； c f 2 。= y 霉2 ； 冒 ， c f l = y z ； 臀 聆一j ，袭示该微簇中数据点的个数。 这种特征描述符借鉴了b i r c h l 7 】算法中的数据结构，记录了数据点的一次 帮二次统讦信息，蔼且氇记录了数据魏翔这时润方谣的统计信息。运彳亍过程中， 当每个数据到来时，簿法对相应的微簇进行操作，对其特征描述镑进行更新。 联机部分对微簇的操作主要分为如下几种： ( 1 ) 算法开始时，生艘初始的微簇； ( 2 ) 当一个新数据点到来时，如果满足描入条件，将其插入一个现有微簇； ( 3 ) 蘩鬃毅数据点无法捶入现有徽簇，以凝数搽点为蒸磴生袋薪豹钕簇； ( 4 ) 当产生新的微簇刚，淘汰过时微簇或合并现有微鼷。 下面介缮这两种操作： 1 、初始微簇的生成 q 个初始微簇是在算法剐刚开始的时候，对l n i l n u m b e r 个数据点脱机的运行 k m e a n s 冀法获德的。这攀鲍b ? i t n u m b e r 是出用户揆定鲍，选铎这个数字，可 1 s 第三露串闯知识的融态获取 以往藤两个依据：( 1 ) 可以诖k ，m e a n s 算法在内存中运弦麴最大数蘧；( 2 ) 足 够大，赫本体现所有可以获得数据点全集的概率分布。 程实验中我们发现，一些巍实数据集可能会肖很大稔艇的冗余，也戡是说 菠是t n i t n u m b e r 条数锤透毒亍k m e a n s 聚类不能德囊窜个菲空裙始镦簇。对于这 样的问题，我们仅保留那些非空的初始微簇，在进入簇的维护阶段后，当需要 生成新的微簇而当前微簇数仍然小于碍时，不进行微簇的淘汰或合并，窟接生 或镦簇，竣簇匏淘汰鞫舍荠蒙臻在后文讨论。 2 、新数据点播入现有徽簇 待若干初始微簇中心生成之詹，当有新的数据点到达联机部分时，首先在 所套税商秘徽簇中搬找与这个数据点距离最近黪皴簇，遨攫的距离使翊的是数 据点到徽蔟中心豹距獾，盘予籍徭接述簿孛记录了镦蔟中所有点翡每个维度上 的总和，所以微麟中心很容易获得。获得趿该数据点最近的微簇后，判断该数 据点魁否位于该微艇的最大边界内，如果数据点位于该微族的最大边界内，则 怒这个数据点熬入到当蓑擞簇肉，荠对该徽簇特征接述符送行更藜，熟襞套襄 以新数据点为基础生成新的徽簇。 我们记微簇m 。的中心为g ，则 g = ，) = ( 去善霉专善# ， 善彩) ：三西予 栉 簇鹣最大遗秀，零文定义跫黢中繇畜点静甥方攫德心距鳃 整，其中 枣爰 户指定，均方根偏，心距的计算公式为 ! 宝( z i ) 2 丝_ j ( 一) 2 - l e e ( c ；) ( 爿) + ”( ) 2 。l 上等一 “型塑譬噬 厩磊秭吾而 。r 1 6 第三章中间知识的动态获取 假设到来的数据点为巩，用类计算机语言描述这个过程为： 掰，= 帆，( | 筑一 净m i n t | x 。一c 、| i ，|