關聯規則的ECLAT算法

摘 要：關聯規則挖掘是數據挖掘的一個重要應用，而頻繁項集挖掘對關聯規則挖掘的效果起了決定性的作用。經典的頻繁項集挖掘主要有Apriori算法和FP-Growth算法，它們都是基于水平數據表示的算法，本文分析基于垂直數據表示的ECLAT算法。

關鍵詞：聯規；頻繁項集；Apriori算法；FP-Growth算法；ECLAT算法

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1674-7712 （2014） 16-0000-02

關聯規則是數據挖掘研究的主要模式之一，它能確定數據集中不同域或屬性之間的聯系，從這種聯系中找出有價值的多個域之間的依賴關系，如果兩項或多項屬性之間存在關聯，那么其中一項的屬性值就可以依據其他屬性值進行預測。

在關聯規則挖掘的過程中，頻繁項集挖掘起著重要的作用，而經典的頻繁項集挖掘算法，如Apriori算法和FP-Growth算法都是把數據庫看成水平數據表示，在這個基礎上進行的挖掘，而ECLAT算法是從不同的角度進行頻繁項集挖掘，它把數據庫看成垂直數據表示，只需要掃描數據庫一次就能計算項集的支持度計算，降低了算法掃描數據庫的次數。

本文主要分析經典的頻繁項集挖掘算法以及ECLAT算法，并探討各個算法的優劣。

一、關聯規則的基本概念

關聯規則的挖掘是分兩步來實現的，首先按照用戶給定的最低閾值，找出數據集中的所有頻繁項目集，然后從頻繁項目集中構造規則，要求構造的規則的可信度大于等于用戶設定的最低值。

支持度是對關聯規則代表的重要性進行度量的指標，它體現了關聯規則的頻度。如果某個項集的支持度的值太小，則表明相應的規則很可能只是偶然發生的。頻繁項集挖掘就是要在事務數據庫里找出所有大于給定的最小支持度的頻繁項集。頻繁閉項集是一組事務都包含的項的最大項集。頻繁閉項集和頻繁項集的信息量相等，但是頻繁閉項集比頻繁項集的元素少很多，因此挖掘頻繁閉項集能夠滿足用戶的需求并且對減少了算法的開銷，提升了頻繁項集挖掘的效率，同時還減少了冗余信息的輸出。最大頻繁項集是指那些在所有的頻繁項集中不存在超集的頻繁項集。如果一個頻繁項集不是其它任何頻繁項集的真子項集，那么稱此頻繁項集為最大頻繁項集。由于最大頻繁項集的個數遠遠小于頻繁閉項集，更遠遠小于完全頻繁項集，所以挖掘最大頻繁項集可以有效縮小問題解的規模，給稠密集中的長頻繁模式挖掘提供了新的解決方案。

二、關聯規則的經典算法

關聯規則的經典算法主要有Apriori算法和FP-Growth算法，它們都是基于水平數據表示的頻繁項集挖掘算法。其中，Apriori算法是一種寬度優先算法，而FP-Growth算法是一種深度優先算法。

Apriori算法是需要多次掃描數據庫，算法主要由連接和剪枝兩個步驟組成。首先通過連接操作生成候選集Ck，再通過剪枝操作刪除候選集中不可能成為頻繁項集的元素。算法的具體思路是，先掃描數據庫，計算數據庫中每個項目的支持度計數，根據用戶給定的最小支持度，把符合要求的項目放入一維頻繁項集，，再次掃描數據集，生成二維頻繁項集，依次重復這個步驟直到掃描結束為止。在掃描過程中進行剪枝，當第k次掃描時，先對k-1維頻繁項集中的項目集進行連接操作，生成k維項集的候選集，再利用Apriori性質對其進行剪枝，刪除其中不可能是頻繁項集的候選項，再計算其中每個候選的支持度計數，把不小于最小支持度計數的項集組成頻繁項集，重復上述步驟，直到無頻繁項集生成為止，最后的頻繁項集的集合為所有的并集。

Apriori算法在挖掘頻繁項集過程中完成剪枝操作，盡可能不生成和不計算那些不可能是頻繁項集的候選項集，但是該算法需要多次掃描數據庫，在計算頻繁項集的過程中可能生成的候選項集也較多，使算法的效率急劇下降。

針對Apriori算法的問題，提出了深度優先的FP-Growth算法，它將原始數據集中的相關重要信息壓縮在一個新的數據結構中，不需要像寬度優先挖掘算法那樣多次遍歷數據集，只需要兩次遍歷數據集就能發現頻繁項集。在FP-Growth算法中，把數據集中的重要信息壓縮在一個稱為頻繁模式樹的數據結構中，在頻繁模式樹中的每一個結點都保存了相應的項或項集以及支持該項或項集的事務列表等信息。該算法首先掃描數據集，構造頻繁模式樹把每個項集的信息存儲在頻繁模式樹中，然后使用FP-Growth來挖掘頻繁模式樹中的所有頻繁項集。

FP-Growth算法將頻繁項集的挖掘問題轉換成遞歸挖掘短頻繁項集的問題，對于挖掘出的短頻繁項集進行連接后綴。這種方法大大降低了對數據集的搜索量，但是當頻繁模式樹過于龐大時，算法的效率會明顯降低。

三、關聯規則的ECLAT算法

不同與經典的關聯規則挖掘算法，ECLAT算法是采用垂直數據表示的頻繁項集挖掘算法，在該算法中，首次提出垂直數據表示的概念，用垂直數據表示可以大大減少掃描數據集的次數，以概念格理論為基礎，采用深度優先搜索策略，采用前綴等價關系劃分搜索空間。ECLAT算法對數據集只需要掃描一次，使用數據垂直表示形式，通過交叉計數來計算支持度，在實際應用中有較好的效果，是一種性能較好的頻繁項集挖掘算法。

ECLAT算法采用的垂直數據表示是一種稱為Tidset的數據庫結構。對于數據集中的事務，對任意一個項目X，把所有包含項目X的所有事務的事務id放入一個集合，稱這個集合為項目X的Tidset。數據庫中的所有事務不再按照事務Id進行排列，而是按照每一個項目X來排列，每一條記錄由一個項目及其所出現過的所有事務記錄的列表構成。也就是說，垂直數據表示就是把事務用項目和該項目所屬的Tidset構成，該事務由項目Id唯一標識，這樣使得任何一個頻繁項集的支持度計數都可以通過對Tidset交集運算求得。

ECLAT算法采用自下而上的深度優先搜索策略，把數據集中的等價類進行分解，即把較大的等價類分成較小的等價類，通過枚舉每一個等價類中所有原子項的交集來逐層求出所有的等價類，其中，每一個等價類都是由一些原子項組成的。ECLAT算法采用基于前綴的分類，即任意一個項目X的等價類[X]就表示所有前綴為X的項集構成的子概念格。在將等價類[X]劃分為多個較小的子概念格后，采用與分類時相反的順序來處理這些等價類，這樣做的目的是為了使所有的子集信息都可以參與剪枝操作，減少搜索量。

和采用基于水平數據表示的Apriori算法以及FP-Growth算法不同的是，ECLAT算法中，對于候選集的生成過程和對其支持度的計算過程不是分開的兩個步驟，這兩個內容是同時進行的。在對數據集進行第一次掃描時，算法就會得到所有項目的Tidset和項目的支持度計算。也就是說，支持度計數的計算是在候選集生成的同時完成的。該算法通過對兩個集合求并集來產生新的候選集，再通過計算這兩個項集的Tidset的交集，能迅速地得到候選集的支持度計數。若得到的候選集的支持度計數小于給定的最小支持度計數，就自動刪除該候選項，若候選集的支持度計算大于給定的最小支持度計算，則保留該候選項。

ECLAT算法采用了新的視角來解決頻繁項集挖掘問題，它僅掃描數據集一次，大大的節省了對搜索空間的搜尋時間，同時也為解決頻繁項集挖掘提供了新的思路。但是該算法還是存在著一些不足，首先，它沒能利用Apriori先驗性質來進行剪枝，即任何頻繁項集的子集也一定是頻繁項集，而任何非頻繁項集的超集也一定是非頻繁項集。其次，由兩個集合的并集產生新的候選集，即候選集是由兩個集合的并集產生的，而每個項集都會用Tidset形式表示，通過計算這兩個項集的Tidset的交集快速得到候選集的支持度，并自動刪除那些支持度小于給定最小支持度計數的候選項集，導致算法的大量操作消耗在Tidset的求交集過程上。最后，當Tidset的規模較大時，會出現另外兩個問題。一是對Tidset求交集的操作會消耗大量時間，影響了算法的效率。二是對Tidset的交集操作所使用的數據表示形式會占用大量的內存空間，尤其是當Tidset的規模龐大時，會消耗大量的系統內存。

四、結束語

關聯規則挖掘是數據挖掘的一個重要的研究領域，在各個領域尤其是商業銷售方面有極其廣泛及重要的應用。快速的挖掘頻繁項集能提高關聯規則挖掘的效率，基于垂直數據表示的ECLAT算法能減少掃描數據庫的次數，提高頻繁項集挖掘算法的性能。

參考文獻：

[1]吳學雁，莫贊.基于Aproiri算法的頻繁項集挖掘優化方法[J].計算機系統應用，2014（06）：124-129.

[2]付沙，周航軍.關聯規則挖掘Aproiri算法的研究與改進[J].微電子學與計算機，2013（09）：110-114.

[3]胡中棟，羅會蘭，曾珽.基于FP-Tree的共享前綴頻繁項集挖掘算法[J].計算機工程與應用，2009（27）：137-140.

[4]陳培恩.關聯規則算法ECLAT改進研究[D].重慶大學，2010.

[5]耿曉斐.關聯規則中ECLAT算法的研究與應用[D].重慶大學，2009.

[作者簡介]陳鳳娟（1979.10—），女，本科，碩士，教師，副教授，研究方向：數據挖掘。