最大频繁项集

频繁项集

称I={i1, i2, ..., im}为项( Item) 的集合, D={T1, T2, ...,Tn},i∈[1,n]为事务数据集( Transaction Data Itemsets) , 事务Ti由I 中若干项组成。

设S 为由项组成的一个集合, S={i|i∈I}，简称项集( Itemset) 。包含k个项的项集称为k-项集。

S的支持度sup(S) =（包含项集S 的事务数量/D 中总的事务数量的百分比）x100%

若S 的支持度≥给定最小支持度，称S 为频繁项集( Frequent Itemset) 。t 为一条事务, 如果S⊆t, 则称事务t 包含S。

超集Superset

若一个集合S2中的每一个元素都在集合S1中，且集合S1中可能包含S2中没有的元素，则集合S1就是S2的一个超集。 S1是S2的超集，则S2是S1的真子集，反之亦然。

最大频繁项集

如果频繁项集L 的所有超集都是非频繁项集, 那么称L 为最大频繁项集或称最大频繁模式, 记为MFI (Maximal Frequent Itemset) 。频繁项集是最大频繁项集的子集。最大频繁项集中包含了频繁项集的频繁信息， 且通常项集的规模要小几个数量级。所以在数据集中含有较长的频繁模式时挖掘最大频繁项集是非常有效的手段。

综上，最大频繁项集是各频繁k项集中符合无超集条件的频繁项集。

下例只给出频繁项集生成步骤中的项集列表，没有每个项集的频数或支持度。

候选1项集： a b c d e f

频繁1项集： a b c d

候选2项集： ab ac ad bc bd cd

频繁2项集： ab ac bc cd

候选3项集： abc abd acd bcd

频繁3项集： abc

候选4项集： abcd

频繁4项集：

最大频繁项集：abc cd

求取频繁项集：

候选1项集是全项列出，按定义的支持度阈值取出有较高值的频繁1项集

对频繁1项集二项全组合得出候选2项集，并同样按支持度阈值取出高频的频繁2项集

对频繁1项集三项全组合得出候选3项集，并同样按支持度阈值取出高频的频繁3项集

对频繁1项集四项全组合得到频繁4项集，没有满足条件的频繁集，结束。

求取最大频繁项集，由顶向下：

从有效最高项级n开始，频繁3项集只有一个abc，没有频繁4项集，故没有相应超集=>abc是一个最大频繁项集。

在n-1级的频繁2项集里，用频繁3项级排除掉ab,ac,bc=>cd是一个最大频繁项集。

在n-2级的频繁1项集里，用频繁3项级和频繁2项级排除掉所有abcd。

所以最后求出的最大频繁项集是abc和cd。