19決策樹與隨機(jī)森林和ASMS3000決策分析平臺(tái)

決策樹與隨機(jī)森林

鄒博北京10月機(jī)器學(xué)習(xí)班&ML在線公開課第1期

2023年1月11日1?目標(biāo)任務(wù)與主要內(nèi)容復(fù)習(xí)信息熵熵、聯(lián)合熵、條件熵、互信息決策樹學(xué)習(xí)算法信息增益ID3、C4.5、CARTBagging與隨機(jī)森林的思想投票機(jī)制分類算法的評(píng)價(jià)指標(biāo)ROC曲線和AUC值2?決策樹的實(shí)例(Weka自帶測(cè)試數(shù)據(jù))注：Weka的全名是懷卡托智能分析環(huán)境(WaikatoEnvironmentforKnowledgeAnalysis)，是一款免費(fèi)的，非商業(yè)化(與之對(duì)應(yīng)的是SPSS公司商業(yè)數(shù)據(jù)挖掘產(chǎn)品--Clementine)的，基于JAVA環(huán)境下開源的機(jī)器學(xué)習(xí)(machinelearning)以及數(shù)據(jù)挖掘(dataminining)軟件。它和它的源代碼可在其官方網(wǎng)站下載。3?復(fù)習(xí)：熵將離散隨機(jī)變量X的概率分布為P(X=xi)，則定義熵為：若P為連續(xù)隨機(jī)變量，則概率分布變成概率密度函數(shù)，求和符號(hào)變成積分符號(hào)。在不引起混淆的情況下，下面談到的“概率分布函數(shù)”，其含義是：1、若X為離散隨機(jī)變量，則該名稱為概率分布函數(shù)；2、若X為連續(xù)隨機(jī)變量，則該名稱為概率密度函數(shù)。4?對(duì)熵的理解熵是隨機(jī)變量不確定性的度量，不確定性越大，熵值越大；若隨機(jī)變量退化成定值，熵為0均勻分布是“最不確定”的分布熵其實(shí)定義了一個(gè)函數(shù)(概率分布函數(shù))到一個(gè)值(信息熵)的映射。P(x)H(函數(shù)數(shù)值)泛函回憶一下關(guān)于“變分推導(dǎo)”章節(jié)中對(duì)于泛函的內(nèi)容。5?聯(lián)合熵和條件熵兩個(gè)隨機(jī)變量X，Y的聯(lián)合分布，可以形成聯(lián)合熵JointEntropy，用H(X,Y)表示H(X,Y)–H(Y)(X,Y)發(fā)生所包含的信息熵，減去Y單獨(dú)發(fā)生包含的信息熵——在Y發(fā)生的前提下，X發(fā)生“新”帶來的信息熵該式子定義為Y發(fā)生前提下，X的熵：條件熵H(X|Y)=H(X,Y)–H(Y)6?推導(dǎo)條件熵的定義式7?相對(duì)熵相對(duì)熵，又稱互熵，交叉熵，鑒別信息，Kullback熵，Kullback-Leible散度等設(shè)p(x)、q(x)是X中取值的兩個(gè)概率分布，則p對(duì)q的相對(duì)熵是說明：相對(duì)熵可以度量兩個(gè)隨機(jī)變量的“距離”在“貝葉斯網(wǎng)絡(luò)”、“變分推導(dǎo)”章節(jié)使用過一般的，D(p||q)≠D(q||p)D(p||q)≥0、D(q||p)≥0提示：凸函數(shù)中的Jensen不等式8?互信息兩個(gè)隨機(jī)變量X，Y的互信息，定義為X，Y的聯(lián)合分布和獨(dú)立分布乘積的相對(duì)熵。I(X,Y)=D(P(X,Y)||P(X)P(Y))9?計(jì)算H(X)-I(X,Y)10?整理得到的等式H(X|Y)=H(X,Y)-H(Y)條件熵定義H(X|Y)=H(X)-I(X,Y)根據(jù)互信息定義展開得到有些文獻(xiàn)將I(X,Y)=H(Y)–H(Y|X)作為互信息的定義式對(duì)偶式H(Y|X)=H(X,Y)-H(X)H(Y|X)=H(Y)-I(X,Y)I(X,Y)=H(X)+H(Y)-H(X,Y)有些文獻(xiàn)將該式作為互信息的定義式試證明：H(X|Y)≤H(X)，H(Y|X)≤H(Y)11?強(qiáng)大的Venn圖：幫助記憶12?決策樹示意圖13?決策樹(DecisionTree)決策樹是一種樹型結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉結(jié)點(diǎn)代表一種類別。決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)。決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法，其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子節(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類。14?決策樹學(xué)習(xí)算法的特點(diǎn)決策樹學(xué)習(xí)算法的最大優(yōu)點(diǎn)是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過程中，不需要使用者了解過多背景知識(shí)，只需要對(duì)訓(xùn)練實(shí)例進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。顯然，屬于有監(jiān)督學(xué)習(xí)。從一類無序、無規(guī)則的事物(概念)中推理出決策樹表示的分類規(guī)則。15?決策樹學(xué)習(xí)的生成算法建立決策樹的關(guān)鍵，即在當(dāng)前狀態(tài)下選擇哪個(gè)屬性作為分類依據(jù)。根據(jù)不同的目標(biāo)函數(shù)，建立決策樹主要有一下三種算法。ID3C4.5CART16?信息增益概念：當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(jì)(特別是極大似然估計(jì))得到時(shí)，所對(duì)應(yīng)的熵和條件熵分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵。信息增益表示得知特征A的信息而使得類X的信息的不確定性減少的程度。定義：特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差，即：g(D,A)=H(D)–H(D|A)顯然，這即為訓(xùn)練數(shù)據(jù)集D和特征A的互信息。17?基本記號(hào)設(shè)訓(xùn)練數(shù)據(jù)集為D，|D|表示其容量，即樣本個(gè)數(shù)。設(shè)有K個(gè)類Ck，k=1,2,…,K，|Ck|為屬于類Ck的樣本個(gè)數(shù)。Σk|Ck|=|D|。設(shè)特征A有n個(gè)不同的取值{a1,a2…an}，根據(jù)特征A的取值將D劃分為n個(gè)子集D1,D2,…Dn,|Di|為Di的樣本個(gè)數(shù)，Σi|Di|=D。記子集Di中屬于類Ck的樣本的集合為Dik，|Dik|為Dik的樣本個(gè)數(shù)。18?信息增益的計(jì)算方法計(jì)算數(shù)據(jù)集D的經(jīng)驗(yàn)熵計(jì)算特征A對(duì)數(shù)據(jù)集D的經(jīng)驗(yàn)條件熵H(D|A)計(jì)算信息增益：g(D,A)=H(D)–H(D|A)19?經(jīng)驗(yàn)條件熵H(D|A)20?其他目標(biāo)信息增益率：gr(D,A)=g(D,A)/H(A)基尼指數(shù)：21?討論(一家之言)考察基尼指數(shù)的圖像、熵、分類誤差率三者之間的關(guān)系將f(x)=-lnx在x0=1處一階展開，忽略高階無窮小，得到f(x)≈1-x22?三種決策樹學(xué)習(xí)算法適應(yīng)信息增益來進(jìn)行特征選擇的決策樹學(xué)習(xí)過程，即為ID3決策。所以如果是取值更多的屬性，更容易使得數(shù)據(jù)更“純”，其信息增益更大，決策樹會(huì)首先挑選這個(gè)屬性作為樹的頂點(diǎn)。結(jié)果訓(xùn)練出來的形狀是一棵龐大且深度很淺的樹，這樣的劃分是極為不合理的。C4.5：信息增益率gr(D,A)=g(D,A)/H(A)CART：基尼指數(shù)總結(jié)：一個(gè)屬性的信息增益越大，表明屬性對(duì)樣本的熵減少的能力更強(qiáng)，這個(gè)屬性使得數(shù)據(jù)由不確定性變成確定性的能力越強(qiáng)。23?決策樹的例子對(duì)于下面的數(shù)據(jù)，希望分割成紅色和綠色兩個(gè)類24?決策樹的生成過程25?決策樹的生成過程26?決策樹的生成過程27?決策樹的生成過程28?決策樹的生成過程29?決策樹的生成過程30?決策樹的生成過程31?決策樹的生成過程32?決策樹的生成過程33?決策樹的過擬合決策樹對(duì)訓(xùn)練屬于有很好的分類能力，但對(duì)未知的測(cè)試數(shù)據(jù)未必有好的分類能力，泛化能力弱，即可能發(fā)生過擬合現(xiàn)象。剪枝隨機(jī)森林34?BootstrapingBootstraping的名稱來自成語“pullupbyyourownbootstraps”，意思是依靠你自己的資源，稱為自助法，它是一種有放回的抽樣方法。注：Bootstrap本義是指高靴子口后面的懸掛物、小環(huán)、帶子，是穿靴子時(shí)用手向上拉的工具。“pullupbyyourownbootstraps”即“通過拉靴子讓自己上升”，意思是“不可能發(fā)生的事情”。后來意思發(fā)生了轉(zhuǎn)變，隱喻“不需要外界幫助，僅依靠自身力量讓自己變得更好”。35?Bagging的策略bootstrapaggregation從樣本集中重采樣(有重復(fù)的)選出n個(gè)樣本在所有屬性上，對(duì)這n個(gè)樣本建立分類器(ID3、C4.5、CART、SVM、Logistic回歸等)重復(fù)以上兩步m次，即獲得了m個(gè)分類器將數(shù)據(jù)放在這m個(gè)分類器上，最后根據(jù)這m個(gè)分類器的投票結(jié)果，決定數(shù)據(jù)屬于哪一類36?AnotherdescriptionofBagging37?Bagging38?Bagging的結(jié)果39?隨機(jī)森林隨機(jī)森林在bagging基礎(chǔ)上做了修改。從樣本集中用Bootstrap采樣選出n個(gè)樣本；從所有屬性中隨機(jī)選擇k個(gè)屬性，選擇最佳分割屬性作為節(jié)點(diǎn)建立CART決策樹；重復(fù)以上兩步m次，即建立了m棵CART決策樹這m個(gè)CART形成隨機(jī)森林，通過投票表決結(jié)果，決定數(shù)據(jù)屬于哪一類40?應(yīng)用實(shí)例：KinectReal-TimeHumanPoseRecognitioninPartsfromSingleDepthImages,JamieShottonetc,2023,41?隨機(jī)森林/Bagging和決策樹的關(guān)系當(dāng)然可以使用決策樹作為基本分類器但也可以使用SVM、Logistic回歸等其他分類器，習(xí)慣上，這些分類器組成的“總分類器”，仍然叫做隨機(jī)森林。舉例42?回歸問題離散點(diǎn)是樣本集合，描述了臭氧(橫軸)和溫度(縱軸)的關(guān)系試擬合二者的變化曲線43?使用Bagging算法過程做100次bootstrap，每次得到的數(shù)據(jù)Di，Di的長度為N對(duì)于每一個(gè)Di，使用局部回歸(LOESS)擬合一條曲線(圖中灰色線是其中的10條曲線)將這些曲線取平均，即得到紅色的最終擬合曲線顯然，紅色的曲線更加穩(wěn)定，并且沒有過擬合明顯減弱記原始數(shù)據(jù)為D，長度為N(即圖中有N個(gè)離散點(diǎn))44?附：局部加權(quán)線性回歸LWR：LocallyWeightedlinearRegressionLOESS:LOcalregrESSion45?附：線性回歸與局部加權(quán)回歸黑色是樣本點(diǎn)紅色是線性回歸曲線綠色是局部加權(quán)回歸曲線46?投票機(jī)制簡單投票機(jī)制一票否決(一致表決)少數(shù)服從多數(shù)有效多數(shù)(加權(quán))閾值表決貝葉斯投票機(jī)制47?貝葉斯投票機(jī)制簡單投票法假設(shè)每個(gè)分類器都是平等的。在實(shí)際生活中，我們聽取一個(gè)人的意見，會(huì)考慮這個(gè)人過去的意見是否有用，從而加大或者減少權(quán)值。貝葉斯投票機(jī)制基于每個(gè)基本分類器在過去的分類表現(xiàn)設(shè)定一個(gè)權(quán)值，然后按照這個(gè)權(quán)值進(jìn)行投票。48?投票機(jī)制舉例假定有N個(gè)用戶可以為X個(gè)電影投票(假定投票者不能給同一電影重復(fù)投票)，投票有1、2、3、4、5星共5檔。如何根據(jù)用戶投票，對(duì)電影排序？本質(zhì)仍然是分類問題：對(duì)于某個(gè)電影，有N個(gè)決策樹，每個(gè)決策樹對(duì)該電影有1個(gè)分類(1、2、3、4、5類)，求這個(gè)電影應(yīng)該屬于哪一類(可以是小數(shù)：分類問題變成了回歸問題)49?一種可能的方案WR：加權(quán)得分(weightedrating)R：該電影的用戶投票的平均得分(Rating)C：所有電影的平均得分v：該電影的投票人數(shù)(votes)m：排名前250名的電影的最低投票數(shù)根據(jù)總投票人數(shù)，250可能有所調(diào)整按照v=0和m=0分別分析50?評(píng)價(jià)指標(biāo)以下近考慮二分類問題，即將實(shí)例分成正類(positive)或負(fù)類(negative)。對(duì)一個(gè)二分問題來說，會(huì)出現(xiàn)四種情況。如果一個(gè)實(shí)例是正類并且也被預(yù)測(cè)成正類，即為真正類(Truepositive),如果實(shí)例是負(fù)類被預(yù)測(cè)成正類，稱之為假正類(Falsepositive)。相應(yīng)地，如果實(shí)例是負(fù)類被預(yù)測(cè)成負(fù)類，稱之為真負(fù)類(Truenegative),正類被預(yù)測(cè)成負(fù)類則為假負(fù)類(falsenegative)。51?混淆矩陣(ConfusionMatrix)TP：正確肯定——實(shí)例是正例，劃分為正例FN：漏報(bào)——實(shí)際是正例，卻劃分成了負(fù)例FP：誤報(bào)——實(shí)際是負(fù)例，卻劃分成了正例TN：正確拒絕——實(shí)例是負(fù)例，劃分為負(fù)例52?誤分率ErrorRate：(FN+FP)/C準(zhǔn)確度Accuracy：(TP+TN)/C查準(zhǔn)率Recall：TP/(TP+FP)假正類率(FalsePositiveRate,FPR)：FP/(FP+TN)虛報(bào)概率，代價(jià)(costs)真正類率(truepositiverate,TPR)：TP/(TP+FN)擊中概率，收益(benefits)思考：可否按此模式，定義“真負(fù)類率TNR”？53?使用TPR和FPR分析二分類模型對(duì)于一個(gè)二分類模型，假設(shè)已確定一個(gè)閥值，比如說0.6，大于這個(gè)值的實(shí)例劃歸為正類，小于這個(gè)值則劃到負(fù)類中。如果減小閥值，比如減到0.5，一方面，能識(shí)別出更多的正類，即提高TPR(樣本集合的正例總數(shù)沒變)；另一方面，也將更多的負(fù)實(shí)例當(dāng)作了正實(shí)例，即提高了FPR。根據(jù)不同的閾值，將離散點(diǎn)(TPR,FPR)繪制成曲線，就得到ROC曲線，可以用于評(píng)價(jià)一個(gè)分類器。ReceiverOperatingCharacteristic，接受者操作特性曲線54?ROC曲線以假正類率FPR為橫軸，真正類率TPR為縱軸，得到ROC曲線虛報(bào)概率(代價(jià))為橫軸，擊中概率(收益)為縱軸55?ROC曲線的分析對(duì)于一個(gè)分類器，每個(gè)閾值對(duì)應(yīng)一個(gè)(TPR，F(xiàn)PR)；閾值最大時(shí)，沒有實(shí)例被分成正例，因此，TP=FP=0，對(duì)應(yīng)于原點(diǎn)(0,0)；閾值最小時(shí)，所有實(shí)例都被分成正例，TN=FN=1，對(duì)應(yīng)于右上角的點(diǎn)(1,1)；隨著閾值從最大變化到最小，TP和FP都逐漸增大。56?ROC曲線實(shí)例57?使用ROC曲線評(píng)價(jià)分類器在ROC曲線中，通常，如果曲線X始終位于曲線Y的左上方，則曲線X優(yōu)于曲線Y。這意味著，對(duì)于所有可能的錯(cuò)誤分類代價(jià)，X分類器的正分類率總是比Y要高。如果一條ROC曲線是經(jīng)過(0,0)和(1,1)的直線，則該分類器為隨機(jī)猜測(cè)分類器。如果X并不總是位于Y的左上側(cè)，可以使用ROC曲線下方的面積作為度量，即：AUC值。AreaUnderrocCurve58?參考文獻(xiàn)ElementsofInformationTheory(Cover&Thomas)PatternRecognitionandMachineLearning,BishopM,Springer-Verlag,2023統(tǒng)計(jì)學(xué)習(xí)方法，李航著，清華大學(xué)出版社，2023年JamieShotton,AndrewFitzgibbon,etc,Real-TimeHumanPoseRecognitioninPartsfromSingleDepthImages,2023:///wiki/Localregression59?謝謝大家！懇請(qǐng)大家批評(píng)指正！60?ASMS3000決策分析平臺(tái)

1、決策分析平臺(tái)的重要性2、訂票、出票、送票統(tǒng)計(jì)3、銷售數(shù)據(jù)分析、坐席工作效率分析與航線銷售對(duì)比分析的查看與統(tǒng)計(jì)4、盈利分析5、員工業(yè)績統(tǒng)計(jì)分析6、問題考核?1.1決策分析平臺(tái)的重要性全方位的統(tǒng)計(jì)公司銷售上的各類數(shù)據(jù)，有利于代理人的領(lǐng)導(dǎo)層掌握公司運(yùn)轉(zhuǎn)狀態(tài)，針對(duì)現(xiàn)有的情況作出進(jìn)一步的決策。

準(zhǔn)確把握員工的工作效率利用決策分析平臺(tái)的各類員工工作效率的分析，制定有效地獎(jiǎng)懲措施，解決工作效率存在的問題。盈利分析

管理層通過具體的盈利數(shù)據(jù)，查看公司的一段時(shí)間內(nèi)各個(gè)階段的盈利數(shù)據(jù)，通過對(duì)比分析原因，制訂下階段的策略。?2.1訂票、出票、送票統(tǒng)計(jì)三個(gè)報(bào)表的統(tǒng)計(jì)數(shù)據(jù)來源1、訂票統(tǒng)計(jì)：訂單來源的統(tǒng)計(jì)，以訂票員為主，