Dada una matriz 2D de números, encontrar grupos

Question

Dada una matriz 2D, por ejemplo:

0 0 0 0 0 
0 2 3 0 1 
0 8 5 0 7 
7 0 0 0 4 

salida debe ser grupos de cúmulos:

Cluster 1: <2,3,8,5,7>

Cluster 2: <1,7,4>

Answer 1

Una forma de hacerlo es con un gráfico. Atraviesa la matriz en algún orden (iría de izquierda a derecha, de arriba a abajo). Cuando encuentre un elemento distinto de cero, agréguelo al gráfico. Luego, compruebe todos sus vecinos (parece que quiere vecinos con 8 conexiones), y para cada uno que sea distinto de cero, agregue su nodo al gráfico y conéctelo al elemento actual. Los elementos en el gráfico probablemente tendrán que hacer un seguimiento de sus coordenadas para que pueda ver si está agregando un duplicado o no. Cuando haya terminado de atravesar la matriz, tendrá un gráfico que contiene un conjunto de clústeres. Los clústeres deben ser sub-gráficos de los elementos conectados.

Answer 2

Parece que su problema es encontrar los componentes conectados. Debe usar un método transversal (ya sea BFS o DFS harán el trabajo). Itere sobre todos los elementos, para cada elemento que no sea cero, inicie una poligonal y registre todos los elementos que vea en esa poligonal y convierta cada elemento visitado en cero. Algo así como el código de abajo:

void DFS(int x, int y) 
{ 
    printf("%d ", g[x][y]); 
    g[x][y] = 0; 
    // iterate over neighbours 
    for(dx=-1; dx<=1; dx++) 
    for(dy=-1; dy<=1; dy++) 
     if (g[x+dx][y+dy]) DFS(x+dx, y+dy); 
} 

for(i=0; i<n; i++) 
    for(j=0; j<n; j++) 
    if (g[i][j]) 
    { 
     DFS(i, j); 
     printf("\n"); 
    } 

Answer 3

Si conoce el número de grupos o desea encajar sus datos a un número estático de los grupos, se puede hacer k-medias.

http://en.wikipedia.org/wiki/K-means_clustering

Answer 4

que quiere hacer Connected Component Labeling. Esto generalmente se considera un algoritmo de procesamiento de imágenes, pero coincide con lo que describes.

También obtendrá recomendaciones de K-means porque dijiste matriz 2D de números y es fácil de interpretar que a medida que matriz de números 2D. K-means encuentra grupos de puntos en un plano, no grupos conectados en una matriz 2D como usted solicita.

Answer 5

muestra

Código:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Practice 
{ 
    class Program 
    { 
     static void Main() 
     { 
      var matrix = new[] { new StringBuilder("00000"), new StringBuilder("02301"), new StringBuilder("08507"), new StringBuilder("70004") }; 
      var clusters = 0; 
      for (var i = 0; i < matrix.Length; i++) 
       for (var j = 0; j < (matrix.Any() ? matrix[i].Length : 0); j++) 
        if (matrix[i][j] != '0') 
        { 
         Console.Write("Cluster {0}: <", ++clusters); 
         var cluster = new List<char>(); 
         Traverse(matrix, i, j, ref cluster); 
         Console.WriteLine("{0}>", string.Join(",", cluster)); 
        } 
      Console.ReadKey(); 
     } 

     private static void Traverse(StringBuilder[] matrix, int row, int col, ref List<char> cluster) 
     { 
      cluster.Add(matrix[row][col]); 
      matrix[row][col] = '0'; 
      for (var i = -1; i <= 1 && row + i >= 0 && row + i < matrix.Length; i++) 
       for (var j = -1; j <= 1 && col + j >= 0 && col + j < (matrix.Any() ? matrix[row + i].Length : 0); j++) 
        if(matrix[row + i][col + j] != '0') 
         Traverse(matrix, row + i, col + j, ref cluster); 
     } 
    } 
} 

Algoritmo explicación:

• Para cada fila:
  • Para cada columna en esa fila:
    • Si el artículo es una unvisited distinto de cero:
      1. Guarde el miembro del clúster encontrado;
      2. Marque la ubicación en [fila, columna] como visitado;
      3. Comprobar si los vecinos no cero no visitados durante su estancia en-límites de la matriz:
         • [fila - 1, columna - 1];
         • [fila - 1, columna];
         • [fila - 1, columna + 1];
         • [fila, columna - 1];
         • [fila, columna + 1];
         • [fila + 1, columna - 1];
         • [fila + 1, columna];
         • [fila + 1, columna + 1].
      4. Si un vecino no es visitado, no es cero, repita los pasos 1-4 recursivamente hasta que se visiten todos los vecinos ceros (se han encontrado todos los miembros del clúster).