Frequency itemset mining (2)- Association rule
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
-
找出符合 support 限制的 itemsets 組合
{B},{C},{E} -
找出符合 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,組合數會高達,很容易產生記憶體不足的問題。因此我們下一節會介紹幾個演算法來嘗試解決這個問題。