相親、交友與決策樹ppt課件

1、決策樹學(xué)習(xí)方法初探 一個初學(xué)者的視角嘚兒個沒從我國的一個社會問題說起這是一個愁壞父親母親捧紅了江蘇衛(wèi)視卻樂壞了馬云和寶強(qiáng)的問題從我國的一個社會問題說起剩男剩女問題引爆的商機(jī)雙十一的購物狂歡交友婚介網(wǎng)站/節(jié)目的盛行于是尼瑪希望可以協(xié)助獨身男女青年更好地選擇交友對象現(xiàn)狀：尼瑪曾經(jīng)搜集了一些男同胞的資料目的：為優(yōu)秀的女性引薦與之匹配的男性But How？先看看如今相親的根本的特征從我國的一個社會問題說起相親的常見場景有一些還沒開場就失敗了有一些還是能夠勝利的母親：尼美，給他引見個男朋友吧。尼美：多大年紀(jì)了？母親：26。尼美：長的怎樣樣？母親：挺帥的。尼美：收入高不？母親：不算很高，中等情況。尼美：是

2、公務(wù)員不？母親：是，在稅務(wù)局上班呢。尼美：那好，我去見見。決策樹的根本思想尼美女，23歲，企業(yè)白領(lǐng)是如何選擇相親對象的尼美對對象的屬性建模尼美心中對對象挑選過程性別：當(dāng)然不能是女的長相：要帥的年齡：比本人大但小于30收入：中等或以上職業(yè)：收入中等那么要穩(wěn)定面子尼美根據(jù)屬性將男同胞們分類見 or 不見決策樹的根本思想尼瑪分析了尼美相親判別過程的根本組成測試結(jié)點表示某種作為判別條件的屬性分支根據(jù)條件屬性取值選取的途徑葉子使判別終止的結(jié)論尼美做選擇時，其適用的是決策樹關(guān)鍵在于決策樹如何構(gòu)造測試節(jié)點分支葉子決策樹的根本思想尼瑪?shù)弥崦老嘤H決策樹構(gòu)造的根本思緒從一棵空決策樹開場，選擇某一屬性作為分裂屬性

3、；根據(jù)分裂屬性的值的不同，可將訓(xùn)練樣本分成假設(shè)干子集；假設(shè)該子集為空，或當(dāng)前子集中的樣本屬于同一個類，那么該子集為葉子結(jié)點；否那么繼續(xù)以該子集作為測試結(jié)點，選擇一個新的分類屬性反復(fù)上述步驟對該子集進(jìn)展劃分，直至屬性集為空或每個子集中的樣本均屬于同一各類。決策樹的最根本功能分類這個思緒就是CLS算法Hunt，Marin和Stone于1966年提出，決策樹的雛形尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼瑪決議開場構(gòu)造本人的決策樹數(shù)據(jù)就是王道，尼瑪公開了16組數(shù)據(jù)序號姓名職業(yè)分類職位評級收入水平有房有車債務(wù)情況評級1A金融A類高1低鉆石男2BITA類中3高經(jīng)適男3C行政A類中2低經(jīng)適男4D司法A類高0低鉆石男5

4、E行政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)的構(gòu)造和優(yōu)化尼瑪構(gòu)造的決策樹看上去像模像樣但是兩個綠圈里是什么鬼？尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼瑪?shù)膶?dǎo)師憤怒了尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化面對老板之怒，尼瑪決議求助尼美Yao尼瑪尼美尼美，跪求他的相親決策樹如何去掉那些不用要的判別，5555構(gòu)造決策樹的關(guān)鍵步驟是分裂屬性。所謂分裂屬

5、性就是在某個節(jié)點處按照某一特征屬性的不同劃分構(gòu)造不同的分支，其目的是讓各個分裂子集盡能夠地“純。盡能夠“純就是盡量讓一個分裂子集中待分類項屬于同一類別。尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化面對老板之怒，尼瑪決議求助尼美Yao尼瑪尼美尼美，別光說“純好不好，我知道要“純，但怎樣看“純不純？55551948年，香農(nóng)提出了“信息熵的概念，處理了對系統(tǒng)信息的量化度量問題。尼美，shang是啥？這種概念我不懂，聽了就覺得很受傷 5555別打岔，好好聽！熵是描畫系統(tǒng)混亂程度的度量。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越亂，信息熵就越高。尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼美對熵的論述其實應(yīng)該是轉(zhuǎn)述熵的數(shù)學(xué)定義

6、根據(jù)Shannon1948信息論實際。事件ai的信息量I可如下度量：其中p(ai)表示事件ai發(fā)生的概率。給定樣本S，包含n個互不相容的事件a1,a2,a3,.,an,它們中有且僅有一個發(fā)生，那么其S平均的信息量可如下度量：尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化決策樹的目的是讓分裂子集盡量地“純越純那么“熵越低因此運用“信息增益定義每次屬性分裂帶來的熵的變化將樣本集S按屬性A進(jìn)展劃分為一次屬性分裂，那么定義這一次分裂的期望熵為其中v為分裂后子樣本集的個數(shù)I(Sj)為子樣本集對目的分類的熵。在定義好一次分裂的期望熵后，可以定義信息增益尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化根據(jù)信息增益，可以輔助分裂屬性的選擇選取信息

7、增益最大的屬性作為分裂屬性防止CLS中盲目選擇導(dǎo)致的無意義選擇節(jié)點ID3決策樹算法的根本思緒Hi，Guys！我是Ross Quinlan，ID3是我的發(fā)明，希望大家喜歡，雖然ID3曾經(jīng)32歲了，但在我看來他還是個孩子。尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼瑪運用ID3重新構(gòu)造了本人的決策樹先計算目的分類的熵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)適

8、男9J經(jīng)適男10K牛奮男11L鉆石男12M牛奮男13N牛奮男14P經(jīng)適男15Q經(jīng)適男16R牛奮男尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼瑪運用ID3重新構(gòu)造了本人的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事IT行業(yè)的為例設(shè)為類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)的構(gòu)造和優(yōu)化尼瑪運

9、用ID3重新構(gòu)造了本人的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事金融行業(yè)的為例設(shè)為類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)的構(gòu)造和優(yōu)化尼瑪運用ID3重新構(gòu)造了本人的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事行政行業(yè)的為例設(shè)為類3經(jīng)適男2個，牛奮男1個I (S3)=0+-0.6667*log20.6667+(-0.3333*log20.3333)=0

10、.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)的構(gòu)造和優(yōu)化尼瑪運用ID3重新構(gòu)造了本人的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事司法行業(yè)的為例設(shè)為類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牛奮男

11、8司法經(jīng)適男9行政經(jīng)適男10教育牛奮男11司法鉆石男12教育牛奮男13IT牛奮男14教育經(jīng)適男15教育經(jīng)適男16IT牛奮男尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼瑪運用ID3重新構(gòu)造了本人的決策樹再逐個計算各分裂屬性的期望熵職業(yè)分類5類以從事教育行業(yè)的為例設(shè)為類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)的構(gòu)造和優(yōu)

12、化尼瑪運用ID3重新構(gòu)造了本人的決策樹綜合得到按照職業(yè)分類進(jìn)展屬性分裂的期望熵IA(S)= 0.7972同理可得按照其他屬性分裂的期望熵職為評級 - IB(S)=1.0173收入程度 - IC(S)=1.3325有房有車 - ID(S)=1.2420債務(wù)程度 - IE(S)=1.7011選取職業(yè)分類作為分裂屬性時信息增益最高尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼瑪運用ID3重新構(gòu)造了本人的決策樹按職業(yè)分類分裂接下去，如何選取下一級分裂屬性？以司法分支為例對職業(yè)分類為司法的子表重新進(jìn)展ID3運算序號姓名職業(yè)分類職位評級收入水平有房有車債務(wù)情況評級4D司法A類高0低鉆石男11L司法B類中3低鉆石男8H司法

13、B類中3中經(jīng)適男尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化以司法分支為例目的分類的熵 0.9182以職位評級分裂 1以收入程度分裂 1以有房有車分裂 1以債務(wù)情況分裂 0直接選取債務(wù)情況分裂序號姓名職業(yè)分類職位評級收入水平有房有車債務(wù)情況評級4D司法A類高0低鉆石男11L司法B類中3低鉆石男8H司法B類中3中經(jīng)適男尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化基于ID3的決策樹的最終構(gòu)造勝利消除了不該存在的無效分裂屬性減少了搜索深度尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化yao尼瑪尼美尼美，他太棒了，如今可以回去跟老板交差了慢著！ID3還是有很多缺陷的：1、ID3選擇分裂屬性時趨向于多值屬性；2、ID3無法處置延續(xù)的屬性值；3、ID3不

14、包含剪枝，易受噪聲影響 。就這樣交差，一定還是會被批判的，還有這么多費事，他舉個栗子？尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化假設(shè)尼瑪?shù)臄?shù)據(jù)是這樣的(留意紅字)序號姓名職業(yè)分類職位評級收入有房有車債務(wù)情況評級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

15、類32W2中經(jīng)適男15Q教育C類14W2低經(jīng)適男16RITB類19.2W2高牛奮男尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼瑪運用ID3重新構(gòu)造了本人的決策樹按照各種分類進(jìn)展屬性分裂的期望熵職業(yè)分類 - IA(S)= 0.7972職位評級 - IB(S)=1.0173收入 - IC(S)=0!(這是感慨號，不是階乘)有房有車 - ID(S)=1.2420債務(wù)程度 - IE(S)=1.7011尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化生成的決策樹會是這樣滴這樣的分類可用嗎？如今有X男，年收入40.1W，查無此分支這樣的分類有意義嗎？分類不具有代表性ID號也會成為最正確的分裂屬性O(shè)MG！尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化關(guān)于收入

16、這個分裂屬性的特征多值屬性分裂子集小，所以分裂的期望熵較低分裂屬性的值本身引入了較大的混亂度收入是延續(xù)型變量將其當(dāng)作離散數(shù)據(jù)分析無法構(gòu)成正確的分類如何處理這些問題尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化C4.5決策樹算法的根本思緒采用信息增益率取代信息增益作為分裂屬性選取的規(guī)范對延續(xù)型的屬性值進(jìn)展離散化Hey，Guys！可以嘗試下C4.5。我用了三年時間來處理這些問題。他值得擁有尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化信息增益率的定義設(shè)樣本集S按離散屬性A的V個不同的取值劃分為S1, S2, SV，共V個子集定義分裂指數(shù)表示這次分裂行為引入的混亂程度那么信息增益率定義為尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化尼瑪運用C4.5重新

17、評價各項分裂屬性GainA(S)=0.7640 SpliteA(S)=1.8806GainRatioA=0.4063GainB(S)=0.5439 SpliteB(S)=1.8772GainRatioB=0.2897GainC(S)= 1.5612 SpliteC (S)=4.0GainRatioC=0.3903GainD(S)= 0.3192 SpliteD(S)=1.8606GainRatioD=0.1716GainE(S)= -0.9 SpliteE(S)=1.3766GainRatioE=-0.1016經(jīng)過信息增益率，可以逃避選擇離散的收入作為分裂屬性尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化現(xiàn)實上

18、，收入是個延續(xù)變量，不能做離散值處置對延續(xù)變量進(jìn)展離散化，變?yōu)榧僭O(shè)干個離散的區(qū)間尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化分割區(qū)間的戰(zhàn)略從排序數(shù)據(jù)兩端向中間挪動分割邊境y和y；計算分割出的三個子集的信息增益率；按照信息增益率最高的分割選取y和y；新的劃分的信息增益率為：0.5409大于GainRatioA=0.4063應(yīng)該選取延續(xù)型的收入作為第一級分裂屬性收入屬性按照選取的邊境分割成三個區(qū)間尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化決策樹的剪枝為什么要剪枝？數(shù)據(jù)中有噪音、訓(xùn)練數(shù)據(jù)量少和過擬合會導(dǎo)致出現(xiàn)錯誤的分類如何剪枝？根據(jù)錯誤分類出現(xiàn)的情況，去掉部分子樹尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化剪枝的簡單例如病毒分類樹C4.5運用樣

19、本數(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負(fù)C正正負(fù)YYYNNN尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化第1步、決策樹規(guī)那么化C4.5表示決策樹的方法規(guī)那么1 IF A=Y AND B=Y THEN 陽規(guī)那么2 IF A=Y AND B=N AND C=Y THEN 陽規(guī)那么3 IF A=Y AND B=N AND C=N THEN 陰規(guī)那么4 IF

20、A=N THEN 陰AB負(fù)C正正負(fù)YYYNNN尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化第2步 規(guī)那么精度的計算規(guī)那么1 IF A=Y AND B=Y THEN 陽規(guī)那么2 IF A=Y AND B=N AND C=Y THEN 陽規(guī)那么3 IF A=Y AND B=N AND C=N THEN 陰規(guī)那么4 IF A=N THEN 陰規(guī)則分類正確的數(shù)目分類錯誤的數(shù)目精度1535/82404/43323/54303/3尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化第3步 對規(guī)那么進(jìn)展修剪規(guī)那么2與規(guī)那么4精度為100%，保管規(guī)那么1和3引入了錯誤，進(jìn)展判別條件的挑選規(guī)那么1運用特征A和特征B規(guī)那么3運用了特征A、特征B和特征C

21、建立特征子集引入錯誤率的對比表規(guī)則去掉A去掉B去掉C去掉AB去掉BC去掉AC如何裁剪15/1011/17去掉B34/66/83/98/104/106/17去掉AB尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化第4步、裁剪規(guī)那么規(guī)那么1 IF A=Y AND B=Y THEN 陽18, 19, 20規(guī)那么2 IF A=Y AND B=N AND C=Y THEN 陽 9, 10, 11, 12規(guī)那么3 IF A=Y AND B=N AND C=N THEN 陰6, 7, 8, 13, 14, 15, 16, 17規(guī)那么4 IF A=N THEN 陰 1, 2, 3, 4, 5依然還有13、14兩個錯誤，但是顯著降低了錯誤率尼瑪交友引薦系統(tǒng)的構(gòu)造和優(yōu)化SB技術(shù)員尼美他如今真的可以回去交差了，C4.5足夠處理很多問題了非常贊賞！但是，我還有個問題，我們公司要面向的是獨身女青年們，會不會眾口難調(diào)啊他逐漸開竅了，確實存在這樣的問題，每個人關(guān)注的