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

时间：2022-05-01 03:17:08

终于搞定了决策树的生成算法，决策树看起来简单，实现超复杂。楼主用书本64页例5.3作为本次的数据集。
定义5.1（决策树） 分类决策树模型是一种描述对实例进行分类的树形结点。
先说一下熵和条件熵的公式。
熵： H(X)=−∑ni=1pilogpi
条件熵： H(Y|X)=−∑ni=1piH(Y|X=xi)
好了，如果这两个公式的概率是由数据估计得到时，所对应的熵与条件熵又称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。
经验熵： H(D)=−∑Kk=1|Ck||D|log2|Ck||D|
条件经验熵： H(D|A)=∑Kk=1|Di||D|H(Di)=−∑Kk=1|Di||D|∑Kk=1DikDilog2DikDi
信息增益比： gR(D,A)=g(D,A)HA(D)
，其中 HA(D)=−∑ni=1|Di||D|log2|Di||D|
先说下经验熵的一些符号的含义，不然你可能会有点懵。D是数据集，K是最后一列的标签类别（“是”，“否”）的个数，这里K对应着2，|D|代表数据集，这里是15。
然后说下条件经验熵，条件经验熵就是根据A的这个特征进行数据划分，比如我们现在可以根据第一维进行划分，数据集D会分成3个数据子集 Di ，前面5个青年的 D1 ，中间5个中年的 D2 ，后面5个老年的 D3 。那么 |D1| 和 D2 和 D3 就是5， 5， 5。然后 H(Di) 就是数据子集的一个经验熵 H(Di)=−∑Kk=1|Cik||D|log2|Cik||D| ，代入进去就得到了条件经验熵最后面的式子。

dataSet = [['青年', '否', '否', '一般', '否'],
           ['青年', '否', '否', '好', '否'],
           ['青年', '是', '否', '好', '是'],
           ['青年', '是', '是', '一般', '是'],
           ['青年', '否', '否', '一般', '否'],
           ['中年', '否', '否', '一般', '否'],
           ['中年', '否', '否', '好', '否'],
           ['中年', '是', '是', '好', '是'],
           ['中年', '否', '是', '非常好', '是'],
           ['中年', '否', '是', '非常好', '是'],
           ['老年', '否', '是', '非常好', '是'],
           ['老年', '否', '是', '好', '是'],
           ['老年', '是', '否', '好', '是'],
           ['老年', '是', '否', '非常好', '是'],
           ['老年', '否', '否', '一般', '否']]

好了，再看下下面的式子，是否会清晰一点？
经验熵： H(D)=−∑Kk=1|Ck||D|log2|Ck||D|
条件经验熵： H(D|A)=∑Kk=1|Di||D|H(Di)=−∑Kk=1|Di||D|∑Kk=1DikDilog2DikDi
这里我用了2个函数来实现上面2个式子的计算。

def entropy(self, dataSet, featureKey = -1): #经验熵,默认选最后一列作为特征
        classLabel = [row[featureKey] for row in dataSet]   #读取数据集中的最后一列，也就是类标签
        labelSet = set(classLabel)  #类别的集合
        k = len(labelSet)    #有k个类别，此次数据集中只有2个类别，“是”和“否”
        entropy = 0
for x in labelSet:  #此为遍历类标签的类别，计算熵
            p = classLabel.count(x) / float(len(classLabel))    #计算概率
            entropy -= p * math.log(p, 2)   #按照经验熵公式来的
return entropy

这个就是经验熵的计算，第一个参数是数据集，第二个参数是经验熵根据第几维的特征进行划分的。这里写-1，是代表最后一列的意思，也就是默认是按标签类别作为特征来计算经验熵的。

def conditionalEntropy(self, dataSet, i, featureSet): #条件经验熵
        column = [row[i] for row in dataSet]    #读取i列
        entropy = 0
for x in featureSet[i]:    #划分数据集，并计算
            subDataSet = [row for row in dataSet if row[i] == x]    #按i维的特征划分数据子集
            entropy += (column.count(x) / float(len(column))) * self.entropy(subDataSet)    #按条件经验熵公式来的
return entropy

这个就是条件经验熵的计算，你会看到这个经验熵最后我乘以了self.entropy(subDataSet)，这个就是 H(Di) ，subDataSet就是我通过第i维的特征进行划分出来的子集。如果按1维（Python的列表啥的都是从0开始计数的，所以此处i=0）也就是上面说的前面5个青年的 D1 ，中间5个中年的 D2 ，后面5个老年的 D3 。
你还记得吧，生成决策树是需要一个特征子集的。来看一下特征子集的代码。

def createFeatureSet(self, dataSet):    #创建特征集
        featureSet = {}
        m, n = np.shape(dataSet)
for i in range(n - 1):  #按列来遍历,n-1代表不存入类别的特征
            column = list(set([row[i] for row in dataSet]))    #按列提取数据
            featureSet[i] = column   #每一行就是每一维的特征值
return featureSet

楼主用了字典来保存（本来是用列表来保存的，后面发现计算（已分类的特征子集要去除掉）有些不便）。特征子集会是这样的。

{"0": ["青年", "中年", "老年"], "1": ["否", "是"], "2": ["否", "是"], "3": ["好", "非常好", "一般"]}

好了，铺垫了很多。我们来看一下建树。首先给你们看下结点，结点因为决策树呀，不一定是二叉树，楼主用了字典的形式来保存子结点，key代表着决策树的权值（或者说”边的值“会不会更贴切点？），value就是子结点了。

class Node: #结点
def __init__(self, data = None, lchild = None, rchild = None):
        self.data = data
        self.child = {}

下面是建树的代码。

def create(self, dataSet, labels):   #ID3算法和C4.5算法
        featureSet = self.createFeatureSet(dataSet) #特征集
def createBranch(dataSet, featureSet):
            label = [row[-1] for row in dataSet]    #按列读取标签
            node = Node()
#TODO:算法(2)
if (len(set(label)) == 1):   #说明已经没有需要划分的了
                node.data = label[0]
                node.child = None
return node
            HD = self.entropy(dataSet)  #数据集的熵
            maxGa = 0   #最大信息增益
            maxGaKey = 0  #最大信息增益的索引
for key in featureSet: #计算最大信息增益
                gDA = HD - self.conditionalEntropy(dataSet, key, featureSet)  #当前按i维特征划分的信息增益
                gDA = gDA / float(self.entropy(dataSet, key))   #这行注释掉,就是用ID3算法了，否则就是C4.5算法
print gDA
if (maxGa < gDA):
                    maxGa = gDA
                    maxGaKey = key
#TODO:算法(4)
            node.data = labels[maxGaKey]
            subFeatureSet = featureSet.copy()
del subFeatureSet[maxGaKey]#删除特征集（不再作为划分依据）
for x in featureSet[maxGaKey]:  #这里是计算出信息增益后，知道了需要按哪一维进行划分集合
                subDataSet = [row for row in dataSet if row[maxGaKey] == x] #这个可以得出数据子集
print json.dumps(subDataSet,encoding='UTF-8',ensure_ascii=False)
                node.child[x] = createBranch(subDataSet, subFeatureSet)
return node
return createBranch(dataSet, featureSet)

这段代码其实ID3和C4.5都有实现，两者唯一的区别就在于一个用信息增益判断，一个用信息增益比判断。
复述下信息增益比： gR(D,A)=g(D,A)HA(D)
，其中 HA(D)=−∑ni=1|Di||D|log2|Di||D|
注：在这里楼主并未实现书中的算法（2）和（4），因为没有数据集测试呀，不过你如果理解了楼主这个做法，你应该能想出来的。我用了TODO来表示。
这就是建树的过程了，后面楼主用了先序遍历进行简单的验证，以及分类函数来分类。
下面贴出完整的代码。

#-*-coding:utf-8-*-
import numpy as np
import math
import json
class Node: #结点
def __init__(self, data = None, lchild = None, rchild = None):
        self.data = data
        self.child = {}

class DecisionTree: #决策树
def create(self, dataSet, labels):   #ID3算法
        featureSet = self.createFeatureSet(dataSet) #特征集
def createBranch(dataSet, featureSet):
            label = [row[-1] for row in dataSet]    #按列读取标签
            node = Node()
#TODO:算法(2)
if (len(set(label)) == 1):   #说明已经没有需要划分的了
                node.data = label[0]
                node.child = None
return node
            HD = self.entropy(dataSet)  #数据集的熵
            maxGa = 0   #最大信息增益
            maxGaKey = 0  #最大信息增益的索引
for key in featureSet: #计算最大信息增益
                gDA = HD - self.conditionalEntropy(dataSet, key, featureSet)  #当前按i维特征划分的信息增益
                gDA = gDA / float(self.entropy(dataSet, key))   #这行注释掉,就是用ID3算法了，否则就是C4.5算法
print gDA
if (maxGa < gDA):
                    maxGa = gDA
                    maxGaKey = key
#TODO:算法(4)
            node.data = labels[maxGaKey]
            subFeatureSet = featureSet.copy()
del subFeatureSet[maxGaKey]#删除特征集（不再作为划分依据）
for x in featureSet[maxGaKey]:  #这里是计算出信息增益后，知道了需要按哪一维进行划分集合
                subDataSet = [row for row in dataSet if row[maxGaKey] == x] #这个可以得出数据子集
print json.dumps(subDataSet,encoding='UTF-8',ensure_ascii=False)
                node.child[x] = createBranch(subDataSet, subFeatureSet)
return node
return createBranch(dataSet, featureSet)
def classify(self, node, labels, testVec):
while node != None:
if (node.data in labels):
                index = labels.index(node.data)
                x = testVec[index]
for key in node.child:
if x == key:
                        node = node.child[key]
else:
# print node.data
break
return node.data

def createFeatureSet(self, dataSet):    #创建特征集
        featureSet = {}
        m, n = np.shape(dataSet)
for i in range(n - 1):  #按列来遍历,n-1代表不存入类别的特征
            column = list(set([row[i] for row in dataSet]))    #按列提取数据
            featureSet[i] = column   #每一行就是每一维的特征值
return featureSet

def conditionalEntropy(self, dataSet, i, featureSet): #条件经验熵
        column = [row[i] for row in dataSet]    #读取i列
        entropy = 0
for x in featureSet[i]:    #划分数据集，并计算
            subDataSet = [row for row in dataSet if row[i] == x]    #按i维的特征划分数据子集
            entropy += (column.count(x) / float(len(column))) * self.entropy(subDataSet)    #按公式来的
return entropy

def entropy(self, dataSet, featureKey = -1): #经验熵,默认选最后一列作为特征
        classLabel = [row[featureKey] for row in dataSet]   #读取数据集中的最后一列，也就是类标签
        labelSet = set(classLabel)  #类别的集合
        k = len(labelSet)    #有k个类别，此次数据集中只有2个类别，“是”和“否”
        entropy = 0
for x in labelSet:  #此为遍历类标签的类别，计算熵
            p = classLabel.count(x) / float(len(classLabel))    #计算概率
            entropy -= p * math.log(p, 2)   #按照公式来的
return entropy

def preOrder(self, node, depth = 0):
if (node != None):
print node.data, depth
if (node.child != None):
for key in node.child:
print key
                    self.preOrder(node.child[key], depth + 1)

dataSet = [['青年', '否', '否', '一般', '否'],
           ['青年', '否', '否', '好', '否'],
           ['青年', '是', '否', '好', '是'],
           ['青年', '是', '是', '一般', '是'],
           ['青年', '否', '否', '一般', '否'],
           ['中年', '否', '否', '一般', '否'],
           ['中年', '否', '否', '好', '否'],
           ['中年', '是', '是', '好', '是'],
           ['中年', '否', '是', '非常好', '是'],
           ['中年', '否', '是', '非常好', '是'],
           ['老年', '否', '是', '非常好', '是'],
           ['老年', '否', '是', '好', '是'],
           ['老年', '是', '否', '好', '是'],
           ['老年', '是', '否', '非常好', '是'],
           ['老年', '否', '否', '一般', '否']]
labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
# print dataSet
tree = DecisionTree()
node = tree.create(dataSet, labels)
for line in dataSet:
print tree.classify(node, labels, line)

注：本文中用了一些json.dumps(subDataSet,encoding=’UTF-8’,ensure_ascii=False)来打印，这是因为如果直接打印中文会出错的。
标签：

相关文章