[Кластерный анализ] из серии «Классическое машинное обучение»

В «Политике Воюющих царств Ци Цэ III» есть такое предложение: «Рыбак рыбака видит издалека" используется для описания однотипных вещей, которые часто собираются вместе, а единомышленники собираются в группы, и наоборот. Так называемая наука есть не что иное, как описание нашего повседневного жизненного опыта и законов природы математическим языком , В машинном обучении есть еще такой тип алгоритма, алгоритм кластеризации, который основан на "Рыбак рыбака видит издалека"подумал о.

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

этоКак алгоритм кластеризации в машинном обучении делает это?? Прежде чем мы говорили о проблеме классификации, его выборочное пространство задается формулой (X,Y) составляют,назвать это особенностью,это метка, которая является дискретным значением, и если это непрерывное значение, это проблема регрессии.

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

Существует множество методов измерения сходства, в предыдущей статьеСуммируйте 12 общих показателей сходства данных:[Мера сходства] из серии «Классическое машинное обучение».

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

Метод деления
Иерархический подход
Методы, основанные на плотности
сеточный метод
модельный подход

Давайте обсудим их по очереди:

Метод деления

В методе деления для заданногонабор данных объекта, а количество кластеров(то есть количество разделяемых категорий), алгоритм деления организует объекты какразделение ( $k \leq n$ ). Основной принцип деленияВысокое сходство внутри кластеров(внутрикластерное сходство),низкое сходство между кластерами(межкластерное сходство). Классическими методами являются:K-meansи его варианты,K-中心点,CLARA,CLARANSЖдать.

K-means

k-meansалгоритм, также известный какk-平均илиk-均值, является широко используемым алгоритмом кластеризации или становится основой других алгоритмов кластеризации.Этапы алгоритма описываются следующим образом:

Предположим, что входная выборка $S=X_{1}，X_{2}，\cdots X_{m}$ , шаги алгоритма:

выберите начальныйцентры категорий $\mu_{1}$ , $\mu_{2}$ , $\cdots$ , $\mu_{k}$
для каждого образца $X_{i}$ , обозначьте его как расстояние от центра классанедавнийкатегории, а именно:

\text{label}_{i} =\text{argmin}_{1 \leq j \leq k}||X_{i}-\mu_{i}||

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

\mu_{j}=\frac{1}{|c_{j}|}\sum_{i \in c_{j}}x_{i}

Повторяйте последние два шага, пока изменение центра класса не станет меньше определенного порога.

Формальное понимание k-средних

ПомнитеЦентры кластеров $\mu_{1}$ , $\mu_{2}$ , $\cdots$ , $\mu_{k}$ , количество отсчетов в каждом кластере равно $N_{1}$ , $N_{2}$ , $\cdots$ , $N_{k}$ . Используйте квадрат ошибки как целевую функцию:

J(\mu_{1},\mu_{2} \cdots,\mu_{k})=\frac{1}{2}\sum_{j=1}^{K}\sum_{i=1}^{N_{j}}(x_{i}-\mu_{j})^{2}

Согласно идее выпуклой оптимизации, мы хотим взять его минимальное значение и найти его отношение к $\mu_{1},\mu_{2},\cdots,\mu_{k}$ , и установите его равным 0. имеют:

\frac{\partial J}{\partial \mu_{j}}=-\sum_{i=1}^{N_{j}}(x_{i}-\mu_{j})=0

может запускать:

\mu_{j}=\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}x_{i}

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

Вариант K-средних

Кластеризация K-Medoids (K-медианное расстояние)

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

Например: Массивы【1，2，3，4，100】Среднее значение22,видимо далеко не "большинство" данных【1，2，3，4】Это дальше, если его изменить на медиану массива из 3, в этом примере это более безопасно.Этот метод кластеризации $\text{k-Mediods}$ кластеризация(К-среднее расстояние).

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

Фактический процесс работыКак найти эти далекие точки выборки?? Общая практика такова: выборка случайным образом $X_{1}$ , затем вычислить расстояние между другими отсчетами и ним, а затем выбрать самое дальнее расстояние от него (или вероятность, пропорциональную расстоянию) в качестве следующего начального точечного отсчета $X_{2}$ , по необходимости разбивать на несколько типов кластеров и действовать по очереди, этот эффект часто немного лучше, чем случайно выбранная начальная точка.sklearnВнутри метод выбора начального значенияk-mean++,иsklearnОн будет рассчитан по умолчанию10раз, возьмите тот, у которого лучший результат, и верните его.

k-meansАлгоритм лучше влияет на такие данные, которые представляют собой смесь распределения Гаусса. После ротации данных эффект часто бывает нехорошим, и эффект не очень хороший для данных с неравной дисперсией.

Дихотомические k-средние

Для улучшенияK-meansАлгоритмы, у нас есть другие идеи, такие как二分k-means.

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

Мини-пакетный алгоритм k-средних

Если вместо усреднения всех выборок мы усредняли одну изbatchЕсли точка выборки усреднена, это может сделатьk-meansУскорение алгоритма (учитывается намного меньше точек выборки).

Сравнение преимуществ и недостатков алгоритма k-средних

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

Это классический алгоритм решения задач кластеризации, простой и быстрый. Его временная сложность $O(t\cdot n\cdot k)$ ,вэто количество итераций,количество образцов,Количество кластеров, на которые нужно разделить.
Алгоритм остается масштабируемым и эффективным для обработки больших наборов данных.
Это работает лучше, когда кластеры приблизительно гауссовы.

недостаток:

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

Иерархический подход

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

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

восходящая стратегия, постепенно объединять маленькие категории в большие категории, этот метод называетсяагломерат.конкретные методы: сначала рассматривайте каждый объект как кластер, затем объединяйте эти атомарные кластеры во все более и более крупные кластеры, пока не будет выполнено определенное конечное условие.Типичный алгоритмAGNESалгоритм.
нисходящая стратегия, большая категория постепенно делится на мелкие категории, этот метод называетсяРасколоть.конкретные методы: используется нисходящая стратегия, при которой все объекты сначала помещаются в кластер, а затем постепенно подразделяются на все более мелкие кластеры, пока не будет достигнуто определенное конечное состояние.Типичные алгоритмыDIANAалгоритм.

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

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

$d_{min}(C_{i},C_{j})=min_{p\in C_{i},p^{'}\in C_{j}}|p-p^{'}|$

максимальное расстояние: Расстояние между двумя самыми дальними образцами в двух наборах. Этот метод не очень стабилен при наличии выбросов.

$d_{max}(C_{i},C_{j})=max_{p\in C_{i},p^{'}\in C_{j}}|p-p^{'}|$

среднее расстояние: среднее попарных расстояний между двумя наборами образцов.

$d_{avg}(C_{i},C_{j})=\frac{1}{n_{i}n_{j}}\sum_{p\in C,p^{'}\in C_{j}}|p-p^{'}|$

$n_{i}$ это кластер $C_{i}$ количество объектов в $n_{j}$ это кластер $C_{j}$ количество объектов.

среднее расстояние:

$d_{mean}(C_{i},C_{j})=|m_{i}-m_{j}|$

$m_{i}$ это кластер $C_{i}$ среднее значение .

дисперсия: минимизировать сумму квадратов расстояний внутри кластеров и максимизировать сумму квадратов между кластерами.

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

Кроме того, существуют некоторые методы, такие какBRICHметод,ROCKМетоды иChameleonметод.

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

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

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

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

Классические методы:DBSCAN,OPTICS,DENCLUEЖдать.

Алгоритм DBSCAN

DBSCAN(Density-Based Spatial Clustering of Applications with Noise) является репрезентативным алгоритмом кластеризации на основе плотности. В отличие от методов деления и иерархической кластеризации, упомянутых выше,Он определяет кластер как самый большой набор плотно связанных точек., может разделять области с достаточно высокой плотностью на кластеры и может находить кластеры произвольной формы в «зашумленных» данных.

Прежде чем мы начнем описывать этот алгоритм, нам нужно определить некоторые понятия-существительные:

$\epsilon$ поле: заданный радиус объекта $\epsilon$ в поле, называемом объектом $\epsilon$ поле.

основной объект: если объект $\epsilon$ Поле содержит не менее минимального количестваобъект, объект называется основным объектом.

Прямая доступность плотности (Прямая плотность): Учитывая набор объектов,еслисуществуетиз $\epsilon$ внутри поля иЯвляетсяосновной объект, то объектот объектаВылеты доступны непосредственно из плотности. Другими словами, если объект известенот объектаОтправление доступно непосредственно по плотности, затемявляется основным объектом, т.к.Неясно, является ли это основным объектом или нет.

плотность до: если есть цепочка объектов $p_{1}$ , $p_{2}$ , $\cdots$ , $p_{n}$ ,правильно $p_{i}\in D$ ,( $1 \leq i \leq n$ ), $p_{i+1}$ От $p_{i}$ о $\epsilon$ инепосредственно достижимая плотность, то объектот объектао $\epsilon$ иПлотность достижимая. Достижимость плотности - это транзитивное замыкание достижимости прямой плотности, т.е.асимметричныйДа, только основные объекты взаимно достижимы по плотности (и, наоборот, эта точка может не быть основным объектом).

связанная плотность: если коллекция объектовсерединаесть объект, так чтообъектиОто $\epsilon$ иПлотность достижима, то объектиэто о $\epsilon$ исвязана плотность. Плотность соединения представляет собой симметричное отношение.

Из рисунка ниже легко понять приведенное выше определение, на рисунке, красные точкиосновной объект, потому что это $\epsilon$ поле имеет по крайней мере5образцы. Черный образецнепрофильные объекты. все основные объектыплотность прямаяОбразец находится внутри гиперсферы с центром на объекте красного ядра, и если он не находится внутри гиперсферы, прямой плотности нет. Основные объекты, соединенные зелеными стрелками на рисунке, состоят изплотность допримерная последовательность. при этих плотностях достижимые последовательности образцов $\epsilon$ Все образцы в поле взаимносвязанная плотностьиз.

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

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

Проверка каждой точки в наборе данных $\epsilon$ поле.

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

Процесс кластеризации завершается, когда ни в какие кластеры нельзя добавить новые точки.

Оценка алгоритма:

Вычислительная сложность $O(n^{2})$ , вычислительная сложность может быть уменьшена до. в параметре $\epsilon$ иПри правильных настройках,DBSCANАлгоритм может эффективно находить кластеры произвольной формы;

Но этот алгоритм очень чувствителен к параметрам;

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

сеточный метод

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

Функции: Объектом прямой кластеризации является пространство, а не объект данных.

преимущество: быстрая обработка

Классический метод:STINGиWaveClusterЖдать.

модельный подход

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

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

Классический метод: метод максимизации ожидания, кластеризация концепций, на основе нейронной сети и т. д.

Критерии оценки качества алгоритмов кластеризации

Когда мы разрабатываем алгоритм кластеризации, каков индекс оценки качества алгоритма кластеризации? Эта проблема называется мерой производительности кластеризации, также известной как «индекс эффективности кластеризации» (validity index). Если конечная используемая метрика производительности уточняется, ее можно напрямую использовать в качестве цели оптимизации процесса кластеризации, чтобы получить лучшие результаты кластеризации, соответствующие требованиям.

Существует примерно две категории показателей производительности кластеризации. Один из них — сравнить результаты кластеризации с определенным «эталонная модель"сравнивать, называется"внешние индикаторы"(внешний индекс); другой - непосредственно исследовать результаты кластеризации без использования какой-либо эталонной модели, которая называется "Внутренние показатели(внутренний указатель).

внешние индикаторы

Соедините образцы попарно, а затем определите 4 значения:

aдля эталонной моделипринадлежат к одному классуи в результатах кластеризациипринадлежат к одному кластеруколичество пар образцов.
bдля эталонной моделине в том же классеи в результатах кластеризациипринадлежат к одному кластеруколичество пар образцов.
cдля эталонной моделипринадлежат к одному классуи в результатах кластеризациине в одном кластереколичество пар образцов.
dдля эталонной моделине в том же классеи в результатах кластеризациине в одном кластереколичество пар образцов.

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

Коэффициент Жаккара(Коэффициент Жаккара) (JC):

FM-индекс(Индекс Фаулкса и Маллоуса) (FMI)

FMI=\sqrt{\frac{a}{a+b}\times \frac{a}{a+c}}

Индекс Рэнда(Индекс Рэнда) (RI)

вэто общее количество образцов.

Все результаты приведенных выше показателей производительности [0,1] интервал, чем больше значение, тем лучше. Существует также расширенная версия этого критерия оценки, которая корректирует коэффициент Рэнда (ARI(Adjusted Rand Index)), и аналогично этому есть скорректированная взаимная информация (AMI,Adjusted Mutual Information), который использует внутреннюю информационную энтропию. Я не буду вдаваться в подробности, и если вам интересно, вы можете обратиться к соответствующей информации.

Внутренние показатели

Мы выше层次方法изAGNESКак измерить расстояние в пределах выборки обсуждалось в алгоритме, Вот краткое изложение точек знаний из книги Чжоу Чжихуа-машинное обучение:

Сначала определим4расстояние:

— среднее расстояние между выборками внутри кластера.
максимальное расстояние между отсчетами в пределах кластера.
$dmin(C_{i},C_{j})$ для кластера $C_{i},C_{j}$ Минимальное расстояние между образцами.
$dcen(C_{i},C_{j})$ два кластера $C_{i},C_{j}$ Расстояние между центральными точками образца.

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

Индекс БД(Индекс Дэвиса-Булдина) (DBI)

D B I=\frac{1}{k} \sum_{i=1}^{k} \max _{i \neq j}\left(\frac{\operatorname{avg}\left(C_{i}\right)+\operatorname{avg}\left(C_{j}\right)}{d_{\operatorname{cen}}\left(C_{i}, C_{j}\right)}\right)

Индекс Данна(Индекс Данна) (DI)

D I=\min _{1 \leq i \leq k}\left\{\min _{i \neq j} \frac{d_{\min }\left(C_{i}, C_{j}\right)}{\max _{1 \leq l \leq k} \operatorname{diam}\left(C_{l}\right)}\right\}

Помимо вышеперечисленного, существуют однородность (кластер содержит только один класс выборок), полнота (подобные выборки отнесены к одному кластеру), однородность и полнота обычно не выполняются одновременно, поэтому их обычно взвешивают, чтобы получить меруV-measure. Существуют также силуэтные коэффициенты (Silhouette)Ждать.

мойИмя общедоступной учетной записи WeChat: Глубокое обучение Расширенное интеллектуальное принятие решенийИдентификатор официального аккаунта WeChat: Мультиагент1024Введение в публичный аккаунт: В основном исследуйте глубокое обучение, обучение с подкреплением, машинные игры и другой связанный контент! Ждем вашего внимания, добро пожаловать учиться и обмениваться прогрессом вместе!