基于圖論的最大頻繁項(xiàng)集挖掘

摘要：利用有向項(xiàng)集圖來存儲(chǔ)事務(wù)數(shù)據(jù)庫中有關(guān)頻繁項(xiàng)集的信息，提出了有向項(xiàng)集圖的三叉鏈表式存儲(chǔ)結(jié)構(gòu)和基于有向項(xiàng)集圖的最大頻繁項(xiàng)集挖掘算法。它不僅實(shí)現(xiàn)了事務(wù)數(shù)據(jù)庫的一次掃描，減少了I/O代價(jià)，而且可以同時(shí)解決好稀疏數(shù)據(jù)庫和稠密數(shù)據(jù)庫的最大頻繁項(xiàng)集挖掘問題。

關(guān)鍵詞：數(shù)據(jù)挖掘； 關(guān)聯(lián)規(guī)則； 最大頻繁項(xiàng)集； 有向項(xiàng)集圖； 三叉鏈表式存儲(chǔ)結(jié)構(gòu)； 挖掘算法

中圖分類號(hào)：TP311.13文獻(xiàn)標(biāo)志碼：A

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

數(shù)據(jù)挖掘也稱數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)，是從大型數(shù)據(jù)庫中發(fā)現(xiàn)潛在的、新穎的、有價(jià)值的、能被用戶理解的概念和信息的過程。在數(shù)據(jù)挖掘研究中，關(guān)聯(lián)規(guī)則挖掘是一個(gè)非常重要的研究內(nèi)容[1]；

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

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

2．2三叉鏈表式存儲(chǔ)結(jié)構(gòu)

有向項(xiàng)集圖的三叉鏈表式存儲(chǔ)結(jié)構(gòu)由索引鏈表、節(jié)點(diǎn)鏈表和連接鏈表三類鏈表構(gòu)成。索引鏈表是主鏈表，有且只有一個(gè)。其每個(gè)索引單元均與一個(gè)節(jié)點(diǎn)鏈表和一個(gè)連接鏈表相關(guān)聯(lián)，從而構(gòu)成了一個(gè)以索引鏈表為主鏈表，以若干節(jié)點(diǎn)鏈表和連接鏈表為枝杈的三叉型存儲(chǔ)結(jié)構(gòu)[4]。 

索引鏈表是由索引單元組成的鏈表。索引單元按順序存儲(chǔ)，每個(gè)單元包括兩個(gè)鏈表指針和兩個(gè)整型量。兩個(gè)指針分別指向一個(gè)節(jié)點(diǎn)鏈表和一個(gè)連接鏈表；兩個(gè)整型量分別存儲(chǔ)了相應(yīng)兩類鏈表的長度信息。

節(jié)點(diǎn)鏈表存儲(chǔ)了一個(gè)有向項(xiàng)集圖的節(jié)點(diǎn)數(shù)據(jù)，它的單元就是節(jié)點(diǎn)，節(jié)點(diǎn)單元之間順序存儲(chǔ)。每個(gè)節(jié)點(diǎn)包括了本體數(shù)據(jù)域和連接關(guān)系域。對(duì)于有向項(xiàng)集圖來說，節(jié)點(diǎn)描述了事務(wù)數(shù)據(jù)庫中的1－頻繁項(xiàng)集模式，因而其本體數(shù)據(jù)域信息一般包括頻繁項(xiàng)名稱、支持頻繁項(xiàng)的Tidlist和支持?jǐn)?shù)；連接關(guān)系域包括一個(gè)指針和一個(gè)整型量，分別為出點(diǎn)指針和出度，指針指向連接鏈表的相應(yīng)連接單元。

連接鏈表單元存儲(chǔ)的是節(jié)點(diǎn)的相對(duì)地址。相對(duì)地址由兩個(gè)偏移量構(gòu)成，分別表示連接節(jié)點(diǎn)所隸屬的節(jié)點(diǎn)鏈表在索引鏈中的偏移位置和此連接節(jié)點(diǎn)在節(jié)點(diǎn)鏈表中的偏移位置。節(jié)點(diǎn)鏈表中的節(jié)點(diǎn)可以通過出點(diǎn)指針和出度在連接鏈表中找到一段連續(xù)的連接單元，這些單元存儲(chǔ)的節(jié)點(diǎn)地址就是本節(jié)點(diǎn)鄰接點(diǎn)的相對(duì)地址。因此，根據(jù)這些地址就可以連接本節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)。三叉鏈表基本結(jié)構(gòu)及其相互關(guān)系如圖1所示。

2．3有向項(xiàng)集圖的構(gòu)建算法

傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法利用的是橫向數(shù)據(jù)庫，橫向數(shù)據(jù)庫中的事務(wù)是一個(gè)二元組T=（Tid，itemset）。其中：Tid 是事務(wù)序列號(hào)，itemset是事務(wù)支持的項(xiàng)集。其計(jì)算候選項(xiàng)集的支持度是通過多次掃描數(shù)據(jù)庫來完成的。為了減少掃描數(shù)據(jù)庫次數(shù)，本文將傳統(tǒng)的橫向數(shù)據(jù)庫轉(zhuǎn)換為縱向數(shù)據(jù)庫形式。在縱向數(shù)據(jù)庫中數(shù)據(jù)被表示成如下的二元組（item，Tidlist）。其中：項(xiàng)item與支持它的一個(gè)事務(wù)列表Tidlist 相對(duì)應(yīng)；Tidlist中保存的是相應(yīng)的事務(wù)序列號(hào)Tid。

本文應(yīng)用二進(jìn)制編碼技術(shù)，定義了項(xiàng)的Tidlist 的長度與事務(wù)數(shù)據(jù)庫中的事務(wù)總數(shù)L相等，并用L個(gè)二進(jìn)制位，即L/8個(gè)字節(jié)來表示一個(gè)Tidlist。每一個(gè)字節(jié)中的一個(gè)位的取值是0或1，分別對(duì)應(yīng)著數(shù)據(jù)庫中相應(yīng)的事務(wù)不支持或支持該項(xiàng)。這樣，計(jì)算候選項(xiàng)集支持?jǐn)?shù)時(shí)只需要執(zhí)行相對(duì)應(yīng)的二進(jìn)制位操作，代替了文件記錄的集合運(yùn)算，有效地提高了計(jì)算效率和存儲(chǔ)效率。

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

3基于有向項(xiàng)集圖的最大頻繁項(xiàng)集挖掘算法

完成有向項(xiàng)集圖構(gòu)建后，關(guān)聯(lián)規(guī)則中最大頻繁項(xiàng)集的挖掘過程就已經(jīng)完全轉(zhuǎn)換為對(duì)有向項(xiàng)集圖的遍歷過程。首先選擇首節(jié)點(diǎn)作為遍歷起始節(jié)點(diǎn)，出發(fā)訪問其鄰接點(diǎn)；然后再從此鄰接點(diǎn)出發(fā)進(jìn)行類似的訪問，即訪問該鄰接點(diǎn)的鄰接點(diǎn)，直到末鄰接點(diǎn)或支持?jǐn)?shù)不滿足要求時(shí)就挖掘出了一個(gè)最大頻繁項(xiàng)集。將挖掘出的最大頻繁項(xiàng)集保存到最大頻繁項(xiàng)集的集合中；然后返回上一層節(jié)點(diǎn)繼續(xù)進(jìn)行類似的訪問。如果后續(xù)挖掘出的頻繁項(xiàng)集是已有最大頻繁項(xiàng)集的子集，則不保存到最大頻繁項(xiàng)集的集合中；反之，則保存。如此重復(fù)，依次從不同的有向項(xiàng)集圖起始出發(fā)節(jié)點(diǎn)開始遍歷，直到挖掘出所有的最大頻繁項(xiàng)集為止。在遍歷的同時(shí)，應(yīng)用最大頻繁項(xiàng)集的約簡(jiǎn)性質(zhì)來優(yōu)化和提高時(shí)空效率。基于有向項(xiàng)集圖的最大頻繁項(xiàng)集挖掘算法如算法2所示。

4實(shí)例分析

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

5特性分析

5．1存儲(chǔ)特性

如果有向項(xiàng)集圖有M個(gè)節(jié)點(diǎn)和N條邊，則三叉鏈表結(jié)構(gòu)要存儲(chǔ)M個(gè)節(jié)點(diǎn)、N個(gè)連接地址和相對(duì)少數(shù)的索引單元。與現(xiàn)有的有向圖的存儲(chǔ)結(jié)構(gòu)相比較，可節(jié)省存儲(chǔ)空間，存儲(chǔ)效率高。另一方面，對(duì)于有向圖的存儲(chǔ)，判斷到底

應(yīng)用哪種形式的存儲(chǔ)結(jié)構(gòu)，主要取決于該有向圖是稀疏圖還是稠密圖。但在實(shí)際應(yīng)用中，由于無法預(yù)知大型數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換后的有向項(xiàng)集圖到底是稀疏圖還是稠密圖，無法給出統(tǒng)一存儲(chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)。三叉鏈表結(jié)構(gòu)不受此影響。因此，三叉鏈表結(jié)構(gòu)的提出可以真正規(guī)范大型有向圖的存儲(chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)。

5．2時(shí)間特性

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

6結(jié)束語

發(fā)現(xiàn)最大頻繁項(xiàng)集是多種數(shù)據(jù)挖掘應(yīng)用中的關(guān)鍵問題。本文提出的存儲(chǔ)結(jié)構(gòu)及挖掘算法可以較好地滿足大型數(shù)據(jù)庫轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)后對(duì)有向項(xiàng)集圖的高效存儲(chǔ)要求，以及關(guān)聯(lián)規(guī)則中挖掘最大頻繁項(xiàng)集的高效時(shí)間要求，有效地解決了關(guān)聯(lián)規(guī)則挖掘中所遇到的技術(shù)難點(diǎn)，具有一定的理論價(jià)值和現(xiàn)實(shí)意義。

參考文獻(xiàn)：

［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］許卓群，楊冬青，唐世渭，等.數(shù)據(jù)結(jié)構(gòu)與算法[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］宋志平，李應(yīng)紅，屈裕安.大型有向圖的三叉鏈表式存儲(chǔ)結(jié)構(gòu)[J].計(jì)算機(jī)工程與應(yīng)用，2002，38(21):39-41.

［5］黃建設(shè). 一種改進(jìn)的關(guān)聯(lián)規(guī)則算法探討[J]. 計(jì)算機(jī)仿真，2005，22(12):72-75.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”