论文总结(negFIN: An efficient algorithm for fast mining frequent itemsets)

时间:2021-09-15 01:02:23

一、论文整体思路:

作者提出了一种基于前缀树的数据结构,NegNodeset,其实是对之前前缀树的一种改进,主要区别在于采用了位图编码,通过这种数据结构产生的算法称为negFIN。

negFIN算法高效有三个原因

二、问题定义

I= {i1,i2,…, init} 表示事务数据库所有项的集合,T表示每个事务,T⊆I ,DB = {T1,T2,…, Tnt} 是所有事务的集合

P称为k-项集,如果P⊆T ,那么事务T包含了项集P,support(P)是DB中包含P的百分比,如果support(P)大于min-support

我们就称P为频繁项集,频繁项集是2的nit 次方,nit = |I| 。

三、之前贡献

主要对前缀树的研究,结构1)Node-list,2)N-list,3)Nodeset,4)DisffNodeset (***先理解下前缀树和哈希树)

1) Node-list和N-list是通过对节点进行先序和后序排列,这两种数据结构产生的算法分别是PPV和PrePost频繁项集挖掘算法,

这两个算法的缺点消耗了大量内存;

2)对于这种情况,数据结构Nodeset将其进行改进,k-项集的获得通过取k-1项集的交集,算法为FIN,确定是对于一些数据集Nodeset基数太大;

3)为了将其进行改进,DiffNodest数据结构提出,k-项集的获得两个不同的k-1项集获得,算法为dFIN,算法的更快了。

4)文中提出了NegNodeset为了实现计算两个不同的DiffNodesets花费时间较长,主要利用的是位图,提出的算法negFIN;

四、相关工作

频繁项集挖掘算法

1)通过产生候选项集

比如Apriori算法,以及一些其他的算法,这种方法的主要缺点是需要多次扫描数据库。

2)模式增长方法

这种方式不会产生候选项集,也避免了多次扫描数据库,包括FP-tree和FP-growth算法,缺点:对于稀疏的数据集效率低,数据结构复杂。

3)前缀树方法

五、基本术语

F1频繁项集的集合,例如F1 = {e, b, a, c, d} ,
L1是根据支持度进行非降序排列的频繁项集L1 = [e, d, c, b, a] ,L1 = [i0,i1,…, inf - 1] ,nf=|F1|
k-项集P,Pk = ik…i2i1 ,ik>...>i2>i1

例如P = {e, b, d} ,P3 = bde ,对Pk进行位图编码BMC(Pk) = bnf - 1…b1b0 ,这里需要注意的是

BMC(node-path)分为两部分,主要部分和无关部分