[KO机器学习] Day4 特征工程：如何有效地找到组合特征？

场景描述：

昨天更新了如何利用降维方法来减少两个高维特征组合后需要学习的参数，还没看过的同学可以到主页查看Day3。但是在很多实际问题中，我们常常需要面对多种高维特征。如何简单地两两组合，依然容易存在参数过多、过拟合等问题，而且并不是所有的特征组合都是有意义的。因此，需要一种有效的方法来帮助我们找到应该对哪些特征进行组合。

怎么样有效地找到组合特征呢？难度：★★☆☆☆

本文介绍一种基于决策树的特征组合寻找方法（关于决策树的详细内容过段时间为大家更新）。以点击预测问题为例，假设原始输入特征包含年龄、性别、用户类型（试用期、付费）、物品类型（护肤、食品等）4个方面的信息，并且根据原始输入和标签（ 点击 / 未点击 ）构造出了决策树，如下图所示。

图1 基于决策树的特征组合方法

于是，每一条从根节点到叶节点的路径都可以看成一种特征组合的方式。具体来说，就有以下4种特征组合的方式。

1. 年龄 <= 35 且 性别 = 女
2. 年龄 <= 35 且 物品类型 = 护肤
3. 用户类型 = 付费 且 物品类型 = 食品
4. 用户类型 = 付费 且 年龄 <= 40

表1：两个不同样本对应的原始输入特征 

 上表是两个样本信息，那么第一个样本按照上述 4种特征组合就可以编码为（1，1，0，0），因为同时满足1和2，但不能满足3和4。同理，第二个样本可以编码为（0，0，1，1），因为他同时满足3和4，不能满足1和2。

给定原始输入该如何有效地构造决策树呢？可以采用梯度提升决策树，该方法的思想是每次都在之前构建的决策树的残差上构建下一颗决策树。