《统计学习方法》决策树 ID3和C4.5 生成算法 Python实现

迈不过友情╰ 2022-06-10 13:26 151阅读 0赞

代码可在Github上下载:[代码下载][Link 1]

## 前言 ##

在博主刚接触编程的时候，曾经想过一个如何实现聊天机器人，当时最直接的想法是打算用if-else来做（事实上真用VB实现了一个简单的以自嗨）。而今天的决策树就是可以视为一种if-else的集合。  
而决策树的可以用来分类也可以用来完成回归任务。  
本部分介绍的决策树实现了ID3和C4.5算法。两者算法差别在于一个使用了信息增益一个使用了信息增益比。

## 算法理论 ##

定义5.1（决策树） 分类决策树模型是一种描述对实例进行分类的树形结点。  
先说一下熵（熵是一个种可以反应随机变量混乱程度的指标）和条件熵的公式。  
熵： H ( X ) = − ∑ i = 1 n p i l o g p i H(X)=-\\sum\_\{i=1\}^\{n\}p\_ilogp\_i H(X)=−∑i=1npilogpi  
条件熵： H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X)=\\sum\_\{i=1\}^\{n\}p\_iH(Y|X=x\_i) H(Y∣X)=∑i=1npiH(Y∣X=xi)  
好了，如果这两个公式的概率是由数据估计得到时，所对应的熵与条件熵又称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。  
经验熵： H ( D ) = − ∑ k = 1 K ∣ C k ∣ ∣ D ∣ l o g 2 ∣ C k ∣ ∣ D ∣ H(D)=-\\sum\_\{k=1\}^\{K\}\\frac \{|C\_k|\}\{|D|\}log\_2\\frac\{|C\_k|\}\{|D|\} H(D)=−∑k=1K∣D∣∣Ck∣log2∣D∣∣Ck∣  
条件经验熵： H ( D ∣ A ) = ∑ k = 1 K ∣ D i ∣ ∣ D ∣ H ( D i ) = − ∑ k = 1 K ∣ D i ∣ ∣ D ∣ ∑ k = 1 K D i k D i l o g 2 D i k D i H(D|A)=\\sum\_\{k=1\}^\{K\}\\frac \{|D\_i|\}\{|D|\}H(D\_i)=-\\sum\_\{k=1\}^\{K\}\\frac \{|D\_i|\}\{|D|\}\\sum\_\{k=1\}^\{K\}\\frac \{D\_\{ik\}\}\{D\_i\}log\_2\\frac \{D\_\{ik\}\}\{D\_i\} H(D∣A)=∑k=1K∣D∣∣Di∣H(Di)=−∑k=1K∣D∣∣Di∣∑k=1KDiDiklog2DiDik  
信息增益: g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)  
信息增益比： g R ( D , A ) = g ( D , A ) H A ( D ) g\_R(D,A)=\\frac\{g(D, A)\}\{H\_A(D)\} gR(D,A)=HA(D)g(D,A)  
其中 H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g 2 ∣ D i ∣ ∣ D ∣ H\_A(D)=-\\sum\_\{i=1\}^\{n\}\\frac\{|D\_i|\}\{|D|\}log\_2\\frac\{|D\_i|\}\{|D|\} HA(D)=−∑i=1n∣D∣∣Di∣log2∣D∣∣Di∣  
其中，D是数据集，K是最后一列的标签类别（“是”，“否”）的个数，这里K对应着2，|D|代表数据集的大小，这里是15。  
然后说下条件经验熵，条件经验熵就是根据A的这个特征进行数据划分，比如我们现在可以根据第一维进行划分，数据集D会分成3个数据子集 D i D\_i Di，前面5个青年的 D 1 D\_1 D1，中间5个中年的 D 2 D\_2 D2，后面5个老年的 D 3 D\_3 D3。那么 ∣ D 1 ∣ |D\_1| ∣D1∣和 D 2 D\_2 D2和 D 3 D\_3 D3就是5， 5， 5。然后 H ( D i ) H(D\_i) H(Di)就是数据子集的一个经验熵 H ( D i ) = − ∑ k = 1 K ∣ C i k ∣ ∣ D ∣ l o g 2 ∣ C i k ∣ ∣ D ∣ H(D\_i)=-\\sum\_\{k=1\}^\{K\}\\frac \{|C\_\{ik\}|\}\{|D|\}log\_2\\frac\{|C\_\{ik\}|\}\{|D|\} H(Di)=−∑k=1K∣D∣∣Cik∣log2∣D∣∣Cik∣，代入进去就得到了条件经验熵最后面的式子。  
![P64例5.3][P64_5.3]  
以上是P59的表5.1数据。熵是反应随机变量的不确定度量（一个矢量）。在这里我们想知道“类别”这个随机变量的不确定度量。从图中可以看到类别有“是”，“否”两种取值。 P ( 类 别 = 是 ) = ∣ D ( 类 别 = 是 ) ∣ ∣ D ∣ = 9 15 P(类别=是)=\\frac\{|D(类别=是)|\}\{|D|\}=\\frac\{9\}\{15\} P(类别=是)=∣D∣∣D(类别=是)∣=159, P ( 类 别 = 否 ) = ∣ D ( 类 别 = 否 ) ∣ ∣ D ∣ = 6 15 P(类别=否)=\\frac\{|D(类别=否)|\}\{|D|\}=\\frac\{6\}\{15\} P(类别=否)=∣D∣∣D(类别=否)∣=156。  
这样我们就可以算出这数据集在“类别”这个随机变量下的熵 H ( X ) = − ∑ i = 1 n p i l o g p i = − P ( 类 别 = 是 ) ∗ l o g ( P ( 类 别 = 是 ) ) − P ( 类 别 = 否 ) ∗ l o g ( P ( 类 别 = 否 ) ) = − 9 15 l o g ( 9 15 ) − 6 15 l o g ( 6 15 ) H(X)=-\\sum\_\{i=1\}^\{n\}p\_ilogp\_i=-P(类别=是)\*log(P(类别=是))-P(类别=否)\*log(P(类别=否))=-\\frac\{9\}\{15\}log(\\frac\{9\}\{15\})-\\frac\{6\}\{15\}log(\\frac\{6\}\{15\}) H(X)=−∑i=1npilogpi=−P(类别=是)∗log(P(类别=是))−P(类别=否)∗log(P(类别=否))=−159log(159)−156log(156)  
 H ( Y ∣ X ) H(Y|X) H(Y∣X)是给定随机变量X下随机变量Y的条件熵。  
这里举个例子，我们想知道在给定随机变量“年龄”下随机变量“类别”的条件熵。  
首先先计算 P ( 年 龄 = 青 年 ) = ∣ D ( 年 龄 = 青 年 ) ∣ ∣ D ∣ = 5 15 P(年龄=青年)=\\frac\{|D(年龄=青年)|\}\{|D|\}=\\frac\{5\}\{15\} P(年龄=青年)=∣D∣∣D(年龄=青年)∣=155, P ( 年 龄 = 中 年 ) = ∣ D ( 年 龄 = 中 年 ) ∣ ∣ D ∣ = 5 15 P(年龄=中年)=\\frac\{|D(年龄=中年)|\}\{|D|\}=\\frac\{5\}\{15\} P(年龄=中年)=∣D∣∣D(年龄=中年)∣=155, P ( 年 龄 = 老 年 ) = ∣ D ( 年 龄 = 老 年 ) ∣ ∣ D ∣ = 5 15 P(年龄=老年)=\\frac\{|D(年龄=老年)|\}\{|D|\}=\\frac\{5\}\{15\} P(年龄=老年)=∣D∣∣D(年龄=老年)∣=155。  
接着我们需要知道 H ( Y ∣ X = x i ) H(Y|X=x\_i) H(Y∣X=xi)是什么，比如在给定"年龄"="青年"的数据集中，随机变量"类别"的熵是多少。  
“年龄”="青年"的数据集是  
![年龄=青年的数据集][20190711113011229.png]  
那对应的 H ( Y ∣ X = x i ) = H ( 类 别 ∣ 年 龄 = 青 年 ) = − P ( 类 别 = 是 ) ∗ l o g ( P ( 类 别 = 是 ) ) − P ( 类 别 = 否 ) ∗ l o g ( P ( 类 别 = 否 ) ) = − 2 5 l o g ( 2 5 ) − 3 5 l o g ( 3 5 ) H(Y|X=x\_i)=H(类别|年龄=青年)=-P(类别=是)\*log(P(类别=是))-P(类别=否)\*log(P(类别=否))=-\\frac\{2\}\{5\}log(\\frac\{2\}\{5\})-\\frac\{3\}\{5\}log(\\frac\{3\}\{5\}) H(Y∣X=xi)=H(类别∣年龄=青年)=−P(类别=是)∗log(P(类别=是))−P(类别=否)∗log(P(类别=否))=−52log(52)−53log(53)  
当然还有"年龄=中年"的情况。  
![年龄=中年][20190711113737472.png]  
 H ( Y ∣ X = x i ) = H ( 类 别 ∣ 年 龄 = 中 年 ) = − P ( 类 别 = 是 ) ∗ l o g ( P ( 类 别 = 是 ) ) − P ( 类 别 = 否 ) ∗ l o g ( P ( 类 别 = 否 ) ) = − 3 5 l o g ( 3 5 ) − 2 5 l o g ( 2 5 ) H(Y|X=x\_i)=H(类别|年龄=中年)=-P(类别=是)\*log(P(类别=是))-P(类别=否)\*log(P(类别=否))=-\\frac\{3\}\{5\}log(\\frac\{3\}\{5\})-\\frac\{2\}\{5\}log(\\frac\{2\}\{5\}) H(Y∣X=xi)=H(类别∣年龄=中年)=−P(类别=是)∗log(P(类别=是))−P(类别=否)∗log(P(类别=否))=−53log(53)−52log(52)  
以及"年龄=老年"的情况。  
![年龄=老年][20190711120732618.png]  
 H ( Y ∣ X = x i ) = H ( 类 别 ∣ 年 龄 = 老 年 ) = − P ( 类 别 = 是 ) ∗ l o g ( P ( 类 别 = 是 ) ) − P ( 类 别 = 否 ) ∗ l o g ( P ( 类 别 = 否 ) ) = − 4 5 l o g ( 4 5 ) − 1 5 l o g ( 1 5 ) H(Y|X=x\_i)=H(类别|年龄=老年)=-P(类别=是)\*log(P(类别=是))-P(类别=否)\*log(P(类别=否))=-\\frac\{4\}\{5\}log(\\frac\{4\}\{5\})-\\frac\{1\}\{5\}log(\\frac\{1\}\{5\}) H(Y∣X=xi)=H(类别∣年龄=老年)=−P(类别=是)∗log(P(类别=是))−P(类别=否)∗log(P(类别=否))=−54log(54)−51log(51)  
 H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) = P ( 年 龄 = 青 年 ) H ( 类 别 ∣ 年 龄 = 青 年 ) + P ( 年 龄 = 中 年 ) H ( 类 别 ∣ 年 龄 = 中 年 ) + P ( 年 龄 = 老 年 ) H ( 类 别 ∣ 年 龄 = 老 年 ) = 5 15 ∗ − 2 5 l o g ( 2 5 ) − 3 5 l o g ( 3 5 ) + 5 15 ∗ − 3 5 l o g ( 3 5 ) − 2 5 l o g ( 2 5 ) + 5 15 ∗ − 4 5 l o g ( 4 5 ) − 1 5 l o g ( 1 5 ) H(Y|X)=\\sum\_\{i=1\}^\{n\}p\_iH(Y|X=x\_i)=P(年龄=青年)H(类别|年龄=青年)+P(年龄=中年)H(类别|年龄=中年)+P(年龄=老年)H(类别|年龄=老年)=\\frac\{5\}\{15\}\*-\\frac\{2\}\{5\}log(\\frac\{2\}\{5\})-\\frac\{3\}\{5\}log(\\frac\{3\}\{5\})+\\frac\{5\}\{15\}\*-\\frac\{3\}\{5\}log(\\frac\{3\}\{5\})-\\frac\{2\}\{5\}log(\\frac\{2\}\{5\})+\\frac\{5\}\{15\}\*-\\frac\{4\}\{5\}log(\\frac\{4\}\{5\})-\\frac\{1\}\{5\}log(\\frac\{1\}\{5\}) H(Y∣X)=∑i=1npiH(Y∣X=xi)=P(年龄=青年)H(类别∣年龄=青年)\+P(年龄=中年)H(类别∣年龄=中年)\+P(年龄=老年)H(类别∣年龄=老年)=155∗−52log(52)−53log(53)\+155∗−53log(53)−52log(52)\+155∗−54log(54)−51log(51)  
随后我们先计算数据集的经验熵，然后再算出每一个随机变量（年龄，有工作，有自己的房子，信贷情况）下随机变量类别的经验条件熵。然后计算得出信息增益。分别比较这些信息增益，最大的信息增益的随机变量作为划分特征。

## 算法实现 ##

def entropy(self, dataset, feature_key = -1): #计算熵
            """
            :param dataset:
            :param feature_key: we calculate entropy based on feature key
            :return: float
            """
            column = [row[feature_key] for row in dataset] #get the value by axis
            feature_set = set(column)  #range of this axis
            entropy = 0
            for x in feature_set:  #iterate every
                p = column.count(x) / float(len(column))
                entropy -= p * math.log(p, 2)   #emprical entropy=-p(log(p))
            return entropy

这里实现了经验熵的计算。第一个参数是数据集，第二个参数是经验熵根据第几维的特征进行划分的。这里写-1，是代表最后一列的意思，也就是默认是按标签类别作为特征来计算经验熵的。  
columns = \[row\[feature\_key\] for row in dataset\]是用来提取某一列的，比如提取最后一列。  
![最后一列][2019071112085449.png]  
接着遍历指定轴的每个取值，获得每个类别的概率计算得出经验熵。

def conditional_entropy(self, dataset, feature_key): #条件经验熵
            """
            :param dataset: 
            :param feature_key: 
            :return: float
            """
            column = [row[feature_key] for row in dataset]    #读取i列
            conditional_entropy = 0
            for x in set(column):   #划分数据集，并计算
                sub_data_set = [row for row in dataset if row[feature_key] == x]    #按i轴的特征划分数据子集
                conditional_entropy += (column.count(x) / float(len(column))) * self.entropy(sub_data_set)    #p*entropy(sub_data_set)
            return conditional_entropy

这里实现了经验条件熵的计算。先得到每个key的特征取值，比如"年龄"这个特征取值为\{青年，中年， 老年\}。你会看到这个条件熵最后乘以了self.entropy(subDataSet)，这个就是 H ( D i ) H(D\_i) H(Di)，subDataSet就是通过第i维的特征进行划分出来的子集。如果按1维（Python的列表啥的都是从0开始计数的，所以此处i=0）也就是上面说的前面5个青年的 D 1 D\_1 D1，中间5个中年的 D 2 D\_2 D2，后面5个老年的 D 3 D\_3 D3。接着得到各自的概率 p i p\_i pi以及子集的熵的乘积并相加求和就得到条件熵了。

def create_feature_set(self, dataset):    #创建特征集,特征集是样本每个维度的值域（取值）
            """
            :param dataset:
            :return: A dict. Key is the axis, value is the range
            like {0: ['老年', '青年', '中年'], 1: ['否', '是'], 2: ['否', '是'], 3: ['好', '一般', '非常好']}
            """
            feature_set = {}
            m, n = np.shape(dataset)    #m means rows, n means columns
            for axis in range(n - 1):  #按列来遍历,n-1代表不存入类别的特征(标签不存入)
                column = list(set([row[axis] for row in dataset]))    #按列提取数据，并用set过滤
                feature_set[axis] = column   #每一行就是每一维的特征值
            return feature_set

在构建之前，我们还需要创建一个特征集，用于后面建数的划分用。特别地，一旦我们已经对某个特征进行划分，那子树也就不再需要对这个特征进行划分，所以这个特征集保存着可划分的集合。

def create(self, dataset, labels, option="ID3"):
            """
            :param dataset:
            :param labels:
            :param option: "(ID3|C4.5)"
            :return: a root node
            """
            feature_set = self.create_feature_set(dataset) #特征集
            print(feature_set)
            def create_branch(dataset, feature_set):
                label = [row[-1] for row in dataset]    #按列读取标签
                node = Node()
                # TODO:算法(2)
                if (len(set(label)) == 1):   #this means this dataset needn't split
                    node.data = label[0]
                    node.child = None
                    return node
                HD = self.entropy(dataset)  #数据集的熵
                max_ga = 0   #最大信息增益
                max_ga_key = 0  #最大信息增益的索引
                for key in feature_set: #计算最大信息增益
                    g_DA = HD - self.conditional_entropy(dataset, key)  #当前按i维特征划分的信息增益
                    if option=="C4.5":
                        g_DA = g_DA / float(self.entropy(dataset, key))   #这里是计算信息增益比，这行注释掉,就是用ID3算法了，否则就是C4.5算法
                    if (max_ga < g_DA):
                        max_ga = g_DA
                        max_ga_key = key
                #TODO:算法(4)
                node.data = labels[max_ga_key]
                sub_feature_set = feature_set.copy()
                del sub_feature_set[max_ga_key]#删除特征集（不再作为划分依据）
                for x in feature_set[max_ga_key]:  #这里是计算出信息增益后，知道了需要按哪一维进行划分集合
                    sub_data_set = [row for row in dataset if row[max_ga_key] == x] #这个可以得出数据子集
                    node.child[x] = create_branch(sub_data_set, sub_feature_set)    #continue to split the sub data set
                return node
            return create_branch(dataset, feature_set)

首先要想划分决策树，必须知道哪一个特征（对我们的数据集是哪一列）是最混乱的（可以用信息增益或者信息增益比做为指标，信息增益越大不确定性越大）。  
好了，铺垫了很多，来看一下建树。首先看下结点，结点因为决策树呀，不一定是二叉树，楼主用了字典的形式来保存子结点，key代表着决策树的权值（或者说”边的值“会不会更贴切点？），value就是子结点了。  
在文本中，树的内部结点存放的值node.data是我们的描述（description， \[‘年龄’, ‘有工作’, ‘有自己的房子’, ‘信贷情况’\] ），表明这个是根据第几位划分的。叶子结点node.data存放着是类别。这样我们在搜索树的时候只要看node.data是不是在description子集中，如果不是就说明到叶结点了，返回叶结点的node.data就是类别了。  
每次建树时我们都看这个类别的数据集是否只有一个，如果只有一个说明不用再继续划分了，直接构造给叶子结点返回。  
如果不只只有一个，那么说明可以继续划分，则遍历计算每个特征的信息增益（或信息增益比），最大的信息增益的特征将会作为划分条件。  
这段代码其实ID3和C4.5都有实现，两者唯一的区别就在于一个用信息增益判断，一个用信息增益比判断。复述下信息增益比： g R ( D , A ) = g ( D , A ) H A ( D ) g\_R(D,A)=\\frac\{g(D, A)\}\{H\_A(D)\} gR(D,A)=HA(D)g(D,A)  
，其中 H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g 2 ∣ D i ∣ ∣ D ∣ H\_A(D)=-\\sum\_\{i=1\}^\{n\}\\frac\{|D\_i|\}\{|D|\}log\_2\\frac\{|D\_i|\}\{|D|\} HA(D)=−∑i=1n∣D∣∣Di∣log2∣D∣∣Di∣  
**注**：在这里楼主并未实现书中的算法（2）和（4），因为没有数据集测试呀，不过你如果理解了楼主这个做法，你应该能想出来的。我用了TODO来表示。  
这就是建树的过程了，后面楼主用了先序遍历进行简单的验证，以及分类函数来分类。  
全部代码可在Github上下载:[代码下载][Link 2]

[Link 1]: https://github.com/FlameCharmander/MachineLearning
[P64_5.3]: /images/20220610/5ee337a3349748a1a06e0ed66b3fa4d2.png
[20190711113011229.png]: /images/20220610/15ef0b5558d04886b2c8ad08df0b1b3d.png
[20190711113737472.png]: /images/20220610/7c4d87b0694c4dbdaf38e18823adc158.png
[20190711120732618.png]: /images/20220610/8ded77b20f5945c2bb37e983f7ae6b57.png
[2019071112085449.png]: /images/20220610/e9a88a97d4f5415184ab3668560157bb.png
[Link 2]: https://github.com/FlameCharmander/MachineLearning/blob/master/decision_tree/decision_tree%28ID3_C4.5%29.py