K-近邻算法

🎈1.1 K - 近邻算法简介

🌟学习目标

• 目标：了解什么是 KNN 算法
• 知道：KNN 算法求解过程

🌸1 什么是 K - 近邻算法

根据你的 “邻居” 来推断出你的类别。

🐾1.1 K - 近邻算法 (KNN) 概念

K Nearest Neighbor 算法又叫 KNN 算法，这个算法是机器学习里面一个比较经典的算法，总体来说 KNN 算法是相对比较容易理解的算法。

💡定义

如果一个样本在特征空间中的 k 个最相似 (即特征空间中最邻近) 的样本中的大多数属于某一个类别，则该样本也属于这个类别。例如，在一个水果分类问题中，我们有一堆已知类别的水果样本（苹果、橙子等），对于一个未知类别的水果，我们通过计算它与已知水果样本的相似度（距离），找到最相似的 k 个样本，如果这 k 个样本中大多数是苹果，那么我们就可以推断这个未知水果也可能是苹果。

🌟来源

KNN 算法最早是由 Cover 和 Hart 提出的一种分类算法。

📏距离公式

两个样本的距离可以通过如下公式计算，又叫欧式距离 。

$$对于二维平面上点a(x_{1}, y_{1})与b(x{2}, y{2}) 之间的欧氏距离：$$ $$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$ $$对于三维空间点 a(x{_1}, y{_1}, z{_1})与b(x{_2}, y{_2}, z{_2}) 之间的欧氏距离：$$ $$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}$$ $$对于n维空间点 a(x_{11}, x_{12}, \ldots, x_{1n})与b(x_{21}, x_{22}, \ldots, x_{2n}) 之间的欧氏距离（两个n维向量）：$$ $$d_{12} = \sqrt{\sum_{k=1}^{n} (x_{1k} - x_{2k})^2}$$

🍿1.2 电影类型分析

假设我们现在有几部电影（电影数据表格，包含电影名称、特征数据、类别等信息）。其中有一部 “？号电影” 不知道类别，如何去预测？我们可以利用 K 近邻算法的思想。

分别计算每个电影和被预测电影的距离，然后求解。比如，我们可以从电影的多个特征（如搞笑镜头、拥抱镜头、打斗镜头等）来计算它们之间的距离。

假设我们已经计算出了各电影与 “？号电影” 的距离，如下表所示（示例数据）：

🐼分类过程🐠

当 (K = 5) 时，从表格中可知距离《唐人街探案》最近的 5 部电影分别是《功夫熊猫》《美人鱼》《宝贝当家》《新步步惊心》《代理情人》。

• 这 5 部电影中：
• 《功夫熊猫》《美人鱼》《宝贝当家》是喜剧片；
• 《新步步惊心》和《代理情人》是爱情片。

喜剧片的数量为 3，爱情片的数量为 2。 根据 KNN 算法中多数表决的原则，在这 5 个最近邻中，喜剧片的数量占多数。

🎬结论

通过 KNN 分析，预测《唐人街探案》的电影类型为喜剧片。因为在距离它最近的 5 部电影中，喜剧片的数量多于其他类型的电影数量。

📈1.3 KNN 算法流程总结

1. 计算已知类别数据集中的点与当前点之间的距离：利用距离公式（如欧氏距离），计算每个已知样本点与待预测点的距离。
2. 按距离递增次序排序：将计算得到的距离从小到大进行排序。
3. 选取与当前点距离最小的 k 个点：从排序后的距离列表中，选取前 k 个最小距离对应的样本点。
4. 统计前 k 个点所在的类别出现的频率：查看这 k 个点分别属于哪些类别，并统计每个类别出现的次数。
5. 返回前 k 个点出现频率最高的类别作为当前点的预测分类：如果这 k 个点中属于动作片类别的点最多，那么就预测待预测电影为动作片。

🌈2 小结

• K - 近邻算法简介【了解】：就是通过你的 “邻居” 来判断你属于哪个类别。
• 如何计算你到你的 “邻居” 的距离：一般时候，都是使用欧氏距离。欧氏距离能够直观地衡量两个样本在特征空间中的距离远近，帮助我们找到最邻近的样本。