Я немного читаю об алгоритме кластеризации со сдвигом по средним значениям (http://en.wikipedia.org/wiki/Mean_shift), и это то, что я получил до сих пор. Для каждой точки в вашем наборе данных: выберите все точки на определенном расстоянии от нее (включая исходную точку), рассчитайте среднее значение для всех этих точек, повторяйте, пока эти средние значения не стабилизируются.
Что меня смущает, так это то, как отсюда можно решить, что такое конечные кластеры и при каких условиях эти средства сливаются. Кроме того, расстояние, используемое для выбора точек, колеблется в ходе итераций или остается постоянным?
заранее спасибо
Ответ 1 · рейтинг 1 · DrV
Нахождение кластера среднего сдвига - это простой итерационный процесс, который на самом деле гарантированно сходится. Итерация начинается с начальной точки x, и шаги итерации (обратите внимание, что x может иметь несколько компонентов, так как алгоритм будет работать и в более высоких измерениях):
вычислить взвешенное среднее положение x' всех точек вокруг x - возможно, простейшая форма - вычислить среднее значение положений всех точек в пределах d расстояние от x, но функция Гаусса также широко используется и математически выгодна.
установить x ‹- x'
- повторять до тех пор, пока разница между x и x' не станет очень маленькой
Это можно использовать в кластерном анализе, начав с разных значений x. Окончательные значения окажутся в разных центрах кластера. Количество кластеров не может быть известно (кроме того, что ‹= количество точек).
Алгоритм верхнего уровня:
- пройтись по выбору начальных значений
- для каждого значения рассчитайте значение сходимости, как показано выше
- если значение еще не находится в списке значений сходимости, добавьте его в список (допустив некоторую разумную погрешность числовой неточности)
И тогда у вас есть список кластеров. Единственная трудность - найти разумный выбор начальных значений. Это легко с одним или двумя измерениями, но с более высокими размерностями исчерпывающий поиск не совсем возможен.
Все начальные точки, попадающие в один и тот же режим (точки конвергенции), принадлежат одному и тому же кластеру.
Может быть интересно, если вы делаете это на 2D-изображении, этого должно быть достаточно для вычисления градиента (т.е. первой итерации) для каждого пикселя. Это быстрая операция с обычными методами свертки, после чего относительно легко сгруппировать пиксели в кластеры.
