決策樹(shù)算法

1.特性

優(yōu)點(diǎn):可讀性、分類速度快

缺點(diǎn):對(duì)未知數(shù)據(jù)集泛華能力弱，容易發(fā)生過(guò)擬合現(xiàn)象

特點(diǎn):劃分?jǐn)?shù)據(jù)集后，數(shù)據(jù)純度變大的過(guò)程

分類:離散型決策樹(shù)、連續(xù)型決策樹(shù)

與KNN的區(qū)別:KNN的缺點(diǎn)是無(wú)法給出數(shù)據(jù)內(nèi)在含義，而決策樹(shù)在數(shù)據(jù)形式上易于理解

2.構(gòu)建過(guò)程

創(chuàng)建決策樹(shù)三個(gè)過(guò)程:特征選擇，建立樹(shù)、裁剪(解決過(guò)擬合現(xiàn)象)

遞歸選擇熵值最大的特征進(jìn)行分類，以最快速度降低數(shù)據(jù)集不確定程度

根據(jù)特征選擇指標(biāo)的不同，分為ID3/CART/C4.5

（1）計(jì)算當(dāng)前分類信息熵（經(jīng)驗(yàn)熵）

H = -\sum_{i=1}^np(xi)\log_2 p(xi) ? ? ? ? ? ? ? ?n:分類次數(shù)； p(xi):該分類出現(xiàn)的概率

（2）求當(dāng)前每個(gè)特征分類后的條件熵

H(Y|X) = \sum_{i=1}^np(xi)H(Y|X=xi)

條件熵:我們假設(shè)以某個(gè)特征進(jìn)行分類(條件概率)，在已知該特征值分類情況下的分類結(jié)果Y計(jì)算熵（該特征每個(gè)取值的概率乘以一直該取值下的信息熵）

（3）求信息增益/信息增益比/基尼系數(shù)(增益:衡量劃分?jǐn)?shù)據(jù)前后信息發(fā)生的變化)

信息增益最大(ID3):僅用于二分類離散屬性問(wèn)題

g(D,A) = H(D) - H(D|A)

信息增益比最大(C4.5):可處理連續(xù)值屬性問(wèn)題(取連續(xù)屬性中值作為劃分標(biāo)準(zhǔn))

g_{R}(D,A) = \frac{g(D,A)}{H( D)}

基尼系數(shù)最小(CART):CART必須是二叉樹(shù)，分類和回歸都可運(yùn)用，但更偏向于連續(xù)屬性，不作對(duì)數(shù)運(yùn)算，更加高效:

Gini(D) = 1 - \sum_{i=1}^n \frac{(|C_{i} |}{| D|})^2? ??K:分類類別 ??|D|樣本個(gè)數(shù) ?|Ci|該類別個(gè)數(shù)

Gini(D,A) = \frac{|D1|}{D} Gini(D1) + \frac{|D2|}{D} Gini(D2)??D1 ?D2為該特征的分類，CART都是二分

（4）擇信息增益/信息增益比最大的特征進(jìn)行當(dāng)次劃分，然后取出該列特征。

（5）對(duì)于整棵樹(shù)的構(gòu)造，使用遞歸原則處理數(shù)據(jù)集

3.幾種衡量對(duì)比


4.剪枝

剪枝:考慮決策樹(shù)的復(fù)雜度，不出現(xiàn)過(guò)擬合現(xiàn)象，對(duì)決策樹(shù)進(jìn)行修剪；從已經(jīng)生成的樹(shù)上裁掉一些子樹(shù)或葉節(jié)點(diǎn)，并將其根節(jié)點(diǎn)或父節(jié)點(diǎn)作為新的葉子節(jié)點(diǎn)，從而簡(jiǎn)化分類樹(shù)模型

1.預(yù)剪枝:構(gòu)造結(jié)點(diǎn)錢判斷是否構(gòu)建該結(jié)點(diǎn)對(duì)泛化能力有所提升，運(yùn)算簡(jiǎn)單但可能欠擬合，適用于大規(guī)模問(wèn)題

四種簡(jiǎn)單方式判斷:

(1) 決策樹(shù)到達(dá)一定高度

(2) 結(jié)點(diǎn)下的實(shí)例少于一定個(gè)數(shù)

(3)信息增益、信息增益比低于某個(gè)閾值

2.后剪枝:先構(gòu)建整樹(shù)，自底向上對(duì)非葉節(jié)點(diǎn)進(jìn)行泛化能力判斷，通過(guò)極小化決策樹(shù)整體的損失函數(shù)或代價(jià)函數(shù)來(lái)實(shí)現(xiàn)的

后剪枝CCP:（CART/GBDT中所用的剪枝方法），代價(jià)復(fù)雜度剪枝

依次剪枝計(jì)算誤差，選擇誤差最小的那棵樹(shù)

注:關(guān)于剪枝部分? 以后來(lái)補(bǔ)充

5.基本代碼實(shí)現(xiàn)(來(lái)自機(jī)器學(xué)習(xí)實(shí)戰(zhàn))

（1）計(jì)算香農(nóng)熵

from math import log

from numpy import *

# 給定樣本集，計(jì)算該樣本集的熵，樣本集最后一列為分類

def cal_entropy(data):

? ? # 樣本個(gè)數(shù)

? ? entries_num = len(data)

? ? # 存儲(chǔ)每個(gè)分類出現(xiàn)的次數(shù)

? ? label_count = {}

? ? for vec in data:

? ? ? ? cur_label = vec[-1]

? ? ? ? label_count[cur_label] = label_count.get(cur_label,0) + 1

? ? # 熵

? ? Entropy = 0.0

? ? # 計(jì)算信息熵

? ? for key in label_count:

? ? ? ? prob = float(label_count[key]) / entries_num

? ? ? ? Entropy += prob * math.log(prob, 2) #此處使用numpy.math

? ? return (0-Entropy)

（2）計(jì)算信息增益，給出最優(yōu)特征

# -*- coding: utf-8 -*-

from Cal_Entropy import *

# 返回拆分后的數(shù)據(jù)集

def Split_Data(dataset, axis, value):

? ? new_subset = []

? ? for vec in dataset:

? ? ? ? if vec[axis] == value:

? ? ? ? ? ? feature_split = vec[:axis]

? ? ? ? ? ? feature_split.extend(vec[axis + 1:])

? ? ? ? ? ? new_subset.append(feature_split)

? ? return new_subset

# 傳入數(shù)據(jù)集，返回最優(yōu)特征(計(jì)算每個(gè)特征信息增益)

def Split_by_entropy(dataset):

? ? # 記錄當(dāng)前有多少個(gè)特征

? ? feature_num = len(dataset[0]) - 1

? ? # 當(dāng)前數(shù)據(jù)集信息熵

? ? ent_old = cal_entropy(dataset)

? ? # 最大信息增益

? ? best_gain = 0.0

? ? # 最好特征列

? ? best_feature = -1

? ? # 對(duì)每一個(gè)特征進(jìn)行遍歷

? ? for i in range(feature_num):

? ? ? ? feature_list = [x[i] for x in dataset]

? ? ? ? uniVal = set(feature_list)

? ? ? ? ent_new = 0.0

? ? ? ? for value in uniVal:

? ? ? ? ? ? sub_set = Split_Data(dataset, i, value)

? ? ? ? ? ? prob = len(sub_set) / float(len(dataset))

? ? ? ? ? ? ent_new += prob * (0 - cal_entropy(sub_set))

? ? ? ? Info_gain = ent_old - ent_new

? ? ? ? if(Info_gain > best_gain):

? ? ? ? ? ? best_gain = Info_gain

? ? ? ? ? ? best_feature = i

? ? return best_feature

（3）主函數(shù)，遞歸構(gòu)建決策樹(shù)

# -*- coding: utf-8 -*-

import operator

from Split_by_entropy import *

# 該方法輸入一組分類值，返回最多的分類結(jié)果

def Majority_vote(classList):

? ? classcount = {}

? ? for vote in classList:

? ? ? ? classcount[vote] = classcount.get(vote,0) + 1

? ? sorted_count = sorted(classcount.items(), key = operator.itemgetter(1),reverse = True)

? ? return sorted_count[0][0]

# 該方法用于遞歸構(gòu)建決策樹(shù)

def Create_Tree(dataset,labels):

? ? # 分類結(jié)果集

? ? classList = [x[-1] for x in dataset]

? ? # 如果該結(jié)點(diǎn)下所有數(shù)據(jù)都為同一分類，則返回該分類作為最終分類

? ? if classList.count(classList[0]) == len(classList):

? ? ? ? return classList[0]

? ? # 如果已經(jīng)分到最后一個(gè)特征但是該特征下還是有多個(gè)分類，選擇最多的那個(gè)分類作為最終分類

? ? if len(dataset[0]) == 1:

? ? ? ? return Majority_vote(classList)

? ? # 通過(guò)計(jì)算每個(gè)特征信息增益，選擇最優(yōu)特征及特征名

? ? best_feature = Split_by_entropy(dataset)

? ? best_labels = labels[best_feature]


? ? # 特征列表刪除該特征(已經(jīng)進(jìn)行了分類)

? ? subLabels=labels[:]

? ? del(subLabels[best_feature])

? ? myTree = {best_labels:{}}

? ? # 選取數(shù)據(jù)集中最優(yōu)特征列去重后進(jìn)行分類，繼續(xù)遞歸生成子樹(shù)

? ? f_val = [x[best_feature] for x in dataset]

? ? uni_val = set(f_val)

? ? for value in uni_val:

? ? ? ? # 遞歸創(chuàng)建子樹(shù)并返回

? ? ? ? myTree[best_labels][value] = Create_Tree(Split_Data(dataset\

? ? ? ? ? ? ? ,best_feature,value), subLabels)

? ? return myTree

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容