決策樹

決策樹是十大數(shù)據(jù)挖掘算法之一，在很多工程實踐中都取得了很好的效果。其分類決策過程與20問游戲類似，專家系統(tǒng)中經(jīng)常適用決策樹，而且決策樹給出結(jié)果往往可以匹敵在當(dāng)前領(lǐng)域具有幾十年工作經(jīng)驗的人類專家。

本文對決策樹的基本原理，優(yōu)缺點，應(yīng)用場景等進(jìn)行了簡要的概述。此外將會陸續(xù)實現(xiàn)常用的機器學(xué)習(xí)和數(shù)據(jù)挖掘算法，有簡單直觀的notebook形式，也有python易用重用的代碼。代碼實踐部分參考[4]，數(shù)據(jù)也來源于課本附帶的小的數(shù)據(jù)集，方便使用。
代碼鏈接：https://github.com/hfl15/MLinAction

概述

優(yōu)點：

  • 計算復(fù)雜度不高，輸出結(jié)果易于理解，對中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)[4]。

  • 不需要領(lǐng)域知識和參數(shù)設(shè)置，可以處理高維數(shù)據(jù)，樹型表示直觀容易理解，學(xué)習(xí)和分類步驟簡單、快速，一般有較好的準(zhǔn)確率[3]

缺點：

  • 可能產(chǎn)生過擬合[4]

適用數(shù)據(jù)類型：

  • 標(biāo)稱型、數(shù)值型（需要離散化）[4]

關(guān)鍵字：

  • 決策樹歸納，分裂屬性選擇，剪枝

算法步驟

Input:
    D: data set, contain value and class label
    attribute_list : candidate attribute list
    Attribute_selection_method: a process to select best split attribute in candidate attribute list
Return:
    a decision tree
    
DecisionTree(D, attribute_list, Attribute_selection_method):
    create a new node TNode;    if all instance in D have the same class label C:
        return TNode as a leaf node and label with class C;