基于FP樹的極大頻繁項(xiàng)集的挖掘方法

石芹芹

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

基于FP樹的極大頻繁項(xiàng)集的挖掘方法

石芹芹

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0　引言

數(shù)據(jù)挖掘是20世紀(jì)90年代興起的一項(xiàng)新技術(shù)，是知識發(fā)現(xiàn)的關(guān)鍵步驟。數(shù)據(jù)挖掘是多門學(xué)科和多門技術(shù)相結(jié)合的產(chǎn)物，是指從數(shù)據(jù)庫中抽取隱含的、潛在的、先前未知的、有用的信息（如知識、規(guī)則、約束和規(guī)律等）的一個(gè)非平凡過程［1］。其中挖掘關(guān)聯(lián)規(guī)則是一個(gè)非常重要的研究內(nèi)容，而挖掘頻繁項(xiàng)集是研究關(guān)聯(lián)規(guī)則的基本和關(guān)鍵步驟。頻繁項(xiàng)集導(dǎo)致發(fā)現(xiàn)大型事務(wù)或關(guān)系數(shù)據(jù)集中項(xiàng)之間有趣的關(guān)聯(lián)或相關(guān)性，發(fā)現(xiàn)的這些相關(guān)聯(lián)系，可以為分類設(shè)計(jì)、交叉銷售和顧客購買習(xí)慣分析等許多商務(wù)決策過程提供幫助，故受到業(yè)界人士的青睞。然而從大型數(shù)據(jù)集中挖掘頻繁項(xiàng)集是具有很大的挑戰(zhàn)性的，因?yàn)閷γ恳粋€(gè)k維的頻繁項(xiàng)集個(gè)頻繁1項(xiàng)集個(gè)頻繁2項(xiàng)集因此頻繁項(xiàng)集總共為個(gè)，項(xiàng)集個(gè)數(shù)太大。而極大頻繁項(xiàng)集隱含了頻繁項(xiàng)集的信息，因此近些年對極大頻繁項(xiàng)集的研究也越來越多。

目前，極大頻繁項(xiàng)集挖掘算法主要是基于Apriori 和FP-tree的改良和衍生算法?；贏priori的有maxminer、pincer-search、Mafia、GenMax等，基于FP-tree的有Fpmax、IDMFIA、FPMFI等2。由于訪問內(nèi)存中的數(shù)據(jù)比訪問外存磁盤中相同大小的數(shù)據(jù)快五六個(gè)數(shù)量級，上述這些算法至少需要兩次外存數(shù)據(jù)庫掃描，其數(shù)據(jù)結(jié)構(gòu)表達(dá)形式也主要是枚舉樹、字典樹和頻繁模式樹（FP-tree）等樹形結(jié)構(gòu)，結(jié)構(gòu)較單一。

1　相關(guān)定義

定義1設(shè)τ=｛I1，I2，…，Im｝是項(xiàng)的集合，設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個(gè)事務(wù)T是一個(gè)非空項(xiàng)集（項(xiàng)的集合稱為項(xiàng)集），使得T?τ。每一個(gè)事務(wù)T都有一個(gè)標(biāo)識符，成為TID。設(shè)A是一個(gè)項(xiàng)集，當(dāng)A?T時(shí)，則稱事務(wù)T包含A。

定義2形如A?B（其中A?τ，B?τ，A≠?，B≠?，且A∩B≠?）的蘊(yùn)含式叫關(guān)聯(lián)規(guī)則。

定義3在事務(wù)D中規(guī)則A?B成立，則把D中事務(wù)包含A∪B的百分比叫做支持度（有時(shí)也稱為相對支持度），記為s，即support（A?B）=P（A∪B）。

定義4在事務(wù)D中規(guī)則A?B成立，則把D中事務(wù)包含A∩B（包含A的事務(wù)也同時(shí)包含B）的百分比叫做置信度，記為c，即confidence（A?B）=P（B|A）。

定義5同時(shí)滿足最小支持度閾值（min_sup）和最小置信度閾值（min_conf）的規(guī)則成為強(qiáng)規(guī)則。

定義6包含項(xiàng)集的事務(wù)數(shù)稱為項(xiàng)集的出現(xiàn)頻度，簡稱為項(xiàng)集的頻度、支持度計(jì)數(shù)或計(jì)數(shù)，該支持度是絕對支持度。

定義7如果項(xiàng)集I的相對支持度滿足預(yù)定義的最小支持度閾值 （即I的絕對支持度滿足對應(yīng)的最小支持度計(jì)數(shù)閾值），則I是頻繁項(xiàng)集。頻繁k項(xiàng)集的集合記為Lk。

定義8項(xiàng)集X是事務(wù)D中的頻繁項(xiàng)集，且不存在超項(xiàng)集Y使得X?Y且Y在D中也是頻繁的，則稱X是極大頻繁項(xiàng)集。

2　頻繁項(xiàng)集挖掘的兩大經(jīng)典算法

Apriori算法是在1994年由Agrawal和R.Srikant提出的一種為布爾關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集原創(chuàng)性算法。它使用逐層搜索的迭代方法，其中k項(xiàng)集用于探索（k+1）項(xiàng)集，其算法思想是：第一遍掃描數(shù)據(jù)庫，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，得到頻繁1項(xiàng)集的集合，記為L1，第二遍掃描數(shù)據(jù)庫，通過L1找出頻繁2項(xiàng)集的集合L2，然后每一遍掃描數(shù)據(jù)庫，都通過Lk-1找出LK，直到不能找到頻繁K項(xiàng)集。在通過Lk-1找出LK時(shí)，根據(jù)先驗(yàn)性質(zhì)進(jìn)行剪枝。

頻繁模式增長（Frequent-Pattern Growth），稱為FP算法，該算法采用分治策略，發(fā)現(xiàn)頻繁模式而不產(chǎn)生候選。其算法思想是：先將代表頻繁項(xiàng)集的數(shù)據(jù)庫壓縮到一顆頻繁模式樹（FP-tree）中，該樹能保留項(xiàng)集的關(guān)聯(lián)信息。再把壓縮后的數(shù)據(jù)庫劃分成一組條件數(shù)據(jù)庫，使每一個(gè)數(shù)據(jù)庫關(guān)聯(lián)一個(gè)頻繁項(xiàng)或者“模式段”，并分別挖掘每個(gè)條件數(shù)據(jù)庫。該算法分兩部分，第一部分是構(gòu)造FP樹，先創(chuàng)建樹的根節(jié)點(diǎn)，第二遍掃描數(shù)據(jù)庫D，對每個(gè)事務(wù)中的項(xiàng)按遞減支持度計(jì)數(shù)排序，為其創(chuàng)建一個(gè)分枝，如果當(dāng)前分枝與樹的已有分枝有共同路徑，則共享路徑前綴；第二部分是挖掘FP樹，由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基，然后構(gòu)造它的條件FP樹，并遞歸地在該樹上進(jìn)行挖掘。

兩大算法中Apriori算法的候選產(chǎn)生-檢查方法顯著壓縮了候選項(xiàng)集的規(guī)模，能產(chǎn)生很好的性能，卻仍可能需要產(chǎn)生大量的候選項(xiàng)集，過程中需要重復(fù)地掃描整個(gè)數(shù)據(jù)庫，因此挖掘出全部的頻繁項(xiàng)集需要花費(fèi)較昂貴的代價(jià)。FP-growth算法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換成在較小的條件數(shù)據(jù)庫中遞歸地搜索一些較短模式，顯著地降低了搜索開銷，但當(dāng)數(shù)據(jù)庫很大時(shí)，構(gòu)造基于主存的FP樹有時(shí)是不現(xiàn)實(shí)的。

3　基于FP樹的極大頻繁項(xiàng)集的挖掘方法

我們看到，頻繁模式挖掘可能產(chǎn)生大量的頻繁項(xiàng)集，特別是當(dāng)最小支持度閾值設(shè)置較小或者數(shù)據(jù)集中存在長模式時(shí)尤其如此。而實(shí)際中，有的時(shí)候只需要挖掘出極大頻繁模式的集合，而不是所有頻繁模式的集合。

在一個(gè)新的頻繁項(xiàng)集導(dǎo)出之后，要對其進(jìn)行超集檢查和子集檢查，檢查新發(fā)現(xiàn)的項(xiàng)集是否是某個(gè)已經(jīng)發(fā)現(xiàn)的、極大項(xiàng)集的子集。這些檢查可以在構(gòu)建FP樹時(shí)完成。

算法思路：（1）先掃描一遍數(shù)據(jù)庫，導(dǎo)出頻繁1項(xiàng)集的集合，并按照它們的支持度計(jì)數(shù)降序排列；（2）構(gòu)建極大頻繁項(xiàng)集候選集列表，第二遍掃描數(shù)據(jù)庫，構(gòu)造FP-tree，在對每個(gè)事務(wù)創(chuàng)建分支時(shí)，若當(dāng)前事務(wù)的分支與已存在的事務(wù)分支完全重合，則說明該事務(wù)是已發(fā)現(xiàn)的極大頻繁項(xiàng)集的子集，不應(yīng)被導(dǎo)出，否則存入候選集列表中。

算法：基于FP樹的挖掘極大頻繁項(xiàng)集的算法輸入：DB：事務(wù)數(shù)據(jù)庫；msup：最小支持度閾值輸出：極大頻繁項(xiàng)集的完全集M步驟構(gòu)造極大頻繁項(xiàng)集的FP樹

①掃描事務(wù)數(shù)據(jù)庫DB一次，導(dǎo)出滿足msup的頻繁項(xiàng)集合，保存它們的支持度計(jì)數(shù)，并按支持度計(jì)數(shù)降序排列，得到頻繁項(xiàng)列表L，L中每項(xiàng)包括item-name、count；

②創(chuàng)建FP樹tree的根節(jié)點(diǎn) “null”。每個(gè)節(jié)點(diǎn)有parent，child，item-name，count屬性；

③創(chuàng)建極大頻繁項(xiàng)候選列表M，初始為空；

④CreatTree（）｛

排序Ti中的項(xiàng)，得到Ti的頻繁項(xiàng)列表為［p|P］；//如果Ti在M表中沒有共享前綴，按照L的次序排列，反之按M中的順序排列；p是第一個(gè)項(xiàng)元素，P是剩余項(xiàng)元素

If each p in Ti is in Mi；//如果當(dāng)前事務(wù)T所有項(xiàng)集已在M中出現(xiàn)，那么此不是極大頻繁項(xiàng)集候選，刪除該事務(wù)集中的所有項(xiàng)

4　算法應(yīng)用結(jié)果

假設(shè)某商店的事務(wù)數(shù)據(jù)如下表，最小支持度閾值msup=2。

表1　某商店的事務(wù)數(shù)據(jù)

全局頻繁1項(xiàng)集組成的集合是L1=｛A，B，C，D，E｝，排序之后得到的L為｛B：8，A:7，C:6，D:2，E:2｝，M=｛｝。根據(jù)L構(gòu)建的頻繁樹如圖1所示，該樹并沒有將非頻繁的項(xiàng)集剪枝，極大項(xiàng)集完全集M構(gòu)建過程如表2所示。

圖1　頻繁模式樹FP-tree

表2　極大頻繁項(xiàng)集候選每趟讀取事務(wù)之后的結(jié)果

5　結(jié)語

該算法基于FP樹，通過增加極大頻繁項(xiàng)集候選列表M，能夠準(zhǔn)確地從事務(wù)數(shù)據(jù)庫中挖掘出所有的最大頻繁項(xiàng)集，在每趟讀取事務(wù)項(xiàng)時(shí)，如果已被候選表中的項(xiàng)集包含，則不需要再記錄該頻繁項(xiàng)集，從而節(jié)省了時(shí)間，而最后得到的候選表M就是極大頻繁項(xiàng)集的集合。因候選表M是存在于內(nèi)存中，故計(jì)算機(jī)內(nèi)存大小對該算法有一定限制，在事務(wù)數(shù)據(jù)量不大時(shí)效果較好，但在事務(wù)數(shù)據(jù)量龐大時(shí)該算法不太理想。

［1］張德干，王曉曄.規(guī)則挖掘技術(shù)［M］.北京：科學(xué)出版社，2008：2.

［2］王黎明，趙輝.基于FP樹的全局最大頻繁項(xiàng)集挖掘算法［J］.計(jì)算機(jī)研究與發(fā)展，2007：445-451.

［3］何波.基于FP-tree的快速挖掘全局最大頻繁項(xiàng)集算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011-07：1547-1552.

［4］任永功，張亮，付玉.一種基于頻繁模式樹的最大頻繁項(xiàng)目集挖掘算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2010：317-321.

［5］Jiangwen Han，Micheline Kamber，Jian Pei.Data Mining Concepts and Techniques Third Edition［M］.北京：機(jī)械工業(yè)出版社，2012.7.

［6］阮幼林，李慶華，楊世達(dá).一種基于事務(wù)樹的快速頻繁項(xiàng)集挖掘與更新算法［J］.計(jì)算機(jī)科學(xué)，2005：2-5.

［7］崔海莉，袁兆山.一種快速發(fā)現(xiàn)最大頻繁項(xiàng)集的挖掘算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2006：11-16.

［8］張忠平，鄭為夷.基于事務(wù)樹的最大頻繁項(xiàng)集挖掘算法［J］.計(jì)算機(jī)工程，2009：97-100.

［9］宋晶晶，姜保慶，關(guān)麗霞.在單向FP-tree上挖掘最大頻繁項(xiàng)集［J］.現(xiàn)代計(jì)算機(jī)，2010：19-25.

Maximal Frequent Itemsets；FP-tree；Association Rules

Maximum Frequent Itemsets Mining Method Based on FP-tree SHI Qin-qin

（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2015）36-0007-04

10.3969/j.issn.1007-1423.2015.36.002

石芹芹（1990-），女，四川蓬溪人，碩士，碩士研究生，研究方向?yàn)閳D像處理與合成、數(shù)據(jù)挖掘

2015-11-17

2015-12-10

提出一種基于FP樹的極大頻繁項(xiàng)集的挖掘算法，該算法在構(gòu)建FP樹的過程中，通過子項(xiàng)集剪枝的方法，將挖掘到的極大頻繁項(xiàng)集存儲起來，從而節(jié)省再次挖掘FP樹的時(shí)間，較已有的算法在挖掘極大頻繁項(xiàng)集時(shí)簡化挖掘過程。該算法的提出，為關(guān)聯(lián)規(guī)則的精簡提供新的解決辦法。

極大頻繁項(xiàng)集；FP樹；關(guān)聯(lián)規(guī)則

Proposes an algorithm for mining maximum frequent itemsets based on frequent pattern tree.The algorithm is an algorithm in the process of building FP-tree by pruning children-set and storing maximum frequent itemsets，thereby saves time mining again FP-tree than existing algorithms during mining Maximum frequent itemsets.It is a new algorithm to search association rules.