一、实验内容简介

该实验主要利用ID3算法和已有的数据建立决策树和随机森林，并利用决策树和随机森林来预测未知数据的值。本实验使用Python实现。

二、算法说明

下面介绍几个基础但很重要的概念：

• 决策树：决策树是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。

• 随机森林：随机森林是一种包含很多决策树的分类器，既可以用于处理分类和回归问题，也适用于降维问题。其对异常值与噪音也有很好的容忍，相较于决策树有着更好的预测和分类性能。

• ID3算法：该算法是本实验的重点。ID3 算法的核心是根据信息增益来选择进行划分的特征，然后递归地构建决策树。它的思想并不复杂，步骤也比较简单。下面简单介绍一下ID3算法的步骤。

1. 从根节点开始，计算所有可能的特征的信息增益，选择信息增益最大的特征，来划分节点。

2. 按该特征的不同取值建立子节点。

3. 如果没有特征可以选择或类别完全相同，则得到决策树，该算法结束。否则转向第4步。

4. 对子节点递归1、2步。

三、算法分析与设计

说明：因为屎山代码比较长，所以这里部分只给出函数名，函数具体实现请见附录。

学习完算法的基本原理后，现在开始真正实现该算法。实现该算法就没有理解算法思想那么容易了。这里运用面向对象的思想，把决策树和随机森林分开来写，这样不至于混淆。

首先实现决策树，按照算法步骤首先需要计算信息增益，而想要计算信息增益首先需要计算熵和条件熵。这里把它们分到三个方法里：

def entropy(self, condition=None):
def entropy_condition(self, condition=None):
def information_gain(self, condition):

关于实现的具体过程，就是按照相关的数学表达式实现即可。比如说信息增益，等于最终特征本身的熵，减去给定A的条件下该特征的条件熵。
接着实现信息增益最大的节点进行分裂，方法很简单，就是计算出所有节点的信息增益，然后选择信息增益最大的节点即可。

def find_best(self, condition=None):

然后就可以使用递归的方法建立决策树，每走一步就算一遍信息增益，然后建立一个子节点。最后结果返回整棵决策树。

def create_tree(self, condition=None):

最后，也就是最重要的一步，那就是预测值，因为构建决策树是为了把数据分类，最终目的就是预测未知数据的值。因为在Python中我使用字典套字典的数据类型来存储树，具体代码就是每到一个key就识别一次，如果value是最终结果的话就返回，如果还是字典的话就递归下去，直到获取到最终的值。

def predict(self, info, t={}):

到这里决策树建立完毕，接下来就要建立随机森林了。一般来说，随机森林有很多棵树，但是这里因为数据和个人能力的原因，就只分了两棵树。具体步骤也不难，就是把数据集均分成两个，分别建立各自的决策树，然后按各自的预测结果汇总，数量最多的结果作为最终的预测结果。如果两种决策结果一样多，就返回结果不确定。
在这里，代码实现的主要难点在于数据集的划分，以及对应预测数据的划分，因为是随机选择的划分方法，很容易出现两者划分方法不一致，这样预测过程就会出问题，代码就会经常报错。最后处理的方法就是在划分数据集的时候把划分方式记录下来，来适配预测数据的划分模式。具体代码比较繁琐，就不展示了。
下面是使用的主要函数。

def build_forest(self, info=None):
def predict(self, info):
def split_dict_by_key(dictionary, keys, result):
def split_dict_by_key2(dictionary, keys, result):

四、测试结果

在写完代码后，最重要的就是进行测试，来分析其正确性与性能。

这里的数据量比较小，只有28条数据和5个特征，但也足够用来简单实现决策树和随机森林了。

首先测试决策树，先输出决策树：

然后测试两条数据，分别是[‘rain’, ‘mild’, ‘normal’, ‘no’]和[‘sunny’,‘hot’,‘high’,‘no’]，然后给出预测结果。

与真实结果相吻合，这说明这棵决策树具备了一定的预测能力。

然后测试随机森林，先输出随机森林：

用元组来存储了这两棵树，然后就上面两条数据来进行预测，给出预测结果。

出现了两种不同的结果，分析具体的原因，是因为每棵树只分到了两个特征，而有可能这两个特征的信息增益比较低，不能很好地预测或者说预测效果很差。但当森林里有很多棵树时，这个问题可以大大缓解，并提升预测准确性。

下面给出总程序的预测结果：

五、分析与探讨

测试完算法后，来分析它的性能和优劣。首先分析ID3算法，ID3算法作为决策树算法较早出现的一个算法，在设计上有着它的瓶颈和缺陷。比如说ID3并没有考虑连续特征，对可取值数目较多的属性有倾向性，没有考虑过拟合的问题等。在ID3算法之后出现的决策树算法中，也借鉴了它ID3算法的思想。比如说C4.5算法，只不过把信息增益改为了信息增益比，就解决了倾向性问题和不能处理连续型数据的问题。又比如CART算法，生成二叉树，能同时处理连续型和离散型数据，还能处理数据缺失的问题，无疑是对以前算法的较大改进。

再来分析随机森林，虽然我程序里的随机森林比较低效，但事实上随机森林是有着比单棵决策树更好的预测能力，有着比决策树更加卓越的性能。比如说它可以判断特征的重要程度、不容易过拟合、实现简单、平衡误差等优势。这些优点使得随机森林成为机器学习中十分重要的算法。但即使如此，它也跟其他算法一样，有它本身的缺陷。其中最大的两个缺陷是1、随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。2、对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。因此，在使用不同的机器学习算法时，要充分考虑不同数据和算法的特点。没有最好的算法，只有最合适的算法。

附录：源代码

# 决策树和随机森林（Python实现）
import time
import math
import random
import pandas as pd

# 实现ID3算法
class ID3:
    # 初始化
    def __init__(self, data, label, d):
        self.data = data
        self.condition_data = []
        self.tree = None
        self.label = label
        self.Dict = d
        self.black = set()
        self.queue = []

    def entropy(self, condition=None):
        """
        计算熵
        :param condition: 条件
        :return:
        """
        if not condition:
            numEntries = len(self.data)
            Labels = dict()
            for value in self.data:
                currentLabel = value[self.label[-1]]
                if currentLabel not in Labels.keys():
                    Labels[currentLabel] = 1
                else:
                    Labels[currentLabel] += 1
            shang = 0.0
            for Label in Labels.keys():
                p = float(Labels[Label]) / numEntries
                shang -= p * math.log2(p)
            return shang
        else:
            self.condition_data.clear()
            for j in range(len(self.data)):
                if self.data[j][condition[0]] == condition[1]:
                    self.condition_data.append(self.data[j])
            numEntries = len(self.condition_data)
            Labels = dict()
            for value in self.condition_data:
                currentLabel = value[self.label[-1]]
                if currentLabel not in Labels.keys():
                    Labels[currentLabel] = 1
                else:
                    Labels[currentLabel] += 1
            shang = 0.0
            for Label in Labels.keys():
                p = float(Labels[Label]) / numEntries
                shang -= p * math.log2(p)
            return shang

    def entropy_condition(self, condition=None):
        """
        计算条件熵
        :param condition:条件
        :return:
        """
        shang = 0.0
        d = dict()
        for value in self.data:
            if value[condition] not in d.keys():
                d[value[condition]] = 1
            else:
                d[value[condition]] += 1
        for value in d.keys():
            p = float(d[value]) / len(self.data)
            shang += self.entropy((condition, value)) * p
        return shang

    def information_gain(self, condition):
        """
        计算信息增益
        :param condition: 第几个条件
        :return:信息增益
        """
        return self.entropy() - self.entropy_condition(condition)

    def find_best(self, condition=None):
        """
        寻找信息增益最大的一项
        :param condition: 条件
        :return: 最大项，以及最大项具体各个值的信息
        """
        Max = 0
        lab = None
        dic = {}  # 字典，如{'sunny':[1,1],...} 第一项为pos，第二项为neg
        for i in self.label[:-1]:
            if i in self.black:
                continue
            if self.information_gain(i) > Max:
                Max = self.information_gain(i)
                lab = i
        self.queue.append(lab)
        num = self.label.index(lab)
        for value in self.Dict[num][lab]:
            dic[value] = [0, 0]
        for value in self.data:
            if condition and value[condition[0]] != condition[1]:
                continue
            if value['playtennis'] == 'positive':
                dic[value[lab]][0] += 1
            else:
                dic[value[lab]][1] += 1
        return lab, dic

    def create_tree(self, condition=None):
        """
        建立决策树
        :param condition:条件
        :return: 返回决策树
        """
        my_tree = {}
        if len(self.black) <= len(self.label) - 2:
            lab, dic = self.find_best(condition)
            my_tree = {lab: {}}
            for value in dic.keys():
                if dic[value][1] <= 1:  # 基本全为pos
                    my_tree[lab][value] = 'positive'
                elif dic[value][0] <= 1:  # 基本全为neg
                    my_tree[lab][value] = 'negative'
                else:
                    self.black.add(lab)
                    my_tree[lab][value] = self.create_tree((lab, value))
                    if my_tree[lab][value] == {}:
                        if dic[value][0] > dic[value][1]:
                            my_tree[lab][value] = 'positive'
                        else:
                            my_tree[lab][value] = 'negative'
        return my_tree

    def predict(self, info, t={}):
        """
        根据信息预测最有可能的值
        :param info: 信息
        :param t: 辅助参数
        :return: 预测结果
        """
        self.black.clear()
        if t == {}:
            tree = self.create_tree()
        else:
            tree = t
        for i in tree.keys():
            num = self.label.index(i)
            if tree[i][info[num]] == 'positive':
                return 'positive'
            elif tree[i][info[num]] == 'negative':
                return 'negative'
            else:
                return self.predict(info, tree[i][info[num]])


# 扩展：随机森林(两颗决策树)
class Forest:
    # 初始化
    def __init__(self, data, Dict):
        self.data = data
        self.forest = []
        self.Dict = Dict
        self.information = []

    def build_forest(self, info=None):
        """
        建立随机森林（基于决策树）
        :param info: 条件
        :return: 随机森林
        """
        labels = list(self.data[0].keys())[:-1]
        one = random.sample(labels, len(labels) // 2)
        two = list(set(labels) - set(one))
        if info:
            l = []
            r = []
            for j in info:
                for i in self.Dict[:-1]:
                    if j in list(i.values())[0] and list(i.keys())[0] in one:
                        l.append(j)
                        break
                    if j in list(i.values())[0] and list(i.keys())[0] in two:
                        r.append(j)
                        break
            for i in self.Dict[:-1]:
                if one[0] == list(i.keys())[0]:
                    if l[0] in list(i.values())[0]:
                        break
                    else:
                        l.reverse()
                        break
            for i in self.Dict[:-1]:
                if two[0] == list(i.keys())[0]:
                    if r[0] in list(i.values())[0]:
                        break
                    else:
                        r.reverse()
                        break
            self.information = [l, r]
        one.append(list(self.data[0].keys())[-1])
        two.append(list(self.data[0].keys())[-1])
        one_dict = split_dict_by_key(self.data, one, list(self.data[0].keys())[-1])
        two_dict = split_dict_by_key(self.data, two, list(self.data[0].keys())[-1])

        one_dict2 = split_dict_by_key2(self.Dict, one[:-1], list(self.data[0].keys())[-1])
        two_dict2 = split_dict_by_key2(self.Dict, two[:-1], list(self.data[0].keys())[-1])
        one_tree = ID3(one_dict, one, one_dict2)
        two_tree = ID3(two_dict, two, two_dict2)

        o = one_tree.create_tree()
        t = two_tree.create_tree()
        self.forest.append(one_tree)
        self.forest.append(two_tree)
        return o, t

    def predict(self, info):
        """
        随机森林预测
        :param info: 条件
        :return: 预测值
        """
        if not self.forest:
            print("随机森林为", self.build_forest(info))
        else:
            self.forest.clear()
            self.build_forest(info)
        a = self.forest[0].predict(self.information[0])
        b = self.forest[1].predict(self.information[1])
        if a == b:
            return a
        else:
            return '不确定'


# 字典分裂的两个函数
def split_dict_by_key(dictionary, keys, result):
    sub_dict = [{keys[0]: i[keys[0]], keys[1]: i[keys[1]], result: i[result]} for i in dictionary]
    return sub_dict


def split_dict_by_key2(dictionary, keys, result):
    sub_dict = []
    keys.append(result)
    for i in keys:
        for j in dictionary:
            if i == list(j.keys())[0] and j not in sub_dict:
                sub_dict.append(j)
                break
    return sub_dict


if __name__ == '__main__':
    begin = time.time()
    # 读取数据以及准备数据
    data = pd.read_csv("data.csv")
    data = data.to_dict(orient='records')
    label = ['outlook', 'temperature', 'humidity', 'wind', 'playtennis']
    Dict = [{'outlook': ['sunny', 'overcast', 'rain']},
            {'temperature': ['hot', 'mild', 'cool']},
            {'humidity': ['high', 'normal']},
            {'wind': ['yes', 'no']},
            {'playtennis': ['positive', 'negative']}]
    print("以下是单纯的决策树算法：")
    # 实例化对象
    a = ID3(data, label, Dict)
    # 输出决策树
    print('决策树为', a.create_tree())
    # 给定一组值，预测结果
    info = ['rain', 'mild', 'normal', 'no']
    info2=['sunny','hot','high','no']
    print(f'[rain,mild,normal,no]预测结果为{a.predict(info)}')
    print(f'[sunny,hot,high,no]预测结果为{a.predict(info2)}')
    # 随机森林
    print("----------------------------\n以下是引入随机森林的算法：")
    f = Forest(data, Dict)
    print(f'[rain,mild,normal,no]预测结果为{f.predict(info)}')
    print(f'[sunny,hot,high,no]预测结果为{f.predict(info2)}')
    # 运行时间
    print("本次运行共花费了%.3f秒" % (time.time() - begin))

附录：csv

outlook,temperature,humidity,wind,playtennis

sunny,hot,high,no,negative

sunny,hot,high,yes,negative

overcast,hot,high,no,positive

rain,mild,high,no,positive

rain,cool,normal,no,positive

rain,cool,normal,yes,negative

overcast,cool,normal,yes,positive

sunny,mild,high,no,negative

sunny,cool,normal,no,positive

rain,mild,normal,no,positive

sunny,mild,normal,yes,positive

overcast,mild,high,yes,positive

overcast,hot,normal,no,positive

rain,mild,high,yes,negative

sunny,hot,high,no,negative

sunny,hot,high,yes,negative

overcast,hot,high,no,positive

rain,mild,high,no,positive

rain,cool,normal,no,positive

rain,cool,normal,yes,negative

overcast,cool,normal,yes,positive

sunny,mild,high,no,negative

sunny,cool,normal,no,positive

rain,mild,normal,no,positive

sunny,mild,normal,yes,positive

overcast,mild,high,yes,positive

overcast,hot,normal,no,positive

rain,mild,high,yes,negative