CH3 關聯規則 授課老師：簡禎富 講座教授 簡禎富、許嘉裕©2014 著作權所有.

Presentation on theme: "CH3 關聯規則 授課老師：簡禎富 講座教授 簡禎富、許嘉裕©2014 著作權所有."— Presentation transcript:

1 CH3 關聯規則 授課老師：簡禎富 講座教授 簡禎富、許嘉裕©2014 著作權所有

2 關聯規則(Association Rule)
又稱購物籃分析 由Agrawal et al.(1993)提出，從蒐集的龐大交易資料中，發掘 隱含於商品間的關聯性，以瞭解消費者購買行為與產品銷售關 係

3 關聯規則的衡量指標 衡量指標： 篩選關聯規則： 支持度(support)：衡量關聯規則的顯著性
信賴度(confidence)：衡量關聯規則的正確性 增益(lift)：衡量關聯規則的資訊價值 篩選關聯規則： 最小支持度 (minimum support)門檻 最小信賴度 (minimum confidence)門檻

4 關聯規則類型 以規則中屬性值的型態為基礎 布林關聯規則 ：指關聯規則中的資料集合屬性皆為布林值， 僅探討「項目是否出現」，如0或1
以規則中所涵蓋的資料維度為基礎 單一維度關聯規則 多維度關聯規則或複合維度關聯 以規則集合中所涵蓋的抽象層級為基礎 單一層級關聯規則(single-level association rule) 多階層關聯規則(multilevel association rule)

5 關聯規則演算法 從搜尋的可能規則中，根據其支持度、信賴度和增益等衡量指 標，篩選出具有足夠支持度的所有高頻項目集(frequent itemsets)中找出屬性或項目間有所關聯的規則 規則成立條件： 避免產生的規則過於繁多導致無法凸顯真正重要的規則 適當定義最小支持度以過濾多數次要的規則 產生的規則之信賴度與增益值須高於給定的最低門檻值 關聯規則演算法主要由搜尋方式、計算項目及支持度來組成

6 搜尋與資料配置方式 搜尋方式 計算項目及支持度的方式
廣度優先搜尋：計算 K 個項目集的支持度前，先算出 K-1 項目集的支持度，才能由下往上找出項目集之關聯規則 深度優先搜尋：以遞迴地方式順著所建構的樹狀資料結構，由上而下尋找並計算項目集的支持度，以找出顯著的關聯規則 計算項目及支持度的方式 水平資料配置：計算項目發生次數來提升演算法效率。計數器的初始值設為0，之後掃描所有交易資料，假若某筆交易內存在顯著的項目時，該計數器的數值即從0開始往上累加 垂直資料配置：以交集找出顯著項目集所組成之關聯規則，其交易資料代號皆以升冪的方式儲存，以提升整體效率

7 Apriori 演算法 在大量的資料集中，利用項目集來建立關聯規則，並計算每一 個候選項目出現的數目，依據所設定的支持度來衡量候選項目 是否可建立顯著的關聯規則 採用水平方向進行項目集的搜尋；透過 k項目集之組合去探索 k+1項目集，提升發現高頻項目集的效率 由單一項目集(1-itemset)開始，反覆產生候選項目集與蒐集項 目集之步驟，直到找出所有高頻項目集為止 應用類似遞移律的概念，稱為反單調性：若某候選項目集為高 頻，則其所有的子集合必定是高頻項目集

8 Partition演算法 為解決Apriori演算法效率不彰的問題，應用「切割」的概 念將交易資料分割成一些沒有重疊的部分，使得主記憶體 運作時能加快速度。以多次小群的搜尋過程取代並降低整 體資料的搜尋過程 計算步驟 將資料庫分成多個互不相交的時間區段，分別計算區段中相關項目集的支持度，找出各區段中的高頻項目集，稱為區域高頻項目集 (local frequent itemset) 取所有區域高頻項目集之聯集，以產生D之整體候選項目集集合。對D重新計算各候選項目集的支持度，以搜尋資料庫之真正的高頻項目集 (global itemset)

9 DHP演算法 以雜湊(hash)技術，減少記錄或刪除不必要的候選2-項目 集，以改善Apriori演算法的搜尋效率
雜湊樹(hash tree)架構，設計一個雜湊函數，將資料庫中的項 目集對應至雜湊表(hash table)中，以累計各雜湊階層所包含項 目集的個數；並以所累積之階層計數粗略估算候選項目集之支 持度，以提前刪除不可能成為高頻項目集的候選項目集 雜湊表形式 箱子位置 1 2 3 4 5 6 計數 項目集 {C, E} {A, D} {A, E} {B, C} {B, E} {A, B} {A, C} {C, D}

10 MSApriori演算法 不再依循向下封閉的特性來搜尋高頻項目集，須以排序或 權重來搜尋候選項目集及建立規則
能對各項產品項目之最小支持度閥值做出合適的定義 不再依循向下封閉的特性來搜尋高頻項目集，須以排序或 權重來搜尋候選項目集及建立規則 給予各商品組合不同權重，並由不同的支持度門檻值來建構關 聯規則，以避免效益高但發生頻率較低的商品組合被刪除

11 FP-Growth演算法 為目前最有效率的關聯規則演算法
將資料庫內含之頻繁項目集壓縮到一棵頻繁模式樹(FP-tree)中， 並保留項目集間的重要關聯資訊 在挖礦時不需產生大量的候選項目集，最多只需掃描資料庫兩 次，可大量減少I/O時間 分為兩個階段： 建立FP-tree 挖掘FP-tree FP-tree是先儲存交易資料庫中交易紀錄項目集所對應的交易紀錄筆數，利用相同「字首」(prefix)共享樹中同一路徑(path)的原則，而可將各項目集在資料庫出現過的資訊緊密壓縮儲存於FP-tree中

12 建構FP-tree的三個步驟 第一次掃描資料庫，找出符合最小支持度的第一階高頻項目集， 依支持度大小降冪排列
建立FP-tree的根節點，標示為空節點，再次掃描資料庫，將 高頻項目集的交易紀錄依步驟1所排列的項目順序加入FP-tree 為使FP-tree更容易解讀，建立項目連接表。使每個項目可透 過一個節點鏈來指出該葉節點在樹中出現的位置

13 FP-growth演算法程序三階段 由項目連接表中的項目欄由下而上，依葉節點X座落的順序挖 礦，按照每個關聯項目連接FP-tree，以找出FP-tree中X葉節 點的字首路徑，而X葉節點之字首路徑所建構之FP-tree即稱為 X的條件頻繁模式樹 以相同方法遞迴挖礦X的條件FP-tree，計算模式庫中每個項目 的支持度，找出非空集合且具有高頻項目集特徵的項目集合， 用模式庫中的高頻項目與X組合成高頻項目集，列於候選項目 集中 運用階段一與階段二之模式不斷地對FP-tree遞迴挖礦，找出 包含該葉節點之所有字首路徑，直到所有的葉節點均不存在任 何字首路徑

14 多維度關聯規則 一般關聯規則僅在單筆交易紀錄內 找尋項目間的關係 若加入多維度概念，以時間為另一 維度因子時，則可挖掘出
購買尿布購買啤酒 若加入多維度概念，以時間為另一 維度因子時，則可挖掘出 顧客週末均會購買尿布購買啤酒 紀錄項目具有多個屬性值，並藉由 定義數個多維度限制式，尋求不同 交易間的關聯式法則，以推廣至高 維度空間之交易資料庫 二維資料 交易紀錄示意圖

15 多階層關聯規則 建立概念層級樹(concept hierarchy tree)，可挖掘更多概念層 級之階層關聯規則
交易筆次 項目集 501 帆布鞋、牛仔褲、短外套 502 籃球鞋、短外套 503 低筒皮鞋、V領上衣 504 娃娃鞋、長外套、丹寧褲 資料量少，很難發掘項目間的關係 提升概念層級數後，較容易發現某些鞋類與服飾之間的關聯規則

16 GID編碼 GID (generalized identifier)利用編碼方式，將概念層級樹所 包含的原始資料名稱項目重新定義並以數值重新編碼，以萃取 階層概念的關聯規則 編碼方式取決於交易紀錄、商品種類以及階層樹的多寡 交易筆次 項目集 501 帆布鞋、牛仔褲、短外套 502 籃球鞋、短外套 503 低筒皮鞋、V領上衣 504 娃娃鞋、長外套、丹寧褲 交易筆次 項目集 501 {121}、{231}、{222} 502 {112}、{222} 503 {132}、{212} 504 {122}、{221}、{232}

17 關聯規則的應用 關聯規則須同時經過領域知識的推論與評估，才能決定哪 些規則能夠發展成有用的資訊 挖掘到的關聯規則可區分為兩大類：
可依常理推論之規則 巧合造成之無法解釋規則 關聯規則於商業實務的應用包括： 分析顧客行為 進行市場區隔與選擇目標顧客 改進賣場陳設與實行目標行銷 組合搭售商品 發掘詐欺行為 流失客戶分析 

18 建構關聯規則資料挖礦方法及其在台電配電事故定位之研究
PDF Reference: 彭金堂、張盛鴻、簡禎富、楊景晴（2004），建構關聯規則資料挖礦架構及其在臺電配電事故定位之研究，資訊管理學報，12(4)， 。 18

19 研究背景 配電事故對於電力系統的安全性、 可靠度以及供電品質均有很大影響。 當配電事故發生時，台電人員必須 檢視發生原因或利用發電試驗找出 事故的發生位置，並進一步將之隔 離與維修 如何發展一套可以快速找到事故發 生地點的方法來縮短供電恢復時間， 為電力公司所關心的議題 Where? What?

20 研究目的 運用關聯規則分析挖掘事故診斷記錄的共同特性，從配電事故記錄歷史資料中，找出事故發生原因與損壞設備間的關聯性
支持度(support) 信賴度(confidence) 增益(lift) 提供維修人員系統化、科學化的參考資訊，在特定決策環境下 推測配電事故的樣型，減少事故定位所需的時間 輸入屬性 目標屬性 氣候、停電範圍、相數、電壓、事故情形、事故原因、季節、時辰 損壞部位

21 資料準備 本個案研究所採用的資料為台電公司於1995至1997年間台 北市區的配電事故記錄表，共有1,649筆資料
針對「損壞部位」資料屬性進行統計與圖表分析，以初步檢視資料之分布樣型

22 範例說明-問題架構 輸入屬性：天氣、事故情形、事故原因 目標屬性：損壞部位
天氣屬性包含有兩個項目，分別是0代表雨天以及1代表陰天， 其他項目組的定義如下表最後一列所示 資料 編號 輸入屬性 目標屬性 天氣 事故情形 事故原因 損壞部位 1 2 3 4 5 -- 6 定義 0：雨天 1：陰天 0：挖斷 1：燒斷 2：斷落 0：外物碰觸 1：自然劣化 2：絕緣劣化 0：高壓電纜 1：變壓器 22

23 範例說明-資料準備 編號5資料有兩個遺失值，且無法補值，將該筆資料刪除， 利用剩餘的5筆資料來產生關聯規則 資料 編號 輸入屬性 目標屬性
天氣 事故情形 事故原因 損壞部位 1 2 3 4 5 -- 6 定義 0：雨天 1：陰天 0：挖斷 1：燒斷 2：斷落 0：外物碰觸 1：自然劣化 2：絕緣劣化 0：高壓電纜 1：變壓器 23

24 範例說明- 計算支持度與找出高頻項目組 事先定義最小支持度為30%，下表中最右一欄打勾的有四種組合，其支持度 為40%，高於最小支持度，選取為高頻項目組 前提項目X 結果項目Y 支持度 高頻項目組 天氣：0 部位：0 1/5 = 0.2 天氣：1 0.2 部位：1 2/5 = 0.4  情形：1 情形：0 情形：2 0.4 原因：1 原因：2 原因：0 （其他可能組合省略，其支持度皆等於0.2） 24

25 範例說明- 計算信賴度與找出候選規則 事先定義的最小信賴度為80%，下表中最右欄打勾的有二種組 合，其信賴度為100%，高於最小信賴度，選為候選規則 前提項目X 結果項目Y 信賴度 候選規則 天氣：1 部位：1 情形：1 2/3 原因：0  1 25

26 範例說明-產生關聯規則 計算所有候選規則的增益，是否大於1
規則以下表所示，若規則表示為XY，即如果事故原因為外物 碰觸，則可以推論損壞部位為變壓器「支持度為40%，信賴度 100%」 前提項目X 結果項目Y 增益 關聯規則 原因：0 部位：1  天氣：1 5/3 26

27 實證研究-關聯規則推導 以關聯規則工具挖掘在決策環境下推測配電事故的樣 型(規則) 參數設定依據如下：
支持度：假設分布服從均勻分配，每一損壞部位平均應有13筆資料(780筆，60種可能損壞部位)，設定其支持度應大於13/780＝1.67％，才足夠顯著 信賴度：設定需大於50％，保證獲得之關聯規則其顯著程度達一半以上 增益：值需>1 27

28 篩選顯著關聯規則 28

29 篩選後之關聯規則 … 規則1為例，當巡修股人員發現事故情形為「挖斷」時，可以推論損壞部位 為「高壓電纜」的機率很高 29
輸入變數(前提項目組) 目標變數(損壞部位) 支持度 信賴度 增益 1.事故情形[挖斷] 2.事故情形[挖斷] 且 事故原因[施工機器碰觸] 3.相數[3ø] 且 事故情形[挖斷] 4.氣候[晴] 且 事故情形[挖斷] 5.氣候[晴] 且 事故情形[挖斷] 且 事故原因[施工機器碰觸] ==>[高壓電纜] 12.05 11.66 8.33 8.84 8.71 100 3.61 1.氣候[陰] 且 事故原因[用戶設備不良] 2.時辰[17點~1點] 且 事故原因[用戶設備不良] 3.相數[3ø] 且 事故原因[用戶設備不良] 4.相數[3ø] 且 事故原因[用戶設備不良] 且 停電範圍[高壓戶] ==>[用戶設備] 2.17 1.92 3.46 2.56 17.33 16.71 1.電壓[22KV] 且 停電範圍[地下高壓幹線] 且 氣候[陰] ==>[高壓電纜直線接頭] 2.30 51.43 4.72 1.停電範圍[架空高壓分歧] 且 事故情形[燒損] 且 事故原因[自然劣化] ==>[熔絲鏈開關] 71.43 10.13 … 29

30 案例小結 建構關聯規則資料挖礦模式，並利用台電配電事故歷史資 料為實證來檢驗其效度
「高壓電纜」、「用戶設備」、「高壓電纜直線接頭」及 「熔絲鏈開關」四項損壞設備有關 以系統的方法與決策的規則，提供台電巡修股人員即時決 策的有效方法 最小支持度的選取，影響模式之效率 30

31 結論 關聯規則是資料挖礦中最常用於分析顧客交易紀錄中商品項目 關聯性的方法之一。若能以適當的演算方法挖掘出不同顧客群 的需求，便能發現商機、創造利潤 顧客的消費行為會隨著時間而改變，所以需不斷地重新挖礦以 更新資料庫並週期性地執行關聯規則運算，以萃取出最新的關 聯規則來洞悉顧客消費型態 在產生關聯規則的程序中，會有許多重複或不重要的關聯規則， 如何制定合適之支持度、信賴度與增益值門檻亦為關聯規則分 析重要的議題