03.《大數據》配套之四第3章-數據挖掘算法下

1、,全國高校標準教材《云計算》姊妹篇，剖析大數據核心技術和實戰(zhàn)應用,大數據,,,,劉鵬　　主編　　　　張燕　張重生　張志立　 副主編,,,BIG DATA,,劉 鵬,,,全國高校標準教材《云計算》姊妹篇，剖析大數據核心技術和實戰(zhàn)應用,,,of,65,3,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關聯規(guī)則是數據挖掘中最活躍的研究方法之一，是指搜索業(yè)務系統(tǒng)中的所有

2、細節(jié)或事務，找出所有能把一組事件或數據項與另一組事件或數據項聯系起來的規(guī)則，以獲得存在于數據庫中的不為人知的或不能確定的信息，它側重于確定數據中不同領域之間的聯系，也是在無指導學習系統(tǒng)中挖掘本地模式的最普通形式。,應用市場：市場貨籃分析、交叉銷售（Crossing Sale）、部分分類（Partial Classification）、金融服務（Financial Service），以及通信、互聯網、電子商務 ··&#

3、183;···,第三章 數據挖掘算法,of,65,4,,,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,一般來說，關聯規(guī)則挖掘是指從一個大型的數據集（Dataset）發(fā)現有趣的關聯（Association）或相關關系（Correlation），即從數據集中識別出頻繁出現的屬性值集（Sets of Attribu

4、te Values），也稱為頻繁項集（Frequent Itemsets，頻繁集），然后利用這些頻繁項集創(chuàng)建描述關聯關系的規(guī)則的過程。,3.4.1 關聯規(guī)則的概念,關聯規(guī)則挖掘問題：,發(fā)現所有的頻繁項集是形成關聯規(guī)則的基礎。通過用戶給定的最小支持度，尋找所有支持度大于或等于Minsupport的頻繁項集。,通過用戶給定的最小可信度，在每個最大頻繁項集中，尋找可信度不小于Minconfidence的關聯規(guī)則。,發(fā)現頻繁項集,生成關聯規(guī)則,

5、如何迅速高效地發(fā)現所有頻繁項集，是關聯規(guī)則挖掘的核心問題，也是衡量關聯規(guī)則挖掘算法效率的重要標準。,of,65,5,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.2 頻繁項集的產生及其經典算法,格結構（Lattice Structure）常常被用來枚舉所有可能的項集。,圖3-10 項集的格,of,65,6,,3.4 關聯規(guī)則,,,

6、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.2 頻繁項集的產生及其經典算法,格結構（Lattice Structure）常常被用來枚舉所有可能的項集。,of,65,7,,,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.2 頻繁項集的產生及其經典算法,

7、1．Apriori算法,Apriori算法基于頻繁項集性質的先驗知識，使用由下至上逐層搜索的迭代方法，即從頻繁1項集開始，采用頻繁k項集搜索頻繁k+1項集，直到不能找到包含更多項的頻繁項集為止。,Apriori算法由以下步驟組成，其中的核心步驟是連接步和剪枝步：,生成頻繁1項集L1,連接步,剪枝步,生成頻繁k項集Lk,重復步驟（2）～（4），直到不能產生新的頻繁項集的集合為止，算法中止。,,,,,性能瓶頸,Apriori算法是一個多趟搜

8、索算法,可能產生龐大的候選項集,,of,65,8,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.2 頻繁項集的產生及其經典算法,2．FP-Growth算法,頻繁模式樹增長算法（Frequent Pattern Tree Growth）采用分而治之的基本思想，將數據庫中的頻繁項集壓縮到一棵頻繁模式樹中，同時保持項集之間的關聯關系。然后

9、將這棵壓縮后的頻繁模式樹分成一些條件子樹，每個條件子樹對應一個頻繁項，從而獲得頻繁項集，最后進行關聯規(guī)則挖掘。,FP-Growth算法由以下步驟組成：,掃描事務數據庫D，生成頻繁1項集L1,將頻繁1項集L1按照支持度遞減順序排序，得到排序后的項集L1,構造FP樹,通過后綴模式與條件FP樹產生的頻繁模式連接實現模式增長,1,2,3,4,圖3-11 FP樹的構造,of,65,9,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,

10、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.2 頻繁項集的產生及其經典算法,3．辛普森悖論,雖然關聯規(guī)則挖掘可以發(fā)現項目之間的有趣關系，在某些情況下，隱藏的變量可能會導致觀察到的一對變量之間的聯系消失或逆轉方向，這種現象就是所謂的辛普森悖論（Simpson’s Paradox）。,為了避免辛普森悖論的出現，就需要斟酌各個分組的權重，并以一定的系數去消除以分組數據基數差異所造成的影響。同時必

11、須了解清楚情況，是否存在潛在因素，綜合考慮。,of,65,10,,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.3 分類技術,分類技術或分類法（Classification）是一種根據輸入樣本集建立類別模型，并按照類別模型對未知樣本類標號進行標記的方法。,根據所采用的分類模型不同,基于決策樹模型的數據分類,基于統(tǒng)計模型的數據分類,基

12、于神經網絡模型的數據分類,基于案例推理的數據分類,基于實例的數據分類,,1．決策樹,決策樹就是通過一系列規(guī)則對數據進行分類的過程。,決策樹分類算法通常分為兩個步驟：構造決策樹和修剪決策樹。,of,65,11,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.3 分類技術,構造決策樹,修剪決策樹,根據實際需求及所處理數據的特性，選擇類別標

13、識屬性和決策樹的決策屬性集,在決策屬性集中選擇最有分類標識能力的屬性作為決策樹的當前決策節(jié)點,根據當前決策節(jié)點屬性取值的不同，將訓練樣本數據集劃分為若干子集,根據符合條件不同生成葉子節(jié)點,對決策樹進行修剪，除去不必要的分枝，同時也能使決策樹得到簡化。,,,,,常用的決策樹修剪策略,基于代價復雜度的修剪,悲觀修剪,最小描述長度修剪,,,,按照修剪的先后順序,先剪枝（Pre-pruning）,后剪枝（Post-pruning）,,,of,6

14、5,12,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.3 分類技術,2．k-最近鄰,,,,最臨近分類基于類比學習，是一種基于實例的學習，它使用具體的訓練實例進行預測，而不必維護源自數據的抽象（或模型）。它采用n 維數值屬性描述訓練樣本，每個樣本代表n 維空間的一個點，即所有的訓練樣本都存放在n 維空間中。若給定一個未知樣本，k-最

15、近鄰分類法搜索模式空間，計算該測試樣本與訓練集中其他樣本的鄰近度，找出最接近未知樣本的k 個訓練樣本，這k 個訓練樣本就是未知樣本的k 個“近鄰”。其中的“鄰近度”一般采用歐幾里得距離定義：兩個點 和 的Euclid距離是 。,最近鄰分類是基于要求的或懶散的學習法，即它存放

16、所有的訓練樣本，并且直到新的（未標記的）樣本需要分類時才建立分類。其優(yōu)點是可以生成任意形狀的決策邊界，能提供更加靈活的模型表示。,of,65,13,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.4 案例：保險客戶風險分析,1．挖掘目標,,,,由過去大量的經驗數據發(fā)現機動車輛事故率與駕駛者及所駕駛的車輛有著密切的關系，影響駕駛人員安全

17、駕駛的主要因素有年齡、性別、駕齡、職業(yè)、婚姻狀況、車輛車型、車輛用途、車齡等。因此，客戶風險分析的挖掘目標就是上述各主要因素與客戶風險之間的關系，等等。,2．數據預處理,數據準備與預處理是數據挖掘中的首要步驟，高質量的數據是獲得高質量決策的先決條件。在實施數據挖掘之前，及時有效的數據預處理可以解決噪聲問題和處理缺失的信息，將有助于提高數據挖掘的精度和性能。,去除數據集之中的噪聲數據和無關數據，處理遺漏數據和清洗“臟”數據等。數據清洗

18、處理通常包括處理噪聲數據、填補遺漏數據值/除去異常值、糾正數據不一致的問題，等等。,在處理完噪聲數據后，就可以對數據進行轉化，主要的方法有： 聚集 忽略無關屬性 連續(xù)型屬性離散化等。,數據清洗,數據轉化,,,,of,65,14,,3.4 關聯規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第三章 數據挖掘算法,3.4.4 案例：保

19、險客戶風險分析,3．關聯規(guī)則挖掘,,,,表3-7 客戶風險關聯規(guī)則,詳細分析所得數據，可以為公司業(yè)務提供數據支撐，針對不同客戶提供偏好服務，既能確保公司收益，又能給予用戶更多的實惠。,of,65,15,,全國高校標準教材《云計算》姊妹篇，剖析大數據核心技術和實戰(zhàn)應用,,,of,65,16,,,,,3.5 預測模型,,,3.5.1 預測與預測模型,,第三章 數據挖掘算法,預測分析是一種統(tǒng)計或數據挖掘解決方案，包含可在結構化與非結構化數據

20、中使用以確定未來結果的算法和技術，可為預測、優(yōu)化、預報和模擬等許多其他相關用途而使用。,時間序列預測是一種歷史資料延伸預測，以時間序列所能反映的社會經濟現象的發(fā)展過程和規(guī)律性，進行引申外推預測發(fā)展趨勢的方法。,從時間序列數據中提取并組建特征，仍用原有的數據挖掘框架與算法進行數據挖掘,將時間序列數據作為一種特殊的挖掘對象，找尋對應的數據挖掘算法進行專門研究,,,依據研究的方式分類,,,,相似性問題挖掘,時態(tài)模式挖掘,,,依據研究的內容分類

21、,,,,,,依據研究的對象分類,,,事件序列的數據挖掘,事務序列的數據挖掘,數值序列的數據挖掘,時間序列預測及數據挖掘分類,of,65,17,,3.5 預測模型,,,3.5.1 預測與預測模型,,第三章 數據挖掘算法,預測方案分類,,1）均值函數,,,2）自協(xié)方差函數,,,3）自相關函數,,,,,of,65,18,,3.5 預測模型,,,3.5.1 預測與預測模型,,第三章 數據挖掘算法,,,,,,,of,65,19,預測方案分類,,3

22、.5 預測模型,,,3.5.2 時間序列預測,,第三章 數據挖掘算法,,,,,,,時間序列：對按時間順序排列而成的觀測值集合，進行數據的預測或預估。,典型的算法：序貫模式挖掘SPMGC算法,序貫模式挖掘算法SPMGC（Sequential Pattern Mining Based on General Constrains）SPMGC算法可以有效地發(fā)現有價值的數據序列模式，提供給大數據專家們進行各類時間序列的相似性與預測研究。,時間序列

23、領域約束規(guī)則,of,65,20,,,,,3.5 預測模型,,,3.5.2 時間序列預測,,第三章 數據挖掘算法,,,,,,,SPMGC算法的基本處理流程,掃描時間序列數據庫，獲取滿足約束條件且長度為1的序列模式L1，以序列模式L1作為初始種子集,根據長度為i-1的種子集Li-1，通過連接與剪切運算生成長度為i 并且滿足約束條件的候選序列模式Ci，基于此掃描序列數據庫，并計算每個候選序列模式Ci 的支持數，從而產生長度為I 的序列模式Li

24、，將Li作為新種子集,在此重復上一步，直至沒有新的候選序列模式或新的序列模式產生,SPBGC算法首先對約束條件按照優(yōu)先級進行排序，然后依據約束條件產生候選序列。SPBGC算法說明了怎樣使用約束條件來挖掘序貫模式，然而，由于應用領域的不同，具體的約束條件也不盡相同，同時產生頻繁序列的過程也可采用其他序貫模式算法。,,,of,65,21,,3.5 預測模型,,,3.5.3 案例：地震預警,,第三章 數據挖掘算法,,,,,,,1．地震波形數據

25、存儲和計算平臺,南京云創(chuàng)大數據有限公司為山東省地震局研發(fā)了一套可以處理海量數據的高性能地震波形數據存儲和計算平臺，將從現有的光盤中導入地震波形數據并加以管理，以提供集中式的地震波形數據分析與地震預測功能，為開展各種地震波形數據應用提供海量數據存儲管理和計算服務能力。,圖3-12山東省地震波測數據云平臺的顯示界面,of,65,22,,,,,,,,3.5 預測模型,,,3.5.3 案例：地震預警,,第三章 數據挖掘算法,,,,,,,2．地震

26、波形數據存儲和計算平臺的主要性能指標,數據存儲和處理指標,系統(tǒng)響應時間指標,地震波形數據存儲性能指標,每年的原始地震波形數據及相關輔助信息約為15TB，為保證數據存儲的可靠性，要求采用3倍副本方式保存數據，云平臺每年需要提供約45TB的總存儲量，同時系統(tǒng)必須能實時接收和處理高達10MB/s的入庫數據,千兆網絡環(huán)境下，局域網客戶端從分布式文件存儲系統(tǒng)中讀取4096B存儲內容的響應時間不高于50毫秒,采用HDFS格式進行數據讀取，讀取性能為

27、40～80MB/s節(jié)點，數據規(guī)模10PB，數據負載均衡時間可依據流量配置而確定，集群重新啟動時間按10PB規(guī)模計算達到分鐘級別,of,65,23,,3.5 預測模型,,,3.5.3 案例：地震預警,,第三章 數據挖掘算法,,,,,,,3．地震波形數據存儲和計算平臺的功能設計,數據解析,數據入庫,數據存儲管理,云計算平臺的數據應用接口,數據異地修復,,,,,,功能設計,of,65,24,,3.5 預測模型,,,3.5.3 案例：地震預警,

28、,第三章 數據挖掘算法,,,,,,,4．平臺的組成、總體構架與功能模塊,圖3-13 地震波形數據云平臺總體構架與功能模塊,of,65,25,,3.5 預測模型,,,3.5.3 案例：地震預警,,第三章 數據挖掘算法,,,,,,,5．地震中的時間序列預測,地震預測的主要手段也就是對地震序列進行特征研究。通過對地震序列的特征研究，可以幫助判斷某大地震發(fā)生后地質活動的規(guī)律，掌握一定區(qū)域內地震前后震級次序間的某種內在關聯性，有利于判斷次地震發(fā)

29、生后，震區(qū)地質活動的客觀趨勢,1）地震數據收集和預處理,采用SPBGC算法，預處理的流程步驟具體如下：,設定地震序列的空間跨度，并劃分震級標準M,依據地震目錄數據庫，將震級大于或等于震級標準M的地震信息存入大地震文件,獲取大地震文件中的每一條記錄E，并取得震級M與震中所在位置G,掃描地震目錄數據，對每一地震記錄E，均判斷當前地震位置與震中G的距離是否滿足設定的空間跨度。如果滿足空間跨度，則將該記錄標注為與震中等同的序列號，同時將震中為圓

30、心的區(qū)域范圍內地震的次數加l；否則繼續(xù)處理下一條地震記錄,大地震文件處理完畢后，該階段地震數據收集和預處理階段結束,,,,,,of,65,26,,全國高校標準教材《云計算》姊妹篇，剖析大數據核心技術和實戰(zhàn)應用,,,of,65,27,,,,,3.6數據挖掘算法綜合應用,,,3.6.1 案例分析：精確營銷中的關聯規(guī)則應用,,數據挖掘在各領域的應用非常廣泛，只要該產業(yè)擁有具備分析價值與需求的數據倉儲或數據庫，都可以利用挖掘工具進行有目的的挖掘

31、分析。一般較常見的應用案例多發(fā)生在零售業(yè)、制造業(yè)、財務金融保險、通信業(yè)及醫(yī)療服務等。,？,如何通過交叉銷售，得到更大的收入？,如何在銷售數據中發(fā)掘顧客的消費習性，并由交易記錄找出顧客偏好的產品組合？,如何找出流失顧客的特征與推出新產品的時機點？,通過關聯規(guī)則挖掘來發(fā)現和捕捉數據間隱藏的重要關聯，從而為產品營銷提供技術支撐。,第三章 數據挖掘算法,of,65,28,,3.6數據挖掘算法綜合應用,,,3.6.2 挖掘目標的提出,,第三章 數

32、據挖掘算法,電子商務網站中的商品推薦為例,客戶忠誠度,影響因素,其他因素：如社會文化、國家政策等,客戶自身原因,企業(yè)原因,,數據挖掘技術可以建立客戶忠誠度分析模型，了解哪些因素對客戶的忠誠度有較大的影響，從而采取相應措施。因此，基于數據挖掘技術的客戶忠誠度分析具有重要的應用價值。,of,65,29,,3.6數據挖掘算法綜合應用,,,3.6.3 分析方法與過程,,第三章 數據挖掘算法,圖3-14 電子商務網站操作流程,of,65,30,

33、,3.6數據挖掘算法綜合應用,,,3.6.3 分析方法與過程,,第三章 數據挖掘算法,在電子商務系統(tǒng)中，忠誠度分析所需要的客戶信息和交易信息分別存放在網站數據庫的客戶表、訂單表及訂單明細表中。,將客戶的忠誠度分為4個等級：0——忠誠；1——由忠誠變?yōu)椴恢艺\；2——由不忠誠變?yōu)橹艺\；3——不忠誠。,表3-9 經抽取而成的客戶信息表,所得到的用戶數據很難做到完整全面，用戶在注冊時可能選擇不填注冊信息的幾項，造成數據項空缺。對于空缺的數據項

34、，要視情況排除或填入默認值。按照一般的統(tǒng)計劃分經驗來對屬性值進行分段，實現離散化。,of,65,31,,3.6數據挖掘算法綜合應用,,,3.6.3 分析方法與過程,,第三章 數據挖掘算法,表3-10 經離散變換后的客戶信息表,本案例采用基于信息論的ID3決策樹分類算法進行客戶忠誠度分析。,客戶群細分使得公司可以更好地識別不同的客戶群體，區(qū)別對待不同客戶，采取不同的客戶策略，達到最優(yōu)化配置客戶資源的目的。,使用聚類算法進行客戶群，數據

35、項處理過程主要將這些表內反映客戶身份背景、購買興趣度等相關信息提取出來，并加以清理，除去噪聲數據，對信息不完全的數據填入默認值或舍去，進行必要的離散化變換。,of,65,32,,3.6數據挖掘算法綜合應用,,,3.6.3 分析方法與過程,,第三章 數據挖掘算法,表3-11 客戶興趣度表,商品推薦是電子商務網站用來向訪問網站的顧客提供商品信息和建議，并模擬銷售人員幫助顧客完成購買過程。它是利用數據挖掘技術在電子商務網站中來幫助顧客訪問有

36、興趣的產品信息。推薦可以是根據其他客戶的信息或此客戶的信息，參照該顧客以往的購買行為預測未來的購買行為，幫助用戶從龐大的商品目錄中挑選真正適合自己需要的商品。推薦技術在幫助了客戶的同時也提高了顧客對網站的滿意度，換來對商務網站的進一步支持。,of,65,33,,1．依據研究的方式分類，可將時間序列預測與挖掘分為哪些類？2．根據預測方法的性質將預測方法分為哪些類？各有何優(yōu)缺點？3．時序預測方面典型的算法有哪些？各有什么特點？4．什么

37、是序貫模式挖掘SPMGC算法？5．時間序列預測方法分哪幾類？主要適用領域是哪些？,習題：,百度排名首位的大數據資料和交流中心,百度排名首位的云計算資料和交流中心,BDRack大數據實驗一體機,虛擬出百套集群，并行開展大數據實驗預裝各種流行云計算和大數據平臺提供配套實驗教程、課件、PPT和培訓,,,,,劉鵬看未來,云計算頭條,云創(chuàng)大數據,中國大數據,微信號： chinacloudnj,微信號： cstorbigdata,資源豐富、分