【文章內容簡介】 .按照從表尾到表頭的順序考察表中的每一個表項 . 從表項 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)}.我們在上面構建條件樹 ,得到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ù)結構 對應于算法描述中所出現(xiàn)的各個對象分別定義了一些數(shù)據(jù)結構 .下面予以分別介紹 .(有關代碼的清單只列出重要部分，如類中的普通的構造函數(shù)之類就不予詳細描述了 .) 1． Item class Item{ public: CString name。 int count。 LPVOID lpvoid。 Item()。 Item(const Itemamp。 item)。 Item(CString strName,int icount)。 ~Item()。 Itemamp。 operator=(const Itemamp。 right)。 bool operator==(const Itemamp。 right)。 bool operator(const Itemamp。 right)。 }。 Item 類對應于算法中的項 .為了操作方便其中的成員變量和成員函數(shù)都定義為 public 類型 . 成員變量 name 用來存放項的名字 . count 則是每個項的記數(shù)值 ,在最后的輸出之中 ,它的意義就變成了支持度 . 還有一個變量 lpvoid,是沒有在算法描述中出現(xiàn)過的 ,用來在使用過程中指向一個新分配的 Table_Iter 對象 .因為 Table_Iter 類還沒有聲明 ,所以只好用 LPVOID 類型的指針 .對它的釋放在析構函 數(shù) ~Item()中 .~Item()又調用 DeleteVoid(LPVOID),這個函數(shù)在 class Item 聲明之前聲明 ,但又在 class Table_Iter 定義之后定義 ,因此可以用它來刪除這個對象 . 三個構造函數(shù) Item(),Item(const Itemamp。 item)和 Item(CString strName,int icount)在實例化對象的時候起到不同的作用 .其中第二個是一個賦值構造函數(shù) ,因為在后面定義的一些類中需要使用 class Item做為類型參數(shù) ,根據(jù)約定 ,需要 class Item實現(xiàn)一個 賦值構造函數(shù) .最后三個成員函數(shù)重載了兩個運算符 ?==?和 ??,是因為在后面的函數(shù)中我們需要對頻繁的項集進行查找 ,插入，所以要對比較作出規(guī)定 . class Trans:public std::vectorItem { public: int TID。 Trans(){TID=0。}。 Trans(int t){ TID=t。 } bool operator==(const Transamp。 right)。 bool operator(const Transamp。 right)。 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １１ } typedef Trans::iterator Trans_Iter。 Trans 類對應于交易對象 (Transaction).對它的定義利用了 STL 中的 vector 模板 ,把它定義為一個以 Item 為元素的向量 .把它定義為向量 ,是因為后來需要對其中的元素進行排序 ,向量可以使用快速排序 . 這個 Trans 類身肩兩任 ,它不僅代表交易對象 ,還在最后的結果輸出中還被用來存放頻繁集 . Trans_Iter 是 Trans 類的遍歷子 .在以后使用 STL 容器模板定義的類都會有一個與之相對應的遍歷子 ,不再贅述 . typedef std::listTrans DB。 typedef DB::iterator DB_Iter。 DB 對應于數(shù)據(jù)庫對象 ,它是一個存在于內存中的 ”數(shù)據(jù)庫 ”.它的定義借助于 STL 的 list 模板就非常的簡明 .之所以使用 list模板而不是 vector是因為對一個數(shù)據(jù)庫的操作我們通常只需要對其進行遍歷 ,不需要查找 ,排序等操作 ,因此 list 最合適 ,效率因此也最高。 typedef std::mapCString,Item FreqSet。 typedef FreqSet::iterator FreqSet_Iter。 FreqSet跟我們要得到的頻繁集并不是一回事 ,它只是一個中間的數(shù)據(jù)結構 .我們在掃描數(shù)據(jù)庫的時候需要計算每個項的記數(shù)值 ,因此需要建立一個項的集合類 ,其中有所有的項 ,每次在數(shù)據(jù)庫中掃描到一個項就增加其中相應的項的記數(shù)值 .它相當于算法描述中的頻繁項集合 . 為了使得查找相應項的速度加快 ,用 map 模板來定義 FreqSet. STL 在實現(xiàn) map 的時候 ,實際上在其內部維持了一個平衡樹 , 因此其插入，查找 ,刪除的速度是 O(ln).map 模板使用第一個類型參數(shù)作為比較的鍵值 類型 ,第二個類型參數(shù)做為節(jié)點內部值 .在這里 ,鍵值類型為 CString,節(jié)點內部值類型為 Item的成員變量 name為鍵值 .就可以根據(jù) Item的名字來尋找它在 FreqSet中的位置 ,在 O(ln)時間內完成對相應項的操作 . 使用 map 模板的另外一個原因參見后面的算法實現(xiàn)細節(jié)部分對函數(shù) (f5)的說明 . Node class Node。 typedef std::vectorNode* NodeVector。 typedef NodeVector::iterator NVector_Iter。 class Node{ public: CString name。 int count。 Node* node_link。 NodeVector* pChildren。 Node* pParent。 Node(){ pChildren=(NodeVector*) new NodeVector。 node_link=NULL。 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １２ pParent=NULL。 count=0。 name=。 } ~Node(){ if(pChildren)delete pChildren。//在析構函數(shù)中刪除 } }。 class Node 是建立 FPtree的關鍵數(shù)據(jù)結構 ,節(jié)點。其中 pChildren 指針指向子節(jié)點 ,由于一個節(jié)點的子節(jié)點的數(shù)目是不定的，所以用了一個 NodeVector 類來管理子節(jié)點 .因為我們要在 Node 類的構造函數(shù)中給 pChildren 分配空間 ,所以需要在定義 Node 之前定義 NodeVector. NodeVector是一個以 Node*為元素的向量類 .所以我們在定義它之前聲明了 Node類 .雖然我們在后面的算法中需要根據(jù)名字在 pChildren 中查找子節(jié)點 ,我們并沒有使用 hash 表或者平衡樹這樣復雜但高效的數(shù)據(jù)結構 ,是因為子節(jié)點的數(shù)目一般都不是很多 ,使用復雜的這樣復雜的數(shù)據(jù)結構對于少量的數(shù)據(jù)來說時間并沒有縮短多少 ,空間卻要浪費一些 .因此使用了一個向量類 ,查找的時候使用簡單的遍歷算法 . 成員變量 name 和 count 的意義很清楚 ,它們分別是節(jié)點的名字和計數(shù)值 . pParent 指向父節(jié)點 ,定義這樣一個變量的作用在函數(shù) DB* Generate2(Node* node,intamp。 retcount)中可以看到 . node_link 也是一個 Node*類型 的變量 ,它用來指向下一個同名的節(jié)點 ,其作用在函數(shù)Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB)中可以看到 . class Entry{ public: CString name。 int count。 Node* head_link。 Entry()。 Entry(const Entryamp。 entry)。 Entry(const Itemamp。 item)。 }。 Entry 類對應于頭表中的表項 .因此它有一個 name 成員 ,所指 項的名字 ,還有一個 Node*類 ,head_link,用來串起同名的項 . 成員變量 count 是為了優(yōu)化算法而添加的 ,它的作用可以在下面 Table 的說明看到 . class Compare2{ public: Compare2(){}。 bool operator()(const