В этой серии я собираюсь объяснить наиболее распространенные алгоритмы машинного обучения, начиная с основ и заканчивая гораздо более сложными.
Это вторая часть этой серии, и если вы не читали предыдущую о модели KNN, которая очень похожа на эту, нажмите здесь, чтобы ознакомиться с ней:
Модель K-средних — это неконтролируемая модель, которая группирует наш набор данных по разным категориям. Другими словами, мы используем эту модель, когда у нас нет заранее известной метки для каждой точки данных, но мы хотим создать некоторые категории.
Данные
Нам нужен наш набор данных. Для этого демонстрационного сеанса я буду генерировать случайный набор данных с двумя переменными (для хорошей подгонки к 2D-диаграмме рассеяния), но применимо любое количество измерений. Как и модель KNN, эта также непараметрическая, поэтому нам не нужно «подгонять» нашу модель, вместо этого мы используем весь набор данных каждый раз, когда собираемся вычислять кластеры. Это также означает, что время расчета сильно зависит от размера нашего набора данных, и мы также должны убедиться, что весь набор данных может быть загружен в память.
На рисунке видно, что наши данные очень разбросаны, и наша цель — найти 2 (или более) группы, которые хорошо отделяют их друг от друга.
Модель
Подгонка нашей модели основана на нахождении «K» числа кластерных центров (так называемых центроидов), что идеально распределяет каждую точку данных в одну из «K» категорий. Итак, теперь нам нужно определить некоторые термины: сколько кластеров «K» мне следует использовать? Как расположить эти центроиды для достижения наилучших результатов? Как пометить точки данных на основе центроидов? Давайте рассмотрим каждый шаг за шагом.
Сначала мы размещаем наши кластеры случайным образом (на данный момент мы собираемся использовать 2 центроида), вычисляем расстояние каждой точки данных относительно каждого центроида и назначаем ближайшему из них. На картинке ниже мы видим, что наши два случайных центроида выделены «красным», и каждая точка данных распределена в зависимости от расстояния.
Первый центроид случайным образом размещается поверх точки данных, а следующий центроид размещается поверх самой дальней точки данных. Это одна из наиболее распространенных отправных точек, но существует несколько других методов, некоторые из них используют фактические точки данных в качестве начальных центроидов, а другие вычисляют синтетические центры кластеров.
Назначение каждой точки данных основано на расстоянии. Расстояние можно рассчитать разными способами, но формулы такие же, как мы видели в модели KNN:
- Евклидово: Сумма[(xi-yi)^2]^1/2
- Манхэттен: Сумма(|xi-yi|)
- Минковский: Sum(|xi-yi|^c)^1/c → равно евклидову, если c=2, и Манхэттену, если c=1
где xi-yi — различия в каждом измерении точки данных x и центра тяжести y.
Мы можем ясно видеть, что приведенная выше кластеризация далека от оптимальной, поскольку «зеленая» группа намного больше, чем «оранжевая». Очевидно, что мы должны сместить центроид из правого верхнего угла внутрь, но как узнать насколько? Или, другими словами, как определить, насколько хороша наша модель, и как сравнить две разные ситуации друг с другом? В модели K-средних функция «потери» обычно рассчитывается как сумма квадратов остатков (SSE) каждой точки данных по отношению к ее центру кластера. Чем меньше sse, тем лучше приспособлена наша модель. Таким образом, мы должны сначала вычислить сумму ошибок каждой группы, поэтому у нас есть эталонное число. Математики говорят, что это будет наименьшим, если центроиды равны среднему значению группы. В нашем случае SSE составляет 1506,4 и 70,1 для двух кластеров, а средние значения: (4,14, 2,33) и (7,06, 5,85).
На рисунке выше мы видим новую настройку, в которой центры кластеров выбираются с помощью средних, рассчитанных на предыдущем шаге. Декорации начинают выглядеть немного более оптимизированными, так как вес каждой группы нормализуется, но «зеленая» группа все еще намного больше. Кроме того, если мы пересчитаем SSE, который на этот раз равен 1218,8 и 197,7, мы увидим, что ошибка «зеленой» группы действительно немного уменьшилась, а ошибка «оранжевой» выросла. Это не проблема, так как общий SSE также снизился с прежних 1576,5 до 1416,4. Кроме того, если мы пересчитаем средние значения, мы увидим, что центры кластеров все еще не равны средним значениям. Это потому, что по мере того, как мы смещали центры, менялась и группа, а также менялись и средства. Теперь мы видим, что это итеративная задача, которую мы можем повторять столько раз, сколько захотим.
В общем случае итерации могут закончиться в одном из 3-х обстоятельств:
- Группы не меняются при перемещении центров кластеров: это означает, что центры кластеров являются средними для групп, и мы достигли (локального) минимума, что может быть лучшим решением.
- SSE улучшается меньше, чем предопределенное значение «допуска»: модель начала улучшаться на незначительном уровне с каждым шагом, поэтому, возможно, лучше остановиться на этом. Это значение должно быть установлено на очень низкое число для высокой точности.
- Количество итераций достигает предопределенного числа «max_iteration»: это наихудший случай, так как можно улучшить гораздо больше, поэтому лучше всего установить действительно большое число. Это полезно только в тех случаях, когда SSE не сходится.
На рисунке выше мы видим, что наш набор данных подходит, пока мы не нашли лучший сценарий на основе SSE. Наш общий SSE уменьшился до 1367,2, а центры кластеров равны средним. Кроме того, визуально он гораздо более оптимален, так как действительно разделил набор данных на две четко различимые группы.
Итак, мы увидели, как разделить наши данные на две категории, но мы все еще не знаем, должны ли мы искать 3, 4 или даже больше групп. Если мы рассматриваем минимизацию SSE в качестве нашей цели, легко согласиться с тем, что, увеличив «K», мы можем еще больше минимизировать SSE. Фактически 0 SSE достигается, если «K» равно количеству точек данных или, другими словами, каждая точка данных сгруппирована в свой собственный кластер. Конечно, это означало бы отсутствие дополнительной информации в нашем наборе данных, даже в этом случае, чем меньше «К», тем лучше мы можем интерпретировать результаты. Таким образом, мы должны найти оптимальный баланс между сохранением низкого «K» и максимально возможной минимизацией «SSE».
Мы можем проверить значение оптимизированного SSE по каждому «K» и построить результаты:
SSE быстро снижается в начале, но потом очень быстро замедляется. Существует так называемый «метод локтя», в котором мы находим «локоть» нашей фигуры или точку, в которой SSE уменьшается значительно медленнее. В этом примере локоть может быть под номером 5 (или может быть под номером 3, в зависимости от предпочтений).
Давайте посмотрим, как наш набор данных полностью оснащен параметром «K», равным 5:
На этот раз общий SSE составляет 364,9, поэтому мы видим, что можем значительно уменьшиться по сравнению с нашей двухкластерной моделью, но набор данных становится слишком подробным.
