KNN算法
一 三大要素
KNN算法三大要素：K值的选择，距离向量，以及分类规则。
KNN属于懒惰学习算法，不需要训练过程。既可以分类，也可以进行回归分析。
（1）K值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最有的 K值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。
（2）该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别，对应于经验风险最小化。
（3）距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。
二 优化方法
实现K近邻，主要考虑的问题是如何对训练数据进行快速K近邻搜索。这点在特征空间维数大以及训练数据量大的时候，尤其重要。一种解决方式就是KD树。
KD树是一种对K维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，KD树是一颗二叉树，表示对K维空间的一个划分。时间复杂度为O(logn)。
KNN是基于准确率的，不需要训练过程。
三 优缺点
1、优点 简单，易于理解，易于实现，无需估计参数，无需训练 适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型） 特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好 2、缺点 懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢 可解释性较差，无法给出决策树那样的规则。 四 常见问题 1、k值设定为多大？ k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响） k值通常是采用交叉检验来确定（以k=1为基准） 经验规则：k一般低于训练样本数的平方根 2、类别如何判定最合适？ 投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。 3、如何选择合适的距离衡量？ 高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。 变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。 4、训练样本是否要一视同仁？ 在训练集中，有些样本可能是更值得依赖的。 可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。 5、性能问题？ kNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）。 懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。 已经有一些方法提高计算的效率，例如压缩训练样本量等。 6、能否大幅减少训练样本量，同时又保持分类精度？ 浓缩技术(condensing) 编辑技术(editing) KNN可以用于推荐：
这里我们不用KNN来实现分类，我们使用KNN最原始的算法思路，即为每个内容寻找K个与其最相似的内容，并推荐给用户。
五 基本缺点以及改进
（1）计算复杂度高
（2）分类准确度
a）相似度衡量
b)类别判断策略
c)K值的选择
（1）计算复杂度高解决方案：
a）最简单直接的方法就是：进行特征上的处理，包括特征选择与降维，减少计算量。常用的特征处理方法比如说计算所有特征的信息增益，特征聚类，过滤式/包裹式特征选择，PCA，KPCA降维。
b)优化训练集。裁剪：思想认为训练集中靠近各个类别中心的大部分样本对分类决策用处不大，去掉这部分样本将大大减小开销并压缩数据量。生成代表：通过聚类，将聚类产生的中心点作为新的样本。
c)利用KD树进行K近邻搜索，大大减少计算量。
（2）分类准确度
a)相似度衡量：传统的KNN是将所有特征进行等权重处理，此时我们可以根据重要性对特征分配权重，提高分类准确性。
b)类别判断策略：传统的方式是进行投票法。如果此时样本数据类别不均衡等，此时应该将每个类别根据其密度分配以权重。
c)K值的选择。目前并没有很好的方法，交叉验证，选择一个较好的。K值较小，特别容易受噪声点的影响。K值太大，将其他类别的点加进来了。
