基于不确定数据的高平均效用序列模式挖掘算法的研究

摘要

近年来，数据挖掘可以为决策提供关键信息，已经成为大数据时代一个重要的研究方向。高效用序列模式挖掘（high utility sequential patterns mining， HUSPM）考虑时间戳、内部量化、外部效用因子来挖掘高效用序列（high utility sequential pattern，HUSP），已经成为近十年热点研究课题。然而，通常情况下序列的效用值会随着序列长度（项目数）的增加而增大，HUSPM却没有考虑序列长度对序列效用值的影响。在高平均效用项集挖掘(high average-utility itemsets mining，HAUIM）领域，学者们用平均效用值来衡量项集的重要、有用程度，可以解决项集长度对项集效用值的影响，同样本文使用平均效用值来解决序列长度对序列效用值的影响。另外，在实际生活中由于环境因素，设备限制，隐私问题等收集到的数据可能是不确定的，目前HUSPM的研究主要针对的是精确数据，在不确定数据挖掘领域还没有相关研究。
　　本研究提出了高平均效用模式挖掘算法HAUI-Miner，设计了平均效用列表（average-utility list，AU-list）结构来保存来挖掘高平均效用项集所需要的信息。HAUI-Miner使用深度优先搜索技术不需要重复扫描数据库，相比于前人算法在性能上有较大的提升。随后本文提出了潜在高效用序列模式挖掘（potential high utility sequential patterns mining，PHUSPM）算法框架，基于这个框架提出了两个算法，一个是基于效用高估的PHUSPM-UP算法，设计的剪枝策略可以有效减少搜索空间提升算法性能；另一个是基于投影数据库技术的pre-PHUSPM算法，pre-PHUSPM算法迭代生成投影数据库，随着数据库规模的减小潜在高效用序列的挖掘速度越来越快。PHUSPM依然受困于序列长度对序列效用值的影响，结合HAUIM和 PHUSPM的研究要点，提出了基于不确定数据的高平均效用序列模式挖掘算法框架，一同提出的还有两个算法MUHAUSP和 PrefixMUHAUSP。做了大量实验来验证所提算法的性能，对所提算法的正确性和完整性进行了证明。

目录

第1章 绪 论

1.1 课题的研究意义和背景

1.2 国内外研究现状

1.3 本文主要贡献

1.4 本文的组织结构

第2章 高平均效用模式挖掘

2.1 预备知识和问题定义

2.2 HAUI-Miner算法

2.3 实验结果及分析

2.4 本章小结

第3章 潜在高效用序列模式挖掘

3.1问题定义及符号说明

3.2 PHUSPM-UP算法

3.3 pre-PHUSPM算法

3.4 实验结果及分析

3.5 本章小结

第4章 基于不确定数据的高平均效用序列模式挖掘

4.1 预备知识和问题定义

4.2 基于高估平均效用值的MUHAUSP算法

4.3 基于投影数据库的PrefixMUHAUSP算法

4.4 实验结果及分析

4.5 本章小结

结论

参考文献

攻读学位期间发表的论文

声明

致谢