кластеризация в машинном обучении это

Кластеризация

Материал из MachineLearning.

Кластерный анализ (Data clustering) — задача разбиения заданной выборки объектов (ситуаций) на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.

Задача кластеризации относится к широкому классу задач обучения без учителя.

Содержание

Типология задач кластеризации

Типы входных данных

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

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

Таким образом, постановка задачи кластеризации по матрице расстояний является более общей. С другой стороны, при наличии признаковых описаний часто удаётся строить более эффективные методы кластеризации.

Цели кластеризации

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

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

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

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

Функции расстояния

Методы кластеризации

Формальная постановка задачи кластеризации

Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин:

Источник

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

Дата публикации Mar 6, 2019

Введение в обучение без учителя

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

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

Необучаемый процесс анализа обучения

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

Основные приложения для обучения без учителя:

Таким образом, основная цель состоит в том, чтобы изучить внутреннюю (и обычно скрытую) структуру данных.

Эти методы могут быть сведены к двум основным типам проблем, которые пытается решить неконтролируемое обучение. Это проблемы:

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

Кластерный анализ

Визуально: представьте, что у нас есть набор данных фильмов и мы хотим их классифицировать. У нас есть следующие обзоры фильмов:

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

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

Вот некоторые из наиболее распространенных алгоритмов кластеризации, которые будут рассмотрены в этой статье:

K-средства кластеризации

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

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

Ключевые идеи

Наиболее часто используемое расстояние в K-средних означает квадрат Евклидова расстояния. Пример этого расстояния между двумя точкамих и увт-мерноепространство это:

Вот,Jэто-яизмерение (или столбец элементов) точек выборких и у.

гдеμ (к)центр тяжести для кластераJ,а такжеш (I, J)1, если образецх (я)находится в кластереJи 0 в противном случае.

K-средние можно понимать как алгоритм, который попытается минимизировать коэффициент инерции кластера.

Шаги алгоритма

Гиперпараметры K-средних

Вызовы K-Means

Точки, которые следует учитывать при применении K-средних

Как правильно выбрать номер K

Выбор правильного количества кластеров является одним из ключевых моментов алгоритма K-Means. Чтобы найти это число есть несколько методов:

Будучи согласованным с мотивацией и природой Data Science, метод локтя является предпочтительным вариантом, поскольку для принятия решения он опирается на аналитический метод, подкрепленный данными.

Метод локтя

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

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

В этом случае мы выберем k = 3, где находится колено.

Ограничения K-средних

Хотя K-Means является отличным алгоритмом кластеризации, он наиболее полезен, когда мы заранее знаем точное количество кластеров и когда имеем дело с распределениями сферической формы.

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

Весьма распространено использовать алгоритм K-Means в качестве эталона для оценки производительности других методов кластеризации.

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

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

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

Виды иерархической кластеризации

Существует два подхода к этому типу кластеризации: агломерационный и разделительный.

Одиночная связь и полная связь

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

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

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

Преимущества иерархической кластеризации

Недостатки иерархической кластеризации

Плотная пространственная кластеризация приложений с шумом (DBSCAN)

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

DBSCAN Назначение критериев

Он основан на количестве точек с заданным радиусом ε, и каждой точке данных назначена специальная метка Процесс присвоения этой метки следующий:

Алгоритм DBSCAN

Алгоритм следует логике:

Следующий рисунок очень хорошо суммирует этот процесс и закомментированную запись.

DBSCAN против кластеризации K-средних

DBDSCAN Преимущества

DBSCAN Недостатки

Гауссовые модели смесей (GMM)

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

Например, выделенная точка будет принадлежать кластерам A и B одновременно, но с более высоким членством в группе A из-за ее близости к ней.

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

Распределение GMM в одном измерении

GMM будет искать гауссовские распределения в наборе данных и смешивать их.

GMM в двух измерениях

При наличии многомерного распределения в качестве следующего, средний центр будет µ + σ для каждой оси распределения набора данных.

Алгоритм GMM

Это алгоритм максимизации ожидания, процесс которого можно суммировать следующим образом:

Преимущества GMM

Недостатки GMM

Проверка кластеризации

Внешние показатели

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

Чтобы понять это, мы должны сначала определить его компоненты:

Индексы внутренней проверки

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

Одним из наиболее распространенных показателей является Коэффициент Силуэт.

Существует Коэффициент Силуэт для каждой точки данных.

Он подходит только для определенных алгоритмов, таких как K-средние и иерархическая кластеризация. Не подходит для работы с DBSCAN, вместо этого мы будем использовать DBCV.

Вывод

Мы впервые познакомились с обучением без присмотра и основными алгоритмами кластеризации.

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

Источник

Кластеризуем лучше, чем «метод локтя»

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

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

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

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

Метод локтя

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

Что это за балл, или метрика, которая откладывается на графике? Почему называют методом локтя?

Характерный график выглядит так:

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

Например, этот метод балльной оценки сразу доступен в средстве оценки по методу k-средних в Scikit-learn.

Но взгляните ещё раз на этот график. В нём чувствуется что-то странное. Какое оптимальное количество кластеров у нас получилось, 4, 5 или 6?

Непонятно, не правда ли?

Силуэт — более подходящая метрика

Вот видео, в котором объясняется эта идея:

Допустим, мы сгенерировали случайные данные с помощью функции make_blob из Scikit-learn. Данные расположены в четырёх измерениях и вокруг пяти кластерных центров. Суть проблемы в том, что данные сгенерированы вокруг пяти кластерных центров. Однако алгоритм k-средних об этом не знает.

Кластеры можно отобразить на графике следующим образом (попарные признаки):

Затем прогоним алгоритм k-средних со значениями от k=2 до k=12, а затем вычислим метрику по умолчанию к k-средних и среднее значение силуэта для каждого прогона, с выводом результатов в двух соседних графиках.

Разница очевидна. Среднее значение силуэта возрастает до k=5, а затем резко снижается для более высоких значений k. То есть мы получаем выраженный пик при k=5, это количество кластеров, сгенерированных в исходном датасете.

График силуэта имеет пиковый характер, в отличие от мягко изогнутого графика при использовании метода локтя. Его проще визуализировать и обосновать.

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

В этом случае вычисление k-средних по умолчанию с применением метода локтя даёт ещё более неопределённый результат. Ниже показан график метода локтя, на котором трудно выбрать подходящую точку, в которой линия на самом деле изгибается. Это 4, 5, 6 или 7?

При этом график силуэта всё ещё демонстрирует пик в районе 4 или 5 кластерных центров, что существенно облегчает нам жизнь.

Если вы посмотрите на накладывающиеся друг на друга кластеры, то увидите, что, несмотря на то, что мы сгенерировали данные вокруг 5 центров, из-за высокой дисперсии структурно можно выделить только 4 кластера. Силуэт легко выявляет это поведение и показывает оптимальное количество кластеров между 4 и 5.

Оценка BIC с моделью смеси нормальных распределений

Есть и другие замечательные метрики для определения истинного количества кластеров, например, байесовский информационный критерий (BIC). Но их можно применять лишь в том случае, если нам нужно перейти от метода k-средних к более обобщённой версии — смеси нормальных распределений (Gaussian Mixture Model (GMM)).

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

BIC для регуляризации

Вы уже могли сталкиваться с BIC в статистическом анализе или при использовании линейной регрессии. BIC и AIC (Akaike Information Criterion, информационный критерий Акаике) используются в линейной регрессии в качестве методик регуляризации для процесса отбора переменных.

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

Метод BIC штрафует многочисленные нормальные распределения и пытается сохранить модель достаточно простой, чтобы она описывала заданный паттерн.

Следовательно, можно прогнать алгоритм GMM для большого количества кластерных центров, и значение BIC вырастет до какой-то точки, а затем начнёт снижаться по мере роста штрафа.

Вот Jupyter notebook для этой статьи. Можете свободно форкать и экспериментировать.

Мы в «Инфосистемы Джет» обсудили пару альтернатив популярному методу локтя с точки зрения выбора правильного количества кластеров при обучении без учителя с применением алгоритма k-средних.

Мы убедились, что вместо метода локтя для визуального определения оптимального количества кластеров лучше использовать коэффициент «силуэт» и значение BIC (из GMM-расширения для k-средних).

Источник

Кластерные алгоритмы и их значение в машинном обучении

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

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

Значение кластеризации

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

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

Методы кластеризации

Иерархические методы

Созданные в этой процедуре кластеры создают древовидную структуру, представляющую иерархию. Новые кластеры, появляющиеся на дереве, происходят из ранее сформированных комков. Эксперты разделили их на следующие категории:

Агломерационный

Подход “снизу вверх” – каждая точка данных представляет собой единый кластер, и они непрерывно сливаются (агломерат) до тех пор, пока все не будут постепенно сливаться в один кластер. Этот процесс также известен как HAC.

Разделяющий

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

Методы на основе плотности

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

Методы на основе сетки

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

Методы разбиения

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

Что такое К-образные кластеры?

К-Минс (k-means)- это, пожалуй, наиболее узнаваемый алгоритм кластеризации. Этот алгоритм преподается на большинстве курсов машинного обучения и информатики, особенно на вводных занятиях. Понимать его довольно легко, а реализовать его в коде еще проще. К-Минс выделяется на фоне других алгоритмов своим быстрым темпом. Большинство из нас вычисляет расстояния между групповыми центрами и точками с минимальными вычислениями. Так что сложность часто бывает линейной O

Примеры алгоритма кластеризации в реальном мире Использует

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

Распознавание фальшивых новостей

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

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

Продажи и маркетинг

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

Фэнтези-спорт

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

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

Выявление преступной деятельности

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

С помощью кластеризации можно проанализировать GPS-журналы и создать группу идентичного поведения. Можно изучить характеристики группы и классифицировать мошенническое и подлинное поведение.

Фильтры спама

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

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

Заключительные Мысли

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

Источник