机器学习实战 - KNN（K近邻）算法PDF知识点详解 + 代码实现

邻近算法，或者说K最邻近（KNN，K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。近邻算法就是将数据集合中每一个记录进行分类的方法. KNN（K- Nearest Neighbor）法即K最邻近法，最初由 Cover和Hart于1968年提出，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路非常简单直观：如果一个样本在特征空间中的K个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别 [2] 。 该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最邻近点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种 Reverse KNN法，它能降低KNN算法的计算复杂度，提高分类的效率 [2] 。 KNN算法比较适用于样本容量比较大的类域的自动分类 **K-近邻（KNN）算法**是机器学习领域中一种基础且直观的分类算法。它的核心思想是根据输入样本最接近的K个训练样本的类别来预测新样本的类别。KNN算法最早由Cover和Hart在1968年提出，是一种基于实例的学习方法，无需对数据进行任何假设或模型拟合。 ### **一、KNN算法原理** 1. **距离度量**：KNN算法依赖于计算样本间的距离。在二维空间中，通常使用高中数学中的欧几里得距离公式。对于多维数据，可以扩展到欧氏距离，即计算所有特征向量的平方差之和的平方根。例如，两个样本点A和B在N维空间中的欧氏距离表示为： \[ dist(A, B) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2} \] 2. **K值选择**：K值代表了考虑的最近邻的数量，一般取值小于20。较小的K值可能导致过拟合，而较大的K值可能使结果过于平滑，降低分类效果。 3. **分类决策**：通过计算新样本到所有训练样本的距离，找到距离最小的K个样本，然后统计这K个样本中各类别的出现频率，返回出现频率最高的类别作为新样本的预测类别。 ### **二、KNN算法步骤** 1. **计算距离**：计算新样本与训练集中所有样本的距离。 2. **排序**：按距离从近到远对训练样本排序。 3. **选取K个最近邻**：选取距离最近的前K个样本。 4. **类别统计**：统计这K个样本的类别分布。 5. **预测分类**：返回出现次数最多的类别作为新样本的预测类别。 ### **三、Python实现** 在Python中，我们可以使用pandas库处理数据，并实现KNN算法。首先创建一个包含电影信息的DataFrame，包括电影名称、打斗镜头数、接吻镜头数和电影类型。接着，计算新电影与训练集中电影的距离，排序并选取K个最近邻。统计这K个电影的类别频率，返回出现频率最高的类别。 ```python import pandas as pd def classify0(inX, dataSet, k): # 计算距离 dist = list((((dataSet.iloc[:6, 1: 3] - inX)**2).sum(1))**0.5) # 排序 dist_l = pd.DataFrame({'dist': dist, 'labels': (dataSet.iloc[:6, 3])}) dr = dist_l.sort_values(by = 'dist')[: k] # 统计类别频率 re = dr.loc[:, 'labels'].value_counts() # 返回预测类别 return re.index[0] ``` ### **四、KNN算法的优缺点** 优点： 1. 算法简单，易于理解。 2. 无需进行复杂的模型训练。 3. 可以处理多分类问题。 缺点： 1. 计算量大，尤其是当样本量大时。 2. 对于大规模数据集，存储需求较高。 3. 对于样本不平衡的情况，可能会导致分类偏向多数类。 4. K值的选择对结果影响较大，需要进行调参。 5. 不适用于高维数据，因为维度灾难问题。 为解决上述问题，可以采取以下策略： - **降维技术**：如主成分分析（PCA）减少特征维度。 - **剪枝技术**：去除对分类作用不大的样本，减少计算量。 - **逆向KNN（Reverse KNN）**：可以提高分类效率。 KNN算法虽然简单，但在许多场景下仍然有效，尤其是在小规模数据集和低维数据上。然而，实际应用中需结合其他技术优化，以应对计算复杂性和高维数据等问题。