陳鳳娟

【摘要】頻繁項集的挖掘是數(shù)據(jù)挖掘中的一個基礎(chǔ)和核心問題，具有廣泛的應(yīng)用領(lǐng)域。而頻繁項集挖掘可分為完全頻繁項集挖掘、頻繁閉項集挖掘和最大頻繁項集挖掘三類，其中，最大頻繁項集的數(shù)目最少。頻繁項集的挖掘是一個搜索問題，剪枝優(yōu)化技術(shù)是提高頻繁項集挖掘效率的一個重要手段。對于最大頻繁項集的挖掘可以從寬度優(yōu)先和深度優(yōu)先兩個角度來考慮，而基于FP樹的深度優(yōu)先算法比寬度優(yōu)先算法掃描數(shù)據(jù)集的次數(shù)要少很多，因此，具有較好的性能。本文主要分析寬度優(yōu)先的最大頻繁項集挖掘算法和基于FP樹的深度優(yōu)先最大頻繁項集挖掘算法。

【關(guān)鍵詞】關(guān)聯(lián)規(guī)則;頻繁項集;最大頻繁項集;FP樹

1.引言

數(shù)據(jù)挖掘技術(shù)能從數(shù)據(jù)庫中智能地獲取有價值的知識和信息，是人工智能和數(shù)據(jù)庫等多個學(xué)科的重要研究內(nèi)容。數(shù)據(jù)挖掘發(fā)展到現(xiàn)在，出現(xiàn)了許多技術(shù)分支和研究方向。應(yīng)用不同的挖掘技術(shù)可以從數(shù)據(jù)庫中挖掘出不同類型的知識，根據(jù)挖掘出的知識不同的形式，可以把數(shù)據(jù)挖掘分為通用關(guān)聯(lián)規(guī)則挖掘、特征規(guī)則挖掘、分類挖掘、聚類挖掘、序列模式分析、時間序列分析、趨勢分析和偏差分析等類別。其中關(guān)聯(lián)規(guī)則挖掘及頻繁項集的挖掘是數(shù)據(jù)挖掘研究的核心內(nèi)容之一，頻繁項集的挖掘效果對數(shù)據(jù)挖掘算法的性能和效率有重要的作用。

關(guān)聯(lián)規(guī)則是數(shù)據(jù)中一種簡單規(guī)則，這些規(guī)則能反映出實際的需求，是大量數(shù)據(jù)中項集之間相關(guān)聯(lián)系。關(guān)聯(lián)規(guī)則的挖掘算法是無監(jiān)督學(xué)習(xí)的方法，其中，頻繁項集挖掘是關(guān)聯(lián)規(guī)則挖掘的第一步，也是關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵步驟，是影響數(shù)據(jù)挖掘效率的關(guān)鍵問題。

本文主要分析頻繁項集與最大頻繁項集的概念，然后分析關(guān)聯(lián)規(guī)則中的最大頻繁項集挖掘的常用算法，并探討算法的優(yōu)劣。

2.頻繁項集和最大頻繁項集

關(guān)聯(lián)規(guī)則挖掘的主要目的是確定數(shù)據(jù)集中不同屬性之間的聯(lián)系，從這種聯(lián)系中找出有價值的多個屬性之間的依賴關(guān)系，通過這種依賴關(guān)系給出決策支持。關(guān)聯(lián)規(guī)則的挖掘可以分成兩步來完成。第一步是按照用戶給定的最低閾值，識別出數(shù)據(jù)集中的所有頻繁項目集，第二步是從頻繁項目集中構(gòu)造規(guī)則，要求構(gòu)造的規(guī)則的可信度大于等于用戶設(shè)定的最低值。

設(shè)U={U1，U2，…，Un}為n個不同字符的集合，其中的字符稱為項或商品。任意一個集合XU稱為一個項集，若|X|=k，則稱X為k項集。事務(wù)（或交易）T是項的集合，且任意的TU，對應(yīng)每一個事務(wù)有唯一的標(biāo)識，記作TID。設(shè)A={T1，T2，…，Tn}，稱A為U上的交易集或者數(shù)據(jù)集，簡稱交易集或者數(shù)據(jù)集。如果XT，稱事務(wù)T包含X。對于一個項集X和一個交易集A，X在A中的支持度定義為X在A中的支持計數(shù)與A中總的交易個數(shù)之比，記作sup（X）。如果X的支持度大于某個給定的最小閾值，則稱X是頻繁的。

支持度是對關(guān)聯(lián)規(guī)則代表的重要性進(jìn)行度量的指標(biāo)，它體現(xiàn)了關(guān)聯(lián)規(guī)則的頻度。如果某個項集的支持度的值太小，則表明相應(yīng)的規(guī)則很可能只是偶然發(fā)生的。

給定數(shù)據(jù)集A、項集X和min_sup，且min_sup∈（0，l），sup＼（XY）= 為項集X在數(shù)據(jù)集A上的支持度，簡記為sup（X）。當(dāng)sup（X）≥min_sup時，項集X稱為A上的完全頻繁項集，簡稱為頻繁項集。頻繁項集挖掘就是要在事務(wù)數(shù)據(jù)庫里找出所有大于給定的最小支持度的頻繁項集。

數(shù)據(jù)集A上的頻繁閉項集定義為：若項集X滿足條件sup（X）≥min_sup且（YA∧XY→sup（Y）

項集X滿足條件sup（X）≥min_sup且（YA∧XY→sup（Y）

最大頻繁項集是指那些在所有的頻繁項集中不存在超集的頻繁項集。如果一個頻繁項集不是其它任何頻繁項集的真子項集，那么稱此頻繁項集為最大頻繁項集。由于最大頻繁項集的個數(shù)遠(yuǎn)遠(yuǎn)小于頻繁閉項集，更遠(yuǎn)遠(yuǎn)小于完全頻繁項集，所以挖掘最大頻繁項集可以有效縮小問題解的規(guī)模，給稠密集中的長頻繁模式挖掘提供了新的解決方案。

3.最大頻繁項集挖掘

如果X是一個頻繁項集，且X的任何一個超集都是非頻繁的，則X是最大頻繁項集。把所有的最大頻繁項集放入一個集合中，稱為最大頻繁項集的集合，即MFS（Maximum Frequent Sets）。如果X是最大頻繁項集，那么X的任何真子集都不是最大頻繁項集。從這個特性可知，在挖掘最大頻繁項集的過程中，最大頻繁項集所有的子集都可以不去挖掘，只需要挖掘最大頻繁項集就可以了，這樣能有效地縮短算法的運行時間，提高算法的運行效率。按遍歷搜索空間的策略，可以把最大頻繁項集挖掘算法分為寬度優(yōu)先搜索和深度優(yōu)先搜索兩類算法。

Pincer-search算法是典型的采用寬度優(yōu)先搜索策略的算法，它使用傳統(tǒng)的橫向數(shù)據(jù)集的表示方法，通過多次遍歷數(shù)據(jù)集來計算各個項集的支持度計數(shù)。該算法把自頂向下的搜索策略與由底向上的搜索策略結(jié)合起來，使用兩種策略同時對數(shù)據(jù)空間進(jìn)行搜索。其中，由底向上的搜索方法與Apriori算法的方法相似，先掃描數(shù)據(jù)集k次生成的k階頻繁項集，用k階頻繁項集來生成k+l階侯選項集，再掃描數(shù)據(jù)集，計算候選項集的支持度計數(shù)，并將候選項集分為k+1項頻繁項集和k+1項非頻繁項集。Pincer-search算法利用兩個不同方向搜索生成的非頻繁項集和最大頻繁項集相互剪枝，不斷重復(fù)剪枝動作，直到兩個不同方向的搜索過程發(fā)現(xiàn)的頻繁項集一致時為止。通過互相剪枝，可以迅速降低搜索空間，提高挖掘效率，但算法需要多次遍歷數(shù)據(jù)集，并計算項集的支持度，還會產(chǎn)生過多的無用的候選項集，對海量數(shù)據(jù)算法效率會急劇下降。

Max-Miner算法也是采用寬度優(yōu)先搜索策略，它利用子集剪枝策略對候選項集進(jìn)行剪枝，又利用超集剪枝策略對非最大頻繁項集進(jìn)行剪枝。Max-Miner提出的利用尾項集按項支持度從低到高的排序方法，不但提高了超集剪枝策略的效率，還被廣泛地應(yīng)用在其他的最大頻繁項集挖掘算法中。Max-Miner算法根據(jù)提出的搜索空間樹概念，盡可能早地對項目集進(jìn)行剪枝，有效地縮小了搜索空間。但是，由于Max-Miner算法也是橫向的寬度優(yōu)先策略，所以它也需要多次掃描數(shù)據(jù)集，降低了算法的效率。

4.基于FP樹的最大頻繁項集挖掘

FP-Max算法是一種基于FP-Tree的最大頻繁項集挖掘算法，它是一種使用深度優(yōu)先搜索策略的有效算法。FP-Max算法在深度優(yōu)先遍歷搜索空間樹時，對于數(shù)據(jù)集，建立其FP樹，對于每個結(jié)點，還保存該結(jié)點到根結(jié)點搜索路徑上的每一個結(jié)點對應(yīng)的FP子樹。這些FP子樹表示與相關(guān)結(jié)點挖掘有關(guān)的頻繁信息。在當(dāng)前結(jié)點上，通過在相應(yīng)項集之中添加對應(yīng)的FP子樹頭表中的某個項，來生成搜索空間中的子結(jié)點。

在構(gòu)建子結(jié)點的FP子樹之前做，先對其進(jìn)行超集是否存在的判斷，如果在已有最大頻繁項集的集合中，存在首尾項集并集的超集，則進(jìn)行前瞻剪枝;否則，創(chuàng)建子結(jié)點FP子樹，遞歸調(diào)用算法在該子結(jié)點上進(jìn)行挖掘，直至某個子孫結(jié)點的FP子樹是單路徑樹。當(dāng)某個節(jié)點的子FP樹為單一路徑樹時表明，該節(jié)點對應(yīng)項集與子FP樹的頭表項集的并集，為最大頻繁項集，將其加入最大頻繁項集樹中。最大頻繁項集樹是FP-Max算法用來壓縮保存已經(jīng)產(chǎn)生的最大頻繁項集的存儲結(jié)構(gòu)。它的結(jié)構(gòu)與FP樹的結(jié)構(gòu)一樣，都包含頭表和樹結(jié)構(gòu)，從某個葉節(jié)點到根節(jié)點的路徑代表一個最大頻繁項集。

FP-Max算法只需要在構(gòu)建FP樹時，對事務(wù)數(shù)據(jù)庫進(jìn)行兩次掃描，在挖掘過程中，該算法不會產(chǎn)生候選項集，但會產(chǎn)生一些候選最大頻繁項集。因此FP-Max算法在一定程度上減少了 I/O開銷，提高了算法的挖掘效率。但是FP-Max算法也有一些不足之處，首先，為了有效的進(jìn)行前瞻剪枝，該算法需要在最大頻繁項集樹中查詢超集，就需要將給定項集集合中每一個項集與被檢測項集做項匹配，使得超集存在判斷的開銷較大。其次，該算法會構(gòu)建大量的條件模式樹，在某些存在大量的長模式以及強(qiáng)模式的數(shù)據(jù)集中，構(gòu)建FP樹的工作量非常大，而節(jié)點鏈的復(fù)雜度將增加數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性。最后，F(xiàn)P-Max算法是基于雙向FP樹結(jié)構(gòu)的，就導(dǎo)致存儲FP樹需要其他單向FP樹的兩倍的存儲空間，因此，F(xiàn)P樹的存儲也會占用大量的內(nèi)存空間。

5.結(jié)束語

在關(guān)聯(lián)規(guī)則挖掘、序列模式挖掘、多層模式挖掘等數(shù)據(jù)挖掘問題中，挖掘頻繁項集既是基本步驟，也是關(guān)鍵步驟。最大頻繁項集比頻繁項集的數(shù)量少，在某些挖掘中，挖掘最大頻繁項集可以有更好的算法效率。最大頻繁項集挖掘算法按對搜索空間樹的遍歷策略可以分為兩種，分別是寬度優(yōu)先算法和深度優(yōu)先算法。Pincer-search算法和Max-Miner算法是寬度優(yōu)先算法，而FP-Max算法是基于FP樹的深度優(yōu)先算法，對這幾個算法的分析和研究對以后的最大頻繁項集挖掘算法的改進(jìn)有很大的幫助。

參考文獻(xiàn)

[1]李慶華，王卉等.挖掘最大頻繁項集的并行算法[J].計算機(jī)科學(xué)，2004，31（12）：132-134.

[2]吳振光.一個改進(jìn)的關(guān)聯(lián)規(guī)則的頻繁項目集數(shù)據(jù)挖掘算法[J].科學(xué)，2007，34（9）：145-147.

[3]陳晨，鞠時光.基于改進(jìn)FP-tree的最大頻繁項集挖掘算法[J].計算機(jī)工程與設(shè)計，2008，29（24）：6236-6239.

[4]王丹陽，田衛(wèi)東.一種有效的并行頻繁項集挖掘算法[J].計算機(jī)應(yīng)用研究，2008，25（11）：3332-3334.

[5]花紅娟，張健，陳少華.基于頻繁模式樹的約束最大頻繁項集挖掘算法[J].計算機(jī)工程，2011，37（9）：78-80.

[6]廖福榮，王成良.基于有序FP-tree的最大長度頻繁項集挖掘算法[J].計算機(jī)工程與應(yīng)用，2012，48（30）：147-150.

[7]劉芝怡，常睿.頻繁項集高效挖掘算法研究[J].微計算機(jī)信息，2012，28（10）：491-493.