1700508090
3．决策树
1700508091
1700508092
决策树（Decision Tree，如表11-7所示）也是一种相对比较常见的经典分类学习算法，面对的训练对象同样是一些输入向量Xi。Xi是一个n维向量及Xi所对应的分类标签。
1700508093
1700508094
表11-7 决策树
1700508095
1700508096
1700508097
1700508098
1700508099
对这类问题，决策树算法都希望用尽可能简洁并准确的方式描述分类过程，并平衡“简洁”和“准确”这对矛盾。
1700508100
1700508101
在这个算法中，需要对整个训练样本集分类进行熵的评估，其目的是衡量这种分类本身的杂乱程度。这里的“熵”和《信息论》中所说的“熵”是同一个概念。从公式上来看，分类的数量越多，发生的概率越均等，熵的值就越大。根据《信息论》的经典理论——信息是用于消除不确定性的东西，那么在这样一个环境中，如何通过尽可能短的“消息”来尽可能多地消除不确定性，就成了破解这类问题的主要思路，而这个所谓的“消息”就是构造出来的分类树的“树枝”（如图11-33所示）。
1700508102
1700508103
1700508104
1700508105
1700508106
图11-33 决策树的构造
1700508107
1700508108
一般来说，通过一个维度条件的约束就能确定分类是不是最好的。也就是说，如果只用“条件1”这个节点来划分，给予一个维度的约束条件，就已经能把整个分类描述“精确”，那就完全没有必要加入其他任何维度的描述了（因为那些维度不能带来消除不确定性的信息）。
1700508109
1700508110
对于构造一层“决策树”来说，引入哪个字段最为合理，完全取决于这个维度带来的信息增益——也就是熵减的大小。熵减越大，就说明这个维度对于分类的划分越有利。在这个环节，经典的算法有ID3、C4.5和CART。
1700508111
1700508112
1700508113
1700508114
1700508115
ID3直接对各个维度的信息增益进行计算，选择信息增益最大的维度作为决策点，将集合分成两部分，然后在第二层继续选择剩余维度中信息增益最大的作为决策点，如此一层一层构造下去。随着层数增多，信息熵逐渐减少，这个过程就是求解过程。
1700508116
1700508117
1700508118
1700508119
1700508120
C4.5和ID3的流程看上去没有本质的区别，都是在寻找信息熵逐渐减小的路径。不过，ID3的算法导致它倾向于使用取值较多的维度。而C4.5就没有这个问题，它使用信息增益比来代替信息。
1700508121
1700508122
1700508123
1700508124
1700508125
CART（Classification and Regression Tree）则使用标准的二叉树，在节点裂解的时候使用基尼系数进行计算。基尼系数的含义与信息熵的含义类似，是用来量化纯度的。混杂度越高，基尼系数就越高。通过计算，得到使基尼系数降低幅度最大的维度作为裂解所使用的维度。
1700508126
1700508127
最后，通过剪枝法对生成的树模型进行修正，分为“前剪枝”和“后剪枝”两大类方法。
1700508128
1700508129
前剪枝是指在应用所有的维度条件之前就终止树的生成的方法，只要目前的树的层数和分类的不纯度都已经逼近业务场景能够接受的极限就可以了。
1700508130
1700508131
后剪枝是指在决策树构造完成后对树进行修剪，主要目的是消除过拟合。常见的算法有降低错误剪枝（Reduced Error Pruning，REP）、悲观错误剪枝（Pessimistic Error Pruning，PEP）、基于错误剪枝（Error-Based Pruning，EBP）、代价-复杂度剪枝（Cost-Complexity Pruning，CCP）、最小错误剪枝（Minimum Error Pruning，MEP）等。
1700508132
1700508133
这些剪枝方法各有优缺点，总体来说是在降低过拟合程度这个环节上平衡算法复杂性和精确度改善这对矛盾，这里也可能产生过拟合现象。因为只要引入的样本不够多，就有产生过拟合的风险，所以在验证集上进行验证后，强烈建议使用后剪枝方法。
1700508134
1700508135
4．支持向量机
1700508136
1700508137
支持向量机（Support Vector Machine，SVM）是机器学习分类模型中适用范围比较广的一种算法。
1700508138
1700508139
在用支持向量机求解分类问题的过程中有这样一个视角，就是在多维空间中找到一个平面，使训练集中的两类多维向量与这个平面的距离最大化。而每个向量到平面的距离之和最大化的问题，可以转化为一个等价的凸函数，将其作为损失函数最小化的问题求解——仍然是凸优化问题。