论文部分内容阅读
随着计算机技术与通信技术的快速发展,传感器网络、Web服务和RFID技术得到了广泛应用,从而使得不确定性数据管理得到广泛的重视.在许多现实的应用中,例如经济形势预测、金融信息分析、生态环境监测、网络安全监控、物流管理等等,不确定数据流扮演着关键角色.在这些应用中,传统的数据管理技术却无法有效地管理新型的不确定数据流,这就引发了学术界和工业界对研发新型的不确定数据流管理技术的兴趣.因此,不确定数据流上的数据挖掘已经成为当前数据挖掘领域的研究热点.当前对于不确定数据流上的挖掘主要集中在不确定数据流上的聚类、不确定数据流上的频繁模式挖掘、Skyline查询、数据世系分析、异常分析等.本文在深入研究国内外的各种不确定数据流挖掘技术的基础上,讨论了目前国内外有关不确定数据流频繁数据挖掘的研究现状.由于不确定数据流上的频繁数据挖掘是不确定数据流上的关联规则、分类、聚类等挖掘的基础,在不确定数据流挖掘中具有重要的地位.因此,本文在不确定数据流上频繁数据挖掘方面进行了深入的研究,提出了有效的频繁数据挖掘算法.本文的主要工作有:(1)提出了一种基于滑动窗口的不确定数据流中频繁项查询算法SWBUFIM.本文根据频繁项的本质特性以及马尔科夫不等式,给出了两个裁剪规则,用于对不确定数据流进行预处理,裁剪掉不可能成为频繁项的元组.在此基础上我们:一方面利用动态规划方法计算期望概率,保证在时间内完成期望概率的计算;另一方面,根据不同数据项相互独立性原理,针对不同数据项开辟子滑动窗口,并且根据数据项的组合数目进行行列划分来处理频繁项挖掘问题,并在动态规划方法的基础上,进一步改进期望概率计算方法,只需要动态规划滑动窗口中前k-1项即可保证在时间内有效地完成期望概率的计算.实验结果表明,所提出的查询算法SWBUFIM具有较快的处理速度,其空间复杂度随着处理数据规模的增加成线性增长.(2)提出了一种基于滑动窗口的不确定数据流中top-k查询算法MPTopKTS.本文针对top-k查询的定义,根据不确定数据流及其滑动窗口的特性,研究基于滑动窗口top-k查询问题,提出了所有可能世界中元组集成员相对得分值高并且具有最大出现概率的top-k元组集(MPTopKTS)的查询算法.该算法基于滑动窗口建立概要表,然后在每一时刻对概要表进行修改,有效地减少了top-k查询问题的复杂性;能够在查询准确性与查询开销之间取得平衡,较小的计算开销获得高质量的近似结果.实验结果表明,所提出的查询算法在时间与空间复杂性方面优于其他类似的算法.(3)提出一种基于滑动窗口的不确定数据流中频繁闭项集的采样挖掘算法MFCIFUDS.本文针对不确定数据流频繁闭项集的挖掘问题,首先使用采样的方法,基于随机采样概率,把由不确定数据组成的事务转换成由确定性数据组成的事务,再利用基于确定性数据模型的频繁闭项集挖掘技术完成不确定数据流中频繁闭项集的挖掘任务.本文不但从理论上证明了基于采样技术利用确定性数据挖掘算法解决不确定数据挖掘问题的可行性,而且提出了一种改进频繁模式树生成与修改技术,有效地提高了基于FP-tree频繁模式树的频繁闭项集挖掘速度.实验结果表明,所提出的查询算法MFCIFUDS有较高的挖掘精度和处理速度.(4)提出了一种基于滑动窗口的不确定数据流中频繁数量区间模式的挖掘算法MFIPatFUS.不同于处理常规二进制项集事务不确定数据流,数量区间事务不确定数据流使用数量区间来表示事务属性,其不确定性在于属性数量区间范围的波动性,数量区间分布体现某种分布概率.本文借鉴常规的基于频繁模式树的不确定数据流频繁模式挖掘算法,设计一种频繁数量区间模式生成树FIPatTree,用于捕获不确定数据流中所有事务的数量区间信息.我们把原始数量区间边界值作为基元素,根据基元素的分布情况建立基数量区间,从而一方面基于基数量区间对原始数量区间进行重新划分;另一方面根据基数量区间数值范围在原始数量区间中所占比例决定其基数量区间概率.算法MFIPatFUS采用滑动窗口模型,使用FIPatTree树作为概要数据结构,事务属性以基数量区间结点保存在FIPatTree树中.建立树的过程类似常规频繁模式生成树的建立过程,不同点在于当属性基数量区间与出现概率均相同时,结点方可共享.对于共享结点设立频次与局部概率统计数值,为了方便遍历与修改,增设了与FIPatTree树相关联的属性索引与基数量区间索引.基于频繁数量区间模式生成树FIPatTree的频繁数量区间模式挖掘过程采用基于投影基与条件树的递归挖掘方法.实验结果表明,所提出滑动窗口模型的挖掘算法MFIPatFUS对处理数量区间事务组成的不确定数据流频繁数量区间模式挖掘是有效的.