PARASOL: a hybrid approximation approach for scalable frequent itemset mining in streaming data
PARASOL: a hybrid approximation approach for scalable frequent itemset mining in streaming data
复制标题
PARASOL：一种用于流数据中可扩展频繁项集挖掘的混合近似方法
DOI：
10.1007/s10844-019-00590-9
复制
发表时间：
2019
影响因子：
3.4
通讯作者：
Koji Iwanuma
中科院分区：
文献类型：
--
作者：
Yoshitaka Yamamoto;Yasuo Tabei;Koji Iwanuma
在这里，我们提出了一种新的算法频繁项集挖掘流数据（FIM-SD）。在过去的十年中，已经提出了各种FIM-SD方法在一次近似设置，允许近似每个项集的支持。它们可以分为两种近似类型：参数约束（PC）挖掘和资源约束（RC）挖掘。PC方法基于预定义的参数控制可以包括在近似支持中的最大误差。相比之下，RC方法基于资源约束限制最大内存消耗。然而，现有的PC方法可以指数地增加存储器消耗，而现有的RC方法可以快速地增加最大误差。在这项研究中，我们解决这个问题，通过引入一个混合的方法PC-RC近似，calledPARASOL。对于任何流数据，PARASOL确保提供一个压缩表示，称为Δ-覆盖集，它被认为是封闭性压缩的扩展;当Δ = 0时，解决方案对应于普通的封闭项集。PARASOL搜索近似闭项集，该近似闭项集能恢复频繁项集及其支持度，且最大误差为一个整数Δ.然后，我们经验证明，该算法显着优于最先进的PC和RC方法FIM-SD。
Here, we present a novel algorithm for frequent itemset mining in streaming data (FIM-SD). For the past decade, various FIM-SD methods in one-pass approximation settings that allow to approximate the support of each itemset have been proposed. They can be categorized into two approximation types:parameter-constrained(PC) mining andresource-constrained(RC) mining. PC methods control the maximum error that can be included in the approximate support based on a pre-defined parameter. In contrast, RC methods limit the maximum memory consumption based on resource constraints. However, the existing PC methods can exponentially increase the memory consumption, while the existing RC methods can rapidly increase the maximum error. In this study, we address this problem by introducing a hybrid approach of PC-RC approximations, calledPARASOL. For any streaming data, PARASOL ensures to provide a condensed representation, called aΔ-covered set, which is regarded as an extension of the closedness compression; when Δ = 0, the solution corresponds to the ordinary closed itemsets. PARASOL searches for such approximate closed itemsets that can restore the frequent itemsets and their supports while the maximum error is bounded by an integer, Δ. Then, we empirically demonstrate that the proposed algorithm significantly outperforms the state-of-the-art PC and RC methods for FIM-SD.