Это звучит как тривиальная проблема, но я не мог ничего найти в Интернете.
У нас есть набор элементов 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
.
Этот алгоритм (кластеризация + расширение) будет работать на одном узле, затем большая часть данных будет объединена и обработана в распределенной системе.
мы также можем запустить это параллельно - если есть такой алгоритм - конечно, параллельные алгоритмы более сложны. Я хотел сказать, что хотя сами элементы могут быть большими, информация о попарных расстояниях не такая уж большая и поместится в память одной машины.
На первом этапе можно протестировать простой жадный алгоритм.
У меня такое ощущение, что логичнее определить перекрывающиеся (расширенные) множества, а затем определить нерасширенные.
Выберем K (= M ?) точек как можно дальше от всех остальных.
Здесь я предполагаю, что выбор таких экстремальных точек возможен, 1
и 6
в вашем примере.
Обратите внимание, что начальное количество точек может быть меньше, чем M.
Вариант состоит в том, чтобы продолжать процесс до тех пор, пока в каждом наборе не будет требуемого количества удовлетворенных точек.
Каждый случайный процесс может дать другое решение. Несколько попыток могут выполняться параллельно на разных узлах.
В вашем простом примере процесс немедленно предоставляет решение:
Может случиться так, что два разных набора имеют одну и ту же точку довольный. Даже если эта точка должна оставаться в каждом расширенном наборе, ее можно удалить из одного из нерасширенных наборов.
Одно обоснование этого алгоритма: я считаю само собой разумеющимся, что крайние точки должны находиться в разных нерасширенных множествах. Это означает, что их соседи должны присутствовать в соответствующем расширенном множестве Si.
хорошо, я очень ценю усилия, но я надеялся на "нестандартное" решение. Кроме того I assume here that selecting such extremal points is feasible
- ну, не в общем случае - как я уже сказал - расстояния определяются "попарно", поэтому проекция не обязательно доступна. Вы говорите о стохастическом подходе, и он может быть быстрым, но его трудно отлаживать! Но, в конце концов, я, вероятно, сделаю именно то, что вы предложили (выбор случайных точек в начале тоже сработает!). Сейчас не соглашусь, может кто подскажет что попроще.
Я приму ваши ответы - похоже, других желающих нет - большое спасибо, что уделили время и написали для меня подробный алгоритм! :)
Спасибо. Надеюсь, это даст хорошие результаты. Не стесняйтесь задавать вопросы или упоминать некоторые проблемы с ним. Как правило, с такими проблемами мы реализуем первый алгоритм, а затем анализ результатов дает подсказки для его улучшения. Я согласен, что решение нестандартный было бы лучше, но...
Если кластеризация выполняется на одном узле, я думаю, это означает, что алгоритм не может быть слишком сложным.