кластеризация

[AndreyL]

Друзья!

Возник вопрос по кластерному анализу. Как указывают все специалисты в кластерном анализе, решением задачи кластерного анализа является разбиение, оптимизирующее некоторую целевую функцию. Для каждого метода эта функция своя. Интерес представляют целевые функции, связанные с агломерацией (иерархическими методами).
Пусть, например, имеется некоторое разбиение $X=\left\{\left\{x_{1,1},..x_{1,n_1}\right\},\left\{x_{2,1},..x_{2,n_2}\right\},..,\left\{x_{K,1},..x_{K,n_K}\right\}\right\}$, состоящее из $K$ кластеров, в каждом из которых $n_k$ элементов, $k=1..K$. Разбиение сделано по правилам кластерного анализа, т.е. все кластеры непустые и не пересекаются. Есть мера различия двух элементов $d \left( x_{k,i},x_{k,j} \right)$.

Так, например, для метода ближнего соседа (Single) целевой функцией будет

$$\sum_{k=1}^K \sum_{i=1}^{n_k} \min_{j=1..n_k} d\left(x_{k,i},x_{k,j} \right)$$

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

Для метода дальнего соседа (Complete) целевая функция

$$\sum_{k=1}^K \sum_{i=1}^{n_k} \max_{j=1..n_k} d\left(x_{k,i},x_{k,j} \right)$$

а, для метода среднего расстояния (Average)

$$\sum_{k=1}^K \sum_{i=1}^{n_k} \frac {1}{n_k} \sum_{j=1}^{n_k} d\left(x_{k,i},x_{k,j} \right)$$

Для метода Варда (Ward), если я не ошибся, целевая функция должна быть

$$\sum_{k=1}^K \sum_{i=1}^{n_k} \frac {1}{n_k} \sum_{j=1}^{n_k} d^2\left(x_{k,i},x_{k,j} \right)$$

т.е как сумма средних квадратов внутрикластерных расстояний. Может быть не сумма средних квадратов внутрикластерных расстояний, а просто сумма квадратов внутрикластерных расстояний - к сожалению, нигде в литературе не нашел.

Обычно в литературе и в программном обеспечении имеются еще методы "WeightedAverage", "Centroid", "Median". Не мог бы кто нибудь подсказать, как будут выглядеть целевые функции для этих методов? Или подсказать литературу по этому вопросу.

[provincialka]

AndreyL в сообщении #1257133 писал(а):

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

Точно? Это для меня новость... Мне-то как раз казалось, что многие методы чисто эвристические и никакую функцию не оптимизируют.. Только k-means является приятным исключением. Да и то он дает только локальный минимум.

-- 20.10.2017, 19:34 --

Вот, возьмем функцию, которую вы предложили для "ближайшего соседа". Рассмотрите тривиальное разбиение, в котором каждый элемент составляет кластер. Чему будет равно значение вашей функции? Впрочем, в таком виде, как вы записали, она вообще всегда равна 0, потому что $\min_j(d(x_i,x_j))=d(x_i,x_i) = 0$

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

[AndreyL]

provincialka в сообщении #1257299 писал(а):

Точно? Это для меня новость... Мне-то как раз казалось, что многие методы чисто эвристические и никакую функцию не оптимизируют.. Только k-means является приятным исключением. Да и то он дает только локальный минимум.

Читаем классиков:
Дюран, Оделл, параграф 1.2, второй абзац
"Решением задачи кластерного анализа является разбиение, удовлетворяющее некоторому критерию оптимальности. Этот критерий может представлять собой некоторый функционал, выражающий уровни желательности различных разбиений и группировок. Этот функционал часто называют целевой функцией."

В моем понимании именно таки должно быть, иначе совсем не понятно, что делает конкретный метод.

Мандель, параграф 2.1.1, там правда много написано, но смысл в конечном счете тот-же, а в таблице 2.5 ажно 46 функционалов качества кластеризации, но нет четкого соответствия методам.

provincialka в сообщении #1257299 писал(а):

Вот, возьмем функцию, которую вы предложили для "ближайшего соседа". Рассмотрите тривиальное разбиение, в котором каждый элемент составляет кластер. Чему будет равно значение вашей функции? Впрочем, в таком виде, как вы записали, она вообще всегда равна 0, потому что $\min_j(d(x_i,x_j))=d(x_i,x_i) = 0$.

Да, здесь я погрешил против истины при упрощении - конечно, нужно было еще поставить условие $i \neq j$, в кластерах с одним элементом суммы будут просто нулевыми.

provincialka в сообщении #1257299 писал(а):

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

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

[provincialka]

AndreyL в сообщении #1259236 писал(а):

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

Ну что... благие пожелания!

AndreyL в сообщении #1259236 писал(а):

ажно 46 функционалов качества кластеризации, но нет четкого соответствия методам.

Хм... И почему бы это? Странно ведь!

AndreyL в сообщении #1259236 писал(а):

нужно было еще поставить условие $i \neq j$, в кластерах с одним элементом суммы будут просто нулевыми.

Уверяю вас, это ничего не спасет. Ну, будут вместо одноэлементых двухэлементные классы. Да и не будут! Вот скажите, чему будет равно значение вашего первого функционала при разбиении множества $\{x_1,..., x_n\}$ на подмножества $\{x_1,x_2\}\cup \{x_2\} \cup... \cup \{x_n\}$. То есть все кластеры, кроме одного -- одноэлементные.

Честно говоря, я встречала в литературе другие (более разумные) целевые функции. Они весьма громоздки и не очень-то интуитивно понятны/хороши. Но сильно я в них не вдумывалась, именно из-за того, что алгортмы кластеризации в основном чисто эвристические, и к оптимизации имеют малое отношение... Нет, не говорю, что все, но многие.

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

-- 26.10.2017, 19:29 --

Не могу утверждать уверенно, но мне кажется, вы не совсем поняли суть иерархичекого метода и различие его разновидностей.. Может, напишете сюда, например, вариант с методом complete? И для чего, собственно, этот метод применяется? На каком этапе алгоритма?

-- 26.10.2017, 19:31 --

AndreyL в сообщении #1259236 писал(а):

иерархические алгоритмы, причем с заранее заданным количеством кластеров.

А с заданным! Ну, это другое дело... Хотя обычно так не делают: дендрограмма строится безотносительно числа кластеров, а потом уже режется на нужном уровне на "ветки".

[AndreyL]

provincialka в сообщении #1259345 писал(а):

Вот скажите, чему будет равно значение вашего первого функционала при разбиении множества $\{x_1,..., x_n\}$ на подмножества $\{x_1,x_2\}\cup \{x_2\} \cup... \cup \{x_n\}$. То есть все кластеры, кроме одного -- одноэлементные.

Значение первого, второго и третьего функционалов будут одинаковые $d\left(x_1,x_2 \right)$, четвертого $d^2 \left(x_1,x_2 \right)$, и действительно, первое объединение (количество кластеров $n-1$) для этих четырех методов всегда одинаковое.

provincialka в сообщении #1259345 писал(а):

Честно говоря, я встречала в литературе другие (более разумные) целевые функции. Они весьма громоздки и не очень-то интуитивно понятны/хороши. Но сильно я в них не вдумывалась, именно из-за того, что алгортмы кластеризации в основном чисто эвристические, и к оптимизации имеют малое отношение... Нет, не говорю, что все, но многие.

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

Я в книжках тоже видел много целевых функций, только нигде пока не нашел, какому методу из выше названых они могли бы соответствовать.

provincialka в сообщении #1259345 писал(а):

А с заданным! Ну, это другое дело... Хотя обычно так не делают: дендрограмма строится безотносительно числа кластеров, а потом уже режется на нужном уровне на "ветки".

Обычно - да, но у меня очень частный случай, где я заранее задаю количество кластеров.

[provincialka]

Дело в другом: вам зачем нужна эта целевая функция? Что она даст? Для понимания содержательной постановки -- это вряд ли нужно.

AndreyL в сообщении #1259358 писал(а):

и действительно, первое объединение (количество кластеров $n-1$) для этих четырех методов всегда одинаковое.

Какое отношение это имеет к целевой функции??

[provincialka]

AndreyL
Может быть вы имеете в виду, что на каждом шаге алгоритма "склейки кластеров" минимизируется соотвествующий функционал? Хм... как-то не замечала.. По крайней мере, в описании ничего такого не сказано.

-- 26.10.2017, 23:54 --

[AndreyL]

provincialka в сообщении #1259428 писал(а):

AndreyL
Может быть вы имеете в виду, что на каждом шаге алгоритма "склейки кластеров" минимизируется соотвествующий функционал? Хм... как-то не замечала.. По крайней мере, в описании ничего такого не сказано.

Можно и так сказать. Ведь после построения дендрограммы мы все равно разобьем весь набор на несколько. И вот эта разбивка, по идее, должна обеспечивать минимум какого-то функционала.

[provincialka]

AndreyL в сообщении #1259485 писал(а):

по идее, должна

Только "по идее". Иерархический алгоритм -- полностью эвристический, насколько я знаю.
Мне все-таки так и непонятно, а зачем вам, чтобы обеспечивался минимум какого-то функционала? Могу предположить одну причину: от вида функционала зависит тип разбиения. Но, боюсь, связь тут сильно отдаленная. Я же недаром предложила вам картинку.

Метод "ближайшего соседа" дал весьма корявое распределение на два класса (в "красном" классе всего один элемент!) И это довольно типично.
Метод "полной связи" дает более "компактные" "округлые" кластеры... Это неплохо, хотя в некоторых случаях нам важнее, что элементы "плотно заполняют" пространство кластера. Ну, вроде как такие "облака".

[AndreyL]

provincialka в сообщении #1259703 писал(а):

Только "по идее". Иерархический алгоритм -- полностью эвристический, насколько я знаю.

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

provincialka в сообщении #1259703 писал(а):

Мне все-таки так и непонятно, а зачем вам, чтобы обеспечивался минимум какого-то функционала? Могу предположить одну причину: от вида функционала зависит тип разбиения. Но, боюсь, связь тут сильно отдаленная. Я же недаром предложила вам картинку.

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

provincialka в сообщении #1259703 писал(а):

Метод "ближайшего соседа" дал весьма корявое распределение на два класса (в "красном" классе всего один элемент!) И это довольно типично.

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

provincialka в сообщении #1259703 писал(а):

Метод "полной связи" дает более "компактные" "округлые" кластеры... Это неплохо, хотя в некоторых случаях нам важнее, что элементы "плотно заполняют" пространство кластера. Ну, вроде как такие "облака".

Согласен, но моя задача заметно сложнее. Начнем с того, что она минимум 10-тимерная.

[provincialka]

AndreyL жаль, что остальной народ не подтягивается к обсуждению. Я конкретно с точки зрения целевых функций этой темой не интересовалась.
Но я все-таки так и не поняла, для чего вам нужна целевая функция. Чтобы упомянуть в работе, для научности? Или вы считаете, что, зная ее, вы узнаете, какого типа результат получится при кластеризации?

В общем, нужна постановка задачи, чего вы хотите от знания ц.ф. добиться.

[AndreyL]

provincialka в сообщении #1259726 писал(а):

AndreyL жаль, что остальной народ не подтягивается к обсуждению. Я конкретно с точки зрения целевых функций этой темой не интересовалась.
Но я все-таки так и не поняла, для чего вам нужна целевая функция. Чтобы упомянуть в работе, для научности? Или вы считаете, что, зная ее, вы узнаете, какого типа результат получится при кластеризации?

Я в своих работах и словосочетания такие, как "кластерный анализ", "целевая функция" и "функционал качества" не употребляю - побьют хуже чем за непарламентскую лексику. Интересует только результат их работы.

provincialka в сообщении #1259726 писал(а):

В общем, нужна постановка задачи, чего вы хотите от знания ц.ф. добиться.

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

[provincialka]

AndreyL в сообщении #1259733 писал(а):

подбор метрики

А вот тут как раз возникает вопрос: из каких соображений "подбор"?
По моему скромному опыту, в подобных задачах мало что можно формализовать, поэтому я больше полагаюсь на здравый смысл и статистический эксперимент... ну, я только преподаю немножко эти темы, не практик.

[AndreyL]

provincialka в сообщении #1259734 писал(а):

А вот тут как раз возникает вопрос: из каких соображений "подбор"?

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

[provincialka]

AndreyL
Не о том речь. А о том, чем одна метрика лучше другой. Вот, на основе метрики вы сделали кластеризацию? Или функционал посчитали? Или что?
Почему какая-то конкретная метрика "лучше"? к какому "идеалу" она приближается?