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

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

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

Поскольку кластеризация популярна во многих областях, существует множество методов кластеризации. Но мы будем специально сосредоточиваться на кластеризации K-средних, где мы стремимся разбить наблюдение на заранее заданное количество кластеров.

Кластеризация K-средних - это простой и элегантный подход для разделения набора данных на K отдельных неперекрывающихся кластеров. Под неперекрытием мы подразумеваем, что ни одно наблюдение не принадлежит более чем одному кластеру. Чтобы выполнить кластеризацию K-средних, мы должны сначала указать желаемое количество кластеров K; тогда алгоритм K-средних назначит каждое наблюдение ровно одному из K кластеров. Рисунок 1. показывает результаты, полученные при выполнении кластеризации K-средних на смоделированном примере, состоящем из 150 наблюдений в двух измерениях, с использованием трех различных значений K.

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

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

________________________________________________________________

Алгоритм: кластеризация K-средних

1. Случайным образом присвойте номер от 1 до K каждому наблюдению. Они служат в качестве начальных кластерных назначений для наблюдений.

2. Итерируйте (повторяйте), пока назначения кластера не перестанут меняться:

(a) Для каждого из K кластеров вычислите центроид кластера. Центроид k-го кластера является вектором средних значений p характеристик (среднего) для наблюдений в k-м кластере.

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

_________________________________________________________________

На шаге 2 (а) мы вычисляем среднее значение наблюдений в кластере (центроид кластера). Здесь наблюдение - это не что иное, как вектор из p характеристик. Затем на шаге 2 (b) мы вычисляем расстояние между наблюдением до каждого центроида кластера и затем назначаем наблюдение кластеру, для которого расстояние минимально. Это означает, что по мере выполнения алгоритма полученная кластеризация будет постоянно улучшаться, пока результат не перестанет меняться. Когда результат больше не меняется, значит, достигнут локальный оптимум. На рисунке 2 показано развитие алгоритма на игрушечном примере с рисунка 1.

Кластеризация K-средних получила свое название от того факта, что на шаге 2 (а) центроиды кластера вычисляются как среднее значение наблюдений, назначенных каждому кластеру. Поскольку алгоритм K-средних находит локальный оптимум (минимизируя дисперсию внутри кластера), а не глобальный, полученные результаты будут зависеть от начального (случайного) кластерного назначения каждого наблюдения на шаге 1 алгоритма. По этой причине важно запускать алгоритм несколько раз с разными случайными начальными конфигурациями. Затем выбирается лучшее решение, т. Е. Сумма внутрикластерных дисперсий всех кластеров (цель) наименьшая. На рисунке 3 показаны локальные оптимумы, полученные шестикратным запуском кластеризации K-средних с использованием шести различных начальных назначений кластеров, с использованием игрушечных данных из рисунка 1. В этом случае наилучшая кластеризация - это кластеризация с целевым значением 235,8 (минимум).

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

Ссылка: Книга Роберта Тибширани, Гарета Джеймса, Тревора Хасти и Даниэлы Виттен «Введение в статистическое обучение с приложениями на языке R».