流数据的聚类分类算法研究

论文摘要

近年来,随着信息处理应用的发展,许多应用中的数据是以流的形式产生的,数据呈现出“连续数据流”的形式而不是传统的静态存储结构形式。这些应用领域包括金融证券信息分析、网络传输监控、计算机网络安全、通信数据管理、web应用、生产制作、传感器网络等。这些应用产生的数据形式称为数据流。与传统数据库不同,数据流具有如下特点:（1）数据总量的无限性;（2）数据到达的快速性;（3）数据到达次序的无约束性;（4）除非可以保存,每个元素均只能被处理一次。数据流的上述特点对数据流上的挖掘提出了如下要求:首先,算法必须能够进行实时在线挖掘,快速处理每一个元组,并实时输出挖掘处理结果。其次,由于相对于无限规模的数据流而言,内存通常是有限的,这就要求算法的空间复杂度要低,往往需要在数据量的对数范围内。再次,由于算法实时在线挖掘以及对空间复杂度的限制,算法往往只能得到近似解,且需要具有一定的精确度保证。最后,算法要具有较强的适应性,包括对数据流不断进化的底层模型的适应性,处理离群点能力等。学术界己经对数据流上的挖掘问题进行了很多研究工作,但仍存在许多问题尚待研究和解决。本文研究了数据流上的聚类问题和分类问题,做了以下一些工作: （1）提出了基于相关系数的多数据流聚类算法。使用相关系数作为数据流间距离的度量,将有相同变化趋势的数据流聚为一类。我们使用衰减系数来使得新数据比旧数据在聚类结构中有更大的重要性,采用更新时间片段的机制很好地反映了聚类结构的变化过程。我们采用动态k-means,不断的试探性地调整聚类的个数,通过比较聚类质量,选取最优的类的个数,提高聚类质量。此外,我们基于相关系数的度量,提出了另一种满足用户需求的聚类算法框架。算法分为前台和后台两个部分:在前台部分,我们提出了一种新颖的保存汇总信息的机制;后台阶段,根据用户的聚类请求,读取相应长度的信息进行聚类。满足了用户对不同长度的聚类需求。（2）提出了一种基于谱分量相似度的多数据流的聚类算法框架。使用自回归模型对数据流序列作谱分析,把数据流表示为谱参数的和。通过将相位设为零后,使用谱分量信息计算两条数据流之间的相关性。（3）提出了一种基于网格密度的数据流聚类算法GDCS算法。算法采用了在线/离线双层框架,它在前台在线层快速实时地将到达的数据点放入相应的单元格,在后台离线层不断地更新单元格的密度并将网格单元聚成类。此外,算法适时检测和剔除孤立点以改进系统的时间空间有效性。实验表明,算法具有更优的聚类效率和聚类质量,能发现任意形状的类,且能有效识别实时数据流的变化行为。（4）基于改进的Fisher判别分析方法,我们提出了一种新的数据流的分类方法。改进的Fisher判别准则能同时适用于类内散布矩阵奇异和非奇异两种不同场合。提高了分类的速度,更好的满足了流数据处理的要求。使用最新滑动窗口中的样本不断重复构建分类模型,能及时反应概念的漂移。

论文目录

• 摘要
• Abstract
• 1. 绪论
• 1.1 研究背景
• 1.1.1 数据挖掘技术概述
• 1.1.2 数据流管理概述及应用需求
• 1.1.3 数据流的特点
• 1.1.4 数据流管理系统与传统数据库管理系统的对比
• 1.1.5 数据流模式
• 1.1.6 数据流计算模型
• 1.2 基本技术
• 1.2.1 随机抽样（Radom Sampling Technique）
• 1.2.2 梗概技术（Skeching Technique）
• 1.2.3 直方图（Histogram）
• 1.2.4 滑动窗口（Sliding Windows）
• 1.2.5 小波技术（Wavelets Techniques）
• 1.2.6 哈希方法（Hashing）
• 1.3 主要工作
• 1.4 论文组织
• 2 流数据挖掘算法综述
• 2.1 流数据挖掘算法的特点
• 2.2 数据流聚类分析
• 2.2.1 聚类分析
• 2.2.2 数据挖掘对聚类分析的要求
• 2.2.3 传统的聚类方法
• 2.2.4 数据流的对聚类算法的要求
• 2.2.5 数据流聚类算法的发展和演化
• 2.2.6 数据流聚类算法
• 2.3 数据流分类规则挖掘
• 2.3.1 分类规则挖掘的概念
• 2.3.2 分类规则挖掘的步骤
• 2.3.3 传统的分类规则挖掘算法
• 2.3.4 数据流对分类算法的要求
• 2.4 已有的数据流分类算法
• 2.4.1 数据平稳分布的分类方法
• 2.4.2 数据带概念漂移的分类方法
• 2.5 其他数据流挖掘算法
• 2.6 数据流分析挖掘系统
• 2.7 本章小结
• 3 基于相关系数的多数据流聚类
• 3.1 引言
• 3.1.1 聚类多条数据流的动机
• 3.1.2 相关工作
• 3.2 问题描述和相关概念
• 3.2.1 滑动窗口技术
• 3.2.2 衰减系数
• 3.2.3 相似度量
• 3.3 汇总信息的计算及更新
• 3.3.1 汇总信息的计算
• 3.3.2 汇总信息的合并
• 3.4 实时聚类算法框架
• 3.5 离线聚类
• 3.5.1 COR 框架的信息保存
• 3.5.2 COR 前台信息保存算法描述
• 3.5.3 后台聚类
• 3.6 实验分析
• 3.6.1 实验环境和数据集
• 3.6.2 实时聚类性能分析
• 3.6.3 COR 算法性能分析
• 3.7 本章小结
• 4 基于谱分量相似度的多数据流的聚类
• 4.1 引言
• 4.2 问题描述和相关概念
• 4.2.1 数据流间的延迟相关
• 4.2.2 数据流间的距离
• 4.3 AR 模型和谱分量对相关
• 4.4 在滑动窗口中聚类多条数据流
• 4.5 实验分析
• 4.5.1 实验环境和测试数据
• 4.5.2 性能测试
• 4.6 本章小结
• 5 基于网格密度的数据流聚类算法
• 5.1 引言
• 5.2 问题描述和相关概念
• 5.3 GDCS 算法描述及框架
• 5.3.1 算法的基本思想
• 5.3.2 GDCS 算法框架
• 5.3.3 时间间隔gap 的确定
• 5.3.4 对孤立点的检查及删除
• 5.3.5 聚类的形成和调整算法
• 5.4 实验分析
• 5.4.1 实验环境和测试数据
• 5.4.2 聚类的演化过程与效果分析
• 5.4.3 聚类结果的正确率比较
• 5.4.4 聚类速度的比较
• 5.5 本章小结
• 6 一种基于改进的FDA 方法挖掘数据流
• 6.1 引言
• 6.2 问题描述及研究现状
• 6.3 线性判别分析（FDA）概述
• 6.3.1 Fisher 判别法的基本思想
• 6.3.2 Fisher 线性判别函数的求法
• 6.3.3 Fisher 判别规则
• 6.4 改进的 Fisher 鉴别准则
• 6.5 DFDA 分类算法
• 6.6 实验分析
• 6.6.1 实验环境和测试数据
• 6.6.2 性能测试
• 6.7 本章小结
• 7 总结与展望
• 7.1 研究总结
• 7.2 研究展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文和参加的研究工作