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