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

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

Результат кластерного анализа показан в виде раскраски квадратов на три кластера.

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

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

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

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

Определение

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

• Модели связности : например,иерархическая кластеризациястроит модели на основе удаленной связи.
• Модель центроида : например,алгоритм k-среднихпредставляет каждый кластер одним средним вектором.
• Модели распределения : кластеры моделируются с использованием статистических распределений, таких какмногомерные нормальные распределения,используемыеалгоритмом максимизации ожидания.
• Модель плотности : например,DBSCANиOPTICSопределяют кластеры как связанные плотные области в пространстве данных.
• Модели подпространства : прибикластеризации(также известной как совместная кластеризация или двухмодовая кластеризация) кластеры моделируются как с использованием членов кластера, так и с соответствующими атрибутами.
• Групповые модели :некоторые алгоритмы не предоставляют уточненную модель своих результатов, а просто предоставляют информацию о группировке.
• Модель на основе графа :клика, то есть подмножество узлов вграфе, в котором каждые два узла в подмножестве соединены ребром, может рассматриваться как прототипическая форма кластера. Ослабление требований полной связности (часть ребер может отсутствовать) известны как квазиклики, как валгоритме кластеризации 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 -mean дает формальное определение как задача оптимизации: найти k центров кластеров и назначить объекты ближайшему центру кластера так, чтобы квадраты расстояний от кластера были минимизированы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Примеры кластеризации на основе плотности
• 
  Кластеризация на основе плотности с помощью DBSCAN
• 
  DBSCAN предполагает, что кластеры имеют одинаковую плотность, и могут возникнуть проблемы с разделением соседних кластеров.
• 
  ОПТИКА — это вариант 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]} Среди них КЛАРАНС , ^[20] и БЕРЕЗА . ^[21] В связи с недавней необходимостью обрабатывать все большие и большие наборы данных (также известные как большие данные ), готовность обменивать семантическое значение генерируемых кластеров на производительность растет. Это привело к разработке методов предварительной кластеризации, таких как Canopy Clustering , которые могут эффективно обрабатывать огромные наборы данных, но полученные «кластеры» представляют собой просто грубое предварительное разделение набора данных для последующего анализа разделов с помощью существующих более медленных методов, таких как как k-средства кластеризации .

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

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

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

Оценка и оценка

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

Меры внутренней оценки страдают от той проблемы, что они представляют собой функции, которые сами по себе могут рассматриваться как цель кластеризации. Например, можно кластеризовать набор данных по коэффициенту Силуэта; за исключением того, что для этого не существует известного эффективного алгоритма. Используя такую ​​внутреннюю меру для оценки, можно скорее сравнить сходство задач оптимизации ^[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 -средних, ^{[ нужна ссылка ]} , а также используется для определения оптимального количества кластеров.

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

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

Ряд показателей адаптирован из вариантов, используемых для оценки задач классификации. Вместо подсчета количества раз, когда класс был правильно присвоен одной точке данных (известный как истинные положительные результаты ), такие метрики подсчета пар оценивают, прогнозируется ли, что каждая пара точек данных, которая действительно находится в одном и том же кластере, будет находиться в одном и том же кластере. кластер. ^[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%.

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

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

${\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}$

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

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

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

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

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

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

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

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

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

Кластерная тенденция

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

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

Существует несколько формулировок статистики Хопкинса . ^[49] Типичный пример заключается в следующем. ^[50] Пусть будет набором точек данных в размерном пространстве. Рассмотрим случайную выборку (без замены) точек данных с членами . Также сгенерируйте набор равномерно случайно распределенных точек данных. Теперь определим две меры расстояния: расстояние от ближайшего соседа в 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 . ^{[51] [52]} Часто такие группы содержат функционально связанные белки, такие как ферменты определенного пути или гены, которые совместно регулируются. Высокопроизводительные эксперименты с использованием меток экспрессируемых последовательностей (EST) или микрочипов ДНК могут стать мощным инструментом для аннотации генома  – общего аспекта геномики .

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

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

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

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

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

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

Лекарство

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

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

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

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

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

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

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

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

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

Группировка товаров для покупок

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

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

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

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

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

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

Скользкая оптимизация карты

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

Информатика

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

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

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

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

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

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

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

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

Цепь Маркова, методы Монте-Карло

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

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

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

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

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

DevOps

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

Социальная наука

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

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

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

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

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

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

Типологии

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

Другие

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

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

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

Для нахождения структурного сходства и т. д., например, 3000 химических соединений группировались в пространстве 90 топологических индексов . ^[60]

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

Чтобы найти погодные режимы или предпочтительные атмосферные характеристики давления на уровне моря. ^[61]

Финансы

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

Нефтяная геология

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

Геохимия

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

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

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

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

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

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

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

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

Другой

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

Рекомендации

1. Драйвер и Кребер (1932). «Количественное выражение культурных связей». Публикации Калифорнийского университета по американской археологии и этнологии . Беркли, Калифорния: Издательство Калифорнийского университета. Количественное выражение культурных связей: 211–256. Архивировано из оригинала 06 декабря 2020 г. Проверено 18 февраля 2019 г.
2. Зубин, Джозеф (1938). «Методика измерения единомышленников». Журнал аномальной и социальной психологии . 33 (4): 508–516. дои : 10.1037/h0055441. ISSN  0096-851X.
3. Трайон, Роберт К. (1939). Кластерный анализ: профиль корреляции и ортометрический (факторный) анализ для выделения единств в сознании и личности . Братья Эдвардс.
4. Кеттелл, РБ (1943). «Описание личности: основные черты, разбитые на кластеры». Журнал аномальной и социальной психологии . 38 (4): 476–506. дои : 10.1037/h0054116.
5. Эстивилл-Кастро, Владимир (20 июня 2002 г.). «Почему так много алгоритмов кластеризации - позиционный документ». Информационный бюллетень об исследованиях ACM SIGKDD . 4 (1): 65–75. дои : 10.1145/568574.568575. S2CID  7329935.
6. Джеймс А. Дэвис (май 1967) «Кластеризация и структурный баланс в графиках», Human Relations 20: 181–7
7. Гао, Кэролайн X.; Дуайер, Доминик; Чжу, Е; Смит, Кэтрин Л.; Ду, Лан; Филия, Кейт М.; Байер, Джоанна; Менсинк, Яна М.; Ван, Тереза; Бергмейр, Кристоф; Вуд, Стивен; Коттон, Сью М. (1 сентября 2023 г.). «Обзор методов кластеризации с рекомендациями по применению в исследованиях психического здоровья». Психиатрические исследования . 327 : 115265. doi : 10.1016/j.psychres.2023.115265 . hdl : 10481/84538 . ISSN  0165-1781.
8. Эверитт, Брайан (2011). Кластерный анализ . Чичестер, Западный Суссекс, Великобритания: Wiley. ISBN 9780470749913.
9. Сибсон, Р. (1973). «SLINK: оптимально эффективный алгоритм для метода однозвенной кластеризации» (PDF) . Компьютерный журнал . Британское компьютерное общество. 16 (1): 30–34. дои : 10.1093/comjnl/16.1.30.
10. Дефейс, Д. (1977). «Эффективный алгоритм для метода полной ссылки». Компьютерный журнал . Британское компьютерное общество. 20 (4): 364–366. дои : 10.1093/comjnl/20.4.364.
11. Ллойд, С. (1982). «Квантование по методу наименьших квадратов в PCM». Транзакции IEEE по теории информации . 28 (2): 129–137. дои : 10.1109/TIT.1982.1056489. S2CID  10833328.
12. Кригель, Ганс-Петер ; Крегер, Пер; Сандер, Йорг; Зимек, Артур (2011). «Кластеризация на основе плотности». WIREs Интеллектуальный анализ данных и обнаружение знаний . 1 (3): 231–240. дои : 10.1002/widm.30. S2CID  36920706.
13. Академический поиск Microsoft: наиболее цитируемые статьи по интеллектуальному анализу данных. Архивировано 21 апреля 2010 г. на Wayback Machine : DBSCAN занимает 24-е место при доступе: 18 апреля 2010 г.
14. Эстер, Мартин; Кригель, Ханс-Петер ; Сандер, Йорг; Сюй, Сяовэй (1996). «Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом». В Симудисе, Евангелосе; Хан, Цзявэй; Файяд, Усама М. (ред.). Материалы Второй международной конференции по обнаружению знаний и интеллектуальному анализу данных (KDD-96) . АААИ Пресс . стр. 226–231. ISBN 1-57735-004-9.
15. Анкерст, Михаэль; Брюниг, Маркус М.; Кригель, Ханс-Петер ; Сандер, Йорг (1999). «ОПТИКА: точки упорядочения для определения структуры кластеризации». Международная конференция ACM SIGMOD по управлению данными . АКМ Пресс . стр. 49–60. CiteSeerX 10.1.1.129.6542 . 
16. Ахтерт, Э.; Бём, К.; Крегер, П. (2006). «DeLi-Clu: повышение надежности, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайших пар». Достижения в области обнаружения знаний и интеллектуального анализа данных . Конспекты лекций по информатике. Том. 3918. стр. 119–128. CiteSeerX 10.1.1.64.1161 . дои : 10.1007/11731139_16. ISBN  978-3-540-33206-0.
17. Аггарвал, Чару К.; Редди, Чандан К. (ред.). Кластеризация данных: алгоритмы и приложения . ISBN 978-1-315-37351-5. ОКЛК  1110589522.
18. Скалли, Д. (2010). Кластеризация k-средних в веб-масштабе . Учеб. 19-я WWW.
19. Хуанг, З. (1998). «Расширения алгоритма k -means для кластеризации больших наборов данных с категориальными значениями». Интеллектуальный анализ данных и обнаружение знаний . 2 (3): 283–304. дои : 10.1023/А: 1009769707641. S2CID  11323096.
20. Р. Нг и Дж. Хан. «Эффективный и действенный метод кластеризации для интеллектуального анализа пространственных данных». В: Материалы 20-й конференции VLDB, страницы 144–155, Сантьяго, Чили, 1994 г.
21. Тянь Чжан, Рагху Рамакришнан, Мирон Ливни. «Эффективный метод кластеризации данных для очень больших баз данных». В: Учеб. Международная конференция. по управлению данными, ACM SIGMOD, стр. 103–114.
22. Кригель, Ганс-Петер ; Крегер, Пер; Зимек, Артур (июль 2012 г.). «Подпространственная кластеризация». Междисциплинарные обзоры Wiley: интеллектуальный анализ данных и обнаружение знаний . 2 (4): 351–364. дои : 10.1002/widm.1057. S2CID  7241355.
23. Агравал, Р.; Герке, Дж.; Гунопулос, Д.; Рагхаван, П. (2005). «Автоматическая подпространственная кластеризация многомерных данных». Интеллектуальный анализ данных и обнаружение знаний . 11 :5–33. CiteSeerX 10.1.1.131.5152 . дои : 10.1007/s10618-005-1396-1. S2CID  9289572. 
24. Карин Кайлинг, Ханс-Петер Кригель и Пер Крёгер. Кластеризация подпространств, связанных по плотности, для многомерных данных . В: Учеб. СИАМ Междунар. Конф. по интеллектуальному анализу данных (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. Ахтерт, Э.; Бём, К.; Кригель, HP ; Крегер, П.; Мюллер-Горман, И.; Зимек, А. (2007). «Обнаружение и визуализация иерархий подпространственных кластеров». Достижения в области баз данных: концепции, системы и приложения . Конспекты лекций по информатике. Том. 4443. стр. 152–163. CiteSeerX 10.1.1.70.7843 . дои : 10.1007/978-3-540-71703-4_15. ISBN  978-3-540-71702-7.
27. Ахтерт, Э.; Бём, К.; Крегер, П.; Зимек, А. (2006). «Горные иерархии корреляционных кластеров». 18-я Международная конференция по управлению научными и статистическими базами данных (SSDBM'06) . стр. 119–128. CiteSeerX 10.1.1.707.7872 . дои :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 . дои : 10.1145/1007568.1007620. ISBN  978-1581138597. S2CID  6411037.
29. Ахтерт, Э.; Бом, К.; Кригель, HP ; Крегер, П.; Зимек, А. (2007). «Об исследовании сложных взаимосвязей корреляционных кластеров». 19-я Международная конференция по управлению научными и статистическими базами данных (SSDBM 2007) . п. 7. CiteSeerX 10.1.1.71.5021 . дои : 10.1109/SSDBM.2007.21. ISBN  978-0-7695-2868-7. S2CID  1554722.
30. Мейлэ, Марина (2003). «Сравнение кластеров по изменению информации». Теория обучения и машины ядра . Конспекты лекций по информатике. Том. 2777. стр. 173–187. дои : 10.1007/978-3-540-45167-9_14. ISBN 978-3-540-40720-1.
31. Красков, Александр; Стёгбауэр, Харальд; Анджейак, Ральф Г.; Грассбергер, Питер (1 декабря 2003 г.). «Иерархическая кластеризация на основе взаимной информации». arXiv : q-bio/0311039 . Бибкод : 2003q.bio....11039K. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
32. Ауффарт, Б. (18–23 июля 2010 г.). «Кластеризация с помощью генетического алгоритма со смещенным оператором мутации». Wcci Cec . IEEE.
33. Фрей, Би Джей; Дуек, Д. (2007). «Кластеризация путем передачи сообщений между точками данных». Наука . 315 (5814): 972–976. Бибкод : 2007Sci...315..972F. CiteSeerX 10.1.1.121.3145 . дои : 10.1126/science.1136800. PMID  17218491. S2CID  6502291. 
34. Пфицнер, Дариус; Лейббрандт, Ричард; Пауэрс, Дэвид (2009). «Характеристика и оценка мер сходства пар кластеризаций». Знания и информационные системы . Спрингер. 19 (3): 361–394. дои : 10.1007/s10115-008-0150-6. S2CID  6935380.
35. Фельдман, Ронен; Сэнгер, Джеймс (1 января 2007 г.). Справочник по интеллектуальному анализу текста: продвинутые подходы к анализу неструктурированных данных . Кембриджский университет. Нажимать. ISBN 978-0521836579. ОКЛК  915286380.
36. Вайс, Шолом М.; Индурхья, Нитин; Чжан, Тонг; Дамерау, Фред Дж. (2005). Анализ текста: прогнозные методы анализа неструктурированной информации . Спрингер. ISBN 978-0387954332. ОСЛК  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. дои : 10.1080/01969727408546059.
40. Фарбер, Инес; Гюннеманн, Стефан; Кригель, Ханс-Петер ; Крегер, Пер; Мюллер, Эммануэль; Шуберт, Эрих; Зайдль, Томас; Зимек, Артур (2010). «Об использовании меток классов при оценке кластеризации» (PDF) . В «Папоротнике» Сяоли З.; Дэвидсон, Ян; Дай, Дженнифер (ред.). MultiClust: обнаружение, обобщение и использование нескольких кластеров . АСМ СИГКДД .
41. Пурраджаби, М.; Мулави, Д.; Кампелло, RJGB; Зимек, А. ; Сандер, Дж.; Гебель, Р. (2014). «Выбор модели для полуконтролируемой кластеризации». Материалы 17-й Международной конференции по расширению технологий баз данных (EDBT) . стр. 331–342. дои : 10.5441/002/edbt.2014.31.
42. Рэнд, WM (1971). «Объективные критерии оценки методов кластеризации». Журнал Американской статистической ассоциации . Американская статистическая ассоциация. 66 (336): 846–850. arXiv : 1704.01036 . дои : 10.2307/2284239. JSTOR  2284239.
43. Фаулкс, Э.Б.; Маллоуз, CL (1983). «Метод сравнения двух иерархических кластеров». Журнал Американской статистической ассоциации . 78 (383): 553–569. дои : 10.1080/01621459.1983.10478008. JSTOR  2288117.
44. Пауэрс, Дэвид (2003). Напомним и точность против букмекера . Международная конференция по когнитивной науке. стр. 529–534.
45. Араби, П. (1985). «Сравнение разделов». Журнал классификации . 2 (1): 1985. doi : 10.1007/BF01908075. S2CID  189915041.
46. Уоллес, DL (1983). "Комментарий". Журнал Американской статистической ассоциации . 78 (383): 569–579. дои : 10.1080/01621459.1983.10478009.
47. Пауэрс, Дэвид (2012). Проблема с Каппой . Европейское отделение Ассоциации компьютерной лингвистики. стр. 345–355.
48. Луна-Ромера, Хосе Мария; Мартинес-Баллестерос, Мария; Гарсиа-Гутьеррес, Хорхе; Рикельме, Хосе К. (июнь 2019 г.). «Индекс достоверности внешней кластеризации на основе статистического теста хи-квадрат». Информационные науки . 487 : 1–17. doi :10.1016/j.ins.2019.02.046. hdl : 11441/132081 . S2CID  93003939.
49. Хопкинс, Брайан; Скеллам, Джон Гордон (1954). «Новый метод определения типа распространения растительных особей». Анналы ботаники . Annals Botany Co. 18 (2): 213–227. doi : 10.1093/oxfordjournals.aob.a083391.
50. Банерджи, А. (2004). «Проверка кластеров с использованием статистики Хопкинса». Международная конференция IEEE по нечетким системам, 2004 г. (каталожный номер IEEE 04CH37542) . Том. 1. С. 149–153. дои : 10.1109/FUZZY.2004.1375706. ISBN 978-0-7803-8353-1. S2CID  36701919.
51. Джонсон, Стивен К. (1 сентября 1967). «Иерархические схемы кластеризации». Психометрика . 32 (3): 241–254. дои : 10.1007/BF02289588. ISSN  1860-0980. PMID  5234703. S2CID  930698.
52. Хартув, Эрез; Шамир, Рон (31 декабря 2000 г.). «Алгоритм кластеризации, основанный на связности графов». Письма об обработке информации . 76 (4): 175–181. дои : 10.1016/S0020-0190(00)00142-3. ISSN  0020-0190.
53. Ремм, Майдо; Шторм, Кристиан Э.В.; Зоннхаммер, Эрик Л.Л. (14 декабря 2001 г.). «Автоматическая кластеризация ортологов и паралогов на основе парных сравнений видов 11. Под редакцией Ф. Коэна». Журнал молекулярной биологии . 314 (5): 1041–1052. дои : 10.1006/jmbi.2000.5197. ISSN  0022-2836. ПМИД  11743721.
54. Ботштейн, Дэвид; Кокс, Дэвид Р.; Риш, Нил; Олшен, Ричард; Керб, Дэвид; Дзау, Виктор Дж.; Чен, Юй-Дер И.; Эберт, Джоан; Песич, Роберт (1 июля 2001 г.). «Высокопроизводительное генотипирование с однонуклеотидными полиморфизмами». Геномные исследования . 11 (7): 1262–1268. дои : 10.1101/гр.157801. ISSN  1088-9051. ПМК 311112 . ПМИД  11435409. 
55. Филипович, Роман; Резник, Сьюзен М.; Давацикос, Христос (2011). «Полуконтролируемый кластерный анализ данных визуализации». НейроИмидж . 54 (3): 2185–2197. doi :10.1016/j.neuroimage.2010.09.074. ПМК 3008313 . ПМИД  20933091. 
56. Ди Марко, Антонио; Навильи, Роберто (2013). «Кластеризация и диверсификация результатов веб-поиска с помощью графической индукции смысла слов». Компьютерная лингвистика . 39 (3): 709–754. дои : 10.1162/COLI_a_00148. S2CID  1775181.
57. Бьюли А. и Апкрофт Б. (2013). Преимущества использования структуры проекции для сегментации плотных трехмерных облаков точек. На Австралийской конференции по робототехнике и автоматизации [1]
58. «Отчет об ускоренном состоянии DevOps за 2022 год» . 29 сентября 2022 г.: 8, 14, 74. {{cite journal}}: Для цитирования журнала требуется |journal=( помощь ) [2]
59. Бьюли, А.; и другие. «Оценка объема полезной нагрузки драглайна в режиме реального времени». Международная конференция IEEE по робототехнике и автоматизации . 2011 : 1571–1576.
60. Басак, Южная Каролина; Магнусон, VR; Ниеми, CJ; Регал, Р.Р. (1988). «Определение структурного сходства химических веществ с использованием теоретико-графовых индексов». Дискр. Прил. Математика . 19 (1–3): 17–44. дои : 10.1016/0166-218x(88)90004-2 .
61. Хут, Р.; и другие. (2008). «Классификации моделей атмосферной циркуляции: последние достижения и применения» (PDF) . Анна. Н-Й акад. Наука . 1146 (1): 105–152. Бибкод : 2008NYASA1146..105H. дои : 10.1196/анналы.1446.019. PMID  19076414. S2CID  22655306.
62. Арнотт, Роберт Д. (1 ноября 1980 г.). «Кластерный анализ и движение цен на акции». Журнал финансовых аналитиков . 36 (6): 56–62. дои : 10.2469/faj.v36.n6.56. ISSN  0015-198X.