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

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

Иерархическая кластеризация

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

Мы начинаем с n разных точек и k различных кластеров, которые хотим обнаружить; для наших целей n = 4 и k = 2.

Начните с рассмотрения каждой точки, как если бы это был отдельный кластер.

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

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

В любом случае, мы начинаем объединять кластеры, которые находятся ближе всего друг к другу. Допустим, мы знаем, что x1 и x3 наиболее близки друг к другу. Затем мы объединяем эти два в новый кластер ca.

Теперь мы пересчитаем расстояние CA от всех остальных кластеров, используя тот метод, который мы предпочитаем из вышеупомянутой сумки. Затем мы повторяем, объединяя наши кластеры снова и снова, пока не получим k кластеров верхнего уровня - в нашем примере это два кластера. Допустим, мы выяснили, что x2 ближе к ca, чем к x4.

Теперь у нас есть два кластера верхнего уровня, cb и x4 (помните, что каждая точка начинается как отдельный кластер). Теперь мы можем искать в созданной нами древовидной структуре для поиска подкластеров, которые в нашем исходном двухмерном представлении выглядели бы следующим образом:

Кластеризация на основе плотности

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

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

Этот подход требует двух параметров: радиуса 𝜖 и плотности окрестности. Для каждой точки мы вычисляем Neps (x) - количество точек, которые находятся не более чем на 𝜖 от x. Если Neps (x) ≥ 𝛳, не считая x, то x считается основной точкой. Если точка не является базовой точкой, но входит в ее окрестности, то она считается граничной точкой. Все остальное считается шумом.

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

Скажем, у нас есть относительно маленький 𝜖 и прилично большой. Мы можем получить такие кластеры:

Видеть? Эти две одинокие точки находятся очень далеко от двух кластеров, и их слишком мало, чтобы они действительно что-то значили - так что они просто шум.

Обратите внимание, что таким образом мы также можем обнаруживать невыпуклые кластеры (см. Оранжевую дугу). Довольно аккуратно!

Нам не нужно указывать количество кластеров, которые нас интересуют, чтобы кластеризация на основе плотности работала - она ​​автоматически обнаружит некоторое количество кластеров на основе ваших 𝜖 и 𝛳. Это особенно полезно, когда вы ожидаете, что все ваши кластеры будут иметь одинаковую плотность.

Кластеризация K-средних

Иерархическая кластеризация лучше всего подходит для обнаружения встроенных структур в данных, а подходы, основанные на плотности, превосходны при обнаружении неизвестного числа кластеров с аналогичной плотностью. Однако оба не могут прийти к «консенсусу» по всему набору данных. Иерархическая кластеризация может объединять кластеры, которые кажутся близкими, но информация о других точках не учитывается. Методы, основанные на плотности, смотрят только на небольшую окрестность ближайших точек и точно так же не учитывают весь набор данных.

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

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

После того, как все точки назначены, пройдите по каждому кластеру и возьмите среднее значение всех точек, которые он содержит. Эта новая «средняя» точка - новое среднее значение кластера.

Просто повторяйте эти два шага снова и снова, пока назначение очков не перестанет меняться!

Как только назначение точек перестает меняться, говорят, что алгоритм сходится.

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

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

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

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

Прочтите больше статей по науке о данных на OpenDataScience.com