• 项目

2019 年 1 月

第 34 卷，第 1 期

[测试运行]

使用 C# 自组织映射

作者 James McCaffrey

James McCaffrey自组织映射 (SOM) 是一种相对简单的机器学习 (ML) 技术/对象。但是，描述 SOM 有点困难，因为变体太多，且 SOM 的特性与其他几种 ML 技术相似，包括无监督聚类和监督分类。简单来说，我通常认为 SOM 是一种探索性聚类分析，其目标是将彼此相似的数据项分配给映射节点。

若要了解什么是 SOM 以及本文要讨论的内容，最好的方法是查看图 1 中的演示程序和图 2**** 中的图表。该演示为 UCI 数字数据集创建了一个 5x5 SOM。数据集有 1,797 个项目，SOM 有 25 个节点。创建 SOM，以便每个数据项只与一个映射节点相关联。

自组织映射 (SOM) 演示
图 1 自组织映射 (SOM) 演示

一种可能的 SOM 可视化效果
图 2 一种可能的 SOM 可视化效果

在构建 SOM 之后，该演示计算与每个映射节点关联的最常见数字，并且该信息会显示在图 2 中。SOM 分析的结果通常是直观的，必须主观地进行某种程度的分析。例如，可以看到将表示特定数字的大部分数据项分配给彼此接近的 SOM 节点。并且，表示数字 0 和数字 6 的数据项在 SOM 中彼此接近，这表明它们在某种程度上比数字 4 和数字 8 更相似。

若要更好地理解本文，至少必须拥有中等水平或更好的编程技能，但无需对 SOM 有任何了解。虽然演示程序是使用 C# 进行编码，但将代码重构为其他语言（如 Visual Basic 或 Python），应该不会遇到太多麻烦。图 3**** 展示了完整的演示程序代码（为节省空间，进行了少量小幅改动）。还可以在本文随附的下载内容中获取该代码和数据文件。

图 3 自组织映射演示程序

using System;
using System.Collections.Generic;
using System.IO;
namespace SOmap
{
  class SOmapProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin self-organizing map demo \n");
      Random rnd = new Random(0);
      int Rows = 5, Cols = 5;
      int RangeMax = Rows + Cols;
      double LearnRateMax = 0.5;
      int StepsMax = 100000;
      // Initialize SOM nodes to random values
      double[][][] map = new double[Rows][][];  // [r][c][vec]
      for (int i = 0; i < Rows; ++i) {
        map[i] = new double[Cols][];
        for (int j = 0; j < Cols; ++j) {
          map[i][j] = new double[64];
          for (int k = 0; k < 64; ++k)
            map[i][j][k] = rnd.NextDouble();
        }
      }
      // Read data and labels into memory
      Console.WriteLine("Reading UCI digits data into memory");
      double[][] data = new double[1797][];
      for (int i = 0; i < 1797; ++i)
        data[i] = new double[64];
      int[] labels = new int[1797];
      FileStream ifs = new FileStream("..\\..\\digits_uci.txt",
        FileMode.Open);
      StreamReader sr = new StreamReader(ifs);
      string line = ""; string[] tokens = null;
      int row = 0;
      while ((line = sr.ReadLine()) != null)  {
        tokens = line.Split(',');
        for (int j = 0; j < 64; ++j)
          data[row][j] = double.Parse(tokens[j]) / 16.0;
        labels[row] = int.Parse(tokens[64]);
        ++row;
      }
      sr.Close(); ifs.Close();
      // Construct the SOM
      Console.WriteLine("Constructing 5x5 SO Map");
      for (int s = 0; s < StepsMax; ++s)  // main loop
      {
        if (s % (int)(StepsMax/5) == 0 && s > 0)
          Console.WriteLine("step = " + s);
        double pctLeft = 1.0 - ((s * 1.0) / StepsMax);
        int currRange = (int)(pctLeft * RangeMax);
        double currLearnRate = pctLeft * LearnRateMax;
        // Pick random data index
        int t = rnd.Next(0, 1797);
        // Get (row,col) of closest map node -- 'bmu'
        int[] bmuRC = ClosestNode(data, t, map);
        // Move each map mode closer to the bmu
        for (int i = 0; i < Rows; ++i) {
          for (int j = 0; j < Cols; ++j) {
            if (ManDist(bmuRC[0], bmuRC[1], i, j) <= currRange)
              for (int k = 0; k < 64; ++k)
                map[i][j][k] = map[i][j][k] +
                  currLearnRate * (data[t][k] - map[i][j][k]);
          } // j
        } // i
      } // s(tep)
      Console.WriteLine("Map construction complete \n");
      // Show one map node
      Console.WriteLine("Value of map[1][1] vector is: ");
      Console.WriteLine(map[1][1][0].ToString("F4") + "  " +
        map[1][1][1].ToString("F4") + " . . " +
        map[1][1][63].ToString("F4"));
      Console.WriteLine(" [0]     [1]   . .  [63] \n");
      // Map has been created. assign data items to map
      Console.WriteLine("Assigning data indices to map \n");
      List<int>[][] mapping = new List<int>[Rows][];
      for (int i = 0; i < Rows; ++i)
        mapping[i] = new List<int>[Cols];
      for (int i = 0; i < Rows; ++i)
        for (int j = 0; j < Cols; ++j)
          mapping[i][j] = new List<int>();
      for (int t = 0; t < 1797; ++t)  // each data item
      {
        // Find node map coords where node is closest to D(t)
        int[] rc = ClosestNode(data, t, map);
        int r = rc[0]; int c = rc[1];
        mapping[r][c].Add(t);
      }
      Console.WriteLine("Data indices assigned to map[3][3]: ");
      foreach (int idx in mapping[3][3])
        Console.Write(idx.ToString().PadLeft(5) + "  ");
      Console.WriteLine("\n");
      // Show one possible visualization
      Console.WriteLine("Most common labels for each map node: ");
      for (int i = 0; i < Rows; ++i) {
        for (int j = 0; j < Cols; ++j) {
          List<int> members = new List<int>();  // '0'- '9'
          foreach (int idx in mapping[i][j])
            members.Add(labels[idx]);
          int mcv = MostCommonVal(members);
          Console.Write(mcv + "  ");
        }
        Console.WriteLine("");
      }
      Console.WriteLine("\nEnd self-organizing map demo");
      Console.ReadLine();
    } // Main
    static int ManDist(int x1, int y1, int x2, int y2)
    {
      return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
    }
    static double EucDist(double[] v1, double[] v2)
    {
      double sum = 0;
      for (int i = 0; i < v1.Length; ++i)
        sum += (v1[i] - v2[i]) * (v1[i] - v2[i]);
      return Math.Sqrt(sum);
    }
    static int[] ClosestNode(double[][] data, int t,
      double[][][] map)
    {
      // Coords in map of node closest to data[t]
      double smallDist = double.MaxValue;
      int[] result = new int[] { 0, 0 };  // (row, col)
      for (int i = 0; i < map.Length; ++i) {
        for (int j = 0; j < map[0].Length; ++j)  {
          double dist = EucDist(data[t], map[i][j]);
          if (dist < smallDist) {
            smallDist = dist; result[0] = i; result[1] = j;
          }
        }
      }
      return result;
    }
    static int MostCommonVal(List<int> list)
    {
      if (list.Count == 0) return -1;
      int largestCount = 0; int mostCommon = 0;
      int[] counts = new int[10];
      foreach (int val in list) {
        ++counts[val];
        if (counts[val] > largestCount) {
          largestCount = counts[val]; mostCommon = val;
        }
      }
      return mostCommon;
    }
  } // Program
} // ns

了解 SOM

创建 SOM 的第一步是确保你了解目标数据。UCI 数字数据集有 1,797 个项目。数据如下所示：

0, 12, 0, 8, . . 16, 70, 9, 11, 5, . . 13, 4...

每个项都有 65 个值。前 64 个值是灰度像素值，介于 0 和 16 之间，表示简略的 8x8 手写体数字。最后一个值是数字标签，介于 0 到 9，对应于像素值。因此，之前数据集中的两项表示 7 和 4。可以为具有标签的数据或没有标签的数据创建 SOM，但对于基本 SOM，非标签数据必须严格为数值。

演示程序创建一个 5x5 SOM。SOM 的维度在很大程度上是任意的，主要就是要进行反复试验。SOM 的每个单元都称为一个节点。每个节点保存一个矢量值，所有矢量值都具有相同的长度，都包含数据项，但不包括标签。因此，演示 SOM 中的每个节点都有一个包含 64 个值的矢量。例如，如果查看图 1，将看到在创建 SOM 之后，位置 [1][1] 的映射节点是 (0.000, 0.0237, . .0.0086)。

创建 SOM，使得每个节点矢量代表一些数据项，同时也使得彼此接近的映射节点以几何形式表示相似的数据项。用于在非常高级别的伪代码中创建演示 SOM 的算法是：

create map with random node vectors
loop while s < StepsMax times
  compute what a "close" node is, based on s
  compute a learn rate, based on s
  pick a random data item
  determine map node closest to data item ("BMU")
  for-each node close to the BMU
    adjust node towards data item
end-loop

创建 SOM 实际上更像是一种元启发式算法，而不是严格规定的算法。伪代码中的每个语句都可以用几种方式实现。   

演示程序

为了创建演示程序，我启动了 Visual Studio，并新建了一个名为 SOmap 的 C# 控制台应用程序项目。我使用的是 Visual Studio 2017，但由于演示程序并不严重依赖 .NET，因此可以使用任意一版 Visual Studio。加载模板代码后，我将文件 Program.cs 重命名为 SOmapProgram.cs，并允许 Visual Studio 自动重命名 Program 类。在“编辑器”窗口中，我删除了所有不需要的 using 语句，只留下了对 System 命名空间的引用。然后，我添加了对 Collections.Generic 和 IO 命名空间的引用，因为该演示程序使用 List<int> 集合并从文本文件中读取数据。

演示程序 Main 方法的开头如下所示：

Random rnd = new Random(0);
int Rows = 5, Cols = 5;
int RangeMax = Rows + Cols;
double LearnRateMax = 0.5;
int StepsMax = 100000;

SOM 算法的一个关键部分是确定两个映射节点接近的含义。该演示程序使用曼哈顿距离；例如，位于 [1][1] 和 [3][4] 处的映射节点的曼哈顿距离为 2 + 3 = 5。对于 5x5 映射，任何两个节点之间的最远距离可以是 5 + 5 = 10。

在主处理循环中，定义“接近”节点的当前最大距离计算方式如下：

double pctLeft = 1.0 - ((s * 1.0) / StepsMax);
int currRange = (int)(pctLeft * RangeMax);
double currLearnRate = pctLeft * LearnRateMax;

pctLeft 变量计算剩余步数的百分比。例如，如果 StepsMax 设置为 100 并且当前循环计数器变量为 s = 33，则剩余步数的百分比为 0.67。使用百分比计算步骤 s 的最大相邻距离。同样，当更新相邻节点时，剩余步骤的百分比用于逐渐降低学习速率。

在每个训练迭代步骤中，就欧氏距离而言，映射中最接近随机选择的数据项的一个节点称为最佳匹配单元 (BMU)。更新接近当前 BMU 的每个映射节点的代码是：

for (int i = 0; i < Rows; ++i) {
  for (int j = 0; j < Cols; ++j) {
    if (ManDist(bmuRC[0], bmuRC[1], i, j) <= currRange)
      for (int k = 0; k < 64; ++k)
        map[i][j][k] = map[i][j][k] +
          currLearnRate * (data[t][k] - map[i][j][k]);

换言之，对于每个映射节点，如果曼哈顿距离小于定义距离远近的当前最大范围，则映射节点矢量将在矢量的当前值与当前数据项之间差的一小部分进行调整。

使用 SOM

假设已经创建了 SOM —一个 M 行 × N 列的节点网格，其中每个节点都是一个数值矢量，其长度与被分析的数据长度相同（不包括任何标签）。现在要做什么？使用 SOM 是由具体问题决定的。如果数据没有标签，一种常见技术是创建 U-Matrix，这是一个 M 行 × N 列网格，其中每个节点的值是相应 SOM 节点矢量和相邻节点矢量之间的平均距离。通常显示 U-Matrix，以便将每个值解释为灰度像素值。

显示从没有标签的数据创建的 SOM 的另一种可能原因是将每个节点矢量映射到颜色。例如，如果 SOM 节点矢量的大小为 6，则使用 RGB 颜色模型为每个 SOM 单元着色，方法是将前两个矢量值的平均值分配给 R，将后两个值的平均值分配给 G，将最后两个值的平均值分配给 B。演示 SOM 节点矢量的大小为 64，因此无法明显地将每个矢量与颜色相关联。 

如果数据带有标签，则可以将每个 SOM 节点映射到标签。演示程序根据与每个 SOM 节点关联的分析数据确定所有标签，接下来计算每个节点的最常见标签，然后根据任意颜色分配对节点进行着色。 

总结

演示程序中使用的基本自组织映射结构具有多种变体。可以使用 SOM 中每个单元为六边形的布局，而不是使用 M 行 × N 列的矩形网格。可以使用 SOM 的边缘连接的环形几何图形。可以使用三维代替二维。并且还有许多方法可以定义节点的邻域。其他在此就不一一列举了。

尽管 SOM 在 ML 领域广为人知，但它们的使用频率并不高，至少在我的同事中是这样的。我认为造成这种情况有多个原因，但主要原因也许是 SOM 有如此多的变体，让人难以选择一个特定的设计。此外，根据我的经验，为了让 SOM 能够提供有关数据集的有用见解，需要自定义 SOM（而不是使用 ML 库中的现成 SOM）。但是，总言之，对于某些问题场景，SOM 可以提供有用的见解。

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

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