论文部分内容阅读
显露模式(Emerging Patterns，EPs)是指那些从一个数据集到另一个数据集支持度发生显著变化的项集，它们能够捕获数据库中两个数据集之间的多个属性上的差异，可以用来建立分类器。近来已经提出了一系列基于EPs的分类器，如CAEP、JEP-Classifier、DeEP、BCEP、CEEP等。相关研究表明，它们的分类精度显著的优于传统的分类器。因此，EPs的挖掘具有重要的意义。 EPs的有效挖掘是一个具有挑战性的课题。因为，(ⅰ)EPs不具有Aptiori的性质，即EP的超集和子集都不一定是EP；(ⅱ)在挖掘EPs时，如果数据集维数较高或支持度阈值较低，需要考察的候选项数量巨大。因此，朴素的挖掘算法效率太低而几乎不可行。 Dong和Li首先把集族闭区间的表示引入到EPs的挖掘，提出了利用集族边界来表示EPs，利用边界运算来挖掘EPs。基于边界的EPs挖掘算法提高了EPs的挖掘效率，进而使得EPs的有效挖掘具有可行性。然而，已有的边界算法效率仍然很低，并且所挖掘的结果需要用一组上下边界表示，形式不自然，枚举EPs的效率低。 本文首先提出了一种改进的边界运算算法FFBD(Filter First Border Differential，FFBD)，该算法在求解差区间的左边界时，逐层迭代扩展，并采取优先过滤的策略：在每层迭代前，考察上层迭代的中间结果，选择其中的一部分扩展为候选项，另外一部分作为过滤非最小项时的比较空间，提高了算法的效率。 然后，我们证明了具有相同左边界的两个任意闭区间的差是闭的，可以用一对上下边界表示。在此基础上，本文提出了一种新的边界运算算法EUBBD(Expanded Upper Border Border-Differential，EUBBD)，能够有效地计算具有相同左边界的两个任意闭区间的差，返回一对上下边界。 FFBD和EUBBD都是通用的集族区间边界运算算法，我们在此基础上可以构建挖掘任意给定支持度和增长率EPs的挖掘算法。