基于Python实现的决策树

决策树作业

环境配置

python3.8.5

matplotlib 3.4.1

决策树算法原理

这里使用的是id3的决策树。

信息熵

一个节点信息熵，$p_k$是每个属性出现的概率。

$Ent(D)=-{\sum }_{k=1}^K{p}_k\ast lo{g}_2{p}_k$

每种特征中每个属性的信息熵

$Ent(D^v)$

每个特征的信息熵，$\frac{|D^v|}{|D|}$为各个属性在该节点所有样本中的占比

${\sum }_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$

信息增益，a是属性

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

算法过程

1. 将所有的特征看成一个一个的节点。创建根节点。
2. 遍历所有特征。遍历到其中某一个特征时，遍历当前特征的所有分割方式，找到最好的分割点，将数据划分为不同的子节点，计算划分后子节点的信息熵。
3. 在遍历的所有特征中，比较寻找最优的特征以及最优特征的最优划分方式。选择信息增益最高的特征，根据特征则对当前数据集进行分割操作，产生子树。
4. 对新的子节点继续执行2 - 3步，直到下面的停止条件退出循环。

决策树算法构建的停止条件

1. 当子节点中只有一种类型或为空的时候停止构建(会导致过拟合)

2. 当前节点种样本数小于某个值，同时迭代次数达到指定值，停止构建，此时使用该节点中出现最多的类别样本数据作为对应值(比较常用)

核心代码

主要的核心代码在id3.py中

建树的递归代码

def create_tree(data_set, labels):
    # 决策结果的集合
    classList = [example[-1] for example in data_set]

    # 当类别与属性完全相同时停止，这里的classList[0]就是no lenses,soft 和hard
    if classList.count(classList[0]) == len(classList):
        # 返回标签。
        return classList[0]
    # 遍历完所有特征值时，返回数量最多的
    if len(data_set[0]) == 1:
        return main_feat(classList)

    # 获取最佳划分属性的Index，以0开始
    bestFeat = best_feature(data_set)
    bestFeatLabel = labels[bestFeat]
    my_tree = {bestFeatLabel: {}}
    # 清空labels中的该列
    del (labels[bestFeat])
    # 获取该列中所有的属性值
    featValues = [example[bestFeat] for example in data_set]
    # 唯一化
    uniqueVals = set(featValues)

    for value in uniqueVals:
        # 获取剩下的属性
        subLabels = labels[:]
        # 递归调用创建决策树
        my_tree[bestFeatLabel][value] = create_tree(split_data(data_set, bestFeat, value), subLabels)
    return my_tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

遍历特征

计算信息熵

def calculate_shannon(data_set):
    data_set_len = len(data_set)
    label_counts = {}
    for feature_vec in data_set:
        # 提取soft hard还是不适合的标签
        label = feature_vec[-1]
        if label not in label_counts.keys():
            label_counts[label] = 0
        label_counts[label] += 1
    # 信息熵
    entropy = 0.0
    for key in label_counts.keys():
        # 这个就是每种决策结果（soft,hard还是no lenses占数据集的比重，也就是p）
        part_ent = float(label_counts[key] / data_set_len)
        # 将结果累加，得到根节点或该属性取值的信息熵
        entropy -= part_ent * log(part_ent, 2)
    return entropy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

计算最佳信息增益

def best_feature(data_set):
    feature_num = len(data_set[0]) - 1
    # 计算根节点的信息熵
    root_env = calculate_shannon(data_set)
    info_increase = float(0)
    feature_pos = -1
    # 每列属性
    for i in range(feature_num):
        features = []
        # 同一列的相同属性
        for fe_choose in data_set:
            features.append(fe_choose[i])
        # 取值的集合
        unique_feature = set(features)
        # 信息熵
        entropy = 0.0
        for value in unique_feature:
            sub_data = split_data(data_set, i, value)
            # 计算该种可能性出现的概率
            probability = len(sub_data) / float(len(data_set))
            # 用这个概率去乘以子集的香农熵
            entropy += probability * calculate_shannon(sub_data)

        info_gain = root_env - entropy
        if info_gain > info_increase:
            info_increase = info_gain
            feature_pos = i
    return feature_pos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

实验结果

{
  'tearRate': {
    'reduced': 'no lenses',
    'normal': {
      'astigmatic': {
        'yes': {
          'prescript': {
            'hyper': {
              'age': {
                'presbyopic': 'no lenses',
                'young': 'hard',
                'pre': 'no lenses'
              }
            },
            'myope': 'hard'
          }
        },
        'no': {
          'age': {
            'presbyopic': {
              'prescript': {
                'hyper': 'soft',
                'myope': 'no lenses'
              }
            },
            'young': 'soft',
            'pre': 'soft'
          }
        }
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

      'myope': 'no lenses'
          }
        },
        'young': 'soft',
        'pre': 'soft'
      }
    }
  }
}
1
2
3
4
5
6
7
8
9

}
}