Apriori algorithm

    Apriori是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的关联规则挖掘算法。
本文着重于Apriori的基础过程：如何生成频繁集。而有关Apriori优化、改良的版本或其他内容，后面再另开文章介绍。

|||||||||||||||||||||||| |||||||||||||||||||||||| |||||||||||||||||||||||| |||||||||||||||||| | |

先看看以下定义：

    * 资料库（Transaction Database）：存储着二维结构的记录集。定义为：D。例如：
        TID  A   B   C   D   E   F
        --- --- --- --- --- --- ---
        001  1   0   1   1   0   0
        002  0   1   0   1   0   0
        003  1   1   1   0   1   0
        004  0   1   0   1   0   1

    * 所有项集（Items） ：所有项目的集合。定义为：I。
    * 记录（Transaction ） ：在资料库里的一笔记录。定义为：T，T ∈ D，T ⊆ I。
    * 项集（Itemset） ：同时出现的项的集合。定义为：k-itemset（k项集），k-itemset ⊆ T。除非特别说明，否则下文出现的k均表示项数。
    * 支持度（Support） ：定义为 supp(X) = occur(X) / count(D) = P(X)。
    * 置信度（Confidence/Strength） ： 定义为 conf(X->Y) = supp(X ∪ Y) / supp(X) = P(Y|X)。
    * 候选集（Candidate itemset） ：通过向下合并得出的项集。定义为C[k]。
    * 频繁集（Frequent itemset） ：支持度大于等于特定的最小支持度（Minimum Support/minsup）的项集。表示为L[k]。注意，频繁集的子集一定是频繁集。

|||||||||||||||||||||||| |||||||||||||||||||||||| |||||||||||||||||||||||| |||||||||||||||||| | |

再看看流程：

    1)  L[1] = {large 1-itemsets};
    2)  for ( k = 2; L[k-1] ≠ ∅ ; k++ ) do begin
    3)    C[k] = apriori-gen( L[k-1] ); // New candidates
    4)    forall transactions t ∈ D do begin
    5)      C[t] = subset(C[k] , t); // Candidates contained in t
    6)      forall candidates c ∈ C[t] do
    7)        c.count++;
    8)    end
    9)    L[k] = { c ∈ C[k] | c.count ≥ minsup}
    10) end
    11) Answer = ∪[k]L[k];

    解剖：

        * 1) L[1] = {large 1-itemsets};
            第一步是直接利用所有项集作生成C1和L[1]。

        * 3) C[k] = apriori-gen( L[k-1] );
            从L[k]-1生成C[k]，逻辑可以用SQL来表示，后面还会有具体例子说明：

                insert into C[k]
                  select p.item[1], p.item[2], ..., p.item[k-1], q.item[k-1]
                  from L[k-1] p, L[k-1] q
                  where p.item[1] = q.item[1], ..., p.item[k-2] = q.item[k-2], p.item[k-1] < q.item[k-1];

            由于“频繁集的子集一定是频繁集”，换句话说，就是C[k]的所有k-1子集，都必须是属于L[k-1]。所以C[k]生成后，还需要作修剪：

                3-1) forall itemsets c ∈ C[k] do
                3-2)   forall (k-1)-subsets s of c do
                3-3)     if (s ∉ L[k-1]) then
                3-4)       delete c from C[k];

        * 4) ～8) 是计算C[k]的项集的支持度。

        * 5) C[t] = subset(C[k] , t);
            求t里与C[k]的交集，以供6)～7)做计算。

        * 9) L[k] = { c ∈ C[k] | c.count ≥ minsup}
            C[k]的支持度算好了，就需要做筛选，然后正式成为L[k]

        * 11) Answer = ∪[k]L[k];
            然后这就是结果啦

|||||||||||||||||||||||| |||||||||||||||||||||||| |||||||||||||||||||||||| |||||||||||||||||| | |

下面举例说明：
    
  设：
    最小支持度为：40%
    最小置信度为：60%
    资料库为：
        TID  A   B   C   D   E
        --- --- --- --- --- ---
        001  1   1   1   0   0
        002  1   1   1   1   1
        003  1   0   1   1   0
        004  1   0   1   1   1
        005  1   1   1   1   0


    * 以下过程，如果某个步骤是空的，就说明该过程已经满足条件不需要被修剪或筛选。
    * 由于格式问题，所以用大写'U'表示数学并集符号'∪'。
    * k-itemset后带星号'*'，表示会被修剪掉或筛掉。

    +------------------------+-----------------------+-----------------------+-----------------------+
    |       Candidate       =|>  Pruning Candidate  =|>   Saving Frequent   =|>      Frequent        |
    +------------------------+-----------------------+-----------------------+-----------------------+
    |       C[1]             |                       |                       |   L[1]                |
    |       1-itemset        |                       |                       |   1-itemset support   |
    |       ---------       =|>                     =|>                     =|>  --------- -------   |
    |           A            |                       |                       |       A       100%    |
    |           B            |                       |                       |       B       60%     |
    |           C            |                       |                       |       C       100%    |
    |           D            |                       |                       |       D       80%     |
    |           E            |                       |                       |       E       40%     |
    +------------------------+-----------------------+-----------------------+-----------------------+
    |       C[2]             |                       |   L[2]                |   L[2]                |
    |       2-itemset        |                       |   2-itemset support   |   2-itemset support   |
    |       ---------       =|>                     =|>  --------- -------  =|>  --------- -------   |
    |          A,B           |                       |      A,B      60%     |      A,B      60%     |
    |          A,C           |                       |      A,C      100%    |      A,C      100%    |
    |          A,D           |                       |      A,D      80%     |      A,D      80%     |
    |          A,E           |                       |      A,E      40%     |      A,E      40%     |
    |          B,C           |                       |      B,C      60%     |      B,C      60%     |
    |          B,D           |                       |      B,D      40%     |      B,D      40%     |
    |          B,E           |                       |      B,E      20% *   |      C,D      80%     |
    |          C,D           |                       |      C,D      80%     |      C,E      40%     |
    |          C,E           |                       |      C,E      40%     |      D,E      40%     |
    |          D,E           |                       |      D,E      40%     |                       |
    +------------------------+-----------------------+-----------------------+-----------------------+
    | C[3]                   |       C[3]            |                       |   L[3]                |
    | 3-itemset              |       3-itemset       |                       |   3-itemset support   |
    | ---------             =|>      ---------      =|>                     =|>  --------- -------   |
    |   A,B,C  // AB U AC    |         A,B,C         |                       |     A,B,C     60%     |
    |   A,B,D  // AB U AD    |         A,B,D         |                       |     A,B,D     40%     |
    |   A,B,E  // AB U AE *  |         A,C,D         |                       |     A,C,D     80%     |
    |   A,C,D  // AC U AD    |         A,C,E         |                       |     A,C,E     40%     |
    |   A,C,E  // AC U AE    |         A,D,E         |                       |     A,D,E     40%     |
    |   A,D,E  // AD U AE    |         B,C,D         |                       |     B,C,D     40%     |
    |   B,C,D  // BC U BD    |         C,D,E         |                       |     C,D,E     40%     |
    |   C,D,E  // CD U CE    |                       |                       |                       |
    +------------------------+-----------------------+-----------------------+-----------------------+
    | C[4]                   |                       |                       |   L[4]                |
    | 4-itemset              |                       |                       |   4-itemset support   |
    | ---------             =|>                     =|>                     =|>  --------- -------   |
    | A,B,C,D // ABC U ABD   |                       |                       |    A,B,C,D    40%     |
    | A,C,D,E // ACD U ACE   |                       |                       |    A,C,D,E    40%     |
    +------------------------------------------------------------------------------------------------+


  根据结果和置信度导出关联规则：

    k-itemset support
    --------- -------
       A,B      60%
       A,C      100%
       A,D      80%
       A,E      40%
       B,C      60%
       B,D      40%
       C,D      80%
       C,E      40%
       D,E      40%
      A,B,C     60%
      A,B,D     40%
      A,C,D     80%
      A,C,E     40%
      A,D,E     40%
      B,C,D     40%
      C,D,E     40%
     A,B,C,D    40%
     A,C,D,E    40%

    由于结果太多，这里只取最后两个做例子：

    A,B,C,D
        if A and B and C then D    conf(A,B,C -> D) = supp(A,B,C,D) / supp(A,B,C) = 40 / 60 = 66%
        if A and B and D then C    conf(A,B,D -> C) = supp(A,B,C,D) / supp(A,B,D) = 40 / 40 = 100%
        if A and C and D then B    conf(A,C,D -> B) = supp(A,B,C,D) / supp(A,C,D) = 40 / 80 = 50% *
        if B and C and D then A    conf(B,C,D -> A) = supp(A,B,C,D) / supp(B,C,D) = 40 / 40 = 100%
        
        if A and B then C and D    conf(A,B -> C,D) = ...
        if A and C then B and D    conf(A,C -> B,D) = ...
        if A and D then B and C    conf(A,D -> B,C) = ...
        if B and C then A and D    conf(B,C -> A,D) = ...
        if B and D then A and C    conf(B,D -> A,C) = ...
        if C and D then A and B    conf(C,D -> A,B) = ...
        
        if A then B and C and D    conf(A -> B,C,D) = ...
        if B then A and C and D    conf(B -> A,C,D) = ...
        if C then A and B and D    conf(C -> A,B,D) = ...
        if D then A and B and C    conf(D -> A,B,C) = ...

    A,C,D,E
        if A and C and D then E    conf(A,C,D -> E) = supp(A,C,D,E) / supp(A,C,D) = 40 / 80 = 50% *
        if A and C and E then D    conf(A,C,E -> D) = supp(A,C,D,E) / supp(A,C,E) = 40 / 40 = 100%
        if A and D and E then C    conf(A,D,E -> C) = supp(A,C,D,E) / supp(A,D,E) = 40 / 40 = 100%
        if C and D and E then A    conf(C,D,E -> A) = supp(A,C,D,E) / supp(C,D,E) = 40 / 60 = 100%
        ... ...
        .
        .
        .

    由于现在的情况是我懒，所以我就不全列出来了。

  度量标准还有很多很多很多，如：Lift/Interest、All-confidence、Consine、Conviction、Jaccard、Leverage、Collective strength... 等等等等，太多了。
  有兴趣的同学可以多多了解一下。

|||||||||||||||||||||||| |||||||||||||||||||||||| |||||||||||||||||||||||| |||||||||||||||||| | |

温馨小提示：

    1.对于整个过程生成的itemset总数量，最坏情况是：2^k - 1。定义为：count-all(k)。例如：
        *（有一个抱歉，我记得我之前跟jas说过是2^k，但经过实验，2^k是错的）。

        TID  A   B   C   D   E
        --- --- --- --- --- ---
        001  1   1   1   0   0
        002  1   1   1   1   1
        003  1   0   1   1   0
        004  1   0   1   1   1
        005  1   1   1   1   0

        所有项是：A,B,C,D,E，共5项
        最坏情况的总数量是：2^5 - 1 = 31


    2.对于从L[1]生成C[2]，最坏情况C[2]的数量是：

        n(a1 + an)   (n - 1)(1 + n - 1)   n(n - 1)
        ---------- = ------------------ = --------
            2                 2              2

      n表示L[1]成员数量。定义为：count-first(n)。

      count-first(count(L[1]))，count(L[1])表示求L[1]的成员数量。例如：

        L[1]
        1-itemset
        ---------
            A
            B
            C
            D
            E

        最坏情况C[2]的数量是：5 * (5 - 1) / 2 = 10

    3.对于从L[k]生成C[k+1]，k≥2，最坏情况C[k+1]的数量是：

        count-group(L[k])
        ∑ count-first(count(group(L[k],i)))        如果 count(group(L[k],i))≥2
        i=1

      i：第几组同类k-itemset。
      count-group(L[k])：求L[k]里共有多少组同类k-itemset。
      group(L[k],i)：取L[k]里第i组。

      例如：

         L[3]
        +-----+
        |A,B,C|
        |A,B,D| <- 第1组
        |A,B,E|
        +-----+
        |A,C,D| <- 第2组
        |A,C,E|
        +-----+
        |A,D,E| <- 第3组
        +-----+
        |B,C,D| <- 第4组
        |B,C,E|
        +-----+
        |B,D,E| <- 第5组
        +-----+
        |C,D,E| <- 第6组
        +-----+

        *第3、5、6组将不会被纳入计算

        最坏情况C[k+1]的数量是：(3 * (3 - 1) / 2) + (2 * (2 - 1) / 2) + (2 * (2 - 1) / 2) = 5

    4.最小支持度换算：minsup * count(D)。例如：

    设：
          最小支持度是：40%

        TID  A   B   C   D   E
        --- --- --- --- --- ---
        001  1   1   1   0   0
        002  1   1   1   1   1
        003  1   0   1   1   0
        004  1   0   1   1   1
        005  1   1   1   1   0

        0.4 * 5 = 2
        接下来C[k]提升为L[k]的筛选，就直接将k-itemset的出现次数与2进行比较，而不需要每次都换算。

    5.fisher同学的一个很好的提议，为什么说是很好的提议呢？因为已经涵盖了第2点和第3点。对于从L[k]生成C[k+1]，k≥1，最坏情况C[k+1]的数量是：

        k
        ∏ n-(i-1)
        i=1
        ----------
        k
        ∏ k-(i-1)
        i=1

        n：所有项集的大小。
        k：需要生成多少项的 ?-itemset。

      例如：k = 3。I = {A, B, C, D, E}，则 n = 5。

        最坏情况C[k+1]的数量是：

        (5 - (1 - 1)) * (5 - (2 - 1)) * (5 - (3 - 1))   5 * 4 * 3
        --------------------------------------------- = --------- = 10
        (3 - (1 - 1)) * (3 - (2 - 1)) * (3 - (3 - 1))   3 * 2 * 1