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