6.7. 核近似#

此子模块包含近似对应于某些核的特征映射的函数，例如它们在支持向量机中使用（参见支持向量机）。以下特征函数执行输入的非线性转换，可以用作线性分类或其他算法的基础。

与使用隐式特征映射的核技巧相比，使用近似的显式特征映射的优势在于，显式映射更适合在线学习，并且可以显著降低使用非常大的数据集进行学习的成本。标准的核化 SVM 无法很好地扩展到大型数据集，但是使用近似的核映射，可以使用更高效的线性 SVM。特别是，核映射近似与SGDClassifier的结合可以使大型数据集上的非线性学习成为可能。

由于使用近似嵌入的经验工作不多，因此建议尽可能将结果与精确的核方法进行比较。

另请参见

多项式回归：使用基函数扩展线性模型，了解精确的多项式变换。

6.7.1. 用于核近似的 Nystroem 方法#

在Nystroem中实现的 Nystroem 方法是一种用于核的降秩近似的通用方法。它通过对评估核的数据的行列进行无放回抽样来实现这一点。虽然精确方法的计算复杂度为\(\mathcal{O}(n^3_{\text{samples}})\)，但近似的复杂度为\(\mathcal{O}(n^2_{\text{components}} \cdot n_{\text{samples}})\)，其中可以设置\(n_{\text{components}} \ll n_{\text{samples}}\)而不会显著降低性能[WS2001]。

我们可以根据数据的特征构建核矩阵\(K\)的特征分解，然后将其分成采样和未采样数据点。

\[\begin{split}K = U \Lambda U^T = \begin{bmatrix} U_1 \\ U_2\end{bmatrix} \Lambda \begin{bmatrix} U_1 \\ U_2 \end{bmatrix}^T = \begin{bmatrix} U_1 \Lambda U_1^T & U_1 \Lambda U_2^T \\ U_2 \Lambda U_1^T & U_2 \Lambda U_2^T \end{bmatrix} \equiv \begin{bmatrix} K_{11} & K_{12} \\ K_{21} & K_{22} \end{bmatrix}\end{split}\]

其中

\(U\) 是正交矩阵
\(\Lambda\) 是特征值的对角矩阵
\(U_1\) 是所选样本的正交矩阵
\(U_2\) 是未选样本的正交矩阵

鉴于\(U_1 \Lambda U_1^T\)可以通过矩阵\(K_{11}\)的正交化获得，并且可以计算\(U_2 \Lambda U_1^T\)（及其转置），唯一剩下的要阐明的项是\(U_2 \Lambda U_2^T\)。为此，我们可以用已经计算出的矩阵来表示它

\[\begin{split}\begin{align} U_2 \Lambda U_2^T &= \left(K_{21} U_1 \Lambda^{-1}\right) \Lambda \left(K_{21} U_1 \Lambda^{-1}\right)^T \\&= K_{21} U_1 (\Lambda^{-1} \Lambda) \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} U_1 \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} K_{11}^{-1} K_{21}^T \\&= \left( K_{21} K_{11}^{-\frac12} \right) \left( K_{21} K_{11}^{-\frac12} \right)^T .\end{align}\end{split}\]

在fit过程中，类Nystroem会计算基\(U_1\)，并计算归一化常数\(K_{11}^{-\frac12}\)。之后，在transform过程中，会确定基（由components_属性给出）和新的数据点X之间的核矩阵。然后将此矩阵乘以normalization_矩阵以得到最终结果。

默认情况下，Nystroem使用rbf核，但它可以使用任何核函数或预计算的核矩阵。使用的样本数（这也是计算出的特征的维度）由参数n_components给出。

示例

请参阅标题为与时间相关的特征工程的示例，该示例展示了一个使用Nystroem核的高效机器学习管道。

6.7.2. 径向基函数核#

RBFSampler构建径向基函数核的近似映射，也称为 *随机厨房水槽* [RR2007]。例如，这种变换可以用来在应用线性算法（例如线性SVM）之前显式地建模核映射。

>>> from sklearn.kernel_approximation import RBFSampler
>>> from sklearn.linear_model import SGDClassifier
>>> X = [[0, 0], [1, 1], [1, 0], [0, 1]]
>>> y = [0, 0, 1, 1]
>>> rbf_feature = RBFSampler(gamma=1, random_state=1)
>>> X_features = rbf_feature.fit_transform(X)
>>> clf = SGDClassifier(max_iter=5)
>>> clf.fit(X_features, y)
SGDClassifier(max_iter=5)
>>> clf.score(X_features, y)
1.0

该映射依赖于对核值的蒙特卡洛近似。fit函数执行蒙特卡洛采样，而transform方法执行数据的映射。由于过程固有的随机性，对fit函数的不同调用可能会产生不同的结果。

fit函数有两个参数：n_components，它是特征变换的目标维度；gamma，是RBF核的参数。较高的n_components值将导致对核的更好近似，并将产生与核SVM产生的结果更相似的结果。请注意，“拟合”特征函数实际上并不依赖于提供给fit函数的数据。仅使用数据的维度。有关该方法的详细信息，请参见[RR2007]。

对于给定的n_components值，RBFSampler通常不如Nystroem精确。RBFSampler计算成本更低，因此使用更大的特征空间更有效。

../_images/sphx_glr_plot_kernel_approximation_002.png — 比较精确的RBF核（左）和近似值（右）#

示例

RBF核的显式特征映射近似

6.7.3. 加性卡方核#

加性卡方核是直方图上的核，常用于计算机视觉。

此处使用的加性卡方核由下式给出：

\[k(x, y) = \sum_i \frac{2x_iy_i}{x_i+y_i}\]

这与sklearn.metrics.pairwise.additive_chi2_kernel并不完全相同。[VZ2010]的作者更喜欢上面的版本，因为它始终是正定的。由于核是加性的，因此可以分别处理所有分量\(x_i\)进行嵌入。这使得可以以规则的间隔对傅里叶变换进行采样，而不是使用蒙特卡洛采样进行近似。

类AdditiveChi2Sampler实现了这种分量级的确定性采样。每个分量被采样\(n\)次，每个输入维度产生\(2n+1\)维（2的倍数来自傅里叶变换的实部和虚部）。在文献中，\(n\)通常选择为1或2，将数据集转换为大小n_samples * 5 * n_features（在\(n=2\)的情况下）。

AdditiveChi2Sampler提供的近似特征映射可以与RBFSampler提供的近似特征映射相结合，以产生指数卡方核的近似特征映射。有关详细信息，请参见[VZ2010]，以及与RBFSampler结合的详细信息，请参见[VVZ2010]。

6.7.4. 偏斜卡方核#

偏斜卡方核定义如下：

\[k(x,y) = \prod_i \frac{2\sqrt{x_i+c}\sqrt{y_i+c}}{x_i + y_i + 2c}\]

它具有与计算机视觉中常用的指数卡方核相似的特性，但允许对特征映射进行简单的蒙特卡洛近似。

SkewedChi2Sampler 的用法与上面描述的 RBFSampler 用法相同。唯一的区别在于自由参数，称为 \(c\)。有关此映射的动机和数学细节，请参见 [LS2010]。

6.7.5. 基于张量草图的多项式核近似#

多项式核是一种流行的核函数，定义如下：

\[k(x, y) = (\gamma x^\top y +c_0)^d\]

其中

x、y 是输入向量
d 是核的阶数

直观地说，d 阶多项式核的特征空间由输入特征之间所有可能的 d 阶乘积组成，这使得使用此核的学习算法能够考虑特征之间的交互作用。

PolynomialCountSketch 中实现的张量草图 [PP2013] 方法是一种可扩展的、独立于输入数据的多项式核近似方法。它基于计数草图的概念 [WIKICS] [CCF2002]，这是一种类似于特征哈希的降维技术，它使用多个独立的哈希函数。张量草图获得了两个向量（或向量自身）外积的计数草图，这可以用作多项式核特征空间的近似值。特别是，张量草图不是显式地计算外积，而是计算向量的计数草图，然后使用快速傅里叶变换通过多项式乘法来计算其外积的计数草图。

方便的是，张量草图的训练阶段仅仅包括初始化一些随机变量。因此它独立于输入数据，即它只取决于输入特征的数量，而不取决于数据值。此外，此方法可以在 \(\mathcal{O}(n_{\text{samples}}(n_{\text{features}} + n_{\text{components}} \log(n_{\text{components}})))\) 时间内转换样本，其中 \(n_{\text{components}}\) 是所需的输出维度，由 n_components 确定。

示例