【正文】 } retcount+=count。 } } } 該函數(shù)的作用是將每一個(gè) set2中項(xiàng)的組合與 set合并 ,其結(jié)果即為一個(gè)頻繁集 ,然后將產(chǎn)生的頻繁集放入 pDB 中 . bitint 是我自己定義的一個(gè)類 .它跟產(chǎn)生一個(gè)集合的所有組合有關(guān) . bitint 實(shí)際上是一個(gè)無符號(hào)長(zhǎng)整數(shù) ,但我們可以根據(jù)其中的成員函數(shù)得到這個(gè)無符號(hào)長(zhǎng)整數(shù)的每一個(gè)比特位為 0 還是為 0 每次加 1,遞增到 pow(2,n)1,選出那些比特位為 1 所代表的元素就得到了有 n 個(gè)元素的集合的所有組合 . (f12) DB* Generate2(Node* node,intamp。 Trans_Iter tit。//如果 set 也為空 ,返回 count=()count。//節(jié)點(diǎn)向下移動(dòng) } return true。 } } delete tree2。 db=Generate2(tithead_link,count)。 tree=*treepChildrenbegin()。//通過頻繁項(xiàng)集合 pSet 中項(xiàng)的 lpvoid 域 //找到相應(yīng)頭表表項(xiàng) nodenode_link=taithead_link。 nodepChildrenpush_back(temp2)。dit++){//對(duì)數(shù)據(jù)庫(kù)中每個(gè)交易 node=root。 return lcountrcount。 l,Itemamp。 }else std::sort(dbitbegin(),dbitend(),Compare(pSet))。 fit=new Table_Iter。而 map 模板將元素和鍵值分離開來 ,你可以使用另外一個(gè)不變的量來充當(dāng)鍵值 ,從而可以放心的對(duì)元素進(jìn)行各種修改 ,在這里我們主要修改每個(gè)元素的計(jì)數(shù)值 . (f6) void SetupTable(FreqSet* pSet,Table* pTable){ FreqSet_Iter fit,fit2。 } 函數(shù) (f4)基本上對(duì)應(yīng)于算法描述中的 算法一 ,它通過 db中傳來的數(shù)據(jù)庫(kù) ,得到一棵 FPtree,其根結(jié)點(diǎn)為 tree 和相應(yīng)的頭表 .它依次調(diào)用下面的幾個(gè)函數(shù) .(f5)(f8) (f5) void Scan1(FreqSet* pSet,Trans* pTrans){ Trans_Iter transit。dbit!=dbend()。 } return pDB。 pDBpush_front(Trans(tid))。 最后一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)是 Table 類，它對(duì)應(yīng)于算法描述中的頭表 . Table是由 multiset模板定義的 .multiset也是一個(gè)集合模板 ,其中的實(shí)現(xiàn)也是借助于一棵內(nèi)部維護(hù)的平衡樹 .它和 map 模板的區(qū)別在于不需要另外指定鍵值類型，它直接使用內(nèi)部節(jié)點(diǎn)值類型作為鍵值類型 .在這里 ,我們使用 Entry 作為它的內(nèi)部值類型 . 因此 ,需要對(duì) Entry類的比較作出規(guī)定 ,我們 使用 Compare2類作為比較算子 .它通過重載運(yùn)算符 ()(const Entryamp。 Entry 類對(duì)應(yīng)于頭表中的表項(xiàng) .因此它有一個(gè) name 成員 ,所指 項(xiàng)的名字 ,還有一個(gè) Node*類 ,head_link,用來串起同名的項(xiàng) . 成員變量 count 是為了優(yōu)化算法而添加的 ,它的作用可以在下面 Table 的說明看到 . class Compare2{ public: Compare2(){}。 int count。 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) １２ pParent=NULL。 typedef NodeVector::iterator NVector_Iter。 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) １１ } typedef Trans::iterator Trans_Iter。 item)和 Item(CString strName,int icount)在實(shí)例化對(duì)象的時(shí)候起到不同的作用 .其中第二個(gè)是一個(gè)賦值構(gòu)造函數(shù) ,因?yàn)樵诤竺娑x的一些類中需要使用 class Item做為類型參數(shù) ,根據(jù)約定 ,需要 class Item實(shí)現(xiàn)一個(gè) 賦值構(gòu)造函數(shù) .最后三個(gè)成員函數(shù)重載了兩個(gè)運(yùn)算符 ?==?和 ??,是因?yàn)樵诤竺娴暮瘮?shù)中我們需要對(duì)頻繁的項(xiàng)集進(jìn)行查找 ,插入，所以要對(duì)比較作出規(guī)定 . class Trans:public std::vectorItem { public: int TID。 operator=(const Itemamp。 int count。fit++){ printf(%s %d \n,(*fit).,(*fit).)。 數(shù)據(jù)評(píng)價(jià) 即用一種通用的數(shù)據(jù)采掘評(píng)價(jià)的架構(gòu)來比較不同模型的效果；預(yù)報(bào)各種不同類型分析工具的結(jié)果。 圖 1 該工具的主要功能塊的說明如下： (上圖及說明主要參考 [3]) 數(shù)據(jù)預(yù)處理 負(fù)責(zé)對(duì)待采掘的數(shù)據(jù)源作必要的準(zhǔn)備 ， 其各模塊功能如下： （ 1）數(shù)據(jù)獲取 指定要使用的數(shù)據(jù)集的名稱及位置。其形式化的陳述如下。實(shí)際上，所有發(fā)現(xiàn)的知識(shí)都是相對(duì)的，是有特定前提和約束條件，面向特定領(lǐng)域的，同時(shí)還要能夠易于被用戶理解。 何為知識(shí) ?從廣義上理解，數(shù)據(jù)、信息也是知識(shí)的表現(xiàn)形式，但是人們更把概念、規(guī)則、模式、規(guī)律和約束等看作知識(shí)。 本文分析并且實(shí)現(xiàn)了在論文 [1]中提出的 FPgrowth算法。在大多數(shù)以前的實(shí)現(xiàn)中，人們普 遍采用了類似于 Apriori[2]的算法。該實(shí)現(xiàn)基于 Windows平臺(tái)，編程工具是 Visual C++ ，許多地方還用到了 C++的標(biāo)準(zhǔn)模板庫(kù)。因此，數(shù)據(jù)挖掘是一門交叉學(xué)科，它把人們對(duì)數(shù)據(jù)的應(yīng)用從低層次的簡(jiǎn)單查詢，提升到從數(shù)據(jù)中挖掘知識(shí)，提供決策支持。預(yù)測(cè)準(zhǔn)客戶的需要是美國(guó)商業(yè)銀行的競(jìng)爭(zhēng)優(yōu)勢(shì)。可信度為 c,如果|Txy|/|Tx|=c%. 舉例來說 ,有一個(gè)特定的關(guān)聯(lián)規(guī)則 ,錘子 ==釘子 ,這個(gè) 規(guī)則可能意味著買錘子的人也有傾向買釘子 .在一個(gè)有 10000 條交易記錄的交易數(shù)據(jù)庫(kù)中 ,若有 300 條記錄既包含了錘子又包含了釘子 ,則我們說此關(guān)聯(lián)規(guī)則的支持度為 300/10000=3%.這個(gè)支持度還是比較的高 ,但我們并不能就此作出這個(gè)關(guān)聯(lián)有意義的結(jié)論 .假如通過統(tǒng)計(jì)發(fā)現(xiàn)一共有 6000 條記錄包含了 ”錘子 ”,則僅有可信度 300/6000=5%的購(gòu)買了 ”錘子 ”的人又去購(gòu)買了釘子，那么這個(gè)關(guān)聯(lián)規(guī)則的可信度不高 ,它并沒有告訴我們什么 .但是假如只有 600人購(gòu)買了錘子 ,則我們可以知道其中有一半的人又去購(gòu)買了釘子 ,這個(gè)現(xiàn)象就值得注 意了 . 另一個(gè)更詳細(xì)的例子來自于 [4]. 總交易筆數(shù) :1000 包含 ”錘子 ”:50 包含 ”釘子 ”:80 包含 ”鉗子 ”:20 包含 ”錘子 ”和 ”釘子 ”:15 包含 ”鉗子 ”和 ”釘子 ”:10 包含 ”錘子 ”和 ”鉗子 ”:10 包含 ”錘子 ”,”鉗子 ”和 ”釘子 ”:15 則可以計(jì)算出 : “錘子和釘子 ”的支持度 =%(15/1000) “錘子 ,釘子和鉗子 ”的支持度 =(5/1000) “錘子 ==釘子 ”的可信度 =30%(15/50) “釘子 ==錘子 ”的可信度 =19%(15/80) “錘子和釘子 ==鉗子 ”的可信度 =33%(5/15) “鉗子 ==錘子和釘子 ”的可信度 =25%(5/20) 注意到數(shù)據(jù)挖掘得到的關(guān)聯(lián)規(guī)則 ,它只是對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)之間相關(guān)性的一種描述。 （ 4）數(shù)據(jù)轉(zhuǎn)換 將某一個(gè)數(shù)據(jù)進(jìn)行某種轉(zhuǎn)換操作，然后將轉(zhuǎn)換后的值作為新的變量存放在樣本數(shù)據(jù)中，而轉(zhuǎn)換的 目的是為了把數(shù)據(jù)和將來要建立的模型擬和得更好。同樣因?yàn)橐幚泶罅康臄?shù)據(jù) ,所以對(duì)內(nèi)存的管理要尤其嚴(yán)格 ,如果出現(xiàn)內(nèi)存泄漏將是很麻煩的事情 . 第三，是編程風(fēng)格的考慮 .要盡量采用通用化的代碼 .因?yàn)閷?duì)于一個(gè)比較大的系統(tǒng)來說，任何一個(gè)小的部分都應(yīng)該清楚明白 ,便于別人閱讀和修改 . 基于上 面三點(diǎn)的考量，我在對(duì)程序的數(shù)據(jù)結(jié)構(gòu)的定義和算法的實(shí)現(xiàn)的時(shí)候大量采用了C++的標(biāo)準(zhǔn)模板庫(kù) (STL,Standard Template Library).這是基于以下的事實(shí) ,關(guān)聯(lián)規(guī)則的挖掘所涉及到的數(shù)據(jù)結(jié)構(gòu)和基本算法都是以往的常用數(shù)據(jù)結(jié)構(gòu)和算法 ,如向量類 ,集合類 ,快速排序算法等 .而 STL 正是包含了這樣許多通用的數(shù)據(jù)結(jié)構(gòu)和基本算法的庫(kù) . 模板實(shí)際上是一種宏 ,但比宏安全可靠的多 .它在編譯期間就被處理了 ,因此根本不會(huì)影響程序的執(zhí)行速度 .又因?yàn)椋?STL 中的種種數(shù)據(jù)結(jié)構(gòu)和算法都是精心編寫的 ,對(duì)同一問題的實(shí)現(xiàn)一般是比較經(jīng)典 的 .不僅在速度上有優(yōu)勢(shì) ,而且還避免了許多低層次上的內(nèi)存泄漏問題 .使我們把注意力集中到各個(gè)函數(shù)接口上面 . 由于 STL 本身就是一中很通用的庫(kù) ,因此可以很好的滿足第三個(gè)條件 .用他編寫的代碼 ,對(duì)類似的數(shù)據(jù)結(jié)構(gòu)和算法的處理都很相象 . 例如 ,在 STL 中有一大類模板叫容器模板 (container),簡(jiǎn)單的說就是包含了許多元素的類的模板 ,象 vector,array,set 等就屬于容器模板 .對(duì)于這些模板中的元素的訪問都可以通過它們的遍歷子 ,用完全一致的方式進(jìn)行 .請(qǐng)看下面兩段程序清單 : void print(FreqSet* pSet){ FreqSet_Iter fit。 } } 這兩個(gè)函數(shù)是在調(diào)試的時(shí)候分別打印出頻繁集 pSet 和頭表 pTable 中的元素的 . 盡管 pSet 的類 FreqSet 是由 map模板生成的 ,pTable 的類 Table 是由 multiset 生成的 ,但對(duì)它們的元素的訪問形式幾乎一模一樣都是利用相應(yīng)的遍歷子 .涉及的函數(shù)名也很相似 .其實(shí) ,所有的容器模板都定義了函數(shù) begin()和 end()代表元素列表的起始和結(jié)束 .另外還有大量的具有相同名字和類似功能的函數(shù) ,方便了我們對(duì)數(shù)據(jù)結(jié)構(gòu)的管理。 Item(CString strName,int icount)。 right)。 right)。 typedef FreqSet::iterator FreqSet_Iter。 Node* pParent。 class Node 是建立 FPtree的關(guān)鍵數(shù)據(jù)結(jié)構(gòu) ,節(jié)點(diǎn)。 Entry(const Itemamp。 } }。 (f3)void StorePatterns(DB* pDB,_ConnectionPtr pConn)。 int count=fieldsvalue(pRs,COUNT).lVal。 FreqSet* pSet=(FreqSet*)new FreqSet。 Node* root=SetupFP(pSet,pTable,db)。 } } } 這個(gè)函數(shù)的作用很簡(jiǎn)單 ,它只是從 pTrans 所代表的交易中取出每個(gè)項(xiàng) ,然后試圖將其插入到 pSet中去 (pSetinsert(...)),如果插入失敗 (if(==false)),則表明 pSet中已經(jīng)有此項(xiàng)了 ,因此只須增加其計(jì)數(shù)值 ((*).+=(*transit).count。 pSeterase(fit2)。 for(dbit=pDBbegin()。 if(tit!=dbitend())dbiterase(tit,dbitend())。 if((fit=setfind())==setend())=rcount=0。 把它們?nèi)縿h除掉 . (f8) Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB)。 if(temp==NULL){ //如果子節(jié)點(diǎn)中沒有要找的項(xiàng)則創(chuàng)建一個(gè) Node* temp2=(Node*)new Node。 continue。 if(HasNoBranch(tree)){//如果 tree 沒有分支 Trans set2。){//從尾到頭遍歷每一個(gè)頭表表項(xiàng) DB* db。 Trans set2(set)。//nit 為 tree 的第一個(gè)子節(jié)點(diǎn) nit++。 bitin