（计算机软件与理论专业论文）传感器网络中的数据挖掘.pdf

槲要 y 7 7 亏二亏莎 中文摘要 随着通信技术、嵌入式计算技术和传感器技术的飞速发展和曰益成 熟，具有感知能力、计算能力和通信能力的微型传感器j l ：始在越界范围 内出现。由这些微型传感器构成的传感器删络引起了人们的极大天注。 现有的传感器嘲络数据处理系统只能向用户提供简单的奁询操作。如何 高效的处理传感器网络的海量数据流，以及如何在其中获取钶用的知识， 成为我们新的挑战。 本文主要研究传感器网络中的数据挖掘技术，包括分类技术、关联 规则挖掘技术和聚类技术。本文提出了一种基于传感器网络的分布式决 策树分类算法，在准确性卜保证了概率。阡的界限。该算法使用数值问隔 剪枝策略来处理数值莲参减少了处理数值属性所需的h 、j 间。算法采用 雨林算法框架，实验证明算法的通信负载和计算时间都较少，具有计算 高效性。本文研究了在传感器网络中挖掘关联规则的算法，首先在各个 传感器节点上产生局部的频繁项集，然后通过传感器网络逐层上传、合 并，最终在中心节点形成全局的频繁项集，并产生相应的关联规则。实 验证明该算法具有较少的计算时问和内存使用量。本文还提出了种基 于传感器网络的分布式k 。平均聚类算法，首先由中心点下发k 个质心的 初始值，各个节点将数据对象赋于质心距离它最近的簇，并将簇的信息 通过传感器嘲络逐层i ：传。合并。然后中心点计算k 个簇中对象的平均 值，再卜发，进行迭代，直到各个簇满足误差准则，得到最后的聚类结 果。灾验证明，该算法准确率较高，训算时f 、h j 较低。最后，本文基于以 上算法，实现了一个传感器网络上的数据挖掘原型系统。 关键词：传感器网络分布式数据流挖掘分类关联规则聚类 a b s t r a c t i n p a c e w i t h r a p i dd e v e l o p m e n ta n di n c r e a s i n g l y m a t u r a t i o ni n c o m m u n i c a t i o n ，e m b e d d e dc o m p u t i n ga n d s e n s i n gt e c l u l o l o g y , s e n s o r c a p a b l eo fs e n s i n g ，c o m m u n i c a t i o na n dc o m p u t a t i o na p p e a r si nt h ew o r l d n e t w o r k so fs u c hd e v i c e st y p i c a l l yc o n s i s to ft e n so rh u n d r e d so fs m a l l ， p o w e rc o n s t r a i n e dn o d e sd e p l o y e di nr e m o t el o c a t i o n sw h i c ht h e ya r e e x p e c t e dt o m o n i t o rf o rm o n t h so ry e a r sa tat i m e h o wt op r o c e s st h e c o n t i n u o u sl a r g ed a t as t r e a m si ns e n s o rn e t w o r k se f f i c i e n t l ya n dh o wt of i n d i n t e r e s t i n gk n o w l e d g ei nt h e s es t r e a m sb e c o m en e wc h a l l e n g e u b i q u i t o u s d a t am i n i n g ( u d m ) i sc o n c e m e dw i t ht h i sp r o b l e m t h i s p a p e rm a i n l ys t u d y s t h ed a t am i n i n gt e c h n o l o g i e si ns e n s o r n e t w o r k s ，i n c l u d i n gc l a s s i f i c a t i o n ，a s s o c i a t i o nr u l e ，c l u s t e r i n g t h i sp a p e r p r e s e n t s a l l a l g o r i t h md e s i g n e dt oe f f i c i e n tc o n s t r u c t ad e c i s i o nt r e eo v e r d i s t r i b u t e dd a t as t r e a m si ns e n s o rn e t w o r k s an u m e r i c a li n t e r v a l p r u n i n g a p p r o a c hi s u s e df o r e f f i c i e n t l yp r o c e s s i n g n u m e r i c a la t t r i b u t e s ，a n da p r o b a b i l i s t i cb o u n d o nt h e a c c u r a c y i s g u a r a n t e e d r a i n f o r e s ta l g o r i t h m f r a m e w o r ki sa s ou s e di nt h i sa l g o r i t h mw h i c hc a ns i g n i f i c a n t l yr e d u c et h e s i z eo ft h ed a t a s e tt ob ep r o c e s s e d i nt h i sp a p e r ，a na l g o r i t h mo ff i n d i n g f r e q u e n ti t e m si nd i s t r i b u t e dd a t as t r e a m so fs e n s o rn e t w o r k si sd e v e l o p e d a t f i r s t ，t h ea l g o r i t h mf i n d sl o c a lf r e q u e n ti t e m s e ti ne a c hs e n s o r , a n dt r a n s m i t s t h e mt ot h e i rp a r e n t st om e r g e r e p e a tt h i s u n t i lt h e yr e a c hac e n t r a ln o d e a t l a s t ，t h ec e n t r a ln o d ec o m b i n e st h e mi n t oag l o b a lf r e q u e n ti t e m s e t ，a n d p r o d u c e sa s s o c i a t i o nr u l e sb a s e do nt h e m t h i sp a p e rd e s c r i b e sat e c h n i q u e i i 外文捅要 f o rc l u s t e r i n g h o m o g e n e o u s l yd i s t r i b u t e d d a t ai ns e n s o rn e t w o r k st h e p r o p o s e dt e c h n i q u ei sb a s e do nt h ep r i n c i p l e so ft h ek - m e a n sa l g o r i t h m a t f i r s t ，t h ec e n t r a ln o d eg e n e r a t e skc e n t r o i d sa n db r o a d c a s ti nt h en e t w o r k ， t h e r e a f t e r , e a c hs e n s o rn o d ea s s i g n se a c hp o i n ti nt h e i rl o c a ld a t a s e tt ot h e n e a r e s tc e n t r o i d ，a n dt r a n s m i t st h e i r l o c a lkc l u s t e r si n f o n n a t i o nt ot h e i r p a r e n t sn o d et om e r g e t h i sp r o c e s si sr e p e a t e du n t i lt h ec e n t r a ln o d er e c e i v e s a l lt h ei n f o r m a t i o no fi t sc h i l dn o d e sf o re a c hc l u s t e r , t h ec e n t r a ln o d e r e c o m p u t e st h ec e n t r o i d a st h ea v e r a g eo fd a t ap o i n t sa s s i g n e dt oi t i fi t d o e s n tm e e tw i t ht h es t o pc o n d i t i o n ，t h ea l g o r i t h m , , v i i ii t e r a t e st h ep r o c e s s f r o mt h es t a r t i nt h ee n d ，b a s e do nt h ea b o v ea l g o r i t h m s ，t h ep a p e rr e a l i z e sa d i s t r i b u t e dd a t am i n i n gp r o t o t y p es y s t e mi ns e n s o rn e t w o r k s t h et h e o r ya n d t h et e c h n o l o g yh a v et h eg e n e r a ls i g n i f i c a t i o na n di ti se a s yt oe x t e n dt os o m e a p p l i c a t i o nf i e l d s k e y w o r d s ： s e n s o r n e t w o r k s ，d i s t r i b u t e d d a t as t r e a m m i n i n g ， c l a s s i f i c a t i o n ，a s s o c i a t i o nr u l e s ，c l u s t e r i n g 1 1 1 第1 章引言 第1 章引言 近年来，综合了传感器技术、嵌入式计算技术、分布式信息处理技 术和通信技术的传感器网络的出现，引起了人们了的极大关注。如何高 效的处理传感器网络的海量数据流，以及如何存其中获取有用的知_ i ； ， 成为我们新的挑战。无处不在的数据挖掘( u b i q u i t o u sd a t am i n i n g ，简 记u d m ) 是解决这个问题的方法之一。本章将讨论传感器网络相关技术 研究综述、数据挖掘技术在传感器网络中的应用以及本文主要的研究工 作。 1 1 研究背景 随着通信技术、嵌入式计算技术和传感器技术的飞速发展和同益成 熟，具有感知能力、计算能力和通信能力的微型传感器开始在世界范围 内出现。由这些微型传感器构成的传感器网络引起了人们的极大关注。 这种传感器网络综合了传感器技术、嵌入式计算技术、分布式信息处理 技术和通信技术，能够协作地实时监测、感知和采集网络分布区域内的 各种环境或监测对象的信息，并对这些信息进行处理，获得详尽而准确 的信息，传送到需要这些信息的用户。例如，传感器网络可以向正在准 备进行登陆作战的部队指挥官报告敌方岸滩的详实特征信息，如丛林地 带的地面坚硬度、干湿度等，为制定作战方案提供可靠的信息。传感器网 络可以使人们在任何时间、地点和任何环境条件下获取大量详实而可靠 的信息。因此，这种网络系统可以被广泛地应用于国防军事、国家安全、 环境监测、交通管理、医疗卫生、制造业、反恐抗灾等领域。传感器网 络是信息感知和采集的一场革命。传感器网络作为个全新的研究领域， 黑龙江大学硕士学位论文 在基础理论和 二程技术两个层丽向科技工作者提出了大量的挑战性研究 课题。 传感器网络的感知数据流巨大，传感器网络中的每个传感器通常都 产生较大的流式数据，并具有实时性。每个传感器仅仅具有有限的能量 和计算资源，难以处理巨大的实时数据流。面对海量的数据，人们当然 不会仅仅满足对这些数据的简单查询。从信息处理的角度，人们更希望 计算机帮助我们分析数据、理解数据，帮助我们基于丰富的数据作出决 策，做人力所不能及的事情。这种数据的爆炸性的增长业已激起对新技 术和自动工具的需要，以便帮助我们把海量的数据转化成有用的信息和 知识。基于传感器网络自身的特性，集中式的数据流挖掘算法已经很难 应用到传感器网络中了，我们需要研究强有力的分布式数据流挖掘方法。 1 1 1 传感器网络概述 传感器网络【2 l 是由一组传感器以a dh o e 方式构成的有线或无线州 络，其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象 的信息，并发布给观察者。 在不同应用中，传感器网络节点的组成不尽相同，但一般都由传感 部件、处理部件、传输部件和电源部件这4 部分组成，如图1 1 所示口l 。 根据应用，传感器节点还可以包含位置定位系统、能源产生器和移动部 件。传感部件用于感知、获取外界的信息，并将其转换为数字信号。处 理部件负责协调节点各部分的工作，如对感知部件获取的信息进行必要 的处理、保存，控制感知部件和电源的工作模式等。传输部件负责与其 他传感器或观察者的通信。电源部件为传感器提供正常工作所必需的能 源。被监测物理信号的形式决定了传感器的类型。处理器通常选用嵌入 第1 章引言 式c p u ，如m o t o r o l a 的6 8 h c l 6 ，a r m 公司的a r m 7 和i m e l 的8 0 8 6 等。数据传输部件主要由低功耗、短距离的无线通信模块组成，比如r f m 公司的t r l 0 0 0 等。因为需要进行较复杂的任务调度与管理，系统需要 个微型化的操作系统，u cb e r k e l e y 为此专门开发了t i n y o s ”，当然， “c o s 和嵌入式l i n u x 等也是不错的选择。 图1 1 传感器网络节点的组成 圈1 2 是一个分布式的无线微型传感器网络的示例。图中，由微型 的无线传感器节点构成的a dh o c 网络正被用于监测一个动态的物理环 境。传感器节点散布在感知区域内，每个节点都可以收集数据，并通过 “多跳”路由的方式把数据传送给g a t e w a y ，g a t e w a y 也可以用同样的方 式将数据发送给各节点。g a t e w a y 直接与i n t e r n e t 相连，通过i n t e r n e l 实 现任务管理节点( 即观察者) 与传感器之间的通信。 图1 2 分布式无线微型传感器网络的结构图 黑龙江大学硕士学位论文 1 1 2 传感器网络的特点 传感器网络除了具有a dh o c 网络的移动性、断接性、电源能力局限 等共同特征以外，还具有很多其他鲜明的特点1 5 1 。 首先，传感器网络中每个传感器节点使用的都是嵌入式的处理器和 存储器，它的能力和存储容量有限，所以它的计算能力比较低。有的传 感器使用f l a s h r a m ，但其容量很小，一般在几k 到几m ，存取速度也 较慢。 其次，传感器的电源能量极其有限，网络中的传感器由于电源能量 的原区i 经常失效或废弃。而且传感器传输信息要比执行计算更消耗电能。 传感器传输l 位信息所需要的电能足以执行30 0 0 条计算指令。电源能 量约束是阻碍传感器网络应用的严重问题。 再次，传感器的通信能力也是影响传感器网络性能的重要因素。传 感器网络的传感器的通信带宽窄而且经常变化，通信覆盖范围只有几十 到几百米，还会经常受到障碍和建筑物的阻挡及干扰。传感器之间的通 信断接频繁，经常导致通信失败。 最后，传感器数量大，分布范围广，产生的感知数据流巨大。而每 个传感器自身的计算资源，存储资源，能量都十分有限，无法执行大规 模的计算。所以，这一特点对网络的性能影响也较大。 还有，传感器网络还有网络动态性强以及存在大规模分布式触发器 等特_ 。 传感器网络的上述特点向我们提出了新的挑战。在短期内迅速提高 传感器自身的计算能力，存储能力，通信能力和电源能量不是解决问题 的可行方法。我们应该考虑如何充分利用传感器网络中各个节点的计算 资源，开发分布式算法，在尽可能满足用户需求的情况下减少传感器网 第1 章引言 络中节点的能量歼销和延长网络的生命周期。 传感器网络的性能直接影响其可用性，至关重要。如何评价一个传 感器网络的性能是一个需要深入研究的问题。在文献 5 中提出了几个评 价传感器网络性能的标准，包括传感器网络的能源有效性，生命周期， 时间延迟，感知精度，可扩展性，容错性等。这些标准还没有达到实用 的程度，需要进步地模型化和量化。 1 1 3 传感器网络的研究问题 在一个比较抽象的级别上，可以将传感器网络分为5 层【5 j ，如图1 3 所示： 图1 3 传感器网络的抽象结构 基础层以传感器集合为核心，包括每个传感器的软、硬件资源，如 传感部件、嵌入式处理器与存储器、通信器件、嵌入式操作系统、嵌入 式数据库系统等。网络层包括通信网络、支持网络通信的各种协议和软、 硬件资源。数据管理与处理层以传感器数据管理与处理软件为核心，包 括支持感知数据的采集、存储、查询、分析、挖掘等各种数据管理和分 析处理软件系统，有效地支持感知数据的存储、查询、分析和挖掘，为 用户决策提供有效的支持。应用开发环境层为用户能够在基础层、网络 层和数据管理与处理层的基础上开发各种传感器网络应用软件提供有效 的软件开发环境和软件工具。应用层由各种传感器网络应用软件系统构 黑龙江大学硕士学位论文 成。 本文必注的是数据管理与处理层的问题，重点研究感知数据的挖掘 技术。感知数据挖掘技术的研究主要包括相关舰则等传统类型知识的挖 掘、与感知数据相关的新知识模型及其挖掘技术的研究、感知数据的分 布式挖掘技术的研究。 显然，感知数据管理和处理技术的研究是一项实现高效率传感器网 络的重要和关键的任务。遗憾的是，到目前为止，感知数据管理和处理 技术的研究还不多，还有大量的问题需要解决。感知数据管理与处理技 术的研究是数据库界面临的新任务和新挑战，也为数据库界提供了新机 遇。 传感器网络中的每个传感器通常都会产生巨大的流式数据，并具有 实时性。每个传感器仅仅具有有限的计算资源，难以处理巨大的实时数 据流。我们需要研究强有力的分布式数据流挖掘方法。现有的集中式的 数据流挖掘方法很难直接应用到传感器网络中来，他们在以下几方面都 有些局限性： 首先，一遍扫描算法所使用的内存问题没有被充分的考虑。一个具 有高内存消耗的数据流挖掘算法就不能被应用于许多环境，比如传感器 网络。 其次，现有的在数据流中进行数据挖掘的技术仍然是计算密集的， 如果数据到达的太快的话，它可能跟不上数据流的速度，从而造成有崩 信息的丢失。 再次，现有的数据流挖掘算法都是针对单一数据流的。传感器网络 中的每个传感器都会产生一个数据流，而且每个传感器都有一定的计算 能力和存储能力，虽然很有限，但我们应该充分利用他们自身的计算资 源，开发分布式的数据流挖掘算法，提高挖掘的速度和效率。 第j 章引言 最后，关于帮助提高整个数据流挖掘过程方面的研究很少。在传感 器网络中，如果整个挖掘过程没有被优化的话，单个的挖掘任务也会受 到限制。 基于以上几点，本文设计了低内存消耗的计算高效的分布式数据流 挖掘算法，并研究了相应的系统支持，来优化整个挖掘任务。 1 2 国内外的研究现状 由于传感器网络的巨大引用前景，其研究正逐步受到各国研究人员 的重视。美国的加州大学伯克力分校、康奈尔大学等学校开始了传感器 网络的基础理论和关键技术的研究。其他一些发达国家的大学和研究机 构也纷纷开展了该领域的研究工作。我国的哈尔滨工业大学和黑龙江大 学也开始了对传感器网络的研究。学术界已经开展了一些感知数据查询 处理技术的研究，取得了。+ 些初步研究结果。 康奈尔大学在感知数据查询处理技术方面开展了较多的研究j ：作 6 j 。他们研制了一个测试感知数据查询技术性能的c o u g a r 系统，探索 了把传感器网络表示为数据库的思想，探讨了如何把分布式查询处理技 术应用于感知数据查询的处理。 加州大学伯克力分校研究了传感器网络的数据查询技术，应用数据 库技术实现了传感器网络上的数据聚集函数，提出了在低能源、分布式无 线传感器网络环境下实现聚集函数的方法，并研制了一个感知数据库系 统t j n v d b t ”。南加州大学还研究了传感器网络上的聚集函数的计算方法， 提出了节省能源的计算聚集的树构造算法，并通过实验证明了无线通信 机制对聚集计算的性能有很大的影响刚。 哈尔滨工业大学和黑龙江大学在传感器数据管理系统方面开展了研 黑龙江大学硕士学位论文 究工作，提出了以数据为中心的传感器网络的数据模型，设计了一系列的 能源有效的感知数据操作算法和感知数据查询处理技术，并研制了一个 传感器网络数据管理系统 9 - i t l 。 美国马里兰州立大学的h i l l o lk a r g u p t a ，r u c h i t ab h a r g a v a 等人为实 时的车辆监控开发了一个移动的分布式数据流挖掘系统( ”】。他们在车辆 中安装一个传感器，通过不断监控车辆中传感器产生的数据流，鉴别突 发模式，并通过无线网络将其汇报给远程的控制中心。 b h a s k a r k i s h n a s w a m y 和s i t h a r a m a i y e n g a r 开发了个传感器网络中 容错的事件区域检测的贝叶斯算法i ”i 。他们检测所关一t l , 的环境中发生的 事件的区域，如在环境中哪些区域中的化学物质的浓度大于一个阙值。 算法只做了一些挖掘的初步工作。 1 3 本文的贡献 本文的主要研究成果包括： 1 传感器网络中的数据分类问题。传感器网络中的数据流大部分都 是数值属性，如果每个不同值都成为候选的划分点，就会导致非常高的 通信和存储负载。本文使用了数值间隔剪枝策略，将数值属性按取值范 围划分成若干间隔，将不太可能含有划分点的间隔剪枝，减少了处理数 值属性的时间。本文还使用了抽样的方法，并且在准确性上保证了概率 的界限。最后，本文基于传感器网络的特性，采用雨林算法框架，设计 了一个分布式的决策树分类算法。该算法有效的减少了分类时所需处理 的数据量，减少了内存的需求和计算时间。 2 研究了传感器网络中的关联规则挖掘算法。关联规则挖掘的关键 就是如何产生频繁项集。本文首先分析了频繁项集挖掘算法在分布式数 第1 章引言 据流的环境中的特点和需要解决的问题。本文采用了树型的层次通信结 构，每个传感器先采用e 近似算法生成局部频繁项集，然后将局部的频 繁项集逐层上传，进行合并。不断重复这个过程，直到根节点收到所有 孩子节点上的局部频繁项集。最后，南根节点将局部的频繁项集合并成 全局的频繁项集，并且在准确性上保证了概率的界限。实验证明，该算 法是在传感器网络中进行分布式关联规则挖掘的种有效方式。 3 本文提出了一个基于传感器网络的分布式k 平均聚类算法。首先 由网络中的中心节点s i n k 产生切始的k 个簇的质心，并将其下发到传感 器网络中，各个节点将本地数据分别划分到k 个簇中，并将簇的相关信 息根据传感器网络的通信结构逐层上传，合并。最后，由s i n k 节点重新 计算k 个簇的平均值，如果不满足误差准则，则产生新的k 个质心，重 复上述过程，直到误差准则收敛，输出全局的k 个簇的质心。实验证明， 该算法能够高效而准确地对传感器网络中的数据进行聚类分析。 4 基于以上算法，本文实现了一个传感器网络卜的数据挖掘原型系 统。该系统向用户提供传感器网络数据的分类，关联规则挖掘，聚类分 析的功能。 1 4 论文结构 本文分为六个部分。 第一章引言。介绍了本文的研究背景、传感器网络上的数据挖掘的 意义，国内外的研究现状、本文主要研究工作，阐明了本文的研究意义 和学术价值。 第二章背景知识，介绍了数据挖掘的有关知识，以及无处不在的数 据流挖掘的问题和方法。 黑龙江大学硕士学位论文 第三章传感器网络中分类算法的研究。在对已有的分类算法深入研 究的基础上，采用抽样的方法，应用数值属性间隔剪枝策略，设计了基 于传感器网络的分布式的数据流分类算法，在准确性上保证了概率的界 限并给出了相应的实验结果。 第四章传感器网络中关联舰则挖掘算法的研究。分析了频繁项集挖 掘伍分布式数据流环境中的特点和需要解决的问题。提出了基于传感器 网络的分布式关联规则挖掘的近似算法，采用树型的层次通信结构，将 局部频繁项集合并成全局的频繁项集，并且在准确性上保证了确定性的 界限。 第五章传感器网络中聚类算法的研究。通过对传统的聚类算法k 平 均的深入研究，提出了基于传感器网络的分布式k 平均聚类算法，并给 出了相关实验结果与分析。 第六章传感器网路数据挖掘原型系统的设计与实现。本章简述了 s e n s o r m i n i n g 原型系统的实现方法和各部分的功能。 最后，给出了本文的结论，不足之处和未来的工作。 第2 章背景知识 2 1 数据挖掘技术 第2 章背景知识 随着信息技术的高速发展，人类积累了大量数据。条码技术在商业 领域的广泛使用、政府和商业领域事务处理的计算机化以及数据采集工 具能力的提高，不断产生和搜集的数据量呈爆炸性增长。全球拥有的数 据量每2 0 个月翻番。我们不仅拥有极其庞大的数据，而且它们的数据 类型越来越复杂、结构越来越多样，使得应用系统面临着海量数据处理 和数据多样性的挑战。 然而数据量的急剧膨胀并没有给我们在信息获取方面带来理想中的 便捷，人们很难从类似的大规模数据中获得对数据高度概括性的知识。 出现了数据危机，被人们描绘为“人类正被数据所淹没，但却饥渴于知 识( w ea r ed r o w n i n gi ni n f o r m a t i o n ，b u ts t a r v i n gf o rk n o w l e d g e ) ”。这导 致了数据挖掘技术的出现。数据挖掘技术旨在从大量数据中挖掘出有用 的知识提供给人们，辅助人们进行科学分析和决策。短短的十几年里， 数据挖掘引起了人们的极大关注，现已成为一个热门的研究方向。 数据挖掘，也称知识发现( k n o w l e d g ed i s c o v e r yf r o md a l a s e t ，简记 k d d ) ，被描述为从数据中抽取出隐含的、具有潜在用途的、人类可理解 的模式。数据挖掘通过发现有用的新规律和新概念，提高了数据拥有者 对大量原始数据的深层次理解、认识和应用 1 4 1 。 一般地，数据挖掘的任务可以分为两大类：描述性数据挖掘和预测 性数据挖掘。前者用简单和总结的方式描述数据，表示出人们感兴趣的 一般数据特点；后者则构造一个或一组模型。完成在有效数据集上的推 黑龙江大学硕士学位论文 论，并且能够预测新的数据集合的行为。一个数据挖掘系统可以完成以 f 任务中的一个或几个： ( 1 ) 类描述( c l a s sd e s c r i p t i o n ) 。类描述为数据集合提供个简单 的概括( s u m m a r y ) ，并且把它们与其他的类加以区分。类描述分为类特征 和类比较两种。对一个数据集合的概括称为类特征，两个或多个数据集 合之间的比较称为类比较。 ( 2 ) 关联( a s s o c i a t i o n ) 。关联是指在事务处理( t r a n s a c t i o n p r o c e s s i n g ) 数据中发现项目集合之间的关联关系和相关性，关联规则表示为a j b 。 这种关联分析广泛地应用于直销、目录设计、商业决策等领域。它的最 初问题是超级商场的售货交易数据( b a s k e td a t a ) 分析，即超级商场售货 交易记录分析。商场经营者希望发现顾客的购买习惯，包括顾客通常同 时购买的商品有哪些? 顾客购买一种( 或几种) 商品通常还会购买哪种 ( 哪几种) 商品? 如顾客的购货交易( 一次购物的商品) 会同时有牛奶 和面包，即顾客购买牛奶时通常还会购买面包。关联规则涉及到乏静复 和可借度概念。例如，如上规则可表示为“牛奶j 面包，2 0 ，8 0 ”，其 中2 0 年n8 0 分别代表支持度和可信度，表示在所有顾客中有2 0 的顾 客购买了牛奶，在购买牛奶的用户中有8 0 会去购买面包。这些关联规 则可以辅助管理者制定商品在货架上的摆放顺序，促销方案和贷物的采 购方案等。 ( 3 ) 分类( c l a s s i f i c a t i o n ) 。数据分类是从训练数据中发现同类数据 对象的共性，建立一个类的判别模型，并用该模型为新出现的数据进行 类别识别的一个过程。在数据分类中，一个样本数据集合被当作一个训 练集，训练集中的每个样本都拥有一些特征描述数据，并且每一个样本 都有一个类的标识符标记它所属的类别。分类的目标是首先对训练数据 集合进行分析，使用数据的某些特征描述，给出每个类的准确刻画，然 第2 章背景知识 i i i i i i 嗣ii ii 鼍 后使用这些描述，对总数据库中的其它数据进行分类。分类的结果是为 每个类产生易于机器处理的描述也即分类规则，它可以表示为分类树 或规则集的形式。用这些舰则集或分类树为将来的数据分类。分类技术 被广泛的应用于顾客分类、交易建模、信用分析以及医疗诊断等领域。 ( 4 ) 聚类( c l u s t e r i n g ) 。聚类是通过对数据对象间相似性的整体分 析之后，对数据对象进行分类。聚类问题可定义为给定数据对象集合， 去找出数据对象l b j 的相似性，并咀此对数据对象进干亍分类处理的一个过 程。使得相似程度高的数据对象分在同一类，相似程度低的数据对象分 在不周的类。相似性可由用户或专家指定的某种距离函数表示。一个好 的聚类方法可以得到高质量的聚类，即类与类之间相似性很小，每个类 内的数据则相似性极高。 聚类同分类的区别在于聚类属于无监督学习，分类属于有监督学习。 分类的训练样本数据事先被指定所属类。与此相反，聚类问题的初始数 据不仅不指定所属类，甚至可能存在多少个类都是未知的。 ( 5 ) 时间序列分析( t i m e - s e r i e sa n a l y s i s ) 。时间序列分析是指通过 分析比较大的时间序列数据集合，发现某些规律和感兴趣的特征。时间 序列分析包括查找相似的序列或者子序列、挖掘序列模式和周期性、趋 势及偏差分析。例如，可以根据一个公司股票的历史数据、商业状况、 竞争者的能力和当前的市场情况，分析这个公司股票发展趋势。 ( 6 ) 预测( p r e d i c t i o n ) 。预测是指用于对未来或未知的变化趋势的 预言和猜测，还包括对一些丢失数据可能值的预测。例如，一个职员可 能的工资，可以根据公司中与他相似的职员的工资分布情况进行预测。 又例如，对货币汇率未来变化趋势的预测。一般地，回归分析、一般化 线性模型、相关性分析、遗传算法和神经网络模型都是预测的有用工具。 数据挖掘方法主要是利用挖掘出的关联规则、分类规则、聚类规则或时 黑龙江大学硕士学位论文 间序列模式进行预测。 数据挖掘的关键技术在于商效的数据挖掘算法，它们决定数据挖掘 过程的效率。数据挖掘算法的评价标准同其它算法的评价标准基本相同。 目目口主要考虑算法的时间复杂性、空间复杂性和t o 复杂性等指标。 另外，在算法效率和解答精度之问采取了折衷的策略，部分算法使 用了近似算法。所以这些近似算法还要评价其精度指标。 从挖掘的知识角度还存在知识的有用性、有效性、可理解性和有趣 性等度量【”】。但由于这些度量还没有公认的、致的标准，所以难以给 出严格的客观评价。 2 2 无处不在的数据挖掘技术 无处不在的数据挖掘( u b i q u i t o u s d a t a m i n i n g ，简记u d m ) 是指在 移动的，嵌入式的和无处不在的设备上执行数掘分析的过程1 1 6 】。它代表 了下一代数据挖掘系统，这种系统能够支持移动用户智能的，时间关键 的信息需求，并且它还面临着任一时间，任一地点的数据挖掘问题【1 6 - 1 8 1 。 u d m 系统的关键是在移动环境中执行计算密集的数据挖掘技术，同时这 利，环境具有有限的计算资源，而且网络特性也不不断变化坶j 。 随着移动设备计算能力的增加以及无线网络的广泛应用，无处不在 的计算环境面临这一种新的应用，称为无处彳；在的数据挖掘( u d m ) ， 也就是移动用户在其中可以执行数据监测以及智能分析m 1 7 娜。0 1 。典型的 方案包括： 在旅行时监测股票交易市场的流式信息【1 6 】： 为了进行冲突监测或者实验室实验而进行的持续的监测和状态 信息分析【2 0 ； 第2 章背景知识 i i i i i i 鼍i i i i i i i i i i ii i 一 通过分析移动车辆上的传感器信息来避免发生严重的交通事故 i t 2 ； 对一个传感器网络产生的数据进行初步的挖掘州； 天文学和地球物理学数据的在线分析2 ”3 1 ； 要注意，无处不在的数据挖掘不等于在资源有限的设备上执行传统 的数据挖掘任务，而是要考虑不同应用的独特需求，也就是要在个时 问关键和移动的上下文中进行数据分析。 下面，我们给出在处理数据流我们所面临的问题与挑战以及一些 现有的解决办法： 处理不断到来的数据流： 最小化移动设备的能量消耗； 由持续的数据流导致的无限制内存需求； 处理结果的准确性； 在无线网络中用有限的通信带宽传输数据挖掘结果； 在移动设备的f i b j , 的屏幕上实现数据挖掘结果的可视化； 对挖掘结果随时问的改变建模： 交互的挖掘环境来满足用户的需求。 传统的数据挖掘技术很难直接应用到数据流中，这是因为过去的挖 掘算法通常都要扫描数据多次。数据流挖掘只允许扫描数据次，在技 术上还要能跟得上数据到达的速度。而且，动态的数据流还带来了新的 挑战，因为它们约分布可能在不断的变化。最近，一些算法被用来解决 这些问题。这些算法集中于近似一遍扫描算法，挖掘动态数据流，以及 挖掘数据流的变化和趋势等。 近几年，人们在数据流上又开发了新的算法，大体上可以分为以下 三个方向： 黑龙江大学硕士掌位论文 萱萱宣i i i i i i i i i i i i i i i i i i i 皇i | 置萱吉宣i i i i i 誓 11 i i i 葺i | | i _ i 挖掘静念数据流的近似算法。在静态数据流中，每一个到达的数据 都是一个固定的分布中的随机实例。d o m i n g o 2 4 , 2 5 研究了解决决策树 分类算法和k 平均聚类算法的抽样方法；m a n k u 和m o t w a n i 开发了 一种基于计数的方法来挖掘数据流中的频繁项集”j 。斯坦福大学的 数据流组开发了近似的k 一中心点聚类算法，它保证了概率性的界限 【2 7 t 9 1 。 i i 研究动态的数据流。有两种方法来解决这个问题。是假设用户不 知道数据流什么时候会改变。h u l t e n i ”】提出了c v f d t 方法来构建随 时闯变化数据流上的决策树。另一种被许多研究小组所采用的方法 是应用嵌入式分类器。a g g a r w a l 提出了一种数据流中的聚类问题的 框架f 3 l 】。另种方法是假设用户了解一些数据流变化的方式，并且 允许他们定义窗口模型来挖掘动态数据流。d e m o n 方法f ”认为动 念环境是通过系统的增加数据或删除数据来发展的。l e e 3 3 1 在大数据 集合上开发了一个滑动窗口模型。最近，g i a n n e l l a 3 4 1 设汁了一种数 据流关联规则挖掘算法，称为f p s t r e a m ，它是基于倾斜的滑动窗【 模型的。 i i i 在动态数据流中挖掘数据的变化和趋势。g a n t i 提出了一种框架来量 化由不同数据集合归纳出来的模型之间的区别3 ”。d o n g 和l i l ”3 研究 了数据集合之间找新兴模式的方法。z h u 和s h a s h 研究了在数据流中 出现不平常聚集的时候，如何执行高效的冲突检测方法1 3 们。p e i 提出 了种密度列表表示方法来描述数据流中聚类的变化3 8 】。 a g g a r w a l 39 1 ，p r a t t 和t s c h a p e c k 4 0 1 ，和p e i 【3 8 1 研究了可视化的技术来 帮助发现动态数据流中趋势。 以上都是基于单数据流上的算法，没有考虑分布式数据流上的数据挖掘 方法。本文基于传感器网络的特性，提出了分布式的数据流挖掘方法。 第3 章传感器网络中分类算法的研究 i i i i i _ i _ _ i i i i _ _ _ _ _ i i i i i i i _ _ i - _ - 第3 章传感器网络中分类算法的研究 数据分类是数据挖掘中比较重要的一个研究课题。本章在深入研究 已有t 作的基础上，基于传感器网络自身的特性，设计了新的分布式决 策树分类方法。 3 1 引言 数据分类是从数据库中发现同类数据对象的共性，给与描述和刻画， 并将未知类别的数据对象归类到已知类别的过程。在数据分类过程中， 将一个样本数据库作为训练集，训练集中的每条记录有一个类属性值， 数据对象的类属性值是已知的。分类算法通过分析训练集，为每一类构 造一个模型，产生决策树或者类规贝u 集合。利用它们可以更好地理解每 个类，并可以应用到未知数据的分类判别中。 数据分类的算法很多，包括决策树、支持向量机、统计学和神经网 络、粗糙集和最邻近等方法。在这些方法中，基于决策树的分类方法与 其它的分类方法比较起来，具有速度较快、较容易转换成简单的并且很 容易理解的分类规则、也较容易转换成数据库查询语句、有时可得到更 高准确度等优点。 传统的分类方法在处理大数据量时会出现性能下降或者精度降低的 问题。为此，r ，a g r a w a l 等人提出了s l i q l 4 1 i 算法和s p r i n t 算法4 ”，可 以处理通常数据量的数据分类问题。该算法的精确度高，可以同时控制 数值型和范畴型属性。在决策树的构造阶段采用了预排序技术，并与宽 度优先增长策略相结合，使得能够对保存在磁盘上的数据进行分类。在 修剪阶段，采用了基于m d l 原理的方法，时间复杂性很小。但是s l i q 黑龙江大学硕士学位论文 需要把整个类列表保存在内存中才会有效，否则算法的效率很低。当数 据量增大时对内存的要求增大，成为该算法性能的芏要障碍。s p r i n t 算法克服了对内存的限制，性能较好。j g e h r k e 等人提出了雨林 ( r a i n f o r e s t ) 算法框架【4 3j 大数据集决策树快速生成框架。雨林算法框 架关注于提高决策树算法的伸缩性，该框架可运用于大多数决策树算法 ( 例如s p r i n t 和s l i q ) ，使算法获得的结果与将全部的数据放置于内存所 得到的结果一致，但是在运行时叮以使用较少的内存。而在内存定的 情况下，也可以更好的满足算法的需求。生成的决策树的质量取决于具 体的决策树算法，于该框架无关。 分类方法分为精确分类和近似分类两种。s l i q 和s p r i n t 方法是精 确分类方法，离散化方法和抽样方法是近似分类方法。s l i q 和s p r i n t 分类算法解决了内存上的限制问题，但在处理大数据量的数据分类时， 变成一种非常费时的操作。近似分类方法可以得到更快的响应时间，但 它是用精度作为代价。 最近，在数据流上分类算法的研究引起了人们的重视。d o m i n g o s 研 究了一种数据流上决策树分类的一遍扫描算法v f d t r 2 “，该算法在构建 决策树的准确性上保证了概率性的界限。但是该算法只考虑了枚举属性， 没有考虑如何处理数值属性。本文也再次研究了这个问题，并对该算法 进行了改进，使之能够高效的处理感知数据流的大量数值属性，对其进 行准确的分类。 在处理传感器网络数据分类问题时，本文采用了基于拙样的分布式 的分类算法，它具有良好的可扩展性，在提高数据分类效率的同时，精 度也得到了很好的控制。 第3 章传感器网络中分类算法的研究 3 2 算法的理论基础 本章的分类算法采用信息论中信息熵的方法构造决策树，下而给出 几个跟算法有关的概念。 定义3 - 1 ( 训练集) 设数据集合上芦，恐，墨) ，其中每一个记录 形式为x = ，c i 称为记录的分类属性值，工，称为记录 的条件属性值。整个d 称为训练集合，简称训练集。分类属性的值域为 c 。条件属性的值域分别为d ，d ? ，d 。 定义3 - 2 ( 分类模式) 设存在训练集d ，分类模式p 是指存在个 可计算的映射厂，满足条件f ：d ，x d z x x 现寸c 。使得 d ( ，( x ，) ，cr ) i ，