第三章+分類和預(yù)測-20140923

04二月2023DataMining:ConceptsandTechniques1

第三章分類與預(yù)測軟件工程系鄭皎凌04二月2023DataMining:ConceptsandTechniques2分類和預(yù)測什么是分類,什么是預(yù)測用決策樹歸納分類分類名字體溫胎生…類別鴕鳥恒溫否…非哺乳動物海豚恒溫是…非哺乳動物……………分類04二月2023DataMining:ConceptsandTechniques8分類和預(yù)測是兩種數(shù)據(jù)分析方式，用來提取重要數(shù)據(jù)類或預(yù)測未來的數(shù)據(jù)趨勢的模型。分類:預(yù)測分類標號（離散，無序的）基于訓(xùn)練集和分類屬性的值(類標號)對組成一個模型的數(shù)據(jù)進行分類,并將其用在對新的數(shù)據(jù)進行分類上預(yù)測:對連續(xù)值函數(shù)建模,比如預(yù)測未知或者遺失的值典型應(yīng)用信貸審批目標營銷醫(yī)學(xué)診斷治療效果分析分類VS預(yù)測預(yù)測04二月2023DataMining:ConceptsandTechniques10分類是一個兩步過程構(gòu)建模型(分類器):

描述預(yù)先定義的數(shù)據(jù)類或概念集假定每個元組都屬于一個預(yù)先定義的類,由稱作類標號屬性的數(shù)據(jù)庫屬性確定用來構(gòu)建模型的元組的集合叫做訓(xùn)練集模型可以表示成分類規(guī)則,決策樹或者數(shù)學(xué)公式使用模型:

對未來和未知的目標進行分類估計模型的準確率使用模型的分類結(jié)果來和測試樣本的已知標簽進行比較準確率是被模型正確分類的檢驗元組所占的百分比檢驗集獨立于訓(xùn)練元組,否則就會發(fā)生過分擬合(即在學(xué)習(xí)期間,它可能并入了訓(xùn)練數(shù)據(jù)中的某些特殊的異常點,這些異常不再一般數(shù)據(jù)集中出現(xiàn))04二月2023DataMining:ConceptsandTechniques11預(yù)測是一個兩步過程該過程類似于分類過程。沒有類標號屬性，因為預(yù)測的屬性值是連續(xù)值（有序的）。同樣使用獨立的檢驗集來評估預(yù)測的準確率。04二月2023DataMining:ConceptsandTechniques12分類和預(yù)測什么是分類,什么是預(yù)測用決策樹歸納分類04二月2023DataMining:ConceptsandTechniques13第6章分類和預(yù)測什么是分類,什么是預(yù)測用決策樹歸納分類分類04二月2023DataMining:ConceptsandTechniques16顧客數(shù)據(jù)庫類標記的訓(xùn)練元組

04二月2023DataMining:ConceptsandTechniques17輸出:對應(yīng)“buys_computer”的一個決策樹age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..4004二月202318、30熵后面直觀例子說明

entropy(S)=– purity(S1,S2,…..,Sr)=

Information-gain(S,{S1,S2,….,Sr)=

purity(S)–purity(S1,S2,…Sr)ri=1|Si||S|purity(Si)ki-1pilog2pi04二月202319、30補充熵概念用8=23個字符（a1,..a8)寫密碼信,需要壓縮編碼，節(jié)約資源用huffman編碼，編碼長度與使用頻度反比，用得頻繁的碼長短，設(shè)8各字符出現(xiàn)的為頻率分布如表。編碼如下頁字符頻率A1?A2?A31/8A41/8A51/16A61/16A71/16A81/16補充熵概念字符頻率編碼碼長計算A1P1=1/4002-Log2(P1)A2P2=1/4022-Log2(P2)A3P3=1/81003-Log2(P3)A4P4=1/81013-Log2(P4)A5P5=1/1610014-Log2(P5)A6P6=1/1610104-Log2(P6)A7P7=1/1610114-Log2(P7)A8P8=1/1611004-Log2(P8)04二月202320、30最小平均碼長（加權(quán)平均）長度越大加權(quán)越小=-Pilog2(Pi)=2.75bit用它作為信息量的度量是合理的。稱為熵。是分布不均勻度或混亂程度的度量記為H(A1,,…,A8)性質(zhì)0<H(X<log2(N)04二月202321、30補充熵概念當8個字符均勻分布，每個字符出現(xiàn)頻率為1/8,編碼從000—111,平均碼長為3，H=3(n個字符，平均為1/2n,H=n,可見n越大分布越平均

H越大。情況越混亂，熵H越大，要表達它所需要的平均碼長越大，直觀感覺：要說清混亂的事情，比較費口舌（費信息量）04二月2023DataMining:ConceptsandTechniques22信息增益(ID3)選擇具有最高信息增益的屬性作為分裂屬性假設(shè)有兩個類,P和N讓樣本集S包含類P的p個元素以及類N的n個元素識別S中一個樣本是否屬于P或N所需要的平均信息量為04二月2023DataMining:ConceptsandTechniques23決策樹歸納中的信息增益假定A為分裂屬性,集合D可以分裂為{D1,D2,…,Dv}，如果Di

包括P類的pi

個樣本以及N類的ni

個樣本,則D的熵(識別Si中元組的類標號所需要的平均信息量,是一個期望值)為

v是屬性A具有的不同值的個數(shù)根據(jù)屬性A劃分的信息增益為04二月2023DataMining:ConceptsandTechniques24用決策樹歸納分類決策樹一種類似于流程圖的樹結(jié)構(gòu)每個內(nèi)部節(jié)點(非樹葉節(jié)點)表示在一個屬性上的測試每個分枝代表一個測試輸出每個葉節(jié)點存放一個類標號決策樹的生成包括兩個步驟樹的構(gòu)建開始時,所有的訓(xùn)練樣本都位于根節(jié)點基于選定的屬性對樣本進行遞歸分裂樹剪枝識別并剪去反映噪聲或離群點的分枝識別使用決策樹:對未知樣本進行分類04二月2023DataMining:ConceptsandTechniques25顧客數(shù)據(jù)庫類標記的訓(xùn)練元組

04二月2023DataMining:ConceptsandTechniques26輸出:對應(yīng)“buys_computer”的一個決策樹age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..4004二月2023DataMining:ConceptsandTechniques27信息增益(ID3)選擇具有最高信息增益的屬性作為分裂屬性假設(shè)有兩個類,P和N讓樣本集S包含類P的p個元素以及類N的n個元素識別S中一個樣本是否屬于P或N所需要的平均信息量為04二月2023DataMining:ConceptsandTechniques28決策樹歸納中的信息增益假定A為分裂屬性,集合D可以分裂為{D1,D2,…,Dv}，如果Di

包括P類的pi

個樣本以及N類的ni

個樣本,則D的熵(識別Si中元組的類標號所需要的平均信息量,是一個期望值)為

v是屬性A具有的不同值的個數(shù)根據(jù)屬性A劃分的信息增益為04二月2023DataMining:ConceptsandTechniques29顧客數(shù)據(jù)庫類標記的訓(xùn)練元組

04二月2023DataMining:ConceptsandTechniques30信息增益計算的屬性選擇類P:buys_computer=“yes”類N:buys_computer=“no”I(p,n)=I(9,5)=0.940計算age:的熵因此類似地04二月2023DataMining:ConceptsandTechniques31屬性選擇度量信息增益

(ID3)所有屬性都假定為包含的信息量為最小可以度量連續(xù)值屬性增益率(C4.5)使用分裂信息值將信息增益規(guī)范化Gini指標所有屬性都假定為連續(xù)值對于每個屬性,假定存在幾個不同的分裂值可能需要其他工具,比如聚類,來得到可能的分裂值04二月2023DataMining:ConceptsandTechniques32信息增益對于連續(xù)值的處理必須確定分裂屬性A的”最佳”分裂點,其中分裂點是A上的閾值.將A的值按增序排序.典型的,每對相鄰值的中點都可以看作為可能的分裂點.給點A的v個值,則需要計算v-1個可能的分裂.選擇具有最小期望信息需求的點作為A的分裂點.

04二月2023DataMining:ConceptsandTechniques33增益率（C4.5）信息增益趨向于選擇具有大量值的屬性,比如針對product_ID這個充當唯一標識的屬性,很容易導(dǎo)致大量劃分,每個只包含一個分組,每個劃分都是純的,則E(product_id)=0.這種劃分對于分類沒用增益率的引入:使用分裂信息值將信息增益規(guī)范化,分裂信息值定義為:

04二月2023DataMining:ConceptsandTechniques34該值代表通過將訓(xùn)練數(shù)據(jù)集D劃分成對應(yīng)于屬性A測試的v個輸出的v個劃分產(chǎn)生的信息.對于每個輸出,它關(guān)于D中元組總數(shù)考慮具有該輸出的元組數(shù).04二月2023DataMining:ConceptsandTechniques3504二月2023DataMining:ConceptsandTechniques36顧客數(shù)據(jù)庫類標記的訓(xùn)練元組

04二月2023DataMining:ConceptsandTechniques37例子:屬性income的增益率計算屬性income將數(shù)據(jù)分為三類:low,medium,high,分別包含4,6,4個元組.

因此.GainRatio(income)=0.029/1.557=0.01904二月2023DataMining:ConceptsandTechniques38

Gini

指標如果數(shù)據(jù)集T

來自n個類的樣本,則gini指標,gini(T)定義為

其中pj

是T中元組屬于j類的概率.如果數(shù)據(jù)集T分裂成T1

和T2,各自大小分別為N1

和N2,分裂數(shù)據(jù)的gini指標包含來自N個類的樣本,則gini指標gini(T)定義為選擇具有最小gini指標ginisplit(T)的屬性作為分裂屬性(對于每個屬性都需要枚舉所有可能的分裂節(jié)點).對于連續(xù)值的處理,類似于信息增益04二月2023DataMining:ConceptsandTechniques39顧客數(shù)據(jù)庫類標記的訓(xùn)練元組

04二月2023DataMining:ConceptsandTechniques40使用Gini指標進行決策樹歸納假定D是表中的訓(xùn)練數(shù)據(jù),其中屬于類buys_cpmputer=yes的元組有9個,另外5個屬于類buys_cpmputer=no.首先,使用gini指標式計算D的不純度04二月2023DataMining:ConceptsandTechniques41

Gini指標考慮每個屬性的二元劃分,因此需要從income開始考慮每個可能的分裂子集.

考慮子集{low,medium}.則表中有10個元組滿足條件”income屬于{low,medium}”,劃分到D1,其余4個被劃分到D2.基于該劃分的Gini指標值04二月2023DataMining:ConceptsandTechniques42類似的,對其余子集分裂的Gini指標值是:0.456(子集{low,high}和{medium})和0.450(子集{medium,high}和{low}).可以看出,屬性income的最好二元劃分在{low,medium}(或{high})上.可以采用同樣的方法分別對屬性age,student以及credit_rating進行評估.在產(chǎn)生的所有Gini指標值中,選擇最小的,則使用對應(yīng)的屬性作為分裂屬性.04二月2023DataMining:ConceptsandTechniques43決策樹歸納的算法基本算法

（相當直接）決策樹以自頂而下遞歸的分治方式構(gòu)造從訓(xùn)練元組集和他們相關(guān)聯(lián)的類標號開始構(gòu)造決策樹分裂屬性包含的信息量最小(如果是連續(xù)值,應(yīng)該事先對其離散化)通過分裂準則（由attribute_selection_method確定）來確定分裂屬性基于選定的屬性對樣本進行遞歸劃分停止分裂的條件對于一個給定節(jié)點,其所有樣本都屬于同一個類沒有剩余屬性可以用來進一步劃分元組,在此情況下,使用多數(shù)表決，即標記為多數(shù)類。給定的分枝沒有元組04二月2023DataMining:ConceptsandTechniques44樹剪枝:避免分類中產(chǎn)生的過分擬合問題生成樹可能對訓(xùn)練數(shù)據(jù)產(chǎn)生過分擬合產(chǎn)生過多的分枝,其中一些因為噪聲或離群點而產(chǎn)生異常對于未知樣本的預(yù)測,該結(jié)果準確率很低避免過分擬合的兩種方法先剪枝:通過提前停止樹的構(gòu)造而對樹剪枝很難選取一個合適的閾值后剪枝:由完全生成的樹剪去子樹.通過刪除節(jié)點的分枝并用樹葉替換它而剪掉給定節(jié)點的子樹.樹葉用被替換的子樹中最頻繁的類標記04二月2023DataMining:ConceptsandTechniques45CART使用的代價復(fù)雜度剪枝算法是后剪枝算法的一個實例將樹的代價復(fù)雜度看作樹中樹葉節(jié)點的個數(shù)和樹的錯誤率（錯誤率是樹誤分類的元組所占的百分比）的函數(shù)從樹的底部開始，對于每個內(nèi)部節(jié)點N，計算N處子樹的代價復(fù)雜度和該處剪枝后N處子樹（即用一個樹葉節(jié)點替換）的代價復(fù)雜度。對兩個值進行比較，如果剪枝后產(chǎn)生較小的代價復(fù)雜度，則剪去該子樹，否則保留。最小化代價復(fù)雜度的最小決策樹是首選04二月2023DataMining:ConceptsandTechniques46處理樹剪枝后可能遇到的重復(fù)和復(fù)制問題剪枝后的樹仍然可能很大，很復(fù)雜沿著樹中一個給定的分枝反復(fù)的測試一個屬性時就會遇到重復(fù)，比如測試age<60后接著測試age<45復(fù)制是指樹中存在重復(fù)的子樹重復(fù)和復(fù)制影響了決策樹的準確率和可解釋性?？梢允褂枚嘣至眩ɑ趯傩约系姆至眩┮约安煌问降闹R表示（如規(guī)則），來防止該問題出現(xiàn)04二月2023DataMining:ConceptsandTechniques47可伸縮性與決策樹歸納ID3，C4.5，CART的有效性都是為相對較小的數(shù)據(jù)集設(shè)計的。面臨超大型現(xiàn)實世界的數(shù)據(jù)庫的挖掘時，大部分情況下，訓(xùn)練數(shù)據(jù)都不能放在主存中。訓(xùn)練樣本在主存和高速緩存中的換進換出，產(chǎn)生低效率。因此需要更加可伸縮的方法。04二月2023DataMining:ConceptsandTechniques48可伸縮性與決策樹歸納SLIQ

對每個屬性構(gòu)建一個索引，只有類列表和當前屬性列表駐留在內(nèi)存SPRINT

使用屬性列表數(shù)據(jù)結(jié)構(gòu)存放類和RID信息。BOAT不基于特殊數(shù)據(jù)結(jié)構(gòu)的使用，而使用統(tǒng)計學(xué)技術(shù)（自助法）。RainForest

適應(yīng)可用的內(nèi)存量，并用于任意決策樹歸納算法在每個樹節(jié)點，對每個屬性維護一個AVC集(Attribute,Value,Classlabel),描述該節(jié)點的訓(xùn)練元組。04二月2023DataMining:ConceptsandTechni