1. 决策树表示法

1.1 决策树是什么

基于统计的方式学习。

是一个把很多 if-else 规则综合到一起的树形结构。 树内部的每一个节点 node 代表了一个属性判断，树节点的每一个边 branch ，代表了属性的每一个可能的取值。 叶子节点 leaf node 代表了一个类别标签，一旦走到了叶子节点，就表示完成了数据的分类。

决策树学习机制的参数，就是树的形式是什么。根节点是什么属性，边是什么，下一个节点是什么，叶子节点分别是什么。

决策树可以表征所有可能的规则，比如合区关系（与）、析取关系（或）、异或关系。

1.2 决策树适用的问题

• 实例是由 属性-值 对表示的
• 目标函数具有离散的输出值
• 训练数据可以包含错误。决策树学习对错误具有很好的健壮性。
• 训练数据可以包含缺少属性值的实例

决策树是最流行的归纳推理算法之一，被成功的应用于学习医疗诊断、学习评估带宽申请信用风险等领域。

2. ID3学习算法

2.1 基本算法

ID3是一种自顶向下增长树的贪婪算法，在每个节点选取能最好的分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都被使用过。

在每一步，如何选取最好的属性，使用最高信息增益(information gain)方法。

2.2 哪个属性是最佳的分类属性

the “best” decision attribute for next node

定性分析

直观的讲，如果一个属性的区分度高，就比较好，比如判断男女问题中，头发长短属性比较好，籍贯比较差。

定性，通过这个属性的判定，能让结果数据集更接近完美分类，或者说能让数据集中程度提升越多，这个属性就更好。

定量

熵

Entropy 熵：度量集合的类别混杂程度

熵的计算公式：

假设 $S$ 是一个训练数据集合，$p+$ 是正例的百分比，$p-$ 是负向的百分比。

正例的百分比乘以正例的百分比的对数，加上，负例的百分比乘以负例的百分比的对数。

二分类问题里：

$ Entropy(S) = -p _+ \log_2 p _+ - p _- \log_2 p _- $

信息增益

是混杂程度的变化量，度量熵的好坏。

代表着通过属性的判定，熵变化了多少，熵的变化越大，则说明该属性的判定越接近完美分类，该属性越好。

计算公式：原来的熵，减去结果的熵。结果的熵，是对于每一个可能的取值，分别计算熵，再乘以取值的百分比。

$ Gain(S,A)=Entropy(S) - \sum _{v\in values(A)} \frac{|S _v|}{|S|} Entropy(S _v) $

3. 过拟合

过拟合是指为了得到一致假设而使假设变得过度严格。分类机制归于精细和复杂，拟合了所有的特殊情况，导致在训练数据集上精度很高，在未来的数据集上分类效果很差。

常见原因

（1）建模样本选取有误，如样本数量太少，选样方法错误，样本标签错误等，导致选取的样本数据不足以代表预定的分类规则，举例：李玉刚、李宇春。
（2）样本噪音干扰过大，使得机器将部分噪音认为是特征从而扰乱了预设的分类规则；
（3）假设的模型无法合理存在，或者说是假设成立的条件实际并不成立；
（4）参数太多，模型复杂度过高；
（5）对于决策树模型，如果我们对于其生长没有合理的限制，其自由生长有可能使节点只包含单纯的事件数据(event)或非事件数据(no event)，使其虽然可以完美匹配（拟合）训练数据，但是无法适应其他数据集。
（6）对于神经网络模型：a)对样本数据可能存在分类决策面不唯一，随着学习的进行,，BP算法使权值可能收敛过于复杂的决策面；b)权值学习迭代次数足够多(Overtraining)，拟合了训练数据中的噪声和训练样例中没有代表性的特征。

哲学思想

天之道，损有余而补不足。不足胜有余。