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

王利軍，唐 立

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

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

1 改進方案

1.1 有序FP-tree替代FP-tree

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

1.1.1 有序FP-tree概述

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

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

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

1.1.2 有序FP-tree與FP-tree的區別

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

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

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

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

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

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

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

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

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

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

定理2 若存在g，h∈（1，m），且g＜h，根據有序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}，根據有序 FP-tree 樹結構建樹規則要求在同一個父節點的子節點在插入時需要按照編號的大小升序依次排列，在插入Dj{g}中的事務編號6時，這個節點必在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}是最大頻繁項集，根據最大頻繁項集的任何真子集都不可能是最大頻繁項集，則Dj{h}不可能是最大頻繁項集.

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

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

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

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

1.3.2 初始化二維表

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

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

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

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

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

2 舉例說明

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

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

表1 事務數據庫D’

圖1 有序FP-tree樹結構

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

查看有序FP-tree樹結構發現最左最大分支為＜1，2，3＞，根據消除冗余策略挖掘時只需要從最后編號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∶3}，{A，B，C，E∶3}，{D∶3}}.

3 算法性能測試

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

表4 數據集信息

圖2 執行時間比較

圖3 內存消耗比較

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