Mean Shift в компьютерном зрении и K-Means в машинном обучении
Во время моего 14-дневного карантинного периода, когда я возвращался из Нью-Йорка на Тайвань, свободное время я тратил на проект по компьютерному зрению. В поисках отслеживания объектов я обнаружил, что алгоритм кластеризации Mean Shift очень похож на кластеризацию K-Means, которой обучают в машинном обучении.
Прежде чем погрузиться в мир компьютерного зрения, давайте рассмотрим содержание кластеризации K-средних. Так что же такое кластеризация K-средних?
Кластеризация методом K-средних — это обучение без учителя в классификации двух других популярных алгоритмов кластеризации: иерархический кластерный анализ и смешанные модели Гаусса. Определение кластеризации может быть нечетким, поскольку кластеры имеют объекты, которые «в чем-то похожи». Давайте остановимся на некоторое время, как мы рассчитываем расстояние между различными точками данных? Евклидово расстояние! И это математика, используемая в алгоритме иерархического кластера.
Для кластеризации K-средних первым шагом является выбор входного параметра k (ядро), что означает, что мы хотим идентифицировать k кластеров. Далее мы случайным образом выберем k точек данных в качестве начальных точек. А затем мы измерили расстояние между 1-й точкой и k начальными кластерами и присвоили 1-ю точку ближайшему кластеру. После того, как все точки окрашены в кластер, мы вычисляем среднее значение каждого кластера. А как определить число «k»? мы можем использовать «график локтя», чтобы определить, что количество кластеров (k) имеет огромное сокращение, и после этого числа k изменение не уменьшается так быстро [рисунок 2].
Что касается алгоритма среднего сдвига, он также использует метод извлечения информации из точки данных с операцией среднего вектора, что похоже на кластеризацию K-средних. В Mean Shift все данные являются центром кластера, и он работает, обновляя кандидатов на центроиды, чтобы они были средним значением точек. И на основе ядра точка переместится в место с наибольшей плотностью. Делая это для кластеризации или отслеживания.
Давайте разберем шаги.
1-й: Направление к центроиду ближайшего кластера определяется тем, где находится большинство ближайших точек.
2-й: Таким образом, с каждой итерацией каждая синяя точка будет приближаться к тому месту, где находится наибольшее количество точек, что является или приведет к центру кластера.
3-й: красные и синие точки данных полностью перекрываются в первой итерации до запуска алгоритма среднего сдвига.
В конце итерации 1 все синие точки перемещаются к кластерам. Вот видимо будет либо 3 либо 4 кластера
Подводя итог, сложность для среднего сдвига составляет O (kN²), а для K-Means — только O (kN), здесь k означает количество шагов итерации, а N — количество точек данных. Поскольку средний сдвиг имеет дело с евклидовым расстоянием, он стал более сложным и требует много времени, если набор данных огромен. Что касается ограничений, некоторые выбросы не могут быть правильно идентифицированы как шум, тогда как K-Means часто требует, чтобы количество кластеров было предварительно определено.
- Ссылка -
- Визуализация кластеризации K-средних. https://stanford.edu/class/engr108/visualizations/kmeans/kmeans.html
- StatQuest: кластеризация K-средних. https://www.youtube.com/watch?v=4b5d3muPQmA&t=376s
- О среднем сдвиге и кластеризации K-средних. http://jamesxli.blogspot.com/2012/03/on-mean-shift-and-k-means-clustering.html#:~:text=Mean%20shift%20and%20K%2DMeans%20algorithm%20are% 20two%20similar%20кластеризация (например,%20for%20image%20сегментация.)
- Python для компьютерного зрения с OpenCV и глубоким обучением. https://www.udemy.com/course/python-for-computer-vision-with-opencv-and-deep-learning/
