机器算法验证 - 如何知道数据是否线性可分？ - 吾爱随笔录

机器算法验证机器学习物流支持向量机数据挖掘分离

2022-01-16 05:19:00

数据具有许多特征（例如 100），实例数约为 100,000。数据稀疏。我想使用逻辑回归或 svm 来拟合数据。我如何知道特征是线性的还是非线性的，以便在非线性时可以使用内核技巧？

3个回答

有几种方法可以确定数据是否线性可分，本文重点介绍了其中的一些方法 (1)。假设数据集中有两个类，以下是几种确定它们是否线性可分的方法：

线性规划：定义受满足线性可分性约束的目标函数。您可以在此处找到有关实施的详细信息。
感知器方法：如果数据是线性可分的，则感知器保证收敛。
二次规划：二次规划优化目标函数可以像在 SVM 中那样用约束来定义。
计算几何：如果可以找到两个不相交的凸包，则数据是线性可分的
聚类方法：如果使用一些聚类方法（例如k-means）可以找到两个聚类纯度为100％的聚类，则数据是线性可分的。

(1)：Elizondo, D.，“线性可分性问题：一些测试方法”，载于神经网络，IEEE Transactions on，第 17 卷，第 2 期，第 330-344 页，2006 年 3 月 doi: 10.1109/TNN。 2005.860871

我假设您谈论的是 2 类分类问题。在这种情况下，有一条线将您的两个类分开，任何经典算法都应该能够在它收敛时找到它。

在实践中，您必须对相同的数据进行训练和测试。如果有这样一条线，那么您应该接近 100% 准确度或 100% AUC。如果没有这样一条线，那么对相同数据的训练和测试至少会导致一些错误。根据错误的数量，它可能值得尝试非线性分类器，也可能不值得尝试。

考虑硬边距 SVM 公式，它试图找到一个严格分离数据的超平面。

m i n_{w, b} | | w | |^{2}

$min_{w,b} \space ||w||^2$

s . t \forall i, (w^{'} x_{i} + b) y_{i} \geq 1

$s.t \space \forall i, (w'x_{i} + b)y_{i} \ge 1$

如果我们的数据是线性可分的，那么所有的不等式约束都将得到满足。请注意，仅表示点位于平面的哪一侧。知道 SVM 问题的可行性就等于知道我们的数据是否线性可分。然而，我们实际上并不太关心简单检查线性可分性的目标。我们能解决一个更简单的可行性问题，比如线性规划吗？ $w'x + b$

可以解出以下LP来检验可行性。

m i n_{s, b, w} s

$min_{s,b, w} \space s$

s . t \forall i, (w^{'} x_{i} + b) y_{i} \geq 1 - s

$s.t \space \forall i, (w'x_{i} + b)y_{i} \ge 1 - s$

s \geq 0

$s \ge 0$

如果这个问题的最优为零，我们知道可以满足原始的不等式约束。这意味着我们的数据在原始空间中是线性可分的。为每个训练示例使用单独可以告诉我们哪些数据点导致线性不可分。 $s$ $s_i$

其它你可能感兴趣的问题