Алгоритмы автоматической кластеризации
Алгоритмы автоматической кластеризации — это алгоритмы, которые могут выполнять кластеризацию без предварительного знания наборов данных. В отличие от других методов кластерного анализа , алгоритмы автоматической кластеризации могут определять оптимальное количество кластеров даже при наличии шума и точек-выбросов. [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, на котором пользователь должен был ввести количество кластеров, и в улучшении остальной части алгоритма, называемой Tree-BIRCH, путем оптимизации порогового параметра на основе данных. В этом алгоритме пороговый параметр рассчитывается на основе максимального радиуса кластера и минимального расстояния между кластерами, которые часто известны. Этот метод оказался эффективным для наборов данных из десятков тысяч кластеров. Если выйти за пределы этой суммы, возникает проблема разделения сверхскоплений. Для этого были разработаны другие алгоритмы, такие как MDB-BIRCH, который уменьшает расщепление суперкластера при относительно высокой скорости. [8]
На основе плотности
[ редактировать ]В отличие от методов разделения и иерархических методов, алгоритмы кластеризации на основе плотности способны находить кластеры любой произвольной формы, а не только сферы.
Алгоритм кластеризации на основе плотности использует автономное машинное обучение, которое определяет закономерности, касающиеся географического положения и расстояния до определенного количества соседей. Он считается автономным, поскольку не требуется априорных знаний о том, что такое кластер. [9] Этот тип алгоритма предоставляет различные методы поиска кластеров в данных. Самый быстрый метод — DBSCAN , который использует определенное расстояние, чтобы различать плотные группы информации и редкий шум. Более того, HDBSCAN может самонастраиваться, используя диапазон расстояний вместо заданного. Наконец, метод OPTICS создает график достижимости на основе расстояния до соседних объектов, чтобы отделить шум от кластеров различной плотности.
Эти методы по-прежнему требуют от пользователя предоставления центра кластера и не могут считаться автоматическими. Алгоритм автоматической локальной кластеризации плотности (ALDC) является примером нового исследования, направленного на разработку автоматической кластеризации на основе плотности. ALDC рассчитывает локальную плотность и отклонение расстояния для каждой точки, тем самым увеличивая разницу между потенциальным центром кластера и другими точками. Это расширение позволяет машине работать автоматически. Машина определяет центры кластеров и назначает точки, оставленные их ближайшим соседом с более высокой плотностью. [10]
При автоматизации плотности данных для идентификации кластеров исследования также были сосредоточены на искусственном создании алгоритмов. Например, «Оценка алгоритмов распределения» гарантирует создание действительных алгоритмов с помощью ориентированного ациклического графа (DAG), в котором узлы представляют процедуры (строительный блок), а ребра представляют возможные последовательности выполнения между двумя узлами. Строительные блоки определяют алфавит EDA или, другими словами, любой сгенерированный алгоритм. В экспериментальных результатах искусственно созданные алгоритмы кластеризации сравниваются с ручным алгоритмом DBSCAN. [11]
Ссылки
[ редактировать ]- ^ Выброс
- ^ «Использование метода локтя для определения оптимального количества кластеров для кластеризации k-средних» . bl.ocks.org . Проверено 12 ноября 2018 г.
- ^ Хамерли, Грег; Элкан, Чарльз (9 декабря 2003 г.). Себастьян Трун; Лоуренс К. Сол; Бернхард Х. Шёлкопф (ред.). Изучение k в k-средних (PDF) . Материалы 16-й Международной конференции по нейронным системам обработки информации . Уистлер, Британская Колумбия, Канада: MIT Press. стр. 281–288. Архивировано из оригинала (PDF) 16 октября 2022 года . Проверено 3 ноября 2022 г.
{{cite conference}}: CS1 maint: дата и год ( ссылка ) - ^ «Введение в кластеризацию II: алгоритмы кластеризации — GameAnalytics» . Игровая аналитика . 20 мая 2014 г. Проверено 6 ноября 2018 г.
- ^ Алмейда, JAS; Барбоса, LMS; Паис, AACC; Формозинью, SJ (июнь 2007 г.). «Улучшение иерархического кластерного анализа: новый метод с обнаружением выбросов и автоматической кластеризацией» (PDF) . Хемометрика и интеллектуальные лабораторные системы . 87 (2). Эльзевир: 208–217. doi : 10.1016/j.chemolab.2007.01.005 . hdl : 10316/5042 . Архивировано из оригинала (PDF) 15 ноября 2018 года . Проверено 3 ноября 2022 г.
- ^ Алмейда, JAS; Барбоса, LMS; Паис, AACC; Формозиньо, SJ (15 июня 2007 г.). «Улучшение иерархического кластерного анализа: новый метод с обнаружением выбросов и автоматической кластеризацией» (PDF) . Хемометрика и интеллектуальные лабораторные системы . 87 (2): 208–217. doi : 10.1016/j.chemolab.2007.01.005 . hdl : 10316/5042 . ISSN 0169-7439 .
- ^ Чжан, Тянь; Рамакришнан, Рагху; Ливный, Мирон; Чжан, Тянь; Рамакришнан, Рагху; Ливны, Мирон (1 июня 1996 г.). «BIRCH: эффективный метод кластеризации данных для очень больших баз данных. BIRCH: эффективный метод кластеризации данных для очень больших баз данных» . Запись ACM SIGMOD . 25 (2): 103, 103–114, 114. doi : 10.1145/235968.233324 . ISSN 0163-5808 .
- ^ Лорел, Борис; Косарева Ана; Дева, Берсант; Софтич, Дженан; Руппель, Питер; Кюппер, Аксель (01 марта 2018 г.). «Вариации алгоритма кластеризации BIRCH» . Исследование больших данных . 11 :44–53. дои : 10.1016/j.bdr.2017.09.002 . ISSN 2214-5796 .
- ^ «Как работает кластеризация на основе плотности—ArcGIS Pro | ArcGIS Desktop» . pro.arcgis.com . Проверено 5 ноября 2018 г.
- ^ «Алгоритм автоматического распознавания центров кластеров на основе кластеризации локальной плотности - публикация конференции IEEE». дои : 10.1109/CCDC.2017.7978726 . S2CID 23267464 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ «Автокластеризация: оценка алгоритма распределения для автоматической генерации алгоритмов кластеризации - публикация конференции IEEE». CiteSeerX 10.1.1.308.9977 . дои : 10.1109/CEC.2012.6252874 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь )