监督学习中的分类算法详解

# 监督学习中的分类算法详解 ## 1. 支持向量机（SVM） ### 1.1 线性SVM 支持向量机（SVM）是一种线性学习系统，旨在找到最大间隔决策边界，以分离正例和负例。学习过程被表述为一个二次优化问题。最终决策边界公式为： \[ \sum_{i = 1}^{n} \alpha_i y_i \langle \mathbf{x}_i, \mathbf{x} \rangle + b \] 分类（测试）的决策规则与可分情况相同，即 \( \text{sign}(\langle \mathbf{w}, \mathbf{x} \rangle + b) \)。需要注意的是，对于相关公式，无需显式计算 \( \mathbf{w} \)，这对于使用核函数处理非线性决策边界至关重要。 参数 \( C \) 的确定通常是在训练集上尝试一系列值，构建多个分类器，然后在验证集上进行测试，选择在验证集上给出最佳分类结果的那个值。交叉验证也是常用的方法。 ### 1.2 非线性SVM：核函数 在许多实际数据集里，决策边界是非线性的。为处理非线性可分数据，可将输入数据从原始空间转换到另一个通常维度更高的空间（特征空间），使线性决策边界能在转换后的空间中分离正例和负例。 基本思路是通过非线性映射 \( \Phi \) 将输入空间 \( X \) 中的数据映射到特征空间 \( F \)： \[ \Phi: \mathbf{x} \to \Phi(\mathbf{x}) \] 转换后，原始训练数据集 \( \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_n, y_n)\} \) 变为 \( \{(\Phi(\mathbf{x}_1), y_1), (\Phi(\mathbf{x}_2), y_2), \ldots, (\Phi(\mathbf{x}_n), y_n)\} \)。 然而，将输入数据显式转换到特征空间再应用线性SVM可能会遭遇维数灾难。幸运的是，通过核函数可以避免显式转换。核函数 \( K \) 定义为： \[ K(\mathbf{x}, \mathbf{z}) = \langle \Phi(\mathbf{x}), \Phi(\mathbf{z}) \rangle \] 常见的核函数有： - 多项式核：\( K(\mathbf{x}, \mathbf{z}) = (\langle \mathbf{x}, \mathbf{z} \rangle + \theta)^d \) - 高斯径向基函数（RBF）核：\( K(\mathbf{x}, \mathbf{z}) = \exp\left(-\frac{\|\mathbf{x} - \mathbf{z}\|^2}{2\sigma^2}\right) \) 直接使用核函数替换特征空间中的点积这一策略被称为核技巧，无需明确知道映射函数 \( \Phi \)。 ### 1.3 SVM的局限性 - **数据类型限制**：仅适用于实值空间，对于分类属性，需将其分类值转换为数值。 - **分类数量限制**：仅允许二分类，对于多分类问题，需应用一些策略，如一对多、纠错输出编码等。 - **可解释性差**：SVM生成的超平面难以被用户理解，在高维空间中很难想象超平面的位置，核函数的使用更是加剧了这一问题。 ## 2. K近邻（kNN）学习 与之前学习数据模型的急切学习方法不同，k近邻（kNN）是一种懒惰学习方法，它不在训练数据上学习模型，仅在需要对测试示例进行分类时才进行学习。 ### 2.1 kNN算法步骤 算法kNN(D, d, k)： 1. 计算测试实例 \( d \) 与训练集 \( D \) 中每个示例的距离。 2. 选择 \( D \) 中与 \( d \) 最近的 \( k \) 个示例，记为集合 \( P \)。 3. 将 \( d \) 分配为 \( P \) 中最频繁出现的类别（多数类）。 ### 2.2 距离/相似度函数 kNN算法的关键组成部分是距离/相似度函数，其选择取