最大頻繁項集

頻繁項集

稱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)。頻繁項集是最大頻繁項集的子集。最大頻繁項集中包含了頻繁項集的頻繁信息，且通常項集的規模要小几個數量級。所以在數據集中含有較長的頻繁模式時挖掘最大頻繁項集是非常有效的手段。

下例只給出頻繁項集生成步驟中的項集列表，沒有每個項集的頻數或支持度。

候選1項集： a b c d

頻繁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。