商業(yè)分析第7章-商業(yè)數(shù)據(jù)挖掘方法課件

--商業(yè)數(shù)據(jù)的分析、挖掘和應(yīng)用商業(yè)分析華東師范大學(xué)出版社--商業(yè)數(shù)據(jù)的分析、挖掘和應(yīng)用商業(yè)分析華東師范大學(xué)出版1第7章

商業(yè)數(shù)據(jù)挖掘方法

第7章 商業(yè)數(shù)據(jù)挖掘方法

2主要內(nèi)容數(shù)據(jù)挖掘概論決策樹關(guān)聯(lián)規(guī)則聚類分析主要內(nèi)容數(shù)據(jù)挖掘概論37.1數(shù)據(jù)挖掘概論產(chǎn)生概念技術(shù)及過程應(yīng)用7.1數(shù)據(jù)挖掘概論產(chǎn)生47.1.1數(shù)據(jù)挖掘的產(chǎn)生隨著世界信息技術(shù)的迅猛發(fā)展，信息量也呈幾何指數(shù)增長。特別是隨著云時代的來臨，海量數(shù)據(jù)發(fā)展到大數(shù)據(jù)（BigData）已日益明顯，現(xiàn)在許多單位與組織在日常運營中生成、累積的各種數(shù)據(jù)，規(guī)模是如此龐大，以至于不能用G或T來衡量。例如，一天之中，互聯(lián)網(wǎng)產(chǎn)生的全部內(nèi)容可以刻滿1.6億多張DVD；發(fā)出的郵件有2940億封之多（相當(dāng)于美國兩年的紙質(zhì)信件數(shù)量）；發(fā)出的社區(qū)帖子達200萬個（相當(dāng)于《時代》雜志770年的文字量）；賣出的手機為37.8萬臺，高于全球每天出生的嬰兒數(shù)量37.1萬……（2011年數(shù)據(jù)）7.1.1數(shù)據(jù)挖掘的產(chǎn)生隨著世界信息技術(shù)的迅猛發(fā)展，信息量也57.1.1數(shù)據(jù)挖掘的產(chǎn)生如何從巨量、復(fù)雜的數(shù)據(jù)中獲取有用的信息，成為了信息技術(shù)研究領(lǐng)域的熱門課題。在這樣的背景下，數(shù)據(jù)挖掘技術(shù)誕生并成為了近年來的研究熱點。機器學(xué)習(xí)、數(shù)據(jù)庫技術(shù)和數(shù)理統(tǒng)計是數(shù)據(jù)挖掘的三個技術(shù)支柱。機器學(xué)習(xí)數(shù)據(jù)庫技術(shù)數(shù)理統(tǒng)計7.1.1數(shù)據(jù)挖掘的產(chǎn)生如何從巨量、復(fù)雜的數(shù)據(jù)中獲取有用的信67.1.2數(shù)據(jù)挖掘的概念從技術(shù)角度看：數(shù)據(jù)挖掘（DataMining）就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。從商業(yè)角度看：按企業(yè)既定業(yè)務(wù)目標(biāo)，對大量的企業(yè)數(shù)據(jù)進行探索和分析，揭示隱藏的、未知的或驗證已知的規(guī)律性，并進一步將其模型化的先進有效的方法。數(shù)據(jù)挖掘是從海量數(shù)據(jù)中提取隱含在其中的有用信息和知識的過程。它可以幫助企業(yè)對數(shù)據(jù)進行微觀、中觀乃至宏觀的統(tǒng)計、分析、綜合和推理，從而利用已有數(shù)據(jù)預(yù)測未來，幫助企業(yè)贏得競爭優(yōu)勢。7.1.2數(shù)據(jù)挖掘的概念從技術(shù)角度看：數(shù)據(jù)挖掘（DataM7數(shù)據(jù)挖掘任務(wù)主要有很多種，常見的有監(jiān)督學(xué)習(xí)（或稱為分類學(xué)習(xí)）、無監(jiān)督學(xué)習(xí)（或稱為聚類分析）、關(guān)聯(lián)規(guī)則挖掘、預(yù)測、時序挖掘和偏差分析等等。分類學(xué)習(xí)聚類分析關(guān)聯(lián)規(guī)則預(yù)測時序模式偏差分析7.1.3數(shù)據(jù)挖掘技術(shù)及過程數(shù)據(jù)挖掘任務(wù)主要有很多種，常見的有監(jiān)督學(xué)習(xí)（或稱為分類學(xué)習(xí)）8一般來說，數(shù)據(jù)挖掘需要經(jīng)歷以下過程：確定挖掘?qū)ο螅ɡ斫庋芯康臉I(yè)務(wù)領(lǐng)域）、收集數(shù)據(jù)（理解業(yè)務(wù)領(lǐng)域中的數(shù)據(jù)屬性）、數(shù)據(jù)預(yù)處理（對獲得的數(shù)據(jù)進行清洗等各種處理）、數(shù)據(jù)挖掘（用數(shù)據(jù)挖掘算法和模型來進行數(shù)據(jù)挖掘）和信息解釋（對得到的數(shù)據(jù)挖掘模型進行評估，評估有效后再在實際環(huán)境中使用），在數(shù)據(jù)挖掘過程中如能配以可視化的方法，則可大幅度提高效果。7.1.3數(shù)據(jù)挖掘技術(shù)及過程圖7-1.數(shù)據(jù)挖掘過程一般來說，數(shù)據(jù)挖掘需要經(jīng)歷以下過程：確定挖掘?qū)ο螅ɡ斫庋芯康?數(shù)據(jù)挖掘工具目前國際上廣泛應(yīng)用的數(shù)據(jù)挖掘工具有很多SASEnterpriseMiner

SPSS公司的Clementine（被IBM公司收購后改名為Modeler）SQLSever中的數(shù)據(jù)挖掘模塊Waikato大學(xué)開發(fā)的Weka平臺IBM公司的IntelligentMiner開源軟件R語言 ……7.1.4數(shù)據(jù)挖掘應(yīng)用數(shù)據(jù)挖掘工具7.1.4數(shù)據(jù)挖掘應(yīng)用10數(shù)據(jù)挖掘應(yīng)用場景

數(shù)據(jù)挖掘在商業(yè)分析領(lǐng)域的一些應(yīng)用如下：金融領(lǐng)域營銷領(lǐng)域電子政務(wù)電信領(lǐng)域工業(yè)生產(chǎn)生物和醫(yī)學(xué) ……7.1.4數(shù)據(jù)挖掘應(yīng)用數(shù)據(jù)挖掘應(yīng)用場景7.1.4數(shù)據(jù)挖掘應(yīng)用11數(shù)據(jù)挖掘應(yīng)用場景——金融領(lǐng)域客戶信用等級評估客戶透支分析客戶利潤分析客戶消費行為分析客戶消費異常行為分析 ……7.1.4數(shù)據(jù)挖掘應(yīng)用數(shù)據(jù)挖掘應(yīng)用場景——金融領(lǐng)域7.1.4數(shù)據(jù)挖掘應(yīng)用127.2決策樹定義分類與作用常用算法剪枝7.2決策樹定義137.2.1決策樹定義理解什么是決策樹，決策樹有什么作用之前，我們先給出一個決策樹的基本結(jié)構(gòu)。它的形狀是一棵倒置的樹，包括節(jié)點和分支。有三種類型的節(jié)點：父節(jié)點、內(nèi)部節(jié)點和葉節(jié)點。圖7-2.決策樹示意圖7.2.1決策樹定義理解什么是決策樹，決策樹有什么作用之前，147.2.1決策樹定義決策樹(DecisionTree)是一種以實例為基礎(chǔ)的歸納學(xué)習(xí)算法，是一種從無次序、無規(guī)則的訓(xùn)練樣本集中推理出決策樹表示形式的分類規(guī)則的方法，它提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。工作過程：圖7-3.決策樹工作過程7.2.1決策樹定義決策樹(DecisionTree)是一157.2.2決策樹分類與作用決策樹主要應(yīng)用于分類預(yù)測。分類預(yù)測的結(jié)果有定性和定量兩種。例如，預(yù)測天氣，定性有下雨或不下雨；定量則是下多少雨，具體的數(shù)值。在實際應(yīng)用中，我們將定性的分類預(yù)測稱為分類，用來確定類別屬性；定量的分類預(yù)測成為預(yù)測，用來預(yù)測具體的數(shù)值。分類是一種重要的數(shù)據(jù)挖掘技術(shù)。分類的目的是根據(jù)數(shù)據(jù)集的特點構(gòu)造一個分類函數(shù)或分類模型（也常常稱作分類器），該模型能把未知類別的樣本映射到給定類別中的某一個。因此，決策樹可以分為兩類：分類決策樹，簡稱分類樹，實現(xiàn)對分類型輸出變量的分類；回歸決策樹，簡稱回歸樹，完成對數(shù)值型輸出變量的預(yù)測。7.2.2決策樹分類與作用決策樹主要應(yīng)用于分類預(yù)測。分類預(yù)測167.2.2決策樹常用算法決策樹的兩大核心問題：決策樹的生長：在樣本數(shù)據(jù)中選擇哪一個屬性作為根節(jié)點，然后如何分支，如何選擇內(nèi)部節(jié)點，直到生長出樹葉，即到達葉節(jié)點，這一系列過程可稱為決策樹的分枝準(zhǔn)則，即具體算法；決策樹的剪枝：防止決策樹生長過于茂盛，無法適應(yīng)實際應(yīng)用的需要。7.2.2決策樹常用算法決策樹的兩大核心問題：177.2.2決策樹常用算法決策樹常用算法：基于信息論的方法：ID系列算法C4.5C5.0最小GINI指標(biāo)的方法：

CART

SLIQSPRINT決策樹剪枝方法：預(yù)修剪(Pre-Pruning)后修剪(Post-Pruning)7.2.2決策樹常用算法決策樹常用算法：187.2.2決策樹常用算法決策樹常用算法——ID3算法1986年，J.R.Quinlan提出了ID3(IterativeDichotomizer)算法。該算法是以信息論為基礎(chǔ)，運用信息熵理論，采用自頂向下的貪心搜索算法。其核心思想是在決策樹中各級節(jié)點上選擇分裂屬性。用信息增益作為屬性選擇的標(biāo)準(zhǔn)，使每個非葉子節(jié)點測試時，能獲得關(guān)于被測試例子最大的類別信息。使用該屬性將訓(xùn)練樣本集分成子集后，系統(tǒng)的信息熵值最小。7.2.2決策樹常用算法決策樹常用算法——ID3算法197.2.2決策樹常用算法決策樹常用算法——ID3算法信息熵與信息增益信息論之父申農(nóng)（C.E.Shannonm）把信息中排除了冗余后的平均信息量稱為“信息熵”，并給出了計算信息熵的數(shù)學(xué)表達式，他把信息熵定義為離散隨機事件的出現(xiàn)概率?？偠灾畔㈧氐幕咀饔镁褪窍藗儗κ挛锏牟淮_定性。ID3算法根據(jù)信息論，采用劃分后樣本集的不確定性作為衡量劃分好壞的標(biāo)準(zhǔn)，用信息增益度量，信息增益值越大，不確定性越小。因此，算法在每個非葉子節(jié)點選擇信息增益最大的屬性作為分裂屬性。7.2.2決策樹常用算法決策樹常用算法——ID3算法207.2.2決策樹常用算法

7.2.2決策樹常用算法

217.2.2決策樹常用算法

7.2.2決策樹常用算法

227.2.2決策樹常用算法

7.2.2決策樹常用算法

2324Example(ID3信息增益)n=16

n1=4

I(16,4)=-((4/16)*log2(4/16)+(12/16)*log2(12/16))=0.8113E(年齡)=(6/16)*I(6,1)+(10/16)*I(10,3)=0.7946Gain(年齡)=I(16,4)-E(年齡)=0.0167Gain(年齡)=0.0167Gain(性別)=0.0972Gain(家庭所得)=0.0177Max:作為第一個分類依據(jù)圖7-4a.ID3工作過程示意圖a24Example(ID3信息增益)n=16

n1=2425Gain(家庭所得)=0.688Example(續(xù))I(7,3)=-((3/7)*log2(3/7)+(4/7)*log2(4/7))=0.9852Gain(年齡)=0.9852Gain(年齡)=0.2222I(9,1)=-((1/9)*log2(1/9)+(8/9)*log2(8/9))=0.5032Gain(家庭所得)=0.5032圖7-4b.ID3工作過程示意圖b25Gain(家庭所得)=0.688Example(續(xù))I(2526Example(end)ID3算法分類規(guī)則IF性別=FemaleAND家庭所得=

低所得THEN購買RV房車=否IF性別=FemaleAND家庭所得=

小康THEN購買RV房車=否IF性別=FemaleAND家庭所得=

高所得THEN購買RV房車=是IF性別=MaleAND年齡<35

THEN購買RV房車=否IF性別=MaleAND年齡≧35

THEN購買RV房車=是資料DecisionTree圖7-4c.ID3工作過程示意圖c26Example(end)ID3算法分類規(guī)則資料Deci267.2.2決策樹常用算法決策樹常用算法——C5.0算法C4.5算法在ID3算法的基礎(chǔ)上進行了改進，增加了對連續(xù)屬性的離散型的處理。對于預(yù)測變量的缺值處理、剪枝技術(shù)、派生規(guī)則等方面作了較大改進，既適合于分類問題，又適合于回歸問題。而C5.0則是在C4.5的基礎(chǔ)上改進了執(zhí)行效率和內(nèi)存使用，應(yīng)用于大數(shù)據(jù)集的分類算法。它采用Boosting方式來提高模型準(zhǔn)確率。決策樹是用樣本的屬性作為結(jié)點，用屬性的取值作為分枝的樹結(jié)構(gòu)的。屬性的度量標(biāo)準(zhǔn)有很多，C5.0采用信息增益率作為屬性的度量標(biāo)準(zhǔn)。7.2.2決策樹常用算法決策樹常用算法——C5.0算法277.2.2決策樹常用算法決策樹常用算法——C5.0算法（1）信息增益率在1993年J．R．Quinlan提出信息增益率。信息增益率克服了在計算信息增益時偏向于選擇取值較多的屬性的缺點，能夠在樹的生成中或完成后對樹進行剪枝。信息增益率的計算公式如下式：其中，

是屬性A的信息熵。7.2.2決策樹常用算法決策樹常用算法——C5.0算法287.2.2決策樹常用算法決策樹常用算法——C5.0算法（2）Boosting技術(shù)Boosting是一種提高任意給定學(xué)習(xí)算法準(zhǔn)確度的方法。在C5.0中是用來提高模型準(zhǔn)確度的。Boosting中最基本的是Adaboost算法，其他算法的主要原理都差不多，只是實現(xiàn)手段或者說采用的數(shù)學(xué)公式不同。Adaboost算法在現(xiàn)實生活中的經(jīng)典使用領(lǐng)域就是用于人臉識別。圖7-5.基于Adaboost算法的人臉識別示意圖7.2.2決策樹常用算法決策樹常用算法——C5.0算法圖7-297.2.2決策樹常用算法決策樹常用算法——CART算法它是由統(tǒng)計學(xué)家L.Breiman，J.Friedman，R.Olshen和C.Stone在出版的著作《分類與回歸樹》中提出的一種產(chǎn)生二叉決策樹分類模型的技術(shù)。它與前面Quinlan提出的ID系列算法和C4.5不同的是，它使用的屬性度量標(biāo)準(zhǔn)是Gini指標(biāo)。CART與C4.5/C5.0算法的最大相異之處是其在每一個節(jié)點上都是采用二分法，也就是一次只能夠有兩個子節(jié)點，C4.5/5.0則在每一個節(jié)點上可以產(chǎn)生不同數(shù)量的分枝。CART模型適用于目標(biāo)變量為連續(xù)型和類別型的變量，如果目標(biāo)變量是類別型變量，則可以使用分類樹（classificationtrees），目標(biāo)變量是連續(xù)型的，則可以采用回歸樹（regressiontrees）。7.2.2決策樹常用算法決策樹常用算法——CART算法307.2.2決策樹常用算法決策樹常用算法——CART算法Gini指標(biāo)Gini指標(biāo)主要是度量數(shù)據(jù)劃分或訓(xùn)練數(shù)據(jù)集D的不純度為主，系數(shù)值的屬性作為測試屬性，Gini值越小，表明樣本的“純凈度”越高。Gini指標(biāo)的計算公式如下式：其中Pi是類別Ci在D中出現(xiàn)的概率。如果集合T分成兩部分N1andN2。則此分割的Gini就是：提供最小Ginisplit就被選擇作為分割的標(biāo)準(zhǔn)(對于每個屬性都要經(jīng)過所有可以的分割方法)。7.2.2決策樹常用算法決策樹常用算法——CART算法31Example(Gini)例：顧客數(shù)據(jù)庫/訓(xùn)練數(shù)據(jù)D例中，預(yù)測變量為buycomp,是否購買電腦。Age\income\student\cred都為非連續(xù)變量。

對于離散性屬性，選擇該屬性產(chǎn)生最小的Gini指標(biāo)的子集作為它的分裂子集；對于連續(xù)值屬性，必須考慮每個可能的分裂點，選擇某一分裂點導(dǎo)致最小的Gini指標(biāo)。樣本D中：10（yes），4（no）D的不純度為按下列公式：為找出D中元組的分裂準(zhǔn)則，需要計算每個屬性的Gini指標(biāo)。對age的二元分組可以有：取其中2個一組，剩下的一組同樣對income的二元分組可以有：取其中2個一組，剩下的一組Example(Gini)例：顧客數(shù)據(jù)庫/訓(xùn)練數(shù)據(jù)D32Example(Gini)“income∈{low,medium}，形成D1，8（yes),2(no)“income∈{high}，形成D2，2（yes),2(no)例如：income屬性，假設(shè)考慮子集｛low，medium},這將D中的元組二元劃分。D中的元組10個元組滿足條件“income∈{low,medium}，形成D1，其余的4組劃分到D2，income∈{high}.同樣可計算得出：Example(Gini)“income∈{low,med337.2.2決策樹常用算法剪枝現(xiàn)實世界的數(shù)據(jù)一般不可能是完美的，可能某些屬性字段上缺值；可能缺少必要的數(shù)據(jù)而造成數(shù)據(jù)不完整；可能數(shù)據(jù)不準(zhǔn)確、含有噪聲甚至是錯誤的?；镜臎Q策樹構(gòu)造算法沒有考慮噪聲，因此生成的決策樹完全與訓(xùn)練例子擬合。在有噪聲情況下，完全擬合將導(dǎo)致過分擬合，即對訓(xùn)練數(shù)據(jù)的完全擬合反而使對現(xiàn)實數(shù)據(jù)的分類預(yù)測性能下降。剪枝是一種克服噪聲的基本技術(shù)，同時它也能使樹得到簡化而變得更容易理解。7.2.2決策樹常用算法剪枝347.2.2決策樹常用算法決策樹剪枝方法——前剪枝前期剪枝(Forward-Pruning)是提前停止樹的構(gòu)造而對樹進行剪枝。停止決策樹的生長的方法大體上可以歸納為以下幾種：在決策樹到達一定高度的情況下就停止樹的生長；到達此結(jié)點的實例具有相同的特征向量，而不必一定屬于同一類，也可停止生長；到達此結(jié)點的實例個數(shù)小于某一個閾值也可停止樹的生長；計算每次擴張對系統(tǒng)性能的增益，如果這個增益值小于某個閾值則不進行擴展；如果在最好情況下的擴展增益都小于閾值，即使有些葉子結(jié)點的實例不屬于同一類，也停止樹的增長。7.2.2決策樹常用算法決策樹剪枝方法——前剪枝357.2.2決策樹常用算法決策樹剪枝方法——后剪枝后剪枝(Post-Pruning)首先構(gòu)造完整的決策樹，允許決策樹過度擬合訓(xùn)練數(shù)據(jù)，然后對那些置信度不夠的結(jié)點的子樹用葉子結(jié)點來替代，這個葉子結(jié)點所應(yīng)標(biāo)記的類別為子樹中大多數(shù)實例所屬的類別。ID3算法、C5.0算法和CART算法都是先建樹再剪枝，屬于后剪枝。后剪枝方法現(xiàn)在得到比較廣泛地使用。常用的后剪枝算法有：CCP(CostComplexityPruning)REP(ReducedErrorPruning)PEP(PessimisticErrorPruning)MEP(MinimumErrorPruning)7.2.2決策樹常用算法決策樹剪枝方法——后剪枝367.3關(guān)聯(lián)規(guī)則定義分類算法原理常用算法7.3關(guān)聯(lián)規(guī)則定義377.3關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則主要用于發(fā)現(xiàn)大量數(shù)據(jù)之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。關(guān)聯(lián)規(guī)則挖掘的一個典型例子是購物籃分析除此以外，關(guān)聯(lián)規(guī)則分析還可以應(yīng)用于客戶交叉營銷、風(fēng)險防范等方面。例如，為了高效率地營銷信用卡業(yè)務(wù)，營銷人員可以通過關(guān)聯(lián)規(guī)則的分析，在眾多銀行產(chǎn)品客戶中選擇可信度較高的群體進行交叉營銷，如基金客戶、外匯交易客戶等。圖7-6.關(guān)聯(lián)規(guī)則工作過程示意圖7.3關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則主要用于發(fā)現(xiàn)大量數(shù)據(jù)之間有趣的關(guān)聯(lián)或相387.3.1關(guān)聯(lián)規(guī)則定義

7.3.1關(guān)聯(lián)規(guī)則定義

397.3.1關(guān)聯(lián)規(guī)則定義

7.3.1關(guān)聯(lián)規(guī)則定義

407.3.2關(guān)聯(lián)規(guī)則分類⑴

基于規(guī)則中處理變量的類型，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。布爾型考慮的是項集的存在與否，而數(shù)值型則是量化的關(guān)聯(lián)。⑵

基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。⑶

基于規(guī)則中涉及到的數(shù)據(jù)維數(shù)，可以分為單維關(guān)聯(lián)規(guī)則和多維關(guān)聯(lián)規(guī)則。7.3.2關(guān)聯(lián)規(guī)則分類⑴基于規(guī)則中處理變量的類型，關(guān)聯(lián)規(guī)則417.3.3關(guān)聯(lián)規(guī)則算法原理原理關(guān)聯(lián)規(guī)則的挖掘就是在事務(wù)數(shù)據(jù)庫D中找出具有用戶給定的最小支持度（MinimumSupport,minsup）和最小置信度(MinimumConfidence,minconf)的關(guān)聯(lián)規(guī)則。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集或大項集。步驟Step1根據(jù)最小支持度閾值找出數(shù)據(jù)集D中所有頻繁項目集；Step2根據(jù)頻繁項目集和最小置信度閾值產(chǎn)生所有關(guān)聯(lián)規(guī)則。7.3.3關(guān)聯(lián)規(guī)則算法原理原理427.3.3關(guān)聯(lián)規(guī)則算法原理基本模型算法1算法2數(shù)據(jù)集規(guī)則用戶最小支持度最小置信度圖7-7.關(guān)聯(lián)規(guī)則挖掘的基本模型7.3.3關(guān)聯(lián)規(guī)則算法原理基本模型算法1算法2數(shù)據(jù)集規(guī)則用437.3.3關(guān)聯(lián)規(guī)則算法原理基本算法搜索算法分層算法(寬度優(yōu)先算法)深度優(yōu)先算法劃分算法抽樣算法7.3.3關(guān)聯(lián)規(guī)則算法原理基本算法447.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——介紹Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。Apriori算法——兩大缺點一是可能產(chǎn)生大量的候選集；二是可能需要重復(fù)掃描數(shù)據(jù)庫。7.3.4關(guān)聯(lián)規(guī)則常用算法457.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——基本思路Apriori算法使用頻繁項集的先驗知識（稱為逐層搜索的迭代方法），k項集用于探索(k+1)項集。首先，通過掃描事務(wù)（交易）記錄，找出所有的頻繁1項集，該集合記做L1，然后利用L1找頻繁2項集的集合L2，L2找L3，如此下去，直到不能再找到任何頻繁k項集。最后再在所有的頻繁集中找出強規(guī)則，即產(chǎn)生用戶感興趣的關(guān)聯(lián)規(guī)則。7.3.4關(guān)聯(lián)規(guī)則常用算法467.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——剪枝步Ck是Lk的超集，也就是說，Ck的成員可能是也可能不是頻繁的。通過掃描所有的事務(wù)（交易），確定CK中每個候選的計數(shù)，判斷是否小于最小支持度計數(shù)，如果不是，則認為該候選是頻繁的。為了壓縮Ck,可以利用Apriori性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的；反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。7.3.4關(guān)聯(lián)規(guī)則常用算法477.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——連接步為找出Lk（所有的頻繁k項集的集合），通過將Lk-1（所有的頻繁k-1項集的集合）與自身連接產(chǎn)生候選k項集的集合。候選集合記作Ck。設(shè)l1和l2是Lk-1中的成員。記li[j]表示li中的第j項。假設(shè)Apriori算法對事務(wù)或項集中的項按字典次序排序，即對于（k-1）項集li，li[1]<li[2]<…<li[k-1]。將Lk-1與自身連接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&…&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那認為l1和l2是可連接。連接l1和l2產(chǎn)生的結(jié)果是{l1[1],l1[2],…,l1[k-1],l2[k-1]}。7.3.4關(guān)聯(lián)規(guī)則常用算法487.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——連接步為找出Lk（所有的頻繁k項集的集合），通過將Lk-1（所有的頻繁k-1項集的集合）與自身連接產(chǎn)生候選k項集的集合。候選集合記作Ck。設(shè)l1和l2是Lk-1中的成員。記li[j]表示li中的第j項。假設(shè)Apriori算法對事務(wù)或項集中的項按字典次序排序，即對于（k-1）項集li，li[1]<li[2]<…<li[k-1]。將Lk-1與自身連接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&…&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那認為l1和l2是可連接。連接l1和l2產(chǎn)生的結(jié)果是{l1[1],l1[2],…,l1[k-1],l2[k-1]}。7.3.4關(guān)聯(lián)規(guī)則常用算法497.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——實例上表7-1某商場的交易記錄，共有9個事務(wù)。交易ID商品ID列表T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I37.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——實例交易ID507.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——實例利用Apriori算法求得所有的頻繁項集過程如下圖：圖7-8.關(guān)聯(lián)規(guī)則Apriori算法實例7.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——實例圖7-8517.3.4關(guān)聯(lián)規(guī)則常用算法FP-Tree算法——介紹FP-Growth算法是韓家煒老師在2000年提出的關(guān)聯(lián)分析算法，它采取如下分治策略：將提供頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（FrequentPattern-growth,FP-Tree），但仍保留項集關(guān)聯(lián)信息。FP-Tree算法與Apriori算法的區(qū)別一是FP-Tree不產(chǎn)生候選集；二是FP-Tree只需要兩次遍歷數(shù)據(jù)庫，大大提高了效率。7.3.4關(guān)聯(lián)規(guī)則常用算法FP-Tree算法——介紹527.3.4關(guān)聯(lián)規(guī)則常用算法FP-Tree算法——基本思路不斷地迭代FP-tree的構(gòu)造和投影過程。FP-Tree算法——具體描述①對于每個頻繁項，構(gòu)造它的條件投影數(shù)據(jù)庫和投影FP-tree；②對每個新構(gòu)建的FP-tree重復(fù)這個過程，直到構(gòu)造的新FP-tree為空，或者只包含一條路徑；③當(dāng)構(gòu)造的FP-tree為空時，其前綴即為頻繁模式；當(dāng)只包含一條路徑時，通過枚舉所有可能組合并與此樹的前綴連接即可得到頻繁模式。7.3.4關(guān)聯(lián)規(guī)則常用算法FP-Tree算法——基本思路537.4聚類分析定義聚類與分類的區(qū)別應(yīng)用領(lǐng)域分類常用算法異常檢測“物以類聚，人以群分”7.4聚類分析定義“物以類聚，人以群分”547.4.1聚類分析定義俗話說：“物以類聚，人以群分”，在自然科學(xué)和社會科學(xué)中，存在著大量的聚類問題。所謂類，通俗地說，就是指相似的元素的集合。聚類分析是對樣品或指標(biāo)進行分類的一種多元統(tǒng)計分析方法。聚類分析的起源是分類學(xué)，但是與分類不同的是，它要劃分的類是未知的。聚類就是將數(shù)據(jù)對象分組成為多個有意義或有用簇，在同一個簇中的對象具有較高的相似度，而不同的簇中的對象差別很大。聚類就是把整個數(shù)據(jù)集分成不同的“簇”，并且要使簇與簇之間的區(qū)別盡可能的大，而簇內(nèi)的數(shù)據(jù)的差異盡可能小。圖7-9.聚類的理解7.4.1聚類分析定義俗話說：“物以類聚，人以群分”，在自然557.4.2聚類與分類的區(qū)別聚類是一種無指導(dǎo)學(xué)習(xí)（無監(jiān)督學(xué)習(xí)），即從樣本的特征向量出發(fā)研究通過某種算法將特征相似的樣本聚集在一起，從而達到區(qū)分具有不同特征樣本的目的。分類則是一種有指導(dǎo)學(xué)習(xí)（有監(jiān)督學(xué)習(xí)），它具有先驗知識（分類號），而無監(jiān)督聚類學(xué)習(xí)并不具有這種先驗知識。聚類與分類不同的是，它要劃分的類是未知的。即聚類是一種無指導(dǎo)學(xué)習(xí)，它不依賴預(yù)先定義的類和帶類標(biāo)號的訓(xùn)練實例。由于這個原因，聚類是觀察式學(xué)習(xí)，而不是示例式學(xué)習(xí)。7.4.2聚類與分類的區(qū)別聚類是一種無指導(dǎo)學(xué)習(xí)（無監(jiān)督學(xué)習(xí)）567.4.3聚類應(yīng)用領(lǐng)域聚類分析在許多實際問題上都有應(yīng)用：商務(wù)領(lǐng)域生物領(lǐng)域地理保險行業(yè)電子商務(wù)

7.4.3聚類應(yīng)用領(lǐng)域聚類分析在許多實際問題上都有應(yīng)用：577.4.4聚類算法分類

7.4.4聚類算法分類

587.4.4聚類算法分類劃分方法(PartitioningMethods)k-meansk-medoids層次的方法(HierarchicalMethods)凝聚和分裂的層次聚類BIRCH(ClusteringFeature)ROCK:分類屬性層次聚類算法CURE:使用代表點聚類方法Chameleon:動態(tài)建模層次聚類基于網(wǎng)絡(luò)的方法(Grid-basedMethods)STING：統(tǒng)計信息網(wǎng)格聚類WaveCluster：利用小波變換聚類基于模型的方法(Model-basedMethods)7.4.4聚類算法分類劃分方法(PartitioningM597.4.5聚類常用算法K-Means算法——介紹K-Means算法，也稱K-平均算法，用來根據(jù)樣本屬性值之間的相似度來對樣本進行分組。其基本思路是，以K為參數(shù)，把n個對象劃分為K個簇，從而使每個簇內(nèi)具有較高的相似度。但不同的簇的樣本則非常相異。K-Means是一種迭代算法，初始的K個簇被隨機地定義之后，這些簇將被不斷地更新，并在更新中被優(yōu)化，當(dāng)無法再進一步優(yōu)化（或者達到一定的迭代次數(shù)）時算法停止。7.4.5聚類常用算法K-Means算法——介紹607.4.5聚類常用算法K-Means算法——具體流程①

從數(shù)據(jù)集中選擇聚類的K個質(zhì)心，作為初始的簇中心；②

計算每個對象到各質(zhì)心的距離，把樣本指派給距離最小的簇；③

根據(jù)每個簇當(dāng)前所擁有的所有對象更新質(zhì)心；④

根據(jù)每個對象與各個簇中心的距離，分配給最近的簇；⑤

然后轉(zhuǎn)③，重新計算每個簇的平均值。這個過程不斷重復(fù)直到滿足某個準(zhǔn)則函數(shù)才停止。圖7-10.聚類K-Means實例示意圖7.4.5聚類常用算法K-Means算法——具體流程圖7-1617.4.5聚類常用算法兩步聚類算法——介紹兩步聚類是一種探索性的聚類方法，是隨著人工智能的發(fā)展而發(fā)展起來的智能聚類方法中的一種。它最顯著的特點就是它分兩步進行聚類，主要用于處理非常大的數(shù)據(jù)集，可以處理連續(xù)屬性和離散屬性。它只需遍歷數(shù)據(jù)集一次。兩步聚類算法——特點①

同時處理離散變量和連續(xù)變量的能力。②

自動選擇聚類數(shù)。③

通過預(yù)先選取樣本中的部分數(shù)據(jù)構(gòu)建聚類模型。④

可以處理超大樣本量的數(shù)據(jù)。7.4.5聚類常用算法兩步聚類算法——介紹627.4.5聚類常用算法兩步聚類算法——步驟第一步：預(yù)聚類。遍歷一次的數(shù)據(jù)，對記錄進行初始的歸類，用戶自定義最大類別數(shù)。通過構(gòu)建和修改特征樹（CFTREE）來完成；第二步：聚類。對第一步完成的初步聚類進行再聚類并確定最終的聚類方案，使用層次聚類的方法將小的聚類逐漸合并成越來越大的聚類，這一過程不需要再次遍歷數(shù)據(jù)。層次聚類的好處是不要求提前選擇聚類數(shù)。許多層次聚類從單個記錄開始聚類，逐步合并成更大的類群。7.4.5聚類常用算法兩步聚類算法——步驟637.4.5聚類異常檢測簡介基于聚類的異常檢測方法：基于統(tǒng)計的方法基于距離的方法基于偏差的方法基于密度的方法高維數(shù)據(jù)的異常檢測7.4.5聚類異常檢測簡介基于聚類的異常檢測方法：64Clicktoeditcompanyslogan.ThankYou!Clicktoeditcompanyslogan.65--商業(yè)數(shù)據(jù)的分析、挖掘和應(yīng)用商業(yè)分析華東師范大學(xué)出版社--商業(yè)數(shù)據(jù)的分析、挖掘和應(yīng)用商業(yè)分析華東師范大學(xué)出版66第7章

商業(yè)數(shù)據(jù)挖掘方法

第7章 商業(yè)數(shù)據(jù)挖掘方法

67主要內(nèi)容數(shù)據(jù)挖掘概論決策樹關(guān)聯(lián)規(guī)則聚類分析主要內(nèi)容數(shù)據(jù)挖掘概論687.1數(shù)據(jù)挖掘概論產(chǎn)生概念技術(shù)及過程應(yīng)用7.1數(shù)據(jù)挖掘概論產(chǎn)生697.1.1數(shù)據(jù)挖掘的產(chǎn)生隨著世界信息技術(shù)的迅猛發(fā)展，信息量也呈幾何指數(shù)增長。特別是隨著云時代的來臨，海量數(shù)據(jù)發(fā)展到大數(shù)據(jù)（BigData）已日益明顯，現(xiàn)在許多單位與組織在日常運營中生成、累積的各種數(shù)據(jù)，規(guī)模是如此龐大，以至于不能用G或T來衡量。例如，一天之中，互聯(lián)網(wǎng)產(chǎn)生的全部內(nèi)容可以刻滿1.6億多張DVD；發(fā)出的郵件有2940億封之多（相當(dāng)于美國兩年的紙質(zhì)信件數(shù)量）；發(fā)出的社區(qū)帖子達200萬個（相當(dāng)于《時代》雜志770年的文字量）；賣出的手機為37.8萬臺，高于全球每天出生的嬰兒數(shù)量37.1萬……（2011年數(shù)據(jù)）7.1.1數(shù)據(jù)挖掘的產(chǎn)生隨著世界信息技術(shù)的迅猛發(fā)展，信息量也707.1.1數(shù)據(jù)挖掘的產(chǎn)生如何從巨量、復(fù)雜的數(shù)據(jù)中獲取有用的信息，成為了信息技術(shù)研究領(lǐng)域的熱門課題。在這樣的背景下，數(shù)據(jù)挖掘技術(shù)誕生并成為了近年來的研究熱點。機器學(xué)習(xí)、數(shù)據(jù)庫技術(shù)和數(shù)理統(tǒng)計是數(shù)據(jù)挖掘的三個技術(shù)支柱。機器學(xué)習(xí)數(shù)據(jù)庫技術(shù)數(shù)理統(tǒng)計7.1.1數(shù)據(jù)挖掘的產(chǎn)生如何從巨量、復(fù)雜的數(shù)據(jù)中獲取有用的信717.1.2數(shù)據(jù)挖掘的概念從技術(shù)角度看：數(shù)據(jù)挖掘（DataMining）就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。從商業(yè)角度看：按企業(yè)既定業(yè)務(wù)目標(biāo)，對大量的企業(yè)數(shù)據(jù)進行探索和分析，揭示隱藏的、未知的或驗證已知的規(guī)律性，并進一步將其模型化的先進有效的方法。數(shù)據(jù)挖掘是從海量數(shù)據(jù)中提取隱含在其中的有用信息和知識的過程。它可以幫助企業(yè)對數(shù)據(jù)進行微觀、中觀乃至宏觀的統(tǒng)計、分析、綜合和推理，從而利用已有數(shù)據(jù)預(yù)測未來，幫助企業(yè)贏得競爭優(yōu)勢。7.1.2數(shù)據(jù)挖掘的概念從技術(shù)角度看：數(shù)據(jù)挖掘（DataM72數(shù)據(jù)挖掘任務(wù)主要有很多種，常見的有監(jiān)督學(xué)習(xí)（或稱為分類學(xué)習(xí)）、無監(jiān)督學(xué)習(xí)（或稱為聚類分析）、關(guān)聯(lián)規(guī)則挖掘、預(yù)測、時序挖掘和偏差分析等等。分類學(xué)習(xí)聚類分析關(guān)聯(lián)規(guī)則預(yù)測時序模式偏差分析7.1.3數(shù)據(jù)挖掘技術(shù)及過程數(shù)據(jù)挖掘任務(wù)主要有很多種，常見的有監(jiān)督學(xué)習(xí)（或稱為分類學(xué)習(xí)）73一般來說，數(shù)據(jù)挖掘需要經(jīng)歷以下過程：確定挖掘?qū)ο螅ɡ斫庋芯康臉I(yè)務(wù)領(lǐng)域）、收集數(shù)據(jù)（理解業(yè)務(wù)領(lǐng)域中的數(shù)據(jù)屬性）、數(shù)據(jù)預(yù)處理（對獲得的數(shù)據(jù)進行清洗等各種處理）、數(shù)據(jù)挖掘（用數(shù)據(jù)挖掘算法和模型來進行數(shù)據(jù)挖掘）和信息解釋（對得到的數(shù)據(jù)挖掘模型進行評估，評估有效后再在實際環(huán)境中使用），在數(shù)據(jù)挖掘過程中如能配以可視化的方法，則可大幅度提高效果。7.1.3數(shù)據(jù)挖掘技術(shù)及過程圖7-1.數(shù)據(jù)挖掘過程一般來說，數(shù)據(jù)挖掘需要經(jīng)歷以下過程：確定挖掘?qū)ο螅ɡ斫庋芯康?4數(shù)據(jù)挖掘工具目前國際上廣泛應(yīng)用的數(shù)據(jù)挖掘工具有很多SASEnterpriseMiner

SPSS公司的Clementine（被IBM公司收購后改名為Modeler）SQLSever中的數(shù)據(jù)挖掘模塊Waikato大學(xué)開發(fā)的Weka平臺IBM公司的IntelligentMiner開源軟件R語言 ……7.1.4數(shù)據(jù)挖掘應(yīng)用數(shù)據(jù)挖掘工具7.1.4數(shù)據(jù)挖掘應(yīng)用75數(shù)據(jù)挖掘應(yīng)用場景

數(shù)據(jù)挖掘在商業(yè)分析領(lǐng)域的一些應(yīng)用如下：金融領(lǐng)域營銷領(lǐng)域電子政務(wù)電信領(lǐng)域工業(yè)生產(chǎn)生物和醫(yī)學(xué) ……7.1.4數(shù)據(jù)挖掘應(yīng)用數(shù)據(jù)挖掘應(yīng)用場景7.1.4數(shù)據(jù)挖掘應(yīng)用76數(shù)據(jù)挖掘應(yīng)用場景——金融領(lǐng)域客戶信用等級評估客戶透支分析客戶利潤分析客戶消費行為分析客戶消費異常行為分析 ……7.1.4數(shù)據(jù)挖掘應(yīng)用數(shù)據(jù)挖掘應(yīng)用場景——金融領(lǐng)域7.1.4數(shù)據(jù)挖掘應(yīng)用777.2決策樹定義分類與作用常用算法剪枝7.2決策樹定義787.2.1決策樹定義理解什么是決策樹，決策樹有什么作用之前，我們先給出一個決策樹的基本結(jié)構(gòu)。它的形狀是一棵倒置的樹，包括節(jié)點和分支。有三種類型的節(jié)點：父節(jié)點、內(nèi)部節(jié)點和葉節(jié)點。圖7-2.決策樹示意圖7.2.1決策樹定義理解什么是決策樹，決策樹有什么作用之前，797.2.1決策樹定義決策樹(DecisionTree)是一種以實例為基礎(chǔ)的歸納學(xué)習(xí)算法，是一種從無次序、無規(guī)則的訓(xùn)練樣本集中推理出決策樹表示形式的分類規(guī)則的方法，它提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。工作過程：圖7-3.決策樹工作過程7.2.1決策樹定義決策樹(DecisionTree)是一807.2.2決策樹分類與作用決策樹主要應(yīng)用于分類預(yù)測。分類預(yù)測的結(jié)果有定性和定量兩種。例如，預(yù)測天氣，定性有下雨或不下雨；定量則是下多少雨，具體的數(shù)值。在實際應(yīng)用中，我們將定性的分類預(yù)測稱為分類，用來確定類別屬性；定量的分類預(yù)測成為預(yù)測，用來預(yù)測具體的數(shù)值。分類是一種重要的數(shù)據(jù)挖掘技術(shù)。分類的目的是根據(jù)數(shù)據(jù)集的特點構(gòu)造一個分類函數(shù)或分類模型（也常常稱作分類器），該模型能把未知類別的樣本映射到給定類別中的某一個。因此，決策樹可以分為兩類：分類決策樹，簡稱分類樹，實現(xiàn)對分類型輸出變量的分類；回歸決策樹，簡稱回歸樹，完成對數(shù)值型輸出變量的預(yù)測。7.2.2決策樹分類與作用決策樹主要應(yīng)用于分類預(yù)測。分類預(yù)測817.2.2決策樹常用算法決策樹的兩大核心問題：決策樹的生長：在樣本數(shù)據(jù)中選擇哪一個屬性作為根節(jié)點，然后如何分支，如何選擇內(nèi)部節(jié)點，直到生長出樹葉，即到達葉節(jié)點，這一系列過程可稱為決策樹的分枝準(zhǔn)則，即具體算法；決策樹的剪枝：防止決策樹生長過于茂盛，無法適應(yīng)實際應(yīng)用的需要。7.2.2決策樹常用算法決策樹的兩大核心問題：827.2.2決策樹常用算法決策樹常用算法：基于信息論的方法：ID系列算法C4.5C5.0最小GINI指標(biāo)的方法：

CART

SLIQSPRINT決策樹剪枝方法：預(yù)修剪(Pre-Pruning)后修剪(Post-Pruning)7.2.2決策樹常用算法決策樹常用算法：837.2.2決策樹常用算法決策樹常用算法——ID3算法1986年，J.R.Quinlan提出了ID3(IterativeDichotomizer)算法。該算法是以信息論為基礎(chǔ)，運用信息熵理論，采用自頂向下的貪心搜索算法。其核心思想是在決策樹中各級節(jié)點上選擇分裂屬性。用信息增益作為屬性選擇的標(biāo)準(zhǔn)，使每個非葉子節(jié)點測試時，能獲得關(guān)于被測試例子最大的類別信息。使用該屬性將訓(xùn)練樣本集分成子集后，系統(tǒng)的信息熵值最小。7.2.2決策樹常用算法決策樹常用算法——ID3算法847.2.2決策樹常用算法決策樹常用算法——ID3算法信息熵與信息增益信息論之父申農(nóng)（C.E.Shannonm）把信息中排除了冗余后的平均信息量稱為“信息熵”，并給出了計算信息熵的數(shù)學(xué)表達式，他把信息熵定義為離散隨機事件的出現(xiàn)概率。總而言之，信息熵的基本作用就是消除人們對事物的不確定性。ID3算法根據(jù)信息論，采用劃分后樣本集的不確定性作為衡量劃分好壞的標(biāo)準(zhǔn)，用信息增益度量，信息增益值越大，不確定性越小。因此，算法在每個非葉子節(jié)點選擇信息增益最大的屬性作為分裂屬性。7.2.2決策樹常用算法決策樹常用算法——ID3算法857.2.2決策樹常用算法

7.2.2決策樹常用算法

867.2.2決策樹常用算法

7.2.2決策樹常用算法

877.2.2決策樹常用算法

7.2.2決策樹常用算法

8889Example(ID3信息增益)n=16

n1=4

I(16,4)=-((4/16)*log2(4/16)+(12/16)*log2(12/16))=0.8113E(年齡)=(6/16)*I(6,1)+(10/16)*I(10,3)=0.7946Gain(年齡)=I(16,4)-E(年齡)=0.0167Gain(年齡)=0.0167Gain(性別)=0.0972Gain(家庭所得)=0.0177Max:作為第一個分類依據(jù)圖7-4a.ID3工作過程示意圖a24Example(ID3信息增益)n=16

n1=8990Gain(家庭所得)=0.688Example(續(xù))I(7,3)=-((3/7)*log2(3/7)+(4/7)*log2(4/7))=0.9852Gain(年齡)=0.9852Gain(年齡)=0.2222I(9,1)=-((1/9)*log2(1/9)+(8/9)*log2(8/9))=0.5032Gain(家庭所得)=0.5032圖7-4b.ID3工作過程示意圖b25Gain(家庭所得)=0.688Example(續(xù))I(9091Example(end)ID3算法分類規(guī)則IF性別=FemaleAND家庭所得=

低所得THEN購買RV房車=否IF性別=FemaleAND家庭所得=

小康THEN購買RV房車=否IF性別=FemaleAND家庭所得=

高所得THEN購買RV房車=是IF性別=MaleAND年齡<35

THEN購買RV房車=否IF性別=MaleAND年齡≧35

THEN購買RV房車=是資料DecisionTree圖7-4c.ID3工作過程示意圖c26Example(end)ID3算法分類規(guī)則資料Deci917.2.2決策樹常用算法決策樹常用算法——C5.0算法C4.5算法在ID3算法的基礎(chǔ)上進行了改進，增加了對連續(xù)屬性的離散型的處理。對于預(yù)測變量的缺值處理、剪枝技術(shù)、派生規(guī)則等方面作了較大改進，既適合于分類問題，又適合于回歸問題。而C5.0則是在C4.5的基礎(chǔ)上改進了執(zhí)行效率和內(nèi)存使用，應(yīng)用于大數(shù)據(jù)集的分類算法。它采用Boosting方式來提高模型準(zhǔn)確率。決策樹是用樣本的屬性作為結(jié)點，用屬性的取值作為分枝的樹結(jié)構(gòu)的。屬性的度量標(biāo)準(zhǔn)有很多，C5.0采用信息增益率作為屬性的度量標(biāo)準(zhǔn)。7.2.2決策樹常用算法決策樹常用算法——C5.0算法927.2.2決策樹常用算法決策樹常用算法——C5.0算法（1）信息增益率在1993年J．R．Quinlan提出信息增益率。信息增益率克服了在計算信息增益時偏向于選擇取值較多的屬性的缺點，能夠在樹的生成中或完成后對樹進行剪枝。信息增益率的計算公式如下式：其中，

是屬性A的信息熵。7.2.2決策樹常用算法決策樹常用算法——C5.0算法937.2.2決策樹常用算法決策樹常用算法——C5.0算法（2）Boosting技術(shù)Boosting是一種提高任意給定學(xué)習(xí)算法準(zhǔn)確度的方法。在C5.0中是用來提高模型準(zhǔn)確度的。Boosting中最基本的是Adaboost算法，其他算法的主要原理都差不多，只是實現(xiàn)手段或者說采用的數(shù)學(xué)公式不同。Adaboost算法在現(xiàn)實生活中的經(jīng)典使用領(lǐng)域就是用于人臉識別。圖7-5.基于Adaboost算法的人臉識別示意圖7.2.2決策樹常用算法決策樹常用算法——C5.0算法圖7-947.2.2決策樹常用算法決策樹常用算法——CART算法它是由統(tǒng)計學(xué)家L.Breiman，J.Friedman，R.Olshen和C.Stone在出版的著作《分類與回歸樹》中提出的一種產(chǎn)生二叉決策樹分類模型的技術(shù)。它與前面Quinlan提出的ID系列算法和C4.5不同的是，它使用的屬性度量標(biāo)準(zhǔn)是Gini指標(biāo)。CART與C4.5/C5.0算法的最大相異之處是其在每一個節(jié)點上都是采用二分法，也就是一次只能夠有兩個子節(jié)點，C4.5/5.0則在每一個節(jié)點上可以產(chǎn)生不同數(shù)量的分枝。CART模型適用于目標(biāo)變量為連續(xù)型和類別型的變量，如果目標(biāo)變量是類別型變量，則可以使用分類樹（classificationtrees），目標(biāo)變量是連續(xù)型的，則可以采用回歸樹（regressiontrees）。7.2.2決策樹常用算法決策樹常用算法——CART算法957.2.2決策樹常用算法決策樹常用算法——CART算法Gini指標(biāo)Gini指標(biāo)主要是度量數(shù)據(jù)劃分或訓(xùn)練數(shù)據(jù)集D的不純度為主，系數(shù)值的屬性作為測試屬性，Gini值越小，表明樣本的“純凈度”越高。Gini指標(biāo)的計算公式如下式：其中Pi是類別Ci在D中出現(xiàn)的概率。如果集合T分成兩部分N1andN2。則此分割的Gini就是：提供最小Ginisplit就被選擇作為分割的標(biāo)準(zhǔn)(對于每個屬性都要經(jīng)過所有可以的分割方法)。7.2.2決策樹常用算法決策樹常用算法——CART算法96Example(Gini)例：顧客數(shù)據(jù)庫/訓(xùn)練數(shù)據(jù)D例中，預(yù)測變量為buycomp,是否購買電腦。Age\income\student\cred都為非連續(xù)變量。

對于離散性屬性，選擇該屬性產(chǎn)生最小的Gini指標(biāo)的子集作為它的分裂子集；對于連續(xù)值屬性，必須考慮每個可能的分裂點，選擇某一分裂點導(dǎo)致最小的Gini指標(biāo)。樣本D中：10（yes），4（no）D的不純度為按下列公式：為找出D中元組的分裂準(zhǔn)則，需要計算每個屬性的Gini指標(biāo)。對age的二元分組可以有：取其中2個一組，剩下的一組同樣對income的二元分組可以有：取其中2個一組，剩下的一組Example(Gini)例：顧客數(shù)據(jù)庫/訓(xùn)練數(shù)據(jù)D97Example(Gini)“income∈{low,medium}，形成D1，8（yes),2(no)“income∈{high}，形成D2，2（yes),2(no)例如：income屬性，假設(shè)考慮子集｛low，medium},這將D中的元組二元劃分。D中的元組10個元組滿足條件“income∈{low,medium}，形成D1，其余的4組劃分到D2，income∈{high}.同樣可計算得出：Example(Gini)“income∈{low,med987.2.2決策樹常用算法剪枝現(xiàn)實世界的數(shù)據(jù)一般不可能是完美的，可能某些屬性字段上缺值；可能缺少必要的數(shù)據(jù)而造成數(shù)據(jù)不完整；可能數(shù)據(jù)不準(zhǔn)確、含有噪聲甚至是錯誤的?；镜臎Q策樹構(gòu)造算法沒有考慮噪聲，因此生成的決策樹完全與訓(xùn)練例子擬合。在有噪聲情況下，完全擬合將導(dǎo)致過分擬合，即對訓(xùn)練數(shù)據(jù)的完全擬合反而使對現(xiàn)實數(shù)據(jù)的分類預(yù)測性能下降。剪枝是一種克服噪聲的基本技術(shù)，同時它也能使樹得到簡化而變得更容易理解。7.2.2決策樹常用算法剪枝997.2.2決策樹常用算法決策樹剪枝方法——前剪枝前期剪枝(Forward-Pruning)是提前停止樹的構(gòu)造而對樹進行剪枝。停止決策樹的生長的方法大體上可以歸納為以下幾種：在決策樹到達一定高度的情況下就停止樹的生長；到達此結(jié)點的實例具有相同的特征向量，而不必一定屬于同一類，也可停止生長；到達此結(jié)點的實例個數(shù)小于某一個閾值也可停止樹的生長；計算每次擴張對系統(tǒng)性能的增益，如果這個增益值小于某個閾值則不進行擴展；如果在最好情況下的擴展增益都小于閾值，即使有些葉子結(jié)點的實例不屬于同一類，也停止樹的增長。7.2.2決策樹常用算法決策樹剪枝方法——前剪枝1007.2.2決策樹常用算法決策樹剪枝方法——后剪枝后剪枝(Post-Pruning)首先構(gòu)造完整的決策樹，允許決策樹過度擬合訓(xùn)練數(shù)據(jù)，然后對那些置信度不夠的結(jié)點的子樹用葉子結(jié)點來替代，這個葉子結(jié)點所應(yīng)標(biāo)記的類別為子樹中大多數(shù)實例所屬的類別。ID3算法、C5.0算法和CART算法都是先建樹再剪枝，屬于后剪枝。后剪枝方法現(xiàn)在得到比較廣泛地使用。常用的后剪枝算法有：CCP(CostComplexityPruning)REP(ReducedErrorPruning)PEP(PessimisticErrorPruning)MEP(MinimumErrorPruning)7.2.2決策樹常用算法決策樹剪枝方法——后剪枝1017.3關(guān)聯(lián)規(guī)則定義分類算法原理常用算法7.3關(guān)聯(lián)規(guī)則定義1027.3關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則主要用于發(fā)現(xiàn)大量數(shù)據(jù)之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。關(guān)聯(lián)規(guī)則挖掘的一個典型例子是購物籃分析除此以外，關(guān)聯(lián)規(guī)則分析還可以應(yīng)用于客戶交叉營銷、風(fēng)險防范等方面。例如，為了高效率地營銷信用卡業(yè)務(wù)，營銷人員可以通過關(guān)聯(lián)規(guī)則的分析，在眾多銀行產(chǎn)品客戶中選擇可信度較高的群體進行交叉營銷，如基金客戶、外匯交易客戶等。圖7-6.關(guān)聯(lián)規(guī)則工作過程示意圖7.3關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則主要用于發(fā)現(xiàn)大量數(shù)據(jù)之間有趣的關(guān)聯(lián)或相1037.3.1關(guān)聯(lián)規(guī)則定義

7.3.1關(guān)聯(lián)規(guī)則定義

1047.3.1關(guān)聯(lián)規(guī)則定義

7.3.1關(guān)聯(lián)規(guī)則定義

1057.3.2關(guān)聯(lián)規(guī)則分類⑴

基于規(guī)則中處理變量的類型，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。布爾型考慮的是項集的存在與否，而數(shù)值型則是量化的關(guān)聯(lián)。⑵

基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。⑶

基于規(guī)則中涉及到的數(shù)據(jù)維數(shù)，可以分為單維關(guān)聯(lián)規(guī)則和多維關(guān)聯(lián)規(guī)則。7.3.2關(guān)聯(lián)規(guī)則分類⑴基于規(guī)則中處理變量的類型，關(guān)聯(lián)規(guī)則1067.3.3關(guān)聯(lián)規(guī)則算法原理原理關(guān)聯(lián)規(guī)則的挖掘就是在事務(wù)數(shù)據(jù)庫D中找出具有用戶給定的最小支持度（MinimumSupport,minsup）和最小置信度(MinimumConfidence,minconf)的關(guān)聯(lián)規(guī)則。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集或大項集。步驟Step1根據(jù)最小支持度閾值找出數(shù)據(jù)集D中所有頻繁項目集；Step2根據(jù)頻繁項目集和最小置信度閾值產(chǎn)生所有關(guān)聯(lián)規(guī)則。7.3.3關(guān)聯(lián)規(guī)則算法原理原理1077.3.3關(guān)聯(lián)規(guī)則算法原理基本模型算法1算法2數(shù)據(jù)集規(guī)則用戶最小支持度最小置信度圖7-7.關(guān)聯(lián)規(guī)則挖掘的基本模型7.3.3關(guān)聯(lián)規(guī)則算法原理基本模型算法1算法2數(shù)據(jù)集規(guī)則用1087.3.3關(guān)聯(lián)規(guī)則算法原理基本算法搜索算法分層算法(寬度優(yōu)先算法)深度優(yōu)先算法劃分算法抽樣算法7.3.3關(guān)聯(lián)規(guī)則算法原理基本算法1097.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——介紹Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。Apriori算法——兩大缺點一是可能產(chǎn)生大量的候選集；二是可能需要重復(fù)掃描數(shù)據(jù)庫。7.3.4關(guān)聯(lián)規(guī)則常用算法1107.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——基本思路Apriori算法使用頻繁項集的先驗知識（稱為逐層搜索的迭代方法），k項集用于探索(k+1)項集。首先，通過掃描事務(wù)（交易）記錄，找出所有的頻繁1項集，該集合記做L1，然后利用L1找頻繁2項集的集合L2，L2找L3，如此下去，直到不能再找到任何頻繁k項集。最后再在所有的頻繁集中找出強規(guī)則，即產(chǎn)生用戶感興趣的關(guān)聯(lián)規(guī)則。7.3.4關(guān)聯(lián)規(guī)則常用算法1117.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——剪枝步Ck是Lk的超集，也就是說，Ck的成員可能是也可能不是頻繁的。通過掃描所有的事務(wù)（交易），確定CK中每個候選的計數(shù)，判斷是否小于最小支持度計數(shù)，如果不是，則認為該候選是頻繁的。為了壓縮Ck,可以利用Apriori性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的；反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。7.3.4關(guān)聯(lián)規(guī)則常用算法1127.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——連接步為找出Lk（所有的頻繁k項集的集合），通過將Lk-1（所有的頻繁k-1項集的集合）與自身連接產(chǎn)生候選k項集的集合。候選集合記作Ck。設(shè)l1和l2是Lk-1中的成員。記li[j]表示li中的第j項。假設(shè)Apriori算法對事務(wù)或項集中的項按字典次序排序，即對于（k-1）項集li，li[1]<li[2]<…<li[k-1]。將Lk-1與自身連接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&…&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那認為l1和l2是可連接。連接l1和l2產(chǎn)生的結(jié)果是{l1[1],l1[2],…,l1[k-1],l2[k-1]}。7.3.4關(guān)聯(lián)規(guī)則常用算法1137.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——連接步為找出Lk（所有的頻繁k項集的集合），通過將Lk-1（所有的頻繁k-1項集的集合）與自身連接產(chǎn)生候選k項集的集合。候選集合記作Ck。設(shè)l1和l2是Lk-1中的成員。記li[j]表示li中的第j項。假設(shè)Apriori算法對事務(wù)或項集中的項按字典次序排序，即對于（k-1）項集li，li[1]<li[2]<…<li[k-1]。將Lk-1與自身連接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&…&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那認為l1和l2是可連接。連接l1和l2產(chǎn)生的結(jié)果是{l1[1],l1[2],…,l1[k-1],l2[k-1]}。7.3.4關(guān)聯(lián)規(guī)則常用算法1147.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——實例上表7-1某商場的交易記錄，共有9個事務(wù)。交易ID商品ID列表T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I37.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——實例交易ID1157.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——實例利用Apriori算法求得所有的頻繁項集過程如下圖：圖7-8.關(guān)聯(lián)規(guī)則Apriori算法實例7.3.4關(guān)聯(lián)規(guī)則常用算法Apriori算法——實例圖7-81167.3.4關(guān)聯(lián)規(guī)則常用算法FP-Tree算法——介紹FP-Growth算法是韓家煒老師在2000年提出的關(guān)聯(lián)分析算法，它采取如下分治策略：將提供頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（FrequentPattern-growth,FP-Tree），但仍保留項集關(guān)聯(lián)信息。FP-Tree算法與Apriori算法的區(qū)別一是FP-Tree不