關聯規則學習（Association rule learning）是一種在大型資料庫中發現變數之間的有趣性關係的方法。它的目的是利用一些有趣性的量度來識別資料庫中發現的強規則。基於強規則的概念，Rakesh Agrawal等人引入了關聯規則以發現由超市的POS系統記錄的大批交易數據中產品之間的規律性。。
基本介紹
- 中文名：關聯規則學習
- 外文名：Association rule learning
- 領域：數據挖掘
- 目的：挖掘事物之間的關聯
- 有關術語：關聯規則
- 算法：Apriori 算法
簡介,關聯規則的分類,算法,
簡介
關聯規則學習作為數據挖掘的重要研究方向之一，關聯規則學習挖掘的目的是從事務數據集中分析數據項之間潛在的關聯關係，揭示其中蘊含的對於用戶有價值的模式。一般認為，關聯規則挖掘主要由兩個步驟組成：(1)從事務數據集中挖掘所有支持度不小於最小支持度閾值的頻繁項集；(2)從上一步結果中生成滿足最小置信度閾值要求的關聯規則。其中，由於具有指數級別的時間複雜度，頻繁項集挖掘所消耗的時間往往超過用戶可以接受的程度。例如，從銷售數據中發現的規則 {洋蔥, 土豆}→{漢堡} 會表明如果顧客一起買洋蔥和土豆，他們也有可能買漢堡的肉。此類信息可以作為做出促銷定價或產品植入等行銷活動決定的根據。除了上面購物籃分析中的例子以外， 關聯規則如今還被用在許多套用領域中，包括網路用法挖掘、入侵檢測、連續生產及生物信息學中。與序列挖掘相比，關聯規則學習通常不考慮在事務中、或事務間的項目的順序。
關聯規則的分類
基於規則中處理的變數類別
關聯規則分為布爾型和多值屬性型。布爾型關聯規則處理的是離散、種類化的數據，它研究項是否在事務中出現; 多值屬性關聯規則又可分為數量屬性和分類屬性，它顯示了量化的項或屬性之間的關係。在挖掘多值屬性關聯規則時，通常將連續屬性運用離散( 等深度桶、部分 K 度完全法) 、統計學方法劃分為有限個區間，每個區間對應一個屬性，分類屬性的每個類別對應一個屬性，再對轉換後的屬性運用布爾型關聯規則算法進行挖掘。
基於規則中數據的抽象層次
關聯規則分為單層和多層。實際套用中，數據項之間有價值的關聯規則常出現較高的概念層中，因此，挖掘多層次關聯規則比單層關聯規則能得到更深入的知識。根據規則中對應項目的粒度層次，多層關聯規則可以劃分為同層和層間關聯規則。多層關聯規則挖掘的兩種設定支持度的策略為統一的最小支持度和不同層次設定不同的最小支持度。前者相對而言容易生成規則，但未考慮到各個層次的精度，容易造成信息丟失和信息冗餘問題，後者增加了挖掘的靈活性。
基於規則中數據的維數
關聯規則分為單維和多維。單維關聯規則處理的對象只是一維的; 多維關聯規則處理的則是兩個或兩個以上的變數。根據同一維在規則中是否重複出現，多維關聯規則又可分為維內關聯規則和混合關聯規則。
算法
先驗算法
在計算機科學以及數據挖掘領域中， 先驗算法（Apriori Algorithm）是關聯規則學習的經典算法之一。先驗算法的設計目的是為了處理包含交易信息內容的資料庫（例如,顧客購買的商品清單，或者網頁常訪清單。）而其他的算法則是設計用來尋找無交易信息（如Winepi算法和Minepi算法）或無時間標記（如DNA測序）的數據之間的聯繫規則。在關聯式規則中,一般對於給定的項目集合（例如，零售交易集合，每個集合都列出的單個商品的購買信息），算法通常嘗試在項目集合中找出至少有C個相同的子集。先驗算法採用自底向上的處理方法，即頻繁子集每次只擴展一個對象（該步驟被稱為候選集產生），並且候選集由數據進行檢驗。當不再產生匹配條件的擴展對象時，算法終止。
先驗算法採用廣度優先搜尋算法進行搜尋並採用樹結構來對候選項目集進行高效計數。它通過長度為 k-1的候選項目集來產生長度為 k的候選項目集，然後從中刪除包含不常見子模式的候選項。根據向下封閉性引理,該候選項目集包含所有長度為k的頻繁項目集。之後，就可以通過掃描交易資料庫來決定候選項目集中的頻繁項目集。
雖然先驗算法具有顯著的歷史地位，但是其中的一些低效與權衡弊端也進而引致了許多其他的算法的產生。候選集產生過程生成了大量的子集（先驗算法在每次對資料庫進行掃描之前總是嘗試載入儘可能多的候選集）。
FP-Growth算法
FP-Growth算法採用分而治之的思想，遞歸地將事務數據集劃分為多個更小的條件事務數據集來挖掘頻繁項集。同時，採用FP-Tree來表示事務數據集，FP-Tree是一種前綴樹的變形，具有較高的壓縮性能。FP-Growth算法在執行過程中只需要兩次遍歷事務數據集，並且不產生候選項集，從而在性能上比Apriori算法快了一個數量級。FP增長算法的運行性能依賴於數據集的壓縮因子。如果生成的條件FP樹非常茂盛，則算法的性能顯著下降，因為算法必須產生大量的子問題，並且需要合併每個子問題返回的結果。在FP-Growth算法挖掘頻繁項集的過程中，每一次遞歸都需要兩次遍歷FP-Tree。第一次是通過遍歷FP-Tree生成條件事務數據集，第二次是根據條件事務數據集建立條件FP-Tree。儘管採用FP-Tree來表示事務數據集具有較高的壓縮性能，但是，當FP-Tree所包含的節點數量較多時，遍歷FP-Tree所需的時間明顯增加。採用FP-Array技術後，每一次遞歸可以只需要一次遍歷，進一步提高了FP-Growth算法的性能。
基於圖的關聯規則挖掘
圖挖掘是指將關聯分析用於基於圖的數據，在圖的集合中發現一組公共子結構，即頻繁子圖挖掘。根據挖掘的搜尋路徑頻繁子圖挖掘算法分為BFS廣度優先搜尋( broad first search)和DFS 深度優先搜尋( depth first search) 兩類。基於廣度優先搜尋算法包括 AGM、FSG。AGM算法基於 Apriori 思想以頻繁頂點作為初始集，採用遞歸方法逐步增加節點來挖掘所有頻繁子圖。FSG 在 AGM 算法基礎上作出了改進，以擴展邊代替增加頂點生成候選子圖模式，最佳化了候選子圖剪枝策略，提高了計算支持度的速度。針對基於 Apriori 思想的算法產生大量候選子圖的缺點，出現了基於 FP-growth 的頻繁子圖挖掘算法Span、FFSM、close Graph。Yan 等人首次提出了基於深度優先搜尋算法Span，算法中對最小 DFS 編碼作標記並對其進行最右路擴展，避免複製圖的產生以減少冗餘。
