企业官网建设流程全解析

scikit-learn 核近似（Kernel Approximation）完全指南：从 Nystroem 到 Tensor Sketch 的大规模非线性学习

【免费下载链接】scikit-learnscikit-learn: machine learning in Python项目地址: https://gitcode.com/gh_mirrors/sc/scikit-learn

导读

在支持向量机等核方法中，核技巧（Kernel Trick）通过隐式特征映射避免了显式计算高维特征，但代价是优化过程中需要存储和计算大量核矩阵元素，难以扩展到大规模数据集。scikit-learn 的sklearn.kernel_approximation子模块提供了一组显式近似特征映射（如Nystroem、RBFSampler、AdditiveChi2Sampler、SkewedChi2Sampler、PolynomialCountSketch），将输入做非线性变换后作为线性分类器（如SGDClassifier、LinearSVC）的输入，从而在超大数据集上实现非线性学习。读完本文，你将掌握各类核逼近方法的数学原理、参数含义、源码实现细节与典型应用场景，并能在实际 Pipeline 中正确选用与调参。

本文主体基于 kernel_approximation.rst，并结合 sklearn/kernel_approximation.py、测试文件 及官方示例进行源码级佐证。

为什么需要核逼近：显式映射 vs 隐式核技巧

核方法（如核 SVM、核 PCA）依赖再生核希尔伯特空间（RKHS）的一个性质：对任意正定核函数 $k$（即 Mercer 核），必定存在一个映射 $\phi$ 进入希尔伯特空间 $\mathcal{H}$，使得

$$ k(x,y) = \langle \phi(x), \phi(y) \rangle $$

其中 $\langle \cdot, \cdot \rangle$ 表示希尔伯特空间中的内积。如果一个算法（如线性 SVM 或 PCA）只依赖数据点 $x_i$ 的标量积，就可以用 $k(x_i, x_j)$ 代替 $\langle \phi(x_i), \phi(x_j) \rangle$，相当于把算法作用在映射后的数据点 $\phi(x_i)$ 上。使用 $k$ 的好处是 $\phi$ 永远无需显式计算，允许任意大（甚至无穷维）的特征空间。

核方法的一个缺点是：优化过程中可能不得不存储大量核值 $k(x_i, x_j)$；当把训练好的核分类器应用到新数据 $y_j$ 时，需要计算 $k(x_i, y_j)$，可能要针对训练集中的许多不同 $x_i$ 逐一计算。

sklearn.kernel_approximation子模块中的类允许我们显式逼近嵌入 $\phi$，直接以 $\phi(x_i)$ 表示工作，从而避免应用核技巧或存储训练样本。与隐式核技巧相比，显式特征映射的优势在于：

• 更适合在线学习（online learning）；
• 能显著降低超大数据集上的学习成本；
• 标准核化 SVM 难以扩展到大数据集，而使用近似核映射后，可以改用高效得多的线性 SVM。

特别地，核逼近与SGDClassifier（随机梯度下降线性分类器）的组合，使得大规模数据集上的非线性学习成为可能。scikit-learn 官方在 svm.rst 中也明确指出：需要更快、更可扩展的 RBF 核解决方案时，请参见kernel_approximation章节。

注意：由于针对近似嵌入的实证研究相对较少，官方建议在条件允许时，将逼近结果与精确核方法的结果进行对比验证。

Nystroem 方法：基于数据子集的低秩核逼近

方法原理

Nystroem 类实现了 Nystroem 方法，这是一种通用的核矩阵降秩近似方法。它通过在数据上无放回地子采样（subsampling without replacement）核矩阵的行/列来达到目的。

精确方法的计算复杂度为 $\mathcal{O}(n_{\text{samples}}^3)$，而近似方法的复杂度为 $\mathcal{O}(n_{\text{components}}^2 \cdot n_{\text{samples}})$，其中可以设置 $n_{\text{components}} \ll n_{\text{samples}}$ 而不会显著降低性能（见 Williams & Seeger, 2001）。

可以基于数据特征构造核矩阵 $K$ 的特征分解，然后将其拆分为已采样与未采样的数据点：

$$ 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} $$

其中：

• $U$ 是正交矩阵（orthonormal）；
• $\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{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} 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 / transform 分工

对照源码 sklearn/kernel_approximation.py 可以看到：

• 在fit阶段，Nystroem评估基 $U_1$，并计算归一化常数 $K_{11}^{-\frac12}$。具体实现是：用check_random_state打乱样本序号（rnd.permutation(n_samples)），取前n_components个作为基向量，调用pairwise_kernels计算基上的核矩阵basis_kernel，再通过 SVD（xp.linalg.svd）并裁剪奇异值下界（xp.clip(S, 1e-12, None)）得到normalization_矩阵。
• 在transform阶段，计算基（由components_属性给出）与新数据点X之间的核矩阵，然后将该矩阵乘以normalization_矩阵得到最终结果（embedded @ self.normalization_.T）。

从源码结构看，components_保存的是用于构造特征映射的训练点子集（形状(n_components, n_features)），component_indices_保存这些点在训练集中的下标，normalization_是嵌入所需的归一化矩阵（基上核矩阵的平方根）。

参数说明

默认情况下，Nystroem使用rbf核，但可以使用任意核函数或预计算核矩阵。关键参数：

需要注意的使用细节（源码中均有约束或测试佐证）：

• 若n_components > n_samples，源码会发出警告并将n_components截断为n_samples，此时退化为低效的全核求值（见 fit 实现）。
• 若使用 callable 或"precomputed"核，就不能再传gamma/coef0/degree，否则抛出ValueError（见 _get_kernel_params）。

实战示例

Nystroem 的官方 docstring 示例（sklearn/kernel_approximation.py）展示了它与线性 SVM 的组合：

>>> from sklearn import datasets, svm >>> from sklearn.kernel_approximation import Nystroem >>> X, y = datasets.load_digits(n_class=9, return_X_y=True) >>> data = X / 16. >>> clf = svm.LinearSVC() >>> feature_map_nystroem = Nystroem(gamma=.2, random_state=1, n_components=300) >>> data_transformed = feature_map_nystroem.fit_transform(data) >>> clf.fit(data_transformed, y) LinearSVC() >>> clf.score(data_transformed, y) 0.9987...

在 plot_cyclical_feature_engineering.py 示例中，作者在自行车租赁数据上先用样条（spline）特征做周期特征工程，再用Nystroem(kernel="poly", degree=2, n_components=300, random_state=0)逼近多项式核以建模"workingday"与"hours"等特征间的非线性交互，最后接RidgeCV。该示例说明：虽然 Pipeline 的最终步骤是线性回归，但中间的样条特征提取与 Nyström 核逼近都是高度非线性的，组合后的 Pipeline 远比原始特征上的线性回归表达能力强。

RBF 核：RBFSampler 与 Random Kitchen Sinks

方法原理

RBFSampler 构造径向基函数（RBF）核的近似映射，该方法也被称为Random Kitchen Sinks（Rahimi & Recht, 2007）。该变换可用于在应用线性算法（例如线性 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

该映射依赖对核值的Monte Carlo 近似（即随机傅里叶特征）：fit函数执行 Monte Carlo 采样，transform方法执行数据映射。由于过程本身具有随机性，不同fit调用之间结果可能不同。

fit 的两个核心参数与源码细节

fit函数有两个关键参数：

• n_components：特征变换的目标维度。n_components越大，对核的逼近越好，结果越接近核 SVM 的输出。注意：fit实际上不依赖传入的数据值，只用数据的维度。
• gamma：RBF 核参数（$e^{-\gamma x^2}$）。除浮点数外，从 1.2 版本开始支持字符串'scale'，此时使用 $1 / (n_features \cdot X.var())$ 作为 gamma 值（见 fit 实现），测试 test_rbf_sampler_gamma_scale 验证了这一行为。

从源码 RBFSampler.fit 可以确认底层实现细节：

1. 随机权重random_weights_的生成：(2.0 * self._gamma) ** 0.5 * random_state.normal(size=(n_features, n_components))，即从 RBF 核的傅里叶变换（高斯分布）中采样；
2. 随机偏移random_offset_在 $[0, 2\pi)$ 上均匀采样，形状为(n_components,)；
3. transform阶段先做safe_sparse_dot(X, self.random_weights_)，加上偏移后取cos，最后乘以 $(2.0 / n_components)^{0.5}$ 做归一化（见 transform）。

值得注意的两个工程细节：

• random_weights_与random_offset_的 dtype 会跟随输入X的 dtype（float32输入得到float32的拟合属性），测试 test_rbf_sampler_fitted_attributes_dtype 与 test_rbf_sampler_dtype_equivalence 分别验证了 dtype 保持与 32/64 位结果等价性；
• 支持稀疏输入（accept_sparse="csr"）。

与 Nystroem 的取舍

在给定的n_components下，RBFSampler的精度通常不如Nystroem（Nystroem 基于实际数据子集，而 RBFSampler 与数据无关）。但RBFSampler计算更廉价，因此利用更大的特征空间更高效。

在 plot_kernel_approximation.py 示例中，两者被系统对比：示例用RBFSampler(gamma=0.2, random_state=1)和Nystroem(gamma=0.2, random_state=1)分别逼近 RBF 核，在不同n_components下训练线性 SVM，并与精确 RBF 核 SVM、原始特征上的线性 SVM 比较精度与耗时，直观展示了"以特征维度换取训练时间"的权衡。

加法卡方核：AdditiveChi2Sampler

核函数与设计动机

加法卡方核（additive chi squared kernel）是作用在直方图上的核，常用于计算机视觉。本文档使用的形式为：

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

这与sklearn.metrics.pairwise.additive_chi2_kernel并不完全相同——[VZ2010] 的作者偏好上述版本，因为它总是正定的。

由于该核是可加的（additive），可以把所有分量 $x_i$ 分开进行嵌入处理。这使得可以在规则间隔上采样傅里叶变换，而不必用 Monte Carlo 采样近似。

参数与特征维度

AdditiveChi2Sampler 实现这种逐分量的确定性采样。每个分量被采样 $n$ 次，每个输入维度产生 $2n+1$ 个维度（因子 2 来自傅里叶变换的实部与虚部）。文献中 $n$ 通常取 1 或 2，此时数据集被变换为大小n_samples * 5 * n_features（$n=2$ 的情形）。

源码中，transform阶段在sample_interval=None时会根据sample_steps自动选取经验最优间隔：sample_steps=1取 0.8、sample_steps=2取 0.5、sample_steps=3取 0.4（见 transform 实现）；若sample_steps不在 {1,2,3} 且未提供sample_interval，则抛出ValueError（fit），测试 test_additive_chi2_sampler_wrong_sample_steps 覆盖了该场景。

每个输出分量的构造遵循 [VZ2010] 的公式：第 0 个分量为sqrt(X * sample_interval)（sech的 0 阶项），第 j 个分量对为factor * cos(j * log(X) * sample_interval)与factor * sin(...)，其中factor = sqrt(2 * X * sample_interval / cosh(pi * j * sample_interval))（见 _transform_dense）。输出特征形状为(n_samples, n_features * (2 * sample_steps - 1))，且支持稀疏矩阵输入（_transform_sparse），输入必须为非负（ensure_non_negative=True）。

该类是**无状态（stateless）**的：fit只做参数校验，不依赖数据。官方建议调用fit_transform而非transform，因为参数校验只在fit中执行（见类 docstring 的 Notes 部分）。

与其他核的组合

AdditiveChi2Sampler提供的近似特征映射可以与RBFSampler的近似特征映射组合，得到**指数化卡方核（exponentiated chi squared kernel）**的近似特征映射。数学细节见 [VZ2010]，与RBFSampler的组合见 [VVZ2010]。

偏斜卡方核：SkewedChi2Sampler

偏斜卡方核（skewed chi squared kernel）定义为：

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

它拥有与常用于计算机视觉的指数化卡方核相似的属性，但允许对特征映射进行简单的 Monte Carlo 近似。

SkewedChi2Sampler 的用法与RBFSampler完全相同，唯一区别在于自由参数名为skewedness（即上式中的 $c$），官方注释建议该参数需要交叉验证。数学动机与细节见 [LS2010]。

从源码看：

• fit阶段从均匀分布采样并用 secant hyperbolic 分布的逆 CDF 变换得到随机权重：1.0 / np.pi * np.log(np.tan(np.pi / 2.0 * uniform))，同时采样 $[0, 2\pi)$ 上的随机偏移（见 SkewedChi2Sampler.fit）；
• transform阶段要求输入 X 的所有值严格大于-skewedness，否则抛出ValueError("X may not contain entries smaller than -skewedness.")；随后对X + skewedness取对数再做投影、加偏移、取cos并按sqrt(2) / sqrt(n_components)归一化（见 transform）。

docstring 示例（sklearn/kernel_approximation.py）：

>>> from sklearn.kernel_approximation import SkewedChi2Sampler >>> from sklearn.linear_model import SGDClassifier >>> X = [[0, 0], [1, 1], [1, 0], [0, 1]] >>> y = [0, 0, 1, 1] >>> chi2_feature = SkewedChi2Sampler(skewedness=.01, n_components=10, random_state=0) >>> X_features = chi2_feature.fit_transform(X, y) >>> clf = SGDClassifier(max_iter=10, tol=1e-3) >>> clf.fit(X_features, y) SGDClassifier(max_iter=10) >>> clf.score(X_features, y) 1.0

多项式核逼近：PolynomialCountSketch 与 Tensor Sketch

核函数与特征空间直觉

多项式核（polynomial kernel）是一类流行的核函数，定义为：

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

其中 $x, y$ 是输入向量，$d$ 是核度数。直觉上，度数 $d$ 的多项式核的特征空间由输入特征间所有可能的度 $d$ 乘积组成，这使得使用该核的学习算法能够刻画特征之间的交互作用。

Tensor Sketch 方法

PolynomialCountSketch 实现了TensorSketch[PP2013] 方法，这是一种可扩展、与输入数据无关的多项式核逼近方法。它基于Count sketch[WIKICS][CCF2002] 的概念——一种与特征哈希类似的降维技术，但使用若干独立的哈希函数。TensorSketch 计算两个向量（或一个向量与自身）外积的 Count Sketch，作为多项式核特征空间的近似。特别地，它不显式计算外积，而是：

1. 计算各向量的 Count Sketch；
2. 通过**快速傅里叶变换（FFT）**做多项式乘法，得到外积的 Count Sketch。

因此，TensorSketch 的训练阶段只是初始化一些随机变量，与输入数据无关——只依赖输入特征数，不依赖数据取值。此外，该方法可以在 $\mathcal{O}(n_{\text{samples}}(n_{\text{features}} + n_{\text{components}} \log(n_{\text{components}})))$ 时间内变换样本，其中 $n_{\text{components}}$ 由n_components决定。

参数与源码实现

源码中，fit生成两组随机变量（见 PolynomialCountSketch.fit）：

• indexHash_：形状(degree, n_features)的 int64 数组，取值在 $[0, n_components)$ 内，表示 Count Sketch 的 2-wise 独立哈希函数；
• bitHash_：形状(degree, n_features)的 float32 数组，随机取 ${+1, -1}$。

若coef0 != 0，特征数会加一（在训练与变换两端都追加一列 $\sqrt{coef0}$，见 transform）。transform阶段对每个样本计算各阶的 Count Sketch，再对最后一维做 FFT、逐阶相乘、逆 FFT 取实部（fft→np.prod→ifft，见 transform），并支持 CSC 稀疏输入。

docstring 示例（sklearn/kernel_approximation.py）：

>>> from sklearn.kernel_approximation import PolynomialCountSketch >>> from sklearn.linear_model import SGDClassifier >>> X = [[0, 0], [1, 1], [1, 0], [0, 1]] >>> y = [0, 0, 1, 1] >>> ps = PolynomialCountSketch(degree=3, random_state=1) >>> X_features = ps.fit_transform(X) >>> clf = SGDClassifier(max_iter=10, tol=1e-3) >>> clf.fit(X_features, y) SGDClassifier(max_iter=10) >>> clf.score(X_features, y) 1.0

大规模实战：Covtype 数据集示例

plot_scalable_poly_kernels.py 展示了完整的对比实验流程：

1. 加载 Covtype 数据集（581,012 个样本、54 个特征、6 个类别），并转换为二分类问题（分离类别 2 与其他 6 类）；
2. 划分训练/测试集（示例用 5,000/10,000，论文复现则用 100,000 训练）；
3. 用MinMaxScaler+Normalizer做特征归一化；
4. 建立基线：原始特征上的LinearSVC；
5. 对n_components ∈ [250, 500, 1000, 2000]分别构建PolynomialCountSketch(n_components=..., degree=4)+LinearSVC的 Pipeline；
6. 训练核化 SVM（SVC(C=500.0, kernel="poly", degree=4, coef0=0, gamma=1.0)）作为精确参照；
7. 绘制"训练时间 vs 准确率"散点图。

示例注释强调：原始样本有 54 个特征，而 4 阶多项式核的显式特征映射约有 850 万个特征（精确值为 $54^4$）；借助PolynomialCountSketch，可以把该特征空间中大部分判别信息压缩到紧凑得多的表示中。由于该方法具有随机性，实践中应多次重复实验取均值。测试 test_polynomial_count_sketch 以多种gamma/degree/n_components组合验证了其逼近精度，test_polynomial_count_sketch_dense_sparse 验证了稠密与稀疏输入的一致性。

方法选型与最佳实践

各方法适用场景速查

组合使用与验证建议

• 各近似类都是标准的 scikit-learn Transformer（继承TransformerMixin/BaseEstimator，支持fit_transform、get_feature_names_out），可直接放进make_pipeline，如上文 Nystroem 与RidgeCV、PolynomialCountSketch 与LinearSVC的组合；
• 将显式近似映射与SGDClassifier组合，是官方文档明确推荐的在超大数据集上做非线性学习的方式（在线学习 + 线性复杂度）；
• 由于近似嵌入的实证研究有限，官方建议在可行时与精确核方法对比；对于随机方法（RBFSampler、SkewedChi2Sampler、PolynomialCountSketch），务必设置random_state并多次运行取平均，以抵消随机性带来的方差；
• 增大n_components普遍能提升逼近质量，但会线性增加特征维度与下游线性模型的计算/内存开销，需结合具体数据集权衡。

参考资料

• [WS2001] Williams, C.K.I.; Seeger, M. —"Using the Nyström method to speed up kernel machines", NIPS 2001。
• [RR2007] Rahimi, A. and Recht, B. —"Random features for large-scale kernel machines", NIPS 2007。
• [LS2010] Li, F., Ionescu, C., and Sminchisescu, C. —"Random Fourier approximations for skewed multiplicative histogram kernels", DAGM 2010。
• [VZ2010] Vedaldi, A. and Zisserman, A. —"Efficient additive kernels via explicit feature maps", CVPR 2010。
• [VVZ2010] Vempati, S., Vedaldi, A., Zisserman, A., and Jawahar, C.V. —"Generalized RBF feature maps for Efficient Detection", 2010。
• [PP2013] Pham, N. & Pagh, R. —"Fast and scalable polynomial kernels via explicit feature maps", KDD 2013（DOI: 10.1145/2487575.2487591）。
• [CCF2002] Charikar, M., Chen, K., and Farach-Colton —"Finding frequent items in data streams", 2002。
• [WIKICS] Wikipedia —"Count sketch"。

以上方法的完整实现与参数约束可在 sklearn/kernel_approximation.py 中查阅，行为验证参见 sklearn/tests/test_kernel_approximation.py，更深入的使用范例见 examples/kernel_approximation/plot_scalable_poly_kernels.py、examples/miscellaneous/plot_kernel_approximation.py 与 examples/applications/plot_cyclical_feature_engineering.py。

【免费下载链接】scikit-learnscikit-learn: machine learning in Python项目地址: https://gitcode.com/gh_mirrors/sc/scikit-learn