Постановка задачи кластеризации

[_rip_]

Hi All!

Господа, тут возник такой вопрос.
Хочу выдать на избиение рассуждения посвященные постановке задачи кластеризации.

Причина, в одной из веток http://dxdy.ru/topic35379.html я поднял тему решения задачи кластеризации методом генетических алгоритмов. Худо бедно, задача была решена, заказчика как говорится все удовлетворило, но не удовлетворило меня.

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

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

1. Среднее внутрикластерное расстояние должно стремиться к min

$F_1 = \frac {\sum\limits_{i<j}[y_i = y_j]]\rho(x_i,x_j)} {\sum\limits_{i<j}[y_i = y_j]} \to min$

2. Среднее межкластерное расстояние должно стремиться к max

$F_2 = \frac {\sum\limits_{i<j}[y_i \neq y_j]]\rho(x_i,x_j)} {\sum\limits_{i<j}[y_i \neq y_j]} \to max$

где $\rho(x_i,x_j)$ - расстояние между двумя объектами
$y_i,y_j$ - кластера

Т.е. при ${\phi = \frac {F_1} {F_2}} \to min$ будет достигаться "лучшее разбиение" на кластеры

В чем я не прав?

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

[Gortaur]

Насколько я понимаю, Вы хотите характеризовать разбиение на кластеры, т.е. ввести некоторые ограничения а-ля чему должна удовлетворять "стандартная кластеризация по _rip_". Не могли бы Вы привести более четкое описание своих условий, например что Вы в точности имеете ввиду под $x_i$ и $y_i$?

[_rip_]

Gortaur в сообщении #380917 писал(а):

Насколько я понимаю, Вы хотите характеризовать разбиение на кластеры, т.е. ввести некоторые ограничения а-ля чему должна удовлетворять "стандартная кластеризация по _rip_". Не могли бы Вы привести более четкое описание своих условий, например что Вы в точности имеете ввиду под $x_i$ и $y_i$?

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

Есть некоторое множество $X$ которому принадлежит $i$-й т.е. элемент $x_i$ входящий в кластер $y_i$

[Gortaur]

У Вас фиксированное число кластеров? И почему Вы спршиваете, в чем Вы не правы - возможно, Вы правы.

[_rip_]

Gortaur в сообщении #380965 писал(а):

У Вас фиксированное число кластеров? И почему Вы спршиваете, в чем Вы не правы - возможно, Вы правы.

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

Кстати, кол-во кластеров фиксированное или нет, тоже относится к допущению.
Первое допущение которое я предположил что $x_i \in \mathbb{R}$. А вот кол-во кластеров при такой постановке задачи, должно прийти к "лучшему".

Появятся вырожденные кластеры, т.е. первичное кол-во кластеров может быть сформулировано как равное кол-ву элементов выборки.

[_rip_]

Гугл знает все :) главное знать как спрашивать.

натолкнулся на материалы
http://logic.pdmi.ras.ru/~sergey/teaching/ml/11-cluster.pdf и
http://logic.pdmi.ras.ru/~sergey/teaching/ml/12-cluster2.pdf

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

[DoctorZLO]

_rip_ в сообщении #381191 писал(а):

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

Не нашел в ваших ссылках оценку сравнения разбиения на кластеры. Указанный источник показался мне малоинформативным.

[_rip_]

DoctorZLO в сообщении #382741 писал(а):

Не нашел в ваших ссылках оценку сравнения разбиения на кластеры. Указанный источник показался мне малоинформативным.

Согласен, источники действительно малоинформативны.
Может вы что-то можете подсказать по данной тематике? Буду очень признателен.