决策树
- 决策树是一种基本的分类与回归方法。
- 相比朴素贝叶斯分类，决策树的优势在于构造过程不需要任何领域知识或参数设置。
- 决策树是给定特征条件下，类的条件概率分布的一种表示。该条件分布定义在特征空间的划分（partition）上，特征空间被划分为互不相交的单元（cell），每个单元定义一个类的概率分布就构成了一个条件概率分布。（互斥并且完备）
香农熵
随机变量的熵定义为： \(H(X) = -\sum{p_i\log p_i}\) 熵越大，随机变量的不确定性就越大。 \(0 \leq H(X) \leq \log n\)
条件熵
随机变量X，Y的联合概率分布： $P(X=x_i,Y=y_j)=p_{ij}$ 条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。 \(H(Y|X) = \sum{p_iH(Y|X=x_i)}\) , where $p_i=P(X=x_i)$
信息增益
信息增益表示得知X的信息而使得Y的信息不确定性减少的程度： \(g(Y,A) = H(Y)-H(Y|A)\)
信息增益比
信息增益比=惩罚参数*信息增益 \(g_R(Y,A) = \frac{g(Y,A)}{H(A)}\) ##基尼指数（基尼不纯度）
- 表示在样本集合中一个随机选中的样本被分错的概率。
- Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。
- 基尼指数 = 样本被选中的概率 * 样本被分错的概率 \(Gini(p) = \sum_{k=1}^K{p_k(1-p_k)}=1- \sum_{k=1}^Kp_k^2\) $p_k$表示选中的样本属于k类别的概率，则这个样本被分错的概率是$1-p_k$
决策树的生成——ID3
- ID3是决策树的鼻祖，全称为Iterative Dichotomiser 3。建立在“奥卡姆剃刀”的基础上：越小型的决策树越优于大的决策树。
- ID3算法中根据信息增益评估和选择特征，每次选择信息增益最大的特征作为判断模块建立子结点。（自顶向下的贪心策略）
- ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可以通过裁剪合并相邻的无法产生大量信息增益的叶子节点。
- 缺点1：偏向于具有大量值的属性。就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的。
- 缺点2：不能处理连续分布的数据特征———》C4.5算法、CART算法
决策树的生成——C4.5
- 用信息增益率来选择属性
- （实质上是从划分属性中找出信息增益高于平均水平的属性，再从中选择增益率高的）
- 具有贪心性质：通过局部最优构造全局最优
- 优点1：克服了用信息增益选择属性时偏向选择取值多的属性的不足
- 优点2：在树构造过程中进行剪枝
- 优点3：能够完成对连续属性的离散化处理（二分法）
- 优点4：能够对不完整数据进行处理
- 优点5：分类规则易于理解，准确率较高
- 缺点1：效率低，在树的构造过程中，需要对数据集进行多次的顺序扫描和排序。
决策树的生成——CART
全分类决策树Classification and Regression Tree
- 基于基尼指数来选择属性：选择最小的属性
