机器学习系列03-决策树算法

Posted by Naah on Saturday, Oct 05,2019 15:06:16

1 概述

决策树本质上是数据结构中的,不过有一些区别是,树的根节点中间节点都是判断,而树的条件,而所有叶子节点都是一些结果。其实本质上就是if-else,不过这个if-else是通过算法来构建出的树状if-else

一些决策树采用二分法划分数据,我们在这里主要使用ID3算法进行划分数据集,后续还会介绍C4.5CART的决策树算法

2 优缺点

  1. 优点:计算复杂度不高,输出结果容易理解,对中间值的缺失不敏感,可以处理不相关特征数据,可以保存成模型
  2. 缺点:可能参数过渡匹配问题
  3. 适用数据范围:数值型和标称型

3 数据准备

3.1 数据准备

  1. 要测试的向量。是我们要进行预测的数据
  2. 训练数据集,包含目标向量的特征数据集
  3. 各个特征的标签名词

3.2 信息增益

划分数据集的最大原则是将无序的数据变得更加有序。那么使用信息论来度量信息就是一种组织杂乱无章数据的一种方法。

在划分数据集之前之后,信息发生的变化,我们称为信息增益,划分数据集时,获取信息增益最高的特征就是最好的选择。那么如何计算信息增益呢?这里我们可以通过来计算数据的信息增益。

除了这个方法外,还有个叫基尼不纯度的方法去度量集合的无序程度,就是从一个数据集中随机选取子项,度量其被错误分类到其他分组的概率,这里就不详细说这个方法啦。

3.3 熵

熵:一般意义上指的都是信息熵。就是信息的期望度,换个说法,就是信息的不确定性,因为不确定,所以期望。期望度越大,熵越高(不确定性越大,熵越高),反之,熵越高,混合的数据越多。(除了信息熵,还有相对熵

下面是熵的计算公式

  1. Σ:求和,不赘述了
  2. n:特征的数量
  3. p(xi):这个特征值出现概率

下面的代码就是用来求熵的:

import math
class trees(object):
    def cal_shannonnt_entropy(self, data_set):
        """
        通过最后一列计算香农熵(熵:信息的期望度)
        公式:
        X 标签出现的概率
        n 标签分类的数量
               ---
        H = - \     n
              /     i=1   P(Xi)*log  P(Xi)
              ---                  2
        :param data_set: 数据集
        :return: 香农熵
        """
        # 数据行数
        data_set_len = len(data_set)
        # 数据中的 标签——数量
        labels_count = {}
        # 遍历数据
        for vec in data_set:
            #  获取标签
            current_label = vec[-1]
            # 初始化标签
            if current_label not in labels_count.keys():
                labels_count[current_label] = 0
            # 标签计数
            labels_count[current_label] += 1

        #  香农熵
        shannon_entropy = 0.0
        for key in labels_count:
            # 计算标签出现的概率P(Xi)
            prob = float(labels_count[key]) / data_set_len
            # 计算累减P(Xi)*log2P(Xi)
            shannon_entropy -= prob * math.log(prob, 2)

        return shannon_entropy

3.4 划分数据集

分类算法除了要测量信息熵,还要划分数据集度量划分数据集的熵来判断当前是否争取的划分数据集。我们将每个特征划分数据集的结果计算一次熵,然后判断按照哪个特征划分数据集是最好的。

其实就是计算信息增益,算法就是矩阵的基础熵-划分该特征后的熵,这样对每个特征的信息增益求出后,取最大的那个,就是信息增益最好的那个

下面的代码,就是如何划分数据集和如何选择信息增益最好的那个!

class trees(trees_3_1_1):
    def split_dataset(self, dataset, axis, value):
        """
        筛选并重新划分数据集
        axis位置等于value 并且 将这列去除
        :param dataset: 数据集
        :param axis: 位置
        :param value: 值
        :return:
        """
        ret_dataset = []
        for vec in dataset:
            # 如果某个位置等于某值
            if vec[axis] == value:
                # 将这列抽出不要,生成新的向量
                temp_vec = vec[:axis]
                temp_vec.extend(vec[axis + 1:])

                # 向量追加到矩阵
                ret_dataset.append(temp_vec)
        return ret_dataset

    def choose_best_feature_to_split(self, dataset):
        """
        计算最佳的数据集划分方式(本质上就是找到熵最小的那个特征字段)
        通过比较各特征的信息增益来计算(信息增益:基础熵-划分该字段后的熵)
        :param dataset:
        :return:
        """

        # 向量维度(矩阵列长)
        feature_count = len(dataset[0]) - 1
        # 计算基础香农熵
        base_entropy = self.cal_shannonnt_entropy(dataset)
        # 最佳信息增益
        best_info_gain = 0.0
        # 最佳特征位置
        best_feature_index = -1

        # 遍历每一列
        for i in range(feature_count):
            # 将所有数据的某列值提取成一个向量
            feature_list = [example[i] for example in dataset]
            # set去重
            unique_vals = set(feature_list)
            new_entropy = 0.0

            # 遍历去重后的数据
            # 计算每种划分方式的熵
            for value in unique_vals:
                # 筛选数据生成子数据集
                sub_data_set = self.split_dataset(dataset, i, value)

                # 计算子数据集的熵
                prob = len(sub_data_set) / float(len(dataset))
                new_entropy += prob * self.cal_shannonnt_entropy(sub_data_set)

            # 计算信息增益
            info_gain = base_entropy - new_entropy
            # 判断最大信息增益
            if info_gain > best_info_gain:
                # 保存最大信息增益
                best_info_gain = info_gain
                # 保存最大信息增益特征的位置
                best_feature_index = i
        return best_feature_index

4 原理

4.1 算法思想

  1. 准备上方所说的数据
  2. 输入新数据后,首先对特征标签向量进行复制一份,这样对这个标签向量修改时,不会影响原有结构
  3. 对数据集的最后一列进行抽取,也就是要把我们的最后的分类抽出,如果只有一个分类的话,直接返回
  4. 计算当前数据集的最佳划分方式,并获取这个特征的特征标签,以这个标签作为根节点创建一棵数
  5. 在特征标签变量中删除这个最佳划分方式的特征的标签
  6. 将所有数据的这个最佳划分方式的特征这一列的值抽取出来,然后去重
  7. 再对这个去重后的集合进行遍历,以这些特征值进行筛选划分数据集,然后递归计算这些数据集,返回的树作为当前树的字树
  8. 直到遍历完为止

5 代码

class trees(object):
    def create_dataset(self):
        dataSet = [
            [1, 1, 'yes'],
            [1, 1, 'yes'],
            [1, 0, 'no'],
            [0, 1, 'no'],
            [0, 1, 'no']
        ]
        labels = ['不浮出水面能生存', '有脚蹼']
        return dataSet, labels
        
    def majority_cnt(self, class_list):
        """
        返回出现次数最多的标签
        :param class_list:
        :return:
        """
        class_count = {}
        for vote in class_list:
            if vote not in class_count.keys():
                class_count[vote] = 0
            class_count[vote] += 1
        sorted_class_count = sorted(class_count.items(), operator.itemgetter(1), reverse=True)
        return sorted_class_count[0][0]

    def create_tree(self, dataset, labels):
        """
        生成决策树
        :param dataset: 数据集
        :param labels: 便签
        :return:
        """
        # 创建一个新的list,不对原有labels操作
        labels=list(labels)
        # 生成分类列表
        class_list = [example[-1] for example in dataset]

        # 如果只有一个分类则返回
        if class_list.count(class_list[0]) == len(class_list):
            return class_list[0]

        # 如果只有一列的话,返回出现次数最多的标签
        if len(dataset[0]) == 1:
            return self.majority_cnt(class_list)

        # 计算最佳的划分方式的特征字段位置
        best_feature_index = self.choose_best_feature_to_split(dataset)

        # 获取该字段所以代表的标签
        best_feature_label = labels[best_feature_index]

        # 初始化树
        tree = {best_feature_label: {}}

        # 删除最佳划分方式字段的标签
        del (labels[best_feature_index])

        # 将最佳划分方式的一列抽出来
        feat_val = [example[best_feature_index] for example in dataset]

        # set去重
        unique_val = set(feat_val)
        for val in unique_val:
            sub_labels = labels[:]
            # 通过最佳特征字段筛选并重新划分数据集
            sub_dataset = self.split_dataset(dataset, best_feature_index, val)
            # 递归遍历
            tree[best_feature_label][val] = self.create_tree(sub_dataset, sub_labels)

        return tree

if __name__ == '__main__':
    tree = trees()
    dataset, labels = tree.create_dataset()
    m_tree = tree.create_tree(dataset, labels)
    print(m_tree)

上面的代码的结果是{'不浮出水面能生存': {0: 'no', 1: {'有脚蹼': {0: 'no', 1: 'yes'}}}}! 这就是我们通过算法构建出的决策树,通过杂乱的数据来清洗的构造出这个决策树,是不是很神奇呢?

6 实战

经过上面的简单计算后,也进入我们的实战项目了!下面我们将构建一个预测隐形眼镜类型的简单小项目吧!

6.1 数据准备

首先,我们的数据可以通过我的github进行下载![点我]() digits目录存放的就是我们所要需要的数据!

6.2 算法准备

首先我们在写程序的时候,要经历哪些步骤呢? 1. 查看数据,数据是怎么样子的? 2. 写特征转化算法,将单条数据转化为向量,多条数据转化为矩阵 3. 输入训练数据,构建决策树 4. 查看决策树的结构


class trees(objecy):
    # 将上面的算法copy过来就行
    pass
if __name__ == '__main__':
    # 隐形眼镜数据集
    filename = "../data/lenses.txt"
    trees = trees()
    lenses = []
    with open(filename, 'r') as fr:
        lenses = [line.strip().split('\t') for line in fr.readlines()]
    labels = ["年龄", "病因", "散光", "泪液率"]
    tree = trees.create_tree(lenses, labels)
    print(tree)

最后我们得到下面的决策树,貌似匹配选项可能太多,有点复杂! 其实这个问题就叫做过渡匹配。 我们其实可以通过裁剪决策树,去掉一些不必要的叶子节点,如果子节点只能增加少许信息,则可以删除该节点。

{
    "泪液率": {
        "减少": "不适合戴",
        "正常": {
            "散光": {
                "yes": {
                    "病因": {
                        "近视": "硬的",
                        "远视": {
                            "年龄": {
                                "年轻": "硬的",
                                "老人": "不适合戴",
                                "中年": "不适合戴"
                            }
                        }
                    }
                },
                "no": {
                    "年龄": {
                        "年轻": "软的",
                        "老人": {
                            "病因": {
                                "近视": "不适合戴",
                                "远视": "软的"
                            }
                        },
                        "中年": "软的"
                    }
                }
            }
        }
    }
}