Что такое K-means кластеризация, работа, преимущества, недостатки и варианты использования.

История

Термин "k-средние" впервые был использованДжеймсом Маккуином в 1967 году в его статье о "некоторых методах классификации и анализа многомерных наблюдений". Стандартный алгоритм также использовался в лабораториях Белла как часть метода импульсно-кодовой модуляции в 1957 году. Он также был опубликован в 1965 году Э. У. Форги и обычно также известен как метод Ллойда-Форги.

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

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

Давайте разберемся с алгоритмом кластеризации K-средних с его простым определением.

“A K-means clustering algorithm tries to group similar items in the form of clusters. The number of groups is represented by K.”

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

Сейчас мы это поймем с помощью красивой фигуры.

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

Теперь посмотрите на второй рисунок (рис. 2). Это показывает данные после применения алгоритма кластеризации K-средних. вы можете видеть, что все три разных элемента классифицируются по трем различным категориям, которые называются кластерами.

Где я могу применить K-means?

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

Как работает алгоритм кластеризации K-средних?

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

  1. Выберите значения k.
  2. Инициализируйте центроиды.
  3. Выберите группу и найдите среднее значение.

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

Мы будем понимать каждую цифру одну за другой.

  • На рис. 1 показано представление данных двух разных элементов. первый элемент отображается синим цветом, а второй элемент отображается красным цветом. Здесь я выбираю значение K случайным образом равным 2. Существуют разные методы, с помощью которых мы можем выбрать правильные значения k.
  • На рисунке 2 соедините две выбранные точки. Теперь, чтобы узнать центр тяжести, мы проведем перпендикулярную линию к этой линии. Точки переместятся к их центроидам. Если вы заметите там, то увидите, что некоторые из красных точек теперь переместились в синие точки. Теперь эти точки относятся к группе элементов синего цвета.
  • Тот же процесс продолжится на рисунке 3. Мы соединим две точки и проведем к ним перпендикулярную линию и найдем центр тяжести. Теперь две точки переместятся к своему центроиду, и снова некоторые из красных точек будут преобразованы в синие точки.
  • Тот же процесс происходит на рисунке 4. Этот процесс будет продолжаться до тех пор, пока мы не получим два совершенно разных кластера этих групп.

Как выбрать значение К?

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

  1. Локтевой метод.
  2. Силуэтный метод.

Теперь давайте подробно разберем обе концепции.

Метод локтя

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

Это эмпирический метод определения наилучшего значения k. он выбирает диапазон значений и выбирает лучшее из них. Он вычисляет сумму квадратов точек и вычисляет среднее расстояние.

Когда значение k равно 1, сумма квадрата внутри кластера будет высокой. По мере увеличения значения k сумма квадратов внутри кластера будет уменьшаться.

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

Метод силуэта

Метод силуэта несколько отличается. Метод локтя также выбирает диапазон значений k и рисует график силуэта. Он вычисляет коэффициент силуэта каждой точки. Он вычисляет среднее расстояние точек в своем кластере a (i) и среднее расстояние точек до своего следующего ближайшего кластера, называемого b (i).

Note : The a (i) value must be less than the b (i) value, that is a(i)<<b(i)

Теперь у нас есть значения a (i) и b (i). мы рассчитаем коэффициент силуэта, используя приведенную ниже формулу.

Теперь мы можем вычислить коэффициент силуэта всех точек в кластерах и построить график силуэта. Этот график также поможет обнаружить выбросы. График силуэта находится в диапазоне от -1 до 1.

Note that for silhouette coefficient equal to -1 is the worst case scenario.

Кроме того, проверьте график с меньшим количеством выбросов, что означает менее отрицательное значение. Затем выберите это значение k для настройки вашей модели.

Преимущества K-средних

  1. Это очень просто реализовать.
  2. Он масштабируется до огромного набора данных, а также быстрее работает с большими наборами данных.
  3. он очень часто адаптирует новые примеры.
  4. Обобщение кластеров для разных форм и размеров.

Недостатки K-средних

  1. Он чувствителен к выбросам.
  2. Выбор значений k вручную — тяжелая работа.
  3. По мере увеличения количества измерений его масштабируемость снижается.

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

Анализ преступности с использованием кластеризации K-средних

  • Определить геопространственный сюжет преступлений в городе: Первым шагом является сбор информации о преступлениях в данном городе. Обычно их можно получить из нескольких источников, таких как отчеты правоохранительных органов, статистические обзоры виктимизации, сопоставление газетных статей и т. д. Эти данные можно нанести на географическую карту, например, показанную выше.
  • Использование подхода интеллектуального анализа данных K-средних помогает нам выявлять закономерности, поскольку людям очень сложно обрабатывать большие объемы данных, особенно если отсутствует информация для обнаружения закономерностей.
  • Кластеры полезны для выявления серии преступлений, совершенных одной или одной и той же группой подозреваемых. Затем эти кластеры представляются детективам, которые углубляются, используя свой опыт в предметной области, для раскрытия дел.

Используйте следующие шаги для кластерного анализа:

  • Сортировка записей — первая сортировка будет производиться по наиболее важным характеристикам, исходя из опыта детектива.
  • Затем интеллектуальный анализ данных используется для обнаружения более сложных закономерностей, поскольку в реальной жизни существует множество атрибутов, связанных с преступлением, и у нас часто есть частичная доступная информация.
  • Идентификация значимых атрибутов для кластеризации.
  • Динамическое присвоение разного веса различным атрибутам в зависимости от группируемых типов преступлений.
  • Кластеризируйте набор данных для шаблонов преступлений и представьте результаты детективу или эксперту в предметной области вместе со статистикой важных атрибутов.
  • Детектив смотрит на кластеры и дает рекомендации.
  • Нераскрытые преступления группируются по существенным признакам, и результат передается детективу для проверки.
  • В этой статье мы будем использовать подход K-средних для создания кластеров. Алгоритм K-средних состоит из следующих шагов:
  • Определите количество кластеров, K. Кластерный анализ K-средних требует, чтобы вы знали, сколько кластеров нужно сгенерировать до запуска алгоритма.
  • Инициализируйте кластеры K или сгенерируйте их случайным образом. Различные начальные точки для кластеров могут давать разные результаты.
  • Назначьте каждое наблюдение ближайшему центру кластера. Это итеративный метод, который строит кластеры по мере нашего продвижения.
  • Пересчитайте новые центры кластеров. Обратите внимание, что вам необходимо указать алгоритмы определения расстояния между кластерами.
  • Повторяйте процесс до тех пор, пока ни одно из наблюдений не изменит свое членство в последней итерации.
  • Пример кластерного анализа K-средних показан на рисунке ниже. В этом примере мы показываем создание 3 кластеров (каждый разного цвета).

  • Анализ паттернов и выводы Это включает в себя анализ каждого сформированного кластера. Компьютер не может понять, что уникально в каждом кластере. Здесь в игру вступает человеческая компетентность. Например, все преступления, выделенные красным цветом, могли быть совершены с использованием аналогичного оружия или все преступления, выделенные синим цветом, могут быть связаны с кражей драгоценностей, когда люди шли по дороге, а нападавшие передвигались на мотоцикле и т. д. Это помогает находить модели преступности и корреляции тенденций. Как только определенная закономерность обнаружена, сотрудники правоохранительных органов могут задействовать дополнительные и подходящие ресурсы для обнаружения и пресечения преступной деятельности.

Спасибо за прочтение статьи!