一種基于倒排索引的頻繁項集挖掘方法

（長春理工大學(xué) 計算機科學(xué)技術(shù)學(xué)院，長春 130022）

大數(shù)據(jù)時代的到來，數(shù)據(jù)呈爆炸式增長，為了能夠從大量的數(shù)據(jù)中挖掘出有價值的信息，研究關(guān)聯(lián)規(guī)則得到了高度的重視，關(guān)聯(lián)規(guī)則挖掘過程一般包括兩步：（1）頻繁項集的識別（2）從頻繁項集中挖掘隱含關(guān)聯(lián)規(guī)則［1］。其中頻繁項集的識別是整個挖掘過程的主要部分，頻繁項集的規(guī)模也決定了數(shù)據(jù)挖掘性能。

目前，已有眾多學(xué)者針對頻繁項集挖掘的經(jīng)典算法進行改進，他們分別從“事物：項集合”和“項目：事務(wù)集合”兩種方式展開研究，前者被稱為“水平數(shù)據(jù)格式”，后者被稱為“垂直數(shù)據(jù)格式”。文獻［2］利用了二維數(shù)組的結(jié)構(gòu)來對算法進行了改進，大大減少了輸入輸出操作，使查找速度得到提高，但隨著數(shù)據(jù)庫中數(shù)據(jù)量不斷增大，導(dǎo)致了數(shù)據(jù)庫中的事務(wù)無法全部存入數(shù)組當(dāng)中。文獻［3］提出的十字鏈表和二維數(shù)組相結(jié)合的方法實現(xiàn)了頻繁項集挖掘，但由于十字鏈表是靜態(tài)的，不能隨著挖掘過程的進行而隨時壓縮鏈表，因此增大了內(nèi)存開銷。針對上述算法的問題，在二維數(shù)組的基礎(chǔ)上引入倒排索引結(jié)構(gòu)，提出了一種基于倒排索引和二維數(shù)組的頻繁項集挖掘算法。

1 基于倒排索引和二維數(shù)組的頻繁項集挖掘

1.1 倒排索引表示事務(wù)數(shù)據(jù)庫

倒排索引［4-5］（Inverted Index），也稱為反向索引，是一種直接通過屬性值來確定該屬性所在記錄位置的索引方法，包括詞項詞典和倒排記錄表兩個部分。倒排索引是信息檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)，倒排索引表是由一組包含屬性值和屬性所在地址的記錄所形成的二維表，其存儲結(jié)構(gòu)對檢索的效率和效果起著至關(guān)重要的作用。倒排索引結(jié)構(gòu)如圖1所示。

圖1 倒排索引結(jié)構(gòu)

為了提高頻繁項集的挖掘效率，引入倒排索引技術(shù)，獲取其對應(yīng)的事務(wù)編號Tid，并按Tid對應(yīng)事務(wù)的項目長度進行分組，構(gòu)建倒排索引。其中倒排索引由兩部分組成：第一部分是頻繁項目，其內(nèi)容是頻繁項目頭節(jié)點；第二部分是倒排索引節(jié)點，由項目長度和事務(wù)Tid列表組成，對Tid按照事務(wù)長度列表進行分塊保存。對于包含N個項目的候選項集，采用倒排索引技術(shù)，每個候選項集只需掃描長度為N的頭節(jié)點表，并取出頭節(jié)點表中事務(wù)集合，這將大大提升掃描數(shù)據(jù)庫效率，從而提高頻繁項集挖掘的效率。

假設(shè)事務(wù)數(shù)據(jù)庫D共有6條事務(wù)，事務(wù)中的項目用I1，I2，I3，I4，I5，I6表示，每條事務(wù)都按字典順序排序，如表1所示。事務(wù)數(shù)據(jù)庫D對應(yīng)的倒排索引如圖2所示，通過將項目的倒排索引轉(zhuǎn)換為列向量，并用“與”運算得到支持度，最后刪除小于支持度的頻繁項集。

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

圖2 事務(wù)數(shù)據(jù)庫D對應(yīng)的倒排索引

1.2 基于二維數(shù)組的候選k項集生成方法

首先，定義頻繁項集Lk，候選項集CK。將（k-1）項頻繁項集分為兩部分存儲到二維數(shù)組，記二維數(shù)組為Ak。將頻繁（k-1）項集的前（k-2）項集存儲到Ak的第0列，第（k-1）項集存儲到Ak的第1列，分組編號存儲到Ak的第2列，有效標(biāo)識位存儲到Ak的第3列，其中1表示該項集可以和其他項集鏈接，0表示不可以鏈接。例如，頻繁3項集L3={{I1，I4，I6}，{I2，I3，I4}，{I4，I5，I6}}，它在二維數(shù)組Ak中的存儲形式如表2所示。

表2 頻繁3項集L3的二維數(shù)組

在存入二維數(shù)組Ak的過程中把頻繁（k-1）項集分組，由于Apriori算法［6］在執(zhí)行連接生成頻繁K項集Lk+1的過程中，需要從Lk中找到兩個項集與前k-1項集均相同的項集，才可以連接，因此分組規(guī)則是把與第0列相同的頻繁項集分成一組；根據(jù)表2可知，頻繁3項集L3應(yīng)該分成三組，第0行的{I1，I4，I6}分在第1組，第1行的{I2，I3，I4}分在第2組，第2行的{I4，I5，I6}分在第3組。由于兩個頻繁（k-1）項集鏈接生成候選項集Ck時，必須滿足前k-2項相同，第k-1項不同。根據(jù)鏈接條件，三組項集均無法與其他項集進行鏈接，所以第3列的有效標(biāo)識位均為0。在生成候選k項集Ck時按照分組來進行，因為分組后的頻繁項集正好滿足了鏈接條件，不僅能生成所有的候選k項集，而且不會產(chǎn)生多余的候選k項集。

2 實例分析

下面以部分實驗數(shù)據(jù)為例說明挖掘頻繁項集的過程：

掃描數(shù)據(jù)庫，生成倒排索引。在生成倒排索引前首先根據(jù)項目編號得到對應(yīng)的Tid值，再按照每個項目的Tid值個數(shù)進行分組，最后生成每個項目和Tid值的倒排索引。如圖2所示。

再次掃描數(shù)據(jù)庫，獲得頻繁1項集L1={I1，I2，I3，I4，I5，I6}，然后將頻繁1項集存入二維數(shù)組中，當(dāng)存入二維數(shù)組時，需要遵循一定的規(guī)則，其中二維數(shù)組有四列，每列數(shù)據(jù)都有不同的意義，以頻繁1項集為例，第0列存儲前k-1項頻繁項集，因為頻繁1項集不存在前k-1項頻繁項集，所以第0列用空表示，第1列存儲第k項集，第2列存儲在第0列基礎(chǔ)上的分組編號，第3列代表各項集間是否可以鏈接，可以鏈接記為1，否則記為0。所以頻繁1項集對應(yīng)存儲的二維數(shù)組如表3所示。

表3 頻繁1項集的二維數(shù)組

接下來生成頻繁2項集，由于所有頻繁1項集的第0列相同，且標(biāo)志位均為1，因此直接鏈接生成候選頻繁 2 項集 C2={I1I2，I1I3，I1I4，I1I5，I1I6，I2I3，I2I4，I2I5，I2I6，I3I4，I3I5，I3I6，I4I5，I4I6，I5I6}，再通過上述的倒排索引技術(shù)計算支持度來篩選頻繁2項集。支持度計算以I1I4為例，I1的倒排索引是（1，6），相應(yīng)的列向量R1=（1，0，0，0，0，1）T，I4的倒排索引是（1，3，4，5，6），相應(yīng)的列向量R2=（1，0，1，1，1，1）T，計算R1&R2=（1，0，0，0，0，1）T，R1&R2結(jié)果中1的個數(shù)就是支持度，綜上所述可知I1I4的支持度是2，假設(shè)實驗設(shè)定最小支持度為2，因為I1I4的支持度等于2，所以I1I4為頻繁項集，依次計算得到頻繁2項集L2={I1I4，I1I6，I2I3，I2I4，I3I4，I4I5，I4I6，I5I6}。

利用上述方法生成頻繁3項集L3={{I1I4I6}，{I2I3I4}，{I4I5I6}}。

接下來計算頻繁4項集，根據(jù)性質(zhì)，頻繁k項集若能產(chǎn)生頻繁（k+1）項集，那么頻繁k項集中項集個數(shù)肯定大于k。由于L3的個數(shù)小于4，因此不能生成頻繁4項集，算法結(jié)束。

3 實驗結(jié)果及分析

為了驗證算法的性能，分別在以下兩方面與文獻［2］、文獻［3］中的算法做了對比：一是最小支持度閾值不變，數(shù)據(jù)集規(guī)模不斷增加的情況（如圖3所示）；二是數(shù)據(jù)集大小一定，支持度不斷增加的情況（如圖4所示）分別得出實驗結(jié)果。

根據(jù)圖3所示，當(dāng)最小支持度閾值不變而數(shù)據(jù)集不斷增加時，在數(shù)據(jù)集未達到25萬時，算法ALN的運行時間較短；當(dāng)數(shù)據(jù)集超過25萬之后，文中算法的運行時間明顯少于Apriori-BR和ALN兩種算法，更適用于大數(shù)據(jù)的頻繁項集挖掘。

圖3 不同數(shù)據(jù)集下的運行時間結(jié)果

圖4 不同最小支持度下的運行時間結(jié)果

根據(jù)圖4所示，在原始數(shù)據(jù)集不變，最小支持度閾值改變時，文中提出的算法比Apriori-BR和ALN生成頻繁項集的系統(tǒng)運行時間短，故比其他兩種算法更高效。

4 結(jié)束語

通過對文獻［2］和文獻［3］算法的改進與結(jié)合，提出基于倒排索引和二維數(shù)組的頻繁項集挖掘算法。雖然該算法需要掃描兩次數(shù)據(jù)庫，但在數(shù)據(jù)集較大的時候，倒排索引技術(shù)大大提高了檢索效率，運行時間也相對較少。在計算支持度時無需掃描數(shù)據(jù)庫，并且通過標(biāo)志位約束減少候選項集的生成數(shù)量，從而提高了候選項集的連接效率以及內(nèi)存利用率。