基于web服務(wù)的分布式數(shù)據(jù)挖掘系統(tǒng)研究

1、<p><b>　　華中科技大學(xué)</b></p><p><b>　　碩士學(xué)位論文</b></p><p>　　基于Web服務(wù)的分布式數(shù)據(jù)挖掘系統(tǒng)研究</p><p><b>　　姓名：侯敬軍</b></p><p><b>　　申請學(xué)位級別：碩士</

2、b></p><p><b>　　專業(yè)：水利水電工程</b></p><p><b>　　指導(dǎo)教師：曾致遠</b></p><p><b>　　20040501</b></p><p><b>　　摘</b></p><p>

3、<b>　　要</b></p><p><b>　　由于以下原因</b></p><p>　　原有的集中式數(shù)據(jù)挖掘越來越不適應(yīng)新的需求</p><p>　　1 待處理的數(shù)據(jù)源是分布式存放在網(wǎng)絡(luò)的不同主機上的</p><p>　?。?于網(wǎng)絡(luò)帶寬的限制 數(shù)據(jù)的私有性和安全性 系統(tǒng)的不兼容性等原因 把所&

4、lt;/p><p>　　有數(shù)據(jù)源集到一個集中的地方</p><p><b>　　如數(shù)據(jù)倉庫</b></p><p>　　進行集中數(shù)據(jù)挖掘往往是不現(xiàn)實的</p><p>　　3 對挖掘系統(tǒng)的開放性和易用性的要求越來越高</p><p>　　分布式數(shù)據(jù)挖掘技術(shù)就是為了解決上述問題而被提出的</p&g

5、t;<p><b>　　目前</b></p><p><b>　　該研究領(lǐng)域的</b></p><p>　　兩個重要問題式設(shè)計合適的分布式數(shù)據(jù)挖掘系統(tǒng)的體系結(jié)構(gòu)和相應(yīng)的分布式挖掘算</p><p>　　法 本文將最新的分布式組件技術(shù)</p><p>　　解決上述兩個問題方面做了一些嘗試

6、</p><p>　　Web 服務(wù)技術(shù)引入分布式數(shù)據(jù)挖掘領(lǐng)域</p><p><b>　　在</b></p><p>　　首先介紹了分布式數(shù)據(jù)挖掘產(chǎn)生的背景</p><p><b>　　研究現(xiàn)狀和成果</b></p><p><b>　　存在的問題以及關(guān)</b

7、></p><p>　　聯(lián)規(guī)則挖掘的不同算法 接著介紹了 Web 服務(wù)及其相關(guān)技以及 Web 服務(wù)技術(shù)的優(yōu)點</p><p><b>　　和其適用場合</b></p><p>　　給出了 Web 服務(wù)技術(shù)與分布式數(shù)據(jù)挖掘的結(jié)合點 然后提出了一種</p><p><b>　　跨平臺的</b>&l

8、t;/p><p><b>　　易擴展的</b></p><p>　　適用于分布環(huán)境下的基于 Web 服務(wù)的分布式數(shù)據(jù)挖掘系統(tǒng)架</p><p><b>　　構(gòu)</b></p><p>　　并結(jié)合上述系統(tǒng)的特點</p><p>　　給出一個該系統(tǒng)中的分布式關(guān)聯(lián)規(guī)則挖掘算法</

9、p><p>　　FDM-GS(FDM with global site) 該算法應(yīng)用了新的候選集剪枝策略</p><p><b>　　可有效減小候</b></p><p>　　選集的規(guī)模和收集候選集支持計數(shù)時的網(wǎng)絡(luò)信息流量</p><p><b>　　了詳細的說明</b></p><

10、p>　　并結(jié)合一個實例對該算法做</p><p><b>　　關(guān)鍵詞</b></p><p>　　數(shù)據(jù)挖掘 關(guān)聯(lián)規(guī)則 分布式計算 組件技術(shù) Web 服務(wù)</p><p><b>　　IV</b></p><p><b>　　Abstract</b></p>

11、<p>　　For the following reasons, the original centralized data mining became more and</p><p>　　more out of date:</p><p>　　1. The data source need to be processed is distributed on the diffe

12、rent computers in</p><p>　　the networks.</p><p>　　2. For the constrain of networks band, the privacy and safety of data, the</p><p>　　incompatibility of systems, etc, it is not real

13、istic to put all data source in a place (for</p><p>　　example, the data warehouse) for centralized data mining.</p><p>　　3. More and more demands have addressed on the openness and easy accessib

14、ility.</p><p>　　The distributed data mining technology was presented for the problems mentioned</p><p>　　above. Presently, the two important matters in this field are that, design for suitable&l

15、t;/p><p>　　architecture of distributed data mining systems and corresponding distributed mining</p><p>　　algorithms. This article introduced the latest technology for distributed component</p>

16、;<p>　　technology — Web services technology into distributed data mining field, and took some</p><p>　　tentative efforts in solving the aforementioned two problems.</p><p>　　In the beginn

17、ing, the background for bringing distributed data mining, the status of</p><p>　　research and research achievements, the existing problems, and algorithm for association</p><p>　　rules were intr

18、oduced. And then, the web services and related technology, and the</p><p>　　advantages and disadvantages of web service technology were introduced, and the</p><p>　　connecting point for web serv

19、ice technology and distributed data mining. And then a</p><p>　　multi-platform, easy-extensible, suitable for distributed environment and web-based</p><p>　　services distributed association rule

20、 mining algorithm FDM-GS (FDM with global site)</p><p>　　were proposed. This algorithm adopted a new pruning strategy of candidate set and it can</p><p>　　decrease the scale of candidate set and

21、 the networks information flow for collecting</p><p><b>　　V</b></p><p>　　candidate set supporting counts. In addition, the detailed explanation for this algorithm</p><p>

22、;　　was made with a practical example.</p><p>　　Keywords: Data mining, Association rules, Distributed computing, Component</p><p>　　technology, Web service</p><p><b>　　VI</b

23、></p><p><b>　　獨創(chuàng)性聲明</b></p><p>　　本人聲明所呈交的學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進行的研究工作及取得的研究</p><p>　　成果 盡我所知 除文中已經(jīng)標明引用的內(nèi)容外 本論文不包含任何其他個人或集體已</p><p>　　經(jīng)發(fā)表或撰寫過的研究成果 對本文的研究做出貢獻的個人和

24、集體 均已在文中以明確</p><p>　　方式標明 本人完全意識到本聲明的法律結(jié)果由本人承擔(dān)</p><p><b>　　學(xué)位論文作者簽名</b></p><p><b>　　日期</b></p><p><b>　　年</b></p><p><

25、;b>　　月</b></p><p><b>　　日</b></p><p>　　學(xué)位論文版權(quán)使用授權(quán)書</p><p>　　本學(xué)位論文作者完全了解學(xué)校有關(guān)保留 使用學(xué)位論文的規(guī)定 即 學(xué)校有權(quán)保留</p><p>　　并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版 允許論文被查閱和借閱 本人授<

26、/p><p>　　權(quán)華中科技大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索 可以采</p><p><b>　　用影印</b></p><p>　　縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文</p><p><b>　　保密</b></p><p>　　在_______

27、_____年解密后適用本授權(quán)書</p><p><b>　　本論文屬于 不保密</b></p><p><b>　　請在以上方框內(nèi)打</b></p><p><b>　　學(xué)位論文作者簽名</b></p><p><b>　　指導(dǎo)教師簽名</b></p

28、><p><b>　　日期</b></p><p><b>　　年</b></p><p><b>　　月</b></p><p><b>　　日</b></p><p><b>　　日期</b></p>

29、;<p><b>　　年</b></p><p><b>　　月</b></p><p><b>　　日</b></p><p><b>　?。薄　【w　論　</b></p><p>　　1.1 課題的目的和意義　</p><

30、;p><b>　　近來</b></p><p><b>　　由于挖掘?qū)ο?lt;/b></p><p><b>　　數(shù)據(jù)源</b></p><p><b>　　在地理上的分布</b></p><p>　　數(shù)據(jù)集中代價太大或根本無</p>&l

31、t;p><b>　　法進行</b></p><p>　　挖掘系統(tǒng)所涉及的軟組件以及用戶在地理上的分布</p><p><b>　　遺留系統(tǒng)的重用和集</b></p><p>　　成 成本方面的考慮等原因 分布式數(shù)據(jù)挖掘受到越來越多的重視 在目前的分布</p><p>　　式數(shù)據(jù)開采的研究工作中

32、</p><p>　　非常重要的一個方面是如何設(shè)計分布式數(shù)據(jù)開采系統(tǒng)的</p><p><b>　　體系結(jié)構(gòu)</b></p><p>　　真正能支持各種分布式開采算法 真正實現(xiàn)平臺無關(guān)性 本文就如何解</p><p>　　決上述問題做了一些探索</p><p>　　1.2 本文的主要研究內(nèi)容和創(chuàng)新

33、點</p><p>　　1 介紹了分布式數(shù)據(jù)挖掘產(chǎn)生的背景 研究現(xiàn)狀和成果</p><p><b>　　存在的問題以及關(guān)</b></p><p>　　聯(lián)規(guī)則挖掘的不同算法</p><p>　　2 概述了 Web 服務(wù)及其相關(guān)技術(shù) 介紹了 Web 服務(wù)技術(shù)的優(yōu)點和其適用場合</p><p>　　3

34、給出了 Web 服務(wù)技術(shù)與分布式數(shù)據(jù)挖掘的結(jié)合點</p><p><b>　　提出一種跨平臺的</b></p><p><b>　　易</b></p><p>　　擴展的 適用于分布環(huán)境下的基于 Web 服務(wù)的分布式數(shù)據(jù)挖掘系統(tǒng)架構(gòu)</p><p><b>　　4 上述系統(tǒng)的特點</

35、b></p><p>　　FDM with global site</p><p><b>　　1.3 章節(jié)安排</b></p><p><b>　　全文章節(jié)安排如下</b></p><p>　　給出一個該系統(tǒng)中的分布式關(guān)聯(lián)規(guī)則挖掘算法 FDM-GS</p><p>　

36、　并結(jié)合一個實例對該算法做了詳細的說明</p><p><b>　　第一章</b></p><p><b>　　緒論</b></p><p>　　介紹了本論文研究課題的出發(fā)點 給出了本文的主要研究內(nèi)容和創(chuàng)新點 同時</p><p>　　對文章的組織進行了敘述</p><p>

37、<b>　　1</b></p><p>　　第二章 分布式數(shù)據(jù)挖掘概述</p><p>　　簡單介紹數(shù)據(jù)挖掘技術(shù)產(chǎn)生的背景以及數(shù)據(jù)挖掘的主要功能 接著給出了分布</p><p>　　式數(shù)據(jù)挖掘的定義 介紹了進行分布式數(shù)據(jù)挖掘的必要性和需要解決好的問題以及</p><p>　　分布式數(shù)據(jù)挖掘的研究現(xiàn)狀</p>

38、<p><b>　　成果以及趨勢</b></p><p><b>　　第三章</b></p><p><b>　　關(guān)聯(lián)規(guī)則挖掘</b></p><p>　　首先結(jié)合一個例子給出了關(guān)聯(lián)規(guī)則挖掘的定義和其相關(guān)術(shù)語 然后介紹了關(guān)聯(lián)</p><p>　　規(guī)則挖掘的經(jīng)典頻繁項

39、集發(fā)現(xiàn)算法 Apriori 算法及其改進以及其它的算法</p><p><b>　　第四章</b></p><p><b>　　Web 服務(wù)技術(shù)</b></p><p>　　介紹了 Web 服務(wù)技術(shù)出現(xiàn)的背景及其相關(guān)技術(shù)</p><p>　　論述了 Web 服務(wù)技術(shù)的優(yōu)點</p>&l

40、t;p><b>　　及其適用場合</b></p><p>　　第五章 基于 Web 服務(wù)的分布式數(shù)據(jù)挖掘體系結(jié)構(gòu)</p><p>　　首先介紹了 Web 服務(wù)技術(shù)和分布式數(shù)據(jù)挖掘的結(jié)合點</p><p><b>　　接著提出了一種基于</b></p><p>　　Web 服務(wù)的分布式數(shù)據(jù)挖掘體

41、系結(jié)構(gòu) 然后給出了一個該體系結(jié)構(gòu)下的分布式關(guān)聯(lián)</p><p><b>　　規(guī)則挖掘算法</b></p><p>　　并通過一個實例詳細說明</p><p><b>　　第五章</b></p><p><b>　　總結(jié)與展望</b></p><p>&l

42、t;b>　　對全文進行了總結(jié)</b></p><p>　　并提出了有待進一步研究的內(nèi)容</p><p><b>　　2</b></p><p>　　2 分布式數(shù)據(jù)挖掘概述</p><p>　　2.1 數(shù)據(jù)挖掘簡介</p><p><b>　　近年來</b>&

43、lt;/p><p>　　隨著越來越多的企業(yè)將通信</p><p>　　計算機和網(wǎng)絡(luò)技術(shù)引入企業(yè)的日常工作</p><p><b>　　和業(yè)務(wù)處理當中</b></p><p>　　企業(yè)的信息化程度不斷提高</p><p>　　現(xiàn)代信息技術(shù)的廣泛應(yīng)用顯著的提</p><p>　　高

44、了企業(yè)的工作效率和經(jīng)濟效益</p><p><b>　　然而</b></p><p>　　在享用信息技術(shù)帶來的方便 快捷的同時 新的問題和需求也在不斷涌</p><p>　　現(xiàn) 其中比較突出的有</p><p><b>　　第一</b></p><p>　　企業(yè)積累了大量的歷

45、史數(shù)據(jù)</p><p><b>　　這些數(shù)據(jù)對企業(yè)當前</b></p><p>　　的日常經(jīng)營活動幾乎沒有任何的使用價值</p><p>　　完全儲藏這些歷史數(shù)據(jù)會對企業(yè)造成很</p><p><b>　　大的困難和開銷</b></p><p>　　但其中顯然蘊涵著對企業(yè)高層

46、次的決策有著寶貴價值的信息</p><p><b>　　簡</b></p><p>　　單的將它們丟棄是很大的浪費</p><p>　　希望能夠?qū)ζ溥M行更高層次的分析 以便利用好這</p><p><b>　　些數(shù)據(jù)</b></p><p>　　雖然目前的數(shù)據(jù)庫系統(tǒng)可以高效的

47、實現(xiàn)數(shù)據(jù)的錄入</p><p><b>　　查詢 統(tǒng)計等功能</b></p><p>　　但是這些功能都是對企業(yè)的宏觀經(jīng)營決策沒有多大幫助的低層次的 微觀的功能</p><p>　　無法發(fā)現(xiàn)海量數(shù)據(jù)中存在的關(guān)系和規(guī)則 無法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測未來的發(fā)展趨勢</p><p>　　缺乏發(fā)現(xiàn)數(shù)據(jù)背后隱藏的知識的手段 導(dǎo)致了 數(shù)據(jù)

48、豐富</p><p><b>　　但信息貧乏</b></p><p><b>　　理解這些</b></p><p>　　海量歷史數(shù)據(jù)已經(jīng)遠遠超出了人的能力</p><p><b>　　結(jié)果這些數(shù)據(jù)變成了</b></p><p><b>　　數(shù)據(jù)

49、墳?zāi)?lt;/b></p><p><b>　　難</b></p><p>　　得再訪問的數(shù)據(jù)檔案 第二</p><p>　　上述的大量歷史數(shù)據(jù)是以各種各樣的形式存在著的</p><p>　　直接在其上進行高層次的分析是幾乎無法實現(xiàn)的</p><p>　　層次分析能夠順利進行</p&g

50、t;<p>　　必須對上述信息做初加工</p><p><b>　　使高</b></p><p><b>　　有需求就有供給</b></p><p>　　為解決上述問題 數(shù)據(jù)挖掘技術(shù)應(yīng)運而生</p><p><b>　　許多研究成果和</b></p>

51、<p><b>　　應(yīng)用產(chǎn)品不斷涌現(xiàn)</b></p><p>　　該課題依然是當前信息技術(shù)領(lǐng)域的熱門研究方向之一</p><p>　　那么到底什么是數(shù)據(jù)挖掘 Data Mining 呢</p><p>　　許多文獻[1][2]對其有著不同的定義</p><p>　　但其共同點都大致為 數(shù)據(jù)挖掘是從大量的 不完

52、全的</p><p><b>　　有噪聲的 模糊的</b></p><p><b>　　隨機</b></p><p><b>　　的數(shù)據(jù)中</b></p><p>　　提取隱含在其中 人們事先不知道的但又是潛在有用的信息和知識的過</p><p>　　程

53、 數(shù)據(jù)挖掘提取的知識可以表示為概念</p><p><b>　　規(guī)律</b></p><p><b>　　模式</b></p><p><b>　　約束</b></p><p><b>　　可視化</b></p><p><b

54、>　　數(shù)據(jù)挖掘</b></p><p><b>　　3</b></p><p>　　算法的好壞將直接影響到所發(fā)現(xiàn)知識的好壞 數(shù)據(jù)挖掘的任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)模式</p><p>　　2.2 數(shù)據(jù)挖掘的功能</p><p>　　數(shù)據(jù)挖掘功能用于制定數(shù)據(jù)挖掘</p><p>　　任務(wù)中要

55、找的模式類型 數(shù)據(jù)挖掘任務(wù)</p><p>　　一般可以分為兩類 描述和預(yù)測 描述</p><p>　　性挖掘任務(wù)刻畫數(shù)據(jù)庫中數(shù)據(jù)的一般</p><p>　　特性 預(yù)測性數(shù)據(jù)挖掘任務(wù)在當前數(shù)據(jù)</p><p>　　上進行推斷 以進行預(yù)測</p><p>　　下面介紹一下數(shù)據(jù)挖掘功能以及它們可以發(fā)現(xiàn)的模式類型</p

56、><p><b>　　1 特征化和區(qū)分</b></p><p><b>　　數(shù)據(jù)特征化是目標類</b></p><p><b>　　所研究的對象</b></p><p>　　數(shù)據(jù)的一般特征或特征的匯總 數(shù)據(jù)特</p><p>　　征的輸出可以用多種形式提供&

57、lt;/p><p><b>　　包括餅圖</b></p><p><b>　　條圖</b></p><p><b>　　曲線</b></p><p>　　多維數(shù)據(jù)立方體和包括交</p><p><b>　　叉表在內(nèi)的多維表</b><

58、;/p><p>　　數(shù)據(jù)區(qū)分是將目標類對象的一般特征與一個或多個對比類對象的一般特征比</p><p>　　較 區(qū)分描述的形式類似與特征描述</p><p>　　但區(qū)分描述應(yīng)當包括比較度量</p><p><b>　　幫助區(qū)分目</b></p><p><b>　　標類和對比類</b&

59、gt;</p><p>　　用戶應(yīng)當能夠?qū)μ卣骱蛥^(qū)分描述的輸出進行操作</p><p><b>　　2 關(guān)聯(lián)分析</b></p><p>　　關(guān)聯(lián)分析用于發(fā)現(xiàn)關(guān)聯(lián)規(guī)則</p><p>　　若兩個或多個數(shù)據(jù)項的取值重復(fù)出現(xiàn)且概率很高</p><p>　　時 它就存在著某種關(guān)聯(lián)</p>

60、<p>　　可以建立起這些數(shù)據(jù)項的關(guān)聯(lián)規(guī)則</p><p><b>　　關(guān)聯(lián)分析的目的是</b></p><p>　　找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)網(wǎng) 在大型數(shù)據(jù)庫中 這種關(guān)聯(lián)規(guī)則是很多的 一般用 支</p><p><b>　　4</b></p><p><b>　　持度</b&

61、gt;</p><p><b>　　和</b></p><p><b>　　置信度</b></p><p>　　兩個閾值來淘汰那些無用的關(guān)聯(lián)規(guī)則</p><p><b>　　3 分類</b></p><p>　　分類是數(shù)據(jù)挖掘中應(yīng)用得最多的方法</

62、p><p>　　分類是找出一個類別的概念描述</p><p><b>　　它代</b></p><p>　　表了這類數(shù)據(jù)的整體信息</p><p><b>　　即該類的內(nèi)涵描述</b></p><p>　　一般用規(guī)則或決策樹模式表示</p><p><

63、;b>　　一</b></p><p>　　個類的內(nèi)涵描述分為特征性描述和區(qū)別性描述</p><p>　　特征性描述是對類中對象的共同特</p><p><b>　　征的描述</b></p><p>　　區(qū)別性描述是對兩個或多個類之間的區(qū)別的描述</p><p><b>

64、　　4 聚類分析</b></p><p>　　數(shù)據(jù)庫中的數(shù)據(jù)可以分為一系列有意義的子集</p><p><b>　　或稱為類</b></p><p><b>　　在同一類別中</b></p><p><b>　　個</b></p><p>&

65、lt;b>　　體之間的距離較小</b></p><p>　　而不同類別的個體之間距離較大</p><p>　　但是如何劃分這些子集</p><p><b>　　即</b></p><p>　　如何標記這些不同的類</p><p>　　聚類可以用于產(chǎn)生這種標記 待劃分的對象根據(jù)最大

66、化</p><p><b>　　類內(nèi)的相似性</b></p><p>　　最小化類間的相似性的原則進行聚類或分組</p><p><b>　　5 序貫?zāi)Ｊ?lt;/b></p><p>　　通過時間序列搜索出重復(fù)發(fā)生概率較高的模式</p><p>　　這里強調(diào)時間序列的影響<

67、/p><p><b>　　例</b></p><p><b>　　如</b></p><p>　　在所有購買激光打印機的人中</p><p>　　半年后有 80%的人再購買新硒鼓</p><p><b>　　20%的人用</b></p><

68、;p><b>　　舊硒鼓裝碳粉</b></p><p><b>　　6 孤立點分析</b></p><p>　　數(shù)據(jù)庫中的數(shù)據(jù)常有一些異常記錄 這些記錄稱為孤立點</p><p><b>　　從數(shù)據(jù)庫中檢測出</b></p><p>　　這些孤立點很有意義 孤立點包括很多

69、潛在的知識 如分類中的反常實例 不滿足</p><p>　　規(guī)則的特例 觀測結(jié)果與模型預(yù)測值的偏差 量值隨時間的變化等 孤立點分析基</p><p>　　本方法是尋找觀測結(jié)果與參照之間的差別</p><p>　　2.3 分布式數(shù)據(jù)挖掘簡介</p><p>　　最近 分布式數(shù)據(jù)挖掘 DDM 又吸引了不少研究者的目光 并取得了一些進</p&

70、gt;<p><b>　　展</b></p><p>　　2.3.1 何謂分布式數(shù)據(jù)挖掘</p><p>　　所謂分布式數(shù)據(jù)挖掘有兩層含義 第一 就是使用分布式算法 從邏輯上或物</p><p><b>　　5</b></p><p>　　理上分布的數(shù)據(jù)源中發(fā)現(xiàn)知識的過程　</p

71、><p>　　這里主要強調(diào)數(shù)據(jù)源的分布性</p><p><b>　　第二</b></p><p><b>　　是</b></p><p>　　指與某個數(shù)據(jù)挖掘任務(wù)相關(guān)的用戶 數(shù)據(jù) 挖掘軟件以及其他軟組件是地理上分散</p><p><b>　　的</b>&

72、lt;/p><p>　　這里主要強調(diào)的是軟組件的分散性</p><p>　　2.3.2 分布式數(shù)據(jù)挖掘的必要性</p><p>　　為什么分布式數(shù)據(jù)挖掘會被重視呢</p><p>　　這是因為以下幾個因素</p><p>　?。保?shù)據(jù)挖掘的目標是大規(guī)模的數(shù)據(jù)集 而在現(xiàn)實環(huán)境中 絕大部分的大型數(shù)據(jù)</p>&l

73、t;p>　　庫都是以分布式的形式存在的 因此 提出新的分布式數(shù)據(jù)挖掘系統(tǒng)的體系結(jié)構(gòu)是</p><p><b>　　非常必要的</b></p><p>　?。玻┰跀?shù)據(jù)挖掘系統(tǒng)中 經(jīng)常需要來自不同站點的數(shù)據(jù)庫中的數(shù)據(jù) 這就使得數(shù)</p><p>　　據(jù)挖掘系統(tǒng)必須具有分布式挖掘的能力 同時也需要我們根據(jù)分布式數(shù)據(jù)挖掘的特</p>

74、<p>　　點設(shè)計出新的分布式數(shù)據(jù)挖掘算法</p><p>　?。常┯捎诰W(wǎng)絡(luò)帶寬的限制 數(shù)據(jù)的私有性和安全性 系統(tǒng)的不兼容性等原因 把</p><p>　　所有數(shù)據(jù)源集到一個集中的地方 如數(shù)據(jù)倉庫 進行集中數(shù)據(jù)挖掘往往是不現(xiàn)實的 　</p><p>　　４）上述三點都是因數(shù)據(jù)源的分布而帶來的問題 另外 成本是另一個必須考慮</p><

75、p>　　的因素 這主要是針對上述分布式數(shù)據(jù)挖掘的第二層含義而言的 為了完成不同的</p><p>　　數(shù)據(jù)挖掘任務(wù) 用戶必須使用許多不同的挖掘工具 在分布的環(huán)境下更是可能進一</p><p>　　步增加成本 因為這需要挖掘工具的多個拷貝 還有 為了節(jié)約投資 用戶往往希</p><p>　　望只使用那些能夠滿足他們需要的組件</p><p&g

76、t;<b>　　而不是整個軟件包</b></p><p><b>　　一個典型的例子是</b></p><p>　　用戶用一個供應(yīng)商的工具 例如一個較新的并且是免費的研究模型 來獲取他感興</p><p>　　趣的模式 然后用另一個供應(yīng)商的可視化工具來顯示這些模式 一個可能的解決方</p><p>

77、　　案是把這些分布的挖掘工具集成到一個數(shù)據(jù)挖掘應(yīng)用中</p><p><b>　　資 　</b></p><p>　　2.3.3 進行分布式數(shù)據(jù)挖掘需要解決的問題</p><p>　　這將大大減少用戶的投</p><p><b>　　在分布式數(shù)據(jù)挖掘中</b></p><p>

78、;　　有幾個技術(shù)細節(jié)需要注意</p><p>　?。保┤旨锌刂?為了方便地實現(xiàn)分布式數(shù)據(jù)挖掘 一個用于集中控制的站點</p><p>　　是必須的 在不存在全局控制站點情況下 整個系統(tǒng)的通訊開銷是非常巨大的 為</p><p>　　了得到全局知識 所有的站點將進行大量的廣播 比起使用全局控制站點的系統(tǒng)來</p><p><b>

79、　　6</b></p><p>　　說 開銷和難度無疑要大得多 此外 在某些分布式數(shù)據(jù)挖掘算法中 需要進行全</p><p>　　局范圍內(nèi)的決策 這也是引入全局控制站點的一個自然原因 實際上在引入了全局</p><p><b>　　控制站點后</b></p><p>　　系統(tǒng)的可擴展性和靈活性都得到了很好的支

80、持</p><p>　?。玻┎⑿泻头植际綌?shù)據(jù)挖掘算法 這實際上是針對性能問題提出來的 服務(wù)器端</p><p>　　的大容量數(shù)據(jù)集上運行數(shù)據(jù)挖掘要耗費很長時間 因為數(shù)據(jù)挖掘算法的時間復(fù)雜度</p><p>　　很高 一個比較好的方法是使用并行化數(shù)據(jù)挖掘算法</p><p>　　將數(shù)據(jù)集劃分成多個子集</p><p>　

81、　并行處理后合并各個子集的挖掘結(jié)果 這些算法應(yīng)該具有增量特點 它與數(shù)據(jù)庫結(jié)</p><p>　　合 可以不必重新挖掘全部數(shù)據(jù)</p><p><b>　?。常≈R共享</b></p><p>　　在各個站點間進行分布式挖掘時必須采用可以被理解的知識形</p><p>　　式 一是因為分布式數(shù)據(jù)挖掘一般包含面向知識的挖掘

82、 即在本地知識的基礎(chǔ)上挖</p><p>　　掘全局知識 所以必須采取能夠被統(tǒng)一理解的知識表示方式才能夠在各個站點間實</p><p>　　現(xiàn)協(xié)同挖掘 二是因為各個站點上的用戶可能需要訪問其它站點上的知識 這也需</p><p>　　要有一種通用的知識表示方式</p><p>　?。矗┓植际杰浖O(shè)計 當今系統(tǒng)設(shè)計軟件的重用和復(fù)用的要求越來越高

83、 對系統(tǒng)</p><p>　　設(shè)計的層次性也有很高要求 很多情況下 應(yīng)用開發(fā)主要是開發(fā)軟組件 然后再把</p><p>　　它們組合起來 軟組件是一種不和特定程序或計算機語言綁定的分布式對象 可以</p><p>　　跨越平臺的異構(gòu)性 具有封裝性 它和外界通過預(yù)先定義好的應(yīng)用程序接口來完成</p><p>　　交互 其最大的優(yōu)點是支持軟件復(fù)用

84、 系統(tǒng)設(shè)計人員可以使用現(xiàn)存的軟組件 這樣</p><p><b>　　可以優(yōu)化分工</b></p><p><b>　　大大減少編碼工作量</b></p><p><b>　　提高工作效率</b></p><p><b>　　降低成本</b></p&

85、gt;<p>　　2.3.4 分布式數(shù)據(jù)挖掘的研究現(xiàn)狀</p><p>　　雖然分布式數(shù)據(jù)開采是近幾年才提出的一個新的研究領(lǐng)域 但是已經(jīng)引起了相</p><p><b>　　當多的研究者的注意</b></p><p>　　取得了一定的進展[3]</p><p>　　PADMA[4]系統(tǒng)是 Hi11o1 Ka

86、rgupta 等提出的一個基于 Agent 的并行/分布式數(shù)據(jù)</p><p>　　挖掘系統(tǒng) 該系統(tǒng)不限定于特定的數(shù)據(jù)挖掘領(lǐng)域</p><p>　　PADMA 系統(tǒng)由如下組件構(gòu)成</p><p>　　數(shù)據(jù)挖掘 Agent 協(xié)調(diào)各 Agent 工作的 Facilitator 和用戶接口 數(shù)據(jù)挖掘 Agent 負責(zé)</p><p>　　讀取數(shù)據(jù)并

87、提取高層次的信息</p><p>　　Agent 通過 Facilitator 并行工作 Facilitator 負責(zé)協(xié)</p><p>　　調(diào)各 Agent 工作并提供信息給用戶接口</p><p>　　同時接收用戶的反饋信息給各個 Agent</p><p><b>　　7</b></p><p&

88、gt;　　PADMA 系統(tǒng)有一個圖形化的基于 Web 的用戶接口用來把各 Agent 提取的信息展現(xiàn)</p><p>　　給用戶 Facilitator 接收用戶接口以標準 SQL 格式提交的查詢 這些查詢被廣播給</p><p>　　各 Agent Agent 提取與特定查詢相關(guān)的信息 Facilitator 收集這些信息并將其展現(xiàn)</p><p>　　給用戶 該

89、系統(tǒng)使用 PPFS(Parallel Portable File System)開發(fā)</p><p><b>　　以面向?qū)ο蟮姆绞接?lt;/b></p><p><b>　　C++語言編碼</b></p><p>　　提供了一個可擴展的架構(gòu)</p><p>　　使用 MPI Message Passin

90、g Interface</p><p>　　進行底層的消息交換和通信 該系統(tǒng)可以劃分為如下三個功能模塊 并行數(shù)據(jù)讀取</p><p><b>　　和查詢處理模塊</b></p><p><b>　　收集匯總模塊</b></p><p>　　用戶交互和結(jié)果展現(xiàn)模塊</p><p&g

91、t;　　JAM Java Agents for Meta-learning</p><p><b>　　[5]</b></p><p>　　分布式數(shù)據(jù)開采系統(tǒng) 在這個系統(tǒng)中提出了使用 meta-learning 進行分布式數(shù)據(jù)開采</p><p><b>　　的思想</b></p><p>　　me

92、ta-learning 是一種計算高層 classifiers</p><p>　　稱為 meta-classifiers</p><p><b>　　的技術(shù)</b></p><p>　　即把各個數(shù)據(jù)庫上分別獨立計算的 classifiers 以某種原則匯集成高層 classifiers 的技</p><p><b

93、>　　術(shù)</b></p><p>　　該系統(tǒng)使用 JAVA 語言編寫</p><p>　　具有較好的平臺無關(guān)性</p><p>　　很多分布式數(shù)據(jù)挖掘系統(tǒng)都是針對數(shù)據(jù)源 水平劃分 的情形 即各個數(shù)據(jù)分</p><p>　　塊中的記錄具有相同的屬性結(jié)構(gòu)</p><p>　　Hi11o1 Kargupta

94、[6]等 最 近 提 出 一 種 稱 為</p><p>　　Collective Data Mining 的思想來實現(xiàn)對數(shù)據(jù)源 垂直劃分 的情形進行分布式數(shù)據(jù)</p><p>　　挖掘 其主要方法是首先各個站點根據(jù)自己的數(shù)據(jù)集獨立計算一個近似規(guī)范正交基</p><p>　　系數(shù) 然后從各個站點的數(shù)據(jù)集選取一些特定的樣本移到一個站點上 根據(jù)這個集</p>

95、<p>　　成數(shù)據(jù)集來計算針對于非線性交叉項的近似基系數(shù) 最后根據(jù)基系數(shù)將局部模型合</p><p>　　并成全局模型并提交給用戶</p><p>　　其它的分布式數(shù)據(jù)挖掘系統(tǒng)還有美國 Pittsburgh 大學(xué)的 Aronis 教授等設(shè)計的</p><p>　　World[7]系統(tǒng) Chavez 的 Challenger[8]系統(tǒng)等</p>

96、;<p>　　在目前的分布式數(shù)據(jù)開采的研究工作中 非常重要的一個方面是如何設(shè)計一個</p><p>　　分布式數(shù)據(jù)開采系統(tǒng)的體系結(jié)構(gòu) 真正能支持各種分布式開采算法 真正實現(xiàn)平臺</p><p>　　無關(guān)性 目前這方面的工作仍屬于起步階段</p><p><b>　　8</b></p><p><b&g

97、t;　　3 關(guān)聯(lián)規(guī)則挖掘</b></p><p>　　3.1 關(guān)聯(lián)規(guī)則的形式化定義</p><p>　　第二章中我們已經(jīng)提到過關(guān)聯(lián)規(guī)則</p><p>　　讓我們從一個典型的例子</p><p><b>　　購物籃分</b></p><p><b>　　析</b>

98、</p><p>　　給出關(guān)聯(lián)規(guī)則的形式化定義</p><p>　　以一個擁有大量商品的超級市場為例 為了更加了解顧客的購物習(xí)慣 以此決</p><p>　　定該賣什么商品 怎樣訂貨 怎樣在貨架上放置商品以吸引顧客購買 從而獲得最</p><p>　　大的利潤 為了做好這些決策 可以對一段時間內(nèi)積累的歷史數(shù)據(jù)利用計算機進行</p>

99、<p>　　分析 過去的交易記錄詳細的記載了每一筆業(yè)務(wù)中用戶購買商品的情況 就可以在</p><p>　　這些數(shù)據(jù)的基礎(chǔ)上分析得到顧客的購買習(xí)慣 如 顧客在購買餅干的同時往往也購</p><p>　　買了一定數(shù)量的牛奶 關(guān)聯(lián)規(guī)則正是對貨籃數(shù)據(jù)進行分析 以得到商品之間關(guān)系的</p><p>　　一種很流行的數(shù)據(jù)挖掘算法 當關(guān)聯(lián)規(guī)則被找到后 就可以利用這些

100、規(guī)則幫助管理</p><p><b>　　者進行決策</b></p><p>　?。保┤绻l(fā)現(xiàn)包含牛奶的所有規(guī)則</p><p>　　我們就知道為了增加牛奶的銷量該做些什</p><p><b>　　么</b></p><p>　　２）如果找到購買某種面包的同時顧客還購買了哪

101、些商品的規(guī)則 我們就知道當</p><p>　　停止這種面包的銷售時</p><p>　　哪些商品的銷售會收到影響</p><p>　?。常┤绻l(fā)現(xiàn)顧客購買某種面包的同時購買某種牛奶的所有規(guī)則 我們就可以決</p><p>　　定是否為了促銷牛奶而將牛奶和面包捆綁銷售</p><p>　　上述的購買模式可以用關(guān)聯(lián)規(guī)則的

102、形式表示 例如購買面包的同時也趨向于購</p><p>　　買牛奶可以用以下關(guān)聯(lián)規(guī)則表示</p><p>　　面包?? 牛奶［支持度</p><p><b>　　20</b></p><p><b>　　置信度</b></p><p>　　60 ］　　　　　　　　　　　　　　

103、　?。ǎ常保?lt;/p><p>　　規(guī)則的支持度和置信度是規(guī)則的兩個興趣度度量</p><p><b>　　對于形如</b></p><p><b>　　A?? B 的關(guān)聯(lián)</b></p><p>　　規(guī)則 其確定性度量是置信度</p><p>　　其中 A 和 B 是項目

104、的集合</p><p><b>　　給定一個任務(wù)相關(guān)的</b></p><p><b>　　數(shù)據(jù)元組集合</b></p><p>　　或事務(wù)數(shù)據(jù)庫事務(wù)的集合</p><p>　　A?? B 的置信度定義為</p><p><b>　　9</b></

105、p><p><b>　　置信度 A?? B</b></p><p><b>　　包含A和B的元組數(shù)</b></p><p><b>　　包含A的元組數(shù)</b></p><p><b>　　（３．２）　</b></p><p>　　關(guān)聯(lián)模

106、式的支持度是模式為真的任務(wù)相關(guān)的元組 或事務(wù) 所占的百分比 對</p><p><b>　　于形如 Ａ?? Ｂ</b></p><p><b>　　的關(guān)聯(lián)規(guī)則</b></p><p><b>　　其支持度定義為</b></p><p><b>　　支持度 A?? B&

107、lt;/b></p><p><b>　　包含A和B的元組數(shù)</b></p><p><b>　　元組總數(shù)</b></p><p><b>　　（３．３）　</b></p><p>　　只要找出所有用戶感興趣的關(guān)聯(lián)規(guī)則</p><p>　　就可以幫

108、助決策者做出科學(xué)的決策</p><p>　　關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的主要功能之一</p><p>　　它是 R.Agrawal 等人在 1993[9]年提</p><p>　　出的 目的是希望在事務(wù)數(shù)據(jù)庫中發(fā)現(xiàn)各項目之間的關(guān)系</p><p><b>　　設(shè) I { i1</b></p><p>

109、<b>　　i 2</b></p><p><b>　　….</b></p><p>　　i m }是由 m 個不同的項目組成的集合</p><p><b>　　其中的元素稱為項</b></p><p>　　(item) 項的集合稱為項集(itemset) 包含 k 個項的項集

110、稱為 k-項集 記 D 為事務(wù) T</p><p>　　的集合 這里事務(wù) T 是項的集合 其中每個事務(wù) T 包含若干項目 i1</p><p><b>　　i 2</b></p><p><b>　　….</b></p><p><b>　　i m?∈ I</b></p&

111、gt;<p>　　設(shè) X 是一個項集 事務(wù) T 包含 X 當且僅當 X?? T 一個關(guān)聯(lián)規(guī)則是形如 X?? Y 的蘊</p><p>　　涵式 這里 X?? I</p><p>　　Y?? I 并且 X?∩ Y</p><p><b>　　?</b></p><p>　　規(guī)則 X?? Y 在事務(wù)集 D 中成

112、立</p><p><b>　　其在</b></p><p>　　D 中的支持度是 D 中包含 X 和 Y 的事務(wù)數(shù)和所有事務(wù)數(shù)之比 它是概率 P X?∪ Y</p><p>　　規(guī)則 X?? Y 在事務(wù)集 D 中的置信度是指包含 X 和 Y 的事務(wù)數(shù)與包含 X 的事務(wù)數(shù)之</p><p><b>　　比<

113、;/b></p><p><b>　　這是條件概率 P</b></p><p><b>　　Y|X</b></p><p><b>　　即</b></p><p><b>　　支持度 X?? Y</b></p><p><

114、;b>　　置信度 X?? Y</b></p><p><b>　　P X?∪ Y</b></p><p><b>　　P Y|X</b></p><p><b>　　(3.4)</b></p><p><b>　　(3.5)</b><

115、;/p><p>　　同時滿足最小支持度和最小置信度的規(guī)則稱作強規(guī)則</p><p>　　項集出現(xiàn)的頻率是包含項集的事務(wù)數(shù) 簡稱為頻率或計數(shù) 如果項集滿足最小</p><p>　　支持度 即項集出現(xiàn)的頻率大于或等于最小支持度與 D 中事務(wù)總數(shù)的乘積 則稱它</p><p><b>　　為頻繁項集</b></p>

116、<p>　　頻繁 k-項集的集合通常記做 Lk</p><p>　　關(guān)聯(lián)規(guī)則的挖掘可以分為兩個子問題</p><p><b>　?。?lt;/b></p><p><b>　?。?lt;/b></p><p>　　產(chǎn)生出現(xiàn)次數(shù)大于某個閾值的所有項目的集合 即找出所有頻繁項集</p>&l

117、t;p>　　由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則 　</p><p><b>　　10</b></p><p>　　第一個子問題解決了 第二個子問題很直接 所以發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的重點就在于</p><p><b>　　第一個子問題</b></p><p><b>　　如何發(fā)現(xiàn)頻繁項集</b&g

118、t;</p><p>　　下面介紹一個經(jīng)典的發(fā)現(xiàn)頻繁項集的算法</p><p>　　現(xiàn)在許多新提出的算法都是以這個算法為基礎(chǔ)的</p><p>　　3.2 Apriori 經(jīng)典頻繁項集發(fā)現(xiàn)算法 [1]</p><p>　　Apriori 算法是一種最有影響的挖掘關(guān)聯(lián)規(guī)則頻繁項集的算法 它利用頻繁項集</p><p>　

119、　性質(zhì)的先驗知識 使用一種逐層搜索的迭代方法</p><p>　　k-項集用于探索(k+1)-項集</p><p><b>　　首</b></p><p>　　先找出頻繁 1-項集的集合 該集合記做 L1</p><p>　　L1 用于尋找頻繁 2-項集的集合 L2 而 L2</p><p>&l

120、t;b>　　用于尋找 L3</b></p><p><b>　　如此類推</b></p><p>　　直到不能找到頻繁 k-項集</p><p>　　找每個 Lk 需要掃描一次數(shù)據(jù)</p><p><b>　　庫 　</b></p><p>　　頻繁項集的所

121、有非空子集都必須也是頻繁的</p><p><b>　　根據(jù)定義</b></p><p>　　如果項集 I 不滿足最</p><p>　　小支持都閾值 min_sup 則 I 不是頻繁的 即 P(I)<min_sup 如果項 A 添加到 I 則</p><p>　　結(jié)果項集(I?∪ A)不可能比 I 更頻繁出現(xiàn)&l

122、t;/p><p>　　因此 I?∪ A 也不是頻繁的即 P(I?∪ A)<</p><p>　　min_sup 頻繁項集的這一特性稱作 Apriori 性質(zhì) Apriori 算法利用這一重要性質(zhì)來</p><p>　　壓縮搜索空間 生成較小的候選項集 也就是盡可能不生成和計算那些不可能成為</p><p><b>　　頻繁項集的候

123、選集</b></p><p>　　提高頻繁項集逐層產(chǎn)生的效率</p><p>　　可以將 Apriori 性質(zhì)用在由 Lk??1 尋找 Lk 中</p><p><b>　?。保檎?Lk</b></p><p>　　通過 Lk??1 與自己連接產(chǎn)生候選 k-項集的集合 該候選項集的結(jié)合記</p>

124、<p><b>　　做 Ck</b></p><p>　　設(shè) l1和 l2 是 Lk??1 中的項集</p><p>　　記號 li [j]表示 li 的第 j 項 為方便計</p><p><b>　　假定事務(wù)和</b></p><p>　　項集中的項是按字典次序排序 執(zhí)行連接 Lk

125、??1>< Lk??1 其中 Lk??1 的元素是可連接的</p><p>　　如果它們前(k-2)個項相同 即</p><p>　　Lk??1 的元素 l1和 l2 是可連接的 如果（ l1 [1]＝　 l2 [1]）?∧ 　</p><p>　?。?l1［２］＝ l2 ［２］）　?∧</p><p>　　∧ 　（ l1 [k-

126、2]＝ l2 [k-2]）　?∧ ?。?l1 [k-1]< l2 [k-1]） 條件（ l1 [k-1]< l2 [k-1]）</p><p>　　是簡單地保證不產(chǎn)生重復(fù)</p><p>　　連接 l1和 l2 產(chǎn)生的結(jié)果項集是 l1 [1] l1 [2] … l1 [k-1] l2 [k-1]</p><p><b>　　這一步為連接步<

127、;/b></p><p><b>　　11</b></p><p><b>　?。?lt;/b></p><p>　　Ck 是 Lk 的超集 它的成員可以是也可以不是頻繁的</p><p>　　但所有頻繁的 ｋ－項</p><p>　　集都包含在 Ck 中 掃描數(shù)據(jù)庫<

128、/p><p>　　確定 Ck 中每個候選的計數(shù)</p><p><b>　　從而確定 Lk</b></p><p><b>　　根據(jù)定</b></p><p>　　義 計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的</p><p><b>　　從而屬于 Lk</b&

129、gt;</p><p><b>　　然而 Ck 可</b></p><p>　　能很大 這樣所涉及的計算量就很大</p><p><b>　　為壓縮 Ck</b></p><p>　　可以用以下辦法使用 Apriori 性</p><p>　　質(zhì) 任何非頻繁的(k-1)-項集

130、都不可能是頻繁 k-項集的子集</p><p><b>　　因此</b></p><p><b>　　如果一個候選</b></p><p>　　k-項集的(k-1)-子集不在 Lk??1 中 則該候選也不可能是頻繁的 從而可以從 Ck 中將其</p><p><b>　　刪除</b&

131、gt;</p><p><b>　　該步稱為剪枝步</b></p><p>　　下面給出 Apriori 算法</p><p><b>　　算法</b></p><p>　　Apriori 使用根據(jù)候選生成的逐層迭代找出頻繁項集</p><p>　　輸入 事務(wù)數(shù)據(jù)庫 D 最小

132、支持度閾值 min_sup</p><p>　　輸出 D 中的頻繁項集 L</p><p><b>　　方法</b></p><p><b>　　begin</b></p><p><b>　　L1</b></p><p>　　{large 1-item

133、sets}</p><p>　　for(k=2; Lk??1?≠?? ;k++){</p><p>　　Ck =apriori_gen( Lk??1 ,min_sup)</p><p>　　for all tracsaction t∈ D do{</p><p>　　Ct =subset( Ck ,t)</p><p>

134、;　　for all candidate c∈ Ct do c.count++}</p><p>　　Lk ={c∈ Ck |c.count?≥ min_sup}</p><p><b>　　}</b></p><p>　　answer=?∪k Lk</p><p><b>　　end</b><

135、;/p><p><b>　　12</b></p><p>　　算法的第一步是計算單個項目在事務(wù)集的出現(xiàn)次數(shù)以決定含有一個項目的頻</p><p><b>　　繁項集</b></p><p>　　隨后的步驟稱為 k-pass</p><p><b>　　共分兩步</

136、b></p><p>　　1) 利用 Apriori_gen 函數(shù)從 Lk??1 中產(chǎn)生候選集 Ck</p><p><b>　　枝兩步執(zhí)行</b></p><p>　　Apriori_gen 函數(shù)分連接和剪</p><p><b>　　第一步</b></p><p>

137、<b>　　連接</b></p><p>　　insert into Ck ?。螅澹欤澹悖簟。穑椋簦澹恚?，ｐ．ｉｔｅｍ２，</p><p>　?。妫颍铮怼?Lk??1 ?。穑?Lk??1 ?。瘛?lt;/p><p>　　，ｐ．ｉｔｅｍ（ｋ－１），ｑ．ｉｔｅｍ（ｋ－１）　</p><p>　　ｗｈｅｒｅ?。穑椋簦澹恚保剑瘢?/p>

138、ｉｔｅｍ１?。粒危摹。穑椋簦澹恚玻剑瘢椋簦澹恚病。粒危摹?lt;/p><p><b>　?。粒危摹?lt;/b></p><p>　?。穑椋簦澹恚ǎ耄玻剑瘢椋簦澹恚ǎ耄玻。粒危摹。穑椋簦澹恚ǎ耄保迹瘢椋簦澹恚ǎ耄保?lt;/p><p><b>　　第二步 剪枝</b></p><p>

139、　　對 Ck 中的任一候選 ｃ</p><p>　　如果 ｃ 中存在一個不屬于 Lk??1 的長度為 ｋ－１ 的子序列</p><p>　　那么就從 Ck 中刪除 ｃ</p><p>　　for all itemset c∈ Ck do</p><p>　　for all (k-1)-subset s of c do</p>&

140、lt;p>　　if (s? Lk??1 ) then delete c from Ck</p><p>　　２）利用 Ck 對數(shù)據(jù)庫進行掃描</p><p>　　以求出 Ck 的支持度</p><p>　　Apriori 算法的流程圖如下</p><p><b>　　13</b></p><p&

141、gt;　　圖 ３－１　算法 Ａｐｒｉｏｒｉ 流程圖</p><p>　　一旦由數(shù)據(jù)庫 D 中的事務(wù)找出頻繁項集</p><p>　　由它們產(chǎn)生強關(guān)聯(lián)規(guī)則是直截了當</p><p><b>　　的</b></p><p>　　強關(guān)聯(lián)規(guī)則滿足最小支持度和最小置信度</p><p><b>