【正文】 t bit。bitmaxsize。tit!=()。 int count=nodecount。 } return pDB。 while(node){ Trans trans。tit++,i++){ if(bit[i]) (Item(titname,count))。 count=titcount。 set) { int size=()。 while(tree){ if(treepChildrenempty())return true。 if(!dbempty()) 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) １８ Algorithm1(db,node,table)。 for(tit=pTableend()。 在算法的描述中只規(guī)定了根節(jié)點(diǎn)的標(biāo)記為 ”null”,并沒(méi)有要求它和其它的節(jié)點(diǎn)一樣具有count 和 node_link 域 .為了不用給根節(jié)點(diǎn)另外建立一個(gè)類(lèi) ,就簡(jiǎn)單使用了一般節(jié)點(diǎn)的類(lèi) Node.把其中的 count 設(shè)為 0,node_link 設(shè)為 null. Node* find_node(NVector_Iter f,NVector_Iter l,CString name)在子節(jié)點(diǎn)的集合中查找是否含有 name 的子節(jié)點(diǎn) ,并返回之 ,若無(wú) ,則返回 ,其原因已經(jīng)在數(shù)據(jù)結(jié)構(gòu)部分 的 ”NodeVector和 Node”中說(shuō)明了 . (f9) void Algorithm2(Node* tree,Table* pTable,DB *pDB,Trans set){ if(tree==NULL)return。 }else{ tempcount+=titcount。tit++){對(duì)某個(gè)交易中的每個(gè)項(xiàng) Node* temp。titcount) tit++。 if((fit=setfind())==setend())=lcount=0。amp。 } } 這個(gè)函數(shù)的作用是根據(jù)頻繁項(xiàng)集合 pSet 建立頭表 pTable. 首先是刪除那些支持度小于 threshold 的項(xiàng) .把剩下的 插入到頭表中去 .注意到頭表的類(lèi)Table 是建立在 multiset 的基礎(chǔ)上的，所以每個(gè)元素在被插入以后就已經(jīng)被排好了序 . 這是我們可以看到 Item 類(lèi)的 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。fit!=pSetend()。transit++){ std :: pair FreqSet :: iterator , bool rpair = pSet insert ( FreqSet :: value_type ( ( *transit ) . name , * transit ) ) 。 } SetupTable(pSet,pTable)。 tree,Table*amp。 pDBpush_front(Trans(tid))。 (f2)DB* GetDB(_ConnectionPtramp。 r){ if(==)return 。 Entry(const Entryamp。 } ~Node(){ if(pChildren)delete pChildren。 Node* node_link。 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 最合適 ,效率因此也最高。 Trans(int t){ TID=t。 right)。 Item(const Itemamp。tit!=pTableend()。 程序的實(shí)現(xiàn)是基于 Windows95/NT 平臺(tái) ,編譯器是 Visual C++數(shù)據(jù)挖掘工具 ARMiner 相兼容 . 程序在定義數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)算法的時(shí)候主要有以下一些考量。 （ 3）數(shù)據(jù)篩選 通過(guò)數(shù)據(jù)篩選篩選掉不希望包括進(jìn)來(lái)的觀測(cè)值。每一個(gè)交易 T 都有一個(gè)唯一的標(biāo)識(shí)， TID。 Firstar銀行市場(chǎng)調(diào)查和數(shù)據(jù)庫(kù)營(yíng)銷(xiāo)部經(jīng)理發(fā)現(xiàn)：公共數(shù)據(jù)庫(kù)中存儲(chǔ)著關(guān)于每位消費(fèi)者的大量信息，關(guān)鍵是要透徹分析消費(fèi)者投入到新產(chǎn)品中的原因，在數(shù)據(jù)庫(kù)中找到一種模式，從而能夠?yàn)槊糠N新產(chǎn)品找到最合適的消費(fèi)者。發(fā)現(xiàn)知識(shí)的方法可以是數(shù)學(xué)的，也可以是非數(shù)學(xué)的；可以是演繹的，也可以是歸納的。 FPtree 是一個(gè)數(shù)據(jù)庫(kù)里跟產(chǎn)生頻繁集有關(guān)的信息的壓縮表示。 目 錄 摘要 ： ................................................................................................... １ 1．介紹 ................................................................................................. １ ............................................................................................ １ ............................................................................................ ２ 4．?dāng)?shù)據(jù)采掘工具的研制及其應(yīng)用 ...................................................... ４ ............................................................................................ ５ 算法描述 ............................................................................................ ６ 數(shù)據(jù)結(jié)構(gòu) ........................................................................................ １０ 算法實(shí)現(xiàn)細(xì)節(jié) ................................................................................ １３ ................................................................................................ ２０ ................................................................................................ ２０ 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) １ 摘要 ： 關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘是一個(gè)重要的研究?jī)?nèi)容。 FPgrowth算法主要通過(guò) FPtree來(lái)構(gòu)造頻繁集。原始數(shù)據(jù)可以是結(jié)構(gòu)化的，如關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)；也可以是半結(jié)構(gòu)化的，如文本、圖形和圖像數(shù)據(jù)；甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。 數(shù)據(jù)挖掘的主要過(guò)程如下 : 1. 確定業(yè)務(wù)對(duì)象 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) ２ 清晰地定義出業(yè)務(wù)問(wèn)題 ,認(rèn)清數(shù)據(jù)挖掘的目的是數(shù)據(jù)挖掘的重要一步 .挖掘的最后結(jié)構(gòu)是不可預(yù)測(cè)的 ,但要探索的問(wèn)題應(yīng)是有預(yù)見(jiàn)的 ,為了數(shù)據(jù)挖掘而數(shù)據(jù)挖掘則帶有盲目性 ,是不會(huì)成功的 . 2. 數(shù)據(jù)準(zhǔn)備 1) 數(shù)據(jù)的選擇 搜索所有與業(yè)務(wù)對(duì)象有關(guān)的內(nèi)部和外部數(shù)據(jù)信息 ,并從中選擇出適用于數(shù)據(jù)挖掘應(yīng)用的數(shù)據(jù) . 2) 數(shù)據(jù)的預(yù)處理 研究數(shù)據(jù)的質(zhì)量 ,為進(jìn)一步的分析作準(zhǔn)備 .并確定將要進(jìn)行的挖掘操作的類(lèi)型 . 3) 數(shù)據(jù)的轉(zhuǎn)換 將數(shù)據(jù)轉(zhuǎn)換成一個(gè)分析模型 .這個(gè)分析模型是針對(duì)挖掘算法建立的 .建立一個(gè)真正適合挖掘算法的分析模型是數(shù)據(jù)挖掘成功的關(guān)鍵 . 3. 數(shù)據(jù)挖掘 對(duì)所得到的經(jīng)過(guò)轉(zhuǎn)換的數(shù)據(jù)進(jìn)行挖掘 .除了完善從選擇合適的挖掘算法 外 ,其余一切工作都能自動(dòng)地完成 . 4. 結(jié)果分析 解釋并評(píng)估結(jié)果 .其使用的分析方法一般應(yīng)作數(shù)據(jù)挖掘操作而定 ,通常會(huì)用到可視化技術(shù) . 5. 知識(shí)的同化 將分析所得到的知識(shí)集成到業(yè)務(wù)信息系統(tǒng)的組織結(jié)構(gòu)中去 . 數(shù)據(jù)挖掘技術(shù)目前已經(jīng)有不少成功的范例 .其實(shí)在日常生活中我們也可以看到許多數(shù)據(jù)挖掘的應(yīng)用 .例如 ,如果你在滬上一家比較著名的電子商務(wù)網(wǎng)站購(gòu)買(mǎi)了一張周星馳的經(jīng)典搞笑片 ”大話西游 ”,該網(wǎng)站會(huì)提醒你 , 【購(gòu)買(mǎi)該商品的用戶還買(mǎi)了這些商品】 行運(yùn)一條龍 97家有喜事 武狀元蘇乞兒 月光寶盒 秀蘭鄧波兒（ 12 套裝） 這些就是用數(shù)據(jù)挖掘技術(shù)從購(gòu)買(mǎi)這部片子的人群中統(tǒng)計(jì)出來(lái)的 .當(dāng)然這只是一種比較簡(jiǎn)單的應(yīng)用 .更復(fù)雜的應(yīng)用見(jiàn)下面這個(gè)例子 : 美國(guó) Firstar 銀行使用 Marksman 數(shù)據(jù)挖掘工具，根據(jù)客戶的消費(fèi)模式預(yù)測(cè)何時(shí)為客戶提供何種產(chǎn)品。 D是交易集合，其中每個(gè)交易 T是一個(gè)項(xiàng)的集合并且 T?L。例如，隨機(jī)取樣，數(shù)據(jù)集中每一組觀測(cè)值都有相同的被取樣概率；等距取樣，對(duì)數(shù)據(jù)編號(hào)，取樣的觀測(cè)值之間的距離相等；分層取樣，將樣本總體分成若干層次，每個(gè) 層次中的觀測(cè)值都具有相同的被選用概率，但不同層次之間設(shè)定的概率可不同，使模型具有更好的擬和度；起始順序取樣，從輸入數(shù)據(jù)的起始處開(kāi)始取樣，對(duì)取樣數(shù)量預(yù)先規(guī)定；分類(lèi)取樣，按觀測(cè)值的某種屬性分類(lèi)，取樣以類(lèi)為單位。 本文所基于的程序?qū)崿F(xiàn)即是屬于上面數(shù)據(jù)采掘部分 ,數(shù)據(jù)采掘過(guò)程中的關(guān)聯(lián)規(guī)則部分 . 程序所要實(shí)現(xiàn)的 FPgrowth 算法是一個(gè)頻繁集產(chǎn)生算法 ,與一般的類(lèi)似于 Apriori 的頻繁集產(chǎn)生算法相比 ,FPgrowth 的優(yōu)點(diǎn)在于它不需要產(chǎn)生大量的候選集 ,因而在時(shí)間和空間上都有很好的效率 .關(guān)于 FPgrowth 請(qǐng)參看本部分中的算法描述部分。 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) ６ for(tit=pTablebegin()。 Item()。 bool operator==(const Itemamp。}。 typedef DB::iterator DB_Iter。 int count。 name=。 Entry()。 l,const Entryamp。 r)來(lái)實(shí)現(xiàn)比較 .比較的原則可以在這個(gè)函數(shù)的定義中看到 .count 較大的比較大 ,count 一樣的其 name 按字典序較前面的較大 . 算法實(shí)現(xiàn)細(xì)節(jié) 本程序的輸入和最終輸出都需要訪問(wèn)數(shù)據(jù)庫(kù) ,因此首先對(duì)程序涉及到數(shù)據(jù)庫(kù)訪問(wèn)的部分做一下說(shuō)明 . 因?yàn)槭褂昧?ADO(ActiveX Data Object)方式訪問(wèn)數(shù)據(jù)庫(kù) ,在程序的源代碼中有這樣兩行語(yǔ)句 : import c:\program files\mon files\system\ado\ no_namespace rename(EOF,adoEOF) import c:\program files\mon files\system\ole db\ rename_namespa