Алгоритмы кластеризации - Обзор

Введение в кластеризацию

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

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

Например, ниже приведена диаграмма, которая показывает систему кластеризации, сгруппированную вместе схожие типы данных в разных кластерах:

Методы формирования кластеров

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

На основе плотности

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

На основе иерархии

В этих методах кластеры формируются в виде древовидной структуры на основе иерархии. У них есть две категории, а именно: агломеративные (подход снизу вверх) и разделительные (подход сверху вниз). Ex. Кластеризация с использованием представителей (CURE), сбалансированная итеративная сокращающая кластеризация с использованием иерархий (BIRCH) и т. Д.

Разбиение

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

Сетка

В этих методах кластеры формируются в виде сетчатой ​​структуры. Преимущество этих методов заключается в том, что все операции кластеризации, выполняемые в этих сетках, выполняются быстро и не зависят от количества объектов данных. Ex. Сетка статистической информации (STING), Кластеризация в Quest (CLIQUE).

Измерение эффективности кластеризации

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

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

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

Анализ силуэта

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

Анализ оценки силуэта

Диапазон оценки Silhouette составляет [-1, 1]. Его анализ выглядит следующим образом -

  • +1 Score - Рядом +1 Silhouette score указывает на то, что образец находится далеко от соседнего кластера.

  • 0 Score - 0 Silhouette score указывает, что образец находится на границе решения, разделяющей два соседних кластера, или очень близко к ней.

  • -1 Score & минус -1 Silhouette score указывает, что образцы были назначены неправильным кластерам.

Расчет очков Silhouette можно выполнить с помощью следующей формулы -

= (-) / (,)

Здесь = среднее расстояние до точек в ближайшем кластере

И = среднее внутрикластерное расстояние до всех точек.

Индекс Дэвиса-Болдина

Индекс БД - еще один хороший показатель для анализа алгоритмов кластеризации. С помощью индекса БД мы можем понять следующие моменты модели кластеризации:

  • Удачно ли расположены кластеры друг от друга или нет?

  • Насколько плотны кластеры?

Мы можем рассчитать индекс БД с помощью следующей формулы -

$$ DB = \ frac {1} {n} \ displaystyle \ sum \ limits_ {i = 1} ^ n max_ {j \ neq {i}} \ left (\ frac {\ sigma_ {i} + \ sigma_ {j }} {d (c_ {i}, c_ {j})} \ right) $$

Здесь = количество кластеров

σ i = среднее расстояние всех точек в кластере от центра тяжести кластера.

Чем меньше индекс БД, тем лучше модель кластеризации.

Индекс Данна

Он работает так же, как индекс БД, но есть следующие моменты, в которых оба отличаются:

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

  • Индекс Данна увеличивается по мере увеличения производительности, в то время как индекс БД становится лучше, когда кластеры хорошо разнесены и плотны.

Мы можем рассчитать индекс Данна с помощью следующей формулы -

$$ D = \ frac {min_ {1 \ leq i <{j} \ leq {n}} P (i, j)} {mix_ {1 \ leq i <k \ leq n} q (k)} $$

Здесь ,, = каждый индекс для кластеров

= межкластерное расстояние

q = расстояние внутри кластера

Типы алгоритмов кластеризации машинного обучения

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

К-означает кластеризацию

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

Алгоритм среднего сдвига

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

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

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

Мы подробно обсудим все эти алгоритмы в следующих главах.

Приложения кластеризации

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

Data summarization and compression- Кластеризация широко используется в тех областях, где нам также требуется суммирование, сжатие и сокращение данных. Примеры - обработка изображений и векторное квантование.

Collaborative systems and customer segmentation - Поскольку кластеризацию можно использовать для поиска похожих продуктов или пользователей того же типа, ее можно использовать в области систем для совместной работы и сегментации клиентов.

Serve as a key intermediate step for other data mining tasks- Кластерный анализ может генерировать компактную сводку данных для классификации, тестирования, генерации гипотез; следовательно, он также служит ключевым промежуточным этапом для других задач интеллектуального анализа данных.

Trend detection in dynamic data - Кластеризация также может использоваться для обнаружения тенденций в динамических данных путем создания различных кластеров схожих тенденций.

Social network analysis- Кластеризация может использоваться при анализе социальных сетей. Примеры - создание последовательностей в изображениях, видео или аудио.

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