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

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

　　現(xiàn)如今，通過(guò)使用數(shù)據(jù)挖掘技術(shù)，我們可以從海量數(shù)據(jù)中挖掘有趣的信息。其中，關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘技術(shù)中較為重要的一種手段。它一般分為兩個(gè)步驟：一是依據(jù)事先設(shè)定的支持度閾值找出所有符合條件的頻繁項(xiàng)集；二是依據(jù)頻繁項(xiàng)集及給定的置信度閾值產(chǎn)生關(guān)聯(lián)規(guī)則。其中，挖掘算法的性能主要取決于頻繁項(xiàng)集的生成，因此識(shí)別或發(fā)現(xiàn)所有頻繁項(xiàng)目集是關(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 算法使用一種稱為逐層搜索的迭代方法，通過(guò)項(xiàng)目集元素?cái)?shù)目的不斷增長(zhǎng)來(lái)逐步完成頻繁項(xiàng)集的發(fā)現(xiàn)，核心思想是通過(guò)候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來(lái)挖掘頻繁項(xiàng)集，該算法設(shè)計(jì)思想簡(jiǎn)單，易于實(shí)現(xiàn)，但是產(chǎn)生了大量候選集，同時(shí)需要多次對(duì)事務(wù)庫(kù)進(jìn)行掃描，計(jì)算耗時(shí)過(guò)長(zhǎng)；FP-growth 算法使用一種稱為頻繁模式增長(zhǎng)的方法，采取分治策略，將代表頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵頻繁模式樹(shù)（FP 樹(shù)）上，然后把這種壓縮后的數(shù)據(jù)庫(kù)劃分成條件數(shù)據(jù)庫(kù)，每個(gè)數(shù)據(jù)庫(kù)關(guān)聯(lián)一個(gè)頻繁項(xiàng)或“模式段”，并分別挖掘每個(gè)條件數(shù)據(jù)庫(kù)，這種方法可以顯著地壓縮被搜索的數(shù)據(jù)集的大小，該算法只掃描事務(wù)庫(kù)兩次，且無(wú)需產(chǎn)生候選集，相比Apriori 算法性能有顯著的提高，但由于所有項(xiàng)集都?jí)嚎s在一棵樹(shù)上，對(duì)內(nèi)存要求較高，且遞歸算法設(shè)計(jì)復(fù)雜；Eclat 算法［4］的核心思想是將水平數(shù)據(jù)庫(kù)轉(zhuǎn)換成垂直數(shù)據(jù)庫(kù)，然后將項(xiàng)集的TID_set 進(jìn)行交運(yùn)算來(lái)得到項(xiàng)集的支持度，該算法由于只掃描一次事務(wù)庫(kù)，且項(xiàng)集支持度是通過(guò)交運(yùn)算得到的，大大減少了計(jì)算時(shí)間，但Eclat 算法存在搜索空間大、連接操作頻繁、求交運(yùn)算耗時(shí)的問(wèn)題。

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