极简机器学习栏目专为想要快速了解相关知识领域的学生/从业者服务。以「惜墨如金」，「栩栩如生」，重视理论为第一原则，方便各位节省时间入门机器学习。
机器学习（Machine Learning）是近年来兴起的一门多领域交叉学科，主要研究让机器可以从已知数据中分析规律，并利用规律对未知数据进行预测的算法们。
算法分为监督式学习，即在已知训练数据结果的情况下让算法有效的预测未知目标，常见的例子有回归分析（如预测波士顿地区房价）和统计分类（如预测文章分类）；非监督式学习，即输入数据没有已知结果，常见的例子有聚类（把认为相似的数据聚集起来）；半监督学习，即输入数据有的有已知结果，有的没有；强化学习：输入数据直接反馈到模型。
决策树决策树算法是一种监督式学习算法，既可以解决回归分析问题，也可以解决统计分类问题。
举例说明：假如你想知道心仪的男生/女生喜欢听什么类型的歌曲，如果以播放频率高低为喜欢程度的标准，并且获得了一份他/她的歌单。
我们可以按照不同的方式划分这个歌单，以按照流派分类为例
Brit pop 里的所有歌曲播放频率为高，不需要继续划分，在这种情况下我们认为所有属于 Brit pop 流派的歌曲都受到喜爱。之后按照国家划分。
最后按照歌手划分，对于全都归为一类的节点无需继续划分
这就是一个完整的决策树模型，对于任何一个未知的歌曲，先判断流派，如果是 Brit pop 则认为喜欢，否则看进入哪个分支，再进行判断，比如进入摇滚分支，并且歌曲来自中国，那么就会被标记为喜欢，如果是来自美国的 OneRepublic 乐队的歌曲则会被认为相对不喜欢。
另一个决策树的例子是银行预测贷款用户的还款能力：
决策树中每次经过不同的判断条件（属性）向下延伸，分支表示符合节点条件的集合，每个叶子节点代表一种预测结果。
如何建立决策树在上文歌曲的例子当中，选择不同的特征当作第一次判别的依据结果会很不一样，如果以艺术家的不同当作第一次判别的条件，我们几乎立刻就能认为旅行团乐队和 OneRepublic 的歌曲相对不受喜爱，其他艺术家的歌曲都会收到喜爱。此时决策树发展一次就能得出结果。选择一个合适的特征优先做判断，可以大大减少树的深度，加快决策速度。如何做出选择？常用的有以下几种方法：
- ID3：每次都选择使信息增益最大的特征
- C4.5：每次都选择信息增益率最大的特征
- CART：每次只做二分类，使用基尼指数划分
前两种方法都使用到了信息熵的概念，熵这个概念缘起于自然科学，表示体系混乱程度。直观理解，在一个集合里，如果不同类别的样本参杂在一起，其混乱程度就会比只有单一种类的样本的集合高，也就是信息熵更高。其公式定义如下：
其中 H(X) 表示系统的信息熵，N表示所有样本的种类 Pk 表示第 k 类样本所占的比例。
每一次判别后，系统的混乱程度（信息熵）都会降低，用数学表达式表示如下：
G 表示信息增益，D 表示系统样本，|D| 是样本数量，v 表示派别后的每一个子节点。
ID3 算法每次都选择使信息增益 G 最大的特征进行当前的判别，以此类推。这种算法的问题是如果一个特征类别很多，其容易被优先考虑，造成很难泛化。因此 C4.5 算法引入信息增益率的概念。
其特点是信息增益相同时，分类少的优先考虑。当然 C4.5 本身的改进比较复杂，这里不做详细介绍。
CART 每次都只进行 2 分类，可以用于回归，采用基尼指数进行判别：
决策树是一种简单高效的模型，容易产生过拟合的问题，因此需要使用剪枝等手法进行处理。掌握决策树，可以对之后更为复杂的模型如随机森林的理解打下良好基础。
参考资料- https://www.ibm.com/developerworks/cn/analytics/library/ba-1507-decisiontree-algorithm/index.html
- https://zhuanlan.zhihu.com/p/27313529
