论文部分内容阅读
随着信息技术的快速发展,流式数据以不同方式出现在了众多领域的应用之中。包括网络流量的监测、金融应用、通信数据管理、网络安全监控、传感器网络等等。在这些应用中,对新型的流数据形式以及相关技术进行研究显得非常重要。因此,数据流上的数据挖掘成为当前数据挖掘领域的研究热点。当前对于数据流上的挖掘主要集中在:频繁项(集)挖掘、聚类分析、分类、异常分析等。本文分析了当前国内外各种流数据挖掘算法,针对数据流上的频繁项挖掘、单条及多条数据流上的聚类分析中存在的问题,提出了更为有效的算法。本论文的主要贡献如下:(1)现有大多数的数据流频繁项挖掘算法并没有足够强调当前数据的重要性。滑动窗是一种对最近一段时间内的数据进行挖掘的有效技术。因此,我们提出了一种基于滑动窗的流数据频繁项挖掘算法。该算法采用了链表队列策略得以大大简化算法,从而提高了挖掘的效率。对于给定的阈值S、误差ε和窗口长度n,算法可在εn的误差内检测窗内频度超过Sn的数据流频繁项,且其复杂度为O(ε-1),处理和查询每个数据项的时间均为O(1)。在此基础上,我们还将该算法进行了扩展,通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法在时间和空间复杂度之间可以进行调节。通过大量的实验证明,本文算法比其它类似算法具有更好的精度及时空效率。(2)通过强调近期数据而弱化“旧”数据重要性的时间衰减模型,提出了流数据频繁项挖掘算法FC1及其改进的算法FC2来检测数据流上ε-近似频繁项。FC2算法的空间复杂度为O(ε -1),每个数据项的处理时间为O(1)。通过大量的实验证明,FC2比其他类似方法有较高的正确率,较快的处理速度以及较少的内存需求。接着,提出了一种更加简洁快速的挖掘数据流频繁项的λ-Count算法。算法可以在O( logλε)空间复杂度下,检测ε-近似频繁项,对每个数据项的处理时间为O(1)。通过大量的实验证明,λ-Count在正确率、内存要求和处理速度上都优于其他类似方法。(3)大多数现存的实时流数据上的聚类算法如CluStream等,都是基于k-means算法的。这些算法在挖掘任意形状的聚类以及处理孤立点问题上都存在难度,而且这些算法需要先验知识来确定聚类的个数k以及用户定义的时间窗口长度。为了解决这些问题,我们提出了一种基于密度的流数据聚类算法框架D-Stream,并相继提出了基于此框架的算法DS0和引入吸引度策略的算法DS1。通过探索衰减系数、吸引度、数据密度以及聚类结构之间的潜在联系,算法可以有效地生成聚类并进行实时调整,探测并移除那些由孤立点映射的奇异单元格来动态地提高系统的空间和时间效率。实验结果证明,算法具有较高的质量和效率,可以准确地反映实时数据流的进化过程。(4)多数据流聚类的研究通常都是利用欧几里德距离来衡量数据流间的相似性。而欧几里德距离具有很大的局限性,它忽略了数据流的变化趋势和序列模式。而对用户来说,这些信息往往更加重要。为此,我们提出基于Kendall相关系数的多数据流聚类算法。该算法利用AU统计量将多数据流的原始数据快速压缩成一个统计概要。根据这些统计概要可增量式地计算Kendall相关系数来衡量数据间的相似度。我们还提出了一种动态的k-means算法来生成聚类结果。动态的k-means算法可动态、实时地调整聚类数目,及时检测数据流的发展变化。算法被应用到按照用户要求的聚类问题(COD),使用户可在任意时间区间上查询聚类结果。通过一种合理的时间片断划分机制,可使用户指定的任意时间区间都可以由这些时间片断组合而成。实验结果证明,算法比其他类似方法具有更好的聚类质量、速度和稳定性,能实时地反映数据流的变化。