王利軍，唐 立

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

FPMax算法［1］是基于FP-tree［2］樹結(jié)構(gòu)的最大頻繁項(xiàng)集挖掘算法，該算法是一種深度優(yōu)先算法，通過遞歸構(gòu)建條件模式樹進(jìn)行挖掘直接獲得候選最大頻繁項(xiàng)集，檢測通過后存入一根最大頻繁項(xiàng)目樹中，提高了最大頻繁項(xiàng)集的存取速度.但FPMax算法仍存在一些問題，主要有幾個方面：（1）FP-tree中的每一個節(jié)點(diǎn)都需要6個域空間，分別存儲節(jié)點(diǎn)名稱、支持度計(jì)數(shù)、子節(jié)點(diǎn)的指針、父節(jié)點(diǎn)的指針、兄弟節(jié)點(diǎn)的指針、同名節(jié)點(diǎn)的指針，因此FP-tree結(jié)構(gòu)占用了較多的內(nèi)存空間.（2）項(xiàng)頭表中的除第一個事務(wù)項(xiàng)外的其他事務(wù)項(xiàng)都需要被挖掘，這樣會大大減少挖掘效率.（3）FPMax算法進(jìn)行最大頻繁模式［3］挖掘時需要遞歸創(chuàng)建產(chǎn)生大量的條件模式樹［4］，這些條件模式樹仍需要占用大量的空間資源，會影響挖掘的時間效率.（4）MFI-tree［5］是FPMax算法用來存儲已經(jīng)產(chǎn)生的最大頻繁模式的存儲結(jié)構(gòu)，并且在將候選最大頻繁項(xiàng)集加入MFI-tree之前，需要進(jìn)行超集檢測浪費(fèi)了一定時間資源，但其中一部分超集檢測是可以避免的［6］.

1 改進(jìn)方案

1.1 有序FP-tree替代FP-tree

針對FPMax算法在挖掘最大頻繁模式存在的問題，需要將FP-tree結(jié)構(gòu)進(jìn)行改進(jìn)，改進(jìn)后的存儲結(jié)構(gòu)與FP-tree具有相似的結(jié)構(gòu)，但具有單向有序性，它依舊完整地保存著頻繁項(xiàng)集的信息，在此存儲結(jié)構(gòu)的基礎(chǔ)上采用相關(guān)的策略可避免條件模式樹的產(chǎn)生，減少遍歷的節(jié)點(diǎn)個數(shù)和減少超集檢測的次數(shù).

1.1.1 有序FP-tree概述

有序FP-tree樹結(jié)構(gòu)［7］的項(xiàng)頭表包含事務(wù)項(xiàng)名稱、事務(wù)項(xiàng)編號和指向第一個節(jié)點(diǎn)的鏈接.項(xiàng)頭表的事務(wù)項(xiàng)名稱按照支持度計(jì)數(shù)的大小降序排列，支持度最大的事務(wù)項(xiàng)名稱使用編號1，其他事務(wù)項(xiàng)的編號依次遞增1，事務(wù)項(xiàng)名稱與編號一一對應(yīng)，方便后期生成最大頻繁模式后進(jìn)行轉(zhuǎn)換.

有序FP-tree中的每個節(jié)點(diǎn)只包含4個域空間，它們分別為number，count，horizontal，vertical.number域存放事務(wù)項(xiàng)編號；count域?yàn)槭聞?wù)項(xiàng)的支持度計(jì)數(shù)；horizontal域在建立樹結(jié)構(gòu)時指向兄弟節(jié)點(diǎn)，建樹完成后指向相同事務(wù)項(xiàng)編號的下一個節(jié)點(diǎn)，vertical域在建立樹結(jié)構(gòu)時指向第一個子節(jié)點(diǎn)，建樹完成后實(shí)現(xiàn)逆轉(zhuǎn)指向父節(jié)點(diǎn).

有序FP-tree的建立過程與FP-tree相似，區(qū)別在建立有序FP-tree過程中，同一個父節(jié)點(diǎn)的子節(jié)點(diǎn)在插入時需要按照編號的大小升序依次排列，這樣使得兄弟節(jié)點(diǎn)在樹結(jié)構(gòu)中是有序的，這樣的排列結(jié)構(gòu)可以為建樹過程中減少遍歷子節(jié)點(diǎn)的個數(shù)，提高了建樹的效率.樹結(jié)構(gòu)成型后，執(zhí)行指針逆轉(zhuǎn)指向父節(jié)點(diǎn)，最終完成有序FP-tree的建立.

1.1.2 有序FP-tree與FP-tree的區(qū)別

有序FP-tree比FP-tree更優(yōu)越，主要表現(xiàn)在幾個方面.（1）FP-tree每個節(jié)點(diǎn)中的name域在實(shí)際使用時使用字符串?dāng)?shù)據(jù)類型存儲事務(wù)名稱，而有序FP-tree每個節(jié)點(diǎn)中的number域則采用整數(shù)型數(shù)據(jù)類型存儲事務(wù)編號，字符串?dāng)?shù)據(jù)類型往往需要更大的存儲空間，整數(shù)型數(shù)據(jù)類型只在完成數(shù)據(jù)挖掘后才將事務(wù)項(xiàng)編號轉(zhuǎn)換成事務(wù)項(xiàng)名稱.（2）有序FP-tree的每個節(jié)點(diǎn)只包含4個域空間，而FP-tree的每個節(jié)點(diǎn)則需要包含6個域空間，因此有序FP-tree比FP-tree更節(jié)省空間，結(jié)合（1）和（2）中所述，有序FP-tree占用的內(nèi)存空間約為FP-tree的2/3.（3）有序FP-tree是單向的，有序FP-tree中只存在指向父節(jié)點(diǎn)的垂直指針和指向相同節(jié)點(diǎn)編號的水平指針.而FP-tree是雙向的，不僅在水平方向上存在雙向指向，并且在垂直方向上也存在雙向指向.（4）有序FP-tree的節(jié)點(diǎn)在水平方向和垂直方向上都是有序排列的.建樹過程可以利用水平方向上的有序性減少遍歷子節(jié)點(diǎn)的個數(shù)，加快建樹效率，而FP-tree樹結(jié)構(gòu)在子節(jié)點(diǎn)的插入步驟中沒有考慮排列的順序情況.有序FP-tree的有序性可以為后期挖掘最大頻繁項(xiàng)集時減少挖掘事務(wù)項(xiàng)的數(shù)量和避免沒必要的挖掘帶來便利，加快挖掘效率.

1.2 消除冗余策略可以減少挖掘的事務(wù)項(xiàng)個數(shù)

有序FP-tree項(xiàng)頭表中的事務(wù)項(xiàng)編號為1，2，3，n，最小支持度計(jì)數(shù)為minsup，根據(jù)有序FP-tree樹結(jié)構(gòu)的特點(diǎn)，該樹結(jié)構(gòu)具有幾個特性.

定義1 最左最大分支：若有序FP-tree樹結(jié)構(gòu)中存在從事務(wù)項(xiàng)編號1到某個節(jié)點(diǎn)所組成的項(xiàng)集{1，2，3，…，k}（k≤n）為頻繁項(xiàng)集，事務(wù)項(xiàng)編號是連續(xù)的，事務(wù)項(xiàng)編號k為后綴節(jié)點(diǎn)，并且該節(jié)點(diǎn)的支持度計(jì)數(shù)大于等于minsup，k的后續(xù)節(jié)點(diǎn)沒有k+1或者后續(xù)節(jié)點(diǎn)有k+1但支持度計(jì)數(shù)小于minsup，根據(jù)有序FP-tree樹結(jié)構(gòu)的有序性，則＜1，2，3，…，k＞組成路徑稱為最左最大分支.

定理1 若＜1，2，3，…，k＞（k≤n）組成路徑為最左最大分支，則{1，2，3，…，k}（k≤n）必為頻繁項(xiàng)集，根據(jù)頻繁項(xiàng)集的任何真子集都不可能是最大頻繁項(xiàng)集，因此{(lán)1，2，3…，k-1}的任何子集都不是最大頻繁項(xiàng)集.

證有序FP-tree與FP-tree樹在結(jié)構(gòu)上相似，＜1，2，3，…，k＞（k≤n）組成路徑是以事務(wù)項(xiàng)編號k為后綴節(jié)點(diǎn)的路徑，根據(jù)前綴路徑性質(zhì)，k的前綴路徑中的每個節(jié)點(diǎn)與k在該路徑上同時出現(xiàn)的次數(shù)正好等于k的支持度計(jì)數(shù)，{1，2，3，…，k}組成的項(xiàng)集的支持度計(jì)數(shù)為k的支持度計(jì)數(shù)，根據(jù)最左最大分支的定義可知，k的支持度計(jì)數(shù)必大于等于minsup，因此{(lán)1，2，3，…，k}項(xiàng)集必為頻繁項(xiàng)集；頻繁項(xiàng)集的任何真子集都不可能是最大頻繁項(xiàng)集，從而獲得以后綴節(jié)點(diǎn)為1，2，3，…，k-1的項(xiàng)集都不是最大頻繁項(xiàng)集，定理得證.

根據(jù)定理1得到消除冗余策略方案，具體內(nèi)容如下：若在有序FP-tree樹結(jié)構(gòu)中找到最左最大分支＜1，2，3，…，k＞（k≤n），則在后期的最大頻繁項(xiàng)集挖掘時，只需要從項(xiàng)頭表的最后一項(xiàng)n開始挖掘，挖掘到事務(wù)項(xiàng)編號k為止，而事務(wù)項(xiàng)編號1，2，3，…，k-1都不要挖掘，這樣就可以減少挖掘的事務(wù)項(xiàng)個數(shù)，加快挖掘最大頻繁項(xiàng)集的效率.

1.3 利用二維表格避免遞歸產(chǎn)生條件模式樹

1.3.1 挖掘最大頻繁項(xiàng)集的相關(guān)性質(zhì)

挖掘項(xiàng)頭表中事務(wù)項(xiàng)j的最大頻繁項(xiàng)集時，設(shè)在有序FP-tree樹結(jié)構(gòu)中以j為尾節(jié)點(diǎn)的路徑總數(shù)為m，則路徑表示為 Pj{i}（i∈（1，m）），Pj{1}為最左側(cè)路徑，Pj{m}為最右側(cè)路徑，路徑對應(yīng)的項(xiàng)集 Dj{i}（i∈（1，m））.

定理2 若存在g，h∈（1，m），且g＜h，根據(jù)有序FP-tree的有序性，則Dj{g}不可能是Dj{h}的真子集，而Dj{h}可能是Dj{g}的真子集.

證利用反證法和舉例法進(jìn)行證明，存在g，h∈（1，m），且g＜h，假設(shè) Dj{g}是 Dj{h}的真子集，則 Dj{h}包含的事務(wù)項(xiàng)編號必包含 Dj{g}的所有的事務(wù)項(xiàng)編號，如 Dj{h}為{1，3，4，6}，Dj{g}為{1，3，6}，根據(jù)有序 FP-tree 樹結(jié)構(gòu)建樹規(guī)則要求在同一個父節(jié)點(diǎn)的子節(jié)點(diǎn)在插入時需要按照編號的大小升序依次排列，在插入Dj{g}中的事務(wù)編號6時，這個節(jié)點(diǎn)必在Dj{h}的事務(wù)編號4的右側(cè)，這樣Dj{h}表示的路徑必在Dj{g}的左側(cè)，即h＜g，這樣與已知條件g＜h矛盾，Dj{g}不可能是Dj{h}的真子集得證；同理證得Dj{h}可能是Dj{g}的真子集.

定理3 若存在g，h∈（1，m），且g＜h和Dj{h}是Dj{g}的真子集.若Dj{g}是最大頻繁項(xiàng)集，根據(jù)最大頻繁項(xiàng)集的任何真子集都不可能是最大頻繁項(xiàng)集，則Dj{h}不可能是最大頻繁項(xiàng)集.

定理4 挖掘以j為尾節(jié)點(diǎn)的最大頻繁項(xiàng)集一定是在3種情況下產(chǎn)生：

第一種：Dj{i}（i∈（1，m））自身就是最大頻繁項(xiàng)集；

第二種：Dj{i}（i∈（1，m））自身不是最大頻繁項(xiàng)集，但其右側(cè)的以 j為尾節(jié)點(diǎn)的項(xiàng)集 Dj{t}，Dj{t}是 Dj{i}的子集，Dj{i}可能為最大頻繁項(xiàng)集；

第三種：可能存在 a，b，…，f∈（1，m），a，b，…f，互不相等，則 Dj{a}∩Dj…∩Dj{f}可能是最大頻繁項(xiàng)集.

1.3.2 初始化二維表

有序FP-tree樹中已經(jīng)包含了所有的最大頻繁項(xiàng)集信息，為了避免產(chǎn)生條件模式樹浪費(fèi)時間和空間，采用二維表保存挖掘事務(wù)項(xiàng)編號的所有路徑和交集，采用相應(yīng)計(jì)算方法直接得到最大頻繁項(xiàng)集，從而達(dá)到減少空間的浪費(fèi)，加快挖掘速度［8］.

二維表由三部分組成：第一部分存放以挖掘事務(wù)項(xiàng)編號的路徑及交集，第二部分存放支持度計(jì)數(shù)count1，該計(jì)數(shù)為挖掘的事務(wù)項(xiàng)編號在樹結(jié)構(gòu)中節(jié)點(diǎn)支持度計(jì)數(shù)，第三部分存放累計(jì)支持度計(jì)數(shù)count2，方便后期進(jìn)行累加計(jì)算生成最大頻繁項(xiàng)集.

二維表第一部分的標(biāo)題頭存放挖掘的事務(wù)項(xiàng)編號開始遞減到1，查找有序FP-tree中以挖掘的事務(wù)項(xiàng)結(jié)尾的路徑，按照從左到右的順序?qū)⑺新窂叫畔⑻钊攵S表格（路徑上包含節(jié)點(diǎn)則置1，否則為0），將結(jié)尾節(jié)點(diǎn)的支持度計(jì)數(shù)填入count1，直接將0填入count2；另外將上述路徑進(jìn)行交集運(yùn)算，將得到的結(jié)果無重復(fù)的也錄入二維表格（包含節(jié)點(diǎn)則置1，否則為0），直接將0填入count1和count2，至此二維表格初始化完成.

1.3.3 使用二維表格生成最大頻繁模式

從二維表的第1條記錄開始進(jìn)行判斷，若該記錄的count1與count2之和大于最小支持度計(jì)數(shù)，則進(jìn)行超集檢測符合要求則加入最大頻繁項(xiàng)集集合，根據(jù)定理3可知該記錄的所有真子集都不是最大頻繁項(xiàng)集，根據(jù)定理2則只需要向下查找該記錄的真子集位置，然后從二維表中刪除無需挖掘，從而減少了不必要的挖掘過程，并且減少了超集檢測；否則，將該記錄的真子集的count2值分別加上該記錄的count1.采用相同的方法逐行進(jìn)行判斷，二維表中所有記錄執(zhí)行完后即可得到最大頻繁項(xiàng)集.

2 舉例說明

2.1 舉例生成有序FP-tree樹結(jié)構(gòu)

設(shè)置最小支持度計(jì)數(shù)為3，對事務(wù)數(shù)據(jù)庫D進(jìn)行掃描刪除每個事務(wù)中非頻繁項(xiàng)并進(jìn)行排序，根據(jù)事務(wù)項(xiàng)的支持度大小進(jìn)行編號，整理后的數(shù)據(jù)庫D’見表1，采用上述建樹方法得到有序FP-tree樹結(jié)構(gòu)見圖1.

表1 事務(wù)數(shù)據(jù)庫D’

圖1 有序FP-tree樹結(jié)構(gòu)

2.2 利用二維表格挖掘最大頻繁項(xiàng)集

查看有序FP-tree樹結(jié)構(gòu)發(fā)現(xiàn)最左最大分支為＜1，2，3＞，根據(jù)消除冗余策略挖掘時只需要從最后編號6 開始挖掘，挖掘到編號 3 即可.以編號 6 為結(jié)尾的路徑有＜6，5，3，2，1＞和＜6，4，2＞，它們的交集為＜6，2＞，事務(wù)編號6的初始化二維表見表2.

表2 事務(wù)編號6的初始化二維表

挖掘完編號6得到的二維表格見表3，得到最大頻繁模式{6，2∶3}直接加入MFS.

表3 挖掘后的二維表

同理挖掘編號5得到最大頻繁模式{1，2，3，5∶3}，挖掘編號4得到最大頻繁模式{4∶3}，挖掘編號3得到最大頻繁模式{1，2，3∶3}，因該項(xiàng)集為{1，2，3，5∶3}的子集，故刪除.挖掘完編號 3 后即可結(jié)束挖掘，最終的最大頻繁項(xiàng)集集合為{{6，2∶3}，{1，2，3，5∶3}，{4∶3}}，還原成事務(wù)名稱{{B，F(xiàn)∶3}，{A，B，C，E∶3}，{D∶3}}.

3 算法性能測試

采用Order Table FPMAX和FPMax兩種不同的算法對相同數(shù)據(jù)庫集進(jìn)行挖掘比較，通過圖表的方式顯示挖掘的時間效率和空間使用情況，分析圖表驗(yàn)證Order Table FPMAX算法的優(yōu)越性.實(shí)驗(yàn)環(huán)境為CPU i5-6500@3.2 GHz，內(nèi)存4 G，64位windows7操作系統(tǒng)，程序采用JAVA編寫，JDK版本為1.8.實(shí)驗(yàn)使用的3個標(biāo)準(zhǔn)數(shù)據(jù)集見表4.

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

圖2 執(zhí)行時間比較

圖3 內(nèi)存消耗比較

Order Table FPMax和FPMax兩種算法在同一個數(shù)據(jù)集上采用相同的支持度閾值下挖掘得到的最大頻繁項(xiàng)集的內(nèi)容是一樣的，表明Order Table FPMAX算法的正確性.實(shí)驗(yàn)選用的三種數(shù)據(jù)集分別代表稀疏數(shù)據(jù)集、密集數(shù)據(jù)集和人工數(shù)據(jù)集，這兩種不同的算法在3種數(shù)據(jù)集上的執(zhí)行時間見圖2，在支持度閾值較大時，兩種算法的執(zhí)行時間相差不大，隨著支持度閾值的減少，Order Table FPMAX算法在執(zhí)行時間上的優(yōu)越性逐漸體現(xiàn)出來.內(nèi)存消耗情況見圖3，兩種算法都是隨著支持度閾值的減少而升高，支持度閾值越低時，Order Table FPMAX算法的內(nèi)存消耗明顯少于FPMax算法.Order Table FPMAX算法在3種類型的數(shù)據(jù)集上都具有較好的執(zhí)行效率，并且內(nèi)存消耗上也相對較少，因此Order Table FPMAX算法比FPMAX更加優(yōu)越.