Кластерный анализ

Группировка набора объектов по сходству

Результат кластерного анализа, представленный в виде раскрашивания квадратов в три кластера.

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

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

Помимо термина кластеризация , существует ряд терминов со схожими значениями, включая автоматическую классификацию , числовую таксономию , ботриологию (от греч . βότρυς ' виноград ' ), типологический анализ и обнаружение сообществ . Тонкие различия часто заключаются в использовании результатов: в то время как при интеллектуальном анализе данных интерес представляют полученные группы, при автоматической классификации интерес представляет полученная дискриминационная способность.

Кластерный анализ был зародился в антропологии Драйвером и Крёбером в 1932 году ^[1] и введен в психологию Джозефом Зубиным в 1938 году ^[2] и Робертом Трайоном в 1939 году ^[3]. Широко использовался Кеттеллом с 1943 года ^[4] для классификации теорий черт в психологии личности .

Определение

Понятие «кластер» не может быть точно определено, что является одной из причин, по которой существует так много алгоритмов кластеризации. ^[5] Существует общий знаменатель: группа объектов данных. Однако разные исследователи используют разные модели кластеров, и для каждой из этих моделей кластеров могут быть даны разные алгоритмы. Понятие кластера, найденное разными алгоритмами, значительно различается по своим свойствам. Понимание этих «моделей кластеров» является ключом к пониманию различий между различными алгоритмами. Типичные модели кластеров включают:

• Модели связности : например,иерархическая кластеризациясоздает модели на основе дистанционной связности.
• Центроидная модель s: например,алгоритм k-среднихпредставляет каждый кластер одним средним вектором.
• Модели распределения : кластеры моделируются с использованием статистических распределений, таких какмногомерные нормальные распределения,используемые алгоритмоммаксимизации ожидания.
• Модели плотности : например,DBSCANиOPTICSопределяют кластеры как связанные плотные области в пространстве данных.
• Подпространственные модели :прибикластеризации(также известной как совместная кластеризация или двухмодовая кластеризация) кластеры моделируются как с членами кластера, так и с соответствующими атрибутами.
• Групповые модели :некоторые алгоритмы не предоставляют уточненную модель для своих результатов, а предоставляют только информацию о группировке.
• Графовая модель s:клика, то есть подмножество узлов вграфе,такое, что каждые два узла в подмножестве соединены ребром, может рассматриваться как прототипическая форма кластера. Ослабления требования полной связности (часть ребер может отсутствовать) известны как квазиклики, как валгоритме кластеризации HCS.
• Модели знаковых графов : каждый путь в знаковом графе имеет знак из произведения знаков на ребрах. Согласно предположениям теории баланса , ребра могут менять знак и приводить к раздвоенному графу. Более слабая «аксиома кластеризации» (ни один цикл не имеет ровно одного отрицательного ребра) дает результаты с более чем двумя кластерами или подграфами только с положительными ребрами. ^[6]
• Нейронные модели :наиболее известнаянеконтролируемая нейронная сеть— этосамоорганизующаяся карта, и эти модели обычно можно охарактеризовать как похожие на одну или несколько из вышеперечисленных моделей, а также включающие модели подпространств, когда нейронные сети реализуют формуанализа главных компонентовилианализа независимых компонентов.

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

• Жесткая кластеризация : каждый объект принадлежит кластеру или нет.
• Мягкая кластеризация (также:нечеткая кластеризация ): каждый объект принадлежит каждому кластеру в определенной степени (например, вероятность принадлежности к кластеру)

Возможны и более тонкие различия, например:

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

Алгоритмы

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

Не существует объективно «правильного» алгоритма кластеризации, но, как было отмечено, «кластеризация — это в глазах смотрящего». ^[5] Наиболее подходящий алгоритм кластеризации для конкретной проблемы часто необходимо выбирать экспериментально, если только нет математической причины предпочесть одну модель кластеризации другой. Алгоритм, разработанный для одного вида модели, как правило, не будет работать с набором данных, содержащим радикально иной вид модели. ^[5] Например, k-средние не могут найти невыпуклые кластеры. ^[5] Большинство традиционных методов кластеризации предполагают, что кластеры имеют сферическую, эллиптическую или выпуклую форму. ^[7]

Кластеризация на основе связности (иерархическая кластеризация)

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

Кластеризация на основе связности — это целое семейство методов, которые различаются способом вычисления расстояний. Помимо обычного выбора функций расстояния , пользователю также необходимо выбрать критерий связи (поскольку кластер состоит из нескольких объектов, существует несколько кандидатов для вычисления расстояния) для использования. Популярные варианты известны как кластеризация с одинарной связью (минимум расстояний между объектами), кластеризация с полной связью (максимум расстояний между объектами) и UPGMA или WPGMA («Метод невзвешенной или взвешенной парной группы со средним арифметическим», также известный как кластеризация со средней связью). Кроме того, иерархическая кластеризация может быть агломеративной (начинающейся с отдельных элементов и объединяющей их в кластеры) или разделительной (начинающейся с полного набора данных и разделяющей его на разделы).

Эти методы не дадут уникального разбиения набора данных, а лишь иерархию, из которой пользователю все еще нужно выбрать соответствующие кластеры. Они не очень надежны по отношению к выбросам, которые либо будут отображаться как дополнительные кластеры, либо даже приведут к слиянию других кластеров (известно как «феномен цепочечного объединения», в частности, при кластеризации с одинарной связью ). В общем случае сложность заключается в агломеративной кластеризации и разделительной кластеризации , ^[8] что делает их слишком медленными для больших наборов данных. Для некоторых особых случаев известны оптимальные эффективные методы (сложности ): SLINK ^[9] для одинарной связи и CLINK ^[10] для кластеризации с полной связью. ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle {\mathcal {O}}(2^{n-1})}$ ${\displaystyle {\mathcal {O}}(n^{2})}$

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

Центроидная кластеризация

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

Известно, что сама задача оптимизации является NP-трудной , и поэтому распространенным подходом является поиск только приближенных решений. Особенно известным приближенным методом является алгоритм Ллойда ^[11] , часто называемый просто « алгоритмом k-средних » (хотя другой алгоритм ввел это название ). Однако он находит только локальный оптимум и обычно запускается несколько раз с различными случайными инициализациями. Вариации k -средних часто включают такие оптимизации, как выбор лучшего из нескольких запусков, но также ограничение центроидов членами набора данных ( k -medoids ), выбор медиан ( k -medians clustering ), выбор начальных центров менее случайным образом ( k -means++ ) или разрешение нечеткого назначения кластера ( fuzzy c-means ).

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

K-means имеет ряд интересных теоретических свойств. Во-первых, он разбивает пространство данных на структуру, известную как диаграмма Вороного . Во-вторых, он концептуально близок к классификации ближайшего соседа и, как таковой, популярен в машинном обучении . В-третьих, его можно рассматривать как разновидность кластеризации на основе модели, а алгоритм Ллойда — как разновидность алгоритма максимизации ожидания для этой модели, обсуждаемой ниже.

• Примеры кластеризации методом k -средних
• 
  Метод k -средних разделяет данные на ячейки Вороного, что предполагает наличие кластеров одинакового размера (в данном случае это не подходит).
• 
  k -средние не могут представлять кластеры на основе плотности.

Задачи кластеризации на основе центроидов, такие как k -средние и k -медоиды, являются частными случаями некапитальной метрической задачи размещения объектов , канонической задачи в сообществах исследования операций и вычислительной геометрии. В базовой задаче размещения объектов (существует множество вариантов, моделирующих более сложные настройки) задача состоит в том, чтобы найти наилучшие местоположения складов для оптимального обслуживания заданного набора потребителей. Можно рассматривать «склады» как центроиды кластера, а «местоположения потребителей» как данные, подлежащие кластеризации. Это позволяет применять хорошо разработанные алгоритмические решения из литературы по размещению объектов к рассматриваемой в настоящее время задаче кластеризации на основе центроидов.

Кластеризация на основе моделей

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

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

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

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

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

Кластеризация на основе плотности

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

Самый популярный ^[13] метод кластеризации на основе плотности — это DBSCAN . ^[14] В отличие от многих новых методов, он имеет четко определенную модель кластера, называемую «плотность-достижимость». Подобно кластеризации на основе связей, он основан на соединении точек в пределах определенных пороговых расстояний. Однако он соединяет только точки, которые удовлетворяют критерию плотности, в исходном варианте определенному как минимальное количество других объектов в пределах этого радиуса. Кластер состоит из всех объектов, связанных плотностью (которые могут образовывать кластер произвольной формы, в отличие от многих других методов), а также всех объектов, которые находятся в пределах диапазона этих объектов. Еще одним интересным свойством DBSCAN является то, что его сложность довольно низкая — он требует линейного числа запросов диапазона в базе данных — и что он будет обнаруживать по сути те же самые результаты (он детерминирован для основных и шумовых точек, но не для пограничных точек) в каждом запуске, поэтому нет необходимости запускать его несколько раз. OPTICS ^[15] — это обобщение DBSCAN, которое устраняет необходимость выбора подходящего значения для параметра диапазона и выдает иерархический результат, связанный с кластеризацией связей . DeLi-Clu, ^[16] Density-Link-Clustering объединяет идеи кластеризации с одной связью и OPTICS, полностью устраняя параметр и предлагая улучшения производительности по сравнению с OPTICS за счет использования индекса R-дерева . ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$

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

Mean-shift — это подход к кластеризации, при котором каждый объект перемещается в самую плотную область в его окрестности на основе оценки плотности ядра . В конечном итоге объекты сходятся к локальным максимумам плотности. Подобно кластеризации k-средних, эти «аттракторы плотности» могут служить представителями для набора данных, но mean-shift может обнаруживать кластеры произвольной формы, подобные DBSCAN. Из-за дорогостоящей итеративной процедуры и оценки плотности mean-shift обычно медленнее, чем DBSCAN или k-Means. Кроме того, применимость алгоритма mean-shift к многомерным данным затруднена негладким поведением оценки плотности ядра, что приводит к чрезмерной фрагментации хвостов кластера. ^[16]

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

Кластеризация на основе сетки

Метод на основе сетки используется для многомерного набора данных. ^[17] В этом методе мы создаем структуру сетки, и сравнение выполняется на сетках (также известных как ячейки). Метод на основе сетки быстрый и имеет низкую вычислительную сложность. Существует два типа методов кластеризации на основе сетки: STING и CLIQUE. Шаги, включенные в алгоритм кластеризации на основе сетки :

1. Разделите пространство данных на конечное число ячеек.
2. Случайным образом выберите ячейку «c», где c не должна быть пройдена заранее.
3. Рассчитайте плотность «c»
4. Если плотность «c» больше пороговой плотности
   1. Отметить ячейку «c» как новый кластер
   2. Рассчитайте плотность всех соседей «c»
   3. Если плотность соседней ячейки больше пороговой плотности, то добавьте ячейку в кластер и повторите шаги 4.2 и 4.3 до тех пор, пока не останется соседей с плотностью больше пороговой плотности.
5. Повторяйте шаги 2, 3 и 4, пока не будут пройдены все ячейки.
6. Останавливаться.

Последние события

В последние годы были приложены значительные усилия для улучшения производительности существующих алгоритмов. ^{[18] [19]} Среди них CLARANS , ^[20] и BIRCH . ^[21] С недавней потребностью в обработке все больших и больших наборов данных (также известных как большие данные ), готовность торговать семантическим значением сгенерированных кластеров ради производительности увеличивается. Это привело к разработке методов предварительной кластеризации, таких как кластеризация полога , которые могут эффективно обрабатывать огромные наборы данных, но полученные «кластеры» являются всего лишь грубым предварительным разбиением набора данных для последующего анализа разбиений с помощью существующих более медленных методов, таких как кластеризация k-средних .

Для многомерных данных многие из существующих методов терпят неудачу из-за проклятия размерности , которое делает определенные функции расстояния проблематичными в многомерных пространствах. Это привело к появлению новых алгоритмов кластеризации для многомерных данных , которые фокусируются на кластеризации подпространства (где используются только некоторые атрибуты, а модели кластера включают соответствующие атрибуты для кластера) и корреляционной кластеризации , которая также ищет произвольные вращаемые («коррелированные») кластеры подпространства, которые можно моделировать, задавая корреляцию их атрибутов. ^[22] Примерами таких алгоритмов кластеризации являются CLIQUE ^[23] и SUBCLU . ^[24]

Идеи методов кластеризации на основе плотности (в частности, семейства алгоритмов DBSCAN / OPTICS ) были адаптированы к кластеризации подпространств (HiSC, ^[25] иерархическая кластеризация подпространств и DiSH ^[26] ) и кластеризации корреляций (HiCO, ^[27] иерархическая кластеризация корреляций, 4C ^[28] с использованием «корреляционной связности» и ERiC ^[29], исследующий иерархические кластеры корреляций на основе плотности).

Было предложено несколько различных систем кластеризации, основанных на взаимной информации . Одна из них — это вариация информационной метрики Марины Мейлэ; ^[30] другая обеспечивает иерархическую кластеризацию. ^[31] Используя генетические алгоритмы, можно оптимизировать широкий спектр различных функций соответствия, включая взаимную информацию. ^[32] Также распространение убеждений , недавнее развитие в области компьютерной науки и статистической физики , привело к созданию новых типов алгоритмов кластеризации. ^[33]

Оценка и анализ

Оценка (или «валидация») результатов кластеризации так же сложна, как и сама кластеризация. ^[34] Популярные подходы включают « внутреннюю » оценку, где кластеризация суммируется в единый показатель качества, « внешнюю » оценку, где кластеризация сравнивается с существующей «истинной» классификацией, « ручную » оценку экспертом-человеком и « косвенную » оценку, определяющую полезность кластеризации в ее предполагаемом применении. ^[35]

Внутренние меры оценки страдают от проблемы, что они представляют функции, которые сами по себе могут рассматриваться как цель кластеризации. Например, можно кластеризовать набор данных по коэффициенту Silhouette; за исключением того, что для этого не существует известного эффективного алгоритма. Используя такую ​​внутреннюю меру для оценки, скорее сравнивают сходство задач оптимизации, ^[35] и не обязательно насколько полезна кластеризация.

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

Ни один из этих подходов не может в конечном итоге судить о фактическом качестве кластеризации, но для этого нужна человеческая оценка, ^[35] которая весьма субъективна. Тем не менее, такая статистика может быть весьма информативной при выявлении плохих кластеризаций, ^[36] но не следует игнорировать субъективную человеческую оценку. ^[36]

Внутренняя оценка

Когда результат кластеризации оценивается на основе данных, которые были кластеризованы сами по себе, это называется внутренней оценкой. Эти методы обычно присваивают лучшую оценку алгоритму, который производит кластеры с высоким сходством внутри кластера и низким сходством между кластерами. Одним из недостатков использования внутренних критериев при оценке кластера является то, что высокие баллы по внутренней мере не обязательно приводят к эффективным приложениям поиска информации. ^[37] Кроме того, эта оценка смещена в сторону алгоритмов, которые используют ту же модель кластера. Например, кластеризация k-средних естественным образом оптимизирует расстояния объектов, а внутренний критерий на основе расстояния, скорее всего, переоценит результирующую кластеризацию.

Таким образом, внутренние меры оценки лучше всего подходят для получения некоторого понимания ситуаций, когда один алгоритм работает лучше другого, но это не должно означать, что один алгоритм выдает более достоверные результаты, чем другой. ^[5] Достоверность, измеряемая таким индексом, зависит от утверждения о том, что этот тип структуры существует в наборе данных. Алгоритм, разработанный для какого-либо типа моделей, не имеет шансов, если набор данных содержит радикально другой набор моделей или если оценка измеряет радикально другой критерий. ^[5] Например, кластеризация k-средних может находить только выпуклые кластеры, и многие индексы оценки предполагают выпуклые кластеры. На наборе данных с невыпуклыми кластерами ни использование k -средних, ни критерия оценки, который предполагает выпуклость, не является обоснованным.

Существует более дюжины внутренних оценочных мер, обычно основанных на интуитивном предположении, что элементы в одном кластере должны быть более похожи, чем элементы в разных кластерах. ^{[38] : 115–121} Например, для оценки качества алгоритмов кластеризации на основе внутреннего критерия можно использовать следующие методы:

• Индекс Дэвиса–Боулдина

Индекс Дэвиса–Боулдина можно рассчитать по следующей формуле:

${\displaystyle DB={\frac {1}{n}}\sum _{i=1}^{n}\max _{j\neq i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)}$

где n — количество кластеров, — центроид кластера , — среднее расстояние всех элементов в кластере до центроида , а — расстояние между центроидами и . Поскольку алгоритмы, которые создают кластеры с низкими внутрикластерными расстояниями (высокое внутрикластерное сходство) и высокими межкластерными расстояниями (низкое межкластерное сходство), будут иметь низкий индекс Дэвиса–Боулдина, алгоритм кластеризации, который создает набор кластеров с наименьшим индексом Дэвиса–Боулдина, считается лучшим алгоритмом на основе этого критерия. ${\displaystyle c_{i}}$ ${\displaystyle i}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle d(c_{i},c_{j})}$ ${\displaystyle c_{i}}$ ${\displaystyle c_{j}}$

• индекс Данна

Индекс Данна направлен на выявление плотных и хорошо разделенных кластеров. Он определяется как отношение минимального расстояния между кластерами к максимальному расстоянию внутри кластера. Для каждого кластерного раздела индекс Данна может быть рассчитан по следующей формуле: ^[39]

${\displaystyle D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,}$

где d ( i , j ) представляет расстояние между кластерами i и j , а d '( k ) измеряет внутрикластерное расстояние кластера k . Межкластерное расстояние d ( i , j ) между двумя кластерами может быть любым числом мер расстояния, например, расстоянием между центроидами кластеров. Аналогично, внутрикластерное расстояние d '( k ) может быть измерено различными способами, например, максимальным расстоянием между любой парой элементов в кластере  k . Поскольку внутренний критерий ищет кластеры с высоким внутрикластерным сходством и низким межкластерным сходством, алгоритмы, которые производят кластеры с высоким индексом Данна, более желательны.

• Коэффициент силуэта

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

Внешняя оценка

При внешней оценке результаты кластеризации оцениваются на основе данных, которые не использовались для кластеризации, таких как известные метки классов и внешние эталоны. Такие эталоны состоят из набора предварительно классифицированных элементов, и эти наборы часто создаются (экспертными) людьми. Таким образом, эталонные наборы можно рассматривать как золотой стандарт для оценки. ^[34] Эти типы методов оценки измеряют, насколько близка кластеризация к предопределенным эталонным классам. Однако недавно обсуждалось, является ли это адекватным для реальных данных или только для синтетических наборов данных с фактической истинностью, поскольку классы могут содержать внутреннюю структуру, присутствующие атрибуты могут не позволять разделять кластеры или классы могут содержать аномалии . ^[41] Кроме того, с точки зрения обнаружения знаний воспроизведение известных знаний не обязательно может быть предполагаемым результатом. ^[41] В особом сценарии ограниченной кластеризации , где метаинформация (например, метки классов) уже используется в процессе кластеризации, удержание информации для целей оценки является нетривиальным. ^[42]

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

Как и в случае с внутренней оценкой, существует несколько внешних мер оценки, ^{[38] : 125–129} например:

• Чистота : Чистота — это мера степени, в которой кластеры содержат один класс. ^[37] Ее расчет можно представить следующим образом: для каждого кластера подсчитайте количество точек данных из наиболее распространенного класса в этом кластере. Теперь возьмите сумму по всем кластерам и разделите на общее количество точек данных. Формально, если задан некоторый набор кластеров и некоторый набор классов , оба разделяющих точки данных, чистоту можно определить как: ${\displaystyle M}$ ${\displaystyle D}$ ${\displaystyle N}$

${\displaystyle {\frac {1}{N}}\sum _{m\in M}\max _{d\in D}{|m\cap d|}}$

Эта мера не штрафует за наличие большого количества кластеров, а большее количество кластеров облегчит получение высокой чистоты. Оценка чистоты 1 всегда возможна, если поместить каждую точку данных в свой собственный кластер. Кроме того, чистота не очень хорошо работает для несбалансированных данных, где даже плохо работающие алгоритмы кластеризации дадут высокое значение чистоты. Например, если набор данных размером 1000 состоит из двух классов, один из которых содержит 999 точек, а другой — 1 точку, то каждое возможное разделение будет иметь чистоту не менее 99,9%.

• Индекс Рэнда ^[43]

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

${\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}}$

где — число истинно положительных результатов, — число истинно отрицательных результатов , — число ложно положительных результатов , — число ложно отрицательных результатов . Здесь подсчитываются следующие примеры: число правильных парных назначений. То есть — число пар точек, которые объединены в предсказанный раздел и в раздел наземной истины, — число пар точек, которые объединены в предсказанный раздел, но не в раздел наземной истины и т. д. Если набор данных имеет размер N, то . ${\displaystyle TP}$ ${\displaystyle TN}$ ${\displaystyle FP}$ ${\displaystyle FN}$ ${\displaystyle TP}$ ${\displaystyle FP}$ ${\displaystyle TP+TN+FP+FN={\binom {N}{2}}}$

Одна из проблем индекса Рэнда заключается в том, что ложные положительные и ложные отрицательные результаты имеют одинаковый вес. Это может быть нежелательной характеристикой для некоторых приложений кластеризации. F-мера решает эту проблему, ^{[ необходима цитата ]} , как и скорректированный по шансам индекс Рэнда .

• F-мера

F-мера может использоваться для балансировки вклада ложноотрицательных результатов путем взвешивания отзыва через параметр . Пусть точность и отзыв (оба внешние оценочные меры сами по себе) определяются следующим образом: ${\displaystyle \beta \geq 0}$

${\displaystyle P={\frac {TP}{TP+FP}}}$

${\displaystyle R={\frac {TP}{TP+FN}}}$

где — скорость точности , а — скорость отзыва . Мы можем рассчитать F-меру, используя следующую формулу: ^[37] ${\displaystyle P}$ ${\displaystyle R}$

${\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}}$

Когда , . Другими словами, отзыв не влияет на F-меру, когда , а увеличение присваивает отзыву все больший вес в окончательной F-мере. ${\displaystyle \beta =0}$ ${\displaystyle F_{0}=P}$ ${\displaystyle \beta =0}$ ${\displaystyle \beta }$

Также не учитывается и может изменяться от 0 и выше без ограничений. ${\displaystyle TN}$

• индекс Жаккара

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

${\displaystyle J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {TP}{TP+FP+FN}}}$

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

Обратите внимание, что это не принимается во внимание. ${\displaystyle TN}$

• Индекс кубика

Симметричная мера Дайса удваивает вес, при этом по-прежнему игнорируя : ${\displaystyle TP}$ ${\displaystyle TN}$

${\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}$

• Индекс Фоулкса–Мэллоуза ^[44]

Индекс Фаулкса–Мэллоуза вычисляет сходство между кластерами, возвращаемыми алгоритмом кластеризации, и эталонными классификациями. Чем выше значение индекса Фаулкса–Мэллоуза, тем более похожи кластеры и эталонные классификации. Его можно вычислить с помощью следующей формулы:

${\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}}$

где — число истинно положительных результатов , — число ложноположительных результатов , — число ложноотрицательных результатов . Индекс — это среднее геометрическое точности и полноты и , и поэтому также известен как G-мера , в то время как F-мера — это их среднее гармоническое. ^{[45] [46]} Кроме того, точность и полнота также известны как индексы Уоллеса и . ^[47] Случайно нормализованные версии полноты, точности и G-меры соответствуют Информированности , Маркированности и Корреляции Мэтьюса и тесно связаны с Каппой . ^[48] ${\displaystyle TP}$ ${\displaystyle FP}$ ${\displaystyle FN}$ ${\displaystyle FM}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle B^{I}}$ ${\displaystyle B^{II}}$

• Индекс Хи ^[49] — это внешний индекс проверки, который измеряет результаты кластеризации с помощью статистики хи-квадрат . Этот индекс положительно оценивает тот факт, что метки в кластерах максимально разрежены, т. е. каждый кластер имеет как можно меньше различных меток. Чем выше значение индекса Хи, тем сильнее связь между полученными кластерами и используемой меткой.
• Взаимная информация — это информационная теоретическая мера того, сколько информации разделяется между кластеризацией и истинностной классификацией, которая может обнаружить нелинейное сходство между двумя кластеризациями. Нормализованная взаимная информация — это семейство скорректированных на случай вариантов этого, которое имеет уменьшенное смещение для различных номеров кластеров. ^[34]
• Матрица путаницы

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

Тенденция к образованию кластеров

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

• Статистика Хопкинса

Существует несколько формулировок статистики Хопкинса . ^[50] Типичная из них выглядит следующим образом. ^[51] Пусть будет набором точек данных в размерном пространстве. Рассмотрим случайную выборку (без замены) точек данных с членами . Также сгенерируем набор равномерно распределенных случайным образом точек данных. Теперь определим две меры расстояния, как расстояние от его ближайшего соседа в X и как расстояние от его ближайшего соседа в X. Затем мы определяем статистику Хопкинса как: ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle m\ll n}$ ${\displaystyle x_{i}}$ ${\displaystyle Y}$ ${\displaystyle m}$ ${\displaystyle u_{i}}$ ${\displaystyle y_{i}\in Y}$ ${\displaystyle w_{i}}$ ${\displaystyle x_{i}\in X}$

${\displaystyle H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,,}$

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

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

Приложения

Биология, вычислительная биология и биоинформатика

Экология растений и животных

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

Транскриптомика

Кластеризация используется для построения групп генов с родственными паттернами экспрессии (также известных как коэкспрессированные гены), как в алгоритме кластеризации HCS . ^{[52] [53]} Часто такие группы содержат функционально связанные белки, такие как ферменты для определенного пути , или гены, которые корегулируются. Высокопроизводительные эксперименты с использованием экспрессированных тегов последовательностей (EST) или ДНК-микрочипов могут быть мощным инструментом для аннотации генома  — общего аспекта геномики .

Анализ последовательности

Кластеризация последовательностей используется для группировки гомологичных последовательностей в семейства генов . ^[54] Это очень важная концепция в биоинформатике и эволюционной биологии в целом. См. эволюцию путем дупликации генов .

Высокопроизводительные платформы генотипирования

Алгоритмы кластеризации используются для автоматического назначения генотипов. ^[55]

Генетическая кластеризация человека

Сходство генетических данных используется при кластеризации для определения структуры популяции.

Лекарство

Медицинская визуализация

При сканировании ПЭТ кластерный анализ может использоваться для дифференциации различных типов тканей на трехмерном изображении для различных целей. ^[56]

Анализ антимикробной активности

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

Сегментация IMRT

Кластеризацию можно использовать для разделения карты плотности потока на отдельные области для преобразования в доставляемые поля в лучевой терапии на основе MLC.

Бизнес и маркетинг

Исследование рынка

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

Группировка товаров

Кластеризация может использоваться для группировки всех товаров, доступных в Интернете, в набор уникальных продуктов. Например, все товары на eBay могут быть сгруппированы в уникальные продукты (eBay не имеет концепции SKU ).

Всемирная паутина

Анализ социальных сетей

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

Группировка результатов поиска

В процессе интеллектуальной группировки файлов и веб-сайтов кластеризация может использоваться для создания более релевантного набора результатов поиска по сравнению с обычными поисковыми системами, такими как Google ^{[ требуется цитата ]} . В настоящее время существует ряд веб-инструментов кластеризации, таких как Clusty . Он также может использоваться для возврата более полного набора результатов в случаях, когда поисковый термин может относиться к совершенно разным вещам. Каждое отдельное использование термина соответствует уникальному кластеру результатов, что позволяет алгоритму ранжирования возвращать всеобъемлющие результаты, выбирая лучший результат из каждого кластера. ^[57]

Оптимизация карты Slippy

Карта фотографий Flickr и другие картографические сайты используют кластеризацию для сокращения количества маркеров на карте. ^{[ необходима ссылка ]} Это ускоряет работу и уменьшает количество визуального беспорядка.

Информатика

Эволюция программного обеспечения

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

Сегментация изображения

Кластеризацию можно использовать для разделения цифрового изображения на отдельные области для обнаружения границ или распознавания объектов . ^[58]

Эволюционные алгоритмы

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

Рекомендательные системы

Рекомендательные системы предназначены для рекомендации новых товаров на основе вкусов пользователя. Иногда они используют алгоритмы кластеризации для прогнозирования предпочтений пользователя на основе предпочтений других пользователей в кластере пользователя.

Методы Монте-Карло на основе цепей Маркова

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

Обнаружение аномалий

Аномалии/выбросы обычно определяются — явно или неявно — относительно структуры кластеризации данных.

Обработка естественного языка

Кластеризация может быть использована для разрешения лексической неоднозначности . ^[57]

DevOps

Кластеризация использовалась для анализа эффективности команд DevOps. ^[59]

Социальные науки

Анализ последовательности в социальных науках

Кластерный анализ используется, например, для выявления закономерностей траекторий семейной жизни, профессиональной карьеры, а также ежедневного или еженедельного использования времени.

Анализ преступности

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

Интеллектуальный анализ образовательных данных

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

Типологии

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

Другие

Полевая робототехника

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

Математическая химия

Например, для поиска структурного сходства и т. д. 3000 химических соединений были сгруппированы в пространстве 90 топологических индексов . ^[61]

Климатология

Найти погодные режимы или предпочтительные атмосферные модели давления на уровне моря. ^[62]

Финансы

Кластерный анализ использовался для группировки акций по секторам. ^[63]

Геология нефти

Кластерный анализ используется для реконструкции отсутствующих данных керна забоя скважины или отсутствующих каротажных кривых с целью оценки свойств коллектора.

Геохимия

Кластеризация химических свойств в различных местах образца.

Смотрите также

Специализированные типы кластерного анализа

• Алгоритмы автоматической кластеризации
• Сбалансированная кластеризация
• Кластеризация многомерных данных
• Концептуальная кластеризация
• Консенсусная кластеризация
• Ограниченная кластеризация
• Обнаружение сообщества
• Кластеризация потока данных
• Кластеризация HCS
• Кластеризация последовательностей
• Спектральная кластеризация

Методы, используемые в кластерном анализе

• Искусственная нейронная сеть (ИНС)
• Поиск ближайшего соседа
• Анализ компонентов соседства
• Анализ латентного класса
• Распространение сродства

Проекция и предварительная обработка данных

• Уменьшение размеров
• Анализ главных компонент
• Многомерное масштабирование

Другой

• Кластерно-взвешенное моделирование
• Проклятие размерности
• Определение количества кластеров в наборе данных
• Параллельные координаты
• Структурированный анализ данных
• Линейная разделимость

Ссылки

1. Драйвер и Крёбер (1932). «Количественное выражение культурных отношений». Публикации Калифорнийского университета по американской археологии и этнологии . Количественное выражение культурных отношений. Беркли, Калифорния: Издательство Калифорнийского университета: 211–256. Архивировано из оригинала 2020-12-06 . Получено 2019-02-18 .
2. Зубин, Джозеф (1938). «Методика измерения единомыслия». Журнал ненормальной и социальной психологии . 33 (4): 508–516. doi :10.1037/h0055441. ISSN  0096-851X.
3. Трайон, Роберт С. (1939). Кластерный анализ: профиль корреляции и ортометрический (факторный) анализ для изоляции единств в разуме и личности . Edwards Brothers.
4. Кеттелл, РБ (1943). «Описание личности: основные черты, разделенные на кластеры». Журнал ненормальной и социальной психологии . 38 (4): 476–506. doi :10.1037/h0054116.
5. Эстивилл-Кастро, Владимир (20 июня 2002 г.). «Почему так много алгоритмов кластеризации – Позиционная статья». ACM SIGKDD Explorations Newsletter . 4 (1): 65–75. doi :10.1145/568574.568575. S2CID  7329935.
6. Джеймс А. Дэвис (май 1967 г.) «Кластеризация и структурный баланс в графах», Human Relations 20:181–7
7. Гао, Кэролайн X.; Дуайер, Доминик; Чжу, Йе; Смит, Кэтрин Л.; Ду, Лан; Филия, Кейт М.; Байер, Йоханна; Менссинк, Яна М.; Ван, Тереза; Бергмейр, Кристоф; Вуд, Стивен; Коттон, Сью М. (2023-09-01). «Обзор методов кластеризации с рекомендациями по применению в исследованиях психического здоровья». Psychiatry Research . 327 : 115265. doi : 10.1016/j.psychres.2023.115265 . hdl : 10481/84538 . ISSN  0165-1781.
8. Эверитт, Брайан (2011). Кластерный анализ . Чичестер, Западный Сассекс, Великобритания: Wiley. ISBN 9780470749913.
9. Сибсон, Р. (1973). "SLINK: оптимально эффективный алгоритм для метода кластера с одной связью" (PDF) . The Computer Journal . 16 (1). British Computer Society: 30–34. doi :10.1093/comjnl/16.1.30.
10. Defays, D. (1977). "Эффективный алгоритм для метода полной связи". The Computer Journal . 20 (4). British Computer Society: 364–366. doi :10.1093/comjnl/20.4.364.
11. Ллойд, С. (1982). «Квантование по наименьшим квадратам в PCM». Труды IEEE по теории информации . 28 (2): 129–137. doi :10.1109/TIT.1982.1056489. S2CID  10833328.
12. Кригель, Ганс-Петер ; Крегер, Пер; Сандер, Йорг; Зимек, Артур (2011). «Кластеризация на основе плотности». WIREs Интеллектуальный анализ данных и обнаружение знаний . 1 (3): 231–240. дои : 10.1002/widm.30. S2CID  36920706.
13. Microsoft academic search: наиболее цитируемые статьи по интеллектуальному анализу данных Архивировано 21.04.2010 на Wayback Machine : DBSCAN находится на 24-м месте при доступе: 18.04.2010
14. Эстер, Мартин; Кригель, Ханс-Питер ; Сандер, Йорг; Сюй, Сяовэй (1996). «Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом». В Simoudis, Evangelos; Хан, Цзявэй; Файяд, Усама М. (ред.). Труды Второй международной конференции по обнаружению знаний и интеллектуальному анализу данных (KDD-96) . AAAI Press . стр. 226–231. ISBN 1-57735-004-9.
15. Анкерст, Михаэль; Брейниг, Маркус М.; Кригель, Ханс-Петер ; Сандер, Йорг (1999). «ОПТИКА: упорядочение точек для идентификации структуры кластеризации». Международная конференция ACM SIGMOD по управлению данными . ACM Press . С. 49–60. CiteSeerX 10.1.1.129.6542 . 
16. Achtert, E.; Böhm, C.; Kröger, P. (2006). "DeLi-Clu: Повышение надежности, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайших пар". Достижения в области обнаружения знаний и интеллектуального анализа данных . Конспект лекций по информатике. Том 3918. С. 119–128. CiteSeerX 10.1.1.64.1161 . doi :10.1007/11731139_16. ISBN  978-3-540-33206-0.
17. Аггарвал, Чару К.; Редди, Чандан К. (ред.). Кластеризация данных: алгоритмы и приложения . ISBN 978-1-315-37351-5. OCLC  1110589522.
18. Скалли, Д. (2010). Кластеризация k-средних в масштабе сети Интернет . Труды 19-й Всемирной конференции.
19. Хуан, З. (1998). «Расширения алгоритма k -средних для кластеризации больших наборов данных с категориальными значениями». Data Mining and Knowledge Discovery . 2 (3): 283–304. doi :10.1023/A:1009769707641. S2CID  11323096.
20. Р. Нг и Дж. Хан. «Эффективный и действенный метод кластеризации для пространственного анализа данных». В: Труды 20-й конференции VLDB, страницы 144–155, Сантьяго, Чили, 1994.
21. Тянь Чжан, Рагу Рамакришнан, Мирон Ливни. «Эффективный метод кластеризации данных для очень больших баз данных». В: Труды Международной конференции по управлению данными, ACM SIGMOD, стр. 103–114.
22. Кригель, Ханс-Петер ; Крёгер, Пир; Зимек, Артур (июль 2012 г.). «Кластеризация подпространства». Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery . 2 (4): 351–364. doi :10.1002/widm.1057. S2CID  7241355.
23. Агравал, Р.; Герке, Дж.; Гунопулос, Д.; Рагхаван, П. (2005). «Автоматическая кластеризация подпространств многомерных данных». Data Mining and Knowledge Discovery . 11 : 5–33. CiteSeerX 10.1.1.131.5152 . doi :10.1007/s10618-005-1396-1. S2CID  9289572. 
24. Карин Кайлинг, Ханс-Петер Кригель и Пир Крёгер. Кластеризация подпространств с плотностью, связанной с высокой размерностью данных . В: Труды SIAM Int. Conf. on Data Mining (SDM'04) , стр. 246–257, 2004.
25. Ахтерт, Э.; Бём, К.; Кригель, Х.-П. ; Крегер, П.; Мюллер-Горман, И.; Зимек, А. (2006). «Нахождение иерархий подпространственных кластеров». Обнаружение знаний в базах данных: PKDD 2006 . Конспекты лекций по информатике. Том. 4213. стр. 446–453. CiteSeerX 10.1.1.705.2956 . дои : 10.1007/11871637_42. ISBN  978-3-540-45374-1.
26. Achtert, E.; Böhm, C.; Kriegel, HP ; Kröger, P.; Müller-Gorman, I.; Zimek, A. (2007). "Обнаружение и визуализация иерархий кластеров подпространства". Advances in Databases: Concepts, Systems and Applications . Lecture Notes in Computer Science. Vol. 4443. pp. 152–163. CiteSeerX 10.1.1.70.7843 . doi :10.1007/978-3-540-71703-4_15. ISBN  978-3-540-71702-7.
27. Achtert, E.; Böhm, C.; Kröger, P.; Zimek, A. (2006). "Mining Hierarchies of Correlation Clusters". 18-я Международная конференция по управлению научными и статистическими базами данных (SSDBM'06) . стр. 119–128. CiteSeerX 10.1.1.707.7872 . doi :10.1109/SSDBM.2006.35. ISBN  978-0-7695-2590-7. S2CID  2679909.
28. Бём, К.; Кайлинг, К.; Крёгер, П.; Зимек, А. (2004). "Вычислительные кластеры корреляционно-связанных объектов". Труды международной конференции ACM SIGMOD 2004 года по управлению данными - SIGMOD '04 . стр. 455. CiteSeerX 10.1.1.5.1279 . doi :10.1145/1007568.1007620. ISBN  978-1581138597. S2CID  6411037.
29. Achtert, E.; Bohm, C.; Kriegel, HP ; Kröger, P.; Zimek, A. (2007). "On Exploring Complex Relationships of Correlation Clusters". 19-я Международная конференция по управлению научными и статистическими базами данных (SSDBM 2007) . стр. 7. CiteSeerX 10.1.1.71.5021 . doi :10.1109/SSDBM.2007.21. ISBN  978-0-7695-2868-7. S2CID  1554722.
30. Мейла, Марина (2003). «Сравнение кластеризации по вариации информации». Теория обучения и ядерные машины . Конспект лекций по информатике. Том 2777. С. 173–187. doi :10.1007/978-3-540-45167-9_14. ISBN 978-3-540-40720-1.
31. Красков, Александр; Штёгбауэр, Харальд; Анджейак, Ральф Г.; Грассбергер, Питер (1 декабря 2003 г.). «Иерархическая кластеризация на основе взаимной информации». arXiv : q-bio/0311039 . Bibcode :2003q.bio....11039K. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
32. Ауффарт, Б. (18–23 июля 2010 г.). «Кластеризация с помощью генетического алгоритма с оператором смещенной мутации». Wcci Cec . IEEE.
33. Фрей, Б. Дж.; Дьюк, Д. (2007). «Кластеризация путем передачи сообщений между точками данных». Science . 315 (5814): 972–976. Bibcode :2007Sci...315..972F. CiteSeerX 10.1.1.121.3145 . doi :10.1126/science.1136800. PMID  17218491. S2CID  6502291. 
34. Пфицнер, Дариус; Лейббрандт, Ричард; Пауэрс, Дэвид (2009). «Характеристика и оценка мер сходства для пар кластеризаций». Системы знаний и информации . 19 (3). Springer: 361–394. doi :10.1007/s10115-008-0150-6. S2CID  6935380.
35. Фельдман, Ронен; Сэнгер, Джеймс (2007-01-01). Справочник по интеллектуальному анализу текста: передовые подходы к анализу неструктурированных данных . Cambridge Univ. Press. ISBN 978-0521836579. OCLC  915286380.
36. Weiss, Sholom M.; Indurkhya, Nitin; Zhang, Tong; Damerau, Fred J. (2005). Text Mining: Predictive Methods for Analyzing Unstructured Information . Springer. ISBN 978-0387954332. OCLC  803401334.
37. Мэннинг, Кристофер Д.; Рагхаван, Прабхакар; Шютце, Хинрих (7 июля 2008 г.). Введение в поиск информации . Издательство Кембриджского университета. ISBN 978-0-521-86571-5.
38. Обнаружение знаний в базах данных – Часть III – Кластеризация (PDF) , Гейдельбергский университет , 2017{{citation}}: CS1 maint: location missing publisher (link)
39. Данн, Дж. (1974). «Хорошо разделенные кластеры и оптимальные нечеткие разбиения». Журнал кибернетики . 4 : 95–104. doi :10.1080/01969727408546059.
40. Питер Дж. Руссеу (1987). «Силуэты: графическое средство интерпретации и проверки кластерного анализа». Журнал вычислительной и прикладной математики . 20 : 53–65. doi :10.1016/0377-0427(87)90125-7.
41. Färber, Ines; Günnemann, Stephan; Kriegel, Hans-Peter ; Kröger, Peer; Müller, Emmanuel; Schubert, Erich; Seidl, Thomas; Zimek, Arthur (2010). "Об использовании меток классов при оценке кластеризации" (PDF) . В Fern, Xiaoli Z.; Davidson, Ian; Dy, Jennifer (ред.). MultiClust: обнаружение, суммирование и использование множественной кластеризации . ACM SIGKDD .
42. Pourrajabi, M.; Moulavi, D.; Campello, RJGB; Zimek, A .; Sander, J.; Goebel, R. (2014). «Выбор модели для полуконтролируемой кластеризации». Труды 17-й Международной конференции по расширению технологий баз данных (EDBT) . стр. 331–342. doi :10.5441/002/edbt.2014.31.
43. Рэнд, В. М. (1971). «Объективные критерии оценки методов кластеризации». Журнал Американской статистической ассоциации . 66 (336). Американская статистическая ассоциация: 846–850. arXiv : 1704.01036 . doi : 10.2307/2284239. JSTOR  2284239.
44. Fowlkes, EB; Mallows, CL (1983). «Метод сравнения двух иерархических кластеризаций». Журнал Американской статистической ассоциации . 78 (383): 553–569. doi :10.1080/01621459.1983.10478008. JSTOR  2288117.
45. Пауэрс, Дэвид (2003). Полнота и точность против букмекера . Международная конференция по когнитивной науке. С. 529–534.
46. Араби, П. (1985). «Сравнение разделов». Журнал классификации . 2 (1): 1985. doi :10.1007/BF01908075. S2CID  189915041.
47. Уоллес, DL (1983). «Комментарий». Журнал Американской статистической ассоциации . 78 (383): 569–579. doi :10.1080/01621459.1983.10478009.
48. Пауэрс, Дэвид (2012). Проблема с каппой . Европейское отделение Ассоциации компьютерной лингвистики. С. 345–355.
49. Луна-Ромера, Хосе Мария; Мартинес-Баллестерос, Мария; Гарсиа-Гутьеррес, Хорхе; Рикельме, Хосе К. (июнь 2019 г.). «Индекс достоверности внешней кластеризации на основе статистического теста хи-квадрат». Информационные науки . 487 : 1–17. doi : 10.1016/j.ins.2019.02.046. hdl : 11441/132081 . S2CID  93003939.
50. Хопкинс, Брайан; Скеллам, Джон Гордон (1954). «Новый метод определения типа распределения особей растений». Annals of Botany . 18 (2). Annals Botany Co: 213–227. doi :10.1093/oxfordjournals.aob.a083391.
51. Баннерджи, А. (2004). «Проверка кластеров с использованием статистики Хопкинса». Международная конференция IEEE по нечетким системам 2004 г. (IEEE Cat. No.04CH37542) . Том 1. стр. 149–153. doi :10.1109/FUZZY.2004.1375706. ISBN 978-0-7803-8353-1. S2CID  36701919.
52. Джонсон, Стивен С. (1967-09-01). «Иерархические схемы кластеризации». Психометрика . 32 (3): 241–254. doi :10.1007/BF02289588. ISSN  1860-0980. PMID  5234703. S2CID  930698.
53. Хартув, Эрез; Шамир, Рон (2000-12-31). «Алгоритм кластеризации, основанный на связности графа». Information Processing Letters . 76 (4): 175–181. doi :10.1016/S0020-0190(00)00142-3. ISSN  0020-0190.
54. Ремм, Майдо; Сторм, Кристиан EV; Зоннхаммер, Эрик LL (2001-12-14). «Автоматическая кластеризация ортологов и паралогов из парных сравнений видов»11 Под редакцией Ф. Коэна. Журнал молекулярной биологии . 314 (5): 1041–1052. doi :10.1006/jmbi.2000.5197. ISSN  0022-2836. PMID  11743721.
55. Botstein, David; Cox, David R.; Risch, Neil; Olshen, Richard; Curb, David; Dzau, Victor J.; Chen, Yii-Der I.; Hebert, Joan; Pesich, Robert (2001-07-01). "Высокопроизводительное генотипирование с однонуклеотидными полиморфизмами". Genome Research . 11 (7): 1262–1268. doi :10.1101/gr.157801. ISSN  1088-9051. PMC 311112 . PMID  11435409. 
56. Филипович, Роман; Резник, Сьюзан М.; Давацикос, Христос (2011). «Полуконтролируемый кластерный анализ данных изображений». NeuroImage . 54 (3): 2185–2197. doi :10.1016/j.neuroimage.2010.09.074. PMC 3008313 . PMID  20933091. 
57. Ди Марко, Антонио; Навильи, Роберто (2013). «Кластеризация и диверсификация результатов веб-поиска с помощью индукции смысла слов на основе графов». Компьютерная лингвистика . 39 (3): 709–754. doi :10.1162/COLI_a_00148. S2CID  1775181.
58. Bewley, A., & Upcroft, B. (2013). Преимущества использования проекционной структуры для сегментации плотных трехмерных облаков точек. На Австралийской конференции по робототехнике и автоматизации [1]
59. «Отчет об ускорении DevOps в 2022 году». 29 сентября 2022 г.: 8, 14, 74. {{cite journal}}: Цитировать журнал требует |journal=( помощь ) [2]
60. Бьюли, А. и др. «Оценка объема полезной нагрузки драглайна в реальном времени». Международная конференция IEEE по робототехнике и автоматизации . 2011 : 1571–1576.
61. Basak, SC; Magnuson, VR; Niemi, CJ; Regal, RR (1988). «Определение структурного сходства химических веществ с использованием индексов теории графов». Discr. Appl. Math . 19 (1–3): 17–44. doi : 10.1016/0166-218x(88)90004-2 .
62. Хут, Р.; и др. (2008). «Классификации атмосферных циркуляционных моделей: последние достижения и приложения» (PDF) . Ann. NY Acad. Sci . 1146 (1): 105–152. Bibcode : 2008NYASA1146..105H. doi : 10.1196/annals.1446.019. PMID  19076414. S2CID  22655306.
63. Арнотт, Роберт Д. (1 ноября 1980 г.). «Кластерный анализ и параллельная динамика цен на акции». Financial Analysts Journal . 36 (6): 56–62. doi :10.2469/faj.v36.n6.56. ISSN  0015-198X.