【正文】 _name的節(jié)點通過 node_link被連結(jié)在一起 . Header table item head of node_link f c a b m p root f : 4 c :1 c : 3 a : 3 m : 2 p : 2 m : 1 b : 1 b : 1 p : 1 b : 1 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) ８ 圖 2 FPtree 是一個壓縮的數(shù)據(jù)結(jié)構(gòu) ,它用較少的空間存儲了后面頻繁集挖掘所需要的全部信息 . 算法二建立在算法一所產(chǎn)生的 Ftree 上面 .它會遞歸調(diào)用自己 ,并且反復(fù)調(diào)用算法一產(chǎn)生新的 FPtree. 輸入 :一棵用算法一建立的樹 Tree 輸出 :所有的頻繁集 步驟 : 調(diào)用 FPgrowth(Tree,null). 下面是對過程 FPgrowth 的偽碼描述 . Procedure FPgrowth(Tree,α) { if Tree 只有一條路徑 P then 對 P 中的節(jié)點的每一個組合 (記為 β)做 (1) (1) 產(chǎn)生頻繁集 β?α,并且把它的支持度指定為 β中節(jié)點的最小支持度 . else 對 Tree 的頭表從表尾到表頭的每一個表項 (記為 a)做 (2)(5) (2) 產(chǎn)生頻繁集 β=a?α,并且支持度為 a 的支持度 (3) 建立 β的條件模式庫 (conditional pattern base)和 β的條件樹 (conditional FPtree)Tree2 (4) if Tree2!=? (5) then 調(diào)用 FPgrowth(Tree2,β) } 關(guān)于什么是條件模式庫 (conditional pattern base)和條件樹 (conditional FPtree),我們繼續(xù)上面那個例子來介紹 . 我們把圖 2 中已經(jīng)得到的 FPtree 和相應(yīng)的頭表作為算法二的輸入 .按照從表尾到表頭的順序考察表中的每一個表項 . 從表項 p 出發(fā) ,先可以得到一個頻繁集 (p:3).然后 ,我們可以得到包含 p 的所有模式 .順著 p表項的 node_link域 ,我們找到所有包含 p的路徑 f:4,c:3,a:3,m:2,p:2和 c:1,b:1,p:1.對第一條路徑 ,雖然 f 出現(xiàn)了 3 次 ,c 和 a 各出現(xiàn)了兩次 ,但它們同 p 在一起只出現(xiàn)了 2 次 ,所以把它們 的計數(shù)改為 2,得到 f:2,c:2,a:2,m:2,p:2.第二條路徑中各項的計數(shù)都已相同 ,不用修改了 .把這 2條路徑中的 p項去掉 ,就得到了 p的條件模式庫 ,{(f:2,c:2,a:2,m:2),(c:1,b:1)},這是下一步遞歸的依據(jù) .我們把這個條件模式庫看作一個數(shù)據(jù)庫 ,在上面運用算法一產(chǎn)生一個新的 FPtree,這就是算法二中的條件樹 ,這個新樹只有一個節(jié)點 (c:3).這時又得到一個新的頻繁集 (cp:3).包含 p項的頻繁集就挖掘完了 . 接著考察 m,先還是得到 (m:3).順著它的 node_link 得到 2 條路 徑 f:4,c:3,a:3,m:2和f:4,c:3,a:3,b:1,m:1.這時 ,不需要考慮 p 項了 ,因為含有它的頻繁集都已經(jīng)產(chǎn)生完畢了 .按照上面的做法 ,得到一個條件模式庫 {(f:2,c:2,a:3),(f:1,c:1,b:1,m:1)}.我們在上面構(gòu)建條件樹 ,得到f:3,c:3,a:3,這是一棵只有一條路徑的 繁集 ,得到 {(am:3),(cm:3),(acm:3),(fm:3),(fam:3),(fcm:3),(fcam:3)}. 類似的 ,表項 b產(chǎn)生一個頻繁集 (b:3)和 3條路徑 f:4,c:3,a:3,b:1,f:4,b:1,和 c:1,b:1.同樣的 ,這里也不在考慮項 p和項 m 了 .b的條件模式庫 {(f:1,c:1,a:1),(f:1,b:1),(c:1,b:1)},在這個條件一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) ９ 模式庫上面運用算法一 ,得到一棵空樹 ,對含有 b 的頻繁集的挖掘到此為止 . 表 2 和圖 2 顯示了算法二的部分執(zhí)行過程 . item conditional pattern base conditional FPtree p {(f:2,c:2,a:2,m:2),(c:1,b:1)} {(c:3)}|p m {(f:2,c:2,a:2),(f:1,c:1,a:1,b:1)} {(f:3,c:3,a:3)}|m b {(f:1,c:1,a:1),(f:1),(c:1)} ? a {(f:3,c:3)} {(f:3,c:3)}|a c {(f:3)} {(f:3)}|c f ? ? 表 2 (f:2,c:2,a:2) (f::1,a::1) ?m?的條件模式庫 頭表 item head of node_links f c a 算法一產(chǎn)生的 FPtree 圖 2 root f : 4 c : 1 c : 3 a : 3 m :2 p : 2 m :1 b : 1 b : 1 p : 1 b : 1 root f:3 c:3 a:3 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １０ 數(shù)據(jù)結(jié)構(gòu) 對應(yīng)于算法描述中所出現(xiàn)的各個對象分別定義了一些數(shù)據(jù)結(jié)構(gòu) .下面予以分別介紹 .(有關(guān)代碼的清單只列出重要部分，如類中的普通的構(gòu)造函數(shù)之類就不予詳細(xì)描述了 .) 1． Item class Item{ public: CString name。 Item(const Itemamp。 Itemamp。 right)。 Item 類對應(yīng)于算法中的項 .為了操作方便其中的成員變量和成員函數(shù)都定義為 public 類型 . 成員變量 name 用來存放項的名字 . count 則是每個項的記數(shù)值 ,在最后的輸出之中 ,它的意義就變成了支持度 . 還有一個變量 lpvoid,是沒有在算法描述中出現(xiàn)過的 ,用來在使用過程中指向一個新分配的 Table_Iter 對象 .因為 Table_Iter 類還沒有聲明 ,所以只好用 LPVOID 類型的指針 .對它的釋放在析構(gòu)函 數(shù) ~Item()中 .~Item()又調(diào)用 DeleteVoid(LPVOID),這個函數(shù)在 class Item 聲明之前聲明 ,但又在 class Table_Iter 定義之后定義 ,因此可以用它來刪除這個對象 . 三個構(gòu)造函數(shù) Item(),Item(const Itemamp。 Trans(int t){ TID=t。 right)。 DB 對應(yīng)于數(shù)據(jù)庫對象 ,它是一個存在于內(nèi)存中的 ”數(shù)據(jù)庫 ”.它的定義借助于 STL 的 list 模板就非常的簡明 .之所以使用 list模板而不是 vector是因為對一個數(shù)據(jù)庫的操作我們通常只需要對其進(jìn)行遍歷 ,不需要查找 ,排序等操作 ,因此 list 最合適 ,效率因此也最高。 typedef std::vectorNode* NodeVector。 Node* node_link。 node_link=NULL。 } ~Node(){ if(pChildren)delete pChildren。 retcount)中可以看到 . node_link 也是一個 Node*類型 的變量 ,它用來指向下一個同名的節(jié)點 ,其作用在函數(shù)Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB)中可以看到 . class Entry{ public: CString name。 Entry(const Entryamp。 }。 r){ if(==)return 。 typedef Table::iterator Table_Iter。 (f2)DB* GetDB(_ConnectionPtramp。 int tid=pRsFieldsGetItem(TID)。 pDBpush_front(Trans(tid))。 pRsMoveNext()。 tree,Table*amp。 for(dbit=dbbegin()。 } SetupTable(pSet,pTable)。 delete pSet。transit++){ std :: pair FreqSet :: iterator , bool rpair = pSet insert ( FreqSet :: value_type ( ( *transit ) . name , * transit ) ) 。這 3 個模板在實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的時候都在內(nèi)部維護(hù)了一個平衡樹 ,使得元素在插入以后就已經(jīng)按鍵值排好了序 .但是 set和 multiset都使用插入元素本身作為鍵值 ,因此在一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １５ 插入以后就不允許修改這些元素 ,除非刪除它們 .因為任何一個對元素的修改都 是對鍵值的修改 ,會使得平衡樹不在保持原有的有序性。fit!=pSetend()。 } tit=pTableinsert((*fit).second)。 } } 這個函數(shù)的作用是根據(jù)頻繁項集合 pSet 建立頭表 pTable. 首先是刪除那些支持度小于 threshold 的項 .把剩下的 插入到頭表中去 .注意到頭表的類Table 是建立在 multiset 的基礎(chǔ)上的，所以每個元素在被插入以后就已經(jīng)被排好了序 . 這是我們可以看到 Item 類的 lpvoid 域被分配了內(nèi)存對象 .程序利用它所指向的內(nèi)存對象來記錄相應(yīng)項在頭表中的位置 .這樣當(dāng)我們知道項的名字的時候可以通過名字查找它在頻繁項集合 (用數(shù)據(jù)結(jié)構(gòu) FreqSet 表示 )中的位置 (注意一下 FreqSet 的說明 ,我們可以在時間 O(ln)中完成查找 ),再通過頻繁項集合中每個項的 lpvoid 找到它在頭表中的位置 ,在通過頭表表項中的 node_link 指針完成對樹中 相應(yīng)路徑的遍歷 . (f7) void SortTrans(DB* pDB,FreqSet* pSet){ DB_Iter dbit。dbit++){ if(dbitsize()==1){ if(pSetfind(dbitbegin()name)==pSetend()) dbitbegin()count=0。amp。 上面這條語句就是對交易 (由 dbit 代表 )排序 .排序的方式和附加的操作在比較算子Comapare 類里面 .這里的 sort(...) 函數(shù)是 STL 中的一個快速排序算法 . 比較算子的主要部分如下 : bool operator()(Itemamp。 if((fit=setfind())==setend())=lcount=0。 if(lcount==rcount)return 。titcount) tit++。dit!=pDBend()。tit++){對某個交易中的每個項 Node* temp。 temp2count=titcount。 }else{ tempcount+=titcount。 tait=*((Table_Iter*)fit)。 在算法的描述中只規(guī)定了根節(jié)點的標(biāo)記為 ”null”,并沒有要求它和其它的節(jié)點一樣具有count 和 node_lin