Janeiro de 2019

Volume 34 – Número 1

[Execução de Teste]

Mapas auto-organizados usando C#

Por James McCaffrey

James McCaffreyUm SOM (mapa auto-organizado) é uma técnica/objeto de ML (aprendizado de máquina) relativamente simples. No entanto, os SOMs são um pouco difíceis de descrever já que tem muitas variações e também têm características que se assemelham a várias outras técnicas de ML, incluindo clustering sem supervisão e classificação supervisionada. Em resumo, geralmente penso em um SOM como um tipo de análise exploratória de clustering em que a meta é atribuir itens de dados que são semelhantes entre si a um nó do mapa.

Uma melhor maneira de ter uma noção do que é um SOM e ver onde esse artigo pretende chegar é examinar o programa de demonstração na Figura 1 e o diagrama na Figura 2. A demonstração cria um SOM de 5x5 para o conjunto de dados de dígitos da UCI. O conjunto de dados tem 1.797 itens e o SOM tem 25 nós. O SOM é criado para que cada item de dados seja associado exatamente a um nó de mapa.

Demonstração de SOM (mapa auto-organizado)
Figura 1 Demonstração de SOM (mapa auto-organizado)

Uma possível visualização do SOM
Figura 2 Uma possível visualização do SOM

Depois de criar o SOM, a demonstração calcula o dígito mais comum associado a cada nó do mapa e essa informação é exibida na Figura 2. O resultado de uma análise de SOM é geralmente visual e deve ser analisado de uma maneira um pouco subjetiva. Por exemplo, você pode ver que a maioria dos itens de dados que representam um dígito específico são atribuídos a nós do SOM que estão perto uns dos outros. Os itens de dados que representam o dígito 0 e o dígito 6 estão perto uns dos outros no SOM e isso sugere que eles são mais semelhantes entre si do que o dígito 4 e o dígito 8.

Esse artigo pressupõe que você tenha habilidades de programação intermediárias ou melhores, mesmo que não tenha familiaridade alguma com os SOMs. O programa de demonstração é codificado usando a linguagem C#, mas você não deve ter muita dificuldade para refatorar o código em outra linguagem, como Visual Basic ou Python. O código completo para o programa de demonstração, com algumas pequenas edições para economizar espaço, é apresentado na Figura 3. O código e o arquivo de dados estão disponíveis no download que acompanha este artigo.

Figura 3 Programa de demonstração de mapa auto-organizado

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

Noções básicas sobre SOMs

A primeira etapa ao criar um SOM é certificar-se de que você compreende os dados de destino. O conjunto de dados dos dígitos da UCI possui 1.797 itens. Os dados têm esta aparência:

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

Cada item tem 65 valores. Os primeiros 64 valores são valores de pixel em escala de cinza, entre 0 e 16, que representam um dígito de manuscrito bruto de 8x8. O último valor é o rótulo do dígito, 0 a 9, que corresponde ao valor do pixel. Portanto, os dois itens no conjunto de dados anterior representam um 7 e um 4. Você pode criar um SOM para dados com ou sem rótulos, mas, para SOMs básicos, os dados sem rótulos devem ser estritamente numéricos.

O programa de demonstração cria um SOM de 5x5. As dimensões de um SOM são arbitrárias em grande parte e são principalmente uma questão de tentativa e erro. Cada célula de um SOM é chamada de nó. Cada nó contém um valor de vetor, todos do mesmo tamanho, e os itens de dados, exceto o rótulo. Portanto, cada nó no SOM de demonstração tem um vetor com 64 valores. Por exemplo, se você examinar na Figura 1, verá que depois da criação do SOM, o nó do mapa no local [1][1] é (0,000, 0,0237... 0,0086).

Um SOM é criado para que cada vetor de nó seja representativo de alguns dos itens de dados, mas também para que os nós do mapa que estão próximos uns dos outros geometricamente representem itens de dados semelhantes. O algoritmo usado para criar o SOM de demonstração, em pseudocódigo de alto nível, é:

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

Na verdade, criar um SOM é mais uma meta-heurística do que um algoritmo rigidamente prescrito. Cada uma das instruções no pseudocódigo pode ser implementada de várias maneiras.   

O programa de demonstração

Para criar o programa de demonstração, iniciei o Visual Studio e criei um novo projeto de aplicativo no console C# denominado SOmap. Usei o Visual Studio 2017, mas o programa de demonstração não tem dependências significativas de .NET. Portanto, você pode usar qualquer versão do Visual Studio. Após o carregamento do código de modelo, renomeei o arquivo Program.cs para SOmapProgram.cs e permiti que o Visual Studio renomeasse automaticamente a classe Program para mim. Na janela do Editor, removi tudo usando instruções, deixando somente a referência ao namespace System. Em seguida, adicionei as referências aos namespaces Collections.Generic e E/S porque a demonstração usa uma coleção List<int> e lê dados de um arquivo de texto.

O método Main do programa de demonstração começa com:

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

Uma parte importante do algoritmo de SOM é determinar o que significa para dois nós do mapa estarem próximos um do outro. A demonstração usa a distância de Manhattan. Por exemplo, os nós do mapa em [1][1] e [3][4] têm uma distância de Manhattan de 2 + 3 = 5. Para um mapa de 5x5, o mais distante entre dois nós pode ser 5 + 5 = 10.

No loop de processamento principal, a distância máxima atual que define nós "próximos" é calculada como:

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

A variável pctLeft calcula a porcentagem das etapas restantes. Por exemplo, se StepsMax tiver sido definido como 100 e a variável de contador de loop atual for s = 33, logo, a porcentagem das etapas restantes será 0,67. A distância máxima entre vizinhos para a etapa s é calculada usando a porcentagem. Da mesma forma, quando os nós vizinhos são atualizados, a porcentagem das etapas restantes é usada para diminuir gradualmente a taxa de aprendizagem.

Em cada etapa de iteração de treinamento, um nó no mapa que está mais próximo ao item de dados selecionado aleatoriamente, em termos de distância euclidiana, é chamado de unidade de melhor correspondência (BMU). O código que atualiza cada nó do mapa que está próximo da BMU atual é:

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

Em palavras, para cada nó do mapa, se a distância de Manhattan for menor que o intervalo máximo atual que define a proximidade, o vetor de nó do mapa é ajustado a uma pequena fração da diferença entre o valor atual do vetor e o item de dados atual.

Como usar um SOM

Suponha que você tenha criado um SOM, uma grade de nós n por m, em que cada nó é um vetor numérico que tem o mesmo tamanho que os dados que estão sendo analisados (exceto os rótulos). E agora? Usar um SOM depende do problema. Se seus dados não têm rótulos, uma técnica comum é criar uma matriz U, que é uma grade de n por m, em que o valor de cada nó é a distância média entre o vetor do nó de SOM correspondente e os vetores de nós vizinhos. Uma matriz U normalmente é exibida para que cada valor seja interpretado como um valor de pixel em escala de cinza.

Outra possibilidade de exibir um SOM criado a partir de dados sem rótulos é mapear cada vetor de nó por cor. Por exemplo, se um vetor de nó de SOM tiver tamanho seis, você colorirá cada célula de SOM usando o modelo de cores RGB, atribuindo a média dos dois primeiros valores de vetor a R, os segundos dois valores a G e os dois últimos valores a B. Os vetores do nó de SOM de demonstração têm tamanho 64, portanto, não há uma maneira óbvia de associar cada vetor a uma cor. 

Se os dados tiverem rótulos, você pode mapear cada nó de SOM por rótulo. O programa de demonstração determina todos os rótulos dos dados analisados associados a cada nó de SOM e, em seguida, calcula o rótulo mais frequente para cada nó e colore os nós de acordo com uma atribuição arbitrária de cor. 

Conclusão

Há dezenas de variações da estrutura básica de mapa auto-organizado usada no programa de demonstração. Em vez de usar uma grade retangular de n por m, é possível usar um layout em que cada célula no SOM seja um hexágono. Você pode usar uma geometria toroidal onde as bordas do SOM se conectam. Você pode usar três dimensões, em vez de duas. Há muitas maneiras de definir uma vizinhança próxima para os nós. e assim por diante.

Embora os SOMs sejam amplamente conhecidos no campo de ML, eles não são usados com frequência, pelo menos entre meus colegas. Suspeito que existam motivos para isso, mas talvez a principal causa seja que os SOMs têm tantas variações que é bastante confuso selecionar um design específico. Além disso, com base na minha experiência, para que um SOM forneça informações úteis em um conjunto de dados, é necessário um SOM personalizado (em vez de usar um SOM existente de uma biblioteca de ML). Dito tudo isso, no entanto, para determinados cenários de problemas, os SOMs podem fornecer informações úteis.


Dr. James McCaffreytrabalha para a Microsoft Research em Redmond, Washington. Ele trabalhou em vários produtos importantes da Microsoft, incluindo o Internet Explorer e o Bing. Dr. McCaffrey pelo email jamccaff@microsoft.com.

Agradecemos aos seguintes especialistas técnicos da Microsoft pela revisão deste artigo: Chris Lee, Ricky Loynd, Kenneth Tran