使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集

陳偉

（淮南聯(lián)合大學(xué) 計算機(jī)系，安徽 淮南232038）

通常，關(guān)聯(lián)規(guī)則挖掘是指從一個大型的數(shù)據(jù)集中發(fā)現(xiàn)有趣的關(guān)聯(lián)或相關(guān)關(guān)系，即從數(shù)據(jù)集中識別出頻繁出現(xiàn)的屬性值集（Sets of Attribute-Values），也稱為頻繁項(xiàng)集（Frequent Itemsets,簡稱頻繁集），然后再利用這些頻繁集創(chuàng)建描述關(guān)聯(lián)規(guī)則的過程。

1 關(guān)聯(lián)規(guī)則挖掘算法

關(guān)聯(lián)規(guī)則挖掘算法——Apriori算法是使用候選項(xiàng)集找頻繁項(xiàng)集的過程。

Apriori算法通過對數(shù)據(jù)庫D的多趟掃描來發(fā)現(xiàn)所有的頻繁項(xiàng)目集。在第一趟掃描數(shù)據(jù)庫時，對項(xiàng)集I中的每一個數(shù)據(jù)項(xiàng)計算其支持度，確定出滿足最小支持度的頻繁1項(xiàng)集的集合L1，然后，L1用于找頻繁2項(xiàng)集的集合L2，如此下去……在后續(xù)的第k次掃描中，首先以k-1次掃描中所發(fā)現(xiàn)的含k-1個元素的頻繁項(xiàng)集的集合Lk-1為基礎(chǔ)，生成所有新的候選項(xiàng)目集CK（Candidate Itemsets），即潛在的頻繁項(xiàng)目集，然后掃描數(shù)據(jù)庫 D，計算這些候選項(xiàng)目集的支持度，最后從候選集CK中確定出滿足最小支持度的頻繁k項(xiàng)集的集合Lk,并將Lk作為下一次掃描的基礎(chǔ)。重復(fù)上述過程直到不再發(fā)現(xiàn)新的頻繁項(xiàng)目集[1]。

2 關(guān)聯(lián)規(guī)則算法的改進(jìn)

從Apriori算法中由k頻繁項(xiàng)集生成k+1頻繁項(xiàng)集時，首先生成候選項(xiàng)目集Ck+1，該函數(shù)不僅要對 k項(xiàng)集的所有符合Apriori算法條件的數(shù)據(jù)進(jìn)行交集，并且要判斷候選項(xiàng)目集的所有子集是否在k頻繁項(xiàng)集中。該函數(shù)生成的許多候選項(xiàng)目集并不是要找的頻繁項(xiàng)集，但在掃描數(shù)據(jù)庫時，要記錄下這些數(shù)據(jù)的出現(xiàn)次數(shù)，這會耗費(fèi)大量的CPU開銷。如果D中的事務(wù)數(shù)很大，k頻繁項(xiàng)集中項(xiàng)數(shù)很多，則侯選項(xiàng)目集的元素個數(shù)就會很大，例如2 000個頻繁 1項(xiàng)集，將產(chǎn)生 2 000×999/2=999 000個候選2項(xiàng)集。如此巨大數(shù)量的候選項(xiàng)目集，對它進(jìn)行出現(xiàn)次數(shù)的統(tǒng)計時開銷非常大，這也是整個算法性能優(yōu)劣的關(guān)鍵所在。

（1）使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集

Apriori算法是從 TID項(xiàng)集格式（即{TID：itemset}）的事務(wù)集挖掘頻繁模式，其中TID是事務(wù)標(biāo)識符，而item-set是事務(wù)TID中購買的商品集。這種數(shù)據(jù)格式稱作水平數(shù)據(jù)格式。另外,數(shù)據(jù)也可以用項(xiàng)-TID集格式(即{item:TID_set})表示，其中 item是項(xiàng)的名稱，而 TID_set是包含item事務(wù)標(biāo)識符的集合。這種格式稱作垂直數(shù)據(jù)格式。下面使用垂直數(shù)據(jù)格式進(jìn)行有效的挖掘頻繁項(xiàng)集。

首先，通過掃描一次數(shù)據(jù)庫D，在求頻繁 l項(xiàng)集的同時，把數(shù)據(jù)由水平格式轉(zhuǎn)化為垂直格式，即記錄下每個項(xiàng)集在事務(wù)數(shù)據(jù)庫中出現(xiàn)時該條數(shù)據(jù)在數(shù)據(jù)庫D中的TID號，則項(xiàng)集的支持度計數(shù)直接是項(xiàng)集的TID集的長度。從k=2開始，根據(jù)Apriori性質(zhì)中相交條件的項(xiàng)集進(jìn)行Apriroi連接運(yùn)算，使用頻繁k項(xiàng)集來構(gòu)造候選k+1項(xiàng)集。通過取頻繁k項(xiàng)集的TID集的交計算對應(yīng)的k+1項(xiàng)集的TID集。如果該TID集的長度大于最小支持度計數(shù)，則該記錄為頻繁項(xiàng)集。重復(fù)該過程，每次k值增加1，直到不能再找到頻繁項(xiàng)集或候選項(xiàng)集。

（2）挖掘?qū)嵗?/p>

設(shè)事務(wù)數(shù)據(jù)庫D，如表1。

假定要求最小支持度計數(shù)為2，掃描一次該數(shù)據(jù)集可以把它轉(zhuǎn)換成表2所示的垂直數(shù)據(jù)格式。

2015年東京警視廳的數(shù)據(jù)顯示，一年中有1.3998萬人借錢，借出去的金額為688.7346萬日元（約40萬元人民幣），歸還率是78.6%，這一數(shù)據(jù)比2009年的64.3%有了很大進(jìn)步。但是，也可以看出，超過20%的人，還是借錢沒還。

表1 事務(wù)數(shù)據(jù)庫

表2 頻繁1項(xiàng)集

通過取每對頻繁單個項(xiàng)的TID集的交，可以在該數(shù)據(jù)集上進(jìn)行挖掘。由于表2中有4個項(xiàng)是頻繁的，總共進(jìn)行6次交運(yùn)算，結(jié)果有6個非空2項(xiàng)集，如表3所示。

表3 頻繁2項(xiàng)集

根據(jù)Apriori性質(zhì)，對得到的頻繁2項(xiàng)集求交集，只進(jìn)行1次交集，所以符合條件的頻繁三項(xiàng)集為{I2,I3,I5}。如表 4所示。

表4 頻繁3項(xiàng)集

通過挖掘可以驗(yàn)證最終得到的頻繁項(xiàng)集和用Apriori算法得到的結(jié)果是相同的[2-3]。

（3）算法的描述

輸入:事務(wù)數(shù)據(jù)庫D；

最小支持度計數(shù)閾值min_sup。

輸出：D中的頻繁項(xiàng)集L。

輸出:所有的頻繁1項(xiàng)集。

輸入:頻繁k-1項(xiàng)集。最小支持度計數(shù)min_sup。

輸出:所有的頻繁k項(xiàng)集。

3 改進(jìn)算法的分析

理論上，改進(jìn)算法應(yīng)快于算法Apriori，原因如下：

(1)該算法不用求候選頻繁項(xiàng)集，從而省去了項(xiàng)集進(jìn)行連接步以后對該項(xiàng)集所有子集的判斷，這會節(jié)省大量的CPU開銷，尤其是當(dāng)數(shù)據(jù)庫D中的數(shù)據(jù)比較多，同時候選項(xiàng)集比較多時，例如頻繁1項(xiàng)集2 000個，根據(jù)Apriori性質(zhì),則候選頻繁1項(xiàng)集要有2 000×999/2=999 000個，但其中也許只有少數(shù)是要找的頻繁2項(xiàng)集。Apriori算法要求其中所有999 000個在數(shù)據(jù)庫中的頻繁度。

(2)除了由頻繁k項(xiàng)集產(chǎn)生候選k+1項(xiàng)集時利用Apriori性質(zhì)之外，這種方法的另一優(yōu)點(diǎn)是不需要掃描數(shù)據(jù)庫來確定k+1項(xiàng)集(k≥1)的支持度。這是因?yàn)槊總€k項(xiàng)集的TID集攜帶了計算該支持度所需的完整信息。

該算法的缺點(diǎn)是TID集可能很長，長集合不僅需要大量空間，而且求交運(yùn)算需要大量計算時間。

[1]韓家煒.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2000.

[2]陸楠.關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D].長春：吉林大學(xué)，2007.

[3]羅可，張學(xué)茂.一種高效的頻集挖掘算法[J].長沙理工大學(xué)學(xué)報(自然科學(xué)版)，2006，3(3)：84-90.

[4]汪光一.關(guān)聯(lián)規(guī)則挖掘算法的研究[D].北京：北京交通大學(xué),2007.

[5]高峰，謝劍英.發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的增量式更新算法[J].計算機(jī)工程，2000(12):49-50.

[6]KANTARDZIC M(美).數(shù)據(jù)挖掘-概念、模型、方法和算法[M].北京：清華大學(xué)出版社，2003.