【正文】 ,數(shù)據(jù)采掘過程中的關(guān)聯(lián)規(guī)則部分 . 程序所要實現(xiàn)的 FPgrowth 算法是一個頻繁集產(chǎn)生算法 ,與一般的類似于 Apriori 的頻繁集產(chǎn)生算法相比 ,FPgrowth 的優(yōu)點在于它不需要產(chǎn)生大量的候選集 ,因而在時間和空間上都有很好的效率 .關(guān)于 FPgrowth 請參看本部分中的算法描述部分。 數(shù)據(jù)采掘 即對經(jīng)過預(yù)處理的數(shù)據(jù)進行采掘，可分為兩個模塊： （ 1）數(shù)據(jù)采掘數(shù)據(jù)庫 在進行數(shù)據(jù)采掘分析模型的操作之前，要建立一個數(shù)據(jù)采掘的數(shù)據(jù)庫 (DMDB)，放置此次要進行操作的數(shù)據(jù)，可預(yù)先進行一些諸如變量最大、最小、平均、標(biāo)準(zhǔn)差等處理，為數(shù)據(jù)一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) ５ 采掘建立一個良好的工作環(huán)境。例如，隨機取樣，數(shù)據(jù)集中每一組觀測值都有相同的被取樣概率；等距取樣，對數(shù)據(jù)編號，取樣的觀測值之間的距離相等；分層取樣，將樣本總體分成若干層次，每個 層次中的觀測值都具有相同的被選用概率，但不同層次之間設(shè)定的概率可不同，使模型具有更好的擬和度；起始順序取樣，從輸入數(shù)據(jù)的起始處開始取樣，對取樣數(shù)量預(yù)先規(guī)定；分類取樣，按觀測值的某種屬性分類，取樣以類為單位。還沒有其他數(shù)據(jù)來驗證得到的規(guī)則的正確性 . 除了支持度和可信度還有其他的關(guān)聯(lián)規(guī)則評價標(biāo)準(zhǔn)如改善度 (lift)和興趣度 (interest). 本文的實現(xiàn)當(dāng)中 ,對支持度的定義和上述不同 ,參見第 5 部分 . 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) ４ 4．?dāng)?shù)據(jù)采掘工具的研制及其應(yīng)用 “數(shù)據(jù)采掘工具的研制及其應(yīng)用”（ 8633060205）是國家 863項目，是前一階段 863項目研究的繼續(xù)，由復(fù)旦大 學(xué)計算機系數(shù)據(jù)庫組承擔(dān)。 D是交易集合，其中每個交易 T是一個項的集合并且 T?L。 關(guān)聯(lián)規(guī)則是關(guān)聯(lián)分析中的一種常用技術(shù)（另一種是序列模式）。 數(shù)據(jù)挖掘的主要過程如下 : 1. 確定業(yè)務(wù)對象 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) ２ 清晰地定義出業(yè)務(wù)問題 ,認(rèn)清數(shù)據(jù)挖掘的目的是數(shù)據(jù)挖掘的重要一步 .挖掘的最后結(jié)構(gòu)是不可預(yù)測的 ,但要探索的問題應(yīng)是有預(yù)見的 ,為了數(shù)據(jù)挖掘而數(shù)據(jù)挖掘則帶有盲目性 ,是不會成功的 . 2. 數(shù)據(jù)準(zhǔn)備 1) 數(shù)據(jù)的選擇 搜索所有與業(yè)務(wù)對象有關(guān)的內(nèi)部和外部數(shù)據(jù)信息 ,并從中選擇出適用于數(shù)據(jù)挖掘應(yīng)用的數(shù)據(jù) . 2) 數(shù)據(jù)的預(yù)處理 研究數(shù)據(jù)的質(zhì)量 ,為進一步的分析作準(zhǔn)備 .并確定將要進行的挖掘操作的類型 . 3) 數(shù)據(jù)的轉(zhuǎn)換 將數(shù)據(jù)轉(zhuǎn)換成一個分析模型 .這個分析模型是針對挖掘算法建立的 .建立一個真正適合挖掘算法的分析模型是數(shù)據(jù)挖掘成功的關(guān)鍵 . 3. 數(shù)據(jù)挖掘 對所得到的經(jīng)過轉(zhuǎn)換的數(shù)據(jù)進行挖掘 .除了完善從選擇合適的挖掘算法 外 ,其余一切工作都能自動地完成 . 4. 結(jié)果分析 解釋并評估結(jié)果 .其使用的分析方法一般應(yīng)作數(shù)據(jù)挖掘操作而定 ,通常會用到可視化技術(shù) . 5. 知識的同化 將分析所得到的知識集成到業(yè)務(wù)信息系統(tǒng)的組織結(jié)構(gòu)中去 . 數(shù)據(jù)挖掘技術(shù)目前已經(jīng)有不少成功的范例 .其實在日常生活中我們也可以看到許多數(shù)據(jù)挖掘的應(yīng)用 .例如 ,如果你在滬上一家比較著名的電子商務(wù)網(wǎng)站購買了一張周星馳的經(jīng)典搞笑片 ”大話西游 ”,該網(wǎng)站會提醒你 , 【購買該商品的用戶還買了這些商品】 行運一條龍 97家有喜事 武狀元蘇乞兒 月光寶盒 秀蘭鄧波兒（ 12 套裝） 這些就是用數(shù)據(jù)挖掘技術(shù)從購買這部片子的人群中統(tǒng)計出來的 .當(dāng)然這只是一種比較簡單的應(yīng)用 .更復(fù)雜的應(yīng)用見下面這個例子 : 美國 Firstar 銀行使用 Marksman 數(shù)據(jù)挖掘工具，根據(jù)客戶的消費模式預(yù)測何時為客戶提供何種產(chǎn)品。在這種需求牽引下，匯聚了不同領(lǐng)域的研究者，尤其是數(shù)據(jù)庫技術(shù)、人工智能技術(shù)、數(shù) 理統(tǒng)計、可視化技術(shù)、并行計算等方面的學(xué)者和工程技術(shù)人員，投身到數(shù)據(jù)挖掘這一新興的研究領(lǐng)域，形成新的技術(shù)熱點。原始數(shù)據(jù)可以是結(jié)構(gòu)化的，如關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)；也可以是半結(jié)構(gòu)化的，如文本、圖形和圖像數(shù)據(jù)；甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。 1．介紹 數(shù)據(jù)挖掘技術(shù)的出現(xiàn)是伴隨著當(dāng)今時代信息的爆炸性增長和人們面對紛繁的數(shù)據(jù)得到?jīng)Q策支持而出現(xiàn)的 .數(shù)據(jù)挖掘工具中要實現(xiàn)的一個很重要的功能就是關(guān)聯(lián)規(guī)則的找尋，而關(guān)聯(lián)規(guī)則找尋的第一步就是要找到相應(yīng)的頻繁集 . 本文就是建立在對一個頻繁集產(chǎn)生算法的分析和實現(xiàn)的基礎(chǔ)上的 .通過一個程序具體實現(xiàn)了 FPgrowth算法 ,并將它作為一個使用數(shù)據(jù)挖掘工具 ,ARMiner的一部分 . 本文的第 2部分將介紹一些數(shù) 據(jù)挖掘的基本知識 . 第 3部分討論關(guān)聯(lián)規(guī)則的一些問題 . 第 4部分是本文所實現(xiàn)的程序所屬的數(shù)據(jù)挖掘工具 ARMiner的一些介紹 . 第 5部分結(jié)合程序設(shè)計著重討論一下本文是怎樣實現(xiàn) FPgrowth算法的。 FPgrowth算法主要通過 FPtree來構(gòu)造頻繁集。這種算法有一個很大的缺點，就是使用了不斷產(chǎn)生候選集并加以測試的方式來得到頻繁集。 目 錄 摘要 ： ................................................................................................... １ 1．介紹 ................................................................................................. １ ............................................................................................ １ ............................................................................................ ２ 4．?dāng)?shù)據(jù)采掘工具的研制及其應(yīng)用 ...................................................... ４ ............................................................................................ ５ 算法描述 ............................................................................................ ６ 數(shù)據(jù)結(jié)構(gòu) ........................................................................................ １０ 算法實現(xiàn)細(xì)節(jié) ................................................................................ １３ ................................................................................................ ２０ ................................................................................................ ２０ 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １ 摘要 ： 關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘是一個重要的研究內(nèi)容。但是，產(chǎn)生候選集的代價是很大的。 FPtree 是一個數(shù)據(jù)庫里跟產(chǎn)生頻繁集有關(guān)的信息的壓縮表示。 數(shù)據(jù)挖掘（ Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。發(fā)現(xiàn)知識的方法可以是數(shù)學(xué)的，也可以是非數(shù)學(xué)的；可以是演繹的，也可以是歸納的。 這里所說的知識發(fā)現(xiàn)，不是要求發(fā)現(xiàn)放之四海而皆準(zhǔn)的真理，也不是要去發(fā)現(xiàn)嶄新的自然科學(xué)定理和純數(shù)學(xué)公式，更不是什么機器定理證明。 Firstar銀行市場調(diào)查和數(shù)據(jù)庫營銷部經(jīng)理發(fā)現(xiàn)：公共數(shù)據(jù)庫中存儲著關(guān)于每位消費者的大量信息，關(guān)鍵是要透徹分析消費者投入到新產(chǎn)品中的原因，在數(shù)據(jù)庫中找到一種模式，從而能夠為每種新產(chǎn)品找到最合適的消費者。關(guān)聯(lián)規(guī)則是尋找在同一一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) ３ 個事件中出現(xiàn)的不同項的相關(guān)性。每一個交易 T 都有一個唯一的標(biāo)識， TID。目前已經(jīng)設(shè)計并實現(xiàn)系統(tǒng)原型數(shù)據(jù)采掘工具 ARMiner（圖 1）。 （ 3）數(shù)據(jù)篩選 通過數(shù)據(jù)篩選篩選掉不希望包括進來的觀測值。 （ 2）數(shù)據(jù)采掘過程 利用某一種數(shù)據(jù)采掘算法進行數(shù)據(jù)采掘。 程序的實現(xiàn)是基于 Windows95/NT 平臺 ,編譯器是 Visual C++數(shù)據(jù)挖掘工具 ARMiner 相兼容 . 程序在定義數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)算法的時候主要有以下一些考量。fit!=pSetend()。tit!=pTableend()。否則 ,創(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)建一個標(biāo)記為 ”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