（计算机科学与技术专业论文）基于滑动窗口的xml数据流的聚类算法研究与实现.pdf

黪嚣 1 1 ； 独创性声明 l i i ii i ii iii i i iii i iii il y 17 8 8 8 4 9 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 签名：壑醯 同期：醴! ! ：璺 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：继导师签名：日期：塑鱼：! ! ! 兰 ： c j 一窭 ：#，一蛰， 摘要 摘要 x m l 是一种用于数据交换和共享的自描述语言，已经成为互联网上数据表 示和数据交换的标准。在数据传输及交换过程中，许多结构化或半结构化数据都 以x m l 格式来表示，由此产生了大量的x m l 数据。该数据是一种按时间顺序 无限到达的实时数据，我们称之为l 数据流。 对x m l 数据流进行知识挖掘，是一个重要的研究课题，同时也面临着很多 挑战。为了从x m l 数据流中发掘出有用的知识，众多研究者主要集中于x m l 数据的聚类挖掘，并提出了大量的x m l 聚类算法。但现有的x m l 数据聚类算 法主要用于静态数据集的处理，一般需要多次反复的文档读取和解析，并没有考 虑随时间变化的在线聚类研究。 本文针对上述问题，提出了一种基于滑动窗口的x m l 数据流聚类算法。 首先，以时间聚类特征为基础，采用层次结构的方法，来表示x m l 文档的 概要数据结构。这种表示方法较好的完成了对x m l 文档结构信息的提取和文档 间相似度的计算。 其次，采用滑动面口模型，以x m l 聚类特征指数直方图为该窗口中的一个 微簇，来动态的接纳“新”的数据，淘汰“旧”的数据，从而较好的保存当前窗 口内的数据流分布特征。 最后，在y d v i l 真实和模拟数据集上的实验结果表明：本文提出的算法不仅 可以达到实时在线聚类的要求，而且可以获得较高的聚类质量和较快的处理速 度。 关键词x m l 数据流；聚类；指数直方图；滑动窗口 北京t 业大学工学硕 ：学位论文 ， 、 。鸷 幽一 a b s t r a c t a b s t r a o t x m l l a n g u a g ei sas e l f - d e s c r i p t i o nl a n g u a g e ，w h i c hi su s e df o rd a t ae x c h a n g i n g a n dd a t as h a r i n g , h a sb e c o m et h es t a n d a r do fd a t ar e p r e s e n t a t i o na n dd a t ae x c h a n g e o n l ei n t e m e t i nt h ep r o c e s s i n go fd a t at r a n s m i s s i o na n de x c h a n g e ，m a n ys t r u c t u r e d 0 rs 锄i s t r u c t u r e dd a t aa r ep r e s e n t e da n dt r a n s m i t t e di nx m lf o r m ，弱ar e s u l t g e n e r a t e sal a r g en u m b e ro fx m l d a t a t h ed a t aa r er e a lr e a l t i m ed a t aw i t ht i m e ；w e c a l li ta sx m ld a t as t r e a m d i s c o v e r i n gt h eu s e f u lk n o w l e d g ef r o mt h ex m l d a t as t r e a m s ，i sa ni m p o r t a n t r e s e a r c ht o p i c ，b u ta l s of a c e sm a n yc h a l l e n g e s i no r d e rt od i s c o v e rm o r eu s e f u l k n o w l e d g e , m a n yr e s e a r c h e r sf o c u s o nt h ex m ld a t ac l u s t e r i n g , a n dp r o p o s ea n u m b e ro fx m lc l u s t e r i n ga l g o r i t h m h o w e v e r , e x i s t i n gx m l d a t ac l u s t e r i n g a l g o r i t h m sa r em a i n l yu s e df o rs t a t i cd a t as e t s ，a n dg e n e r a l l yn e e dt or e p e a t e d l y r e a d a n dp a r s et h ed o c u m e n tm a n yt i m e s ，w h i c hd i d n tc o n s i d e rt h et i m e - v a r y i n go n l i n e c l u s t e r i n gx m l d a t as t r e a m s t os o l v et h ea b o v ep r o b l e m s ，t h i sp a p e rp r o p o s e da na l g o r i t h mf o rc l u s t e r i n g x m ld a t as t r e a mu s i n gs l i d i n gw i n d o w f i r s t l y , w eu s e t h eh i e r a r c h ys t r u c t u r et oe x p r e s st h es u m m a r yd a t as t r u c t u r eo f x m ld o c u n l e n t ，w h i c hi sb a s e do nt h et i m ec l u s t e r i n gf e a t u r e s t h es t r u c t u r ei sb e t t e r 触m ee x t r a c t i o no fx 2 c l ld o c u m e n ts t r u c t u r ei n f o r m a t i o na n df o rt h ec a l c u l a t i o no f s i m i l a r i t yb e t w e e nd o c u m e n t s s e c o n d l y , w eu s et h es l i d i n gw i n d o wm o d e l ，w h i c ha d o p t se x p o n e n t i a lh i s t o g r a m o fx m le l u s t e rf e a t u r ea sam i c r o c l u s t e ro fi t u s i n gt h em o d e l ，w ec a nd y n a m i c a l l y a c c 印tt h e ”n e w ”d a t a ，g e tr i do ft h e “o l d ”d a t a ，a n dg e t ab e t t e rd i s t r i b u t i o nf e a t u r e s o ft h ec u r r e n tw i n d o w f i n a l l y , t h ee x p e r i m e n t a lr e s u l t sb a s e do nx m l r e a la n ds i m u l a t e dd a t as e t s s h o wt h a t ：o u ra l g o d t h mn o to n l ya c h i e v e st h er e a l t i m er e q u i r e m e n t so ft h eo n l i n e c l u s t e r i n g , b u ta l s og e t sah i g h e rc l u s t e r i n gq u a l i t ya n d af a s t e rp r o c e s s i n gs p e e d k e y w o r d s x m ld a t as t r e a m ；c l u s t e r i n g ；e x p o n e n t i a lh i s t o g r a m ；s l i d i n gw i n d o w 北京t 业大学t 学硕七学位论文 i v ? 一 矗 炒 目录 目录 摘要”i a b s t r a c t i i i 第l 章绪论1 1 1 数据流挖掘技术简介一l 1 2 研究背景与意义3 1 3 国内外研究现状5 1 3 1 传统数据流聚类研究5 1 3 2x m l 文档聚类研究6 1 4 本文主要研究内容“7 1 5 本文的组织结构8 第2 章相关理论与关键技术9 2 1 静态数据聚类9 2 2 数据流聚类lo 2 2 1 数据流1o 2 2 2 数据流处理模型1 1 2 2 3 滑动窗口1 2 2 2 4 概要数据结构1 2 2 3x m l 1 3 2 3 1x m l 简介1 3 2 - 3 2x m l 数据流16 2 4 本章小结1 6 第3 章基于滑动窗口的x m l 数据流聚类算法1 7 3 1x m l 的层次结构1 8 3 1 1 层次结构的特征”1 8 3 1 2 层次结构的合并- 19 3 1 3 层次结构的相似度计算2 0 3 2x m l 聚类特征指数直方图“2 2 3 2 1x m l 聚类特征指数直方图的生成2 2 3 2 2x m l 聚类特征指数直方图的维护2 3 3 2 3 基于滑动窗口的x m l 数据流聚类算法2 4 3 3 本章小结2 7 第4 章算法的实现与实验结果的分析一2 9 4 1 实验环境2 9 4 2 实验数据2 9 4 3 实验方案及评测标准2 9 4 4 实验结果及分析3 0 4 4 1 聚类质量3 0 4 4 2 参数的影响31 4 4 3 处理时间3 2 v 北京工业大学工学硕十学位论文 4 5 本章小结3 3 结论”3 5 参考文献”3 7 攻读硕士学位期间发表的学术论文“4 l 致j 射4 3 ， ： 掣“ 第1 章绪论 第l 章绪论 1 1 数据流挖掘技术简介 作为统计学、人工智能、机器学习等学科的交叉学科，数据挖掘近年来正逐 渐成为研究热点，各种数据挖掘技术相继被提出并广泛运用，以达到从大量复杂 资料中获取有用信息的目的。 近年来，由于硬件技术的高速发展，人们获取数据的能力得到了极大的提高。 在现实生活中，大量需要处理的数据以很快的速度产生，而这些数据的量太大、 数据产生的速度太快，按传统的数据库应用模式已经达不到处理这些数据的要 求。 为了有效的分析和管理这种大量的快速的数据，人们提出了一种流的解决方 案。这些方案最大的特点是，待处理的数据不再静态，固定地存储在可多次，随 机访问的介质中，而是以一种动态的流式的形式出现，也就是数据流( d a t a s t r e a m ) 。 如何从这些连续不断的数据流中挖掘有用的信息，正变成我们需要面 对的新考验。 数据流模型区别于传统的数据模型最主要有以下3 个特点： ( 1 ) 数据高速到达，实时性要求高。 ( 2 ) 数据规模宏大，不可能把所有的数据都放入内存甚至是硬盘。 ( 3 ) 数据一经处理，除非特意保存，否则不能被再次取出处理，或者再次提 取数据代价昂贵。 传统的数据挖掘方法，必须将数据全部存储到介质中，然后通过访问存储介 质进行挖掘。由于数据流的快速到达和数据规模巨大等原因，传统数据挖掘技术 难以满足其要求。数据流是现象驱动的，其速度与数据项到达的次序无法被控制。 数据流通常具有潜在无限的体积，且数据可能的取值是无限的，处理数据流的系 统无法保存整个数据流。而数据流的在线处理要求又使系统无法进行代价昂贵的 磁盘存取。因此，数据流中的数据项在被读取一次之后，就被丢弃，以后不可能 再读到。 因此，如何根据数据流的特点建立其相应的数据流模型，并且其数据模型还 要随着数据流的变化而改变，就成为当前数据挖掘研究领域的一项研究热点。 数据流实时、连续、有序、快速到达的特点以及在线分析的应用需求，对流 数据挖掘算法提出了诸多挑战。数据流对挖掘算法的典型要求如下： ( 1 ) 单次线性扫描。即算法只能按数据的流入顺序依次读取数据一次。 ( 2 ) 低的时间复杂度。数据流算法是在线处理算法，为了跟上数据流的流速， 算法处理每个数据项的时间不能太长，必须保证对数据的处理速度，最好能为常 】 北京丁业大学t 学硕仁学位论文 数时间。 ( 3 ) 低的空间复杂度。数据流算法是主存算法，其可用的空间是有限的，算 法的空间复杂度不能随数据量无限增长。 ( 4 ) 能在理论上保证计算结果具有好的近似程度。 ( 5 ) 能适应动态变化的数据与流速。产生数据的现象可能在不断变化，导致 数据内容与流速的改变。 ( 6 ) 能有效处理噪音与空值。这是一个具有健壮的算法所必须具有的能力。 ( 7 ) 能作o nd e m a n d 的挖掘。即能响应用户在线提出的任意时问段内的挖掘 请求。 ( 8 ) 能作a n y t i m e 的回答。即算法在任何时刻都能给出当前数据的挖掘结果。 ( 9 ) 建立的概要数据结构具有通用性。算法所构建的概要数据结构不仅能支 持算法当前的目标计算，而且能支持其他的计算。 在上述要求中，单次扫描和低的时间复杂度是一个流数据挖掘算法所必须满 足的。早期的流数据挖掘算法都是以这三项为目标设计的。对于算法的空间复杂 度，理想的情况是它与数据流长度无关。但是，目前大部分问题都无法找到这样 的解。 近似性与自适应性是数据流算法的两大特点。由于一次线性扫描以及时间与 空间的限制，数据流算法往往只能得到对所处理的问题的近似计算结果。能在理 论上保证其计算结果的近似程度，是算法应该考虑的一个问题。算法的自适应性 是指当流数据内容或流速受各种因素的影响而发生改变时，算法能够根据这些改 变自动调整计算策略与计算结果。 噪音与空值是一个健壮的算法所必须解决的问题。对于流数据挖掘算法，这 个问题显得更为突出。这是因为在挖掘数据库中的静态数据集之前，通常会进行 数据的预处理，消除数据中的噪音与空值。而在在线进行的流数据挖掘过程中， 无法在挖掘前对数据进行预处理。而且数据流中的数据在采集以及传输过程中， 都可能出现错误，产生噪音或空值。数据流的动态变化性更进一步增加了噪音识 别的困难。当产生数据流的现象发生改变时，新数据无法被现有数据模型所描述， 可能被误认为是噪音。 图1 1 展示为传统处理模型和数据流处理模型的比较。如果利用传统技术进 行数据处理，必须将数据全部存储到介质( 如关系数据库) 中，然后通过提交d m l 语句访问存储介质来获取查询结果。但是，当数据规模宏大且到达速度很快时， 因执行查询操作需要大量的i 0 交换，效率低下，往往难以满足实时性要求。相 反，数据流处理技术可以不保存整个数据集，仅维护一个远小于其规模的概要数 据结构，从而能够常驻内存。基于数据流的处理技术通常包含两部分算法：一部 分监控流中的数据，更新概要数据结构；另一部分响应用户查询请求，返回近似 2 支i - ，一! j ； ! j 第1 章绪论 查询结果。 图1 - 1 传统数据处理模型与数据流处理模型的比较 f i g u r e l 一1t r a d i t i o n a ld a t ap r o c e s s i n gm o d e lv s d a t as g e a mp r o c e s s i n gm o d e l s 1 2 研究背景与意义 近几年来，随着社会信息化进程的不断深入发展，人类对信息的需求和依赖 程度越来越高，如何从海量的信息资源中快速有效的获取有用的信息，已经成为 研究的热点，这也给信息检索带来了极大的挑战。 因特网大大方便了信息的传播，对我们的工作、生活和学习产生了深刻的影 响。但是，如果要对某一个问题进行研究，人们就会试图在因特网上检索信息。 但通过雅虎等搜索引擎检索出的信息成千上万，有时几乎没有研究价值，这就是 一种信息的冗余。从用户的角度来说，就是怎样找到我想要的信息；而从研究角 度，即从信息检索的结果来看，怎样高效、准确地从w e b 数据库中查找用户需 要的信息，并以有效的形式呈现给用户。 如果对检索结果进行聚类研究，把相似度很高的信息归为一类，用户可以在 有限时间内判断是不是他需要的信息。聚类是一个无指导的学习过程，它是指根 据样本之间的某种距离在无监督条件下的聚簇过程。利用聚类方法可以把大量的 文档划分成用户可迅速理解的簇( c l u s t e r ) ，从而使用户可以更快地把握大量文档 中所包含的内容，加快分析速度并辅助决策。大规模文档聚类是解决海量文本中 数据理解和信息挖掘的有效解决手段之一。作为一种无监督的机器学习方法，聚 类技术已经成为对文本信息进行有效地组织、摘要和导航的重要手段，为越来越 多的研究人员所关注。 随着w e b 的广泛使用，x m l 以其巨大的通用性和灵活性逐渐成为了企业所 关注的焦点，也为基于w e b 的信息交换带来了新的希望。x m l 语言因“自描述”、 “树形结构”、“结构嵌套”等特点受到了业界的普遍欢迎和支持，越来越多的应 用领域己经将其作为主要的存储格式和传输媒体。因此如何有效的处理这些 x m l 文档已经成为一个重要的研究课题。 3 北京工业大学工学硕十学位论文 从半结构化文档( 特别是h t m l 和x m l 文档) 中提取信息变得越来越重要。 如何识别出具有相同结构的文档是我们研究的主要任务。如果我们能很容易识别 出具有相同结构的文档，就可以根据文档结构对文档进行聚类，这样就能更好地 组织和管理信息，并快速，准确，全面的从中搜索到用户所需要的信息，要完成 这个任务最基本的要求是：有一个模型能很好地描述x m l 文档的结构信息。作 为x m l 文档的近似搜索的基础，首先要能够准确地度量查询与文档、文档与文 档间的相似度。传统的信息检索技术利用向量空间模型来表示一个文档，并利用 代表文档的空间向量间的距离来度量两个文档间的相关程度。但向量空间模型无 法反映x m l 文档中的元素嵌套结构的语义。一般地，一个x m l 文档可以模型 化为一棵树或一个图，两个x m l 文档间的相似度可以用这两棵树( 图) 间的距离 来度量。 烈霓0 1 d 岫硎n e 2 0 1 2w o r l de n d 嘶i t ! e c o m e d y 吨e n 炒二赫三： 咖o r 赢o n e y 1 2 0 - o , j o w o ”o = 妯- o n e y c h ，：“二7 ”， ， 曲l 劬姗e ( d 0 c 2 ) t a k n i k l9 9 2 k a m a i l o n g g o n g f u m a r y j u n ( d o c 3 ) ? x m lv e r s i o n = 1 0 ”e n c o d i n g = u t f 一87 d a t a b a s e 19 9 9 w e i g u f a n ( d o e 4 ) 图1 - 2x m l 文档实例 ， 图1 - 2s a m p l e so fx m ld o c u m e n t s 为了很好的识别具有相同结构的文档，本文采用的是一种所谓的“层次结构 的模型来表示不同的x m l 文档，这样就可以通过这个层结构来计算不同文档间 的相似度，从而可以判断出哪些文档的相似度比较的高，那些文档的相似度比较 的低。将相似度高的文档聚为一个簇，就可以减少搜索的范围，加快搜索的速度。 图1 2 给出了4 个x m l 文档描述。从设计者的本意上看，d o c l 、d o c 2 和d o c 3 是为了描述m o v i e 信息，d o c 4 描述b o o k 信息。对于x m l 结构分析而言，希望 4 第1 章绪论 能找到有效方法把这些文档进行分类。如果使用“相似度 来度量的话，有效的 方法应该能保证d o c l 、d o c 2 、d o c 3 之间的相似度要明显大于它们和d o c 4 的相似 度。这样，4 个文档就可能被分成两个大类：m o v i e 类f d o c l 、d o c 2 、d o c 3 和b o o k 类 d o c 4 ，。随着大量的类似的x m l 文档的到来，就形成了一种x m l 文档流。 因此，本文研究的主要目标就是在要解决在x m l 文档流的形式下完成对x m l 文档的分析，来实现x m l 文档的聚类。 1 3 国内外研究现状 随着x m l 技术被广泛地应用到诸多领域，它逐渐承担起存储海量数据的重 任。目前，x m l 技术已经广泛地应用于出版业、电子商务、数字图书馆等当今 的热门领域。它以其良好的数据存储格式、可扩展性、高度结构化、便于网络传 输等优势将在许多领域中应用，便于网页信息组织，不仅能满足不断增长的网络 应用需求，而且还能够确保在与网络进行交互时，具有良好的可靠性与互操作性。 x m l 可以定义标记和模型化的文档嵌套结构，各文档利用这些语义标记可以实 现自描述功能，同样，我们也可以根据文档中的嵌套标记获得各文档的结构信息， 然后利用这些结构信息来实现文档检索的目的。因此，每个行业的组织和开发人 员都可用x m l 创建他们自己的标识语言，用于在他们各自的领域中实现信息的 交互。 从总体上说，本文关注的是x m l 数据流的聚类算法，该方向的研究在国内 外属于刚起步阶段。构成此研究的主要技术基础是传统数据流聚集研究和x m l 文档聚类研究等成果。 1 3 1 传统数据流聚类研究 数据流是快速变化的，所以对数据流聚类要能随时间而不断地进行；数据流 是海量而有序的，可能保证存贮整个数据集，只能分析一定范围内的数据，因而 要有效地利用有限的空间与时间。随着数据流的提出，学术界提出了大量的关于 数据流聚类的算法。 2 0 0 0 年s u d i p t o i 2 4 1 等人基于k - m e d i a n 算法提出了单遍扫描聚类算法s m a l l s p a c e t ， 算法的基本思想是基于分治的思想，使用多层多次迭代过程实现有限空间对数据 流进行聚类。算法首先将数据流中最初的o ( m k ) 个点采用随机算法聚类为2 k 个 中值点，然后对每o ( m ) 个第i 层的中值点采用l o c a ls e a r c h 算法聚类为2 k 个i + l 层 的中值点。最后采用p r i m a ld u a l 算法将各层所有的中值点聚类为最后的k 个中值 点作为聚类结果。 2 0 0 2 年c h l a a g h a n t 2 7 】等人提出的s t r e a m 算法网，使用质心和权值( 类中数据 个数) 表示聚类，同样使用分级聚类的方法处理数据流。s t r e a m 算法首先确定样 s 北京工业大学工学硕十学位论文 本大小，每当数据块大小超过先前计算出来的样本大小时，就采用l o c a ls e a r c h 子处理过程进行聚类获取中值点，最后对中值点进行聚类以获取最终结果。 2 0 0 3 年b a b c o c k 2 6 】从理论上对滑动窗口中的数据聚类问题进行了研究，通过 引入滑动窗口概念，在数据流窗口维护方差和k m e d i a n s ，利用滑动窗口技术解决 数据流中的数据过时问题。 2 0 0 3 年a g g a r w a l 3 】等人中提出了流数据聚类算法c l u s t r c a m ，首次提出把数 据流看成一个随时间变化的过程，而不是一个整体进行聚类分析，在数据流随时 间变化较大时该算法比其它算法产生更高质量的聚类。 2 0 0 6 年朱蔚恒【2 3 j 等在文中提出了基于密度与空间的a c l u s t r c a m 聚类算法， 通过引入有严格空间的意义聚类块，在对数据流进行初步聚类的同时，尽量保留 数据的空间特性，从而能很好的支持对任意形状的聚类。 1 3 2x m l 文档聚类研究 一般地，一个x m l 文档可以模型化为一棵树或一个图，两个x m l 文档间 的相似度可以用这两棵树( 图) 间的距离来度量。 在x m l 出现之前，己有许多工作研究了两棵树( 图) 问的相似测度的问题【l 】 【4 】【5 】【2 2 】【2 4 1 】。其中最自然和应用最广的测度是树的编辑距离【1 2 】f 1 3 】【1 4 】【1 5 】【1 6 】【17 1 。各 种编辑距离方法不同之处是他们允许编辑操作不同。这些树编辑距离算法的时间 复杂度为o ( n 2 ) ，其中n 为待比较的两文档大小和。然而，w e b 上的x m l 文档 往往是大规模的，在处理海量的x m l 文档时，遍历每棵文档树中的每个结点是 不现实的，另外，对于文档中存在的元素重复和元素可选问题树模型不能很好处 理。例如：如果两个文档仅仅是其中某个子元素的个数不同，计算出的相似度应 该很大，但树编辑距离方法得不到这样结果。 2 0 0 2 年，s e r g i of l e s c a 把x m l 文档进行编码【9 1 ( 该编码不同于本文所述的编 码) ，然后将x m l 文档表述为一个傅里叶展式。该方法的缺点在于对快速傅里叶 变换的依赖性很强，这就影响了其对x m l 文档处理的速度，其代价最少也为 o ( n * i g n ) 。另外更重要的是，该文对x m l 文档建模时所采用的模型并没有合理 地将x m l 文档结构中的相关信息表述出来，因此它在计算不同x m l 文档问的 相似测度值时其效果并不是很理想。 2 0 0 4 年，w a n gl i a n t l 0 】等人定义了判断相似结构之间距离大小的标准。这种 方法需要对每个x m l 文档进行分析处理，并根据文档的结构信息构建一个有向 图( s g 图) 。测量x m l 文档间相似度大小的标准就是建立在这个有向图的基础 之上。标准的实质是用两个有向图中所包含的公共边数与两个文档中边数较大的 一个比值大小来确定文档间距离大小。但是许多结构不同的x m l 文档却可能由 几乎完全相同的元素( 或属性) 构成，因此这个标准存在一定的局限性，因为它仅 6 第1 章绪论 仅考虑了公共边的数目，而没有考虑每条边在x m l 文档中所起的语义作用。 2 0 0 4 年，c o s t a 采用了编辑距离的思想，把每个x m l 文档看作是一棵有序 树的结构【7 j ，并采用有序树之间的边匹配和路径匹配以及j a c c a r d 系数来进行度 量，完成对x m l 相似度的计算。 2 0 0 4 年，n i e r m a n 和j a g a d i s h t 2 2 】对编辑距离的方法进行了优化，在其基础上 又增加了子树的插入和删除等操作，这使得计算两个文档间的相似度变得更加灵 活，更加方便。但是该方法的计算代价却很高，至少是o ( n 2 ) 。 2 0 0 8 年，n a y a k 【6 】定义了一种表示y a m l 文档结构信息的层次结构，并给出 了这种结构下的相似度计算标准。但这种方法存在的一个最大的局限性是计算的 结果跟读取文档的顺序有关，不同的读取顺序得到的差异性很大。 本文针对文献【6 的缺陷，采用滑动窗口技术，很好的获取当前窗口中数据 流的分布特征。当新的元组到达时，及时地淘汰“过老”的数据，接纳“新”的 数据，降低了过去数据对结果的影响。 1 4 本文主要研究内容 数据流的技术在很多实例中已经开始得到了初步的应用，解决了大量用传统 的数据库管理系统所不能处理的问题。同时随着x m l 研究的进一步深入，一些 基于x m l 的实际问题逐渐浮现出来。如何从基于x m l 的数据流中提取有用的 信息，又成了研究的难题。 基于x m l 的研究，又大体又可以分为两类，基于x m l 的语义的研究和基 于x m l 结构的研究，本文就是基于x m l 文档结构的研究。 在对x m l 数据流的研究中，本文中数据流的每个结点对应着一个x m i 。文 档，以x m l 文档为结点的研究对象。主要的工作如下： ( 1 ) 把静态的x m l 文档结构的研究扩展到x m l 数据流的聚类研究上来； 针对半结构化的x m l 文档的形式，提取x m l 文档的有效结构信息，摒弃了结 点的语义信息，只关心文档的结构。有效的把复杂的x m l 文档解析为只包含结 构信息的概要数据结构。并将该结构应用到x m l 数据流的聚类研究上。 ( 2 ) 成功的把滑动窗口技术应用到x m l 数据流的研究中，并提出了基于滑 动窗口的x m l 数据流聚类算法s w - x s c l s ；滑动窗口技术，很好的保存了当前 窗口内的数据流分布特征，降低了过时数据对聚类结果的影响；指数直方图是滑 动窗口模型中常用的保存概要数据结构的方式，很好的保证了“新”数据的到来 和“旧 数据的删除。 ( 3 ) 通过大量的实验对本文提出的算法进行了验证。与传统的静态文本的聚 类算法进行了聚类质量等方面的实验比较，全面的实验证明，本文所采用的算法 可以很好的完成对x m l 数据流的聚类，得到很好的聚类效果。在聚类质量上可 7 北京工业人学工学硕士学位论文 以达到甚至超过静态聚类方法。 1 5 本文的组织结构 本文将按照以下结构进行组织全文： 第1 章本文的绪论，简要介绍了数据流挖掘技术，主要介绍了本文的研究 背景与意义、国内外研究现状以及本文的主要研究内容。 第2 章主要介绍了本文研究所设计到的相关技术：静态数据聚类技术、数 据流聚类技术、可扩展标记语言x m l 。 第3 章本文的核心章节，本文的核心算法基于滑动窗口的x m l 数据流聚 类算法。其中包括本文所要处理的x m l 文档的层次结构形式和聚类特征指数直 方图的。x m l 的层次结构形式包括x m l 文档层次结构的特征、合并和相似度 的计算；聚类特征指数直方图包括直方图的生成、维护与算法的实现。 第4 章算法的实现与实验结果的分析，通过本文所提出的算法与文献 6 】所 提出的x c l s 算法，在聚类质量等方面做了大量的实验比较，大量的实验证明， 本文提出的算法可以获得更高的聚类质量和更快的处理速度 最后对本文进行总结，并对以后的研究工作进行展望。 8 第2 章相关理论与关键技术 第2 章相关理论与关键技术 2 1 静态数据聚类 聚类分析是人们认识和探索事物内在联系的一种手段，其目的是将一个数据 集划分为若干聚类，并使得同一个聚类内的数据对象具有较高的相似度，而不同 聚类中的数据对象的相似度尽可能低。聚类分析是分类分析的逆向方法，但聚类 分析中要划分的类的数目是未知的，就是说聚类把没有分类的记录，在不知道应 分成几类的情况下，按照数据内在的差异性大小，合理地划分成几类，并确定每 个记录所属别。聚类分析在经济、生物、医学等许多领域有着广泛的应用，比如 在市场研究中，面对个体经营户的“营业收入额”、“营业支出额”、“产品销售水平” 等多个评价指标，无法按照一个指标去分类，就可以通过聚类按照数据间的自然联 系把分散的记录“聚”成几“堆”，然后再对每堆进行深入分析。还可以通过聚类分析 把一组数据按照其相似性和差异性分为几个类别，使属于同一类别的数据间的相 似性尽可能大，不同类别中的数据间的相似性尽可能小。 聚类算法大体可以划分为以下几类：划分方法、层次方法、基于密度的方法、 基于网格的方法和基于模型的方法： ( 1 ) 划分方法 给定一个包含1 1 个数据对象或元组的数据库，一个划分方法构建数据的c 个 划分，每个划分表示一个簇，且c n 。通常会采用一个划分准则( 经常称为相 似度函数) ，例如距离，以便在同一个簇中的对象是“相似的”，在不同簇中的对 象是“相异的”。这些聚类方法对在中小规模的数据库中发现球状簇很适用。为 了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要 进一步的扩展。 ( 2 ) 层次方法 层次方法对给定数据对象集合进行层次的分解。根据层次分解是自底向上还 是自顶向下形成，层次聚类的方法可以进一步分为凝聚的和分裂的。层次聚类方 法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤消，因此而不 能更正错误的决定。改进层次方法的聚类质量的一个有希望的方向是将层次聚类 和其他聚类技术进行集成，形成多阶段聚类。 ( 3 ) 基于密度的方法 提出了基于密度的聚类方法是为了发现任意形状的聚类结果。其主要思想 是：只要临近区域的密度超过某个阈值，就继续聚类。这样的方法可以用来过滤 “噪声”孤立点数据，发现任意形状的簇。 ( 4 ) 基于网格的方法 g 北京t 业大学工学硕士学位论文 基于网格的聚类方法采用一个多分辨率的网格数据结构。把对象空间量化为 有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构上进 行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数 目，只与量化空间中每一维的单元数目有关。 ( 5 ) 基于模型的方法 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟 合。基于模型的算法可能性通过构建反映数据点空间分布的密度函数来定位聚 类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。 聚类分析在数据挖掘中的应用主要包括如下几个方面： ( 1 ) 聚类分析可以作为其他算法的预处理步骤，这些算法再在生成的簇上进 行处理。可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联 分析。 ( 2 ) 可以作为一个独立的工具来获得数据分布的情况，观察每个簇的特点， 集中对特定的某些簇做进一步分析。可用在市场细分、目标顾客定位、业绩评估、 生物群种划分等方面。如在商务上，聚类分析可以帮助市场分析人员从客户基本 库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。 ( 3 ) 聚类分析可以完成孤立点挖掘。许多数据挖掘算法试图使孤立点影响最 小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤 立点可能预示着欺诈行为。 2 2 数据流聚类 2 2 1 数据流 h e n z i n g e r 【4 2 j 等人于1 9 9 8 年在论文“c o m p u t i n go nd a t as t r e a m 中首次将数 据流作为一种数据处理模型提出来。从2 0 0 0 年开始，数据流作为一个热点研究 方向出现在数据挖掘与数据库领域的几大顶级会议中，如v l d b 、s i g m o d 、 s i g k d d 、i c d e 、i c d m 等会议每年都有多篇有关数据流处理的文章。 数据流即指那些连续的、无限的、快速的、随时间变化的数据元素的流。数 据流中的数据即流数据。而流数据挖掘就是在流式数据上发现提取隐含在其中 的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据流是现象驱 动的，其速度与数据项到达的次序无法被控制。数据流通常具有潜在无限的体积， 且数据可能的取值是无限的，处理数据流的系统无法保存整个数据流。而数据流 的在线处理要求又使系统无法进行代价昂贵的磁盘存取。因此，数据流中的数据 项在被读取一次之后，就被丢弃，以后不可能再读到。 与传统数据挖掘相比，流数据挖掘技术的数据搜集过程和挖掘过程同时进 第2 苹相关理论与关键技术 行，以最快的速度，从不断到来的数据中挖掘出感兴趣的模式，即它以精度换取 时间。 进行流数据挖掘需要考虑如下几个问题： ( 1 ) 实时性：即如何高效地对连续的、多维的流数据进行实时处理。 ( 2 ) 有限的内存空间：即在挖掘时需要有效利用有限的存储空间并需要实 时对过期数据进行相应的处理。 ( 3 ) 设计高效的单遍扫描算法：流数据产生的不确定性，使得在进行处理数 据时尽量对数据进行一次或数次扫描，保证每个数据至多扫描一次。 ( 4 ) 处理过期数据：如何对已处理完的过期数据操作也影响到流数据处理效 率。 2 2 2 数据流处理模型 由于数据流是一个长期、动态的过程，部分算法在处理数据流时并不是将所 有的数据流数据作为处理对象，而是根据应用需求选取某个时间范围内的数据进 行处理。按算法处理数据流时所选取的时序范围，数据流模型可分为以下几类： ( 1 ) 快照模型：处理数据的范围限制在两个预定义的时间戳之间。 ( 2 ) 界标模型：处理数据的范围从某一个已知的初始时间点到当前时间点为 止。 ( 3 ) 滑动窗口模型：处理数据的范围由某个固定大小的滑动窗口确定，此滑 动窗口的终点永远为当前时刻。其中，滑动窗口的大小可以由一个时间区间定义， 也可以由窗口所包含的数据项数目定义。从直观上看，这种模式就像用一个不变 的窗口，数据随时间的推移而不断的经过窗口，出现在窗口内的数据就是被计算 的数据集合，滑动窗口模型所处理的数据是数据流中最新到达的滑动窗口内的数 据。随着数据的不断到达，新数据从窗口另一端移入，旧数据从窗口一端移出。 在这3 种模型中，界标模型和滑动窗口模型是采用得比较多的模型。界标模 型通常将数据流的起始点作为数据处理的初始时间点。此时，算法对数据流中所 有数据进行处理，此时数据流上只存在插入操作。在滑动窗口模型中，窗口随着 数据的流入而不断的向前滑动，此时数据流中存在着新数据的插入和旧数据的删 除操作。滑动窗口模型非常适用于只要求对最近时间段内的数据进行处理的应 用。 由于滑动窗口模型随着时间的推移，窗口不断的往前滑动，存在新数据的插 入和旧数据的删除操作。这个特性能够很好的满足流数据处理的要求。 本文在数据流处理模型就是采用的滑动窗口模型。具体的滑动窗口模型技术 将在下一节中详细介绍。 2 2 3 滑动窗口 使用滑动窗口的需求来自于算法和应用。在算法方面，滑动窗口减少了算法 需要处理的数据量，并对挖掘变化的数据流提供支持。在应用方面，有些应用只 对最近的数据感兴趣，要求算法对以当前时间为终点的某个滑动窗口内的数据进 行处理。 滑动窗口，即指在处理数据时只考虑最近数据流。它主要处理窗口内最近的 数据，可被用来更好地获取当前数据流的特征信息。但在滑动窗口下不仅有新数 据连续到达，而且旧数据会过期。图2 1 所示为一个滑动窗口模型。 iliiilliiill1 1011101010l 0 1 图2 - l 滑动窗口 f i g u r e 2 1s l i d i n gw i n d o w s 滑动窗口模型在内存