Это 11-й день моего участия в августовском испытании обновлений.Подробности о событии:Испытание августовского обновления

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

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

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

Алгоритм K-средних

$K$это количество кластеров. Это число выбрано искусственно. Алгоритм K-Means основан на центроидальном разбиении.

Алгоритм потока:

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

Оценка расстояния: евклидово расстояние или косинусное сходство

Описание алгоритма:

• $\mu^{(i)}$означает первый$i$Центр кластеризации,$x^{(i)}$означает первый$i$образцы,$m$Указывает количество образцов

Оптимизация алгоритма

K-Means также минимизирует стоимость кластеризации, а минимизируется сумма расстояний между всеми точками данных и связанными с ними центральными точками кластера.Введена функция стоимости K-Means:

$J(c^{(1)},...,c^{(m)},\mu^{(1)},...,\mu^{(K)})=\dfrac{1}{m}\sum\limits_{i=1}^{m}||x^{(i)}-\mu^{c^{(i)}}||^2$ $J$также называемыйФункция искажения

На самом деле, в первом цикле for при назначении центров кластеров образцам вы сокращаете$c^{(i)}$Понесенные затраты; во втором цикле for они уменьшаются$\mu^{(k)}$понесенные затраты.

определить значение k

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

Вот некоторые другие распространенные алгоритмы кластеризации:

Двудольный алгоритм K-средних

Алгоритм Bisection K-Means (bisecting kmeans), по сравнению с обычным K-Means, bisection K-Means не спешит рандомизировать K центров кластеров, а сначала классифицирует все точки в кластер, а затем кластер разбивается на два. Вычислите функцию стоимости (т. е. ошибку) каждого результирующего кластера, выберите кластер с наибольшей ошибкой, затем разделите его (т. е. минимизируйте ошибку) и повторяйте процесс, пока не будет достигнуто желаемое количество кластеров.

Ошибка принимает SSE (Sum of Squared Error), которая представляет собой сумму квадратов ошибок. Чем меньше SSE, тем более сконцентрированы объекты в кластере.

Алгоритм жадный, объем вычислений не маленький.

Алгоритм DBSCAN

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

Базовые концепты:

• $Eps$ Площадь: заданный радиус объекта$Eps$Окрестности внутри объекта называются$Eps$Площадь.
• $MinPts$: минимальное количество точек, содержащихся в данной окрестности, для определения точки$p$Является ли это основной частью кластера или граничными точками или шумом.
• основной объект: если объект$Eps$Окрестность содержит не менее$MinPts$Объект называется основным объектом.
• пограничная точка: граничная точка не является центральной точкой, но находится в окрестности центральной точки. Точки на краях плотных областей.
• точка шума: любая точка, которая не является ни центральной, ни граничной точкой. Точки в разреженных областях.
• Прямая плотность до: если$p$существует$q$из$Eps$по соседству и$q$является основным объектом, он называется объектом$p$от объекта$q$Отправление непосредственно плотности досягаемости.
• плотность до: если есть цепочка объектов$p_1,p_2,...,p_n,p_1=q,p_n=p$, за$p_i\in D(1\le i\le n)$,$p_{i+1}$да$p_i$примерно от$Eps$и$MinPts$непосредственно достижимая плотность, то объект$p$от объекта$q$о$Eps$и$MinPts$Достижимая плотность (densityreachable).
• связанная плотность: если объект существует$O\in D$, сделать объект$p$и$q$все из$O$о$Eps$и$MinPts$плотность достижима, то объект$p$прибыть$q$это о$Eps$и$MinPts$плотностно-связанный.
• кластеры на основе плотности: это самый большой набор объектов, связанных плотностью, основанный на достижимости плотности.
• шум: Объекты, не содержащиеся ни в одном кластере.

Алгоритм DBSCAN заключается в проверке значения каждой точки в наборе данных.$Eps$окрестности для поиска кластеров.

Поток алгоритма

Алгоритмы плюсы и минусы

Преимущество:

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

Недостаток:

• Параметры сложно подобрать (параметры очень сильно влияют на результаты)
• Многомерные данные несколько сложны (можно уменьшить размерность)