Direct local pattern sampling by efficient two-step random procedures
Direct local pattern sampling by efficient two-step random procedures
复制标题
DOI：
10.1145/2020408.2020500
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
Mario Boley;C. Lucchese;Daniel Paurat;Thomas Gärtner
中科院分区：
文献类型：
--
作者：
Mario Boley;C. Lucchese;Daniel Paurat;Thomas Gärtner
我们提出了几个精确的和高度可扩展的局部模式采样算法。它们可以作为一种替代穷举局部模式发现方法（例如，频繁集挖掘或基于乐观估计的子群发现），并可以大大提高效率以及模式发现过程的可控性。虽然以前的采样方法主要依赖于马尔可夫链蒙特卡罗方法，但我们的程序是直接的，即，非过程模拟，采样算法。这些直接方法的优点是每个模式的时间复杂度几乎是最优的，以及所产生的模式的精确控制的分布。也就是说，所提出的算法可以根据频率，面积，平方频率，和类的区分度措施（项目）集的样本。实验表明，这些程序可以提高基于模式的模型，类似于频繁集的准确性，往往也导致可扩展性方面的实质性收益。
We present several exact and highly scalable local pattern sampling algorithms. They can be used as an alternative to exhaustive local pattern discovery methods (e.g, frequent set mining or optimistic-estimator-based subgroup discovery) and can substantially improve efficiency as well as controllability of pattern discovery processes. While previous sampling approaches mainly rely on the Markov chain Monte Carlo method, our procedures are direct, i.e., non process-simulating, sampling algorithms. The advantages of these direct methods are an almost optimal time complexity per pattern as well as an exactly controlled distribution of the produced patterns. Namely, the proposed algorithms can sample (item-)sets according to frequency, area, squared frequency, and a class discriminativity measure. Experiments demonstrate that these procedures can improve the accuracy of pattern-based models similar to frequent sets and often also lead to substantial gains in terms of scalability.