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