一种多数据流变化趋势的同异反分析方法研究

摘要

随着通信技术和传感器技术的高速发展,在实时监控和联机分析等应用领域产生了大量流数据。数据流挖掘技术的研究已成为当前国际数据库研究领域的一个热点。数据流快速、持续、无限量等特点,以及对数据流挖掘算法的单遍扫描、实时响应等要求,对数据流挖掘技术的研究带来了巨大挑战。趋势分析是数据流挖掘研究的重要内容之一,其目的在于揭示数据流随时间变化所呈现出的规律或趋势,有效的趋势挖掘可用于被监控对象的状态评估、早期预警以及决策支持等。
　　 现有的数据流趋势分析几乎都是关于单条数据流的研究内容,如趋势描述、趋势提取和趋势预测等,而关于多数据流趋势分析的研究内容并不多见。据此,本课题引入集对分析思想,对多数据流的变化趋势进行同异反分析,其实质是变化趋势的比较分析。
　　 本文对多数据流变化趋势的同异反分析方法研究包括三个方面。首先,对峰值等概念作形式化描述,在此基础上对峰值变化情况与原始数据变化情况的关系进行研究,进而以峰值数据作为同异反分析的基础。其次,对集对分析中同、异、反概念作出适合于数据流的具体定义,并根据同、异、反关系判断数据流所属的集对势类型,用集对势描述两数据流变化趋势之间1与1的关系,这是多数据流变化趋势同异反分析方法的核心所在。最后,将具有相同集对势的流构成的集合定义为集对势簇,并结合与集对势簇相关的一系列概念,用于描述多数据流变化趋势之间1与n的关系。
　　 为实现上述研究,适应数据流快速处理的要求,本文提出四个算法。(1)在数据采集或预处理阶段,提出用于从原始流中快速提取峰值点序列的算法;(2)提出用于计算流对之间的集对势的增量算法,该算法通过判断基本窗口内流之间的同异反关系实现集对势的计算;(3)提出用于计算极大阶强势簇的算法,其基本思想是将极大阶强势簇的计算归结为极大完全子图的计算,该算法是对求解极大完全子图的已有算法FMCSG的改进,改进后的算法适用于顶点较多的图的求解,并提高了时空效率;(4)提出用于计算极大强势频繁簇的算法,其基本思想是将极大强势频繁簇的计算归结为顶点不变的特殊图集的公共子图的计算;该算法在图集上定义一种称为边与算子的特殊操作,通过单遍扫描即可完成公共子图的快速求解。
　　 仿真实验结果表明,用集对势及集对势簇等概念描述多数据流变化趋势是合适的;本文给出的算法不仅对多数据流变化趋势的同异反分析是有效的,而且也是适合于数据流快速处理要求的;另外,峰值的变化趋势较能真实地反映数据流的变化趋势,使用峰值能带来较高的数据压缩率,从而使数据流的处理速度自然得到较大提高。