决策树C#的实现探索

关于GBDT的概念性的文章，这里不再重复了，请自行百度一下。

决策树（分类）

组委会是要求测算GAP值，是个定量问题。在这之前，我们看一下是否能够限定性分析一下GAP的高低呢？

从滴滴算法大赛的数据可以知道，数据的特征值大约有这些：

• 天气相关：天气类型，PM2.5(离散化处理)，温度(离散化处理)
• 交通状态：需要将原有数据重新计算为一个新的指标，例如将拥挤度进行加权平均。
• POI数据：挑选特征明显的分类

有一些特征需要自己去发现

• 工作日/休息日
• 特殊天气（极端最低气温）
• 时间段（根据组委会的题目，可以将9个待预测时间片，变化为9个时间段）

整理出来的表格大概像这个样子的（不完全，示例）

这个时候，我们到底先用哪个条件作为优先决策的依据呢？答案就是上文提到的信息增益。

Information Gain 信息增益 和 Relative Information Gain

• IG（GAP分类 | 天气类型） = H（GAP分类） – H（GAP分类 | 天气类型）
• IG（GAP分类 | 交通状态） = H（GAP分类） – H（GAP分类 | 交通状态）
• IG（GAP分类 | 工作日） = H（GAP分类） – H（GAP分类 | 工作日）

哪个数字最大就挑选哪个作为第一优先分类条件。
现在我们假设工作日是最高信息增益的，作为第一个决策条件
第一次分组之后就是这个样子了：

按照理论（大神的文章，以后会翻译的），工作日组的GAP分类都一致了，所以就无需决策了。
对于节假日组，根据交通状态进行再分类

交通状态再分类结果如下

这里无需天气类型就可以完成分类决策了。
（当然还有一种情况是所有特征都用完了，还是不能完全分类，这个时候可以使用多数表决的方式决定分类）

决策树（定量）

上面是一个定性的过程，下面我们来看一下，如果需要定量怎么处理呢？

• 根节点的输入是所有的值，输出是所有目标值得均值。
  （输入和输出之间的差就是误差，这里往往不是计算简单的差，而是方差）
  这里的平均值就是（ 893 + 375 + 542 + 437 + 753 ） / 5 = 600

第一次分类怎么处理呢？
分裂的时候选取使得误差下降最多的分裂
如果我们选择工作日作为分裂条件

工作日的均值是：（893 + 753 ）/ 2 = 823

误差的方差是： 70 × 70 + 70 × 70 = 9800

节假日的均值是：（375 + 542 + 437 ）/ 3 = 451

误差的方差是： 76 × 76 + 91 × 91 + 14 × 14 = 14253

按照是否为工作日分裂之后的总误差是 9800 + 14253 = 24053

当然标准做法是计算所有的总误差，然后选取最小的总误差的特征作为分类特征
（如果在这里结束，则认为工作日的预测是823，节假日的预测是541当然这还没有完）

第一颗树：
工作日：+823
休息日：+451

第二颗树：
如果按照拥挤分类呢？
注意这里我们使用的输入值是误差！！

首先计算均值：

• 轻度拥挤 ： -76
• 重度拥挤 ： -70
• 拥挤 ： +49

(这些数字的意思是，如果你认为工作日的预测是823，节假日的预测是541，两者都需要根据拥挤程度根据上述值进行修正)

第三颗树：

晴天：+ 31
雪：- 63

在交通状态为拥堵的时候，如果是晴天，修正 31，雪：修正 -63

预测一下

工作日 +823
拥挤：+49
拥挤 且 雪天：-63
预测：809

C#代码

回归分类树节点

    /// 

    /// 回归分类树节点
    /// 
    class TreeNode
    {
        /// 

        /// 节点属性名字
        /// 
        public string attrName { set; get; }
        /// 

        /// 节点索引标号
        /// 
        public int nodeIndex { set; get; }
        /// 

        /// 包含的叶子节点数
        /// 
        public int leafNum { set; get; }
        /// 

        /// 节点误差率
        /// 
        public double alpha { set; get; }
        /// 

        /// 父亲分类属性值
        /// 
        public string parentAttrValue { set; get; }
        /// 

        /// 孩子节点
        /// 
        public TreeNode[] childAttrNode { set; get; }
        /// 

        /// 数据记录索引
        /// 
        public List dataIndex { set; get; }
    }

滴滴算法大赛算法解决过程 – 数据分析
滴滴算法大赛算法解决过程 – 拟合算法
滴滴算法大赛算法解决过程 – 方案设计
滴滴算法大赛算法解决过程 – 机器学习
滴滴算法大赛算法解决过程 – 决策树
参考文献

GBDT的基本原理