集成学习-Chapter1

2019-08-10 本文已影响0人世界上的一道风

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）样本集合 $D$ 对特征 $A$ 的信息增益（ID3）：

$g(D, A)=H(D)-H(D|A)$

$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$

$H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)$

其中， $H(D)$ 是数据集 $D$ 的熵， $H(D_i)$ 是数据集 $D_i$ 的熵， $H(D|A)$ 是数据集 $D$ 对特征 $A$ 的条件熵。
$D_i$ 是 $D$ 中特征 $A$ 取第 $i$ 个值的样本子集， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集。
$n$ 是特征 $A$ 取值的个数， $K$ 是类的个数。

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

$g_{R}(D, A)=\frac{g(D, A)}{H(D)}$

其中， $g(D,A)$ 是信息增益， $H(D)$ 是数据集 $D$ 的熵。

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

$\operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$

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

$\operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)$

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

集成学习-Chapter1

summary

特征选择：

猜你喜欢

热点阅读