【正文】 Node* node2=nodepParent。//頻繁集的支持度是 set2 中最小的 ,即最后一個 } for(。//若 tree 節(jié)點沒有子節(jié)點 ,返回 true nit=treepChildrenbegin()。tit!=pTablebegin()。//否 則 ,增加該項的支持度 node=temp。 if(tit!=dbitend())dbiterase(tit,dbitend())。titcount) tit++。){ if((*fit).threshold){ fit2=fit++。 SortTrans(db,pSet)。 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １４ } CString name=fieldsvalue(pRs,IID).bstrVal。 return 。//在析構(gòu)函數(shù)中刪除 } }。 typedef std::mapCString,Item FreqSet。 bool operator(const Itemamp。tit++){ printf(%s %d \n,(*tit).name,(*tit).count)。例如，對于分類變量可給定某一類的類值說明此類觀測值是要排除于取樣范圍之外的，對于區(qū)間變量可指定其值大于或小于某值的那些觀測值排除于取樣范圍之外。 Marksman能讀取 800到 1000個變量并且給它們賦值 ，根據(jù)消費者是否有家庭財產(chǎn)貸款、賒帳卡、存款證或其它儲蓄、投資產(chǎn)品，將它們分成若干組，然后使用數(shù)據(jù)挖掘工具預(yù)測何時向每位消費者提供哪種產(chǎn)品。在具體的實現(xiàn)中，我通過了一系列的從低到高的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)它，并進而實現(xiàn)整個算 法。 FPgrowth算法的優(yōu)點是節(jié)省時間和空間，對大規(guī)模數(shù)據(jù)采用分治的辦法以避免規(guī)模巨大難以接受。最好能用自然語言表達所發(fā)現(xiàn)的結(jié)果。 （ 2）數(shù)據(jù)取樣 對獲取的數(shù)據(jù)從中取樣，取樣的方式有很多種，根據(jù)數(shù)據(jù)采掘的目的性靈活選用。 } } void print(Table* pTable){ Table_Iter tit。 right)。 Trans 類對應(yīng)于交易對象 (Transaction).對它的定義利用了 STL 中的 vector 模板 ,把它定義為一個以 Item 為元素的向量 .把它定義為向量 ,是因為后來需要對其中的元素進行排序 ,向量可以使用快速排序 . 這個 Trans 類身肩兩任 ,它不僅代表交易對象 ,還在最后的結(jié)果輸出中還被用來存放頻繁集 . Trans_Iter 是 Trans 類的遍歷子 .在以后使用 STL 容器模板定義的類都會有一個與之相對應(yīng)的遍歷子 ,不再贅述 . typedef std::listTrans DB。 count=0。 bool operator()(const Entryamp。 while(!pRsadoEOF){ int ttid=pRsFieldsGetItem(TID)。dbit++){ Scan1(pSet,amp。 Table_Iter tit。 tit=dbitbegin()。 } 對于那些在 pSet 中沒有找到的項 ,把它們的支持度都置為 0,排序以后這些支持度 為 0 的項 (也就是支持度小于最小支持度的項 )都被排在最后面 ,最后通過語句 while(tit!=dbitend()amp。 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １７ temp2pParent=node。 } Generate1(set2,pDB,set)。 delete pTable。//否則這里產(chǎn)生的頻繁集的支持度為 set 的支持度 }else{如果 set2 不為空 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １９ Trans_Iter tit=()。 retcount){ DB* pDB=(DB*)new DB。 node2=node2pParent。 int i=0。//返回 false tree=(*nit)。 int count。 tait=*((Table_Iter*)fit)。dit!=pDBend()。 上面這條語句就是對交易 (由 dbit 代表 )排序 .排序的方式和附加的操作在比較算子Comapare 類里面 .這里的 sort(...) 函數(shù)是 STL 中的一個快速排序算法 . 比較算子的主要部分如下 : bool operator()(Itemamp。 } tit=pTableinsert((*fit).second)。 delete pSet。 pRsMoveNext()。 typedef Table::iterator Table_Iter。 retcount)中可以看到 . node_link 也是一個 Node*類型 的變量 ,它用來指向下一個同名的節(jié)點 ,其作用在函數(shù)Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB)中可以看到 . class Entry{ public: CString name。 typedef std::vectorNode* NodeVector。 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。否則 ,創(chuàng)建一個新節(jié)點 N,使它的 count 為 1,使它的父節(jié)點為 T,并且使它的 node_link 和那些具有相一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) ７ 同 item_name 域串起來 .如果 P 非空 ,則遞歸調(diào)用 insert_tree(P,N). 完 畢 . 通過一個例子 ,可以更清楚的看到一棵 FPtree 是怎樣建立的 . 設(shè)有如下交易數(shù)據(jù)庫 : TID 購買項 (有序的 )頻繁項 100 f,a,c,d,g,i,m,p f,c,a,m,p 200 a,b,c,f,l,m,o f,c,a,b,m 300 b,f,h,j,o f,b 400 b,c,k,s,p c,b,p 500 a,f,c,e,l,p,m,n f,c,a,m,p 表 1. 我們首先掃描一遍這個數(shù)據(jù)庫 ,計算每個項的計數(shù)值并保存在頻繁項的集合 F中 ,F={(a:3),(b:3),(c:4),(d:1),(e:1),(f:4),(g:1),(h:1),(i:1),(j:1),(k:1),(l:2),(m:3),(n:1),(o:2),(p:3)}. 集合中每個元素的第二個分量代表第一個分量所代表項的支持度 .我們假定最小支持度為 出 F 中支持度大于 3 的項 , 并按支持度遞降排列 , 將結(jié)果放入列表 L 中 , 此時 ,L={(f:4),(c:4),(a:3),(b:3),(m:3),(p:3)}. 執(zhí)行算法的第二步 ,創(chuàng)建一個標記為 ”null”的根節(jié)點 .開始對數(shù)據(jù)庫的第二遍掃描 .對第一個交易的掃描將建立這棵樹的第 一個分支 :(f:1),(c:1),(a:1),(m:1),(p:1).注意 ,在這個交易中的頻繁項已經(jīng)被按照 L 中的順序進行排序了 .對于第二個交易來說 ,它已經(jīng)排序好的頻繁項列表 f,c,a,b,m同已經(jīng)存在的路徑 f,c,a,m,p有共同的前綴 f,c,a,所以把這個前綴中的所有節(jié)點的 count 增加 (b:1)被創(chuàng)建并且被作為節(jié)點 (a:2)的子節(jié)點 ,隨后 ,新節(jié)點 (m:1)被創(chuàng)建并做為節(jié)點 (b:1)的子節(jié)點 .對第三個交易 ,因為它的頻繁項列表只同以 f 為前綴的子樹有一個共同節(jié)點 f.所以把這個 節(jié)點的 count 增加 1,并且創(chuàng)建新節(jié)點 (b:1),把它作為 (f::3)的子節(jié)點 .以此類推 ,掃描完整個數(shù)據(jù)庫 . 為了方便對樹的遍歷 .一個頻繁項頭表 (frequent item header table)被建立了，頭表表項的node_link 指向樹里面具有相同 item_name的節(jié)點 .具有相同 item_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項的頻繁集就挖掘完了 . 接著考察