决策树

是使用频率最高的数据挖掘算法，原因是不需要了解机器学习的知识也能搞明白决策树是怎么工作。

优势：数据形式非常容易理解，可以从不熟悉的数据集合中提取出一系列规则，计算复杂度不高，对中间值的缺失不敏感，可以处理不相关特征数据

缺点：可能会产生过度匹配问题

使用数据范围：数值型和标称型

基尼不纯度：从一个数据集中随机选取子项，度量其被错误分类到其他分组里的概率。

信息增益：计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择

熵定义为信息的期望值，如果待分类的事务可能划分在多个分类中，则符号Xi的信息定义为l(Xi)=-lgP(Xi),P(Xi)是选择该分类的概率，所有类别所有可能值包含的信息期望值E=-∑P(Xi)lgP(Xi)

信息表示

算法流程： 

每次遍历特征，对数据集按此特征进行划分后，计算数据集的新熵值，并对所以唯一特征值得到的熵求和，和越小，划分结果越有序，用此特征划分效果越好。

递归构建决策树， 直到遍历完所有划分数据集的属性，或者每个分枝下的所有实例都具有相同的分类

---

C4.5

信息增益准则会对可能取值数目较多的属性有所偏好，为了减少这种偏好带来的不良影响，考虑内在信息量，使用信息增益率

内在信息 信息增益率

特征的重要性会随着其内在信息（Intrinsic Information）的增大而减小。 信息增益率作为一种补偿（Compensate）措施来解决信息增益所存在的问题，但是它也有可能导致过分补偿，而选择那些内在信息很小的特征，这一点可以尝试：首先，仅考虑那些信息增益超过平均值的特征，其次再比较信息增益。

---

CART

使用基尼不纯度进行划分

基尼系数，其中pj是类j在T中的相对频率，当类在T中是倾斜的时，gini(T)会最小 将T划分为T1（实例数为N1）和T2（实例数为N2）两个子集后，划分数据的Gini定义

随后选择最小的Gini(T)作为结点划分决策树

---

剪枝

解决决策树学习算法中过拟合

预剪枝： 在决策树生成过程中，对每个节点在划分前先进行估计，如不能带来泛化性能提高，则停止划分

后剪枝：在生成完决策树后，自底向上对非叶子节点进行考察，如将其替换为叶子节点后泛化性能提升，则将该子树替换为叶节点。

泛化性能的考察可以使用留出法:即留出一部分样本用作测试。

---

数值型属性的转化

如密度，长度等，采用二分法转化

如20个密度数据，进行排序后相邻两个数据进行折中，Ta = { ai+ai+1/2 1<=i<=n-1}

那么每个决策点的含义变为  “密度是否>Ta”,相当于额外再增加N-1个属性，但感觉这么做在数据量大的时候效率衰减会很快

---

缺失值的处理

可以采取加入权重的方法，表示这条数据可能处于这个划分集的概念，对于属性不缺失的数据，权重为1，对于剩余的，权重为元样本中的概率分布

在计算信息增益的时候先不考虑属性缺失数据，待确定划分属性后，将这条在该属性上数据缺失的数据以原样本中的概率分布分别加入到划分的下一层去

---

多变量决策树

轴平行是一般决策树的决策边界的特点，但存在一些情况需要多段划分才能取得较好的近似

如某个决策点变为 -0.8*密度-0.44*含糖率<=-0.333

主要算法有OC1，先贪心的寻找每个属性的最优权值，在局部优化的基础上再对分类边界进行随机扰动以试图找到更好的边界，