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