【学习】《算法图解》第十二章学习笔记：K近邻算法

# 前言 《算法图解》第十二章介绍了一种简单而强大的机器学习算法——K近邻算法（K-Nearest Neighbors，简称KNN）。这是一种基于实例的学习方法，也是机器学习领域中最基础、最直观的算法之一。本章不仅讲解了KNN的基本原理和实现方式，还探讨了特征提取、归一化等重要概念，为读者打开了机器学习的大门。本笔记将梳理KNN算法的核心思想、实现步骤以及应用场景。 # 一、K近邻算法概述 ## （一）基本思想 K近邻算法的核心思想非常简单：**物以类聚，人以群分**。它基于一个假设：相似的事物通常具有相似的特征，并且在特征空间中彼此靠近。 具体来说，KNN算法的基本思路是： 1. 对于一个待分类的新实例，在训练数据集中找到与它最相似（距离最近）的K个实例 2. 这K个实例中出现最多的类别，就作为新实例的预测类别 ## （二）算法特点 KNN算法具有以下特点： 1. **非参数化方法**：不对数据分布做任何假设，完全依赖于数据本身 2. **惰性学习**：没有显式的训练过程，只在需要预测时才进行计算 3. **直观易懂**：算法思想简单，容易理解和实现 4. **计算复杂度高**：预测时需要计算新实例与所有训练实例的距离 # 二、KNN算法步骤详解 ## （一）算法流程 KNN算法的基本流程如下： 1. **收集数据**：准备训练数据集，每个实例包含特征向量和类别标签 2. **选择距离度量**：确定如何计算实例之间的相似度（通常使用欧几里得距离） 3. **对新实例进行分类**： - 计算新实例与训练集中所有实例的距离 - 选择距离最近的K个实例 - 统计这K个实例中各类别的频次 - 将出现频次最高的类别作为新实例的预测类别 ## （二）距离度量 KNN算法中，距离度量是衡量两个实例相似度的关键。常用的距离度量方法包括： 1. **欧几里得距离**：最常用的距离计算方法 $$d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$$ 2. **曼哈顿距离**：沿坐标轴方向的距离总和 $$d(x, y) = \sum_{i=1}^{n}|x_i - y_i|$$ 3. **闵可夫斯基距离**：欧几里得距离和曼哈顿距离的一般化形式 $$d(x, y) = \left(\sum_{i=1}^{n}|x_i - y_i|^p\right)^{1/p}$$ 4. **余弦相似度**：计算两个向量的夹角余弦值，常用于文本分析 $$\cos(\theta) = \frac{x \cdot y}{||x|| \times ||y||}$$ 在《算法图解》中，主要使用欧几里得距离作为度量标准。 ## （三）K值的选择 K值的选择对KNN算法的性能有重要影响： - **K值过小**（如K=1）：算法对噪声敏感，容易过拟合 - **K值过大**：可能会忽略局部特征，导致欠拟合 - **经验法则**：一般选择训练样本数量的平方根作为K值的参考 - **实践建议**：通常通过交叉验证等方法从多个候选值中选择最优的K值 另外，为了避免平局情况，K值通常选择奇数。 # 三、特征工程与数据预处理 ## （一）特征提取 在应用KNN算法之前，需要将原始数据转换为特征向量。《算法图解》中提到了几种常见的特征提取方法： 1. **数值型特征**：直接使用原始数值，如身高、体重等 2. **分类特征**：通过独热编码（One-Hot Encoding）等方法转换为数值 3. **文本特征**：可以使用词袋模型（Bag of Words）或TF-IDF等方法提取特征 4. **图像特征**：可以提取颜色直方图、纹理特征等 特征提取的质量直接影响KNN算法的性能，因此需要根据具体问题选择合适的特征表示方法。 ## （二）特征归一化 由于KNN算法基于距离计算，不同特征的量纲（单位和范围）差异会对结果产生不公平的影响。例如，如果一个特征的取值范围是0-1，另一个特征的取值范围是0-1000，那么第二个特征将在距离计算中占据主导地位。 为了解决这个问题，需要对特征进行归一化处理，常用的方法包括： 1. **最小-最大归一化（Min-Max Scaling）**：将特征缩放到[0, 1]区间 $$x' = \frac{x - \min(x)}{\max(x) - \min(x)}$$ 2. **Z-score标准化**：将特征转换为均值为0、标准差为1的分布 $$x' = \frac{x - \mu}{\sigma}$$ 在《算法图解》中，作者强调了归一化的重要性，并建议在实际应用中始终对特征进行适当的归一化处理。 # 四、Python实现KNN算法 ## （一）基本实现 以下是KNN算法的简单Python实现： ```python import numpy as np from collections import Counter def knn_classify(training_data, training_labels, new_instance, k=3, distance_fn=None): """ 使用KNN算法对新实例进行分类 参数: training_data -- 训练数据集，每行是一个实例的特征向量 training_labels -- 训练数据的类别标签 new_instance -- 待分类的新实例 k -- 近邻数量 distance_fn -- 距离计算函数，默认为欧几里得距离 返回: predicted_label -- 预测的类别标签 """ # 如果没有提供距离函数，使用欧几里得距离 if distance_fn is None: distance_fn = lambda x, y: np.sqrt(np.sum((x - y) ** 2)) # 计算新实例与所有训练实例的距离 distances = [] for i, instance in enumerate(training_data): dist = distance_fn(instance, new_instance) distances.append((dist, training_labels[i])) # 按距离排序并选择前k个 distances.sort(key=lambda x: x[0]) k_nearest = distances[:k] # 统计这k个近邻中各类别的频次 k_nearest_labels = [label for _, label in k_nearest] most_common = Counter(k_nearest_labels).most_common(1) return most_common[0][0] ``` ## （二）示例应用 以《算法图解》中的电影分类例子为例，我们可以使用KNN算法对电影进行分类： ```python # 电影数据：[动作场景数, 浪漫场景数] movies = np.array([ [3, 104], # "爱情片" [2, 100], # "爱情片" [1, 81], # "爱情片" [101, 10], # "动作片" [99, 5], # "动作片" [98, 2] # "动作片" ]) # 电影类别标签 labels = ["爱情片", "爱情片", "爱情片", "动作片", "动作片", "动作片"] # 对特征进行归一化 def normalize(data): min_vals = np.min(data, axis=0) max_vals = np.max(data, axis=0) ranges = max_vals - min_vals normalized_data = np.zeros(np.shape(data)) m = data.shape[0] normalized_data = (data - np.tile(min_vals, (m, 1))) / np.tile(ranges, (m, 1)) return normalized_data # 归一化后的电影数据 normalized_movies = normalize(movies) # 待分类的新电影：[动作场景数, 浪漫场景数] new_movie = np.array([18, 90]) normalized_new_movie = (new_movie - np.min(movies, axis=0)) / (np.max(movies, axis=0) - np.min(movies, axis=0)) # 使用KNN算法进行分类 predicted_category = knn_classify(normalized_movies, labels, normalized_new_movie, k=3) print(f"这部新电影可能是: {predicted_category}") ``` # 五、KNN算法的优缺点 ## （一）优点 1. **简单直观**：算法思想容易理解，实现简单 2. **无需训练**：不需要构建模型，可以直接用于分类 3. **适用性广**：可用于分类和回归问题 4. **理论成熟**：有完善的数学理论支持 5. **对数据分布无假设**：不需要对数据分布做任何假设 ## （二）缺点 1. **计算复杂度高**：预测时需要计算与所有训练实例的距离，时间复杂度为O(n)，其中n是训练集大小 2. **存储开销大**：需要存储全部训练数据 3. **对特征缩放敏感**：不同特征的量纲差异会影响结果 4. **维度灾难**：在高维空间中，距离度量的区分能力下降 5. **对噪声敏感**：异常值可能对结果产生较大影响 # 六、KNN的实际应用 ## （一）应用场景 KNN算法在许多领域都有广泛应用： 1. **推荐系统**：基于用户相似度推荐商品、电影等 2. **图像识别**：通过图像特征进行分类 3. **文本分类**：对文档进行主题分类 4. **医疗诊断**：基于病人症状和历史病例进行疾病诊断 5. **金融风控**：信用评分和风险评估 ## （二）KNN的改进 为了解决KNN算法的一些缺点，研究人员提出了多种改进方法： 1. **KD树**：使用KD树等数据结构加速近邻搜索 2. **加权KNN**：根据距离对近邻的投票进行加权 3. **局部加权回归**：在回归问题中使用加权平均 4. **降维技术**：使用PCA等方法降低特征维度 5. **特征选择**：选择最相关的特征子集 # 七、总结 K近邻算法是一种简单而强大的机器学习方法，它通过比较新实例与已知实例的相似度来进行分类或回归。尽管KNN算法有计算复杂度高、存储开销大等缺点，但其简单直观的特性使其成为机器学习入门的理想算法，也是实际应用中的重要工具之一。 在实践中，特征工程（特别是特征提取和归一化）对KNN算法的性能至关重要。此外，K值的选择也需要根据具体问题进行调整，通常通过交叉验证等方法确定最优值。 《算法图解》通过生动的例子和清晰的解释，帮助读者理解了KNN算法的基本原理和应用方法，为进一步学习更复杂的机器学习算法奠定了基础。 # 八、参考资料 - 《算法图解》（Grokking Algorithms）by Aditya Y. Bhargava - 周志华《机器学习》 - Peter Harrington《机器学习实战》 - [scikit-learn KNN文档](https://scikit-learn.org/stable/modules/neighbors.html) - [K近邻算法 - 维基百科](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm) 本文由[mdnice](https://mdnice.com/?platform=6)多平台发布
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容