轉(zhuǎn)自
算法雜貨鋪--決策樹(shù)
決策樹(shù)和隨機(jī)森林學(xué)習(xí)筆記-歡迎補(bǔ)充
http://www.cnblogs.com/fionacai/p/5894142.html
決策樹(shù)- 基礎(chǔ)概念
熵
熵是表示隨機(jī)變量不確定性的度量镶柱。設(shè)X是一個(gè)取有限個(gè)值的離散隨機(jī)變量,其概率分布為
P(X=xi)=pi,i=1,2,?,n
則隨機(jī)變量的熵定義為
另外,0log0=0佳恬,當(dāng)對(duì)數(shù)的底為2時(shí)榨了,熵的單位為bit江锨;為e時(shí)闻牡,單位為nat盗似。
熵越大,隨機(jī)變量的不確定性就越大沥邻。從定義可驗(yàn)證
0≤H(p)≤logn
算法思想
基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹(shù)危虱,到葉子節(jié)點(diǎn)處的熵值為零,此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類(lèi)唐全。
就是通過(guò)一棵按照屬性分裂出來(lái)的二叉樹(shù)埃跷,多叉樹(shù),最后決定這一組樣本所屬的類(lèi)別邮利。
內(nèi)部節(jié)點(diǎn)標(biāo)示屬性弥雹、葉子節(jié)點(diǎn)存放所屬的類(lèi)別。
圖示如下:
通過(guò)根節(jié)點(diǎn)根據(jù)這些屬性對(duì)下走延届,很容易判斷出來(lái)這組屬性的瓜是屬于好瓜還是壞瓜缅糟。
信息熵下降越快,說(shuō)明信息越明確祷愉,就是尋找純度最好的分類(lèi)方法窗宦,純度通俗點(diǎn)理解就是目標(biāo)變量要分得足夠開(kāi)(y=1的和y=0的混到一起就會(huì)不純)。
決策樹(shù)分裂算法
決策樹(shù)使用比較簡(jiǎn)單二鳄,那么如何構(gòu)建就成了關(guān)鍵赴涵。
一般來(lái)說(shuō),可以選擇的屬性很多订讼,那么每一步應(yīng)該選擇哪個(gè)分支髓窜,這是根據(jù)前面的原來(lái)判斷信息熵下降最快的分支作為分裂的分支。
而判斷信息熵下降情況的有三種算法:
ID3算法: 使用信息增益作為不純度欺殿,核心思想是以信息增益度量屬性選擇寄纵,選擇分裂后的信息增益最大的,也就是熵在分裂前后差值最大的屬性進(jìn)行分裂脖苏。
根據(jù)log(x)的函數(shù)可知程拭,p值越小,熵越大棍潘,所以當(dāng)分組完全是會(huì)出現(xiàn)p=0此時(shí)熵最大恃鞋,概率為0說(shuō)明已經(jīng)最純了。
學(xué)習(xí)數(shù)據(jù)挖掘技術(shù)的最好方法是找到詳細(xì)案例和看懂計(jì)算過(guò)程亦歉。有時(shí)算法雖然不難恤浪,但公式表達(dá)很難理解。
表中S肴楷、M和L分別表示小水由、中和大。
設(shè)L赛蔫、F砂客、H和R表示日志密度直秆、好友密度、是否使用真實(shí)頭像和賬號(hào)是否真實(shí)鞭盟,試用ID3算法構(gòu)造決策樹(shù)圾结。
解:設(shè)D為10個(gè)樣本集,其中決策屬性(真實(shí)賬戶(hù)/R)有7個(gè)YES齿诉、3個(gè)NO筝野。決策屬性信息熵為:
如果按照日志密度來(lái)分類(lèi):計(jì)算日志密度熵值,日志密度分為3類(lèi)S粤剧,L歇竟,M
其中L分類(lèi),樣本總數(shù)10抵恋,L類(lèi)3焕议,L類(lèi)中假賬號(hào)0 真實(shí)賬號(hào)3
所以:
所以gain(L) = 0.876-0.603 = 0.273
同理計(jì)算好友密度信息增益:
計(jì)算真實(shí)頭像的信息增益:
因?yàn)楹糜衙芏龋‵)具有最大的信息增益(好友密度信息熵最小,最易分割)弧关,所以第一次分裂選擇好友密度F為分裂屬性(實(shí)際中如果特征非常多是隨機(jī)選擇一些特征然后計(jì)算后選取的不能遍歷所有情況)盅安,分裂后的結(jié)果如下:
圖中:按好友密度(F)分割樹(shù),水平M和L為單一水平?jīng)Q策屬性分支(樹(shù)葉)世囊,沒(méi)有必要繼續(xù)分割别瞭。水平S包含決策屬性的不同水平,應(yīng)該繼續(xù)分割株憾。待分割決策信息表為:
此時(shí)蝙寨,設(shè)D為4個(gè)樣本集,其中決策屬性(真實(shí)賬戶(hù)/R)有1個(gè)YES嗤瞎、3個(gè)NO墙歪。決策屬性信息熵為:
日志密度屬性期望信息熵為:
真實(shí)頭像屬性期望信息熵為:
因?yàn)槿罩久芏龋↙)具有最大的信息增益,所以第二次分裂選擇日志密度(L)為分裂屬性贝奇,分裂后的結(jié)果如下圖表示:
圖中虹菲,日志密度為M時(shí),無(wú)法做出判斷弃秆、也無(wú)法繼續(xù)進(jìn)行分裂届惋。至此,決策樹(shù)構(gòu)建完畢菠赚。
設(shè)某人在SNS社區(qū)中的好友密度為L(zhǎng)或M,無(wú)論其它屬性水平取值如何郑藏,均可判定為是真實(shí)賬戶(hù)衡查;如果某人在SNS社區(qū)中的好友密度為S、日志密度也為S必盖,可判定為是虛假賬戶(hù)拌牲;如果某人在SNS社區(qū)中的好友密度為S俱饿、日志密度為M,應(yīng)根據(jù)真實(shí)頭像信息做出判斷塌忽,由于樣本過(guò)少拍埠,無(wú)法繼續(xù)進(jìn)行。
C4.5算法:使用信息增益率作為不純度土居。
ID3算法是決策樹(shù)的一個(gè)經(jīng)典的構(gòu)造算法枣购,但I(xiàn)D3算法也存在一些問(wèn)題,比較突出的缺陷是信息增益的計(jì)算依賴(lài)于特征水平較多的特征擦耀,而屬性取值最多的屬性并不一定最優(yōu)棉圈。例如,投擲一枚分幣和一個(gè)色子這兩個(gè)隨機(jī)試驗(yàn)眷蜓,所有可能的期望信息熵為:
通過(guò)信息熵的定義可知,在給定特征水平數(shù)條件下吁系,各水平發(fā)生概率相等(如擲篩子6個(gè)數(shù)字發(fā)生的概率都為1/6。期望信息熵最大汽纤。所以,當(dāng)決策信息中某個(gè)變量特征水平較多時(shí)液茎,ID3算法按信息增益指標(biāo)往往會(huì)選擇該變量或?qū)傩宰鰹榉指罟?jié)點(diǎn)。
I辞嗡、“分裂信息”公式
C4.5算法首先定義了“分裂信息”捆等,其定義可以表示成:
II、增益率
III续室、分裂信息和增益率計(jì)算實(shí)例
在ID3算法案例中(SNS社區(qū)中不真實(shí)賬號(hào)檢測(cè))栋烤,決策屬性信息熵為:
把決策屬性替換成其它屬性,即為各屬性分裂信息熵挺狰。
日志密度分裂信息:
好友密度分裂信息:
真實(shí)頭像分裂信息:
由前面ID3算法已知明郭,
各屬性增益率為,
由上述計(jì)算結(jié)果可知“好友密度”在屬性中具有最大的信息增益比丰泊,取“好友密度”為分割屬性薯定,引出一個(gè)分枝,樣本按此劃分瞳购。對(duì)引出的每一個(gè)分枝再用此分類(lèi)法進(jìn)行分類(lèi)话侄,再引出分枝。
某屬性的信息增益除以分裂信息,消除了屬性水平數(shù)量多少的影響年堆,使得分裂屬性的選擇更加合理吞杭。
CART:: 使用基尼系數(shù)函數(shù)作為不純度。
決策樹(shù)方法是會(huì)把每個(gè)特征都試一遍变丧,然后選取那個(gè)芽狗,能夠使分類(lèi)分的最好的特征,也就是說(shuō)將A屬性作為父節(jié)點(diǎn)痒蓬,產(chǎn)生的純度增益(GainA)要大于B屬性作為父節(jié)點(diǎn)童擎,則A作為優(yōu)先選取的屬性。既可以做分類(lèi)谊却,也可以做回歸。只能形成二叉樹(shù)捕透。
分支條件:二分類(lèi)問(wèn)題
分支方法:對(duì)于連續(xù)特征的情況:比較閾值乙嘀,高于某個(gè)閾值就屬于某一類(lèi),低于某個(gè)閾值屬于另一類(lèi)几莽。對(duì)于離散特征:抽取子特征章蚣,比如顏值這個(gè)特征,有帥峭沦、丑熙侍、中等三個(gè)水平蛉抓,可以先分為帥和不帥的,不帥的里面再分成丑和中等的笑跛。
得分函數(shù)(y):就是上面提到的gt(x)飞蹂,對(duì)于分類(lèi)樹(shù)取得是分類(lèi)最多的那個(gè)結(jié)果(也即眾數(shù)),對(duì)于回歸樹(shù)取得是均值惊窖。
損失函數(shù):其實(shí)這里的損失函數(shù)界酒,就是分類(lèi)的準(zhǔn)則,也就是求最優(yōu)化的準(zhǔn)則
對(duì)于分類(lèi)樹(shù)(目標(biāo)變量為離散變量):同一層所有分支假設(shè)函數(shù)的基尼系數(shù)的平均凭疮。
對(duì)于回歸樹(shù)(目標(biāo)變量為連續(xù)變量):同一層所有分支假設(shè)函數(shù)的平方差損失
對(duì)于分類(lèi)樹(shù)(目標(biāo)變量為離散變量):使用基尼系數(shù)作為分裂規(guī)則哭尝。比較分裂前的gini和分裂后的gini減少多少材鹦,減少的越多桶唐,則選取該分裂規(guī)則尤泽,這里的求解方法只能是離散窮舉熊咽。關(guān)于基尼系數(shù)横殴,可以參考周志華的西瓜書(shū)決策樹(shù)那章,講得比較簡(jiǎn)潔文狱,也比較易懂瞄崇「芨ぃ“直觀來(lái)說(shuō)楣富,(數(shù)據(jù)集D的基尼系數(shù))Gini(D)反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個(gè)樣本,其類(lèi)別標(biāo)記不一致的概率塘安,因此Gini(D)越小兼犯,則數(shù)據(jù)集D的純度越高切黔。”
具體這個(gè)的計(jì)算驱显,我覺(jué)得有例子才好理解伏恐,下面這個(gè)紅綠球的例子很好的說(shuō)明了臭笆,如何根據(jù)損失函數(shù)最谐诱啤(也就是基尼系數(shù)最小)來(lái)選取分裂規(guī)則孟岛。最后GIINs2更小渠羞,因此選擇它作為分類(lèi)規(guī)則次询。
對(duì)于回歸樹(shù)(目標(biāo)變量為連續(xù)變量):使用最小方差作為分裂規(guī)則。只能生成二叉樹(shù)。
缺點(diǎn)補(bǔ)充幾點(diǎn),不是很穩(wěn)點(diǎn),數(shù)據(jù)變化一點(diǎn)武花,你的樹(shù)就會(huì)發(fā)生變化;沒(méi)有考慮變量之間相關(guān)性跃须,每次篩選都只考慮一個(gè)變量(因此不需要?dú)w一化)菇民;只能線性分割數(shù)據(jù)玛荞;貪婪算法(可能找不到最好的樹(shù))。優(yōu)點(diǎn)也補(bǔ)充三點(diǎn)塞蹭,同時(shí)可以處理分類(lèi)變量和數(shù)值變量(但是可能決策樹(shù)對(duì)連續(xù)變量的劃分并不合理,所以可以提前先離散化)钧舌;可以處理多輸出問(wèn)題洼冻;另外決策樹(shù)不需要做變量篩選叔营,它會(huì)自動(dòng)篩選;適合處理高維度數(shù)據(jù)蟹但。
三種方法對(duì)比:
ID3的缺點(diǎn),傾向于選擇水平數(shù)量較多的變量华糖,可能導(dǎo)致訓(xùn)練得到一個(gè)龐大且深度淺的樹(shù);另外輸入變量必須是分類(lèi)變量(連續(xù)變量必須離散化)诵竭;最后無(wú)法處理空值兼搏。
C4.5選擇了信息增益率替代信息增益。
CART以基尼系數(shù)替代熵向族;最小化不純度而不是最大化信息增益。
剪樹(shù):
如何停止分裂
下面這六種情況都會(huì)停止分裂。
其中第一種其實(shí)屬于樹(shù)的完全長(zhǎng)成氧苍,但這會(huì)出現(xiàn)過(guò)擬合問(wèn)題紊撕,所有之前很流行一種抑制這種情況的方法络凿,叫樹(shù)的剪枝
樹(shù)的剪枝分為預(yù)剪枝和后剪枝,預(yù)剪枝膀息,及早的停止樹(shù)增長(zhǎng)控制樹(shù)的規(guī)模裁替,方法可以參考如下6點(diǎn)停止分類(lèi)的條件。后剪枝在已生成過(guò)擬合決策樹(shù)上進(jìn)行剪枝,刪除沒(méi)有意義的組更振,可以得到簡(jiǎn)化版的剪枝決策樹(shù)宣肚,包括REP(設(shè)定一定的誤分類(lèi)率啥么,減掉對(duì)誤分類(lèi)率上升不超過(guò)閾值的多余樹(shù))氯迂、PEP僻孝,還有一種CCP,即給分裂準(zhǔn)則—基尼系數(shù)加上懲罰項(xiàng)挖垛,此時(shí)樹(shù)的層數(shù)越深凭舶,基尼系數(shù)的懲罰項(xiàng)會(huì)越大闽铐。
隨機(jī)森林
盡管有剪枝等等方法,一棵樹(shù)的生成肯定還是不如多棵樹(shù),因此就有了隨機(jī)森林,解決決策樹(shù)泛化能力弱的缺點(diǎn)料扰。(可以理解成三個(gè)臭皮匠頂過(guò)諸葛亮)
而同一批數(shù)據(jù),用同樣的算法只能產(chǎn)生一棵樹(shù)亩歹,這時(shí)Bagging策略可以幫助我們產(chǎn)生不同的數(shù)據(jù)集。Bagging策略來(lái)源于bootstrap aggregation:從樣本集(假設(shè)樣本集N個(gè)數(shù)據(jù)點(diǎn))中重采樣選出Nb個(gè)樣本(有放回的采樣,樣本數(shù)據(jù)點(diǎn)個(gè)數(shù)仍然不變?yōu)镹)蝠引,在所有樣本上,對(duì)這n個(gè)樣本建立分類(lèi)器(ID3\C4.5\CART\SVM\LOGISTIC),重復(fù)以上兩步m次欠啤,獲得m個(gè)分類(lèi)器屋灌,最后根據(jù)這m個(gè)分類(lèi)器的投票結(jié)果,決定數(shù)據(jù)屬于哪一類(lèi)共郭。
隨機(jī)森林在bagging的基礎(chǔ)上更進(jìn)一步:
樣本的隨機(jī):從樣本集中用Bootstrap隨機(jī)選取n個(gè)樣本
特征的隨機(jī):從所有屬性中隨機(jī)選取K個(gè)屬性,選擇最佳分割屬性作為節(jié)點(diǎn)建立CART決策樹(shù)(泛化的理解除嘹,這里面也可以是其他類(lèi)型的分類(lèi)器写半,比如SVM尉咕、Logistics)
重復(fù)以上兩步m次,即建立了m棵CART決策樹(shù)
這m個(gè)CART形成隨機(jī)森林年缎,通過(guò)投票表決結(jié)果悔捶,決定數(shù)據(jù)屬于哪一類(lèi)(投票機(jī)制有一票否決制、少數(shù)服從多數(shù)单芜、加權(quán)多數(shù))
關(guān)于調(diào)參:1.如何選取K,可以考慮有N個(gè)屬性洲鸠,取K=根號(hào)N
2.最大深度(不超過(guò)8層)
3.棵數(shù)
4.最小分裂樣本樹(shù)
5.類(lèi)別比例
決策樹(shù)的重要參數(shù)都是防止過(guò)擬合的. 有2個(gè)參數(shù)是關(guān)鍵馋缅,min_samples_leaf 這個(gè)sklearn的默認(rèn)值是1绢淀,經(jīng)驗(yàn)上必須大于100萤悴,如果一個(gè)節(jié)點(diǎn)都沒(méi)有100個(gè)樣本支持他的決策更啄,一般都被認(rèn)為是過(guò)擬合稚疹;max_depth 這個(gè)參數(shù)控制樹(shù)的規(guī)模祭务。決策樹(shù)是一個(gè)非常直觀的機(jī)器學(xué)習(xí)方法。一般我們都會(huì)把它的決策樹(shù)結(jié)構(gòu)打印出來(lái)觀察义锥,如果深度太深對(duì)于我們的理解是有難度的。