机器学习算法总结3:k近邻法

k近邻法(k-NN)是一种基本分类与回归方法。算法思想：给定一个数据集，对新的输入实例，在训练数据集中找到与其最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为哪个类。 k近邻的特殊情况是k=1的情形，称为最近邻算法。 k近邻算法没有显式的学习过程。 1.模型：k近邻法使用的模型对应于对特征空间的划分。 k近邻法中，当训练集、k值、距离度量(如欧式距离)及分类决策规则确定后，对于任何一个新的输入实例，它所属的类唯一地确定。 模型的三个基本要素：k值的选择、距离度量以及分类决策规则。 (1)k值的选择 k值较小，意味着整体模型变得复杂，容易发生过拟合；k值较大，意味着整体模型变 k近邻法（k-NN）是机器学习领域中一种基础且直观的分类与回归算法。它的核心思想是基于“邻居”的概念，即通过寻找新样本在训练数据集中最接近的k个邻居来预测其类别。如果这k个邻居中的大多数属于某一类别，那么新样本也将被归入这一类别。当k=1时，该算法被称为最近邻算法。 k-NN算法没有显式的学习过程，因为其模型构建并不涉及参数训练，而是依赖于训练数据集本身。模型的构建主要涉及以下三个关键要素： 1. **k值的选择**：k值是决定算法行为的关键参数。较小的k值可能导致模型过拟合，因为它更容易受到噪声或异常值的影响。相反，较大的k值可以减少过拟合，但可能使模型过于简单，丢失一些重要信息。通常，k值是通过交叉验证来选择的，以达到最佳的泛化能力。 2. **距离度量**：k-NN算法使用某种距离度量来计算样本之间的相似性，最常见的选择是欧式距离。然而，根据问题的特性，也可以使用其他度量，如曼哈顿距离、余弦相似度等。不同的距离度量会直接影响到哪些样本被视为“近邻”。 3. **分类决策规则**：k-NN通常采用多数表决策略，即新样本的类别由其k个最近邻的多数类别决定。这反映了经验风险最小化的理念，即选择最常见或最常见的类别。 在实际应用中，为了提高k-NN的搜索效率，通常会利用数据结构，如kd树。kd树是一种专为高维空间数据设计的平衡二叉树，用于加速最近邻搜索。kd树的构建过程中，每次分割选择方差最大的维度，以最大程度地分离数据点。这有助于减少搜索时间，尤其是当训练实例数量远大于空间维数时。 kd树的最近邻搜索算法的时间复杂度是O(logN)，显著优于简单的线性搜索。但是，kd树在高维数据中可能会出现所谓的“维数灾难”，因为随着维度增加，所有点都趋向于相等距离，导致搜索效率降低。 k-NN算法虽然简单且易于理解，但它也有一些局限性。例如，它对异常值敏感，计算量大，特别是对于大数据集。此外，它不适用于在线学习场景，因为必须存储整个训练数据集。尽管如此，k-NN仍然是许多复杂机器学习算法的基础，如集成学习中的bagging和boosting方法，以及作为其他复杂算法的基准。通过理解和掌握k-NN，我们可以更好地理解机器学习中的其他高级算法，并能更有效地解决实际问题。