如何使用剪枝優(yōu)化與索引求交改進(jìn)Eclat算法

　　針對現(xiàn)有Eclat算法中普遍存在的候選集規(guī)模大、求交效率低的問題，提出了基于剪枝優(yōu)化和索引求交的改進(jìn)Eclat算法。首先根據(jù)頻繁集的性質(zhì)采用預(yù)剪枝和后剪枝相結(jié)合的候選集優(yōu)化策略，即利用預(yù)剪枝技術(shù)裁剪待連接的項集數(shù)量以減少項集連接操作，同時利用先驗性質(zhì)對連接后的項集進(jìn)行后剪枝處理；接著提出了一種基于事務(wù)索引的布爾數(shù)組求交方法，即通過將事務(wù)標(biāo)識作為索引來設(shè)置并檢索布爾數(shù)組，以獲得項集支持度計數(shù)；最后通過設(shè)計對比實驗，在經(jīng)典數(shù)據(jù)集上測試該方法的有效性。實驗表明，通過該方法能夠有效壓縮候選集規(guī)模，改善求交計算效率，特別是在支持度閾值小、事務(wù)數(shù)規(guī)模大的情況下，算法的運(yùn)行效率得到了明顯的提升。

　　現(xiàn)如今，通過使用數(shù)據(jù)挖掘技術(shù)，我們可以從海量數(shù)據(jù)中挖掘有趣的信息。其中，關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘技術(shù)中較為重要的一種手段。它一般分為兩個步驟：一是依據(jù)事先設(shè)定的支持度閾值找出所有符合條件的頻繁項集；二是依據(jù)頻繁項集及給定的置信度閾值產(chǎn)生關(guān)聯(lián)規(guī)則。其中，挖掘算法的性能主要取決于頻繁項集的生成，因此識別或發(fā)現(xiàn)所有頻繁項目集是關(guān)聯(lián)規(guī)則挖掘算法的核心。隨著數(shù)據(jù)挖掘技術(shù)理論研究的深入，各類關(guān)聯(lián)規(guī)則挖掘算法也在不斷地涌現(xiàn)。傳統(tǒng)的算法主要包括Apriori算法、FP-growth 算法以及Eclat 算法，后續(xù)的大部分算法都是在這三類算法的基礎(chǔ)上進(jìn)行相應(yīng)的優(yōu)化和改進(jìn)。

　　Apriori 算法使用一種稱為逐層搜索的迭代方法，通過項目集元素數(shù)目的不斷增長來逐步完成頻繁項集的發(fā)現(xiàn)，核心思想是通過候選集生成和情節(jié)的向下封閉檢測兩個階段來挖掘頻繁項集，該算法設(shè)計思想簡單，易于實現(xiàn)，但是產(chǎn)生了大量候選集，同時需要多次對事務(wù)庫進(jìn)行掃描，計算耗時過長；FP-growth 算法使用一種稱為頻繁模式增長的方法，采取分治策略，將代表頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（FP 樹）上，然后把這種壓縮后的數(shù)據(jù)庫劃分成條件數(shù)據(jù)庫，每個數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項或“模式段”，并分別挖掘每個條件數(shù)據(jù)庫，這種方法可以顯著地壓縮被搜索的數(shù)據(jù)集的大小，該算法只掃描事務(wù)庫兩次，且無需產(chǎn)生候選集，相比Apriori 算法性能有顯著的提高，但由于所有項集都壓縮在一棵樹上，對內(nèi)存要求較高，且遞歸算法設(shè)計復(fù)雜；Eclat 算法［4］的核心思想是將水平數(shù)據(jù)庫轉(zhuǎn)換成垂直數(shù)據(jù)庫，然后將項集的TID_set 進(jìn)行交運(yùn)算來得到項集的支持度，該算法由于只掃描一次事務(wù)庫，且項集支持度是通過交運(yùn)算得到的，大大減少了計算時間，但Eclat 算法存在搜索空間大、連接操作頻繁、求交運(yùn)算耗時的問題。

　　本文選取上述幾類算法中性能較好的Eclat 算法，結(jié)合近年來該算法的相關(guān)研究，針對其普遍存在的問題和不足，從候選集的生成和支持度的計算兩個方面對其加以優(yōu)化和改進(jìn)，提出了前后剪枝相結(jié)合的候選集優(yōu)化策略以及利用數(shù)組索引取值計數(shù)的求交運(yùn)算方法，以達(dá)到提高Eclat 算法效率的目的。