不确定数据库的近似极大频繁项集挖掘

摘要

近些年来，概率数据库或不确定数据库广泛地应用到了多个领域中，例如地下煤矿检测、移动物体搜索等。对于一个不确定数据库，其概率频繁项集的挖掘是国内外学者关注的热点问题。为了更好地转译和利用不确定数据库的概率属性，可能世界模型的概念经常被用到。不过，由于一个不确定数据库能产生指数级个可能世界，对于较大规模数据库，直接在可能世界上挖掘极大概率频繁项集是一项极具有挑战性的工作。
　　研究人员提出了一些算法以解决在可能世界上计算代价过大的问题，例如引入动态规划算法(DP)或者分治算法(DC)。这些算法计算的结果和通过可能世界得到的结果是相同的，但是这些方法的效率更高、计算速度更快。原因是这些算法只需要计算项集支持度的概率分布而不是生成所有的可能世界。计算卷积值的时间复杂度为O(nlogn) (n为数据库规模大小)，显然，这种方式远比在指数级的可能世界上计算项集的组合高效。
　　不过，随着数据集的增大，动态规划算法(DP)和分治算法(DC)不再十分有效。原因是当数据库规模n足够大时，算法复杂度O(nlogn)也会变得过大。为了解决这个问题，本文提出一种使用近似算法来计算极大概率频繁项集的方法，该方法以较小的精度损失为代价，极大地提高挖掘频繁项集的效率。算法包括两个过程:候选集产生和极大概率频繁项集确认。在候选集的产生阶段，论文结合切诺夫定理得到频繁项集支持度期望的界限，大大降低了频繁项候选集的规模;在极大概率频繁项集确认阶段，论文利用中心极限定理，给出了高效估计项集的频繁度的方法。同时，论文也给出了算法中涉及的相关定理的证明，进一步增强了论文提出算法的理论性和可信性。
　　为了进一步说明算法的有效性和性能，论文在六个不同类型的数据库上进行了数值实验和性能分析。在候选集产生上，论文与经典的Apriori算法进行了比较，分析了数据库规模、支持度阈值等参数对于不同算法的影响;在极大频繁项挖掘上，论文与主流的TODIS-MAX算法进行了比较，从运行时间、频繁项的精确度等方面评价了不同算法的优缺点。大量的实验结果表明，论文提出的算法有效地降低了频繁项候选集的规模，以较小挖掘精度的损失为代价，极大地提高的极大概率频繁项集的挖掘效率。

目录

声明

摘要

1．1 课题研究的背景及意义

1．2 国内外研究现状

1．3 论文的主要工作及组织结构

第2章 相关技术介绍

2．1 基于确定数据库的频繁项集

2．1．1 确定事务数据库介绍

2．1．2 基于确定数据库的频繁项集

2．2 基于不确定数据库的频繁项集

2．2．1 不确定数据库介绍

2．2．2 可能世界语义

2．2．3 概率频繁项集

2．2．4 极大概率频繁项集

2．3 现有算法概述

2．3．2 分治算法介绍（DC）

2．3．3 自顶向下继承挖掘方法介绍（TODlS）

2．4 本章小结

第3章 极大概率频繁项集挖掘算法

3．1 算法整体思路

3．2 候选集生成算法

3．2．1 基于切诺夫界的剪枝方法

3．2．2 基于剪枝的候选集生成算法

3．3 极大概率频繁项集挖掘算法

3．3．1 APF I-MAX算法

3．3．2 频繁度估计方法

3．3．3 频繁度估计中的继承性证明

3．3．4 方差和期望的估计

3．4 本章小结

第4章 实验结果与分析

4．1 实验环境配置

4．1．2 实验数据集

4．2 实验对比方案

4．3 候选集生成算法和Apriori算法对比

4．3．1 数据库规模的影响

4．3．2 支持度的影响

4．4 PMFl和TODIS-MAX对比

4．4．1 数据库规模对运行时间的影响

4．4．2 最小相对支持度运行时间的影响

4．4．3 频繁概率阈值对运行时间的影响

4．5 精确度分析

4．5．1 数据库规模对精度的影响

4．5．2 期望和方差对精度的影响

4．5 本章小结

第5章 总结与展望

5．1 论文工作总结

5．2 未来工作展望

参考文献

攻读学位期间公开发表论文

致谢