基于效用矩阵和索引的top-k高效用项目集挖掘研究

摘要

随着信息时代的到来，产生了海量的数据，这些大量数据的背后隐藏着许多人们所需要的信息和知识，人们迫切需要将这些数据转换成有用的信息。传统的频繁项目集挖掘以频繁度作为衡量指标。这样就会导致一些频繁度低，但是效用值高、用户感兴趣的项目集不能被挖掘出来。为了解决这个问题而出现了高效用项目集挖掘。虽然目前已经有很多关于高效用项目集挖掘的研究，但是让用户来设定阈值对于用户来说是一个很困难的事情。如果用户设定的阈值过低，那么过多的高效用项目集将会产生，这就可能导致挖掘算法效率低下，甚至出现挖掘出来的项目集数量超出内存容量。反之将会导致没有高效用项目集产生。用户通过实验不断地调整阈值来得到最终需要的阈值，这一过程对于用户来说是非常繁琐的。
　　为了解决上述问题，本文中提出了一种新的基于效用矩阵和索引的top-k高效用项目集挖掘算法，用户无需设定阈值，只需要给出要挖掘的项目集数量。本文的主要贡献包括:
　　首先，在高效用项目集挖掘中，本文首次提出了利用项目集的真实效用值进行挖掘的算法。这样可以有效地在top-k高效用项目集挖掘中提高边界阈值。
　　其次，本文提出了效用矩阵结构，避免为计算大量的项目集效用值而多次扫描数据库。
　　再次，针对高效用项目集挖掘算法中失去了反单调性，在算法执行过程中无法进行剪枝的问题，本文中提出了基于索引结构的消减策略。
　　最后，本文摒弃了以往由短项目集连接生成长项目集的固有思想模式，根据top-k高效项目集挖掘中的特点，采用了自顶向下的挖掘过程。既可以有效地提高边界阈值，又能减少在挖掘过程中产生的项目集数量。
　　通过理论分析和实验评估，验证了本文提出的基于效用矩阵和索引的top-k高效用项目集挖掘算法的正确性和高效性。

目录

声明

摘要

第1章 引言

1．1 研究背景

1．2 研究现状

1．2．1 频繁项目集挖掘的现状

1．2．2 高效用项目集挖掘的现状

1．2．3 top-k高效用项目集挖掘的研究现状和应用

1．3 本文的研究内容

1．4 本文结构

第2章 问题定义及相关工作

2．1 高效用项目集挖掘中的问题定义

2．2 已有的高效用项目集挖掘算法

2．2．1 Two-phase算法

2．2．2 树形结构算法

2．2．3 Udepth算法

2．3 已有的top-k高效用项目集挖掘算法

2．4 已有top-k高效用项目集挖掘算法的分析

2．5 本章小结

第3章 top-k高效用项目集挖掘算法

3．1 算法框架

3．2 top-k高效用项目集挖掘的削减策略

3．2．1 基于长项目集的分裂消减策略

3．2．2 基于相同事务中长项目集的封闭性的消减策略

3．2．3 基于索引的事务效用值的消减策略

3．3 基于效用矩阵和索引的top-k高效用项目集挖掘

3．3．1 构建效用矩阵

3．3．2 数据预处理

3．3．3 建立索引

3．3．4 产生top-k高效用项目集

3．4 本章小结

第4章 实验分析

4．1 实验基本设置

4．2 算法的总体分析

4．3 算法的时间性能分析

4．4 算法的空间性能分析

4．5 算法的扩展性分析

4．6 本章小结

第5章 结论

5．1 总结

5．2 未来工作

参考文献

致谢

攻读硕士学位期间的论文项目情况