决策树 Decision Tree

2020-04-25

字数统计: 2.3k字 | 阅读时长≈ 9分

1. 介绍

决策树（Decision Tree）是一种常见的机器学习算法，以分类树为例，我们希望从数据中学习到一个模型来对新的数据进行分类，这个过程其实和人类在做决策时的时候的处理机制相似，提取事物的特征(features),按照一定的优先级判断事物的种类。

一般来说，一颗决策树包含一个根结点，若干个内部节点和若干个叶子结点，叶子节点即为决策树的分类，其它每个结点则对应一个属性测试；根结点包含样本全集，每个结点包含的样本集合根据属性测试的结果被划分到子结点中，从根结点到叶子结点的路径对应一个判定测试程序。

2. 划分选择

一个数据集中往往包含多个特征，按照每个特征划分出来的决策树通常时不一样的，这就涉及到哪个特征应该先被用到，现在常用的有三种选择标准：信息增益(information gain)，增益率(gain ratio)和基尼指数(Gini index).

2.1 信息熵

信息熵(information entropy)指的是平均而言发生一个事件我们可以得到的信息量的大小，是度量样本集合纯度最常用的一种指。假设一个样本集合D中包含n个事件，第i个事件发生的概率为pi,则D的信息熵定义为：

$H(D) = \sum_{i=1}^n -p_{i} * log_{2}p_{i}$

entropy

熵可以简单的理解为一个空间内、集合内的混乱度，熵越大，混乱度越高，得到的信息也就越少（高中化学老师教的）。

2.2 信息增益

如果属性a有V个可能的取值 $(a^1,a^2, …,a^V)$若用属性a来对样本集D进行划分，则会产生V个子结点，其中第v个子结点包含的样本子集记为$D^v$。我们可以根据上面的公式计算出$D^v$的信息熵。由于每个分支包含的样本数量不同，给分支结点赋予权重$|D^v|/|D|$, 即样本数量越多的分支结点影响越大。于是可计算用属性a对样本集D进行划分之后的信息增(information gain)。

$Gain(D,a) = H(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} H(D^v)$

能够更好划分数据集的特征能够得到更高的信息增益，相反越坏则信息增益越小。在对树进行分裂的时候，即选择使信息增益最大的特征来划分样本集。ID3决策时就是以信息增益为准则来划分属性。本文采用的便是信息增益准则，下面便是信息熵的计算以及信息增益计算的代码：

def get_entropy(self, classes):
'''compute the entropy'''
		counts = pd.value_counts(classes) 
    probs = [v/len(classes) for v in counts] 
    entropy = sum(-prob * log2(prob) for prob in probs)
    
    return entropy

def choose_feature(self, dataset): 
    '''compute the entropy gain to choose the best split feature'''
    dataset = pd.DataFrame(dataset) 
    base_entropy = self.get_entropy(dataset['classification']) 
    feature_num = dataset.shape[1] - 1 # since the last column is the label
    entropy_gains = []
    for feature in range(feature_num):
        new_entropy = 0
        _, subset = self.split_dataset(dataset, feature) 
        if len(dataset) != 0:
            for i in range(len(subset)):
                weight = len(subset[i])/len(dataset) # compute the weight of each subset
                new_entropy += (weight * self.get_entropy(dataset.loc[subset[i]]         																		['classification']))
            entropy_gains.append(base_entropy - new_entropy) # compute the entropy gain
        else:
            entropy_gains.append(0) # when one of the subsets is empty

    return entropy_gains.index(max(entropy_gains))  # return the index of max entropy,

2.3 增益率

信息增益准则可能会偏向于可能取值最多的属性，导致树的泛化能力变差。为了克服这个影响，C4.5决策时采用增益率(gain ratio)的方法对特征进行选择，其定义为：

$Gain_{ratio} = \frac{Gain(D,a)}{IV(a)}$ $IV(a) = - \sum_{v=1}^{n} \frac{|D^v|}{|D|} log_{2}\frac{|D^v|}{|D|}$

$IV(a)$ 称为特征a的“固有值”(instrinsic value)， a的可能取值越多，即V越大，$IV(a)$ 的值通常会越大，增益率也就会越小。由于增益率可能会对取值较少的特征有所偏向，因此，C4.5决策树其实并不是严格的按照增益率来选择特征的。C4.5先选择出信息增益高于某个平均值的特征，然后再从中选择出增益率最大的。

2.4 基尼指数

基尼指数(Gini index) 也被称为基尼不纯度(Gini Inpurity), 其描述了从集合中随机选择元素被错误分类的概率，当Gini index越小的时候，说明该数据集的纯度越高。样本集D的纯度可用基尼指数来衡量：

$Gini(D) = 1 - \sum_{k=1}^{|y|}p_{k}^2$

样本集D中属性a对应的Gini值可表示为：

$Gini_{index}(D,a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|}Gini(D)$ $Gain(D) = Gini(D) - Gini_{index}(D,a)$

于是，我们选择能够使增益最大的特征，也即寻找使Gini_index最小的特征来优先划分。

3. 树的生成

3.1 子集的划分

子集的划分其实就是在选定特征a之后，找出符合特征的取值$a^1,a^2,…,a^V$ 的样本集合，由于本次作业的要求，选择的两个特征都只有四个取值，所以在写程序的时候也比较“生硬”。

 def split_dataset(self, dataset, feature_index): 
'''define method to split subset for a feature'''
     dataset = pd.DataFrame(dataset) # if the type of dataset is not DataFrame, transfer it to DataFrame
     subset1, subset2, subset3, subset4= [],  [],  [],  [] # define 4 cluster to store the index of subset
     instances = dataset.iloc[:, feature_index] # get the examples of  each feature
     
     split_dict = {} # define the dict to store feature value and its corresponding subset
     features = list(dataset.columns)[0:]
     feature_value = sorted(list(set(dataset[features[feature_index]]))) # return the feature values(symbols)

     for index in list(dataset.index):
         if instances[index] == feature_value[0]: 
             subset1.append(index)
         elif instances[index] == feature_value[1]:
             subset2.append(index)
         elif instances[index] == feature_value[2]:
             subset3.append(index)
         elif instances[index] == feature_value[3]:
             subset4.append(index)
     subset = [subset1, subset2, subset3, subset4]

     for i in range(len(feature_value)):
         split_dict[feature_value[i]] = subset[i] # key = feature value, value = subset belongs to each feature value

     return split_dict, subset # return split subsets

3.2 树的生成

在选定最佳特征之后，下一步就是对生成一颗树。树的生成过程其实就是根据选择的特征对样本集进行划分，然后在选择出来的样本集中调用选择属性的方法选择该子集中的最佳特征，然后进一步的划分数据集。实现该过程的最佳思想就是递归。递归返回的条件有三个：

1). 当前结点包含的样本属于同一个类别，无需划分；

2). 当前特征集合为空，或是所有的样本在所有特征上取值相同，无法划分；

3). 当前结点包含的样本集为空，不能划分。

def create_tree(self, dataset, feature_names): 
    '''use the recursive method to create the decision tree '''
    dataset = pd.DataFrame(dataset)  # transfer the type of dataset to DataFrame
    classes = dataset['classification'] # get the classifications of dataset
    feature_names = list(feature_names)

    # stop conditions
    if len(set(classes)) == 1: # if the dataset has only one classification
        return set(classes)

    if len(dataset) == 0: # if the dataset is empty
        return None # return none
      
    if len(feature_names) == 0: # if we have split all features
        if len(set(classes)) != 1: # but there still are more than 1 classification
            probs= [] # return the probability of each class
            for i in range(len(set(classes))):
                probs.append([list(set(classes))[i],round(pd.value_counts(classes)[i] / len(classes), 4)]) 
            return probs
          
    # create tree, return in dict
    tree = {}
    best_feature_index = self.choose_feature(dataset)
    feature = feature_names[best_feature_index]
    tree[feature] = {} 
  
    sub_feature_names = feature_names[:]
    sub_feature_names.pop(best_feature_index) 
    
    split_dict, subset = self.split_dataset(dataset, best_feature_index) 
    for feature_value, sub_dataset in split_dict.items():
        if len(dataset) != 0: # if dataset is not empty
            tree[feature][feature_value] = self.create_tree(dataset.loc[sub_dataset], sub_feature_names) 
        else:
            continue
    return tree

4. 创建一颗决策树

在本文中决策树的创建即为类实例化的过程，不清楚的小伙伴建议看一下前面几篇文章。使用的数据是老师给的一个IDS(Intrusion Detection System)的log，里面包含source IP，destination IP和classification等属性。作业要求只选择了两个特征，所以出现了未能被完全分类的数据。树是存储在dict中的，可视化使用的是dot+graphviz方式。

from tree import DecisionTreeClassifier

DT_data = pd.DataFrame(DT_data, columns=['sourceIP', 'destIP', 'classification'])
my_tree = DecisionTreeClassifier() 
tree_dict = my_tree.create_tree(DT_data, DT_data.columns[0:-1]) 
print(tree_dict) 
dot_file = my_tree.dotify() # convert the dict to dot file
with open('./results/my_tree1.dot', 'w') as f: # write dot file to local
    dot = my_tree.dotify()
    f.write(dot)
my_tree.visualize('./results/my_tree1.dot') # visualize the decision tree

5. 总结

第一次自己写决策树，有很多地方其实是根据数据的格式和结构来做特定处理的，使代码能用，但是算法本身的繁华能力较差，以后有机会继续改进（其实sklearn挺香的）；
由于本次选用的特征只有两个，导致跑完两个特征之后，仍有数据未被分开。但是由观察数据，想着使用另一个特征”dest port” 来继续划分，但是算了一下这个特征对应的信息增益是最大的，而且所有数据都能分开，由于不符合要求，所以就没有尝试了。现在想想其实可以换一个准则，也许用gain ratio就可以了；
本次还写了对新数据分类的部分，dict转dot，以及可视化的部分可到GitHub上查看。

参考

周志华—-《机器学习》（“西瓜书”）
PytLab: https://github.com/PytLab/MLBox