K近邻算法总结
K近邻法（k-nearest neighbor,k-NN）是一种基于分类和回归的方法。
- 输入：实例的特征向量，对应于特征空间的点
- 输出：实例的类别
分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻法不具有显式的学习过程，k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的"模型"。
k=1时称为最近邻算法。
KNN算法的直观理解
它基于这样的简单假设：彼此靠近的点更有可能属于同一个类别。用大俗话来说就是『臭味相投』,或者说『近朱者赤，近墨者黑』。
它并未试图建立一个显示的预测模型，而是直接通过预测点的临近训练集点来确定其所属类别。
K近邻算法的实现主要基于三大基本要素：
- K的选择；
- 距离度量方法的确定；
- 分类决策规则。
KNN算法的原理
算法步骤
K近邻算法的实施步骤如下：
-
根据给定的距离度量，在训练集TT中寻找出与xx最近邻的k个点，涵盖这k个点的x的邻域记作Nk(x);
-
在Nk(x)中根据分类决策规则决定样本的所属类别y:
K的选择
K近邻算法对K的选择非常敏感。K值越小意味着模型复杂度越高，从而容易产生过拟合；K值越大则意味着整体的模型变得简单，学习的近似近似误差会增大。
在实际的应用中，一般采用一个比较小的K值。并采用交叉验证的方法，选取一个最优的K值。
距离度量
距离度量一般采用欧式距离。也可以根据需要采用LpLp距离或明氏距离。
分类决策规则
K近邻算法中的分类决策多采用多数表决的方法进行。它等价于寻求经验风险最小化。
但这个规则存在一个潜在的问题：有可能多个类别的投票数同为最高。这个时候，究竟应该判为哪一个类别？
可以通过以下几个途径解决该问题：
- 从投票数相同的最高类别中随机地选择一个；
- 通过距离来进一步给票数加权；
- 减少K的个数，直到找到一个唯一的最高票数标签。
KNN算法的优缺点
优点
- 精度高
- 对异常值不敏感
- 没有对数据的分布假设；
缺点
- 计算复杂度高
- 在高维情况下，会遇到『维数诅咒』的问题
适用情况
特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好
KNN回归
数据点的类别标签是连续值时应用KNN算法就是回归，与KNN分类算法过程相同，区别在于对K个邻居的处理上。KNN回归是取K个邻居类标签值得加 权作为新数据点的预测值。加权方法有：K个近邻的属性值的平均值（最差）、1/d为权重（有效的衡量邻居的权重，使较近邻居的权重比较远邻居的权重大）、 高斯函数（或者其他适当的减函数）计算权重= gaussian(distance) （距离越远得到的值就越小，加权得到更为准确的估计。
总结
K-近邻算法是分类数据最简单最有效的算法，其学习基于实例，使用算法时我们必须有接近实际数据的训练样本数据。K-近邻算法必须保存全部数据集， 如果训练数据集的很大，必须使用大量的存储空间。此外,由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。k-近邻算法的另一个缺陷是它 无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。
