基本介紹
- 中文名：單機挖掘算法
- 外文名：single-machinemining algorithms
- 領域：數據挖掘
- 定義：在一台機器上的頻繁項集挖掘算法
- 特點：數據量小
- 典型算法：Apriori 和 FP-growth
定義,頻繁項集挖掘算法,算法類型,DHP 算法,
定義
單機（single-machine）挖掘算法是指在單台機器運行的頻繁項集挖掘算法，這種算法對機器要求不大，對應數據量小。和其他頻繁項集挖掘算法一樣，單機（single-machine）挖掘算法主要分兩步來完成：第一步是找出資料庫中所有滿足最小支持度閾值的頻繁項集；第二步是由頻繁項集產生所有滿足最小置信度閾值的關聯規則。由於關聯規則挖掘的整體性能主要是由第一步的性能所決定，因此，關聯規則挖掘的關鍵和難點都集中在了頻繁項集的挖掘上。
頻繁項集挖掘算法
頻繁項集挖掘是數據挖掘研究課題中一個很重要的研究基礎，它可以告訴我們在數據集中經常一起出現的變數，為可能的決策提供一些支持。頻繁項集挖掘是關聯規則、相關性分析、因果關係、序列項集、局部周期性、情節片段等許多重要數據挖掘任務的基礎。因此，頻繁項集有著很廣泛的套用，例如：購物藍數據分析、網頁預取、交叉購物、個性化網站、網路入侵檢測等。
對頻繁項集挖掘算法進行研究的方向大概可歸納為以下四個方面：一、在遍歷方向上採取自底向上、自頂向下以及混合遍歷的方式；二、在搜尋策略上採取深度優和先寬度優先策略；三、在項集的產生上著眼於是否會產生候選項集；四、在資料庫的布局上，從垂直和水平兩個方向上考慮資料庫的布局。對於不同的遍歷方式，資料庫的搜尋策略和布局方式將會產生不同的方法，研究表明，沒有什麼挖掘算法能同時對所有的定義域和數據類型都優於其他的挖掘算法，也就是說，對於每一種相對較為優秀的算法，它都有它具體的適用場景和環境。所以，應該了解不同挖掘算法的不同特性和適用場景，掌握不同算法的適用環境和條件，這樣才可以使研究者清楚算法的改進點，明白自己的研究方向，從而使用戶更加方便地把算法套用到實際的生產活動中。
隨著大數據時代的到來，傳統的算法，比如 Apriori 算法、FP-growth 算法等，都無法處理這些處理大量的數據，主要原因有：一、時間消耗太大。面對大量數據，即使是比 Apriori快一個數量級的 FP-growth 算法，也無法在較短的時間內完成挖掘任務；二、記憶體無法滿足要求。由於 Apriori 算法（包括類 Apriori算法）需要產生大量的候選項集，所以在處理大量數據的時候，就會由於記憶體消耗殆盡而無法使算法繼續進行下去，即使是不需要生成候選項集的 FP-growth 算法，也會因為 FP-tree 太大無法放入記憶體，而使得算法無法運行。
面對這樣的問題，眾多的研究學者開始著眼研究基於多處理器系統的並行頻繁項集挖掘算法，以及基於 Hadoop 等分散式集群的分散式頻繁項集挖掘算法。比如 Agrawal 等人 CD 算法、DD 算法和 Ca D 算法，以及 Zaiane 等人的 MLFPT算法和 Li 等人的 PFP 算法等等，都是一些很優秀的並行或分散式頻繁項集挖掘算法。
頻繁項集挖掘是數據挖掘研究領域中的一個重要課題，它是關聯規則、因果關係、相關性分析、情節片段、序列項集、局部周期性等許多數據挖掘任務的基礎。所以，頻繁項集有著廣泛的實際套用，例如：購物藍數據分析、網頁預取、交叉購物、個性化網站以及網路入侵檢測等。
算法類型
Apriori
算法 1993 年，Agrawal 等人在文章《Mining Association Rules between Sets of Items in Large Databases》提出了一個挖掘布爾關聯規則的經典算法——Apriori 算法，該算法使用了一種分層的完備搜尋算法，即寬度優先搜尋。 首先，它通過掃面事務資料庫，得到頻繁 1-項集；然後，利用頻繁 1-項集產生候選的頻繁 2-項集，再一次掃描事務資料庫，從候選的頻繁2-項集中篩選出滿足最小支持度的 2-項集，得到頻繁 2-項集；接著又利用頻繁 2-項集產生候選的頻繁 3-項集……如此反覆進行下去，直到無法發現新的頻繁項集，算法結束。
Apriori 算法充分利用了項集的反單調性這一先驗知識：如果一個項集它是非頻繁的，那么它的所有超集也一定是非頻繁的，這個性質也被稱為向下閉合性。
DHP 算法
1995 年，J.S Park 等人在文章《An Effective Hash-Based Algorithm for Mining Association Rules》中提出了一種通過刪減不必要的候選項集來完善挖掘效率的算法——DHP 算法。DHP 以 Apriori 為基礎，並且引入一個 hash table 結構，根據統計學原理，將其轉化為非頻繁項集的刷選機制，以減少算法執行過程中不必要的項集數量，從而降低計算成本，提高挖掘效率。DHP 算法的執行步驟如下：
1、首先利用頻繁 1-項集建立候選頻繁 2-項集，並保存在 HASH 表中；
2、然後根據 HASH 表中的候選項集，從中篩選出頻繁項集，接著再利用頻繁項集縮減資料庫的大小；
3、在產生頻繁 2-項集之後，後面就可以按照經典的 Apriori 算法的步驟挖掘頻繁項集，直到無法產生更高層次的頻繁項集為止。
DHP 算法利用 hash table 來刪除不必要的候選 2-項集，雖然在開始的時候需要花時間來建立 hash table，但是它對後來頻繁項集的生成卻有很大的改善，總體說來，該方法在一定程度上改善了Apriori 算法。
DIC 算法
1997 年，Bring 等人在文章《Dynamic Itemset Counting and Implication Rules for Market Basket Data》中提出了 DIC（Dynamic Itemset Counting）算法。DIC 算法的整體思想為：在同一次的資料庫搜尋中，對 k 值不同的候選 k-項集計數。DIC算法將資料庫 D 分成N個大小均為 M 的子資料庫1D 進行搜尋。首先它搜尋1D 並計算 1-項集的支持度，然後用這些 1-項集產生候選的頻繁 2-項集；接著，算法搜尋2D並得到 1-項集和候選 2-項集，也就是當前有所的候選項集，計算它們的支持度，並用所得的 2-項集產生候選 3-項集。重複這一搜尋過程，直到nD 完成。在對資料庫D的第一次搜尋中，當算法搜尋到kD 的時候，DIC就開始計算候選 k-項集的支持度，當所有的子資料庫都處理過一次之後，IDC 重新開始第二次搜尋，當算法回到kD 搜尋時，就能夠算出 k-項集的全局支持度。DIC 算法一次又一次循環搜尋資料庫，直到kD 沒有新的候選項集出現，並且所有的候選項集的支持度都已經計算完成，此時算法結束。
1998 年，M.J Zaki 等人在文章《Scalable Data Mining for Rules》中提出了一種新的頻繁項集挖掘算法——Eclat 算法。Eclat 算法使用的是資料庫的一個垂直表示方式，並且使用了集合的交集運算方法來計算項集（itemset）的支持度計數。在計算候選項集的時候，它採用的是深度優先搜尋的方式來產生候選的頻繁項集，並且在頻繁 k-項集的基礎之上，通過合併頻繁 k-項集，產生以該頻繁 k-項集為前綴的候選頻繁(k+1)-項集。通過上面的方法，不斷地擴展該項集，直到該項集已經不能再進行擴展了為止，算法才結束。
FP-growth 算法
2000 年，Jiawei Han 等在文章《Mining Frequent Patterns without Candidate Generation》中提出了一種基於頻繁模式樹（Frequent Pattern tree，FP-tree）的頻繁項集挖掘算法——頻繁模式增長算法，簡稱 FP-growth。
算法的整體思路是這樣的：首先，通過資料庫的一次掃描，計算並得到頻繁1-項集，並對頻繁 1-項集按照支持度的遞減順序排序放在項頭表（header table）中；接著，第二次掃描資料庫，構建 FP-tree：對於資料庫中的每一條事務記錄T ，根據項頭表對T 中的項按遞減順序排序並刪除不在項頭表中的項，之後按照構造FP-tree 的方法將T 插入 FP-tree 中並更新項頭表的節點連結，當資料庫掃描完成之後，FP-tree 也同時建立好了；最後，在 FP-tree上進行頻繁項集挖掘：在項頭表（header table）中，從項頭表的下面往上開始，由長度為1 的頻繁模式（即頻繁 1-項集，初始的後綴模式）開始，構造它的條件模式基。這些條件模式基可以看成是一個子事務資料庫，它是由 FP-tree 中與後綴模式一起出現的前綴路徑集所組成。接著，算法開始構造這個初始後綴模式的條件 FP-tree，構造方式與構造 FP-tree的方式一樣，然後遞歸地在該條件 FP-tree 上實現挖掘，這個過程是一個遞歸挖掘的過程，模式的增長方式是通過將後綴模式與條件 FP-tree 產生的頻繁模式連線起來，從而實現模式的增長。
