极客笔记Python 什么是点集的分裂和VC维度
分裂是机器学习中的一个关键概念，指的是分类器准确区分一组点的任意标记的能力。严格来说，分类器在能将一组点划分为所有可行的二元类别时称为“分裂”该集合的点。分类器能够分裂的最大点数由VC维度指定，它衡量了分类器对数据进行分类的能力。对于机器学习的实践者来说，理解分裂和VC维度的概念是至关重要的。在本文中，我们将仔细研究分割点的VC维度。
什么是点集的分裂
当分类器能够正确区分点的任何潜在标记时，它被称为“分裂”一组点。更准确地说，分类器在能够正确分类点的每种潜在的正面或负面标记时，它就分裂了一组点。
换句话说，如果我们在空间中有一组点，我们可以将每个点标记为正或负。如果分类器能够准确地将这些点划分为正和负两组，无论我们如何选择标记它们，那么这个点集被认为是被分裂的。
以一个真实的例子来考虑一个二维空间中的点集。每个点旁边可以放置红色或蓝色标签。如果分类器能够在平面上画一条将所有红色点放在一侧，蓝色点放在另一侧的直线，那么这表示每个标记为红色或蓝色的点都会被分类器正确分类。
什么是VC维度
VC维度是机器学习中一个关键概念，量化了分类器理解数据中复杂模式的能力。分类器能够将一组点分割成两个或更多不同区域的最大点数被称为最大集合的大小。分类器的VC维度与其分裂点集的能力密切相关，VC维度越大，表示它具有更多分裂复杂点集的能力。相反，VC维度较低的分类器很难理解复杂模式，并更容易过拟合或欠拟合数据。
样本可以用来展示分裂点集和VC维度的关系。例如，在二维空间中的线性分类器具有2的VC维度，这意味着它可以分裂每组两个点，但无法分裂所有组三个点。与此相反，二维空间中的多项式分类器具有与多项式的阶数相关的VC维度，使其能够分裂越来越复杂的点集。
如何找到VC维度
找到分类器的VC维度涉及计算它在考虑所有潜在点标记时能够分离的最大点数。分析分类器可以为给定点集产生多少个唯一的二分法可能有助于理解VC维度。然后，分类器可以失去的最大点数被称为VC维度。
例如，在给定一个二维空间的情况下，可以确定线性分类器能够分裂的最大点数，同时考虑到点的每种可能标记。线性分类器可以分裂任意两个点的集合，但无法分裂所有三个点的集合，这证明了它在二维空间中具有2的VC维度。这意味着线性分类器可以完全分离任何二维空间中的两个点，但不能分裂所有三个点的集合。
找到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函数将一条线拟合到点和它们的类别上。最后，它确定线性模型的预测是否与分叉字典的实际类别相对应。
‘找vc维度’利用二分查找确定在接收一组点作为输入后，打破一组点所需的最小点数。首先，它将最小点数设置为零，将最大点数设置为点集的长度。然后，反复将点的集合分割为两个子集，使用‘能否打破’函数确定线性分类器是否能够打破较小子集中的所有分叉。如果可以，它将最大点数更改为当前子集的中点，并在无法打破时将最小点数更新为当前子集的中点。重复此操作，直到最小点数和最大点数相等，此时返回min points – 1，即分类器的VC维度。
现在，只需使用一组点作为输入使用‘找vc维度’函数来使用此代码即可。点必须定义为一个元组列表。示例包括-
示例
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维度是其复杂性的一种度量。了解这些概念对于机器学习至关重要，因为它使我们能够评估模型的表达能力和对其他类型数据的泛化能力。通过了解分类器的VC维度，我们可以预测获得特定准确度水平所需的样本数量，并防止过拟合。