第4章 分類：基本概念、決策樹(shù)與模型評(píng)估課件

數(shù)據(jù)挖掘

分類：基本概念、決策樹(shù)與模型評(píng)價(jià)第4章分類：基本概念、決策樹(shù)與模型評(píng)價(jià)數(shù)據(jù)挖掘

分類：基本概念、決策樹(shù)與模型評(píng)價(jià)第4章分類：基

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

分類的是利用一個(gè)分類函數(shù)（分類模型、分類器分類分類訓(xùn)練集：數(shù)據(jù)庫(kù)中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集。訓(xùn)練集中的單個(gè)元組稱為訓(xùn)練樣本,每個(gè)訓(xùn)練樣本有一個(gè)類別標(biāo)記。一個(gè)具體樣本的形式可為:(v1,v2,...,vn;c);其中vi表示屬性值,c表示類別。測(cè)試集：用于評(píng)估分類模型的準(zhǔn)確率訓(xùn)練集：數(shù)據(jù)庫(kù)中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集。數(shù)據(jù)分類——一個(gè)兩步過(guò)程(1)第一步，建立一個(gè)模型，描述預(yù)定數(shù)據(jù)類集和概念集假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)類標(biāo)號(hào)屬性確定學(xué)習(xí)模型可以用分類規(guī)則、決策樹(shù)或數(shù)學(xué)公式的形式提供數(shù)據(jù)分類——一個(gè)兩步過(guò)程(1)第一步，建立一個(gè)模型，描述預(yù)數(shù)據(jù)分類——一個(gè)兩步過(guò)程(2)第二步，使用模型，對(duì)將來(lái)的或未知的對(duì)象進(jìn)行分類首先評(píng)估模型的預(yù)測(cè)準(zhǔn)確率對(duì)每個(gè)測(cè)試樣本，將已知的類標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類預(yù)測(cè)比較模型在給定測(cè)試集上的準(zhǔn)確率是正確被模型分類的測(cè)試樣本的百分比測(cè)試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(xiàn)“過(guò)分適應(yīng)數(shù)據(jù)”的情況如果準(zhǔn)確性能被接受，則分類規(guī)則就可用來(lái)對(duì)新數(shù)據(jù)進(jìn)行分類數(shù)據(jù)分類——一個(gè)兩步過(guò)程(2)第二步，使用模型，對(duì)將來(lái)的或有監(jiān)督的學(xué)習(xí)VS.無(wú)監(jiān)督的學(xué)習(xí)有監(jiān)督的學(xué)習(xí)（用于分類）模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“監(jiān)督”下進(jìn)行新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類無(wú)監(jiān)督的學(xué)習(xí)（用于聚類）每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的通過(guò)一系列的度量、觀察來(lái)建立數(shù)據(jù)中的類編號(hào)或進(jìn)行聚類有監(jiān)督的學(xué)習(xí)VS.無(wú)監(jiān)督的學(xué)習(xí)有監(jiān)督的學(xué)習(xí)（用于分類）分類模型的構(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ī)則分類模型的構(gòu)造方法1.機(jī)器學(xué)習(xí)方法：一個(gè)決策樹(shù)的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried

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

Single,Divorced<80K>80K決策樹(shù)的另一個(gè)例子categoricalcategorica用決策樹(shù)歸納分類什么是決策樹(shù)？類似于流程圖的樹(shù)結(jié)構(gòu)每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試每個(gè)分枝代表一個(gè)測(cè)試輸出每個(gè)樹(shù)葉節(jié)點(diǎn)代表類或類分布決策樹(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)行分類通過(guò)將樣本的屬性值與決策樹(shù)相比較用決策樹(shù)歸納分類什么是決策樹(shù)？為了對(duì)未知數(shù)據(jù)對(duì)象進(jìn)行分類識(shí)別，可以根據(jù)決策樹(shù)的結(jié)構(gòu)對(duì)數(shù)據(jù)集中的屬性進(jìn)行測(cè)試，從決策樹(shù)的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就形成了相應(yīng)對(duì)象的類別測(cè)試。決策樹(shù)可以很容易轉(zhuǎn)換為分類規(guī)則為了對(duì)未知數(shù)據(jù)對(duì)象進(jìn)行分類識(shí)別，可以根據(jù)決策樹(shù)的結(jié)構(gòu)決策樹(shù)分類任務(wù)DecisionTree決策樹(shù)分類任務(wù)DecisionTree一個(gè)決策樹(shù)的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried

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

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

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

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

Single,Divorced<80K>80K測(cè)試數(shù)據(jù)應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESN應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K測(cè)試數(shù)據(jù)應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESN應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K測(cè)試數(shù)據(jù)AssignCheatto“No”應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESN決策樹(shù)分類DecisionTree決策樹(shù)分類DecisionTree決策樹(shù)有許多決策樹(shù)算法:Hunt算法信息增益——Informationgain

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

(SLIQ，SPRINT)決策樹(shù)有許多決策樹(shù)算法:Hunt算法設(shè)Dt

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

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

中包含屬于多個(gè)類的記錄，則選擇一個(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算法設(shè)Dt是與結(jié)點(diǎn)t相關(guān)聯(lián)的訓(xùn)練記錄集Dt?Hunt算法Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat<80K>=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedHunt算法Don’tRefundDon’tDon’t決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)估每種測(cè)試條件?如何停止分裂過(guò)程決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)估每種測(cè)試條件?如何停止分裂過(guò)程決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).怎樣為不同類型的屬性指定測(cè)試條件?依賴于屬性的類型標(biāo)稱序數(shù)連續(xù)依賴于劃分的路數(shù)2路劃分多路劃分怎樣為不同類型的屬性指定測(cè)試條件?依賴于屬性的類型基于標(biāo)稱屬性的分裂多路劃分:

劃分?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}基于標(biāo)稱屬性的分裂多路劃分:劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不多路劃分:

劃分?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}多路劃分:劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù).基基于連續(xù)屬性的劃分多路劃分:vi≤A＜vi+1（i=1,…,k)二元?jiǎng)澐?(A<v)or(Av)考慮所有的劃分點(diǎn)，選擇一個(gè)最佳劃分點(diǎn)v基于連續(xù)屬性的劃分基于連續(xù)屬性的劃分基于連續(xù)屬性的劃分決策樹(shù)決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)估每種測(cè)試條件?如何停止分裂過(guò)程決策樹(shù)怎樣選擇最佳劃分？在劃分前:10個(gè)記錄class0,

10個(gè)記錄class1怎樣選擇最佳劃分？在劃分前:10個(gè)記錄class0,怎樣選擇最佳劃分？選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度。不純性的程度越低，類分布就越傾斜結(jié)點(diǎn)不純性的度量:不純性大不純性小怎樣選擇最佳劃分？選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不怎樣找到最佳劃分？B?YesNoNodeN3NodeN4A?YesNoNodeN1NodeN2劃分前:M0M1M2M3M4M12M34Gain=M0–M12vsM0–M34怎樣找到最佳劃分？B?YesNoNodeN3NodeN4結(jié)點(diǎn)不純性的測(cè)量GiniEntropyclassificationerror結(jié)點(diǎn)不純性的測(cè)量Gini不純性的測(cè)量:GINI給定結(jié)點(diǎn)t的Gini值計(jì)算:

(p(j|t)是在結(jié)點(diǎn)t中，類j發(fā)生的概率).當(dāng)類分布均衡時(shí)，Gini值達(dá)到最大值(1-1/nc)相反當(dāng)只有一個(gè)類時(shí)，Gini值達(dá)到最小值0不純性的測(cè)量:GINI給定結(jié)點(diǎn)t的Gini值計(jì)算:計(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計(jì)算GINI的例子P(C1)=0/6=0基于GINI的劃分當(dāng)一個(gè)結(jié)點(diǎn)p分割成k個(gè)部分(孩子),劃分的質(zhì)量可由下面公式計(jì)算

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

=父結(jié)點(diǎn)p的記錄數(shù).基于GINI的劃分當(dāng)一個(gè)結(jié)點(diǎn)p分割成k個(gè)部分(孩二元屬性:計(jì)算GINI對(duì)于二元屬性，結(jié)點(diǎn)被劃分成兩個(gè)部分得到的GINI值越小，這種劃分越可行.B?YesNoNodeN1NodeN2Gini(N1)

=1–(5/6)2–(2/6)2

=0.194Gini(N2)

=1–(1/6)2–(4/6)2

=0.528Ginisplit

=7/12*0.194+

5/12*0.528

=0.333二元屬性:計(jì)算GINI對(duì)于二元屬性，結(jié)點(diǎn)被劃分成兩個(gè)部分標(biāo)稱屬性:計(jì)算Gini多路劃分二元?jiǎng)澐忠话愣嗦穭澐值腉ini值比二元?jiǎng)澐中?，這一結(jié)果并不奇怪，因?yàn)槎獎(jiǎng)澐謱?shí)際上合并了多路劃分的某些輸出，自然降低了子集的純度Multi-waysplitTwo-waysplit(findbestpartitionofvalues)標(biāo)稱屬性:計(jì)算Gini多路劃分Multi-waysplit連續(xù)屬性:計(jì)算Gini使用二元?jiǎng)澐謩澐贮c(diǎn)v選擇N個(gè)記錄中所有屬性值作為劃分點(diǎn)對(duì)每個(gè)劃分進(jìn)行類計(jì)數(shù),A<vandAv計(jì)算每個(gè)候選點(diǎn)v的Gini指標(biāo)，并從中選擇具有最小值的候選劃分點(diǎn)時(shí)間復(fù)雜度為(n2)連續(xù)屬性:計(jì)算Gini使用二元?jiǎng)澐诌B續(xù)屬性:計(jì)算Gini...降低計(jì)算復(fù)雜性的方法,將記錄進(jìn)行排序從兩個(gè)相鄰的排過(guò)序的屬性值之間選擇中間值作為劃分點(diǎn)計(jì)算每個(gè)候選點(diǎn)的Gini值時(shí)間復(fù)雜度為nlogn劃分點(diǎn)排序后的值連續(xù)屬性:計(jì)算Gini...降低計(jì)算復(fù)雜性的方法,劃分點(diǎn)

定義：給定一個(gè)概率空間事件的自信息定義為

因自信息反映了事件發(fā)生所需要的信息量。值越大說(shuō)明需要越多的信息才能確定事件的發(fā)生，其隨機(jī)性也越大，而當(dāng)發(fā)生時(shí)所攜帶的信息量也越大。反過(guò)來(lái)，值越小，需要較少信息量就能確定的發(fā)生，即事件隨機(jī)性較小。當(dāng)其發(fā)生時(shí)所攜信息量就少。是對(duì)不確定性大小的一種刻畫熵---定義定義：給定一個(gè)概率空間熵---定義1.定義：在概率空間上定義的隨機(jī)變量I(X)的數(shù)學(xué)期望

稱為隨機(jī)變量X的平均自信息，又稱X的信息熵或熵記為H(x)熵---定義1.定義：在概率空間非負(fù)性：H大于等于0連續(xù)性：H對(duì)任意q連續(xù)極值性：當(dāng)q都等于1\K時(shí)H達(dá)到最大值logK熵---定義非負(fù)性：H大于等于0熵---定義基于InformationGain的劃分給定結(jié)點(diǎn)t的Entropy值計(jì)算:(p(j|t)是在結(jié)點(diǎn)t中，類j發(fā)生的概率).當(dāng)類分布均衡時(shí)，Entropy值達(dá)到最大值(lognc)相反當(dāng)只有一個(gè)類時(shí)，Gini值達(dá)到最小值0Entropy與GINI相似基于InformationGain的劃分給定結(jié)點(diǎn)t的E計(jì)算Entropy的例子P(C1)=0/6=0P(C2)=6/6=1Entropy=–0log0

–1log1=–0–0=0P(C1)=1/6P(C2)=5/6Entropy=–(1/6)log2(1/6)

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

–(4/6)log2(4/6)=0.92計(jì)算Entropy的例子P(C1)=0/6=0基于InformationGain的劃分...InformationGain:

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

=結(jié)點(diǎn)p的記錄數(shù). 在ID3andC4.5中使用基于InformationGain的劃分...Infor基于InformationGain的劃分...增益率（GainRatio）:熵和Gini指標(biāo)等不純性趨向于有利于具有大量不同值的屬性!如：利用雇員id產(chǎn)生更純的劃分，但它卻毫無(wú)用處每個(gè)劃分相關(guān)聯(lián)的記錄數(shù)太少，將不能做出可靠的預(yù)測(cè)解決該問(wèn)題的策略有兩種：限制測(cè)試條件只能是二元?jiǎng)澐质褂迷鲆媛?。K越大SplitInfo越大增益率越小基于InformationGain的劃分...增益率（G基于ClassificationError的劃分給定結(jié)點(diǎn)t的ClassificationError值計(jì)算

:當(dāng)類分布均衡時(shí)，error值達(dá)到最大值(1-1/nc)相反當(dāng)只有一個(gè)類時(shí)，error值達(dá)到最小值0基于ClassificationError的劃分給定結(jié)點(diǎn)例子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例子P(C1)=0/6=0P(C2)=不純性度量之間的比較二元分類問(wèn)題:不純性度量之間的比較二元分類問(wèn)題:第4章分類：基本概念、決策樹(shù)與模型評(píng)估課件決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)估每種測(cè)試條件?如何停止分裂過(guò)程決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).停止分裂過(guò)程當(dāng)所有的記錄屬于同一類時(shí)，停止分裂當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂提前終止樹(shù)的生長(zhǎng)停止分裂過(guò)程當(dāng)所有的記錄屬于同一類時(shí)，停止分裂第4章分類：基本概念、決策樹(shù)與模型評(píng)估課件三種著名的決策樹(shù)Cart：基本的決策樹(shù)算法Id3：利用增益比不純性，樹(shù)采用二叉樹(shù)，停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類時(shí)，停止分裂，或當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂C4.5：id3的改進(jìn)版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。三種著名的決策樹(shù)Cart：基本的決策樹(shù)算法決策樹(shù)特點(diǎn):決策樹(shù)是一種構(gòu)建分類模型的非參數(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)代表的類，不能做出具有統(tǒng)計(jì)意義的判決子樹(shù)可能在決策樹(shù)中重復(fù)多次。使決策樹(shù)過(guò)于復(fù)雜決策樹(shù)特點(diǎn):子樹(shù)重復(fù)問(wèn)題

Samesubtreeappearsinmultiplebranches子樹(shù)重復(fù)問(wèn)題Samesubtreeappearsin決策邊界

決策邊界斜決策樹(shù)x+y<1Class=+

Class=斜決策樹(shù)x+y<1Class=+Class=模型過(guò)分?jǐn)M合和擬合不足分類模型的誤差大致分為兩種：訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類樣本比例泛化誤差：是模型在未知記錄上的期望誤差一個(gè)好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對(duì)未知樣本也要能準(zhǔn)確分類。換句話說(shuō)，一個(gè)好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高，這種情況成為模型過(guò)分?jǐn)M合模型過(guò)分?jǐn)M合和擬合不足分類模型的誤差大致分為兩種：模型過(guò)分?jǐn)M合和擬合不足當(dāng)決策樹(shù)很小時(shí)，訓(xùn)練和檢驗(yàn)誤差都很大，這種情況稱為模型擬合不足。出現(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合和擬合不足當(dāng)決策樹(shù)很小時(shí)，訓(xùn)練和檢驗(yàn)誤差都很大，模型模型過(guò)分?jǐn)M合和擬合不足過(guò)分?jǐn)M合模型模型過(guò)分?jǐn)M合和擬合不足過(guò)分?jǐn)M合導(dǎo)致過(guò)分?jǐn)M合的原因?qū)е逻^(guò)分?jǐn)M合的原因?qū)е逻^(guò)分?jǐn)M合的原因噪聲導(dǎo)致的過(guò)分?jǐn)M合例子：哺乳動(dòng)物的分類問(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)集中記錄的誤分類導(dǎo)致過(guò)分?jǐn)M合的原因噪聲導(dǎo)致的過(guò)分?jǐn)M合噪聲導(dǎo)致的過(guò)分?jǐn)M合（例子）噪聲導(dǎo)致決策邊界的改變?cè)肼晫?dǎo)致的過(guò)分?jǐn)M合（例子）噪聲導(dǎo)致決策邊界的改變?nèi)狈Υ硇詷颖緦?dǎo)致的過(guò)分?jǐn)M合根據(jù)少量訓(xùn)練記錄做出分類決策的模型也容易受過(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合根據(jù)少量訓(xùn)練記錄做出分類決策的模第4章分類：基本概念、決策樹(shù)與模型評(píng)估課件例子：五個(gè)訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對(duì)應(yīng)的決策樹(shù)盡管訓(xùn)練誤差為0，但檢驗(yàn)誤差高達(dá)30%人、大象和海豚被誤分類，因?yàn)闆Q策樹(shù)把恒溫但不冬眠的動(dòng)物分為非哺乳動(dòng)物。決策樹(shù)做出這樣的分類決策是因?yàn)橹挥幸粋€(gè)訓(xùn)練記錄（鷹）具有這些特征。這個(gè)例子清楚的表明，當(dāng)決策樹(shù)的葉結(jié)點(diǎn)沒(méi)有足夠的代表性樣本時(shí)，很可能做出錯(cuò)誤的預(yù)測(cè)。例子：五個(gè)訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對(duì)應(yīng)的決策樹(shù)盡過(guò)分?jǐn)M合與多重比較模型的過(guò)分?jǐn)M合可能出現(xiàn)在使用多重比較過(guò)程的算法中多重比較的例子：考慮未來(lái)十個(gè)交易日股市是升還是降一個(gè)人十次猜測(cè)至少正確預(yù)測(cè)八次的概率是：0.0547假設(shè)從50個(gè)股票分析家中選擇一個(gè)投資顧問(wèn)，策略是選擇在未來(lái)的十個(gè)交易日做出最多正確預(yù)測(cè)的分析家。該策略的缺點(diǎn)是，即使所有的分析家都用隨機(jī)猜測(cè)做出預(yù)測(cè)，至少有一個(gè)分析家做出八次正確預(yù)測(cè)的概率是：1-（1-0.0547）50=0.9399，這一結(jié)果相當(dāng)高。過(guò)分?jǐn)M合與多重比較模型的過(guò)分?jǐn)M合可能出現(xiàn)在使用多重比較過(guò)程的多重比較過(guò)程與模型過(guò)分?jǐn)M合有什么關(guān)系？在決策樹(shù)增長(zhǎng)過(guò)程中，可以進(jìn)行多種測(cè)試，以確定哪個(gè)屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。在這種情況下，算法實(shí)際上是使用多重比較過(guò)程來(lái)決定是否需要擴(kuò)展決策樹(shù)。當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時(shí)，這種影響就變得更加明顯。多重比較過(guò)程與模型過(guò)分?jǐn)M合有什么關(guān)系？泛化誤差估計(jì)過(guò)分?jǐn)M合的主要原因一直是個(gè)爭(zhēng)辯的話題，但大家還是普遍同意模型的復(fù)雜度對(duì)模型的過(guò)分?jǐn)M合有影響。如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度。估計(jì)泛化誤差的方法使用再代入估計(jì)。用訓(xùn)練誤差提供對(duì)泛化誤差的樂(lè)觀估計(jì)結(jié)合模型復(fù)雜度估計(jì)統(tǒng)計(jì)上界使用確定集泛化誤差估計(jì)過(guò)分?jǐn)M合的主要原因一直是個(gè)爭(zhēng)辯的話題，但大家還是第4章分類：基本概念、決策樹(shù)與模型評(píng)估課件結(jié)合模型復(fù)雜度奧卡姆剃刀（Occam'sRazor）：給定兩個(gè)具有相同泛化誤差的模型，較簡(jiǎn)單的模型比復(fù)雜的模型更可取

因?yàn)閺?fù)雜模型中的附加成分很大程度上是偶然的擬合。因此，分類模型評(píng)估應(yīng)把模型復(fù)雜度考慮進(jìn)去方法：悲觀誤差估計(jì)、最小描述長(zhǎng)度原則（MDL）結(jié)合模型復(fù)雜度奧卡姆剃刀（Occam'sRazor）：悲觀誤差評(píng)估悲觀誤差估計(jì)公式：Q(ti)為每個(gè)結(jié)點(diǎn)ti的罰分，e(T)為訓(xùn)練樣本集的錯(cuò)分樣本數(shù)，Nt為訓(xùn)練樣本總數(shù)，k為葉結(jié)點(diǎn)數(shù)。悲觀誤差評(píng)估第4章分類：基本概念、決策樹(shù)與模型評(píng)估課件例子1：如果罰分等于0.5，訓(xùn)練樣本集中樣本數(shù)為24個(gè)，我們構(gòu)建了7個(gè)葉結(jié)點(diǎn)的決策樹(shù)，訓(xùn)練樣本集的錯(cuò)分樣本數(shù)為4根據(jù)公式我們得e’(T)=(4+7*0.5)/24=0.3125例子2：如果罰分等于0.5，訓(xùn)練樣本集中樣本數(shù)為24個(gè)，我們構(gòu)建了4個(gè)葉結(jié)點(diǎn)的決策樹(shù)，訓(xùn)練樣本集的錯(cuò)分樣本數(shù)為6根據(jù)公式我們得e’(T)=(6+4*0.5)/24=0.3333當(dāng)罰分等于1時(shí)，例1，2為0.458，0.4170.5的罰分項(xiàng)表示只要至少能夠改進(jìn)一個(gè)訓(xùn)練記錄的分類，結(jié)點(diǎn)就應(yīng)當(dāng)擴(kuò)充，因?yàn)閿U(kuò)展一個(gè)結(jié)點(diǎn)等價(jià)于總誤差增加0.5，代價(jià)比犯一個(gè)訓(xùn)練錯(cuò)誤小例子1：如果罰分等于0.5，訓(xùn)練樣本集中樣本數(shù)為24個(gè)，我們最小描述長(zhǎng)度(MDL)Cost(Model,Data)=Cost(Data|Model)+Cost(Model)Cost是傳輸總代價(jià).最小化cost值.Cost(Data|Model)是誤分類記錄編碼的開(kāi)銷.Cost(Model)是模型編碼的開(kāi)銷.最小描述長(zhǎng)度(MDL)Cost(Model,Data)=使用確認(rèn)集該方法中，不是用訓(xùn)練集估計(jì)泛化誤差，而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個(gè)較小的子集，一個(gè)子集用于訓(xùn)練，而另一個(gè)稱為確認(rèn)集，用于估計(jì)泛化誤差。該方法為評(píng)估模型在未知樣本上的性能提供了較好辦法。使用確認(rèn)集該方法中，不是用訓(xùn)練集估計(jì)泛化誤差，而是把原始的訓(xùn)處理決策樹(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合先剪枝(EarlyStopping處理決策樹(shù)中的過(guò)分?jǐn)M合…后剪枝在該方法中，初始決策樹(shù)按照最大規(guī)模生長(zhǎng)，然后進(jìn)行剪枝的步驟，按照自底向上的方式修剪完全增長(zhǎng)的決策樹(shù)。修剪有兩種做法:

用新的葉結(jié)點(diǎn)替換子樹(shù)，該葉結(jié)點(diǎn)的類標(biāo)號(hào)由子樹(shù)下記錄中的多數(shù)類確定用子樹(shù)中最常用的分支代替子樹(shù)處理決策樹(shù)中的過(guò)分?jǐn)M合…后剪枝處理決策樹(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)銷就被浪費(fèi)了。處理決策樹(shù)中的過(guò)分?jǐn)M合…不平衡類問(wèn)題PREDICTEDCLASS

ACTUAL

CLASSClass=YesClass=NoClass=Yesa

(TP)b

(FN)Class=Noc

(FP)d

(TN)不平衡類問(wèn)題PREDICTEDCLASS

Class=Ye準(zhǔn)確率的缺點(diǎn)考慮2類問(wèn)題類0的樣本數(shù)=9990類1的樣本數(shù)=10如果模型預(yù)測(cè)所有的樣本為類0,準(zhǔn)確率為9990/10000=99.9%準(zhǔn)確率的值具有欺騙性模型并沒(méi)有分對(duì)類1的任何樣本準(zhǔn)確率的缺點(diǎn)考慮2類問(wèn)題度量度量精度確定在分類器斷言為正類的那部分記錄中實(shí)際為正類的記錄所占的比例。精度越高，分類器的假正類錯(cuò)誤率就越低。召回率度量被分類器正確預(yù)測(cè)的正樣本的比例。具有高召回率的分類器很少將正樣本誤分為負(fù)樣本。精度確定在分類器斷言為正類的那部分記錄中實(shí)際為正類的記錄所占ROC(ReceiverOperatingCharacteristic)ROC曲線是顯示分類器真正率（TPR）和假正率（FPR）之間折中的一種圖形化方法。ROC曲線上有幾個(gè)關(guān)鍵點(diǎn)，它們有公認(rèn)的解釋：（TPR=0，F(xiàn)PR=0）：把每個(gè)實(shí)例都預(yù)測(cè)為負(fù)類的模型（TPR=1，F(xiàn)PR=1）：把每個(gè)實(shí)例都預(yù)測(cè)為正類的模型（TPR=1，F(xiàn)PR=0）：理想模型ROC(ReceiverOperatingCharac使用ROC曲線比較模型沒(méi)有哪個(gè)模型能夠壓倒對(duì)方FRR<0.36,M1

較好FRR>0.36,M2較好ROC曲線下方的面積理想情況:

面積=1隨機(jī)猜測(cè):

面積=0.5使用ROC曲線比較模型沒(méi)有哪個(gè)模型能夠壓倒對(duì)方怎樣產(chǎn)生ROC曲線Threshold>=ROC曲線:怎樣產(chǎn)生ROC曲線Threshold>=ROC曲線:演講完畢，謝謝觀看！演講完畢，謝謝觀看！數(shù)據(jù)挖掘

分類：基本概念、決策樹(shù)與模型評(píng)價(jià)第4章分類：基本概念、決策樹(shù)與模型評(píng)價(jià)數(shù)據(jù)挖掘

分類：基本概念、決策樹(shù)與模型評(píng)價(jià)第4章分類：基

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

分類的是利用一個(gè)分類函數(shù)（分類模型、分類器分類分類訓(xùn)練集：數(shù)據(jù)庫(kù)中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集。訓(xùn)練集中的單個(gè)元組稱為訓(xùn)練樣本,每個(gè)訓(xùn)練樣本有一個(gè)類別標(biāo)記。一個(gè)具體樣本的形式可為:(v1,v2,...,vn;c);其中vi表示屬性值,c表示類別。測(cè)試集：用于評(píng)估分類模型的準(zhǔn)確率訓(xùn)練集：數(shù)據(jù)庫(kù)中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集。數(shù)據(jù)分類——一個(gè)兩步過(guò)程(1)第一步，建立一個(gè)模型，描述預(yù)定數(shù)據(jù)類集和概念集假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)類標(biāo)號(hào)屬性確定學(xué)習(xí)模型可以用分類規(guī)則、決策樹(shù)或數(shù)學(xué)公式的形式提供數(shù)據(jù)分類——一個(gè)兩步過(guò)程(1)第一步，建立一個(gè)模型，描述預(yù)數(shù)據(jù)分類——一個(gè)兩步過(guò)程(2)第二步，使用模型，對(duì)將來(lái)的或未知的對(duì)象進(jìn)行分類首先評(píng)估模型的預(yù)測(cè)準(zhǔn)確率對(duì)每個(gè)測(cè)試樣本，將已知的類標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類預(yù)測(cè)比較模型在給定測(cè)試集上的準(zhǔn)確率是正確被模型分類的測(cè)試樣本的百分比測(cè)試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(xiàn)“過(guò)分適應(yīng)數(shù)據(jù)”的情況如果準(zhǔn)確性能被接受，則分類規(guī)則就可用來(lái)對(duì)新數(shù)據(jù)進(jìn)行分類數(shù)據(jù)分類——一個(gè)兩步過(guò)程(2)第二步，使用模型，對(duì)將來(lái)的或有監(jiān)督的學(xué)習(xí)VS.無(wú)監(jiān)督的學(xué)習(xí)有監(jiān)督的學(xué)習(xí)（用于分類）模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“監(jiān)督”下進(jìn)行新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類無(wú)監(jiān)督的學(xué)習(xí)（用于聚類）每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的通過(guò)一系列的度量、觀察來(lái)建立數(shù)據(jù)中的類編號(hào)或進(jìn)行聚類有監(jiān)督的學(xué)習(xí)VS.無(wú)監(jiān)督的學(xué)習(xí)有監(jiān)督的學(xué)習(xí)（用于分類）分類模型的構(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ī)則分類模型的構(gòu)造方法1.機(jī)器學(xué)習(xí)方法：一個(gè)決策樹(shù)的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried

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

Single,Divorced<80K>80K決策樹(shù)的另一個(gè)例子categoricalcategorica用決策樹(shù)歸納分類什么是決策樹(shù)？類似于流程圖的樹(shù)結(jié)構(gòu)每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試每個(gè)分枝代表一個(gè)測(cè)試輸出每個(gè)樹(shù)葉節(jié)點(diǎn)代表類或類分布決策樹(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)行分類通過(guò)將樣本的屬性值與決策樹(shù)相比較用決策樹(shù)歸納分類什么是決策樹(shù)？為了對(duì)未知數(shù)據(jù)對(duì)象進(jìn)行分類識(shí)別，可以根據(jù)決策樹(shù)的結(jié)構(gòu)對(duì)數(shù)據(jù)集中的屬性進(jìn)行測(cè)試，從決策樹(shù)的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就形成了相應(yīng)對(duì)象的類別測(cè)試。決策樹(shù)可以很容易轉(zhuǎn)換為分類規(guī)則為了對(duì)未知數(shù)據(jù)對(duì)象進(jìn)行分類識(shí)別，可以根據(jù)決策樹(shù)的結(jié)構(gòu)決策樹(shù)分類任務(wù)DecisionTree決策樹(shù)分類任務(wù)DecisionTree一個(gè)決策樹(shù)的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried

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

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

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

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

Single,Divorced<80K>80K測(cè)試數(shù)據(jù)應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESN應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K測(cè)試數(shù)據(jù)應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESN應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K測(cè)試數(shù)據(jù)AssignCheatto“No”應(yīng)用決策樹(shù)進(jìn)行分類RefundMarStTaxIncYESN決策樹(shù)分類DecisionTree決策樹(shù)分類DecisionTree決策樹(shù)有許多決策樹(shù)算法:Hunt算法信息增益——Informationgain

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

(SLIQ，SPRINT)決策樹(shù)有許多決策樹(shù)算法:Hunt算法設(shè)Dt

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

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

中包含屬于多個(gè)類的記錄，則選擇一個(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算法設(shè)Dt是與結(jié)點(diǎn)t相關(guān)聯(lián)的訓(xùn)練記錄集Dt?Hunt算法Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat<80K>=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedHunt算法Don’tRefundDon’tDon’t決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)估每種測(cè)試條件?如何停止分裂過(guò)程決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)估每種測(cè)試條件?如何停止分裂過(guò)程決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).怎樣為不同類型的屬性指定測(cè)試條件?依賴于屬性的類型標(biāo)稱序數(shù)連續(xù)依賴于劃分的路數(shù)2路劃分多路劃分怎樣為不同類型的屬性指定測(cè)試條件?依賴于屬性的類型基于標(biāo)稱屬性的分裂多路劃分:

劃分?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}基于標(biāo)稱屬性的分裂多路劃分:劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不多路劃分:

劃分?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}多路劃分:劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù).基基于連續(xù)屬性的劃分多路劃分:vi≤A＜vi+1（i=1,…,k)二元?jiǎng)澐?(A<v)or(Av)考慮所有的劃分點(diǎn)，選擇一個(gè)最佳劃分點(diǎn)v基于連續(xù)屬性的劃分基于連續(xù)屬性的劃分基于連續(xù)屬性的劃分決策樹(shù)決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)估每種測(cè)試條件?如何停止分裂過(guò)程決策樹(shù)怎樣選擇最佳劃分？在劃分前:10個(gè)記錄class0,

10個(gè)記錄class1怎樣選擇最佳劃分？在劃分前:10個(gè)記錄class0,怎樣選擇最佳劃分？選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度。不純性的程度越低，類分布就越傾斜結(jié)點(diǎn)不純性的度量:不純性大不純性小怎樣選擇最佳劃分？選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不怎樣找到最佳劃分？B?YesNoNodeN3NodeN4A?YesNoNodeN1NodeN2劃分前:M0M1M2M3M4M12M34Gain=M0–M12vsM0–M34怎樣找到最佳劃分？B?YesNoNodeN3NodeN4結(jié)點(diǎn)不純性的測(cè)量GiniEntropyclassificationerror結(jié)點(diǎn)不純性的測(cè)量Gini不純性的測(cè)量:GINI給定結(jié)點(diǎn)t的Gini值計(jì)算:

(p(j|t)是在結(jié)點(diǎn)t中，類j發(fā)生的概率).當(dāng)類分布均衡時(shí)，Gini值達(dá)到最大值(1-1/nc)相反當(dāng)只有一個(gè)類時(shí)，Gini值達(dá)到最小值0不純性的測(cè)量:GINI給定結(jié)點(diǎn)t的Gini值計(jì)算:計(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計(jì)算GINI的例子P(C1)=0/6=0基于GINI的劃分當(dāng)一個(gè)結(jié)點(diǎn)p分割成k個(gè)部分(孩子),劃分的質(zhì)量可由下面公式計(jì)算

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

=父結(jié)點(diǎn)p的記錄數(shù).基于GINI的劃分當(dāng)一個(gè)結(jié)點(diǎn)p分割成k個(gè)部分(孩二元屬性:計(jì)算GINI對(duì)于二元屬性，結(jié)點(diǎn)被劃分成兩個(gè)部分得到的GINI值越小，這種劃分越可行.B?YesNoNodeN1NodeN2Gini(N1)

=1–(5/6)2–(2/6)2

=0.194Gini(N2)

=1–(1/6)2–(4/6)2

=0.528Ginisplit

=7/12*0.194+

5/12*0.528

=0.333二元屬性:計(jì)算GINI對(duì)于二元屬性，結(jié)點(diǎn)被劃分成兩個(gè)部分標(biāo)稱屬性:計(jì)算Gini多路劃分二元?jiǎng)澐忠话愣嗦穭澐值腉ini值比二元?jiǎng)澐中?，這一結(jié)果并不奇怪，因?yàn)槎獎(jiǎng)澐謱?shí)際上合并了多路劃分的某些輸出，自然降低了子集的純度Multi-waysplitTwo-waysplit(findbestpartitionofvalues)標(biāo)稱屬性:計(jì)算Gini多路劃分Multi-waysplit連續(xù)屬性:計(jì)算Gini使用二元?jiǎng)澐謩澐贮c(diǎn)v選擇N個(gè)記錄中所有屬性值作為劃分點(diǎn)對(duì)每個(gè)劃分進(jìn)行類計(jì)數(shù),A<vandAv計(jì)算每個(gè)候選點(diǎn)v的Gini指標(biāo)，并從中選擇具有最小值的候選劃分點(diǎn)時(shí)間復(fù)雜度為(n2)連續(xù)屬性:計(jì)算Gini使用二元?jiǎng)澐诌B續(xù)屬性:計(jì)算Gini...降低計(jì)算復(fù)雜性的方法,將記錄進(jìn)行排序從兩個(gè)相鄰的排過(guò)序的屬性值之間選擇中間值作為劃分點(diǎn)計(jì)算每個(gè)候選點(diǎn)的Gini值時(shí)間復(fù)雜度為nlogn劃分點(diǎn)排序后的值連續(xù)屬性:計(jì)算Gini...降低計(jì)算復(fù)雜性的方法,劃分點(diǎn)

定義：給定一個(gè)概率空間事件的自信息定義為

因自信息反映了事件發(fā)生所需要的信息量。值越大說(shuō)明需要越多的信息才能確定事件的發(fā)生，其隨機(jī)性也越大，而當(dāng)發(fā)生時(shí)所攜帶的信息量也越大。反過(guò)來(lái)，值越小，需要較少信息量就能確定的發(fā)生，即事件隨機(jī)性較小。當(dāng)其發(fā)生時(shí)所攜信息量就少。是對(duì)不確定性大小的一種刻畫熵---定義定義：給定一個(gè)概率空間熵---定義1.定義：在概率空間上定義的隨機(jī)變量I(X)的數(shù)學(xué)期望

稱為隨機(jī)變量X的平均自信息，又稱X的信息熵或熵記為H(x)熵---定義1.定義：在概率空間非負(fù)性：H大于等于0連續(xù)性：H對(duì)任意q連續(xù)極值性：當(dāng)q都等于1\K時(shí)H達(dá)到最大值logK熵---定義非負(fù)性：H大于等于0熵---定義基于InformationGain的劃分給定結(jié)點(diǎn)t的Entropy值計(jì)算:(p(j|t)是在結(jié)點(diǎn)t中，類j發(fā)生的概率).當(dāng)類分布均衡時(shí)，Entropy值達(dá)到最大值(lognc)相反當(dāng)只有一個(gè)類時(shí)，Gini值達(dá)到最小值0Entropy與GINI相似基于InformationGain的劃分給定結(jié)點(diǎn)t的E計(jì)算Entropy的例子P(C1)=0/6=0P(C2)=6/6=1Entropy=–0log0

–1log1=–0–0=0P(C1)=1/6P(C2)=5/6Entropy=–(1/6)log2(1/6)

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

–(4/6)log2(4/6)=0.92計(jì)算Entropy的例子P(C1)=0/6=0基于InformationGain的劃分...InformationGain:

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

=結(jié)點(diǎn)p的記錄數(shù). 在ID3andC4.5中使用基于InformationGain的劃分...Infor基于InformationGain的劃分...增益率（GainRatio）:熵和Gini指標(biāo)等不純性趨向于有利于具有大量不同值的屬性!如：利用雇員id產(chǎn)生更純的劃分，但它卻毫無(wú)用處每個(gè)劃分相關(guān)聯(lián)的記錄數(shù)太少，將不能做出可靠的預(yù)測(cè)解決該問(wèn)題的策略有兩種：限制測(cè)試條件只能是二元?jiǎng)澐质褂迷鲆媛?。K越大SplitInfo越大增益率越小基于InformationGain的劃分...增益率（G基于ClassificationError的劃分給定結(jié)點(diǎn)t的ClassificationError值計(jì)算

:當(dāng)類分布均衡時(shí)，error值達(dá)到最大值(1-1/nc)相反當(dāng)只有一個(gè)類時(shí)，error值達(dá)到最小值0基于ClassificationError的劃分給定結(jié)點(diǎn)例子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例子P(C1)=0/6=0P(C2)=不純性度量之間的比較二元分類問(wèn)題:不純性度量之間的比較二元分類問(wèn)題:第4章分類：基本概念、決策樹(shù)與模型評(píng)估課件決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)估每種測(cè)試條件?如何停止分裂過(guò)程決策樹(shù)Hunt算法采用貪心策略構(gòu)建決策樹(shù).停止分裂過(guò)程當(dāng)所有的記錄屬于同一類時(shí)，停止分裂當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂提前終止樹(shù)的生長(zhǎng)停止分裂過(guò)程當(dāng)所有的記錄屬于同一類時(shí)，停止分裂第4章分類：基本概念、決策樹(shù)與模型評(píng)估課件三種著名的決策樹(shù)Cart：基本的決策樹(shù)算法Id3：利用增益比不純性，樹(shù)采用二叉樹(shù)，停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類時(shí)，停止分裂，或當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂C4.5：id3的改進(jìn)版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。三種著名的決策樹(shù)Cart：基本的決策樹(shù)算法決策樹(shù)特點(diǎn):決策樹(shù)是一種構(gòu)建分類模型的非參數(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)代表的類，不能做出具有統(tǒng)計(jì)意義的判決子樹(shù)可能在決策樹(shù)中重復(fù)多次。使決策樹(shù)過(guò)于復(fù)雜決策樹(shù)特點(diǎn):子樹(shù)重復(fù)問(wèn)題

Samesubtreeappearsinmultiplebranches子樹(shù)重復(fù)問(wèn)題Samesubtreeappearsin決策邊界

決策邊界斜決策樹(shù)x+y<1Class=+

Class=斜決策樹(shù)x+y<1Class=+Class=模型過(guò)分?jǐn)M合和擬合不足分類模型的誤差大致分為兩種：訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類樣本比例泛化誤差：是模型在未知記錄上的期望誤差一個(gè)好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對(duì)未知樣本也要能準(zhǔn)確分類。換句話說(shuō)，一個(gè)好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高，這種情況成為模型過(guò)分?jǐn)M合模型過(guò)分?jǐn)M合和擬合不足分類模型的誤差大致分為兩種：模型過(guò)分?jǐn)M合和擬合不足當(dāng)決策樹(shù)很小時(shí)，訓(xùn)練和檢驗(yàn)誤差都很大，這種情況稱為模型擬合不足。出現(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合和擬合不足當(dāng)決策樹(shù)很小時(shí)，訓(xùn)練和檢驗(yàn)誤差都很大，模型模型過(guò)分?jǐn)M合和擬合不足過(guò)分?jǐn)M合模型模型過(guò)分?jǐn)M合和擬合不足過(guò)分?jǐn)M合導(dǎo)致過(guò)分?jǐn)M合的原因?qū)е逻^(guò)分?jǐn)M合的原因?qū)е逻^(guò)分?jǐn)M合的原因噪聲導(dǎo)致的過(guò)分?jǐn)M合例子：哺乳動(dòng)物的分類問(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)集中記錄的誤分類導(dǎo)致過(guò)分?jǐn)M合的原因噪聲導(dǎo)致的過(guò)分?jǐn)M合噪聲導(dǎo)致的過(guò)分?jǐn)M合（例子）噪聲導(dǎo)致決策邊界的改變?cè)肼晫?dǎo)致的過(guò)分?jǐn)M合（例子）噪聲導(dǎo)致決策邊界的改變?nèi)狈Υ硇詷颖緦?dǎo)致的過(guò)分?jǐn)M合根據(jù)少量訓(xùn)練記錄做出分類決策的模型也容易受過(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合根據(jù)少量訓(xùn)練記錄做出分類決策的模第4章分類：基本概念、決策樹(shù)與模型評(píng)估課件例子：五個(gè)訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對(duì)應(yīng)的決策樹(shù)盡管訓(xùn)練誤差為0，但檢驗(yàn)誤差高達(dá)30%人、大象和海豚被誤分類，因?yàn)闆Q策樹(shù)把恒溫但不冬眠的動(dòng)物分為非哺乳動(dòng)物。決策樹(shù)做出這樣的分類決策是因?yàn)橹挥幸粋€(gè)訓(xùn)練記錄（鷹）具有這些特征。這個(gè)例子清楚的表明，當(dāng)決策樹(shù)的葉結(jié)點(diǎn)沒(méi)有足夠的代表性樣本時(shí)，很可能做出錯(cuò)誤的預(yù)測(cè)。例子：五個(gè)訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對(duì)應(yīng)的決策樹(shù)盡過(guò)分?jǐn)M合與多重比較模型的過(guò)分?jǐn)M合可能出現(xiàn)在使用多重比較過(guò)程的算法中多重比較的例子：考慮未來(lái)十個(gè)交易日股市是升還是降一個(gè)人十次猜測(cè)至少正確預(yù)測(cè)八次的概率是：0.0547假設(shè)從50個(gè)股票分析家中選擇一個(gè)投資顧問(wèn)，策略是選擇在未來(lái)的十個(gè)交易日做出最多正確預(yù)測(cè)的分析家。該策略的缺點(diǎn)是，即使所有的分析家都用隨機(jī)猜測(cè)做出預(yù)測(cè)，至少有一個(gè)分析家做出八次正確預(yù)測(cè)的概率是：1-（1-0.0547）50=0.9399，這一結(jié)果相當(dāng)高。過(guò)分?jǐn)M合與多重比較模型的過(guò)分?jǐn)M合可能出現(xiàn)在使用多重比較過(guò)程的多重比較過(guò)程與模型過(guò)分?jǐn)M合有什么關(guān)系？在決策樹(shù)增長(zhǎng)過(guò)程中，可以進(jìn)行多種測(cè)試，以確定哪個(gè)屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。在這種情況下，算