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

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

0 голосов
/ 14 мая 2019

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

У нас есть набор элементов 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.

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

1 Ответ

1 голос
/ 14 мая 2019

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

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

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

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

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

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

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

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

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

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

...