第4章(1)

分類(lèi)：決策樹(shù)4.1預(yù)備知識(shí)4.2解決分類(lèi)問(wèn)題的一般方法4.3決策樹(shù)歸納4.3.1決策樹(shù)的工作原理4.3.2如何建立決策樹(shù)補(bǔ)充：ID3決策樹(shù)詳解（后繼C4.5）4.3.3表示屬性測(cè)試條件的方法4.3.4選擇最佳劃分的度量4.4模型的過(guò)分?jǐn)M合

分類(lèi)的是利用一個(gè)分類(lèi)函數(shù)（分類(lèi)模型、分類(lèi)器），該模型能把數(shù)據(jù)庫(kù)中的數(shù)據(jù)映射到給定類(lèi)別中的一個(gè)。

訓(xùn)練樣本、學(xué)習(xí)測(cè)試、分類(lèi)屬性分類(lèi)界限or分類(lèi)規(guī)則思路：人如何學(xué)習(xí)、分類(lèi)類(lèi)比計(jì)算機(jī)如何學(xué)習(xí)、分類(lèi)？分類(lèi)基本概念訓(xùn)練集：數(shù)據(jù)庫(kù)中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集。訓(xùn)練集中的單個(gè)元組稱(chēng)為訓(xùn)練樣本,每個(gè)訓(xùn)練樣本有一個(gè)類(lèi)別標(biāo)記。一個(gè)具體樣本的形式可為:(v1,v2,...,vn;c);其中vi表示屬性值,c表示類(lèi)別。測(cè)試集（檢驗(yàn)集）：用于評(píng)估分類(lèi)模型的準(zhǔn)確率數(shù)據(jù)分類(lèi)——一個(gè)兩步過(guò)程(1)第一步，建立一個(gè)模型，描述預(yù)定數(shù)據(jù)類(lèi)集和概念集假定每個(gè)元組屬于一個(gè)預(yù)定義的類(lèi)，由一個(gè)類(lèi)標(biāo)號(hào)屬性確定學(xué)習(xí)模型可以用分類(lèi)規(guī)則、決策樹(shù)或數(shù)學(xué)公式的形式提供數(shù)據(jù)分類(lèi)——一個(gè)兩步過(guò)程(2)第二步，使用模型，對(duì)將來(lái)的或未知的對(duì)象進(jìn)行分類(lèi)首先評(píng)估模型的預(yù)測(cè)準(zhǔn)確率對(duì)每個(gè)測(cè)試樣本，將已知的類(lèi)標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類(lèi)預(yù)測(cè)比較模型在給定測(cè)試集上的準(zhǔn)確率是正確被模型分類(lèi)的測(cè)試樣本的百分比測(cè)試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(xiàn)“過(guò)分適應(yīng)數(shù)據(jù)”的情況如果準(zhǔn)確性能被接受，則分類(lèi)規(guī)則就可用來(lái)對(duì)新數(shù)據(jù)進(jìn)行分類(lèi)有監(jiān)督的學(xué)習(xí)VS.無(wú)監(jiān)督的學(xué)習(xí)有監(jiān)督的學(xué)習(xí)（用于分類(lèi)）模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類(lèi)的“監(jiān)督”下進(jìn)行新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類(lèi)無(wú)監(jiān)督的學(xué)習(xí)（用于聚類(lèi)）每個(gè)訓(xùn)練樣本的類(lèi)編號(hào)是未知的，要學(xué)習(xí)的類(lèi)集合或數(shù)量也可能是事先未知的通過(guò)一系列的度量、觀察來(lái)建立數(shù)據(jù)中的類(lèi)編號(hào)或進(jìn)行聚類(lèi)分類(lèi)模型的構(gòu)造方法1.機(jī)器學(xué)習(xí)方法：決策樹(shù)法規(guī)則歸納2.統(tǒng)計(jì)方法：知識(shí)表示是判別函數(shù)和原型事例貝葉斯法非參數(shù)法(近鄰學(xué)習(xí)或基于事例的學(xué)習(xí))3.神經(jīng)網(wǎng)絡(luò)方法：BP算法,模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型4.粗糙集(roughset)知識(shí)表示是產(chǎn)生式規(guī)則4.1預(yù)備知識(shí)4.2解決分類(lèi)問(wèn)題的一般方法4.3決策樹(shù)歸納4.3.1決策樹(shù)的工作原理4.3.2如何建立決策樹(shù)補(bǔ)充：ID3決策樹(shù)詳解（后繼C4.5）4.3.3表示屬性測(cè)試條件的方法4.3.4選擇最佳劃分的度量4.4模型的過(guò)分?jǐn)M合

一個(gè)決策樹(shù)的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KSplittingAttributes訓(xùn)練數(shù)據(jù)模型:決策樹(shù)決策樹(shù)的另一個(gè)例子categoricalcategoricalcontinuousclassMarStRefundTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K用決策樹(shù)歸納分類(lèi)什么是決策樹(shù)？類(lèi)似于流程圖的樹(shù)結(jié)構(gòu)每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試每個(gè)分枝代表一個(gè)測(cè)試輸出每個(gè)樹(shù)葉節(jié)點(diǎn)代表類(lèi)或類(lèi)分布決策樹(shù)的生成由兩個(gè)階段組成決策樹(shù)構(gòu)建開(kāi)始時(shí)，所有的訓(xùn)練樣本都在根節(jié)點(diǎn)遞歸的通過(guò)選定的屬性，來(lái)劃分樣本（必須是離散值）樹(shù)剪枝許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹(shù)剪枝試圖檢測(cè)和剪去這種分枝決策樹(shù)的使用：對(duì)未知樣本進(jìn)行分類(lèi)通過(guò)將樣本的屬性值與決策樹(shù)相比較為了對(duì)未知數(shù)據(jù)對(duì)象進(jìn)行分類(lèi)識(shí)別，可以根據(jù)決策樹(shù)的結(jié)構(gòu)對(duì)數(shù)據(jù)集中的屬性進(jìn)行測(cè)試，從決策樹(shù)的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就形成了相應(yīng)對(duì)象的類(lèi)別測(cè)試。決策樹(shù)可以很容易轉(zhuǎn)換為分類(lèi)規(guī)則決策樹(shù)分類(lèi)任務(wù)DecisionTree一個(gè)決策樹(shù)的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KSplittingAttributes訓(xùn)練數(shù)據(jù)模型:決策樹(shù)應(yīng)用決策樹(shù)進(jìn)行分類(lèi)RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K測(cè)試數(shù)據(jù)Startfromtherootoftree.應(yīng)用決策樹(shù)進(jìn)行分類(lèi)RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K測(cè)試數(shù)據(jù)應(yīng)用決策樹(shù)進(jìn)行分類(lèi)RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K測(cè)試數(shù)據(jù)應(yīng)用決策樹(shù)進(jìn)行分類(lèi)RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K測(cè)試數(shù)據(jù)應(yīng)用決策樹(shù)進(jìn)行分類(lèi)RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K測(cè)試數(shù)據(jù)應(yīng)用決策樹(shù)進(jìn)行分類(lèi)RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K測(cè)試數(shù)據(jù)AssignCheatto“No”決策樹(shù)分類(lèi)DecisionTree4.1預(yù)備知識(shí)4.2解決分類(lèi)問(wèn)題的一般方法4.3決策樹(shù)歸納4.3.1決策樹(shù)的工作原理4.3.2如何建立決策樹(shù)補(bǔ)充：ID3決策樹(shù)詳解（后繼C4.5）4.3.3表示屬性測(cè)試條件的方法4.3.4選擇最佳劃分的度量4.4模型的過(guò)分?jǐn)M合

決策樹(shù)有許多決策樹(shù)算法:Hunt算法信息增益——Informationgain

（ID3）增益比率——Gainration（C4.5）基尼指數(shù)——Giniindex

(SLIQ，SPRINT)Hunt算法設(shè)Dt

是與結(jié)點(diǎn)t相關(guān)聯(lián)的訓(xùn)練記錄集算法步驟:如果Dt

中所有記錄都屬于同一個(gè)類(lèi)yt,則t是葉結(jié)點(diǎn)，用yt標(biāo)記如果Dt

中包含屬于多個(gè)類(lèi)的記錄，則選擇一個(gè)屬性測(cè)試條件，將記錄劃分成較小的子集。對(duì)于測(cè)試條件的每個(gè)輸出，創(chuàng)建一個(gè)子結(jié)點(diǎn)，并根據(jù)測(cè)試結(jié)果將Dt中的記錄分布到子結(jié)點(diǎn)中。然后，對(duì)于每個(gè)子結(jié)點(diǎn)，遞歸地調(diào)用該算法Dt?Hunt算法Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat<80K>=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarried決策樹(shù)構(gòu)建Hunt算法采用貪心策略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄如何停止分裂過(guò)程怎樣選擇最佳劃分？選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度。不純性的程度越低，類(lèi)分布就越傾斜結(jié)點(diǎn)不純性的度量:不純性大不純性小怎樣找到最佳劃分？B?YesNoNodeN3NodeN4A?YesNoNodeN1NodeN2劃分前:M0M1M2M3M4M12M34Gain=M0–M12vsM0–M34結(jié)點(diǎn)不純性的測(cè)量GiniEntropyclassificationerror停止分裂過(guò)程當(dāng)所有的記錄屬于同一類(lèi)時(shí)，停止分裂當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂提前終止樹(shù)的生長(zhǎng)三種著名的決策樹(shù)Cart：基本的決策樹(shù)算法Id3：利用增益比不純性，樹(shù)采用二叉樹(shù)，停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類(lèi)時(shí)，停止分裂，或當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂C4.5：id3的改進(jìn)版本，也是最流行的分類(lèi)數(shù)算法。采用多重分支和剪枝技術(shù)。決策樹(shù)特點(diǎn):決策樹(shù)是一種構(gòu)建分類(lèi)模型的非參數(shù)方法不需要昂貴的的計(jì)算代價(jià)決策樹(shù)相對(duì)容易解釋決策樹(shù)是學(xué)習(xí)離散值函數(shù)的典型代表決策數(shù)對(duì)于噪聲的干擾具有相當(dāng)好的魯棒性冗余屬性不會(huì)對(duì)決策樹(shù)的準(zhǔn)確率造成不利影響數(shù)據(jù)碎片問(wèn)題。隨著數(shù)的生長(zhǎng)，可能導(dǎo)致葉結(jié)點(diǎn)記錄數(shù)太少，對(duì)于葉結(jié)點(diǎn)代表的類(lèi)，不能做出具有統(tǒng)計(jì)意義的判決子樹(shù)可能在決策樹(shù)中重復(fù)多次。使決策樹(shù)過(guò)于復(fù)雜4.1預(yù)備知識(shí)4.2解決分類(lèi)問(wèn)題的一般方法4.3決策樹(shù)歸納4.3.1決策樹(shù)的工作原理4.3.2如何建立決策樹(shù)補(bǔ)充：ID3決策樹(shù)詳解（后繼C4.5）4.3.3表示屬性測(cè)試條件的方法4.3.4選擇最佳劃分的度量4.4模型的過(guò)分?jǐn)M合

ID3算法詳解ID3使用信息增益作為屬性選擇度量。該度童基于香農(nóng)(ClaudeShannon)在研究消息的值或"信息內(nèi)容"的信息論方面的先驅(qū)工作。設(shè)結(jié)點(diǎn)N代表或存放分區(qū)D的元組。選擇具有最高信息增益的屬性作為結(jié)點(diǎn)N的分裂屬性。該屬性使結(jié)果分區(qū)中對(duì)元組分類(lèi)所需要的信息量最小，并反映這些分區(qū)中的最小隨機(jī)性或"不純性"。這種方法使得對(duì)一個(gè)對(duì)象分類(lèi)所需要的期望測(cè)試數(shù)目最小，并確保找到一棵簡(jiǎn)單的(但不必是最簡(jiǎn)單的)樹(shù)。ID3算法對(duì)D中的元組分類(lèi)所需要的期望信息由下式給出:其中，Pi是D中任意元組屬于類(lèi)Ci的非零概率，并用

估計(jì)。Info(D)是識(shí)別D中無(wú)組的類(lèi)標(biāo)號(hào)所需要的平均信息量。注意，此時(shí)我們所有的信息只是每個(gè)類(lèi)的元組所占的百分比。Info(D)又稱(chēng)為D的熵(entropy)非負(fù)性：Info(D)大于等于0連續(xù)性：Info(D)對(duì)任意q連續(xù)極值性：當(dāng)q都等于1\K時(shí)Info(D)達(dá)到最大值logKID3算法——期望信息，熵(entropy)ID3算法——計(jì)算Entropy的例子P(C1)=0/6=0P(C2)=6/6=1Info(D)=–1log1=–0=0P(C1)=1/6P(C2)=5/6Info(D)=–(1/6)log2(1/6)

–(5/6)log2(1/6)=0.65P(C1)=2/6P(C2)=4/6Info(D)=–(2/6)log2(2/6)

–(4/6)log2(4/6)=0.92P(C1)=3/6P(C2)=3/6Info(D)=–(1/2)log2(1/2)

–(1/2)log2(1/2)=1現(xiàn)在，假設(shè)我們要按某屬性A劃分D中的元組，其中屬性A根據(jù)訓(xùn)練數(shù)據(jù)的觀測(cè)具有v個(gè)不同值如果A是離散值的，則這些值直接對(duì)應(yīng)A上測(cè)試的v個(gè)輸出?？梢杂脤傩訟將D劃分為v個(gè)分區(qū)或子集其中，Dj包含D中的元組，它們的A值為aj。這些分區(qū)對(duì)應(yīng)于從結(jié)點(diǎn)N生長(zhǎng)出來(lái)的分枝。理想情況下，我們希望該劃分產(chǎn)生元組的準(zhǔn)確分類(lèi)。即我們希望每個(gè)分區(qū)都是純的。然而，這些分區(qū)多半是不純的(例如，分區(qū)可能包含來(lái)自不同類(lèi)而不是來(lái)自單個(gè)類(lèi)的元組)。(在此劃分之后）為了得到準(zhǔn)確的分類(lèi)，我們還需要多少信息？這個(gè)量由劃分A的期望信息度量ID3算法——期望信息，熵(entropy)劃分的期望信息項(xiàng)充當(dāng)?shù)趈個(gè)分區(qū)的權(quán)重。InfoA(D)是基于按A劃分對(duì)D的元組分類(lèi)所需要的期望信息。需要的期望信息越小，分區(qū)的純度越高。信息增益定義為原來(lái)的信息需求(僅基于類(lèi)比例)與新的信息需求(對(duì)A劃分后1)之間的差。即ID3算法——信息增益信息增益定義為原來(lái)的信息需求(僅基于類(lèi)比例)與新的信息需求(對(duì)A劃分后1)之間的差。即換言之，Gain(A)告訴我們通過(guò)A上的劃分我們得到了多少。它是知道A的值而導(dǎo)致的信息需求的期望減少。選擇具有最高信息增益Gain(A)的屬性A作為結(jié)點(diǎn)N的分裂屬性。這等價(jià)于在“能做最佳分類(lèi)”的屬性A上劃分，使得完成元組分類(lèi)還需要的信息最小(即最小化Gain(A))。ID3算法——信息增益Trainingdataset:BuyscomputerThedatasetfollowsanexample

ofQuinlan’sID3(PlayingTennis)Resultingtree:ID3算法——例子age?overcasstudent?creditrating?<=30>40noyesyesyes31..40nofairexcellentyesno一個(gè)標(biāo)記類(lèi)的元組的訓(xùn)練集D，隨機(jī)地從AlIElectronics顧客數(shù)據(jù)庫(kù)中選取。在這個(gè)例子中，每個(gè)屬性都是離散值的，連續(xù)值屬性已經(jīng)被離散化。類(lèi)標(biāo)號(hào)屬性buyscompter有兩個(gè)不同值(即{yes,no})，因此有兩個(gè)不同的類(lèi)(即m=2)。設(shè)類(lèi)C1對(duì)應(yīng)于yes，而類(lèi)C2對(duì)應(yīng)于no。類(lèi)yes有9個(gè)元組，類(lèi)no有5個(gè)元組。為D中的元組創(chuàng)建(根)結(jié)點(diǎn)N。為了找出這些元組的分裂準(zhǔn)則，必須計(jì)算每個(gè)屬性的信息增益。ID3算法——例子下一步，需要計(jì)算每個(gè)屬性的期望信息需求。從屬性age開(kāi)始。需要對(duì)age的每個(gè)類(lèi)考察yes和no元組的分布。ID3算法——例子ClassP:buyscomputer=“yes”ClassN:buyscomputer=“no”“yes”“no”<=3031…40>40由于age在屬性中具有最高的信息增益，所以它被選作分裂屬性。結(jié)點(diǎn)N用age標(biāo)記，并且每個(gè)屬性值生長(zhǎng)出一個(gè)分枝。然后元組據(jù)此劃分，如圖所示。ID3算法——例子注意，落在分區(qū)age=“30…40"的元組都屬于相同的類(lèi)。由于它們都屬于類(lèi)"yes"，所以要在該分枝的端點(diǎn)創(chuàng)建一個(gè)樹(shù)葉，并用"yes"標(biāo)記。ID3算法——例子信息增益度量偏向具有許多輸出的測(cè)試。換句話說(shuō)，它傾向于選擇具有大量值的屬性。例如，考慮充當(dāng)唯一標(biāo)識(shí)符的屬性，如productID。在product

ID的劃分將導(dǎo)致大量分區(qū)(與值一樣多)，每個(gè)只包含一個(gè)元組。由于每個(gè)分區(qū)都是純的，所以基于該劃分對(duì)數(shù)據(jù)集D分類(lèi)所需要的信息Infoproduct

ID

(D)=0。因此，通過(guò)對(duì)該屬性的劃分得到的信息增益最大。顯然，這種劃分對(duì)分類(lèi)沒(méi)有用。1D3的后繼C4.5使用一種稱(chēng)為增益率(gainratio)的信息增益擴(kuò)充，試圖克服這種偏倚。它用"分裂信息(splitinfonnation)"值將信息增益規(guī)范化。C4.5算法——增益率分裂信息(splitinfonnation)定義如下：該值代表由訓(xùn)練數(shù)據(jù)集D劃分成對(duì)應(yīng)于屬性A測(cè)試的v個(gè)輸出的v個(gè)分區(qū)共生的信息。注意，對(duì)于每個(gè)輸出，它相對(duì)于D中元組的總數(shù)考慮具有該輸出的元組數(shù)。增益率(gainratio)定義如下：GainRatio(A)=Gain(A)/SplitInfo(A)屬性income的測(cè)試將數(shù)據(jù)劃分成3個(gè)分區(qū)，即low、medium和high，分別包含4、6和4個(gè)元組。gainratio(income)=0.029/1.557=0.019C4.5算法——增益率4.1預(yù)備知識(shí)4.2解決分類(lèi)問(wèn)題的一般方法4.3決策樹(shù)歸納4.3.1決策樹(shù)的工作原理4.3.2如何建立決策樹(shù)補(bǔ)充：ID3決策樹(shù)詳解（后繼C4.5）4.3.3表示屬性測(cè)試條件的方法4.3.4選擇最佳劃分的度量4.4模型的過(guò)分?jǐn)M合

怎樣為不同類(lèi)型的屬性指定測(cè)試條件?依賴(lài)于屬性的類(lèi)型二元標(biāo)稱(chēng)序數(shù)連續(xù)依賴(lài)于劃分的路數(shù)2路劃分多路劃分基于標(biāo)稱(chēng)屬性的分裂多路劃分:

劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù).二元?jiǎng)澐?

劃分?jǐn)?shù)為2，這種劃分要考慮創(chuàng)建k個(gè)屬性值的二元?jiǎng)澐值乃?k-1-1種方法.CarTypeFamilySportsLuxuryCarType{Family,

Luxury}{Sports}CarType{Sports,Luxury}{Family}ORCarType{Family,

Sports}{Luxury}多路劃分:

劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù).二元?jiǎng)澐?

劃分?jǐn)?shù)為2，需要保持序數(shù)屬性值的有序性.基于序數(shù)屬性的劃分SizeSmallMediumLargeSize{Medium,

Large}{Small}Size{Small,Medium}{Large}ORSize{Small,Large}{Medium}基于連續(xù)屬性的劃分多路劃分:vi≤A＜vi+1（i=1,…,k)二元?jiǎng)澐?(A<v)or(Av)考慮所有的劃分點(diǎn)，選擇一個(gè)最佳劃分點(diǎn)v基于連續(xù)屬性的劃分ID3算法如何計(jì)算連續(xù)值屬性的信息增益?假設(shè)屬性A是連續(xù)值的，而不是離散值的。(例如，假定有屬性age的原始值，而不是該屬性的離散化版本。)對(duì)于這種情況，必須確定A的“最佳”分裂點(diǎn)，其中分裂點(diǎn)是A上的閾值。首先，將A的值按遞增序排序。典型地，每對(duì)相鄰值的中點(diǎn)被看做可能的分裂點(diǎn)。這樣，給定A的v個(gè)值，則需要計(jì)算v-1個(gè)可能的劃分。例如，A的值ai和ai+1之間的中點(diǎn)是(ai+ai+1)/2如果A的值已經(jīng)預(yù)先排序，則確定A的最佳劃分只需要掃描一遍這些值。對(duì)于A的每個(gè)可能分裂點(diǎn)，計(jì)算lnfoA(D)，其中分區(qū)的個(gè)數(shù)為2。A具有最小期望信息需求的點(diǎn)選做A的分裂點(diǎn)。D1是滿(mǎn)足A≤splitpoin的元組集合，而D2是滿(mǎn)足A>splitpoint的元組集合?；谶B續(xù)屬性的劃分（ID3算法）4.1預(yù)備知識(shí)4.2解決分類(lèi)問(wèn)題的一般方法4.3決策樹(shù)歸納4.3.1決策樹(shù)的工作原理4.3.2如何建立決策樹(shù)補(bǔ)充：ID3決策樹(shù)詳解（后繼C4.5）4.3.3表示屬性測(cè)試條件的方法4.3.4選擇最佳劃分的度量4.4模型的過(guò)分?jǐn)M合

怎樣選擇最佳劃分？選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度。不純性的程度越低，類(lèi)分布就越傾斜結(jié)點(diǎn)不純性的度量:不純性大不純性小結(jié)點(diǎn)不純性的測(cè)量GiniEntropyclassificationerror不純性的測(cè)量:GINI給定結(jié)點(diǎn)t的Gini值計(jì)算:

(p(j|t)是在結(jié)點(diǎn)t中，類(lèi)j發(fā)生的概率).當(dāng)類(lèi)分布均衡時(shí)，Gini值達(dá)到最大值(1-1/nc)相反當(dāng)只有一個(gè)類(lèi)時(shí)，Gini值達(dá)到最小值0計(jì)算GINI的例子P(C1)=0/6=0P(C2)=6/6=1Gini=1–P(C1)2–P(C2)2=1–0–1=0P(C1)=1/6P(C2)=5/6Gini=1–(1/6)2–(5/6)2=0.278P(C1)=2/6P(C2)=4/6Gini=1–(2/6)2–(4/6)2=0.444基于GINI的劃分當(dāng)一個(gè)結(jié)點(diǎn)p分割成k個(gè)部分(孩子),劃分的質(zhì)量可由下面公式計(jì)算

ni=孩子結(jié)點(diǎn)i的記錄數(shù), n

=父結(jié)點(diǎn)p的記錄數(shù).基于ClassificationError的劃分給定結(jié)點(diǎn)t的ClassificationError值計(jì)算

:當(dāng)類(lèi)分布均衡時(shí)，error值達(dá)到最大值(1-1/nc)相反當(dāng)只有一個(gè)類(lèi)時(shí)，error值達(dá)到最小值0例子P(C1)=0/6=0P(C2)=6/6=1Error=1–max(0,1)=1–1=0P(C1)=1/6P(C2)=5/6Error=1–max(1/6,5/6)=1–5/6=1/6P(C1)=2/6P(C2)=4/6Error=1–max(2/6,4/6)=1–4/6=1/3不純性度量之間的比較二元分類(lèi)問(wèn)題:4.1預(yù)備知識(shí)4.2解決分類(lèi)問(wèn)題的一般方法4.3決策樹(shù)歸納4.3.1決策樹(shù)的工作原理4.3.2如何建立決策樹(shù)補(bǔ)充：ID3決策樹(shù)詳解（后繼C4.5）4.3.3表示屬性測(cè)試條件的方法4.3.4選擇最佳劃分的度量4.4模型的過(guò)分?jǐn)M合

模型過(guò)分?jǐn)M合和擬合不足分類(lèi)模型的誤差大致分為兩種：訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類(lèi)樣本比例泛化誤差：是模型在未知記錄上的期望誤差一個(gè)好的分類(lèi)模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對(duì)未知樣本也要能準(zhǔn)確分類(lèi)。換句話說(shuō)，一個(gè)好的分類(lèi)模型必須具有低訓(xùn)練誤差和低泛化誤差。當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高，這種情況成為模型過(guò)分?jǐn)M合模型過(guò)分?jǐn)M合和擬合不足當(dāng)決策樹(shù)很小時(shí)，訓(xùn)練和檢驗(yàn)誤差都很大，這種情況稱(chēng)為模型擬合不足。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí)結(jié)構(gòu)。隨著決策樹(shù)中結(jié)點(diǎn)數(shù)的增加，模型的訓(xùn)練誤差和檢驗(yàn)誤差都會(huì)隨之下降。當(dāng)樹(shù)的規(guī)模變得太大時(shí)，即使訓(xùn)練誤差還在繼續(xù)降低，但是檢驗(yàn)誤差開(kāi)始增大，導(dǎo)致模型過(guò)分?jǐn)M合模型模型過(guò)分?jǐn)M合和擬合不足過(guò)分?jǐn)M合導(dǎo)致過(guò)分?jǐn)M合的原因（1、噪聲）導(dǎo)致過(guò)分?jǐn)M合的原因（1、噪聲）噪聲導(dǎo)致的過(guò)分?jǐn)M合例子：哺乳動(dòng)物的分類(lèi)問(wèn)題十個(gè)訓(xùn)練記錄中有兩個(gè)被錯(cuò)誤標(biāo)記：蝙蝠和鯨如果完全擬合訓(xùn)練數(shù)據(jù)，決策樹(shù)1的訓(xùn)練誤差為0，但它在檢驗(yàn)數(shù)據(jù)上的誤差達(dá)30%.人和海豚，針鼴誤分為非哺乳動(dòng)物相反，一個(gè)更簡(jiǎn)單的決策樹(shù)2，具有較低的檢驗(yàn)誤差（10%），盡管它的訓(xùn)練誤差較高，為20%決策樹(shù)1過(guò)分?jǐn)M合了訓(xùn)練數(shù)據(jù)。因?yàn)閷傩詼y(cè)試條件4條腿具有欺騙性，它擬合了誤標(biāo)記的訓(xùn)練紀(jì)錄，導(dǎo)致了對(duì)檢驗(yàn)集中記錄的誤分類(lèi)噪聲導(dǎo)致的過(guò)分?jǐn)M合（例子）噪聲導(dǎo)致決策邊界的改變導(dǎo)致過(guò)分?jǐn)M合的原因（2、缺乏代表性樣本）根據(jù)少量訓(xùn)練記錄做出分類(lèi)決策的模型也容易受過(guò)分?jǐn)M合的影響。由于訓(xùn)練數(shù)據(jù)缺乏具有代表性的樣本，在沒(méi)有多少訓(xùn)練記錄的情況下，學(xué)習(xí)算法仍然細(xì)化模型就會(huì)產(chǎn)生過(guò)分?jǐn)M合。導(dǎo)致過(guò)分?jǐn)M合的原因（2、缺乏代表性樣本）導(dǎo)致過(guò)分?jǐn)M合的原因（2、缺乏代表性樣本）例子：五個(gè)訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對(duì)應(yīng)的決策樹(shù)盡管訓(xùn)練誤差為0，但檢驗(yàn)誤差高達(dá)30%人、大象和海豚被誤分類(lèi)，因?yàn)闆Q策樹(shù)把恒溫但不冬眠的動(dòng)物分為非哺乳動(dòng)物。決策樹(shù)做出這樣的分類(lèi)決策是因?yàn)橹挥幸粋€(gè)訓(xùn)練記錄（鷹）具有這些特征。這個(gè)例子清楚的表明，當(dāng)決策樹(shù)的葉結(jié)點(diǎn)沒(méi)有足夠的代表性樣本時(shí)，很可能做出錯(cuò)誤的預(yù)測(cè)。處理決策樹(shù)中的過(guò)分?jǐn)M合先剪枝(EarlyStoppingRule)樹(shù)增長(zhǎng)算法在產(chǎn)生完全擬合整個(gè)訓(xùn)練數(shù)據(jù)集的之前就停止決策樹(shù)的生長(zhǎng)為了做到這一點(diǎn)，需要采用更具限制性的結(jié)束條件:

當(dāng)結(jié)點(diǎn)的記錄數(shù)少于一定閾值，則停止生長(zhǎng)當(dāng)不純性度量的增益低于某個(gè)確定的閾值時(shí)，則停止生長(zhǎng)(e.g.,informationgain).缺點(diǎn)：很難為提前終止選取正確的閾值:

閾值太高，導(dǎo)致擬合不足閾值太低，導(dǎo)致不能充分解決過(guò)分?jǐn)M合的問(wèn)題。處理決策樹(shù)中的過(guò)分?jǐn)M合…后剪枝在該方法中，初始決策樹(shù)按照最大規(guī)模生長(zhǎng)，然后進(jìn)行剪枝的步驟，按照自底向上的方式修剪完全增長(zhǎng)的決策樹(shù)。修剪有兩種做法:

用新的葉結(jié)點(diǎn)替換子樹(shù)，該葉結(jié)點(diǎn)的類(lèi)標(biāo)號(hào)由子樹(shù)下記錄中的多數(shù)類(lèi)確定用子樹(shù)中最常用的分支代替子樹(shù)處理決策樹(shù)中的過(guò)分?jǐn)M合…與先剪枝相比，后剪枝技術(shù)傾向于產(chǎn)生更好的結(jié)果。因?yàn)椴幌裣燃糁Γ蠹糁κ歉鶕?jù)完全增長(zhǎng)的決策樹(shù)作出的剪枝決策，先剪枝則可能過(guò)早終止決策樹(shù)的生長(zhǎng)。然而，對(duì)于后剪枝，當(dāng)子樹(shù)被剪掉后，生長(zhǎng)完全決策樹(shù)的額外開(kāi)銷(xiāo)就被浪費(fèi)了。第3章科學(xué)決策與信息分析主要內(nèi)容：信息分析在決策中的作用；各類(lèi)型決策中的信息保障；信息分析的工作流程。基本要求：了解各類(lèi)決策中信息利用的重要性；了解不同決策階段信息服務(wù)的特點(diǎn)；理解決策對(duì)信息的基本要求；掌握信息分析工作的基本流程。3.1信息分析在決策中的作用3.1.1決策活動(dòng)中的信息利用信息分析:是對(duì)情報(bào)進(jìn)行定向濃集和科學(xué)抽象的一種科學(xué)勞動(dòng).信息在軍事戰(zhàn)略制定中的作用；信息在制定地區(qū)經(jīng)濟(jì)發(fā)展規(guī)劃中的作用；信息在科學(xué)管理中的作用；信息在對(duì)外貿(mào)易中的作用；信息在制定生產(chǎn)計(jì)劃中的作用；信息在提高產(chǎn)品質(zhì)量、發(fā)展花色品種中的作用。3.1信息分析在決策中的作用3.1.2不同決策階段的信息服務(wù)決策階段信息服務(wù)的內(nèi)容與特點(diǎn)決策前（超前服務(wù)）促成決策及早完成（快）；有助于決策者掌握預(yù)測(cè)性信息（準(zhǔn)）；有助于決策者更新知識(shí)、增強(qiáng)判斷力（增）決策中（跟蹤服務(wù)）確立目標(biāo)階段；決策方案準(zhǔn)備階段；選定決策方案階段。決策后（反饋服務(wù)）跟蹤反饋；循環(huán)反饋；同步追蹤反饋。3.1信息分析在決策中的作用