今天的上課重點是
授課教授：交通大學 交通運輸研究所 陳穆臻 教授
參考書籍：Introduction to Data Mining, Tan, P. T., Steinbach, M., Kumar,. Vipin
１. 關聯分析（Association Analysis）
２. 關連規則（Association Rule）
３. 關連規則的探勘（Mining Association Rule）
４. 關連規則的簡化（Reducing Association Rule）
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
１. 關聯分析（Association Analysis）
關聯分析，在資料探勘上也是相當重要的一個主題，因為提到資料探勘大家最愛提到的例子：
「尿布與啤酒」這個從全球最大零售商 Walmart百貨來的經典案例。
就是Walmart發現，在同一個購物籃結帳時「啤酒」經常跟「尿布」伴隨在一起，
換句話說就是「啤酒」與「尿布」經常「關連」在一起，
因此，關連分析經常也叫做「購物籃分析」，也常拿交易記錄做範例。
上述，是一個五筆交易的紀錄，購物籃的特色就是，只有兩個欄位
一是交易編號，另一個就是買了什麼，所以第二個欄位有多少東西是不一定的。
而我們可以從這五筆交易資料中發現一些規則（Rule），比方說：
{Diaper}→{Beer}
{Milk,Diaper}→{Eggs,Coke}
從上述會發現一件事：購物籃 沒有因果關係，只有關連而已！
＝＝＝＝＝＝＝＝接著進入比較數學的部分了！！（有趣！）＝＝＝＝＝＝＝＝＝
既然是購物籃，那一定可以探出一些經常被購買，
或一起購買的項目，這類的項目我們稱為「項目集（Itemset）」
也會聽到 K-Itemset，是指有K個項目包在一起，如 1-Itemset、2-Itemset。
接著我們會好奇這個項目集總共在交易記錄中出現了幾次？
這個稱作 「支持數 Support count （σ）」，比方說 σ {Bread, Milk}的支持數 = 3
再來，我們又會問，這些項目集總共占了總交易次數的多少呢？
即為支持數 ÷ 總交易數 ＝ 支持度（Support），比方說 S( {Bread, Milk}) = 3/5 = 0.6
最後，這些經常被購買的項目組，會給個名稱叫做「強物項（Frequent Itemset）」
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
２. 關連規則（Association Rule）
緊接著，介紹什麼叫做「關連規則（Association Rule）」
所謂關連的意思是 X → Y ，即為 X 關聯到 Y ，比方說：
{Milk, Diaper} → {Bread}，即為 買牛奶跟尿布，會關聯到買麵包
既然是規則，我們就要量化這個規則的好壞程度
我們採用的方法是計算剛剛提到的支持度（Support）
S ＝ σ {Milk, Diaper, Bread} / 全部的交易數 ＝ 2 / 5 ＝ 0.4
這邊我們看到，計算支持度必須同時把 X 與 Y 放在一起看
另外支持度的意思，牛奶、尿布、麵包三者同時出現時，佔據所有交易比數的多少。
另外，我們還會計算他的信賴度（Confidence）
C ＝ σ{Milk, Diaper, Bread} / σ{Milk, Diaper} ＝ 2 / 3 ＝ 0.67
所以信賴度的意思是
出現牛奶還有尿布的次數，與牛奶、尿布、麵包同時出現的次數是多少的比值。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
３. 關連規則的探勘（Mining Association Rule）
今天既然我們會從交易記錄裡頭看一些規則了，那下面這個課本的例子就相當不錯
以下是{Milk, Diaper, Beer}的排列組合
{Milk,Diaper} → {Beer} (s=0.4, c=0.67)
{Milk,Beer}→ {Diaper} (s=0.4, c=1.0)
{Diaper,Beer}→ {Milk} (s=0.4, c=0.67)
{Beer} → {Milk,Diaper} (s=0.4, c=0.67)
{Diaper} → {Milk,Beer} (s=0.4, c=0.5)
{Milk} → {Diaper,Beer} (s=0.4, c=0.5)
從中可以看到，大家的支持度都是一樣啦！但大家卻有著不同的信賴度？！
這邊，導出了一個很重要的觀念「 What is Frequent Itemset ? 」
強物項就是規則的 支持度Support >= 我們設定的最小支持度 minsup
再來，「How to Generation Rule？」
一個好的規則，首先要符合他至少是個強物項，且！必須要有夠高的信賴度（Confidence）
符合以上條件，才能算是一個好的規則！
但是！！！！！強物項的產生計算過程，是相當繁雜的
比方說 我只有 ABCDE五項產品，經過排列組合，就會產生 2的五次方 種組合。
這更何況是賣場上成千上萬總商品，不就會算到死？！
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
４. 關連規則的簡化（Reducing Association Rule）
因此，我們必須透過一些機率的概念，產生可以依靠策略，來減少我們計算的複雜程度。
1. 減少排列組合的次數
2. 減少交易的筆數
3. 採用更好的資料儲存架構
這邊僅介紹，怎麼減少排列組合的次數，其餘方法有興趣可在找尋相關書籍
關於減少排列組合的次數，首先要了解「先驗法則（Apriori principle）」：
也就是說假設ABC三項產品，{A}的支持度一定會大於等於{A,B}
而{A, B}的支持度也一定會大於等於{A,B,C}
如此一來，我們就可以大幅減少運算的次數，如圖所示：
而上面的詳細步驟如下：
首先：假設我們的Minimum Support = 3，也就是支持數要超過三次，才算強物項
第二步：先從 K-itemset = 1 開始
第三步：換 K-itemset = 2
這步驟我們砍掉{麵包、啤酒}，還有{牛奶、啤酒}這兩個選項
第四步：換 K-itemset = 3
