Reference

• 【机器学习】决策树（上）——ID3、C4.5、CART
• 决策树—ID3、C4.5、CART

【ID3 算法】

概述

【概率分布的基尼指数】

基尼指数表示在样本集合中一个随机选中的样本被分错的概率，与信息熵相似，基尼指数越大，样本集合 $D$ 的不确定性也就越大

假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$，则概率分布的基尼指数定义为：

【信息增益与互信息】

在决策树中，信息增益（Information Gain）表示在知道了特征 $X$ 的信息后，使得使类 $Y$ 的信息的不确定性减少了的程度

信息增益是针对特征而言的，因此，特征 $A$ 对于训练集 $D$ 的信息增益 $g(D,A)$，被定义为：训练集 $D$ 的经验信息熵 $H(D)$ 与给定条件下特征 $A$ 与训练集 $D$ 的经验条件熵 $H(D|A)$ 的差，即：

【学习步骤】

决策树学习通常包括特征选择、决策树生成、决策树剪枝三个步骤：

1. 特征选择：选择最优的特征作为决策结点
2. 决策树生成：即决策树的构建，仅考虑局部最优，对应模型的局部选择
3. 决策树剪枝：对生成的决策树进行简化，考虑全局最优，对应模型的全局选择

【决策树】

决策树（Decision Tree）是一种用于分类或回归的机器学习方法，对于复杂的预测问题，通过建立树模型产生分支结点，依照规则递归地分割数据集，使得问题从结构上划分为不同的子问题

决策树本质是从训练集中归纳出一组规则，在给出一个新的输入后，根据规则给出相应的输出，由于与训练集不矛盾的决策树可能有多个，需要选择一个与训练数据矛盾较小的决策树，同时具有较好的泛化能力

Reference

• 西瓜书读书笔记——第七章：贝叶斯分类器
• 贝叶斯算法小总结
• 半朴素贝叶斯分类器

【概述】

在 朴素贝叶斯 中介绍了朴素贝叶斯分类器与其所假设的条件独立性，但该假设过于强势，在实际模型中有时并不满足，即样本的很多特征可能存在关联关系，并不独立

Reference

• 【辨析】先验概率、后验概率、似然概率
• 带你理解朴素贝叶斯分类算法
• 算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)
• 贝叶斯估计
• 平滑处理—拉普拉斯（Laplace Smoothing）
• Naive Bayes classifier
• Additive smoothing

【朴素贝叶斯参数估计】

对于朴素贝叶斯分类器：

Reference

• 【辨析】先验概率、后验概率、似然概率
• 带你理解朴素贝叶斯分类算法
• 算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)
• 贝叶斯估计
• 平滑处理—拉普拉斯（Laplace Smoothing）
• Naive Bayes classifier
• Additive smoothing

【概述】

贝叶斯分类模型是基于贝叶斯定理与特征条件独立假设的分类模型，朴素贝叶斯（Naive Bayes）是贝叶斯分类模型中最简单、最常见的一种分类方法，该方法从概率论的角度来进行分类预测，实现简单，预测效率高

Reference

• 详解最大熵模型
• 最大熵模型原理
• 深入机器学习系列21-最大熵模型
• 二十一.最大熵模型原理
• 最大熵模型中的对数似然函数表示法解释
• 最大熵模型中的对数似然函数的解释

【最大熵模型学习的最优化算法】

由于在最大熵模型中，对偶函数的极大化等价于最大熵模型的极大似然估计，那么最大熵模型的学习问题就转换为具体求解对偶函数 $\psi(\boldsymbol{\omega})$ 极大化或对数似然函数 $L_{\tilde{p}}(p_{\boldsymbol{\omega}})$ 极大化的问题，即：

【概述】

改进的迭代尺度法（Improve Iterative Scaling，IIS）是一种专用于最大熵模型学习的最优化算法，其是在通用迭代尺度法（Generalized Iterative Scaling，GIS）的基础上改进得来的

已知最大熵模型为：