數(shù)據(jù)挖掘基礎電子課件

大數(shù)據(jù)應用人才培養(yǎng)系列教材數(shù)據(jù)挖掘基礎第一章數(shù)據(jù)挖掘概念1.1數(shù)據(jù)挖掘概述1.3數(shù)據(jù)挖掘的應用習題大數(shù)據(jù)應用人才培養(yǎng)系列教材1.2數(shù)據(jù)探索1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.1什么是數(shù)據(jù)挖掘數(shù)據(jù)挖掘(DataMining)，就是從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。數(shù)據(jù)挖掘的數(shù)據(jù)源包括數(shù)據(jù)庫、數(shù)據(jù)倉庫、Web或其他數(shù)據(jù)存儲庫。1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.2數(shù)據(jù)挖掘常用算法概述在面對海量數(shù)據(jù)時，需要使用一定的算法，才能從中挖掘出有用的信息，下面介紹數(shù)據(jù)挖掘中常用的算法。1.分類算法(1)決策樹算法決策樹算法是一種典型的分類算法，首先利用已知分類的數(shù)據(jù)構造決策樹，然后利用測試數(shù)據(jù)集對決策樹進行剪枝，每個決策樹的葉子都是一種分類，最后利用形成的決策樹對數(shù)據(jù)進行分類。決策樹的典型算法有ID3，C4.5，CART等。1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.2數(shù)據(jù)挖掘常用算法概述(2)貝葉斯分類算法

貝葉斯分類算法是統(tǒng)計學的一種方法，其中樸素貝葉斯算法在許多情況下可以與決策樹和神經(jīng)網(wǎng)絡算法相媲美，而且方法簡單，準確度高，速度快。貝葉斯算法是基于貝葉斯定理的，而貝葉斯定理假設一個屬性值對給定類的影響獨立于其它屬性值，但這種假設在很多情況下是不成立的，因此為了降低這個假設的影響，產(chǎn)生了很多改進算法，比如TAN(treeaugmentedBayesnetwork)算法。1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.2數(shù)據(jù)挖掘常用算法概述(3)支持向量機

支持向量機(SupportVectorMachine，SVM)是建立在統(tǒng)計學理論的VC維理論和結構風險最小原理基礎上的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應用到函數(shù)擬合等其他機器學習問題中。支持向量機算法將在后面章節(jié)做詳細介紹。1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.2數(shù)據(jù)挖掘常用算法概述2.聚類算法

聚類算法不同于分類算法，不會考慮類標號，這是因為在很多情況下，開始并不存在類標號。聚類算法可以根據(jù)最大化類內(nèi)相似性、最小化類間相似性的原則進行聚類或分組，這樣就形成了對象的簇，同一個簇內(nèi)的數(shù)據(jù)具有較高的相似性，不同簇之間的數(shù)據(jù)具有較低的相似性。常見的分類算法有K-MEANS算法、K-MEDOIDS算法等。3.關聯(lián)規(guī)則關聯(lián)規(guī)則是形如X→Y的蘊涵式，X和Y分別稱為關聯(lián)規(guī)則的先導和后繼。1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.3數(shù)據(jù)挖掘常用工具概述1.Weka軟件Weka(WaikatoEnvironmentforKnowledgeAnalysis)的全名是懷卡托智能分析環(huán)境，是一款免費與非商業(yè)化的數(shù)據(jù)挖掘軟件，基于Java環(huán)境下開源的機器學習與數(shù)據(jù)挖掘軟件。Weka的源代碼可在其官方網(wǎng)站下載。它集成了大量數(shù)據(jù)挖掘算法，包括數(shù)據(jù)預處理、分類、聚類、關聯(lián)分析等。用戶既可以使用可視化界面進行操作，也可以使用Weka提供的接口，實現(xiàn)自己的數(shù)據(jù)挖掘算法。圖形用戶界面包括WekaKnowledgeFlowEnvironment和WekaExplorer。用戶也可以使用Java語言調(diào)用Weka提供的類庫實現(xiàn)數(shù)據(jù)挖掘算法，這些類庫存在于weka.jar中。1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.3數(shù)據(jù)挖掘常用工具概述2.Clementine(SPSS)軟件Clementine是SPSS所發(fā)行的一種資料探勘工具，集成了分類、聚類和關聯(lián)規(guī)則等算法，Clementine提供了可視化工具，方便用戶操作。其通過一系列節(jié)點來執(zhí)行挖掘過程，這一過程被稱作一個數(shù)據(jù)流，數(shù)據(jù)流上面的節(jié)點代表了要執(zhí)行的操作。Clementine的資料可視化能力包含散布圖、平面圖及Web分析。1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.3數(shù)據(jù)挖掘常用工具概述Clementine(SPSS)案例圖1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.3數(shù)據(jù)挖掘常用工具概述3.KNIME軟件KNIME(KonstanzInformationMiner)是基于Eclipse開發(fā)環(huán)境來精心開發(fā)的數(shù)據(jù)挖掘工具，可以擴展使用Weka中的數(shù)據(jù)挖掘算法。和Clementine類似，KNIME使用類似數(shù)據(jù)流的方式實現(xiàn)數(shù)據(jù)挖掘過程，挖掘流程由一系列功能節(jié)點組成，每個節(jié)點有輸入、輸出端口，用于接收數(shù)據(jù)或模型、導出結果。1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.3數(shù)據(jù)挖掘常用工具概述KNIME軟件案例圖1.1數(shù)據(jù)挖掘概述第一章數(shù)據(jù)挖掘概念1.1.3數(shù)據(jù)挖掘常用工具概述4.RapidMiner軟件RapidMiner在2015年KDnuggets舉辦的第16屆國際數(shù)據(jù)挖掘暨分析軟件投票中位居第2，僅次于R語言。RapidMiner具有豐富的數(shù)據(jù)挖掘分析和算法功能，常用與解決各種商業(yè)關鍵問題，如：資源規(guī)劃、營銷響應率等等典型商業(yè)案例。RapidMiner提供解決方案涉及多個行業(yè)、領域，如：生命科學、制造業(yè)、石油、保險、汽車、銀行通訊等等。不過，它不支持分析流程圖方式。第一章數(shù)據(jù)挖掘概念1.2數(shù)據(jù)探索1.3數(shù)據(jù)挖掘的應用習題大數(shù)據(jù)應用人才培養(yǎng)系列教材1.1數(shù)據(jù)挖掘概述1.2數(shù)據(jù)探索第一章數(shù)據(jù)挖掘概念1.2.1數(shù)據(jù)概述數(shù)據(jù)挖掘質量的高低與數(shù)據(jù)有著密切的關系，本節(jié)主要探索性學習一些數(shù)據(jù)相關的知識。數(shù)據(jù)類型、數(shù)據(jù)質量、

數(shù)據(jù)挖掘前預處理、數(shù)據(jù)分析數(shù)據(jù)集是數(shù)據(jù)對象的集合。數(shù)據(jù)對象又叫做點、記錄、向量、事件、案例、樣本、模式、觀測或實體。數(shù)據(jù)對象用一組刻畫對象基本特性（如物體質量或事件發(fā)生時間）的屬性描述。屬性又稱為維度、變量、特性、字段、特征等。1.2數(shù)據(jù)探索第一章數(shù)據(jù)挖掘概念1.2.1數(shù)據(jù)概述1.屬性（1）區(qū)分屬性可通過屬性可能取值的個數(shù)來判斷。（2）非對稱的屬性2.數(shù)據(jù)集的一般特性數(shù)據(jù)集一般具有三個特性，分別是維度、稀疏性、

分辨率三個，它們對數(shù)據(jù)挖掘有重要影響。3.較常見的數(shù)據(jù)類型1.2數(shù)據(jù)探索第一章數(shù)據(jù)挖掘概念1.2.2數(shù)據(jù)質量1.什么是測量誤差和數(shù)據(jù)收集誤差測量誤差是測量中測量結果與實際值之間的差值叫誤差。數(shù)據(jù)收集誤差是指收集數(shù)據(jù)時遺漏數(shù)據(jù)對象或屬性值，或包含了其他數(shù)據(jù)對象等情況。2.什么是噪聲噪聲是從物理角度而言，噪聲是波形不規(guī)則的聲音。1.2數(shù)據(jù)探索第一章數(shù)據(jù)挖掘概念1.2.2數(shù)據(jù)質量3.什么是精度和準確率精度（同一個基本量）重復測量值之間的近似程度，一般用值集合的標準差度量。準確率從實驗角度是指在一定實驗條件下的多個測定值中，滿足限定條件的測定值所占的比例，常用符合率來表示。4.遺漏刪除數(shù)據(jù)對象或屬性估計遺漏值1.2數(shù)據(jù)探索第一章數(shù)據(jù)挖掘概念1.2.2數(shù)據(jù)質量5.離群點離群點又稱歧義值或異常值，離群點從數(shù)理統(tǒng)計角度是指一個時間序列中，遠離序列的一般水平的極端大值和極端小值。6.重復數(shù)據(jù)時效性相關性1.2數(shù)據(jù)探索第一章數(shù)據(jù)挖掘概念1.2.3數(shù)據(jù)預處理1.聚集聚集是將兩個或多個對象合并成單個對象。2.抽樣抽樣方法漸進抽樣3.維歸約4．維災難5．維歸約的線性代數(shù)技術第一章數(shù)據(jù)挖掘概念1.3數(shù)據(jù)挖掘的應用1.2數(shù)據(jù)探索習題大數(shù)據(jù)應用人才培養(yǎng)系列教材1.1數(shù)據(jù)挖掘概述1.3數(shù)據(jù)挖掘的應用第一章數(shù)據(jù)挖掘概念1.3.1數(shù)據(jù)挖掘現(xiàn)狀及發(fā)展趨勢就目前而言，大數(shù)據(jù)的來源是通過各種數(shù)據(jù)采集器、數(shù)據(jù)庫、開源的數(shù)據(jù)發(fā)布、GPS信息、網(wǎng)絡痕跡（搜索記錄、購物等）、傳感器收集、用戶保存等等結構化、半結構化、非結構化的數(shù)據(jù)。1.3數(shù)據(jù)挖掘的應用第一章數(shù)據(jù)挖掘概念1.3.1數(shù)據(jù)挖掘現(xiàn)狀及發(fā)展趨勢數(shù)據(jù)挖掘發(fā)展第一，語言標準化，使語言描述形式化、標準化。第二，實施標準化，即真正的可視化數(shù)據(jù)挖掘，在知識發(fā)現(xiàn)過程人機交互更便捷。第三，Web數(shù)據(jù)挖掘，建立DMKD（數(shù)據(jù)挖掘和知識發(fā)現(xiàn)）服務器。第四，實現(xiàn)多媒體數(shù)據(jù)挖掘，多媒體數(shù)據(jù)是一種多維的、半結構化、非結構化等形式的數(shù)據(jù)。1.3數(shù)據(jù)挖掘的應用第一章數(shù)據(jù)挖掘概念1.3.2數(shù)據(jù)挖掘需要解決什么問題在面對大量非結構、半結構數(shù)據(jù)集帶來的問題時，傳統(tǒng)的數(shù)據(jù)分析技術、方法常常遇到很多的問題甚至是困境，這也是要進行真正數(shù)據(jù)挖掘需要解決的問題。1.3數(shù)據(jù)挖掘的應用第一章數(shù)據(jù)挖掘概念1.3.2數(shù)據(jù)挖掘需要解決什么問題1.算法延展性2.高維性3.多種而復雜數(shù)據(jù)4.數(shù)據(jù)的所有權與分布5.非傳統(tǒng)的分析1.3數(shù)據(jù)挖掘的應用第一章數(shù)據(jù)挖掘概念1.算法延展性算法延展性即為算法彈性，隨著數(shù)據(jù)產(chǎn)生、采集技術的快速進步，以GB、TB、PB（1GB=1024MB，1TB=1024GB，1PB=1024TB）為單位的數(shù)據(jù)集越來越普遍。2.高維性在以前的數(shù)據(jù)庫構成中只有少量屬性的數(shù)據(jù)集，現(xiàn)在大數(shù)據(jù)集群構成中是具有成百上千屬性的數(shù)據(jù)集。3.多種而復雜數(shù)據(jù)在傳統(tǒng)數(shù)據(jù)分析方法里只處理包含相同類型屬性的數(shù)據(jù)集，或者是連續(xù)的，或者是分類的。4.數(shù)據(jù)的所有權與分布現(xiàn)在經(jīng)常會有這樣的狀況，需要分析的數(shù)據(jù)并非存放在一個站點，或歸屬一個機構，而是地理或空間分布在屬于多個機構的資源中。5.非傳統(tǒng)的分析統(tǒng)計方法的傳統(tǒng)方法是基于先提出一種假設然后檢驗，即提出一種假設，再設計實驗來收集數(shù)據(jù)，然后以假設為基礎分析數(shù)據(jù)。1.3數(shù)據(jù)挖掘的應用第一章數(shù)據(jù)挖掘概念1.3.3數(shù)據(jù)挖掘的應用場景1.商業(yè)數(shù)據(jù)挖掘應用場景2.智慧交通數(shù)據(jù)挖掘應用場景3.金融行業(yè)數(shù)據(jù)挖掘應用場景4.醫(yī)療行業(yè)數(shù)據(jù)挖掘應用場景5.農(nóng)業(yè)數(shù)據(jù)挖掘應用場景6.氣象數(shù)據(jù)挖掘應用場景1.3數(shù)據(jù)挖掘的應用第一章數(shù)據(jù)挖掘概念

數(shù)據(jù)挖掘的應用場景對應應用場景模式商業(yè)數(shù)據(jù)挖掘應用場景在銷售策略制定中，可以通過數(shù)據(jù)挖掘產(chǎn)品之間的關聯(lián)性，從中發(fā)現(xiàn)產(chǎn)品銷售中預期不到的模式智慧交通數(shù)據(jù)挖掘應用場景電子地圖導航應用。將用戶出行數(shù)據(jù)進行分析，從而可以預測不同城市之間的人口遷移情況，或者某個城市內(nèi)群體出行的態(tài)勢金融行業(yè)數(shù)據(jù)挖掘應用場景金融行業(yè)是一個數(shù)據(jù)挖掘應用凸顯經(jīng)濟價值的領域，數(shù)據(jù)挖掘的應用能幫助金融行業(yè)突破其傳統(tǒng)模式的弊端醫(yī)療行業(yè)數(shù)據(jù)挖掘應用場景預測建模新藥物研發(fā)階段的醫(yī)藥公司，通過數(shù)據(jù)建模、分析，找到最有效的投入產(chǎn)出比例，使資源獲得最佳組合農(nóng)業(yè)數(shù)據(jù)挖掘應用場景數(shù)據(jù)挖掘時代，農(nóng)民也在使用移動設備管理農(nóng)場，以方便掌握實時的土壤、溫度、作物狀況等信息，提高了農(nóng)場管理的精確性氣象數(shù)據(jù)挖掘應用場景通過對氣象數(shù)據(jù)挖掘，天氣預報的準確性、時效性都有了極大的提高，同時對重大自然災害的預警及精確掌握了解危害等級等等，這些都能幫助人們最大限度的減少自然災害帶來的危害第1章數(shù)據(jù)挖掘概念習題1.2數(shù)據(jù)探索1.3數(shù)據(jù)挖掘的應用大數(shù)據(jù)應用人才培養(yǎng)系列教材1.1數(shù)據(jù)挖掘概述習題：下例每項活動是否是數(shù)據(jù)挖掘任務？1．根據(jù)性別劃分公司的顧客。2．根據(jù)可盈利性劃分公司的顧客。3．計算公司的總銷售額。4．按學生的標識號對學生數(shù)據(jù)庫排序。5．預測擲一對骰子的結果。6．使用歷史記錄預測某公司未來的股價價格。第二章分類2.1分類概述2.2貝葉斯決策與分類器2.3支持向量機2.4分類在實際場景中的應用案例作業(yè)與練習大數(shù)據(jù)應用人才培養(yǎng)系列教材2.1分類概述第二章分類2.1.1分類基本概念定義：分類是一種重要的數(shù)據(jù)分析形式。根據(jù)重要數(shù)據(jù)類的特征向量值及其他約束條件，建立分類函數(shù)或分類模型。分類模型可以用于描述性建模和預測性建模。2.1分類概述第二章分類2.1.2解決分類問題的一般方法分類法是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。它包括決策樹分類法、基于規(guī)則的分類法、支持向量機分類法、樸素貝葉斯分類法、神經(jīng)網(wǎng)絡等分類法。解決分類問題的一般方法。第一步，建立一個模型。這需要有一個訓練樣本數(shù)據(jù)集作為預先的數(shù)據(jù)集或概念集，通過分析屬性/特征描述等構成的樣本（也可以是實體等）建立模型。2.1分類概述第二章分類2.1.2解決分類問題的一般方法2.1分類概述第二章分類2.1.2解決分類問題的一般方法應用模2.1分類概述第二章分類2.1.3決策樹1.決策樹工作原理通過提出一系列精心構思的關于檢驗記錄屬性的問題，解決分類問題。類問題的決策樹，樹中包含三種節(jié)點：*根節(jié)點沒有進邊，有0條或更多條出邊；*內(nèi)部節(jié)點有一條進邊，有2條或更多條出邊；*葉節(jié)點有一條進邊，沒有出邊。2.1分類概述第二章分類2.1.3決策樹2.1分類概述第二章分類2.1.3決策樹2.如何建立決策樹3.決策樹歸納算法算法2.1給出了稱作Treegrowth的決策樹歸納算法的框架。該算法的輸入是訓練記錄集A和屬性集B。算法遞歸地選擇最優(yōu)的屬性來劃分數(shù)據(jù)（步驟7），并擴展樹的葉節(jié)點（步驟11和步驟12），直到滿足結束條件（步驟1）。2.1分類概述第二章分類2.1.3決策樹3.決策樹歸納算法2.1分類概述第二章分類2.1.3決策樹4.決策樹歸納的學習算法必須解決兩個問題（1）訓練記錄分裂（2）停止分裂過程案例:Web機器人檢測2.1分類概述第二章分類2.1.3決策樹5.決策樹歸納的特點（1）決策樹歸納是不用假設類和其它屬性服從某一分布概率，是一種構建分類模型的非參數(shù)方法。（2）找到最佳的決策樹即決策樹獲得的不是全局最優(yōu)，是每個結點的局部最優(yōu)決策。（3）決策樹建立后，未知樣本分類很快。而已開發(fā)構建的決策樹技術計算成本不高，就算訓練集很大，也能快速建立模型。（4）決策樹相對其它分類算法更簡便，特別是小型的決策樹的準確率較高。冗余屬性不會對決策樹的準確率造成不利的影響。（5）決策樹算法對于噪聲干擾有較強的抗干擾性。（6）決策樹算法通常采用自頂向下的遞歸劃分方法，解決該問題通常是采用樣本數(shù)小于某個特定閾值時停止分裂。2.1分類概述第二章分類2.1.4模型的過分擬合1.模型過分擬合的形成所謂模型過分擬合是指訓練數(shù)據(jù)擬合度過高的模型。2.處理決策樹歸納中的過分擬合在這介紹兩種決策樹歸納上避免過分擬合的策略：（1）先剪枝（提前終止）（2）后剪枝（過程修剪）第二章分類2.1分類概述2.2貝葉斯決策與分類器2.3支持向量機2.4分類在實際場景中的應用案例作業(yè)與練習大數(shù)據(jù)應用人才培養(yǎng)系列教材2.2貝葉斯決策與分類器第二章分類2.2.1規(guī)則分類器基于規(guī)則的分類器是使用一組“if…then…”規(guī)則來對記錄進行分類的技術?；谝?guī)則的分類器產(chǎn)生的規(guī)則集有兩個重要性質：1.互斥性

如果規(guī)則集中不存在兩條規(guī)則被同一條記錄觸發(fā)，則稱規(guī)則集中的規(guī)則是互斥的。2.窮舉性

如果屬性值任一種組合，規(guī)則集中都存在一條規(guī)則加以覆蓋，則稱規(guī)則集具有窮舉覆蓋。它確保每一條記錄都至少被規(guī)則集里的一條規(guī)則覆蓋。2.2貝葉斯決策與分類器第二章分類2.2.1規(guī)則分類器r1:（胎生=否）∧（飛行動物=是）

鳥類r2:（胎生=否）∧（水生動物=是）

魚類r3:（胎生=是）∧（體溫=恒溫）

哺乳動物r4:（胎生=否）∧（飛行動物=否）

爬行類r5:（水生動物=半）兩棲類2.2貝葉斯決策與分類器第二章分類2.2.2分類中貝葉斯定理的應用假設Ｘ，Ｙ是一對隨機變量，聯(lián)合概率P（Ｘ=x,Ｙ=y）是指Ｘ取值x且Ｙ取值y的概率，條件概率是指一隨機變量在另一隨機變量取值已知的情況下取某一特定值得概率。2.2貝葉斯決策與分類器第二章分類2.2.2分類中貝葉斯定理的應用2.貝葉斯定理在分類中的應用先從統(tǒng)計學的角度對分類問題加以形式化。設Ｘ表示屬性集，Ｙ表示類變量。如果類變量和屬性之間的關系不確定，可以把Ｘ和Ｙ看作隨機變量，用Ｐ(Ｙ|Ｘ)以概率的方式捕捉二者之間的關系，這個條件概率又稱為Ｙ的后驗概率，對應Ｐ(Y)稱為Ｙ的先驗概率。在訓練階段，要根據(jù)從訓練數(shù)據(jù)中收集的信息，對Ｘ和Ｙ的每一種組合學習后驗概率Ｐ(Ｙ|Ｘ)。知道這些概率后，通過找出使后驗概率Ｐ(Ｙ|Ｘ)最大的類Ｙ可以對測試記錄Ｘ進行分類。2.2貝葉斯決策與分類器第二章分類2.2.2分類中貝葉斯定理的應用2.2貝葉斯決策與分類器第二章分類2.2.3分類中樸素貝葉斯的應用1.條件獨立性在研究樸素貝葉斯分類法如何工作之前，先介紹條件獨立概念。設Ｘ,Ｙ和Ｚ表示三個隨機變量的集合。給定Ｚ，Ｘ條件獨立于Ｙ，如果下面的條件成立：2.樸素貝葉斯分類器如何工作分類測試記錄時，樸素貝葉斯分類器對每個類Ｙ計算后驗概率：2.2貝葉斯決策與分類器第二章分類2.2.3分類中樸素貝葉斯的應用3.樸素貝葉斯分類器特征1）在面對孤立的噪聲點，樸素貝葉斯分類器性能影響不大；2）面對無關屬性，樸素貝葉斯分類器性能同樣影響不大；3）相關屬性可能降低樸素貝葉斯分類器的性能。樸素貝葉斯分類法使用兩種方法估計連續(xù)屬性的類條件概率。（1）可以把每一個連續(xù)的屬性離散化，然后用相應的離散區(qū)間替換連續(xù)屬性值。（2）可以假設連續(xù)變量服從某種概率記錄，然后使用訓練數(shù)據(jù)估計分布的參數(shù)。第二章分類2.1分類概述2.3支持向量機2.2貝葉斯決策與分類器2.4分類在實際場景中的應用案例作業(yè)與練習大數(shù)據(jù)應用人才培養(yǎng)系列教材2.3支持向量機第二章分類2.3.1最大邊緣超平面支持向量機（SupportVectorMachine），以下簡稱SVM，成為最主要的模式識別方法之一，它可以在高維空間構造良好的預測模型，在OCR、語言識別、圖像識別等廣泛應用。它以扎實的統(tǒng)計學理論為基礎，并在許多實際應用（如手寫數(shù)字的識別、文本分類等）中展示了不俗的實踐效果。一個數(shù)據(jù)集，包含兩個不同類的樣本，分別用小黑加號塊和小圓圈表示。數(shù)據(jù)集是線性可分的，即能找到一個超平面，使得所有小黑方塊位于這個超平面的一側，所有小圓圈在它的另一側。如圖所示，可看到這種超平面可能存在無窮多個。通過檢驗樣本運行效果，分類器要從這些超平面中選一個作為它的決策邊界。2.3支持向量機第二章分類2.3.1最大邊緣超平面SVM最基本的任務就是在分開數(shù)據(jù)超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化，平行超平面間的距離或差距越大，分類器的總誤差越小。分類的過程是一個機器學習的過程。設樣本屬于兩個類，用該樣本訓練SVM得到的最大間隔超平面。在超平面上的樣本點也稱為支持向量。2.3支持向量機第二章分類2.3.2線性支持向量機SVMSVM算法是從線性可分情況的最優(yōu)分類超平面提出的。最優(yōu)分類面是指要求分類超平面不但能將兩類樣本點無錯誤地分開，而且要使兩類的分類空隙最大。2.3支持向量機第二章分類2.3.2非線性支持向量機SVMSVM應用到具有非線性決策邊界數(shù)據(jù)集上的方法，關鍵是在于將數(shù)據(jù)從原先的坐標空間x變換到一個新的坐標空間?（x）中，然后在新的坐標空間中使用一個線性的決策邊界劃分樣本。1.屬性變換2.非線性支持向量機3.核函數(shù)4.支持向量機的一般特征（1）SVM學習問題可表示為凸優(yōu)化問題，利用已知的有效算法發(fā)現(xiàn)目標函數(shù)的全局最小值。（2）SVM通過最大化決策邊界的邊緣來控制模型。（3）通過對數(shù)據(jù)中每個分類屬性值引入一個啞變量，SVM可應用于分類數(shù)據(jù)。第二章分類2.1分類概述2.2貝葉斯決策與分類器2.4分類在實際場景中的應用案例2.3支持向量機作業(yè)與練習大數(shù)據(jù)應用人才培養(yǎng)系列教材2.4分類在實際場景中的應用案例第二章分類1案例：如何解決文章主題關鍵字與搜索引擎關鍵字帶來的檢索結果差異2案例：甄別新金融交易方式的欺詐行為3案例：在線廣告推薦中的分類2.4分類在實際場景中的應用案例2.4分類在實際場景中的應用案例第二章分類1案例：如何解決文章主題關鍵字與搜索引擎關鍵字帶來的檢索結果差異在網(wǎng)頁學術性判定方面,提出了基于貝葉斯算法的網(wǎng)頁學術性判斷算法,通過對網(wǎng)頁內(nèi)容、格式、結構三個維度的分析,完成網(wǎng)頁學術性的判定;在分類方面,以中圖法的分類大綱作為分類目錄,提出了基于改進空間向量模型的學術網(wǎng)頁分類算法,通過利用網(wǎng)頁主題關鍵字構建網(wǎng)頁向量空間,最后實現(xiàn)了網(wǎng)頁的正確分類。通過兩個關鍵算法,在系統(tǒng)中的網(wǎng)頁主題提取部分,采用HtmlParser技術與正則表達式相結合的網(wǎng)頁主題提取算法,實現(xiàn)對抓取的網(wǎng)頁主題內(nèi)容的獲取。2.4分類在實際場景中的應用案例第二章分類2案例：甄別新金融交易方式的欺詐行為中國工商銀行建立基于大數(shù)據(jù)技術金融交易反欺詐系統(tǒng)，針對欺詐的不同場景，給系統(tǒng)采取不同的分析維度，在海量的基礎數(shù)據(jù)池中，通過對客戶、產(chǎn)品、商戶、渠道等多維度，提煉出近1000個指標、3000多個特征量。讓金融交易行為的流程數(shù)據(jù)化，構建智能模型，為精準打擊欺詐交易奠定基礎。在對每個客戶的歷史交易的行為數(shù)據(jù)，提煉近3000多的風險特征，結合運用決策樹、支持向量機、邏輯回歸、神經(jīng)網(wǎng)絡等方法，構建出不同的欺詐識別模型、識別最新欺詐模型。如圖反欺詐模型2013年12月5日，某客戶的萬事達卡短短15分鐘內(nèi)，在美國沃爾瑪超市內(nèi)發(fā)生非密碼驗證的POS刷卡交易14筆，累計交易金額10250美元。交易金額大、交易頻繁等于客戶日常行為習慣不符，14筆交易被系統(tǒng)攔截，后經(jīng)核實發(fā)現(xiàn)這14筆交易系嫌疑人盜刷，不是客戶本人消費。2.4分類在實際場景中的應用案例第二章分類3案例：在線廣告推薦中的分類推薦系統(tǒng)具有用戶需求驅動、主動服務和信息個性化程度高等優(yōu)點，可有效解決信息過載問題。它研究大量借鑒了認知科學、近似理論、信息檢索、預測理論、管理科學及市場建模等多個領域的知識，且已經(jīng)成為數(shù)據(jù)挖掘、機器學習和人機接口領域的熱門研究方向。推薦系統(tǒng)的工作原理與一般信息過濾系統(tǒng)比較類似，可以一種特殊形式的信息過濾系統(tǒng)推薦系統(tǒng)可以分為兩種：一種是獨立為信息服務系統(tǒng)，另一種是作為宿主信息服務系統(tǒng)的推薦子系統(tǒng)輔助信息、服務系統(tǒng)。第2章分類2.1分類概述2.2貝葉斯決策與分類器2.3支持向量機2.4分類在實際場景中的應用案例作業(yè)與練習大數(shù)據(jù)應用人才培養(yǎng)系列教材作業(yè)與練習：第三章聚類3.1聚類概述3.2

聚合分析方法3.3

聚類在實際場景中的應用案例3.4

聚類的實現(xiàn)例子習題大數(shù)據(jù)應用人才培養(yǎng)系列教材3.1聚類概述3.1聚類概述第三章聚類聚類的過程把相似數(shù)據(jù)歸并到一類的過程，形成同類對象具有共同特征,不同類對象之間的有顯著區(qū)別，直到所有數(shù)據(jù)的歸類都完成。特征性描述:對象的共同特征區(qū)別性描述:不同類對象之間的區(qū)別概念描述:特征性描述和區(qū)別性描述3.1聚類概述第三章聚類聚類的目的通過數(shù)據(jù)間的相似性把數(shù)據(jù)歸類，并根據(jù)數(shù)據(jù)的概念描述，來制定對應的策略。電商例子在電子商務領域，電商可以對有相似瀏覽行為的客戶進行歸類，從而找出他們的共同特征，達到充分理解客戶需求的目的，并提供相適應的客戶服務。3.1聚類概述第三章聚類聚類技術主要包括傳統(tǒng)的模式識別方法和數(shù)學分類學聚類的評價標準PurityRI3.1聚類概述第三章聚類PurityΩ={ω?,ω?,...,ωk}是聚類(cluster)的集合，ωk表示第k個聚類的集合；C={c?,c?,...,cj}是數(shù)據(jù)對象類型(class)的集合，cj表示第j個數(shù)據(jù)對象類型集；

N表示數(shù)據(jù)對象總數(shù)。3.1聚類概述第三章聚類Purity例子對象類型(class)包括x,o,□N=17purity=(5+4+3)/N=12/17≈0.71purity是簡單透明的方法，它的取值在0—1之間，數(shù)值越大，表示聚類效果越好。3.1聚類概述第三章聚類RITP：計算每個聚類中同類對象歸類到同一類的組合次數(shù)，并累計所有的結果TN：計算每個不同類對象歸類到不同類的組合次數(shù)，并累計所有的結果FP：計算每個聚類中不同類對象歸類到同一類的組合次數(shù)，并累計所有的結果FN：計算每個同類對象歸類到不同類的組合次數(shù)，并累計所有的結果3.1聚類概述第三章聚類RI例子C(n,m)=在m中任選n個的組合數(shù)Cluster1：TP=C(2,5)=10Cluster2：TP=C(2,4)=6Cluster3：TP=C(2,3)+C(2,2)=4TP=10+6+4=20TP+FP=C(2,6)+C(2,6)+C(2,5)=15+15+10=40FP=TP+FP-TP=20x：FN=5+5+5+2=15o：FN=4□：FN=3FN=15+4+3=24TN+FN=C(1,6)*C(1,6)+C(1,6)*C(1,5)+C(1,6)*C(1,5)=36+30+30=96TN=TN+FN-FN=96-24=72RI=（TP+TN）/（TP+FP+FN+TN）=（20+72）/（40+96）=92/136≈0.683.1聚類概述第三章聚類聚類算法層次聚類算法（HierarchicalMethods）劃分聚類算法（PartitioningMethods）基于密度的聚類算法（Density-basedMethods）基于網(wǎng)格的聚類算法（Grid-basedMethods）基于模型的聚類算法（Model-BasedMethods）3.1聚類概述第三章聚類層次聚類算法對給定的數(shù)據(jù)集進行層次似的分解，直到某種條件滿足為止。通過計算各個對象的相似性，并把相似對象合在一起，由同一的父類代表他們，由此構成一棵樹，父類為根節(jié)點,其所代表的對象即構成樹的子節(jié)點。從樹的構造順序劃分，有自底而上、自頂而下兩種方式。前者對應的是聚合聚類，后者對應的是分裂聚類。3.1聚類概述第三章聚類劃分聚類先預設劃分的分類數(shù)K，將給定的數(shù)據(jù)劃分成K個非空集合即簇，然后通過調(diào)整每個數(shù)據(jù)在各簇的分布，使得每個簇的相似度得到進一步提高，而簇之間的相異度加大。不斷重復這個過程即迭代，直到每個簇不再改變。3.1聚類概述第三章聚類劃分聚類代表算法:K-means第三章聚類3.1聚類概述3.2

聚合分析方法3.3

聚類在實際場景中的應用案例3.4

聚類的實現(xiàn)例子習題大數(shù)據(jù)應用人才培養(yǎng)系列教材3.1

聚類概述3.2聚合分析方法第三章聚類聚合分析過程聚合分析方法是層次聚類的常用方法，其聚合過程是自底而上的過程。它把所有數(shù)據(jù)樣本分別看作獨立的簇；計算簇的相似度，即簇之間的距離。距離最小的即相似度最高。把相似度最高的簇合并成一個簇，并再與剩余的其它簇重新聚合。如此重復迭代以上聚合過程，直到所有數(shù)據(jù)樣本合并為一個簇。在聚類分析中，需要確定數(shù)據(jù)樣本間的相似程度，這個相似度稱為數(shù)據(jù)樣本間的距離。計算距離的方法包括歐氏距離、曼哈頓距離、閔可夫斯基距離、切比雪夫距離等。本章重點介紹常用的歐氏距離方法。3.2聚合分析方法第三章聚類歐氏距離在一個p維空間中，任一點Xi表示為（Xi1,Xi2,…,Xip）,它與另一點Xj的歐氏距離d(Xi,Xj)可按如下方法計算：d(Xi,Xj)=例子：X1=（6，3），X2=（3，7）d(X1,X2)===53.2聚合分析方法第三章聚類聚合分析例子原始數(shù)據(jù)A=（6，3）B=（3，7）C=（12，6）第1次計算相似度歐氏

距離

ABCA0.005.006.71B

0.009.06C

0.00得到A,B最相似；把A，B合并為一簇，并與剩余的C聚合合并簇的值：這里為簡易說明，采用簇的質心的方法，即簇的均值作為合并簇的值的方法3.2聚合分析方法第三章聚類聚合分析例子A,B簇的質心：(A+B)/2=(4.5,5)(A,B)質心A63B37(A,B)4.55第2次計算相似度歐氏

距離

A,BCA,B0.007.57C

0.00得到(A,B),C最相似把(A,B),C合并為一簇。3.2聚合分析方法第三章聚類聚合分析例子1((A,B),C)簇的質心：((A,B)+C)/2=()((A,B),C)質心第3次計算相似度歐氏

距離所有的數(shù)據(jù)點都合并完。聚合過程完成。A,B4.55C126(A,B),C8.255.5

(A,B),C(A,B),C0.003.2聚合分析方法第三章聚類聚類樹將前面的每一步的計算結果以樹狀圖的形式展現(xiàn)出來就是層次聚類樹。最底層是原始數(shù)據(jù)點。依照數(shù)據(jù)點間的相似度組合為聚類樹的第二層。以此類推生成完整的層次聚類樹樹狀圖。3.2聚合分析方法第三章聚類聚合分析方法應用例子A19.7

B21.420.620.6

C24.924.9

D27.527.526.223.4

E63.363.363.363.343.3原始數(shù)據(jù)聚合數(shù)據(jù)第1列是原始數(shù)據(jù)，后面列是聚合過程數(shù)據(jù)，其中以質心作合并簇值。在區(qū)隔程度閥值T=3時，可以得到3個簇類（Ａ，Ｂ），（Ｃ，Ｄ），Ｅ3.2聚合分析方法第三章聚類聚合分析方法應用例子聚合過程對應的層次聚類樹如下：實際上，這里Ａ、Ｂ、Ｃ、Ｄ、Ｅ的數(shù)值分別表示首爾、香港、北京、上海、東京的ＧＤＰ值。以３（即３千億）作為區(qū)分標準。通過上面描述的聚合過程，可以把亞洲這５個最發(fā)達城市劃分成以下３個方陣：第一方陣：東京第二方陣：上海，北京第三方陣：香港，首爾第三章聚類3.1聚類概述3.2

聚合分析方法3.3

聚類在實際場景中的應用案例3.4

聚類的實現(xiàn)例子習題大數(shù)據(jù)應用人才培養(yǎng)系列教材3.1

聚類概述3.3聚類在實際場景中的應用案例第三章聚類聚類分析在電網(wǎng)運行中，可以大幅度提高電網(wǎng)業(yè)務的安全運行水平。聚類分析在電力用戶用電行為分析中，可以大幅度提高售電策略的準確性。聚類分析在電商的應用3.3聚類在實際場景中的應用案例第三章聚類聚類分析在電網(wǎng)運行中，可以大幅度提高電網(wǎng)業(yè)務的安全運行水平。通過對電網(wǎng)、調(diào)度網(wǎng)等重要生產(chǎn)業(yè)務的歷史故障和缺陷情況進行故障概率聚類分析，發(fā)掘故障因素關聯(lián)性、共性規(guī)律，從而制定相應的防范對策和措施，在故障和缺陷發(fā)生之前進行預防式防護，達到大幅提升電網(wǎng)運行可靠性的目的。3.3聚類在實際場景中的應用案例第三章聚類聚類分析在電力用戶用電行為分析中，可以大幅度提高售電策略的準確性。通過對電力用戶用電規(guī)模、用電模式作聚類分析，就能把用戶劃分成不同的類別，并分別制定相應的售電策略、風險防范策略電力公司通過客戶價值細分模型，對客戶基本信息、用電負荷、違章歷史等方面的用電行為特征進行聚類分析，把多個用戶的用電方式通過聚類分析形成用電屬性相似的行業(yè)群體，根據(jù)客戶對電力公司的貢獻度、用電變化趨勢、風險程度等情況，將客戶細分為多種類別，推進客戶細分管理、欠費和用電風險有效預測、配用電錯峰調(diào)度，實現(xiàn)個性化營銷和服務，促進服務質量和防范風險能力的不斷提升。3.3聚類在實際場景中的應用案例第三章聚類聚類分析在電商的應用電商把交易信息包括消費者購買時間、購買商品、購買數(shù)量、支付金額、性別、年齡、地域分布、關聯(lián)收藏等進行聚類分析，可以了解客戶的消費習慣，制定對應的商品營銷推廣活動，提高成交轉化率和成交率。第三章聚類3.1聚類概述3.2

聚合分析方法3.3

聚類在實際場景中的應用案例3.4

聚類的實現(xiàn)例子習題大數(shù)據(jù)應用人才培養(yǎng)系列教材3.1

聚類概述3.4聚類的實現(xiàn)例子第三章聚類通過例子展示K-means聚類的實現(xiàn)圖3-10大數(shù)據(jù)集群節(jié)點3.4聚類的實現(xiàn)例子第三章聚類圖3-11hadoop集群的基本信息3.4聚類的實現(xiàn)例子第三章聚類圖3-12datanode的基本信息3.4聚類的實現(xiàn)例子第三章聚類選取3維數(shù)據(jù)組，共6個數(shù)據(jù)，如下：0.00.00.00.10.10.10.20.20.29.09.09.09.19.19.19.29.29.2聚類的目標是把原始數(shù)據(jù)分成2類，并找出每一類的質心。3.4聚類的實現(xiàn)例子第三章聚類創(chuàng)建hadoop工作目錄/34/in[root@slave1hadoop]#bin/hadoopfs-mkdir-p/34/in把需要聚類的數(shù)據(jù)文件kmeans_data.txt裝進hadoop的HDFS分布式文件系統(tǒng)中[root@slave1hadoop]#bin/hdfsdfs-put/usr/cstor/spark/data/mllib/kmeans_data.txt/34/in[root@slave1hadoop]#bin/hadoopfs-cat/34/in/kmeans_data.txt

進入spark-shell接口scala[root@slave1spark]#bin/spark-shell--masterspark://master:7077

運行K-meansspark算法3.4聚類的實現(xiàn)例子第三章聚類實施方法過程如下：從本地連接slave1:[c:\~]$ssh4Connectingto4:22...Connectionestablished.Toescapetolocalshell,press'Ctrl+Alt+]'.查看hadoop工作目錄[root@slave1~]#cd/usr/cstor/hadoop[root@slave1hadoop]#ls-ltotal28-rw-r--r--1100211002115429May1616:35LICENSE.txt-rw-r--r--11002110021101May1616:35NOTICE.txt-rw-r--r--110021100211366May1616:35README.txtdrwxr-xr-x21002110021194Jun292015bindrwxr-xr-x4rootroot37May1616:36clouddrwxr-xr-x3100211002120Jun292015etc。。。設置JAVA_HOME路徑[root@slave1~]#exportJAVA_HOME=/usr/local/jdk1.7.0_793.4聚類的實現(xiàn)例子第三章聚類導入所需的包:scala>importbreeze.linalg.{Vector,DenseVector,squaredDistance}importbreeze.linalg.{Vector,DenseVector,squaredDistance}

scala>importorg.apache.spark.{SparkConf,SparkContext}importorg.apache.spark.{SparkConf,SparkContext}

scala>importorg.apache.spark.SparkContext._importorg.apache.spark.SparkContext._3.4聚類的實現(xiàn)例子第三章聚類定義分析方法和計算最短距離點的方法(method):scala>defparseVector(line:String):Vector[Double]={|DenseVector(line.split('').map(_.toDouble))|}parseVector:(line:String)breeze.linalg.Vector[Double]

scala>defclosestPoint(p:Vector[Double],centers:Array[Vector[Double]]):Int={|varbestIndex=0|varclosest=Double.PositiveInfinity|for(i<-0untilcenters.length){|valtempDist=squaredDistance(p,centers(i))|if(tempDist<closest){|closest=tempDist|bestIndex=i|}|}|bestIndex|}closestPoint:(p:breeze.linalg.Vector[Double],centers:Array[breeze.linalg.Vector[Double]])Int3.4聚類的實現(xiàn)例子第三章聚類裝入并讀取挖掘數(shù)據(jù)文件：scala>vallines=sc.textFile("/34/in/kmeans_data.txt")17/05/1706:14:50INFOstorage.MemoryStore:Blockbroadcast_0storedasvaluesinmemory(estimatedsize86.5KB,free86.5KB)17/05/1706:14:50INFOstorage.MemoryStore:Blockbroadcast_0_piece0storedasbytesinmemory(estimatedsize19.4KB,free105.9KB)17/05/1706:14:50INFOstorage.BlockManagerInfo:Addedbroadcast_0_piece0inmemoryon4:42657(size:19.4KB,free:511.5MB)17/05/1706:14:50INFOspark.SparkContext:Createdbroadcast0fromtextFileat<console>:32lines:org.apache.spark.rdd.RDD[String]=MapPartitionsRDD[1]attextFileat<console>:32

scala>valdata=lines.map(parseVector_).cache()data:org.apache.spark.rdd.RDD[breeze.linalg.Vector[Double]]=MapPartitionsRDD[2]atmapat<console>:363.4聚類的實現(xiàn)例子第三章聚類定義K的數(shù)目：scala>valK="2".toIntK:Int=2

scala>valconvergeDist="0.1".toDoubleconvergeDist:Double=0.1初始化K個簇：scala>valkPoints=data.takeSample(withReplacement=false,K,42).toArraykPoints:Array[breeze.linalg.Vector[Double]]=Array(DenseVector(0.1,0.1,0.1),DenseVector(9.2,9.2,9.2))3.4聚類的實現(xiàn)例子第三章聚類計算每個點的距離并調(diào)整簇，直到K個簇不再有變動，得到挖掘結果：scala>vartempDist=1.0tempDist:Double=1.0scala>while(tempDist>convergeDist){|valclosest=data.map(p=>(closestPoint(p,kPoints),(p,1)))|valpointStats=closest.reduceByKey{case((p1,c1),(p2,c2))=>(p1+p2,c1+c2)}|valnewPoints=pointStats.map{pair=>|(pair._1,pair._2._1*(1.0/pair._2._2))}.collectAsMap()|tempDist=0.0|for(i<-0untilK){|tempDist+=squaredDistance(kPoints(i),newPoints(i))|}|for(newP<-newPoints){|kPoints(newP._1)=newP._2|}|println("Finishediteration(delta="+tempDist+")")|}3.4聚類的實現(xiàn)例子第三章聚類結果展示scala>kPoints.foreach(println)DenseVector(0.1,0.1,0.1)DenseVector(9.099999999999998,9.099999999999998,9.099999999999998)1.請說明聚類的過程。2.請說明2種聚類方法的評價標準。3.請列出3種以上聚類算法。4.K-means算法是層次聚類，還是劃分聚類？請說明其算法流程。5.請舉例并畫出一顆層次聚類樹，并說明其作用。6.請舉例說明歐氏距離（EuclideanDistance）的計算過程。習題：第四章關聯(lián)規(guī)則4.1關聯(lián)規(guī)則的基本概念4.2關聯(lián)規(guī)則的挖掘過程4.3關聯(lián)規(guī)則的Apriori算法4.4關聯(lián)規(guī)則的FP-Growth算法習題大數(shù)據(jù)應用人才培養(yǎng)系列教材4.1關聯(lián)規(guī)則的基本概念第四章關聯(lián)規(guī)則關聯(lián)規(guī)則概念最早是由Agrawal等人在1993年首先提出的，最初的動機是針對購物籃分析問題提出的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品之間的聯(lián)系規(guī)則。Agrawal等人于1993年提出了關聯(lián)規(guī)則挖掘算法AIS，但是性能較差。1994年，他們建立了項目集格空間理論，并提出了著名的Apriori算法，至今Apriori仍然作為關聯(lián)規(guī)則挖掘的經(jīng)典算法被廣泛討論，以后諸多的研究人員對關聯(lián)規(guī)則的挖掘問題進行了大量的研究。4.1關聯(lián)規(guī)則的基本概念第四章關聯(lián)規(guī)則More應用市場：市場貨籃分析、交叉銷售（CrossingSale）、部分分類（PartialClassification）、金融服務（FinancialService），以及通信、互聯(lián)網(wǎng)、電子商務······4.1關聯(lián)規(guī)則的基本概念第四章關聯(lián)規(guī)則4.1.1基本概念1）項（Item）、項集（Itemset）、k-項集與事務項：是指數(shù)據(jù)庫中不可分割的最小單位。項集：是指多個項的集合，其中，空集是指不包含任何項的項集。k-項集：是指由k個項構成的項集組合。事務：是指用戶定義的一個數(shù)據(jù)庫操作序列，這些操作序列是一個不可分割的工作單位。2）頻繁項集（FrequentItemset）頻繁項集：是指在所有訓練元組中同時出現(xiàn)的次數(shù)，超過人工定義的閾值的項集。在關聯(lián)規(guī)則的挖掘過程中，一般只保留候選項集中滿足支持度條件的項集，不滿足條件的舍棄。4.1關聯(lián)規(guī)則的基本概念第四章關聯(lián)規(guī)則4.1.1基本概念3）極大頻繁項集（FrequentLargeItemset）極大頻繁項集：不存在包含當前頻繁項集的頻繁超集，則當前頻繁項集就是極大頻繁項集。4）支持度（Support）支持度：是指項集在所有訓練元組中同時出現(xiàn)的次數(shù)，因此，支持度可以表述為Support(X->Y)=|XUY|/|N|。其中，X，YN，X∩Y=Ф，|XUY|表示集合X與Y在一個事務中同時出現(xiàn)的次數(shù)，|N|表示數(shù)據(jù)記錄的總個數(shù)。5）置信度（Confidence）置信度可以表述為：Confidence(X->Y)=|XUY|/|X|=Support(X->Y)/Support（X），其中，X，YN，X∩Y=Ф，|XUY|表示集合X與Y在一個事務中同時出現(xiàn)的次數(shù)，|X|表示X出現(xiàn)的總次數(shù)。4.1關聯(lián)規(guī)則的基本概念第四章關聯(lián)規(guī)則4.1.2關聯(lián)規(guī)則定義關聯(lián)規(guī)則（Associationrule）：指從事務數(shù)據(jù)庫、關系數(shù)據(jù)庫和其他信息存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關聯(lián)和相關性。關聯(lián)分析（Associationanalysis）：用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集中的令人感興趣的聯(lián)系。所發(fā)現(xiàn)的聯(lián)系可以用關聯(lián)規(guī)則或者頻繁項集的形式表示。關聯(lián)規(guī)則挖掘就是從大量的數(shù)據(jù)中挖掘出描述數(shù)據(jù)項之間相互聯(lián)系的有價值的有關知識。4.1關聯(lián)規(guī)則的基本概念第四章關聯(lián)規(guī)則4.1.2關聯(lián)規(guī)則定義一般地，關聯(lián)規(guī)則挖掘問題可以劃分成兩個子問題：1）發(fā)現(xiàn)頻繁項目集通過用戶給定的Minsupport，尋找所有頻繁項目集，即滿足Support不小于Minsupport的項目集。事實上，這些頻繁項目集可能具有包含關系。一般地，我們只關心那些不被其它頻繁項目集所包含的所謂頻繁大項集的集合。這些頻繁大項集是形成關聯(lián)規(guī)則基礎。2）生成關聯(lián)規(guī)則通過用戶給定的Minconfidence，在每個最大頻繁項目項目集中，尋找Confidence不小于Minconfidence的關聯(lián)規(guī)則。這兩個子問題主要在4.3節(jié)中進行介紹。4.1關聯(lián)規(guī)則的基本概念第四章關聯(lián)規(guī)則4.1.3關聯(lián)規(guī)則分類1）基于規(guī)則中處理的變量的類別，關聯(lián)規(guī)則可以分為布爾型和數(shù)值型。

2）基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關聯(lián)規(guī)則和多層關聯(lián)規(guī)則。3）基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關聯(lián)規(guī)則可以分為單維的和多維的。第四章關聯(lián)規(guī)則4.2關聯(lián)規(guī)則的挖掘過程4.1關聯(lián)規(guī)則的基本概念4.3關聯(lián)規(guī)則的Apriori算法4.4關聯(lián)規(guī)則的FP-Growth算法習題大數(shù)據(jù)應用人才培養(yǎng)系列教材4.2關聯(lián)規(guī)則的挖掘過程第四章關聯(lián)規(guī)則4.2.1頻繁項集產(chǎn)生格結構（LatticeStructure）常常被用來枚舉所有可能的項集。圖1項集的格4.2關聯(lián)規(guī)則的挖掘過程第四章關聯(lián)規(guī)則4.2.2頻繁項集的產(chǎn)生及其經(jīng)典算法查找頻繁項目集經(jīng)典的查找策略基于精簡集的查找策略基于最大頻繁項集的查找策略按照挖掘的策略不同經(jīng)典的挖掘完全頻繁項集方法基于廣度優(yōu)先搜索策略的關聯(lián)規(guī)則算法基于深度優(yōu)先搜索策略的算法Apriori算法、DHP算法FP-Growth算法、ECLAT算法COFI算法與經(jīng)典查找不同方法基于精簡集的方法基于最大頻繁項目集的方法A-close算法MAFIA算法、GenMax算法DepthProject算法格結構（LatticeStructure）常常被用來枚舉所有可能的項集。4.2關聯(lián)規(guī)則的挖掘過程第四章關聯(lián)規(guī)則4.2.3強關聯(lián)規(guī)則生成關聯(lián)規(guī)則是指通過用戶給定的最小可信度，在每個最大頻繁項集中，尋找可信度不小于Minconfidence的關聯(lián)規(guī)則。得到頻繁項目集之后，則需要從頻繁項目集中找出符合條件的關聯(lián)規(guī)則。最簡單的辦法是：遍歷所有的頻繁項目集，然后從每個項目集中依次取1、2、...k個元素作為后件，該項目集中的其他元素作為前件，計算該規(guī)則的置信度進行篩選即可。這樣的窮舉效率顯然很低。假如對于一個頻繁項目集f，可以生成下面這樣的關聯(lián)規(guī)則：（f-β）->β4.2關聯(lián)規(guī)則的挖掘過程第四章關聯(lián)規(guī)則4.2.4關聯(lián)規(guī)則評價標準在某些特定情況下，僅憑支持度和置信度來衡量一條規(guī)則，是完全不夠的，對于數(shù)據(jù)的篩選力度也不足。因此，需要介紹更多的判斷強關聯(lián)規(guī)則的評價標準，來滿足實際需求。支持度和置信度并不能過成功濾掉那些我們不感興趣的規(guī)則，因此我們需要一些新的評價標準，下面介紹六中評價標準：相關性系數(shù)，卡方指數(shù)，全置信度、最大置信度、Kulc、cosine距離。4.2關聯(lián)規(guī)則的挖掘過程第四章關聯(lián)規(guī)則4.2.4關聯(lián)規(guī)則評價標準1）相關性系數(shù)lift引入正相關和負相關的機制，對于不是正相關的商品規(guī)則，可以用相關性系數(shù)lift過濾掉。對于規(guī)則A->B或者B->A，lift(A,B)=P(A∩B)/(P(A)*P(B))，如果lift(A,B)>1表示A、B呈正相關，lift(A,B)<1表示A、B呈負相關，lift(A,B)=1表示A、B不相關（獨立）。實際運用中，正相關和負相關都是我們需要關注的，而獨立往往是我們不需要的，兩個商品都沒有相互影響也就是不是強規(guī)則，lift(A,B)等于1的情形也很少，一般只要接近于1，便認為是獨立了。4.2關聯(lián)規(guī)則的挖掘過程第四章關聯(lián)規(guī)則4.2.4關聯(lián)規(guī)則評價標準2）卡方系數(shù)卡方分布是數(shù)理統(tǒng)計中的一個重要分布，利用卡方系數(shù)我們可以確定兩個變量是否相關?？ǚ较禂?shù)的定義：4.2關聯(lián)規(guī)則的挖掘過程第四章關聯(lián)規(guī)則4.2.4關聯(lián)規(guī)則評價標準3）全置信度all_confidence全置信度的定義如下：all_confidence(A,B)=P(A∩B)/max{P(A),P(B)}=min{P(B|A),P(A|B)}=min{confidence(A->B),confidence(B->A)}4）最大置信度max_confidence最大置信度則與全置信度相反，求的不是最小的支持度而是最大的支持度，max_confidence(A,B)=max{confidence(A->B),confidence(B->A)}，不過感覺最大置信度不太實用。4.2關聯(lián)規(guī)則的挖掘過程第四章關聯(lián)規(guī)則4.2.4關聯(lián)規(guī)則評價標準5）KulcKulc系數(shù)本質上是對兩個置信度做一個平均處理，公式為：kulc(A,B)=(confidence(A->B)+confidence(B->A))/2。6）cosine距離cosine(A,B)=P(A∩B)/sqrt(P(A)*P(B))=sqrt(P(A|B)*P(B|A))=sqrt(confidence(A->B)*confidence(B->A))第四章關聯(lián)規(guī)則4.3關聯(lián)規(guī)則的Apriori算法4.1關聯(lián)規(guī)則的基本概念4.2關聯(lián)規(guī)則的挖掘過程4.4關聯(lián)規(guī)則的FP-Growth算法習題大數(shù)據(jù)應用人才培養(yǎng)系列教材4.3關聯(lián)規(guī)則的Apriori算法第四章關聯(lián)規(guī)則頻繁項集的產(chǎn)生及其經(jīng)典算法之一——Apriori算法>>>Apriori算法——1概念Apriori算法基于頻繁項集性質的先驗知識，使用由下至上逐層搜索的迭代方法，即從頻繁1項集開始，采用頻繁k項集搜索頻繁k+1項集，直到不能找到包含更多項的頻繁項集為止。Apriori算法由以下步驟組成，其中的核心步驟是連接步和剪枝步：4.3關聯(lián)規(guī)則的Apriori算法第四章關聯(lián)規(guī)則頻繁項集的產(chǎn)生及其經(jīng)典算法之一——Apriori算法>>>Apriori算法——2核心思想Apriori算法的核心思想主要體現(xiàn)在兩個方面，即其兩個關鍵步驟：1)連接步為了找到頻繁k項集Lk，首先將Lk-1與自身連接，產(chǎn)生候選k項集Ck，Lk-1的元素是可連接的。4.3關聯(lián)規(guī)則的Apriori算法第四章關聯(lián)規(guī)則頻繁項集的產(chǎn)生及其經(jīng)典算法之一——Apriori算法>>>Apriori算法——2核心思想Apriori算法的核心思想主要體現(xiàn)在兩個方面，即其兩個關鍵步驟：2)剪枝步候選k項集Ck是Lk的超集，因此，Ck成員即可為頻繁項集也可不是頻繁的，但所有的頻繁項集都包括在Ck中。掃描數(shù)據(jù)庫，確定Ck中每一個候選的計數(shù)，從而確定Lk（計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，使用Apriori性質：任何非頻繁的(k-1)項集都不可能是頻繁k項集的子集。因此，如果一個候選k項集的(k-1)項集不在Lk中，則該候選項也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。4.2關聯(lián)規(guī)則的挖掘過程4.2關聯(lián)規(guī)則的挖掘過程頻繁項集的產(chǎn)生及其經(jīng)典算法之一——Apriori算法>>>Apriori算法——3步驟生成頻繁1項集L1連接步剪枝步生成頻繁k項集Lk重復步驟（2）～（4），直到不能產(chǎn)生新的頻繁項集的集合為止，算法中止。性能瓶頸Apriori算法是一個多趟搜索算法可能產(chǎn)生龐大的候選項集4.3關聯(lián)規(guī)則的Apriori算法第四章關聯(lián)規(guī)則4.3關聯(lián)規(guī)則的Apriori算法第四章關聯(lián)規(guī)則頻繁項集的產(chǎn)生及其經(jīng)典算法之一——Apriori算法>>>Apriori算法——4算法描述算法4-1Apriori——發(fā)現(xiàn)頻繁項目集(1)L1={large1-itemsets};(2)FOR(k=2;Lk-1

;k++)DOBEGIN(3)Ck=apriori-gen(Lk-1);//Ck是k個元素的候選集(4)FORalltransactionst

DDOBEGIN(5)Ct=subset(Ck,t);//Ct是所有t包含的候選集元素(6)FORallcandidatesc

CtDO(7)c.count++;(8)END(9)Lk={c

Ck|c.count

minsup_count}(10)END(11)Answer=

kLk;4.3關聯(lián)規(guī)則的Apriori算法第四章關聯(lián)規(guī)則頻繁項集的產(chǎn)生及其經(jīng)典算法之一——Apriori算法>>>Apriori算法——5改進鑒于Apriori算法需要多次掃描數(shù)據(jù)庫，在實際應用中，運行效率往往不能令人感到滿意，尤其是當數(shù)據(jù)庫較大時更為棘手。為了提高Apriori算法的性能和運行效率，許多專家對Apriori算法的改進展開了研究，形成了許多改進和擴展Apriori的方法。4.3關聯(lián)規(guī)則的Apriori算法第四章關聯(lián)規(guī)則頻繁項集的產(chǎn)生及其經(jīng)典算法之一——Apriori算法>>>Apriori算法——5改進改進算法的途徑包括以下幾個方面：①通過減少掃描數(shù)據(jù)庫的次數(shù)改進I/O的性能；②改進產(chǎn)生頻繁項集的計算性能；③尋找有效的并行關聯(lián)規(guī)則算法；④引入抽樣技術改進生成頻繁項集的I/O和計算性能；⑤擴展應用領域。比如展開定量關聯(lián)規(guī)則、泛化關聯(lián)規(guī)則及周期性的關聯(lián)規(guī)則的研究。4.3關聯(lián)規(guī)則的Apriori算法第四章關聯(lián)規(guī)則頻繁項集的產(chǎn)生及其經(jīng)典算法之一——Apriori算法>>>Apriori算法——5改進鑒于Apriori算法需要多次掃描數(shù)據(jù)庫，在實際應用中，運行效率往往不能令人感到滿意，尤其是當數(shù)據(jù)庫較大時更為棘手。為了提高Apriori算法的性能和運行效率，許多專家對Apriori算法的改進展開了研究，形成了許多改進和擴展Apriori的方法。第四章關聯(lián)規(guī)則4.4關聯(lián)規(guī)則的FP-Growth算法4.1關聯(lián)規(guī)則的基本概念4.2關聯(lián)規(guī)則的挖掘過程4.3關聯(lián)規(guī)則的Apriori算法習題大數(shù)據(jù)應用人才培養(yǎng)系列教材4.2關聯(lián)規(guī)則的挖掘過程頻繁項集的產(chǎn)生及其經(jīng)典算法之二——FP-Growth算法>>>FP-Growth算法——1概念頻繁模式樹增長算法（FrequentPatternTreeGrowth）采用分而治之的基本思想，將數(shù)據(jù)庫中的頻繁項集壓縮到一棵頻繁模式樹中，同時保持項集之間的關聯(lián)關系。然后將這棵壓縮后的頻繁模式樹分成一些條件子樹，每個條件子樹對應一個頻繁項，從而獲得頻繁項集，最后進行關聯(lián)規(guī)則挖掘。4.4關聯(lián)規(guī)則的FP-Growth算法第四章關聯(lián)規(guī)則4.2關聯(lián)規(guī)則的挖掘過程頻繁項集的產(chǎn)生及其經(jīng)典算法之二——FP-Growth算法>>>FP-Growth算法——2構建FP樹FP-growth算法將數(shù)據(jù)集的特點以一種樹結構的方式存儲，稱為FpTree。FpTree是一種用于編碼數(shù)據(jù)集的有效方式，樹結構定義如下：publicclassFpNode{StringidName;//id號

List<FpNode>children;//子結點

FpNodeparent;//父結點

FpNodenext;//下一個id號相同的結點

longcount;//出現(xiàn)次數(shù)}4.4關聯(lián)規(guī)則的FP-Growth算法第四章關聯(lián)規(guī)則4.2關聯(lián)規(guī)則的挖掘過程頻繁項集的產(chǎn)生及其經(jīng)典算法之二——FP-Growth算法>>>FP-Growth算法——2構建FP樹樹的每一個結點FpNode代表一個項，項的內(nèi)容包括id號idName、子結點children、父結點parent、下一個id號相同的結點next以及該項的出現(xiàn)次數(shù)count。4.4關聯(lián)規(guī)則的FP-Growth算法第四章關聯(lián)規(guī)則4.2關聯(lián)規(guī)則的挖掘過程頻繁項集的產(chǎn)生及其經(jīng)典算法之二——FP-Growth算法>>>FP-Growth算法——3從FP樹中挖掘頻繁項集（1）從headertable的最下面的item開始，構造每個item的條件模式基（ConditionalPatternBase，CPB）。（2）構造條件FP-tree（ConditionalFP-tree）累加每個CPB上的item的頻繁度（計數(shù)），過濾低于閾值的item，構建FP-tree。（3）FP-Growh：遞歸的挖掘每個條件FP-tree，累加后綴頻繁項集，直到找到FP-tree為空或者FP-tree只有一條路徑（只有一條路徑情況下，所有路徑上item的組合都是頻繁項集）?？梢宰C明（嚴謹?shù)乃惴ê妥C明在此不進行敘述），頻繁項集即不重復也不遺漏。4.4關聯(lián)規(guī)則的FP-Growth算法第四章關聯(lián)規(guī)則4.2關聯(lián)規(guī)則的挖掘過程>>>FP-Growth算法——4步驟FP-Growth算法由以下步驟組成：掃描事務數(shù)據(jù)庫D，生成頻繁1項集L1將頻繁1項集L1按照支持度遞減順序排序，得到排序后的項集L1構造FP樹通過后綴模式與條件FP樹產(chǎn)生的頻繁模式連接實現(xiàn)模式增長1234圖2FP樹的構造4.4關聯(lián)規(guī)則的FP-Growth算法第四章關聯(lián)規(guī)則頻繁項集的產(chǎn)生及其經(jīng)典算法之二——FP-Growth算法4.2關聯(lián)規(guī)則的挖掘過程頻繁項集的產(chǎn)生及其經(jīng)典算法之二——FP-Growth算法>>>FP-Growth算法——5對比FpGrowth算法的平均效率遠高于Apriori算法，但它并不能保證高效率，它的效率依賴于數(shù)據(jù)集。當數(shù)據(jù)集中的頻繁項集的沒有公共項時，所有的項集都掛在根結點上，不能實現(xiàn)壓縮存儲，而且Fptree還需要其他的開銷，需要存儲空間更大，使用FpGrowth算法前，首先需要對數(shù)據(jù)分析，在決策是否采用FpGrowth算法。4.4關聯(lián)規(guī)則的FP-Growth算法第四章關聯(lián)規(guī)則