关键词：
1 k近邻算法
k nearest neighbor，k-NN，是一种基本分类与回归的方法，输入为实例的特征向量——对应空间的点，输出为实例的类别，可取多类。kNN假定一个训练集，实例类别已确定，分类时，对新的实例根据其k个最近邻训练集实例的类别，通过多数表决的方式进行预测。不具有显式学习过程。利用训练集对特征空间划分，并作为其分类的model。三要素是k值的选择，距离度量，分类决策规则。1968年Cover和Hart提出。
算法：
I为指示函数，即当yi=cj时I=1，否则I=0
2 模型
kNN的model对应于特征空间的划分，有三个要素：k选择，距离度量，分类决策。对于每个实例x，当三要素确定后，就能得到其所在的对特征空间的划分单元cell。
2.1 距离测量
特征空间中，两个实例点的距离其实是相似度的反应，距离越近越相似。一般对于特征空间Rn，常用欧氏距离（Euclidean distance），也可以更一般的Lp距离或Minkowski距离。
几种距离度量方法：
2.2 k值选择
k选择较小的时候，对实例较小的邻域进行预测，近似误差（approximation error）会减小，只有与输入实例较近的训练实例才会起作用。缺点是估计误差（estimation error）会增大，预测结果对近邻的实例点会非常敏感。总之，k值减小，意味着模型复杂度增大，容易发生过拟合。
同样的，较大k值意味着较大邻域训练，近似误差增大，估计误差减少，离实例点较远的点也会对预测起作用，使预测发生错误，意味着模型过于简单。
在实际应用中，常取较小的k值，采用交叉验证来选取最优 k值。
2.3 分类决策规则
kNN采用多数表决规则（majority voting rule）：由输入实例的k个近邻的训练实例中，多数类决定输入实例的类别。
多数表决规则数学含义是经验风险最小化：
证明：
若loss function是0-1损失函数，分类函数为：f:Rn——>c1,c2,…,ck
误分类率是：P(Y!=f(X)) = 1-P(Y=f(X))
可以看到误分类率最小就是经验风险最小，就要 使得右边Sigma(I(yi=cj))最大，即多数表决！
3 kNN的实现——kd树
KNN最简单的实现是线性扫描（linear scan），要求计算输入实例与训练实例的每一个距离，当训练集很大时，这样扫描十分耗时，因此考虑到如何对特征空间和维数大，容量大的训练数据进行快速的搜索，十分必要。可以考虑特殊的存储结构训练数据，以减少计算距离的次数，比如kd树（kd tree）方法。
3.1 构造kd树
kd树是一种对k维空间实例点进行存储以便于快速检索的数据结构。kd树是二叉树，表示对k维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间划分，构成一系列k维超矩形区域，kd树的每个节点对应于一个k维超矩形区域。
构造方法：首先构造根节点——对应于k维空间中包含所有实例点的超矩形区域；通过递归方法，不断对k维空间进行划分生成子节点，在此超矩形区域上选择一个坐标轴和一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子节点），这时实例被分到两个子区域，这个过程持续到区域内没有实例时终止，终止时节点为叶子结点。在此过程中将实例保存在相应的结点上。
通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴的中位数（median）为切分点，得到平衡kd树——但是不一定是搜索效率最优。
平衡kd树算法：
针对高维数据需要对每一维都进行二分，更好的方法是对方差最大的特征进行比较和划分。（具体可看文末的博文推荐）
3.2 kd树搜索
利用kd树进行k近邻搜索
给定一个目标点，搜索其最近邻。首先找到包含该目标点的叶子结点，然后从叶子结点出发，一次回退到父结点；不断查找与目标结点最近邻的结点，当确定不可能存在更近的结点时终止。这样搜索就会限制在空间的局部区域上，效率大为提高。
包含目标结点的叶子结点对应包含目标点的最小超矩形区域，以此叶子结点的实例点当做当前最近点，目标点最近邻一定在以目标点为中心并通过当前最近点的超球体内部。然后返回当前结点的父节点，如果父节点的另一子节点超矩形区域与超球相交，那么就在相交区域寻找与目标点的更近实例点，若存在，就当做当前最近点，算法转到更上一级的父节点，继续迭代上述过程，父节点的另一子节点超矩形区域与超球体不想交，或不存在当前最近点更近的点，则停止搜索。
kd树最近邻搜索算法：
算法复杂度为O(logN),而不是之前的O(N),更适合实例数目远远大于空间维数的情况，当二者接近时效率将降低为线性扫描
推荐读一读这篇博文，比书上写的更通俗一些。
K-D Tree原理及实现
k-近邻（knn）算法
K-近邻算法（K-NN） 邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。 kNN... 查看详情
基本分类方法——knn(k近邻)算法
...程中，提到了KNN算法。有点熟悉，上网一查，居然就是K近邻算法，机器学习的入门算法。参考内容如下：http://www.cnblogs.com/charlesblc/p/6193867.html1、kNN算法又称为k近邻分类(k-nearestneighborclass 查看详情
机器学习分类算法--k近邻算法knn(代码片段)
一、K近邻算法基础KNN-------K近邻算法--------K-NearestNeighbors思想极度简单应用数学知识少（近乎为零）效果好（缺点？）可以解释机器学习算法使用过程中很多细节问题更完整的刻画机器学习应用的流程 importnumpyasnpimportmatplotlib... 查看详情
k近邻算法（knn）
1.前言K近邻法(k-nearestneighbors,KNN)是一种很基本的机器学习方法了，在我们平常的生活中也会不自主的应用，就是“物以类聚，人以群分”。比如，我们判断一个人的人品，只需要观察他来往最密切的几个人的人品好坏就可以得出... 查看详情
k-近邻算法（knn）
...的新样本时，用算法提取训练样本集中和待分类的样本最近邻的K个分类标签（比如样本只有两个特征，在二维坐标系中用点来表示一个样本，选择和新样本点距离最近的K个点）。选取这k个分类标签中出现次数最多的分类，作为... 查看详情
k-近邻算法(knn)
算法简介KNN算法原理是：存在一个样本数据集合（训练样本集），并且样本集合中每个数据都已知该数据的分类。当输入没有标签的新数据时，我们将新数据的特征与已知样本集合进行逐个比较，提取K个最相近的数据的标签，... 查看详情
k-近邻算法（knn）
1、K-近邻算法原理 1.1算法特点简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。优点：精度高、对异常值不敏感、无数据输入假定缺点：计算复杂度高、空间复杂度高适用数据范围：数值型和标称型 1... 查看详情
机器学习实战☛k-近邻算法（k-nearestneighbor，knn）(代码片段)
机器学习实战☛k-近邻算法（K-NearestNeighbor，KNN）文章目录机器学习实战☛k-近邻算法（K-NearestNeighbor，KNN）k-近邻算法概述原理简介k-近邻算法一般流程伪代码与实现示例：使用kNN改进约会网站的配对效... 查看详情
手写数字识别的k-近邻算法实现
...况下转载）前言手写字符识别是机器学习的入门问题，k-近邻算法（kNN算法）是机器学习的入门算法。本文将介绍k-近邻算法的原理、手写字符识别问题分析、手写字符识别的kNN实现、测试。kNN算法原理kNN算法是一种分类算法，... 查看详情
k-近邻算法（knn）(代码片段)
K-近邻算法（KNN）1KNN介绍2KNN的初步使用3距离度量3.1基本性质3.2常见距离公式3.3距离属性4k值选择5KNN优化—kd树5.1kd树简介5.2构造方法5.3案例分析6数据集6.1获取数据集6.2划分数据集7特征工程—特征预处理7.1归一化7.2标准化... 查看详情
knn-k近邻算法
...程中的很多细节问题更完整的刻画机器学习应用的流程K近邻本质：如果两个样本足够相似，那么它们就有可能属于同一类别。e.g.绿色的点是新加入的点，取其最近的k（3）个点作为小团体来投票，票数高的获胜（蓝比红-3：0）,... 查看详情
k-近邻算法（knn）
参考技术A简单地说，K-近邻算法采用测量不同特征值之间的距离方法进行分类。欧氏距离是最常见的距离度量，衡量的是多维空间中各个点之间的绝对距离。公式如下：身高、体重、鞋子尺码数据对应性别导包，机器学习的算法... 查看详情
分类算法之k-近邻算法（knn）(代码片段)
一、k-近邻算法概述 1、什么是k-近邻算法如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。2、欧式距离两个样本的距离可以通过如下公式计算，又叫... 查看详情
机器学习实战第2章k-近邻算法(k-nearestneighbor，knn)
第2章k-近邻算法<scripttype="text/javascript"src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>KNN概述k-近邻（kNN,k-NearestNeighbor）算法主要是用来进行分类的.KNN场景电影可以按照题材分类，那么如何区分&nbs 查看详情
k近邻算法（knn）与k-means算法的对比
k近邻算法（knn）是一种基本的分类与回归的算法，k-means是一种基本的聚类方法。k近邻算法（knn）基本思路：如果一个样本在特征空间的k个最相似（即特征空间最邻近）的样本大多数属于某一类，则该样本也属于这一类。影响... 查看详情
k-近邻算法（knn）
概述简单地说，K-近邻算法（K-Nearest-NeighborsClassification）采用测量不同特征值之间的距离方法进行分类。优点：精度高、对异常值不敏感、无数据输入假定缺点：计算复杂度高、空间复杂度高使用数据范围：数值型和标称型工作... 查看详情
机器学习实战k-近邻算法实施knn分类算法
2.预测数据分类时，出现‘dict’objecthasnoattribute‘iteritems‘如： 最常见的解决办法是更改环境变量顺序如 注意：哪个版本在上面，cmd中的python版本即是谁。如又如： 然后预测数据所在分类即可实现： 查看详情
knn最近邻分类算法(代码片段)
如题所示，该算法简称KNN，采用的方法是最近邻，目的是分类。KNN算法概述在已有数据集中已将数据分为n类，那么如果此时再进来一个新的数据如何给他分类呢？应该选取距离他最近的k个邻居（k由你定&#x... 查看详情