共用方式為

2017 年 12 月

第 32 卷，第 12 期

本文章是由機器翻譯。

測試回合 - 使用 C# 了解 k-NN 分類

由James McCaffrey

James McCaffrey分類問題的目標是要用於預測 （有時稱為 「 標籤 」） 的類別 （通常稱為機器學習 [ML] 術語中的功能） 的兩個或多個預測量變數的值。例如，您可能想要預測伺服器失敗 （低、 中、 高） 的風險根據 HTP 處理的要求平均數目和實體伺服器的溫度。

有許多 ML 分類技術，包括貝氏機率分類分類、 類神經網路分類，以及決策樹分類。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 定型資料來進行預測的項目。

分類示範使用 k NN 演算法
圖 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-score 正規化和最小值最大值正規化，則兩個其他常見正規化技術。

許多 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 會自動為我重新命名類別的程式。在範本產生的程式碼頂端，我刪除所有不必要使用陳述式，留下只有一個參考最上層系統命名空間。

中會顯示整體的程式結構，以節省空間，少數稍加編輯圖 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 分類通常會將所有定型資料都儲存至記憶體，因為項技術輕鬆地不適合非常大型資料集的案例。方法使用定義為：

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 NN 分類時決定的值，k。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 定義實作 IComparable 介面定義 CompareTo 方法。這樣做可讓您自動排序 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

Helper 方法投票接受索引距離的所有項目陣列。另一個方法是陣列的將僅的第 k 儲存格。

距離和投票

分類方法呼叫的距離，並投票的 helper 方法。方法距離被定義為：

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);
}

這是歐幾里德距離的簡單實作。常見的替代項目，您可以考慮包括的曼哈頓距離、 Mahalanobis 距離和相似度，例如星形基礎函式核心為基礎的量值。因為 k NN 必須 「 最接近的 」 概念，而且大部分距離度量使用嚴格的數值或嚴格非數值資料，k NN 分類不適合用於混合的數值和分類資料的問題。

Helper 方法中會顯示投票圖 5。判斷共識類別標籤從 k 項目是想像您猜的。示範使用簡單的方法，每個 k 接近定型項目用來取得其類別標籤 1 票。這個方法不會列入考量的距離。一般替代方式是加權投票距離使得訓練未知的項目近的項目會有更大的影響。

圖 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 分類是高度機密至定型資料的本機的幾何。

我有嚴格數值的預測值的分類問題和非龐大的一組定型資料 （例如，小於 1 百萬個項目），使用 k NN 時通常我第一種方法。然後，我將會嘗試更趨精密完美的技術，通常包括 [類神經網路分類。在某些情況下，k NN 分類與類神經網路分類的結果結合的集團方法可能會導致非常強大且精確預測系統。

Dr。James McCaffrey適用於 Microsoft Research Redmond，Wash.他已投入許多 Microsoft 產品，包括 Internet Explorer 和 Bing。Dr。在可到達 McCaffrey jamccaff@microsoft.com。

非常感謝下列 Microsoft 技術專家已檢閱本文章：Chris Lee、 Ricky Loynd、 Ken Tran

2017 年 12 月

第 32 卷，第 12 期

MSDN Magazine 論壇中的這篇文章的討論