.. _kernel_approximation: 核近似 ====== 这个子模块包含了一些函数，这些函数近似于某些核所对应的特征映射，例如在支持向量机中使用的核（参见 :ref:`svm` ）。 以下特征函数执行输入的非线性变换，可以作为线性分类或其他算法的基。 .. currentmodule:: sklearn.linear_model 使用近似的显式特征映射相比于使用 `核技巧 `_ （该技巧隐式地利用特征映射）的优势在于，显式映射更适合在线学习，并且可以显著降低处理大型数据集时的学习成本。 标准的核化支持向量机在处理大型数据集时扩展性不佳，但使用近似核映射，可以更有效地使用线性支持向量机。 特别是，将核映射近似与 :class:`SGDClassifier` 结合使用，可以使大型数据集上的非线性学习成为可能。 由于使用近似嵌入的实证工作不多，建议在可能的情况下将结果与精确的核方法进行比较。 .. seealso:: :ref:`polynomial_regression` 用于精确的多项式变换。 .. currentmodule:: sklearn.kernel_approximation .. _nystroem_kernel_approx: Nystroem 方法用于核近似 ----------------------- Nystroem 方法，如在 :class:`Nystroem` 中实现的，是一种通用的方法，用于核的降秩近似。它通过无放回地抽样数据集的行/列来实现这一点，这些数据集是核评估的对象。虽然精确方法的计算复杂度为 :math:`\mathcal{O}(n^3_{\text{samples}})` ，但近似的复杂度为 :math:`\mathcal{O}(n^2_{\text{components}} \cdot n_{\text{samples}})` ，其中可以设置 :math:`n_{\text{components}} \ll n_{\text{samples}}` 而不会影响性能。 性能显著下降 [WS2001]_。 我们可以根据数据的特征构建核矩阵 :math:`K` 的特征分解，然后将其分为采样和未采样数据点。 .. math:: 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} 其中： * :math:`U` 是正交矩阵 * :math:`\Lambda` 是特征值的对角矩阵 * :math:`U_1` 是所选样本的正交矩阵 * :math:`U_2` 是未选样本的正交矩阵 已知 :math:`U_1 \Lambda U_1^T` 可以通过正交化矩阵 :math:`K_{11}` 获得，并且 :math:`U_2 \Lambda U_1^T` 及其转置可以被评估，唯一剩下的待阐明项是 :math:`U_2 \Lambda U_2^T` 。为此，我们可以用已经评估过的矩阵来表示它： .. math:: \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} 在 ``fit`` 过程中，类 :class:`Nystroem` 评估基 :math:`U_1` ，并计算归一化常数 :math:`K_{11}^{-\frac12}` 。之后，在 ``transform`` 过程中，核矩阵在基（由 `components_` 属性给出）和新数据点 ``X`` 之间确定。然后，该矩阵乘以 ``normalization_`` 矩阵以得到最终结果。 默认情况下，:class:`Nystroem` 使用 ``rbf`` 核，但它可以使用任何核。 函数或预计算的核矩阵。使用的样本数量——这也是计算特征的维度——由参数 ``n_components`` 给出。 .. rubric:: 示例 * 请参阅名为 :ref:`sphx_glr_auto_examples_applications_plot_cyclical_feature_engineering.py` 的示例， 该示例展示了一个使用 :class:`Nystroem` 核的高效机器学习流水线。 .. _rbf_kernel_approx: 径向基函数核 -------------- :class:`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`` 值，:class:`RBFSampler` 通常不如 :class:`Nystroem` 准确。然而，:class:`RBFSampler` 的计算成本较低，使得使用更大的特征空间更加高效。 .. figure:: ../auto_examples/miscellaneous/images/sphx_glr_plot_kernel_approximation_002.png :target: ../auto_examples/miscellaneous/plot_kernel_approximation.html :scale: 50% :align: center 比较精确的 RBF 核（左侧）与近似核（右侧） .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_miscellaneous_plot_kernel_approximation.py` .. _additive_chi_kernel_approx: 加性 Chi Squared 核 -------------------- 加性 Chi Squared 核是一种用于直方图的核函数，常用于计算机视觉领域。 此处使用的加性 Chi Squared 核定义为 .. math:: k(x, y) = \sum_i \frac{2x_iy_i}{x_i+y_i} 这与 :func:`sklearn.metrics.pairwise.additive_chi2_kernel` 不完全相同。[VZ2010]_ 的作者倾向于上述版本，因为它总是正定的。 由于该核是加性的，可以分别处理所有分量 :math:`x_i` 进行嵌入。这使得可以在常规间隔内采样傅里叶变换，而不是使用蒙特卡洛采样进行近似。 类 :class:`AdditiveChi2Sampler` 实现了这种分量级的确定性采样。每个分量被采样 :math:`n` 次，每个输入维度产生 :math:`2n+1` 维（两倍的倍数来自傅里叶变换的实部和虚部）。 在文献中，通常选择 :math:`n` 为 1 或 2，将数据集转换为大小 ``n_samples * 5 * n_features`` （在 :math:`n=2` 的情况下）。 :class:`AdditiveChi2Sampler` 提供的近似特征映射可以与 :class:`RBFSampler` 提供的近似特征映射结合，以产生一个近似的特征映射。 指数卡方核的特征图。 详情请参阅 [VZ2010]_，与 :class:`RBFSampler` 结合的说明请参阅 [VVZ2010]_。 .. _skewed_chi_kernel_approx: 偏斜卡方核 ------------ 偏斜卡方核定义如下： .. math:: k(x,y) = \prod_i \frac{2\sqrt{x_i+c}\sqrt{y_i+c}}{x_i + y_i + 2c} 它具有类似于计算机视觉中常用的指数卡方核的性质，但允许对特征图进行简单的蒙特卡洛近似。 :class:`SkewedChi2Sampler` 的使用方法与上述 :class:`RBFSampler` 的描述相同。唯一的区别在于自由参数，称为 :math:`c` 。 关于此映射的动机和数学细节，请参阅 [LS2010]_。 .. _polynomial_kernel_approx: 通过张量草图进行多项式核近似 --------------------------------- :ref:`多项式核 ` 是一种流行的核函数，定义如下： .. math:: k(x, y) = (\gamma x^\top y +c_0)^d 其中： * ``x`` , ``y`` 是输入向量 * ``d`` 是核的度数 直观上，多项式核的特征空间包含所有可能的度数为 `d` 的输入特征之间的乘积，这使得使用此核的学习算法能够考虑特征之间的交互作用。 张量草图 [PP2013]_ 方法，如在 :class:`PolynomialCountSketch` 中实现的，是一种可扩展的、与输入数据无关的多项式核近似方法。它基于计数草图 [WIKICS]_ [CCF2002]_ 的概念，这是一种类似于特征哈希的降维技术，但使用多个独立的哈希函数。张量草图获取两个向量（或向量与自身的）外积的计数草图，这可以作为多项式核特征空间的近似。特别是，它避免了显式计算 外积, TensorSketch 计算向量的 Count Sketch, 然后通过快速傅里叶变换进行多项式乘法来计算它们的外积的 Count Sketch。 方便的是, TensorSketch 的训练阶段仅包括初始化一些随机变量。因此, 它与输入数据无关, 即它仅依赖于输入特征的数量, 而不依赖于数据值。此外, 这种方法可以在 :math:`\mathcal{O}(n_{\text{samples}}(n_{\text{features}} + n_{\text{components}} \log(n_{\text{components}})))` 时间内转换样本, 其中 :math:`n_{\text{components}}` 是期望的输出维度, 由 ``n_components`` 决定。 .. rubric:: 示例 * :ref:`sphx_glr_auto_examples_kernel_approximation_plot_scalable_poly_kernels.py` .. _tensor_sketch_kernel_approx: 数学细节 -------- 支持向量机或核化 PCA 等核方法依赖于再生核希尔伯特空间的性质。对于任何正定核函数 :math:`k` (称为 Mercer 核), 可以保证存在一个映射 :math:`\phi` 到希尔伯特空间 :math:`\mathcal{H}` , 使得 .. math:: k(x,y) = \langle \phi(x), \phi(y) \rangle 其中 :math:`\langle \cdot, \cdot \rangle` 表示希尔伯特空间中的内积。 如果算法 (如线性支持向量机或 PCA) 仅依赖于数据点 :math:`x_i` 的标量积, 可以使用 :math:`k(x_i, x_j)` 的值, 这相当于将算法应用于映射后的数据点 :math:`\phi(x_i)` 。使用 :math:`k` 的优点是映射 :math:`\phi` 永远不需要显式计算, 允许任意大的特征 (甚至是无限的)。 核方法的一个缺点是, 在优化过程中可能需要存储许多核值 :math:`k(x_i, x_j)` 。如果将核化分类器应用于新数据 :math:`y_j` , :math:`k(x_i, y_j)` 需要被计算以进行预测，可能针对训练集中的许多不同的 :math:`x_i` 。 此子模块中的类允许近似嵌入 :math:`\phi` ，从而显式地处理表示 :math:`\phi(x_i)` ，这避免了应用核函数或存储训练样本的需要。 .. rubric:: 参考文献 .. [WS2001] `"Using the Nyström method to speed up kernel machines" `_ Williams, C.K.I.; Seeger, M. - 2001. .. [RR2007] `"Random features for large-scale kernel machines" `_ Rahimi, A. and Recht, B. - Advances in neural information processing 2007, .. [LS2010] `"Random Fourier approximations for skewed multiplicative histogram kernels" `_ Li, F., Ionescu, C., and Sminchisescu, C. - Pattern Recognition, DAGM 2010, Lecture Notes in Computer Science. .. [VZ2010] `"Efficient additive kernels via explicit feature maps" `_ Vedaldi, A. and Zisserman, A. - Computer Vision and Pattern Recognition 2010 .. [VVZ2010] `"Generalized RBF feature maps for Efficient Detection" `_ Vempati, S. and Vedaldi, A. and Zisserman, A. and Jawahar, CV - 2010 .. [PP2013] :doi:`"Fast and scalable polynomial kernels via explicit feature maps" <10.1145/2487575.2487591>` Pham, N., & Pagh, R. - 2013 .. [CCF2002] `"Finding frequent items in data streams" `_ Charikar, M., Chen, K., & Farach-Colton - 2002 .. [WIKICS] `"Wikipedia: Count sketch" `_