R語言-決策樹算法

-.z決策樹算法決策樹定義首先，我們來談談什么是決策樹。我們還是以鳶尾花為例子來說明這個問題。觀察上圖，我們判決鳶尾花的思考過程可以這么來描述：花瓣的長度小于2.4cm的是setosa(圖中綠色的分類)，長度大于1cm的呢?我們通過寬度來判別，寬度小于1.8cm的是versicolor(圖中紅色的分類)，其余的就是virginica(圖中黑色的分類)我們用圖形來形象的展示我們的思考過程便得到了這么一棵決策樹：這種從數據產生決策樹的機器學習技術叫做決策樹學習,通俗點說就是決策樹，說白了，這是一種依托于分類、訓練上的預測樹，根據預測、歸類未來。前面我們介紹的k-近鄰算法也可以完成很多分類任務，但是他的缺點就是含義不清，說不清數據的在邏輯，而決策樹則很好地解決了這個問題，他十分好理解。從存儲的角度來說，決策樹解放了存儲訓練集的空間，畢竟與一棵樹的存儲空間相比，訓練集的存儲需求空間太大了。決策樹的構建一、KD3的想法與實現下面我們就要來解決一個很重要的問題：如何構造一棵決策樹?這涉及十分有趣的細節(jié)。先說說構造的根本步驟，一般來說，決策樹的構造主要由兩個階段組成:第一階段，生成樹階段。選取局部受訓數據建立決策樹，決策樹是按廣度優(yōu)先建立直到每個葉節(jié)點包括一樣的類標記為止。第二階段，決策樹修剪階段。用剩余數據檢驗決策樹，如果所建立的決策樹不能正確答復所研究的問題，我們要對決策樹進展修剪直到建立一棵正確的決策樹。這樣在決策樹每個部節(jié)點處進展屬性值的比較，在葉節(jié)點得到結論。從根節(jié)點到葉節(jié)點的一條路徑就對應著一條規(guī)則，整棵決策樹就對應著一組表達式規(guī)則。問題：我們如何確定起決定作用的劃分變量。我還是用鳶尾花的例子來說這個問題思考的必要性。使用不同的思考方式，我們不難發(fā)現下面的決策樹也是可以把鳶尾花分成3類的。為了找到決定性特征，劃分出最正確結果，我們必須認真評估每個特征。通常劃分的方法為信息增益和基尼不純指數，對應的算法為C4.5和CART。關于信息增益和熵的定義煩請參閱百度百科，這里不再贅述。直接給出計算熵與信息增益的R代碼：1、計算給定數據集的熵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)}我們這里把最后一列作為衡量熵的指標，例如數據集mudat(自己定義的)>mudat*yz111y211y310n401n501n計算熵>calcent(mudat)10.9709506熵越高，混合的數據也越多。得到熵之后，我們就可以按照獲取最大信息增益的方法劃分數據集2、按照給定特征劃分數據集為了簡單起見，我們僅考慮標稱數據(對于非標稱數據，我們采用劃分的方法把它們化成標稱的即可)。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)}這里要求輸入的變量為：數據集，劃分特征變量的序號，劃分值。我們以前面定義的mudat為例，以“*〞作為劃分變量，劃分得到的數據集為：>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)}函數choose包含三個局部，第一局部：求出一個分類的各種標簽;第二局部：計算每一次劃分的信息熵;第三局部：計算最好的信息增益，并返回分類編號。我們以上面的簡易例子mudat為例，計算劃分，有：>choose(mudat)[1]1也就是告訴我們，將第一個變量值為1的分一類，變量值為0的分為另一類，得到的劃分是最好的。4、遞歸構建決策樹我們以脊椎動物數據集為例，這個例子來自?數據挖掘導論?，具體數據集已上傳至百度云盤(點擊可下載)我們先忽略建樹細節(jié)，由于數據變量并不大，我們手動建一棵樹先。>animals<-read.csv("D:/R/data/animals.csv")>choose(animals)[1]1這里變量1代表names，當然是一個很好的分類，但是意義就不大了，我們暫時的解決方案是刪掉名字這一欄，繼續(xù)做有：>choose(animals)[1]4我們繼續(xù)重復這個步驟，直至choose分類為0或者沒方法分類(比方sometimesliveinwater的動物)為止。得到最終分類樹。給出分類邏輯圖(遵循多數投票法)：至于最后的建樹畫圖涉及R的繪圖包ggplot，這里不再給出細節(jié)。下面我們使用著名數據集——隱形眼鏡數據集，利用上述的想法實現一下決策樹預測隱形眼鏡類型。這個例子來自?機器學習實戰(zhàn)?，具體數據集已上傳至百度云盤(點擊可下載)。下面是一個十分簡陋的建樹程序(用R實現的)，為了表達方便，我們給隱形眼鏡數據名稱加上標稱：age,prescript,astigmatic,tearrate.建樹的R程序簡要給出如下：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)}}}運行結果：>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"這棵樹的解讀有些麻煩，因為我們沒有打印標簽，(程序的簡陋總會帶來這樣，那樣的問題，歡迎幫助完善)，人工解讀一下：首先利用4(tearrate)的特征reduce，normal將數據集劃分為nolenses(至此完全分類)，normal的情況下，根據3(astigmatic)的特征no，yes分數據集(劃分順序與因子在數據表的出現順序有關)，no這條分支上選擇1(age)的特征pre，young，presbyopic劃分，前兩個得到結果soft，最后一個利用剩下的一個特征劃分完結(這里，由于split函數每次調用時，都刪掉了一個特征，所以這里的1是實際第二個變量，這個在刪除變量是靠前的情形時要注意)，yes這條分支使用第2個變量prescript作為特征劃分myope劃分完結，hyper利用age進一步劃分，得到最終分類。畫圖說明邏輯：這里并沒有進展剪枝，可能出現過擬合情形，我們暫不考慮剪枝的問題，下面的問題我想是更加迫切需要解決的：在選擇根節(jié)點和各部節(jié)點中的分支屬性時，采用信息增益作為評價標準。信息增益的缺點是傾向于選擇取值較多的屬性，在有些情況下這類屬性可能不會提供太多有價值的信息。則如何處理這些問題，C4.5算法不失為一個較好的解決方案。二、C4.5算法C4.5算法描述：(1)創(chuàng)立根節(jié)點N;(2)IFT都屬于同一類C，則返回N為葉節(jié)點，標記為類C;(3)IFT_attributelist為空或T中所剩的樣本數少于*給定值則返回N為葉節(jié)點，標記為T中出現最多的類;(4)FOReachT_attributelist中的屬性計算信息增益率informationgainratio;(5)N的測試屬性test_attribute=T_attributelist中具有最高信息增益率的屬性;(6)IF測試屬性為連續(xù)型則找到該屬性的分割閥值;(7)FOReach由節(jié)點N長出的新葉節(jié)點{IF該葉節(jié)點對應的樣本子集T’為空則分裂該葉節(jié)點生成一個新葉節(jié)點，將其標記為T中出現最多的類;ELSE在該葉節(jié)點上執(zhí)行C4.5formtree(T’,T’_attributelist),對它繼續(xù)分裂;}(8)計算每個節(jié)點的分類錯誤，進展樹剪枝。以鳶尾花數據為例子，使用C4.5算法得到的分類樹見以下圖：預測結果：觀察\預測setosaversicolorvirginicasetosa5000versicolor0491virginica0248下面我們使用上面提到的隱形眼鏡數據集，利用C4.5實現一下決策樹預測隱形眼鏡類型。得到結果：hardnolensessofthard310nolenses0141soft005看起來還不錯，不是嗎?(注：圖片與預測表輸出結果是已經經過剪枝的，所以可能和我們之前程序算出的有些不同)這里我們再次實現一下脊椎動物數據集的例子(使用C4.5)，得到的分類邏輯圖(R的直接輸出結果)：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)這個分類與我們之前使用ID3分類得到的結果有所不同(搜索效率高了一些，準確率相當)，使用信息增益傾向于多分類的貪心算法導致的缺乏在這里顯示的淋漓盡致，更可以看出C4.5比ID3改進的地方絕不止能處理連續(xù)變量這一條。三、CART算法CART算法描述(1)創(chuàng)立根節(jié)點N;(2)為N分配類別;(3)IFT都屬于同一類別ORT中只剩一個樣本則返回N為葉節(jié)點，為其分配類別;(4)FOReachT_attributelist中的屬性執(zhí)行該屬性上的一個劃分，計算此次劃分的GINI系數;(5)N的測試屬性test_attribute=T_attributelist中具有最小GINI系數的屬性;(6)劃分T得T1、T2兩個子集;(7)調用cartformtree(T1);(8)調用cartformtree(T2);以鳶尾花數據集為例，使用cart算法，得到決策樹：要實現C4.5算法，R提供了一個程序包RWeka，J48函數可以實現決策樹的構建，至于cart算法，R中的tree包提供函數tree來實現決策樹的構建。下面我們來簡要介紹他們：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為劃分指標，分為deviance(偏差)和〞gini〞(基尼)control涉及樹剪枝的各種兇殘細節(jié)，有興趣的可以通過閱讀幫助文檔解決。而且剪枝是一個十分復雜的過程，剪枝也是視需求而定的，C4.5是事后剪枝，id3也就是我們試圖實現的建樹，也可以去手動剪枝。四、R置命令實現我們之前的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