第6章分類預(yù)測基本概念分類Classification數(shù)據(jù)挖掘算法三大類之一關(guān)聯(lián)分析分類聚類分類什么是分類分類就是“貼標(biāo)簽”：描述性Descriptive預(yù)測性Predictive建立(分類)模型應(yīng)用模型屬性A=a1屬性B=b1屬性C=c1屬性A=a2屬性B=b5屬性C=c1……屬性A=a3屬性B=b2屬性C=c2X類Y類？類什么是分類輸入數(shù)據(jù)集分類模型屬性A=a1屬性B=b1屬性C=c1屬性A=a2屬性B=b2屬性C=c2屬性A=a3屬性B=b3屬性C=c3X類Y類Z類什么是分類輸入數(shù)據(jù)集輸出分類標(biāo)簽分類模型屬性A=a屬性B=b屬性C=c類別=Y？類分類的過程歸納(學(xué)習(xí)算法)推演分類模型檢驗(yàn)訓(xùn)練數(shù)據(jù)集測試數(shù)據(jù)集建立模型評估模型應(yīng)用模型

訓(xùn)練數(shù)據(jù)測試數(shù)據(jù)描述性Descriptive算法未分類數(shù)據(jù)預(yù)測性Predictive？？？？？分類的方法(算法)決策樹法貝葉斯算法人工神經(jīng)網(wǎng)絡(luò)隨機(jī)森林規(guī)則歸納近鄰學(xué)習(xí)基于關(guān)聯(lián)規(guī)則7第6章分類預(yù)測決策樹分類原理什么是決策樹？【例】工廠準(zhǔn)備擴(kuò)大電視機(jī)生產(chǎn)。市場預(yù)測表明：產(chǎn)品銷路好的概率為0.7；銷路差的概率為0.3。三個(gè)方案：建大廠，需要投資600萬元，可使用10年；如銷路好，每年可贏利200萬元；如銷路不好，每年會(huì)虧損40萬元。建小廠，需投資280萬元；如銷路好，每年可贏利80萬元；如銷路不好，每年只贏利60萬元。先建小廠，但是如銷路好，3年后擴(kuò)建，擴(kuò)建需投資400萬元，可使用7年，擴(kuò)建后每年會(huì)贏利190萬元。供選方案投資額(萬元)使用年限(年)盈利(萬元)銷路好P1=0.7銷路不好P2=0.3A1:建設(shè)大工廠60010200-40A2:建設(shè)小工廠280108060A3:先建小工廠，盈利好則3年后擴(kuò)建4007190601719萬元2680萬元200萬元-40萬元34930萬元5930萬元6560萬元190萬元80萬元60萬元建大廠建小廠銷路好(0.7)銷路差(0.3)銷路好(0.7)擴(kuò)建不擴(kuò)建銷路好(0.7)銷路好(0.7)銷路差(0.3)XX719萬元X決策樹分類決策樹分類算法，是利用決策樹的原理和結(jié)構(gòu)，構(gòu)造和生成形如決策樹的分類模型，發(fā)現(xiàn)和定義數(shù)據(jù)中蘊(yùn)涵的分類規(guī)則的過程。決策樹中每個(gè)內(nèi)部結(jié)點(diǎn)(非樹葉結(jié)點(diǎn))表示在一個(gè)屬性上的測試，每個(gè)分枝代表一個(gè)測試輸出，而每個(gè)樹葉結(jié)點(diǎn)存放一個(gè)類標(biāo)號。建立了決策樹，對于一個(gè)未給定類標(biāo)號的元組，跟蹤一條有根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑，該葉結(jié)點(diǎn)就存放著該元組的預(yù)測。決策樹分類的步驟：1)建立決策樹分類模型由訓(xùn)練樣本數(shù)據(jù)集生成決策樹分類模型。訓(xùn)練樣本數(shù)據(jù)集通常選用有一定積累的、有一定綜合程度的、用于數(shù)據(jù)分析處理的數(shù)據(jù)集。2)

測試并評估模型使用測試數(shù)據(jù)集，對決策樹模型進(jìn)行測試，根據(jù)測試誤差對分類模型進(jìn)行評估，并根據(jù)情況對模型通過剪枝等手段進(jìn)行進(jìn)行修正，以提高模型的預(yù)測準(zhǔn)確性。是對所生成的決策樹模型進(jìn)行檢驗(yàn)、校正和修正的過程。3)使用決策樹模型對未知分類的樣本數(shù)據(jù)，利用決策樹進(jìn)行分類判別。1.建立決策樹分類模型準(zhǔn)備數(shù)據(jù)(b)測試數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat11yesMarried95Kno12noMarried100Kno13noSingle95Kno14yesSingle70Kno15noDivorced5Kyes16noSingle60Kno(c)未分類數(shù)據(jù)TidRefundMaritalStatusIncomeCheat1yesSingle125K?2noMarried100K?3noSingle70K?(a)訓(xùn)練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyes1.建立決策樹分類模型根據(jù)訓(xùn)練數(shù)據(jù)建立決策樹yesRefundno/3……no(a)訓(xùn)練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no3noSingle70Kno5noDivorced95Kyes6noMarried60Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyes1.建立決策樹分類模型根據(jù)訓(xùn)練數(shù)據(jù)建立決策樹yesRefundno/3no(a)訓(xùn)練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no3noSingle70Kno5noDivorced95Kyes6noMarried60Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no6noMarried60Kno9noMarried75Kno3noSingle70Kno5noDivorced95Kyes8noSingle85Kyes10noSingle90KyesMarStno/3Single,Divorced………Married1.建立決策樹分類模型根據(jù)訓(xùn)練數(shù)據(jù)建立決策樹yesRefundno/3no(a)訓(xùn)練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no3noSingle70Kno5noDivorced95Kyes6noMarried60Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no6noMarried60Kno9noMarried75Kno3noSingle70Kno5noDivorced95Kyes8noSingle85Kyes10noSingle90KyesMarStno/3Incomeyes/3no/1<85k≥85kSingle,DivorcedMarried1.建立決策樹分類模型按此原理，從不同屬性開始，建立不同的分類決策樹(a)訓(xùn)練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat2noMarried100Kno6noMarried60Kno9noMarried75Kno4yesMarried120Kno1yesSingle125Kno7yesDivorced220Kno3noSingle70Kno8noSingle85Kyes10noSingle90Kyes5noDivorced95KyesyesMarStno/4RefundIncomeno/2no/1yes/3noSingle,DivorcedMarried<85K≥85K1.建立決策樹分類模型類似于流程圖的樹結(jié)構(gòu)每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測試每個(gè)分枝代表一個(gè)測試輸出每個(gè)樹葉節(jié)點(diǎn)代表類或類分布yesMarStno/4RefundIncomeno/2no/1yes/3noSingle,DivorcedMarried<85K≥85K2.測試并評估模型測試(b)測試數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat11yesMarried95Kno12noMarried100Kno13noSingle95Kno14yesSingle70Kno15noDivorced95Kyes16noSingle60Kno

誤差率=1/6可以接受，模型確定yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85K3.使用決策樹模型(c)未分類數(shù)據(jù)TidRefundMaritalStatusIncomeCheat1yesSingle125K?2noMarried100K?3noSingle70K?yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85Knonono思考？yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85KyesMarStno/4RefundIncomeno/2no/1yes/3noSingle,DivorcedMarried<85K≥85K以哪個(gè)屬性開始？(a)訓(xùn)練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyes思考？(a)訓(xùn)練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyescategoricalcategoricalcontinuousclass不同類型的屬性，是否處理的方法不同？yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85K(a)訓(xùn)練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyes思考？MarStSingle,divorcedMarriedIncome<60K70~75K60~70K75~85K≥220K125~200K……MarStSingleMarrieddivorced如何劃分多值屬性？Income<85K≥85K思考？yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85K(b)測試數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat11yesMarried95Kno12noMarried100Kno13noSingle95Kno14yesSingle70Kno15noDivorced95Kyes16noSingle60Kno

錯(cuò)誤率太大，如何解決？小結(jié)決策樹分類的基本概念決策樹分類應(yīng)用的基本過程建模（訓(xùn)練數(shù)據(jù)）檢驗(yàn)評估（測試數(shù)據(jù)）使用（未分類數(shù)據(jù)）幾個(gè)問題開始劃分的屬性不同類型的屬性的劃分方法第6章分類預(yù)測決策樹分類模型不同屬性的劃分方法劃分方法CarTypeFamilySportsLuxuryCarType{Family,Luxury}{Sports}CarType{Sports,Luxury}{Family}CarType{Family,Sports}{Luxury}劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù)。

劃分?jǐn)?shù)為2，這種劃分要考慮創(chuàng)建k個(gè)屬性值的二元?jiǎng)澐值乃?k-1-1種方法.多路劃分:二元?jiǎng)澐?劃分方法編號色澤根蒂敲聲紋理臍部觸感密度含糖率好瓜1青綠蜷縮濁響清晰凹陷硬滑0.4970.46是2烏黑蜷縮沉悶清晰凹陷硬滑0.5740.376是3烏黑蜷縮濁響清晰凹陷硬滑0.4340.264是4青綠蜷縮沉悶清晰凹陷硬滑0.6080.318是5青綠蜷縮濁響清晰凹陷硬滑0.3560.215是6青綠稍蜷濁響清晰稍凹軟粘0.4030.337是7烏黑稍蜷濁響稍糊稍凹軟粘0.4810.49是8烏黑蜷縮濁響清晰稍凹硬滑0.4370.511是9烏黑稍蜷沉悶稍糊平坦硬滑0.6660.091否10青綠硬挺清脆清晰平坦軟粘0.2430.067否11淺白硬挺清脆模糊平坦硬滑0.2450.057否12淺白蜷縮濁響模糊平坦軟粘0.3430.099否13青綠稍蜷濁響稍糊平坦硬滑0.6390.161否14淺白稍蜷沉悶稍糊凹陷硬滑0.6570.198否15烏黑稍蜷濁響清晰稍凹軟粘0.6360.37否16淺白硬挺濁響模糊平坦硬滑0.5930.042否17青綠蜷縮沉悶稍糊稍凹硬滑0.7190.103否劃分方法注意：二元?jiǎng)澐?Size{Medium,Large}{Small}Size{Small,Medium}{Large}ORSize{Small,Large}{Medium}劃分方法連續(xù)屬性多路劃分:vi≤A＜vi+1（i=1,…,k)二元?jiǎng)澐?(A<vi)or(A

vi)Income<50K>=50KIncome<10K>=80K{10K,25K}{25K,50K}{50K,80K}二元?jiǎng)澐侄嗦穭澐挚紤]所有的劃分點(diǎn)，選擇一個(gè)最佳劃分點(diǎn)v從哪個(gè)屬性開始：不純性20個(gè)記錄，未劃分時(shí):10個(gè)記錄class0(C0),

10個(gè)記錄class1(C1)性別C0：6C1：4C0：4C1：6男女車型C0：1C1：3C0：8C1：0家用運(yùn)動(dòng)C0：1C1：7豪華客戶號C0：1C1：0C0：1C1：0v1v2C0：0C1：1v20C0：0C1：1…客戶號性別車型…Class1男豪華…C02女家用…C03男豪華…C04女運(yùn)動(dòng)…C05男運(yùn)動(dòng)…C1……………19男運(yùn)動(dòng)…C120女家用…C1從哪個(gè)屬性開始：不純性不純性不純性大不純性小思考：劃分后，應(yīng)不純性大些較好，還是較小比較好？C0：5C1：5C0：9C1：1從哪個(gè)屬性開始：以劃分結(jié)果來衡量屬性BNodeN3NodeN4屬性Aa0a1NodeN1NodeN2劃分前:M0M1M2M3M4M12M34Gain=M0–M12

vs

Gain=M0

–M34C0N00C1N01C0N10C1N11C0N20C1N21C0N30C1N31C0N40C1N41b0b1衡量不純度熵Gini系數(shù)分類誤差

熵熵的概念最早起源于物理學(xué)，在物理學(xué)中是用來度量一個(gè)熱力學(xué)系統(tǒng)的無序程度在信息學(xué)里面，熵是對不確定性的度量。在1948年，香農(nóng)引入了信息熵將其定義為離散隨機(jī)事件出現(xiàn)的概率，信息熵是表示一個(gè)事件的不確定性的大小，不確定性越大那么該事件包含的信息熵就越大如果一個(gè)事件完全確定了，那么它所包含的信息熵就是0。-信息增益熵分類劃分n為數(shù)據(jù)類別的數(shù)目C為類別變量，取值為Ci，i=1,2,…,nCi類別出現(xiàn)的概率為

p(Ci)，i=1,2,…,n熵P(C0)=0/6=0P(C1)=6/6=1Entropy=–0

log20

–1

log21=–0–0=0P(C0)=1/6P(C1)=5/6Entropy=–(1/6)log2(1/6)

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

–(4/6)log2(4/6)=0.92C00C16C01C15C02C14P(C0)=3/6P(C1)=3/6Entropy=–(3/6)log2

(3/6)

–(3/6)log2

(3/6)=1C03C13信息增益根據(jù)熵來定義信息增益對于特征

t，系統(tǒng)具有或沒有該特征時(shí)的信息量的差值，就是這個(gè)特征給系統(tǒng)帶來的信息量，即信息增益。對于某一屬性

T，進(jìn)行屬性劃分的信息增益定義為：劃分前，數(shù)據(jù)的信息熵按屬性T

劃分后的信息熵信息增益具體可寫成：

其中

v是屬性

T的某個(gè)屬性值S為全部樣本集合Sv是

S中屬性

T的值為

v的樣例集合|Sv|為

Sv中所含樣例數(shù)信息增益【例】NO.OutlookTemperatureWindyHumidityPlay1sunnyhotfalseHighno2sunnyhottrueHighno3overcasthotfalseHighyes4rainmildfalseHighyes5raincoolfalseNormalyes6raincooltrueNormalno7overcastcooltrueNormalyes8sunnymildfalseHighno9sunnycoolfalseNormalyes10rainmildfalseNormalyes11sunnymildtrueNormalyes12overcastmildtrueHighyes13overcasthotfalseNormalyes14rainmildtrueHighno屬性“Outlook”sunnyrainyovercastOutlook分裂后的信息熵：信息增益：從哪個(gè)屬性開始：信息增益【例】計(jì)算所有屬性的信息增益從哪個(gè)屬性開始劃分決策樹的分支？

信息增益率信息增益率GainRatio計(jì)算信息增益時(shí)，不同分類的樣本的數(shù)量，會(huì)影響信息熵或信息增益的計(jì)算，即存在歸納偏置的問題。采用信息增益率可減弱不同類別的樣本數(shù)量對不純性度量的影響。信息增益率GainRatio計(jì)算公式前面所定義的信息增益

信息增益率【例】NO.OutlookTemperatureWindyHumidityPlay1sunnyhotfalseHighno2sunnyhottrueHighno3overcasthotfalseHighyes4rainmildfalseHighyes5raincoolfalseNormalyes6raincooltrueNormalno7overcastcooltrueNormalyes8sunnymildfalseHighno9sunnycoolfalseNormalyes10rainmildfalseNormalyes11sunnymildtrueNormalyes12overcastmildtrueHighyes13overcasthotfalseNormalyes14rainmildtrueHighno從哪個(gè)屬性開始：信息增益率【例】

GINI系數(shù)指標(biāo)GINI系數(shù)是20世紀(jì)初意大利經(jīng)濟(jì)學(xué)家基尼，根據(jù)勞倫斯曲線所定義的判斷收入分配公平程度的指標(biāo)。GINI系數(shù)是一個(gè)比例數(shù)值，在0到1之間，是國際上用來綜合考察居民收入分配差異狀況的一個(gè)重要分析指標(biāo)，GINI系數(shù)越接近1就表示收入分配差距越大。GINI系數(shù)指標(biāo)GINI系數(shù)也是反映一組數(shù)據(jù)離散程度的指標(biāo)，其功能類似于標(biāo)準(zhǔn)差。GINI系數(shù)越大，則平均指標(biāo)（如平均數(shù)、中位數(shù)和眾數(shù)）對一組數(shù)據(jù)的代表性越差；反之則越好。在決策樹分類中，使用GINI系數(shù)來反映一組數(shù)據(jù)的類別(class)的雜亂程度，即度量不純度。GINI系數(shù)指標(biāo)給定結(jié)點(diǎn)

t的Gini值計(jì)算：當(dāng)類分布均衡時(shí)，Gini值達(dá)到最大值(1-1/Nc)相反當(dāng)只有一個(gè)類時(shí)，Gini值達(dá)到最小值0類別的數(shù)量在結(jié)點(diǎn)t中，類ci發(fā)生的概率結(jié)點(diǎn)t中出現(xiàn)的各個(gè)類別GINI系數(shù)指標(biāo)P(C0)=0/6=0P(C1)=6/6=1Gini=1–(P(C0)2+P(C1)2)=1–(0+1)=0

P(C0)=1/6P(C1)=5/6Gini=1–((1/6)2+(5/6)2)=0.278P(C0)=2/6P(C1)=4/6Gini=1–((2/6)2+(4/6)2)=0.444P(C0)=3/6P(C1)=3/6Gini=1–((3/6)2+(3/6)2)=0.5GINI系數(shù)指標(biāo)不同的劃分結(jié)果，可以利用GiniSplit參數(shù)來衡量。當(dāng)一個(gè)結(jié)點(diǎn)p

分割成k

個(gè)部分(子結(jié)點(diǎn))，

劃分的質(zhì)量公式：ni=孩子結(jié)點(diǎn)i的記錄數(shù),n=父結(jié)點(diǎn)p的記錄數(shù).分類誤差ClassificationError

P(C0)=0/6=0P(C1)=6/6=1Error=1–max(0,1)=1–1=0P(C0)=1/6P(C1)=5/6Error=1–max(1/6,5/6)=1–5/6=1/6P(C0)=2/6P(C1)=4/6Error=1–max(2/6,4/6)=1–4/6=1/3C00C16C01C15C02C14分類誤差P(C0)=3/6P(C1)=3/6Error=1–max(3/6,3/6)=1–3/6=1/2C02C14連續(xù)屬性的劃分方法如何劃分？NoOutlookTemperatureHumidityWindyplay1sunny8585falseno2sunny8090trueno3overcast8386falseyes4rainy7096falseyes5rainy6880falseyes6rainy6570trueno7overcast6465trueyes8sunny7295falseno9sunny6970falseyes10rainy7580falseyes11sunny7570trueyes12overcast7290trueyes13overcast8175falseyes14rainy7191trueNo連續(xù)屬性的劃分方法多元?jiǎng)澐諬umidityplay85no90no86yes96yes80yes70no65yes95no70yes80yes70yes90yes75yes91No連續(xù)屬性的劃分方法多元?jiǎng)澐?/p>

Humidity

……96≤65(6570](7075](…](9195]Humidity8590869680706595708070907591Humidity6570707075808085869090919596連續(xù)屬性的劃分方法二元?jiǎng)澐謩澐贮c(diǎn)v選擇N個(gè)記錄中所有屬性值作為劃分點(diǎn)，取N-1個(gè)劃分點(diǎn)按照每個(gè)劃分點(diǎn)（A<vi

andA

vi）進(jìn)行類計(jì)數(shù)，計(jì)算每個(gè)候選點(diǎn)vi的GiniSplit指標(biāo)選擇最優(yōu)劃分點(diǎn)Humidity

≤A>A連續(xù)屬性的劃分方法551.數(shù)據(jù)排序，N=102.N-1=9個(gè)劃分點(diǎn)≤65>70≤70>75≤75>80≤80>85……≤91>95≤95>963.比較GiniSplit(≤65,>70)GiniSplit(≤70,>75)GiniSplit(≤75,>80)GiniSplit(≤80,>85)……GiniSplit(≤91,>95)GiniSplit(≤95,96)GiniSplit(≤80,>85)【例】Humidity8590869680706595708070907591Humidity6570707075808085869090919596連續(xù)屬性的劃分方法56【例】Humidity

>85≤80Humidity8590869680706595708070907591從兩個(gè)相鄰的排過序的屬性值之間選擇中間值作為劃分點(diǎn)

Humidity

>82.5≤82.5連續(xù)屬性的劃分方法57如果連續(xù)數(shù)值取值較為分散，則運(yùn)算量較大。可采取一些處理方法來降低計(jì)算量。對排序后的連續(xù)數(shù)值屬性所對應(yīng)的決策屬性值進(jìn)行分類的方法。連續(xù)屬性的劃分方法581.對屬性值由低到高進(jìn)行排序；2.對分類屬性在屬性值排序的基礎(chǔ)上進(jìn)行排序；3.將屬性值或分類值不發(fā)生變化的數(shù)值視為同一組；4.找出屬性值和分類值均發(fā)生變化的邊界點(diǎn)；5.按邊界點(diǎn)為劃分點(diǎn)進(jìn)行劃分增益計(jì)算比較連續(xù)屬性的劃分方法59只要對較少的劃分點(diǎn)進(jìn)行計(jì)算比較，有效地降低了計(jì)算復(fù)雜度。Humidity則從10次減少為只需6次。小結(jié)決策樹分類的過程建立模型評估（測試數(shù)據(jù)集，精確度）應(yīng)用模型討論不純度-信息增益-從哪個(gè)屬性開始多差劃分、二叉劃分連續(xù)屬性劃分第6章分類預(yù)測決策樹剪枝模型評價(jià)一個(gè)好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對未知樣本也要能準(zhǔn)確分類。對模型的評估可以通過多項(xiàng)準(zhǔn)確率指標(biāo)來綜合評價(jià)：一個(gè)好的分類模型必須具有較低的訓(xùn)練誤差和較低的泛化誤差。訓(xùn)練誤差在訓(xùn)練數(shù)據(jù)集上誤分類樣本比例檢驗(yàn)誤差在測試數(shù)據(jù)集上誤分類樣本比例泛化誤差分類模型在未知樣本上的期望誤差交叉驗(yàn)證【例】訓(xùn)練誤差較低檢驗(yàn)誤差？泛化誤差？xValueyValue【例】如果不那么“細(xì)致”？【例】哺乳動(dòng)物的分類問題10個(gè)訓(xùn)練記錄中有2個(gè)被錯(cuò)誤標(biāo)記：蝙蝠和鯨完全擬合訓(xùn)練數(shù)據(jù)，訓(xùn)練誤差為0【例】哺乳動(dòng)物的分類問題但它在檢驗(yàn)數(shù)據(jù)上的誤差達(dá)30%。人和海豚，鼴鼠誤分為非哺乳動(dòng)物【例】哺乳動(dòng)物的分類問題更簡單的決策樹，檢驗(yàn)誤差較低10%，盡管它的訓(xùn)練誤差較高20%前決策樹過度擬合了訓(xùn)練數(shù)據(jù)。因?yàn)閷傩詼y試條件4條腿具有欺騙性，它擬合了誤標(biāo)記的訓(xùn)練紀(jì)錄，導(dǎo)致了對檢驗(yàn)集中記錄的誤分類過度擬合原因噪聲噪聲導(dǎo)致決策邊界的改變過度擬合原因噪聲缺乏代表性樣本根據(jù)少量訓(xùn)練記錄做出分類決策的模型也容易受過度擬合的影響。由于訓(xùn)練數(shù)據(jù)缺乏具有代表性的樣本，在沒有多少訓(xùn)練記錄的情況下，學(xué)習(xí)算法仍然細(xì)化模型就會(huì)產(chǎn)生過度擬合。過度擬合原因噪聲缺乏代表性樣本【例】五個(gè)訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對應(yīng)的決策樹盡管訓(xùn)練誤差為0，但檢驗(yàn)誤差高達(dá)30%。人、大象和海豚被誤分類，因?yàn)闆Q策樹把恒溫但不冬眠的動(dòng)物分為非哺乳動(dòng)物。決策樹做出這樣的分類決策是因?yàn)橹挥幸粋€(gè)訓(xùn)練記錄（鷹）具有這些特征。當(dāng)決策樹的葉結(jié)點(diǎn)沒有足夠的代表性樣本時(shí)，很可能做出錯(cuò)誤的預(yù)測。剪枝剪枝奧卡姆剃刀（Occam'sRazor）：“如無必要，勿增實(shí)體”，即“簡單有效原理”。在能夠保證泛化誤差的前提下，對決策樹模型進(jìn)行剪枝給定兩個(gè)具有相同泛化誤差的模型，較簡單的模型比復(fù)雜的模型更可取剪枝先剪枝后剪枝先剪枝使樹增長算法在產(chǎn)生完全擬合整個(gè)訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長。當(dāng)決策樹的構(gòu)建過程中，達(dá)到某一預(yù)先設(shè)定的條件，則停止樹的生長，用該結(jié)點(diǎn)子集元組中最頻繁的類，即主導(dǎo)類，作為其類別標(biāo)號，該結(jié)點(diǎn)也設(shè)置為葉節(jié)點(diǎn)。先剪枝剪枝的條件主要有以下幾種限制性結(jié)束條件：

定義一個(gè)決策樹樹高上限，當(dāng)決策樹達(dá)到這個(gè)上限時(shí)，就停止生長；定義一定的實(shí)例個(gè)數(shù)閾值，當(dāng)結(jié)點(diǎn)的記錄數(shù)少于該閾值，則停止生長；當(dāng)不純性度量的增益(例如信息增益informationgain)低于某個(gè)確定的閾值時(shí)，則停止生長；實(shí)例具有相同的特征向量的時(shí)候，停止決策樹的生長，即使這些屬性不屬于同一類。這種方法能夠較為有效地處理數(shù)據(jù)中的沖突問題。先剪枝方法相對簡單，具有較高的效率，而且不需要生成整個(gè)決策樹，適合于解決數(shù)據(jù)規(guī)模較大所帶來的問題。要精確地估計(jì)決策樹生長的停止時(shí)間并不容易，選取一個(gè)恰當(dāng)?shù)拈撝蹈欠浅＠щy。閾值太低，無法充分解決過度擬合的問題；閾值太高，則會(huì)導(dǎo)致擬合不足。后剪枝減少錯(cuò)誤剪枝REP(Reduced-ErrorPruning)悲觀錯(cuò)誤剪枝法PEP(Pesimistic-ErrorPruning)代價(jià)-復(fù)雜度剪枝CCP(Cost-ComplexityPruning)最小錯(cuò)誤剪枝MEP(MinimumErrorPruning)減少錯(cuò)誤剪枝REP一種較為簡單的基于測試檢驗(yàn)結(jié)果的后剪枝的方法使用測試數(shù)據(jù)集來對過度擬合訓(xùn)練集中的虛假特征進(jìn)行檢驗(yàn)將決策樹上的每個(gè)結(jié)點(diǎn)都列為剪枝的候選結(jié)點(diǎn)，再根據(jù)算法確定是否對結(jié)點(diǎn)進(jìn)行剪枝：【算法6?2】REP算法（給定由訓(xùn)練集數(shù)據(jù)生成的決策樹T）1:repeat2:

找到最靠近葉結(jié)點(diǎn)的子樹Ts，使Ts變成為葉結(jié)點(diǎn)N，得到一棵新樹T’；3:

利用測試集測試T’，計(jì)算分類誤差；4:ifT’的分類誤差較T的分類誤差有所下降then5:T=T’//即刪除子樹Ts，用葉結(jié)點(diǎn)N代替6:until任意一棵子樹被葉結(jié)點(diǎn)替代而不增加其在測試集上的分類錯(cuò)誤減少錯(cuò)誤剪枝REP【例】減少錯(cuò)誤剪枝REP【例】WEKA未剪枝進(jìn)行了REP剪枝減少錯(cuò)誤剪枝REP用測試數(shù)據(jù)集，來對剪枝前后的錯(cuò)誤率進(jìn)行測試和比對，以確定是否進(jìn)行剪枝。悲觀錯(cuò)誤剪枝法PEPPEP僅使用訓(xùn)練數(shù)據(jù)，根據(jù)剪枝前后數(shù)據(jù)集錯(cuò)誤率的變化來判定是否對子樹進(jìn)行修剪。引入了統(tǒng)計(jì)學(xué)上連續(xù)性修正的概念彌補(bǔ)REP中的缺陷，在評價(jià)子樹的訓(xùn)練錯(cuò)誤公式中添加了一個(gè)常數(shù)，來假定每個(gè)葉結(jié)點(diǎn)都一定程度上對實(shí)例的某個(gè)部分進(jìn)行錯(cuò)誤的分類。悲觀錯(cuò)誤剪枝法PEPPEP的基本原理也是試著用葉結(jié)點(diǎn)代替一顆子樹，如果這樣可使數(shù)據(jù)集分類誤差減低，則確定這個(gè)替換，否則則不替換。但是，這樣的替換必定會(huì)導(dǎo)致其訓(xùn)練集分類誤差上升（測試數(shù)據(jù)集分類誤差不一定會(huì)上升），所以需要進(jìn)行一定的修正，以保證這個(gè)方法有效。修正的方法就是在分類誤差上加上一個(gè)經(jīng)驗(yàn)性的懲罰因子。

悲觀錯(cuò)誤剪枝法PEP對于子樹，假定其有

NLeaf

個(gè)葉結(jié)點(diǎn)，則其經(jīng)過修正后的子樹的錯(cuò)誤率為：ELeafi

為子樹中各葉結(jié)點(diǎn)的誤判個(gè)數(shù)NLeaf

為子樹中葉結(jié)點(diǎn)數(shù)Ni為子樹中各葉結(jié)點(diǎn)的樣本數(shù)加入懲罰因子，在一定程度上消除了因子樹換為葉結(jié)點(diǎn)時(shí)固有的分類誤差增長。如果剪枝，內(nèi)部結(jié)點(diǎn)下的子樹變成了葉節(jié)點(diǎn)J，其誤判個(gè)數(shù)EJ也要加上這個(gè)懲罰因子，變?yōu)镋J+0.5。A1A2c163c132c202c197正確分類的樣本數(shù)量誤判的樣本數(shù)量悲觀錯(cuò)誤剪枝法PEP是否剪枝（替換）？？對于訓(xùn)練數(shù)據(jù)，子樹總是比替換后的葉結(jié)點(diǎn)誤差小，但校正后并非如此。如果剪枝后的誤判個(gè)數(shù)在剪枝前的誤判個(gè)數(shù)的標(biāo)準(zhǔn)誤差之內(nèi)，則可剪枝A1A2c163c132c202c197悲觀錯(cuò)誤剪枝法PEP錯(cuò)誤率eTree

的分布，可根據(jù)經(jīng)驗(yàn)估計(jì)為多種分布模型（二項(xiàng)式、正態(tài)分布）。

A1A2c163c132c202c197悲觀錯(cuò)誤剪枝法PEP【例】圖示決策樹子樹，確定這個(gè)子樹是否應(yīng)被剪枝（用一個(gè)葉結(jié)點(diǎn)代替）。子樹誤差率子樹誤判次數(shù)的標(biāo)準(zhǔn)差：子樹替換為葉結(jié)點(diǎn)后，誤判次數(shù)：因有：所以可以將子樹剪枝，代替為一個(gè)葉結(jié)點(diǎn)。A1A2c163c132c202c197代價(jià)-復(fù)雜度剪枝CCP根據(jù)比較剪枝前后決策樹的分類準(zhǔn)確度的變化情況來決定是否進(jìn)行剪枝。定義了一個(gè)判定指標(biāo)α，為在剪枝過程中因子樹

Tt被葉結(jié)點(diǎn)

t替代而增加的錯(cuò)分樣本發(fā)生率（代價(jià)cost），與決策樹被簡化程度（復(fù)雜度complexity）的比值。即：NTt

為子樹Tt

中的葉結(jié)點(diǎn)數(shù)1為葉結(jié)點(diǎn)t的葉節(jié)點(diǎn)數(shù)α值衡量了因剪枝所引起的錯(cuò)誤率的升高與決策樹復(fù)雜度降低之間的對比關(guān)系。分母：剪枝前后子樹Tt

減少的葉節(jié)點(diǎn)數(shù)，即決策樹復(fù)雜度下降的程度分子：剪枝前后錯(cuò)誤發(fā)生率的增加量，即剪枝前后錯(cuò)誤發(fā)生率之差最小錯(cuò)誤剪枝MEP基本思想對于決策樹中的非葉結(jié)點(diǎn)t，計(jì)算其分類誤差估計(jì)，稱之為靜態(tài)誤差STE(t)再對以t為根節(jié)點(diǎn)的子樹的每一個(gè)葉結(jié)點(diǎn){ti，i=1，2，…，m}，計(jì)算其分類誤差估計(jì)，并以各結(jié)點(diǎn)擁有的訓(xùn)練樣本的比例為權(quán)值，進(jìn)行加權(quán)求和，得到結(jié)點(diǎn)t的動(dòng)態(tài)（回溯）誤差DYE(t)。如果STE(t)≤DYT(t)，則對結(jié)點(diǎn)t

子樹進(jìn)行剪枝。擬合不足當(dāng)決策樹很小時(shí)，訓(xùn)練和檢驗(yàn)誤差都很大，這種情況稱為模型擬合不足。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí)結(jié)構(gòu)。剪枝方法比較剪枝方式是否需要獨(dú)立剪枝集誤差估計(jì)剪枝程度減少錯(cuò)誤剪枝REP自底向上需要剪枝集上的誤差估計(jì)O(n)過剪枝悲觀錯(cuò)誤剪枝PEP自頂向下需要誤差率連續(xù)校正O(n)過剪枝/欠剪枝代價(jià)-復(fù)雜度剪枝CCP自底向上不需要標(biāo)準(zhǔn)誤差O(n2)過剪枝基于錯(cuò)誤剪枝EBP自底向上不需要概率分布的置信區(qū)間欠剪枝臨界值剪枝CVP自底向上不需要卡方檢驗(yàn)欠剪枝最小誤差剪枝MEP自底向上需要m-概率估計(jì)O(n)欠剪枝小結(jié)所構(gòu)建出的決策樹模型，需要進(jìn)行評估，依據(jù)：泛化誤差訓(xùn)練誤差檢驗(yàn)誤差剪枝是提高決策樹模型可用性的重要手段第6章分類預(yù)測決策樹分類

特點(diǎn)常提到的決策樹算法CART二元?jiǎng)澐諫ini誤差平方和準(zhǔn)則剪枝：整體損失函數(shù)極小化ID3僅Nominal屬性信息熵信息增益C4.5信息熵信息增益率處理離散屬性，或離散化了的連續(xù)屬性后剪枝J4.8決策樹歸納的特點(diǎn)決策樹是一種構(gòu)建分類模型的非參數(shù)方法不需要先驗(yàn)假設(shè)不假定類/屬性服從一定的概率分布不需要昂貴的的計(jì)算代價(jià)即使訓(xùn)練集巨大，也可快速建立模型未知樣本分類非?？鞗Q策樹相對容易解釋特別是小型的決策樹對于簡單數(shù)據(jù)集，準(zhǔn)確率高決策樹歸納的特點(diǎn)決策樹是學(xué)習(xí)離散值函數(shù)的典型代表某些特定的布爾問題不適用決策樹對于噪聲的干擾具有相當(dāng)好的魯棒性采用避免過分?jǐn)M合的方法后尤其如此冗余屬性不會(huì)對決策樹的準(zhǔn)確率造成不利影響強(qiáng)相關(guān)屬性

冗余選擇一個(gè)用作劃分，忽略另一個(gè)96決策樹歸納的特點(diǎn)數(shù)據(jù)碎片問題隨著決策樹的生長，可能導(dǎo)致葉結(jié)點(diǎn)記錄數(shù)太少，對于葉結(jié)點(diǎn)代表的類，不能做出具有統(tǒng)計(jì)意義的判決，這些就是數(shù)據(jù)碎片97決策樹歸納的特點(diǎn)子樹可能在決策樹中重復(fù)多次。使決策樹過于復(fù)雜98在多個(gè)分支中出現(xiàn)同樣的子樹MRS313T3S45T2決策樹歸納的特點(diǎn)決策邊界對單個(gè)屬性運(yùn)用測試條件，則樹的生長過程即為講屬性空間劃分為不相交的區(qū)域的過程對單個(gè)屬性運(yùn)用測試條件，決策邊界為直線，且平行于坐標(biāo)軸99決策樹歸納的特點(diǎn)決策邊界斜決策樹100所學(xué)方法中，有沒有可以解決這個(gè)問題的？x+y<1Class=Class=決策樹歸納的特點(diǎn)決策邊界斜決策樹構(gòu)造歸納ConstructiveInduction屬性的算術(shù)或邏輯組合提高區(qū)分性會(huì)產(chǎn)生冗余101決策樹分類決策樹的優(yōu)勢在于不需要任何領(lǐng)域知識或參數(shù)設(shè)置，適合于探測性的知識發(fā)現(xiàn)。決策樹分類算法的關(guān)鍵，在于如何構(gòu)造出精度高、規(guī)模小的決策樹模型。第6章分類預(yù)測6.3k-近鄰分類K-近鄰分類K-近鄰（K-NearestNeighbor，KNN）分類算法，最初是由Cover和Hart于1968年提出，是一個(gè)理論上比較成熟的方法。算法原理簡單直觀：未知樣本的類別，由特征空間中K個(gè)最相似（即特征空間中最鄰近）的樣本的大多數(shù)類別來確定。是一種基于實(shí)例的懶惰學(xué)習(xí)方法。K-近鄰分類K-近鄰分類算法的處理過程為：對于待預(yù)測的未分類樣本，計(jì)算其與數(shù)據(jù)集中每個(gè)樣本之間的相似度；篩選出最近鄰的K個(gè)數(shù)據(jù)樣本；根據(jù)K個(gè)最近鄰數(shù)據(jù)樣本的類別，采用多數(shù)投票機(jī)制確定待預(yù)測樣本的類別。K-近鄰分類這里有幾個(gè)問題需要詳細(xì)討論：以何種指標(biāo)來衡量數(shù)據(jù)樣本之間的相似度；K值如何確定；采用多數(shù)投票機(jī)制判定樣本類別時(shí)如何設(shè)計(jì)具體算法。相似度度量1.距離(1)歐幾里得距離（EuclideanDistance）(2)曼哈頓距離（ManhattanDistance）(3)明可夫斯基距離（MinkowskiDistance）(4)馬氏距離（Mahalanobisdistance）(5)漢明距離（HammingDistance）2.相似系數(shù)(1)余弦相似度(2)相關(guān)系數(shù)(3)Jaccard相似系數(shù)(JaccardSimilarityCoefficient)“距離”度量定義距離函數(shù)，基于屬性值進(jìn)行計(jì)算非負(fù)性對于任意x，y，兩者之間的距離d(x，y)≥0，當(dāng)x

=y時(shí)，等號成立。對稱性對于任意x，y，兩者之間的距離d(x，y)=d(y，x)，即距離是標(biāo)量而不是向量。三角不等式對于任意x，y，z，有d(x，y)

≤d(x，z)+d(z，y)。即對象x到對象y的距離小于等于途經(jīng)其他任何對象z的距離之和。也稱為相似性“距離”度量歐幾里得距離EuclideanDistance對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其歐幾里得距離為在二維空間中的歐幾里得距離就是平面中兩點(diǎn)之間的實(shí)際距離。在三維空間中的歐幾里得距離就是立體（三維）空間中兩點(diǎn)之間的實(shí)際距離。“距離”度量曼哈頓距離對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其曼哈頓距離為(6,6)(2,2)歐幾里得距離=5.66曼哈頓距離=(6-2)+(6-2)=844xy“距離”度量明可夫斯基距離MinkowskiDistance對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其明可夫斯基距離為相似系數(shù)余弦相似度對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，即對于x，y兩個(gè)向量，有：cos(x,y)=(x?y)/‖x‖?‖y‖

余弦相似度【例如】分析以下兩個(gè)句子的相似性：

句子A：我喜歡看電視，不喜歡看電影。句子B：我不喜歡看電視，也不喜歡看電影。1)可以將兩個(gè)句子進(jìn)行分詞：句子A：我/喜歡/看電視/不/喜歡/看/電影句子B：我/不/喜歡/看/電視/也/不/喜歡/看/電影2)對所出現(xiàn)的各個(gè)詞匯（我

喜歡

看

電視

電影

不

也），計(jì)算其詞頻：句子A：我1，喜歡2，看2，電視1，電影1，不1，也0句子B：我1，喜歡2，看2，電視1，電影1，不2，也1余弦相似度【例如】分析以下兩個(gè)句子的相似性：

句子A：我喜歡看電視，不喜歡看電影。句子B：我不喜歡看電視，也不喜歡看電影。3)將詞頻轉(zhuǎn)換為向量：句子A：x=(1221110)句子B：y=(1221121)4)計(jì)算其余弦相似度，有：余弦相似度由此，我們就得到了“找出相似文章”的一種算法：使用TF-IDF算法，找出兩篇文章的關(guān)鍵詞；每篇文章各取出若干個(gè)關(guān)鍵詞（比如20個(gè)），合并成一個(gè)集合，計(jì)算每篇文章對于這個(gè)集合中的詞的詞頻（為了避免文章長度的差異，可以使用相對詞頻）；生成兩篇文章各自的詞頻向量；計(jì)算兩個(gè)向量的余弦相似度，值越大就表示越相似。相似系數(shù)余弦相似度相關(guān)系數(shù)反映變量之間相關(guān)關(guān)系密切程度的統(tǒng)計(jì)指標(biāo)相關(guān)系數(shù)按積差的方法計(jì)算，以兩變量與各自平均值的離差為基礎(chǔ)，通過兩個(gè)離差相乘來反映兩變量之間相關(guān)程度。x與y之間的協(xié)方差x,y的均方差相似系數(shù)余弦相似度相關(guān)系數(shù)Jaccard相似系數(shù)(JaccardSimilarityCoefficient)用于比較有限樣本集之間的相似性與差異性A、B的相似性：Jaccard距離：余弦相似度TF-IDF算法TF-IDF通過統(tǒng)計(jì)方法，對字詞對于語料庫中的一份文件或文件集的重要程度進(jìn)行評估。字詞的重要性隨其在文件中出現(xiàn)的次數(shù)正比增加，隨其在語料庫中出現(xiàn)的頻率成反比下降，即如果某字在一篇文章中出現(xiàn)的頻率TF高，而在其他文章中很少出現(xiàn)，則認(rèn)為該字詞具有很好的類別區(qū)分能力，適合用于分類。這里TF為詞頻(TermFrequency)，表示詞條在文檔d中出現(xiàn)的頻率；IDF為逆向文件頻率(InverseDocumentFrequency)，表示包含詞條的文檔的數(shù)量，值越大，表明詞條具有很好的類別區(qū)分能力。TF-IDF加權(quán)的各種形式常被搜索引擎應(yīng)用，作為文件與用戶查詢之間相關(guān)程度的度量或評級。除了TF-IDF以外，因特網(wǎng)上的搜索引擎還會(huì)使用基于鏈接分析的評級方法，以確定文件在搜尋結(jié)果中出現(xiàn)的順序。K-近鄰分類這里有幾個(gè)問題需要詳細(xì)討論：以何種指標(biāo)來衡量數(shù)據(jù)樣本之間的相似度；K值如何確定；采用多數(shù)投票機(jī)制判定樣本類別時(shí)如何設(shè)計(jì)具體算法。K值如何確定K值是K-近鄰算法的一個(gè)超參數(shù)，表示選擇多少個(gè)最近鄰的樣本來進(jìn)行預(yù)測。K值的選擇對算法的性能有很大影響，需要根據(jù)具體的應(yīng)用問題和數(shù)據(jù)的特征進(jìn)行設(shè)置和調(diào)整。K值如何確定K值如何確定當(dāng)K值設(shè)置偏小時(shí)算法會(huì)更多地關(guān)注局部的細(xì)節(jié)，精確度較高，同時(shí)對訓(xùn)練數(shù)據(jù)中的噪聲和異常值較為敏感，增加了過擬合風(fēng)險(xiǎn)，泛化性降低，導(dǎo)致分類結(jié)果不穩(wěn)定。當(dāng)K值設(shè)置偏大時(shí)算法更多地關(guān)注整體的趨勢，對局部噪聲和異常值的敏感度降低，但可能使模型過于平滑，忽略了數(shù)據(jù)中的某些重要細(xì)節(jié)，導(dǎo)致分類結(jié)果過于籠統(tǒng)。K值的增加通常意味著計(jì)算復(fù)雜度的提高。在實(shí)際應(yīng)用中通過交叉驗(yàn)證等方法來選擇合適的K值除了K值外，還可以考慮調(diào)整其他參數(shù)（如相似度度量方式、特征權(quán)重等）來進(jìn)一步優(yōu)化算法的性能。K-近鄰分類這里有幾個(gè)問題需要詳細(xì)討論：以何種指標(biāo)來衡量數(shù)據(jù)樣本之間的相似度；K值如何確定；采用多數(shù)投票機(jī)制判定樣本類別時(shí)如何設(shè)計(jì)具體算法。多數(shù)投票機(jī)制判定方法：以出現(xiàn)次數(shù)最多的樣本類別以樣本類別的平均值必要時(shí)可對類別屬性進(jìn)行編碼以鄰樣本類別加權(quán)平均值權(quán)重可以選近鄰樣本距離的倒數(shù)或與最大值的差變化：以近鄰半徑判定變化：K-近鄰回歸計(jì)算待預(yù)測樣本與K個(gè)最近鄰樣本的距離，取平均值作為預(yù)測結(jié)果數(shù)據(jù)點(diǎn)0數(shù)據(jù)點(diǎn)1變化：K-近鄰回歸計(jì)算待預(yù)測樣本與Radius半徑內(nèi)的樣本的距離，取平均值作為預(yù)測結(jié)果數(shù)據(jù)點(diǎn)0數(shù)據(jù)點(diǎn)1算法特點(diǎn)K-近鄰方法算法原理簡單，易于理解和實(shí)現(xiàn)算法基于實(shí)例進(jìn)行分類判別，直接利用數(shù)據(jù)集進(jìn)行預(yù)測沒有顯式的訓(xùn)練過程，能夠較為輕松地處理多分類問題算法從原理上依賴于極限定理，但在類別判別時(shí)，只與少量的相鄰樣本有關(guān)，因此可以較好地處理非線性數(shù)據(jù)，也能夠避免樣本的不平衡問題對于類域交叉或重疊較多的待分樣本集的處理也更為適合。算法特點(diǎn)計(jì)算量較大對每一個(gè)待分類的樣本都要計(jì)算它到全體已知樣本的距離。可以采取在計(jì)算相似度時(shí)，構(gòu)建BallTree、KDTree等高效空間索引結(jié)構(gòu)來加快計(jì)算或者事先對已知樣本點(diǎn)進(jìn)行剪輯，去除對分類作用不大的樣本等方法減少計(jì)算量。算法K值和相似度度量方式對算法的性能有很大影響，需要仔細(xì)調(diào)整和選擇。第6章分類預(yù)測貝葉斯分類器詞匯python：蟒蛇or“Python”132單詞dynamic相對較常出現(xiàn)在編程類的文本中單詞constrictor則相對較常出現(xiàn)在生物類的文本中單詞source和單詞long傾向性不強(qiáng)單詞and等一類詞，在各類文檔中出現(xiàn)的概率幾乎一樣，其統(tǒng)計(jì)數(shù)據(jù)，在這里沒有價(jià)值機(jī)器學(xué)習(xí)理論中，這類詞被稱為“停用詞”(stopword)，可事先將其去除，不作為特征詞參與樣本訓(xùn)練，從而減少學(xué)習(xí)時(shí)間。幾乎每個(gè)搜索引擎都會(huì)維護(hù)一份“停用詞表”(stopwordlist))。分類器133訓(xùn)練假定有一篇新的句子或文檔，包含了long、dynamic和source三個(gè)單詞，那么這個(gè)句子或單詞是在敘述生物學(xué)的蟒蛇還是計(jì)算機(jī)科學(xué)的python程序呢？判定規(guī)則：比較以下兩個(gè)概率的大小：出現(xiàn)long、dynamic和source條件下，python的類標(biāo)號為生物學(xué)的概率，記為P(生物學(xué)|詞={long，dynamic，source})出現(xiàn)long、dynamic和source條件下，python的類標(biāo)號為計(jì)算機(jī)科學(xué)的概率，記為P(計(jì)算機(jī)科學(xué)|詞={long，dynamic，source})模式分類器134P(生物學(xué)|詞={long，dynamic，source})>P(計(jì)算機(jī)科學(xué)|詞={long，dynamic，source})蟒蛇P(生物學(xué)|詞={long，dynamic，source})<P(計(jì)算機(jī)科學(xué)|詞={long，dynamic，source})python程序先驗(yàn)概率P(生物學(xué)|詞={long，dynamic，source})P(Y|X)來表示隨機(jī)事件X發(fā)生的前提下，隨機(jī)事件Y發(fā)生的概率。也稱為X條件下Y的條件概率。P(計(jì)算機(jī)科學(xué)|詞={long，dynamic，source})后驗(yàn)概率計(jì)算后驗(yàn)概率怎么計(jì)算135要利用貝葉斯定理P(生物學(xué)|詞={long，dynamic，source})P(計(jì)算機(jī)科學(xué)|詞={long，dynamic，source})概率論基礎(chǔ)136假設(shè)X，Y是一對隨機(jī)變量，其概率分別用P(X)和P(Y)表示。聯(lián)合概率：X，Y的聯(lián)合概率P(X=x，Y=y)是指

X取值

x且

Y取值

y的概率。對于一般情況，對于隨機(jī)事件

X和

Y，聯(lián)合概率記為

P(XY)。

【例】盒中混有100只新、舊乒乓球，各有紅、白兩色，各種顏色和新舊程度的乒乓球數(shù)量如表所示。從盒中隨機(jī)取出一球，若取得的是紅球，求該紅球是新球的概率。設(shè)A=“從盒中隨機(jī)取到紅球”

B=“從盒中隨機(jī)取到新球”則：概率論基礎(chǔ)137

紅色白色新球4030舊球2010概率論基礎(chǔ)138獨(dú)立事件：對于隨機(jī)事件X、Y，若其中任一事件發(fā)生的概率不受另一事件發(fā)生與否的影響，稱事件X、Y是相互獨(dú)立的。如果用數(shù)學(xué)式來表達(dá)，為

概率論基礎(chǔ)139

貝葉斯定理貝葉斯定理：在隨機(jī)事件X、Y相互獨(dú)立的條件下，X和Y的聯(lián)合概率和條件概率滿足如下關(guān)系：140調(diào)整一下，得：貝葉斯公式在

X和

Y

互相獨(dú)立的前提下，事件

X條件下的

Y發(fā)生的概率

P(Y

|X)可以通過事件

Y條件下

X發(fā)生的概率

P(X

|Y)和

X，Y的概率

P(X)，P(Y)求得計(jì)算后驗(yàn)概率怎么計(jì)算141P(生物學(xué)|詞={long，dynamic，source})P(計(jì)算機(jī)科學(xué)|詞={long，dynamic，source})

獨(dú)立事件直觀上來講，對于隨機(jī)事件X、Y，若其中任一事件發(fā)生的概率不受另一事件發(fā)生與否的影響，稱事件X、Y是相互獨(dú)立的。如果用數(shù)學(xué)式來表達(dá)，為：142從數(shù)學(xué)上來定義，對于隨機(jī)事件X、Y，若P(XY)=P(X)P(Y)，則稱事件X，Y相互獨(dú)立。條件獨(dú)立143X和Y之間的條件獨(dú)立時(shí)，有：

計(jì)算條件概率假設(shè)條件獨(dú)立144P(詞={long，dynamic，source}|生物學(xué))=P(詞=long|生物學(xué))

P(詞=dynamic|生物學(xué))

P(詞=source|生物學(xué))=0.2

0.1

0.1=0.002P(詞={long，dynamic，source}|計(jì)算機(jī))=P(詞=long|計(jì)算機(jī))

P(詞=dynamic|計(jì)算機(jī))

P(詞=source|計(jì)算機(jī))=0.1

0.6

0.3=0.018詞匯python：蟒蛇or“Python”145

利用貝葉斯公式（設(shè)生物學(xué)、計(jì)算機(jī)科學(xué)和X相互獨(dú)立），有：

可得出：包含了包含了long、dynamic和source的句子或文檔屬于計(jì)算機(jī)科學(xué)。貝葉斯分類的基本原理通過某對象的先驗(yàn)概率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，即該對象屬于某一類的概率，選擇具有最大后驗(yàn)概率的類作為該對象所屬的類。貝葉斯分類器是最小錯(cuò)誤率意義上的優(yōu)化。當(dāng)一個(gè)貝葉斯分類器經(jīng)過訓(xùn)練之后，就可以利用它來對新的項(xiàng)目進(jìn)行自動(dòng)分類了。146設(shè)每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量X={x1，x2，…，xn}表示，描述由屬性A1，A2，…，An對樣本的n個(gè)度量。假定有m個(gè)類C1，C2，…，Cm。給定一個(gè)未知的（沒有類標(biāo)號）數(shù)據(jù)樣本X，分類法將預(yù)測X屬于（條件X下）具有最高后驗(yàn)概率的類，即將未知的樣本分配給類Ci，當(dāng)且僅當(dāng)：樸素貝葉斯分類器147最大后驗(yàn)假設(shè)(MAPmaximumposteriorihypothesis)將X指派到具有最大后驗(yàn)概率P(cj|X)的類cj也就是：將X指派到P(X|cj)P(cj)

最大的類cj因?yàn)楦鶕?jù)貝葉斯定理，有：樸素貝葉斯分類器148

P(X)對于所有類為常數(shù)，只需要使P(X|Ci)P(Ci)最大即可。因此，對未知數(shù)據(jù)樣本進(jìn)行有效地分類，就是將P(Ci|X)最大化。分類屬性和連續(xù)屬性計(jì)算P(X|Ci)P(Ci)149

分類屬性和連續(xù)屬性計(jì)算P(X|Ci)P(Ci)150如果類的先驗(yàn)概率P(X|Ci)P(Ci)未知，則通常假定這些類是等概率的，即：

P(C1)=

P(C2)=…=

P(Cm)，這時(shí)，只需使P(X|Ci)最大化。

分類屬性和連續(xù)屬性【例】根據(jù)顧客消費(fèi)數(shù)據(jù)，估算是否會(huì)購買計(jì)算機(jī)。預(yù)測一個(gè)未知樣本X的類標(biāo)號。151X={年齡=“<=30”，年收入=medium，是否學(xué)生=yes，信用狀況=fair}P(Cyes|X)vs.P(Cno|X)【例】根據(jù)顧客消費(fèi)數(shù)據(jù)，估算是否會(huì)購買計(jì)算機(jī)。預(yù)測一個(gè)未知樣本X

的類標(biāo)號。分類屬性和連續(xù)屬性152設(shè)：Cyes={購買計(jì)算機(jī)=yes}Cno={購買計(jì)算機(jī)=no}P(xi|Ci)CyesCno年齡<=302/93/5年收入medium4/92/5是否學(xué)生yes6/91/5信用狀況fair6/92/5P(Cyes)=9/14=0.643P(Cno)=5/14=0.357分類屬性和連續(xù)屬性【例】根據(jù)顧客消費(fèi)數(shù)據(jù)，估算是否會(huì)購買計(jì)算機(jī)。預(yù)測一個(gè)未知樣本X的類標(biāo)號。153P(X|Cyes)=P(年齡=“<=30”|Cyes)

P(年收入=medium|Cy