1.决策树学习基本算法（递归，分而治之）
输入：训练集D={(x1,y1),(x2,y2),…(xm,ym)};
? ? ? ? ?属性集A={a1,a2,…ad}.
过程：函数TreeGenerate(D,A)
(1)生成结点node；
(2)if D中样本全属于同一类别C then
将node标记为C类叶结点；return
end if
(3)if A=??或 D中样本在A上取值相同 then
将node标记为D中样本数(当前结点)最多的类(成为叶结点)；return
end if
(4)从A中选择最优划分属性a*：
(5)for a* 的每个值 a‘* do
为node生成一个分支；令Dv表示D中在a*上取值为a’*的样本子集
if Dv为空 then
将分支结点标记为D中样本数(父结点)最多的类(成为叶结点);return
else
以TreeGenerate（Dv，A\{a*}）为分支结点
end if
end for
输出：以node为根结点的一棵决策树
?
2.从A中选择最优划分属性a*的方法
基本思想：希望决策树的分支结点所含的样本尽可能属于同一类别，即结点的“纯度”越来越高
信息熵：（自信息的期望）
?
?2.1.ID3决策树
?
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大，因此可用信息增益来进行决策树的划分属性选择。
原因：在其一状态一致时，信息增益越大表示后一状态熵越小，即后一状态混乱程度越小，该状态的值就越确定。
缺点：信息增益准则对可取数目较多的属性有所偏好，极端例子：将序号做为属性，每个序号仅对应一个样本，纯度最大，但不具有泛化能力
2.2.C4.5决策树
?
?2.3.CART决策树
?3.剪枝(pruning)处理：对付过拟合
3.1预剪枝
是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升（整体泛化性能），则停止划分并将当前结点标记为叶结点
问题：存在欠拟合风险，因为有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行得后续划分却有可能导致性能显著提高。
3.2后剪枝
是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。泛化性能不变时，可以保留
优缺点：后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情况下，后剪枝决策时的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但是时间开销会更大。
泛化性能提升判断：性能评估方法，如留出法，交差验证法，自助法
?4.连续值处理
思路：离散化
C4.5决策树：二分法
做法：（1）将连续属性a的n个不同取值从小到大排列，记为{a1,a2,...,an}
（2）以Ta={(ai+a<i+1>)/2,1<=i<=n-1}为候选划分点集合，含n-1个元素
（3）再用离散从A中选择最优划分属性a*的方法选取最优划分点
注意：与离散属性不同的是，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性
5.缺失值处理
在有大量缺失值时，如果简单得放弃不完整样本，仅使用无缺失值的样本进行学习，是对数据信息的极大浪费。
需解决问题：（1）如何在属性值缺失的情况下进行划分属性选择？（C4.5决策树：按没有缺失值的属性划分）
（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？（C4.5决策树：同一个样本以不同的概率划分到所有子结点）
问题：权重是怎么回事啊？
C4.5决策树处理方法：
???
?6.多变量决策树
非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试，即每个非叶结点是一个形如的线性分类器，其中wi为属性ai的权重
eg：
?