数据流聚类算法及其应用

论文摘要

近年来,伴随着网络信息技术的高速发展,产生了一种新式的数据模型——数据流。它常常产生于web上的用户点击、网络入侵检测、实时监控系统或无线传感器网络等动态环境中。相比较传统据集,这些海量的数据流具有快速性、连续性、变化性、无限性等特点,使数据流的挖掘面临着新的要求和挑战。聚类分析作为数据挖掘领域的一个重要课题,能够使未标记数据按照指定属性分组为不同的类,在近期得到广泛研究和高度重视。本文以数据流聚类算法为研究内容,异常数据点的检测为研究目标,主要作了以下三个方面的工作:(1)总结了数据流模型及其聚类的相关概念和技术,并描述了数据流聚类的特殊要求以及目前国内外数据流聚类算法。同时说明了异常检测的定义、现有方法以及当前所面临的挑战。(2)在高速网络中,数据流具有高速、突发等特性,使得高速网络中的异常检测成为一个难点。本文提出了一种基于SSClu树的流聚类算法用于高速流的异常检测。算法首先引入一种维持数据流概要信息的SSClu树;然后针对数据流的高速特性,采用预先聚集和缓存机制。预先聚集是在数据流对象插入SSClu树聚类之前对其进行预先聚类的过程,以处理突发高速数据流的到达;缓存机制是用于当高速流到达时,暂存当前来不及处理的数据流对象,解决了高速流不能及时聚类的问题。仿真结果表明,本算法能及时处理高速数据流,且具有较高的聚类精度,保证了高速流下异常检测的准确性。(3)针对无线传感器网络中的离群点检测问题,考虑到无线传感器网络(Wireless Sensor Network,WSN)环境分布式以及能源消耗的限制,提出了一种基于相似性群集模型的流聚类算法(Stream Cluster algorithm Based on Similarity Flocking model,SCBSF)。算法采用一种模拟群体运动的群集模型将数据自我组织来形成聚类,这种自组织性更加适用于分布式环境批量数据点的聚类;同时通过群集规则来完成任意形状簇的聚类,而不需要采用传统二阶段聚类思想,减少了算法计算和存储复杂度;考虑到WSN中算法的能耗问题,在采集节点端,利用初始聚类信息来临时记录所产生的相似数据特征,以此来减少数据传输从而达到降低通信能耗的效果。仿真结果表明,算法不仅具有较好的离群点检测效果,同时也降低了聚类过程中数据计算和传输的能源消耗。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.2 数据流模型
• 1.3 数据流研究现状
• 1.4 本文研究内容
• 1.5 论文组织结构
• 第二章 数据流聚类算法及其应用现状
• 2.1 数据流聚类算法
• 2.1.1 数据流聚类要求
• 2.1.2 数据流聚类算法
• 2.2 数据流聚类的主要应用
• 2.3 普适数据流聚类
• 2.4 数据流异常检测技术
• 2.4.1 流异常的定义
• 2.4.2 现有异常检测方法
• 2.4.3 流异常检测面临的挑战
• 2.5 本章小结
• 第三章 基于SSClu树流聚类算法
• 3.1 问题描述
• 3.2 相关概念
• 3.2.1 SS 树定义
• 3.2.2 树的相关操作
• 3.2.3 微聚类
• 3.2.4 SSClu 树结构
• 3.3 基于SSClu 树流聚类算法
• 3.3.1 高速流处理策略
• 3.3.2 高速流聚类算法
• 3.3.3 聚类的更新
• 3.4 高速流的异常检测
• 3.4.1 异常检测框架
• 3.4.2 异常检测分析
• 3.5 实验分析
• 3.5.1 实验环境
• 3.5.2 实验评价
• 3.6 本章小结
• 第四章 基于相似性群集模型的流聚类算法
• 4.1 问题描述
• 4.2 相关工作
• 4.2.1 WSN 结构及离群点
• 4.2.2 WSN 数据流聚类研究现状
• 4.3 相似性群集模型
• 4.3.1 群集模型
• 4.3.2 相似性群集模型
• 4.4 基于相似性群集模型的流聚类算法及其在WSN 中的应用
• 4.4.1 WSN 中离群点检测模型
• 4.4.2 离群点判别
• 4.4.3 采集端数据处理方法
• 4.4.4 基于相似性群集模型的聚类算法
• 4.4.5 能耗分析
• 4.5 实验及结果分析
• 4.5.1 实验环境
• 4.5.2 结果评估
• 4.6 本章小结
• 第五章 总结和展望
• 5.1 论文工作总结
• 5.2 下一步工作计划
• 参考文献
• 攻读硕士期间发表的学术成果