文档介绍：第一章 k近邻
K近邻简介
k近邻（k-Nearest Neighbor，k-NN）是一种基本的、有监督学习的分类方法，于1968年由Cover和Hart提出，其用于判断某个对象的类别。k近邻的输入为对象特征向量，对应于特征空间上的点；输出为对象的类别。
k近邻算法实例引入：
k近邻实例
如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。
所谓物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手。要判别上图中那个绿色的圆是属于哪一类数据，只需根据它周围的邻居即可。但一次性看多少个邻居呢？从上图中，你还能看到：
如果k=3，绿色圆点的最近的3个邻居（欧式距离）是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
上面这个小例子基本上体现了k近邻算法的三个基本要素：确定度量方式（欧式距离）、选着k值（2 or 3）、分类决策规则（少数服从多数）。
下面，给出k近邻算法的数学表述：
输入：训练数据集
其中，为实例的特征向量，为实例的类别，;实例特征向量
;
输出：实例所属的类。
（1）根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作；
（2）在中根据分类决策规则（如多数表决）决定x的类别y：
（1-1）
其中，为指示函数，即当时为1,否则为0。
k近邻的特殊情况是k=1的情形，称为最近邻算法，对于输入的对象（特征向量）x，最近邻法将训练数据集中于x最近邻点所属的类作为x的类。

建立数学模型的过程实质就是确定三个基本要素的过程。
距离度量方式的确定
样本空间（特征空间）中两个对象的距离是它们相似程度的量化反映。k近邻模型的特征空间可被抽象为n维的向量空间R，现在两个对象之间的距离就可转化为两个向量之间的距离，这样研究起来就方便多了。在k近邻模型中，计算向量之间距离的公式列举如下：
（1）欧式距离：（1-2）
（2）曼哈顿距离：（1-3）
（3）切比雪夫距离：（1-4）
（4）闵可夫斯基距离：（1-5）
特点：为综合性的公式。
（5）马氏距离：（1-6）
特点：可排除对象间的相关性。
（6）相关距离：（1-7）
（7）夹角余弦距离和Tonimoto系数：
（I）夹角余弦距离：（1-8）
（II）Tonimoto系数（夹角余弦的改进）：（1-9）
下面给出计算欧式距离的C/C++ 代码：
//计算欧氏距离
double euclideanDistance(const vector<double>& v1, const vector<double>& v2)
{
assert(() == ());
double ret = ;
for (vector<double>::size_type i = 0; i != (); ++i)
{
ret += (v1[i] - v2[i]) * (v1[i] - v2[i]);
}
return sqrt(ret);
}
K值的选择
选择较小的K值，近似误差会减小，估计误差会增大，意味着整体模型变得复杂，容易发生过拟合；
选择较大的K值，减少估计误差，近似误差会增大，K值的增大就意味着整体的模型变得简单。
 在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（一部分样本做训练集，一部分做测试集）来选择最优的K值。

（1）多数表决
k近邻法中的分类决策规则往往是多数表决，即由输入对象的k个邻近中的多数类决定输入对象的类，通俗点就是“少数服从多数”。
（2）误分类率
误分类率即对输入对象出现错误分类的概率。其数学表示如下：
对给定的实例，其最近邻的k个训练实