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

Question

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

Затем, подумав об этом шаге, я обнаружил, что решение не выпрыгнуло на меня так, как я думал. Теперь я прошу вас, ребята, о помощи У нас есть список точек с такими же массами (список кортежей 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 trees для более быстрого поиска ближайших соседей. Ответ smacl описывает один немного другой способ агломерационной кластеризации с использованием диаграммы Вороного.

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

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

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

Answer 6

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

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