为了提高复杂关系的拟合能力，在特征工程中经常会把一阶离散特征两两组合，构成高阶组合特征。在实际问题中，需要面对多种高维特征，简单地两两组合，依然容易存在参数过多、过拟合等问题。
怎样有效地找到组合特征？ 可以利用决策树来寻找特征组合方式。
例如，影视推荐问题有两个低阶特征「语言」和「类型」，其中有语言分为中文和英文，类型分为电影和电视剧，那么这两个特征的高阶组合特征有（中文，电影）、（英文，电视剧）、（英文，电影）、（中文，电视剧）四种。下表的数据，就可以变为新的数据：
| 是否点击 | 语言 | 类型 |
|---|---|---|
| 0 | 中文 | 电影 |
| 1 | 英文 | 电影 |
| 1 | 中文 | 电视剧 |
| 0 | 英文 | 电视剧 |
| 是否点击 | 语言 = 中文，类型 = 电影 | 语言 = 英文，类型 = 电影 | 语言 = 中文，类型 = 电视剧 | 语言 = 英文，类型 = 电视剧 |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 |
以逻辑回归为例，假设数据的特征向量为 $X=(x_1,x_2,\dots,x_k)$，则有：
$$ Y=\text{sigmoid}(\sum_i\sum_jw_{ij}\langle x_i,x_j\rangle) $$
$\langle x_i,x_j\rangle$ 表示 $x_i$ 和 $x_j$ 的组合特征，$w_{ij}$ 的维度等于第 $i$ 和第 $j$ 个特征不同取值的个数。在上例中，「语言」这个特征有中文和英文两个选择，「类型」这个特征有电影和电视剧两个选择，那么 $w_{ij}$ 的维度就为 $2\times 2=4$. 当组合之前的两个特征不同取值的个数都不大时，用这种方式不会有太大的问题。但是对于某些问题，有用户 ID 和物品 ID，而用户和物品的数量动辄几千万，几千万乘几千万 $m\times n$，这么大的参数量，无法进行学习。
对于这种「高维组合特征」要如何处理？ 假设用户和物品的数量分别为 $m$ 和 $n$，一种行之有效的方法是将两个特征分别用 $k$ 维的低维向量表示（$k\ll m,k\ll n$），这样原本 $m\times n$ 的学习参数就降低为 $m\times k + n\times k$，这其实等价于推荐算法中的矩阵分解。
参考：
[1] 诸葛越，葫芦娃，《百面机器学习》，中国工信出版集团，人民邮电出版社
