事件序列上高效用情节挖掘方法研究

论文摘要

随着信息时代的到来,产生了海量的数据,这些大量数据的背后隐藏着许多人们所需要的信息和知识,人们迫切需要将这些数据转换成有用的信息和知识。数据挖掘就是随着人们的这一需要应运而生的。虽然对数据挖掘技术的研究已经很成熟,但随着RFID、Sensor等EDGE(Electronic Data Gathering Equipment)的广泛应用,出现了大量的事件流数据。传统的数据挖掘技术往往针对静态数据进行处理,对这种事件流数据不适用。因此对事件流上的数据进行挖掘处理获得了广泛的应用。频繁情节挖掘是事件流挖掘领域中的重要方面。目前对频繁情节挖掘的研究没有考虑事件序列当中各个事件类型的重要性(权重),即认为所有的情节都有相同的权重。但是在现实环境中,事件序列中不同的情节具有不同的权重,不同的情节具有不同的效用值。这样以前的频繁情节的挖掘方法都不能直接用来挖掘高效用的情节。为此,提出了在事件序列上进行高效用情节挖掘的算法。首先,本文提出了一种度量情节效用值的模型,用情节发生的次数乘以情节本身的权重。这样就避免了以前单纯用次数来判断情节是否频繁的缺点,即挖掘出的情节往往不是非常重要的情节。在这样的模型下挖掘出的高实用性、高效用的情节在实际的某些应用当中更有实际意义。其次,以前在没有考虑权重进行频繁情节挖掘时,情节都具有向下封闭的特性,但是现在由于考虑了情节的效用值,原来向下封闭的特性就不再满足,即如果子情节不满足阈值条件,但它的父情节也有可能是满足阈值条件的。所以不满足阈值条件的子情节不能直接删除,这样一来,就增加了算法的搜索空间。为此,本文提出了两种削减策略,能有效地削减算法的搜索空间。最后,本文在此基础上提出了一种基于前缀投影的高效用情节挖掘算法。通过实验可以发现,本文所提出的高效用情节挖掘算法可以有效地挖掘出当前窗口内用户感兴趣的情节。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 本文的研究内容
• 1.4 本文结构
• 第2章 事件序列和频繁情节、序列模式挖掘
• 2.1 事件序列简介
• 2.2 频繁情节挖掘
• 2.2.1 情节和频繁情节
• 2.2.2 频繁情节挖掘算法
• 2.3 序列模式挖掘
• 2.3.1 序列模式简介
• 2.3.2 序列模式挖掘算法
• 2.4 高效用序列模式挖掘
• 2.4.1 高效用序列模式简介
• 2.4.2 高效用序列模式挖掘算法
• 2.5 本章小结
• 第3章 高效用情节及其挖掘模型的提出
• 3.1 高效用序列模式效用值的定义模型分析
• 3.2 高效用情节的效用值定义
• 3.2.1 高效用情节应用场景介绍
• 3.2.2 情节效用值的定义模型
• 3.2.3 情节的权重范围
• 3.2.4 高效用情节挖掘与高效用序列模式挖掘的对比
• 3.3 高效用情节挖掘模型
• 3.4 本章小结
• 第4章 事件序列上高效用情节挖掘算法
• 4.1 高效用情节挖掘的削减策略
• 4.1.1 基于情节最小发生次数的削减策略
• 4.1.2 基于情节权重范围的削减策略
• 4.2 现有的情节挖掘算法分析
• 4.3 高效用情节挖掘算法
• 4.3.1 Apr-HUEpi算法描述
• 4.3.2 Pre-HUEpi算法描述
• 4.3.3 基于伪投影的Pre-HUEpi算法的改进
• 4.4 高效用情节挖掘算法的比较
• 4.5 本章小结
• 第5章 实验结果分析
• 5.1 实验基本设置
• 5.2 算法的效率验证及削减策略的有效性验证
• 5.2.1 时间代价的比较及分析
• 5.2.2 空间代价的比较及分析
• 5.3 伪投影技术的有效性验证
• 5.3.1 伪投影技术对算法运行时间的影响
• 5.3.2 伪投影技术对算法运行所占空间的影响
• 5.4 本章小结
• 第6章 结论
• 参考文献
• 致谢
• 攻读硕士期间参加的项目和发表的论文