99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀數(shù)據(jù)挖掘之決策樹分類
數(shù)據(jù)挖掘之決策樹分類
2016-05-19
收藏

數(shù)據(jù)挖掘之決策樹分類

1. 理論知識(shí)

決策樹分類算法的一般流程如下：一開始，所有的實(shí)例均位于根節(jié)點(diǎn)，所有參數(shù)的取值均離散化；根據(jù)啟發(fā)規(guī)則選擇一個(gè)參數(shù)，根據(jù)參數(shù)取值的不同對(duì)實(shí)例集進(jìn)行分割；對(duì)分割后得到的節(jié)點(diǎn)進(jìn)行同樣的啟發(fā)式參數(shù)選擇分割過程，如此往復(fù)，直到(a)分割得到的實(shí)例集合屬于同一類；(b)參數(shù)用完，以子集中絕大多數(shù)的實(shí)例類別作為該葉節(jié)點(diǎn)的類別。

核心問題：參數(shù)選擇規(guī)則
   在每一個(gè)節(jié)點(diǎn)進(jìn)行參數(shù)選擇時(shí)，由于有眾多的選項(xiàng)，需要一個(gè)選擇規(guī)則?；镜脑瓌t是使最后構(gòu)造出的決策樹規(guī)模最小。基于這個(gè)基本原則，我們啟發(fā)式地定義規(guī)則為使分割后得到的子節(jié)點(diǎn)純度最大。于是參數(shù)選擇規(guī)則問題就轉(zhuǎn)化為了純度定義的問題。
   我們利用熵(Entropy)的概念去描述“不純度”，熵值越大，說明這個(gè)節(jié)點(diǎn)的純度越低：當(dāng)節(jié)點(diǎn)的類別均勻分布時(shí)，熵值為1；當(dāng)只包含一類時(shí)，熵值為0.熵的計(jì)算公式如下圖，以2為底的概率對(duì)數(shù)與概率乘積之和的相反數(shù)。

   基于熵的概念，我們可以得到參數(shù)選擇的第一個(gè)規(guī)則：信息增益(Info Gain).信息增益的定義是分裂前的節(jié)點(diǎn)熵減去分裂后子節(jié)點(diǎn)熵的加權(quán)和，即不純度的減少量，也就是純度的增加量。參數(shù)選擇的規(guī)則是：選擇使信息增益最大的參數(shù)分割該節(jié)點(diǎn)。信息增益計(jì)算的算例如下圖。

   信息增益存在的問題時(shí):總是傾向于選擇包含多取值的參數(shù)，因?yàn)閰?shù)的取值越多，其分割后的子節(jié)點(diǎn)純度可能越高。為了避免這個(gè)問題，我們引入了增益比例(Gain Ratio)的選擇指標(biāo)，其定義如下圖所示。

   增益比例存在的問題是：傾向于選擇分割不均勻的分裂方法，舉例而言，即一個(gè)拆分若分為兩個(gè)節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)特別多的實(shí)例，一個(gè)節(jié)點(diǎn)特別少的實(shí)例，那么這種拆分有利于被選擇。

   為了克服信息增益和增益比例各自的問題，標(biāo)準(zhǔn)的解決方案如下：首先利用信息增益概念，計(jì)算每一個(gè)參數(shù)分割的信息增益，獲得平均信息增益；選出信息增益大于平均值的所有參數(shù)集合，對(duì)該集合計(jì)算增益比例，選擇其中增益比例最大的參數(shù)進(jìn)行決策樹分裂。 

   上面介紹的是基于熵概念的參數(shù)選擇規(guī)則，另一種流行的規(guī)則稱為基尼指數(shù)（Gini Index），其定義如下圖?；嵯禂?shù)在節(jié)點(diǎn)類別分布均勻時(shí)取最大值1-1/n，在只包含一個(gè)類別時(shí)取最小值0. 所以與熵類似，也是一個(gè)描述不純度的指標(biāo)。

   基于基尼系數(shù)的規(guī)則是：選擇不純度減少量(Reduction in impurity)最大的參數(shù)。不純度減少量是分割前的Gini index減去分割后的Gini index。基尼系數(shù)的特點(diǎn)與信息增益的特點(diǎn)類似。

過度擬合問題(Overfitting)

  過度擬合問題是對(duì)訓(xùn)練數(shù)據(jù)完全擬合的決策樹對(duì)新數(shù)據(jù)的預(yù)測(cè)能力較低。為了解決這個(gè)問題，有兩種解決方法。第一種方法是前剪枝(prepruning)，即事先設(shè)定一個(gè)分裂閾值，若分裂得到的信息增益不大于這個(gè)閾值，則停止分裂。第二種方法是后剪枝（postpruning），首先生成與訓(xùn)練集完全擬合的決策樹，然后自下而上地逐層剪枝，如果一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)被刪除后，決策樹的準(zhǔn)確度沒有降低，那么就將該節(jié)點(diǎn)設(shè)置為葉節(jié)點(diǎn)（基于的原則是Occam剪刀：具有相似效果的兩個(gè)模型選擇較簡(jiǎn)單的那個(gè)）。

Scalable決策樹分類算法

   這里介紹兩個(gè)算法，一個(gè)是RainForest，其主要的貢獻(xiàn)是引入了一個(gè)稱為AVC的數(shù)據(jù)結(jié)構(gòu)，其示意圖如下。主要的作用是加速參數(shù)選擇過程的計(jì)算。

   另一個(gè)算法稱為BOAT，其采用了稱為bootstrap的統(tǒng)計(jì)技術(shù)對(duì)數(shù)據(jù)集進(jìn)行分割，在分割的子數(shù)據(jù)集上分別構(gòu)造決策樹，再基于這些決策樹構(gòu)造一個(gè)新的決策樹，文章證明這棵新樹與基于全局?jǐn)?shù)據(jù)集構(gòu)造的決策樹非常相近。這種方法的主要優(yōu)勢(shì)在于支持增量更新。

2. R語言實(shí)現(xiàn)
   本文采用rpart和rpart.plot包進(jìn)行決策樹分類的案例講解。
函數(shù)說明
   rpart包主要有兩個(gè)函數(shù)組成，分別介紹如下：

rpart(formula, data, weight s, subset, na. action = na. rpart, method, model= FALSE, x= FALSE,y= TRUE, parms, control, cost, . . . )

fomula 回歸方程形式: 例如 y~ x 1+ x2+ x3。

data 數(shù)據(jù): 包含前面方程中變量的數(shù)據(jù)框( data frame) 。

na.action 缺失數(shù)據(jù)的處理辦法: 默認(rèn)辦法是刪除因變量缺失的觀測(cè)而保留自變量缺失的觀測(cè)。

method 根據(jù)樹末端的數(shù)據(jù)類型選擇相應(yīng)變量分割方法,本參數(shù)有四種取值: 連續(xù)型>anova; 離散型>class; 計(jì)數(shù)型( 泊松過程)>poisson; 生存分析型>exp。程序會(huì)根據(jù)因變量的類型自動(dòng)選擇方法, 但一般情況下最好還是指明本參數(shù), 以便讓程序清楚做哪一種樹模型。

parms 用來設(shè)置三個(gè)參數(shù):先驗(yàn)概率、損失矩陣、分類純度的度量方法。anova沒有參數(shù)；poisson分割有一個(gè)參數(shù)，先驗(yàn)分布變異系數(shù)的比率，默認(rèn)為1；生存分布的參數(shù)和poisson一致；對(duì)離散型，可以設(shè)置先驗(yàn)分布的分布的概率(prior)，損失矩陣(loss)，分類純度(split）；priors必須為正值且和為1，loss必須對(duì)角為0且非對(duì)角為正數(shù)，split可以是gini（基尼系數(shù)）或者information（信息增益）；

control 控制每個(gè)節(jié)點(diǎn)上的最小樣本量、交叉驗(yàn)證的次數(shù)、復(fù)雜性參量: 即cp: complexity pamemeter, 這個(gè)參數(shù)意味著對(duì)每一步拆分, 模型的擬合優(yōu)度必須提高的程度, 等等。

PS:交叉驗(yàn)證指，比如xval是10折交叉驗(yàn)證：將數(shù)據(jù)集分為10組，進(jìn)行10次擬合，第i次擬合用除了第i組以外的數(shù)據(jù)訓(xùn)練，用第i組進(jìn)行預(yù)測(cè)；目的是減少misclaassification rate。  

prune(tree, cp, . . . )

tree 一個(gè)回歸樹對(duì)象, 常是rpart()的結(jié)果對(duì)象。

cp 復(fù)雜性參量, 指定剪枝采用的閾值。

建模方法概述
   通常分為兩步建立回歸樹，最初生成一顆較大的樹，然后通過統(tǒng)計(jì)估量刪除底部的一些節(jié)點(diǎn)來對(duì)樹進(jìn)行修剪。這個(gè)過程的目的是防止過度擬合。
   使用rpart函數(shù)構(gòu)建樹的過程中，當(dāng)給定條件滿足時(shí)構(gòu)建過程就停止。偏差的減少小于某一個(gè)給定界限值、節(jié)點(diǎn)中的樣本數(shù)量小于某個(gè)給定界限、樹的深度大于一個(gè)給定的界限，上面三個(gè)界限分別由rpart()函數(shù)的三個(gè)參數(shù)(cp、minsplit、maxdepth)確定，默認(rèn)值是0.01、20和30。如果要避免樹的過度擬合問題，就要經(jīng)常檢查這些默認(rèn)值的有效性，這可以通過對(duì)得到的樹采取事后修剪的過程來實(shí)現(xiàn)。
   選擇樹的方法一般有兩種，一種是最小化交叉驗(yàn)證的相對(duì)方差（xerror）。另外一種是在剪枝理論中,比較著名的規(guī)則就是1-SE(1標(biāo)準(zhǔn)差) 規(guī)則, 其意思是: 首先要保證預(yù)測(cè)誤差( 通過交叉驗(yàn)證獲得, 在程序中表示為xerror) 盡量小,但不一定要取最小值, 而是允許它在“最小的誤差”一個(gè)相應(yīng)標(biāo)準(zhǔn)差的范圍內(nèi), 然后在此范圍內(nèi)選取盡量小的復(fù)雜性參量,進(jìn)而以它為依據(jù)進(jìn)行剪枝。這個(gè)規(guī)則體現(xiàn)了兼顧樹的規(guī)模( 復(fù)雜性) 和誤差大小的思想, 因?yàn)橐话阏f來, 隨著拆分的增多, 復(fù)雜性參量會(huì)單調(diào)下降(純度越來越高) , 但是預(yù)測(cè)誤差則會(huì)先降后升, 這樣, 就無法使復(fù)雜性和誤差同時(shí)降到最低,因此允許誤差可以在一個(gè)標(biāo)準(zhǔn)差內(nèi)波動(dòng)。
案例

rpart包自帶數(shù)據(jù)集stagec，包含了146位患了stage c前列腺(prostate)癌的病人。變量介紹如下：

pgtime: 出現(xiàn)癥狀或復(fù)發(fā)時(shí)間，單位年；

pgstat：狀態(tài)變量，1為復(fù)發(fā)，0為刪減；

age：年齡；

eet：是否內(nèi)分泌治療，1為no，2為yes；

g2：g2階段腫瘤細(xì)胞百分比；

grade：腫瘤等級(jí)，farrow體系；

gleason：腫瘤等級(jí)，gleason體系；

ploidy：腫瘤的倍體狀態(tài)。

代碼：
library(rpart);  
## rpart.control對(duì)樹進(jìn)行一些設(shè)置  
## xval是10折交叉驗(yàn)證：將數(shù)據(jù)集分為10組，進(jìn)行10次擬合，第i次擬合用除了第i組以外的數(shù)據(jù)訓(xùn)練，用第i組進(jìn)行預(yù)測(cè)；目的是減少misclaassification rate  
## minsplit是最小分支節(jié)點(diǎn)數(shù)，這里指大于等于20，那么該節(jié)點(diǎn)會(huì)繼續(xù)分劃下去，否則停止  
## cp全稱為complexity parameter，指某個(gè)點(diǎn)的復(fù)雜度，對(duì)每一步拆分,模型的擬合優(yōu)度必須提高的程度  
ct <- rpart.control(xval=10, minsplit=20, cp=0.01)  
## method：樹的末端數(shù)據(jù)類型選擇相應(yīng)的變量分割方法:  
## 連續(xù)性method=“anova”,離散型method=“class”,計(jì)數(shù)型method=“poisson”,生存分析型method=“exp”  
## parms用來設(shè)置三個(gè)參數(shù):先驗(yàn)概率、損失矩陣、分類純度的度量方法（gini和information）
## parms的解釋：For classification splitting, the list can contain any of: the vector of prior probabilities (component prior), the loss matrix (component loss) or the splitting index (component split). The priors must be positive and sum to 1. The loss matrix must have zeros on the diagonal and positive off-diagonal elements. The splitting index can be gini or information. The default priors are proportional to the data counts, the losses default to 1, and the split defaults to gini.
## cost：給每個(gè)變量一個(gè)成本，選擇某個(gè)變量進(jìn)行split時(shí)，split改進(jìn)量/成本作為評(píng)價(jià)標(biāo)準(zhǔn)，默認(rèn)都為1
str(stagec)
progstat <- factor(stagec$pgstat, levels=0:1, labels=c("No", "Prog"))
cfit <- rpart(progstat~age + eet + g2 + grade + gleason + ploidy,
              data=stagec, method="class", control=ct,
              parms=list(split="gini")
              );
print(cfit)
# 繪制決策樹
library(rpart.plot);  
rpart.plot(cfit, branch=1, branch.type=2, type=1, extra=102,  
           shadow.col="gray", box.col="green",  
           border.col="blue", split.col="red",  
           split.cex=1.2, main="Stage C決策樹");  
## rpart包提供了復(fù)雜度損失修剪的修剪方法，printcp會(huì)告訴分裂到每一層，cp是多少，平均相對(duì)誤差是多少  
## 交叉驗(yàn)證的估計(jì)誤差（“xerror”列），以及標(biāo)準(zhǔn)誤差(“xstd”列)，平均相對(duì)誤差=xerror±xstd  
printcp(cfit);  
## 使用1-SE法則選出最優(yōu)cp值:找到xerror最小的行，得到誤差閾值為該行的xerror+xstd
## 找到所有xerror小于這個(gè)閾值的行，取其中最大值的上限為prune的閾值
cfit2 <- prune(cfit, cp=0.03);  
rpart.plot(cfit2, branch=1, branch.type=2, type=1, extra=102,  
           shadow.col="gray", box.col="green",  
           border.col="blue", split.col="red",  
           split.cex=1.2, main="Kyphosis決策樹");  
附：cp表
        CP nsplit rel error  xerror    xstd
1 0.104938      0   1.00000 1.00000 0.10802
2 0.055556      3   0.68519 1.00000 0.10802
3 0.027778      4   0.62963 0.88889 0.10511
4 0.018519      6   0.57407 0.92593 0.10618
5 0.010000      7   0.55556 0.92593 0.10618


數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼，搜微信號(hào)：CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象，之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說明請(qǐng)參見：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }