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

Question

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

В моем случае средний вес ячеек, не содержащих кластер, составляет около 6, а у ячеек, содержащих кластер, около 6 + 4, т. Е. Где-то около 6 есть «фоновый вес». Веса колеблются в зависимости от Пуассоновская статистика.

Для небольших фоновых алгоритмов жадные алгоритмы или затравочные алгоритмы работают довольно хорошо, но это ломается, если у моих кластерных ячеек есть веса, близкие к флуктуациям на заднем плане, то есть они будут стремиться найти кластер, даже если там ничего нет. Кроме того, я не могу выполнить поиск методом перебора всех возможных настроек, потому что моя сетка большая (что-то вроде 1000x1000), и я планирую делать это очень часто (10 ^ 9 раз). У меня сложилось впечатление, что могут существовать способы решения этой проблемы в теории графов. Я слышал о покрытиях вершин и кликах, но не уверен, как лучше всего перевести мою проблему на их язык . Я знаю, что у теории графов могут быть проблемы со статистической природой входных данных, но мне было бы интересно посмотреть, какие алгоритмы там можно найти, даже если они не могут идентифицировать каждый кластер.

Вот пример отсечения: в рамочной области в среднем по 10 записей на ячейку, во всех остальных ячейках - в среднем 6. Конечно, сетка расширяется.

| 8|  8|  2|  8|  2|  3| 
| 6|  4|  3|  6|  4|  4| 
        ===========
| 8|  3||13|  7| 11|| 7|
|10|  4||10| 12|  3|| 2|
| 5|  6||11|  6|  8||12|
        ===========
| 9|  4|  0|  2|  8|  7|

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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