使用多项式核函数近似进行可扩展学习#
此示例说明了使用 PolynomialCountSketch 有效地生成多项式核特征空间近似值。这用于训练线性分类器，以近似于核化分类器的精度。
我们使用 Covtype 数据集 [2]，试图重现 Tensor Sketch [1] 原论文中的实验，即 PolynomialCountSketch 实现的算法。
首先，我们计算线性分类器在原始特征上的精度。然后，我们使用 PolynomialCountSketch 生成的不同数量的特征 (n_components) 训练线性分类器，以可扩展的方式近似于核化分类器的精度。
# Author: Daniel Lopez-Sanchez <[email protected]>
# License: BSD 3 clause
准备数据#
加载 Covtype 数据集，该数据集包含 581,012 个样本，每个样本具有 54 个特征，分布在 6 个类别中。该数据集的目标是仅从制图变量（无遥感数据）预测森林覆盖类型。加载后，我们将它转换为二元分类问题，以匹配 LIBSVM 网页 [2] 中的数据集版本，该版本是 [1] 中使用的版本。
from sklearn.datasets import fetch_covtype
X, y = fetch_covtype(return_X_y=True)
y[y != 2] = 0
y[y == 2] = 1 # We will try to separate class 2 from the other 6 classes.
划分数据#
这里我们选择 5,000 个样本用于训练，10,000 个样本用于测试。为了真正重现 Tensor Sketch 原论文中的结果，选择 100,000 个样本用于训练。
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(
X, y, train_size=5_000, test_size=10_000, random_state=42
)
特征归一化#
现在将特征缩放到 [0, 1] 范围内，以匹配 LIBSVM 网页中数据集的格式，然后按照 Tensor Sketch 原论文 [1] 中的步骤进行单位长度归一化。
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import MinMaxScaler, Normalizer
mm = make_pipeline(MinMaxScaler(), Normalizer())
X_train = mm.fit_transform(X_train)
X_test = mm.transform(X_test)
建立基线模型#
作为基线，在原始特征上训练线性 SVM 并打印精度。我们还测量并存储精度和训练时间，以便稍后绘制它们。
import time
from sklearn.svm import LinearSVC
results = {}
lsvm = LinearSVC()
start = time.time()
lsvm.fit(X_train, y_train)
lsvm_time = time.time() - start
lsvm_score = 100 * lsvm.score(X_test, y_test)
results["LSVM"] = {"time": lsvm_time, "score": lsvm_score}
print(f"Linear SVM score on raw features: {lsvm_score:.2f}%")
Linear SVM score on raw features: 75.62%
建立核函数近似模型#
然后，我们在 PolynomialCountSketch 生成的特征上训练线性 SVM，n_components 具有不同的值，表明这些核特征近似值提高了线性分类的精度。在典型的应用场景中，n_components 应该大于输入表示中的特征数量，以便相对于线性分类实现改进。作为经验法则，评估分数/运行时间成本的最佳值通常在 n_components = 10 * n_features 左右实现，尽管这可能取决于正在处理的特定数据集。请注意，由于原始样本具有 54 个特征，因此四阶多项式核的显式特征映射将大约有 850 万个特征（准确地说，是 54^4）。多亏了 PolynomialCountSketch，我们可以将该特征空间的大部分判别信息压缩成更紧凑的表示。虽然在本示例中我们只运行一次实验 (n_runs = 1)，但在实践中，应该重复实验几次以弥补 PolynomialCountSketch 的随机性。
from sklearn.kernel_approximation import PolynomialCountSketch
n_runs = 1
N_COMPONENTS = [250, 500, 1000, 2000]
for n_components in N_COMPONENTS:
ps_lsvm_time = 0
ps_lsvm_score = 0
for _ in range(n_runs):
pipeline = make_pipeline(
PolynomialCountSketch(n_components=n_components, degree=4),
LinearSVC(),
)
start = time.time()
pipeline.fit(X_train, y_train)
ps_lsvm_time += time.time() - start
ps_lsvm_score += 100 * pipeline.score(X_test, y_test)
ps_lsvm_time /= n_runs
ps_lsvm_score /= n_runs
results[f"LSVM + PS({n_components})"] = {
"time": ps_lsvm_time,
"score": ps_lsvm_score,
}
print(
f"Linear SVM score on {n_components} PolynomialCountSketch "
+ f"features: {ps_lsvm_score:.2f}%"
)
Linear SVM score on 250 PolynomialCountSketch features: 76.55%
Linear SVM score on 500 PolynomialCountSketch features: 76.92%
Linear SVM score on 1000 PolynomialCountSketch features: 77.79%
Linear SVM score on 2000 PolynomialCountSketch features: 78.59%
建立核化 SVM 模型#
训练一个核化 SVM，看看 PolynomialCountSketch 如何近似于核的性能。当然，这可能需要一些时间，因为 SVC 类具有相对较差的可扩展性。这就是核近似器如此有用的原因。
from sklearn.svm import SVC
ksvm = SVC(C=500.0, kernel="poly", degree=4, coef0=0, gamma=1.0)
start = time.time()
ksvm.fit(X_train, y_train)
ksvm_time = time.time() - start
ksvm_score = 100 * ksvm.score(X_test, y_test)
results["KSVM"] = {"time": ksvm_time, "score": ksvm_score}
print(f"Kernel-SVM score on raw features: {ksvm_score:.2f}%")
Kernel-SVM score on raw features: 79.78%
比较结果#
最后，将不同方法的结果与其训练时间进行比较。正如我们所见，核化 SVM 实现了更高的精度，但其训练时间长得多，最重要的是，如果训练样本数量增加，其训练时间将增长得更快。
import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(7, 7))
ax.scatter(
[
results["LSVM"]["time"],
],
[
results["LSVM"]["score"],
],
label="Linear SVM",
c="green",
marker="^",
)
ax.scatter(
[
results["LSVM + PS(250)"]["time"],
],
[
results["LSVM + PS(250)"]["score"],
],
label="Linear SVM + PolynomialCountSketch",
c="blue",
)
for n_components in N_COMPONENTS:
ax.scatter(
[
results[f"LSVM + PS({n_components})"]["time"],
],
[
results[f"LSVM + PS({n_components})"]["score"],
],
c="blue",
)
ax.annotate(
f"n_comp.={n_components}",
(
results[f"LSVM + PS({n_components})"]["time"],
results[f"LSVM + PS({n_components})"]["score"],
),
xytext=(-30, 10),
textcoords="offset pixels",
)
ax.scatter(
[
results["KSVM"]["time"],
],
[
results["KSVM"]["score"],
],
label="Kernel SVM",
c="red",
marker="x",
)
ax.set_xlabel("Training time (s)")
ax.set_ylabel("Accuracy (%)")
ax.legend()
plt.show()
参考文献#
[1] Pham, Ninh 和 Rasmus Pagh。“通过显式特征映射实现快速且可扩展的多项式核。”KDD '13 (2013)。https://doi.org/10.1145/2487575.2487591
[2] LIBSVM 二元数据集存储库 https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html
脚本的总运行时间：（0 分钟 22.155 秒）
相关示例
