一種基于倒排索引的頻繁項(xiàng)集挖掘方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)例分析

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

4 結(jié)束語

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