какой алгоритм должен быть выбран для выполнения этой задачи

Question

Привет Я новичок в Cluster , я не знаю, какой алгоритм подходит для моей задачи. позвольте мне описать мою задачу:

1. сначала, учитывая набор точек и их расстояния между ними
2. кластеризация их в несколько кластеров на основе расстояния.
3. будет добавлено несколько новых точек, также будет указано расстояние между всеми точками.
4. повторение 2

например, сначала мы имеем следующую матрицу

   | p1 | p2 | p3 |  
---|----|----|----|  
p1 |    |    |    |  
p2 | d1 |    |    |  
p3 | d2 | d3 |    |  

после кластеризации, мы добавляем новую точку и расстояние также дается:

   | p1 | p2 | p3 | p4 | 
---|----|----|----|----|  
p1 |    |    |    |    |  
p2 | d1 |    |    |    |  
p3 | d2 | d3 |    |    |  
p4 | d4 | d5 | d6 |    |  

Проблема здесь заключается в скорости, я ожидаю, что кластеризация является инкрементным кластером, то есть более поздняя кластеризация может использовать предыдущий результат. Потому что мы будем часто добавлять точки (если найдем одну), и если мы будем кластеризовать точки каждый раз. Даже если у самого кластера есть O (n), общее время кластера будет O (n ^ 2).

Есть предложения?

Спасибо

Answer 1

Один из вариантов - установить количество кластеров (скажем, у вас есть K кластеров).Всякий раз, когда вы добавляете новую точку, вы добавляете ее в кластер, центр тяжести которого (среднее от координат точек в кластере) находится ближе всего к добавленной вами точке.Если вы полностью повторяете кластеризацию, когда число точек в вашем пространстве становится степенью двойки (1, 2, 4, 8, 16, 32 ...), амортизированная стоимость повторного кластеризации по-прежнему составляет O (n).