Алгоритмы автоматической кластеризации

Автоматические алгоритмы кластеризации — это алгоритмы, которые могут выполнять кластеризацию без предварительного знания наборов данных. В отличие от других методов кластерного анализа , автоматические алгоритмы кластеризации могут определять оптимальное количество кластеров даже при наличии шума и точек выброса. ^{[1] [ требуется контекст ]}

При наличии набора из n объектов алгоритмы на основе центроидов создают k разделов на основе функции несходства, такой, что k≤n . Основной проблемой при применении этого типа алгоритма является определение подходящего количества кластеров для немаркированных данных. Поэтому большинство исследований в области кластерного анализа были сосредоточены на автоматизации процесса.

Автоматический выбор k в алгоритме кластеризации K -средних , одном из наиболее используемых алгоритмов кластеризации на основе центроида, по-прежнему является серьезной проблемой в машинном обучении. Наиболее приемлемым решением этой проблемы является метод локтя . Он состоит из запуска кластеризации k -средних для набора данных с диапазоном значений, вычисления суммы квадратов ошибок для каждого и построения их на линейной диаграмме. Если диаграмма выглядит как рука, наилучшее значение k будет на «локте». ^[2]

Другим методом, который модифицирует алгоритм k -средних для автоматического выбора оптимального числа кластеров, является алгоритм G -средних. Он был разработан на основе гипотезы о том, что подмножество данных следует гауссовскому распределению. Таким образом, k увеличивается до тех пор, пока данные каждого центра k -средних не станут гауссовыми. Этот алгоритм требует только стандартный уровень статистической значимости в качестве параметра и не устанавливает ограничений на ковариацию данных. ^[3]

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

Иерархические модели могут быть либо разделительными, где разделы строятся из всего доступного набора данных, либо агломерирующими, где каждый раздел начинается с одного объекта, а дополнительные объекты добавляются к набору. ^[4] Хотя иерархическая кластеризация имеет преимущество, позволяя использовать любую допустимую метрику в качестве определенного расстояния, она чувствительна к шуму и колебаниям в наборе данных и ее сложнее автоматизировать.

Были разработаны методы для улучшения и автоматизации существующих иерархических алгоритмов кластеризации ^[5], таких как автоматизированная версия иерархического кластерного анализа с одной связью (HCA). Этот компьютеризированный метод основывает свой успех на самосогласованном подходе снижения выбросов с последующим построением описательной функции, которая позволяет определять естественные кластеры. Отброшенные объекты также могут быть назначены этим кластерам. По сути, не нужно прибегать к внешним параметрам для идентификации естественных кластеров. Информация, собранная с помощью HCA, автоматизированная и надежная, может быть возобновлена ​​в дендрограмме с числом естественных кластеров и соответствующим разделением, опция, отсутствующая в классическом HCA. Этот метод включает два следующих шага: удаление выбросов (это применяется во многих приложениях фильтрации) и необязательная классификация, позволяющая расширять кластеры со всем набором объектов. ^[6]

BIRCH (сбалансированное итеративное сокращение и кластеризация с использованием иерархий) — это алгоритм, используемый для выполнения кластеризации на основе связности для больших наборов данных. ^[7] Он считается одним из самых быстрых алгоритмов кластеризации, но он ограничен, поскольку требует количества кластеров в качестве входных данных. Поэтому были разработаны новые алгоритмы на основе BIRCH, в которых нет необходимости предоставлять количество кластеров с самого начала, но которые сохраняют качество и скорость кластеров. Основная модификация заключается в удалении последнего шага BIRCH, где пользователь должен был вводить количество кластеров, и улучшении остальной части алгоритма, называемого деревом BIRCH, путем оптимизации порогового параметра из данных. В этом результирующем алгоритме пороговый параметр вычисляется из максимального радиуса кластера и минимального расстояния между кластерами, которые часто известны. Этот метод оказался эффективным для наборов данных из десятков тысяч кластеров. Если выйти за пределы этого количества, возникает проблема разделения суперкластера. Для этого были разработаны другие алгоритмы, такие как MDB-BIRCH, который уменьшает расщепление суперкластера с относительно высокой скоростью. ^[8]

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

Алгоритм кластеризации на основе плотности использует автономное машинное обучение, которое определяет закономерности относительно географического положения и расстояния до определенного количества соседей. Он считается автономным, поскольку априорные знания о том, что такое кластер, не требуются. ^[9] Этот тип алгоритма предоставляет различные методы для поиска кластеров в данных. Самый быстрый метод — DBSCAN , который использует определенное расстояние для различения плотных групп информации и более разреженного шума. Более того, HDBSCAN может самонастраиваться, используя диапазон расстояний вместо указанного. Наконец, метод OPTICS создает график достижимости на основе расстояния от соседних объектов для отделения шума от кластеров различной плотности.

Эти методы по-прежнему требуют от пользователя предоставления центра кластера и не могут считаться автоматическими. Алгоритм автоматической локальной кластеризации плотности (ALDC) является примером нового исследования, направленного на разработку автоматической кластеризации на основе плотности. ALDC вычисляет локальную плотность и отклонение расстояния каждой точки, тем самым расширяя разницу между потенциальным центром кластера и другими точками. Это расширение позволяет машине работать автоматически. Машина определяет центры кластеров и назначает точки, которые оставлены их ближайшим соседом с более высокой плотностью. ^[10]

В автоматизации плотности данных для идентификации кластеров исследования также были сосредоточены на искусственной генерации алгоритмов. Например, оценка алгоритмов распределения гарантирует генерацию допустимых алгоритмов с помощью направленного ациклического графа (DAG), в котором узлы представляют процедуры (строительные блоки), а ребра представляют возможные последовательности выполнения между двумя узлами. Строительные блоки определяют алфавит EDA или, другими словами, любой сгенерированный алгоритм. Искусственно сгенерированные алгоритмы кластеризации сравниваются с DBSCAN, ручным алгоритмом, в экспериментальных результатах. ^[11]