Что такое кластеризация K-средних?

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

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

Определение кластеризации

Прежде чем мы рассмотрим точные алгоритмы, используемые для кластеризации K-средних, давайте уделим немного времени определению кластеризации в целом.

Кластеры — это просто группы элементов, а кластеризация — это просто объединение элементов в эти группы. В смысле науки о данных, алгоритмы кластеризации стремитесь сделать две вещи:

• Убедитесь, что все точки данных в кластере максимально похожи друг на друга.
• Убедитесь, что все точки данных в разных кластерах максимально отличаются друг от друга.

Алгоритмы кластеризации группируют элементы вместе на основе некоторой метрики сходства. Это часто делается путем нахождения «центроида» различных возможных групп в наборе данных, хотя и не исключительно. Существует множество различных алгоритмов кластеризации, но цель всех алгоритмов кластеризации одна и та же — определить группы, присущие набору данных.

Кластеризация K-сред

Кластеризация K-средних — один из старейших и наиболее часто используемых типов алгоритмов кластеризации, работающий на основе векторное квантование. В качестве исходной точки выбрана точка в пространстве, а затем от исходной точки рисуются векторы ко всем точкам данных в наборе данных.

В целом, кластеризацию K-средних можно разбить на пять различных этапов:

• Поместите все экземпляры в подмножества, где количество подмножеств равно K.
• Найдите среднюю точку/центроид только что созданных разделов кластера.
• На основе этих центроидов назначьте каждую точку определенному кластеру.
• Вычислите расстояния от каждой точки до центроидов и назначьте точки кластерам, где расстояние от центроида минимально.
• После того, как точки были назначены кластерам, найдите новый центр тяжести кластеров.

Вышеуказанные шаги повторяются до тех пор, пока процесс обучения не будет завершен.

На начальном этапе центроиды размещаются где-то среди точек данных.
Фото: Weston.pace через wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

В качестве альтернативы, после того, как центроиды были размещены, мы можем представить себе кластеризацию K-средних как переключение между двумя разными фазами: маркировка точек данных и обновление центроидов.

На втором этапе используется метрика расстояния, например, евклидово расстояние, для вычисления ближайшего к заданной точке центроида, после чего точкам присваивается класс этого центроида. Фото: Weston.pace через Wikimedia Commons, лицензия GNU Free Doc (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

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

На третьем этапе центроиды перемещаются в среднее значение всех точек данных. Затем классы перераспределяются. Фото: Weston.pace через Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

На этапе обновления центроида центроид вычисляется путем нахождения среднего расстояния между всеми точками данных, которые в настоящее время содержатся в кластере.

Как выбрать правильное значение для «К»

Учитывая, что кластеризация K-средних — это неконтролируемый алгоритм, а количество классов заранее неизвестно, как выбрать подходящее количество классов/правильное значение для K?

Один из методов выбора правильного значения K называется «техника локтя». Метод локтя состоит из запуска алгоритма кластеризации K-средних для диапазона различных значений K и использования метрики точности, обычно суммы квадратов ошибок, для определения того, какие значения K дают наилучшие результаты. Сумма квадратов ошибок определяется путем вычисления среднего расстояния между центром тяжести кластера и точками данных в этом кластере.

Термин «метод локтя» происходит от того факта, что когда вы строите SSE относительно различных значений K, результирующий линейный график часто будет иметь форму «локтя», где SSE быстро уменьшается для первых нескольких значений K, но потом выравнивается. В таких условиях значение К, расположенное на изгибе, является лучшим значением К, так как после этого значения происходит быстрое уменьшение отдачи.

Мини-пакетная кластеризация K-средних

По мере того, как наборы данных становятся больше, время вычислений также увеличивается. Базовая кластеризация K-средних может занять много времени при работе с массивными наборами данных, и в результате были внесены изменения в кластеризацию K-средних, чтобы уменьшить пространственные и временные затраты алгоритма.

Мини-пакетная кластеризация K-средних является вариантом кластеризации K-средних где размер рассматриваемого набора данных ограничен. Обычная кластеризация K-средних работает сразу со всем набором данных/пакетом, в то время как мини-пакетная кластеризация K-средних разбивает набор данных на подмножества. Мини-партии случайным образом выбираются из всего набора данных, и для каждой новой итерации выбирается новая случайная выборка, которая используется для обновления положения центроидов.

В мини-пакетной кластеризации K-средних кластеры обновляются с помощью комбинации значений мини-пакета и скорости обучения. Скорость обучения уменьшается по мере итераций, и она обратно пропорциональна количеству точек данных, помещенных в конкретный кластер. Эффект снижения скорости обучения заключается в том, что снижается влияние новых данных и достигается сходимость, когда после нескольких итераций в кластерах нет изменений.

Результаты исследований эффективности мини-пакетной кластеризации K-средних показывают, что она может успешно сократить время вычислений с небольшим компромиссом в качестве кластера.

Приложения кластеризации K-средних

Кластеризацию K-средних можно безопасно использовать в любой ситуации, когда точки данных можно сегментировать на отдельные группы/классы. Вот несколько примеров распространенных вариантов использования кластеризации K-mean.

Кластеризация K-средних может применяться для классификации документов, группировки документов на основе таких функций, как темы, теги, использование слов, метаданные и другие функции документа. Его также можно использовать для классификации пользователей как ботов или не ботов на основе моделей активности, таких как сообщения и комментарии. Кластеризация K-средних также может использоваться для разделения людей на группы в зависимости от уровня беспокойства при наблюдении за их здоровьем, на основе таких характеристик, как сопутствующие заболевания, возраст, история болезни и т. д.

Кластеризация K-средних также может использоваться для более открытых задач, таких как создание систем рекомендаций. Пользователи такой системы, как Netflix, могут быть сгруппированы на основе шаблонов просмотра и рекомендованного похожего контента. Кластеризация K-средних может использоваться для задач обнаружения аномалий, выделяя потенциальные случаи мошенничества или дефектные элементы.