在机器学习领域,核方法是一种强大的技术,它允许在高维空间中有效地进行分类和回归。然而,这些方法通常计算成本很高,尤其是在大规模数据集上。为了解决这个问题,可以使用多项式计数草图(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,看看多项式计数草图是如何近似核性能的。当然,这可能需要一些时间,因为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).