數(shù)據(jù)挖掘決策樹

數(shù)據(jù)挖掘決策樹第1頁，共47頁，2023年，2月20日，星期五內(nèi)容提要4.1引言4.2構(gòu)造分類樹4.3剪枝導(dǎo)論4.4模型評估

第2頁，共47頁，2023年，2月20日，星期五4.1引言分類樹是使用樹結(jié)構(gòu)算法將數(shù)據(jù)分成離散類的方法。Breiman在20世紀(jì)80年代早期創(chuàng)造了該術(shù)語。該技術(shù)在醫(yī)療、市場調(diào)查統(tǒng)計、營銷和顧客關(guān)系方面得到了很好的應(yīng)用。例如，一個樹結(jié)構(gòu)分類器使用血壓、年齡和先前的治療情況將心臟病患者分成危險和不危險兩類。另一種工具可能使用與年齡相關(guān)的變量和其他人口統(tǒng)計量決定誰應(yīng)該出現(xiàn)在郵件發(fā)送清單上。預(yù)測對直接郵寄廣告的反應(yīng)和確定控制電信業(yè)顧客流失的方法都是具體行業(yè)的應(yīng)用。第3頁，共47頁，2023年，2月20日，星期五決策樹作用(1)下表的數(shù)據(jù)提供了什么信息？第4頁，共47頁，2023年，2月20日，星期五決策樹作用(2)決策樹的主要作用是揭示數(shù)據(jù)中的結(jié)構(gòu)化信息。決策樹匯總了數(shù)據(jù)，并揭示了其中隱藏的結(jié)構(gòu)：規(guī)則：如果血壓高，則采用藥物A。如果血壓低，則采用藥物B。如果血壓正常。年齡小于或等于40，則采用藥物A，否則采用藥物B。第5頁，共47頁，2023年，2月20日，星期五準(zhǔn)確率、支持度、錯誤率該例得到的規(guī)則和對應(yīng)的準(zhǔn)確率和支持度是：如果血壓高，則采用藥物A(準(zhǔn)確率100％，支持度3／12)。如果血壓低，則采用藥物B(準(zhǔn)確率100％，支持度3／12)。如果血壓正常并且年齡小于或等于40，則采用藥物A(準(zhǔn)確率100％，支持度3／12)。如果血壓正常并且年齡大于40。則采用藥物B(準(zhǔn)確率100％，支持度3／12)。第6頁，共47頁，2023年，2月20日，星期五樹生長的策略對于樹生長的策略，算法主要考慮的問題：選擇分裂變量的標(biāo)準(zhǔn)。找到被選擇的變量的分裂點(diǎn)的標(biāo)準(zhǔn)(連續(xù)變量情況)。確定何時停止樹生長過程的標(biāo)準(zhǔn)。第7頁，共47頁，2023年，2月20日，星期五決策樹的分類目標(biāo)變量和預(yù)測變量決策樹根據(jù)目標(biāo)變量的類型可分成分類樹與回歸樹如果目標(biāo)變量(也稱為響應(yīng)變量或類變量)是標(biāo)稱／分類變量(如處方藥)，則稱該樹為分類樹(classificationtree)。如果目標(biāo)變量是連續(xù)的(如“收入”)，則稱該樹為回歸樹(regressiontree)。第8頁，共47頁，2023年，2月20日，星期五預(yù)測變量分類預(yù)測變量也可以一般地分為標(biāo)稱的或連續(xù)的。連續(xù)值變量的處理，大部分實際算法在構(gòu)造樹之前先將連續(xù)值變量轉(zhuǎn)換成具有離散層次(或區(qū)間)的變量。第9頁，共47頁，2023年，2月20日，星期五4.2構(gòu)造分類樹4.2.1用于標(biāo)稱屬性的lD3算法ID3代表歸納決策樹(inductiondecision—tree)版本3，它是一種用來由數(shù)據(jù)構(gòu)造決策樹的遞歸過程。第10頁，共47頁，2023年，2月20日，星期五lD3算法的步驟試探性地選擇一個屬性放置在根節(jié)點(diǎn)，并對該屬性的每個值產(chǎn)生一個分支。分裂根節(jié)點(diǎn)上的數(shù)據(jù)集，并移到子女節(jié)點(diǎn)，產(chǎn)生一棵局部樹(partialtree)。對該劃分的質(zhì)量進(jìn)行評估。對其他屬性重復(fù)該過程。每個用于劃分的屬性產(chǎn)生一棵局部樹。根據(jù)局部樹的質(zhì)量，選擇一棵局部樹。對選定的局部樹的每個子女節(jié)點(diǎn)重復(fù)以上1-6步。這是一個遞歸過程。如果一個節(jié)點(diǎn)上的所有實例都具有相同的類，則停止局部樹的生長。第11頁，共47頁，2023年，2月20日，星期五氣象數(shù)據(jù)集示例(1)第12頁，共47頁，2023年，2月20日，星期五第13頁，共47頁，2023年，2月20日，星期五氣象數(shù)據(jù)集示例(2)有4個屬性，因此有4棵可能的局部樹，見圖4-3所示。哪一棵局部樹最好?葉節(jié)點(diǎn)上顯示了“yes”和“no”類的數(shù)目。只具有一個類(“yes”或“no”)的葉節(jié)點(diǎn)不必再進(jìn)一步劃分，并且到該分支的遞歸過程將結(jié)束。由于我們尋找小樹，因此希望停止劃分盡可能早地發(fā)生。如果我們具有節(jié)點(diǎn)純度的度量，那么應(yīng)當(dāng)選擇產(chǎn)生最純子女節(jié)點(diǎn)的屬性。第14頁，共47頁，2023年，2月20日，星期五氣象數(shù)據(jù)集示例(3)觀察4個圖，并仔細(xì)思索你認(rèn)為哪個屬性是最佳選擇。我們需要一種度量來度量節(jié)點(diǎn)的純度，并需要一種度量告訴我們根據(jù)一個變量的屬性值將一個不純的節(jié)點(diǎn)上的數(shù)據(jù)劃分到其子女后，純度提高了多少。最為廣泛使用的度量是信息熵。第15頁，共47頁，2023年，2月20日，星期五4.2.2信息論和信息熵信息論(informationtheory)是數(shù)學(xué)中的概率論和數(shù)理統(tǒng)計的一個分支，用于處理信息和信息熵、通信系統(tǒng)、數(shù)據(jù)傳輸率和失真理論、密碼學(xué)、信噪比、數(shù)據(jù)壓縮和相關(guān)課題。ClaudeShannon(1916--2001)被稱為信息論之父。他的理論“將信息傳輸看作一種統(tǒng)計學(xué)現(xiàn)象”，并且為通信工程師提供了一種方法，使用普通的二進(jìn)制位流確定通信信道的容量。該理論的信息傳輸并不“關(guān)注信息或消息內(nèi)容本身”第16頁，共47頁，2023年，2月20日，星期五熵(entropy)是源于熱力學(xué)的概念，隨后出現(xiàn)信息論中。熱力學(xué)熵(thermodynamicentropy)S(在化學(xué)和熱力學(xué)中簡稱熵)是物理系統(tǒng)中不能用來做功的能量的一種度量。它也是系統(tǒng)無序性的一種度量。第17頁，共47頁，2023年，2月20日，星期五在構(gòu)造決策樹的過程中，熵定義為無序性度量很合適。如果一個節(jié)點(diǎn)上的數(shù)據(jù)的類值在可能的類值上均勻分布，則稱節(jié)點(diǎn)的熵(無序性)最大。如果一個節(jié)點(diǎn)上的數(shù)據(jù)的類值對于所有數(shù)據(jù)都相同，則熵最小。通過分裂，我們希望得到盡可能純的節(jié)點(diǎn)。這相當(dāng)于降低系統(tǒng)的熵：1)當(dāng)一個節(jié)點(diǎn)上的“yes”或“no”的個數(shù)為零時，信息熵為零。2)當(dāng)一個節(jié)點(diǎn)上的“yes”和“no”的個數(shù)相等時，信息熵最大。這樣的節(jié)點(diǎn)是最不純的節(jié)點(diǎn)。第18頁，共47頁，2023年，2月20日，星期五信息值或熵熵函數(shù):單位是位(bit)第19頁，共47頁，2023年，2月20日，星期五4.2.3劃分的選擇信息增益（informationgain）是指期望信息或者信息熵的有效減少量（通常用“字節(jié)”衡量），根據(jù)它能夠確定在什么樣的層次上選擇什么樣的變量來分類。（百度）劃分的選擇：計算分類前的信息值info([9,5])=0.940位計算每一個分支的信息值info([2,3],[4,0],[3,2])=0.693位計算信息增益info([9,5])-info([2,3],[4,0],[3,2])=0.247位選擇獲得最大信息增益的屬性進(jìn)行劃分第20頁，共47頁，2023年，2月20日，星期五劃分過程的終止當(dāng)所有葉節(jié)點(diǎn)都是純的。因訓(xùn)練集包含兩個具有相同屬性集，但具有不同類的實例。第21頁，共47頁，2023年，2月20日，星期五4.2.4高分支屬性當(dāng)某些屬性具有大量可能值時，會導(dǎo)致具有許多子女節(jié)點(diǎn)的多路分支出現(xiàn)，信息增益的計算就會出現(xiàn)問題。例如，標(biāo)識碼(identification)屬性。信息值為0，增益最大第22頁，共47頁，2023年，2月20日，星期五增益率總體效果是：信息增益度量趨向于選擇具有大量可能值的屬性。作為補(bǔ)償，通常使用一種稱作增益率(gainratio)的度量變型。增益率通過考慮屬性劃分?jǐn)?shù)據(jù)集產(chǎn)生的子女節(jié)點(diǎn)的個數(shù)和大小，忽略關(guān)于類的信息導(dǎo)出。上例所有的計數(shù)值均為1，因此劃分信息值是

info([1,…,1])=-1/14xlog1/14x1/14=logl4或(3.807位)分支越多，該值越大。具有較高分支的屬性，該固有信息值較高。增益率，由信息增益除以該固有信息值得到。例：增益率值0.940/3.807=0.246

各屬性樹樁的計算結(jié)果見表4-7第23頁，共47頁，2023年，2月20日，星期五4.2.5從ID3到C4.5

決策樹歸納(有時也稱決策樹的自頂向下歸納)的分治技術(shù)由澳大利亞悉尼大學(xué)的RossQuinlan開發(fā)并經(jīng)過多年優(yōu)化。增益率的使用正是多年來對ID3的諸多改進(jìn)之一；它在眾多環(huán)境下具有魯棒性。盡管這是一個實際的解決方案，但是它犧牲了信息增益標(biāo)準(zhǔn)的某些優(yōu)雅和整潔的理論動機(jī)。C4.5對ID3進(jìn)行了一系列改進(jìn)。這些改進(jìn)包括處理數(shù)值屬性、缺失值、噪聲數(shù)據(jù)和由決策樹產(chǎn)生規(guī)則的方法。第24頁，共47頁，2023年，2月20日，星期五4.2.6形象化地理解ID3和C4.5算法第25頁，共47頁，2023年，2月20日，星期五4.3剪枝導(dǎo)論修剪樹模型的動機(jī)：樹的構(gòu)建一般是使用一種遞歸劃分訓(xùn)練集的算法得到。這樣做的結(jié)果是，隨著樹的生長，最佳劃分的選擇基于越來越小的樣本來進(jìn)行。樹的較低層上劃分選擇通常會變得統(tǒng)計上不可靠，盡管基于訓(xùn)練數(shù)據(jù)的誤差估計(所有節(jié)點(diǎn)中誤分類的數(shù)據(jù)總數(shù)在數(shù)據(jù)點(diǎn)總數(shù)中所占的比例)持續(xù)降低。通常不太可能認(rèn)為這種誤差估計可以泛化到未見過的案例上，并且稱樹過分?jǐn)M合訓(xùn)練數(shù)據(jù)。這意味樹捕獲了訓(xùn)練樣本的規(guī)律，而不是得到樣本的領(lǐng)域(總體)的規(guī)律。第26頁，共47頁，2023年，2月20日，星期五剪枝（1）Schaffer指出，剪枝不可能視為改善樹預(yù)測誤差的統(tǒng)計手段。事實上，很容易找到一個現(xiàn)實世界領(lǐng)域，剪枝對于獨(dú)立的、大量檢驗樣本而言，會降低預(yù)測準(zhǔn)確率。剪枝應(yīng)當(dāng)被視為優(yōu)先選擇較簡單的模型。理解不同剪枝方法的偏倚將對選擇最適合用戶偏愛的策略提供有用的提示。第27頁，共47頁，2023年，2月20日，星期五剪枝（2）后剪枝是一個過程，通過該過程產(chǎn)生一棵大樹，然后使用可靠的評估方法選擇對初始模型而言“尺寸合適的”剪枝后的樹。后剪枝方法是計算低效的，即通?？梢哉业揭粋€領(lǐng)域，其中具有數(shù)千個節(jié)點(diǎn)的大樹經(jīng)過后剪枝得到具有數(shù)百個節(jié)點(diǎn)的樹。先剪枝：一旦進(jìn)一步劃分被認(rèn)為是不可靠的，就盡快停止樹的生長。與后剪枝相比，先剪枝具有明顯的計算優(yōu)勢，可以較早地停止樹的生長，并且還可以避免后剪枝。然而，過早地停止樹的生成會使這種方法面臨選擇次最優(yōu)樹的危險(Breiman等，1984)。正因為如此，通常避免過分?jǐn)M合的方法是后剪枝。第28頁，共47頁，2023年，2月20日，星期五后剪枝后剪枝的兩種不同的操作：子樹置換(subtreereplacement)，子樹提升(subtreeraising)。在每個節(jié)點(diǎn)，學(xué)習(xí)方案可以決定是應(yīng)該進(jìn)行子樹置換、子樹提升，還是保留子樹不剪枝。第29頁，共47頁，2023年，2月20日，星期五子樹置換第30頁，共47頁，2023年，2月20日，星期五子樹提升第31頁，共47頁，2023年，2月20日，星期五4.4模型評估評估是使數(shù)據(jù)挖掘取得實際進(jìn)展的關(guān)鍵。在數(shù)據(jù)挖掘過程的最后階段，使用一種或多種歸納學(xué)習(xí)技術(shù)得到模型之后，仍然還存在一些重要問題：

1)如何驗證和確認(rèn)模型?2)對于一個具體問題，使用哪種方法?3)如何將一種方法與另一種比較?第32頁，共47頁，2023年，2月20日，星期五確認(rèn)(validation)和驗證(verification)模型確認(rèn)：用合格檢驗證明模型在其應(yīng)用范圍內(nèi)，按照用戶確定的目標(biāo)，以滿意的正確率進(jìn)行工作。換言之，在模型確認(rèn)中，我們證實數(shù)據(jù)轉(zhuǎn)換為模型，并且它在表示被觀測系統(tǒng)方面具有足夠精度。處理構(gòu)造正確的模型——對應(yīng)于系統(tǒng)的模型。模型驗證：證實模型是由數(shù)據(jù)轉(zhuǎn)換來的、具有足夠精度的新表示。處理正確地構(gòu)造模型——對應(yīng)于數(shù)據(jù)的模型。數(shù)據(jù)挖掘結(jié)果通過檢驗過程加以確認(rèn)和驗證。某些檢驗用來評估模型的行為的正確性(即確認(rèn))，而另一些檢驗旨在評估數(shù)據(jù)轉(zhuǎn)換成模型的正確性(即驗證)。第33頁，共47頁，2023年，2月20日，星期五數(shù)據(jù)集的問題豐富的數(shù)據(jù)可用時：在一個大訓(xùn)練集上構(gòu)造模型，并在另一個大檢驗集上檢驗它。但是，盡管數(shù)據(jù)挖掘有時涉及“大數(shù)據(jù)”(特別是在營銷、銷售和顧客支持應(yīng)用中)，但是通常數(shù)據(jù)(高質(zhì)量的數(shù)據(jù))是短缺的。基于有限數(shù)據(jù)：如果樣本數(shù)量較小，那么數(shù)據(jù)挖掘?qū)嶒灥脑O(shè)計者就必須非常小心地劃分?jǐn)?shù)據(jù)。如何將樣本劃分成子集沒有現(xiàn)成的指導(dǎo)原則。無論如何劃分?jǐn)?shù)據(jù)，都應(yīng)當(dāng)明白，不同的隨機(jī)劃分，即使訓(xùn)練集和檢驗集都具有給定的規(guī)模，也將導(dǎo)致不同的誤差估計。第34頁，共47頁，2023年，2月20日，星期五數(shù)據(jù)集的劃分將數(shù)據(jù)集劃分為訓(xùn)練和檢驗樣本的不同方法，通常稱作子抽樣方法(resamplingmethod)。抽樣方法與分析方法殘相比的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不依賴于關(guān)于數(shù)據(jù)統(tǒng)計分布的假定或逼近函數(shù)的特定性質(zhì)缺點(diǎn)：計算量大且基于子抽樣策略估計方差較高。第35頁，共47頁，2023年，2月20日，星期五模型估計方法（1）模型估計的基本方法是：首先使用一部分?jǐn)?shù)據(jù)集準(zhǔn)備或發(fā)現(xiàn)模型，然后使用其余樣本評估該模型的預(yù)測風(fēng)險。第一部分?jǐn)?shù)據(jù)稱為學(xué)習(xí)集(1earningset)，第二部分?jǐn)?shù)據(jù)稱為確認(rèn)集(validationset)，也稱為檢驗集(testingset)第36頁，共47頁，2023年，2月20日，星期五模型估計方法（2）這種樸素策略(naivestrategy)基于如下假定：學(xué)習(xí)集和確認(rèn)集是作為相同的、未知的數(shù)據(jù)分布的代表而選取的。對于大型數(shù)據(jù)集的確如此對于較小的數(shù)據(jù)集，這種策略具有明顯的缺點(diǎn)。如果樣本數(shù)較小，劃分?jǐn)?shù)據(jù)的具體方法對模型的準(zhǔn)確率有所影響。各種子抽樣方法，對于較小的數(shù)據(jù)集的劃分策略各異。數(shù)據(jù)挖掘系統(tǒng)的設(shè)計者必須根據(jù)數(shù)據(jù)和問題的性質(zhì)進(jìn)行選擇。第37頁，共47頁，2023年，2月20日，星期五再代入方法這是最簡單的方法。所有可用的數(shù)據(jù)都用于訓(xùn)練和檢驗。訓(xùn)練和檢驗集相同?！皵?shù)據(jù)分布”的誤差率估計是偏向樂觀的(估計的誤差通常比模型實際應(yīng)用期望的誤差低)。這種方法很少在現(xiàn)實世界的數(shù)據(jù)挖掘應(yīng)用中使用。在樣本大小與維度的比不大時尤其如此。第38頁，共47頁，2023年，2月20日，星期五4.4.1交叉確認(rèn)：保持方法考慮訓(xùn)練和檢驗數(shù)據(jù)量有限時該如何做？保持方法(holdoutmethod)為檢驗保留一定數(shù)量的樣本，并使用其余樣本進(jìn)行訓(xùn)練(如果需要的話，用一部分樣本進(jìn)行確認(rèn))。在實踐中，通常檢驗數(shù)據(jù)1/3，訓(xùn)練數(shù)據(jù)2/3。不同的劃分將產(chǎn)生不同的估計。重復(fù)該過程，隨機(jī)選擇不同的訓(xùn)練和檢驗集，并將誤差結(jié)果集成到一個標(biāo)準(zhǔn)參數(shù)中將改善模型的估計。這是誤差率估計的重復(fù)保持(repeatedholdout)方法。第39頁，共47頁，2023年，2月20日，星期五保持方法根據(jù)所使用的用于選擇訓(xùn)練和檢驗集的抽樣類型，基本有兩種保持方法。抽樣可以是有放回或無放回的。有放回：留一方法、輪轉(zhuǎn)方法無放回：自助方法留一方法：模型使用(n-1)個樣本訓(xùn)練，而在剩下的一個樣本上評估。這種方法重復(fù)n次，適用大小為(n

-1)的不同訓(xùn)練集。這種方法的計算量很大，因為必須構(gòu)造和比較n個不同的模型。輪轉(zhuǎn)方法(凡折交叉確認(rèn))：這種方法是保持和留一方法的折衷。它將可用的樣本劃分成P個不相交的子集，其中1≤P≤n。(P一1)個子集用于訓(xùn)練，而剩下的一個子集用于檢驗。第40頁，共47頁，2023年，2月20日，星期五自助方法自助方法的基本思想是對數(shù)據(jù)集進(jìn)行有放回抽樣，以形成訓(xùn)練集。0.632自助法(0.632bootstrap)：對有n個實例的數(shù)據(jù)集有放回地抽樣n次，產(chǎn)生另一個有n個實例的數(shù)據(jù)集（用作檢驗實例）。由于第二個數(shù)據(jù)集中的某些元素(幾乎肯定)是重復(fù)的，因此原數(shù)據(jù)集（訓(xùn)練集）中一定有一些實例未被選中。一個實例未被選到訓(xùn)練集中的可能性有多大?未選中的概率：e-1=0.368選中的概率：1-e-1=0.632第41頁，共47頁，2023年，2月20日，星期五4.4.2模型比較數(shù)據(jù)挖掘過程中，使用不同的歸納學(xué)習(xí)技術(shù)可產(chǎn)生不同的模型。可以使用標(biāo)準(zhǔn)誤差率參數(shù)作為其性能度量進(jìn)行評估。誤差率表示真實誤差率的一種近似，一個統(tǒng)計學(xué)習(xí)理論定義的參數(shù)。使用通過再抽樣技術(shù)得到的檢驗數(shù)據(jù)集計算。除用誤差率度量的準(zhǔn)確率之外，數(shù)據(jù)挖掘模型還可以用它們的速度、魯棒性、可伸縮性和可解釋性來比較。而且，所有這些參數(shù)都會影響模型的最終驗證和確認(rèn)。第42頁，共47頁，2023年，2月20日，星期五誤差率誤差率的計算基于檢驗過程的錯誤計數(shù)。對于分類問題，這些錯誤簡單地定義為誤分類(將樣本錯誤分類)。如果所有的錯誤都同等重要，則誤差率R是錯誤數(shù)E除以檢驗集中的樣本數(shù)S。R=E/S模型的正確率A是被正確分類的檢驗數(shù)據(jù)所占的比例。A

=1-R第43頁，共47頁，2023年，2月20日，星期五對于標(biāo)準(zhǔn)的分類問題，可能有多達(dá)m2-m類錯誤，其中m是類的數(shù)目。如果只