KNN分类基本思路

kNN算法计算不同特征值之间的距离对样本进行分类。在特征空间中，如果一个样本附近的k个最近(即特征空间中最邻近)样本的大多数属于某一个类别，则该样本也属于这个类别。

KNN分类算法特点

• 是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0；
• KNN 分类的计算复杂度和训练集中的文档数目成正比，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。

KNN分类算法的三个基本要素

• K 值的选择

  K 值的选择会对算法的结果产生重大影响：

  • K值较小，学习的近似误差小，但估计误差大，对噪音敏感；k值小意味着模型复杂，容易发生过拟合；
  • 如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误；K值大意味着模型简单。

  在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。

  交叉验证

  将原始数据(dataset)进行分组，一部分做为训练集(train set)，另一部分做为验证集(validation set or test set)，首先用训练集对分类器进行训练，再利用验证集来测试训练得到的模型(model)，以此来做为评价分类器的性能指标。

• 距离度量

  一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。

  特征缩放

  将特征的取值控制在某一范围内，保证每个特征占据的权重一致。常用的是归一化和标准化。

• 分类决策规则

  往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别。

  多数表决等价于经验风险（误分类率）最小化

  分类的损失函数：0-1损失

  误分类率：

  $$ \frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i\neq c_j)=1-\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i=c_j) $$

  其中实例$x\in \mathcal{X}$，$N_k(x)$为最近邻的k个训练实例点的集合，$c_j$为该集合区域的类。

  要是误分类率最小化，即经验损失最小，就要使$\sum_{x_i\in N_k(x)}I(y_i=c_j)$最大，故多数表决等价于经验风险最小化。

KNN分类算法存在的不足

• 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。由于算法使用多数表决规则，即使该样本不属于大容量类，也被分为了大容量类。该问题可以采用权值的方法（样本距离小的邻居权值大）来改进。
• 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

KNN回归算法

• 通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。
• 更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值，如权值与距离成反比。