基于边界快速求解EPs的算法

【作者】 赵红领；

【导师】 范明；

【作者基本信息】 郑州大学 ， 计算机软件与理论， 2004， 硕士

【摘要】 显露模式(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的挖掘算法。更多还原

【Abstract】 EPs (Emerging Patterns) are itemsets whose supports change significantly from one dataset to another. They can capture multi-attribute distinction between two datasets in the database, and can be applied to classification and predication. Recently, a lot of classifiers, which based on EPs, have been proposed, such as CAEP, JEP-Classifier, DeEP, BCEP, CEEP, and so on. Relevant research shows that their accuracies are higher than the traditional classifiers. So, it’s important to mine EPs.The efficient mining of EPs is a challenging problem, since (i) the Apriori property no longer holds for EPs, which is to say, the superset and subset of an EP might not be an EP, and (ii) there are usually too many candidates for high dimensional databases or for small support thresholds when mining EPs. Naive algorithms are too costly to solve the problem.Dong and Li apply the description of closed collection to the mining of EPs for the first time. They uses the borders of the closed collection of EPs to express the EPs, and manipulate the borders to mine EPs. The EPs-mining algorithm based on borders improves the efficiency of EPs’ mining, which makes it feasible to mine EPs efficiently. However, existing border-based algorithms are still inefficient. Moreover, The results need to be described as the union of several borders, which is not as natural as a single border and is inefficient to enumerate EPs.In this paper, we give an improved algorithm of border’s operation named FFBD( Filter First Border Differential, FFBD). To get the left border, we use the filter first and expand iteratively strategy. At the beginning of each iteration, we check the intermediate result of the former iteration. We only expand a part of them to get the candidates, and use the other part as the referential space to filter the non-minimal elements. So, the algorithm’s efficiency is improved.Furthermore, we prove that the difference of any two close interval with the same left borders is close and can be presented as a pair of upper border and lower border. Based on this, we ulteriorly propose a new border differential algorithm called EUBBD(Expanded Upper Border Border-Differential algorithm), which can manipulate two regions with the same left border and return only a pair of borders.FFBD and EUBBD are all universal algorithms of differential algorithm of interval-closed collection. Based on them, we can build an efficient algorithm to mine the EPs of any growth-rate and threshold.更多还原