【正文】 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)。 一個不需要產生候選集的頻繁集產生算法的分析與實現 １４ } CString name=fieldsvalue(pRs,IID).bstrVal。 return 。//在析構函數中刪除 } }。 typedef std::mapCString,Item FreqSet。 bool operator(const Itemamp。tit++){ printf(%s %d \n,(*tit).name,(*tit).count)。例如，對于分類變量可給定某一類的類值說明此類觀測值是要排除于取樣范圍之外的，對于區(qū)間變量可指定其值大于或小于某值的那些觀測值排除于取樣范圍之外。 Marksman能讀取 800到 1000個變量并且給它們賦值 ，根據消費者是否有家庭財產貸款、賒帳卡、存款證或其它儲蓄、投資產品，將它們分成若干組，然后使用數據挖掘工具預測何時向每位消費者提供哪種產品。在具體的實現中，我通過了一系列的從低到高的數據結構來實現它，并進而實現整個算 法。 FPgrowth算法的優(yōu)點是節(jié)省時間和空間，對大規(guī)模數據采用分治的辦法以避免規(guī)模巨大難以接受。最好能用自然語言表達所發(fā)現的結果。 （ 2）數據取樣 對獲取的數據從中取樣，取樣的方式有很多種，根據數據采掘的目的性靈活選用。 } } void print(Table* pTable){ Table_Iter tit。 right)。 Trans 類對應于交易對象 (Transaction).對它的定義利用了 STL 中的 vector 模板 ,把它定義為一個以 Item 為元素的向量 .把它定義為向量 ,是因為后來需要對其中的元素進行排序 ,向量可以使用快速排序 . 這個 Trans 類身肩兩任 ,它不僅代表交易對象 ,還在最后的結果輸出中還被用來存放頻繁集 . Trans_Iter 是 Trans 類的遍歷子 .在以后使用 STL 容器模板定義的類都會有一個與之相對應的遍歷子 ,不再贅述 . 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。 一個不需要產生候選集的頻繁集產生算法的分析與實現 １７ temp2pParent=node。 } Generate1(set2,pDB,set)。 delete pTable。//否則這里產生的頻繁集的支持度為 set 的支持度 }else{如果 set2 不為空 一個不需要產生候選集的頻繁集產生算法的分析與實現 １９ 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(...) 函數是 STL 中的一個快速排序算法 . 比較算子的主要部分如下 : bool operator()(Itemamp。 } tit=pTableinsert((*fit).second)。 delete pSet。 pRsMoveNext()。 typedef Table::iterator Table_Iter。 retcount)中可以看到 . node_link 也是一個 Node*類型 的變量 ,它用來指向下一個同名的節(jié)點 ,其作用在函數Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB)中可以看到 . class Entry{ public: CString name。 typedef std::vectorNode* NodeVector。 Item 類對應于算法中的項 .為了操作方便其中的成員變量和成員函數都定義為 public 類型 . 成員變量 name 用來存放項的名字 . count 則是每個項的記數值 ,在最后的輸出之中 ,它的意義就變成了支持度 . 還有一個變量 lpvoid,是沒有在算法描述中出現過的 ,用來在使用過程中指向一個新分配的 Table_Iter 對象 .因為 Table_Iter 類還沒有聲明 ,所以只好用 LPVOID 類型的指針 .對它的釋放在析構函 數 ~Item()中 .~Item()又調用 DeleteVoid(LPVOID),這個函數在 class Item 聲明之前聲明 ,但又在 class Table_Iter 定義之后定義 ,因此可以用它來刪除這個對象 . 三個構造函數 Item(),Item(const Itemamp。否則 ,創(chuàng)建一個新節(jié)點 N,使它的 count 為 1,使它的父節(jié)點為 T,并且使它的 node_link 和那些具有相一個不需要產生候選集的頻繁集產生算法的分析與實現 ７ 同 item_name 域串起來 .如果 P 非空 ,則遞歸調用 insert_tree(P,N). 完 畢 . 通過一個例子 ,可以更清楚的看到一棵 FPtree 是怎樣建立的 . 設有如下交易數據庫 : 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. 我們首先掃描一遍這個數據庫 ,計算每個項的計數值并保存在頻繁項的集合 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 的項 , 并按支持度遞降排列 , 將結果放入列表 L 中 , 此時 ,L={(f:4),(c:4),(a:3),(b:3),(m:3),(p:3)}. 執(zhí)行算法的第二步 ,創(chuàng)建一個標記為 ”null”的根節(jié)點 .開始對數據庫的第二遍掃描 .對第一個交易的掃描將建立這棵樹的第 一個分支 :(f:1),(c:1),(a:1),(m:1),(p:1).注意 ,在這個交易中的頻繁項已經被按照 L 中的順序進行排序了 .對于第二個交易來說 ,它已經排序好的頻繁項列表 f,c,a,b,m同已經存在的路徑 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é)點 .以此類推 ,掃描完整個數據庫 . 為了方便對樹的遍歷 .一個頻繁項頭表 (frequent item header table)被建立了，頭表表項的node_link 指向樹里面具有相同 item_name的節(jié)點 .具有相同 item_name的節(jié)點通過 node_link被連結在一起 . 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 一個不需要產生候選集的頻繁集產生算法的分析與實現 ８ 圖 2 FPtree 是一個壓縮的數據結構 ,它用較少的空間存儲了后面頻繁集挖掘所需要的全部信息 . 算法二建立在算法一所產生的 Ftree 上面 .它會遞歸調用自己 ,并且反復調用算法一產生新的 FPtree. 輸入 :一棵用算法一建立的樹 Tree 輸出 :所有的頻繁集 步驟 : 調用 FPgrowth(Tree,null). 下面是對過程 FPgrowth 的偽碼描述 . Procedure FPgrowth(Tree,α) { if Tree 只有一條路徑 P then 對 P 中的節(jié)點的每一個組合 (記為 β)做 (1) (1) 產生頻繁集 β?α,并且把它的支持度指定為 β中節(jié)點的最小支持度 . else 對 Tree 的頭表從表尾到表頭的每一個表項 (記為 a)做 (2)(5) (2) 產生頻繁集 β=a?α,并且支持度為 a 的支持度 (3) 建立 β的條件模式庫 (conditional pattern base)和 β的條件樹 (conditional FPtree)Tree2 (4) if Tree2!=? (5) then 調用 FPgrowth(Tree2,β) } 關于什么是條件模式庫 (conditional pattern base)和條件樹 (conditional FPtree),我們繼續(xù)上面那個例子來介紹 . 我們把圖 2 中已經得到的 FPtree 和相應的頭表作為算法二的輸入 .按照從表尾到表頭的順序考察表中的每一個表項 . 從表項 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 出現了 3 次 ,c 和 a 各出現了兩次 ,但它們同 p 在一起只出現了 2 次 ,所以把它們 的計數改為 2,得到 f:2,c:2,a:2,m:2,p:2.第二條路徑中各項的計數都已相同 ,不用修改了 .把這 2條路徑中的 p項去掉 ,就得到了 p的條件模式庫 ,{(f:2,c:2,a:2,m:2),(c:1,b:1)},這是下一步遞歸的依據 .我們把這個條件模式庫看作一個數據庫 ,在上面運用算法一產生一個新的 FPtree,這就是算法二中的條件樹 ,這個新樹只有一個節(jié)點 (c:3).這時又得到一個新的頻繁集 (cp:3).包含 p項的頻繁集就挖掘完了 . 接著考察