陳鳳娟
【摘要】頻繁項(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.