除线性模型中的逻辑斯谛克回归（包括梯度下降等）、多分类问题之外，分类算法学习主要还包括：决策树，贝叶斯分类器，k近邻算法，支持向量机，神经网络等；下面学习一下决策树。

决策树（decision tree）也是一种无参监督学习方法，其目的是创建一种模型从数据特征中学习简单的决策规则来预测一个目标变量的值。。以树状图为基础，是一系列的if-then语句，它可以用于分类也可以用于回归。 优点是：便于理解，可以可视化。分类速度快。不需要数据规范化，训练需要数据少。既能处理连续属性也可以处理离散属性。 缺点：模型可能会复杂，从而过拟合，可剪枝等方法避免。单个决策树可能不稳定，可以通过集成学习缓解。集成学习缓解单个决策树可能不是全局最优的问题。最好学习前，先对数据进行平衡处理。 1、决策树：一颗决策树包含一个根节点，若干个内部节点，和若干个叶节点，决策结果对应的就是叶结点，其他每个结点都对应一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根节点包含样本全集。从根结点到叶每一个结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强，处理未知结果样本能力强的决策树，基本流程就是简单的分而治之。 2、决策树算法流程流程： 训练集D有m个样本，属性集A有d个判断属性。 1、生成结点node 2、如果训练集D中所有样本全属于同一类别C，那么将当前结点node标记为C类叶结点，返回（情形1）。 3、如果属性集A为空集或者训练集D各个样本在A上所有属性的取值都相同，那么将node标记为叶结点，其类别标记为D中样本数最多对应的那类，进行递归返回（情形2）。 4、若2,3都不符合，那么遍历：从A中选择最优划分属性a，对于a所对应的每个值av（离散属性按值划分，连续属性按大小分）生成分支结点，Dv为该结点上的样本子集。 5、如果Dv是空集，那么其对应的分支结点标记为叶结点，其类别标记为（父结点）D中样本最多的类（将父结点的样本分布当成当前结点的先验分布），若所有都为空，那么父结点就是叶子；进行递归返回（情形3）。 6、否则，在Dv上再次执行4——14步骤，但是这时A中要去除最优属性a，重新再选最优属性。 7、在a的每个值av都遍历结束后结束。

我们希望随着划分过程的不断进行，决策树的分支结点 包含的样本尽可能属于同一类别，纯度越来越高，最后达到一定程度不用再进行划分，生成叶结点。所以我们要选择最佳划分属性，主要看该属性对数据的划分是不是更有区分性，更有区分性则划分后纯度越大。那么如何选择最佳属性呢，利用下面的指标进行判断。 （1）信息增益 信息熵（information entropy)：度量样本集合纯度的一种指标。样本集合为D，信息熵Ent(D)的值越小，则D的纯度越高。 信息增益（information gain）：它是将样本集D按特征A的值划分为两个独立子数据集D1和D2后，两个数据集信息熵的加权和为当前样本集D的信息熵。可计算出用属性a对样本集D进行划分所获得的“信息增益”Gain(D,a），就是划分前后信息熵的减少量。一般而言，信息增益越大，意味着使用属性a划分获得的纯度提升越大。选择使得信息增益最大的划分。ID3决策树使用该方法。 属性选择：a* = argmaxGain(D,a) , a属于A。 （2）增益率 ￥增益率￥：信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5决策树不直接使用信息增益，而是使用“增益率”来选择最优划分属性 增益率定义为：Gain_ratio(D,a)=Gain(D,a) / IV(a) 。 选择方法：但要注意：增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法不是直接选择增益率最大的候选划分属性，而是使用一个启发式方法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。 （3）基尼指数 ￥基尼指数￥：CART决策树使用基尼指数（Gini index)来选择划分属性。 基尼值：数据集D的纯度可以用基尼值来度量Gini(D)。其反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此基尼值越小，数据集D的纯度越高。 基尼指数：属性a的基尼指数定义为：Gini_index(D,a) 选择方法：在候选属性集合A中，选择那个使得D划分后基尼指数最小的属性作为最优划分属性，a* = arg min Gini_index(D,a)。 a属于A 。

决策树过拟合：决策树中的过拟合，为了尽可能正确分类训练样本，结点划分过程不断重复，有时会造成决策树分支过多，这时就可能因为训练样本学习得太好了，使得训练集的一些特点被当做所有数据都具有的一般性质而导致过拟合。 剪枝（Pruning)：是决策树学习算法对付过拟合的主要手段，通过主动去掉一些分支来降低过拟合的风险。 剪枝策略： （1）预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计：若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点。 @@预剪枝使得决策树的很多分支都没有展开，不仅降低了过拟合的风险，还显著减少了决策树训练时间开销和测试时间开销。但其贪心的本质禁止了有些分支的展开，这些分支的展开虽然对当前泛化能力提升没用，但是后续会有好的作用，所以也带来了欠拟合的风险。 （2）后剪枝：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该非叶结点对应的子树替换为叶结点能带来整棵决策树泛化性能的提升，则将其替换为叶结点。 @@后剪枝比预剪枝保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝。但是其在生成决策树后进行，并自底向上对所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大。 泛化能力提升判断：留出法，也就是预留一部分数据作为验证集来进行性能评估。

（1）以上只讨论了基于离散属性（属性的可能取值为离散的，有限个数）来生成决策树，现实学习任务中常会遇到连续属性，但是连续属性可取值数目不再有限，有必要讨论如何在决策树学习中使用连续属性。 连续属性离散化技术：最简单的策略是采用二分法对连续属性进行处理，C4.5决策树中采用该机制。具体就是：对于连续属性，我们将该属性a在D上出现的n个不同的取值，将其从小到大进行排序，划分点为连续的两个之间的值的平均值，一共有n-1个划分点，这样便将其离散化为n-1个属性值了，就可以继续各种求解了。 （2）缺失值处理：为了不对数据信息造成浪费，当出现有缺失值的数据时，我们要考虑两个问题：1，如何在属性值缺失的情况下，选择划分属性？2，给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？ 对于问题1：将信息增益的计算式进行推广，利用数据集D中在属性a上没有缺失值的样本子集，进行信息增益的计算。 对于问题2：若样本在划分属性a上的取值已知，则将x划入与其取值对应的子结点，其在该子结点的权值也保持不变。若取值未知，那么同时划入所有子结点，根据不同的子结点进行权值调整，也就是让一个样本以不同的概率划分到不同的子结点中去。

若每个属性视为一个坐标轴，那么d个属性描述的一个样本就对应了d维空间的一个数据点，对样本分类意味着在该空间找到不同样本之间的分类边界。 决策树的分类边界：轴平行，就是由若干个与坐标轴平行的分段组成。每一段的划分都对应了某一属性的取值。但是在分类边界比较复杂时，要进行大量的属性测试，预测时间开销会很大。 多变量决策树：使用斜的划分边界替代轴平行的划分边界，简化决策树模型。在此决策树中，非叶结点不再是仅针对某个属性，而是对属性的线性组合进行测试。它不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

（1）结点中样本数小于给定阈值； （2）样本集的基尼指数小于给定阈值（也就是样本基本属于同一类） （3）没有更多特征了

DecisionTreeClassifier 既能用于二分类（其中标签为[-1,1]）也能用于多分类（其中标签为[0,…,k-1]）。,采用输入两个数组：数组X，用[n_samples, n_features] 的方式来存放训练样本。整数值数组Y，用 [n_samples] 来保存训练样本的类标签。

训练后，可以进行预测，clf.predict()，可以预测该样本属于每个类的概率。 决策树绘图：可以使用export_graphviz 以 Graphviz 格式导出决策树.。可以根据这个画出决策树的图PDF格式。

注意：feature_names和class_names都是数组的形式，列表都可以。

决策树通过使用 DecisionTreeRegressor 类也可以用来解决回归问题。如在分类设置中，拟合方法将数组X和数组y作为参数，这时，y的值可以是浮点值。

一个样本x的输出可能不止是一个值。这时称为有多个输出值需要预测的监督学习问题。我们仍然用一棵决策树训练。做以下更改： （1）在叶中存储n个输出值，而不是一个; （2）通过计算所有n个输出的平均减少量来作为分裂标准.

当特征数过多时，样本数又少的时候，会出现过拟合现象。 （1）实现进行降维PCA,ICA等，找到更具有分辨性的特征。PCA主成分分析中：在对训练集降维后，要将得到的那个降维矩阵对测试数据降维，然后再送给分类器，这样才可以是同样的降维。如下代码所示：x_train是dataframe格式。

而且主成分分析中已经有标准化的步骤了，不需要再进行标准化归一化操作， （2）使用export可视化我的决策树。 （3）使用max_depth=3初始化树深度，先适应数据，在增加树的深度。使用max_depth也可以防止过拟合。 （4）通过使用 min_samples_split 和 min_samples_leaf 来控制叶节点上的样本数量。 （5）在训练之前平衡您的数据集 （6）如果样本被加权，则使用基于权重的预修剪标准 min_weight_fraction_leaf 来优化树结构将更容易，这确保叶节点包含样本权重的总和的至少一部分。 （7）所有的决策树内部使用 np.float32 数组 ，如果训练数据不是这种格式，将会复制数据集。

ID3（Iterative Dichotomiser 3）：由 Ross Quinlan 在1986年提出。该算法创建一个多路树，找到每个节点（即以贪心的方式）分类特征，这将产生分类目标的最大信息增益。决策树发展到其最大尺寸，然后通常利用剪枝来提高树对未知数据的泛华能力。

C4.5 是 ID3 的后继者：并且通过动态定义将连续属性值分割成一组离散间隔的离散属性（基于数字变量），消除了特征必须被明确分类的限制。C4.5 将训练的树（即，ID3算法的输出）转换成 if-then 规则的集合。然后评估每个规则的这些准确性，以确定应用它们的顺序。如果规则的准确性没有改变，则需要决策树的树枝来解决。

C5.0 ：是 Quinlan 根据专有许可证发布的最新版本。它使用更少的内存，并建立比 C4.5 更小的规则集，同时更准确。

CART（Classification and Regression Trees （分类和回归树））：与 C4.5 非常相似，但它不同之处在于它支持数值目标变量（回归），并且不计算规则集。CART 使用在每个节点产生最大信息增益的特征和阈值来构造二叉树。 注意：scikit-learn 使用 CART 算法的优化版本。

判断在某节点上的分类质量。 分类：基尼指数，交叉熵，错误分类率 回归：均方误差，平均绝对误差