KNN详述
以KNN理论模型为例：
给定一个新样本点时，只需要在训练集中找到距离最近的 k 个样本点，按照一定的决策规则得到新样本点的预测结果。
整个预测过程由三个基本要点组成，分别是：距离、k 值、决策规则。
距离
距离的定义中常见的有欧式距离（Euclidean distance），也被称为 2-范数距离；向量点积；cos余弦值等。
K值
一般 k 值会取一个相对较小的值，并通过交叉验证的方式得到一个最优的 k 值。
决策规则
决策规则一般是采用“少数服从多数”的思想。对于分类问题，这 k 个最近的样本中分类最多的类型即为该新样本点的类型；对于回归问题，将这 k 个最近的样本对应的标签值进行平均即为该新样本点的预测值。
算法内容
-
保存训练集 -
查询最近的 k 个样本点 -
返回这 k 个样本点的标签平均值或返回这 k 个样本点分类最多的类型
可以看到算法中最核心的方法就是查询最近的 k 个样本点，其中一个最简单的方法就是线型扫描，即遍历整个训练集进行搜索，但当训练集中的样本数过大时，该方式需要对每一个训练样本计算距离，往往过于耗时，这时可以考虑使用一个数据结构来组织并存储一开始的训练集，在搜索阶段减少对距离的计算次数，以达到快速检索的目的。
数据结构&算法
通过某种数据结构&算法解决数据查询的问题；即组织原始数据集，加速后续的查询。
K-D Tree
K-D树（K-Dimensional Tree），全称为K维空间中的划分数据结构，是一种在k维空间中存储k维数据点的数据结构，常用于多维空间的查询，比如在多维空间中快速查找最近邻点。
适用场景：在样本不大、维度不多的情况下，可以精确快速地查询出最近邻。
Annoy 算法
Annoy（Approximate Nearest Neighbors Oh Yeah）算法是一种用于高效查找最近邻居的高性能算法，通常用于信息检索、推荐系统、机器学习等领域。它的核心思想是通过构建一种森林（Forest）的数据结构，使得在查询一个点的时候，可以快速地找到它的近似邻居。
适用场景：适合于大规模、数百维特征 数据集的近似查询。
总结
综上所述，对于KNN理论的实现，首先是理论的铺垫，然后是 数据结构&算法 组织起数据集，提供存储与查询检索等功能；对于所有的算法理论实现都是如此。
程序 = 数据结构 + 算法
参考
机器学习算法系列（二十一）-k近邻算法（k-Nearest Neighbor / kNN Algorithm）[1]
机器学习算法系列（二十二）-近似k近邻算法-Annoy（Approximate Nearest Neighbor / ANN）[2]
机器学习算法系列（二十一）-k近邻算法（k-Nearest Neighbor / kNN Algorithm）: https://blog.csdn.net/sai_simon/article/details/124209904
[2]
机器学习算法系列（二十二）-近似k近邻算法-Annoy（Approximate Nearest Neighbor / ANN）: https://blog.csdn.net/sai_simon/article/details/124960727
原文始发于微信公众号（阿郎小哥的随笔驿站）：聊聊机器学习KNN理论实现的思考
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/244135.html
