大數(shù)據(jù)挖掘與算法

1、大數(shù)據(jù)挖掘與算法第三章數(shù)據(jù)挖掘算法3.1數(shù)據(jù)挖掘概述3.2分類3.3聚類3.4關(guān)聯(lián)規(guī)則3.5預(yù)測(cè)規(guī)模習(xí)題3.6數(shù)據(jù)挖掘算法綜合應(yīng)用of3923.1數(shù)據(jù)挖掘概述第三章 數(shù)據(jù)挖掘算法20世紀(jì)80年代末，數(shù)據(jù)挖掘（Data Mining，DM）提出。1989年，KDD 這個(gè)名詞正式開始出現(xiàn)。1995年，“數(shù)據(jù)挖掘” 流傳。從科學(xué)定義分析，數(shù)據(jù)挖掘是從大量的、有噪聲的、不完全的、模糊和隨機(jī)的數(shù)據(jù)中，提取出隱含在其中的、人們事先不知道的、具有潛在利用價(jià)值的信息和知識(shí)的過(guò)程。從技術(shù)角度分析，數(shù)據(jù)挖掘就是利用一系列的相關(guān)算法和技術(shù)，從大數(shù)據(jù)中提取出行業(yè)或公司所需要的、有實(shí)際應(yīng)用價(jià)值的知識(shí)的過(guò)程。知識(shí)表示形式

2、可以是概念、規(guī)律、規(guī)則與模式等。準(zhǔn)確地說(shuō)，數(shù)據(jù)挖掘是整個(gè)知識(shí)發(fā)現(xiàn)流程中的一個(gè)具體步驟，也是知識(shí)發(fā)現(xiàn)過(guò)程中最重要的核心步驟。特征處理大數(shù)據(jù)的能力更強(qiáng)，且無(wú)須太專業(yè)的統(tǒng)計(jì)背景就可以使用數(shù)據(jù)挖掘工具數(shù)據(jù)挖掘的最終目的是方便企業(yè)終端用戶使用，而并非給統(tǒng)計(jì)學(xué)家檢測(cè)用的從使用與需求的角度上看，數(shù)據(jù)挖掘工具更符合企業(yè)界的需求of3933.1.1 數(shù)據(jù)挖掘概念3.1數(shù)據(jù)挖掘概述第三章 數(shù)據(jù)挖掘算法使用廣義角度分類聚類估值預(yù)測(cè)關(guān)聯(lián)規(guī)則數(shù)理基礎(chǔ)角度機(jī)器學(xué)習(xí)方法統(tǒng)計(jì)方法神經(jīng)網(wǎng)絡(luò)方法決策樹基于范例學(xué)習(xí)規(guī)則歸納遺傳算法回歸分析時(shí)間序列分析關(guān)聯(lián)分析聚類分析粗糙集探索性分析支持向量機(jī)最近鄰分析模糊集前向神經(jīng)網(wǎng)絡(luò)自組織神經(jīng)網(wǎng)

3、絡(luò)多層神經(jīng)網(wǎng)絡(luò)深度學(xué)習(xí)感知機(jī)可視化of3943.1.2 數(shù)據(jù)挖掘常用算法3.1數(shù)據(jù)挖掘概述第三章 數(shù)據(jù)挖掘算法1分類數(shù)據(jù)挖掘方法中的一種重要方法就是分類，在給定數(shù)據(jù)基礎(chǔ)上構(gòu)建分類函數(shù)或分類模型，該函數(shù)或模型能夠把數(shù)據(jù)歸類為給定類別中的某一種類別，這就是分類的概念。2聚類3關(guān)聯(lián)規(guī)則4時(shí)間序列預(yù)測(cè)聚類也就是將抽象對(duì)象的集合分為相似對(duì)象組成的多個(gè)類的過(guò)程，聚類過(guò)程生成的簇稱為一組數(shù)據(jù)對(duì)象的集合。關(guān)聯(lián)規(guī)則屬于數(shù)據(jù)挖掘算法中的一類重要方法，關(guān)聯(lián)規(guī)則就是支持度與信任度分別滿足用戶給定閾值的規(guī)則。時(shí)間序列預(yù)測(cè)法是一種歷史引申預(yù)測(cè)法，也即將時(shí)間數(shù)列所反映的事件發(fā)展過(guò)程進(jìn)行引申外推，預(yù)測(cè)發(fā)展趨勢(shì)的一種方法。of

4、3953.1.2 數(shù)據(jù)挖掘常用算法3.1數(shù)據(jù)挖掘概述第三章 數(shù)據(jù)挖掘算法按照數(shù)據(jù)挖掘的應(yīng)用場(chǎng)景分類，數(shù)據(jù)挖掘的應(yīng)用主要涉及通信、股票、金融、銀行、交通、商品零售、生物醫(yī)學(xué)、精確營(yíng)銷、地震預(yù)測(cè)、工業(yè)產(chǎn)品設(shè)計(jì)等領(lǐng)域，在這些領(lǐng)域眾多數(shù)據(jù)挖掘方法均被廣泛采用且衍生出各自獨(dú)特的算法。1數(shù)據(jù)挖掘在電信行業(yè)的應(yīng)用2數(shù)據(jù)挖掘在商業(yè)銀行中的應(yīng)用數(shù)據(jù)挖掘廣泛應(yīng)用在電信行業(yè)，可以幫助企業(yè)制定合理的服務(wù)與資費(fèi)標(biāo)準(zhǔn)、防止欺詐、優(yōu)惠政策，為公司決策者提供可靠的決策依據(jù)，為市場(chǎng)營(yíng)銷、客戶服務(wù)、全網(wǎng)業(yè)務(wù)、經(jīng)營(yíng)決策等提供有效的數(shù)據(jù)支撐，進(jìn)一步完善了國(guó)內(nèi)電信公司對(duì)省、市電信運(yùn)營(yíng)的指導(dǎo)，在業(yè)務(wù)運(yùn)營(yíng)中發(fā)揮重要的作用，從而為精細(xì)化運(yùn)營(yíng)

5、提供技術(shù)與數(shù)據(jù)的基礎(chǔ)。在美國(guó)銀行業(yè)與金融服務(wù)領(lǐng)域數(shù)據(jù)挖掘技術(shù)的應(yīng)用十分廣泛，由于金融業(yè)務(wù)的分析與評(píng)估往往需要大數(shù)據(jù)的支撐，從中可以發(fā)現(xiàn)客戶的信用評(píng)級(jí)與潛在客戶等有價(jià)值的信息，可成功地預(yù)測(cè)客戶的需求。of3963.1.3 數(shù)據(jù)挖掘應(yīng)用場(chǎng)景3.1數(shù)據(jù)挖掘概述第三章 數(shù)據(jù)挖掘算法3數(shù)據(jù)挖掘在信息安全中的應(yīng)用4數(shù)據(jù)挖掘在科學(xué)探索中的應(yīng)用利用機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘等前沿技術(shù)與處理方法對(duì)入侵檢測(cè)的數(shù)據(jù)進(jìn)行自動(dòng)分析，提取出盡可能多的隱藏安全信息，從中抽象出與安全有關(guān)的數(shù)據(jù)特征，從而能夠發(fā)現(xiàn)未知的入侵行為。數(shù)據(jù)挖掘技術(shù)可以建立一種具備自適應(yīng)性、自動(dòng)的、系統(tǒng)與良好擴(kuò)展性的入侵檢測(cè)系統(tǒng)，能夠解決傳統(tǒng)入侵檢測(cè)系統(tǒng)適應(yīng)性

6、與擴(kuò)展性較差的弱點(diǎn)，大幅度提高入侵檢測(cè)系統(tǒng)的檢測(cè)與響應(yīng)的效能。近年來(lái)，數(shù)據(jù)挖掘技術(shù)已經(jīng)開始逐步應(yīng)用到科學(xué)探索研究中。例如，在生物學(xué)領(lǐng)域數(shù)據(jù)挖掘主要應(yīng)用在分子生物學(xué)與基因工程的研究。 使用概率論模型對(duì)蛋白質(zhì)序列進(jìn)行多序列聯(lián)配建模； 特定數(shù)據(jù)挖掘技術(shù)研究基因數(shù)據(jù)庫(kù)搜索技術(shù)； 在被認(rèn)為是人類征服頑疾的最有前途的攻關(guān)課題“DNA序列分析”過(guò)程中，由于DNA序列的構(gòu) 成多種多樣，數(shù)據(jù)挖掘技術(shù)的應(yīng)用可以為發(fā)現(xiàn)疾病蘊(yùn)藏的基因排列信息提供新方法。of3973.1.3 數(shù)據(jù)挖掘應(yīng)用場(chǎng)景3.1數(shù)據(jù)挖掘概述第三章 數(shù)據(jù)挖掘算法根據(jù)適用的范圍，數(shù)據(jù)挖掘工具分為兩類：專用挖掘工具和通用挖掘工具。專用數(shù)據(jù)挖掘工具針對(duì)某個(gè)

7、特定領(lǐng)域的問(wèn)題提供解決方案，在涉及算法的時(shí)候充分考慮數(shù)據(jù)、需求的特殊性。對(duì)任何應(yīng)用領(lǐng)域，專業(yè)的統(tǒng)計(jì)研發(fā)人員都可以開發(fā)特定的數(shù)據(jù)挖掘工具。Weka軟件SPSS軟件Clementine軟件RapidMiner軟件其他數(shù)據(jù)挖掘軟件SPSS采用類似Excel表格的方式輸入與管理數(shù)據(jù)，數(shù)據(jù)接口較為通用，能方便地從其他數(shù)據(jù)庫(kù)中讀入數(shù)據(jù)。突出的特點(diǎn)是操作界面友好，且輸出結(jié)果美觀。Clementine提供出色、廣泛的數(shù)據(jù)挖掘技術(shù)，確保用恰當(dāng)?shù)姆治黾夹g(shù)來(lái)處理相應(yīng)的商業(yè)問(wèn)題，得到最優(yōu)的結(jié)果以應(yīng)對(duì)隨時(shí)出現(xiàn)的問(wèn)題。RapidMiner并不支持分析流程圖方式，當(dāng)包含的運(yùn)算符比較多時(shí)就不容易查看；具有豐富的數(shù)據(jù)挖掘分析和

8、算法功能，常用于解決各種商業(yè)關(guān)鍵問(wèn)題。公開的數(shù)據(jù)挖掘工作平臺(tái)，集成大量能承擔(dān)數(shù)據(jù)挖掘任務(wù)的機(jī)器學(xué)習(xí)算法，包括對(duì)數(shù)據(jù)進(jìn)行預(yù)處理、分類、回歸、聚類、關(guān)聯(lián)規(guī)則，以及交互式界面上的可視化。流行的數(shù)據(jù)挖掘軟件還包括Orange、Knime、Keel與Tanagra等of3983.1.4 數(shù)據(jù)挖掘工具3.2分類3.1數(shù)據(jù)挖掘概述第三章數(shù)據(jù)挖掘算法3.3聚類3.4關(guān)聯(lián)規(guī)則3.5預(yù)測(cè)規(guī)模習(xí)題3.6數(shù)據(jù)挖掘算法綜合應(yīng)用of3993.2 分類分類是一種重要的數(shù)據(jù)分析形式，根據(jù)重要數(shù)據(jù)類的特征向量值及其他約束條件，構(gòu)造分類函數(shù)或分類模型（分類器），目的是根據(jù)數(shù)據(jù)集的特點(diǎn)把未知類別的樣本映射到給定類別中。數(shù)據(jù)分類過(guò)程

9、主要包括兩個(gè)步驟，即學(xué)習(xí)和分類。圖3-1 建立一個(gè)模型第一步，建立一個(gè)模型第三章 數(shù)據(jù)挖掘算法of3910圖3-2 使用模型進(jìn)行分類3.2 分類第二步，使用模型進(jìn)行分類第三章 數(shù)據(jù)挖掘算法of39113.2 分類分類分析在數(shù)據(jù)挖掘中是一項(xiàng)比較重要的任務(wù)，目前在商業(yè)上應(yīng)用最多。分類的目的是從歷史數(shù)據(jù)記錄中自動(dòng)推導(dǎo)出對(duì)給定數(shù)據(jù)的推廣描述，從而學(xué)會(huì)一個(gè)分類函數(shù)或分類模型（也常常稱作分類器），該模型能把數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)映射到給定類別中的某一個(gè)類中。為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集，由一組數(shù)據(jù)庫(kù)記錄或元組構(gòu)成，每個(gè)元組是一個(gè)由有關(guān)字段（又稱屬性或特征）值組成的特征向量，此外，每一個(gè)訓(xùn)練樣本都有

10、一個(gè)預(yù)先定義的類別標(biāo)記，由一個(gè)被稱為類標(biāo)簽的屬性確定。一個(gè)具體樣本的形式可表示為 ,其中 表示字段值，C 表示類別分類又稱為有監(jiān)督的學(xué)習(xí)第三章 數(shù)據(jù)挖掘算法of39123.2 分類1條件概率數(shù)學(xué)基礎(chǔ)知識(shí)事件A 在另外一個(gè)事件B 已經(jīng)發(fā)生條件下的發(fā)生概率，稱為在B 條件下A 的概率。表示為2聯(lián)合概率聯(lián)合概率表示兩個(gè)事件共同發(fā)生的概率。 A 與B 的聯(lián)合概率表示為 、 或者3貝葉斯定理貝葉斯定理用來(lái)描述兩個(gè)條件概率之間的關(guān)系，例如， 與 。根據(jù)乘法法則 可以推導(dǎo)出貝葉斯公式：第三章 數(shù)據(jù)挖掘算法of39133.2.1 貝葉斯決策與分類器3.2 分類4全概率公式全概率公式為概率論中的重要公式，它將對(duì)

11、復(fù)雜事件A 的概率求解問(wèn)題轉(zhuǎn)化為在不同情況下發(fā)生的簡(jiǎn)單事件的概率的求和問(wèn)題。設(shè) 構(gòu)成一個(gè)完備事件組，即它們兩兩互不相容，其和為全集，且 ，則事件A的概率為：貝葉斯分類的工作過(guò)程如下：（1）每個(gè)數(shù)據(jù)樣本均是由一個(gè)n 維特征向量 表示，分別描述其n 個(gè)屬性的具體取值。第三章 數(shù)據(jù)挖掘算法of39143.2.1 貝葉斯決策與分類器3.2 分類4全概率公式（2）假設(shè)共有m 個(gè)不同類別， 。給定一個(gè)未知類別的數(shù)據(jù)樣本X（沒(méi)有類別號(hào)），分類器預(yù)測(cè)屬于X 后驗(yàn)概率最大的那個(gè)類別。也就是說(shuō)，樸素貝葉斯分類器將未知類別的樣本X 歸屬到類別 ，當(dāng)且僅當(dāng) 。也就是 最大。其中類別 就稱為最大后驗(yàn)概率的假設(shè)。根據(jù)貝葉

12、斯公式可得：（3）由于 對(duì)于所有的類別均是相同的，因此，只需要 取最大即可。由于類別的先驗(yàn)概率是未知的，則通常假定類別出現(xiàn)概率相同，即 。這樣對(duì)于式（3-4）取最大轉(zhuǎn)換成只需要求 最大。而類別的先驗(yàn)概率一般可以通過(guò) 公式進(jìn)行估算，其中， 為訓(xùn)練樣本集合中類別 的個(gè)數(shù)，s 為整個(gè)訓(xùn)練樣本集合的大小。（3-4）第三章 數(shù)據(jù)挖掘算法of39153.2.1 貝葉斯決策與分類器3.2 分類4全概率公式（4）根據(jù)所給定包含多個(gè)屬性的數(shù)據(jù)集，直接計(jì)算 的運(yùn)算量非常大。為實(shí)現(xiàn)對(duì)的有效估算，樸素貝葉斯分類器通常都假設(shè)各類別是相互獨(dú)立的，即各屬性間不存在依賴關(guān)系，其取值是相互獨(dú)立的?？梢愿鶕?jù)訓(xùn)練數(shù)據(jù)樣本估算 的值

13、。如果 是分類屬性，則 ；其中 是在屬性 上具有值 的類 的訓(xùn)練樣本數(shù)，而 是 中的訓(xùn)練樣本數(shù)。如果 是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因而 （3-6）給定類 的訓(xùn)練樣本屬性 的值， 是屬性 的高斯密度函數(shù)， ， 分別為均值和方差。（5）為預(yù)測(cè)一個(gè)未知樣本X 的類別，可對(duì)每個(gè)類別 估算相應(yīng)的 。樣本X 歸屬類別 當(dāng)且僅當(dāng) ，即X 屬于 為最大的類 。第三章 數(shù)據(jù)挖掘算法of39163.2.1 貝葉斯決策與分類器3.2 分類第三章 數(shù)據(jù)挖掘算法支持向量機(jī)（Support Vector Machine）是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型

14、的復(fù)雜性（對(duì)特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy）和學(xué)習(xí)能力（無(wú)錯(cuò)誤地識(shí)別任意樣本的能力）之間尋求最佳折中，以期獲得最好的推廣能力（或稱泛化能力）。圖3-3 超平面SVM最基本的任務(wù)就是找到一個(gè)能夠讓兩類數(shù)據(jù)都離超平面很遠(yuǎn)的超平面，在分開數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面。分隔超平面使兩個(gè)平行超平面的距離最大化，平行超平面間的距離或差距越大，分類器的總誤差越小。通常希望分類的過(guò)程是一個(gè)機(jī)器學(xué)習(xí)的過(guò)程。設(shè)樣本屬于兩個(gè)類，用該樣本訓(xùn)練SVM得到的最大間隔超平面。在超平面上的樣本點(diǎn)也稱為支持向量。of39173.2.2 SVM算法3.2 分類第三章 數(shù)據(jù)挖掘算法線性可分情形SVM非線性可

15、分情形SVM支持向量機(jī)（SVM）的核函數(shù)of39183.2.2 SVM算法3.2 分類第三章 數(shù)據(jù)挖掘算法互聯(lián)網(wǎng)的出現(xiàn)和普及，帶來(lái)的網(wǎng)上信息量的大幅增長(zhǎng)，出現(xiàn)信息超載問(wèn)題。為了解決信息過(guò)載的問(wèn)題，提出了很多解決方案，其中最具有代表性的解決方案是分類目錄和搜索引擎。但是隨著互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大，分類目錄和搜索引擎，不能解決用戶的需求。推薦系統(tǒng)就是解決這一矛盾的重要工具。推薦系統(tǒng)具有用戶需求驅(qū)動(dòng)、主動(dòng)服務(wù)和信息個(gè)性化程度高等優(yōu)點(diǎn)，可有效解決信息過(guò)載問(wèn)題。推薦系統(tǒng)是一種智能個(gè)性化信息服務(wù)系統(tǒng)，可借助用戶建模技術(shù)對(duì)用戶的長(zhǎng)期信息需求進(jìn)行描述，并根據(jù)用戶模型通過(guò)一定的智能推薦策略實(shí)現(xiàn)有針對(duì)性的個(gè)性化信息

16、定制，能夠依據(jù)用戶的歷史興趣偏好，主動(dòng)為用戶提供符合其需求和興趣的信息資源。圖3-6 推薦系統(tǒng)的工作原理of39193.2.3 案例：在線廣告推薦中的分類3.2 分類第三章 數(shù)據(jù)挖掘算法推薦系統(tǒng)利用推薦算法將用戶和物品聯(lián)系起來(lái)，能夠在信息過(guò)載的環(huán)境中幫助用戶發(fā)現(xiàn)令他們感興趣的信息，也能將信息推送給對(duì)他們感興趣的用戶。根據(jù)已有用戶注冊(cè)信息和購(gòu)買信息，使用樸素貝葉斯分類預(yù)測(cè)一個(gè)新注冊(cè)用戶購(gòu)買計(jì)算機(jī)的可能性，從而向該用戶推薦計(jì)算機(jī)類廣告。訓(xùn)練樣本如表3-1所示。序號(hào)ID年齡Age（歲）收入等級(jí)Income_level是否學(xué)生student信用等級(jí)Credit rate類別：是否購(gòu)買計(jì)算機(jī)Class:

17、buy computer130以下高否良否230以下高否優(yōu)否331到40高否良是440以上中否良是540以上低是良是640以上低是優(yōu)否731到40低是優(yōu)是830以下中否良否930以下低是良是1040以上中是良是1130以下中是優(yōu)是1231到40中否優(yōu)是1331到40高是良是1440以上中否優(yōu)否表3-1 訓(xùn)練課本of39203.2.3 案例：在線廣告推薦中的分類3.1數(shù)據(jù)挖掘概述第三章數(shù)據(jù)挖掘算法3.2分類3.3聚類3.4關(guān)聯(lián)規(guī)則3.5預(yù)測(cè)規(guī)模習(xí)題3.6數(shù)據(jù)挖掘算法綜合應(yīng)用3.3聚類of39213.3 聚類聚類（clustering）就是將具體或抽象對(duì)象的集合分組成由相似對(duì)象組成的為多個(gè)類或簇的

18、過(guò)程。由聚類生成的簇是一組數(shù)據(jù)對(duì)象的集合，簇必須同時(shí)滿足以下兩個(gè)條件：每個(gè)簇至少包含一個(gè)數(shù)據(jù)對(duì)象；每個(gè)數(shù)據(jù)對(duì)象必須屬于且唯一地屬于一個(gè)簇。聚類分析是指用數(shù)學(xué)的方法來(lái)研究與處理給定對(duì)象的分類，主要是從數(shù)據(jù)集中尋找數(shù)據(jù)間的相似性，并以此對(duì)數(shù)據(jù)進(jìn)行分類，使得同一個(gè)簇中的數(shù)據(jù)對(duì)象盡可能相似，不同簇中的數(shù)據(jù)對(duì)象盡可能相異，從而發(fā)現(xiàn)數(shù)據(jù)中隱含的、有用的信息。數(shù)據(jù)準(zhǔn)備特征選擇、提出特征提取聚類（或分組）聚類過(guò)程聚類算法的要求可擴(kuò)展性處理不同類型屬性的能力發(fā)現(xiàn)任意形狀的聚類需要（由用戶）決定的輸入?yún)?shù)最少處理噪聲數(shù)據(jù)的能力對(duì)輸入記錄順序不敏感高維問(wèn)題基于約束的聚類可解釋性和可用性第三章 數(shù)據(jù)挖掘算法of392

19、23.3.1 非監(jiān)督機(jī)器學(xué)習(xí)方法與聚類3.3 聚類1層次聚類算法層次聚類算法的指導(dǎo)思想是對(duì)給定待聚類數(shù)據(jù)集合進(jìn)行層次化分解。此算法又稱為數(shù)據(jù)類算法，此算法根據(jù)一定的鏈接規(guī)則將數(shù)據(jù)以層次架構(gòu)分裂或聚合，最終形成聚類結(jié)果。從算法的選擇上看，層次聚類分為自頂而下的分裂聚類和自下而上的聚合聚類。分裂聚類初始將所有待聚類項(xiàng)看成同一類，然后找出其中與該類中其他項(xiàng)最不相似的類分裂出去形成兩類。如此反復(fù)執(zhí)行，直到所有項(xiàng)自成一類。聚合聚類初始將所有待聚類項(xiàng)都視為獨(dú)立的一類，通過(guò)連接規(guī)則，包括單連接、全連接、類間平均連接，以及采用歐氏距離作為相似度計(jì)算的算法，將相似度最高的兩個(gè)類合并成一個(gè)類。如此反復(fù)執(zhí)行，直到所

20、有項(xiàng)并入同一個(gè)類。典型代表算法，BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies，利用層次方法的平衡迭代規(guī)約和聚類）第三章 數(shù)據(jù)挖掘算法of39233.3.2 常用聚類算法3.3 聚類2劃分聚類算法劃分法屬于硬聚類，指導(dǎo)思想是將給定的數(shù)據(jù)集初始分裂為K個(gè)簇，每個(gè)簇至少包含一條數(shù)據(jù)記錄，然后通過(guò)反復(fù)迭代至每個(gè)簇不再改變即得出聚類結(jié)果。 K-Means算法也稱作K-平均值算法或者K均值算法，是一種得到廣泛使用的聚類分析算法。1）歐氏距離2）曼哈頓距離3）閔可夫斯基距離4）切比雪夫距離常用距離算法第三章 數(shù)據(jù)挖掘算法

21、of39243.3.2 常用聚類算法3.3 聚類2劃分聚類算法K-Means算法是解決聚類問(wèn)題的一種經(jīng)典算法，簡(jiǎn)單快速，對(duì)于處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮的和高效的圖3-8 K-Means算法流程第三章 數(shù)據(jù)挖掘算法of39253.3.2 常用聚類算法3.3 聚類3基于密度的聚類算法基于密度聚類的經(jīng)典算法DBSCAN（Density-Based Spatial Clustering of Application with Noise，具有噪聲的基于密度的空間聚類應(yīng)用）是一種基于高密度連接區(qū)域的密度聚類算法。DBSCAN的基本算法流程如下：從任意對(duì)象P 開始根據(jù)閾值和參數(shù)通過(guò)廣度優(yōu)先搜索提取從

22、P 密度可達(dá)的所有對(duì)象，得到一個(gè)聚類。若P 是核心對(duì)象，則可以一次標(biāo)記相應(yīng)對(duì)象為當(dāng)前類并以此為基礎(chǔ)進(jìn)行擴(kuò)展。得到一個(gè)完整的聚類后，再選擇一個(gè)新的對(duì)象重復(fù)上述過(guò)程。若P 是邊界對(duì)象，則將其標(biāo)記為噪聲并舍棄缺陷如聚類的結(jié)果與參數(shù)關(guān)系較大閾值過(guò)大容易將同一聚類分割閾值過(guò)小容易將不同聚類合并固定的閾值參數(shù)對(duì)于稀疏程度不同的數(shù)據(jù)不具適應(yīng)性密度小的區(qū)域同一聚類易被分割密度大的區(qū)域不同聚類易被合并第三章 數(shù)據(jù)挖掘算法of39263.3.2 常用聚類算法3.3 聚類4基于網(wǎng)格的聚類算法基于網(wǎng)格的聚類算法是采用一個(gè)多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，即將空間量化為有限數(shù)目的單元，這些單元形成了網(wǎng)格結(jié)構(gòu)，所有的聚類操作都在網(wǎng)

23、格上進(jìn)行。STING（STatistical INformation Grid，統(tǒng)計(jì)信息網(wǎng)格）算法將空間區(qū)域劃分為矩形單元針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，這些單元形成了一個(gè)層次結(jié)構(gòu)高層的每個(gè)單元被劃分為多個(gè)低一層的單元WaveCluster（Clustering using wavelet transformation，采用小波變換聚類）是一種多分辨率的聚類算法先通過(guò)在數(shù)據(jù)空間上加一個(gè)多維網(wǎng)格結(jié)構(gòu)來(lái)匯總數(shù)據(jù)，然后采用一種小波變換來(lái)變換原特征空間，在變換后的空間中找到密集區(qū)域第三章 數(shù)據(jù)挖掘算法of39273.3.2 常用聚類算法3.3 聚類5基于模型的聚類算法基于模型的聚類算

24、法是為每一個(gè)聚類假定了一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。統(tǒng)計(jì)學(xué)方法(EM和COBWEB算法)神經(jīng)網(wǎng)絡(luò)方法(SOM算法)概念聚類是機(jī)器學(xué)習(xí)中的一種聚類方法，給出一組未標(biāo)記的數(shù)據(jù)對(duì)象，它產(chǎn)生一個(gè)分類模式。概念聚類除了確定相似對(duì)象的分組外，還為每組對(duì)象發(fā)現(xiàn)了特征描述，即每組對(duì)象代表了一個(gè)概念或類。概念聚類過(guò)程主要有兩個(gè)步驟：首先，完成聚類；其次，進(jìn)行特征描述。神經(jīng)網(wǎng)絡(luò)方法將每個(gè)簇描述成一個(gè)模型。模型作為聚類的一個(gè)“原型”，不一定對(duì)應(yīng)一個(gè)特定的數(shù)據(jù)實(shí)例或?qū)ο蟆Ｉ窠?jīng)網(wǎng)絡(luò)聚類的兩種方法：競(jìng)爭(zhēng)學(xué)習(xí)方法與自組織特征圖映射方法。神經(jīng)網(wǎng)絡(luò)聚類方法存在較長(zhǎng)處理時(shí)間和復(fù)雜數(shù)據(jù)中復(fù)雜關(guān)系問(wèn)題，還不適合處理大數(shù)據(jù)庫(kù)

25、。第三章 數(shù)據(jù)挖掘算法of39283.3.2 常用聚類算法3.3 聚類圖像分割是圖像處理到圖像分析的關(guān)鍵步驟，也是一種基本的計(jì)算機(jī)視覺技術(shù)，一般來(lái)說(shuō)，圖像分割是把圖像分成每個(gè)區(qū)域并提取感興趣目標(biāo)的技術(shù)和過(guò)程。顏色、灰度、紋理是比較常見和主要的特性，目標(biāo)可以對(duì)應(yīng)多個(gè)區(qū)域，也可以對(duì)應(yīng)單個(gè)區(qū)域，主要與實(shí)際應(yīng)用和目標(biāo)有關(guān)。K-Means聚類算法簡(jiǎn)捷，具有很強(qiáng)的搜索能力，適合處理數(shù)據(jù)量大的應(yīng)用場(chǎng)景，在數(shù)據(jù)挖掘和圖像領(lǐng)域中得到了廣泛的應(yīng)用。圖3-9 K-Means聚類算法進(jìn)行圖像分割示意圖第三章 數(shù)據(jù)挖掘算法of39293.3.3 案例：海量視頻檢索中的聚類3.1數(shù)據(jù)挖掘概述第三章數(shù)據(jù)挖掘算法3.2分類3

26、.3聚類3.1數(shù)據(jù)挖掘概述3.5預(yù)測(cè)規(guī)模習(xí)題3.6數(shù)據(jù)挖掘算法綜合應(yīng)用3.4關(guān)聯(lián)規(guī)則of65303.4 關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中最活躍的研究方法之一，是指搜索業(yè)務(wù)系統(tǒng)中的所有細(xì)節(jié)或事務(wù)，找出所有能把一組事件或數(shù)據(jù)項(xiàng)與另一組事件或數(shù)據(jù)項(xiàng)聯(lián)系起來(lái)的規(guī)則，以獲得存在于數(shù)據(jù)庫(kù)中的不為人知的或不能確定的信息，它側(cè)重于確定數(shù)據(jù)中不同領(lǐng)域之間的聯(lián)系，也是在無(wú)指導(dǎo)學(xué)習(xí)系統(tǒng)中挖掘本地模式的最普通形式。More應(yīng)用市場(chǎng)：市場(chǎng)貨籃分析、交叉銷售（Crossing Sale）、部分分類（Partial Classification）、金融服務(wù)（Financial Service），以及通信、互聯(lián)網(wǎng)、電子商務(wù) 第三

27、章 數(shù)據(jù)挖掘算法of65313.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法一般來(lái)說(shuō)，關(guān)聯(lián)規(guī)則挖掘是指從一個(gè)大型的數(shù)據(jù)集（Dataset）發(fā)現(xiàn)有趣的關(guān)聯(lián)（Association）或相關(guān)關(guān)系（Correlation），即從數(shù)據(jù)集中識(shí)別出頻繁出現(xiàn)的屬性值集（Sets of Attribute Values），也稱為頻繁項(xiàng)集（Frequent Itemsets，頻繁集），然后利用這些頻繁項(xiàng)集創(chuàng)建描述關(guān)聯(lián)關(guān)系的規(guī)則的過(guò)程。3.4.1 關(guān)聯(lián)規(guī)則的概念關(guān)聯(lián)規(guī)則挖掘問(wèn)題：發(fā)現(xiàn)所有的頻繁項(xiàng)集是形成關(guān)聯(lián)規(guī)則的基礎(chǔ)。通過(guò)用戶給定的最小支持度，尋找所有支持度大于或等于Minsupport的頻繁項(xiàng)集。通過(guò)用戶給定的最小可信度，在

28、每個(gè)最大頻繁項(xiàng)集中，尋找可信度不小于Minconfidence的關(guān)聯(lián)規(guī)則。發(fā)現(xiàn)頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則如何迅速高效地發(fā)現(xiàn)所有頻繁項(xiàng)集，是關(guān)聯(lián)規(guī)則挖掘的核心問(wèn)題，也是衡量關(guān)聯(lián)規(guī)則挖掘算法效率的重要標(biāo)準(zhǔn)。of65323.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.2 頻繁項(xiàng)集的產(chǎn)生及其經(jīng)典算法格結(jié)構(gòu)（Lattice Structure）常常被用來(lái)枚舉所有可能的項(xiàng)集。圖3-10 項(xiàng)集的格of65333.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.2 頻繁項(xiàng)集的產(chǎn)生及其經(jīng)典算法格結(jié)構(gòu)（Lattice Structure）常常被用來(lái)枚舉所有可能的項(xiàng)集。查找頻繁項(xiàng)目集經(jīng)典的查找策略基于精簡(jiǎn)集的查找策略基于最大頻繁項(xiàng)集

29、的查找策略按照挖掘的策略不同經(jīng)典的挖掘完全頻繁項(xiàng)集方法基于廣度優(yōu)先搜索策略的關(guān)聯(lián)規(guī)則算法基于深度優(yōu)先搜索策略的算法Apriori算法、DHP算法FP-Growth算法、ECLAT算法COFI算法與經(jīng)典查找不同方法基于精簡(jiǎn)集的方法基于最大頻繁項(xiàng)目集的方法A-close算法MAFIA算法、GenMax算法DepthProject算法of65343.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.2 頻繁項(xiàng)集的產(chǎn)生及其經(jīng)典算法1Apriori算法Apriori算法基于頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，使用由下至上逐層搜索的迭代方法，即從頻繁1項(xiàng)集開始，采用頻繁k項(xiàng)集搜索頻繁k+1項(xiàng)集，直到不能找到包含更多項(xiàng)的頻繁項(xiàng)集

30、為止。Apriori算法由以下步驟組成，其中的核心步驟是連接步和剪枝步：生成頻繁1項(xiàng)集L1連接步剪枝步生成頻繁k項(xiàng)集Lk重復(fù)步驟（2）（4），直到不能產(chǎn)生新的頻繁項(xiàng)集的集合為止，算法中止。性能瓶頸Apriori算法是一個(gè)多趟搜索算法可能產(chǎn)生龐大的候選項(xiàng)集of65353.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.2 頻繁項(xiàng)集的產(chǎn)生及其經(jīng)典算法2FP-Growth算法頻繁模式樹增長(zhǎng)算法（Frequent Pattern Tree Growth）采用分而治之的基本思想，將數(shù)據(jù)庫(kù)中的頻繁項(xiàng)集壓縮到一棵頻繁模式樹中，同時(shí)保持項(xiàng)集之間的關(guān)聯(lián)關(guān)系。然后將這棵壓縮后的頻繁模式樹分成一些條件子樹，每個(gè)條件子樹對(duì)應(yīng)

31、一個(gè)頻繁項(xiàng)，從而獲得頻繁項(xiàng)集，最后進(jìn)行關(guān)聯(lián)規(guī)則挖掘。FP-Growth算法由以下步驟組成：掃描事務(wù)數(shù)據(jù)庫(kù)D，生成頻繁1項(xiàng)集L1將頻繁1項(xiàng)集L1按照支持度遞減順序排序，得到排序后的項(xiàng)集L1構(gòu)造FP樹通過(guò)后綴模式與條件FP樹產(chǎn)生的頻繁模式連接實(shí)現(xiàn)模式增長(zhǎng)1234圖3-11 FP樹的構(gòu)造of65363.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.2 頻繁項(xiàng)集的產(chǎn)生及其經(jīng)典算法3辛普森悖論雖然關(guān)聯(lián)規(guī)則挖掘可以發(fā)現(xiàn)項(xiàng)目之間的有趣關(guān)系，在某些情況下，隱藏的變量可能會(huì)導(dǎo)致觀察到的一對(duì)變量之間的聯(lián)系消失或逆轉(zhuǎn)方向，這種現(xiàn)象就是所謂的辛普森悖論（Simpsons Paradox）。為了避免辛普森悖論的出現(xiàn)，就需要斟

32、酌各個(gè)分組的權(quán)重，并以一定的系數(shù)去消除以分組數(shù)據(jù)基數(shù)差異所造成的影響。同時(shí)必須了解清楚情況，是否存在潛在因素，綜合考慮。of65373.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.3 分類技術(shù)分類技術(shù)或分類法（Classification）是一種根據(jù)輸入樣本集建立類別模型，并按照類別模型對(duì)未知樣本類標(biāo)號(hào)進(jìn)行標(biāo)記的方法。根據(jù)所采用的分類模型不同基于決策樹模型的數(shù)據(jù)分類基于統(tǒng)計(jì)模型的數(shù)據(jù)分類基于神經(jīng)網(wǎng)絡(luò)模型的數(shù)據(jù)分類基于案例推理的數(shù)據(jù)分類基于實(shí)例的數(shù)據(jù)分類1決策樹決策樹就是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過(guò)程。決策樹分類算法通常分為兩個(gè)步驟：構(gòu)造決策樹和修剪決策樹。of65383.4 關(guān)聯(lián)規(guī)則第三章 數(shù)

33、據(jù)挖掘算法3.4.3 分類技術(shù)構(gòu)造決策樹修剪決策樹根據(jù)實(shí)際需求及所處理數(shù)據(jù)的特性，選擇類別標(biāo)識(shí)屬性和決策樹的決策屬性集在決策屬性集中選擇最有分類標(biāo)識(shí)能力的屬性作為決策樹的當(dāng)前決策節(jié)點(diǎn)根據(jù)當(dāng)前決策節(jié)點(diǎn)屬性取值的不同，將訓(xùn)練樣本數(shù)據(jù)集劃分為若干子集 子集中的所有元組都屬于同一類。 該子集是已遍歷了所有決策屬性后得到的。 子集中的所有剩余決策屬性取值完全相同，已不能根據(jù)這些決策屬性進(jìn)一步劃分子集。針對(duì)上一步中得到的每一個(gè)子集，重復(fù)進(jìn)行以上兩個(gè)步驟，直到最后的子集符合約束的3個(gè)條件之一根據(jù)符合條件不同生成葉子節(jié)點(diǎn)對(duì)決策樹進(jìn)行修剪，除去不必要的分枝，同時(shí)也能使決策樹得到簡(jiǎn)化。常用的決策樹修剪策略基于代價(jià)

34、復(fù)雜度的修剪悲觀修剪最小描述長(zhǎng)度修剪按照修剪的先后順序先剪枝（Pre-pruning）后剪枝（Post-pruning）of65393.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.3 分類技術(shù)2k-最近鄰最臨近分類基于類比學(xué)習(xí)，是一種基于實(shí)例的學(xué)習(xí)，它使用具體的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，而不必維護(hù)源自數(shù)據(jù)的抽象（或模型）。它采用n 維數(shù)值屬性描述訓(xùn)練樣本，每個(gè)樣本代表n 維空間的一個(gè)點(diǎn)，即所有的訓(xùn)練樣本都存放在n 維空間中。若給定一個(gè)未知樣本，k-最近鄰分類法搜索模式空間，計(jì)算該測(cè)試樣本與訓(xùn)練集中其他樣本的鄰近度，找出最接近未知樣本的k 個(gè)訓(xùn)練樣本，這k 個(gè)訓(xùn)練樣本就是未知樣本的k 個(gè)“近鄰”。其中的“鄰

35、近度”一般采用歐幾里得距離定義：兩個(gè)點(diǎn) 和 的Euclid距離是 。最近鄰分類是基于要求的或懶散的學(xué)習(xí)法，即它存放所有的訓(xùn)練樣本，并且直到新的（未標(biāo)記的）樣本需要分類時(shí)才建立分類。其優(yōu)點(diǎn)是可以生成任意形狀的決策邊界，能提供更加靈活的模型表示。of65403.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.4 案例：保險(xiǎn)客戶風(fēng)險(xiǎn)分析1挖掘目標(biāo)由過(guò)去大量的經(jīng)驗(yàn)數(shù)據(jù)發(fā)現(xiàn)機(jī)動(dòng)車輛事故率與駕駛者及所駕駛的車輛有著密切的關(guān)系，影響駕駛?cè)藛T安全駕駛的主要因素有年齡、性別、駕齡、職業(yè)、婚姻狀況、車輛車型、車輛用途、車齡等。因此，客戶風(fēng)險(xiǎn)分析的挖掘目標(biāo)就是上述各主要因素與客戶風(fēng)險(xiǎn)之間的關(guān)系，等等。2數(shù)據(jù)預(yù)處理數(shù)據(jù)準(zhǔn)備與

36、預(yù)處理是數(shù)據(jù)挖掘中的首要步驟，高質(zhì)量的數(shù)據(jù)是獲得高質(zhì)量決策的先決條件。在實(shí)施數(shù)據(jù)挖掘之前，及時(shí)有效的數(shù)據(jù)預(yù)處理可以解決噪聲問(wèn)題和處理缺失的信息，將有助于提高數(shù)據(jù)挖掘的精度和性能。去除數(shù)據(jù)集之中的噪聲數(shù)據(jù)和無(wú)關(guān)數(shù)據(jù)，處理遺漏數(shù)據(jù)和清洗“臟”數(shù)據(jù)等。數(shù)據(jù)清洗處理通常包括處理噪聲數(shù)據(jù)、填補(bǔ)遺漏數(shù)據(jù)值/除去異常值、糾正數(shù)據(jù)不一致的問(wèn)題，等等。在處理完噪聲數(shù)據(jù)后，就可以對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)化，主要的方法有： 聚集 忽略無(wú)關(guān)屬性 連續(xù)型屬性離散化等。數(shù)據(jù)清洗數(shù)據(jù)轉(zhuǎn)化of65413.4 關(guān)聯(lián)規(guī)則第三章 數(shù)據(jù)挖掘算法3.4.4 案例：保險(xiǎn)客戶風(fēng)險(xiǎn)分析3關(guān)聯(lián)規(guī)則挖掘影響駕駛?cè)藛T安全駕駛的主要因素年齡性別駕齡職業(yè)婚姻狀況

37、車輛車型車輛用途車齡其他根據(jù)前述關(guān)聯(lián)規(guī)則的生成方法，得到挖掘出來(lái)的客戶風(fēng)險(xiǎn)關(guān)聯(lián)規(guī)則序號(hào)關(guān)聯(lián)規(guī)則支持度置信度1駕齡（X，A）被保車輛的價(jià)值（X，A）年賠付金額（X，B）0.18250.29652投保人年齡（X，A）駕齡（X，A）年賠付次數(shù)（X，B）0.16790.25713駕齡（X，B）車輛用途（X，A）年賠付金額（X，B）0.16630.33374駕齡（X，B）車輛用途（X，B）年賠付次數(shù)（X，A）0.17890.48515駕齡（X，B）被保車輛的價(jià)值（X，C）年賠付金額（X，C）0.18090.30036駕齡（X，C）車輛用途（X，B）年賠付次數(shù)（X，A）0.19940.58647駕齡（X，

38、C）被保車輛的價(jià)值（X，C）車輛用途（X，C）年賠付次數(shù)（X，A）0.10310.66398駕齡（X，A）被保車輛的價(jià)值（X，A）車輛用途（X，B）年賠付金額（X，B）0.10250.36549投保人年齡（X，B）駕齡（X，A）被保車輛的價(jià)值（X，D）年賠付金額（X，D）0.09340.454610駕齡（X，B）被保車輛的價(jià)值（X，A）車輛用途（X，A）年賠付金額（X，B）0.09680.448711投保人年齡（X，C）被保車輛的價(jià)值（X，C）車輛用途（X，C）年賠付金額（X，B）0.09090.353112投保人年齡（X，C）駕齡（X，B）被保車輛的價(jià)值（X，C）年賠付次數(shù)（X，A）0.08

39、270.6094表3-7 客戶風(fēng)險(xiǎn)關(guān)聯(lián)規(guī)則詳細(xì)分析所得數(shù)據(jù)，可以為公司業(yè)務(wù)提供數(shù)據(jù)支撐，針對(duì)不同客戶提供偏好服務(wù)，既能確保公司收益，又能給予用戶更多的實(shí)惠。of65423.4關(guān)聯(lián)規(guī)則3.1數(shù)據(jù)挖掘概述第三章數(shù)據(jù)挖掘算法3.2分類3.3聚類3.4關(guān)聯(lián)規(guī)則習(xí)題3.6數(shù)據(jù)挖掘算法綜合應(yīng)用3.5預(yù)測(cè)規(guī)模of65433.5 預(yù)測(cè)模型3.5.1 預(yù)測(cè)與預(yù)測(cè)模型第三章 數(shù)據(jù)挖掘算法預(yù)測(cè)分析是一種統(tǒng)計(jì)或數(shù)據(jù)挖掘解決方案，包含可在結(jié)構(gòu)化與非結(jié)構(gòu)化數(shù)據(jù)中使用以確定未來(lái)結(jié)果的算法和技術(shù)，可為預(yù)測(cè)、優(yōu)化、預(yù)報(bào)和模擬等許多其他相關(guān)用途而使用。時(shí)間序列預(yù)測(cè)是一種歷史資料延伸預(yù)測(cè)，以時(shí)間序列所能反映的社會(huì)經(jīng)濟(jì)現(xiàn)象的發(fā)展過(guò)程

40、和規(guī)律性，進(jìn)行引申外推預(yù)測(cè)發(fā)展趨勢(shì)的方法。從時(shí)間序列數(shù)據(jù)中提取并組建特征，仍用原有的數(shù)據(jù)挖掘框架與算法進(jìn)行數(shù)據(jù)挖掘?qū)r(shí)間序列數(shù)據(jù)作為一種特殊的挖掘?qū)ο螅覍?duì)應(yīng)的數(shù)據(jù)挖掘算法進(jìn)行專門研究依據(jù)研究的方式分類相似性問(wèn)題挖掘時(shí)態(tài)模式挖掘依據(jù)研究的內(nèi)容分類依據(jù)研究的對(duì)象分類事件序列的數(shù)據(jù)挖掘事務(wù)序列的數(shù)據(jù)挖掘數(shù)值序列的數(shù)據(jù)挖掘時(shí)間序列預(yù)測(cè)及數(shù)據(jù)挖掘分類of65443.5 預(yù)測(cè)模型3.5.1 預(yù)測(cè)與預(yù)測(cè)模型第三章 數(shù)據(jù)挖掘算法預(yù)測(cè)方案分類時(shí)間序列預(yù)測(cè)定性預(yù)測(cè)方法依據(jù)預(yù)測(cè)方法的性質(zhì)因果關(guān)系預(yù)測(cè)時(shí)間序列的統(tǒng)計(jì)特征1）均值函數(shù)2）自協(xié)方差函數(shù)3）自相關(guān)函數(shù)of65453.5 預(yù)測(cè)模型3.5.1 預(yù)測(cè)與預(yù)測(cè)模型

41、第三章 數(shù)據(jù)挖掘算法1）自回歸模型2）移動(dòng)平均模型3）自回歸移動(dòng)平均模型of6546時(shí)間序列模型預(yù)測(cè)方案分類3.5 預(yù)測(cè)模型3.5.2 時(shí)間序列預(yù)測(cè)第三章 數(shù)據(jù)挖掘算法時(shí)間序列：對(duì)按時(shí)間順序排列而成的觀測(cè)值集合，進(jìn)行數(shù)據(jù)的預(yù)測(cè)或預(yù)估。典型的算法：序貫?zāi)Ｊ酵诰騍PMGC算法序貫?zāi)Ｊ酵诰蛩惴⊿PMGC（Sequential Pattern Mining Based on General Constrains）SPMGC算法可以有效地發(fā)現(xiàn)有價(jià)值的數(shù)據(jù)序列模式，提供給大數(shù)據(jù)專家們進(jìn)行各類時(shí)間序列的相似性與預(yù)測(cè)研究。項(xiàng)集間的時(shí)間限制Cgap序列持續(xù)時(shí)間限制Cduration數(shù)據(jù)約束Cdata項(xiàng)的約束Ci

42、tem序列長(zhǎng)度的約束CLength其他約束時(shí)間序列領(lǐng)域約束規(guī)則of65473.5 預(yù)測(cè)模型3.5.2 時(shí)間序列預(yù)測(cè)第三章 數(shù)據(jù)挖掘算法SPMGC算法的基本處理流程掃描時(shí)間序列數(shù)據(jù)庫(kù)，獲取滿足約束條件且長(zhǎng)度為1的序列模式L1，以序列模式L1作為初始種子集根據(jù)長(zhǎng)度為i-1的種子集Li-1，通過(guò)連接與剪切運(yùn)算生成長(zhǎng)度為i 并且滿足約束條件的候選序列模式Ci，基于此掃描序列數(shù)據(jù)庫(kù)，并計(jì)算每個(gè)候選序列模式Ci 的支持?jǐn)?shù)，從而產(chǎn)生長(zhǎng)度為I 的序列模式Li，將Li作為新種子集在此重復(fù)上一步，直至沒(méi)有新的候選序列模式或新的序列模式產(chǎn)生SPBGC算法首先對(duì)約束條件按照優(yōu)先級(jí)進(jìn)行排序，然后依據(jù)約束條件產(chǎn)生候選序列

43、。SPBGC算法說(shuō)明了怎樣使用約束條件來(lái)挖掘序貫?zāi)Ｊ剑欢?，由于?yīng)用領(lǐng)域的不同，具體的約束條件也不盡相同，同時(shí)產(chǎn)生頻繁序列的過(guò)程也可采用其他序貫?zāi)Ｊ剿惴?。of65483.5 預(yù)測(cè)模型3.5.3 案例：地震預(yù)警第三章 數(shù)據(jù)挖掘算法1地震波形數(shù)據(jù)存儲(chǔ)和計(jì)算平臺(tái)南京云創(chuàng)大數(shù)據(jù)有限公司為山東省地震局研發(fā)了一套可以處理海量數(shù)據(jù)的高性能地震波形數(shù)據(jù)存儲(chǔ)和計(jì)算平臺(tái)，將從現(xiàn)有的光盤中導(dǎo)入地震波形數(shù)據(jù)并加以管理，以提供集中式的地震波形數(shù)據(jù)分析與地震預(yù)測(cè)功能，為開展各種地震波形數(shù)據(jù)應(yīng)用提供海量數(shù)據(jù)存儲(chǔ)管理和計(jì)算服務(wù)能力。圖3-12山東省地震波測(cè)數(shù)據(jù)云平臺(tái)的顯示界面of65493.5 預(yù)測(cè)模型3.5.3 案例：地震

44、預(yù)警第三章 數(shù)據(jù)挖掘算法2地震波形數(shù)據(jù)存儲(chǔ)和計(jì)算平臺(tái)的主要性能指標(biāo)數(shù)據(jù)存儲(chǔ)和處理指標(biāo)系統(tǒng)響應(yīng)時(shí)間指標(biāo)地震波形數(shù)據(jù)存儲(chǔ)性能指標(biāo)每年的原始地震波形數(shù)據(jù)及相關(guān)輔助信息約為15TB，為保證數(shù)據(jù)存儲(chǔ)的可靠性，要求采用3倍副本方式保存數(shù)據(jù)，云平臺(tái)每年需要提供約45TB的總存儲(chǔ)量，同時(shí)系統(tǒng)必須能實(shí)時(shí)接收和處理高達(dá)10MB/s的入庫(kù)數(shù)據(jù)千兆網(wǎng)絡(luò)環(huán)境下，局域網(wǎng)客戶端從分布式文件存儲(chǔ)系統(tǒng)中讀取4096B存儲(chǔ)內(nèi)容的響應(yīng)時(shí)間不高于50毫秒采用HDFS格式進(jìn)行數(shù)據(jù)讀取，讀取性能為4080MB/s節(jié)點(diǎn)，數(shù)據(jù)規(guī)模10PB，數(shù)據(jù)負(fù)載均衡時(shí)間可依據(jù)流量配置而確定，集群重新啟動(dòng)時(shí)間按10PB規(guī)模計(jì)算達(dá)到分鐘級(jí)別of65503.5

45、 預(yù)測(cè)模型3.5.3 案例：地震預(yù)警第三章 數(shù)據(jù)挖掘算法3地震波形數(shù)據(jù)存儲(chǔ)和計(jì)算平臺(tái)的功能設(shè)計(jì)21345數(shù)據(jù)解析數(shù)據(jù)入庫(kù)數(shù)據(jù)存儲(chǔ)管理云計(jì)算平臺(tái)的數(shù)據(jù)應(yīng)用接口數(shù)據(jù)異地修復(fù)功能設(shè)計(jì)of65513.5 預(yù)測(cè)模型3.5.3 案例：地震預(yù)警第三章 數(shù)據(jù)挖掘算法4平臺(tái)的組成、總體構(gòu)架與功能模塊圖3-13 地震波形數(shù)據(jù)云平臺(tái)總體構(gòu)架與功能模塊of65523.5 預(yù)測(cè)模型3.5.3 案例：地震預(yù)警第三章 數(shù)據(jù)挖掘算法5地震中的時(shí)間序列預(yù)測(cè)地震預(yù)測(cè)的主要手段也就是對(duì)地震序列進(jìn)行特征研究。通過(guò)對(duì)地震序列的特征研究，可以幫助判斷某大地震發(fā)生后地質(zhì)活動(dòng)的規(guī)律，掌握一定區(qū)域內(nèi)地震前后震級(jí)次序間的某種內(nèi)在關(guān)聯(lián)性，有利于判

46、斷次地震發(fā)生后，震區(qū)地質(zhì)活動(dòng)的客觀趨勢(shì)1）地震數(shù)據(jù)收集和預(yù)處理采用SPBGC算法，預(yù)處理的流程步驟具體如下：設(shè)定地震序列的空間跨度，并劃分震級(jí)標(biāo)準(zhǔn)M依據(jù)地震目錄數(shù)據(jù)庫(kù)，將震級(jí)大于或等于震級(jí)標(biāo)準(zhǔn)M的地震信息存入大地震文件獲取大地震文件中的每一條記錄E，并取得震級(jí)M與震中所在位置G掃描地震目錄數(shù)據(jù)，對(duì)每一地震記錄E，均判斷當(dāng)前地震位置與震中G的距離是否滿足設(shè)定的空間跨度。如果滿足空間跨度，則將該記錄標(biāo)注為與震中等同的序列號(hào)，同時(shí)將震中為圓心的區(qū)域范圍內(nèi)地震的次數(shù)加l；否則繼續(xù)處理下一條地震記錄大地震文件處理完畢后，該階段地震數(shù)據(jù)收集和預(yù)處理階段結(jié)束of65533.4關(guān)聯(lián)規(guī)則3.1數(shù)據(jù)挖掘概述第三章數(shù)據(jù)挖掘算法3.2分類3.