数据挖掘中的模式发现（一）频繁项集、频繁闭项集、最大频繁项集

青旅半醒 2022-07-11 12:27 951阅读 0赞

## Frequent Itemset(频繁项集) ##

称 I = \{ i 1 , i 2 , . . . , i m \} I=\\\{i\_1, i\_2, ..., i\_m\\\} I=\{ i1,i2,...,im\}为**项(Item)的集合**， D = \{ T 1 , T 2 , . . . , T n \} D=\\\{T\_1, T\_2, ...,T\_n\\\} D=\{ T1,T2,...,Tn\}， i ∈ \[ 1 , n \] i∈\[1,n\] i∈\[1,n\]为**事务数据集(Transaction Data Itemsets)**，事务 T i T\_i Ti由 I I I中若干项组成。

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

t t t为一条事务, 如果 S ⊆ t S\\subseteq t S⊆t, 则称事务 t t t包含 S S S。

**S S S的支持度**： s u p ( S ) = ( 包 含 S 的 事 务 数 量 D 中 总 的 事 务 数 量 ) × 100 % sup(S) = (\{包含S的事务数量\\over D中总的事务数量\})\\times 100\\% sup(S)=(D中总的事务数量包含S的事务数量)×100%

若 S S S的支持度≥给定最小支持度，称 S S S为**频繁项集(Frequent Itemset)**。

例如，有交易数据库

TID为事务编号，item为事务数据集的内容。

现在有项集 S 1 = \{ b , c \} S\_1 = \\\{b,c\\\} S1=\{ b,c\}，它出现在TID为1,2,3的事务中，也就是 S 1 ⊆ \{ a , b , c \} S\_1\\subseteq \\\{a,b,c\\\} S1⊆\{ a,b,c\}， S 1 ⊆ \{ a , b , c , d \} S\_1\\subseteq \\\{a,b,c,d\\\} S1⊆\{ a,b,c,d\}， S 1 ⊆ \{ b , c , e \} S\_1\\subseteq \\\{b,c,e\\\} S1⊆\{ b,c,e\}。

所以 S 1 S\_1 S1的支持度计数为3，支持度为 3 5 3\\over 5 53。

如果支持度阈值小于 60 % 60\\% 60%，那么 S 1 S\_1 S1就是一个频繁项集。

## Superset(超集) ##

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

接着上面的例子，

现在有项集 S 1 = \{ b , c \} S\_1 = \\\{b,c\\\} S1=\{ b,c\}，那么它就是 \{ b \} \\\{b\\\} \{ b\}， \{ c \} \\\{c\\\} \{ c\}的超集。 S 1 S\_1 S1也是 \{ a , b , c \} \\\{a,b,c\\\} \{ a,b,c\}等的真子集。

## Max Pattern/Maximal Frequent Itemset(最大频繁项集) ##

如果频繁项集L的所有超集都是非频繁项集，那么称L为**最大频繁项集**或**称最大频繁模式**，记为MFI (Maximal Frequent Itemset)。

频繁项集是最大频繁项集的子集。最大频繁项集中包含了频繁项集的频繁信息，且通常项集的规模要小几个数量级。所以在数据集中含有较长的频繁模式时挖掘最大频繁项集是非常有效的手段。

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

接着上面的例子，

现在有项集 S 1 = \{ b , c \} S\_1 = \\\{b,c\\\} S1=\{ b,c\}，且有支持度阈值 ＝ 60 % ＝60\\% ＝60%。

那么 S 1 S\_1 S1就是一个频繁项集，那么我们来看看它的超集。

<table> 
 <thead> 
  <tr> 
   <th align="center">Superset</th> 
   <th align="center">count</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">abc</td> 
   <td align="center">2</td> 
  </tr> 
  <tr> 
   <td align="center">bcd</td> 
   <td align="center">1</td> 
  </tr> 
  <tr> 
   <td align="center">bce</td> 
   <td align="center">1</td> 
  </tr> 
  <tr> 
   <td align="center">abcd</td> 
   <td align="center">1</td> 
  </tr> 
  <tr> 
   <td align="center">abce</td> 
   <td align="center">0</td> 
  </tr> 
  <tr> 
   <td align="center">bcde</td> 
   <td align="center">0</td> 
  </tr> 
  <tr> 
   <td align="center">abcde</td> 
   <td align="center">0</td> 
  </tr> 
 </tbody> 
</table>

由此可见，它们的支持度都小于 60 % 60\\% 60%，所以它们都不是频繁项集。

所以 S 1 S\_1 S1的所有超集都不是频繁项集，则它是最大频繁项集。

## close pattern(闭合频繁项集) ##

所谓闭项集，就是指一个项集X，它的\*\*直接超集（最小的严格超集）\*\*的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的，也就是它的支持度大于等于最小支持度阈值，那它就称为闭频繁项集。

接着上面的例子，

因为项集\{b,c\}出现在TID为1,2,3的事务中，所以\{b,c\}的支持度计数为3。而\{b,c\}的直接超集：\{a,b,c\}的支持度计数为2，都不等于\{b,c\}的支持度计数3，所以\{b,c\}为闭项集，如果支持度阈值为40%，则\{b,c\}也为闭频繁项集。

项集\{a,b\}出现在TID为1,2的事务中，其支持度计数为2。而它的直接超集\{a,b,c\}支持度计数也为2，所以\{a,b\}不是闭项集。