特征工程：什么是「组合特征」？要如何处理「高维组合特征」？

为了提高复杂关系的拟合能力，在特征工程中经常会把一阶离散特征两两组合，构成高阶组合特征。在实际问题中，需要面对多种高维特征，简单地两两组合，依然容易存在参数过多、过拟合等问题。

怎样有效地找到组合特征？ 可以利用决策树来寻找特征组合方式。

例如，影视推荐问题有两个低阶特征「语言」和「类型」，其中有语言分为中文和英文，类型分为电影和电视剧，那么这两个特征的高阶组合特征有（中文，电影）、（英文，电视剧）、（英文，电影）、（中文，电视剧）四种。下表的数据，就可以变为新的数据：

以逻辑回归为例，假设数据的特征向量为 $X=(x_1,x_2,\dots ,x_k)X=(x\_1,x\_2,\backslash dots,x\_k)$，则有：

$⟨x_i,x_j⟩\backslash langle\; x\_i,x\_j\backslash rangle$ 表示 $x_{i}x\_i$ 和 $x_{j}x\_j$ 的组合特征，$w_{ij}w\_\{ij\}$ 的维度等于第 $ii$ 和第 $jj$ 个特征不同取值的个数。在上例中，「语言」这个特征有中文和英文两个选择，「类型」这个特征有电影和电视剧两个选择，那么 $w_{ij}w\_\{ij\}$ 的维度就为 $2\times 2=42\backslash times\; 2=4$. 当组合之前的两个特征不同取值的个数都不大时，用这种方式不会有太大的问题。但是对于某些问题，有用户 ID 和物品 ID，而用户和物品的数量动辄几千万，几千万乘几千万 $m\times nm\backslash times\; n$，这么大的参数量，无法进行学习。

对于这种「高维组合特征」要如何处理？ 假设用户和物品的数量分别为 $mm$ 和 $nn$，一种行之有效的方法是将两个特征分别用 $kk$ 维的低维向量表示（$k\ll m,k\ll nk\backslash ll\; m,k\backslash ll\; n$），这样原本 $m\times nm\backslash times\; n$ 的学习参数就降低为 $m\times k+n\times km\backslash times\; k\; +\; n\backslash times\; k$，这其实等价于推荐算法中的矩阵分解。

参考： [1] 诸葛越，葫芦娃，《百面机器学习》，中国工信出版集团，人民邮电出版社