Метод k-средних (k-Means Clustering) – это очень известный и мощный алгоритм Обучения без учителя (Unsupervised Learning), который группирует похожие элементы в k кластеров. Он используется для решения многих сложных задач Машинного обучения (ML).
Пример. Предположим, мы пошли в магазин за овощами и увидели, что они будут расположены на полках по типу. Вся морковь хранится в одном месте, картошка – в другом.
До применения кластеризации (появления окрашенных зон и обозначения записей разными иконками) перепутать категорию довольно легко. Неопытные мерчендайзеры до сих пор кладут арбузы в отдел ягод, хоть и правы с научной точки зрения.
Метод k-средних пытается сгруппировать похожие элементы в три этапа:
- Выберем значение k
- Инициализируем центроиды (разделительные линии)
- Выберем группу и найдем среднее значение расстояния между точками.
Давайте разберемся в вышеуказанных шагах с помощью иллюстраций. Допустим, мы на глаз кластеризовали наблюдения, причислив половину к белой категории, оставшуюся часть – к розовой.
Шаг 1. Мы случайным образом выбираем значение K, равное 2:
Существуют различные методы, с помощью которых мы можем выбрать правильные значения параметра k. Об этом позже.
Шаг 2. Соединим две выбранные максимально удаленные точки, обозначенные белой полупрозрачной обводкой. Теперь, чтобы определить центроид, мы построим перпендикуляр к этой линии:
Если вы заметили, одна белая точка попала в группу розовых, и теперь относится к другой группе, чем предположено изначально.
Шаг 3. Мы соединим две другие удаленные точки, проведем к ним перпендикулярную линию и найдем центроид. Теперь некоторые белые точки преобразуются в розовые:
Этот процесс будет продолжаться до тех пор, пока мы не переберем все возможные сочетания пар дистанцированных точек и не уточним границы кластеров. Стабильность центроидов определяется путем сравнения абсолютного значения среднего Евклидова расстояния (Euclidian Distance) между наблюдениями и их соответствующими центроидами с пороговым значением.
Как выбрать значение k?
Одна из самых сложных задач в этом алгоритме кластеризации – выбрать правильные значения k. Существует два метода.
Метод локтя
Метод локтя (Elbow Rule) – один из самых известных методов, с помощью которого вы можете выбрать правильное значение k и повысить производительность Модели (Model). Этот эмпирический метод вычисляет сумму квадратов расстояний между точками и вычисляет Среднее значение (Mean).
Когда значение k равно 1, сумма квадрата внутри кластера будет большой. По мере увеличения значения k сумма квадратов расстояний внутри кластера будет уменьшаться.
Наконец, мы построим график между значениями k и суммой квадрата внутри кластера, чтобы получить значение k. Мы внимательно рассмотрим график. В какой-то момент значение по оси x резко уменьшится. Эта точка будет считаться оптимальным значением k:
Метод силуэта
Метод силуэта (Silhouette Method) вычисляет среднее расстояние между точками в своем кластере a(i) и среднее расстояние от точек до следующего ближайшего кластера, называемого b(i).
Теперь мы можем вычислить коэффициент силуэта всех точек в кластерах и построить график. Последний также поможет в обнаружении Выбросов (Outlier). Значение метрики силуэта находится в диапазоне от -1 до 1. Обратите внимание, что коэффициент силуэта, равный –1 – это наихудший сценарий. Для картинки выше система вычислила расстояния между всеми точками при различных допущениях о числе кластеров и построила соответствующие горизонтальные гистограммы. Мы выбираем k, равный 3, потому что зеленая гистограмма меньше, хотя стоит, возможно, проверить и бо́льшие значения.
Преимущества K-Means
- Простота реализации
- Масштабируемость до огромных наборов данных
- Метод очень быстро обучается на новых примерах
- Поддержка сложных форм и размеров.
Недостатки K-means
- Чувствительность к выбросам
- Трудоемкость выбора k
- Уменьшение масштабируемости.
K-Means и SciPy
Давайте посмотрим, как метод реализован в SciPy. Для начала импортируем необходимые библиотеки:
Создадим набор из 50 точек с парой координат a и b. Метод multivariate_normal() преобразует случайные значения, сгенерированные random(), в многомерную нормальную случайную величину. Объект features объединяет координаты попарно.
Применим Нормализацию (Normalization) – "отбелим" (whiten) данные, прежде чем отправлять в кластеризующую модель. codebook – массив из k центроидов, подбираемых системой автоматически, и вместе с объектом distortion отправим эти данные в K-Means. Искажение (Distortion) здесь –среднее неквадратичное Евклидово расстояние между пройденными наблюдениями и сгенерированными центроидами:
Отрисуем нормализрованные данные и отметим центры кластера красными точками:
Ноутбук, не требующий дополнительной настройки на момент написания статьи, можно скачать здесь.
Автор оригинальной статьи: ADITYA610
Фото: @robertlukeman
Понравилась статья? Поддержите нас, поделившись статьей в социальных сетях и подписавшись на канал. И попробуйте курс «Введение в Машинное обучение» на Udemy.
