Выбор метода кластеризации

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

Кто-нибудь есть какие-либо рекомендации о том, как выбрать среди различных алгоритмов / методов кластеризации и меры расстояния ? Как это связано с природой переменных (например, категориальных или числовых) и проблемой кластеризации? Есть ли оптимальная техника?

Нет однозначного ответа на ваш вопрос, поскольку даже в рамках одного и того же метода выбор расстояния для представления сходства отдельных лиц может привести к разным результатам, например, при использовании евклидовых и квадратичных евклидовых в иерархической кластеризации. В качестве другого примера, для двоичных данных вы можете выбрать индекс Жакара в качестве меры сходства и продолжить классическую иерархическую кластеризацию; но есть альтернативные подходы, такие как Мона ( Монотетический анализ) алгоритм, который рассматривает только одну переменную одновременно, в то время как другие иерархические подходы (например, классический HC, Agnes, Diana) используют все переменные на каждом шаге. Метод k-средних был расширен различными способами, включая разделение вокруг медоидов (PAM) или репрезентативных объектов, а не центроидов (Kaufman and Rousseuw, 1990), или нечеткую кластеризацию (Chung and Lee, 1992). Например, основное различие между k-средних и PAM состоит в том, что PAM сводит к минимуму сумму различий, а не сумму квадратов евклидовых расстояний; Нечеткая кластеризация позволяет учитывать «частичное членство» (мы сопоставляем каждому наблюдению вес, отражающий членство в классе). И для методов, основанных на вероятностной структуре, или так называемой кластеризации на основе моделей (или анализа скрытого профиля)для психометристов), есть отличный пакет: Mclust . Таким образом, вам необходимо подумать о том, как определить сходство отдельных лиц, а также метод связывания отдельных лиц (рекурсивная или итеративная кластеризация, строгое или нечеткое членство в классе, неконтролируемый или полуконтролируемый подход и т. Д.).

Обычно, чтобы оценить стабильность кластера, интересно сравнить несколько алгоритмов, которые в основном «разделяют» некоторое сходство (например, k-средних и иерархическая кластеризация, потому что евклидово расстояние работает для обоих). Для оценки соответствия между двумя кластерными решениями были предложены некоторые указатели в ответ на этот вопрос: где вырезать дендрограмму? (см. также перекрестные ссылки для других ссылок на этом сайте). Если вы используете R, вы увидите, что несколько пакетов уже доступны в представлении задач по кластерному анализу, и несколько пакетов включают виньетки, которые объясняют конкретные методы или предоставляют тематические исследования.

Кластерный анализ: основные понятия и алгоритмы дают хороший обзор нескольких методов, используемых в кластерном анализе. Что касается хорошей недавней книги с иллюстрациями R, я бы порекомендовал главу 12 «Изенман», « Современные многомерные статистические методы» (Springer, 2008). Несколько других стандартных ссылок даны ниже:

• Кормак Р., 1971. Обзор классификации. Журнал Королевского статистического общества, A 134, 321–367.
• Эверитт Б., 1974. Кластерный анализ . Лондон: Heinemann Educ. Книги.
• Гордон А., 1987. Обзор иерархической классификации. Журнал Королевского статистического общества, A 150, 119–137.
• Гордон А., 1999. Классификация , 2-е издание. Чепмен и Холл.
• Кауфман Л., Руссеу П., 1990. Поиск групп в данных: введение в кластерный анализ . Нью-Йорк, Вили.

Цитата Хасти, Тибширани и Фридмана, Элементы статистического обучения , с. 506:

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

(Тем не менее, было бы неплохо, если бы (wibni) был сайт, где студенты могли бы попробовать несколько алгоритмов и метрик для нескольких небольших стандартных наборов данных?)

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

В любом случае это не гарантирует наилучшего результата, поэтому я бы использовал программу, которая позволяет методично запускать различные кластерные алгоритмы, такие как weka, RapidMiner или даже R (не визуально). Там я установлю программу на запустить все разные алгоритмы кластеризации, которые я могу, со всеми возможными различными расстояниями, и, если им нужны параметры, поэкспериментировать каждый с различными значениями параметров (кроме того, если я не знаю количество кластеров, запустите каждый с различными из чисел этого). Завершив эксперимент, оставьте его включенным, но не забудьте где-то хранить результаты каждого запуска кластеризации.

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

• SSE: сумма квадратичной ошибки от элементов каждого кластера.

• Межкластерное расстояние: сумма квадратного расстояния между центроидами каждого кластера.

• Внутрикластерное расстояние для каждого кластера: сумма квадратного расстояния от элементов каждого кластера до его центроида.

• Максимальный радиус: наибольшее расстояние от экземпляра до его центроида кластера.

• Средний радиус: сумма наибольшего расстояния от экземпляра до его центроида кластеров, деленная на количество кластеров.

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

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

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

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

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

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

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

PS: все они связаны с числовыми значениями, а не категориальными. Я не уверен, как можно было бы объединить категориальные данные.

Вот краткое изложение нескольких алгоритмов кластеризации, которые могут помочь ответить на вопрос

"Какой метод кластеризации я должен использовать?"

Там нет объективно «правильно» алгоритм кластеризации реф

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

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

[1] Модели подключения: Создание моделей на основе дистанционной связи. Например, иерархическая кластеризация. Используется, когда нам нужно различное разбиение в зависимости от высоты среза дерева. Функция R: hclust в пакете статистики.

[2] Модели Centroid: строит модели, представляя каждый кластер одним средним вектором. Используется, когда нам нужно четкое разбиение (в отличие от нечеткой кластеризации, описанной ниже). Функция R: kmeans в пакете статистики.

[3] Модели распределения: строит модели на основе статистических распределений, таких как многовариантные нормальные распределения, используемые алгоритмом максимизации ожидания. Используется, когда формы кластеров могут быть произвольными в отличие от k-средних, которые предполагают круговые кластеры. Функция R: emcluster в пакете emcluster.

[4] Модели плотности: строит модели на основе кластеров как связанных плотных областей в пространстве данных. Например, DBSCAN и OPTICS. Используется, когда формы кластеров могут быть произвольными в отличие от k-средних, которые предполагают круговые кластеры. Функция R dbscan в пакете dbscan.

[5] Подпространственные модели: создает модели на основе элементов кластера и соответствующих атрибутов. Например, бикластеризация (также известная как совместная кластеризация или двухрежимная кластеризация). Используется, когда требуется одновременная кластеризация строк и столбцов. R-функция biclust в упаковке biclust.

[6] Групповые модели: создает модели на основе информации о группировке. Например, совместная фильтрация (алгоритм рекомендации). Функция R Рекомендатор в пакете Recommenderlab.

[7] Основанные на графике модели: Строит модели, основанные на клике. Алгоритмы обнаружения структуры сообщества пытаются найти плотные подграфы в ориентированных или неориентированных графах. Например, функция R cluster_walktrap в пакете igraph.

[8] Карта самоорганизующихся функций Кохонена: строит модели на основе нейронной сети. R функция сом в пакете Кохонена.

[9] Спектральная кластеризация: строит модели на основе невыпуклой кластерной структуры или когда мера центра не является подходящим описанием полного кластера. R-функция specc в пакете kernlab.

[10] подпространственная кластеризация: для многомерных данных функции расстояния могут быть проблематичными. Кластерные модели включают соответствующие атрибуты для кластера. Например, функция hddc в пакете R HDclassif.

[11] Кластеризация последовательностей: групповые последовательности, которые связаны между собой. rBlast пакет.

[12] Распространение сродства: Создание моделей на основе передачи сообщений между точками данных. Это не требует определения количества кластеров перед запуском алгоритма. Это лучше для определенных задач компьютерного зрения и вычислительной биологии, например, кластеризации изображений человеческих лиц и идентификации регулируемых транскриптов, чем k-средних, Ref Rpackage APCluster.

[13] Потоковая кластеризация: создает модели на основе постоянно поступающих данных, таких как телефонные записи, финансовые транзакции и т. Д. Например, пакет BIRCH R [ https://cran.r-project.org/src/contrib/Archive/birch/]

[14] Кластеризация документов (или текстовая кластеризация): строит модели на основе SVD. Используется в теме извлечения. Например, Carrot [ http://search.carrot2.org] - это механизм кластеризации результатов поиска с открытым исходным кодом, который может группировать документы по тематическим категориям.

[15] Модель скрытого класса: она связывает набор наблюдаемых многомерных переменных с набором скрытых переменных. LCA может использоваться в совместной фильтрации. Функция R Recommender в пакете Recommenderlab имеет функцию совместной фильтрации.

[16] Бикластеризация: используется для одновременной кластеризации строк и столбцов двухрежимных данных. Например, функция R biclust в упаковке biclust.

[17] Мягкая кластеризация (нечеткая кластеризация): каждый объект в определенной степени принадлежит каждому кластеру. Например, функция Fclust в пакете fclust.