---

2017 年 12 月

第 32 卷，第 12 期

此文章由机器翻译

测试运行 - 使用 C# 了解 k-NN 分类

通过James McCaffrey

分类问题的目标是使用 （通常在机器学习 [ML] 术语中称为功能） 的两个或多个预测器变量的值来预测 （有时称为标签） 的类。例如，你可能想要预测的失败 （低、 中等、 高） 的服务器的风险基于服务器的物理温度和处理的 HTP 请求的平均数目。

有许多 ML 分类技术，包括 naïve Bayes 分类、 神经网络分类和决策树分类。K 最接近的邻居 (k NN) 算法是一种相对简单、 简洁方法。相对于其他技术，k NN 分类的优点是的简洁性与灵活性。两个主要缺点是 k NN 不太适合非数字的预测指标值，它没有很好地大型数据集可扩展性。

此文章介绍了完全如何 k NN 分类，以及提供端到端演示程序用 C# 编写。了解本文所述观点的最佳方式是查看图 1 中的演示程序。演示问题是预测类 ("0，""1，""2") 的具有与值 （5.25、 1.75） 的两个预测器变量的项目。如果 k （邻居值来检查数目） 设置为 1，则预测的类是"1"。 如果 k 设置为 4，预测的类是"2"。 在后台，演示程序使用一套 33 定型的数据项目进行预测。

图 1 分类演示使用 k NN 算法

许多 ML 库包含内置的 k NN 分类函数，但库函数可以是难以或无法 （由于法律问题） 集成到生产系统。了解如何实现从零开始的 k NN 分类可完全控制，并且可以自定义你的系统。

本文假定你有中间或更好的编程技能，但不会假定你知道有关 k NN 分类的任何信息。虽然演示程序是使用 C# 进行编码，但也可以将代码重构为其他语言（如 Java 或 Python），应该不会遇到太多麻烦。演示程序有点太长，无法显示其完整，但在文件下载随附这篇文章提供了完整的源代码。

了解 k NN 算法

中的关系图图 2表示在演示程序中使用的数据。有 33 培训项。每个项包含两个预测器值，x0 和 x1。K NN 算法可以处理问题包含任意数量的预测值，但演示使用只使用两个，以便使问题可以轻松地可视化图形中。

图 2 演示程序定型数据

预测器变量的值是 0 到 9 之间的所有。在执行 k NN 分类时，很重要，以便很大量度不会严重影响小量规范化的预测指标值。例如，假设你有 （如 $48000) 的预测器变量年度收入和年龄 （例如 32)。你无法通过所有的收入值除以 10000 （如 4.8 的给定值），将所有年龄值都除以 10 （赋予值如 3.2） 进行规范化。其他常见的两个规范化技术为 z 评分规范化和最小-最大值规范化。

许多 ML 技术，包括 k NN 分类需要培训具有已知的数据，请更正的预测指标值和类标签。演示定型数据具有三个不同的类，由红色、 绿色和黄色。蓝色的数据点 （5.25，1.75） 是未知的对象，来预测。当 k 设置为 1 时，k NN 查找单个、 最近的定型数据项，并作为未知的项的预测类返回该最接近的数据项目的类。

在此示例中，为 （5.25，1.75） 项、 最接近定型数据项目的未知是绿色 (类 ="1") 在点 （6.0，1.0） 以便预测的类是"1"。 当使用 k NN，你必须指定如何度量数据项，因此，您可以定义"最近的"的含义之间的距离。演示程序使用欧几里得距离。之间的距离 （5.25，1.75） 和 （6.0，1.0） 是 sqrt ((5.25-6.0) ^2 + (1.75 1.0) ^2) = sqrt （0.5625 + 0.5625） = sqrt(1.1250) 中所示 = 1.061，图 1。

当 k 设置为 4 时，预测的类取决于四个最近的定型数据项目。在演示示例中，四个最近的项位于 （6.0，1.0），（5.0、 3.0），（4.0、 2.0） 和 （4.0，1.0）。关联的类标签的项 ("1，""0，""2，""2")。因为有更多"2"的标签，比"0"和"1"的标签，所以预测的类是"2"。

使用 k NN 时必须指定如何确定中的一套 k 最接近类标签的预测的类。演示程序使用大多数投票方法。请注意，使用简单的多数投票时，你可以运行到平分情况。但是，在实践中，k NN 大多数投票 ties 非常少见。演示计划返回发生等同值时的最低类标签。例如，如果关联的标签 ("2，""1，""1，""2")，然后演示计划投票机制将返回"1。

演示程序

若要演示程序进行编码，我启动 Visual Studio 和创建一个新 C# 控制台应用程序并将其命名为 KNN。我使用 Visual Studio 2015 中，但该演示程序有没有有效的.NET Framework 依赖关系，因此任何最新版本的 Visual Studio 将正常工作。

模板代码加载到编辑器窗口后，我将右击解决方案资源管理器窗口中的 Program.cs 文件并且重文件命名为 KNNProgram.cs，则允许自动重类程序命名为我的 Visual Studio。在模板生成的代码顶部，我删除了所有不必要的 using 语句，仅留下引用顶级 System 命名空间的语句。

图 3 展示了整体程序结构（为节省空间，进行了少量小幅改动）。演示使用简单的静态方法的方法，并且所有正常的错误检查已删除了需要清除的主要想法。

图 3 总体程序结构

using System;
namespace KNN
{
  class KNNProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin k-NN classification demo ");
      double[][] trainData = LoadData();
      int numFeatures = 2;
      int numClasses = 3;
      double[] unknown = new double[] { 5.25, 1.75 };
      Console.WriteLine("Predictor values: 5.25 1.75 ");
      int k = 1;
      Console.WriteLine("With k = 1");
      int predicted = Classify(unknown, trainData,
        numClasses, k);
      Console.WriteLine("Predicted class = " + predicted);
      k = 4;
      Console.WriteLine("With k = 4");
      predicted = Classify(unknown, trainData,
        numClasses, k);
      Console.WriteLine("Predicted class = " + predicted);
      Console.WriteLine("End k-NN demo ");
      Console.ReadLine();
    }
    static int Classify(double[] unknown,
      double[][] trainData, int numClasses, int k) { . . }
    static int Vote(IndexAndDistance[] info,
      double[][] trainData, int numClasses, int k) { . . }
    static double Distance(double[] unknown,
      double[] data) { . . }
    static double[][] LoadData() { . . }
  } // Program class
  public class IndexAndDistance : IComparable<IndexAndDistance>
  {
    public int idx;  // Index of a training item
    public double dist;  // To unknown
    // Need to sort these to find k closest
    public int CompareTo(IndexAndDistance other)
    {
      if (this.dist < other.dist) return -1;
      else if (this.dist > other.dist) return +1;
      else return 0;
    }
  }
} // ns

通过设置定型数据开始演示：

static void Main(string[] args)
{
  Console.WriteLine(“Begin k-NN classification demo “);
  double[][] trainData = LoadData();
...

数据是硬编码，并存储到数组的数组样式矩阵。在非演示方案中很可能将到文本文件中的内存中读取数据。因为 k NN 分类通常将所有定型数据都存储到内存中，使用非常大的数据集的方案不容易地进行扩展方法。方法 LoadData 定义为：

static double[][] LoadData()
{
  double[][] data = new double[33][];
  data[0] = new double[] { 2.0, 4.0, 0 };
    ...
  data[12] = new double[] { 3.0, 4.0, 1 };
    ...
  data[32] = new double[] { 4.0, 2.0, 2 };
  return data;
}

每个项的前两个值是预测值的值，最后一个的值为类标签。常见的备选设计是存储的预测指标值存储在矩阵中，但将类标签存储在单独的数组。演示代码假定将类标签是数字，并且连续地进行编号从 0 开始。如果类标签位于非数字，例如"低、""中，""高，"你必须对数据进行编码，在预处理阶段，或以编程方式将数据读入内存时。

接下来，演示设置未知的项来预测，如下所示：

int numFeatures = 2;
int numClasses = 3;
double[] unknown = new double[] { 5.25, 1.75 };
Console.WriteLine("Predictor values: 5.25 1.75 ");

演示计划不实际使用 numFeatures 的变量，但很快就会看到，有许多可能的自定义点 k NN 分类和 numFeatures 值很有用。

接下来，演示使最简单的可能的 k NN 预测：

int k = 1;
Console.WriteLine("With k = 1");
int predicted = Classify(unknown, trainData,
  numClasses, k);
Console.WriteLine("Predicted class = " + predicted);

分类方法接受参数要预测，定型数据、 定型数据中的类的数目和最近近邻，以评估矩阵的项。原则上，你可以实现方法分类，以便它在扫描的训练数据来以编程方式确定的数目类，但所需的工作量超过带来的好处，我认为。

演示程序最后使用：

...
  k = 4;
  Console.WriteLine(“With k = 4”);
  predicted = Classify(unknown, trainData,
    numClasses, k);
  Console.WriteLine(“Predicted class = “ + predicted);
  Console.WriteLine(“End k-NN demo “);
  Console.ReadLine();
}

没有用于确定 k 的值时使用 k NN 分类任何良好规则的经验法则。K k NN 分类中的值是 hyperparameter 而必须由直觉和实验。

实现 k NN 算法

在极高级别伪代码中，演示程序使用的 k NN 分类算法是：

Compute distances from unknown to all training items
Sort the distances from nearest to farthest
Scan the k-nearest items; use a vote to determine the result

分类方法的定义开始计算，并将存储到未知的项进行分类和所有的培训项之间的距离的数组中所示图 4。

图 4 定义的分类方法

static int Classify(double[] unknown,
  double[][] trainData, int numClasses, int k)
{
  int n = trainData.Length;
  IndexAndDistance[] info = new IndexAndDistance[n];
  for (int i = 0; i < n; ++i) {
    IndexAndDistance curr = new IndexAndDistance();
    double dist = Distance(unknown, trainData[i]);
    curr.idx = i;
    curr.dist = dist;
    info[i] = curr;
  }
...

它没有足够可用于存储和排序只之间的距离未知的项到每个训练项，因为你需要知道与每个距离相关联的类。演示计划定义一个名为 IndexAndDistance，训练项和未知的项之间的关联的距离包含索引的简单容器类：

public class IndexAndDistance : IComparable<IndexAndDistance>
{
  public int idx;  // index of a training item
  public double dist;  // distance to unknown
  public int CompareTo(IndexAndDistance other) {
    if (this.dist < other.dist) return -1;
    else if (this.dist > other.dist) return +1;
    else return 0;
  }
}

类标签将间接存储，因为如果你知道培训项的索引，您可以查询定型数据的矩阵中的类标签行中的最后一个单元指向由索引。备用设计是显式存储刚刚类标签但存储的培训项索引提供更大的灵活性。另一种方法是显式存储索引和类标签。

因为 k NN 必须以确定 k 最接近项的索引距离项进行排序，IndexAndDistance 定义通过定义 CompareTo 方法实现 IComparable 接口。执行此操作，可自动排序 IndexAndDistance 对象的数组。如果重构到不支持自动排序的编程语言中的演示代码，你将必须实现上的一种结构，运行自定义排序方法或实现自定义排序方法适用于并行数组。

有几个替代项为索引距离项进行排序-例如，使用的堆数据结构，但在增加的复杂性超过你会收到任何性能改善我看来。

所有定型索引距离项都存储后，顺序存储，并显示 k 最接近项目的信息：

Array.Sort(info);  // sort by distance
Console.WriteLine("Nearest / Distance / Class");
Console.WriteLine("==========================");
for (int i = 0; i < k; ++i) {
  int c = (int)trainData[info[i].idx][2];
  string dist = info[i].dist.ToString("F3");
  Console.WriteLine("( " + trainData[info[i].idx][0] +
    "," + trainData[info[i].idx][1] + " )  :  " +
    dist + "        " + c);
}

类标签，c，会从单元格 [2] 的定型数据的行提取。这假定有两个预测器变量。上级方法将是将 numFeatures 自变量传递给方法分类，然后访问单元格 [numFeatures]。

显示有关 k 最接近定型项目的信息是可选的但它说明了 k NN 分类与许多其他方法相比的一个优点。K NN 算法是某种程度上解释在意义上，你可以确定完全未知的项已分类方式。一些技术，值得注意的是神经网络分类，很难或无法解释。

分类方法来确定通过扫描 k 最接近定型项来确定未知的项的预测的类：

...
  int result = Vote(info, trainData, numClasses, k);
  return result;
} // Classify

帮助器方法投票接受该数组的索引距离的所有项。另一种方法是将传递只是第一个 k 的单元格数组。

距离和投票

分类方法调用帮助器方法的距离并且投票。方法距离定义为：

static double Distance(double[] unknown, double[] data)
{
  double sum = 0.0;
  for (int i = 0; i < unknown.Length; ++i)
    sum += (unknown[i] - data[i]) * (unknown[i] - data[i]);
  return Math.Sqrt(sum);
}

这是欧几里得距离的简单实现。你可以考虑了常见的替代项包括的 Manhattan 距离、 Mahalanobis 距离和基于相似性，如径向基础函数内核度量值。由于 k NN 需要"最近"的概念，和大多数距离度量值使用严格数值或严格非数值数据，则 k NN 分类不适合于混合的数值和分类数据的问题。

帮助器方法显示在屏幕上投票图 5。确定从 k 项共识类标签是不是您可能认为有点棘手。演示使用简单的方法，其中每个 k 最接近定型项获取其类标签的一票。此方法不会考虑之间的距离。常见的替代方法是通过距离的权重投票，以便更接近于未知的项的培训项具有更大的影响力。

图 5 投票方法

static int Vote(IndexAndDistance[] info, double[][] trainData,
  int numClasses, int k)
{
  int[] votes = new int[numClasses];  // One cell per class
  for (int i = 0; i < k; ++i) {       // Just first k
    int idx = info[i].idx;            // Which train item
    int c = (int)trainData[idx][2];   // Class in last cell
    ++votes[c];
  }
  int mostVotes = 0;
  int classWithMostVotes = 0;
  for (int j = 0; j < numClasses; ++j) {
    if (votes[j] > mostVotes) {
      mostVotes = votes[j];
      classWithMostVotes = j;
    }
  }
  return classWithMostVotes;
}

演示实现不显式处理具有重复的定型数据项目。实际数据量没有过多的重复数据，但如果定型数据包含大量重复项，你可能想要考虑删除它们。

总结

K NN 分类算法说是最简单方法之一的所有计算机的学习方法。除了简单起见，k NN 分类可以轻松地处理 （而不是轻松地仅适用于二元分类一些技术） 的多类问题。另一个优点是，k NN 可以轻松地处理具有不寻常的特征的数据，如 dummy 演示数据具有多个犯罪类标签。一些技术，如逻辑回归和非内核支持向量机，可以只处理是以线性方式可分离的数据。K NN 分类的两个其他相对好处是实现，灵活性和 interpretability 的结果。

在负一侧，k NN 分类不能很好地使用分类数据或混合的数值和分类数据。技术不缩放至大型数据集。K NN 分类与定型数据本地几何图形高度敏感。

如果我有严格数值的预测指标值分类问题和一整套非巨大的定型数据 （例如，少于一百万项），使用 k NN 通常是我的第一种方法。然后我将尝试更复杂的技术，通常包括神经网络分类。在某些情况下，将使用神经网络分类 k NN 分类结果进行组合的系综方法可能导致非常可靠和准确的预测系统。

---

Dr.James McCaffrey 供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与过多个 Microsoft 产品的工作，包括 Internet Explorer 和必应。Scripto可通过 jamccaff@microsoft.com 与 McCaffrey 取得联系。

衷心感谢以下 Microsoft 技术专家对本文的审阅：Chris Lee、 Ricky Loynd、 Ken Tran

---

在 MSDN 杂志论坛讨论这篇文章