Алгоритм кластеризации и «расширение» кластеров для включения N ближайших соседей

Это звучит как тривиальная проблема, но я не мог ничего найти в Интернете.

У нас есть набор элементов a b c d e. Для этих элементов определены попарные расстояния. Каждый элемент требует обработки. Для обработки элемента необходимо N его ближайших соседей.

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

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

Вот пример:

We have following elements, the distance between them is just their difference.

N = 4 # number of nearest neighbours required for the computation
M = 2 # desired number of clusters

elements:
  1 2 3 4 5 6

basic clusters:
  1 2 3
  4 5 6

extended clusters:
  1 2 3 (4 5)
  4 5 6 (2 3)

Как это называется, есть ли какой-то общий подход к такой проблеме? Насколько я понимаю, это не строго clustering.

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

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

Damien 14.05.2019 16:18

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

avloss 14.05.2019 16:37
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
2
50
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

На первом этапе можно протестировать простой жадный алгоритм.

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

Выберем K (= M ?) точек как можно дальше от всех остальных.
Здесь я предполагаю, что выбор таких экстремальных точек возможен, 1 и 6 в вашем примере.
Обратите внимание, что начальное количество точек может быть меньше, чем M.

  1. Эти начальные точки Pi определяют K множеств Si.
  2. Затем каждый Si дополняется нужными соседями Pi.
  3. Для каждого набора мы можем определить количество точек, у которых достаточно соседей.
  4. Если K < M, мы можем определить точки M-K, насколько это возможно, из предыдущих множеств и составить новые множества с этими точками и их соседями.
  5. если все точки находятся в множестве со всеми своими соседями: СТОП.
  6. Выберите набор с наименьшим количеством точек довольный, т.е. со всеми их соседями. В этом наборе определите точки с наименьшим количеством отсутствующих соседей. Выбрать случайным образом такую ​​точку и дополнить набор недостающими соседями этой точки
  7. перейти к шагу 3, пока критерии остановки не будут удовлетворены.

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

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

В вашем простом примере процесс немедленно предоставляет решение:

  • S0 = {1} -> S0 = {1, 2, 3, 4, 5}
  • S1 = {6} -> S1 = {6, 5, 4, 3, 2}

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

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

хорошо, я очень ценю усилия, но я надеялся на "нестандартное" решение. Кроме того I assume here that selecting such extremal points is feasible - ну, не в общем случае - как я уже сказал - расстояния определяются "попарно", поэтому проекция не обязательно доступна. Вы говорите о стохастическом подходе, и он может быть быстрым, но его трудно отлаживать! Но, в конце концов, я, вероятно, сделаю именно то, что вы предложили (выбор случайных точек в начале тоже сработает!). Сейчас не соглашусь, может кто подскажет что попроще.

avloss 14.05.2019 21:45

Я приму ваши ответы - похоже, других желающих нет - большое спасибо, что уделили время и написали для меня подробный алгоритм! :)

avloss 15.05.2019 11:05

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

Damien 15.05.2019 11:18

Другие вопросы по теме