基于游程編碼的最大頻繁項集挖掘算法

王茂華，郝云力，儲小靜

（阜陽師范學院，安徽 阜陽 236041）

1 概述

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

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

2 算法描述

2.1 數據庫的游程編碼表示

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

表1 事物數據庫D

表2 游程序列表示的數據庫

D中各項目可用表2中的游程序列表示.

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

由于每個項目的游程個數是不確定的，所以可用單鏈表來表示游程序列.文章用鏈表數組來表示整個事物數據庫.

2.2 算法的相關定義

定義1 鏈表數組TL是長度為n+1的指針數組，TL[i]指向項目Ii所對應的單鏈表，n為數據庫中項目的個數.鏈表上每個結點包含2個域：data域和next域，其中data域為游程長度.

掃描一遍數據庫，構造鏈表數組，最后刪除支持度小于最小支持度的鏈表[6].如表1所示的數據庫D可轉換為圖1所示的鏈表數組TL.

圖1 鏈表數組TL

數據庫中項目的支持度顯然為鏈表中1-游程的data域之和.

定義2 鏈表集CL由若干個單鏈表組成，存儲挖掘過程中產生的所有候選頻繁項目集所對應的單鏈表.

定義3 非頻繁項目集CBI存儲不屬于當前最大頻繁項目集中的項目.

集合CB存儲挖掘過程中產生的所有CBI.

定義4 頻繁項目集CI存儲當前的頻繁項目集.

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

2.3 游程編碼的交運算

對任意兩個鏈表C和F，從第一對結點開始求交，運算結果與結點是0-游程還是1-游程有關，基本思想描述如下：

1）若值大的結點Pmax為1-游程，轉2），否則轉3）.

2）若值小的結點Pmin為1-游程，轉4），否則轉5）.

3）若值小的結點Pmin為0-游程，轉5），否則轉4）.

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

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

6）將結點Pmax和Pmin之差放入臨時結點Lp中.

7）如果結點Lp的值為0，則Pmax、Pmin后移.否則，Pmax指向Lp，Pmin后移.

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

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

2.4 最大頻繁項集的挖掘算法

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

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

2)重復1），直到j>m，此時，CI必為局部最大頻繁項集.若CI不是MFI中最大頻繁項集的子集，則CI為最大頻繁項集，將CI添加到MFI中，將CBI添加到集合CB中.轉3）

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

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

3 實例解釋

以表1所示的數據庫為例，最小支持度min_sup為2，求數據庫的最大頻繁項集，求解步驟如下：

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

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

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

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

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

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

（1）選擇Last(CB)中的項目I5，將Last(CL)與I5對應的鏈表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)中的項目I4，將Last(CL)與I4對應的鏈表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）進入第4層，由于I4已在CI中，不選.進入第5層，同樣不選.則CI={I1,I2,I4,I5}必為最大頻繁項集.

重復上述步驟，最終可以找到所有的最大頻繁項集.

4 實驗結果分析

圖2 性能比較

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

5 結束語

本文提出的基于游程編碼的最大頻繁項集的挖掘算法，只需掃描數據庫一次，將數據庫轉換為0-1游程編碼表示的形式，并以鏈表數組存儲轉換后的數據庫.通過對鏈表的交運算，直接得到局部最大頻繁項集，剪枝力度非常大.當最小支持度發生變化時，本算法不需要重新掃描數據庫和重新構造鏈表數組，就能很容易的挖掘最大頻繁項集.

〔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〕劉應東，冷明偉，陳曉云.基于鏈表數組的最大頻繁項集挖掘算法[J].計算機工程，2010，36(6):89–90.

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

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