knn算法
knn算法简介
邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻近值来代表。
如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
深度理解
算法过程
1. 准备数据，对数据进行预处理
2. 选用合适的数据结构存储训练数据和测试元组。
3. 设定参数，如k。
4.维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列。
5. 遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L 与优先级队列中的最大距离Lmax。
6. 进行比较。若L>=Lmax，则舍弃该元组，遍历下一个元组。若L < Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列。
7. 遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别。
8. 测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k 值。
伪代码
搜索k近邻的算法：kNN(A[n],k)
#输入：A[n]为N个训练样本在空间中的坐标，k为近邻数
#输出：x所属的类别
取A[1]~A[k]作为x的初始近邻，计算与测试样本x间的欧式距离d（x,A[i]）,i=1,2,.....,k；
按d（x，A[i]）升序排序；
取最远样本距离D = max{d(x,a[j]) | j=1,2,...,k};
for(i=k+1;i<=n;i++) #继续计算剩下的n-k个数据的欧氏距离
计算a[i]与x间的距离d(x,A[i]);
if(d(x,A[i]))<D
then 用A[i]代替最远样本 #将后面计算的数据直接进行插入即可
最后的K个数据是有大小顺序的，再进行K个样本的统计即可
计算前k个样本A[i]),i=1,2,..,k所属类别的概率;
具有最大概率的类别即为样本x的类
欧式距离等相关部分知识在前几章均有介绍，这里就不详细说了。
特点总结
优点
1.易于实现，无需估计参数
2.对稀有事件进行分类较为方便
3.对于多个标签的对象分类较为方便
缺点
1.当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
2.计算量大
3.可理解性差，无法给出像决策树那样的规则。（此点暂时不详细解释）
Kmeans本质上是无监督学习而KNN是监督学习。Kmeans是聚类算法，KNN是分类算法。
关于K值选择问题，选择较小值，防止过拟合。选取的太小，模型太复杂。K值选取的太大，导致分类模糊
k选择选择奇数可以排除half-half困境
half-half困境：某测试样本的K近邻中一半样本是正样本，一半样本是负样本，没法进行该分类
分类数应该尽量选择为奇数，并且不要是分类结果的偶数倍，否则出现距离相同。
拟合：曲线对样本描述的程度，泛化能力（对新样本的适应能力）
过拟合：过于贴近训练样本的特征，在新的样本集表现普通。
欠拟合：离曲线过远，对训练样本贴近不足，不能在训练集获得足够低的误差
正样本是指属于某一类别的样本，负样本是指不属于某一类别的样本。
分类：根据文本的特征或属性，划分到已有的类别中，对已知分类的数据进行训练和学习，找到这些不同类的特征，再对未分类的数据进行分类。
聚类：不知道事物会被分为几类，根据
将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇
训练集（train set） —— 用于模型拟合的数据样本。
训练集用来训练模型，即确定模型的权重和偏置这些参数，通常我们称这些参数为学习参数。
验证集（development set）—— 是模型训练过程中单独留出的样本集，它可以用于调整模型的超参数和用于对模型的能力进行初步评估。
验证集只是为了选择超参数
超参数是在开始学习过程之前设置值的参数
测试集 —— 用来评估模最终模型的泛化能力。（但不能作为调参、选择特征等算法相关的选择的依据。）
测试集只使用一次，即在训练完成后评价最终的模型时使用。
训练集和测试集的关系
训练集用于建立模型。
测试集用来检验最终选bai择最优的模型的性能如du何。
