Mining top-k frequent patterns without minimum support threshold
Mining top-k frequent patterns without minimum support threshold
复制标题
DOI：
10.1007/s10115-010-0363-3
复制
发表时间：
2012-01-01
影响因子：
2.7
通讯作者：
Khayal, M. Sikandar Hayat
中科院分区：
文献类型：
--
作者：
Salam, Abdus;Khayal, M. Sikandar Hayat
寻找频繁模式在挖掘关联规则、序列、情节、Web日志挖掘以及数据之间的许多其他有趣关系方面发挥着重要作用。频繁模式挖掘方法通常会产生大量频繁项集，而这些频繁项集无法有效使用。高度相关的模式的数量通常非常少，甚至可能只有一个。大多数现有的频繁模式挖掘技术通常需要设置许多输入参数，并且可能涉及对数据库的多次遍历。最小支持度是频繁模式挖掘中广泛使用的参数，用于发现统计上显着的模式。对于数据分析师来说，指定适当的最小支持是一项具有挑战性的任务，因为最小支持值的选择有些随意。一般来说，需要反复执行一个算法，在大范围内启发式地调整最小支持度的值，直到得到想要的结果，当然，这是一个非常耗时的过程。设置不适当的最小支持也可能导致算法无法找到真正的模式。我们提出了一种新颖的方法，可以在不使用最小支持参数的情况下按重要性顺序有效地检索前几个最大频繁模式。相反，我们只需要指定一个更容易理解的参数，即所需的数量项集 k。我们的技术只需要对数据库进行一次遍历并生成长度为两个的项集。关联比率图被提出为包含简洁信息的紧凑结构，其创建时间与数据库大小成二次方。描述了使用该图结构在没有最小支持阈值的情况下发现最顶层和前k个最大频繁项集的算法。为了有效地实现这一点，该方法采用构建全路径源到目的地树来发现图中的所有最大循环。结果可以按重要性降序排列。结果显示了使用这种方法可以获得的性能优势。
Finding frequent patterns play an important role in mining association rules, sequences, episodes, Web log mining and many other interesting relationships among data. Frequent pattern mining methods often produce a huge number of frequent itemsets that is not feasible for effective usage. The number of highly correlated patterns is usually very small and may even be one. Most of the existing frequent pattern mining techniques often require the setting of many input parameters and may involve multiple passes over the database. Minimum support is the widely used parameter in frequent pattern mining to discover statistically significant patterns. Specifying appropriate minimum support is a challenging task for a data analyst as the choice of minimum support value is somewhat arbitrary. Generally, it is required to repeatedly execute an algorithm, heuristically tuning the value of minimum support over a wide range, until the desired result is obtained, certainly, a very time-consuming process. Setting up an inappropriate minimum support may also cause an algorithm to fail in finding the true patterns. We present a novel method to efficiently retrieve top few maximal frequent patterns in order of significance without use of the minimum support parameter. Instead, we are only required to specify a more human understandable parameter, namely the desired number itemsets k. Our technique requires only a single pass over the database and generation of length two itemsets. The association ratio graph is proposed as a compact structure containing concise information, which is created in time quadratic to the size of the database. Algorithms are described for using this graph structure to discover top-most and top-k maximal frequent itemsets without minimum support threshold. To effectively achieve this, the method employs construction of an all path source-to-destination tree to discover all maximal cycles in the graph. The results can be ranked in decreasing order of significance. Results are presented demonstrating the performance advantages to be gained from the use of this approach.