H-mine算法

H-mine是一種基於記憶體、高效的頻繁模式挖掘算法，使用新的數據結構H-Struct，可以更快的遍歷數據。

基本介紹

• 中文名：H-mine
• 本質：挖掘算法

主要思想

傳統頻繁模式挖掘算法主要存在兩個問題：一是算法需要的記憶體大小是不可預測的並且當數據集規模增大時，需要的記憶體也會隨之劇增；二是在很多情況下算法效率是非常低或無法處理的，如密集型數據集、大量數據集。H-mine 算法一定程度上解決了上面提到的問題。理論上，H-mine 有多項式的空間複雜度，要比使用候選產生髮現頻繁項集和頻繁模式增長方法更加節約空間。H-mine 通過對數據進行分區，每次只挖掘一個分區最後將結果整合，極大的節約了記憶體並能處理更大規模數據集。實驗證明H-mine 算法有很好的可擴展性並且在任何情況下綜合性能都優於Apriori 算法和FP-growth 算法。

方法描述

同樣地，為了讓大家更好地理解該算法，我們也通過一個實例來說明H-mine算法的挖掘過程。下圖1的前面兩列是我們的示例事務資料庫TDB。假設最小支持度計數為min_sup=2。

圖1

與Apriori算法相同，首先掃描TDB一遍，找到並輸出頻繁1項集{a：3，c：3，d：4，e：3，g：2}，這裡a：3表示項a的支持度計數為3。用freq(X)表示項集X（每個X對應每一個事務資料庫）中的一組頻繁項，也就是X的頻繁項投影。每個事務的頻繁項投影如表1第3列所示，比如TID=100的事務，它原來的項為c，d，e，f，g，i，但是f和i均不為頻繁項，所以TID=100的事務的頻繁項投影為c，d，e，g。其他的以此類推。

根據字母順序將頻繁項排列（稱為F-list）：a-c-d-e-g，那么我們最後想要得到的完整的頻繁模式被分成5個子集：（1）那些包含項a的；（2）那些包含項c但是不包含項a的；（3）那些包含項d但是不包含項a也不包含項c的；（4）那些包含項e但是不包含項a、項c和項d的；（5）那些僅僅包含項g的。

根據上述的頻繁項投影可以得到H-struct，如圖1所示：所有在頻繁項投影中的項都根據F-list排序。例如T100的頻繁項投影被列為cdeg，每一個頻繁項的item-id和hyper-link（指針）都被存儲在H-struct中。

Header table H中有3個域：item-id，支持度計數和一個hyper-link（指針）。然後所有第一個項相同的事務會被指針鏈起來形成一個佇列，而這個佇列的頭就是header table H中的結點。比如，在Header table H中的項a是a-佇列的頭結點，它連結了事務200、300和400的頻繁線投影，因為這三個投影的第一個頻繁項均為a；類似地，事務100被連結到c-佇列，d-，e-和g-佇列是空的，因為沒有頻繁項投影以這些項開頭。

H-mine 算法流程

如圖2所示。

圖2