集成学习-Chapter1

summary

• 决策树的研究三点：特征选择、树的构造、树的剪枝。

• 从可能的决策树中直接选取最优决策树是NP完全问题。现实中采用启发式方法学习次优的决策树。

• CART是一颗二叉树，采用二元切割法。

• ID3的信息增益反映的是给定条件以后不确定性减少的程度，某特征在数据中表现得越多，意味着该特征确定性更高，条件熵越小，信息增益越大。ID3的缺点是每个样本的特征都不同（DNA），分类的泛化能力降低。其次是只能处理离散变量。

• C4.5与CART能处理连续型变量。C4.5会对数据做排序之后找到类别不同给的分割点作为切分点。

• 从应用的角度，ID3与C4.5只能用于分类任务，而CART可以应用于回归任务。

特征选择：

---

1．分类决策树模型是表示基于特征对实例进行分类的树形结构。决策树可以转换成一个if-then规则的集合，也可以看作是定义在特征空间划分上的类的条件概率分布。

2．决策树学习旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为

从可能的决策树中直接选取最优决策树是NP完全问题。现实中采用启发式方法学习次优的决策树。

• 决策树学习算法包括3部分：特征选择、树的生成和树的剪枝。常用的算法有ID3、
  C4.5和CART。

3．特征选择的目的在于选取对训练数据能够分类的特征。特征选择的关键是其准则。
常用的准则如下：

（1）样本集合对特征的信息增益（ID3）：

其中，是数据集的熵，是数据集的熵，是数据集对特征的条件熵。
是中特征取第个值的样本子集，是中属于第类的样本子集。
是特征取 值的个数，是类的个数。

（2）样本集合对特征的信息增益比（C4.5）

其中，是信息增益，是数据集的熵。

（3）样本集合的基尼指数（CART）

特征条件下集合的基尼指数：

4．决策树的生成。通常使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。

决策树的生成往往通过计算信息增益或其他指标，从根结点开始，递归地产生决策树。

这相当于用信息增益或其他准则不断地选取局部最优的特征，或将训练集分割为能够基本正确分类的子集。

---

数据熵：先计算每个标签下的数据数目与总数据数目的比。

def calc_ent(datasets):
    data_length = len(datasets)
    label_count = {}
    for i in range(data_length):
        label = datasets[i][-1]
        if label not in label_count:
            label_count[label] = 0
        label_count[label] += 1
    # log(对数，底数)
    ent = -sum([(p / data_length) * log(p / data_length, 2)
                for p in label_count.values()])
    return ent

特征条件熵：

# 经验条件熵,axis表示的是第axis特征
def cond_ent(datasets, axis=0):
    #数据的总数目
    data_length = len(datasets)
    # axis类特征里存在的特征类别：如【青年、老年】
    feature_sets = {}
    for i in range(data_length):
        feature = datasets[i][axis]
        if feature not in feature_sets:
            feature_sets[feature] = []
        feature_sets[feature].append(datasets[i])
    cond_ent = sum(
        [(len(p) / data_length) * calc_ent(p) for p in feature_sets.values()])
    return cond_ent