数据挖掘读书笔记--第八章(上)：分类：基本概念、决策树

程序员文章站 2024-02-08 21:52:46

...

散记知识点

——“分类是一种重要的数据分析形式”

1. 基本概念

1.1 分类的目的

通过构建分类模型来预测一些数据元组的类标签。

1.2 分类的过程

(1) 构建训练集

训练集由数据库中的元组和它们相关联的类标号组成。假设数据库 $D$ 中的每个元组 $X$ 有 $n$ 个属性 $A_{1}, A_{2}, . . ., A_{n}$ ，而每个属性对应一个值 $x_{n}$ ，则元组 $X = (x_{1}, x_{2}, . . ., x_{n})$ 。每个元组都有各自的类标号 $C$ 。
(2) 构造分类器

这一阶段称为学习阶段：通过有监督地学习训练集中的元组属性值与类别的关系，构造分类模型(分类器)。分类器相当于一个映射函数，给定元组预测类标： $y = f (X)$ ，其中 $y$ 为类标， $X$ 为元组。 $f (\cdot)$ 为分类器。
(3) 评估分类器

使用构建好的分类器作用在测试集上，通过分析预测准确率等评价指标来对分类器进行评估。

2. 决策树(Decision Tree)

2.1 决策树归纳

(1) 基本概念

决策树归纳是从有类标号的训练元组中学习决策树。
决策树是一种类似于流程图的树结构，其中，树的最顶层是一个根结点，每个内部结点（不包括树叶结点）表示在一个属性上的测试，每个分枝代表该测试的一个输出，而每个树叶结点（终端结点）存放一个类标号。决策树的一般形式如下：
数据挖掘读书笔记--第八章(上)：分类：基本概念、决策树

(2) 决策树的优点

构造简单，直观，可解释性强（容易被人理解）
可以处理高维数据
具有很好的准确率

(3) 决策树的构造过程

决策树一般采用贪心策略自顶向下递归的分治方式构造，从训练元组集和与之相关联的类标号开始，随着树的构建，训练集递归地划分成较小的子集。构造过程大致如下：

构造根结点，根据属性选择度量（例如ID3的信息增益）来选择合适的属性作为根结点。
根据根结点的属性值（可能是离散的，连续的或二值的）分枝，每个分枝代表元组在该属性下可能满足的条件。
判断经过分枝后的元组类别是否单一（为“纯”）：如果单一表示满足该分枝条件的元组都为一类，生成叶结点，不继续往下分。如果经过某分枝后元组类别仍不单一，则继续根据属性选择度量选择下一个属性生成内部结点，继续往下分枝。以此来构成一个树结构。
树停止生长条件：①当所有分枝后的元组都属于一个类别时，停止构造树。②当没有剩余的属性时，停止构造，而最后一个属性的分枝依然生成树叶结点，类别选择多数表决制，即用数据集中最多的一个类来标记该树叶结点。

2.2 ID3、C4.5决策树

(1) 信息增益与信息增益率

ID3决策树使用信息增益作为属性选择度量。

① 为了便于理解，引入信息论的知识

熵(Entropy)，热力学中表征混乱程度的度量。香农在信息论中定义了信息熵的概念：衡量一个随机变量对自身所包含信息的(平均)不确定性：

H (X) = \sum_{i = 1}^{n} P (x_{i}) \log \frac{1}{P (x_{i})} = - \sum_{i = 1}^{n} P (x_{i}) \log (P (x_{i}))

其中， $P (x_{i})$ 表示随机变量 $X$ 的概率分布。可以证明当 $X$ 的每个值出现的概率都相等时，信息熵达到最大，此时 $X$ 的不确定性达到最大。

在通信系统中，假设一个信道模型，信源 $X$ 具有 $n$ 个可能的符号数 ${x_{1}, x_{2}, . ., x_{n}}$ ， $P (x_{i})$ 表示信源发出符号 $x_{i}$ 的概率。

在实际通信之前，信宿不知道信源发出的具体信息，则信宿对信源信息的先验不确定性即是信息熵 $H (X)$ 。为了消除这种先验不确定性，二者进行通信。

进行通信之后，信宿收到来自信源的信息，此时先验不确定性转化为接收到一定信息之后的后验不确定性 $H (X / Y)$ 又称条件熵。先考虑接收到一个符号记为 $y_{j}$ 的情况，则单个 $y_{j}$ 条件熵为：

H (X / y_{j}) = \sum_{i = 1}^{n} P (x_{i} | y_{j}) \log \frac{1}{P (x_{i} | y_{j})} = - \sum_{i = 1}^{n} P (x_{i} | y_{j}) \log P (x_{i} | y_{j})

平均条件熵为：

H (X / Y) = \sum_{j = 1}^{n} P (y_{i}) \sum_{i = 1}^{n} P (x_{i} | y_{j}) \log \frac{1}{P (x_{i} | y_{j})} = - \sum_{j = 1}^{n} P (y_{j}) \sum_{i = 1}^{n} P (x_{i} | y_{j}) \log P (x_{i} | y_{j})

我们要消除或减小这种不确定性。一般不会完全消除，后验不确定性要小于先验不确定性(

H (X / Y) < H (X)

)。

如果后验不确定性正好等于先验不确定性，则表示信宿根本没有收到信息。
如果后验不确定性的大小等于0，则表示信宿收到的全部信息。

可见，我们使得后验不确定性 $H (X / Y)$ 尽可能小。由此引出互信息的定义：

I (X, Y) = H (X) - H (X / Y)

在信息论中，随机变量

X

和

Y

的互信息越大则二者的关系越紧密，

Y

对

X

的不确定性越小。我们尽可能使信源和信宿的互信息最大以此来实现无失真通信。互信息也即是衡量信宿消除对信源的不确定性大小。

② 考虑ID3属性选择度量

借助信息论的知识，就很容易理解ID3的信息增益了。首先考虑一个有许多元组 $X$ 构成的数据集 $D$ ，类别为 $C = {C_{1}, C_{2}, . . . C_{m}}$ 。则数据集对类别信息的先验不确定性为 $H (C)$ :

H (C) = - \sum_{i = 1}^{m} P (C_{i}) \log P (C_{i})

接下里考虑，将数据集 $D$ 按照属性 $A$ 划分，则考虑数据集 $D$ 经过属性值 $A_{j}$ 划分后对类别信息的后验不确定性为：

H (C / A_{j}) = - \sum_{i = 1}^{m} P (C_{i} / A_{j}) \log P (C_{i} / A_{j})

平均后验不确定性为：

H (C / A) = - \sum_{j = 1}^{n} P (A_{j}) \sum_{i = 1}^{m} P (C_{i} / A_{j}) \log P (C_{i} / A_{j})

而接着，为了消除属性对类别的不确定性，我们试图使得

H (C / A)

尽可能的小，引入互信息，当然这里变成了信息增益(Information Gain)：

G a i n (A) = H (C) - H (C / A)

显而易见，

G a i n (A)

表示通过对数据集进行属性划分，我们对类别信息的判断能Gain到多少”好处”。也即数据集通过属性划分能消除多少对类别的不确定性。
因此，在属性选择的过程中，优先选择属性对类别信息增益较大的属性放在决策树的靠顶层位置。
下面考虑一个例子：
数据挖掘读书笔记--第八章(上)：分类：基本概念、决策树

如上表所示，数据库中有14个训练元组，4个属性分别为：age、income、student和credit_rating。2个类别buy_computer：no和yes。首先计算类别信息的先验不确定性 $H (C)$ ，数据库中有9个元组yes类，5个元组no类则(这里忽略单位比特)：

H (C) = - (\frac{9}{14} \log_{2} \frac{9}{14} + \frac{5}{14} \log_{2} \frac{5}{14}) = 0.940

计算属性关于类别的后验不确定性即条件熵为

H (C / A)

，以属性age为例:

H (C / a g e) = - (\frac{5}{14} \times (\frac{2}{5} \log_{2} \frac{2}{5} + \frac{3}{5} \log_{2} \frac{3}{5}) + \frac{4}{14} \times (\frac{4}{4} \log_{2} \frac{4}{4} + \frac{0}{4} \log_{2} \frac{0}{4}) + \frac{5}{14} \times (\frac{3}{5} \log_{2} \frac{3}{5} + \frac{2}{5} \log_{2} \frac{2}{5})) = 0.694

则，属性age对类别的信息增益为： $G a i n (a g e) = H (C) - H (C / a g e) = 0.940 - 0.694 = 0.246$ ，同理可以计算得 $G a i n (i n c o m e) = 0.029, G a i n (s t u d e n t) = 0.151, G a i n (c r e d i t_{r} a t i n g) = 0.048$ ，因此在构造树的过程中，可以选择属性age作为根结点，然后以此选择较大的属性作为内部结点。

③ 连续值属性的离散化

对于属性是连续值的比如说age，当然数据库中储存的是离散值，但属性本身是连续的。对于这种情况要确定最佳的分裂点。
首先，对属性 $A = {a_{1}, a_{2}, . . ., a_{n}}$ 的值递增排序，确定要把属性区间分为几份，每个属性值之间的中点 $\frac{a_{i} + a_{i + 1}}{2}$ 为可能的分裂点。
假如要分成两份。给定一组年龄为{16， 24， 40， 64}，则可以产生三个分裂点{20，32，52}，则可以按照年龄小于某个分裂点和大于某个分裂点的值把属性值分为两组。
选出最佳分裂点，使得划分后的属性对类别的条件熵最小也即使得属性 $A$ 对类别的信息增益最大的划分。

④ C4.5的属性选择度量

C4.5使用信息增益率作为属性选择度量。ID3的信息增益倾向于选择属性值较多的属性。考虑一个极端的例子：

假设一个属性A对每个元组都有一个不同的属性值。如果根据该属性划分，则每个属性值就对应一个明确的分类。即属性A对类别的后验不确定性为0，信息增益自然最大。但这种划分没有意义，会令决策树的根结点直接产生很多叶结点停止了树往下生长。

信息增益率试图来克服这种倾向，使用属性自身的先验不确定性即属性自身的信息熵 $H (A)$ 将信息增益规范化得到信息增益率：

G a i n R a t e (A) = \frac{G a i n (A)}{H (A)}

属性自身的信息熵

H (A)

大小与自身的分布有关，当

A

的值越多，每个值的概率分布越接近，则

A

就越不稳定（先验不确定性越大），其本身的信息熵就越大。假设

A

有

n

个可能的值

a_{1}, a_{2}, . . ., a_{n}

，相应的概率分布为

p (a_{1})

则：

H (A) = - \sum_{i = 1}^{n} p (a_{i}) \log_{2} p (a_{i})

考虑极端情况，当

n = 1

时

p (a_{1}) = 1

，

H (A) = 0

，对自身不确定性为0。当

n

很大时，

p (a_{i}) = \frac{1}{n}

，

H (A)

达到最大，对自身越不确定。
信息增益率在信息增益的基础除以属性自身的信息熵，算是对信息增益倾向选择属性值多的属性的一种很好的折衷。

(2) 用Python简单构造ID3决策树

① 构造过程的伪代码
② Python代码实现

# -*- coding: utf-8 -*-
__author__ = "Yunfan Yang"

import numpy as np


def data_prep(filename):
    """数据预处理，属性列表以及数据元组列表"""
    with open(filename,'r') as f:
        raw_data = f.read()    # 读取数据
    # print(raw_data)
    data_list = raw_data.split('\n')[:-1]   # 将文本数据转换为列表

    Attributes = []   # 属性和类别名称列表
    X_list = []          # 数据元组列表
    for i in range(len(data_list)):
        X = []
        if i == 0:
            Attributes = data_list[i].split(',')   # 创建属性列表
        else:
            X = data_list[i].split(',')   # 元组列表
            X_list.append(X)
    return Attributes, X_list


def get_attribute_value(Attributes, X_list):
    """获取每个属性的属性值，返回一个母列表，其中的子列表为每个属性的属性值"""
    Attributes_values = []       # 创建列表不重复的储存每个属性和类别值
    for i in range(len(Attributes)):
        value_list = []
        for X in X_list:
            if X[i] not in value_list:
                value_list.append(X[i])
        Attributes_values.append(value_list)   # 为了方便计算，把类别放在列表的最后
    # print(Attributes_values)
    return Attributes_values


def get_entropy(p_list):
    """给定一个概率分布列表计算熵"""
    entropy  = 0
    for p in p_list:
        if p != 0:
            entropy += -p * np.log2(p)

    return entropy


def calculate_info_gain(attributes_values, X_list, attributes, classes, classes_values):
    """统计数据元组中的属性、类别计数以及属性条件下的类别计数"""

    # 先计算类别的先验熵
    classes_count = np.zeros([len(classes_values)])
    for i in range(len(classes_values)):  # 对于每个属性（类别）值
        for X in X_list:  # 遍历整个数据元组
            if X[-1] == classes_values[i]:  # 如果数据元组的属性值等于每个属性值，则属性计数加1
                classes_count[i] += 1
    classes_p = classes_count / np.sum(classes_count)  # 每个属性值对应类别的条件概率
    classes_entropy = get_entropy(classes_p)

    # 再计算信息增益
    Info_Gains = {}  # 储存每个属性对类别的信息增益
    for i in range(len(attributes_values)):  # 遍历属性类别列表中除了第一项之外的属性类别值
        attribute_count = np.zeros([len(attributes_values[i])])   # 每个属性（类别）初始化计数
        value_entropy = []
        for j in range(len(attributes_values[i])):     # 对于每个属性（类别）值
            condition = np.zeros([len(attributes_values[-1])])

            for X in X_list:                            # 遍历整个数据元组
                if X[i+1] == attributes_values[i][j]:   # 如果数据元组的属性值等于每个属性值，则属性计数加1
                    attribute_count[j] += 1
                    for k in range(len(classes_values)):  # 遍历类别值，在满足一定属性值条件下的类别计数
                        if X[-1] == classes_values[k]:
                            condition[k] += 1

            condition_p = condition / np.sum(condition)   # 每个属性值对应类别的条件概率

            value_entropy.append(get_entropy(condition_p))

        attribute_p = attribute_count / np.sum(attribute_count)
        condition_entropy = np.sum(list(map(lambda a,b:a*b, value_entropy, attribute_p)))   # 按照从大到小的顺序排列
        info_gain = classes_entropy - condition_entropy
        info_gain = info_gain.round(4)   # 保留4位小数
        Info_Gains[attributes[i]]= info_gain

    info_gains = sorted(Info_Gains.items(),reverse=True,key=lambda x:x[1])  # 按照从小到大排列
    # 得到信息增益形如 [('age', 0.2467), ('student', 0.1518), ('credit_rating', 0.0481), ('income', 0.0292)]
    return info_gains


def all_same(listX):
    """判断一个列表中的值是否全相等"""
    X1 = listX[0]
    for X in listX:
        if X == X1:
            continue
        else:
            return False
    return True


def generate_tree(X_list, info_gains, attributes, classes, attributes_values, classes_values):
    """生成决策树"""

    # 从数据集中获取类别形成一个列表
    classList = [X[-1] for X in X_list]

    # 递归终止条件1：数据集内所有元组都为一类
    if all_same(classList):
        return classList[0]

    # 递归终止条件2：没有特征剩余
    if len(info_gains) == 1:
        # 返回投票最多的类别
        classes_count ={}
        for value in classes_values:
            classes_count[value] = 0
            for c in classList:
                if value == c:
                    classes_count[value] += 1
        votes = sorted(classes_count.items(), reverse=True, key=lambda x:x[1])
        # print(votes)
        return votes[0][0]

    # 选择信息增益最大的属性
    opt_attribute = info_gains[0][0]

    # 创建结点子树
    Tree = {opt_attribute:{}}

    # 剔除该属性
    info_gains.pop(0)

    # 获取该属性的属性值
    attribute_index = attributes.index(opt_attribute)  # 获取最佳属性的索引值
    attribute_values = attributes_values[attribute_index]   # 根据索引从属性值列表中取属性值

    split_X_list ={}              # 划分的数据集字典，键为每个属性值，值为包含该属性值得每个数据元组
    for value in attribute_values:     # 遍历每个属性值
        split_X_list[value] = []       # 经过属性值划分的数据元组列表
        for X in X_list:               # 遍历数据集
            if X[attribute_index+1] == value:
                split_X_list[value].append(X)

    for value in attribute_values:
        X_list = split_X_list[value][:]  # 在每个划分后得数据集上递归地创建结点子树
        Tree[opt_attribute][value] = generate_tree(X_list, info_gains, attributes, classes, attributes_values, classes_values)

    return Tree


if __name__=="__main__":

    filename = 'raw_data.csv'  # 读取文件，数据预处理

    Attributes, X_list = data_prep(filename)  # 对于每个X，第一个值时标号，最后一个是类别，中间都是属性值
    # print(Attributes)
    # print(X_list)
    attributes = Attributes[1:-1]  # Attributes第一项为数据组标号，最后一项为类别，中间为各种属性
    classes = Attributes[-1]

    Attributes_values = get_attribute_value(Attributes, X_list)

    # 把属性和类别的值分开
    attributes_values = Attributes_values[1:-1]  # 单纯的属性值列表，储存每个属性的属性值，
    classes_values = Attributes_values[-1]  # 单纯的类别列表，储存类别信息
    # print(attributes_values)
    # print(classes_values)
    info_gains = calculate_info_gain(attributes_values, X_list, attributes, classes, classes_values)

    myTree = generate_tree(X_list, info_gains, attributes, classes, attributes_values, classes_values)

    print("\n\n根据该数据集生成的ID3决策树为：")
    print(myTree)

运行结果为：

根据该数据集生成的ID3决策树为：
{'age': {'youth': {'student': {'no': 'no', 'yes': 'yes'}}, 'middle_aged': 'yes', 'senior': {'credit_rating': {'fair': 'yes', 'excellent': 'no'}}}}

附课本P218页数据表格式为.csv: raw_data.csv

2.3 CART决策树

(1) 基尼指数
CART决策树使用基尼指数(Gini index)作为属性选择度量，用来衡量数据分区或训练元组集D的不纯度，定义为：

G i n i (D) = 1 - \sum_{i = 1}^{m} p_{i}^{2}

其中，

p_{i}

是数据元组为

C_{i}

类的概率，

p_{i} = | C_{i, D} | / | D |

用来估计。

CART采用二元划分，每个具有 $v$ 个属性值的属性有 $C_{v - 1}^{2}$ 个可能的二元划分，进行划分数据集。假设某个二元划分将数据集 $D$ 划分为 $D_{1}$ 和 $D_{2}$ ，则给定该划分， $D$ 的基尼指数为：

G i n i_{A} (D) = \frac{| D_{1} |}{| D |} G i n i (D_{1} ） + \frac{| D_{2} |}{| D |} G i n i (D_{2})

对于每个属性，考虑每种可能的二元划分。

对于离散值属性，选择该属性产生最小基尼指数的子集作为它的分裂子集。
对于连续值属性，处理方法同信息增益，考虑每个可能的分裂点，选择产生最小基尼指数的点作为该属性的分裂点。

对离散或连续值属性 $A$ 的二元划分导致的不纯度降低为：

Δ G i n i (A) = G i n i (D) - G i n i_{A} (D)

最大化不纯度降低

Δ G i n i (A)

（或等价地，具有最小基尼指数）的属性选为分裂属性。该属性和它的分裂子集（对于离散值的分裂属性）或分裂点（对于连续值的分裂属性）一起形成分裂准则。

基尼指数偏向于多值属性，并且当类的数量很大时会有困难。同时它还倾向于导致相等大小的分区和纯度。

(2) 构造过程

构造过程同ID3决策树构造类似，计算每个属性每个可能的二元划分的基尼系数，选择最小基尼系数划分的属性作为根结点。分枝为两个二元划分。如果满足决策树终止的两个条件，则分枝连接树叶节点为类别；否则，分枝连接子树。在每个二元划分后的数据集 $D_{1}$ 和 $D_{2}$ 上递归地构造子树。

2.4 决策树剪枝

决策树建立时，许多分枝可能反映训练数据集的噪声或离群点，造成过拟合的问题。树剪枝试图剪掉这些分枝，从而消除过拟合提高测试集准确率。

常用的两种剪枝方法：先剪枝和后剪枝

先剪枝：通过提前停止树的构建实现剪枝，停止时，分枝连接的结点都将成为叶结点（叶结点为剩余投票最多的分类）。
后剪枝：在构造完全的树上剪去子树，通过替换某些分枝连接的子树为叶结点（子树中最频繁的类标记）来实现剪枝。

后剪枝所需要的计算比先剪枝多，但更常用，能产生更可靠的树。

CART使用代价复杂度剪枝算法（后剪枝的一种）：该方法把树的复杂度看作树中树叶结点个数和数的错误率函数。从树的底部开始，对于某个内部节点 $N$ ，计算 $N$ 的子树的代价复杂度和该子树剪枝后 $N$ 的子树的代价复杂度，比较两个值，如果减去 $N$ 的子树后导致较小的复杂度，则减掉该树；否则，保留该树。