什么是決策樹(shù)?決策樹(shù)算法思考總結(jié)

一、什么是決策樹(shù)

決策樹(shù)是一類常見(jiàn)的機(jī)器學(xué)習(xí)方法，通過(guò)歷史數(shù)據(jù)得到的樹(shù)結(jié)構(gòu)模型對(duì)新數(shù)據(jù)進(jìn)行分類決策。

決策樹(shù)是一種基于實(shí)例的歸納學(xué)習(xí)方法，它能從給定的無(wú)序的訓(xùn)練樣本中，提煉出樹(shù)形的分類模型。

樹(shù)中的每個(gè)非葉子節(jié)點(diǎn)記錄了使用哪個(gè)特征來(lái)進(jìn)行類別的判斷，每個(gè)葉子節(jié)點(diǎn)則代表了最后判斷的類別。根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)均形成一條分類的路徑規(guī)則。

每次判斷都是對(duì)某個(gè)屬性的測(cè)試，每次判斷都會(huì)縮小考慮的范圍。

一棵決策樹(shù)包含一個(gè)根節(jié)點(diǎn)、若干個(gè)內(nèi)部結(jié)點(diǎn)和若干個(gè)葉節(jié)點(diǎn)；葉節(jié)點(diǎn)對(duì)應(yīng)于決策結(jié)果，其他每個(gè)節(jié)點(diǎn)則對(duì)應(yīng)于一個(gè)屬性測(cè)試；每個(gè)節(jié)點(diǎn)包含的樣本集合根據(jù)屬性測(cè)試的結(jié)果被劃分到子節(jié)點(diǎn)；

根節(jié)點(diǎn)包含樣本全集。從根節(jié)點(diǎn)到每個(gè)葉節(jié)點(diǎn)的路徑對(duì)應(yīng)了一個(gè)判斷測(cè)試序列。

決策樹(shù)的生成是一個(gè)遞歸的過(guò)程，有三種情形不會(huì)再分類：

當(dāng)前節(jié)點(diǎn)包含的樣本全屬于同一類別

當(dāng)前屬性集為空

當(dāng)前節(jié)點(diǎn)的樣本集合為空

對(duì)于第二種情形，其類別設(shè)定為結(jié)點(diǎn)所含樣本最多的類別。對(duì)于第三種情形，將其類別設(shè)定為其父節(jié)點(diǎn)所含樣本最多的類別

二、常見(jiàn)決策樹(shù)分類算法

1、CLS算法：是最原始的決策樹(shù)分類算法，基本流程是，從一棵空數(shù)出發(fā)，不斷的從決策表選取屬性加入數(shù)的生長(zhǎng)過(guò)程中，直到?jīng)Q策樹(shù)可以滿足分類要求為止。CLS算法存在的主要問(wèn)題是在新增屬性選取時(shí)有很大的隨機(jī)性。

2、ID3算法：對(duì)CLS算法的最大改進(jìn)是摒棄了屬性選擇的隨機(jī)性，利用信息熵的下降速度作為屬性選擇的度量。ID3是一種基于信息熵的決策樹(shù)分類學(xué)習(xí)算法，以信息增益和信息熵，作為對(duì)象分類的衡量標(biāo)準(zhǔn)。

ID3算法結(jié)構(gòu)簡(jiǎn)單、學(xué)習(xí)能力強(qiáng)、分類速度快適合大規(guī)模數(shù)據(jù)分類。但同時(shí)由于信息增益的不穩(wěn)定性，容易傾向于眾數(shù)屬性導(dǎo)致過(guò)度擬合，算法抗干擾能力差。

ID3算法缺點(diǎn)：傾向于選擇那些屬性取值比較多的屬性，在實(shí)際的應(yīng)用中往往取值比較多的屬性對(duì)分類沒(méi)有太大價(jià)值、不能對(duì)連續(xù)屬性進(jìn)行處理、對(duì)噪聲數(shù)據(jù)比較敏感、需計(jì)算每一個(gè)屬性的信息增益值、計(jì)算代價(jià)較高。

3、C4.5算法：基于ID3算法的改進(jìn)，主要包括：使用信息增益率替換了信息增益下降度作為屬性選擇的標(biāo)準(zhǔn)；在決策樹(shù)構(gòu)造的同時(shí)進(jìn)行剪枝操作；避免了樹(shù)的過(guò)度擬合情況；可以對(duì)不完整屬性和連續(xù)型數(shù)據(jù)進(jìn)行處理，提升了算法的普適性。

三、決策樹(shù)特征選擇準(zhǔn)則

1 信息增益

“信息熵”是度量樣本集合純度最常用的一種指標(biāo)。假定當(dāng)前樣本集合D中第K類樣本所占的比例為PK，則D的信息熵定義為

值越小，則D的純度越高。

信息增益越大，則意味著使用屬性a來(lái)進(jìn)行劃分所獲得的“純度提升”越大。

ID3決策樹(shù)學(xué)習(xí)算法就是以信息增益為準(zhǔn)則來(lái)選擇劃分屬性的。

2 信息增益率

實(shí)際上信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的屬性有所偏好，為了減少這種偏好可能帶來(lái)的不利影響。使用信息增益率來(lái)選擇最優(yōu)劃分屬性。

C4.5算法常使用信息增益率來(lái)選擇最優(yōu)屬性劃分

3 基尼指數(shù)

CART決策樹(shù)使用“基尼指數(shù)”來(lái)選擇劃分屬性，

數(shù)據(jù)集D的純度可用基尼值來(lái)度量：

Gini(D)反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概率。故其值越小越好。數(shù)據(jù)集D的純度越高。

屬性a的基尼指數(shù)定義為

于是，我們?cè)诤蜻x屬性集合A中，選擇哪個(gè)使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性。

4 剪枝處理

剪枝是決策樹(shù)學(xué)習(xí)算法對(duì)付“過(guò)擬合”的主要手段。剪枝的基本策略有“預(yù)剪枝”和“后剪枝”。

預(yù)剪枝是指在決策樹(shù)生成過(guò)程中，對(duì)每個(gè)結(jié)點(diǎn)在劃分前進(jìn)行估計(jì)，若當(dāng)前節(jié)點(diǎn)的劃分不能帶來(lái)決策樹(shù)泛化能力提升，則停止劃分并將當(dāng)前節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)。

后剪枝則是先從訓(xùn)練集生成一顆完整的決策樹(shù)，然后自底向上地對(duì)非葉節(jié)點(diǎn)進(jìn)行考察，若將該節(jié)點(diǎn)對(duì)應(yīng)的子樹(shù)替換為葉節(jié)點(diǎn)能帶來(lái)決策樹(shù)泛化能力提升，則將該節(jié)點(diǎn)替換為葉節(jié)點(diǎn)。

5 連續(xù)與缺失值

5.1 連續(xù)值處理

將該節(jié)點(diǎn)上的所有樣本按照屬性的取值有小到大排序，在兩個(gè)值之間去平均值，依次將所有平均值作為分割點(diǎn)，分別計(jì)算他們的信息增益率，將值最大的那個(gè)作為最優(yōu)分割點(diǎn)。

5.2 缺失值的處理

處理過(guò)程如下

四、sklearn參數(shù)

1criterion：gini或者entropy,前者是基尼系數(shù)，后者是信息熵。兩種算法差異不大對(duì)準(zhǔn)確率無(wú)影響，信息墑運(yùn)算效率低一點(diǎn)，

2 因?yàn)樗袑?duì)數(shù)運(yùn)算.一般說(shuō)使用默認(rèn)的基尼系數(shù)”gini”就可以了，即CART算法。除非你更喜歡類似ID3,C4.5的最優(yōu)特征選擇方法。

3 4splitter：bestorrandom前者是在所有特征中找最好的切分點(diǎn)后者是在部分特征中， 5 默認(rèn)的”best”適合樣本量不大的時(shí)候，而如果樣本數(shù)據(jù)量非常大，此時(shí)決策樹(shù)構(gòu)建推薦”random”。 6max_features：None（所有），log2，sqrt，N特征小于50的時(shí)候一般使用所有的 7 8max_depth：intorNone,optional(default=None)一般來(lái)說(shuō)，數(shù)據(jù)少或者特征少的時(shí)候可以不管這個(gè)值。 9如果模型樣本量多，特征也多的情況下，推薦限制這個(gè)最大深度，具體的取值取決于數(shù)據(jù)的分布。10常用的可以取值10-100之間。常用來(lái)解決過(guò)擬合1112min_samples_split：如果某節(jié)點(diǎn)的樣本數(shù)少于min_samples_split，則不會(huì)繼續(xù)再嘗試選擇最優(yōu)特征來(lái)進(jìn)行劃分，13如果樣本量不大，不需要管這個(gè)值。如果樣本量數(shù)量級(jí)非常大，則推薦增大這個(gè)值。14min_samples_leaf：這個(gè)值限制了葉子節(jié)點(diǎn)最少的樣本數(shù)，如果某葉子節(jié)點(diǎn)數(shù)目小于樣本數(shù)，則會(huì)和兄弟節(jié)點(diǎn)一起被剪枝，15如果樣本量不大，不需要管這個(gè)值，大些如10W可是嘗試下516min_weight_fraction_leaf：這個(gè)值限制了葉子節(jié)點(diǎn)所有樣本權(quán)重和的最小值，如果小于這個(gè)值，則會(huì)和兄弟節(jié)點(diǎn)一起被剪枝默認(rèn)是0，就是不考慮權(quán)重問(wèn)題。17一般來(lái)說(shuō)，如果我們有較多樣本有缺失值，或者分類樹(shù)樣本的分布類別偏差很大，就會(huì)引入樣本權(quán)重，這時(shí)我們就要注意這個(gè)值了。1819max_leaf_nodes：通過(guò)限制最大葉子節(jié)點(diǎn)數(shù)，可以防止過(guò)擬合，默認(rèn)是"None”，即不限制最大的葉子節(jié)點(diǎn)數(shù)。如果加了限制，算法會(huì)建立在最大葉子節(jié)點(diǎn)數(shù)內(nèi)最優(yōu)的決策樹(shù)。20如果特征不多，可以不考慮這個(gè)值，但是如果特征分成多的話，可以加以限制具體的值可以通過(guò)交叉驗(yàn)證得到。21class_weight：指定樣本各類別的的權(quán)重，主要是為了防止訓(xùn)練集某些類別的樣本過(guò)多導(dǎo)致訓(xùn)練的決策樹(shù)過(guò)于偏向這些類別。這里可以自己指定各個(gè)樣本的權(quán)重，22如果使用“balanced”，則算法會(huì)自己計(jì)算權(quán)重，樣本量少的類別所對(duì)應(yīng)的樣本權(quán)重會(huì)高。23min_impurity_split：這個(gè)值限制了決策樹(shù)的增長(zhǎng)，如果某節(jié)點(diǎn)的不純度(基尼系數(shù)，信息增益，均方差，絕對(duì)差)小于這個(gè)閾值則該節(jié)點(diǎn)不再生成子節(jié)點(diǎn)。24即為葉子節(jié)點(diǎn)。25