多项式计数草图与线性分类器

在机器学习领域,核方法是一种强大的技术,它允许在高维空间中有效地进行分类和回归。然而,这些方法通常计算成本很高,尤其是在大规模数据集上。为了解决这个问题,可以使用多项式计数草图(PolynomialCountSketch)来近似核特征空间,从而训练线性分类器以模拟核化分类器的准确性。

数据准备

使用Covtype数据集,该数据集包含581,012个样本,每个样本有54个特征,分布在6个类别中。这个数据集的目标是根据地图变量(而不是遥感数据)预测森林覆盖类型。加载数据后,将其转换为二元分类问题,以匹配LIBSVM网页上的版本,这也是原始Tensor Sketch论文中使用的数据集。

from sklearn.datasets import fetch_covtype X, y = fetch_covtype(return_X_y=True) y[y != 2] = 0 y[y == 2] = 1 # 将尝试将类别2与其他6个类别分开。

数据划分

在这里,选择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论文中所做的。

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"线性SVM在原始特征上的得分: {lsvm_score:.2f}%") # 线性SVM在原始特征上的得分: 75.62%

建立核近似模型

然后使用多项式计数草图生成的特征训练线性SVM,展示这些核特征近似提高了线性分类的准确性。在典型的应用场景中,n_components应该大于输入表示中的特征数量,以实现与线性分类相比的改进。通常,评估分数/运行时间成本的最优值通常在n_components = 10 * n_features左右,尽管这可能取决于正在处理的具体数据集。

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"在{n_components}多项式计数草图特征上的线性SVM得分: {ps_lsvm_score:.2f}%") # 在250多项式计数草图特征上的线性SVM得分: 76.55% # 在500多项式计数草图特征上的线性SVM得分: 76.92% # 在1000多项式计数草图特征上的线性SVM得分: 77.79% # 在2000多项式计数草图特征上的线性SVM得分: 78.59%

建立核化SVM模型

训练一个核化SVM,看看多项式计数草图是如何近似核性能的。当然,这可能需要一些时间,因为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"在原始特征上的核SVM得分: {ksvm_score:.2f}%") # 在原始特征上的核SVM得分: 79.78%

比较结果

最后,绘制不同方法的结果与它们的训练时间。可以看到,核化SVM实现了更高的准确率,但其训练时间要大得多,而且如果训练样本的数量增加,其增长速度会更快。

import matplotlib.pyplot as plt fig, ax = plt.subplots(figsize=(7, 7)) ax.scatter( [results["LSVM"]["time"]], [results["LSVM"]["score"]], label="线性SVM", c="green", marker="^", ) ax.scatter( [results["LSVM + PS(250)"]["time"]], [results["LSVM + PS(250)"]["score"]], label="线性SVM + 多项式计数草图", 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="核SVM", c="red", marker="x", ) ax.set_xlabel("训练时间 (s)") ax.set_ylabel("准确率 (%)") ax.legend() plt.show()

[1] Pham, Ninh 和 Rasmus Pagh. “快速且可扩展的多项式核通过显式特征映射.” KDD ‘13 (2013).

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485