基于圖論的最大頻繁項集挖掘

摘要：利用有向項集圖來存儲事務數據庫中有關頻繁項集的信息，提出了有向項集圖的三叉鏈表式存儲結構和基于有向項集圖的最大頻繁項集挖掘算法。它不僅實現了事務數據庫的一次掃描，減少了I/O代價，而且可以同時解決好稀疏數據庫和稠密數據庫的最大頻繁項集挖掘問題。

關鍵詞：數據挖掘； 關聯規則； 最大頻繁項集； 有向項集圖； 三叉鏈表式存儲結構； 挖掘算法

中圖分類號：TP311.13文獻標志碼：A

文章編號：1001-3695(2007)11-0043-03

數據挖掘也稱數據庫中的知識發現，是從大型數據庫中發現潛在的、新穎的、有價值的、能被用戶理解的概念和信息的過程。在數據挖掘研究中，關聯規則挖掘是一個非常重要的研究內容[1]；

挖掘頻繁項集是研究關聯規則的基本步驟，也是關鍵步驟。但是對于一個維數為k的頻繁項集F，根據apriori原理，F的每個子集都是頻繁的，共有2k-1個子集。當k很大時，形成一個復雜度為NP的難度問題。由于最大頻繁項集已經隱含了所有頻繁項集信息，而且許多數據挖掘應用也只需要挖掘最大頻繁項集，如生物信息數據庫、數據通信數據庫等，近些年來很多人開始投入到最大頻繁項集的挖掘研究中。目前，最大頻繁項集挖掘算法主要是基于apriori或FP－tree的改良和衍生算法。例如基于apriori的有max－miner、pincer－search、Mafia、GenMax等，這些算法均需要多次掃描數據庫，增大了I/O負載和時間開銷，但在處理稀疏數據庫

方面表現出了優秀的特性；基于FP－tree的有FPmax、IDMFIA、FPMFI等，這些算法仍需要兩次掃描數據庫，但在處理稠密數據庫方面的性能明顯優于基于apriori的算法。由于訪問內存中的數據比訪問外存磁盤中相同大小的數據快五或六個數量級，上述這些算法至少需要兩次外存數據庫掃描；其數據結構表達形式也主要是枚舉樹、字典樹和頻繁模式樹（FP－tree）等樹型結構，結構較單一。

2．2三叉鏈表式存儲結構

有向項集圖的三叉鏈表式存儲結構由索引鏈表、節點鏈表和連接鏈表三類鏈表構成。索引鏈表是主鏈表，有且只有一個。其每個索引單元均與一個節點鏈表和一個連接鏈表相關聯，從而構成了一個以索引鏈表為主鏈表，以若干節點鏈表和連接鏈表為枝杈的三叉型存儲結構[4]。 

索引鏈表是由索引單元組成的鏈表。索引單元按順序存儲，每個單元包括兩個鏈表指針和兩個整型量。兩個指針分別指向一個節點鏈表和一個連接鏈表；兩個整型量分別存儲了相應兩類鏈表的長度信息。

節點鏈表存儲了一個有向項集圖的節點數據，它的單元就是節點，節點單元之間順序存儲。每個節點包括了本體數據域和連接關系域。對于有向項集圖來說，節點描述了事務數據庫中的1－頻繁項集模式，因而其本體數據域信息一般包括頻繁項名稱、支持頻繁項的Tidlist和支持數；連接關系域包括一個指針和一個整型量，分別為出點指針和出度，指針指向連接鏈表的相應連接單元。

連接鏈表單元存儲的是節點的相對地址。相對地址由兩個偏移量構成，分別表示連接節點所隸屬的節點鏈表在索引鏈中的偏移位置和此連接節點在節點鏈表中的偏移位置。節點鏈表中的節點可以通過出點指針和出度在連接鏈表中找到一段連續的連接單元，這些單元存儲的節點地址就是本節點鄰接點的相對地址。因此，根據這些地址就可以連接本節點的所有鄰接節點。三叉鏈表基本結構及其相互關系如圖1所示。

2．3有向項集圖的構建算法

傳統的關聯規則挖掘算法利用的是橫向數據庫，橫向數據庫中的事務是一個二元組T=（Tid，itemset）。其中：Tid 是事務序列號，itemset是事務支持的項集。其計算候選項集的支持度是通過多次掃描數據庫來完成的。為了減少掃描數據庫次數，本文將傳統的橫向數據庫轉換為縱向數據庫形式。在縱向數據庫中數據被表示成如下的二元組（item，Tidlist）。其中：項item與支持它的一個事務列表Tidlist 相對應；Tidlist中保存的是相應的事務序列號Tid。

本文應用二進制編碼技術，定義了項的Tidlist 的長度與事務數據庫中的事務總數L相等，并用L個二進制位，即L/8個字節來表示一個Tidlist。每一個字節中的一個位的取值是0或1，分別對應著數據庫中相應的事務不支持或支持該項。這樣，計算候選項集支持數時只需要執行相對應的二進制位操作，代替了文件記錄的集合運算，有效地提高了計算效率和存儲效率。

由于1－頻繁項集升序排列可減少運算比較次數[5]，首先采用快速排序算法對所有滿足最小支持數要求的項（1－頻繁項集）按支持數升序方向進行排序；然后選擇第一個項作為首節點依次與其他項（節點）的Tidlist進行交操作（與運算）；如果運算結果滿足最小支持數要求，則是2－頻繁項集，有向邊連接兩節點。如此重復，查找出所有的2－頻繁項集，最后構建成有向項集圖。由于節點按支持數升序排列，有向項集圖中的有向邊由支持數低的節點指向支持數高的節點。有向項集圖的構建算法如算法1所示。

3基于有向項集圖的最大頻繁項集挖掘算法

完成有向項集圖構建后，關聯規則中最大頻繁項集的挖掘過程就已經完全轉換為對有向項集圖的遍歷過程。首先選擇首節點作為遍歷起始節點，出發訪問其鄰接點；然后再從此鄰接點出發進行類似的訪問，即訪問該鄰接點的鄰接點，直到末鄰接點或支持數不滿足要求時就挖掘出了一個最大頻繁項集。將挖掘出的最大頻繁項集保存到最大頻繁項集的集合中；然后返回上一層節點繼續進行類似的訪問。如果后續挖掘出的頻繁項集是已有最大頻繁項集的子集，則不保存到最大頻繁項集的集合中；反之，則保存。如此重復，依次從不同的有向項集圖起始出發節點開始遍歷，直到挖掘出所有的最大頻繁項集為止。在遍歷的同時，應用最大頻繁項集的約簡性質來優化和提高時空效率。基于有向項集圖的最大頻繁項集挖掘算法如算法2所示。

4實例分析

有一個稀疏事務數據庫如表1所示。其縱向數據庫形式如表2所示。當設定最小支持度為37.5%，即最小支持數為3時，事務數據庫中滿足最小支持度要求的項及其相應編碼如表3所示。應用有向項集圖的構建算法構建成的實例數據庫的有向項集圖如圖2所示，該有向項集圖的三叉鏈表式存儲結構如圖3所示。應用基于有向項集圖的最大頻繁項集挖掘算法遍歷該有向項集圖后，挖掘到了實例數據庫的一組頻繁項集，其按先后順序輸出為{B，E}、{D，E}、{C，A，E}。可見，這些頻繁項集是該實例數據庫的所有最大頻繁項集，并且實現了事務數據庫的一次掃描。

5特性分析

5．1存儲特性

如果有向項集圖有M個節點和N條邊，則三叉鏈表結構要存儲M個節點、N個連接地址和相對少數的索引單元。與現有的有向圖的存儲結構相比較，可節省存儲空間，存儲效率高。另一方面，對于有向圖的存儲，判斷到底

應用哪種形式的存儲結構，主要取決于該有向圖是稀疏圖還是稠密圖。但在實際應用中，由于無法預知大型數據庫數據結構轉換后的有向項集圖到底是稀疏圖還是稠密圖，無法給出統一存儲結構標準。三叉鏈表結構不受此影響。因此，三叉鏈表結構的提出可以真正規范大型有向圖的存儲結構標準。

5．2時間特性

算法在時間上的總代價包括兩個組成部分，即有向項集圖構建算法的時間代價和最大頻繁項集挖掘算法的時間代價。有向項集圖構建算法的時間代價主要取決于一次事務數據庫掃描過程中的二進制編碼與支持度計數，即取決于事務數據庫的事務總數L和數據項總數K。它的平均估計執行時間為O（L×K）。最大頻繁項集挖掘算法的時間代價主要取決于遍歷有向項集圖時的執行次數和項集Tidlist的交操作（與運算）。由于三叉鏈表存儲結構中的節點可以通過連接鏈表存儲的地址直接定位搜索，執行次數主要取決于最大頻繁項集的平均長度MFL和最大頻繁項集的個數MFN。它的平均估計執行時間為O（MFL×MFN）。項集Tidlist交操作（與運算）的時間由事務數據庫的事務總數L決定。如果將每一個tid的比較作為基本操作的話，并應用最優化的位串比較算法（如對半方法），它的平均估計執行時間是O（log L）。因此，整個算法的平均估計執行時間為O（L×K+MFL×MFN×log L）。

6結束語

發現最大頻繁項集是多種數據挖掘應用中的關鍵問題。本文提出的存儲結構及挖掘算法可以較好地滿足大型數據庫轉換數據結構后對有向項集圖的高效存儲要求，以及關聯規則中挖掘最大頻繁項集的高效時間要求，有效地解決了關聯規則挖掘中所遇到的技術難點，具有一定的理論價值和現實意義。

參考文獻：

［1］CHEN M S， HAN Jia－wei， YU P S. Data mining: an overview from database perspective [J].IEEE Transactions on Knowledge and Data Engineering， 1996，8(6):866-883.

［2］許卓群，楊冬青，唐世渭，等.數據結構與算法[M].北京: 高等教育出版社，2005：254-270.

［3］LEI Wen， LI Min－qiang. A new association rules mining algorithms based on directed itemsets graph[C]//Proc of the 9 th Int’l Conf RSFDGrc. 2003:660-664.

［4］宋志平，李應紅，屈裕安.大型有向圖的三叉鏈表式存儲結構[J].計算機工程與應用，2002，38(21):39-41.

［5］黃建設. 一種改進的關聯規則算法探討[J]. 計算機仿真，2005，22(12):72-75.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”