Что такое кластерный анализ

Кластерный анализ — это форма исследовательского анализа данных, в которой наблюдения делятся на разные группы, имеющие общие характеристики. Другими словами, поиск сходства между данными по характеристикам, обнаруженным в данных, и группировка похожих объектов данных в кластеры.

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

Основными подходами к кластеризации являются подход с разделением, который включает K-Means и K-Medoids, иерархический подход, который включает Диану и Агнес, и подход на основе плотности, который включает DBSCAN.

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

Наиболее популярным и используемым алгоритмом кластеризации является K-Means. Лучшее представление об этом алгоритме можно получить с помощью иллюстраций. Этот алгоритм группирует немаркированный набор данных в согласованные подмножества (кластеры). Это простой итерационный алгоритм, который состоит всего из двух шагов: первый — это этап назначения кластера, а второй — этап перемещения центроида. Следующие визуализации объясняются шаг за шагом, чтобы показать, как кластеризация K-средних работает под капотом, и итеративно выполнять свои шаги.

Центроиды кластера.Центроид – это точка в центре кластера. Каждому центроиду присваивается среднее арифметическое кластера, к которому он принадлежит.

Давайте извлечем из наших данных две подгруппы (кластера). Обратите внимание, что изначально у нас нет меток, но мы интуитивно выбираем «k».

1-й шаг — назначение кластера.Алгоритм инициализирует две случайные точки, показанные красным и синим цветом на приведенной выше диаграмме. Выбор правильной k-й точки среди набора данных является предлагаемым способом инициализации случайных точек, хотя для целей иллюстрации в графическом представлении выше случайные точки инициализируются иначе, чем заданный набор данных. Первым шагом является этап назначения кластера. В цикле он перебирает каждую точку данных, чтобы вычислить, к какой точке (красной или синей) они ближе всего. Он назначает каждую из точек данных одному из двух центроидов кластера (красному или синему).

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

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

Алгоритм K означает два входа: один — X, который представляет собой немаркированный обучающий набор данных, другой — параметр K, который представляет собой количество кластеров, которые нужно найти в данных (выбор «K» обрабатывается в другом дополнительном разделе) .

Здесь, на этой конкретной итерации снова, алгоритм вычисляет новые средние значения и перемещает центроиды в новые точки. И он останавливается из-за отсутствия дальнейшей итерации, которая больше не может изменить состояние (назначение новому кластеру или поиск нового среднего значения).

Соглашение для данных - это x (i), который является Rn-мерным вектором.

K: общее количество центроидов

k: индекс центроида

Пример: c(2)=3 →2-й пример назначен кластеру 3

Таким образом, из всех возможных значений k∈{1,2,…,K} значение k=3 минимизирует:

Первым шагом является случайная инициализация k центроидов кластера, 1,2, вплоть до k. В предыдущей демонстрации у нас было K=2 кластера красного и синего цвета. Таким образом, что касается обозначения алгоритма здесь, центроид красного креста может быть 1, а синий может быть 2.

Объяснение 1-го шага — назначение кластера: для каждого из обучающих данных переменная объявляется и инициализируется как индекс от 1 до K центроида кластера, ближайшего к x(i). Это шаг назначения кластера, при котором каждая точка данных окрашивается в красный или синий цвет, в зависимости от того, к какому центроиду кластера ближе всего точка данных, с использованием функции расчета расстояния. Соответственно, c(i) будет числом от 1 до K, которое указывает, ближе ли оно к красному кресту или ближе к синему кресту.

Цель состоит в том, чтобы перебрать значения и найти значение k, которое минимизирует это расстояние между x и центроидом кластера, так что c устанавливается как значение k, которое минимизирует это.

Следующим шагом является перемещение центроидов.

Объяснение 2-го шага — перемещение центроидов кластера. Эта часть вычисляется во время второго цикла for в представленном выше псевдокоде. Теперь уже назначены переменные X и соответствующие им центроиды кластера, которые являются точками, к которым они наиболее близки. Здесь выполняется простой расчет, поскольку он просто берет среднее значение набора данных в каждом кластере соответственно как набор k.

Другими словами, для каждого из центроидов кластера, для нижнего регистра k равно от 1 до K, алгоритм устанавливает k равным среднему значению точек, присвоенных кластеру.

Пример:

c(1)=2 →1-й пример назначается кластеру 2

c(2)=2 →2-й пример назначается кластеру 2

c(4)=2 →4-й пример назначается кластеру 2

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

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

Цель оптимизации — минимизировать функцию стоимости J (или искажение). Шаг назначения кластера, который является первой функцией повторения (циклом) в приведенном выше репрезентативном псевдокоде, алгоритм выполняет эту минимизирующую функцию стоимости, которая представляет собой квадратное расстояние каждого x до местоположений центроидов соответственно. И во втором цикле в приведенном выше псевдокоде, который соответствует 2-му шагу алгоритма, который перемещает центроиды, алгоритм пытается выбрать значения средних (μ), чтобы минимизировать функцию стоимости Jотносительно расположения центроидов.

Случайная инициализация

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

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

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

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

Каково правильное значение K?

В приведенных выше примерах кажется довольно двусмысленным сказать, какое количество кластеров было бы лучшим или лучшим вариантом, просто взглянув на графическое представление данных. Более того, существует ряд способов найти правильное (!) значение К.

Метод локтя

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

Следующим шагом является нанесение расстояний на график, на котором горизонтальная ось — это количество кластеров, а вертикальная ось — диаметр (функция стоимости или искажение). Затем последний шаг — соединение точек, как показано ниже.

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

На основе показателя/цели

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

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

Алгоритмы PAM/Клара

В качестве примера реализации в программировании на R функция pamk используется для вызова функции pam или clara и выполнения разбиения вокруг кластеризации медоидов с количеством кластеров, оцененным по оптимальному среднему значению. ширина силуэта или индекс Калинского-Харабаша (calinhara). Тест Дуда-Харта применяется, чтобы решить, должно ли быть более одного кластера.

Пример (реализация на R):

pamk(autox.scaled.df, 2:10)

  • Найдите количество кластеров (от 2 до 10) с выполнением либо PAM (или CLARA, если usepam=FALSE)
  • Значение параметра usepam по умолчанию равно TRUE в функции pamk, поэтому анализ выполняется с помощью PAM.

Пример вывода:

Показатели сходства

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

Центроид, середина кластера:

Радиус, квадратный корень из среднего расстояние от любой точки скопления до его центроида:

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

Одиночное звено, наименьшее расстояние между элементом в одном кластере и элементом в другом, т. е. dis(Ki, Kj) = min(tip, tjq)

Полная ссылка, наибольшее расстояние между элементом в одном кластере и элементом в другом, т. е. dis(Ki, Kj) = max(tip, tjq)

Медоид, расстояние между медоидами двух кластеров, т. е. dis(Ki, Kj) = dis(Mi, Mj)

Центроид, расстояние между центроидами двух кластеров, т. е. dis(Ki, Kj) = dis(Ci, Cj)

Среднее, среднее расстояние между элементом в одном кластере и элементом в другом, т. е. dis(Ki, Kj) = avg(tip, tjq)

Слабые стороны алгоритма K-средних

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

Кластеризация K-Medoids

Кластеризация K-медоидов основана на концепции медоидов (репрезентативных объектов). Алгоритмы k-means и k-medoids являются секциональными (разбивая набор данных на группы). K-means выбирает центр кластера, и на него влияют выбросы, тогда как K-medoids выбирает наиболее центрированный член кластера (сами данные).

K-Medoids будет работать лучше, если набор данных будет включать выбросы, а не K-Means, поскольку на среднее значение выбросы влияют гораздо больше, чем медоиды.

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

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

  1. Определите два кластера, которые находятся ближе всего друг к другу
  2. Объединить два наиболее похожих кластера
  3. Этот итеративный процесс продолжается до тех пор, пока все кластеры не будут объединены вместе.

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

Основные недостатки методов агломеративной кластеризации заключаются в том, что, во-первых, они плохо масштабируются, временная сложность составляет не менее O (n2) (n: количество объектов), а во-вторых, если применить эти методы, то нельзя отменить то, что было сделано ранее.

AGNES (агломеративное вложение)

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

ДИАНА (разделительный анализ)

Порядок, обратный AGNES, и в конечном итоге каждый узел формирует отдельный кластер.

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

Ключевая идея состоит в том, что для каждой точки кластера окрестность заданного радиуса должна содержать хотя бы минимальное количество точек. Цель состоит в том, чтобы определить плотные области, которые можно измерить по количеству объектов, близких к данной точке. Методы разбиения (K-средние, кластеризация PAM) и иерархическая кластеризация подходят для поиска кластеров сферической формы или выпуклых кластеров.

Параметры плотности:

  • Эпсилон: расстояние, определяет радиус окрестности вокруг точки x (стандартное отклонение).
  • Minpoints: количество соседей, минимальное количество соседей в радиусе «eps» (населенность этого соседства)
  • Основная (исходная) точка: любая точка x в наборе данных с числом соседей, большим или равным Minpoints,
  • Пограничная точка: если количество ее соседей меньше, чем Minpoints, но она принадлежит эпсилон-окрестности некоторой центральной точки z
  • Точка шума (или выброс): если точка не является ни основной, ни пограничной точкой.

Алгоритм DBSCAN:

  • Произвольно выберите точку p
  • Получить все точки, достижимые по плотности, из p относительно Eps и Minpoints.
  • Если p является точкой ядра, формируется кластер.
  • Если p является граничной точкой, из точки p нет точек, достижимых по плотности, и DBSCAN обращается к следующей точке базы данных.
  • Продолжайте процесс, пока не будут обработаны все точки.

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

Они могут идентифицировать выбросы:

  • Выбирает случайную точку,
  • Если точка не очень близка к другим точкам, перейдите к другой случайной точке и начните сначала.

использованная литература

  • Алпайдин Э., (2014) Введение в машинное обучение
  • Андрей Н.Г., https://www.coursera.org/learn/machine-learning
  • Кэсси Козырьков, https://www.youtube.com/watch?v=X3nGqDosNtk
  • Г. Равали1, П.Свати Мулика2, А.А. Парна3, Дж.Абхиная4, Т.Анурадха (2017), Анализ данных YouTube с использованием кластеризации K-средних
  • Калински, Р. Б., и Харабаш, Дж. (1974) Дендритный метод для кластерного анализа, Связи в статистике, 3, 1–27.
  • Дуда, Р.О. и Харт, П.Е. (1973) Классификация образов и анализ сцен. Уайли, Нью-Йорк.
  • Решающие данные, https://www.youtube.com/watch?v=Se28XHI2_xE
  • Луис Серрано, https://www.youtube.com/watch?v=QXOkPvFM6NU
  • Хенниг, К. и Ляо, Т. (2013) Как найти подходящую кластеризацию для переменных смешанного типа с применением социально-экономической стратификации, Журнал Королевского статистического общества, Серия C Прикладная статистика, 62, 309–369.
  • Кауфман, Л. и Руссо, П. Дж. (1990). «Поиск групп в данных: введение в кластерный анализ». Уайли, Нью-Йорк.