決策樹

???決策樹是一種樹狀的機(jī)器學(xué)習(xí)模型，模型中以數(shù)據(jù)屬性做為分支結(jié)點违施，最后的分類結(jié)果作為葉子結(jié)點。下圖是西瓜書里所描述的一棵決策樹瑟幕，其分支結(jié)點是數(shù)據(jù)的屬性(紋理磕蒲、根蒂、觸感只盹、色澤)辣往，而葉子結(jié)點則是其分類結(jié)果。(好瓜殖卑、壞瓜)

決策樹.PNG

決策樹的構(gòu)建

???整個決策樹的構(gòu)建過程如下：

createBranch( 數(shù)據(jù)集D, 屬性集A ){
   if  數(shù)據(jù)集D不能再分
       形成葉子結(jié)點并返回

   尋找劃分的最佳特征站削，將數(shù)據(jù)集D切分成相應(yīng)的子集：D_1,D_2,...,D_K
    
    for i: 1 to K
        createBranch( 數(shù)據(jù)集D_i )
}

整個決策樹構(gòu)建過程，是一個遞歸過程孵稽，不斷遞歸創(chuàng)建直至整個數(shù)據(jù)集完成為止许起。這里面最重要的是：尋找劃分的最佳特征十偶，因為最佳特征的標(biāo)準(zhǔn)的不同，就代表著構(gòu)建決策樹構(gòu)建算法的不同园细。
???構(gòu)建決策樹的算法主要有：ID3(信息增益+多叉樹)惦积，C4.5(增益率+多叉樹)，C5.0猛频，CART(基尼指數(shù)+二叉樹)

信息增益與增益率

???信息增益是指數(shù)據(jù)集劃分前與劃分后信息熵的差狮崩；信息熵的定義：
其中為屬于第c類的樣本出現(xiàn)的頻率，那么信息增益的定義可以寫成：
信息增益就是分解前數(shù)據(jù)集D的信息熵Ent(D)鹿寻，和根據(jù)屬性a分解成K個子集后的信息熵的加權(quán)平均的差睦柴。
???增益率是在信息熵的基礎(chǔ)下定義的：
其實增益率相當(dāng)于是信息增益除以數(shù)據(jù)集的“數(shù)量”，類似于信息增益的平均值毡熏，但是這個基數(shù)并非只是數(shù)據(jù)集的規(guī)模坦敌。

基尼指數(shù)

???基尼指數(shù)則是CART決策樹使用的劃分標(biāo)準(zhǔn)。首先基尼值的定義：
其實基尼值主要是形容從一個集合中隨機(jī)抽取兩個樣本招刹，其不屬于同一類別的概率；在這基礎(chǔ)上窝趣，基尼指數(shù)可定義成：

ID3決策樹實現(xiàn)

???本文章中疯暑，ID3決策樹的數(shù)據(jù)結(jié)構(gòu)形式參考的是《機(jī)器學(xué)習(xí)實戰(zhàn)》中的形式： ???關(guān)于信息熵和信息增益的實現(xiàn)，只需按著公式實現(xiàn)即可哑舒。而關(guān)于“尋找最佳劃分特征”妇拯，遍歷屬性集中的屬性值，分別計算以此屬性劃分后的集合的信息熵洗鸵，然后計算信息增益越锈，找到信息增益最大的屬性所對應(yīng)的下標(biāo)返回，代碼如下：

def ID3Core( dataset ):
    
    n = dataset.shape[0]
    dims = dataset.shape[1] - 1
    
    pre_ent = Ent(dataset)
    max_delta = 0.0
    best_idx = -1
    
    for i in range( dims ):
        pro_values = set(dataset[:, i])
        after_ent = 0
        
        for v in pro_values:
            sub_set = dataset[ np.where( dataset[:, i] == v )[0] ]
            after_ent += sub_set.shape[0] * 1.0 / n  * Ent( sub_set )
            
        delta = pre_ent - after_ent
        
        if ( delta > max_delta ):
            max_delta = delta
            best_idx = i
    
    return best_idx

而決策樹建立的代碼如下：

def createTree(dataset, attr):
    
    #計算集合dataset中最多的類別
    set_value = np.argmax( np.bincount( dataset[:, -1] ) )
    
    #如果dataset中的類別只有一類膘滨，建立葉子結(jié)點
    if len( set(dataset[:, -1]) ) == 1:
        return dataset[0, -1]
    
    #找到最佳的劃分特征
    split_idx = ID3Core(dataset)
    set_values = set(dataset[:, split_idx])
    branch = {}
    
    #根據(jù)劃分特征里面的特征值甘凭，遞歸地建立決策樹
    for v in set_values:
        sub_set = dataset[np.where( dataset[:,split_idx] == v)[0]]
        branch[v] = createTree( np.delete(sub_set, split_idx, axis=1), np.delete(attr, split_idx) )
      
    #屬性值沒有覆蓋到的值，設(shè)立為該數(shù)據(jù)集較多的類別的葉子結(jié)點
    rest = attr_values[attr[split_idx]] - set_values
    if len(rest) > 0:
        for v in rest:
            branch[v] = set_value
            
    return { attr[split_idx] : branch }

而具體的分類函數(shù)如下：

def classify(Tree, attr, data):
    
    proper = list(Tree.keys())[0]
    branch = Tree[proper]
    idx = attr.index(proper)
    
    for key in branch.keys():
        if data[idx] == key:
            if type(branch[key]).__name__ == 'dict':
                classLabel = classify(branch[key], attr, data)
            else:
                classLabel = branch[key]
                
    return classLabel

???上述實現(xiàn)中火邓，數(shù)據(jù)集是將其量化成數(shù)據(jù)丹弱，即將數(shù)據(jù)集合中的屬性值相應(yīng)的屬性，標(biāo)記為數(shù)字：0,1,...,k铲咨。ID3算法也是適合用于離散值數(shù)據(jù)躲胳，對于連續(xù)性數(shù)據(jù)需要進(jìn)行離散化。

CART決策樹實現(xiàn)

???這里CART的實現(xiàn)纤勒，是參考《機(jī)器學(xué)習(xí)實戰(zhàn)》坯苹。CART與ID3不同之處，CART是一顆二叉樹摇天，分支結(jié)點不再是某一屬性的所有分支粹湃，而是某個屬性的具體某個值的一個大于和小于的二分恐仑；這也意味著，與ID3不同再芋，所有屬性不再是使用一次后菊霜，將其全部分解，而是可以同時使用济赎，并也可處理連續(xù)型數(shù)據(jù)鉴逞。對于葉子結(jié)點來說，可以是回歸類型(一個數(shù)值)或者是模型類型(一段線性函數(shù))
回歸類型：

def regLeaf(dataset):
    return np.mean( dataset[:, -1] )

def regErr(dataset):
    m = dataset.shape[0]
    return m * np.var( dataset[:, -1] )

模型類型：

def linearSolve(dataset):
    
    m, n = dataset.shape
    X = np.ones((m, n)); y = np.ones((n, 1))
    X[:, 1:n] = dataset[:, 0:n-1]; y = dataset[:, -1]
    
    xTx = np.mat(np.dot(X.T, X))
    
    if np.linalg.det(xTx) == 0.0:
        raise NameError("this matrix is singular, can't do inverse")
        
    ws = np.dot( xTx.I, np.dot(X.T, y) )
    
    return ws, X, y
    
def modelLeaf(dataSet):
    ws, X, Y = linearSolve(dataSet)
    return ws

def modelErr(dataSet):
    ws, X, Y = linearSolve(dataSet)
    yHat = np.dot(X, ws.T)
    
    return np.sum( np.power(Y - yHat, 2) )

選擇劃分特征的代碼：

def chooseBestSplit(dataset, leafType=regLeaf, errType=regErr, ops=(1, 4)):
    
    #數(shù)據(jù)集僅包含一個類別司训，直接返回該數(shù)據(jù)集的類別
    if ( len(set(dataset[:, -1])) == 1):
        return None, leafType( dataset )
    
    tol_gini = ops[0]; tol_n = ops[1]
    m, n = dataset.shape
    
    best_gini = np.inf; best_idx = 0; best_val = 0
    pre_gini = errType( dataset )
    
    for i in range( n-1 ):
        for v in set(dataset[:, i]):
            s1, s2 = splitDataset(dataset, i, v)
            
            #分成兩個數(shù)據(jù)集后构捡，數(shù)據(jù)集規(guī)模太小則不進(jìn)行切分
            if (s1.shape[0] < tol_n) or (s1.shape[0] < tol_n):
                continue
                
            new_gini = errType(s1) + errType(s2)
            
            if new_gini < best_gini:
                best_gini = new_gini
                best_idx = i
                best_val = v
    
    #如果最好的特征劃分后，基尼值的提升不足壳猜，則不劃分勾徽，直接作為葉子結(jié)點
    if (pre_gini - best_gini) < tol_gini:
        return None, leafType(dataset)
    
    s1, s2 = splitDataset(dataset, i, v)
    #分成兩個數(shù)據(jù)集后，數(shù)據(jù)集規(guī)模太小則不進(jìn)行切分, 設(shè)置為葉子結(jié)點
    if (s1.shape[0] < tol_n) or (s1.shape[0] < tol_n):
        return None, leafType(dataset)
    
    return best_idx, best_val

創(chuàng)建樹的代碼：

def createTree(dataset, leafType=regLeaf, errType=regErr, ops=(1, 4)):
    
    idx, val = chooseBestSplit(dataset, leafType, errType, ops)
    
    if idx == None:
        return val
    
    tree = {}
    tree['splitIdx'] = idx
    tree['splitValue'] = val
    
    set1, set2 = splitDataset(dataset, idx, val)
    tree['left'] = createTree(set1, leafType, errType, ops)
    tree['right'] = createTree(set2, leafType, errType, ops)
    
    return tree

可以看到统扳，創(chuàng)建回歸樹和模型樹喘帚，只是葉子結(jié)點和衡量標(biāo)準(zhǔn)不同，其他地方是沒什么差別的咒钟；并且吹由，可以做進(jìn)一步想象，對于模型樹朱嘴，葉子結(jié)點可不可以選擇不只是線性模型倾鲫，也可不可以選擇一個簡單的神經(jīng)網(wǎng)絡(luò)作為葉子結(jié)點？順便說一下萍嬉，sklearn里面的decision tree的具體實現(xiàn)是優(yōu)化版的CART樹乌昔。

決策樹的剪枝

???剪枝主要解決的是決策樹的“過擬合”的手段。剪枝的基本策略主要有：預(yù)剪枝和后剪枝壤追。
???預(yù)剪枝是在決策樹生成時進(jìn)行剪枝磕道；對于當(dāng)前的分支結(jié)點，假設(shè)此時把它看成葉子結(jié)點時其對于訓(xùn)練數(shù)據(jù)的正確率行冰，然后將該節(jié)點進(jìn)行劃分捅厂，計算其劃分后的孩子結(jié)點的正確率；若有所提高則劃分(不剪枝)资柔，若沒有則不進(jìn)行劃分(剪枝)焙贷。
???后剪枝是在決策樹生成后進(jìn)行剪枝；使用后剪枝時贿堰，會將訓(xùn)練集分成兩部分辙芍，一部分用來生成決策樹，另一部分進(jìn)行剪枝。當(dāng)決策樹生成后故硅，會從底到頂遍歷分支結(jié)點庶灿，和預(yù)剪枝類似，計算該分支結(jié)點的正確率吃衅，然后將該分支結(jié)點合并成葉子結(jié)點再計算其正確率往踢；若正確率有提升，則將該分支結(jié)點合并成葉子結(jié)點徘层；反之則不做處理峻呕。
???這里并未展現(xiàn)剪枝的代碼，在《機(jī)器學(xué)習(xí)實戰(zhàn)》中趣效，有CART樹的剪枝方法瘦癌。而sklearn的決策樹中，并未提供剪枝的方法跷敬，但可通過調(diào)整關(guān)于樹的深度等參數(shù)讯私，來防止決策樹的過擬合。

最后

???作為一個分類問題西傀，不可避免地談到其分類邊界斤寇；如果把數(shù)據(jù)的每個屬性看作是樣本空間的一個坐標(biāo)軸，而決策樹的分類邊界其實是由一段段與軸平行的分段所組成拥褂，決策樹的每個分支結(jié)點娘锁，則代表一段這樣的分段。在真實任務(wù)中肿仑，決策樹也會相對復(fù)制致盟，因為決策邊界的組成則會有很多段小線段組成碎税。
???也有一種決策樹尤慰，“多變量決策樹”，每個分支結(jié)點不再是一個屬性雷蹂，而是屬性的線性組合伟端；這樣的話，分類邊界不再是與軸平行的“線段”匪煌，也可以是“斜線”责蝠。OC1則是構(gòu)建“多變量決策樹”的主要算法。