chapter2 机器学习之KNN(k-nearest neighbor algorithm)--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