• 项目

2019 年 5 月

第 34 卷，第 5 期

[测试运行]

使用 C# 的加权 k-NN 分类

通过James McCaffrey

James McCaffrey机器学习 (ML) 分类问题的目标是预测离散值。例如，你可能想要预测其政治倾向 （保守、 温和、 自由） 等基于其年龄、 年度医疗保健支出、 性别、 受教育水平的人员。有许多不同的分类技术，包括神经网络、 决策树和逻辑回归。在本文中，我将介绍如何实现加权的 k 最近的邻居的算法，使用C#语言。

了解本文所述观点的最佳方法是看看该演示中运行图 1以及图表中的关联数据图 2。演示程序设置了 33 虚拟数据项目。每个项表示某人的年龄、 年度医疗保健支出和任意类来预测 （0、 1、 2），其中您可以将视为政治倾向，为 concreteness。数据具有只有两个预测器变量，因此它可以显示在关系图，但 k NN 适用于任意数量的预测值。

加权的 K-NN 分类演示运行
图 1 实施的加权 K-NN 分类演示运行

加权的 K-NN 数据
图 2 加权 k NN 数据

具有已规范化数据。使用 k NN，时，一定要进行规范化数据以便大值，例如 $30000，每年费用不会严重影响较小的值，例如 25 个年龄。演示的目标是预测新人员已规范化年龄的类并节省费用 （0.35，0.38）。该演示设置 k = 6 并找到靠近分类项的六个标记的数据项目。

确定后的六个最接近标记的数据项目，演示使用加权的投票技术来访问决策。类 （0、 1、 2） 的加权投票值为 （0.3879、 0.4911、 0.1209），因此处的项 （0.35，0.38） 将被归类为类 1。

本文假定您有中等或更好地编程技能的C#或 C 系列语言，如 Python 或 Java 中，但并不假定您知道有关加权的 K-NN 算法的任何信息。在本文中显示完整的演示代码和关联的数据。源代码和数据也是在随附下载中提供的。为了尽可能地让主要思想清晰明确，已删除所有常见错误检查。

了解 K-NN 加权的算法

加权的 K-NN 算法是最简单的所有机器学习技术，但有一些棘手的实现详细信息。大多数开发人员的第一个问题是，"如何确定 k 的值？" 某种程度上对答案是 k 的值必须通过反复试验来确定。

使用 k NN，必须计算为所有标记的数据分类项之间的距离。有许多距离函数，但使用欧几里得距离是简单而有效。两个项之间的欧几里得距离是坐标的平方差之和的平方根。例如，如果标记的数据项目为 （0.20，0.60） 和要分类的项是 （0.35，0.38） 然后：

dist = sqrt( (0.20 - 0.35)^2 + (0.60 - 0.38)^2 )
       = sqrt(0.0225 + 0.0484)
       = 0.2663

计算所有距离和查找 k 最近距离之后, 必须使用投票算法来确定预测的类。有许多方法来计算距离从预测。该演示程序使用方法，最好通过举例可以解释的反权重。假设，如下所示演示中，六个最接近的距离为 （0.0728、 0.0781、 0.1118、 0.1217、 0.1300、 0.1414） 和关联标记为类是 （0、 1、 0、 1、 1、 2）。计算的每个距离反转，总和逆方法，然后除以总和的每个反。对于演示，逆方法为 （13.7363、 12.8041、 8.9445、 8.2169、 7.6923、 7.0721）。逆方法之 58.4663。每个反距离除以总和提供权重：(0.2349, 0.2190, 0.1530, 0.1405, 0.1316, 0.1210).

每个权重是其关联的类一票。在演示中，第一个和第三个最接近项具有类 0，因此为类 0 投票是第一个和第三个权重的总和：0.2349 + 0.1530 = 0.3879.同样，类 1 的投票是 0.2190 + 0.1405 + 0.1316 = 0.4911。只需的第六个权重，0.1210 类 2 的投票。最终预测是具有最大的投票的类。

演示程序

图 3 展示了完整的演示程序（为节省空间，进行了少量小幅改动）。若要创建节目，我启动了 Visual Studio 并创建名为 WeightedKNN 的新控制台应用程序。我使用 Visual Studio 2017，但演示程序并不非常依赖.NET Framework。

图 3 加权的 K-NN 演示程序

using System;
namespace WeightedKNN
{
  class WeightedKNNProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin weighted k-NN demo ");
      Console.WriteLine("Normalized age-expenses data: ");
      Console.WriteLine("[id =  0, 0.25, 0.43, class = 0]");
      Console.WriteLine(" . . . ");
      Console.WriteLine("[id = 32, 0.46, 0.22, class = 2]");
      double[][] data = new double[33][];
      data[0] = new double[] { 0, 0.25, 0.43, 0 };
      data[1] = new double[] { 1, 0.26, 0.54, 0 };
      data[2] = new double[] { 2, 0.27, 0.60, 0 };
      data[3] = new double[] { 3, 0.37, 0.31, 0 };
      data[4] = new double[] { 4, 0.38, 0.70, 0 };
      data[5] = new double[] { 5, 0.49, 0.32, 0 };
      data[6] = new double[] { 6, 0.46, 0.70, 0 };
      data[7] = new double[] { 7, 0.55, 0.32, 0 };
      data[8] = new double[] { 8, 0.58, 0.74, 0 };
      data[9] = new double[] { 9, 0.67, 0.42, 0 };
      data[10] = new double[] { 10, 0.69, 0.51, 0 };
      data[11] = new double[] { 11, 0.66, 0.63, 0 };
      data[12] = new double[] { 12, 0.29, 0.43, 1 };
      data[13] = new double[] { 13, 0.35, 0.51, 1 };
      data[14] = new double[] { 14, 0.39, 0.63, 1 };
      data[15] = new double[] { 15, 0.47, 0.40, 1 };
      data[16] = new double[] { 16, 0.48, 0.50, 1 };
      data[17] = new double[] { 17, 0.45, 0.61, 1 };
      data[18] = new double[] { 18, 0.55, 0.41, 1 };
      data[19] = new double[] { 19, 0.57, 0.53, 1 };
      data[20] = new double[] { 20, 0.56, 0.62, 1 };
      data[21] = new double[] { 21, 0.68, 0.12, 1 };
      data[22] = new double[] { 22, 0.78, 0.24, 1 };
      data[23] = new double[] { 23, 0.86, 0.30, 1 };
      data[24] = new double[] { 24, 0.86, 0.22, 1 };
      data[25] = new double[] { 25, 0.86, 0.12, 1 };
      data[26] = new double[] { 26, 0.78, 0.14, 1 };
      data[27] = new double[] { 27, 0.28, 0.13, 2 };
      data[28] = new double[] { 28, 0.25, 0.21, 2 };
      data[29] = new double[] { 29, 0.39, 0.14, 2 };
      data[30] = new double[] { 30, 0.37, 0.24, 2 };
      data[31] = new double[] { 31, 0.45, 0.13, 2 };
      data[32] = new double[] { 32, 0.46, 0.22, 2 };
      double[] item = new double[] { 0.35, 0.38 };
      Console.WriteLine("Nearest (k=6) to (0.35, 0.38):");
      Analyze(item, data, 6, 3);  // 3 classes
      Console.WriteLine("End weighted k-NN demo ");
      Console.ReadLine();
    } // Main
    // ------------------------------------------------------
    static void Analyze(double[] item, double[][] data,
      int k, int c)
    {
      // 1. Compute all distances
      int N = data.Length;
      double[] distances = new double[N];
      for (int i = 0; i < N; ++i)
        distances[i] = DistFunc(item, data[i]);
      // 2. Get ordering
      int[] ordering = new int[N];
      for (int i = 0; i < N; ++i)
        ordering[i] = i;
      double[] distancesCopy = new double[N];
      Array.Copy(distances, distancesCopy, distances.Length);
      Array.Sort(distancesCopy, ordering);
      // 3. Show info for k nearest
      double[] kNearestDists = new double[k];
      for (int i = 0; i < k; ++i)
      {
        int idx = ordering[i];
        Show(data[idx]);
        Console.WriteLine("  distance = " +
          distances[idx].ToString("F4"));
        kNearestDists[i] = distances[idx];
      }
      // 4. Vote
      double[] votes = new double[c];  // one per class
      double[] wts = MakeWeights(k, kNearestDists);
      Console.WriteLine("Weights (inverse technique): ");
      for (int i = 0; i < wts.Length; ++i)
        Console.Write(wts[i].ToString("F4") + "  ");
      Console.WriteLine("\n\nPredicted class: ");
      for (int i = 0; i < k; ++i) {
        int idx = ordering[i];
        int predClass = (int)data[idx][3];
        votes[predClass] += wts[i] * 1.0;
      }
      for (int i = 0; i < c; ++i)
        Console.WriteLine("[" + i + "]  " +
        votes[i].ToString("F4"));
    } // Analyze
    static double[] MakeWeights(int k, double[] distances)
    {
      // Inverse technique
      double[] result = new double[k];  // one perneighbor
      double sum = 0.0;
      for (int i = 0; i < k; ++i)
      {
        result[i] = 1.0 / distances[i];
        sum += result[i];
      }
      for (int i = 0; i < k; ++i)
        result[i] /= sum;
      return result;
    }
    static double DistFunc(double[] item, double[] dataPoint)
    {
      double sum = 0.0;
      for (int i = 0; i < 2; ++i) {
        double diff = item[i] - dataPoint[i+1];
        sum += diff * diff;
      }
      return Math.Sqrt(sum);
    }
    static void Show(double[] v)
    {
      Console.Write("idx = " + v[0].ToString().PadLeft(3) +
        "  (" + v[1].ToString("F2") + " " +
        v[2].ToString("F2") + ") class = " + v[3]);
    }
  } // Program
} // ns

加载模板代码后，在编辑器窗口中我删除不需要命名空间的所有引用，只留下对引用顶级 System 命名空间。在解决方案资源管理器窗口中，我右键单击文件 Program.cs，它重命名为更具描述性的 WeightedKNNProgram.cs，并允许 Visual Studio 会自动重命名 Program 类。

为简单起见，该演示程序使用静态代码方法而不是面向对象的编程方法。分析方法中完成大部分工作。

将数据加载到内存

演示程序会对虚拟数据和分类项：

double[][] data = new double[33][];
data[0] = new double[] { 0, 0.25, 0.43, 0 };
// Etc.
data[32] = new double[] { 32, 0.46, 0.22, 2 };
double[] item = new double[] { 0.35, 0.38 };

在非演示方案中，你可能会将数据存储在文本文件或 SQL 表并写入帮助器方法来将数据加载到数组的数组样式矩阵。我的数据只是"数据，"而不是类似于 trainData 的内容，因此命名为使用 k NN 的数据不真正用于为通用模型定型。

每个数据项中的第一个值是任意的 id。我使用从零到 32 的连续整数，但在许多情况下，您必须有意义的 Id，如人员的雇员 ID 号。K NN 算法不需要数据 Id，因此 ID 列可忽略。第二个和第三个值是规范化预测因子值。第四个值为类 id。K NN 的类 Id 不是从零开始的整数，但使用这种方案是以编程方式非常方便。

计算距离

K NN 算法的第一步是计算每个标记的数据项到项-到-be 分类的距离。根据我的经验和几个研究结果，选择距离函数应用并不为关键，因为可能会想，简单欧几里得距离通常工作良好。

欧几里得距离的演示实现是：

static double DistFunc(double[] item, double[] dataPoint)
{
  double sum = 0.0;
  for (int i = 0; i < 2; ++i) {
    double diff = item[i] - dataPoint[i+1];
    sum += diff * diff;
  }
  return Math.Sqrt(sum);
}

请注意，for 循环索引进行硬编码，2 表示预测因子值和项 [i] 和 dataPoint 之间的差异的数量 [i + 1] 到帐户的位置 [0] 处的数据 ID 值偏移量。这里的一点是，则通常应编码为特定问题的机器学习算法和编写代码进行设计，旨在通用使用算法之间的权衡。由于 k NN 是那么简单且易于实现，我通常更喜欢代码的特定问题方法。

在第一个想法，似乎会施加 K-NN 所有预测器变量必须是严格的数值的主要限制计算距离函数的要求。直到最近这一想法的一点是，大多数情况下，但是，k NN 不断增长的兴趣的原因之一是，则可能为 k-NN 混合的和非数值数据使用的预测器变量神经编码方式进行处理。

简单地说，思路是使用神经 autoencoder 预测因子变量进行编码。Autoencoder 可以处理非数字数据使用独热编码或 1-of-(N-1) 编码。Autoencoder 预测其输出值以匹配其输入的值。Autoencoder 中央隐藏的层是源和非数值数据的完全数字表示形式。

排序或顺序距离

计算出所有距离后，k NN 算法必须找到 k 最近 （最小） 距离。一种方法是增加整个标记为数据集使用每个距离值，然后显式对增强的数据进行排序。该演示中，使用另一种方法是使用.NET Array.Sort 方法的巧妙重载只是距离和并行关联的数据索引进行排序。关键代码是：

int[] ordering = new int[N];
for (int i = 0; i < N; ++i)
  ordering[i] = i;
double[] distancesCopy = new double[N];
Array.Copy(distances, distancesCopy, distances.Length);
Array.Sort(distancesCopy, ordering);

名为最初排序的数组包含 0、 1、 2。.32.因为您不想要失去其原始顺序的距离创建一份到分类项 33 的距离。该语句 Array.Sort(distancesCopy, ordering) 按从小到大使用快速排序算法 distancesCopy 数组中的值，并同时重新排列排序数组中的索引值。结果是项的，排序数组中的第一个值是项的对数据具有最小距离的索引，第二个值排序中的保留索引的第二个最接近的距离，依此类推。很好！

确定 k NN 权重和投票

使用 k 最近距离来预测某个类的最基本形式是使用简单的大多数规则方法。例如，如果 k = 4，c = 3，和两个最接近的距离都与类 2，和一个最接近的距离是与类 0，关联和一个最接近的距离与相关联类 1，则大多数规则方法预测类 2。请注意使用统一的权重，每个都具有值 1/k，该加权的 K-NN 相当于大多数规则方法。

大多数规则方法具有两个重要问题：首先，等同值是可能的。第二个，同样加权所有距离。加权 k NN 的最常见的权重方案是将应用该演示程序使用的反权重方法。但有许多其他技术。例如，反向距离方法计算所有距离之都和，所有距离都除以总和，然后反转顺序。

另一种方法是使用 k 最近距离 （1、 2、...的排名6） 而不是为单位的距离本身。K = 6，将计算的等级顺序形心权重为 (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) / 6 = 0.4083 (1/2 + 1/3 + 1/4 + 1/5 + 1/6) / 6 = 0.2417，依次类推。

对于演示程序、 反转、 一致性，反向和质心权重为：

Inverse   Uniform   Reverse   Centroids
---------------------------------------
0.2349    0.1667    0.2156    0.4083   
0.2190    0.1667    0.1982    0.2417
0.1530    0.1667    0.1856    0.1583
0.1405    0.1667    0.1705    0.1028
0.1316    0.1667    0.1191    0.0611
0.1210    0.1667    0.1110    0.0278

总结

加权的 K-NN 分类算法已收到增加的关注最近两个原因。首先，通过使用神经 autoencoding，k NN 可以处理混合和非数值预测因子值。其次，与许多其他分类算法相比，则结果的加权 k NN 是相对较容易解释。Interpretability 已成为由于法律的机器学习技术从诸如欧盟等法规要求变得越来越重要的 GDPR。

Dr.James McCaffrey 供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他一直从事多个关键 Microsoft 产品，包括 Azure 和必应。Dr.可通过 jamccaff@microsoft.com 与 McCaffrey 取得联系。

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

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