Перевод задачи кластеризации на язык теории графов

Для решений теории графов есть пара предложений в Википедии, но вы вероятно, лучшая публикация на MathOverflow. Этот вопрос также может быть полезен.

Традиционный метод (и, вероятно, лучший, учитывая его повсеместное распространение) в вычислительной технике для решения этих проблем — растровый анализ — хорошо известный в мире ГИС и дистанционного зондирования, поэтому существует ряд инструментов, обеспечивающих реализацию. Ключевые слова, которые можно использовать для поиска наиболее подходящего для вашей задачи, — это растр, ближайший сосед, передискретизация и кластеризация. Библиотека GDAL часто является основой для других инструментов.

Например. http://clusterville.org/spatialtools/index.html

Вы можете попробовать проверить библиотеку GDAL и исходный код, чтобы увидеть, можете ли вы использовать ее в своей ситуации, или посмотреть, как она реализована.

Для проверки круглых форм вы можете преобразовать оставшиеся значения в многоугольники и проверить результирующую функцию.

http://www.gdal.org/gdal_polygonize.html

Я не уверен, что вижу аналогию с теорией графов, но вы можете ускорить процесс, предварительно вычислив интеграл площади. Это похоже на многомасштабную вещь.

A[i,j] = Sum[Sum[p[u,v], {u, 0, i}, {v, 0, j}]];

Тогда средняя яркость прямоугольной (а, б), (в, г) области равна

(A[c,d] - (A[c,b] + A[a,d]) + A[a,b])/((c-a)(d-b))

Переполнение, вероятно, не ваш друг, если у вас есть большие числа в ваших ячейках.

Использовать алгоритм поиска объединения для кластеризации? Это очень быстро.

Я предполагаю, что граф будет получен в результате рассмотрения каждой пары соседних ячеек с высоким значением, связанных. Используйте алгоритм объединения-поиска, чтобы найти все кластеры и принять все те, которые больше определенного размера, возможно, также с ограничениями формы (например, на основе среднего квадрата расстояния от центра кластера по сравнению с размером кластера). Это тривиальная вариация алгоритма объединения-поиска для сбора статистики, которая вам понадобится для этого, по мере продвижения (счетчик, сумма x, сумма x^2, сумма y, сумма y^2).

Если вы просто ищете способ перевести свою проблему в графическую задачу, вот что вы можете сделать.

Из каждой точки посмотрите на всех своих соседей (это могут быть 8 соседних квадратов или 4 соседних, в зависимости от того, что вы хотите). Ищите соседа с максимальным значением, если он больше вашего, то подключайтесь к этому квадрату. если он меньше, то ничего не делать.

после этого у вас будет лес или, возможно, дерево (хотя я думаю, что это маловероятно). Это один из возможных переводов вашей матрицы на график. Я не уверен, что это самый полезный перевод.