基于有序FP-tree結構和二維表的最大頻繁模式挖掘算法

王利軍，唐 立

（安徽經濟管理學院 信息工程系，安徽 合肥230031）

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

1 改進方案

1.1 有序FP-tree替代FP-tree

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

1.1.1 有序FP-tree概述

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

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

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

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

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

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

有序FP-tree項頭表中的事務項編號為1，2，3，n，最小支持度計數(shù)為minsup，根據(jù)有序FP-tree樹結構的特點，該樹結構具有幾個特性.

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

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

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

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

1.3 利用二維表格避免遞歸產生條件模式樹

1.3.1 挖掘最大頻繁項集的相關性質

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

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

證利用反證法和舉例法進行證明，存在g，h∈（1，m），且g＜h，假設 Dj{g}是 Dj{h}的真子集，則 Dj{h}包含的事務項編號必包含 Dj{g}的所有的事務項編號，如 Dj{h}為{1，3，4，6}，Dj{g}為{1，3，6}，根據(jù)有序 FP-tree 樹結構建樹規(guī)則要求在同一個父節(jié)點的子節(jié)點在插入時需要按照編號的大小升序依次排列，在插入Dj{g}中的事務編號6時，這個節(jié)點必在Dj{h}的事務編號4的右側，這樣Dj{h}表示的路徑必在Dj{g}的左側，即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}是最大頻繁項集，根據(jù)最大頻繁項集的任何真子集都不可能是最大頻繁項集，則Dj{h}不可能是最大頻繁項集.

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

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

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

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

1.3.2 初始化二維表

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

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

二維表第一部分的標題頭存放挖掘的事務項編號開始遞減到1，查找有序FP-tree中以挖掘的事務項結尾的路徑，按照從左到右的順序將所有路徑信息填入二維表格（路徑上包含節(jié)點則置1，否則為0），將結尾節(jié)點的支持度計數(shù)填入count1，直接將0填入count2；另外將上述路徑進行交集運算，將得到的結果無重復的也錄入二維表格（包含節(jié)點則置1，否則為0），直接將0填入count1和count2，至此二維表格初始化完成.

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

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

2 舉例說明

2.1 舉例生成有序FP-tree樹結構

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

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

圖1 有序FP-tree樹結構

2.2 利用二維表格挖掘最大頻繁項集

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

表2 事務編號6的初始化二維表

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

表3 挖掘后的二維表

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

3 算法性能測試

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

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

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

圖3 內存消耗比較

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