Кластерный анализ, реализации и эффекты Опции

[Игорь]

Не в порядке обсуждения, но если оно случится, буду рад.
При реализации классического метода k-средних были замечены интересные вычислительные эффекты. Если указать алгоритму некоторое количество кластеров, на которые будут разбиты объекты, то происходит следующее:
1. Количество [непустых] кластеров не может превысить определенное значение. Если в тестах задать, к примеру, число кластеров, равное числу объектов либо большее реально существующему, то выделено будет определенное количество кластеров. Остальные кластеры будут пустыми с нулевыми центрами.
2. Кластеризация не зависит от начального, например, случайного, разбиения. Из любой начальной конфигурации процесс итерационно сходится к тому же самому разбиению, что и из любой другой начальной конфигурации.
Предполагаем, что:
1. Метод устанавливает истинное распределение объектов по кластерам (конечно, в смысле используемой метрики).
2. Если стоит задача установления истинной конфигурации объектов, количество кластеров для данного метода можно вообще не задавать по той же причине. В результате расчета количество кластеров, объективно существующих в заданном массиве данных, будет равно количеству непустых кластеров.

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

Сообщение отредактировал Игорь - 9.03.2023 - 13:54

[Leonov]

В разделе "Кластерный анализ, реализации и эффекты" по "http://forum.disser.ru/index.php?showtopic=5174" сообщается "..кластеров для данного метода можно вообще не задавать...". Однако при этом не уточняются ненужные детали этого метода. Сам я использую для медиков, биологов, и иных исследователей уже более 40 лет именно много разных методов кластерного анализа. И по всем их используемым базам данных практически всегда и обнаруживаются такие важные и разные кластеры, т.е. как по 2 кластера, так и по 3, и по 4, и т.д. Для чего и необходимо использовать как наборы количественных признаков, так и наборы качественных, группирующих признаков.

[Игорь]

Спасибо за информацию.

Сообщение отредактировал Игорь - 10.04.2023 - 07:29

[Игорь]

Ну вот. Попалось подтверждение представленным выше заблуждениям. Свежий источник Ahmad I. 40 algorithms every programmer should know. - Birmingham: Packt Publishing, 2020. На с. 143 утверждается:
"The k-means algorithm ... comes with the following limitations:
- The biggest limitation of k-means clustering is that the initial number of clusters has to be predetermined.
- The initial assignment of cluster centers is random. This means that each time the algorithm is run, it may give slightly different clusters."
Опыт программирования и расчета не подтверждает данные тезисы.

Сообщение отредактировал Игорь - 12.05.2023 - 10:09

[nokh]

В порядке обсуждения:) Как ни странно, вообще не нашёл полезным для практики метод k-средних. Иерархический анализ хотя и плоховат теоретически, но очень нагляден и в некоторых областях почти незаменим. Особенно это касается двойной кластеризации в сочетании с построением кластерной тепловой карты (cluster heatmap) для однородных наборов признаков. Последнее время очень полюбил эту технику: позволяет увидеть всё и сразу + под разные задачи можно выбирать разные меры расстояний между объектами. Под "плоховат" я имею в виду по-сути взвешивание решения в зависимости от набора признаков: паттерн нескольких коррелирующих показателей перевесит вклад остальных и в дендрограмме мы увидим ветвления лишь по этому паттерну. Поэтому если использую иерархический КА, то уже после редукции данных - обычно на факторных метках нелинейного анализа главных компонент. Это снимает и проблему взвешивания, и проблему одновременного анализа количественных и порядковых (ранговых и номинальных) признаков. Кластерная ТК позволяет интерпретировать кластеры сразу, однако если сильно нужно - можно провести сравнения мер положения показателей в полученных кластерах. Отличная индуктивная техника для генерации гипотез.

Практическая польза метода к-средних туманна. Предположим, с помощью иерархического КА я определился с числом кластеров, а теперь задаю его в методе к-средних и получаю какое-то решение. Возможно оно будет очень близким к исходному, а что дальше? Дальше я вынужден сравнивать исходное и конечное решение, частично заново интерпретировать результаты и только потому, что обычно программы удобно реализуют сравнения выделенных кластеров по набору показателей. Но по-сути это двойная работа с отсутствием необходимости второго этапа. Теперь предположим, что мы заранее знаем число кластеров. Например, больные и здоровые, 3-4 вида операции и т.п. Нет никаких гарантий, что метод к-средних сформирует именно эти кластеры, да и вообще для такого дедуктивного подхода существуют замечательные ограниченные ординационные техники (constrained ordination): канононический анализ соответствий (ССА) и анализ избыточности (RDA) с различными модификациями. Они "достанут" именно ту часть изменчивости, которая задаётся болезнью, полом, видами операций и т.д. Сюда же можно отнести "between group PCA", а также варианты дискриминантного анализа, позволяющего строить модель для отнесения объекта к группе или PLS-регрессию, позволяющую строить модель зависимости набора откликов от набора предикторов. А сколько всего сейчас появляется нового, интересного и всегда хоть в чём-то лучше предшественников... достаточно погулять по ссылкам к описанию каких-нибудь новых или адаптации старых техник для машинного обучения, распознавания образов, молекулярно-генетических задач. И вот не вижу здесь места методу k-средних.

Сообщение отредактировал nokh - 10.05.2023 - 21:31

[100$]

Даёшь вместо метода к - средних статистику Гопкинса!
Ссылка

[ИНО]

ИМХО, задача метода k-средних довольно специфическая, типа "я априори знаю, что есть столько-то кластеров, но не знаю, какие именно наблюдения к какому из них относятся, пусть за меня их рассортирует сделает алгоритм. Не встречался с такой задачей на практике, но она представляется вполне реальной, хотя и далеко не самой распространенной. И не представляю как что-либо из сборной солянки разнородных методов, перечисленных nokh, можно было бы применить для ее решения. Они не лучше метода k-средних, они для другого.

[ИНО]

Даёшь вместо метода к - средних статистику Гопкинса!
Ссылка

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

[passant]

....

Сообщение отредактировал passant - 12.05.2023 - 09:40

[Игорь]

... какое отношение имеет статистика Хопкинса-Скеллама к кластеризации методом К-средних

В R так делают: https://ranalytics.github.io/data-mining/10...ng-Quality.html

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

Авторы монографии утверждают, что алгоритмы взяты из исследований по распределению звезд.

Сообщение отредактировал Игорь - 12.05.2023 - 14:39

[ИНО]

Игорь, спасибо за полезную ссылку. Однако там предлагают использовать статистику Хопикнса-Скеллама не для проверки "правильности" конкретной кластеризации, а лишь для определения "общей предрасположенности имеющихся данных к объединению в кластеры" - то есть примерно то же самое, для ее обычно применяют, только с переносом из реального физического пространства в некое абстрактное математическое. В связи с этим совершенно непонятно, каким образом 100$ предлагает применять ее "вместо метода к - средних". Но, думается, можно пойти дальше и применять методы, созданные для анализа пространственных распределений точек (например функции Рипли, Бессага и др. - см. монографию по мое ссылке) для изучения структуры кластеров, выделенных при кластерном анализе, либо чисто визуально на ординационной диаграмме многомерного шкалирования (последнее лично мне больше нравится).

Авторы монографии утверждают, что алгоритмы взяты из исследований по распределению звезд.

Какие именно методы и какой конкретной монографии?

[Игорь]

Какие именно методы ...?

Кластерного анализа - мы ведь его в данной теме обсуждаем.

... какой конкретной монографии?

Baddeley с соавт., на которую Вы ссылку дали - мы же о ней говорили. С. 459: "Cluster processes were developed in a classic paper Neyman and Scott [499] as models for the spatial pattern of galaxies in the distant universe".

Сообщение отредактировал Игорь - 13.05.2023 - 07:47

[ИНО]

Там страниц много и ссылок на разные методы и области их применения тоже много. Конкретно Хопкинс со Скелламом работали с растениями. Да и все примеры, разобранные в самой обсуждаемой книге ботанические, а не астрономические. Но в контексте данной темы это не важно.

[Blaid]

В порядке обсуждения, как дилетант-любитель, вставлю свои 5 копеек:

1) относительно правильности-неправильности (иначе оптимальности-неоптимальности) кластеризации: чем меньше значение внутригрупповой дисперсии (within SS) и больше значение межгрупповой дисперсии (between SS), тем лучше признак-параметр (характеризуемый по результатам кластерного анализа) определяет принадлежность объектов (или наблюдений) к тому или иному кластеру. Тоже относится к параметрам F и p. Т.е. чем меньше within SS (и чем больше between SS), а также чем меньше р (и чем больше F), тем оптимальнее (ну или качественнее) кластеризация. Самой оптимальной кластеризации соответствуют самые минимальные значения within SS и p, с одной стороны, и самые максимальные значения between SS и F, с другой. В идеале - для всех признаков-параметров кластеризуемых объектов (наблюдений).
Between SS, within SS, p, F - терминология из пакета STATISTICA (но в других пакетах, наверное, примерно также эти параметры обозначаются).
Исходя из вышеизложенного как (на практике) достичь оптимальной кластеризации? - выполняя последовательное разбиение исходной выборки объектов (наблюдений) на различное число кластеров (2, 3, 4 и далее) и сравнивая качество получаемых решений (характеризуемых, помимо прочего такими параметрами как Between SS, within SS, p, F).

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

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

Да, так, конечно, можно и упороться до того, что число кластеров будет равно числу кластеризуемых объектов. Но подобное, по-моему, возможно только в случае наличия в исходной выборке уж слишком непохожих объектов (каждый из которых будет отдельным - одиночным - кластером в итоге). А объединять в одну выборку столь непохожие объекты, наверное, бессмысленно изначально.

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

Сообщение отредактировал Blaid - 20.05.2023 - 20:45

[ИНО]

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