决策树_天择随心记

工作原理

决策树通过对训练数据进行学习，构建出一个树形结构。在进行预测时，从根节点开始，根据样本的特征值对每个内部节点的测试条件进行判断，沿着满足条件的分支向下移动，直到到达叶节点，叶节点所代表的类别或值即为预测结果。

信息熵

信息熵（Information Entropy）是信息论中的一个核心概念，由克劳德·香农（Claude Shannon）提出，用于衡量随机变量的不确定性或信息量。它描述了系统的不确定性程度，熵越大，不确定性越高；熵越小，不确定性越低。

定义
对于一个离散随机变量 X ，其取值为 $( x_1, x_2, \dots, x_n )$ ，对应的概率分布为 $P(X = x_i) = p_i$
信息量 $I(x_i) = -log_2p(x_i)$

信息熵 $H(X) = -\sum_{i=1}^{n} p_i \log_2 p_i$

其中：

$p_i$ 是事件 $x_i$ 发生的概率。
$\log_2$ 是以 2 为底的对数，单位为比特（bit）。如果使用自然对数（ $\ln$ ），单位则为纳特（nat）。

直观理解
- 熵越大：随机变量的不确定性越高，信息量越大。
- 例如，抛一枚均匀的硬币，正反面概率均为 0.5，此时熵最大，不确定性最高。
- 熵越小：随机变量的不确定性越低，信息量越小。
- 例如，一枚硬币总是正面朝上（概率为 1），此时熵为 0，没有不确定性。

性质
- 非负性： H(X) ≥ 0，当且仅当 X 是确定事件时， H(X) = 0 。
- 最大值：对于 ( n ) 个可能的事件，当所有事件概率相等时 $(即 p_i = \frac{1}{n} )$ ，熵达到最大值 $\log_2 n$ 。
- 可加性：如果两个随机变量 X 和 Y 是独立的，则它们的联合熵 H(X, Y) = H(X) + H(Y)。

条件熵

条件熵 $H(Y|X)$ ：表示在已知特征 $X$ 的条件下，目标变量 $Y$ 的不确定性。
```
 $H(Y|X) = -\sum_{j=1}^{m} p(x_j) \sum_{i=1}^{k} p(y_i|x_j) \log_2 p(y_i|x_j)$ 
```

其中， $p(x_j)$ 是特征 $X$ 取值为 $x_j$ 的概率， $p(y_i|x_j)$ 是在 $X = x_j$ 的条件下 $Y = y_i$ 的概率。

信息增益

信息增益 $IG(Y, X)$ ：表示特征 X 对目标变量 Y 的不确定性的减少量。
```
 $IG(Y, X) = H(Y) - H(Y|X)$ 
```

代码实例

import numpy as np
from collections import Counter

def calcInfoGain(feature, label, index):
    '''
    计算信息增益
    :param feature:测试用例中字典里的feature，类型为ndarray
    :param label:测试用例中字典里的label，类型为ndarray
    :param index:测试用例中字典里的index，即feature部分特征列的索引。该索引指的是feature中第几个特征，如index:0表示使用第一个特征来计算信息增益。
    :return:信息增益，类型float
    '''
    # 计算熵
    def entropy(labels):
        counts = Counter(labels)
        total = len(labels)
        entropy_value = -sum((count / total) * np.log2(count / total) for count in counts.values())
        return entropy_value
    # 计算条件熵
    def conditional_entropy(features, labels, feature_index):
        # 获取当前特征的所有取值
        feature_values = [sample[feature_index] for sample in features]
        unique_values = set(feature_values)
        total = len(features)
        cond_entropy = 0
        # 对每个特征取值计算子集熵
        for value in unique_values:
            subset_labels = [label for i, label in enumerate(labels) if features[i][feature_index] == value]
            subset_entropy = entropy(subset_labels)
            weight = len(subset_labels) / total
            cond_entropy += weight * subset_entropy
        return cond_entropy
    # 计算信息增益
    def information_gain(features, labels, feature_index):
        # 计算目标变量的熵
        total_entropy = entropy(labels)
        # 计算条件熵
        cond_entropy = conditional_entropy(features, labels, feature_index)
        # 信息增益 = 总熵 - 条件熵
        return total_entropy - cond_entropy
    return information_gain(feature,label,index)

基尼系数

基尼系数（Gini Index）是衡量数据集纯度的指标，常用于决策树算法（如 CART）中选择最优特征进行划分。它表示从数据集中随机抽取两个样本，其类别标签不一致的概率。基尼系数越小，数据集的纯度越高。

 $\text{Gini}(p) = 1 - \sum_{i=1}^{K} p_i^2$

其中：

$p_i$ 是第 $i$ 个类别在数据集中的比例。
$\sum_{i=1}^{K} p_i = 1$ 。

基于数据集D与特征a的基尼系数

 $\text{Gini}(D,a) = \sum_{j=1}^{m} \frac{|D_j|}{|D|} \text{Gini}(D_j)$

其中：

$D$ 是当前节点的数据集。
$D_j$ 是特征取值为第 $j$ 个子集。
$m$ 是特征a的取值个数。

import numpy as np

def calcGiniCoefficient(feature, label, index):
    """
    计算指定特征列的基尼系数
    :param feature: 测试用例中字典里的feature，类型为ndarray
    :param label: 测试用例中字典里的label，类型为ndarray
    :param index: 测试用例中字典里的index，即feature部分特征列的索引
    :return: 基尼系数，类型float
    """
    f = np.array(feature)
    # 获取指定特征列的值集合
    f_set = set(f[:, index])
    total_samples = len(feature)
    gini = 0

    for value in f_set:
        # 找出特征值等于当前值的样本索引
        sub_indices = np.where(f[:, index] == value)[0]
        sub_label = label[sub_indices]
        sub_samples = len(sub_label)
        # 计算当前子集在总样本中的占比
        p = sub_samples / total_samples
        # 计算子集中各类别的占比
        unique_labels, counts = np.unique(sub_label, return_counts=True)
        label_proportions = counts / sub_samples
        # 计算当前子集的基尼指数
        sub_gini = 1 - np.sum(label_proportions ** 2)
        # 累加各子集的基尼指数
        gini += p * sub_gini

    return gini