頻繁項集

頻繁項集挖掘是數據挖掘研究課題中一個很重要的研究基礎，它可以告訴我們在數據集中經常一起出現的變數，為可能的決策提供一些支持。頻繁項集挖掘是關聯規則、相關性分析、因果關係、序列項集、局部周期性、情節片段等許多重要數據挖掘任務的基礎。因此，頻繁項集有著很廣泛的應用，例如：購物籃數據分析、網頁預取、交叉購物、個性化網站、網路入侵檢測等。，對頻繁項集挖掘演演算法進行研究的方向大概可歸納為以下四個方面：一、在遍歷方向上採取自底向上、自頂向下以及混合遍歷的方式；二、在搜索策略上採取深度優先和寬度優先策略；三、在項集的產生上著眼於是否會產生候選項集；四、在資料庫的布局上，從垂直和水平兩個方向上考慮資料庫的布局。對於不同的遍歷方式，資料庫的搜索策略和布局方式將會產生不同的方法，研究表明，沒有什麼挖掘演演算法能同時對所有的定義域和數據類型都優於其他的挖掘演演算法，也就是說，對於每一種相對較為優秀的演演算法，它都有它具體的適用場景和環境。

項的集合稱為 項集。包含k個項的項集稱為k-項集。項集的出項頻率是包含項集的事務數，簡稱為項集的 頻率，支持度計數或 計數。注意，定義項集的支持度有時稱為 相對支持度，而出現的頻率稱為 絕對支持度。如果項集 I的相對支持度滿足預定義的最小支持度閾值，則 I是 頻繁項集

置信度，是指某個關聯規則的概率，可以用P(B|A)表示。

關聯規則，表示的是在某個頻繁項集的條件下推出另一個頻繁項集的概率。如果該關聯規則的置信度大於等於最小置信度，則為強關聯規則。

閉頻繁項集（closed frequent itemset）：當項集X是頻繁項集，且數據集D中不存在X的真超集Y，使得X和Y的支持度相等，則X是閉頻繁項集。閉頻繁項集的表示是無損壓縮，不會丟失支持度的信息。通過閉頻繁項集可以反推出所有的頻繁項集以及相應的支持度。

極大頻繁項集（maximal frequent itemset）：當項集X是頻繁項集，且數據集D中不存在X的真超集Y，使得Y是頻繁項集，則X是極大頻繁項集。極大頻繁項集的表示是有損壓縮，失去了頻繁項集的支持度信息，我們可以根據極大頻繁項集判斷任意項集是否是頻繁的，但無法得到相應的支持度。

最大規則對象數：規則中對象組所包含的最大對象數量。

最小支持：規則中對象或是對象組必頇匹配的最低案例數。

最小信心水準：計算規則所必須匹配的最低信心水準門檻。

關聯規則學習（Association rule learning）是一種在大型資料庫中發現變數之間的有趣性關係的方法。它的目的是利用一些有趣性的量度來識別資料庫中發現的強規則。基於強規則的概念，Rakesh Agrawal等人引入了關聯規則以發現由超市的POS系統記錄的大批交易數據中產品之間的規律性。例如，從銷售數據中發現的規則 {洋蔥, 土豆}→{漢堡} 會表明如果顧客一起買洋蔥和土豆，他們也有可能買漢堡的肉。此類信息可以作為做出促銷定價或產品植入等營銷活動決定的根據。除了上面購物籃分析中的例子以外，關聯規則如今還被用在許多應用領域中，包括網路用法挖掘、入侵檢測、連續生產及生物信息學中。與序列挖掘相比，關聯規則學習通常不考慮在事務中、或事務間的項目的順序。

關聯規則挖掘的整個過程主要分兩步來完成：第一步是找出資料庫中所有滿足最小支持度閾值的頻繁項集；第二步是由頻繁項集產生所有滿足最小置信度閾值的關聯規則。由於關聯規則挖掘的整體性能主要是由第一步的性能所決定，因此，關聯規則挖掘的關鍵和難點都集中在了頻繁項集的挖掘上。隨著關聯分析技術的不斷發展，眾多的研究學者提出了許多優秀的頻繁項集挖掘演演算法，包括單機（single-machine）挖掘演演算法、基於MPI（Message Passing Interface）的挖掘演演算法、基於 Map Reduce 的挖掘演演算法和基於Spark 的挖掘演演算法。單機（single-machine）挖掘演演算法指的是運行在一台機器上的頻繁項集挖掘演演算法，它們的特點是數據量小，對機器的內存大小和計算性能要求不高，在一台機器上即可完成挖掘任務。一些經典的演演算法，如 Apriori和 FP-growth 等經典的頻繁項集挖掘演演算法，都是單機頻繁項集挖掘演演算法。MPI 的全稱是Message Passing Interface，它是一種消息傳遞標準，同時也是一項被廣泛採用的并行編程技術。基於MPI的頻繁項集挖掘演演算法都是一些并行演演算法，它們的特點是各個計算節點并行地挖掘頻繁項集，因此演演算法的效率很高。但是它們也有很多的缺點，比如：沒有容錯能力、節點之間需要進行大量的通信等等，這些缺點嚴重影響了演演算法的性能。

Spark 是一個基於內存計算的通用大數據處理引擎，用於大量數據的迭代計算。所以，需要進行迭代計算的頻繁項集挖掘演演算法，如Apriori演演算法，非常適合基Spark來設計和實現。因此，基於Spark的頻繁項集挖掘演演算法，都是Apriori 演演算法的改進演演算法。它們的優點是挖掘效率很高，並且容錯能力強。但是，它們需要產生大量的候選項集，且各節點之間需要進行大量的通信。

Map Reduce是Hadoop下的一種編程模型，用於大量數據的分散式批處理。基於Map Reduce的頻繁項集挖掘演演算法效率很高，但是磁碟I/O開銷大，且節點之間的通信負載高，集群的負載均衡較難把握。