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

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

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

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

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

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

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

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

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

Кластеризация K-Means – это один из самых старых и наиболее часто используемых типов алгоритмов кластеризации, и он работает на основе квантования векторов. Есть точка в пространстве, выбранная в качестве начала, и затем векторы рисуются из начала ко всем данным точкам в наборе данных.

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

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

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

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

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

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

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

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

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

Как выбрать правильное значение для “K”

Учитывая, что кластеризация K-Means – это алгоритм непervised обучения, и количество классов не известно заранее, как вы решаете, какое количество классов/правильное значение для K?

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

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

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

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

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

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

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

Применения кластеризации K-Means

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

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

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