什么是破碎一组点和 VC 维度
破碎是机器学习中的一个关键概念，指的是分类器准确区分一组点的任意标记的能力。严格地说，如果分类器可以将一组点划分为所有可行的二进制类别，则分类器会破碎它们。分类器能够破碎的最大点数由 VC 维度指定，该维度衡量分类器对数据进行分类的能力。对于机器学习的从业者来说，理解破碎和 VC 维度的概念至关重要。在这篇文章中，我们将仔细研究破碎一组点的 VC 维度。
什么是破碎一组点?
当分类器能够正确区分点的任何潜在标记时，它被称为"破碎"一组点。更准确地说，如果分类器可以正确地对每个潜在的正或负标记点进行分类，那么它就打破了一组点。
换句话说，如果我们在空间中有一组点，我们可以将每个点标记为正或负。如果分类器可以准确地将点分为正组和负组，而不管我们如何选择标记它们，那么这组点就被称为破碎的。
以二维空间中的一组点为例。每个点旁边都可以放置红色或蓝色标签。如果分类器可以在平面上画一条线，一侧是所有红点，另一侧是所有蓝点，那么它就可以对一组点进行样条处理。这表明，每个标记为红色或蓝色的点都会导致分类器正确地对其进行分类。
什么是 VC 维度?
VC 维度是机器学习中的一个关键概念，它量化了分类器理解数据中复杂模式的能力。分类器能够分成两个或更多不同区域的最大点组就是所谓的最大集合的大小。分类器的 VC 维度和其分解点集的能力密切相关，VC 维度越大，分解复杂点集的能力越强。相反，VC 维度较低的分类器难以理解复杂模式，并且更有可能过度拟合或欠拟合数据。
样本可用于显示分解一组点和 VC 维度之间的关系。例如，在二维空间中，线性分类器的 VC 维度为 2，这表明它可以分解每组两个点，但不能分解所有组三个点。与此相反，二维空间中的多项式分类器的 VC 维度会随着多项式的次数而增加，从而使其能够分解越来越复杂的点集。
查找 VC 维度
查找分类器的 VC 维度需要计算在考虑所有潜在点标签的情况下可以分离的最大点数。分析分类器可以为给定的点集产生多少个唯一二分法可能有助于实现此目的。分类器可以丢失的最大点数称为 VC 维度。
例如，给定一个二维空间，可以在考虑点的所有可能的标签的情况下确定线性分类器可以分解的最大点数。线性分类器可以分解任何两点集但不能分解所有三点集，这一事实证明它在二维空间中的 VC 维度为 2。这表明线性分类器可以完全分离二维空间中的任意两点，但不能完全分离所有三点集。
在 Python 中实现查找分类器 VC 维度的过程
在 Python 中实现确定线性分类器 VC 维度的方法如下 −
import itertools
import numpy as np
from sklearn.linear_model import LinearRegression
def generate_dichotomies(points):
"""Generate all possible dichotomies of a set of points."""
dichotomies = []
for combo in itertools.product([-1, 1], repeat=len(points)):
dichotomy = {}
for i, point in enumerate(points):
dichotomy[tuple(point)] = combo[i]
dichotomies.append(dichotomy)
return dichotomies
def can_shatter(points, dichotomy):
"""Check if a linear classifier can shatter a given dichotomy."""
X = np.array([list(point) for point in dichotomy.keys()])
y = np.array(list(dichotomy.values()))
clf = LinearRegression().fit(X, y)
predictions = np.sign(clf.predict(X))
return np.array_equal(predictions, y)
def find_vc_dimension(points):
"""Find the VC dimension of a linear classifier."""
max_points = len(points)
min_points = 1
while min_points < max_points:
mid = (min_points + max_points) // 2
dichotomies = generate_dichotomies(points[:mid])
if all(can_shatter(points[:mid], d) for d in dichotomies):
min_points = mid + 1
else:
max_points = mid
return min_points - 1
该代码用于确定二维空间中线性分类器的 VC 维度。其三个关键组件是查找 vc 维度、可破碎和生成二分法。
"生成二分法"以点集合作为输入，并创建该集合的所有潜在二分法。当点集合被分为两个类时，它被称为二分法。例如，三个点的二分法可以将两个点分配给一个类，将一个点分配给另一个类。该函数使用 itertools.product 方法生成所有可能的类组合(-1 和 1)，并构建一个包含每个点及其相关类的字典。一旦将每个二分法添加到列表中，就会返回该列表。
"可破碎"确定给定点集合和二分法作为输入，线性分类器是否可以破碎二分法。线性分类器是一种使用直线将点分为两类的函数。该函数根据二分词典生成点的矩阵 X 和相关类的向量 Y。然后使用 scikit-learn 中的 LinearRegression 函数将线拟合到点及其类。最后，它确定线性模型的预测是否与二分词典的实际类相对应。
"find vc dimension"利用二分搜索来确定在接收一组点作为输入后打碎一组点所需的最小点数。它所做的第一件事是将最小点设置为零，将最大点设置为点集的长度。然后使用"can-shatter"函数确定在反复将点集分成两个子集后，线性分类器是否可以打碎较小子集中的所有二分法。如果可以，它会将最大点数更改为当前子集的中点，如果不能，它会将最小点数更新为当前子集的中点。重复此操作，直到最小点数和最大点数相等，此时返回最小点数 - 1(分类器的 VC 维度)。
现在，只需使用 find vc dimension 函数并以点集作为输入即可使用此代码。这些点必须定义为元组列表。示例包括 -
示例
points = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)] vc_dimension = find_vc_dimension(points) print(vc_dimension)
输出
2
此代码确定二维空间中线性分类器对角线上的五个点组成的点集的 VC 维度。正如预期的那样，有两个 VC 维度。
结论
总之，打散一组点是指分类器准确分类点集的每种替代排列的能力。分类器可以打散的最大点数由其 VC 维度来衡量，这是其复杂性的度量。了解这些想法对于机器学习至关重要，因为它使我们能够评估模型的表现力和对其他类型数据的通用性。通过了解分类器的 VC 维度，我们可以预测获得特定准确度所需的样本数量，并防止过度拟合。
