基于有序FP-tree結(jié)構(gòu)和投影數(shù)據(jù)庫(kù)的最大頻繁模式挖掘算法

王利軍, 唐 立

(安徽經(jīng)濟(jì)管理學(xué)院 信息工程系, 安徽 合肥 230031)

0 引言

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的重要研究領(lǐng)域,挖掘頻繁模式是關(guān)聯(lián)規(guī)則中的重要內(nèi)容.1993年，Agrawal等人提出了挖掘頻繁模式的Apriori算法[1];2000年，Han等人提出了FP-growth算法[2],該算法是基于FP-tree樹(shù)結(jié)構(gòu)的挖掘算法[2].挖掘頻繁模式會(huì)產(chǎn)生大量的頻繁模式,隨著事務(wù)數(shù)據(jù)庫(kù)的增大和支持度閾值設(shè)置的較小時(shí),頻繁模式的規(guī)模會(huì)更大.

在實(shí)際應(yīng)用中,最大頻繁模式在某些領(lǐng)域更具有價(jià)值,并且最大頻繁模式包含了所有的頻繁模式信息,因此許多專家學(xué)者對(duì)最大頻繁模式的挖掘進(jìn)行了深入的研究,具有代表性的最大頻繁模式挖掘算法有MaxMiner[3]、MAFIA[4]、FP-Max[5]等.這些算法仍然存在改進(jìn)的空間,比如,FP-Max是基于FP-tree樹(shù)結(jié)構(gòu)的挖掘算法,樹(shù)結(jié)構(gòu)會(huì)長(zhǎng)期占用較大的系統(tǒng)資源,算法采用遞歸調(diào)用的方式挖掘數(shù)據(jù),執(zhí)行效率低下,因此盡量減少系統(tǒng)資源的的消耗和減少遞歸調(diào)用的次數(shù)成為加快FP-Max算法的執(zhí)行效率的首要問(wèn)題.本文將采用有序FP-tree替代FP-tree減少系統(tǒng)資源的浪費(fèi),并在此基礎(chǔ)上,采用垂直投影方案生成投影數(shù)據(jù)庫(kù),基于投影數(shù)據(jù)庫(kù)創(chuàng)建局部FP-tree從而進(jìn)一步減少空間資源的浪費(fèi),并且采用相應(yīng)的策略減少?zèng)]必要的挖掘過(guò)程,最終達(dá)到提高挖掘效率的目的.

1 問(wèn)題描述和改進(jìn)策略

1.1 問(wèn)題描述

FP-Max算法目前存在的問(wèn)題如下:

1) FP-tree樹(shù)結(jié)構(gòu)的每一個(gè)節(jié)點(diǎn)(除根節(jié)點(diǎn)外)都包含6個(gè)域,分別存放節(jié)點(diǎn)名、支持度計(jì)數(shù)、孩子節(jié)點(diǎn)的指針、父節(jié)點(diǎn)的指針、兄弟節(jié)點(diǎn)的指針、同名節(jié)點(diǎn)的指針.基于事務(wù)數(shù)據(jù)庫(kù)創(chuàng)建的初始FP-tree樹(shù)結(jié)構(gòu)在整個(gè)挖掘過(guò)程中一直存在,這樣將長(zhǎng)期占據(jù)系統(tǒng)空間資源.

2) FP-Max算法采用遞歸的挖掘方式,期間會(huì)產(chǎn)生大量的條件子樹(shù),這些條件子樹(shù)也是基于FP-tree樹(shù)結(jié)構(gòu)的,這樣并會(huì)加大對(duì)系統(tǒng)空間資源的消耗.若事務(wù)數(shù)據(jù)庫(kù)規(guī)模龐大或者支持度閾值較小時(shí),這種情況會(huì)更嚴(yán)重,可能會(huì)導(dǎo)致內(nèi)存溢出而無(wú)法正常挖掘.

3) 項(xiàng)頭表中的每個(gè)事務(wù)項(xiàng)都需要被挖掘,這樣會(huì)大大降低挖掘效率.系統(tǒng)資源的長(zhǎng)期占用,以及遞歸挖掘方式和創(chuàng)建條件子樹(shù)都會(huì)影響算法的整體執(zhí)行效率.

1.2 改進(jìn)策略

針對(duì)上述3個(gè)問(wèn)題,論文提出以下改進(jìn)策略:

策略1: 采用有序FP-Tree[6]代替FP-Tree,從而減少對(duì)系統(tǒng)空間資源的浪費(fèi);

策略2: 引入“分而治之”的思想,分解事務(wù)數(shù)據(jù)庫(kù)得到投影數(shù)據(jù)庫(kù),基于投影數(shù)據(jù)庫(kù)[3]創(chuàng)建局部樹(shù)結(jié)構(gòu),從而進(jìn)一步減少對(duì)系統(tǒng)空間資源的浪費(fèi);

策略3: 利用有序FP-Tree樹(shù)結(jié)構(gòu)的性質(zhì)減少挖掘次數(shù);

策略4: 采用優(yōu)化方案減少投影次數(shù)加快挖掘效率;

本文在改進(jìn)策略的基礎(chǔ)上提出了基于有序FP-Tree和投影數(shù)據(jù)庫(kù)的挖掘最大頻繁模式算法OPFP-MAX算法.

2 實(shí)現(xiàn)改進(jìn)策略

2.1 有序FP-tree替代FP-tree

有序FP-tree樹(shù)結(jié)構(gòu)的項(xiàng)頭表包含3個(gè)域,別為ItemName、ID和FirstLink.ItemName域存放事務(wù)項(xiàng)的名稱,按照支持度計(jì)數(shù)的大小降序排列;ID域存放編號(hào),從1開(kāi)始依次遞增1升序排列,事務(wù)項(xiàng)名稱與編號(hào)一一對(duì)應(yīng),方便后期生成最大頻繁模式后進(jìn)行轉(zhuǎn)換;FirstLink域指向第一個(gè)相應(yīng)事務(wù)項(xiàng)節(jié)點(diǎn)的位置.

有序FP-tree中的的每個(gè)節(jié)點(diǎn)只包含4個(gè)域空間,分別為NodeName,NodeCount,hLink,vLink.NodeName域存放節(jié)點(diǎn)的事務(wù)項(xiàng)名稱;NodeCount域存放節(jié)點(diǎn)的支持度計(jì)數(shù);hLink域在建立樹(shù)結(jié)構(gòu)時(shí)指向兄弟節(jié)點(diǎn),建樹(shù)完成后指向相同NodeName的下一個(gè)節(jié)點(diǎn)位置,vLink域在建立樹(shù)結(jié)構(gòu)時(shí)指向第一個(gè)孩子節(jié)點(diǎn),建樹(shù)完成后實(shí)現(xiàn)逆轉(zhuǎn)指向父節(jié)點(diǎn).有序FP-tree的建立過(guò)程中,同一個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)在插入時(shí)需要按照編號(hào)的大小升序依次排列,這樣的排列結(jié)構(gòu)可以為建樹(shù)過(guò)程中減少遍歷子節(jié)點(diǎn)的個(gè)數(shù),提高了建樹(shù)的效率.有序FP-tree的每個(gè)節(jié)點(diǎn)只包含4個(gè)域空間,占用的內(nèi)存空間約為FP-tree的2/3.有序FP-tree是單向的,有序FP-tree中只存在指向父節(jié)點(diǎn)的垂直指針和指向相同編號(hào)的水平指針.建樹(shù)過(guò)程可以利用水平方向上的有序性減少遍歷子節(jié)點(diǎn)的個(gè)數(shù),加快建樹(shù)效率,有序FP-tree的垂直方向上的有序性可以為后期挖掘最大頻繁項(xiàng)集時(shí)減少事務(wù)項(xiàng)的挖掘數(shù)量,加快挖掘效率.

2.2 引入“分而治之”的思想

FP-Max算法需要將事務(wù)數(shù)據(jù)庫(kù)的信息一次性裝載到FP-tree樹(shù)結(jié)構(gòu)形成初始FP-tree樹(shù)結(jié)構(gòu),如果事務(wù)數(shù)據(jù)庫(kù)較大,可能會(huì)因內(nèi)存溢出而無(wú)法進(jìn)行裝載,倘若可以一次性裝載成功,這樣勢(shì)必會(huì)長(zhǎng)期占用較大的系統(tǒng)空間資源,即使已經(jīng)使用有序FP-tree替代FP-tree,但仍然是一筆不小的開(kāi)銷.為了解決這一問(wèn)題,我們引入了“分而治之”的思想,它是將事務(wù)數(shù)據(jù)庫(kù)采用某種方案進(jìn)行分解形成一系列較小的數(shù)據(jù)庫(kù),我們稱這些較小的數(shù)據(jù)庫(kù)為投影數(shù)據(jù)庫(kù),然后基于投影數(shù)據(jù)庫(kù)再形成的局部FP-tree[7],若有必要可遞歸投影并挖掘.

最大頻繁模式存放在MFS集合中,若頻繁1-項(xiàng)集的事務(wù)編號(hào)列表為1、2、3、4、5,令MFS|1為以事務(wù)編號(hào)1為結(jié)尾的最大頻繁模式的集合,以此類推,則MFS=MFS|1∪MFS|2∪MFS|3MFS|4∪MFS|5,挖掘最大頻繁模式可以轉(zhuǎn)換成挖掘以這些事務(wù)編號(hào)為結(jié)尾的最大頻繁模式,因此可以采用分治策略.

事務(wù)數(shù)據(jù)庫(kù)的分解方案很多,比如并行投影方案[8]和垂直投影方案[9]等.使用不同的分解方案得到的投影數(shù)據(jù)庫(kù)的事務(wù)內(nèi)容也不盡相同,本文采用的分解方案為垂直投影方案.

在采用垂直投影方案之前需對(duì)事務(wù)數(shù)據(jù)庫(kù)D進(jìn)行如下處理:第一次掃描事務(wù)數(shù)據(jù)庫(kù)D得到全局項(xiàng)頭表L{x1,x2,…,xn-1,xn},項(xiàng)頭表中采用降序的方式存放頻繁1-項(xiàng)集,L的事務(wù)項(xiàng)總數(shù)為n,x1為支持度計(jì)數(shù)最高的事務(wù)項(xiàng),xn為支持度計(jì)數(shù)最低的事務(wù)項(xiàng),刪除事務(wù)數(shù)據(jù)庫(kù)D的每個(gè)事務(wù)中的非頻繁項(xiàng),并將每個(gè)事務(wù)中的事務(wù)項(xiàng)按照L中支持度計(jì)數(shù)降序排序.這樣得到預(yù)處理事務(wù)數(shù)據(jù)庫(kù)D1.

定義1 垂直投影方案 首先根據(jù)L的事務(wù)項(xiàng)總數(shù)n創(chuàng)建一個(gè)堆棧組Z{x1,x2,…,xn-1,xn},根據(jù)D1中的事務(wù)的最后事務(wù)項(xiàng)進(jìn)行分組,將以x1為最后事務(wù)項(xiàng)的事務(wù)去除x1后分配到堆棧x1中,以此類推,這樣既可得到初始投影數(shù)據(jù)庫(kù),然后從堆棧xn開(kāi)始獲取投影數(shù)據(jù)庫(kù)信息構(gòu)建局部FP-tree,并進(jìn)行挖掘若有必要可遞歸挖掘得到局部模式,挖掘完成后將堆棧zn中每一個(gè)事務(wù),繼續(xù)采用垂直投影到其他堆棧(除堆棧zn),接著基于堆棧zn-1中投影數(shù)據(jù)庫(kù)構(gòu)建局部FP-tree繼續(xù)挖掘,挖掘完成后將堆棧zn-1中每一個(gè)事務(wù),繼續(xù)采用垂直投影到其他堆棧(除堆棧zn和zn-1),采用相同的方式直到堆棧z1的投影數(shù)據(jù)庫(kù)也被挖掘,算法執(zhí)行完畢,合并所有的局部頻繁模式.

2.3 減少挖掘策略可以減少挖掘的事務(wù)編號(hào)個(gè)數(shù)

有序FP-tree的事務(wù)項(xiàng)編號(hào)為1,2,3,…,n,根據(jù)有序FP-tree樹(shù)結(jié)構(gòu)的特點(diǎn),該樹(shù)結(jié)構(gòu)具有如下特性.

定義2 若從根節(jié)點(diǎn)向下查找,從事務(wù)編號(hào)1開(kāi)始找到連續(xù)的事務(wù)編號(hào)直至k所組成的路徑<1,2,3,…,k>(k≤n),k的支持度計(jì)數(shù)大于等于最小支持度minsup,k不存在后續(xù)節(jié)點(diǎn)或后續(xù)節(jié)點(diǎn)支持度計(jì)數(shù)小于minsup,則<1,2,3,…,k>組成路徑必為最左最大分支,該路徑所形成的項(xiàng)集{1,2,3,…,k}必為頻繁項(xiàng)集.根據(jù)頻繁項(xiàng)集的任何真子集都不可能是最大頻繁項(xiàng)集,因此{(lán)1,2,3,…,k-1}的任何子集都不是最大頻繁項(xiàng)集.

減少挖掘策略:若找到最左最大分支<1,2,3,…,k>(k≤n),則在挖掘最大頻繁項(xiàng)集時(shí),只需要從項(xiàng)頭表的最后一項(xiàng)n開(kāi)始挖掘,直至事務(wù)項(xiàng)編號(hào)k,而事務(wù)項(xiàng)編號(hào)1,2,3,…,k-1都無(wú)需挖掘,從而達(dá)到減少挖掘的事務(wù)項(xiàng)個(gè)數(shù),加快挖掘效率的目的.

2.4 采用優(yōu)化方案減少投影次數(shù)加快挖掘效率

在減少挖掘策略的基礎(chǔ)上,我們可以繼續(xù)采用優(yōu)化方案來(lái)加快挖掘效率,具體描述如下:在挖掘項(xiàng)頭表中事務(wù)編號(hào)w(k≤w≤n)得到的候選最大頻繁項(xiàng)集,若該候選最大頻繁項(xiàng)集不是MFS的子集,則存入最大頻繁項(xiàng)集集合.立即形成項(xiàng)集{1,2,3,…,w-1},檢測(cè)該項(xiàng)集是否是最大頻繁項(xiàng)集集合中某一個(gè)項(xiàng)集的子集,如果是,則挖掘算法可以終止,因?yàn)殡S后挖掘肯定不會(huì)得到新的最大頻繁項(xiàng)集,因此無(wú)需再投影和挖掘,從而達(dá)到減少投影次數(shù)加快挖掘效率的目的.

3 舉例

3.1 生成初始投影數(shù)據(jù)庫(kù)

設(shè)置最小支持度計(jì)數(shù)為2,掃描事務(wù)數(shù)據(jù)庫(kù)D刪除每個(gè)事務(wù)中非頻繁項(xiàng)并采用降序排序,進(jìn)行編號(hào)得到預(yù)處理事務(wù)數(shù)據(jù)庫(kù)D1如表1所示:

表1 預(yù)處理事務(wù)數(shù)據(jù)庫(kù)D1

采用垂直投影方案對(duì)D1中的編號(hào)列表進(jìn)行操作生成初始投影數(shù)據(jù)庫(kù),堆棧6中的項(xiàng)目包含了所有事務(wù)編號(hào)6的事務(wù),其他堆棧暫時(shí)不完整.堆棧中的項(xiàng)目的演變過(guò)程如表2所示.

3.2 創(chuàng)建局部FP-tree樹(shù)進(jìn)行挖掘

基于堆棧創(chuàng)建局部FP-tree樹(shù)后,首先獲取最左最大分支,若符合要求可采用減少挖掘策略減少挖掘的事務(wù)編號(hào)個(gè)數(shù),從而加快挖掘效率.

堆棧6中保存的項(xiàng)目是事務(wù)編號(hào)6的條件模式基,因?yàn)樗幸允聞?wù)編號(hào)6為結(jié)尾的事務(wù)經(jīng)過(guò)處理后都保存在堆棧6中了.基于堆棧6創(chuàng)建事務(wù)編號(hào)6的條件FP-tree樹(shù)FP-tree|6,該樹(shù)只包含單路徑<2,3,4:2>,故直接獲得候選最大頻繁模式{2,3,4,6:2},此時(shí)的MFS為空,{2,3,4,6:2}直接加入MFS.將堆棧6的項(xiàng)目繼續(xù)采用垂直投影方案繼續(xù)投影,使得堆棧4中增加了<1,2,3>和<2,3>兩個(gè)項(xiàng)目,此時(shí)可以刪除堆棧6減少空間的浪費(fèi).

開(kāi)始對(duì)堆棧5進(jìn)行挖掘,構(gòu)建局部FP-tree樹(shù)FP-tree|5,該樹(shù)只包含單路徑<1:2>,故可以直接獲得候選最大頻繁模式{1,5:2},檢測(cè)MFS后,加入MFS.將堆棧5的項(xiàng)目繼續(xù)采用垂直投影方案繼續(xù)投影后,刪除堆棧5.

挖掘堆棧4,生成局部FP-tree樹(shù)FP-tree|4,該樹(shù)不是單路徑,需要遞歸挖掘,發(fā)現(xiàn)事務(wù)編號(hào)3的條件模式基為{1,2:1}和{2:1},直接生成局部FP-tree樹(shù)FP-tree|3-4為單路徑,獲得候選最大頻繁模式{2,3,4:2},該項(xiàng)集為MFS中{2,3,4,6:2}的子集故舍棄,同理獲得事務(wù)編號(hào)2和1的最大頻繁模式分別為{2,4:2}和{1,4:2},因{2,4:2}是MFS的子集故舍棄,{1,4:2}符合要求加入MFS,堆棧4挖掘完畢.繼續(xù)投影后刪除堆棧4.

同理挖掘堆棧3獲得候選最大頻繁模式{1,2,3:2},檢測(cè)后可加入MFS.

至此算法結(jié)束,根據(jù)優(yōu)化策略發(fā)現(xiàn)項(xiàng)集{1,2}是MFS中{1,2,3:2}的子集,故堆棧1和堆棧2不用再繼續(xù)投影挖掘.

表2 投影數(shù)據(jù)庫(kù)演變過(guò)程

最終,MFS中的最大頻繁模式為{2,3,4,6:2}、{1,5:2}、{1,4:2}和{1,2,3:2}.

4 算法性能測(cè)試

采用OPFP-MAX和FP-Max兩種不同的算法對(duì)相同數(shù)據(jù)庫(kù)集進(jìn)行挖掘比較,通過(guò)圖表的方式顯示挖掘的時(shí)間效率和空間使用情況,分析圖表驗(yàn)證OPFP-MAX算法的優(yōu)越性.

表3 數(shù)據(jù)集信息

OPFP-MAX和FP-Max兩種不同的算法在兩種數(shù)據(jù)集上的執(zhí)行時(shí)間和內(nèi)存消耗情況分別如圖1和圖2所示,OPFP-MAX算法在兩種類型的數(shù)據(jù)集上都具有較好的執(zhí)行效率,并且內(nèi)存消耗上也相對(duì)較少,因此OPFP-MAX算法比FP-Max更加優(yōu)越.

a.Retail數(shù)據(jù)集執(zhí)行時(shí)間比較圖 b.Pumsb數(shù)據(jù)集執(zhí)行時(shí)間比較圖圖1 執(zhí)行時(shí)間比較圖

a.Retail數(shù)據(jù)集內(nèi)存消耗比較圖 b.Pumsb數(shù)據(jù)集內(nèi)存消耗比較圖圖2 內(nèi)存消耗比較圖

5 結(jié)論

本文提出的基于有序FP-tree結(jié)構(gòu)和投影數(shù)據(jù)庫(kù)的最大頻繁項(xiàng)集挖掘算法OPFP-MAX,該算法不僅可以減少空間資源的浪費(fèi),還利用有序FP-tree的特點(diǎn)加快建樹(shù)效率且減少了挖掘事務(wù)編號(hào)的個(gè)數(shù),再結(jié)合優(yōu)化策略減少投影次數(shù),最終達(dá)到加快挖掘效率的目的.但算法還是基于FP-tree樹(shù)結(jié)構(gòu)的,并且仍采用遞歸方式進(jìn)行挖掘的,下一步的工作是直接通過(guò)事務(wù)數(shù)據(jù)庫(kù)在不創(chuàng)建FP-tree樹(shù)結(jié)構(gòu)的基礎(chǔ)上采用相應(yīng)的方案獲得最大頻繁模式.