Юлий Цезарь: «Divida et Impera» (перевод: разделяй и властвуй)

На протяжении тысячелетий мы решали большие проблемы, разбивая их на более мелкие, лучше определенные части, на которых мы можем сосредоточить наши усилия:

  • Большая проблема: как продавать товары миллионам клиентов.
  • Проблема меньшего масштаба: Как продавать товары мужчинам в возрасте от 25 до 30 лет, которые зарабатывают от 75 до 120 тысяч в год?

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

В этом посте я рассмотрю тип задач, на решение которых направлена ​​кластеризация, и опишу «k-means» - популярный метод кластеризации набора данных.

Почему кластер?

Итак, у вас есть база данных с миллионами транзакций ваших клиентов и информацией об аккаунтах.

Представьте, что вы хотите рекламировать этих клиентов. Самый простой способ - крикнуть всем одновременно: «Приходите, наши вещи!».

Глупо, правда? Итак, проведя небольшой анализ, вы сегментируете свои данные - возможно, по демографическим характеристикам, возможно, по определенным категориям продуктов. Теперь ваша реклама более таргетированная (и, надеюсь, более эффективная) - «Эй, вы, ребята, специально, займитесь этим!».

Проблема в том, что ваша способность создавать эти сегменты имеет естественный предел - либо на основе ваших знаний и опыта, либо на времени и энергии, которые у вас есть, чтобы просмотреть свои данные.

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

Типы кластеров

Полезно понимать, что общие типы кластеров являются иерархическими или секционированными.

Иерархическая кластеризация - это:

  • Достигается путем создания и объединения более мелких кластеров в более крупные (или разделения более крупных кластеров на более мелкие) - повторяется снова и снова.
  • Представлен иерархией, называемой «дендрограммой».
  • Иногда более значимый и субъективный с меньшим количеством необходимых входных параметров - но также медленнее в работе.
  • Пример. Использование матрицы расстояний между городами для создания иерархии кластеров на основе близости - от ближайшего к самому дальнему. По мере продвижения вверх по иерархии кластеры становятся больше, например NY и BOS объединяются в NY / BOS, а затем этот кластер присоединяется к DC (NY / BOS + DC) и так далее.

Разделенная кластеризация:

  • Разделы генерируются и оцениваются на основе некоторого критерия.
  • Пользователи вводят количество создаваемых кластеров (обычно называется k)
  • Начните с произвольного создания разделов, а затем проверьте их на близость (к точкам данных) и переместите затем разделы соответственно - повторяйте до тех пор, пока количество точек данных, переходящих между разделами, не будет минимизировано.
  • Быстро запускается, но результаты могут быть менее значимыми, чем иерархическая кластеризация. Необходимо указать, сколько разделов нужно создать.
  • Пример: взяв таблицу оцененных статей для эссе, содержащую такие переменные, как количество слов, орфографические ошибки, оценка и т. д., и создайте k секционированных кластеров статей для эссе (на основе аналогичных переменных ) - где k = количество разделов, указанное пользователем

В этой статье я сосредоточусь на секционированной кластеризации, в частности на «k-means».

К-значит? Что это обозначает?

K-means - это тип секционированной кластеризации и тип обучения без учителя (узнать больше).

Алгоритм создает k групп для ваших данных (где k заранее определено пользователем). Группировка достигается путем минимизации суммы квадратов расстояний (известных как евклидово расстояние) между каждой точкой данных и центроидом (подумайте о центре тяжести) для каждой группы:

Вы начинаете со случайного размещения ваших центроидов, а затем используете евклидово расстояние для сопоставления каждой точки данных с центроидом:

Затем для каждого кластера вы берете среднее значение точек данных, чтобы найти новый центроид, что приводит к новой разделительной линии, а некоторые точки данных меняют команды (на другой центроид):

Затем вы повторяете описанные выше шаги снова и снова.

В конце концов, определение нового центроида (и новой разделительной линии) не приведет ни к одному из, ни к тому же количеству точек данных, переходящих команду:

На этом кластеризация считается завершенной.

Вывод

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