Association rule learning 就是在資料中找尋關係,如買尿布的人很有可能會買奶粉,我們稱尿布與奶粉有”關係”。其定義如下:


若所有在 X 中的 item 皆出現在 basket 中,則Y很有可能也會出現在 basket 中。

那如何量化並描述這個”可能”呢? 首先要先介紹一些名詞跟觀念:

  • database T:

    basket ID A B C D E
    1 1 1 0 0 0
    2 0 0 1 0 1
    3 0 1 0 1 1
    4 1 1 1 0 0
    5 0 1 1 1 1

    1代表有買,0代表無

  • Support:
    意思是 itemset X 有多常出現在database中,也就是X出現的機率

  • Confidence:
    意思是這條關聯有多常是對的,又可以說是有多少機率這條關聯成立。其實基本上這就是條件機率,在 X 出現的機率下,X,Y 同時出現的機率。
    這邊有個容易令人搞混的地方,既然他是條件機率,為什麼是 X ∪ Y 呢? 因為 X,Y 皆為集合而不是機率,故


    EX: conf({A,B} => {C}) = 0.2/0.4 = 1/2

  • Interest:
    並不是每個有高 confidence 的關聯都是我們想要找的,若 Y 出現在每個 bucket,找到 X 與 Y 關聯則沒有什麼意義。因此我們將 confidence 減掉 Y 出現的機率,這個值夠大(通常大於0.5),我們才說這是一條有意義的關聯。

  • Lift:
    若 lift = 1 ,則代表 X,Y 兩者獨立,此條關聯也就毫無意義。

有了上述的概念後,我們即可定義想要找的 association rule: EX: Find all association rules with support > 0.4 and confidence > 0.5

  1. 找出符合 support 限制的 itemsets 組合
    {B},{C},{E}

  2. 找出符合 confidence 限制的 rule
    conf(B → C) = 0.5 (X)
    conf(C → B) = 0.667 (○)
    conf(C → E) = 0.667 (○)
    conf(E → C) = 0.667 (○)
    conf(B → E) = 0.5 (X)
    conf(E → B) = 0.667 (○)

當資料量很大,在第一步上就會遇到困難,為了要找出在 I 中的所有可能的 itemsets,組合數會高達,很容易產生記憶體不足的問題。因此我們下一節會介紹幾個演算法來嘗試解決這個問題。