基于索引數(shù)組的頻繁項(xiàng)集挖掘算法

(燕山大學(xué) 信息科學(xué)與工程學(xué)院 計(jì)算機(jī)應(yīng)用技術(shù)， 河北 秦皇島 066004)



摘 要：基于現(xiàn)有的關(guān)聯(lián)規(guī)則挖掘算法，提出了一種通過循環(huán)迭代增加項(xiàng)為項(xiàng)集后綴的方式產(chǎn)生所有項(xiàng)集的新方法，構(gòu)造了一種新的數(shù)據(jù)結(jié)構(gòu)—索引數(shù)組，存儲(chǔ)所發(fā)現(xiàn)的頻繁1項(xiàng)集及其相關(guān)信息，以便快速發(fā)現(xiàn)項(xiàng)集與事務(wù)之間的關(guān)系；并提出了一種基于索引數(shù)組的頻繁項(xiàng)集挖掘新算法。該算法只需掃描數(shù)據(jù)庫(kù)兩次就能發(fā)現(xiàn)所有頻繁項(xiàng)集。實(shí)驗(yàn)結(jié)果表明，該算法可以有效提高頻繁項(xiàng)集的挖掘效率。

關(guān)鍵詞：數(shù)據(jù)挖掘； 關(guān)聯(lián)規(guī)則； 頻繁項(xiàng)集； 索引數(shù)組

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2009)01004403



Frequent itemsets mining algorithm based on index array

ZHANG Zhongping， LI Yan， LIN Zhijie， WANG Aijie



(Dept. of Computer Application Technology， College of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China)



Abstract:The paper presented a new approach of increasing item to suffix of itemset recursively according to the classical association rule mining algorithms. And used a new data structure—index array to store frequent 1itemset and its correlative information. So the relations of itemsets and transactions were found quickly. Presented a frequent itemsets mining algorithm based on index array and could mine all frequent itemsets through scanning database only twice. The experimental results show that the proposed algorithm outperforms similar stateoftheart algorithms.

Key words：data mining; association rule; frequent itemsets; index array



0 引言

數(shù)據(jù)庫(kù)技術(shù)的廣泛應(yīng)用產(chǎn)生了大量的業(yè)務(wù)數(shù)據(jù)。隨著數(shù)據(jù)在日常決策中的重要性越來越顯著，人們對(duì)數(shù)據(jù)處理技術(shù)的要求也不斷提高，需要對(duì)數(shù)據(jù)進(jìn)行更深層次的處理，以便于對(duì)事物發(fā)展趨勢(shì)的預(yù)測(cè)。因?yàn)閿?shù)據(jù)的爆炸性增長(zhǎng)，難以發(fā)現(xiàn)數(shù)據(jù)的全面信息，客觀上需要一種新的技術(shù)來分析海量的原始數(shù)據(jù)，這樣，數(shù)據(jù)挖掘技術(shù)就應(yīng)運(yùn)而生了。

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域的重要研究方向之一，屬于描述性挖掘，它的目的就是挖掘出隱藏在數(shù)據(jù)間的相互關(guān)系，即從數(shù)據(jù)中挖掘出滿足一定條件的依賴性關(guān)系。1993年Agrawal等人[1]提出了Apriori關(guān)聯(lián)規(guī)則挖掘算法，算法主要分為兩步：a)挖掘頻繁項(xiàng)集，使用逐層搜索的迭代方式從大量候選項(xiàng)集中產(chǎn)生頻繁項(xiàng)集，即支持度大于等于用戶預(yù)先給定的最小支持度的項(xiàng)集；b)從a)步產(chǎn)生的頻繁項(xiàng)集中挖掘強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘的核心問題是如何有效地挖掘頻繁項(xiàng)集。2000年，Han Jiawei等人[2]提出了不產(chǎn)生候選項(xiàng)集的FPgrowth算法，該算法采用將事務(wù)數(shù)據(jù)庫(kù)壓縮到頻繁模式樹(FPtree)的策略，將壓縮后的數(shù)據(jù)庫(kù)分成一組條件數(shù)據(jù)庫(kù)，每個(gè)關(guān)聯(lián)一個(gè)頻繁項(xiàng)并分別挖掘每個(gè)數(shù)據(jù)庫(kù)，從而發(fā)現(xiàn)頻繁項(xiàng)集。文獻(xiàn)[3]提出了Eclat算法，該算法采用數(shù)據(jù)的垂直表示格式，優(yōu)點(diǎn)是不僅利用了Apriori性質(zhì)從頻繁k項(xiàng)集產(chǎn)生候選(k+1)項(xiàng)集，而不用掃描事務(wù)數(shù)據(jù)庫(kù)就能得到(k+1)項(xiàng)集的支持度，并利用了類似FPgrowth的深度優(yōu)先的計(jì)算順序；缺點(diǎn)是要多次執(zhí)行交集操作才能得到項(xiàng)集的支持度。目前大多數(shù)算法都是圍繞這三個(gè)算法改進(jìn)，有的是從數(shù)據(jù)結(jié)構(gòu)上改進(jìn)，如基于矩陣的頻繁項(xiàng)集挖掘算法[4]、基于數(shù)組的頻繁項(xiàng)集挖掘算法[5]、基于十字鏈表的頻繁項(xiàng)集挖掘算法[6]等；有的是根據(jù)頻繁項(xiàng)集的特性改進(jìn)[7]。

為減少頻繁項(xiàng)集產(chǎn)生的數(shù)量，近年來國(guó)內(nèi)外研究人員深入研究了壓縮或近似的頻繁模式挖掘算法[8，9]，不管是壓縮的頻繁模式還是近似的頻繁模式，都是頻繁模式的一部分，屬于頻繁模式完全集的子集。當(dāng)不需要產(chǎn)生所有頻繁項(xiàng)集時(shí)，這種方法十分有效，但是有損壓縮會(huì)丟失支持度信息，從而無法產(chǎn)生關(guān)聯(lián)規(guī)則。

為此，本文針對(duì)頻繁項(xiàng)集的完全集進(jìn)行了深入研究，應(yīng)用集合論和索引理論提出了一種基于索引數(shù)組的頻繁項(xiàng)集挖掘算法(frequent itemsets mining based on index array，F(xiàn)IMBIA)。該算法只需掃描數(shù)據(jù)庫(kù)兩次，利用索引數(shù)組存儲(chǔ)發(fā)現(xiàn)的所有頻繁1項(xiàng)集及其相關(guān)信息，由頻繁1項(xiàng)集構(gòu)成的所有項(xiàng)集按照一定的規(guī)則排列；然后根據(jù)索引數(shù)組中的內(nèi)容對(duì)滿足條件的項(xiàng)集進(jìn)行累加操作以實(shí)現(xiàn)對(duì)項(xiàng)集的計(jì)數(shù)，由此產(chǎn)生所有頻繁項(xiàng)集。

1 FIMBIA算法

1.1 相關(guān)定義

為發(fā)現(xiàn)所有頻繁項(xiàng)集，計(jì)算每個(gè)候選項(xiàng)集發(fā)生的頻率成了重要任務(wù)。因此，許多研究人員提出了頻率計(jì)數(shù)的技術(shù)和數(shù)據(jù)結(jié)構(gòu)，包括位圖[10]、前綴樹[11]等。位圖是把事務(wù)數(shù)據(jù)庫(kù)壓縮存儲(chǔ)在01矩陣M中，行用來存儲(chǔ)所有的事務(wù)，列用來存儲(chǔ)所有的項(xiàng)目；如果項(xiàng)i包含于事務(wù)j，則Mij＝1，否則Mij＝0；通過計(jì)算每k行之間的交集產(chǎn)生頻繁k項(xiàng)集。當(dāng)事務(wù)數(shù)據(jù)庫(kù)是密集型且支持度不很小時(shí)，位圖的表示方法還是比較有效的。前綴樹也稱為頻繁模式樹(FPtree)，是存儲(chǔ)串或序列時(shí)非常有用的數(shù)據(jù)結(jié)構(gòu)，從葉子到根的路徑可以看做項(xiàng)集；如果兩個(gè)項(xiàng)集共享前綴，則稱為共享子路徑。共享前綴節(jié)省了頻率計(jì)數(shù)的計(jì)算時(shí)間，但是遞歸調(diào)用過程中前綴樹的重構(gòu)耗費(fèi)了大量時(shí)間。

針對(duì)以上數(shù)據(jù)結(jié)構(gòu)的不足，本文提出了一種新的數(shù)據(jù)結(jié)構(gòu)——索引數(shù)組，存儲(chǔ)所有頻繁1項(xiàng)集及其相關(guān)信息。當(dāng)掃描事務(wù)數(shù)據(jù)庫(kù)時(shí)能夠通過索引快速找到頻繁1項(xiàng)集與事務(wù)之間的關(guān)系，從而確定項(xiàng)集與事務(wù)之間的關(guān)系，節(jié)省了大量時(shí)間。

定義1 索引數(shù)組index[ ]的元素由一個(gè)三元組組成(item，item_TID，value)。其中：item是頻繁1項(xiàng)集；項(xiàng)集item的包含索引是items_TID(item)={T｜itemT}和value(item)={oi｜oi=itemj，i≤j≤m，1≤i≤l，l=｜L1｜}。

定義2 若｜itemset｜=0，則項(xiàng)集itemset稱為空項(xiàng)集，記為。

頻繁1項(xiàng)集的包含索引item_TID是item所在事務(wù)的標(biāo)志符；value是對(duì)item按字母表順序重新編碼后新的標(biāo)志符{o1，o2，…，ol}，l是頻繁1項(xiàng)集的數(shù)目，即數(shù)組的長(zhǎng)度。

定義3 已知項(xiàng)的集合I(xiàn)={i1，i2，…，im}，事務(wù)數(shù)據(jù)庫(kù)D，則D中的一個(gè)事務(wù)T產(chǎn)生的項(xiàng)集集合稱為T的項(xiàng)集集合，記為IS(T)，即IS(T)={itemset｜ij∈itemset，itemsetT，TD}，規(guī)定IS(T)，IS(T)。

由集合論知，包含m個(gè)項(xiàng)的事務(wù)數(shù)據(jù)庫(kù)產(chǎn)生的所有可能的項(xiàng)集個(gè)數(shù)為2m，其中一個(gè)事務(wù)T產(chǎn)生的項(xiàng)集集合的數(shù)目為｜IS(T)｜=2｜T｜。其中，｜T｜≤m。

因?yàn)槭聞?wù)數(shù)據(jù)庫(kù)D中有2m個(gè)不同的項(xiàng)集，所以有必要把這些項(xiàng)集按照一定的方式排列[12]。本文通過采用循環(huán)迭代增加項(xiàng)作為模式后綴的方式排列所有項(xiàng)集，這種排列方法更便于理解和計(jì)算。

索引數(shù)組中，數(shù)組的長(zhǎng)度為頻繁1項(xiàng)集的數(shù)目l，并在數(shù)組中記錄這些項(xiàng)集的相關(guān)信息，包括項(xiàng)集所在事務(wù)的TID和對(duì)頻繁1項(xiàng)集按字母表順序重新編號(hào)后的標(biāo)志符{o1，o2，…，ol}。由這些頻繁1項(xiàng)集組成的所有項(xiàng)集由式(2)得到：

使用兩兩連接的方式生成候選項(xiàng)集的方法相比，避免了進(jìn)行大量的重復(fù)比較操作和連接操作，節(jié)省了大量的時(shí)間。算法首先掃描一次事務(wù)數(shù)據(jù)庫(kù)發(fā)現(xiàn)所有頻繁1項(xiàng)集，壓縮了所有項(xiàng)集的數(shù)目，利用索引數(shù)組存儲(chǔ)頻繁1項(xiàng)集及其相關(guān)信息；在第二次掃描事務(wù)數(shù)據(jù)庫(kù)時(shí)，直接根據(jù)索引數(shù)組中記錄的信息判斷1項(xiàng)集是否包含于該事務(wù)中，有利于快速判斷項(xiàng)集與事務(wù)之間的關(guān)系。

2.2 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證FIMBIA算法的有效性，本文采用標(biāo)準(zhǔn)數(shù)據(jù)集mushroom (117個(gè)不同項(xiàng)，8 124個(gè)事務(wù)，平均每個(gè)事務(wù)23項(xiàng)，文件大小558 KB)進(jìn)行頻繁項(xiàng)集挖掘?qū)嶒?yàn)。數(shù)據(jù)集可以由FIMI(frequent itemset mining implementations repository)資源庫(kù)下載[13]。實(shí)驗(yàn)的硬件平臺(tái)是Pentium 2.93 GHz CPU，512 MB Memory，操作系統(tǒng)是Windows XP，對(duì)比算法是Apriori算法和FPgrowth算法。

性能對(duì)比分析指標(biāo)是各算法在不同支持度和事務(wù)數(shù)下的運(yùn)行時(shí)間。圖1為FIMBIA與Apriori和FPgrowth算法進(jìn)行比較的實(shí)驗(yàn)結(jié)果。其中，(a)為三種算法在給定不同最小支持度下的比較結(jié)果；(b)為三種算法在固定最小支持度為1%而事務(wù)數(shù)不同情況下的比較結(jié)果。

3 結(jié)束語

本文提出了挖掘頻繁項(xiàng)集完全集的高性能算法FIMBIA。該算法采用循環(huán)迭代增加項(xiàng)為項(xiàng)集后綴的方式生成所有頻繁項(xiàng)集，比Apriori算法中的連接操作節(jié)省了大量的時(shí)間，利用索引數(shù)組這種新的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)頻繁1項(xiàng)集及其相關(guān)信息，可以方便快速地發(fā)現(xiàn)項(xiàng)集與事務(wù)之間的聯(lián)系，從而快速挖掘所有頻繁項(xiàng)集。實(shí)驗(yàn)結(jié)果表明，F(xiàn)IMBIA算法提高了頻繁項(xiàng)集的挖掘效率。

參考文獻(xiàn)：

［1］AGRAWAL R， IMIELINSKI T， SWAMI A. Mining association rules between sets of items in large databases[C]//Proc of ACM SIGMOP Conference on Management of Data. New York:ACM Press， 1993:207216.

[2]HAN Jiawei， PEI Jian， YIN Yiwen. Mining frequent patterns without candidate generation[J].ACM SIGMOD Record， 2000，29(2):112.

[3]ZAKI M J. Scalable algorithms for association mining[J]. IEEE Trans on Knowledge Data Engineering， 2000，12(3):372390.

[4]焦學(xué)磊， 王新莊. 基于矩陣的頻繁項(xiàng)集發(fā)現(xiàn)算法[J].江漢大學(xué)學(xué)報(bào):自然科學(xué)版，2007，35(1):4346.

[5]孟祥萍， 錢進(jìn)， 劉大有. 基于數(shù)組的關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)工程，2003，29(15):9899.

[6]王柏盛， 劉寒冰， 靳書和，等.基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法[J].微計(jì)算機(jī)信息，2007，24(53):143145.

[7]高宏賓， 潘谷， 黃義明. 基于頻繁項(xiàng)集特性的Apriori算法的改進(jìn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(10):22732275.

[8]宋威， 楊炳儒， 徐章艷，等. 基于索引數(shù)組與集合枚舉樹的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)科學(xué)，2007，34(7):146149.

[9]XIN Dong， HAN Jiawei， YAN Xifeng，et al. On compressing frequent patterns[J]. Data Knowledge Engineering，2007，60（1）:529.

[10]ORLANDO S， LUCCHESE C， PALMERINI P，et al. KDCI:a multistrategy algorithm for mining frequent sets[C]//Proc ofICDM Workshop on Frequent Itemset Mining Implementations. Plorida:[s.n.]， 2003.

[11]RACZ B. Nonordfp: An FPgrowth variation without rebuilding the FPtree[C]//Proc ofICDM Workshop onFrequent Itemset Mining Implementations， 2004.

[12]WU Fan， CHIANG S W， LIN J R. A new approach to mine frequent patterns using itemtransformation methods[J]. Information Systems，2007，32(7):10561072.

[13]Frequent itemset mining implementations repository[EB/OL]. (2004). http://fimi.ci.helsinki.fi/.