一直以来学习的方向侧重于深度学习方面，看面试题发现缺少决策树方面的知识，补充学习下，大部分内容来自周志华的《机器学习》。

基本概念

决策树（decision tree）是基于树的结构来进行决策的，树的叶节点对数据点的判定结果；内部节点对应于对属性的某种测试（取某值、大于小于、线性组合后判定、分割连续值）。样本点根据节点的测试结果被分到不同的子节点，递归地划分到叶节点。

决策树学习的目的是产生一棵泛化能力较强的决策树。

强调泛化能力强，是因为在不含特征向量相同而标记不同（冲突数据）而又不进行剪枝处理时，决策树总能完全拟合训练数据。最差条件下，每个样本分到一个叶节点，泛化性能差。

划分依据

从基本概念中可以看出，决策树希望分支节点的同类比例更高。于是引入信息熵来度量样本集的“纯度”。

信息熵的定义：

Ent(D)=-\sum\limits_{k=1}^{|y|}p_klog_2p_k

$|y|$ 为类别数，样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k$ 。以样本集合的比例代替实际数据出现的概率，信息熵越低，则分类确定性更高，样本集合的“纯度”越高。

信息增益（ID3）

有了信息熵，考虑分支节点的样本数不同，为分支节点赋予信息权重（即分支节点样本数与集合样本数之比），得到一次节点划分的信息增益，公式定义：

Gain(D,a)=Ent(D)-\sum\limits_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)

$a$ 为样本数据集的某个属性，对于离散值可以对每个属性分别计算信息增益，根据 $a_*=\underset{a\in A}{argmax}Gain(D,a)$ ，得到最优划分属性。

增益率（C4.5）

以信息增益为划分依据有一个问题是：信息增益准侧罪域可取值数目较多的属性有偏好（划分后得到更多的子节点，纯度较高）。对样本集的属性 $a$ ，引入属性的固有值：

IV(a)=-\sum\limits_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

使用固有值和信息增益定义增益率：

Gain\\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}

增益率准则与信息增益准则相反，倾向于选择可取值数目少的属性作为划分依据（a的取值越少， $IV(a)$ 越小，增益率越大）。

Gini指数（CART）

使用Gini值来度量数据集的“纯度”，Gini值越小纯度越高。定义如下：

Gini(D)=\sum\limits_{k=1}^{|y|}\sum\limits_{k'\neq k}p_kp_{k'}=1-\sum\limits_{k=1}^{|y|}p_k^2

Gini指数的定义：

Gini\_index(D,a)=\sum\limits_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)

其他处理

剪枝

剪枝是为了避免决策树分支过多，避免过拟合现象。主要分预剪枝和后剪枝。

两者的相同点是都用验证集对划分节点的泛化性能进行估计，不同点在于预剪枝在每个节点划分前进行估计，后剪枝在决策树训练完成后自底向上地估计每个划分节点。

两种方式都能降低过拟合风险，预剪枝还能降低训练时间，但由于其贪心性可能带来欠拟合风险；后剪枝训练时间长，但保留分支更多，性能优于预剪枝。

连续值和缺失值

连续值
对于连续值的处理可以采用离散化，对取值按从小到大排序，依次取相邻值的均值为划分点，得到候选的划分点集合，然后选择使增益最大化的划分点。

缺失值
对于缺失值的处理是决策树算法的优势，属性值缺失产生两个问题：

如何选择划分属性；
如何对缺失当前划分属性的样本进行划分。
对于第一个问题，可以使用在属性上没有缺失的样本集进行判断。为样本赋予权重 $w_x$ ， $\tilde{D}$ 表示没有缺失值的样本集， $\rho$ 表示无缺失值样本所占比例（其实是样本权值所占比例），对于信息增益来说，推广后的式子为：

Gain(D,a)=\rho×Gain(\tilde{D},a)

对于第二个问题，若样本在划分属性上取值未知，将样本同时划分到所有子节点，并调整样本权值。

代码部分的问题：1、连续属性分割没做；2、信息增益计算写的有点乱。

代码

数据集

编号	色泽	根蒂	敲声	纹理	脐部	触感	密度	含糖率	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	0.697	0.460	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	0.774	0.376	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	0.634	0.264	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	0.608	0.318	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	0.556	0.215	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	0.403	0.237	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	0.481	0.149	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	0.437	0.211	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	0.666	0.091	否
10	青绿	硬挺	清脆	清晰	平坦	软粘	0.243	0.267	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	0.245	0.057	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	0.343	0.099	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	0.639	0.161	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	0.657	0.198	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	0.360	0.370	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	0.593	0.042	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	0.719	0.103	否

import numpy as np
import pandas as pd
Data = pd.DataFrame.from_csv('./watermelon3_0_En.csv')
X = Data.values[:,0:6]
Y = Data.values[:,-1]
class Node(object):

    def __init__(self,data,labels,attributes=None):
        """
        train_X
            type:np.ndarray()
            size:(n_samples,n_features)
        
        train_Y
            type:np.ndarray()
            size:(n_samples,)
        """
        self.data = data
        self.label = labels
        self.attribute_type = None
        
        self.classes = set(labels)
        self.subnodes = list()
        
        self.leaf = False
        self.y_hat = None
        self.splite_attribute = None
        
        if attributes == None:
            self.attributes = list(range(self.data.shape[1]))
        else:
            self.attributes = attributes

    def GetMajority(self):
        """
        find most common label for a dataset
        """
        y_ = list(node.labels)
        return max(y_,key=y_.count)
       
        
class DecisionTree(object):
    
    def __init__(self,train_X,train_Y):
        self.root = Node(data=train_X,labels=train_Y)
        self.GenrateTree()
    
    def Ent(self,P_k):
        """
        Compute entropy.
        """
        P_k = np.array(P_k)
        P_k[P_k==0] = 1
        return -np.sum(P_k*np.log2(P_k))


    def GetGain(self,node):
        """
        Compute information gain and gain ratio
        return (gain,gain_ratio)
        """
        d_p_k =  [sum(node.label==x)/len(node.label) for x in node.classes]
        ent_d = self.Ent(d_p_k) #compute entropy of dataset D
        gain = list()
        gain_ratio = list()

        for attribute in node.attributes:
            if attribute is not None:
                d_p_v = list()
                ent_d_v = 0.0
                attribute_values = node.data[:,attribute]
                attribute_list = list(set(attribute_values))

                weight_d_v = [sum(attribute_values==x)/len(attribute_values) for x in attribute_list]
                for i,v in enumerate(attribute_list):
                    d_n = node.label[node.data[:,attribute] == v]
                    d_p_k = [sum(d_n==x)/len(d_n) for x in node.classes]

                    ent_d_v += weight_d_v[i] *self.Ent(d_p_k)
                    d_p_v.append(len(d_n)/len(node.label))

                gain.append(ent_d-ent_d_v)
                intrinsic_value = self.Ent(d_p_v)
                gain_ratio.append(np.divide(gain[attribute],intrinsic_value))
            else:
                gain.append(0)
                gain_ratio.append(0)
        return gain,gain_ratio
    
    def GenrateNodes(self,node):
        """
        Genrate sub-nodes for a given node.
        """
        (_,gain_ratio) = self.GetGain(node)
        node.splite_attribute = gain_ratio.index(np.max(gain_ratio))
        attribute_values = node.data[:,node.splite_attribute]
        attribute_list = set(attribute_values)
        subattributes = node.attributes.copy()
        subattributes[node.splite_attribute]=None
        for attr in attribute_list:
            index = (attribute_values == attr)
            subnode = Node(data=node.data[index,:],labels=node.label[index],
                           attributes=subattributes)
            node.subnodes.append(subnode)
        return node.subnodes
    
    def GenrateTree(self):
        """
        Genrate decision tree from root.
        """
        q = list()
        node = self.root
        
        while(len(q)>0 or node!= None):
            if len(node.classes) == 1:#Data belongs to the same class
                node.y_hat = node.classes
                node.leaf = True
            elif len(node.attributes) == 0:# or len(set(node.data[:,attribute]))==1:
                node.y_hat = node.GetMajority()
                node.leaf = True
            else:
                q.extend(self.GenrateNodes(node))
            if len(q) == 0:
                return
            node = q.pop(0)
    def Summary(self):
        """
        Prints a string summary of the decision tree.
        """
        q = list()
        node = self.root
        q.append(node)
        
        while(q):
            node = q.pop(0)
            print('splite_attribute',node.splite_attribute)
            print('data',node.data)
            print('Y_hat',node.y_hat)
            print('===='*20)
            q.extend(node.subnodes)
tree = DecisionTree(train_X=X,train_Y=Y)
tree.Summary()

ji

决策树学习