通过对训练样本的学习，并建立分类规则，然后根据分类规则，对新样本数据进行分类预测，属于有监督学习
# ID3算法
# 其核心实在决策树的各级节点上，使用信息增益方法作为属性的选择标准，来帮助确定生成各个节点是所应采用的合适属性
# 使得在每个非叶节点上进行测试时，都能获得最大类别分类增益，使分类后数据集的熵最小
# 理论：用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益度量不确定性，信息增益值越大
# 算法流程
# 当前样本集合，计算所有属性的信息增益
# 选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划分为一个同一个样本集
# 若子样本集的类别属性只含有单个属性，则分枝为叶子节点
# R语言中建模步骤
# 建树
# 选择最优解释力度的变量
# 在X和Y都是分类变量的基础上
# 计算X中的各个变量的熵
# 也就是说X1相对Y 的信息量
# 筛选出信息量最大的X1进行第一层
# 对每个变量选择最优分割点
# 在第一层的类别里面计算，该类里面的 重新循环计算排序 直到数据分类切割完毕
# 剪树
# 前向剪枝 控制生产树的规模
# 后项剪枝 删除没有意义的分组
# 缺点
# 倾向于选择水平数量较多的变量
# 输入变量必须是分类变量(连续变量必须离散化)
# 重点
# 对一个特征而言，系统有它和没它时信息量将发生变化，而前后信息量的差值就是这个特征给系统带来的信息量。所谓信息量，就是熵。
# 在信息增益中，衡量标准是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要
# 也就是说X可能的变化越多，X所携带的信息量越大，熵也就越大
# 信息增益最大的问题在于它只能考察特征对整个系统的贡献，而不能具体到某个类别上
# 只适合用来做所谓“全局”的特征选择（指所有的类都使用相同的特征集合），而无法做“本地”的特征选择（每个类别有自己的特征集合，因为有的词，对这个类别很有区分度，对另一个类别则无足轻重）
# C4.5算法
# 相对于ID3算法重要改进是使用信息增益率来选择节点属性，克服了ID3算法只适用于离散的描述属性，而C4.5算法技能够处理离散的描述属性，也可以处理连续的表述属性
# 单个分类或等级变量：决策树遍历搜索
# 对分类变量，假设该输入变量有4个水平，则依次遍历所有的组合形式，计算熵增益率最大的那个组合方式
# 单个连续或者等级变量：决策树分割搜索
# 对连续变量，先等宽方式分为50组，依次取阈值分为两组，计算熵增益率变化的最大的那个分割方式
# 不能处理等级变量，要么作为分类变量，要么作为连续变量，设因子类型为连续变量，否则为连续变量
# 计算方式，比较多个变量的优先级
# 假设都是连续变量，先做各自分割，并计算每个分割的熵增益率
# 先计算X1分割方式，然后X2分割方式...
# 比较每个变量所能达到的最大的熵增益率，取最大的那个作为本次分割的选择变量，该变量对应最大熵增益率的分割点作为分割依据
# 在X1 > W10组中，比较每个变量所能达到最大熵增益率，取最大的那个作为本次分割选择的变量，该变量对应最大熵增益率的分割点作为分割依据
# 对X1再进行遍历，计算熵增益率
# 对X2再进行遍历，计算熵增益率
# ...
# 依次循环
# C5.0算法
# 建树 沿用C4.5的方法
# 剪枝
# 前剪枝
# 后剪枝
# 主要创新出 纳入了Boost的方法，可以做组合模型
# CART算法
# 基尼系数 判断分配平等程度的指标
# A ---> 实际收入分配曲线和收入分配绝对平等之间的面积
# B ---> 实际收入分配区间(右下方)的面积为B
# 基尼系数/洛伦兹系数(不平等程度) = A / (A+B)
# A 为 0 ，基尼系数为0 ，收入分配完全平等
# B 为 0 ，基尼系数为1 ， 收入分配绝对不平等
# 洛伦兹曲线弧度大小和基尼系数成正比
# CART决策树是一种十分有效的非参数分类和回归方法了，通过构建数，修剪树，评估树来构建一个二叉树，当终结点是连续变量，该树为回归树，当终结点是分类变量，该树为分类树
# 建树
# 选择最优解释力度的变量
# 对每个变量选择最优分割点
# 剪树
# 决策树创建时,由于数据中的噪音和离群点,许多分枝反映的是训练数据中异常
# 剪枝处理这种过分拟合的数据会影响模型的稳定性
# 通常适用统计度量剪掉最不可靠的分枝
# 剪枝后的树更小、更简单、更统一理解
# 前向剪枝(预修剪) 控制生产树的规模 控制决策树重复生长，可以事先指定一些控制参数
# 决策树最大深度
# 树种父节点和子节点的最小样本量或比例
# 对于父节点，如果节点的样本量小于最小样本量或比例，则不再分组
# 对于子节点，如果分组后生产的子节点的样本量低于最小样本量或比例，则不必进行分组
# 树节点中输出变量的最小异质性减少量。如果分组产生的输出变量异质性变化量小于一个指定值，则不必再分组
# 后项剪枝 删除没有意义的分组
# 允许决策树充分生长，然后在此基本上根据一定的规则，剪去决策树中那些不具有一般代表性的叶节点或者子树
# 一个边修剪边检验的过程。在修剪过程中，应不断计算当天决策子树对测试样本集的预测精度或者误差，判断应该是继续修剪还是停止修剪
# CART采用的后修剪技术称为最小代价复杂性修剪发--> MCCP
# MCCP的基本考虑（选择交叉验证中错误最小的）：
# 首先，考虑的决策树虽然对训练样本有很好的预测进度
# 但在测试样本和未来新样本上不会仍有令人满意的预测结果
# 其次，理解和应用一颗复杂的决策树是一个复杂过程
# 因此，目标是得到一颗“恰当” 的树
# 首先具有一定的预测精度，同时复杂是恰当的
# CART的决策树修剪方法——总结
# 输入变量（自变量）：为分类型变量或连续型变量
# 输出变量（目标变量）：为分类型变量（或连续型：回归分析）
# 连续变量处理：N等分离散化
# 树分支类型：二分枝
# 分割指标：gini增益(分割后的目标变量取值变异较小，纯度高)
# 先剪枝：决策树最大深度、最小样本分割输、叶节点包含的最小样本数、复杂度系数最小
# 后剪枝：使用最小代价复杂度剪枝法
# 决策树建树原理，计算每个首选变量对被解释变量的重要性指标，CART采用的指标为基尼系数
# 第一步 从众多输入变量中选择当前最佳分组变量
# 分类树：对于数值型输入变量，将数据按升序排序，
# 然后，从小到大依次以相邻数值的中间值作为组限，将样本分为两组
# 并计算两组样本输出变量值的差异性。也就是异质性
# 理想的分组应该尽量使两组输出变量值的异质性总和达到最小，即纯度最大
# 也就是使两组输出变量值的异质性随分组而快速下降，而“纯度”快速增加
# 第二步 从分组变量的众多取值中，找到最佳分割点
# 最佳分割点的确定方法与最佳分组变量的确定是同时进行的
# 单个分类或等级变量：决策树遍历搜索
# 对分类变量，假设该输入变量有4个水平，则依次遍历所有的组合形式，计算熵增益率最大的那个组合方式
# 单个连续或者等级变量：决策树分割搜索
# 对连续变量，先等宽方式分为50组，依次取阈值分为两组，计算熵增益率变化的最大的那个分割方式
# 不能处理等级变量，要么作为分类变量，要么作为连续变量，设因子类型为连续变量，否则为连续变量
# 处理方法与C50一致
# API
# 虚拟变量 sklearn包的算法，一般只支持连续值的变量，如果我们的数据中，包含离散值的变量，那么需要将离散值使用有限的连续值来表示，这种表示方法为虚拟变量，例如，男女性别，0或1
# DictVectorizer.fit_transform(dict_字典)
# 决策树生成方法
# dtModel = DecisionTreeClassifier(max_leaf_nodes_最大叶子节点数 = None)
# dtModel.fit(featureData_属性数据,targetData_目标数据)
# dtModel.Predict(featureData_属性目标)
# 决策树绘图方法
# sklearn.tree.export_graphviz(dtModel_决策树模型,out_file_图形数据输出的路径)
参考资料：《Python数据分析与挖掘实战》和 CDA《信用风险建模》微专业
