数据流聚类算法及其应用(可编辑).doc

《数据流聚类算法及其应用(可编辑).doc》由会员分享，可在线阅读，更多相关《数据流聚类算法及其应用(可编辑).doc（35页珍藏版）》请在三一办公上搜索。

1、数据流聚类算法及其应用 南京邮电大学硕士学位论文数据流聚类算法及其应用姓名:余志虎申请学位级别:硕士专业:计算机应用技术指导教师:程春玲2011-03南京邮电大学硕士研究生学位论文 摘要摘 要近年来,伴随着网络信息技术的高速发展,产生了一种新式的数据模型?数据流。它常常产生于 web上的用户点击、网络入侵检测、实时监控系统或无线传感器网络等动态环境中。相比较传统据集,这些海量的数据流具有快速性、连续性、变化性、无限性等特点,使数据流的挖掘面临着新的要求和挑战。聚类分析作为数据挖掘领域的一个重要课题,能够使未标记数据按照指定属性分组为不同的类,在近期得到广泛研究和高度重视。本文以数据流聚类算法为

2、研究内容,异常数据点的检测为研究目标,主要作了以下三个方面的工作:1 总结了数据流模型及其聚类的相关概念和技术,并描述了数据流聚类的特殊要求以及目前国内外数据流聚类算法。同时说明了异常检测的定义、现有方法以及当前所面临的挑战。 2 在高速网络中,数据流具有高速、突发等特性,使得高速网络中的异常检测成为一个难点。本文提出了一种基于 SSClu树的流聚类算法用于高速流的异常检测。算法首先引入一种维持数据流概要信息的 SSClu树;然后针对数据流的高速特性,采用预先聚集和缓存机制。预先聚集是在数据流对象插入 SSClu树聚类之前对其进行预先聚类的过程,以处理突发高速数据流的到达;缓存机制是用于当高速

3、流到达时,暂存当前来不及处理的数据流对象,解决了高速流不能及时聚类的问题。仿真结果表明,本算法能及时处理高速数据流,且具有较高的聚类精度,保证了高速流下异常检测的准确性。 3 针对无线传感器网络中的离群点检测问题,考虑到无线传感器网络Wireless Sensor Network,WSN环境分布式以及能源消耗的限制,提出了一种基于相似性群集模型的流聚类算法Stream Cluster algorithm Based on Similarity Flocking model,SCBSF。算法采用一种模拟群体运动的群集模型将数据自我组织来形成聚类,这种自组织性更加适用于分布式环境批量数据点的聚类;

4、同时通过群集规则来完成任意形状簇的聚类,而不需要采用传统二阶段聚类思想,减少了算法计算和存储复杂度;考虑到 WSN中算法的能耗问题,在采集节点端,利用初始聚类信息来临时记录所产生的相似数据特征,以此来减少数据传输从而达到降低通信能耗的效果。仿真结果表明,算法不仅具有较好的离群点检测效果,同时也降低了聚类过程中数据计算和传输的能源消耗。关键词: 数据流模型,聚类算法,异常检测,高速流,无线传感器网络 I 南京邮电大学硕士研究生学位论文ABSTRACTABSTRACTRecently, with the rapid development of information technology, a

5、new data model called the data stream appears. It often arises from dynamic environment such as user clicking on the web, network intrusion detection, real-time monitoring systems or wireless sensor networks. Compared to traditional data sets, these vast amounts of data streams have fast, continuity

6、, variety, infinity and other characteristics. So data stream mining is facing new demands and challenges. Cluster analysis as a data mining tool is an important topic, because it makes the data without marker group into different classes in accordance with the specified attributes, and has been wid

7、ely studied and highly regarded in the near future. In this paper, we do research on data stream clustering algorithm and anomaly detectionThe main tasks are described as follows: 1 We make a summary of the data flow model and related concepts of cluster, and describe the special requirements and ar

8、ithmetic of current data stream clustering; the definition of anomaly detection, the existing methods and current challenges are also illustrated latterly2 In the high-speed network, data streams with high-speed and sudden features make high-speed network anomaly detection become a difficulty. A str

9、eam clustering algorithm based on SSClu tree for high-speed flow anomaly detection is proposed. The algorithm firstly introduces an SSClu tree to maintain summary information of the data stream; and as for high-speed characteristics of data stream, we use the pre-aggregation and the caching mechanis

10、m. The pre-aggregation is a process of beforehand cluster before data flow objects was inserted into SSClu tree clustering in order to dispose the situation of high-speed data stream; the caching mechanism temporarily is used to save the flow of data currently being processed to solve the arriving b

11、urst data stream. The simulation indicates that the algorithm can not only handles high-speed data streams in a timely manner, but also has a high clustering accuracy and ensures the high accuracy of anomaly detection3 Taking into account constraints of distributed environment and energy consumption

12、 in the wireless sensor network Wireless Sensor Network, WSN, a clustering algorithm is proposed based on similarity flocking model stream SCBSF to solve the outlier detection for Wireless sensor networks. This algorithm use a flocking model simulating swarm activity to form self-organizing II 南京邮电大

13、学硕士研究生学位论文ABSTRACTdata clustering to make the algorithm more suitable for distributed environments of large data collected sets ; it also completes clustering of arbitrary shape by flocking rule without thinking of the traditional two-stage clustering to reduce the algorithm computation and storage

14、complexity; taking the energy consumption into account in WSN, we reduce communication energy through collection nodes which use the initial cluster information .The initial cluster information is generated by the temporary similar data characteristicsSimulation shows that the algorithm not only has

15、 a good results of outlier detection, but also reduces the clustering process data calculation and transmission of energy consumption Key words: Data Stream Model, Clustering Algorithm, Anomaly Detection, High-speed Stream, Wireless Sensor NetworksIII南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得

16、的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包 含其他人已经发表或撰写过的研究成果,也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名:_ 日期:_南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档,可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外,允许论文被查阅和借阅,可以公布(包括刊登)论文的全部或部分内容。 论文的公

17、布(包括刊登)授权南京邮电大学研究生院(筹)办理。研究生签名:_ 导师签名:_ 日期:_南京邮电大学硕士研究生学位论文 每一章绪 论第一章 绪 论 本章中首先介绍了数据流聚类及异常检测的研究背景,然后给出了数据流模型及数据流聚类的基本概念,接着描述了数据流国内外研究现状以及相关技术,最后介绍了本文研究内容和组织结构。 1.1 课题研究背景网络监测中的数据包流、Web 上的用户点击数据流、通信领域中的电话记录数据流、卫星传回的图像数据流、金融领域的证券数据流、各类传感器网络中的检测数据流以及零售业务中的交易数据流等形成了一种与传统数据库中静态数据不同的数据形态。这些数据流产生的数据量在多个应用领

18、域中迅速增长,小型无线传感设备的广泛使用将进一步使数据流体积的增长速度提高几个数量级。而且,产生数据流的应用通常要求在线实时处理,如何及时有效地处理数据流,从中挖掘出有用的知识,将对多个应用领域产生重大意义。 数据挖掘是从大量数据集中发现用感兴趣的或者隐藏的模式,从上面所列举应用可以看出,数据流中数据挖掘的作用已经不言而喻,同时引起了各行业专家和学者的关注和研究。聚类分析作为数据挖掘中经常运用的分析方法,在数据流的挖掘中已经广泛使用,并且有着很广阔的应用前景;同时异常检测也是数据流挖掘领域的一个研究热点,各种数据流应用的安全问题已经不容忽视,所以本文主要以数据流聚类为研究基础,利用聚类分析方法

19、来达到异常检测的目地。 传统的数据挖掘一般都是在静态的数据库或信息仓库中处理,这些被处理的数据对象其特点就是有限的、静态的、非递增中,但对于科学发展的今天,人们得到的信息量是成倍的增长,数据的来源也是越来越多样化,因此需要处理那些庞大的数据集,这些数据都是以很快的速度无限不停的产生,并且是随着时间的变化而变化,这就是一种新式数据模型流1 2数据 。流数据的特点是数据持续到达,且速度快、规模大 。其研究核心是设计高效的单遍3数据集扫描算法 ,在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构?4?概要数据结构 ,使得在任何时候都能够根据这个结构迅速获得查询结果。基于数据流计算的研究与应

20、用是目前国际数据库研究领域的一个热点。数据流上的异常检测技术由于在诸5如互联网监控、金融分析、传感器网络、天气或环境监测等领域中 广阔的应用前景也受到1 南京邮电大学硕士研究生学位论文 每一章绪 论学术界和工业界越来越多的关注。 聚类是目前一种非常有用且普遍的数据分析工具,它主要用于在数据对象不能预先分类的情况将其按照某种特征或者属性的相似度进行分组成簇,它的关键是聚类,这些被分组的对象簇内之间高度相似,而簇和簇之间则相异,它不同于分类方法,聚类是在不知道数据对象标记的情况下,而分类是根据已有标识对数据对象进行度量分类,正是因为聚类的这种不需要预先知道标记的情况下能将数据分类,所以它能够帮助人

21、们从许多未知的数据中挖掘到许多有价值的信息,从而聚类已经变为一个相当活跃的研究领域,已经用在众多的实际应用中,包括异常报警、图像处理、信息检索、数据压缩、市场推销、心理学、模式识别、人工智能、客户关系管理、机器学习、统计学和生物学中等等。 6数据流异常检测技术 是在传统异常检测的基础上,结合数据流相关技术,完成对数据流的异常检测。它能够对系统中产生的数据流进行有效的分析,并快速获取分析结果,满足实7时处理的需求 。目前,数据流异常检测技术的应用研究主要集中在传感器网络、电信网络8监测、股票分析等领域 。如在传感器网络中,异常检测技术可以利用对单个或多个数据流聚集的检测,对异常情况做出分析和补偿

22、。在电信领域,如果在一个特定的时间段内数据包9丢失的数量超过阈值则报警 。在金融领域,股票交易量过大或短时间范围内股票价格波动较大都会引起关注。实际上在工业控制和其它领域也涉及到很多实时的数据流,研究其在天10文领域和电力系统检测中的应用也具有重要的实际意义。在天文观测领域 ,可以用于通过对射线异常的观测,对未来天体事件做出预测。对数据流异常检测技术的研究变得越来越重要。在数据流挖掘领域中,聚类分析和异常检测常常是一个问题的两个方面,聚类分析的目11的是在大量数据对象中发现特征或行为相同的簇 ,即数据对象的集合,它让簇内对象根据某种属性的相似度要尽量高,但簇间对象的相似度尽可能低。聚类分析的一

23、个作用就是生成12那些无法聚集到任何簇的异常对象,而异常检测工作的目标 就是寻找到与大部分对象有显著差异的数据,所以从这个角度上理解,聚类分析与异常检测都是寻求数据本身的某种特征,13只是关注的角度上有所不同而已 。传统对静态数据的处理发展到进化的动态数据流后,传统的聚类分析与异常检测技术不可避免的遇到新的挑战,下面就列举一般数据流聚类算法所要考虑的问题: 1 对数据流处理必须要考虑时间限制,因为要考虑到数据流的不间断和无限性,当数据流出现高速流或突发流时,算法必须尽可能照顾这些高速流对象,同时还能保证算法的准确性和可靠性。 2 考虑算法处理内存,这里主要指算法运行所需要的内存以及读入数据量的

24、大小,因为2 南京邮电大学硕士研究生学位论文 每一章绪 论数据流的无限性且海量的,不可能存储所有过来数据,即这种对数据的处理是单遍的。 3 随时输出流挖掘所产生的结果,即要随时满足用户查询需求,同时要保证这种查询结果是最新的,即能够反映当前数据流的最新变化情况。 4 适应小型无线传感设备网络,通信技术和硬件设备的飞速发展,大量的数据从这些小型无线传感设备中产生,这就要求数据流处理算法要考虑到其传输带宽、能耗、存储空间等资源有限的制约,其中在无线传感器网络环境中最主要是能耗问题。从上面的分析可以看出,数据流聚类及异常检测因其广泛的应用已经成为数据流挖掘分析中一个很重要的研究方面,同时也可以看出它

25、面临着多方面的问题和挑战,如何设计一种高精度高检测率适应数据流的特点的挖掘算法就具有较大的实际意义,本文就上述数据流算法存在的问题1和4来研究,并提出了相应的解决的办法。 1.2 数据流模型本节主要介绍数据流的特点以及相关概念,同时针对数据流的特点描述了现有流聚类方法国内外发展现状以及相关技术。传统的数据处理技术将所有数据存放到数据库或者数据仓库中,当数据规模很大且速度很快时,数据必须全部保存到介质中,然后通过提交 DML语句访问存储介质来获取查询结14-15果,效率低下,难以满足实时需求。区别于传统应用模型,数据流模型具有以下四点特性 :1数据实时到达;2数据到达次序独立,不受应用系统所控制

26、;3数据规模宏大且不能预知其最大值;4数据一经处理,除非特意保存,否则不能够被再次取出处理,或者再次提取数据代价昂贵。为更好理解数据流知识,下面介绍数据流相关概念。1. 数据流模型16数据流模型data streaming model是一个带有时间戳Time Stamp 的多维数据点集合17 1 dX ,X。每一个数据点X是一个包括d维的多维数据记录record ,表示为Xix ,x 。 1 k i i i2. 异常点18异常outlier是指这样的数据点:它与数据集的一般行为和模型不一致 。它可能是度量19或执行错误所导致,在数据挖掘中将其视为噪声或异常。异常检测 又称离群点检测、孤立点检测

27、、偏差检测。在本文的后续部分将不区分这些概念的差别。抽象的概括是数据集中与众不同的数据,它们不符合惯常的数据模式,其产生机制与大多数数据明显不同。 聚类的主要目的是对一个给定的数据对象集合,把里面相似的对象组成单一或者多个不20同的簇 。即一个簇内数据点元素按照某种特征或属性的相似度高,但是簇与簇里面的对象3 南京邮电大学硕士研究生学位论文 每一章绪 论相似度较远。聚类分析在各个领域都有着广泛的应用价值,同时也是其它诸如预测、特征等数据挖掘技术如的预处理过程部分。 传统的聚类方法主要应用于静态数据集,这方面的研究已经有很多了,如果把其算法应用于数据流中,要考虑数据流本身的独有特点,即它的时序性

28、、动态性以及对象的无限性,因此钍对数据流聚类算法必须符合数据流模型、同时能在有界处理时间和有界内存内通过单21遍数据扫描来高效完成。故好的数据流聚类算法应具有三个基本要求 ,即简洁的簇表示方法、数据元素增量式的快速处理和清晰快速的孤立点检测。 为了有效的处理数据流,从而需要新数据结构、技术和算法。考虑到现实中系统没有无限大的空间去存储整个数据流,这就需要在精度和存储空间之间进行折衷,近似结果在很较多应用中一般都能满足要求。为了尽量得到精准的结果同时降低算法时间和空间的消耗。目前大部分数据流流挖掘方法都基共同的基本技术,如概要数据结构、抽样、滑动窗口、衰减函数、倾斜时间构架等。1 概要数据结构。

29、是通过应用概要技术,生成的比当前数据流小得多的数据结构,它是当前数据流的概要描述。新的流数据处理技术并不保存整个数据集,仅维护一个远小于其规16模的概要数据结构 ,从而能够常驻内存。对于不同数据流算法,其概要数据结构相差很大。目前已经提出了多种概要技术包括有:频率矩、直方图和小波分析等等。2 抽样。通过一定的概率来决定一个数据元素是否被处理。这样可以避免处理整个数据16流。但在数据流模型中,抽样技术的问题是不可能预先知道流的长度。一种方法 采用水库抽样技术较好的解决这个问题;在抽样技术中另一问题是数据流其流动率是不是稳定的。故对那些需要监测不规则且浮动上下的流数据是个较好的选择。3 滑动窗口。

30、滑动窗口模型基于这样一个事实:“用户对于最近的数据更感兴趣”。从而17使人们只对少量的近期数据做细节分析,而对大量的历史数据,只给出一个概要结构 。而达到只需存储小的数据窗口,减少对内存的需求。滑动窗口一个缺陷是要求用户预先指定窗口的尺寸,有些应用中,不太可能知道窗口的大小。4 衰减函数。也是一种强调近期数据的重要性、消减历史数据对计算结果影响的方法,22主要利用衰减函数和衰减因子,数据元素在参与计算前,先经过衰减函数的作用 。从而使每个数据元素随着时间的推移逐渐减少对最终结果的影响。常用的衰减函数形式是 Cao等人21 -lt提出的 Den-Stream算法 采用的衰减函数形式:ft 2 ,

31、l 0。5 倾斜时间框架。考虑3和4只能在单一时间维的窗口上得到计算结果。但是,很多应用要求在不同的时间粒度层上进行分析和挖掘。如用户通常对粗粒层的长期变化感兴趣,4 南京邮电大学硕士研究生学位论文 每一章绪 论16但在细粒层上的当前变化感兴趣 。于是,需要构建不同层次的时间粒度窗口,使较早的数据在粗粒度上运算和计算,最近的数据在最细的粒度层上运算和记录,这样,不仅满足需求同时也节省大量存储空间。最主要的是可以构建适合应用需要和当前存储条件的粒度层。所以,这样的时间维模型为“倾斜时间框架”。 1.3 数据流研究现状本节主要介绍数据流挖掘国内外发展现状。从前面研究背景中可以看出数据流的研究有着广

32、泛的应用前景,从而使得国内外众多研究人员对数据流挖掘作了大量的研究,主要可以分为如下两方面的贡献: 1.数据流管理系统DSMS,Data-Stream-Management-System的研究同数据库管理系统DBMS的成熟度来比较,数据流管理系统DSMS的开发和研究,还是14处于一种尝试阶段 ,正式的产品尚未出现,这里列举几种较为熟知的数据流项目: 1 STREAM项目 它是斯坦福桥大学的一个数据流管理系统相关的项目,以数据关系为基础,一个重要贡献是把 SQL语言扩展到处理数据流上去了,并开发了属于它自己的关系和连续查询语言,采用一种独特的窗口处理将流数据转变成关系处理,最后输出的结果也为流数

33、据的形式,同时,它还结合了近似查询得优化内存操作,使得系统能处理突发的、不常规的数据流。目前系统STREAM1.0版本成功运行,并且支持多种语言查询。 2TelegraphCQ项目 TelegraphCQ的前身是 Telegraph,由 Berkeley大学研发,它是目前发展时间最长,而且最成熟的一个自适应数据流管理系统,它是建立在开放源码数据库系统 PostgreSQL之上,能用于支持各种大量数据相关的网络应用,关注是的单用户场景下,如何有效地返回查询的部分结果,同时支持用户对查询过程的控制。目前的已经研制到 TelegraphCQ2.1版本。 3 Aurora项目 它是由 Brandeis

34、、Brown大学及 MIT共同开发的一种管理监控应用方面流式数据的新系统,其系统结构框架比较简单,主要用于处理三种应用:实时监控、大量以时间序列存档的历史数据的管理、当前及历史数据相结合的跨度处理。 2.数据流挖掘算法的研究 目前数据流挖掘相关算法已经越来越多,其中主要包括数据流的关联规则挖掘、频繁模16式挖掘、分类和聚类等等 。 5 南京邮电大学硕士研究生学位论文 每一章绪 论1 关联规则挖掘分析 16它首先是由 Aggrawal等人 在 1993年提出,当时主要是挖掘客户商品交易的关联问题,此后,就有了很多人就关联规则进行了大量的研究,其主要贡献在于不断的对原有算法进行改进以优化算法效率,

35、这里包括采用并行、随机采样等,并且把关联规则的挖掘应用到各个领域中去,使得在数据流中的关联规则的研究进一步扩展,比如有损计算和标记取样、考虑伪正确方法以及 Countin Bloom filter方法等。 2 频繁模式挖掘分析 频繁模式挖掘也是一个很重要的应用,在进化的数据集上挖掘频繁是一项很有挑战的任23务,数据流所要求的单次线性扫描更加增加了其挖掘难度 ,要得到精确的频繁项,算法必须保存所有历史数据,这个要求对于数据流是无法完成,所以,数据流上的频繁项只能得到24其近似值,Motwani等人 提出了一个近似的数据流频繁项分析算法,该算法是采用的界标25窗口模型来完成,是对整个时间序列上的数

36、据进行处理计算,Han JaWei等人 则把它扩展到数据流的时间窗口模型中,从而完成了不同时间粒度的频繁项挖掘。 3 分类分析 分类是对已知标记数据对象进行分类标识,在数据流模型中主要分为数据平衡的分类方法和数据带概念漂移的分类方法,主要具体代表算法有 VFDT、 IFDT、 FLORA和 OLIN, VFDT26是一种基于 Hoeffding不等式来建立决策树的方法 ,它不仅能解决数据流样本过多的问题,还能保证较高精度结果,但它没有处理好连续属性值的问题;IFDT是一种增量式模糊决策树27数据分类方法 ,它不仅具有增量式特点,因为采用模糊逻辑,还能很好的满足人们数据流分类的要求,符合人们的日

37、常思维习惯;FLORA框架是由 Widmer和 Kubat提出的一种针对28概念漂移情况下纯粹增量式学习算法 ,但由于算法每次只能处理一个样本,所以它对数据29到达的速度是有限制的。OLIN 则是一个在线分类系统 ,它采用模糊网络作为基本的分类器,即能保持较高的预测精度,同时对概念漂移的范围、速度以及属性的离散或连续性没有限制。 4 聚类分析 聚类是指对已给的数据对象集合,将其中相似的对象划分为一个或多个组称为“簇”1的过程 ,同一个族中的元素是彼此相似的,而与其它族中的元素相异,聚类分析作为独立的工具有着广泛的应用场景,并且常常作为数据挖掘中的其它部分如预测和特征的预处理过程。 由于数据流本

38、身的特性使得数据流中的聚类面临许多限制,传统的聚类方法不方便直接运用到数据流聚类上,因此需要一种适合于数据流模型、在有界处理时间和有限内存里单遍6 南京邮电大学硕士研究生学位论文 每一章绪 论扫描数据元素的高效聚类方法。 因此,一个好的数据流聚类算法应具备以下三个要求: 1 聚类结构,即能够对已产生的聚类用一个比较简单的方式表示; 2 增量式处理,当新数据元素不断动态实时进化时,能够快速对其进行处理,使得聚类结果是一个增量式实时结果。 3 孤立点检测,流聚类的过程必须要考虑孤立点的情况,这种对孤立点的检测是快速且清晰的。 随着流聚类的应用逐惭扩大,产生了越来越多的数据流聚类算法,同时针对信息化

39、的高速发展以及数据流本身特性,也使得数据流聚类算法面对极大的挑战,本文将在第二章相关小结深入分析和讨论了现有国内外数据流聚类算法发展现状。 1.4 本文研究内容本文的主要研究内容是设计出两种数据流聚类算法,旨在针对现存数据流中异常检测存在的一些问题,主要研究内容分以为下几个方面:首先,对数据流聚类的必要性做了阐述,研究并分析国内外数据流挖掘算法的发展现状,由于聚类分析算法是数据流聚类的基础,现有的比较成熟的聚类算法也是本文学习的一个重点,对各种聚类方法的特点了然于胸是进行下一步工作的基础; 再次,提出了一种基于 SSClu树聚类的高速流异常检测算法。其中采用的 SSClu树是一种维持数据流概要

40、信息的压缩和自适应索引结构,算法主要针对现实网络数据流流速不确定的情况,具体贡献:引入一种维持数据流概要信息的 SSClu树,然后针对数据流的高速特性,采用预先聚集和缓存机制。预先聚集是在数据流对象插入 SSClu树聚类之前对其进行预先聚类的过程,处理批量高速数据流的到达;缓存机制用于暂存高速流对象到达时,来不及处理的数据流对象,解决了突发数据流不能及时聚类的问题。 其次,提出了一种基于相似性群集模型的流聚类算法 SCBSF。主要针对层次拓扑结构的无线传感器网络数据流离群点检测问题,算法采用仿生学中的群集模型来完成分布式传感器网络数据流聚类,并通过聚类思想来达到异常检测的目的。主要工作:首先在

41、聚类过程采用一种启发式策略,这种策略是一种自我组织过程,它能够很好的计算传感器网络大量数据集的情况;其次,在聚类过程中,因为采用相似群集模型聚类,所以聚类的结果是随时可以使用,避免了一般算法要二阶段聚类过程,从而能够更加快速满足人们异常检测的需求;再次,在采集节点端部署数据处理程序,通过初始聚类信息来临时记录所产生的相似数据特征,以7 南京邮电大学硕士研究生学位论文 每一章绪 论此来减少数据传输从而降低通信能耗。 1.5 论文组织结构论文共分为五章,每章内容安排如下:第 1章介绍数据流挖掘的研究背景和意义、国内外研究现状、论文的研究内容、本文所解决的关键问题以及本文的组织结构。第 2章对现有的

42、比较成熟的传统聚类算法进行研究并总结比较了不同算法的适用条件和优缺点,并阐述了现有的异常检测技术。第 3章提出一种基于 SSClu树数据流聚类算法。主要利用 SSClu树结构引入预先聚集机制及临时缓存的概念应对高速数据流的影响,最后以聚类为思想达到高速流中异常检测的目的。第 4章提出基于相似性群集模型的流聚类方法。根据仿生学中的群集模型,本文是通过改进 Vicsel群集模型来建立数据流的运算规则,从而能够较好的考虑到大数据集的情况,同时改变一般聚类二阶段的计算过程而采用一阶在线过程就能满足用户查询的要求,以及通过采集端相似数据处理方法来减少数据传输达到降低能耗的目的。第 5章是最后对本文的研究

43、工作进行总结并对未来工作做出展望。 8 南京邮电大学硕士研究生学位论文 每二章 数据流聚类算法及其应用现状第二章 数据流聚类算法及其应用现状数据流聚类已经越来越受到人们的关注,各种数据流聚类算法也不断产生,但随着信息化飞速发展以及数据流本身的特点,也面临着诸多问题和挑战。为了研究更好的数据流聚类算法及达到异常检测的效果,有必要对现有比较成熟的聚类算法及异常检测技术进行归纳和总结。在本章中,首先介绍数据流聚类的要求、国内外数据流聚类算法发展现状以及其应用,并主要介绍了数据流聚类在无线传感器网络以及异常检测方面两个应用。 2.1 数据流聚类算法在本节中,将对数据流聚类所特有的要求具体描述,同时重点

44、介绍了国内外数据流聚类算法的发展现状,从而能够对数据流聚类有一个更加清晰的认识和理解。 2.1.1 数据流聚类要求如今数据流聚类是一个富有挑战性的研究领域,虽然各种针对性实际应用已经被广泛研究了多年,但其潜在应用价值对算法提出了各自特殊的要求。在数据挖掘中对聚类的典型要求如下: 1 针对不同类型属性的处理能力:许多算法被设计用来聚类数值类型的数据,但是,在实际应用中可能要聚类其他类型的数据,如二元类型,分类标称,序数型数据,或者这些数30据类型的混合 。2 算法规模可扩展性:大部分聚类算法能处理好小于几百个数据对象的数据集合;但是,当面对大规模数据可能包含数百万个甚至更多对象时,进行聚类这样的

45、大型数据集样本可能会导致结果产生偏差。所以需要具有高度可扩展的聚类算法。3 揭示任意形状的聚类:一般聚类算法大多基于欧几里得距离或者曼哈坦距离度量来决定簇。基于这样的距离度量的算法趋向于发现具有相近尺寸和密度的球状簇。但是,很多时候会出现任意形状簇。因此研究能发现任意形状簇的算法是相当重要。4 参数的依赖性:聚类算法很多时候要求聚类分析中用户指定参数,比如希望产生的簇的数目。输入参数会对聚类结果十分敏感。因此参数通常不易确定,特别是处理高速流或多维对象的数据集时。参数输入不仅会增加用户的负担,同时也难以控制得聚类质量。5 数据噪声的容错能力:现实世界中绝大多数据都包含了非正常离群点、未知、缺失

46、或9 南京邮电大学硕士研究生学位论文 每二章 数据流聚类算法及其应用现状者错误的数据。然有些聚类算法对于这样的数据敏感,可能会产生低质量的聚类。6 增量聚类:在数据流中,考虑到数据流的无限性。因此聚类结果必须不断变化递增的。在开发各种流挖掘算法时,必须要将这种聚类增量关系考虑进去才能体现较准确的聚类结果。7 多维性:数据流中的数据点对象可能包含若干维或者若干属性。许多聚类算法擅长处理低维的数据,可能只涉及两到三维。人类在三维的情况下能够很好地判断聚类的质量,高于三维时很难直接判断聚类质量。在高维空间中聚类数据对象是非常有挑战性的,特别是考虑到这样的数据可能非常稀疏,而且高度偏斜。8 聚类的约束

47、性:现实世界的应用可能需要在各种约束条件下进行聚类,假设你的工作是在一个城市中给定数目的自动提款机即 ATM选择安放位置,为了作出决定,你可以对住宅区进行聚类,同时考虑如城市的河流和公路网,每个地区的客户要求等情况,可以看出找到既满足特定的约束,又具有良好聚类特性的数据分组是一项具有挑战性的任务。 29 可用性和可解释性:应用目标如何影响聚类方法的选择是一个重要的研究课题 ,目前较为一致的观点是,还没有一种算法对于所有的应用都具有绝对的优势,不同的应用应选用不同的算法;用户希望聚类结果是可解释的,可理解的,和可用的。也就是说,聚类可能需要和特定的语义解释和应用相联系。 鉴于上面对数据流聚类众多要求,可知数据流聚类面临着