陳鳳娟

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

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

1.引言

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

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

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

2.頻繁項(xiàng)集和最大頻繁項(xiàng)集

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

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

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

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

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

項(xiàng)集X滿足條件sup（X）≥min_sup且（YA∧XY→sup（Y）

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

3.最大頻繁項(xiàng)集挖掘

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

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

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

4.基于FP樹的最大頻繁項(xiàng)集挖掘

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

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

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

5.結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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

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

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