[数据结构与算法]人工智能基础（十九）决策树

决策树

决策树分类原理
1、信息增益
信息增益 = entroy (前) - entroy (后)
注意：信息增益越大，我们优先选择这个属性进行计算
信息增益优先选择属性总类别比较多的进行划分
2、信息增益率
维持了一个分离信息度量，通过这个分离信息度量当分母，进行限制
3、基尼增益
基尼值： 从数据集D中随机抽取两个样本，其类别标记不一致的概率
Gini(D)值越小，数据集D的纯度越高
基尼指数：选择使划分后基尼系数最小的属性作为最优划分属性
基尼增益：选择基尼增益最大的点，进行优化划分

基尼增益构造过程：

• 开始将所有记录看作一个节点
• 遍历每个变量的每一种分割方式，找到最好的分割点
• 分割成节点N1和N2
• 对N2和N2分别继续执行2-3步，直到每个节点足够“纯”为止

决策树的变量可以有两种，分别对应的划分方式：

• 1、数字型
  通过对数据取两个数字之间的中间值进行划分

• 2、名称型
  通过对属性的类别进行划分

如何评估分隔点的好坏？
主要看分割的纯不纯