Фильтрация близлежащих точек из списка

Question

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

Затем, подумав об этом шаге, я обнаружил, что решение не выскочило на меня так, как я думал. Так что теперь я прошу вас, ребята, о помощи. У нас есть список точек с такими массами (список кортежей Python, но вы можете представить его так, как считаете нужным на любом языке):

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

Каждый кортеж имеет форму:

(x, y, mass)

Обратите внимание, что список отсортирован здесь. Если ваше решение предпочитает не сортировать их, это нормально.

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

Когда я попробовал это, мне пришлось снова и снова просматривать части списка. У меня такое чувство, что я просто глуп по этому поводу. Как бы вы это сделали? Псевдокод или реальный код. Конечно, если вы можете просто взять то, что я оставил в этом ответе с кодом Python, мне будет проще с ним поэкспериментировать.

Следующий шаг - выяснить, сколько кластеров действительно имеется в растровом изображении. Я все еще пытаюсь определить эту проблему, поэтому могу вернуться с вопросом об этом.

РЕДАКТИРОВАТЬ: я должен уточнить, что я знаю, что нет " правильного " ответ на этот вопрос. И название вопроса является ключевым. Первый этап моей кластеризации завершен. Я нахожусь в поисках быстрого, точного " достаточно " метод фильтрации соседних точек.

Дайте мне знать, если вы поймете, как я могу прояснить вопрос.

Answer 1

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

Как отметил Арахнид, алгоритм k-means имеет тенденцию быть хорошим и это довольно легко реализовать. Результаты критически зависят от первоначального предположения и количества желаемых кластеров. Чтобы преодолеть начальную проблему с угадыванием, обычно многократно запускают алгоритм со случайной инициализацией и выбирают лучший результат. Вам нужно будет определить, какой " лучший " средства. Одним из показателей будет среднеквадратичное расстояние каждой точки до центра кластера. Если вы хотите автоматически угадать, сколько кластеров существует, вы должны запустить алгоритм с целым диапазоном чисел кластеров. Для любого хорошего "лучшего" мера, больше кластеров всегда будет выглядеть лучше, чем меньше, поэтому вам понадобится способ наказать слишком много кластеров. MDL обсуждение Википедии является хорошей отправной точкой.

Кластеризация K-средних - это, по сути, самая простая модель смеси . Иногда полезно перейти на смесь гауссиан, изученных путем максимизации ожидания (описано в только что приведенной ссылке). Это может быть более надежным, чем k-средних. Требуется немного больше усилий, чтобы понять это, но когда вы это делаете, это не намного сложнее, чем k-средних для реализации.

Существует множество других методов кластеризации , таких как агломерационная кластеризация и спектральная кластеризация. Агломеративная кластеризация довольно проста в реализации, но выбор момента прекращения создания кластеров может быть сложным. Если вы выполняете агломерационную кластеризацию, вы, вероятно, захотите посмотреть kd-деревья , чтобы быстрее поиск ближайшего соседа Ответ smacl описывает один немного другой способ создания агломерационной кластеризации с использованием диаграммы Вороного.

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

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

Answer 2

Мне кажется, что вы ищете алгоритм K-means .

Answer 3

Как я уже упоминал в комментарии к вашему вопросу, ответ основан на том, может ли масса считаться скалярной в этом контексте. Если это так, решения на основе цвета, вероятно, не будут работать, поскольку цвет часто не считается скалярным.

Например, если у меня есть заданная область с 1 точкой большой массы, это то же самое, что иметь ту же область с 10 точками 1/10 массы? Если это так, то масса не скалярна в этом контексте, и я хотел бы взглянуть на алгоритм, используемый для пространственной группировки аналогичных немасштабируемых значений, например, диаграммы вороной .

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

Если, с другой стороны, ваша масса является масштабируемой или что масса в неизвестном месте может быть интерполирована из окружающих точек, я бы склонился triangulate и контурные входные данные и использование областей между контурами, чтобы найти кластеры с одинаковой массой.

Answer 4

Это похоже на квантование цветов, когда вы уменьшаете количество цветов в изображении. Один из способов - построить цвета в пространстве и объединить кластеры в центр (или средневзвешенное значение) кластера.

Точное название алгоритма, вызвавшего эту память, меня не устраивает, но я отредактирую ответ, если он появится, но пока вам следует взглянуть на цветовое квантование и посмотреть, полезны ли некоторые алгоритмы.

Answer 5

Начните с " выпуклой оболочки " проблема. Вы также ищете некоторые кластеры, похожие на выпуклую оболочку.

Обратите внимание, что " кластеры " расплывчато У вас есть средняя масса по полю. Некоторые точки имеют массу выше средней, а некоторые - ниже средней. Насколько выше среднего означает, что вы нашли кластер? Как далеко друг от друга должны быть узлы, чтобы быть частью кластера или отдельного кластера?

В чем разница между двумя горными вершинами и горным хребтом?

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

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

Answer 6

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

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