Как определить окончательные кластеры при использовании алгоритма сдвига средних?

Я немного читаю об алгоритме кластеризации со сдвигом по средним значениям (http://en.wikipedia.org/wiki/Mean_shift), и это то, что я получил до сих пор. Для каждой точки в вашем наборе данных: выберите все точки на определенном расстоянии от нее (включая исходную точку), рассчитайте среднее значение для всех этих точек, повторяйте, пока эти средние значения не стабилизируются.

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

заранее спасибо


cluster-analysis algorithm
person omu_negru    schedule 26.06.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Нахождение кластера среднего сдвига — это простой итерационный процесс, который на самом деле гарантированно сходится. Итерация начинается с начальной точки x, и шаги итерации (обратите внимание, что x может иметь несколько компонентов, так как алгоритм будет работать и в более высоких измерениях):

  • вычислить взвешенное среднее положение x' всех точек вокруг x - возможно, простейшая форма - вычислить среднее значение положений всех точек в пределах d расстояние от x, но функция Гаусса также широко используется и математически выгодна.

  • установить x ‹- x'

  • повторять до тех пор, пока разница между x и x' не станет очень маленькой

Это можно использовать в кластерном анализе, начав с разных значений x. Окончательные значения окажутся в разных центрах кластера. Количество кластеров не может быть известно (кроме того, что ‹= количество точек).

Алгоритм верхнего уровня:

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

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

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

Может быть интересно, если вы делаете это на 2D-изображении, этого должно быть достаточно для вычисления градиента (т.е. первой итерации) для каждого пикселя. Это быстрая операция с обычными методами свертки, после чего относительно легко сгруппировать пиксели в кластеры.

person DrV    schedule 26.06.2014
comment
Это отвечает на вопрос, когда мне остановиться? вопрос, но он не отвечает на вопрос, когда 2 центроида считаются одинаковыми? . Учитывая, что алгоритм указывает, что мы повторяем шаг для каждой точки, и в итоге мы получаем неизвестное количество кластеров, я должен спросить: считается ли конечный кластер набором всех точек, содержащихся внутри центроидов, которые пересекаются друг с другом? Я надеюсь это имеет смысл - person omu_negru; 27.06.2014
comment
@omu_negru: два центроида одинаковы, если они находятся в одном месте. Конечно, должна быть некоторая терпимость к неточности вычислений. Это фаза, на которой значение либо добавляется, либо не добавляется в список. Точка принадлежит кластеру, если алгоритм, запущенный из этой точки, заканчивается в его центроиде. Конечные кластеры представлены списком центроидов, а для каждого центроида списком точек, принадлежащих этому кластеру. - person DrV; 27.06.2014