chapter2 机器学习之KNN(k-nearest neighbor algorithm)--K近邻算法从原理到实现
【摘要】
一.引入
K近邻算法作为数据挖掘十大经典算法之一,其算法思想可谓是intuitive,就是从训练集里找离预测点最近的K个样本来预测分类
因为算法思想简单,你可以用很多方法实现它,这时效率就是我们需要慎重考虑的事情,最简单的自然是求出测试样本和训练集所有点的距离然后排...
一.引入
K近邻算法作为数据挖掘十大经典算法之一,其算法思想可谓是intuitive,就是从训练集里找离预测点最近的K个样本来预测分类
因为算法思想简单,你可以用很多方法实现它,这时效率就是我们需要慎重考虑的事情,最简单的自然是求出测试样本和训练集所有点的距离然后排序选择前K个,这个是O(nlogn)的,而其实从N个数据找前K个数据是一个很常见的算法题,可以用最大堆(最小堆)实现,其效率是O(nlogk)的,而最广泛的算法是使用kd树来减少扫描的点,这也就是这篇文章的主要内容,本文偏实现,详细理论教程见july的文章 ,不得不服,july这篇文章巨细无遗!
二.前提:堆的实现
堆是一种二叉树,用一个数组存储,对于k号元素,k*2号是其左儿子,k*2+1号是其右儿子
而大根堆就是跟比左儿子和右儿子都大,小根堆反之。
要满足这个条件我们需要通过up( index )操作和down( index )维护它的结构
文章来源: wenyusuran.blog.csdn.net,作者:文宇肃然,版权归原作者所有,如需转载,请联系作者。
原文链接:wenyusuran.blog.csdn.net/article/details/26460347
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)