决策树的ID3/C4.5算法

决策树是一种树形结构，在分类问题中，表示基于特征对实例进行分类的过程。

经典的决策树生成方法有ID3和C4.5算法，二者的生成过程大致相同，区别仅在于使用的对特征分类能力的评价标准不同。

ID3算法使用信息增益评估特征。信息增益即某一特征对分类结果的不确定性程度（即熵）的减少量。信息增益越大，某特征越能影响最终的分类结果，该特征应越位于决策树的顶端。而C4.5算法综合校正了选择取值较多的特征这一趋势，在信息增益的基础上除以某特征的熵，称为信息增益比。

由于计算信息增益需要频繁计算log函数，所以首先引入math库。

from math import log2

初始化节点类，每个节点有特征或类标签，子节点等属性。

class node:
    def __init__(self):
        #保存特征或类标记
        self.target = None
        #孩子字典，键为特征取值，值为子节点
        self.child = {}

下面开始树的生成，通过每一层传入的数据集计算出各个特征及类标签的取值。

    def generate(self, dataSet, features, method='ID3', e=0):
        '''生成树，输入参数分别为数据集，特征集，生成方法“ID3/C4.5”，阈值'''

        x_ranges = [set([i[j] for i in dataSet]) for j in range(len(dataSet[0]) - 1)]   #特征取值集合
        y_ranges = set([i[-1] for i in dataSet])                 #类标记取值集合

若所有实例属于同一类，则将该类作为类标记。

        #若所有实例属于同一类，则将该类作为类标记
        t = y_ranges
        if len(t) == 1:
            self.target = t.pop()
            return

若特征集为空，则将数据集中实例数最大的类作为类标记。

        #若特征集为空，则将数据集中实例数最大的类作为类标记
        if not features:
            t_dict = {}
            for x in y_ranges:
                t_dict[x] = len([i[-1] for i in dataSet if i[-1] == x])
            t_ls = list(t_dict.items())
            t_ls.sort(key=lambda a: a[1])
            self.target = t_ls[-1][0]
            return

计算经验熵与经验条件熵。经验熵即对整体分类标签不确定性的度量，经验条件熵是在已知某一特征的条件下计算得到的条件概率值。

        #计算经验熵
        sum0 = 0
        for i in y_ranges:
            ck_d = len([j[-1] for j in dataSet if j[-1] == i]) / len(dataSet)
            if ck_d == 0:
                continue
            sum0 -= ck_d * log2(ck_d)
        h_dataset = sum0
        #计算经验条件熵
        h_conditional = {}
        for i in range(len(features)):
            sum1 = 0
            for a in x_ranges[i]:
                sum2 = 0
                for b in y_ranges:
                    dik_di = len([c[-1] for c in dataSet if c[i] == a and c[-1] == b]) / len([c[-1] for c in dataSet if c[i] == a])
                    if dik_di == 0:
                        continue
                    sum2 += dik_di * log2(dik_di)
                sum1 -= (len([c[-1] for c in dataSet if c[i] == a]) / len(dataSet)) * sum2
            h_conditional[features[i]] = sum1

ID3算法可根据上述结果直接相减计算出各个特征的信息增益。

        if method == 'ID3':
            #计算信息增益
            information_gain = {}
            for i in features:
                information_gain[i] = h_dataset - h_conditional[i]

C4.5算法还需计算各个特征的熵，最后用信息增益比，即信息增益与各个特征的熵的比值来衡量。

        elif method == 'C4.5':
            #计算各个特征的熵
            h_feature = {}
            for n in range(len(features)):
                sum3 = 0
                for i in x_ranges[n]:
                    ck_d = len([j[n] for j in dataSet if j[n] == i]) / len(dataSet)
                    if ck_d == 0:
                        continue
                    sum3 -= ck_d * log2(ck_d)
                h_feature[features[n]] = sum3
            #计算信息增益比
            information_gain = {}
            for i in features:
                information_gain[i] = (h_dataset - h_conditional[i]) / h_feature[i]
        else:
            raise Exception

排序找到信息增益（比）最大的特征。

        #排序找到信息增益（比）最大的特征
        information_gain_ls = list(information_gain.items())
        information_gain_ls.sort(key=lambda x: x[1], reverse=True)
        feature_g = information_gain_ls[0]

若信息增益（比）小于阈值，则将数据集中实例数最大的类作为类标记。

        #若信息增益（比）小于阈值，则将数据集中实例数最大的类作为类标记
        if feature_g[1] < e:
            t_dict = {}
            for x in y_ranges:
                t_dict[x] = len([i[-1] for i in dataSet if i[-1] == x])
            t_ls = list(t_dict.items())
            t_ls.sort(key=lambda a: a[1])
            self.target = t_ls[-1][0]
            return

最后递归地对子节点进行生成构造，子节点的数据集必须是满足子节点的传入条件的数据实例，且传入的数据集与特征集都需要去掉已经用过的特征。

        #对特征的每一可能取值递归的构造子节点
        self.target = feature_g[0]
        f_index = features.index(self.target)
        f = features[:]
        f.remove(self.target)
        for i in x_ranges[f_index]:
            d = [x[:] for x in dataSet if x[f_index] == i]
            for j in range(len(d)):
                d[j].pop(f_index)
            self.child[i] = node()
            self.child[i].generate(d,f,method,e)

至此，整棵决策树生成完毕。下面是查询决策树。

查询方法十分简单，根据满足的特征条件自上而下查询至叶节点即可得出分类标签。

    def query(self, term):
        '''查找决策树，输入{'特征':'取值',...}形式的字典'''

        #判断是否查询到叶节点
        if not self.child:
            result = self.target
            return result
        else:
            result = self.child[term[self.target]].query(term)
            return result

输入数据生成决策树并验证。

if __name__ == "__main__":
    features = ['年龄','有工作','有自己的房子','信贷情况']        #特征集
    train_data = [['青年','否','否','一般','否'],                #训练数据集
                ['青年','否','否','好','否'],
                ['青年','是','否','好','是'],
                ['青年','是','是','一般','是'],
                ['青年','否','否','一般','否'],
                ['中年','否','否','一般','否'],
                ['中年','否','否','好','否'],
                ['中年','是','是','好','是'],
                ['中年','否','是','非常好','是'],
                ['中年','否','是','非常好','是'],
                ['老年','否','是','非常好','是'],
                ['老年','否','是','好','是'],
                ['老年','是','否','好','是'],
                ['老年','是','否','非常好','是'],
                ['老年','否','否','一般','否']]

    n = node()
    n.generate(train_data,features,method="ID3",e=0)

    z = {'有自己的房子':'否','有工作':'否','年龄':'青年','信贷情况':'一般'}
    print(n.query(z))

查询得到的结果为“否”。