По двумерному массиву чисел найти кластеры

Question

Для двумерного массива, например:

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

Выходными данными должны быть группы кластеров:

Кластер 1: <2,3,8,5,7>

Кластер 2: <1,7,4>

Answer 1

Кажется, ваша проблема в поиске подключенных компонентов.Вы должны использовать метод обхода (BFS или DFS сделают всю работу).Выполните итерацию по всем элементам, для каждого ненулевого элемента начните ход и запишите все элементы, которые вы видите в этом ходе, и превратите каждый посещенный элемент в ноль.Что-то вроде кода ниже:

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 2

Вы хотите сделать Маркировка подключенного компонента .Обычно это считается алгоритмом обработки изображений, но он соответствует тому, что вы описываете.

Вы также получите рекомендации K-средних, потому что вы сказали 2D-массив чисел , и его легко интерпретировать.это как массив двумерных чисел .K-means находит кластеры точек на плоскости, а не связанные группы в 2D-массиве, как вы запрашиваете.

Answer 3

Один из способов сделать это с графиком. Пройдите матрицу в некотором порядке (я бы пошел слева направо, сверху вниз). Когда вы встретите ненулевой элемент, добавьте его на график. Затем проверьте всех его соседей (похоже, что вы хотите 8-соединенных соседей), и для каждого ненулевого добавьте свой узел в график и подключите его к текущему элементу. Элементы на графике, вероятно, должны будут отслеживать свои координаты, чтобы вы могли видеть, добавляете ли вы дубликат или нет. Когда вы закончите обход матрицы, у вас есть график, который содержит набор кластеров. Кластеры должны быть подграфами связанных элементов.

Answer 4

Пример кода:

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

Объяснение алгоритма:

• Для каждой строки:
  • Для каждого столбца в этой строке:
    • Если не посещенный ненулевой элемент:
      1. Сохранить найденный элемент кластера;
      2. Пометить местоположение в [строке, столбце] как посещенное;
      3. Проверить, не посещен ли- ноль соседей при нахождении в пределах матрицы:
         • [строка-1, столбец-1];
         • [строка-1, столбец];
         • [строка- 1, столбец + 1];
         • [строка, столбец - 1];
         • [строка, столбец + 1];
         • [строка + 1, столбец - 1];
         • [строка + 1, столбец];
         • [строка + 1, столбец + 1].
      4. Если какой-либо сосед не посещенотличные от нуля, повторяйте шаги 1-4 до тех пор, пока все соседи не посетят нули (все члены кластера были найдены).

Answer 5

Если вы знаете количество групп или хотите подогнать данные к статическому количеству групп, вы можете выполнить k-means.

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