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