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

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

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

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

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

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

Определение [ править ]

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

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

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

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

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

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

Алгоритмы [ править ]

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

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

Кластеризация на основе подключения (иерархическая кластеризация) [ править ]

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

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

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

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

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

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

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

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

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

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

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

• k -средние не могут представлять кластеры на основе плотности

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

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

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

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

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

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

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

• Кластеры на основе плотности не могут быть смоделированы с использованием гауссовых распределений

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

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

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

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

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

• Примеры кластеризации на основе плотности
• Кластеризация на основе плотности с помощью DBSCAN .

• DBSCAN предполагает наличие кластеров одинаковой плотности и может иметь проблемы с разделением соседних кластеров.

• OPTICS - это вариант DBSCAN, улучшающий обработку кластеров различной плотности.

Грид-кластеризация [ править ]

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

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

Последние события [ править ]

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

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

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

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

Оценка и оценка [ править ]

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

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

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

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

Внутренняя оценка [ править ]

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

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

Существует более десятка внутренних мер оценки, обычно основанных на интуиции, что элементы в одном кластере должны быть более похожими, чем элементы в разных кластерах. ^{[37] : 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 _ {я}}$${\ displaystyle i}$${\ displaystyle c_ {i}}$${\ displaystyle d (c_ {i}, c_ {j})}$${\ displaystyle c_ {i}}$${\ displaystyle c_ {j}}$

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

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

${\ Displaystyle D = {\ гидроразрыва {\ мин _ {1 \ Leq я <J \ Leq n} d (я, j)} {\ макс _ {1 \ Leq к \ Leq n} d ^ {\ prime} ( k)}} \ ,,}$

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

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

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

Внешняя оценка [ править ]

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

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

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

• Чистота : Чистота - это мера того, в какой степени кластеры содержат один класс. ^[36] Его расчет можно представить следующим образом: для каждого кластера подсчитайте количество точек данных из наиболее распространенного класса в указанном кластере. Теперь возьмите сумму по всем кластерам и разделите на общее количество точек данных. Формально, учитывая некоторый набор кластеров и некоторый набор классов , обе точки разбиения данных, чистота может быть определена как:${\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%.

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

Индекс 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}}}$

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

• F-мера

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

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

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

где - скорость точности, а - скорость отзыва . Мы можем вычислить F-меру, используя следующую формулу: ^[36]${\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}}}$

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

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

• Индекс кости

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

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

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

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

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

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

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

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

Кластерная тенденция [ править ]

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

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

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

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

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

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

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

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

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

Медицина [ править ]

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

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

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

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

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

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

Бизнес и маркетинг [ править ]

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

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

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

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

Всемирная паутина [ править ]

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

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

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

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

Оптимизация скользящей карты

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

Информатика [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Социальные науки [ править ]

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

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

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

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

Типологии

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

Другое [ править ]

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

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

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

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

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

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

Финансы

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

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

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

Геохимия

Группировка химических свойств в разных местах образца.

См. Также [ править ]

Викискладе есть медиафайлы, связанные с кластерным анализом .

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

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

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

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

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

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

Другое [ править ]

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

Ссылки [ править ]