При обучении с учителем мы знаем названия точек данных и их распределение. Однако ярлыки не всегда могут быть известны. Кластеризация - это практика присвоения меток немаркированным данным с использованием существующих в них шаблонов. Кластеризация может быть полупараметрической или вероятностной.
1. Кластеризация K-средних:
Кластеризация K-средних - это итерационный алгоритм, который начинается с k случайных чисел, используемых в качестве средних значений для определения кластеров. Точки данных принадлежат кластеру, определяемому средним значением, к которому они наиболее близки. Эта координата среднего значения называется центроидом.
Итеративно вычисляется среднее значение точек данных каждого кластера, и новые средние значения используются для перезапуска процесса до тех пор, пока среднее значение не перестанет меняться. Недостатком K-Means является то, что это процедура локального поиска, которая может пропускать глобальные шаблоны.
Начальные центроиды k могут быть выбраны случайным образом. Другой подход к определению k - вычислить среднее значение всего набора данных и добавить к нему k случайные координаты, чтобы получить k начальных точек. Другой подход - определить главный компонент данных и разделить его на k равных частей. Среднее значение каждого раздела можно использовать в качестве начальных центроидов.
2. Кластеризация по K-медианам
K-медианы используют абсолютные отклонения (манхэттенское расстояние) для формирования k кластеров в данных. Центроид кластеров - это медиана точек данных в кластере. Этот метод аналогичен K-средним, но более устойчив к выбросам из-за использования медианы, а не среднего, поскольку K-средние оптимизируют квадраты расстояний.
Рассмотрим список чисел: 3, 3, 3, 9. Его медиана равна 3, а среднее - 4,5. Таким образом, мы видим, что использование медианы предотвращает влияние выбросов.
3. Кластеризация K-режимов
Многие данные в реальных данных являются категориальными, такими как пол и профессия, и, в отличие от числовых данных, категориальные данные дискретны и неупорядочены. Следовательно, алгоритмы кластеризации числовых данных нельзя использовать для категориальных данных. K-средние не могут обрабатывать категориальные данные, поскольку сопоставление категориальных значений с 1/0 не может генерировать качественные кластеры для многомерных данных, поэтому вместо этого мы можем перейти к K-режимам.
Подход K-Modes модифицирует стандартный процесс K-Means для кластеризации категориальных данных, заменяя функцию евклидова расстояния простой мерой несходства сопоставления, используя режимы для представления центров кластеров и обновляя режимы с наиболее частыми категориальными значениями в каждой из итераций процесс кластеризации. Эти модификации гарантируют, что процесс кластеризации сходится к локальному минимальному результату. Количество мод будет равно количеству требуемых кластеров, поскольку они действуют как центроиды. Метрика несходства, используемая для K-режимов, - это расстояние Хэмминга от теории информации, которое можно увидеть на Рис. Здесь x и y - это значения атрибута j в объектах X и Y. Чем больше количество несовпадений категориальных значений между X и Y, тем более различаются два объекта. В случае категориального набора данных режим атрибута - либо 1, либо 0, в зависимости от того, что чаще встречается в кластере. Вектор моды кластера минимизирует сумму расстояний между каждым объектом в кластере и центром кластера.
Процесс кластеризации K-Modes состоит из следующих шагов:
- Случайным образом выбрать k уникальных объектов в качестве начальных центров (мод) кластеров.
- Рассчитайте расстояния между каждым объектом и режимом кластера; назначьте объект кластеру, центр которого имеет кратчайшее расстояние до объекта.
- Повторяйте, пока все объекты не будут назначены кластерам.
- Выберите новую модель для каждого кластера и сравните ее с предыдущим режимом. Если отличается, вернитесь к шагу 2; в противном случае остановитесь.
4. Кластеризация среднего сдвига
Средний сдвиг - это алгоритм иерархической кластеризации. Это алгоритм на основе скользящего окна, который пытается найти плотные области точек данных. Среднее смещение рассматривает пространство признаков как выборку из лежащей в основе функции плотности вероятности. Для каждой точки данных средний сдвиг связывает ее с ближайшим пиком функции плотности вероятности набора данных. Учитывая набор точек данных, алгоритм итеративно назначает каждую точку данных ближайшему центроиду кластера. Определяется размер окна и вычисляется среднее значение точек данных в окне. Направление к ближайшему центроиду скопления определяется тем, где находится большинство ближайших точек. Таким образом, после каждой итерации каждая точка данных будет перемещаться ближе к тому месту, где находится наибольшее количество точек, что приводит к центру кластера. Затем окно сдвигается к вновь вычисленному среднему, и этот процесс повторяется до сходимости. Когда алгоритм останавливается, каждая точка назначается кластеру.
Среднее смещение можно использовать как алгоритм сегментации изображения. Идея состоит в том, что похожие цвета сгруппированы для использования одного цвета. Это может быть выполнено путем кластеризации пикселей изображения. Этот алгоритм действительно прост, поскольку есть только один параметр, которым можно управлять - размер скользящего окна. Вам не нужно знать количество категорий (кластеров) перед применением этого алгоритма, в отличие от K-средних. Обратной стороной среднего сдвига является высокая вычислительная нагрузка - O (n²). Выбор размера окна может быть нетривиальным. Кроме того, он плохо масштабируется с размером пространства функций.
5. Нечеткие K-режимы
Алгоритм кластеризации нечетких K-режимов является расширением K-режимов. Вместо того, чтобы назначать каждый объект одному кластеру, алгоритм кластеризации нечетких K-режимов вычисляет значение степени членства в кластере для каждого объекта в каждом кластере. Подобно нечетким K-средним, это достигается путем введения фактора нечеткости в целевую функцию. Алгоритм кластеризации Fuzzy K-Modes нашел новые применения в биоинформатике. Это может улучшить результат кластеризации всякий раз, когда присущие кластеры перекрываются в наборе данных.
6. Нечеткие C-средние
Нечеткие C-средние - это вероятностная версия кластеризации K-средних. Он связывает все точки данных со всеми кластерами, так что сумма всех ассоциаций равна 1. Влияние состоит в том, что все кластеры имеют непрерывную (в отличие от дискретных, как в K-средних) ассоциацию с каждым кластером относительно друг друга.
Алгоритм итеративно назначает и вычисляет центроиды кластеров так же, как K-средние, до тех пор, пока любая из критериальных функций не будет оптимизирована, чтобы сходимость не упала ниже заранее определенного порогового значения.
Преимущества этого алгоритма заключаются в том, что он не является строгим, как K-средние, при назначении и хорошо работает для перекрывающихся наборов данных. Однако у него есть тот же недостаток, что и у K-средних, заключающийся в предварительном предположении о количестве кластеров. Кроме того, низкое пороговое значение дает лучшие результаты, но требует больших вычислительных затрат.
7. Иерархическая кластеризация
Иерархическая кластеризация использует подход поиска групп в данных, так что экземпляры более похожи друг на друга, чем на экземпляры в других группах. Эта мера сходства обычно представляет собой евклидово расстояние между точками данных, но также могут использоваться Citi-block и геодезические расстояния.
Данные разбиты на кластеры в иерархическом порядке. Количество кластеров равно 0 вверху и максимуму внизу. Из этой иерархии выбирается оптимальное количество кластеров.
8. Максимизация ожиданий.
Максимальное ожидание использует систему оценки максимального правдоподобия и представляет собой трехэтапную процедуру. Первый шаг - это оценка, чтобы предположить параметры и распределение вероятностей для данных. Следующим шагом является загрузка данных в модель. Третий шаг - максимизация - настройка параметров модели для включения новых данных. Эти три шага повторяются итеративно для улучшения модели.
9. Минимальные остовные деревья
Алгоритм кластеризации с минимальным остовным деревом способен обнаруживать кластеры с нерегулярными границами. Метод кластеризации на основе MST может идентифицировать кластеры произвольной формы путем удаления несовместимых краев.
Алгоритм кластеризации создает MST с использованием алгоритма Крускала, а затем устанавливает пороговое значение и размер шага. Затем он удаляет те ребра из MST, длина которых превышает пороговое значение. Рассчитывается соотношение между расстоянием внутри кластера и расстоянием между кластерами. Затем пороговое значение обновляется путем увеличения размера шага. При каждом новом пороговом значении шаги повторяются. Алгоритм останавливается, когда из дерева больше нельзя удалить ребра. На этом этапе можно проверить минимальное значение отношения и сформировать кластеры, соответствующие пороговому значению.
MST ищет то оптимальное значение порога, при котором соотношение внутренних и внутренних расстояний минимально. Как правило, MST работает сравнительно лучше, чем алгоритм k-средних для кластеризации.
10. Модель гауссовой смеси.
Модель гауссовой смеси (GMM) - это вероятностная модель, которая предполагает, что экземпляры были сгенерированы из смеси нескольких гауссовых распределений, параметры которых неизвестны. В этом подходе мы описываем каждый кластер его центроидом (средним), ковариацией и размером кластера (весом). Все экземпляры, сгенерированные из одного гауссовского распределения, образуют кластер, где каждый кластер может иметь различную форму, размер, плотность и ориентацию.
GMM использовались для извлечения функций из речевых данных, а также широко использовались при отслеживании нескольких объектов. Параметры для моделей гауссовой смеси выводятся либо из максимальной апостериорной оценки, либо из итеративного алгоритма максимизации ожидания из хорошо обученной априорной модели.
