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

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

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

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

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

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

Определение

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

Эти методы не создадут уникального разделения набора данных, а создадут иерархию, из которой пользователю по-прежнему необходимо выбрать подходящие кластеры. Они не очень устойчивы по отношению к выбросам, которые либо проявляются как дополнительные кластеры, либо даже вызывают слияние других кластеров (известное как «явление сцепления», в частности, при кластеризации с одной связью ). В общем случае сложность для агломерационной кластеризации и для спорного кластеризация , что делает их слишком медленным для больших наборов данных. Для некоторых особых случаев известны оптимальные эффективные методы (сложности ): SLINK для однократного связывания и CLINK для кластеризации полного связывания. В сообществе интеллектуального анализа данных эти методы признаны теоретической основой кластерного анализа, но часто считаются устаревшими. Однако они послужили источником вдохновения для многих более поздних методов, таких как кластеризация на основе плотности.

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

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

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

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

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

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

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

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

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

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

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

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

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

Самый популярный метод кластеризации на основе плотности - DBSCAN . В отличие от многих новых методов, он имеет четко определенную кластерную модель, называемую «плотность-достижимость». Подобно кластеризации на основе связей, она основана на соединении точек в пределах определенных пороговых значений расстояния. Однако он соединяет только точки, удовлетворяющие критерию плотности, в исходном варианте, определяемом как минимальное количество других объектов в пределах этого радиуса. Кластер состоит из всех связанных плотностью объектов (которые могут образовывать кластер произвольной формы, в отличие от многих других методов) плюс все объекты, которые находятся в пределах диапазона этих объектов. Еще одно интересное свойство DBSCAN заключается в том, что его сложность довольно низкая - для него требуется линейное количество запросов диапазона в базе данных - и что он обнаружит практически одинаковые результаты (он детерминирован для точек ядра и шума, но не для пограничных точек) при каждом запуске, поэтому нет необходимости запускать его несколько раз. ОПТИКА - это обобщение DBSCAN, которое устраняет необходимость выбора подходящего значения для параметра диапазона и дает иерархический результат, связанный с кластеризацией связей . DeLi-Clu, Density-Link-Clustering сочетает в себе идеи кластеризации с одной связью и OPTICS, полностью исключая параметр и предлагая улучшения производительности по сравнению с OPTICS за счет использования индекса R-дерева .

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

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

Грид-кластеризация

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

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

Недавние улучшения

В последние годы были приложены значительные усилия для повышения производительности существующих алгоритмов. Среди них КЛАРАНС и БЕРЕЗА . В связи с недавней необходимостью обрабатывать все большие и большие наборы данных (также известные как большие данные ) желание торговать семантическим значением сгенерированных кластеров для повышения производительности растет. Это привело к развитию методов предварительной кластеризации, таких как кластеризация навеса , которые могут эффективно обрабатывать огромные наборы данных, но полученные «кластеры» представляют собой всего лишь грубое предварительное разбиение набора данных для последующего анализа разделов с помощью существующих более медленных методов, таких как как k-означает кластеризацию .

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

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

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

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

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

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

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

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

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

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

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

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

Индекс Дэвиса – Боулдина можно рассчитать по следующей формуле:
где n - количество кластеров, - это центроид кластера , - это среднее расстояние от всех элементов в кластере до центроида , и - это расстояние между центроидами и . Поскольку алгоритмы, которые создают кластеры с низкими внутрикластерными расстояниями (высокое внутрикластерное сходство) и высокими межкластерными расстояниями (низкое межкластерное сходство), будут иметь низкий индекс Дэвиса-Боулдина, алгоритм кластеризации, который создает набор кластеров с наименьший индекс Дэвиса – Болдина считается лучшим алгоритмом, основанным на этом критерии.
Индекс Данна направлен на выявление плотных и хорошо разделенных кластеров. Он определяется как отношение минимального межкластерного расстояния к максимальному внутрикластерному расстоянию. Для каждого раздела кластера индекс Данна можно рассчитать по следующей формуле:
где d ( i , j ) представляет собой расстояние между кластерами i и j , а d '( k ) измеряет внутрикластерное расстояние кластера k . Межкластерное расстояние d ( i , j ) между двумя кластерами может быть любым числом мер расстояния, например расстоянием между центроидами кластеров. Точно так же расстояние d '( k ) внутри кластера может быть измерено различными способами, такими как максимальное расстояние между любой парой элементов в кластере  k . Поскольку внутренний критерий ищет кластеры с высоким внутрикластерным сходством и низким межкластерным сходством, более желательны алгоритмы, которые создают кластеры с высоким индексом Данна.
Коэффициент силуэта сравнивает среднее расстояние до элементов в одном кластере со средним расстоянием до элементов в других кластерах. Объекты с высоким значением силуэта считаются хорошо сгруппированными, объекты с низким значением могут быть выбросами. Этот индекс хорошо работает с кластеризацией k- средних, а также используется для определения оптимального количества кластеров.

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

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

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

Как и в случае с внутренней оценкой, существует несколько мер внешней оценки, например:

  • Чистота : Чистота - это мера того, в какой степени кластеры содержат один класс. Его расчет можно представить следующим образом: для каждого кластера подсчитайте количество точек данных из наиболее распространенного класса в указанном кластере. Теперь возьмите сумму по всем кластерам и разделите на общее количество точек данных. Формально, учитывая некоторый набор кластеров и некоторый набор классов , обе точки разбиения данных, чистота может быть определена как:
Эта мера не вредит наличию большого количества кластеров, а большее количество кластеров облегчит получение высокой чистоты. Оценка чистоты 1 всегда возможна, если каждая точка данных помещается в отдельный кластер. Кроме того, чистота не подходит для несбалансированных данных, когда даже плохо работающие алгоритмы кластеризации дадут высокую чистоту. Например, если набор данных размером 1000 состоит из двух классов, один из которых содержит 999 точек, а другой - 1 точку, тогда каждый возможный раздел будет иметь чистоту не менее 99,9%.
Индекс Rand вычисляет, насколько кластеры (возвращенные алгоритмом кластеризации) похожи на эталонные классификации. Его можно вычислить по следующей формуле:
где - количество истинных положительных результатов, - количество истинных отрицательных результатов , - количество ложных срабатываний и - количество ложных отрицательных результатов . Подсчитываемые здесь экземпляры - это количество правильных попарных назначений. То есть - это количество пар точек, которые сгруппированы вместе в предсказанном разделе и в разделе основной истинности, - это количество пар точек, которые сгруппированы вместе в предсказанном разделе, но не в основном разделе истинности и т. Д. набор данных имеет размер N, то .

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

F-меру можно использовать для уравновешивания ложноотрицательных результатов путем взвешивания отзыва с помощью параметра . Пусть точность и отзыв (обе меры внешней оценки сами по себе) определены следующим образом:
где - скорость точности, а - скорость отзыва . Мы можем вычислить F-меру, используя следующую формулу:
Когда , . Другими словами, напоминание не влияет на F-меру , а увеличение присваивает возрастающий вес для вспоминания в финальной F-мере.
Также не учитывается и может неограниченно изменяться от 0 и выше.
Индекс Жаккара используется для количественной оценки сходства между двумя наборами данных. Индекс Жаккара принимает значение от 0 до 1. Индекс 1 означает, что два набора данных идентичны, а индекс 0 указывает, что наборы данных не имеют общих элементов. Индекс Жаккара определяется по следующей формуле:
Это просто количество уникальных элементов, общих для обоих наборов, деленное на общее количество уникальных элементов в обоих наборах.
Также не учитывается и может неограниченно изменяться от 0 и выше.
Симметричная мера Dice удваивает вес, но при этом игнорирует :
Индекс Фаулкса – Мэллоуса вычисляет сходство между кластерами, возвращаемыми алгоритмом кластеризации, и эталонными классификациями. Чем выше значение индекса Фаулкса – Маллоуса, тем более похожи кластеры и эталонные классификации. Его можно вычислить по следующей формуле:
где - количество истинных срабатываний , - количество ложных срабатываний , - количество ложноотрицательных результатов . Индекс представляет собой средний геометрическую точность и отзыв и , и, таким образом , также известный как G-мера, в то время как F-мера является их гармоническим средним. Более того, точность и отзыв также известны как индексы Уоллеса и . Нормализованные по вероятности версии припоминания, точности и G-меры соответствуют информированности , отмеченности и корреляции Мэтьюза и сильно связаны с каппой .
Матрицу неточностей можно использовать для быстрой визуализации результатов алгоритма классификации (или кластеризации). Он показывает, насколько кластер отличается от кластера золотого стандарта.

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

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

Есть несколько формулировок статистики Хопкинса . Типичный из них следующий. Позвольте быть набором точек данных в размерном пространстве. Рассмотрим случайную выборку (без замены) точек данных с членами . Кроме того, генерирует набор из равномерно распределенных случайным образом точек данных. Теперь определим две меры расстояния: расстояние до ближайшего соседа в X и расстояние до ближайшего соседа в X. Затем мы определяем статистику Хопкинса как:
При таком определении однородные случайные данные должны иметь значения, близкие к 0,5, а кластеризованные данные должны иметь значения, близкие к 1.
Однако данные, содержащие только один гауссиан, также будут иметь оценку, близкую к 1, поскольку эта статистика измеряет отклонение от однородного распределения, а не мультимодальности , что делает эту статистику в значительной степени бесполезной в применении (поскольку реальные данные никогда не являются отдаленно однородными).

Приложения

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

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

Медицина

Медицинская визуализация
При сканировании ПЭТ кластерный анализ может использоваться для различения различных типов тканей на трехмерном изображении для различных целей.
Анализ антимикробной активности
Кластерный анализ можно использовать для анализа паттернов устойчивости к антибиотикам, для классификации противомикробных соединений в соответствии с их механизмом действия, для классификации антибиотиков в соответствии с их антибактериальной активностью.
IMRT сегментация
Кластеризацию можно использовать для разделения карты плотности потока на отдельные регионы для преобразования в поля результатов в лучевой терапии на основе MLC.

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

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

Всемирная сеть

Анализ социальных сетей
При изучении социальных сетей кластеризация может использоваться для распознавания сообществ внутри больших групп людей.
Группировка результатов поиска
В процессе интеллектуальной группировки файлов и веб-сайтов кластеризация может использоваться для создания более релевантного набора результатов поиска по сравнению с обычными поисковыми системами, такими как Google . В настоящее время существует ряд сетевых инструментов кластеризации, таких как Clusty . Его также можно использовать для получения более полного набора результатов в тех случаях, когда поисковый запрос может относиться к совершенно разным вещам. Каждое отдельное использование термина соответствует уникальному кластеру результатов, что позволяет алгоритму ранжирования возвращать исчерпывающие результаты, выбирая лучший результат из каждого кластера.
Скользкая оптимизация карты
Карта фотографий Flickr и другие сайты карт используют кластеризацию, чтобы уменьшить количество маркеров на карте. Это ускоряет работу и уменьшает визуальный беспорядок.

Информатика

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

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

Последовательный анализ в социальных науках
Кластерный анализ используется, например, для определения моделей траекторий семейной жизни, профессиональной карьеры и ежедневного или еженедельного использования времени.
Анализ преступности
Кластерный анализ можно использовать для выявления областей, где больше случаев определенных видов преступлений. Выявив эти отдельные области или «горячие точки», где подобное преступление произошло в течение определенного периода времени, можно более эффективно управлять ресурсами правоохранительных органов.
Образовательный интеллектуальный анализ данных
Кластерный анализ, например, используется для выявления групп школ или учащихся со схожими свойствами.
Типологии
На основе данных опросов в проектах, подобных тем, которые осуществляет исследовательский центр Pew Research Center, используется кластерный анализ для выявления типологий мнений, привычек и демографических данных, которые могут быть полезны в политике и маркетинге.

Другие

Полевая робототехника
Алгоритмы кластеризации используются для ситуационной осведомленности роботов, чтобы отслеживать объекты и обнаруживать выбросы в данных датчиков.
Математическая химия
Чтобы найти структурное сходство и т. Д., Например, 3000 химических соединений были сгруппированы в пространстве 90 топологических индексов .
Климатология
Чтобы найти погодные режимы или предпочтительные атмосферные характеристики давления на уровне моря.
Финансы
Кластерный анализ был использован для кластеризации акций по секторам.
Нефтяная геология
Кластерный анализ используется для восстановления недостающих данных керна на забое скважины или недостающих каротажных кривых с целью оценки свойств коллектора.
Геохимия
Кластеризация химических свойств в разных местах образца.

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

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

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

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

Другой

использованная литература