《數(shù)據(jù)分類決策樹》PPT課件

2020/5/16,1,數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù),五邑大學(xué)信息學(xué)院2009.06,何國輝教授,2020/5/16,2,第5章決策樹和決策規(guī)則,5.1引例,分類的定義分類是指把數(shù)據(jù)樣本映射到一個(gè)事先定義的類中的學(xué)習(xí)過程，即給定一組輸入的屬性向量及其對應(yīng)的類，用基于歸納的學(xué)習(xí)算法得出分類。,2020/5/16,3,描述屬性,類別屬性,分類問題使用的數(shù)據(jù)集格式：,2020/5/16,4,5.1引例,分類問題使用的數(shù)據(jù)集格式描述屬性可以是連續(xù)型屬性，也可以是離散型屬性；而類別屬性必須是離散型屬性。連續(xù)型屬性是指在某一個(gè)區(qū)間或者無窮區(qū)間內(nèi)該屬性的取值是連續(xù)的，例如屬性“Age”離散型屬性是指該屬性的取值是不連續(xù)的，例如屬性“Salary”和“Class”,2020/5/16,5,5.1引例,分類問題使用的數(shù)據(jù)集格式分類問題中使用的數(shù)據(jù)集可以表示為X=(xi,yi)|i=1,2,totalxi=(xi1,xi2,xid)，其中xi1,xi2,xid分別對應(yīng)d個(gè)描述屬性A1,A2,Ad的具體取值yi表示數(shù)據(jù)樣本xi的類標(biāo)號，假設(shè)給定數(shù)據(jù)集包含m個(gè)類別，則yic1,c2,cm，其中c1,c2,cm是類別屬性C的具體取值未知類標(biāo)號的數(shù)據(jù)樣本x用d維特征向量x=(x1,x2,xd)來表示,2020/5/16,6,5.2分類問題概述,5.2.1分類的過程5.2.2分類的評價(jià)準(zhǔn)則,2020/5/16,7,5.2.1分類的過程,2020/5/16,8,5.2.1分類的過程,獲取數(shù)據(jù)輸入數(shù)據(jù)、對數(shù)據(jù)進(jìn)行量化預(yù)處理去除噪聲數(shù)據(jù)、對空缺值進(jìn)行處理數(shù)據(jù)集成或者變換分類器設(shè)計(jì)劃分?jǐn)?shù)據(jù)集、分類器構(gòu)造、分類器測試分類決策對未知類標(biāo)號的數(shù)據(jù)樣本進(jìn)行分類,2020/5/16,9,5.2.2分類的評價(jià)準(zhǔn)則,給定測試集Xtest=(xi,yi)|i=1,2,NN表示測試集中的樣本個(gè)數(shù)xi表示測試集中的數(shù)據(jù)樣本yi表示數(shù)據(jù)樣本xi的類標(biāo)號對于測試集的第j個(gè)類別，假設(shè)被正確分類的樣本數(shù)量為TPj被錯(cuò)誤分類的樣本數(shù)量為FNj其他類別被錯(cuò)誤分類為該類的樣本數(shù)據(jù)量為FPj,2020/5/16,10,5.2.2分類的評價(jià)準(zhǔn)則,精確度：代表測試集中被正確分類的數(shù)據(jù)樣本所占的比例,2020/5/16,11,5.2.2分類的評價(jià)準(zhǔn)則,查全率：表示在本類樣本中被正確分類的樣本所占的比例查準(zhǔn)率：表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例,2020/5/16,12,5.2.2分類的評價(jià)準(zhǔn)則,F-measure(加權(quán)調(diào)合平均數(shù))：是查全率和查準(zhǔn)率的組合表達(dá)式是可以調(diào)節(jié)的，通常取值為1,2020/5/16,13,5.2.2分類的評價(jià)準(zhǔn)則,幾何均值：是各個(gè)類別的查全率的平方根,2020/5/16,14,決策樹方法的起源是亨特（Hunt，1966）的概念學(xué)習(xí)系統(tǒng)CLS方法，然后發(fā)展到由Quinlan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一個(gè)優(yōu)點(diǎn)是它能夠處理連續(xù)屬性。還有CART算法和Assistant算法也是比較有名的決策樹方法。,5.3決策樹,2020/5/16,15,決策樹的優(yōu)點(diǎn)：進(jìn)行分類器設(shè)計(jì)時(shí)，決策樹分類方法所需時(shí)間相對較少決策樹的分類模型是樹狀結(jié)構(gòu)，簡單直觀，比較符合人類的理解方式可以將決策樹中到達(dá)每個(gè)葉節(jié)點(diǎn)的路徑轉(zhuǎn)換為IFTHEN形式的分類規(guī)則，這種形式更有利于理解,2020/5/16,16,1.什么是決策樹決策樹（DecisionTree）又稱為判定樹，是運(yùn)用于分類的一種樹結(jié)構(gòu)。其中的每個(gè)內(nèi)部結(jié)點(diǎn)（internalnode）代表對某個(gè)屬性的一次測試，每條邊代表一個(gè)測試結(jié)果，葉結(jié)點(diǎn)（leaf）代表某個(gè)類（class）或者類的分布（classdistribution），最上面的結(jié)點(diǎn)是根結(jié)點(diǎn)。決策樹提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。下例是為了解決這個(gè)問題而建立的一棵決策樹，從中可以看到?jīng)Q策樹的基本組成部分：決策結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)。,2020/5/16,17,例圖5-2給出了一個(gè)商業(yè)上使用的決策樹的例子。它表示了一個(gè)關(guān)心電子產(chǎn)品的用戶是否會購買PC（buys_computer）的知識，用它可以預(yù)測某條記錄（某個(gè)人）的購買意向。,圖5-2buys_computer的決策樹,2020/5/16,18,這棵決策樹對銷售記錄進(jìn)行分類，指出一個(gè)電子產(chǎn)品消費(fèi)者是否會購買一臺計(jì)算機(jī)“buys_computer”。每個(gè)內(nèi)部結(jié)點(diǎn)（方形框）代表對某個(gè)屬性的一次檢測。每個(gè)葉結(jié)點(diǎn)（橢圓框）代表一個(gè)類：buys_computers=yes或者buys_computers=no在這個(gè)例子中，樣本向量為：（age,student,credit_rating;buys_computers）被決策數(shù)據(jù)的格式為:（age,student,credit_rating）輸入新的被決策的記錄，可以預(yù)測該記錄隸屬于哪個(gè)類。,2020/5/16,19,2.使用決策樹進(jìn)行分類構(gòu)造決策樹是采用自上而下的遞歸構(gòu)造方法。以多叉樹為例，如果一個(gè)訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)有幾種屬性值，則按照屬性的各種取值把這個(gè)訓(xùn)練數(shù)據(jù)集再劃分為對應(yīng)的幾個(gè)子集（分支），然后再依次遞歸處理各個(gè)子集。反之，則作為葉結(jié)點(diǎn)。決策樹構(gòu)造的結(jié)果是一棵二叉或多叉樹，它的輸入是一組帶有類別標(biāo)記的訓(xùn)練數(shù)據(jù)。二叉樹的內(nèi)部結(jié)點(diǎn)（非葉結(jié)點(diǎn)）一般表示為一個(gè)邏輯判斷，如形式為(a=b)的邏輯判斷，其中a是屬性，b是該屬性的某個(gè)屬性值；樹的邊是邏輯判斷的分支結(jié)果。多叉樹（ID3）的內(nèi)部結(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個(gè)屬性值，就有幾條邊。樹的葉結(jié)點(diǎn)都是類別標(biāo)記。,2020/5/16,20,使用決策樹進(jìn)行分類分為兩步：第1步：利用訓(xùn)練集建立并精化一棵決策樹，建立決策樹模型。這個(gè)過程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取知識，進(jìn)行機(jī)器學(xué)習(xí)的過程。第2步：利用生成完畢的決策樹對輸入數(shù)據(jù)進(jìn)行分類。對輸入的記錄，從根結(jié)點(diǎn)依次測試記錄的屬性值，直到到達(dá)某個(gè)葉結(jié)點(diǎn)，從而找到該記錄所在的類。,2020/5/16,21,問題的關(guān)鍵是建立一棵決策樹。這個(gè)過程通常分為兩個(gè)階段：建樹（TreeBuilding）：決策樹建樹算法見下，這是一個(gè)遞歸的過程，最終將得到一棵樹。剪枝（TreePruning）：剪枝的目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。,2020/5/16,22,由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖掘算法中最有影響的算法。ID3即決策樹歸納（InductionofDecisionTree）。早期的ID算法只能就兩類數(shù)據(jù)進(jìn)行挖掘（如正類和反類）；經(jīng)過改進(jìn)后，現(xiàn)在ID算法可以挖掘多類數(shù)據(jù)。待挖掘的數(shù)據(jù)必須是不矛盾的、一致的，也就是說，對具有相同屬性的數(shù)據(jù)，其對應(yīng)的類必須是唯一的。在ID3算法挖掘后，分類規(guī)則由決策樹來表示。,5.4分類規(guī)則挖掘的ID3算法,2020/5/16,23,1.ID3算法的基本思想由訓(xùn)練數(shù)據(jù)集中全體屬性值生成的所有決策樹的集合稱為搜索空間，該搜索空間是針對某一特定問題而提出的。系統(tǒng)根據(jù)某個(gè)評價(jià)函數(shù)決定搜索空間中的哪一個(gè)決策樹是“最好”的。評價(jià)函數(shù)一般依據(jù)分類的準(zhǔn)確度和樹的大小來決定決策樹的質(zhì)量。如果兩棵決策樹都能準(zhǔn)確地在測試集進(jìn)行分類，則選擇較簡單的那棵。相對而言，決策樹越簡單，則它對未知數(shù)據(jù)的預(yù)測性能越佳。尋找一棵“最好”的決策樹是一個(gè)NP完全問題。,NP完全問題是這樣的問題：用確定性的算法在多項(xiàng)式時(shí)間內(nèi)無法解決的問題。實(shí)際之中，解決這樣的問題，往往是根據(jù)用啟發(fā)式算法，求出近似的解。,2020/5/16,24,ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹，同時(shí)保證找到一棵簡單的決策樹可能不是最簡單的。ID3算法的基本思想描述如下：step1任意選取一個(gè)屬性作為決策樹的根結(jié)點(diǎn)，然后就這個(gè)屬性所有的取值創(chuàng)建樹的分支；step2用這棵樹來對訓(xùn)練數(shù)據(jù)集進(jìn)行分類，如果一個(gè)葉結(jié)點(diǎn)的所有實(shí)例都屬于同一類，則以該類為標(biāo)記標(biāo)識此葉結(jié)點(diǎn)；如果所有的葉結(jié)點(diǎn)都有類標(biāo)記，則算法終止；step3否則，選取一個(gè)從該結(jié)點(diǎn)到根路徑中沒有出現(xiàn)過的屬性為標(biāo)記標(biāo)識該結(jié)點(diǎn)，然后就這個(gè)屬性所有的取值繼續(xù)創(chuàng)建樹的分支；重復(fù)算法步驟step2；,2020/5/16,25,這個(gè)算法一定可以創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹，然而，這棵決策樹不一定是簡單的。顯然，不同的屬性選取順序?qū)⑸刹煌臎Q策樹。因此，適當(dāng)?shù)剡x取屬性將生成一棵簡單的決策樹。在ID3算法中，采用了一種基于信息的啟發(fā)式的方法來決定如何選取屬性。啟發(fā)式方法選取具有最高信息量的屬性，也就是說，生成最少分支決策樹的那個(gè)屬性。,2020/5/16,26,算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹輸入：訓(xùn)練數(shù)據(jù)集samples，用離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹方法：（1）創(chuàng)建結(jié)點(diǎn)N；（2）ifsamples都在同一個(gè)類Cthen（3）返回N作為葉結(jié)點(diǎn)，用類C標(biāo)記；（4）ifattribute_list為空then（5）返回N作為葉結(jié)點(diǎn)，標(biāo)記samples中最普通的類；/多數(shù)表決（6）選擇attribute_list中具有最高信息增益的屬性test_attribute；/用信息增益作為屬性選擇度量（7）標(biāo)記結(jié)點(diǎn)N為test_attribute；（8）foreachtest_attribute中的已知值ai/劃分samples（9）由結(jié)點(diǎn)N生長出一個(gè)條件為test_attributeai的分枝；（10）設(shè)si為samples中test_attributeai的樣本集合；/一個(gè)劃分（11）ifsi為空then（12）加上一個(gè)葉結(jié)點(diǎn)，標(biāo)記為標(biāo)記samples中最普通的類；/多數(shù)表決（13）else加上一個(gè)由Generate_decision_tree（si,attribute_list-test_attribute）返回的結(jié)點(diǎn)；,2020/5/16,27,2.屬性選擇度量在Generate_decision_tree算法的Step6，算法需選擇attribute_list中具有最高信息增益的屬性test_attribute。ID3算法在樹的每個(gè)結(jié)點(diǎn)上以信息增益（informationgain）作為度量來選擇測試屬性。這種度量稱為屬性選擇度量或分裂的優(yōu)良性度量。選擇具有最高信息增益（或最大熵壓縮）的屬性作為當(dāng)前結(jié)點(diǎn)的測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需要的信息量最小，并確保找到一棵簡單的（但不一定是最簡單的）決策樹。,2020/5/16,28,InformationGain指標(biāo)的原理來自于信息論。1948年，香農(nóng)（C.E.Shannon）提出了信息論。其中給出了關(guān)于信息量（Information）和熵（Entropy）的定義，熵實(shí)際上是系統(tǒng)信息量的加權(quán)平均，也就是系統(tǒng)的平均信息量。,2020/5/16,29,假設(shè)要選擇有n個(gè)輸出（所給屬性的n個(gè)值）的檢驗(yàn)，把訓(xùn)練樣本集T分區(qū)成子集T1，T2，Tn。僅有的指導(dǎo)信息是在T和它的子集Ti中的類的分布。如果S是任意樣本集，設(shè)freq(Ci,S)代表S中屬于類Ci（k個(gè)可能的類中的一個(gè)）的樣本數(shù)量，|S|表示集合S中的樣本數(shù)量。下面給出了集合S（單位為比特）的熵計(jì)算：,以2為底的原因是：信息按二進(jìn)制位編碼,2020/5/16,30,熵是一個(gè)衡量系統(tǒng)混亂程度的統(tǒng)計(jì)量。熵越大，表示系統(tǒng)越混亂。分類的目的是提取系統(tǒng)信息，使系統(tǒng)向更加有序、有規(guī)則組織的方向發(fā)展。所以最佳的分裂方案是使熵減少量最大的分裂方案。熵減少量就是InformationGain（信息增益），所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，這個(gè)最佳方案是用“貪心算法+深度優(yōu)先搜索”得到的。,2020/5/16,31,現(xiàn)在考慮T被分區(qū)之后的一個(gè)相似度量標(biāo)準(zhǔn)，T按照一個(gè)屬性檢驗(yàn)X的幾個(gè)輸出進(jìn)行分區(qū)。所需信息可通過這些子集的熵的加權(quán)和求得：,信息增益的計(jì)算公式：Gain(X)=Info(T)-Infox(T)通過計(jì)算求出具有最高增益的屬性。,2020/5/16,32,以下分析有關(guān)度量標(biāo)準(zhǔn)的應(yīng)用和創(chuàng)建決策樹的一個(gè)簡單例子，假設(shè)以平面文件形式給出的數(shù)據(jù)集T，其中有14個(gè)樣本，通過3個(gè)輸入屬性描述且屬于所給的兩個(gè)類之一：類1或類2。,2020/5/16,33,2020/5/16,34,其中：9個(gè)樣本屬于類1，5個(gè)樣本屬于類2，因此分區(qū)前的熵為：info(T)-9/14.log2(9/14)-5/14.log2(5/14)=0.940比特根據(jù)屬性1把初始樣本集分區(qū)成3個(gè)子集（檢驗(yàn)x1表示從3個(gè)值A(chǔ)，B或C中選擇其一）后，得出結(jié)果：Infox1(T)5/14（-2/5log2(2/5)-3/5log2(3/5)）+4/14（-4/4log2(4/4)-0/4log2(0/4)）+5/14（-3/5log2(3/5)-2/5log2(2/5)）=0.694比特通過檢驗(yàn)x1獲得的信息增益是：Gain(x1)=0.9400.694=0.246比特,2020/5/16,35,如果該檢驗(yàn)和分區(qū)是基于屬性3的（檢驗(yàn)x2表示從真或假兩個(gè)值選擇其一），類似地有：Infox2(T)6/14（-3/6log2(3/6)-3/6log2(3/6)）+8/14（-6/8log2(6/8)-2/8log2(2/8)）=0.892比特通過檢驗(yàn)x2獲得的增益是：Gain(x2)=0.9400.892=0.048比特按照增益準(zhǔn)則，將選擇x1作為分區(qū)數(shù)據(jù)庫T的最初檢驗(yàn)。為了求得最優(yōu)檢驗(yàn)還必須分析關(guān)于屬性2的檢驗(yàn)，它是連續(xù)取值的數(shù)值型屬性。,2020/5/16,36,3.ID3算法的改進(jìn)（1）離散化為了解決該問題，在用ID3算法挖掘具有連續(xù)性屬性的知識時(shí)，應(yīng)該首先把該連續(xù)性屬性離散化。最簡單的方法就是把屬性值分成和兩段。如身高可以分為1米以下，1米以上或者分為1.5米以下，1.5米以上。如何選擇最佳的分段值呢？對任何一個(gè)屬性，其所有的取值在一個(gè)數(shù)據(jù)集中是有限的。假設(shè)該屬性取值為，則在這個(gè)集合中，一共存在m-1個(gè)分段值，ID3算法采用計(jì)算信息量的方法計(jì)算最佳的分段值，然后進(jìn)一步構(gòu)建決策樹。ID3算法的擴(kuò)展是C4.5算法，C4.5算法把分類范圍從分類屬性擴(kuò)展到數(shù)字屬性。,2020/5/16,37,1.C4.5算法概述C4.5算法是ID3算法的擴(kuò)展，它的改進(jìn)部分是：能夠處理連續(xù)型的屬性。首先將連續(xù)型屬性離散化，把連續(xù)型屬性的值分成不同的區(qū)間，依據(jù)是比較各個(gè)屬性Gian值的大小。缺失數(shù)據(jù)的考慮：在構(gòu)建決策樹時(shí)，可以簡單地忽略缺失數(shù)據(jù)，即在計(jì)算增益時(shí)，僅考慮具有屬性值的記錄。提供兩種基本的剪枝策略：子樹替代法：用葉結(jié)點(diǎn)替代子樹。子樹上升法：用一棵子樹中最常用的子樹來代替這棵子樹。,5.5分類規(guī)則挖掘的C4.5算法,剪枝目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。,2020/5/16,38,2.離散化的方法把連續(xù)型屬性值離散化的具體方法是：1）尋找該連續(xù)型屬性的最小值，并把它賦值給MIN，尋找該連續(xù)型屬性的最大值，并把它賦值給MAX；2）設(shè)置區(qū)間MIN，MAX中的N個(gè)等分?jǐn)帱c(diǎn)Ai，它們分別是Ai=MIN+（MAXMIN）/N）*i其中，i=1,2,.,N3）分別計(jì)算把MIN，Ai和（Ai，MAX）（i=1,2,.,N）作為區(qū)間值時(shí)的Gain值，并進(jìn)行比較。4）選取Gain值最大的Ak做為該連續(xù)型屬性的斷點(diǎn)，把屬性值設(shè)置為MIN，Ak和（Ak，MAX）兩個(gè)區(qū)間值。,2020/5/16,39,對于前面例子中的數(shù)據(jù)庫T，分析屬性2分區(qū)的可能結(jié)果，分類后得出屬性2的值的集合是：65,70,75,78,80,85,90,95,96按照C4.5算法，選擇每個(gè)區(qū)間的最小值作為閾值，即：65,70,75,78,80,85,90,95共8個(gè)值，從中選取最優(yōu)的閾值。按照前述方法選取兩區(qū)間，并分別計(jì)算其Gain值：6570757880859095如以第二種分段為例計(jì)算，計(jì)算其Gain值：,2020/5/16,40,2020/5/16,41,Infox2(T)4/14（-3/4log2(3/4)-1/4log2(1/4)）+10/14（-6/10log2(6/10)-4/10log2(4/10)）=比特Gain(x2)=0.940Infox2(T)=比特,2020/5/16,42,找到最優(yōu)的閾值（具有最高信息增益）Z=80相應(yīng)的檢驗(yàn)3（屬性280)的信息增益計(jì)算為：Infox3(T)9/14（-7/9log2(7/9)-2/9log2(2/9)）+5/14（-2/5log2(2/5)-3/5log2(3/5)）=0.837比特通過檢驗(yàn)x3獲得的增益是：Gain(x3)=0.9400.837=0.103比特比較本例中3個(gè)屬性的信息增益，可以看出屬性1具有最高增益，選擇該屬性對決策樹的結(jié)構(gòu)進(jìn)行首次分區(qū)。,2020/5/16,43,T1,檢驗(yàn)X1:屬性1=？,T2,T3,A,B,C,葉結(jié)點(diǎn),2020/5/16,44,對于剩下的子結(jié)點(diǎn)T1、T3進(jìn)行分析：對T1的屬性進(jìn)行檢驗(yàn)：最優(yōu)檢驗(yàn)（具有最高的信息增益）有兩個(gè)選擇：屬性270，定義為x4。Info(T1)-2/14log2(2/5)-3/14log2(3/5)=0.940比特用屬性2把T1分成兩個(gè)子集（檢驗(yàn)x4），結(jié)果信息是：Infox4(T)2/5（-2/2log2(2/2)-0/2log2(0/2)）+3/5（-0/3log2(0/3)-3/3log2(3/3)）=0比特該檢驗(yàn)的信息增益最大：Gain(x4)=0.9400=0.940比特這兩個(gè)分枝將生成最終葉結(jié)點(diǎn)。,2020/5/16,45,對于剩下的子結(jié)點(diǎn)T3進(jìn)行分析：對T3的屬性進(jìn)行檢驗(yàn)：選擇的最優(yōu)檢驗(yàn)為x5對屬性3的值進(jìn)行檢驗(yàn)，樹的分枝是屬性3=真和屬性3=假。最終決策樹為：,2020/5/16,46,決策樹可以用偽代碼的形式表示，這種偽代碼用IF-THEN結(jié)構(gòu)對決策樹進(jìn)行分枝。,If屬性1=Athenif屬性2=70then類別=類1;else類別=類2;Elseif屬性1=Bthen類別=類1;elseif屬性1=Cthenif屬性3=真then類別=類2;else類別=類1.,結(jié)果,2020/5/16,47,增益標(biāo)準(zhǔn)對緊湊型決策樹的構(gòu)造有很好的效果，但也存在一個(gè)嚴(yán)重缺陷：對具有多輸出的檢驗(yàn)有嚴(yán)重的偏差。解決方法：根據(jù)info(S)的定義，指定一個(gè)附加的參數(shù)：,含義：通過把集T分區(qū)成n個(gè)子集Ti而生成的潛在信息。新的增益標(biāo)準(zhǔn)-增益率：Gain_ratio(X)=Gain(X)/Split_Info(X),新的增益標(biāo)準(zhǔn)表示分區(qū)所生成的有用信息的比例,2020/5/16,48,根據(jù)前面實(shí)例，求檢驗(yàn)X1的增益比例。計(jì)算Split_Info(X1)Split_Info(X1)-5/14log2(5/14)-4/14log2(4/14)-5/14log2(5/14)=1.577比特計(jì)算Gain_ratio(X1)Gain_ratio(X1)=0.246/1.577=0.156檢驗(yàn)過程，將采用最大增益率代替增益標(biāo)準(zhǔn)值,2020/5/16,49,在實(shí)際應(yīng)用過程中，大量的現(xiàn)實(shí)世界中的數(shù)據(jù)都不是以人的意愿來定的，可能某些字段上缺值（missingvalues）；可能數(shù)據(jù)不準(zhǔn)確含有噪聲或者是錯(cuò)誤的；可能是缺少必須的數(shù)據(jù)造成了數(shù)據(jù)的不完整。解決丟失值問題有兩種選擇：拋棄數(shù)據(jù)庫中有丟失數(shù)據(jù)的樣本。定義一個(gè)新的算法或改進(jìn)現(xiàn)有的算法來處理。,3.未知屬性值問題,如存在大量丟失數(shù)據(jù)?,2020/5/16,50,按照第二種選擇，必須回答幾個(gè)問題：怎樣比較具有不同數(shù)目未知值的兩個(gè)樣本？具有未知值的訓(xùn)練樣本和檢驗(yàn)的具體值之間沒有聯(lián)系，它們不能被分配給任何子集，該如何處理這些樣本？在分類的檢驗(yàn)階段，如果檢驗(yàn)有丟失值的屬性時(shí)，該怎樣處理丟失值？C4.5算法中：有未知值的樣本是按照已知值的相對頻率隨機(jī)分布的。除考慮到僅有的幾個(gè)有已知屬性值的樣本以外用系數(shù)F修正增益參數(shù)F=數(shù)據(jù)庫中一個(gè)給出的屬性值具有已知值的樣本數(shù)量/數(shù)據(jù)集中樣本數(shù)量總和,通過一些方法補(bǔ)充數(shù)據(jù)？,2020/5/16,51,新的增益標(biāo)準(zhǔn)：Gain(X)=F*(info(T)infox(T)同時(shí)，通過把具有未知值的樣本看作分區(qū)的一個(gè)附加組來修改Split_Info(X)。如果檢驗(yàn)x有n個(gè)輸出，Split_Info(X)按照檢驗(yàn)把數(shù)據(jù)集分區(qū)成n+1個(gè)子集計(jì)算。該值Split_Info(X)對修改后的標(biāo)準(zhǔn)Gain_ratio(X)的最終值有直接影響。,2020/5/16,52,2020/5/16,53,屬性1的增益計(jì)算考慮13個(gè)數(shù)據(jù)，丟失的樣本僅用來作修正，屬性1中有8個(gè)屬于類1，5個(gè)屬于類2，因此分區(qū)前的熵為：Info(T)-8/13log2(8/13)-5/13log2(5/13)=0.961比特用屬性1把T分區(qū)成3個(gè)子集（A、B、C）后，得到的信息是：Infox1(T)5/13（-2/