基于游程編碼的最大頻繁項(xiàng)集挖掘算法

王茂華，郝云力，儲(chǔ)小靜

（阜陽師范學(xué)院，安徽 阜陽 236041）

1 概述

最大頻繁項(xiàng)集的挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要的研究方向[1].目前大部分的挖掘算法都是在經(jīng)典的FP-MAX[2]、Mafia[3]等算法的基礎(chǔ)上進(jìn)行的改進(jìn)，也有些學(xué)者提出了使用其他方法的最大頻繁項(xiàng)集的挖掘算法.在文獻(xiàn)[4]中，作者提出了一種基于鏈表運(yùn)算的挖掘算法，該算法雖然拋棄了一部分的候選項(xiàng)，但是仍然會(huì)產(chǎn)生大量的冗余項(xiàng).在文獻(xiàn)[5]中，作者提出了一種基于布爾矩陣的最大頻繁項(xiàng)集的挖掘算法，由于實(shí)際應(yīng)用中數(shù)據(jù)量非常龐大，因此用布爾矩陣存儲(chǔ)數(shù)據(jù)庫會(huì)占用很大的存儲(chǔ)空間.

針對(duì)以上存在的問題，文章提出了一種基于游程編碼的最大頻繁項(xiàng)集的挖掘算法RLCMAX.該算法不僅能減少事務(wù)數(shù)據(jù)庫占用的存儲(chǔ)空間，而且能有效提高算法的效率.

2 算法描述

2.1 數(shù)據(jù)庫的游程編碼表示

在數(shù)據(jù)庫中，可以用1表示某項(xiàng)目被事物包含，0表示不被包含，因此可以用0-1序列來表示數(shù)據(jù)庫.由于在0-1序列中只有0、1兩個(gè)符號(hào)，而且總是交替出現(xiàn)，因此可以用游程編碼來表示數(shù)據(jù)庫.文章規(guī)定每個(gè)項(xiàng)目的游程序列必定從1-游程開始.如表1所示的數(shù)據(jù)庫D.

表1 事物數(shù)據(jù)庫D

表2 游程序列表示的數(shù)據(jù)庫

D中各項(xiàng)目可用表2中的游程序列表示.

由表2可以知道，項(xiàng)目的支持度必為1-游程的長度之和.

由于每個(gè)項(xiàng)目的游程個(gè)數(shù)是不確定的，所以可用單鏈表來表示游程序列.文章用鏈表數(shù)組來表示整個(gè)事物數(shù)據(jù)庫.

2.2 算法的相關(guān)定義

定義1 鏈表數(shù)組TL是長度為n+1的指針數(shù)組，TL[i]指向項(xiàng)目Ii所對(duì)應(yīng)的單鏈表，n為數(shù)據(jù)庫中項(xiàng)目的個(gè)數(shù).鏈表上每個(gè)結(jié)點(diǎn)包含2個(gè)域：data域和next域，其中data域?yàn)橛纬涕L度.

掃描一遍數(shù)據(jù)庫，構(gòu)造鏈表數(shù)組，最后刪除支持度小于最小支持度的鏈表[6].如表1所示的數(shù)據(jù)庫D可轉(zhuǎn)換為圖1所示的鏈表數(shù)組TL.

圖1 鏈表數(shù)組TL

數(shù)據(jù)庫中項(xiàng)目的支持度顯然為鏈表中1-游程的data域之和.

定義2 鏈表集CL由若干個(gè)單鏈表組成，存儲(chǔ)挖掘過程中產(chǎn)生的所有候選頻繁項(xiàng)目集所對(duì)應(yīng)的單鏈表.

定義3 非頻繁項(xiàng)目集CBI存儲(chǔ)不屬于當(dāng)前最大頻繁項(xiàng)目集中的項(xiàng)目.

集合CB存儲(chǔ)挖掘過程中產(chǎn)生的所有CBI.

定義4 頻繁項(xiàng)目集CI存儲(chǔ)當(dāng)前的頻繁項(xiàng)目集.

定義5 局部最大頻繁項(xiàng)集 若集合FI是所有以Ij為起始項(xiàng)的頻繁項(xiàng)集的集合，如果集合A∈FI,則對(duì)坌B∈FI且A≠B，有A不是B的子集，則稱A為局部最大頻繁項(xiàng)集.

2.3 游程編碼的交運(yùn)算

對(duì)任意兩個(gè)鏈表C和F，從第一對(duì)結(jié)點(diǎn)開始求交，運(yùn)算結(jié)果與結(jié)點(diǎn)是0-游程還是1-游程有關(guān)，基本思想描述如下：

1）若值大的結(jié)點(diǎn)Pmax為1-游程，轉(zhuǎn)2），否則轉(zhuǎn)3）.

2）若值小的結(jié)點(diǎn)Pmin為1-游程，轉(zhuǎn)4），否則轉(zhuǎn)5）.

3）若值小的結(jié)點(diǎn)Pmin為0-游程，轉(zhuǎn)5），否則轉(zhuǎn)4）.

4）若結(jié)果集合c1的尾元素Last(c1)是1-游程，則用結(jié)點(diǎn)Pmin的值與Last(c1)的和替換Last(c1)；否則將結(jié)點(diǎn)Pmin添加到集合c1中.

5）若結(jié)果集合c1的尾元素Last(c1)是0-游程，則將結(jié)點(diǎn)Pmin添加到集合c1中；否則用結(jié)點(diǎn)Pmin的值與Last(c1)的值替換Last(c1).

6）將結(jié)點(diǎn)Pmax和Pmin之差放入臨時(shí)結(jié)點(diǎn)Lp中.

7）如果結(jié)點(diǎn)Lp的值為0，則Pmax、Pmin后移.否則，Pmax指向Lp，Pmin后移.

8）重復(fù)上述步驟，直到C,F都為空.

基于上述思路，游程編碼的交運(yùn)算用偽代碼描述如下：

2.4 最大頻繁項(xiàng)集的挖掘算法

算法采用回溯法搜索整個(gè)解空間的最大頻繁項(xiàng)目集[4]，首先搜索出以I1為起始項(xiàng)的最大頻繁項(xiàng)集,然后分別找出以Ij(j=2…n)為起始項(xiàng)的局部最大頻繁項(xiàng)集，去掉其中的非最大頻繁項(xiàng)集，最終可得所有的最大頻繁項(xiàng)集.算法的具體思路如下：

1)搜索j層，鏈表集合CL的尾元素與Ij對(duì)應(yīng)的鏈表L[j]相交，生成新鏈表.若新鏈表的1-游程之和不小于最小支持度min_sup時(shí)，將Ij添加到項(xiàng)目集合CI中，將新鏈表添加到CL中；否則，將Ij添加到項(xiàng)目集合CBI中.繼續(xù)向j+1層搜索.

2)重復(fù)1），直到j(luò)>m，此時(shí)，CI必為局部最大頻繁項(xiàng)集.若CI不是MFI中最大頻繁項(xiàng)集的子集，則CI為最大頻繁項(xiàng)集，將CI添加到MFI中，將CBI添加到集合CB中.轉(zhuǎn)3）

3)返回j-1層，刪除項(xiàng)目集合CI中項(xiàng)目Ij-1及其后面的所有項(xiàng)目，刪除鏈表集合CL的尾元素.若存在Last(CB)的一個(gè)子集 B（對(duì)坌It∈B，有 t>j-1），有 CI∪B的項(xiàng)目支持度不小于最小支持度，且對(duì)坌In∈Last(CB)-B有CI∪In的項(xiàng)目支持度小于最小支持度(其中n>j-1),則所有以CI∪B為前綴的頻繁項(xiàng)集必為局部最大頻繁項(xiàng)集;將B中的項(xiàng)目添加到項(xiàng)目集合CI中，用CI∪B的鏈表替換Last(CL)，然后從Last(CB)中刪除B中的項(xiàng)目，搜索下一層，轉(zhuǎn)1）.否則如果CI為空,清空CB，搜索下一層，轉(zhuǎn)1)；如果CI不為空且CB中存在2個(gè)以上的元素，刪除CB的尾元素，返回上一層，重復(fù)3).

基于上述思路，算法用偽代碼描述如下：

3 實(shí)例解釋

以表1所示的數(shù)據(jù)庫為例，最小支持度min_sup為2，求數(shù)據(jù)庫的最大頻繁項(xiàng)集，求解步驟如下：

1)初始化 CL={{8}},CI=覫,CB=覫;

2)進(jìn)入第1層，選擇項(xiàng)目I1，Last(CL)與I1對(duì)應(yīng)的鏈表TL[1]相交得鏈表｛7,1｝，支持度為7，大于min_sup，則CI=CI∪{I1}={I1}，CL=CL∪{{7,1}}={{8},{7,1}}.

3)按照同樣的步驟繼續(xù)搜索，直到搜索完最底層即第5層，完成第一輪遍歷，得到CI={I1,I2,I3},CL={{8},{7,1},{3,1,3,1},{0,1,2,5}},CB={{I4,I5}}.此CI即為最大頻繁項(xiàng)集.

4)返回第5層，不選擇I5.

5)返回第4層，不選擇I4.

6)返回第3層，刪除CI中的I3，刪除CL的最后一項(xiàng)Last(CL)，逆序遍歷 Last(CB)：

（1）選擇Last(CB)中的項(xiàng)目I5，將Last(CL)與I5對(duì)應(yīng)的鏈表TL[5]相交得鏈表{2,3,2,1}，支持度為4，大于min_sup.則，CI=CI∪{I5}={I1,I2,I5}，CL={{8},{7,1},{2,3,2,1}}，CB={{I4}}.

（2）選擇Last(CB)中的項(xiàng)目I4，將Last(CL)與I4對(duì)應(yīng)的鏈表TL[4]相交得鏈表{2,4,1,1}，支持度為3，大于min_sup.則 CI=CI∪{I4}={I1,I2,I5,I4}，CL={{8},{7,1},{2,3,2,1},{2,4,1,1}}，CB=覫.

7）進(jìn)入第4層，由于I4已在CI中，不選.進(jìn)入第5層，同樣不選.則CI={I1,I2,I4,I5}必為最大頻繁項(xiàng)集.

重復(fù)上述步驟，最終可以找到所有的最大頻繁項(xiàng)集.

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

圖2 性能比較

為驗(yàn)證算法的有效性，本文采用mushroom數(shù)據(jù)集進(jìn)行驗(yàn)證，該數(shù)據(jù)集共有8124個(gè)事物，23個(gè)屬性、127種取值，由于其第11個(gè)屬性有2480個(gè)空值，在不影響實(shí)驗(yàn)結(jié)果的情況下刪除該屬性.算法檢測(cè)的硬件平臺(tái)是AMD 2.9GHZ CPU,2G內(nèi)存，操作系統(tǒng)為WIN7，對(duì)比算法是FP-MAX算法.為保證數(shù)據(jù)正確，算法在每個(gè)比較中運(yùn)行10次，計(jì)算均值作為結(jié)果.兩種算法的實(shí)驗(yàn)結(jié)果如圖2表示.從實(shí)驗(yàn)結(jié)果看，本文提出的RLCMAX算法性能要優(yōu)于FPMAX算法.

5 結(jié)束語

本文提出的基于游程編碼的最大頻繁項(xiàng)集的挖掘算法，只需掃描數(shù)據(jù)庫一次，將數(shù)據(jù)庫轉(zhuǎn)換為0-1游程編碼表示的形式，并以鏈表數(shù)組存儲(chǔ)轉(zhuǎn)換后的數(shù)據(jù)庫.通過對(duì)鏈表的交運(yùn)算，直接得到局部最大頻繁項(xiàng)集，剪枝力度非常大.當(dāng)最小支持度發(fā)生變化時(shí)，本算法不需要重新掃描數(shù)據(jù)庫和重新構(gòu)造鏈表數(shù)組，就能很容易的挖掘最大頻繁項(xiàng)集.

〔1〕Chen M S,Yu P S.Data Mining: An Overview from a Database Perspective [J]. IEEE Transactions on Knowledge and Data Engineering.1996,8(6):866–883.

〔2〕G Grahne and J Zhu.High Performance Mining of Maximal Fre -quent Itemsets [C].Proc.SIAM Workshop High Performance Data Mining: Pervasive and Data Stream Mining，May 2003．

〔3〕Burdick D,Calimlim M,Gehrke J. Mafia: A Maximal Fr -equentItemsetAlgorithm for Transactional Databases[A].In:Stuart Feldman ed,Proceeding of the 17 th International Conference on Data Engineering[C] . Washington:IEEE Computer Society Press,2001:443–452.

〔4〕劉應(yīng)東，冷明偉，陳曉云.基于鏈表數(shù)組的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)工程，2010，36(6):89–90.

〔5〕張世玲，李艷，王熙騰.一種基于布爾矩陣的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)光盤與應(yīng)用，2013（1）：192–193.

〔6〕胡雙,邱金水,賀建峰.基于線性鏈表的 Apriori算法的改進(jìn)[J].信息技術(shù),2013（8）:48–50.