R 中的数据挖掘算法/分类/kNN

介绍

本章介绍了用于分类的 k 最近邻 (kNN) 算法。kNN 最初由 Fix 和 Hodges ^[1] 提出，是一种非常简单的“基于实例”的学习算法。尽管它很简单，但在某些问题上可以提供非常好的性能。我们对算法进行了高级概述，解释了相关的参数和实现选择，然后逐步进行了案例研究。

k 最近邻

kNN 算法与其他基于实例的算法一样，在分类方面不寻常，因为它没有显式模型训练。虽然需要训练数据集，但它仅仅用于用已知类别的实例填充搜索空间的样本。在此阶段没有执行实际的模型或学习；出于这个原因，这些算法也被称为惰性学习算法。可以使用不同的距离度量，具体取决于数据的性质。欧几里德距离通常用于连续变量，但其他度量可用于分类数据。专门的度量通常对特定问题有用，例如文本分类。当要评估的类未知的实例出现时，算法会计算其 k 个最近邻，并通过对这些邻近点进行投票来分配类别。为了防止平局，人们通常使用奇数 k 用于二元分类。对于多个类别，可以使用众数投票或多数投票。后者有时会导致未将任何类别分配给实例，而前者会导致分类的低支持率。还可以通过距离到被分类实例的倒数函数对每个邻近点进行加权。kNN 用于分类的主要优点是

非常简单的实现。
对搜索空间具有鲁棒性；例如，类别不必线性可分。
当出现具有已知类别的新实例时，分类器可以以非常低的成本在线更新。
很少的参数需要调整：距离度量和 k。

算法的主要缺点是

对每个实例的测试成本很高，因为我们需要计算它到所有已知实例的距离。针对特定问题和距离函数，存在专门的算法和启发式方法，可以缓解此问题。对于具有大量属性的数据集，这是一个问题。当实例数量远大于属性数量时，可以使用 R 树或 kd 树来存储实例，从而实现快速准确的邻居识别。
对噪声或不相关属性的敏感性，这会导致不太有意义的距离数字。缩放和/或特征选择通常与 kNN 结合使用以缓解此问题。
对高度不平衡数据集的敏感性，其中大多数实体属于一个或几个类别，因此不常见的类别在大多数邻近点中通常占主导地位。这可以通过在训练阶段对更流行的类别进行平衡采样来缓解，可能还会与集成方法结合使用。

算法描述

kNN 的训练阶段仅包括简单地存储所有已知实例及其类标签。可以使用表格表示，或使用 kd 树等专门结构。如果我们想调整“k”的值和/或执行特征选择，则可以使用 n 折交叉验证在训练数据集上进行。针对新的实例“t”、给定已知集合“I”的测试阶段如下

计算“t”与“I”中每个实例之间的距离
按数值升序对距离进行排序，并选择前“k”个元素
计算并返回“k”个最近邻中最频繁的类别，可以选择通过每个实例到“t”的距离的倒数对每个实例的类别进行加权

可用实现

R 中至少有三种 kNN 分类实现，它们都可以在 CRAN 上获得

knn
kknn
RWeka，它是流行的 WEKA ^[2] 机器和数据挖掘工具包的桥梁，它提供了 kNN 实现以及数十种用于分类、聚类、回归和数据工程的算法。

在本教程中，我们选择 RWeka，因为它提供的不仅仅是 kNN 分类，并且下面显示的示例会话可用于生成其他分类器，只需稍作修改即可。

安装和运行 RWeka

RWeka 是一个 CRAN 包，因此可以在 R 内部安装

> install.packages("RWeka", dependencies = TRUE)

大多数 R 图形用户界面还通过其 UI 提供包管理。安装完成后，RWeka 可以作为库加载

> library(RWeka)

它附带几个众所周知的数据集，可以作为 ARFF 文件（Weka 的默认文件格式）加载。我们现在加载一个示例数据集，著名的 Iris 数据集 ^[3]，并使用默认参数学习一个 kNN 分类器。

> iris <- read.arff(system.file("arff", "iris.arff", package = "RWeka"))
> classifier <- IBk(class ~., data = iris)
> summary(classifier)

=== Summary ===

Correctly Classified Instances         150              100      %
Incorrectly Classified Instances         0                0      %
Kappa statistic                          1     
Mean absolute error                      0.0085
Root mean squared error                  0.0091
Relative absolute error                  1.9219 %
Root relative squared error              1.9335 %
Total Number of Instances              150     

=== Confusion Matrix ===

  a  b  c   <-- classified as
 50  0  0 |  a = Iris-setosa
  0 50  0 |  b = Iris-versicolor
  0  0 50 |  c = Iris-virginica

虽然在上一个会话中，我们只使用了默认参数，但 RWeka 允许我们以多种方式自定义 KNN 分类器，除了设置 k 的值之外

我们可以通过它们到目标实例的距离的倒数，或通过 1 - 距离来对邻近点进行加权。
我们可以使用留一交叉验证在训练数据中选择 k 的最佳值。
我们可以使用训练实例的滑动窗口，因此一旦分类器了解了 W 个实例，当添加新的实例时，旧的实例就会被丢弃。
我们可以自定义算法存储已知实例的方式，这使我们能够在大型数据集上使用 kd 树和类似的数据结构来加快邻居搜索。

案例研究

我们现在将对 Iris 数据集进行更详细的探索，使用交叉验证进行实际测试统计，并进行一些参数调整。

数据集

Iris 数据集包含 150 个实例，对应于三种等频的鸢尾花物种（Iris setosa、Iris versicolour 和 Iris virginica）。下图显示了 Iris versicolor，来自 Wikimedia Commons。

每个实例包含四个属性：萼片长度（厘米）、萼片宽度（厘米）、花瓣长度（厘米）和花瓣宽度（厘米）。下一张图片显示了每个属性相对于其他属性的绘制，不同类别的颜色不同。

执行和结果

我们将生成一个 kNN 分类器，但我们会让 RWeka 自动在 1 到 20 之间找到 k 的最佳值。我们还将使用 10 折交叉验证来评估我们的分类器

> classifier <- IBk(class ~ ., data = iris, 
                    control = Weka_control(K = 20, X = TRUE))
> evaluate_Weka_classifier(classifier, numFolds = 10)
=== 10 Fold Cross Validation ===

=== Summary ===

Correctly Classified Instances         142               94.6667 %
Incorrectly Classified Instances         8                5.3333 %
Kappa statistic                          0.92  
Mean absolute error                      0.041 
Root mean squared error                  0.1414
Relative absolute error                  9.2339 %
Root relative squared error             29.9987 %
Total Number of Instances              150     

=== Confusion Matrix ===

  a  b  c   <-- classified as
 50  0  0 |  a = Iris-setosa
  0 46  4 |  b = Iris-versicolor
  0  4 46 |  c = Iris-virginica

> classifier
IB1 instance-based classifier
using 6 nearest neighbour(s) for classification

由于交叉验证会生成数据集的随机分区，因此您的结果可能会有所不同。但是，通常情况下，模型会犯不超过 10 个错误。

分析

这个简单的案例研究表明，kNN 分类器在数据集上犯的错误很少，尽管简单，但它不是线性可分的，如散点图所示，以及通过查看混淆矩阵，其中所有误分类都在 Iris Versicolor 和 Iris Virginica 实例之间。案例研究还展示了 RWeka 如何使学习分类器（以及预测器和聚类模型）变得非常容易，以及如何试验其参数。在这个经典的数据集中，kNN 分类器犯的错误很少。

参考文献

^ Fix, E., Hodges, J.L. (1951); Discriminatory analysis, nonparametric discrimination: Consistency properties. Technical Report 4, USAF School of Aviation Medicine, Randolph Field, Texas.
^ Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, Ian H. Witten (2009); The WEKA Data Mining Software: An Update. SIGKDD Explorations, 11(1).
^ Fisher,R.A. (1936); The use of multiple measurements in taxonomic problems. Annual Eugenics, 7, Part II, 179-188.

[1]

[2]

[3]