石芹芹

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

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

石芹芹

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

0　引言

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

目前，極大頻繁項(xiàng)集挖掘算法主要是基于Apriori 和FP-tree的改良和衍生算法?；贏priori的有maxminer、pincer-search、Mafia、GenMax等，基于FP-tree的有Fpmax、IDMFIA、FPMFI等2。由于訪問(wèn)內(nèi)存中的數(shù)據(jù)比訪問(wèn)外存磁盤中相同大小的數(shù)據(jù)快五六個(gè)數(shù)量級(jí)，上述這些算法至少需要兩次外存數(shù)據(jù)庫(kù)掃描，其數(shù)據(jù)結(jié)構(gòu)表達(dá)形式也主要是枚舉樹(shù)、字典樹(shù)和頻繁模式樹(shù)（FP-tree）等樹(shù)形結(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ù)庫(kù)事務(wù)的集合，其中每個(gè)事務(wù)T是一個(gè)非空項(xiàng)集（項(xiàng)的集合稱為項(xiàng)集），使得T?τ。每一個(gè)事務(wù)T都有一個(gè)標(biāo)識(shí)符，成為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í)也稱為相對(duì)支持度），記為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)頻度，簡(jiǎn)稱為項(xiàng)集的頻度、支持度計(jì)數(shù)或計(jì)數(shù)，該支持度是絕對(duì)支持度。

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

定義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ù)庫(kù)，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，得到頻繁1項(xiàng)集的集合，記為L(zhǎng)1，第二遍掃描數(shù)據(jù)庫(kù)，通過(guò)L1找出頻繁2項(xiàng)集的集合L2，然后每一遍掃描數(shù)據(jù)庫(kù)，都通過(guò)Lk-1找出LK，直到不能找到頻繁K項(xiàng)集。在通過(guò)Lk-1找出LK時(shí)，根據(jù)先驗(yàn)性質(zhì)進(jìn)行剪枝。

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

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

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

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

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

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

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

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

②創(chuàng)建FP樹(shù)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表中沒(méi)有共享前綴，按照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)建的頻繁樹(shù)如圖1所示，該樹(shù)并沒(méi)有將非頻繁的項(xiàng)集剪枝，極大項(xiàng)集完全集M構(gòu)建過(guò)程如表2所示。

圖1　頻繁模式樹(shù)FP-tree

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

5　結(jié)語(yǔ)

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

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

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

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

［4］任永功，張亮，付玉.一種基于頻繁模式樹(shù)的最大頻繁項(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ù)樹(shù)的快速頻繁項(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ù)樹(shù)的最大頻繁項(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樹(shù)的極大頻繁項(xiàng)集的挖掘算法，該算法在構(gòu)建FP樹(shù)的過(guò)程中，通過(guò)子項(xiàng)集剪枝的方法，將挖掘到的極大頻繁項(xiàng)集存儲(chǔ)起來(lái)，從而節(jié)省再次挖掘FP樹(shù)的時(shí)間，較已有的算法在挖掘極大頻繁項(xiàng)集時(shí)簡(jiǎn)化挖掘過(guò)程。該算法的提出，為關(guān)聯(lián)規(guī)則的精簡(jiǎn)提供新的解決辦法。

極大頻繁項(xiàng)集；FP樹(shù)；關(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.