R語(yǔ)言-決策樹算法

-.z決策樹算法決策樹定義首先，我們來(lái)談?wù)勈裁词菦Q策樹。我們還是以鳶尾花為例子來(lái)說(shuō)明這個(gè)問(wèn)題。觀察上圖，我們判決鳶尾花的思考過(guò)程可以這么來(lái)描述：花瓣的長(zhǎng)度小于2.4cm的是setosa(圖中綠色的分類)，長(zhǎng)度大于1cm的呢?我們通過(guò)寬度來(lái)判別，寬度小于1.8cm的是versicolor(圖中紅色的分類)，其余的就是virginica(圖中黑色的分類)我們用圖形來(lái)形象的展示我們的思考過(guò)程便得到了這么一棵決策樹：這種從數(shù)據(jù)產(chǎn)生決策樹的機(jī)器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí),通俗點(diǎn)說(shuō)就是決策樹，說(shuō)白了，這是一種依托于分類、訓(xùn)練上的預(yù)測(cè)樹，根據(jù)預(yù)測(cè)、歸類未來(lái)。前面我們介紹的k-近鄰算法也可以完成很多分類任務(wù)，但是他的缺點(diǎn)就是含義不清，說(shuō)不清數(shù)據(jù)的在邏輯，而決策樹則很好地解決了這個(gè)問(wèn)題，他十分好理解。從存儲(chǔ)的角度來(lái)說(shuō)，決策樹解放了存儲(chǔ)訓(xùn)練集的空間，畢竟與一棵樹的存儲(chǔ)空間相比，訓(xùn)練集的存儲(chǔ)需求空間太大了。決策樹的構(gòu)建一、KD3的想法與實(shí)現(xiàn)下面我們就要來(lái)解決一個(gè)很重要的問(wèn)題：如何構(gòu)造一棵決策樹?這涉及十分有趣的細(xì)節(jié)。先說(shuō)說(shuō)構(gòu)造的根本步驟，一般來(lái)說(shuō)，決策樹的構(gòu)造主要由兩個(gè)階段組成:第一階段，生成樹階段。選取局部受訓(xùn)數(shù)據(jù)建立決策樹，決策樹是按廣度優(yōu)先建立直到每個(gè)葉節(jié)點(diǎn)包括一樣的類標(biāo)記為止。第二階段，決策樹修剪階段。用剩余數(shù)據(jù)檢驗(yàn)決策樹，如果所建立的決策樹不能正確答復(fù)所研究的問(wèn)題，我們要對(duì)決策樹進(jìn)展修剪直到建立一棵正確的決策樹。這樣在決策樹每個(gè)部節(jié)點(diǎn)處進(jìn)展屬性值的比較，在葉節(jié)點(diǎn)得到結(jié)論。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條規(guī)則，整棵決策樹就對(duì)應(yīng)著一組表達(dá)式規(guī)則。問(wèn)題：我們?nèi)绾未_定起決定作用的劃分變量。我還是用鳶尾花的例子來(lái)說(shuō)這個(gè)問(wèn)題思考的必要性。使用不同的思考方式，我們不難發(fā)現(xiàn)下面的決策樹也是可以把鳶尾花分成3類的。為了找到?jīng)Q定性特征，劃分出最正確結(jié)果，我們必須認(rèn)真評(píng)估每個(gè)特征。通常劃分的方法為信息增益和基尼不純指數(shù)，對(duì)應(yīng)的算法為C4.5和CART。關(guān)于信息增益和熵的定義煩請(qǐng)參閱百度百科，這里不再贅述。直接給出計(jì)算熵與信息增益的R代碼：1、計(jì)算給定數(shù)據(jù)集的熵calcent<-function(data){nument<-length(data[,1])key<-rep("a",nument)for(iin1:nument)key[i]<-data[i,length(data)]ent<-0prob<-table(key)/numentfor(iin1:length(prob))ent=ent-prob[i]*log(prob[i],2)return(ent)}我們這里把最后一列作為衡量熵的指標(biāo)，例如數(shù)據(jù)集mudat(自己定義的)>mudat*yz111y211y310n401n501n計(jì)算熵>calcent(mudat)10.9709506熵越高，混合的數(shù)據(jù)也越多。得到熵之后，我們就可以按照獲取最大信息增益的方法劃分?jǐn)?shù)據(jù)集2、按照給定特征劃分?jǐn)?shù)據(jù)集為了簡(jiǎn)單起見(jiàn)，我們僅考慮標(biāo)稱數(shù)據(jù)(對(duì)于非標(biāo)稱數(shù)據(jù)，我們采用劃分的方法把它們化成標(biāo)稱的即可)。R代碼：split<-function(data,variable,value){result<-data.frame()for(iin1:length(data[,1])){if(data[i,variable]==value)result<-rbind(result,data[i,-variable])}return(result)}這里要求輸入的變量為：數(shù)據(jù)集，劃分特征變量的序號(hào)，劃分值。我們以前面定義的mudat為例，以“*〞作為劃分變量，劃分得到的數(shù)據(jù)集為：>split(mudat,1,1)yz11y21y30n>split(mudat,1,0)yz41n51n3、選擇最正確劃分(基于熵增益)choose<-function(data){numvariable<-length(data[1,])-1baseent<-calcent(data)bestinfogain<-0bestvariable<-0infogain<-0featlist<-c()uniquevals<-c()for(iin1:numvariable){featlist<-data[,i]uniquevals<-unique(featlist)newent<-0for(jin1:length(uniquevals)){subset<-split(data,i,uniquevals[j])prob<-length(subset[,1])/length(data[,1])newent<-newent+prob*calcent(subset)}infogain<-baseent-newentif(infogain>bestinfogain){bestinfogain<-infogainbestvariable<-i}}return(bestvariable)}函數(shù)choose包含三個(gè)局部，第一局部：求出一個(gè)分類的各種標(biāo)簽;第二局部：計(jì)算每一次劃分的信息熵;第三局部：計(jì)算最好的信息增益，并返回分類編號(hào)。我們以上面的簡(jiǎn)易例子mudat為例，計(jì)算劃分，有：>choose(mudat)[1]1也就是告訴我們，將第一個(gè)變量值為1的分一類，變量值為0的分為另一類，得到的劃分是最好的。4、遞歸構(gòu)建決策樹我們以脊椎動(dòng)物數(shù)據(jù)集為例，這個(gè)例子來(lái)自?數(shù)據(jù)挖掘?qū)д?，具體數(shù)據(jù)集已上傳至百度云盤(點(diǎn)擊可下載)我們先忽略建樹細(xì)節(jié)，由于數(shù)據(jù)變量并不大，我們手動(dòng)建一棵樹先。>animals<-read.csv("D:/R/data/animals.csv")>choose(animals)[1]1這里變量1代表names，當(dāng)然是一個(gè)很好的分類，但是意義就不大了，我們暫時(shí)的解決方案是刪掉名字這一欄，繼續(xù)做有：>choose(animals)[1]4我們繼續(xù)重復(fù)這個(gè)步驟，直至choose分類為0或者沒(méi)方法分類(比方sometimesliveinwater的動(dòng)物)為止。得到最終分類樹。給出分類邏輯圖(遵循多數(shù)投票法)：至于最后的建樹畫圖涉及R的繪圖包ggplot，這里不再給出細(xì)節(jié)。下面我們使用著名數(shù)據(jù)集——隱形眼鏡數(shù)據(jù)集，利用上述的想法實(shí)現(xiàn)一下決策樹預(yù)測(cè)隱形眼鏡類型。這個(gè)例子來(lái)自?機(jī)器學(xué)習(xí)實(shí)戰(zhàn)?，具體數(shù)據(jù)集已上傳至百度云盤(點(diǎn)擊可下載)。下面是一個(gè)十分簡(jiǎn)陋的建樹程序(用R實(shí)現(xiàn)的)，為了表達(dá)方便，我們給隱形眼鏡數(shù)據(jù)名稱加上標(biāo)稱：age,prescript,astigmatic,tearrate.建樹的R程序簡(jiǎn)要給出如下：bulidtree<-function(data){if(choose(data)==0)print("finish")else{print(choose(data))level<-unique(data[,choose(data)])if(level==1)print("finish")elsefor(iin1:length(level)){data1<-split(data,choose(data),level[i])if(length(data1)==1)print("finish")elsebulidtree(data1)}}}運(yùn)行結(jié)果：>bulidtree(lenses)[1]4[1]"finish"[1]3[1]1[1]"finish"[1]"finish"[1]1[1]"finish"[1]"finish"[1]2[1]"finish"[1]1[1]"finish"[1]"finish"[1]"finish"這棵樹的解讀有些麻煩，因?yàn)槲覀儧](méi)有打印標(biāo)簽，(程序的簡(jiǎn)陋總會(huì)帶來(lái)這樣，那樣的問(wèn)題，歡迎幫助完善)，人工解讀一下：首先利用4(tearrate)的特征reduce，normal將數(shù)據(jù)集劃分為nolenses(至此完全分類)，normal的情況下，根據(jù)3(astigmatic)的特征no，yes分?jǐn)?shù)據(jù)集(劃分順序與因子在數(shù)據(jù)表的出現(xiàn)順序有關(guān))，no這條分支上選擇1(age)的特征pre，young，presbyopic劃分，前兩個(gè)得到結(jié)果soft，最后一個(gè)利用剩下的一個(gè)特征劃分完結(jié)(這里，由于split函數(shù)每次調(diào)用時(shí)，都刪掉了一個(gè)特征，所以這里的1是實(shí)際第二個(gè)變量，這個(gè)在刪除變量是靠前的情形時(shí)要注意)，yes這條分支使用第2個(gè)變量prescript作為特征劃分myope劃分完結(jié)，hyper利用age進(jìn)一步劃分，得到最終分類。畫圖說(shuō)明邏輯：這里并沒(méi)有進(jìn)展剪枝，可能出現(xiàn)過(guò)擬合情形，我們暫不考慮剪枝的問(wèn)題，下面的問(wèn)題我想是更加迫切需要解決的：在選擇根節(jié)點(diǎn)和各部節(jié)點(diǎn)中的分支屬性時(shí)，采用信息增益作為評(píng)價(jià)標(biāo)準(zhǔn)。信息增益的缺點(diǎn)是傾向于選擇取值較多的屬性，在有些情況下這類屬性可能不會(huì)提供太多有價(jià)值的信息。則如何處理這些問(wèn)題，C4.5算法不失為一個(gè)較好的解決方案。二、C4.5算法C4.5算法描述：(1)創(chuàng)立根節(jié)點(diǎn)N;(2)IFT都屬于同一類C，則返回N為葉節(jié)點(diǎn)，標(biāo)記為類C;(3)IFT_attributelist為空或T中所剩的樣本數(shù)少于*給定值則返回N為葉節(jié)點(diǎn)，標(biāo)記為T中出現(xiàn)最多的類;(4)FOReachT_attributelist中的屬性計(jì)算信息增益率informationgainratio;(5)N的測(cè)試屬性test_attribute=T_attributelist中具有最高信息增益率的屬性;(6)IF測(cè)試屬性為連續(xù)型則找到該屬性的分割閥值;(7)FOReach由節(jié)點(diǎn)N長(zhǎng)出的新葉節(jié)點(diǎn){IF該葉節(jié)點(diǎn)對(duì)應(yīng)的樣本子集T’為空則分裂該葉節(jié)點(diǎn)生成一個(gè)新葉節(jié)點(diǎn)，將其標(biāo)記為T中出現(xiàn)最多的類;ELSE在該葉節(jié)點(diǎn)上執(zhí)行C4.5formtree(T’,T’_attributelist),對(duì)它繼續(xù)分裂;}(8)計(jì)算每個(gè)節(jié)點(diǎn)的分類錯(cuò)誤，進(jìn)展樹剪枝。以鳶尾花數(shù)據(jù)為例子，使用C4.5算法得到的分類樹見(jiàn)以下圖：預(yù)測(cè)結(jié)果：觀察\預(yù)測(cè)setosaversicolorvirginicasetosa5000versicolor0491virginica0248下面我們使用上面提到的隱形眼鏡數(shù)據(jù)集，利用C4.5實(shí)現(xiàn)一下決策樹預(yù)測(cè)隱形眼鏡類型。得到結(jié)果：hardnolensessofthard310nolenses0141soft005看起來(lái)還不錯(cuò)，不是嗎?(注：圖片與預(yù)測(cè)表輸出結(jié)果是已經(jīng)經(jīng)過(guò)剪枝的，所以可能和我們之前程序算出的有些不同)這里我們?cè)俅螌?shí)現(xiàn)一下脊椎動(dòng)物數(shù)據(jù)集的例子(使用C4.5)，得到的分類邏輯圖(R的直接輸出結(jié)果)：Give.Birth=no|Live.in.Water=no||Can.Fly=no:reptiles(4.0/1.0)||Can.Fly=yes:birds(3.0)|Live.in.Water=sometimes:amphibians(4.0/2.0)|Live.in.Water=yes:fishes(2.0)Give.Birth=yes:mammals(7.0/1.0)這個(gè)分類與我們之前使用ID3分類得到的結(jié)果有所不同(搜索效率高了一些，準(zhǔn)確率相當(dāng))，使用信息增益傾向于多分類的貪心算法導(dǎo)致的缺乏在這里顯示的淋漓盡致，更可以看出C4.5比ID3改進(jìn)的地方絕不止能處理連續(xù)變量這一條。三、CART算法CART算法描述(1)創(chuàng)立根節(jié)點(diǎn)N;(2)為N分配類別;(3)IFT都屬于同一類別ORT中只剩一個(gè)樣本則返回N為葉節(jié)點(diǎn)，為其分配類別;(4)FOReachT_attributelist中的屬性執(zhí)行該屬性上的一個(gè)劃分，計(jì)算此次劃分的GINI系數(shù);(5)N的測(cè)試屬性test_attribute=T_attributelist中具有最小GINI系數(shù)的屬性;(6)劃分T得T1、T2兩個(gè)子集;(7)調(diào)用cartformtree(T1);(8)調(diào)用cartformtree(T2);以鳶尾花數(shù)據(jù)集為例，使用cart算法，得到?jīng)Q策樹：要實(shí)現(xiàn)C4.5算法，R提供了一個(gè)程序包RWeka，J48函數(shù)可以實(shí)現(xiàn)決策樹的構(gòu)建，至于cart算法，R中的tree包提供函數(shù)tree來(lái)實(shí)現(xiàn)決策樹的構(gòu)建。下面我們來(lái)簡(jiǎn)要介紹他們：J48(formula,data,subset,na.action,control=Weka_control(),options=NULL)tree(formula,data,weights,subset,na.action=na.pass,control=tree.control(nobs,...),method="recursive.partition",split=c("deviance","gini"),model=FALSE,*=FALSE,y=TRUE,wts=TRUE,...)split為劃分指標(biāo)，分為deviance(偏差)和〞gini〞(基尼)control涉及樹剪枝的各種兇殘細(xì)節(jié)，有興趣的可以通過(guò)閱讀幫助文檔解決。而且剪枝是一個(gè)十分復(fù)雜的過(guò)程，剪枝也是視需求而定的，C4.5是事后剪枝，id3也就是我們?cè)噲D實(shí)現(xiàn)的建樹，也可以去手動(dòng)剪枝。四、R置命令實(shí)現(xiàn)我們之前的C4.5的建樹R代碼如下：鳶尾花一例：library(RWeka)library(party)oldpar=par(mar=c(3,3,1.5,1),mgp=c(1.5,0.5,0),ce*=0.3)data(iris)m1<-J48(Species~Petal.Width+Petal.Length,data=iris)m1table(iris$Species,predict(m1))write_to_dot(m1)if(require("party",quietly=TRUE))plot(m1)隱形眼鏡一例：lenses<-read.csv("D:/R/data/lenses.csv",head=FALS