相親、交友與決策樹課件

決策樹學習方法初探

——一個初學者的視角嘚兒個沒決策樹學習方法初探

從我國的一個社會問題說起這是一個愁壞父親母親捧紅了江蘇衛(wèi)視卻樂壞了馬云（和寶強）的問題從我國的一個社會問題說起這是一個2從我國的一個社會問題說起剩男剩女問題引爆的商機雙十一的購物狂歡交友婚介網(wǎng)站/節(jié)目的盛行于是……尼瑪希望能夠幫助單身男女青年更好地選擇交友對象現(xiàn)狀：尼瑪已經(jīng)收集了一些男同胞的資料目標：為優(yōu)秀的女性推薦與之匹配的男性ButHow？先看看現(xiàn)在相親的基本的特征從我國的一個社會問題說起剩男剩女問題引爆的商機3從我國的一個社會問題說起相親的常見場景有一些還沒開始就失敗了有一些還是可能成功的母親：尼美，給你介紹個男朋友吧。尼美：多大年紀了？母親：26。尼美：長的怎么樣？母親：挺帥的。尼美：收入高不？母親：不算很高，中等情況。尼美：是公務員不？母親：是，在稅務局上班呢。尼美：那好，我去見見。從我國的一個社會問題說起相親的常見場景4決策樹的基本思想尼美（女，23歲，企業(yè)白領）是如何選擇相親對象的尼美對對象的屬性建模<性別，長相，年齡，收入，職業(yè)>尼美心中對對象篩選過程性別：當然不能是女的長相：要帥的年齡：比自己大但小于30收入：中等或以上職業(yè)：收入中等則要穩(wěn)定體面尼美根據(jù)屬性將男同胞們分類見or不見決策樹的基本思想尼美（女，23歲，企業(yè)白領）是如何選擇相親對5決策樹的基本思想尼瑪分析了尼美相親判斷過程的基本組成測試結點表示某種作為判斷條件的屬性分支根據(jù)條件屬性取值選取的路徑葉子使判斷終止的結論尼美做選擇時，其實用的是決策樹關鍵在于決策樹如何構造測試節(jié)點分支葉子決策樹的基本思想尼瑪分析了尼美相親判斷過程的基本組成測試節(jié)點6決策樹的基本思想尼瑪?shù)弥崦老嘤H決策樹構造的基本思路從一棵空決策樹開始，選擇某一屬性作為分裂屬性；根據(jù)分裂屬性的值的不同，可將訓練樣本分成若干子集；如果該子集為空，或當前子集中的樣本屬于同一個類，則該子集為葉子結點；否則繼續(xù)以該子集作為測試結點，選擇一個新的分類屬性重復上述步驟對該子集進行劃分，直至屬性集為空或每個子集中的樣本均屬于同一各類。決策樹的最基本功能——分類這個思路就是CLS算法Hunt，Marin和Stone于1966年提出，決策樹的雛形決策樹的基本思想尼瑪?shù)弥崦老嘤H決策樹構造的基本思路7尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪決定開始構造自己的決策樹數(shù)據(jù)就是王道，尼瑪公開了16組數(shù)據(jù)序號姓名職業(yè)分類職位評級收入水平有房有車債務情況評級1A金融A類高1低鉆石男2BITA類中3高經(jīng)適男3C行政A類中2低經(jīng)適男4D司法A類高0低鉆石男5E行政B類中3中牛奮男6F金融B類高3低鉆石男7GITB類中2中牛奮男8H司法A類中2低經(jīng)適男9J行政A類中0低經(jīng)適男10K教育C類低3低牛奮男11L司法A類高3中鉆石男12M教育C類低2低牛奮男13NITB類高0低牛奮男14P教育A類高2中經(jīng)適男15Q教育C類低2低經(jīng)適男16RITB類高2高牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪決定開始構造自己的決策樹序號8尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪構造的決策樹看上去像模像樣但是兩個綠圈里是什么鬼？尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪構造的決策樹9尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪?shù)膶煈嵟四岈斀挥淹扑]系統(tǒng)的構造和優(yōu)化尼瑪?shù)膶煈嵟?0尼瑪交友推薦系統(tǒng)的構造和優(yōu)化面對老板之怒，尼瑪決定求助尼美Yao尼瑪尼美尼美，跪求你的相親決策樹如何去掉那些不必要的判斷，5555構造決策樹的關鍵步驟是分裂屬性。所謂分裂屬性就是在某個節(jié)點處按照某一特征屬性的不同劃分構造不同的分支，其目標是讓各個分裂子集盡可能地“純”。盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類別。尼瑪交友推薦系統(tǒng)的構造和優(yōu)化面對老板之怒，尼瑪決定求助尼美Y11尼瑪交友推薦系統(tǒng)的構造和優(yōu)化面對老板之怒，尼瑪決定求助尼美Yao尼瑪尼美尼美，別光說“純”好不好，我知道要“純”，但怎么看“純不純”？55551948年，香農提出了“信息熵”的概念，解決了對系統(tǒng)信息的量化度量問題。尼美，shang是啥？這種概念我不懂，聽了就覺得很受傷……5555別打岔，好好聽！熵是描述系統(tǒng)混亂程度的度量。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越亂，信息熵就越高。尼瑪交友推薦系統(tǒng)的構造和優(yōu)化面對老板之怒，尼瑪決定求助尼美Y12尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼美對熵的論述（其實應該是轉述）熵的數(shù)學定義根據(jù)Shannon1948信息論理論。事件ai的信息量I可如下度量：

其中p(ai)表示事件ai發(fā)生的概率。給定樣本S，包含n個互不相容的事件a1,a2,a3,….,an,它們中有且僅有一個發(fā)生，則其S平均的信息量可如下度量：尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼美對熵的論述（其實應該是轉述）13尼瑪交友推薦系統(tǒng)的構造和優(yōu)化決策樹的目標是讓分裂子集盡量地“純”越純則“熵”越低因此使用“信息增益”定義每次屬性分裂帶來的熵的變化將樣本集S按屬性A進行劃分為一次屬性分裂，則定義這一次分裂的期望熵為其中v為分裂后子樣本集的個數(shù)I(Sj)為子樣本集對目標分類的熵。在定義好一次分裂的期望熵后，可以定義信息增益尼瑪交友推薦系統(tǒng)的構造和優(yōu)化決策樹的目標是讓分裂子集盡量地“14尼瑪交友推薦系統(tǒng)的構造和優(yōu)化依據(jù)信息增益，可以輔助分裂屬性的選擇選取信息增益最大的屬性作為分裂屬性避免CLS中盲目選擇導致的無意義選擇節(jié)點ID3決策樹算法的基本思路Hi，Guys！我是RossQuinlan，ID3是我的創(chuàng)造，希望大家喜歡，雖然ID3已經(jīng)32歲了，但在我看來他還是個孩子。尼瑪交友推薦系統(tǒng)的構造和優(yōu)化依據(jù)信息增益，可以輔助分裂屬性的15尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹先計算目標分類的熵S1=鉆石男，S2=經(jīng)適男，S3=牛奮男|S1|=4，|S2|=6，

|S3|=6p1=0.25，p2=0.375，p3=0.375I1=0.5，I2=0.5306，I3=0.5306I(S)=1.5612序號姓名評級1A鉆石男2B經(jīng)適男3C經(jīng)適男4D鉆石男5E牛奮男6F鉆石男7G牛奮男8H經(jīng)適男9J經(jīng)適男10K牛奮男11L鉆石男12M牛奮男13N牛奮男14P經(jīng)適男15Q經(jīng)適男16R牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決16尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事IT行業(yè)的為例設為類1經(jīng)適男1個，牛奮男3個I(S1)=0+（-0.25*log20.25）+ (-0.75*log20.75)=0.8113序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決17尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事金融行業(yè)的為例設為類2鉆石男2個I(S2)=0序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決18尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事行政行業(yè)的為例設為類3經(jīng)適男2個，牛奮男1個I(S3)=0+（-0.6667*log20.6667）+ (-0.3333*log20.3333)=0.9183序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決19尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事司法行業(yè)的為例設為類4鉆石男2個，經(jīng)適男1個I(S4)=（-0.6667*log20.6667）+ (-0.3333*log20.3333)+0=0.9183序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決20尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事教育行業(yè)的為例設為類5經(jīng)適男2個，牛奮男2個I(S1)=0+（-0.5*log20.5）+ (-0.5*log20.5)=1序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決21尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹綜合得到按照職業(yè)分類進行屬性分裂的期望熵IA(S)=

0.7972同理可得按照其他屬性分裂的期望熵職為評級-IB(S)=1.0173收入水平-IC(S)=1.3325有房有車-ID(S)=1.2420債務水平-IE(S)=1.7011選取職業(yè)分類作為分裂屬性時信息增益最高尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決22尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹按職業(yè)分類分裂接下去，如何選取下一級分裂屬性？以司法分支為例對職業(yè)分類為司法的子表重新進行ID3運算序號姓名職業(yè)分類職位評級收入水平有房有車債務情況評級4D司法A類高0低鉆石男11L司法B類中3低鉆石男8H司法B類中3中經(jīng)適男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決23尼瑪交友推薦系統(tǒng)的構造和優(yōu)化以司法分支為例目標分類的熵–0.9182以職位評級分裂–1以收入水平分裂–1以有房有車分裂–1以債務情況分裂–0直接選取債務情況分裂序號姓名職業(yè)分類職位評級收入水平有房有車債務情況評級4D司法A類高0低鉆石男11L司法B類中3低鉆石男8H司法B類中3中經(jīng)適男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化以司法分支為例序號姓名職業(yè)分類職24尼瑪交友推薦系統(tǒng)的構造和優(yōu)化基于ID3的決策樹的最終結構成功消除了不該存在的無效分裂屬性減少了搜索深度尼瑪交友推薦系統(tǒng)的構造和優(yōu)化基于ID3的決策樹的最終結構25尼瑪交友推薦系統(tǒng)的構造和優(yōu)化yao尼瑪尼美尼美，你太棒了，現(xiàn)在可以回去跟老板交差了慢著！ID3還是有很多缺陷的：1、ID3選擇分裂屬性時趨向于多值屬性；2、ID3無法處理連續(xù)的屬性值；3、ID3不包含剪枝，易受噪聲影響。就這樣交差，肯定還是會被批評的……，還有這么多麻煩……，你舉個栗子？尼瑪交友推薦系統(tǒng)的構造和優(yōu)化yao尼瑪尼美尼美，你太棒了，現(xiàn)26尼瑪交友推薦系統(tǒng)的構造和優(yōu)化假如尼瑪?shù)臄?shù)據(jù)是這樣的(注意紅字)序號姓名職業(yè)分類職位評級收入有房有車債務情況評級1A金融A類40W1低鉆石男2BITA類18W3高經(jīng)適男3C行政A類19W2低經(jīng)適男4D司法A類35W0低鉆石男5E行政B類11W3中牛奮男6F金融B類37.5W3低鉆石男7GITB類12W2中牛奮男8H司法A類19.8W2低經(jīng)適男9J行政A類24.2W0低經(jīng)適男10K教育C類9.5W3低牛奮男11L司法A類50W3中鉆石男12M教育C類11.8W2低牛奮男13NITB類17W0低牛奮男14P教育A類32W2中經(jīng)適男15Q教育C類14W2低經(jīng)適男16RITB類19.2W2高牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化假如尼瑪?shù)臄?shù)據(jù)是這樣的(注意紅字27尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹按照各種分類進行屬性分裂的期望熵職業(yè)分類-IA(S)=

0.7972職位評級-IB(S)=1.0173收入-IC’(S)=0!(這是感嘆號，不是階乘)有房有車-ID(S)=1.2420債務水平-IE(S)=1.7011尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決28尼瑪交友推薦系統(tǒng)的構造和優(yōu)化生成的決策樹會是這樣滴……這樣的分類可用嗎？現(xiàn)在有X男，年收入40.1W，查無此分支這樣的分類有意義嗎？分類不具有代表性ID號也會成為最佳的分裂屬性OMG！尼瑪交友推薦系統(tǒng)的構造和優(yōu)化生成的決策樹會是這樣滴……OMG29尼瑪交友推薦系統(tǒng)的構造和優(yōu)化關于收入這個分裂屬性的特征多值屬性分裂子集小，所以分裂的期望熵較低分裂屬性的值本身引入了較大的混亂度收入是連續(xù)型變量將其當作離散數(shù)據(jù)分析無法形成正確的分類如何解決這些問題尼瑪交友推薦系統(tǒng)的構造和優(yōu)化關于收入這個分裂屬性的特征30尼瑪交友推薦系統(tǒng)的構造和優(yōu)化C4.5決策樹算法的基本思路采用信息增益率取代信息增益作為分裂屬性選取的標準對連續(xù)型的屬性值進行離散化Hey，Guys！可以嘗試下C4.5。我用了三年時間來解決這些問題。你值得擁有尼瑪交友推薦系統(tǒng)的構造和優(yōu)化Hey，Guys！可以嘗試下C431尼瑪交友推薦系統(tǒng)的構造和優(yōu)化信息增益率的定義設樣本集S按離散屬性A的V個不同的取值劃分為S1,S2,…SV，共V個子集定義分裂指數(shù)

表示這次分裂行為引入的混亂程度則信息增益率定義為尼瑪交友推薦系統(tǒng)的構造和優(yōu)化信息增益率的定義32尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用C4.5重新評估各項分裂屬性GainA(S)=0.7640

SpliteA(S)=1.8806 GainRatioA=0.4063GainB(S)=0.5439 SpliteB(S)=1.8772

GainRatioB=0.2897GainC’(S)=1.5612

SpliteC’(S)=4.0

GainRatioC’=0.3903GainD(S)=

0.3192

SpliteD(S)=1.8606

GainRatioD=0.1716GainE(S)=-0.1399

SpliteE(S)=1.3766

GainRatioE=-0.1016通過信息增益率，可以回避選擇離散的收入作為分裂屬性尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用C4.5重新評估各項分裂33尼瑪交友推薦系統(tǒng)的構造和優(yōu)化事實上，收入是個連續(xù)變量，不能做離散值處理對連續(xù)變量進行離散化，變?yōu)槿舾蓚€離散的區(qū)間尼瑪交友推薦系統(tǒng)的構造和優(yōu)化事實上，收入是個連續(xù)變量，不能做34尼瑪交友推薦系統(tǒng)的構造和優(yōu)化分割區(qū)間的策略從排序數(shù)據(jù)兩端向中間移動分割邊界y’和y’’；計算分割出的三個子集的信息增益率；按照信息增益率最高的分割選取y’和y’’；新的劃分的信息增益率為：0.5409大于GainRatioA=0.4063應該選取連續(xù)型的收入作為第一級分裂屬性收入屬性按照選取的邊界分割成三個區(qū)間尼瑪交友推薦系統(tǒng)的構造和優(yōu)化分割區(qū)間的策略35尼瑪交友推薦系統(tǒng)的構造和優(yōu)化決策樹的剪枝為什么要剪枝？數(shù)據(jù)中有噪音、訓練數(shù)據(jù)量少和過擬合會導致出現(xiàn)錯誤的分類如何剪枝？根據(jù)錯誤分類出現(xiàn)的情況，去掉部分子樹尼瑪交友推薦系統(tǒng)的構造和優(yōu)化決策樹的剪枝36尼瑪交友推薦系統(tǒng)的構造和優(yōu)化剪枝的簡單示例病毒分類樹（C4.5）使用樣本數(shù)據(jù)分析有五個錯誤分類樣例病毒id特征A特征B特征C類別錯分類1YYY陽2YYY陽3YYY陽4YYY陽5YYY陽6YYN陰*7YYN陰*8YYN陰*9YNY陽10YNY陽11YNY陽12YNY陽13YNN陽*14YNN陽*15YNN陰16YNN陰17YNN陰18NNN陰19NYN陰20NYY陰AB負C正正負YYYNNN尼瑪交友推薦系統(tǒng)的構造和優(yōu)化剪枝的簡單示例病毒id特征A特征37尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第1步、決策樹規(guī)則化（C4.5表示決策樹的方法）規(guī)則1IFA=YANDB=YTHEN陽規(guī)則2IFA=YANDB=NANDC=YTHEN陽規(guī)則3IFA=YANDB=NANDC=N

THEN陰規(guī)則4IFA=NTHEN陰AB負C正正負YYYNNN尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第1步、決策樹規(guī)則化（C4.5表38尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第2步規(guī)則精度的計算規(guī)則1IFA=YANDB=Y

THEN陽規(guī)則2IFA=YANDB=NANDC=YTHEN陽規(guī)則3IFA=YANDB=NANDC=NTHEN陰規(guī)則4IFA=N

THEN陰規(guī)則分類正確的數(shù)目分類錯誤的數(shù)目精度1535/82404/43323/54303/3尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第2步規(guī)則精度的計算規(guī)則分類正39尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第3步對規(guī)則進行修剪規(guī)則2與規(guī)則4精度為100%，保留規(guī)則1和3引入了錯誤，進行判斷條件的篩選規(guī)則1使用特征A和特征B規(guī)則3使用了特征A、特征B和特征C建立特征子集引入錯誤率的對比表規(guī)則去掉A去掉B去掉C去掉AB去掉BC去掉AC如何裁剪15/1011/17去掉B34/66/83/98/104/106/17去掉AB尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第3步對規(guī)則進行修剪規(guī)則去掉A40尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第4步、裁剪規(guī)則規(guī)則1IFA=YANDB=YTHEN陽

{18,19,20}規(guī)則2IFA=YANDB=NANDC=YTHEN陽

{9,10,11,12}規(guī)則3IFA=YANDB=NANDC=NTHEN陰

{6,7,8,13,14,15,16,17}規(guī)則4IFA=N

THEN陰

{1,2,3,4,5}依然還有13、14兩個錯誤，但是顯著降低了錯誤率尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第4步、裁剪規(guī)則41尼瑪交友推薦系統(tǒng)的構造和優(yōu)化SB技術員尼美你現(xiàn)在真的可以回去交差了，C4.5足夠解決很多問題了非常感謝！但是，我還有個問題……，我們公司要面向的是單身女青年們，會不會眾口難調啊你逐漸開竅了，確實存在這樣的問題，每個人關注的屬性不同、每個人的評價標準也不同，還好我們有隨機森林尼瑪交友推薦系統(tǒng)的構造和優(yōu)化SB技術員尼美你現(xiàn)在真的可以回去42尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋尼美有幾個閨蜜小龍包如花鳳姐吃貨女青年關注男士屬性<年齡，收入，廚藝，口味，體力，……>究極文藝女青年關注男士屬性<年齡，長相，身高，學歷，是否愛讀讀者，……>拜金女青年關注男士屬性<收入，車房，工作背景，家庭背景，長相，……>尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋43尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋每個閨蜜都為SB公司建立相親決策樹小龍包采樣建樹剪枝尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋44尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋每個閨蜜都為SB公司建立相親決策樹小龍包采樣建樹剪枝如花采樣建樹剪枝尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋45尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋每個閨蜜都為SB公司建立相親決策樹小龍包采樣建樹剪枝如花采樣建樹剪枝……尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋46尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋基于隨機森林的分類分別使用森林中的樹分類表決產(chǎn)生最后的分類對每一個分類樹不需要使用樣本的所有屬性尼瑪交友推薦系統(tǒng)的構造和優(yōu)化隨機森林——一個很不嚴肅的的解釋47尼瑪交友推薦系統(tǒng)的構造和優(yōu)化SB技術員尼美今天不能再講得更多了，以后有機會再聊叩謝大恩，可以跟老板交差去了記得幫我推薦個好對象哈尼瑪交友推薦系統(tǒng)的構造和優(yōu)化SB技術員尼美今天不能再講得更多48關于決策樹的未盡事宜關于分裂屬性選擇參數(shù)Gini系數(shù)（CART算法最初使用）TowingCriteriaχ2分布（CHAID算法使用）……效果幾乎沒有太大差別關于決策樹的未盡事宜關于分裂屬性選擇參數(shù)49關于決策樹的未盡事宜關于剪枝后剪枝是常用手段，主要技術有降低錯誤剪枝REP悲觀錯誤剪枝PEP基于錯誤剪枝EBP（C4.5的剪枝技術）代價-復雜度剪枝CCP（CART算法的剪枝技術）最小錯誤剪枝MEP…各有各得適用場合，因地制宜地用關于決策樹的未盡事宜關于剪枝50關于決策樹的未盡事宜其他著名而關鍵的算法CART-分類回歸樹使用二叉樹代替多叉數(shù)支持回歸分析……Adaboosting嚴格意義上說不是決策樹方法而是對決策樹的優(yōu)化方法（個人見解，還需要在研究）隨機森林涉及的技術細節(jié)很多，我講的很不嚴肅關于決策樹的未盡事宜其他著名而關鍵的算法5152謝謝!請批評指正2014/05/2952謝謝!2014/05/29決策樹學習方法初探

——一個初學者的視角嘚兒個沒決策樹學習方法初探

從我國的一個社會問題說起這是一個愁壞父親母親捧紅了江蘇衛(wèi)視卻樂壞了馬云（和寶強）的問題從我國的一個社會問題說起這是一個54從我國的一個社會問題說起剩男剩女問題引爆的商機雙十一的購物狂歡交友婚介網(wǎng)站/節(jié)目的盛行于是……尼瑪希望能夠幫助單身男女青年更好地選擇交友對象現(xiàn)狀：尼瑪已經(jīng)收集了一些男同胞的資料目標：為優(yōu)秀的女性推薦與之匹配的男性ButHow？先看看現(xiàn)在相親的基本的特征從我國的一個社會問題說起剩男剩女問題引爆的商機55從我國的一個社會問題說起相親的常見場景有一些還沒開始就失敗了有一些還是可能成功的母親：尼美，給你介紹個男朋友吧。尼美：多大年紀了？母親：26。尼美：長的怎么樣？母親：挺帥的。尼美：收入高不？母親：不算很高，中等情況。尼美：是公務員不？母親：是，在稅務局上班呢。尼美：那好，我去見見。從我國的一個社會問題說起相親的常見場景56決策樹的基本思想尼美（女，23歲，企業(yè)白領）是如何選擇相親對象的尼美對對象的屬性建模<性別，長相，年齡，收入，職業(yè)>尼美心中對對象篩選過程性別：當然不能是女的長相：要帥的年齡：比自己大但小于30收入：中等或以上職業(yè)：收入中等則要穩(wěn)定體面尼美根據(jù)屬性將男同胞們分類見or不見決策樹的基本思想尼美（女，23歲，企業(yè)白領）是如何選擇相親對57決策樹的基本思想尼瑪分析了尼美相親判斷過程的基本組成測試結點表示某種作為判斷條件的屬性分支根據(jù)條件屬性取值選取的路徑葉子使判斷終止的結論尼美做選擇時，其實用的是決策樹關鍵在于決策樹如何構造測試節(jié)點分支葉子決策樹的基本思想尼瑪分析了尼美相親判斷過程的基本組成測試節(jié)點58決策樹的基本思想尼瑪?shù)弥崦老嘤H決策樹構造的基本思路從一棵空決策樹開始，選擇某一屬性作為分裂屬性；根據(jù)分裂屬性的值的不同，可將訓練樣本分成若干子集；如果該子集為空，或當前子集中的樣本屬于同一個類，則該子集為葉子結點；否則繼續(xù)以該子集作為測試結點，選擇一個新的分類屬性重復上述步驟對該子集進行劃分，直至屬性集為空或每個子集中的樣本均屬于同一各類。決策樹的最基本功能——分類這個思路就是CLS算法Hunt，Marin和Stone于1966年提出，決策樹的雛形決策樹的基本思想尼瑪?shù)弥崦老嘤H決策樹構造的基本思路59尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪決定開始構造自己的決策樹數(shù)據(jù)就是王道，尼瑪公開了16組數(shù)據(jù)序號姓名職業(yè)分類職位評級收入水平有房有車債務情況評級1A金融A類高1低鉆石男2BITA類中3高經(jīng)適男3C行政A類中2低經(jīng)適男4D司法A類高0低鉆石男5E行政B類中3中牛奮男6F金融B類高3低鉆石男7GITB類中2中牛奮男8H司法A類中2低經(jīng)適男9J行政A類中0低經(jīng)適男10K教育C類低3低牛奮男11L司法A類高3中鉆石男12M教育C類低2低牛奮男13NITB類高0低牛奮男14P教育A類高2中經(jīng)適男15Q教育C類低2低經(jīng)適男16RITB類高2高牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪決定開始構造自己的決策樹序號60尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪構造的決策樹看上去像模像樣但是兩個綠圈里是什么鬼？尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪構造的決策樹61尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪?shù)膶煈嵟四岈斀挥淹扑]系統(tǒng)的構造和優(yōu)化尼瑪?shù)膶煈嵟?2尼瑪交友推薦系統(tǒng)的構造和優(yōu)化面對老板之怒，尼瑪決定求助尼美Yao尼瑪尼美尼美，跪求你的相親決策樹如何去掉那些不必要的判斷，5555構造決策樹的關鍵步驟是分裂屬性。所謂分裂屬性就是在某個節(jié)點處按照某一特征屬性的不同劃分構造不同的分支，其目標是讓各個分裂子集盡可能地“純”。盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類別。尼瑪交友推薦系統(tǒng)的構造和優(yōu)化面對老板之怒，尼瑪決定求助尼美Y63尼瑪交友推薦系統(tǒng)的構造和優(yōu)化面對老板之怒，尼瑪決定求助尼美Yao尼瑪尼美尼美，別光說“純”好不好，我知道要“純”，但怎么看“純不純”？55551948年，香農提出了“信息熵”的概念，解決了對系統(tǒng)信息的量化度量問題。尼美，shang是啥？這種概念我不懂，聽了就覺得很受傷……5555別打岔，好好聽！熵是描述系統(tǒng)混亂程度的度量。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越亂，信息熵就越高。尼瑪交友推薦系統(tǒng)的構造和優(yōu)化面對老板之怒，尼瑪決定求助尼美Y64尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼美對熵的論述（其實應該是轉述）熵的數(shù)學定義根據(jù)Shannon1948信息論理論。事件ai的信息量I可如下度量：

其中p(ai)表示事件ai發(fā)生的概率。給定樣本S，包含n個互不相容的事件a1,a2,a3,….,an,它們中有且僅有一個發(fā)生，則其S平均的信息量可如下度量：尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼美對熵的論述（其實應該是轉述）65尼瑪交友推薦系統(tǒng)的構造和優(yōu)化決策樹的目標是讓分裂子集盡量地“純”越純則“熵”越低因此使用“信息增益”定義每次屬性分裂帶來的熵的變化將樣本集S按屬性A進行劃分為一次屬性分裂，則定義這一次分裂的期望熵為其中v為分裂后子樣本集的個數(shù)I(Sj)為子樣本集對目標分類的熵。在定義好一次分裂的期望熵后，可以定義信息增益尼瑪交友推薦系統(tǒng)的構造和優(yōu)化決策樹的目標是讓分裂子集盡量地“66尼瑪交友推薦系統(tǒng)的構造和優(yōu)化依據(jù)信息增益，可以輔助分裂屬性的選擇選取信息增益最大的屬性作為分裂屬性避免CLS中盲目選擇導致的無意義選擇節(jié)點ID3決策樹算法的基本思路Hi，Guys！我是RossQuinlan，ID3是我的創(chuàng)造，希望大家喜歡，雖然ID3已經(jīng)32歲了，但在我看來他還是個孩子。尼瑪交友推薦系統(tǒng)的構造和優(yōu)化依據(jù)信息增益，可以輔助分裂屬性的67尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹先計算目標分類的熵S1=鉆石男，S2=經(jīng)適男，S3=牛奮男|S1|=4，|S2|=6，

|S3|=6p1=0.25，p2=0.375，p3=0.375I1=0.5，I2=0.5306，I3=0.5306I(S)=1.5612序號姓名評級1A鉆石男2B經(jīng)適男3C經(jīng)適男4D鉆石男5E牛奮男6F鉆石男7G牛奮男8H經(jīng)適男9J經(jīng)適男10K牛奮男11L鉆石男12M牛奮男13N牛奮男14P經(jīng)適男15Q經(jīng)適男16R牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決68尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事IT行業(yè)的為例設為類1經(jīng)適男1個，牛奮男3個I(S1)=0+（-0.25*log20.25）+ (-0.75*log20.75)=0.8113序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決69尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事金融行業(yè)的為例設為類2鉆石男2個I(S2)=0序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決70尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事行政行業(yè)的為例設為類3經(jīng)適男2個，牛奮男1個I(S3)=0+（-0.6667*log20.6667）+ (-0.3333*log20.3333)=0.9183序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決71尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事司法行業(yè)的為例設為類4鉆石男2個，經(jīng)適男1個I(S4)=（-0.6667*log20.6667）+ (-0.3333*log20.3333)+0=0.9183序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決72尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事教育行業(yè)的為例設為類5經(jīng)適男2個，牛奮男2個I(S1)=0+（-0.5*log20.5）+ (-0.5*log20.5)=1序號職業(yè)分類評級1金融鉆石男2IT經(jīng)適男3行政經(jīng)適男4司法鉆石男5行政牛奮男6金融鉆石男7IT牛奮男8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決73尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹綜合得到按照職業(yè)分類進行屬性分裂的期望熵IA(S)=

0.7972同理可得按照其他屬性分裂的期望熵職為評級-IB(S)=1.0173收入水平-IC(S)=1.3325有房有車-ID(S)=1.2420債務水平-IE(S)=1.7011選取職業(yè)分類作為分裂屬性時信息增益最高尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決74尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹按職業(yè)分類分裂接下去，如何選取下一級分裂屬性？以司法分支為例對職業(yè)分類為司法的子表重新進行ID3運算序號姓名職業(yè)分類職位評級收入水平有房有車債務情況評級4D司法A類高0低鉆石男11L司法B類中3低鉆石男8H司法B類中3中經(jīng)適男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決75尼瑪交友推薦系統(tǒng)的構造和優(yōu)化以司法分支為例目標分類的熵–0.9182以職位評級分裂–1以收入水平分裂–1以有房有車分裂–1以債務情況分裂–0直接選取債務情況分裂序號姓名職業(yè)分類職位評級收入水平有房有車債務情況評級4D司法A類高0低鉆石男11L司法B類中3低鉆石男8H司法B類中3中經(jīng)適男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化以司法分支為例序號姓名職業(yè)分類職76尼瑪交友推薦系統(tǒng)的構造和優(yōu)化基于ID3的決策樹的最終結構成功消除了不該存在的無效分裂屬性減少了搜索深度尼瑪交友推薦系統(tǒng)的構造和優(yōu)化基于ID3的決策樹的最終結構77尼瑪交友推薦系統(tǒng)的構造和優(yōu)化yao尼瑪尼美尼美，你太棒了，現(xiàn)在可以回去跟老板交差了慢著！ID3還是有很多缺陷的：1、ID3選擇分裂屬性時趨向于多值屬性；2、ID3無法處理連續(xù)的屬性值；3、ID3不包含剪枝，易受噪聲影響。就這樣交差，肯定還是會被批評的……，還有這么多麻煩……，你舉個栗子？尼瑪交友推薦系統(tǒng)的構造和優(yōu)化yao尼瑪尼美尼美，你太棒了，現(xiàn)78尼瑪交友推薦系統(tǒng)的構造和優(yōu)化假如尼瑪?shù)臄?shù)據(jù)是這樣的(注意紅字)序號姓名職業(yè)分類職位評級收入有房有車債務情況評級1A金融A類40W1低鉆石男2BITA類18W3高經(jīng)適男3C行政A類19W2低經(jīng)適男4D司法A類35W0低鉆石男5E行政B類11W3中牛奮男6F金融B類37.5W3低鉆石男7GITB類12W2中牛奮男8H司法A類19.8W2低經(jīng)適男9J行政A類24.2W0低經(jīng)適男10K教育C類9.5W3低牛奮男11L司法A類50W3中鉆石男12M教育C類11.8W2低牛奮男13NITB類17W0低牛奮男14P教育A類32W2中經(jīng)適男15Q教育C類14W2低經(jīng)適男16RITB類19.2W2高牛奮男尼瑪交友推薦系統(tǒng)的構造和優(yōu)化假如尼瑪?shù)臄?shù)據(jù)是這樣的(注意紅字79尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決策樹按照各種分類進行屬性分裂的期望熵職業(yè)分類-IA(S)=

0.7972職位評級-IB(S)=1.0173收入-IC’(S)=0!(這是感嘆號，不是階乘)有房有車-ID(S)=1.2420債務水平-IE(S)=1.7011尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用ID3重新構造了自己的決80尼瑪交友推薦系統(tǒng)的構造和優(yōu)化生成的決策樹會是這樣滴……這樣的分類可用嗎？現(xiàn)在有X男，年收入40.1W，查無此分支這樣的分類有意義嗎？分類不具有代表性ID號也會成為最佳的分裂屬性OMG！尼瑪交友推薦系統(tǒng)的構造和優(yōu)化生成的決策樹會是這樣滴……OMG81尼瑪交友推薦系統(tǒng)的構造和優(yōu)化關于收入這個分裂屬性的特征多值屬性分裂子集小，所以分裂的期望熵較低分裂屬性的值本身引入了較大的混亂度收入是連續(xù)型變量將其當作離散數(shù)據(jù)分析無法形成正確的分類如何解決這些問題尼瑪交友推薦系統(tǒng)的構造和優(yōu)化關于收入這個分裂屬性的特征82尼瑪交友推薦系統(tǒng)的構造和優(yōu)化C4.5決策樹算法的基本思路采用信息增益率取代信息增益作為分裂屬性選取的標準對連續(xù)型的屬性值進行離散化Hey，Guys！可以嘗試下C4.5。我用了三年時間來解決這些問題。你值得擁有尼瑪交友推薦系統(tǒng)的構造和優(yōu)化Hey，Guys！可以嘗試下C483尼瑪交友推薦系統(tǒng)的構造和優(yōu)化信息增益率的定義設樣本集S按離散屬性A的V個不同的取值劃分為S1,S2,…SV，共V個子集定義分裂指數(shù)

表示這次分裂行為引入的混亂程度則信息增益率定義為尼瑪交友推薦系統(tǒng)的構造和優(yōu)化信息增益率的定義84尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用C4.5重新評估各項分裂屬性GainA(S)=0.7640

SpliteA(S)=1.8806 GainRatioA=0.4063GainB(S)=0.5439 SpliteB(S)=1.8772

GainRatioB=0.2897GainC’(S)=1.5612

SpliteC’(S)=4.0

GainRatioC’=0.3903GainD(S)=

0.3192

SpliteD(S)=1.8606

GainRatioD=0.1716GainE(S)=-0.1399

SpliteE(S)=1.3766

GainRatioE=-0.1016通過信息增益率，可以回避選擇離散的收入作為分裂屬性尼瑪交友推薦系統(tǒng)的構造和優(yōu)化尼瑪使用C4.5重新評估各項分裂85尼瑪交友推薦系統(tǒng)的構造和優(yōu)化事實上，收入是個連續(xù)變量，不能做離散值處理對連續(xù)變量進行離散化，變?yōu)槿舾蓚€離散的區(qū)間尼瑪交友推薦系統(tǒng)的構造和優(yōu)化事實上，收入是個連續(xù)變量，不能做86尼瑪交友推薦系統(tǒng)的構造和優(yōu)化分割區(qū)間的策略從排序數(shù)據(jù)兩端向中間移動分割邊界y’和y’’；計算分割出的三個子集的信息增益率；按照信息增益率最高的分割選取y’和y’’；新的劃分的信息增益率為：0.5409大于GainRatioA=0.4063應該選取連續(xù)型的收入作為第一級分裂屬性收入屬性按照選取的邊界分割成三個區(qū)間尼瑪交友推薦系統(tǒng)的構造和優(yōu)化分割區(qū)間的策略87尼瑪交友推薦系統(tǒng)的構造和優(yōu)化決策樹的剪枝為什么要剪枝？數(shù)據(jù)中有噪音、訓練數(shù)據(jù)量少和過擬合會導致出現(xiàn)錯誤的分類如何剪枝？根據(jù)錯誤分類出現(xiàn)的情況，去掉部分子樹尼瑪交友推薦系統(tǒng)的構造和優(yōu)化決策樹的剪枝88尼瑪交友推薦系統(tǒng)的構造和優(yōu)化剪枝的簡單示例病毒分類樹（C4.5）使用樣本數(shù)據(jù)分析有五個錯誤分類樣例病毒id特征A特征B特征C類別錯分類1YYY陽2YYY陽3YYY陽4YYY陽5YYY陽6YYN陰*7YYN陰*8YYN陰*9YNY陽10YNY陽11YNY陽12YNY陽13YNN陽*14YNN陽*15YNN陰16YNN陰17YNN陰18NNN陰19NYN陰20NYY陰AB負C正正負YYYNNN尼瑪交友推薦系統(tǒng)的構造和優(yōu)化剪枝的簡單示例病毒id特征A特征89尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第1步、決策樹規(guī)則化（C4.5表示決策樹的方法）規(guī)則1IFA=YANDB=YTHEN陽規(guī)則2IFA=YANDB=NANDC=YTHEN陽規(guī)則3IFA=YANDB=NANDC=N

THEN陰規(guī)則4IFA=NTHEN陰AB負C正正負YYYNNN尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第1步、決策樹規(guī)則化（C4.5表90尼瑪交友推薦系統(tǒng)的構造和優(yōu)化第2步規(guī)則精度的計算規(guī)則1IFA=YANDB=Y

THEN陽規(guī)則2IFA=YANDB=NANDC=YTHEN陽規(guī)則3IFA