Одна остановка для кластеризации методом K-средних

Оптимизация кластеризации методом K-средних на одной платформе

Как объединить похожие точки данных так, чтобы это имело смысл? Ну, K-средних – это один из ответов. В этой статье вы найдете практически все о кластеризации K-средних. Ну, сказано это, я не писала код 🙂

ОПИСАНИЕ —

  1. Что такое кластеризация K-средних
  2. Свойства кластеров
  3. Алгоритм кластеризации K-средних
  4. Критерий сходимости/остановки
  5. Инициализация центроидов: K-средних++
  6. Выбор оптимального K
  7. Оценка качества кластеров

~Птицы одного пера летят вместе

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

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

Простыми словами, K-средних почти похож на KNN, где мы смотрим на K-ближайших точек для определения сходства. В кластеризации K-средних мы образуем K кластеров таким образом, чтобы точки внутри кластера были похожи и имели общие характеристики. На диаграмме ниже это станет яснее:

Идеальная кластеризация с 5 кластерами

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

Применения кластеризации —

1. Сегментация клиентов2. Сегментация документов3. Сегментация изображений4. Системы рекомендаций и т. д.

2. Свойства кластеров

Теперь у этих кластеров есть определенные свойства, благодаря которым они приобретают смысл.

  1. Все точки данных внутри кластера должны быть максимально похожи — Точки данных внутри кластера очень близки друг к другу. Это означает, что в пространстве признаков точки данных представляют подобные характеристики. Кроме того, более похожие точки будут лучше объединяться в кластеры. Поэтому точки внутри кластера должны быть максимально похожи, чтобы кластер имел смысл.
  2. Точки данных из разных кластеров должны быть максимально различны — Точки данных из разных кластеров находятся далеко друг от друга. Это означает, что в пространстве признаков эти точки представляют очень разные характеристики. Более того, разные точки никогда не будут образовывать кластеры. Поэтому точки из разных кластеров должны быть максимально различны, чтобы кластеры имели смысл.
  3. У каждого кластера есть центроид — У каждого образованного нами кластера есть центроид, вокруг которого сгруппированы все точки. Этот центроид – это точка, которая помогает нам формировать кластеры и регулируется на основе среднего значения точек внутри кластера.

~Ну, так не заморачивайтесь слишком насчет свойств, это просто скучная теория. Смешная часть начинается дальше

3. Алгоритм для кластеризации

Здесь мы погружаемся в то, как этот алгоритм генерирует красивые кластеры.

Алго —

  • [Шаг 1] — Выбрать количество кластеров, которое мы хотим (K) — В данный момент это может быть выбрано произвольно, так как мы позже решим, как выбрать значение K. Случайное значение K=3 наиболее часто выбирается для запуска алгоритма.
  • [Шаг 2] — Выбрать K случайных точек как K-центроиды — Эти точки также выбираются случайным образом для формирования центроидов для каждого кластера. Эти точки могут быть выбраны случайно из наших данных или откуда-либо еще.
  • [Шаг 3] — Присвоить каждой точке данных ближайший центроид — Затем мы вычисляем расстояние от каждой точки в нашем наборе данных до всех K-центроидов. Точка присваивается тому центроиду, у которого наименьшее расстояние от этого центроида. Это можно визуализировать, как показано ниже:

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

  • [Шаг 4] — Вычислить новые центроиды — После присвоения каждой точки одному из других центроидов мы вычисляем новые центроиды для каждого кластера, взяв среднее значение всех точек в каждом кластере. Новые центроиды могут быть вычислены путем нахождения среднего значения по x-координатам и y-координатам всех точек данных отдельно.

Здесь ‘m’ – количество точек данных в конкретном кластере.

  • [Шаг 5] — Повторить шаги 3 и 4, пока не достигнута сходимость/условие остановки.

Давайте визуализируем:

1. [Шаг 1] — Предположим, мы выбираем k = 22. [Шаг 2] —

Выбор 2 случайных центроидов

3. [Шаг 3] —

Присвоение точек ближайшему центроиду

4. [Шаг 4] —

Вычисление новых центроидов

5. [Шаг 5] —

Вычисление новых центроидов
Сходимость - идеальные кластеры

4. Сходимость/Условие остановки

Вышеприведенный алгоритм, если не сошелся, будет повторяться бесконечно. Поэтому нам нужны некоторые критерии остановки для данного алгоритма. Их несколько:

  1. Заданные точки данных в определенном кластере остаются такими же – Мы выполняем алгоритм до тех пор, пока точки данных не назначаются новым кластерам. Это очень медленно и может занять много времени.
  2. Центроиды остаются такими же – Мы выполняем алгоритм до тех пор, пока новые рассчитанные центроиды совпадают с предыдущими. Это очень медленно и может занять много времени.
  3. Расстояние от точек данных до центроида минимально – Мы устанавливаем порог для расстояния от точек данных до центроида. Когда этот порог достигается, алгоритм останавливается. Это быстро, но нужно очень тщательно выбирать порог расстояния.
  4. Достигнуто фиксированное количество итераций – Мы устанавливаем порог для количества итераций и прекращаем выполнение, когда этот порог достигается. Это быстро, но неправильная установка порога может привести к неправильному формированию кластеров.

Мы можем реализовать эти критерии остановки в нашем алгоритме для раннего схождения и правильной кластеризации.

5. Начальная инициализация центроидов

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

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

Оба этих проблемы можно визуализировать на следующей диаграмме:

Плохая кластеризация
Идеальная кластеризация

Поэтому нам нужен лучший способ начальной инициализации центроидов. Мы можем использовать один из двух упомянутых подходов:

  1. Повторяем K-Means несколько раз, пока не получим лучшие кластеры
  2. Используем алгоритм K-Means ++

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

K-Means ++

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

Алгоритм —

  1. Выбрать первый центроид случайным образом
  2. Теперь вычислите расстояние от каждой точки до ближайшего центроида (первый центроид в начале алгоритма)
  3. Теперь присвойте каждой точке значение вероятности. Значения вероятности пропорциональны расстоянию от точки до предыдущего центроида. Это означает, что точка, имеющая наибольшее расстояние от центроида, будет иметь наивысшее значение вероятности быть выбранной в качестве следующего центроида.
  4. Повторите эти шаги, пока у нас есть K центроидов.

Такой инициализацией гарантируется, что каждый центроид находится как можно дальше друг от друга. Таким образом, не более одного центроида может быть назначено одному и тому же кластеру, и не более одного кластера назначается одному и тому же центроиду.

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

6. Выбор оптимального K

Выбор оптимального значения K очень важен, так как это может привести к красиво структурированным кластерам, а также к неорганизованным «глупым» кластерам.

Есть несколько способов выбора значения K, но наиболее оптимальным способом является использование метода, называемого методом локтя. Нашей целью является нахождение значения K, при котором внутрикластерная сумма квадратов ошибок (WCSSE) минимальна.

WCSSE представляет собой сумму квадратов расстояний точек данных от центроида в одном кластере.

Метод локтя

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

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

Шаги для метода локтя описаны ниже:

  • Мы выбираем K в диапазоне (например, от 1 до 10)
  • Для каждого значения K в этом диапазоне мы находим WCSSE для всех кластеров.
  • Затем мы построим график WCSSE в зависимости от K, где K находится на оси X.
  • K, при котором значение WCSSE резко уменьшается и образует форму локтя, является оптимальным значением K.

Из графика выше видно, что для значения K равного 5, WCSSE резко уменьшается и становится почти постоянным после этого. Поэтому для более чем 5 кластеров WCSSE не уменьшается значительно. Следовательно, мы выбираем K= 5.

7. Оценка качества кластера

Чтобы кластеры имели смысл, мы должны оценить качество каждого кластера. Под качеством я имею в виду насколько хорошо наши кластеры объясняют наши данные. Для этого мы должны вернуться к нашим свойствам кластера. Кластер, соответствующий всем свойствам, считается хорошим. Так как можно математически оценить свойства кластера?

Существуют два способа: 1. Инерция 2. Индекс Данна

1. Инерция

Инерция относится к общей сумме расстояний между точками и центроидом кластера. Это также можно рассматривать как внутрикластерное расстояние, так как мы рассчитываем расстояние между точками внутри кластера. Для центроида кластера C1 мы можем определить инерцию как:

где i изменяется от 1 до m (количество точек в этом кластере)

Внутрикластерное расстояние

На картинке выше изображено межкластерное расстояние или инерция.

Для того, чтобы кластер имел значение, расстояние между его точками и центроидом должно быть как можно меньше. Таким образом, кластер может удовлетворять первому свойству.

Следовательно, значение инерции должно быть как можно меньше для хорошего кластера.

2. ИНДЕКС ДАННА

Индекс Данна – это мера второго свойства кластеров. Он измеряет, насколько далеко кластеры находятся друг от друга, что указывает на разницу между свойствами двух кластеров. Индекс Данна делает это, рассчитывая межкластерное и внутрикластерное расстояние.

Межкластерное расстояние относится к расстоянию между двумя кластерами. Теперь это различие также может зависеть от того, как мы его измеряем.

– Это может быть разница между центроидами двух кластеров – Это может быть разница между самыми удаленными точками от двух кластеров – Это может быть разница между ближайшими точками от двух кластеров.

Независимо от выбранных критериев для измерения межкластерного расстояния, индекс Данна может быть представлен следующим образом:

Для того чтобы два кластера были как можно более различными/удаленными, числитель должен быть очень большим, а знаменатель – очень маленьким. Следовательно,

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

Чтобы кластер имел значение, межкластерное расстояние должно быть максимально возможным. Таким образом, кластер может удовлетворять второму условию.

Таким образом, индекс Данна должен быть максимально возможным для хорошего кластера.

Ну, это было практически все о кластеризации K-средних, в теории. Я буду писать код.

Также посмотрите на это —

  1. KNN
  2. Логистическая регрессия
  3. Метод опорных векторов
  4. Наивный Байес
  5. Метрики оценки – Классификация