Начало работы с кратким кластерным анализом

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

1. Введение

Технология кластерного анализа разрабатывалась почти 60 лет, и эта область все еще очень активна. $^{[1]}$ . Статус кластерного анализа отличается от других теорий машинного обучения, таких как классификация, SVM и т. д.во-первых, Кластерный анализ является междисциплинарной областью исследований.Большинство алгоритмов кластеризации требуют участия междоменных знаний (знания предметной области).Разные углы будут давать разные результаты кластеризации, поэтому нет единого измерения результатов кластеризации.стандарт;Второй, Существует множество алгоритмов в области кластерного анализа, но для этих алгоритмов сложно предложить общее деление (разделение понятий), и среди алгоритмов есть пересекающиеся понятия. Вышеуказанные причины мешают теории кластерного анализа формировать систематическую теоретическую систему, так что некоторые учебники только занижают некоторые теории кластерного анализа. Но нельзя отрицать, что кластерный анализ занимает очень важное место в реальных задачах.

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

Зачем нужен кластерный анализ?
Что такое кластерный анализ?
Как провести кластерный анализ?
Как оценить результаты кластерного анализа?

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

2 Причина и следствие кластерного анализа

У разных исследователей разные взгляды на область кластерного анализа, например, «Машинное обучение» профессора Чжоу Чжихуа. $^{[2]}$ начнется с измерения производительности и измерения расстояния, и профессор Хан Цзявэй $^{[3]}$ Определение и требования кластеризации будут обсуждаться с точки зрения инструмента для интеллектуального анализа данных. Хотя то, что мы узнаем в конце, непротиворечиво, независимо от того, как мы смотрим на кластеризацию, это может немного сбить с толку новичков. Например, когда я изучал кластеризацию, я надеялся, что учебник скажет мнеЗачем нужны методы кластеризации?, а затем как определить концепцию кластеризации и так далее. Таким образом, этот раздел начинается с самого существенного вопроса о кластеризации и отвечает на причины и следствия кластерного анализа.

2.1 Факторы кластерного анализа

Вопрос 1: Зачем нужен кластерный анализ?

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

Вопрос 2: Что такое кластерный анализ?

Из вопроса 1 мы знаем, что цель кластерного анализа состоит в том, чтобы найти неизвестные заранее сведения о классификации данных, среди которых классификационная информация стоит того понятия «кластер», которое мы теперь называем, и вещи сгруппированы вместе. Профессор Хан Цзявэй $^{[2]}$ Это понятие представлено более изысканным языком, а именно:

Cluster analysis or simply clustering is the process of partitioning a set of data objects (or observations) into subsets. Each subset is a cluster, such that objects in a cluster are similar to one another, yet dissimilar to objects in other clusters. The set of clusters resulting from a cluster analysis can be referred to as a clustering.

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

2.1 Результаты кластерного анализа

Вопрос 3: Как провести кластерный анализ?

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

Разделить на расстояние
Разделить по уровню
Разделить на оценку плотности
Разделить на оценку вероятности
По сетке

Различные методы деления имеют разные преимущества и недостатки (такие как форма кластера, размер набора данных и т. д.), и не существует алгоритма для всего. $^{[2]}$ . Для сходства (как правило, сходства в пространстве признаков, поэтому его также называют мерой расстояния) обычно существуют:

Сходство упорядоченных признаков, обычно используемые евклидово расстояние, расстояние Минковского и т. д.
Сходство неупорядоченных атрибутов, таких как VDM (метрика разницы значений).

Для получения подробной информации, пожалуйста, обратитесь к машинному обучению профессора Чжоу Чжихуа. $^{[2]}$ , и здесь повторяться не будем.

Вопрос 4: Как оценить результаты кластерного анализа?

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

Эмпирический метод, количество кластеров берется $\sqrt{\frac{n}{2}}$ ,вэто количество образцов.
Метод локтя, из которых обычно используется Gap Statistic $^{[4]}$ Метод будет подробно объяснен в третьей части.

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

Метод с учителем (внешний метод), то есть мы имеем ожидаемый результат кластеризации (реальный результат кластеризации), а затем сравниваем разницу между ожидаемым результатом и результатом кластеризатора, такого как BCubed. $^{[5]}$ алгоритм, который находится вscikit-learnВ библиотеке есть соответствующие реализации.
Неконтролируемый метод (внутренний метод), в настоящее время у нас нет ожидаемого результата кластеризации, поэтому мы можем оценить результат кластеризации только из сути кластеризации, то есть достаточно ли близко расстояние между кластерами и расстояние между кластерами достаточно большое, из которых чаще используется коэффициент силуэта, который также реализован в scikit-learn.

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

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

3 Алгоритмы кластеризации и методы оценки

До сих пор не существует очень точного метода классификации алгоритмов кластеризации, и некоторые исследователи грубо классифицируют алгоритмы кластеризации на две категории. $^{[1]}$ : методы разделения и иерархические методы, некоторые из которых сгруппированы в четыре категории. $^{[3]}$ : методы разделения, иерархические методы, методы на основе плотности и методы на основе сетки, а в последнее время более подробный $^{[6]}$ Метод деления, как показано на рисунке 3.1:

Рисунок 3.1: Классификация алгоритмов кластеризации, взятая из Rehioui, Idrissi, Abourezq и Zegrari [6]

Добавлен метод деления модельных методов/кластеризации, но даже при этих методах суммарного деления представленный алгоритм не обязательно является «чистым» (т.е. характеристики полностью относятся к этой категории), например CLIQUE (кластеризация в ВОПРОС) $^{[21]}$ Это алгоритм, основанный как на сетке, так и на плотности, и алгоритмы часто заимствуют идеи друг у друга. В этой статье будет описано несколько репрезентативных алгоритмов для следующей организационной структуры в объединенном виде на рисунке 1 (метод на основе моделей является расширенным содержанием и не будет описываться в этой статье).Все коды в этой статье можно найти в приложение.

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

Метод деления — один из двух классических процессов деления в кластерном анализе. По мере измерения расстоянияОбъекты наблюдения делятся накластеры (разделы), где $k \leq n$ . очевидно, когда k=n является крайним случаем метода деления, когда функция стоимости наименьшая (0). Среди них наиболее часто используется алгоритм, представленный KMeans.Поскольку метод деления основан на метрике расстояния, он очень хорошо находит сферические взаимоисключающие кластеры и может находить репрезентативные объекты каждого кластера, а также часто используется для сжатия. Однако, поскольку метод деления обычно требует вычисления расстояния между каждой парой объектов, он обычно хорошо работает на небольших наборах данных.Однако в последние годы исследователи создали хорошо масштабируемые и подходящие для крупномасштабных наборов данных.Метод деления, такой как как вариант KMeans MiniBatchKMeans $^{[7]}$ . В этом разделе в основном представлены KMeans и другой алгоритм PAM (Partitioning Around Medoids) вокруг центральной точки.

3.1.1 Метод центроидального деления KMeans

KMeans начинается смера вариации внутри кластераПо основанию деления, а именно:

E = \sum^{k}_{i=1} \sum_{p \in C_i} dist(p, c_i)^2 \tag*{(3.1)}

будетОбъекты наблюдения делятся наКластер, представленный центральной точкой (средней точкой) $C_1, C_2 , \cdots , C_k$ ,в $k \geq 2$ . Алгоритм KMeans обычно состоит из двух шагов:НазначениеиОбновлять, с начала(1)Алгоритм будет случайным образомвыберитецентральная точка, затем(2)будетКаждому объекту наблюдения присваивается принцип ближайшего по расстоянию (обычно евклидово расстояние).кластеры и, наконец,(3)Итеративно вычисляет (уравнение 3.1) эвристическим способом для получения новогоцентральную точку, повторяйте шаги (2) и (3) до тех пор, пока центральная точка не перестанет изменяться или не будет достигнуто заданное количество итераций. Подробнее о KMeans см. в разделе "Принцип KMeans, реализация и анализ".

Таким образом, KMeans прост в эксплуатации, что делает его предпочтительным кластеризатором для задач кластерного анализа. Однако KMeans также имеет много недостатков, таких как невозможность найти кластеры произвольной формы.На рисунке 3.2, поскольку KMeans основан на евклидовом расстоянии, он не может найти кластеры, похожие на концентрические круги или U-образные кластеры. Мало того, KMeans используетЗначитЭта более слабая статистика также делает ее чувствительной к выбросам (шуму). Более того, поскольку на шаге (1) используется стратегия случайной инициализации центральной точки, невозможно гарантировать сходимость алгоритма KMeans к глобальному оптимальному решению, поэтому необходимо запускать KMeans несколько раз для получения удовлетворительного результата. результат кластеризации.

Рисунок 3.2: Производительность KMeans на кластерах произвольной формы

До сих пор было разработано множество вариантов KMeans для решения задач кластеризации с различными потребностями. Когда обрабатываемые данные являются атрибутом категории (номинальным атрибутом), использование среднего значения может быть бессмысленным, в этом случае вместо среднего значения можно использовать моду, то есть алгоритм К-режима. $^{[8]}$ , который реализует K-режим на Pythonсторонняя библиотека; Когда необходимо иметь дело с наборами данных большего масштаба, KMeans кажется растянутым, поэтому эффективным методом является выбор набора данных соответствующего масштаба для множественного обучения, такого как MiniBatchKMeans, которыйалгоритмРеализуется scikit-learn в качестве стандартного инструмента, при наличии шума или выбросов в данных результаты кластеризации, сгенерированные алгоритмом KMeans, имеют большое отклонение от реальных результатов, точки наблюдения заменяют средние точки, как в алгоритм K-medoids, упомянутый в разделе 3.1.2.

Несмотря на то, что сам KMeans является очень зрелым, многие новые варианты были разработаны один за другим, и даже история KMeans — это микрокосм истории развития кластерного анализа. Более подробную информацию о KMeans можно найти в Jain $^{[1]}$ статья.

3.1.2 Метод центрального деления PAM

Чтобы уменьшить влияние выбросов на результаты кластеризации, Кауфман и Руссо $^{[9]}$ Разбиение по центру было предложено в 1987 году, а популярной реализацией является K-medoids, как показано на рис. 3.3. Алгоритм K-medoids, как и KMeans, можно разделить на два основных этапа: выделение и обновление в начале(1)случайным образом в наборе данныхвыберитеЦентральная точка,Потом(2)Все остальные объекты наблюдения привязываются к каждой центральной точке по принципу ближайшего для формированиякластеры и, наконец,(3)случайно выбранныхнецентральные объекты $o_{random}$ Попробуйте заменить исходный центральный объект,рассчитать $o_{random}$ Средняя разница в стоимости расстояния,как S<0 , затем используйте $o_{random}$ Заменить исходный центральный объект, в противном случае продолжайте поиск, пока не будут пройдены все объекты. Алгоритм итеративно выполняет шаги (2)(3) до тех пор, пока центральный объектбольше не меняется. Код реализации алгоритма можно найти в файле приложения.

Рисунок 3.3: Алгоритм K-medoids, взятый у Хана Дж. [3]

Очевидно, расчет шага (3) очень трудоемок, когда n,k Когда K-medoids относительно велики, вычислительные затраты времени намного больше, чем у KMeans.Хотя алгоритм K-medoids может иметь хорошие возможности по борьбе с шумом, его трудно хорошо работать с большими наборами данных. Поэтому Кауфман и Руссеу в 1990 году предложили основанный на выборке метод центрального разделения CLARA (кластеризация больших приложений). $^{[10]}$ Предлагаемый алгоритм K-medoids устраняет недостатки больших данных.Теоретически, пока распределение данных выборки достаточно близко к исходному распределению данных, можно найти наилучшую центральную точку, но это приведет к качеству CLARA. результаты кластеризации в зависимости от выборки, хорошие или плохие. Поэтому Рэймонд и Джиавэй Хан предложили более эффективный CLARANS (кластеризация больших приложений на основе рандомизированного поиска). $^{[11]}$ Алгоритм, основанный на случайном поиске глобального оптимального решения, алгоритм реализован на Pythonбиблиотека пиккластеризациивыполнить. Также Шуберт и Руссеу ${^{[22]}}$ В 2019 году был предложен более быстрый алгоритм K-Medoids, и заинтересованные читатели могут проверить его самостоятельно!

3.1.3 Резюме

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

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

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

\begin{aligned} & 最小距离: dist_{min}(C_i, C_j) = \min_{p \in C_i, p^{'} \in C_j} \{ | p - p^{'}| \} \qquad & (3.2) \\ & 最大距离: dist_{max}(C_i, C_j) = \max_{p \in C_i, p^{'} \in C_j} \{ | p - p^{'}| \} \qquad & (3.3) \\ & 均值距离: dist_{mean}(C_i, C_j) = | m_i - m_j | \qquad & (3.4) \\ & 平均距离: dist_{avg}(C_i, C_j) = \frac{1}{n_i n_j} \sum_{p \in C_i, p^{'} \in C_j} | p - p^{'}| \qquad & (3.5)\\ \end{aligned}

где, если алгоритмкратчайшее расстояниеВ качестве основы деления алгоритм добавит отрезок линии в качестве ребра между различными кластерами, чтобы сформировать максимально связный граф, также известный какОдносвязный алгоритм, под изображением понимается, что имеется только один связанный компонент (линия), связывающий все кластеры, как показано в ситуации на рис. 3.4(b), весь набор данных связан линией. И если этомаксимальное расстояниеВ качестве основы деления в это время формируется самый большой полный граф, также известный какАлгоритм полной связи, который понимается как кластер, состоящий из нескольких полносвязных подграфов, как показано на рис. 3.5(c). В этой статье в разделе 3.2.1 описываются основные принципы агломеративной и разделительной иерархической кластеризации, а в разделе 3.2.2 обсуждаются некоторые другие популярные алгоритмы крупномасштабной иерархической кластеризации.

Рисунок 3.4: Одиночная ссылка и полная ссылка, взятые у Хана Дж. [3]

3.2.1 Агломеративная и разделительная иерархическая кластеризация

Агломеративная иерархическая кластеризация использует метод объединения кластеров снизу вверх и, наконец, объединяет n узлов в 1 кластер (корневой корень), аналогичноАлгоритм минимального связующего дерева. нужно всего лишьКластеризацию можно выполнить за несколько итераций, но недостатком является невозможность исправления предыдущих операций. Алгоритм агломерационной кластеризации также является наиболее часто используемым алгоритмом статической иерархической кластеризации, и соответствующие классы алгоритмов реализованы в библиотеках машинного обучения, таких как scikit-learn.AgglomerativeClustering, профессор Чжоу Чжихуа использовал данные арбуза 4.0 $^{[2]}$ чтобы показать агломеративную иерархическую кластеризацию на основе полных ссылок, мы также можем попытаться воспроизвести результаты, используя его данные, используяSciPyкоторый предоставилdendrogramИнструмент может использовать дендрограмму для отображения результатов кластеризации, как показано на рисунке 3.5 (за исключением того, что порядок другой, результаты классификации одинаковы), горизонтальная ось соответствует номеру выборки, а вертикальная ось представляет собой расстояние выборки.

Рисунок 3.5: Алгоритм кластеризации полной ссылки Watermelon Data 4.0

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

\begin{aligned} C_1 & = \{1, 2, 3, 4, 21, 22, 26, 29\}, \\ C_2 &= \{23, 24, 25, 27, 28, 30\}, \\ C_3 &= \{5, 7, 9, 13, 14, 16, 17\}, \\ C_4 &= \{6, 8, 10, 11, 12, 15, 18, 19, 20 \}。 \end{aligned}

У раздельной иерархической кластеризации больше проблем, чем у метода агломерации. Самая большая проблема заключается в том, как превратить большой кластер в маленький кластер. Существуют различные методы разделения на взаимоисключающие кластеры.Когда задача достаточно велика, она является NP-сложной. Следовательно, эвристический алгоритм можно использовать только в ущерб точности. Эта стратегия обычно не может изменить предыдущую операцию. Поэтому алгоритм разделения обычно не используется в отрасли, и ему уделяется меньше внимания в академическом мире, чем когезионному алгоритму. тип.Результат исследования Tengke Xiong $^{[12]}$ Алгоритм DHCC (разделительная иерархическая кластеризация категориальных данных) и др. используется для обработки данных номинальных атрибутов, и этот алгоритм также обладает хорошей масштабируемостью и подходит для больших наборов данных.

3.2.2 Современная популярная иерархическая кластеризация

Хотя классическая иерархическая кластеризация обладает очень хорошим потенциалом визуализации, она будет очень слабой перед лицом больших данных, и после того, как каждый слой будет разделен, его нельзя будет модифицировать, и, скорее всего, будет упущено оптимальное решение. Чтобы устранить ограничения различных аспектов иерархической кластеризации, современные методы иерархической кластеризации приняли стратегию составной кластеризации, то есть в сочетании с другими методами кластеризации: методы разделения, такие как BIRCH (сбалансированное итеративное сокращение и кластеризация с использованием иерархий). $^{[13]}$ или методы плотности, такие как алгоритм Хамелеона $^{[14]}$ Ждать.

Алгоритм BIRCH (переводится как Balanced Iterative Reduction and Clustering with Hierarchy) использует дерево признаков кластеризации для описания кластера, а признак кластеризации (CF) представляет собой трехмерный вектор:

CF=\langle n, LS, SS\rangle \tag*{(3.6)}

вэто кластерколичество образцов,(Линейная сумма) — это линейная сумма n выборок,(Сумма квадратов) — это сумма квадратов n выборок. Центроиды кластеров можно легко получить с помощью CF. x_0 ,радиус R_0 и диаметр D_0 Эти статистические данные:

\begin{aligned} x_0 & = \frac{\sum^{n}_{i=1}x_i}{n} = \frac{LS}{n} \qquad \qquad &(3.7) \\ R_0 & = \sqrt{\frac{\sum^{n}_{i=1}(x_i - x_0)^2}{n}} & (3.8) \\ D_0 & = \sqrt{\frac{\sum^{n}_{i=1} \sum^{n}_{j=1} (x_i - x_j)^2}{n (n-1)}} = \sqrt{\frac{2nSS - 2LS^2}{n(n-1)}} &(3.9) \end{aligned}

где радиус R_0 и диаметр D_0 оба отражают кластеркомпактность и для любых двухне пересекатьсяДля кластеров из их КФ аддитивны. как C_1, C_2 — два непересекающихся кластера, а соответствующая КФ есть $CF_1=\langle n_1, LS_1, SS_1 \rangle, CF_2=\langle n_2, LS_2, SS_2 \rangle$ , объединитьстать C_3 ,но C_3 КФ это: $CF_3 = \langle n_1 + n_2, LS_1 + LS_2, SS_1 + SS_2 \rangle$ . Алгоритм объединяет идеи иерархической кластеризации и секционированной кластеризации, которые могут адаптироваться к обучению крупномасштабных данных и компенсировать недостатки метода агломерации.CF-Tree (CF-Tree) — высоко сбалансированное дерево, дерево CF имеет два важных параметра: фактор ветвления (Branch factor)и порог,вопределяет максимальное количество потомков нелистовых узлов, то есть максимальное количество ветвей, иОпределяет максимальный диаметр хранилища конечных узлов.. Более одного из двух параметров приведет к разделению, подобно дереву B+. BIRCH — метод динамической иерархической кластеризации, судя по характеристикам CF, этот метод хорошо находит круговые кластеры и поддерживает инкрементную кластеризацию, поэтому его часто используют для задач кластеризации потоковых данных. scikit-learn такжевыполнитьАлгоритм БЕРЧ.

Хамелеон также представляет собой динамический иерархический алгоритм кластеризации, который сочетает в себе характеристики метода плотности и вводит степень взаимосвязи между кластерами. RI(C_i, C_j) и межкластерная близость RC(C_i, C_j) , две метрики вместе описываютстепень сходства. Благодаря сочетанию метода плотности метод может находить кластеры произвольной формы, и в то же время он работает лучше, чем метод DBSCAN, в многомерных данных. Читатели, нуждающиеся в подробном изучении Karypis et al. $^{[14]}$ статья.

Кроме того, существуют некоторые методы иерархической кластеризации, основанные на оценке вероятности, такие как байесовская иерархическая кластеризация. $^{[15]}$ , Иерархическая кластеризация с использованием оценки вероятности не требует поиска подходящей метрики соединения и может хорошо справиться с проблемой отсутствующих данных, а цель оптимизации, основанная на оценке вероятности, ясна, и может напрямую решить глобальное оптимальное решение без вышеупомянутого Тот же метод попадает в локальную ловушку. Однако недостатком такого алгоритма является то, что при относительно большом количестве данных вычислительные затраты на оценку параметров огромны.

3.2.3 Резюме

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

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

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

Чтобы преодолеть свою неспособность находить произвольные кластеры, исследователи пересматривают процесс деления кластеров.Одним из фактов является то, что в достаточно большом пространстве данных шум всегда разрежен, в то время как реальные кластеры всегда плотны, поэтому существует плотность- метод разделения на основе. Со стратегией деления возникает вопрос, как определить сходство? Другими словами, как именно он считается плотным? Боюсь, что единого стандарта для этой задачи пока трудно найти, как трудно найти абсолютно единую метрику расстояния для метода деления и иерархического метода. Например, знаменитый DBSCAN (пространственная кластеризация приложений с шумом на основе плотности). $^{[16]}$ Алгоритм требует от пользователя ручной настройки параметров плотности; чтобы преодолеть недостатки DBSCAN, требующие установки глобальных параметров, Ankerst et al. $^{[17]}$ Алгоритм OPTICS (Ordering Points To Identification the Clustering Structure) был придуман для выявления плотных кластеров путем кластерной сортировки, но ему все равно приходилось вручную задавать экстенсивные параметры плотности; чтобы полностью избавиться от ограничения параметров, Гиннебург и Кейм $^{[18]}$ Предлагается алгоритм DENCLUE (DENsity-based CLUstEring), основанный на оценке функции плотности, который использует гауссовуФункция ядраВ качестве меры подобия пользователям не нужно рассматривать проблему эмпирических параметров. В этом разделе подробно представлен основной принцип DBSCAN и его использование в Python в разделе 3.3.1, алгоритм OPTICS в разделе 3.3.2, а также принцип DENCLUE и разработка его альтернативного алгоритма в разделе 3.3.3.

Рисунок 3.6: Кластеры произвольной формы

3.3.1 Алгоритм DBSCAN

Стратегия деления DBSCAN: по заданному радиусу соседства $\varepsilon$ и как минимум количество объектов, которые нужно включить в окрестности MinPts Для определения плотной области наибольшая плотная область, связанная по плотности, образует кластер (принцип алгоритма аналогичен задаче нахождения наибольшего связного блока). Из стратегии разделения алгоритма DBSCAN может отличить шум. В алгоритме DBSCAN есть 3 очень важных понятия:

Концепция 1: Основной объект Основной объект относится к объектув радиусе его окрестности $\varepsilon$ Существует не менееобъект. Основной объект является опорным объектом плотной области, и его функция заключается в непрерывном обнаружении плотно связанных объектов. Кластер может иметь много основных объектов.
Концепция 2: непосредственная доступность по плотности для основного объектаи объект,еслисуществуетиз $\varepsilon$ - внутри поля, тодоступен изДостижима прямая плотность. В это время, еслитакже является основным объектом, можно также сказать, чтоОтПрямая плотность достижима, еслине является основным объектом, это ошибка. Функция прямой достижимости по плотности состоит в том, чтобы учесть все объекты, которые могут быть напрямую достижимы по плотности от основного объекта, и найти плотные области.
Концепция 3: Плотность связана для основного объектаи два объекта,и $p_1 \in A_1, p_2 \in A_2$ , то еслидоступны изнепосредственно плотность достижима, тоЭто связано с плотностью. Существует разница между связностью по плотности и достижимостью по плотности, связность по плотности является отношением эквивалентности, а достижимость по плотности не эквивалентна, если только оба они не являются основными объектами. Функция связи плотности состоит в том, чтобы соединить несколько плотных областей с достижимой плотностью в большую плотную область, то есть сформировать кластер.

Алгоритм DBSCAN начинается с(1)набор данныхВсе объекты отмечены как"unvisited",Потом(2)случайный выбородин из"unvisited"Объект, отметьте как"visited",тогда(3)экзамениз $\varepsilon$ - содержит ли окрестности MinPts объект, или если онСоздайте новый кластер и добавьте все объекты в окрестности в очередь на наблюдение, если нет, отметьтедля шума. Наконец(4)Продолжить из очереди или набора данных для наблюденияудалить объектШаг (3) выполняется до тех пор, пока очередь не опустеет иНет в"unvisited"объект до. Псевдокод показан на рис. 3.7.

Рисунок 3.7: Псевдокод DBSCAN, взятый у Хана Дж. [3]

В sckit-learn есть соответствующая реализация алгоритма DBSCAN, просто задайте радиус окрестности $\varepsilon$ и соседний порог MinPts То есть на рис. 3.8 показана способность DBSCAN к кластеризации кластеров произвольной формы. Судя по результатам, DBSCAN почти соответствует ожидаемым результатам кластеризации.

Рисунок 3.8: DBSCAN обрабатывает кластеры произвольной формы

Но, как было сказано ранее, способность DBSCAN к кластеризации зависит от радиуса соседства. $\varepsilon$ и соседний порог MinPts Однако это часто является результатом опыта, поэтому использование алгоритма DBSCAN требует внедрения большого количества знаний предметной области, чтобы получить удовлетворительный результат кластеризации.

3.3.2 Алгоритм ОПТИКА

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

Концепция 1: ядро-расстояние объекта p

для любого объектанайдет порог наименьшего радиуса $\varepsilon^{'}$ , $\varepsilon^{'}$ называетсяосновное расстояние, еслине является основным объектом (см. 3.3.1), тоРасстояние до ядра не определено. Роль этого базового расстояния состоит в том, чтобы максимизироватьСтаньте основным объектом, то есть автоматическим обнаружением кластеров, очевидно, еслиэто шум, тоЭто должно быть определено.для различных основных объектовТот $\varepsilon^{'}$ Значения, скорее всего, будут другими, что является одним из отличий от DBSCAN.
Концепция 2: Достижимость-расстояние

для объектов,еслиявляется основным объектом, тоОтПлотность достижима (согласуется с DBSCAN), на этот разУстановите достижимое расстояние на $max\{core-distance(o), dist(p, o)\}$ ,еслине является основным объектом, топрибытьнеопределенный. Очевидно,Весьма вероятно, что до каждого основного объекта одновременно есть достижимые расстояния, а ОПТИКА фокусируется только на кратчайшем достижимом расстоянии, чтобы можно было найти наиболее подходящую структуру кластера. Функция достижимого расстояния состоит в том, чтобы сделать кластеры с близкими расстояниями относительно близкими после их сортировки, то есть получить структуру кластеров.

Еще одно отличие состоит в том, чтоOrderSeedsСтруктура данных таблицы, в которой хранится каждый объектpКратчайшее достижимое расстояние до основного объекта. Еще одно интересное применение OPTICS — визуализация структуры кластера. Для высокоразмерных данных нам сложно наблюдать всю картину, но ОПТИКА сортирует все данные по достижимому расстоянию и отображает его, чтобы увидеть структуру кластеров.На рисунке 3.9 4 кластера. C_1, C_2, C_3, C_4 , используя достижимое расстояние (вертикальная ось) и результат сортировки (горизонтальная ось) для отображения кластера, можно увидеть, что есть четыре пустых области (выпуклые области), которые могут отражать реальное положение кластера.

Рисунок 3.9: ОПТИКА для визуализации данных Взято из Анкерста, Брейнига и Кригеля [16] с изменениями.

3.3.3 Основная идея алгоритма DENCLUE

Будь то DBSCAN или OPTICS, это значение радиуса $\varepsilon$ чувствительный, большой $\varepsilon$ приведет к тому, что кластер будет недостаточно компактным, но слишком маленьким $\varepsilon$ приведет к неполной кластеризации. Для решения этой проблемы Hinneburg et al. $^{[18]}$ Вводится непараметрический метод оценки в статистике, оценка плотности ядра, и DENCLUE использует ядро Гаусса для оценки плотности набора объектов, подлежащих кластеризации. Его точка локального максимума (т.е. решение) называется аттрактором плотности x^* , каждая пара точек притяжения плотности определяет линию не выше шумового порога $\xi$ Связанный путь , находит кластеры любой формы с помощью такого метода разделения плотности. Из-за ограничений по объему алгоритм DENCLUE здесь подробно не обсуждается.

С момента разработки DENCLUE было разработано множество вариантов алгоритмов, таких как Rehioui et al. $^{[19]}$ Предлагаемый алгоритм DENCLUE-IM может работать с более сложными типами данных и задачами кластеризации большего объема данных, и заинтересованные читатели могут изучить его самостоятельно.

3.3.4 Резюме

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

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

Если различать с точки зрения деления, то все упомянутые выше методы можно рассматривать как методы деления, управляемые данными. $^{[3]}$ , то есть фокус находится на самих данных, а от данных отделяется ряд пробелов. Метод на основе сетки — это метод пространственного разделения, то есть с точки зрения входного пространства входное пространство делится на ряд подпространств, в которые встраиваются данные. Метод разделения заключается в использовании сетевой структуры данных с несколькими разрешениями для квантования пространства объекта на конечное число единиц. Разные алгоритмы используют разные меры подобия, если STING (STATistical INformation Grid) $^{[20]}$ Иерархическая кластеризация выполняется с использованием статистики в качестве метрики, тогда как CLIQUE представляет собой кластеризацию плотности подпространства. CLIQUE — один из наиболее часто используемых алгоритмов кластеризации сетки.

3.4.1 STING: метод кластеризации статистической сетки

STING использует многослойность и рекурсию для разделения входного пространства, и каждый высокоуровневый разделяется на несколько низкоуровневых единиц, как показано на рис. 3.10. (i-1) Ячейки слоя делятся наЧетыре ячейки слоя, каждая ячейка будет предварительно хранить некоторую статистическую информацию из ячеек нижнего уровня, такую как среднее значение, стандартное отклонение, максимальное и минимальное значения и т. д. Пользователь может предварительно указать распределение данных. Нижний уровень может быть примерно равен результату кластеризации DBSCAN.Когда запрос запроса сгенерирован, STING будет запрашивать связанные ячейки сверху вниз до нижнего уровня.

Рисунок 3.10: Иерархия STING, взятая из Ванга, Янга и Мунца [20]

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

3.4.2 CLIQUE: Метод кластеризации плотности подпространства

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

Алгоритм CLIQUE имеет две фазы работы:

Фаза 1 (разделение и связывание): CLIQUEПространство многомерных данных разбивается на несколько непересекающихся подпространств по каждому измерению, после чего порог плотности идентификации превышается, а затем итеративно свяжите перекрывающиеся области в каждом подпространстве.
Второй этап (синтез): CLIQUE синтезирует несколько плотных единиц, полученных на первом этапе, в максимально плотную область. Используя жадный алгоритм, начните с любой плотной единицы, чтобы найти наибольшую площадь, покрывающую эти плотные единицы, пока не будут покрыты все плотные единицы в этой области. Повторяйте этот шаг до тех пор, пока все данные не будут перезаписаны.

Хотя CLIQUE может автоматически находить подпространства, содержащие кластеры высокой плотности, результаты его кластеризации сильно зависят от порога плотности.настройки, как показано на рис. 3.11 и рис. 3.12 соответственно l=10 и l=20 Ситуация кластеризации , ожидаемый результат кластеризации должен быть кластером из 2 концентрических кругов, и когда l=10 , на рис. 3.11(a) видно, что этому порогу соответствует много плотных областей, поэтому два кластера очень похожи, в результате чего в конечном результате кластеризации получается только один кластер, как показано на рис. 3.11(b). при регулировке l=20 Впоследствии на рис. 3.12(а) видно, что расстояние между кластерами увеличивается, и CLIQUE может найти две самые плотные области и, скорее всего, объединить их в два взаимоисключающих кластера, как показано на рис. 3.12(б).

Рисунок 3.11: Результаты кластеризации CLIQUE с коэффициентом плотности сетки 10

Рисунок 3.12: Результаты кластеризации CLIQUE с коэффициентом плотности сетки 20

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

3.5 Оценка качества кластеризации

До сих пор мы узнали о нескольких репрезентативных алгоритмах в области кластерного анализа, Общие шаги кластеризации всегда одинаковы, и определены процесс разделения и мера сходства. Многие из наборов данных, использованных в этой статье, на самом деле представляют собой размеченные данные, но для неразмеченных данных, как мы можем судить, хорошие или плохие результаты кластеризации? Начнем с двух аспектов: (1) соответствует ли количество разделенных кластеров? (2) Достаточно ли хорошее качество кластеризации? В этом разделе мы обсудим оба эти вопроса.

3.5.1 Определение количества кластеров

Алгоритмы, такие как K-Means, требуют, чтобы пользователь установил ожидаемое количество кластеров, например, метод сетки требует, чтобы пользователь определил степень детализации и т. д. Они требуют от нас правильной оценки конечного числа кластеров, в противном случае результаты кластеризации не имеют практического значения. Из предыдущего введения мы знаем, что количество кластеров имеет две крайности: когда количество кластеров равно 1 или когда количество кластеров равно 1.Время. Очевидно, что ни то, ни другое нежелательно, но как 1～n Выберите подходящее число между ними? Если мы используем (уравнение 3.1) для измерения суммы ошибок кластеризации, как показано на рис. 3.13, в (а) мы решим, что число кластеров, равное фактически 2, является лучшим выбором, а в (б) чем больше количество кластеров кластеры, тем меньше вариация внутри кластера, что объясняет, почему, когда кластер, ошибка минимальна.

Рисунок 3.13: Внутрикластерная вариограмма, взятая из Тибширани, Вальтера и Хасти [22].

Очевидно, что ошибка не может быть использована в качестве эталона для измерения количества кластеров.Существуют два широко используемых метода: (1) эмпирический метод и (2) метод локтя.Эмпирический метод обычно принимает количество кластеров как $\sqrt{\frac{n}{2}}$ , очевидно, подходит не для всех сценариев, а метод колена применим в большинстве случаев, как показано на рис. 3.13(b). Очевидно, что колено появляется в положении 2, но что, если распределение данных не является приблизительно гауссовым? В это время положение локтя неочевидно, потому что кривая ошибок будет плавной. Поэтому в этом разделе будет представлена статистика пробелов, предложенная Тибширани, Вальтером и Хасти. $^{[4]}$ метод, который использует сходство распределения для определения наиболее подходящего количества кластеров. Чтобы понять эту концепцию, нам сначала нужно знать тот факт, что если распределение набора данных является однородным, то результаты кластеризации этого набора данных не имеют практического значения, поскольку кластеры, генерируемые равномерным распределением, случайны. Идея Gap Statistic состоит в том, чтобы предположить, что тест сравнивает распределение реальных данных с эталонным распределением (по сути, с равномерным распределением) для каждого неопределенного количества кластеров.По мере увеличения количества кластеров распределение реальные данные увеличиваются Значение функции ошибок и значение функции ошибок эталонного распределения должны уменьшаться одновременно, и в методе локтя мы знаем, что будет точка перегиба, когда наиболее подходящее количество кластеров появляется, но для равномерного распределения количество кластеров не равно.Это не чувствительно, поэтому в это время будет глобальный наибольший разрыв (Gap) в значениях функции ошибок двух распределений, так что количество кластеров, в которых появляется наибольший разрыв, является оптимальным решением. Итак, у нас есть определение функции разрыва (Gap):

\tag*{(3.10)} Gap(k) = \frac{1}{B}\sum_{n}log(W^{*}_{kb}) - log(W_k)

вколичество кластеров,количество эталонных дистрибутивов, W_k количество кластеровЗначение ошибки ниже, $W^{*}_{kb}$ количество кластеровследующийЗначение ошибки эталонного распределения, доказательство этой теории, можно найти в статье Тибширани и др. Цель Gap Statistic – сделать $Gap(\cdot)$ максимум. Конкретная реализация кода показана в файле приложения к этой статье.

Затем мы можем попытаться использовать Gap Statistic для оценки составного набора данных из двух гауссовских кластеров и арбузных данных Чжоу Чжихуа 4.0. Как показано на рис. 3.14, для набора данных, состоящего из двух гауссовых кластеров, максимальный разрыв появляется в K=2 позиции, в соответствии с нашими ожидаемыми результатами. В данных об арбузах 4.0, использованных на рис. 3.15, наибольший разрыв приходится на K=4 , что также соответствует ожидаемым результатам данных по арбузам. $^{[2]}$ .

Рисунок 3.14: Кластер Гаусса и статистика пропусков

Рисунок 3.15: Данные по арбузам 4.0 и статистика пробелов

3.5.2 Оценка качества кластеров

После того, как у вас есть подходящее количество кластеров, нужно рассмотреть возможность оценки результатов различных алгоритмов кластеризации. Например, для кластера произвольной формы на рис. 3.6, предполагая, что мы не знаем истинного распределения данных, как нам выбрать использование KMEANS, DBSCAN и OPTICS для кластеризации? Как правило, существует две метрики для оценки качества кластеров: метрики контролируемой оценки и метрики неконтролируемой оценки. Это в scikit-learnmetricВ комплекте есть соответствующие инструменты.

(1) Показатели контролируемой оценки

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

from sklearn.metrics import v_measure_score

На данных концентрического круга мы тестируем оценки KMEANS, DBSCAN и OPTICS соответственно:

-------------------- Circle Datasets --------------------
KMeans spended time: 0.03s, and got score 0.00
DBSCAN spended time: 0.01s, and got score 1.00
OPTICS spended time: 0.90s, and got score 1.00
---------------------------------------------------------

Результаты оценки будут в [0, 1] интервал, счетЭто говорит о том, что качество кластеризации очень высокое.

(2) Показатели неконтролируемой оценки

По сравнению с контролируемой, неконтролируемая оценка является более сложной. После того, как у нас нет объекта для ссылки, мы можем начать только с самих данных. Наивная стратегия состоит в том, чтобы рассматривать разделение между кластерами и компактность внутри кластеров. Например, коэффициент силуэта, есть два важных показателя коэффициента силуэта. a(o) и b(o) ,в:

\tag*{(3.11)} a(o) = \frac{\sum_{o^{'} \in C_i, o \neq o^{'}} dist(o, o^{'})}{|C_i| - 1}

представляет собой компактность кластера, которому принадлежит объект o,

\tag*{(3.12)} b(o) = \min_{C_j:1 \leq j \leq k, j \neq i } \lbrace \frac{\sum_{o^{'} \in C_j} dist(o, o^{'})}{|C_j|} \rbrace

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

\tag*{(3.13)} s(o) = \frac{b(o) - a(o)}{\max \{ a(o), b(o)\}}

очевидно, когдаОн более компактен с кластером, к которому принадлежит, и удален от других кластеров, т. е. b(o) > a(o) час, s(o) Это положительное число, и чем ближе оно к 1, тем выше качество кластеризации. когдаКаждый объект кластера, к которому он принадлежит, имеет большое расстояние и близок к другим кластерам, т. е. b(o) < a(o) временами, s(o) Это положительное число, и чем оно меньше, тем хуже результат кластеризации. Используйте соответствующий инструмент в scikit-learn:

from sklearn.metrics import silhouette_score

Но одним недостатком коэффициента силуэта является то, что он будет смещен в сторону круглых кластеров. Точно так же следующие результаты получены путем сравнения алгоритмов KMeans, DBSCAN и OPTICS с использованием коэффициентов силуэта в наборе данных концентрических окружностей:

-------------------- Circle Datasets (without real labels)--------------------
KMeans spended time: 0.04s, and got score 0.35
DBSCAN spended time: 0.01s, and got score 0.11
OPTICS spended time: 0.98s, and got score 0.11
------------------------------------------------------------------------------

В настоящее время оценка KMeans выше, чем у DBSCAN и OPTICS, которые, как известно, имеют лучшие результаты кластеризации. Причина в том, что коэффициент силуэта использует метрику на основе расстояния.

4 Резюме

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

использованная литература

[1]Джейн, А. К. (2010) Кластеризация данных: 50 лет после K-средних, Письма о распознавании образов, 31 (8), 651–666.

[2]Чжоу Чжихуа Машинное обучение [M] Цин хуа да сюэ чу бань шэ, (2016): 197-224.

[3] Han J, Pei J, Kamber M. Data mining: concepts and techniques[M]. Elsevier, (2011): 442-495.

[4]Тибширани, Р., Вальтер, Г., и Хасти, Т. (2001).Оценка количества кластеров данных с помощью статистики пропусков.В Журнале Королевского статистического общества: серия B (том 63, выпуск, часть 2, стр. 411–423).

[5]Амиго, Энрике и др.: Сравнение внешних показателей оценки кластеризации на основе формальных ограничений, В: Информационный поиск 12.4 (2009): 461-486.

[6]Rehioui, H., Idrissi, A., Abourezq, M., & Zegrari, F. (2016) DENCLUE-IM: новый подход к кластеризации больших данных, Procedia Computer Science, 83 (Ant 2016), 560–567.

[7] Sculley D. Web-scale k-means clustering[C]//Proceedings of the 19th international conference on World wide web. 2010: 1177-1178.

[8] Huang, Z.: Clustering large data sets with mixed numeric and categorical values, Proceedings of the First Pacific Asia Knowledge Discovery and Data Mining Conference, Singapore, pp. 21-34, 1997.

[9] Kaufman, L. and Rousseeuw, P.J. (1987), Clustering by means of Medoids.

[10] Kaufman L, Rousseeuw P J. Clustering large applications (Program CLARA)[J]. Finding groups in data: an introduction to cluster analysis, 1990.

[11] Ng, Raymond T., and Jiawei Han. "CLARANS: A method for clustering objects for spatial data mining." IEEE transactions on knowledge and data engineering 14.5 (2002): 1003-1016.

[12]Xiong, T., Wang, S., Mayers, A. и др. DHCC: Разделительная иерархическая кластеризация категориальных данных, Data Min Knowl Disc 24, 103–135 (2012).

[13] Zhang T, Ramakrishnan R, Livny M. BIRCH: an efficient data clustering method for very large databases[J]. ACM Sigmod Record, 1996, 25(2): 103-114.

[14] Karypis G, Han E H, Kumar V. Chameleon: Hierarchical clustering using dynamic modeling[J]. Computer, 1999, 32(8): 68-75.

[15]Кэтрин А. Хеллер и Зубин Гахрамани, 2005. Байесовская иерархическая кластеризация, В материалах 22-й международной конференции по машинному обучению (ICML '05), Ассоциация вычислительной техники, Нью-Йорк, США, 297–304.

[16] Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Kdd. 1996, 96(34): 226-231.

[17] Ankerst M, Breunig M M, Kriegel H P, et al. OPTICS: ordering points to identify the clustering structure[J]. ACM Sigmod record, 1999, 28(2): 49-60.

[18]Хиннебург, А., и Кейм, Д. (1998).Эффективный подход к кластеризации в больших мультимедийных базах данных с шумом, В материалах 4-й Международной конференции по обнаружению знаний и интеллектуальному анализу данных (KDD 98), 58–65.

[19]Rehioui, H., Idrissi, A., Abourezq, M., & Zegrari, F. (2016) DENCLUE-IM: новый подход к кластеризации больших данных, Procedia Computer Science, 83 (Ant 2016), 560–567.

[20]Ван, В., Ян, Дж., и Мунц, Р. (1997) STING: Подход статистической информационной сетки к интеллектуальному анализу пространственных данных, Труды 23-й Международной конференции по очень большим базам данных, VLDB 1997, 186–195.

[21]Агравал Р., Герке Дж., Гунопулос Д. и др. Автоматическая кластеризация подпространств многомерных данных, Data Min Knowl Disc 11, 5–33 (2005).

[22]Шуберт, Э., и Руссеу, П. Дж. (2019).Ускоренная кластеризация k-Medoids: улучшение алгоритмов PAM, CLARA и CLARANS. Конспекты лекций по информатике (включая конспекты лекций по искусственному интеллекту и конспекты лекций по биоинформатике), 11807. LNCS, 171–187.

Приложение

Код этой статьи
Arbitrary shape datasets