（计算机软件与理论专业论文）基于birch算法的网络访问模式发现的研究与应用.pdf

摘要 本论文主要研究内容是：通过区域网的中心路由器，收集用户访问网络的信息并 找出他们访问网络的共同模式，采用r i r c h 聚类算法对数据流进行聚类分析，然后 统计各簇对每类网站点击频率，最后使用簇与全局均值比较图形，来表达网络用户的 使用模式。其结果有助于缓解网络带宽压力，提高网络运营商服务质量，帮助网络服 务进行优化处理。论文搭建了一个软件平台，用于协助数据传输，平台在设计时采用 多种设计模式，目的使其灵活可变。 当前国内外大多数都是通过w e b 挖掘来发现用户的访问模式。传统的w e b 挖掘 按种类分为内容挖掘、结构挖掘与使用挖掘，用户访问模式的发现属于使用挖掘的范 畴。w e b 使用挖掘研究的对象是w e b 使用数据或者w e b 日志，w e b 使用挖掘可以应 用于多种不同的目的，通过分析一个用户访问网站的序列，可以得到用户的简单信息， 从而可以实现个性化等等。但w e b 挖掘发现的是用户访问一个w e b 站点的信息，是 外界用户到站点来访问的模式，是一个由外而内的概念。从区域网的中心路由器发现 网络访问模式，研究的对象是路由器中的i p 分组，针对的是区域网的用户，研究这 些用户通过此路由器访问i n t e m e t 的访问模式。是一个由内而外的概念。 关键字：数据挖掘：聚类；b i r c h ；流挖掘：访问模式 a b s t r a c t t h i st h e s i sf o c u s e so nd i s c o v e ru s e ra c c e s sp a t t e r n s w ec o l l e c t e dd a t af r o mt h ec o r e r o u t e ro far e g i o n a ln e t w o r kc e n t e r w eu s er i r c h c l u s t e r i n ga l g o r i t h mf o rc l u s t e r i n go f t h ed a t af l o wa n ds t a t i s t i c sc l i c ko nt h ef r e q u e n c yo nw e b s i t eo fe v e rc l u s t e r f i n a l ，w eu s e c l u s t e ra v e r a g ec o m p a r i s o nw i t ht h eg l o b a l p a t t e m s t h er e s u l th e l p f u le a s et h ep r e s s u r e a v e r a g eg r a p h i c a lt or e p r e s e n tt h eu s e ra c c e s s o nn e t w o r kb a n d w i d t h ，i m p r o v ea n do p t i m i z e d n 咖r kq u a l i t yo fs e r v i c e w ea r ec r e a t e dap l a t f o r mt oh e l pd a t at ot r a n s m i t w eu s ea l o t d e s i g np a t t e r n st oh e l p f u lm ys y s t e mm o r ef l e x i b l e n o w ：m o s to ft h ec u r r e n td o m e s t i ca n di n t e m a t i o n a lu s ew e bm i n i n gt o d i s c o v e r a c c e s sp a t t e r n so fu s e r s w e bm i n i n gb a s e do nt h et r a d i t i o n a lt y p e so fc o n t e n tm m m g ， s t r u c t u r em i n i n ga n du s a g em i n i n g ， u s e ra c c e s sp a t t e r n sf o u n dmm i n i n ga r e a sa r eu s e d 。 w 曲u s a g em i n i n gi st h eo b j e c to fs t u d yw e bu s a g ed a t ao rw e b l o g s w e bu s a g em i n i n g c a l lb ea p p l i e dt oav a r i e t yo fd i f f e r e n tp u r p o s e s ，t h r o u g h t h ea n a l y s i so fau s e rv i s i t st h es i t e s e q u e n c e ，c a ng e tu s e r ss i m p l ei n f o r m a t i o n ，c a n b ep e r s o n a l i z e d ，e t c h o w e v e r , w e b m i n i n gi sf o u n di nt h eu s e rv i s i t saw e b s i t ei n f o r m a t i o n ，i so u t s i d eu s e r st om ys i t et o a c c e s sp 甜e il l s ，i saf r o mo u t s i d et oi n s i d et h ec o n c e p t f r o mt h ec e n t e ro ft h er e g i o n a l n e t w o r kr o u t e r s n e “ ，o r ka c c e s sm o d eo fd i s c o v e r y , r e s e a r c ht a r g e t e da tt h ei pp a c k e to n r o u t e r s t u d yo ft h e s eu s e r sa c c e s si n t e m e tp a t t e r n ，i sa f r o mi n s i d et oo u t s i d et h ec o n c e p t 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 ；b i r c h ；d a t a f l o wm i n i n g ；a c c e s sp a t t e m s l l 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究 工作所取得的成果。据我所知，除了特另l j j t l 以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡 献的个人和集体，均已在文中作了明确的说明。本声明的法律结果由本人 承担。 学位论文作者签名：立堑基弦：日期：1 7 二，。一 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：划 指导翥师签名： 日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 日期： 篮 电话： 邮编： 东北师范大学硕士学位论文 第一章绪论弟一早三石v 匕 1 1 选题背景及意义 随着i n t e r n e t 的迅猛与蓬勃发展，广大用户对网络服务与质量要求也越来越高。 特别是，在当前网络带宽发展缓慢的趋势下，网络业务量呈大幅度的高速增加， i n t e r n e t 应用服务商非常有必要利用智能系统，透过区域网络的路由器来分析传送的 数据、通过这些数据信息发现使用者的行为，从而改善对他们的服务。如何收集使用 者的访问记录并找出他们的访问模式，以访问模式为基础对网络服务进行优化处理具 有非常重要的应用价值。 当前国内外大多数都是通过w e b 挖掘来发现用户的访问模式。传统的w e b 挖掘按 种类分为内容挖掘、结构挖掘与使用挖掘，用户访问模式的发现属于使用挖掘的范畴。 w e b 使用挖掘研究的对象是w e b 使用数据或者w e b 日志，w e b 使用挖掘可以应用于多 种不同的目的，通过分析一个用户访问网站的序列，可以得到用户的简单信息，从而 可以实现个性化等等n 1 。但w e b 挖掘发现的是一个或者一组用户访问一个w e b 站点的 信息。从区域网的中心路由器发现网络访问模式的研究对象是路由器中的i p 分组， 研究目标是区域网的用户，发现的是整个区域网通过路由器访问i n t e r n e t 的访问模 式。 发现网络的访问模式，是从区域网的中心路由器以流的形式采集i p 分组流。然 后对i p 分组流进行分析处理。研究出适合于i p 分组流挖掘算法的数据结构和建模方 法具有重要的学术价值与实际意义。 1 2 数据流挖掘研究现状 目前数据流挖掘方面的研究成果主要集中在数据流的聚类、分类和关联规则挖掘 方面嘲。 1 2 1 数据流聚类挖掘算法研究 尽管聚类问题在数据库、数据挖掘和统计等领域得到了广泛研究，但是流数据的 分析仍为聚类算法提出了前所未有的挑战，由于完整甚至部分地存储过去数据的方法 不可行，需要能够只使用新数据就能够追踪聚类变化的算法，这就要求算法必须是增 量式的，对聚类表示要简洁，对新数据的处理要快速，对噪音和异常数据是稳健的。 因为数据流可看成是随时间不断变化的无限过程，其隐含的聚类可能随时间动态地变 化而导致聚类质量降低。近年来，有学者提出了应用于大规模数据集的一趟聚类算法， 如s q u e e z e r 算法和b i r c h 算法，它们可以应用于某些数据流问题，也有学者提出了 i 东北师范大学硕士学位论文 针对流数据的聚类算法，典型的有s t r e a m 算法和c l u s t r e a m 算法他1 。 1 2 2 数据流分类挖掘算法研究 在数据流分类方面主要是p d o m i n g o s 和g h u l t e n 的研究成果。一种改进的 l o e f f d i n g 决策树分类算法v f d t ( v e r yf a s td e c i s i o nt r e e ) ，使用恒定的内存大小 和时间处理每个样本，有效地解决了时间、内存和样本对数据挖掘、特别是高速数据 流上的数据挖掘的限制。v f d t 使用信息熵选择属性，通过建立h o e f f d i n g 树来进行决 策支持，并使用h o e f f d i n g 约束来保证高精度地处理高速数据流。既可连续处理数据， 也可通过二次抽样，重新扫描数据集，因此可以处理非常庞大的数据集。v f d t 的另一 个特点是增量式学习及随时可用性，它是一个实时算法，在学习了最初的一些样本之 后，就提供了一个随时可用、不断优化的决策树。v f d t 和其他大多数机器学习方法一 样，假设数据是从静态分布中随机获取的，不能反映数据随时间变化的趋势。因此， p d o m i n g o s 和g 1 l u l t e n 中引入了滑动窗口技术，对v f d t 算法进行改进，提出了 c v f d t ( c o n c e p ta d a p t i n gv e r yf a s td e c i s i o nt r e e ) 算法，除了保留v f d t 算法在速 度和精度方面的优点外，增加了对数据产生过程中变化趋势的检测和响应，使得算法 更好地适应对高速时变流数据的分类。c v f d t 利用样本窗口来有效维护决策树的更新 和模式的一致性，然而它并不需要在每个新样本到来的时候都学习新的模式，而是通 过增加相应新样本的总数来更新充分统计量，相应地减少滑动窗口中旧的节点数量。 如果基本概念是静态的，将不会产生影响：然而，如果概念是动态变化的，因为一个 可替换的属性有更高的增益，使得某些先前通过h o e f f d i n g 测试的分支不再起作用。 在这种情况下，c v f d t 开始在根节点用新的更好属性生成一棵用于替换的子树，当这 棵替换的子树在新的数据上比旧的子树更精确时，就用新的子树代替旧的子树。 1 - 2 3 数据流关联规则挖掘算法研究 数据流上的频繁集挖掘就是单遍扫描数据流来连续地发现其中的频繁项集。频繁 项集是满足最小支持度的项集。由于挖掘频繁模式是一系列连续操作的集合，在看到 所有过去和未来的数据之前，任何项集的计算都不可能完整的完成，因此在数据流环 境中挖掘和更新频繁集非常困难，数据流有更多信息要追踪和更复杂的问题要处理， 频繁集会随时间的变化而变化，存储结构要动态调整以反映频繁集随时间变化的情 况。针对数据流的频繁集挖掘，m a n k u 等提出了一个建立在频繁项挖掘算法的基础上 的频繁集挖掘算法m a n k u ，它在扫描一次数据的基础上得到基于整个数据流的频繁集。 c h a n g 等使用信息衰减模型来区分最新数据和其他的历史数据。g i a n n e l l a 等则通过 滑动窗口机制来挖掘一定时间范围内的频繁集。还有一些人提出一些近似算法，但是 当数据流变化较快时，无法准确计算频繁集。 2 东北师范大学硕士学位论文 1 3 研究方案 为了在一个区域网内了解用户的使用行为并且发现访问网络的模式，首先要解决 在路由器上获取i p 数据包的问题。实际应用中，可以经由某大学网络中心路由器获 取i p 地址。作为大学网络中心，整个学校的流量都集中于网络中心的路由器，如图 1 1 所示。然后把工p 地址映射为可用于b i r c h 算法的p 维行向量数据。但在实验时， 目的是实现b r i c h 算法，研究聚类过程，分析聚类结果。为使实验简单，所以我们直 接模拟产生行向量数据。 图1 1 网络中心的路由器 在当前众多获取数据包的工具中，论文中选用t c p d u m p 工具。其理由我们会在第 二章中做详细描述。i p 数据包中包含大量的信息，但并不是所有的信息对于分析都有 用，只要提取t c p 包的五元组即可。 s r ci p ，源地址： d e s ti p ，目的地址： s r cp o r t ，源端口： d e s tp o r t ，目的端口： p r o t o c o l ，协议。 首先，实际应用中，可以采用正则表达式n 和支持正则表达式的工具来截取数据 包，去除无用信息数据，只留下五元组数据。之所以采用j 下则表达式，因为正则表达 式是强大、便捷、高效的文本处理工具，j 下则表达式本身，加上- - 1 7 袖珍编程语言的 通用模式表示法，赋予使用者描述和分析文本的能力，配合特定工具的额外支持，正 则表达式能够添加、删除、分离、叠加、插入和修改各种类型的文本和数据。 其次，论文中搭建了一个系统平台用于解决获取的数掘如何转换为程序所能处理 3 东北9 币范大学硕士学位论文 的结构、以及数据如何从路由器传输到本地等问题。在系统平台设计与搭建过程中， 我们做了大量工作使系统足够灵活，尽量去满足未来的发展。第四章中详细描述搭建 的系统平台。 最后，由于用户访问网络的模式种类繁多，论文中我们主要针对网站用户进行分 析，其余的访问模式发现作为论文的后续工作再来研究。因为只需要分析网站用户的 访问模式，所以在泛化映射表中只对网站访问进行映射，找出其中属于访问网站的数 据，以此作为我们算法的输入。这样得出的聚类结果也就是网站用户的访问模式。 同时因为数据是流的形式，具有以下特点： ( 1 ) 在获取i p 分组时，i p 分组的流量巨大甚至是无限大，完整甚至部分地存储 过去数据的方法不可行。 ( 2 ) i p 分组往往是以动态流的形式呈现，将动态的数据流转换为静态存储再对 其进行分析，时间效率难以接受。 ( 3 ) 不能实时发现网络访问模式，更无法发现访问模式随时间变化的趋势。 所以论文采用数据流挖掘算法来发现用户的访问模式。论文采用b i r c h 聚类算法 作为用户访问模式发现的算法，就是因为b i r c h 算法是增量式的，完全适合我们i p 数据流聚类。通过b i r c h 算法我们得到对用户访问数据的聚类结果，但只通过聚类结 果还很难发现用户的访问模式，论文中我们采用了一种网页访问平均值的比较图，也 就是把全局对各类网页访问的平均值与每个簇中对各类网页访问的平均值进行比较。 这样，通过考察平均值比较图，可以很容易的看出用户的访问模式。 1 4 论文框架 论文各章节安排如下：第二章，数据挖掘与数据流研究技术，对论文中引用到关 于数据挖掘、数据流、流挖掘、t c p d u m p 工具等文献和工具做了整体性的阐述。第三 章，描述了用于发现用户访问模式的算法与理论基础。第四章，介绍系统平台搭建与 算法实现过程。第五章，我们对实现的算法进行试验，并对实验结果进行分析，从中 发现用户访问网络的模式。最后，结论与展望。 4 东北师范大学硕士学位论文 第二章数据挖掘与数据流研究技术 2 1 数据挖掘 数据挖掘h 。3 技术是多学科交叉的新兴技术，它是随着数据的大量积累以及人们对 信息与知识的迫切需求而产生和发展起来的，并逐渐成为人们关注的热点。人们希望 通过数据挖掘技术找到蕴藏在数据中的有用信息，进而找到尚未发现的知识，为商业 竞争、企业生产和管理、政府部门决策以及科学探索等提供有价值的服务，这种所谓 隐藏在数据中的信息与知识是人的先知和经验无法确定的，对于帮助人们做出适当决 策是很有价值的。数据挖掘技术是在统计、人工智能和数据库等多种技术的基础上发 展起来的。数据挖掘所强调的是从大量数据中获取有效的、新颖的、潜在的、最终可 被理解的非平凡过程。它的目的是帮助决策者寻找数据间潜在的关联，发现被忽略的 要素，而这些信息将有助于预测趋势和提供决策支持。 2 1 1 数据挖掘的分类 数据挖掘是从数据中发现模式。模式有多种类型，按功能可分为两大类，既描述 型模式和预测型模式砸1 。描述型模式是对数据中存在的规则作出一种描述。或者根据 数据的相似性把数据分组。描述型模式不能直接用于预测。预测型模式是可以根据数 据项的值精确确定某种结果模式。 模式挖掘可细分为以下6 种： ( 1 ) 分类模式：是一个分类函数( 分类器) ，能够把数据集中的数据项映射到某 个给定的类上； ( 2 ) 回归模式：回归模式的函数定义与分类模式相似，他们的差别在于分类模式 的预测值是离散的，回归模式的预测值是连续的； ( 3 ) 时间序列模式：时间序列模式根据数据随时间变化的趋势预测将来值； ( 4 ) 聚类模式：聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组 内差别尽可能小； ( 5 ) 关联模式：关联模式是揭示数据之间的相互关系，确定其关联规则； ( 6 ) 序列模式：序列模式与关联模式相仿，是把数据之间的关联性与时间联系起 来。为了发现序列模式，不仅需要知道事件是否发生，而且还需要确定事件 发生的时间。 在解决实际问题时，应根据需要选择合适的模式，有时也可以同时使用多种模式。 东北师范大学硕士学位论文 2 1 2 数据挖掘的步骤 ( 1 ) 数据取样：当进行数据挖掘时，首先要从企业的大量数据中取出一个与探索 目标相关的数据子集，而不是采用全部企业数据。通过数据样本的精选，不 仅能减少数据处理量，还能突出相关的规律性。数据取样要注意保证数据的 质量。如果原始数据不准确的话，探索出来的所谓规律性根本就没有什么意 义。同时数据采样的时候要注意保证能够获得具有代表性的数据。 ( 2 ) 数据探索：数据探索最终的目的是要搞清楚多个因素相互影响的关系。这些 关系不可能一下子就能建立起来，要有耐心反复试探，仔细观察。可以先观 察众多因素之间的相关性：再按其相关的程度，以了解它们之间相互作用 的情况。如果数据是真实可靠的话，不要轻易地否定数据呈现给你的新关 系。由于数据探索是一个反复尝试的过程，因此通过可视化的操作能有效提 高数据探索的效率。 ( 3 ) 数据调整：在数据采样和数据探索实施之后，就会更加了解数据的状态和趋 势，更加明确要解决的问题，此时要及时对问题进一步细化。在问题进一步 明确化的基础上，按照问题的具体要求来审视采样数据集，看它是否适应 需要。同时针对问题的需要可能要对数据进行增删：也可能按照对整个数据 挖掘过程的新认识，组合或者生成一些新的变量，以体现对状态的有效描 述。在问题进一步明确、数据结构和内容进一步调整的基础上，下一步数据 挖掘应采用的技术手段就更加明了清晰。 ( 4 ) 建立模型：建立模型是数据挖掘工作的核心环节。建立模型需要采用数理统 计方法、人工神经元网络和决策树等多种技术。数据挖掘工作中最常用的主 流技术手段是数理统计方法。利用数理统计工具可以实现对各种不同类型模 型、不同特点数据的回归分析，对多种试验设计模型的方差分析，处理一般 线性模型和广义线性模型、多变量统计分析、聚类分析、时间序列分析等。 通过这些数理统计工具不仅能揭示企业已有数据间的新关系和隐藏着的规 律性，而且能反过来预测它的发展趋势，或是在一定条件下将会出现什么 结果。一般情况下，人工神经元网络对数据处理的要求比较多，资源消耗也 比较大。人工神经元网络和决策树的方法结合起来可用于从相关性不强的多 变量中选出重要的变量。其他的还有平方自动交互检验c h a i d 、分类和回归 树c a r t 方法。数据挖掘中使用哪一种方法主要取决于数据集的特征和要实 现的目标，实际上这种选择也不一定是唯一的，一般要多试几种方法，从 实践中选出最适合的。 ( 5 ) 模型评估：从上述过程中将会得出一系列的分析结果、模式或模型。若能得 出一个直接的结论当然很好，但更多的时候会得出对目标问题多侧面的描 述。这时就要综合它们的影响规律性以提供合理的决策支持信息。如何检验 得出的分析结果是否有用? 一个简单的办法是直接使用原来建立模型的样 6 东北师范大学硕士学位论文 本数据进行检验。另一种办法是另外找一批反映客观实际的规律性数据来检 验。再一种办法是在实际运行的环境中取出新数据进行检验。 以上5 个步骤聃3 是数据挖掘的基本流程。这一过程可能要反复进行，在反复过程 中，不断逼近事物的本质，不断优化解决方案。 2 1 3 数据挖掘的统计方法 点估计指通过估计参数0 来估计总体参数0 的过程，它可以通过估计均值、方差、 标准差或任何其他的统计参数来实现。对一般总体的参数估计经常通过实际计算一个 总体样本的参数值得到，估计量方法也可以用来估计( 预测) 缺失数据的值。估计量 的偏差是估计量的期望值和真实值的差： bias = e ( 0 ) 一0 ，9 ，、 无偏估计量是偏差为0 的估计量。对于小数据集，点估计量实际上可以是无偏的， 而对于大型数据库应用，大多数的估计量应该是有偏差的。 一种度量估计有效性的方法是使用均方误差。均方误差定义为估计值与真实值的 差的平方的期望： m s e ( o ) = e ( o 1 5 7 ) z ( 2 2 ) 均方误差很普遍的被用来估计数据挖掘中预测技术的效果，同时在机器学习中它 也是一个很重要的方法。有些时候不是要预测一个参数的简单点估计，而是要确定 真实参数值的范围，这个范围叫做置信区间。 均方根也可以用来估计误差，或者作为描述数据分布的另一个统计量。计算均值 并不能显示出数值幅度的大小，但计算均方根却可以做到。给出一个具有刀个值的集 合x = 如，毛，均方根定义为： r m s = ( 2 3 ) 一种常用的估计法是折叠刀估计，它通过一组观测值中忽略一个值来实现对参数 否的估计。假设有一个具有九个值的集合x = x x 。) ，对均值的单次估计为： ，一l ，| x ，+ x ， 应2 卫1 ( 2 4 ) 这里下标( f ) 表示本次估计是通过忽略第f 个值而得到的。给出一组折叠刀估计 反矿通过他们可以得出总体估计 7 东北师范大学硕士学位论文 万 0 f ) = 上l 厅 ( 2 5 ) 点估计的另一种方法是极大似然估计。似然值定义为与给定样本的实际分布概率 成比例的一个值。因此从样本的分布中能够得到对参数的估计。似然值越高，潜在分 布产生观测到的结果的可能性就越大。给出一个服从己知分布函数厂( 薯 0 ) 的样本集 x = 而， ，极大似然估计能够估计样本所属的总体的参数。这种方法获得了对样 本数据以某种特定模型发生的最大概率的参数估计。它着眼于用来观察样本数据的联 合概率，这个联合概率是样本的单个概率的乘积。因此，似然函数三定义为 f ( oh ，x 打) = 1 - i ( ti ) ，= i ( 2 6 ) 使得三取最大值的o 值就是所求的估计，它可以通过对。求导( 先将上式两边取对数 化简，然后再求导得到) 。 2 1 4 相似性度量 相似性度量对于每个使用搜索引擎在因特网上搜索信息的人来说都不陌生。在搜 索过程中，所有网页的集合代表整个数据库，它们分为两类：满足查询条件的网页和 不满足查询条件的网页。与不满足查询条件的网页相比，满足查询条件的网页之间应 该更相似。在这种情况下，相似性由用户指定查询来定义，这里的查询通常是基于一 个关键字列表进行。由于返回的网页( 在某种程度上) 都含有指定的关键字列表，因 此它们是相似的。 可以将相似性度量的思想抽象化使之应用于更一般的分类问题。问题的难点在于 怎样定义相似性度量并使之应用于数据库中的项。由于大多数相似性度量采用的是数 值( 而且经常是离散的) ，所以我们很难用于更一般化的数据类型。这就需要将属性 域映射到整数集合的一个子集上。相似性的定义如下： 已知数据库d 中两个元组，和，它们的相似性s i m ( t ，t ，) 是从d xd 到区间【o ，l 】 的一个映射。因此，s i m ( t j ，t j ) 【o ，1 】。 这样做的目的是定义相似性映射，从而使越相像的元组相似值越高。因此，一个 好的相似性度量应具备下面特征： v t d ，s i m ( t , ，t j ) = l v t , ，0 d 如果和0 完全不同，则s 砌( ，t j ) = 0 v ，0 ，t k d ，如果t l , t 更像，则s f 肌( ，t j ) s i m ( t _ f ，气) 8 东北师范大学硕士学位论文 那么如何定义一个这样的相似性映射呢? 当然，这是很困难的。通常“相像 这个概 念本身就没有很好的定义。当相似性度量思想用于类已经事先定义的分类时，要比它 用于类没有事先定义的聚类简单一些。另外，考虑信息检索的例子。每个查询都以它 自身的形式给出了类定义。所以，分类问题就演变为不是在数据库的所有元组中确定 相似性，而是在每个元组和查询之问确定相似性。这使得问题的复杂性由o ( n 2 ) 缩减 为o ( n ) ，其中门代表数据库中元组的个数。 下面是几种在传统的信息检索系统和近来在因特网搜索引擎中比较常见的相似 性度量： d i c e 度量 k 2 o s i m ( t f ，t j ) = 1 生l t - 屹2 + f 孟 h = lh = l j a c c a r d 度量 s i r e ( ，f ，7 ) = 余弦度量 s i m ( f f ，f ，) = 重叠度量 s i m ( f ，t j ) = k t 砌 h = l k ，厶 h 主1 七 r 左+ h = l ( 2 7 ) k 一o h ；l ( 2 8 ) mi n ( ( 2 9 ) ( 2 1 0 ) 这些公式用来估计向量t ；= ( 岛，o ) 和向量t j = ( f ，f j k ) 之间的相似性的，向量中 的分量通常设为非负数值。 距离度量或差别度量也经常用到。顾名思义，它们是用来度量项之间的“不相似 性 。传统的距离度量可以在二维空间使用。它们包括： 9 朋t f 一 ， 一 ，- “一叠 。竿 东北师范大学硕士学位论文 欧几里得距离 d ，sc 。r ，= 盯 。2 。， 曼哈顿距离 批( t i , t j ) = 袭。h 一) i ( 2 1 2 ) 为了抵消不同属性值之间的度量标准的差异，可以将属性值都归一化到区间【o ，l 】上， 如果涉及非数值型的取值，就需要采用一些其他方法来确定它们的差别值。一种方法 是如果值相同，则指定差别值为0 ；如果不同，则指定差别值为1 。 2 2 数据流 数据流心1 就是大量连续到达的、潜在无限的数据的有序序列，这些数据或其摘要 信息只能按照顺序存取并被读取一次或有限次。在网络监控、入侵检测、情报分析、 金融服务、股票交易、电子商务、电信、卫星遥感( 气象、环境资源监控等) 、i n t e r n e t 流量控制等众多领域中，数据以流的形式出现。由于数据流的特殊性，短时间内有大 量数据连续到达，这些数据具有随时间动态变化的趋势，并且到达时间隐含表示或显 示地由时间戳制定。按照固定的次序，这些数据项只能被读取一次。怎样对这些流数 据使用有限存储空间进行快速处理以获取有用信息，为数据挖掘及其应用研究带来了 新的机遇和挑战，也具有非常重要的意义。 2 2 1 数据流的特点 ( 1 ) 有序性、连续性、实时性。数据有序地、连续地到达并实时地变化； ( 2 ) 无限性、大数据量，甚至是无限的数据量，存储所有数据的代价是极大的； ( 3 ) 单遍性。由于内存的限制，只能对数据流进行单遍扫描； ( 4 ) 概要性。处理数据流数据时，要求构造概要数据结构； ( 5 ) 低层次和多维性。数据流的原始细节数据的概念层次较低且具有多维( 或高 维) 的特点； ( 6 ) 近似性。数据流查询以及数据挖掘处理得到的结果是近似的； ( 7 ) 即时性。用户要求得到即时的处理结果阳3 。 2 2 2 数据流模型 数据流是一个以一定速度连续到达的数据项序列j c l ，薯，x n ，这个数据 项序列只能按下标f 的递增顺序读取一次。数据流是现象驱动的，其速度与数据项到 达的次序无法被控制。数据流通常具有潜在无限的体积，且数据可能的取值是无限的， l o 东北师范大学硕士学位论文 处理数据流的系统无法保存整个数据流。而数据流的在线处理要求又使系统无法进行 代价昂贵的磁盘存取。因此，数据流中的数据项在被一次读取之后，就被丢弃，以后 不可能再读到。在实际应用中，某些超大型的静态数据集要求处理算法只能进行一次 线性扫描以降低算法的处理代价。此时，算法的输入也可看作是一种数据流。目前， 在数据流研究领域中存在多种数据流模型，不同的数据流模型具有不同的适用范围， 需要设计不同的处理算法。可以分别按照数据流中数据描述现象的方式和算法处理数 据流时所采用的时序范围，对这些模型进行划分。设数据流中的数据项 x x 矗，依次按下标顺序到达，它们描述了一个信号么。按薯描述信号 彳的方式，数据流模型可分为以下几类n 引： ( 1 ) 时序( t i m es e r i e s ) 模型； ( 2 ) 现金登记( c a s hr e g i s t e r ) 模型； ( 3 ) 十字转门( t u r n s t i l e ) 模型。 在这3 种模型中，t u r n s t i l e 是最具一般性的数据流模型，其适用范围最广，也最 难处理。流数据分类与聚类通常使用的是时序模型，它们将数据流中的每个数据项看 作一个独立的对象。若将a j 1 记为信号，出现的次数，则流数据频繁模式挖掘通常使 用的是c a s hr e g i s t e r 模型，只允许数据的插入。也有算法研究了同时存在数据插入 和删除时的流数据频繁模式挖掘问题。此时，算法应用的是数据流的t u r n s t i l e 模型。 由于数据流是一个长期、动态的过程，部分算法在处理数据流时并不是将所有的数据 流数据作为处理对象，而是根据应用需求选取某个时间范围内的数据进行处理。按算 法处理数据流时所选取的时序范围，数据流模型可分为以下几类： ( 1 ) 快照模型( s n a p s h o tm o d e l ) ：处理数据的范围限制在两个预定义的时间戳 之间。 ( 2 ) 界标模型( 1 a n d m a r km o d e l ) ：处理数据的范围从某一个己知的初始时间点到 当前时间点为止。 ( 3 ) 滑动窗口模型( s l i d i n gw i n d o wm o d e l ) ：处理数据的范围由某个固定大小的 滑动窗口确定，此滑动窗口的终点永远为当前时刻。其中，滑动窗口的大小 可以由一个时间区间定义，也可以由窗口所包含的数据项数目定义。 在这3 种模型中，界标模型和滑动窗口模型是采用得比较多的模型。界标模型通 常将数据流的起始点作为数据处理的初始时间点。此时，算法对数据流中所有数据进 行处理，数据流上只存在插入操作。在滑动窗口模型中，窗口随着数据的流入向前滑 动，窗口中存在数据的插入和删除。滑动窗口模型非常适用于只要求对最近时间段内 的数据进行处理的应用。 2 2 3 流数据挖掘算法的特点 数据流实时、连续、有序、快速到达的特点以及在线分析的应用需求，对流数据 l l 东北师范大学硕士学位论文 挖掘算法提出了诸多挑战。数据流对挖掘算法的典型要求如下n 引： ( 1 ) 单次线性扫描。即算法只能按数据的流入顺序依次读取数据一次。 ( 2 ) 低的时间复杂度。流算法是在线算法，为了跟上数据流的流速，算法处理每 个数据项的时间不能太长，最好能为常数时间。 ( 3 ) 低的空间复杂度。流算法是主存算法，其可用的空间是有限的，算法的空间 复杂度不能随数据量无限增长。 ( 4 ) 能在理论上保证计算结果具有好的近似程度。 ( 5 ) 能适应动态变化的数据与流速。产生数据的现象可能在不断变化，导致数据 内容与流速的改变。 ( 6 ) 能有效处理噪音与空值。这是一个具有健壮的算法所必须具有的能力。 ( 7 ) 能作o nd e m a n d 的挖掘。即能响应用户在线提出的任意时间段内的挖掘请 求。 ( 8 ) 能作a n y t i m e 的回答。即算法在任何时刻都能给出当前数据的挖掘结果。 ( 9 ) 建立的概要数据结构具有通用性。算法所构建的概要数据结构不仅能支持算 法当前的目标计算，而且能支持其他的计算。 在上述要求中，第( 1 ) 至( 3 ) 条是一个流数据挖掘算法所必须满足的。早期的流数 据挖掘算法都是以这三项为目标设计的。对于算法的空间复杂度，理想的情况是它与 数据流长度无关。但是，目前大部分问题都无法找到这样的解。因此，这个要求就 让步为找到空间复杂度为o ( p o l y ( 1 0 9 ) ) 的算法，即次线性算法。算法的时间复杂度 通常以每个数据项到来时，更新概要数据结构或目标计算结果所需要的时间来衡量， 理想的情况是算法处理每个数据项的时间为常数。其中，概要数据结构是算法为支持 目标计算而在内存中保存的数据流数据的压缩信息。对于构建概要数据结构的算法， 通常没有对在概要数据结构上计算目标函数所需要的时间做严格的要求。近似性与自 适应性是数据流算法的两大特点。由于一次线性扫描以及时间与空间的限制，数据流 算法往往只能得到对所处理的问题的近似计算结果。能在理论上保证其计算结果的近 似程度是算法应该考虑的一个问题。算法的自适应性是指当流数据内容或流速受各种 因素的影响而发生改变时，算法能够根据这些改变自动调整计算策略与计算结果。噪 音与空值是一个健壮的算法所必须解决的问题。对于流数据挖掘算法，这个问题显得 更为突出。这是因为在挖掘数据库中的静态数据集之前，通常会进行数据的预处理， 消除数据中的噪音与空值。而在在线进行的流数据挖掘过程中，无法在挖掘前对数据 进行预处理。而且，数据流中的数据在采集以及传输过程中都可能出现错误，产生噪 音或空值。数据流的动态变化性更进一步增加了噪音识别的困难。当产生数据流的现 象发生改变时，新数据无法被现有数据模型所描述，可能被误认为是噪音。在一些应 用中，用户可能在数据流流入过程中提出对某个时间段内的数据进行挖掘的请求，能 回答这种请求的算法被称为具有o hd e m a n d 回答能力的算法。算法通常采用多窗口技 术来近似解决这类问题。能对挖掘请求给出a n y t i m e 的回答，指算法在任何时刻都能 1 2 东北师范大学硕士学位论文 给出对当前数据最精确的计算结果。这要求算法每读取一个数据项，就更新处理结果。 有些算法构建的概要数据结构只能用来支持算法的目标计算，为计算数据流对之间的 滞后关联而保留的统计量。有的概要数据结构是对数据流数据一般性的压缩，还可用 来支持其他计算，保留的多个基本窗口内数据的傅立叶变换系数。这样的概要数据结 构显然比只能支持当前计算的概要数据结构更为有用。 2 3t c p d u m p t c p d u m p 程序是由v a nj a c o b s o n 、c r a i gl e r e s 和s t e v e nm c c a n n e 编写的，他们 都来自加利福尼亚大学伯克利分校的劳伦斯伯克利实验室。t c p d u m p 通过将网络接口 卡设置为混杂模式( p r o m i s c u o u sm o d e ) 来截获经过网络接口的每一个分组。正常情况 下，用于诸如以太网媒体的接口卡只截获送往特定接口地址或广播地址的链路层的帧 1 1 】 o 底层的操作系统必须允许将一个接口设置成混杂模式，并且允许一个用户进程截 获帧。下列的操作系统可以支持t c p d u m p 或者可以加入对t c p d u m p 的支持：4 4 b s d ， b s d 3 8 6 ，s u no s ，u 1 t r i x 和h p - u x 。 2 3 1b s d 分组过滤器 当前由b s d 演变而来的u n i x 内核提供了b s d 分组过滤器b p f ( b s dp a c k e t f i l t e r ) ，t c p d u m p 用它来截获和过滤来自一个被置为混杂模式的网络接口卡的分组。 b p f 也可以工作在点对点的链路上，如s l i p ，不需要什么特别的处理就可以截获所有 通过接口的分组。b p f 还可以工作在环回接口上。b p f 有一个很长的历史。1 9 8 0 年卡 耐基梅隆大学的m i k ea c c e t t a 和r i c kr a s h i d 创造了e n e t 分组过滤程序。斯坦福的 j e f f r e ym o g u l 将代码移植到b s d ，从1 9 8 3 年开始继续开发。从那以后，它演变为d e c 的u l t r i x 分组过滤器、s u n o s4 1 下的一个s t r e a m sn i t 模块和b p f 。劳伦斯伯克利 实验室的s t e v e nm c c a n n e 在1 9 9 0 年的夏天实现了b p f 。其中很多设计来自于v a n j a c o b s o n 。给出了最新版本的细节以及与s u n 的n i t 的一个比较。b p f 将以太网设备 驱动程序设置为混杂模式，然后从驱动程序那里接收每一个收到的分组和传输的分 组。这些分组要通过一个用户指明的过滤器，使得只有那些用户进程感兴趣的分组才 会传递给用户进程。 多个进程可以同时监视一个接口，每个进程指明了一个自己的过滤器。t c p d u m p 的每个实例指明了一个自己的过滤器。t c p d u m p 的过滤器可以由用户在命令行指明， 而r a r p d 总是使用只截获r a r p 请求的过滤器。除了指明一个过滤器，b p f 的每个用户 还指明了一个超时定时器的值。因为网络的数据传输率可以很容易地超过c p u 的处理 能力，而且一个用户进程从内核中只读小块数据的代价昂贵，因此，b p f 试图将多个 帧装载进一个读缓存，只有缓存满了或者用户指明的超时到期才将读缓存保存的帧返 回。t c p d u m p 将超时定时器置为1 秒，因为它一般从b p f 收到很多数据。 1 3 东北师范大学硕士学位论文 而r a r p 守护进程收到的帧很少，所以r a r p d 将超时置为0 ( 收到一个帧就返回) 。 用户指明的过滤器告诉b p f 用户进程对什么帧感兴趣，过滤器是对一个假想机器的一 组指令。这些指令被内核中的b p f 过滤器解释。在内核中过滤，而不在用户进程中， 减少了必须从内核传递到用户进程的数据量。r a r p 守护进程总是使用绑定在程序里 的、同样的过滤程序。另一方面，t c p d u m p 在每次运行时，让用户在命令行指明一个 过滤表达式。 2 3 2 安全性考虑 很明显，截获网络中传输的数据流使我们可以看到很多不应该看到的东西。例如， t e l n e t 和f t p 用户输入的口令在网络中传输的内容和用户输入的一样( 与口令的加密 表示相比，这称为口令的明文表示。在u n i x 口令文件中，一般是t e c p a s s w d 或 e t c s h a d o w ，存储的是加密的表示) ，然而，很多时候一个网络管理员需要使用 t c p d u m p 工具来分析网络中出现的问题。 我们是把t c p d u m p 作为一个学习的工具，用来查看网络中实际传输的东西。对 t c p d u m p 以及其他厂商提供的类似工具的访问权限依赖于具体系统。例如，在s u no s ， 对n i t 设备的访问只限于超级用户。b s d 的分组过滤器使用了一种不同的技术：通过对 d e v b p f x x 设备的授权来控制访问。一般来说，只有属主才能读写这些设备( 属主应 该是超级用户) ，对于同组用户是可读的( 经常是系统管理组) 。这就是说如果系统管 理员不对程序设置用户的i d ，一般的用户是不