2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 кластерный анализ
Сообщение16.09.2014, 17:17 


27/10/09
600
Дамы и Господа!

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

 Профиль  
                  
 
 Re: кластерный анализ
Сообщение16.09.2014, 19:33 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
В методе Варда в качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения. Где в этом расстоянии учитывается "на каком шаге какой элемент к какому кластеру был присоединен"?

 Профиль  
                  
 
 Re: кластерный анализ
Сообщение16.09.2014, 20:11 


27/10/09
600
Проблема в том, что эти расстояния я в лоб посчитать не могу, как не могу посчитать и центры кластеров, поскольку сами элементы совокупности не известны. Есть только расстояния между ними. Вот и вопрос - как, имея расстояния между всеми элементами совокупности узнать " прирост суммы квадратов расстояний объектов до центров кластеров"?

-- Вт сен 16, 2014 7:25 pm --

Чтобы было понятнее, вот пример. Есть шесть элементов, матрица их расстояний $$d=\left(
\begin{array}{cccccc}
 0 & 5 & 2 & 3 & 6 & 9 \\
 5 & 0 & 5 & 3 & 5 & 6 \\
 2 & 5 & 0 & 8 & 7 & 8 \\
 3 & 3 & 8 & 0 & 4 & 6 \\
 6 & 5 & 7 & 4 & 0 & 3 \\
 9 & 6 & 8 & 6 & 3 & 0 \\
\end{array}
\right)$$
Элементы первого кластера $A=\{1,3\}$, второго кластера $B=\{2,4,5,6\}$. Расстояние Варда в данном случае $67/6$, но как его найти?

 Профиль  
                  
 
 Re: кластерный анализ
Сообщение17.09.2014, 07:47 


27/10/09
600
В приведенном примере расстояние Варда равно
$1/6(2d[2,1]-4d[3,1]+2d[3,2]+2d[4,1]-d[4,2]+2d[4,3]+2d[5,1]-d[5,2]+2d[5,3]-d[5,4]+2d[6,1]-d[6,2]+2d[6,3]-d[6,4]-d[6,5])$
но почему именно так?

-- Ср сен 17, 2014 6:54 am --

Несложно заметить, что расстояния между элементами внутри кластеров входят в сумму с отрицательными коэффициентами, а расстояния между элементами разных кластеров - с положительными

 Профиль  
                  
 
 Re: кластерный анализ
Сообщение17.09.2014, 11:05 


27/10/09
600
Пока удалось выяснить, что расстояние Варда между двумя кластерами равно $$a\sum_{i,j\in A}d_{ij}+b\sum_{i,j\in B}d_{ij}+c\sum_{i\in A,j\in B}d_{ij}$$где $d_{ij}$ - расстояние между $i$-м и $j$-м элементами, $A$ и $B$ - списки порядковых номеров элементов, принадлежащих двум разным кластерам, $a,b,c$ - коэффициенты. При этом коэффициенты $a,b$ неположительны, а коэффициент $c$ неотрицательный, а сами коэффициенты $a,b,c$ зависят только от количества элементов в кластерах. Вот только как найти эти коэффициенты?

 Профиль  
                  
 
 Re: кластерный анализ
Сообщение17.09.2014, 13:34 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Видимо, у вас какое-то свое расстояние Варда, не совпадающее с тем, которое придумал сам Вард. В таком случае мне не удастся оказать вам помощь.

 Профиль  
                  
 
 Re: кластерный анализ
Сообщение17.09.2014, 21:04 


27/10/09
600
Brukvalub в сообщении #908756 писал(а):
Видимо, у вас какое-то свое расстояние Варда, не совпадающее с тем, которое придумал сам Вард.
Расстояние Варда у меня точно такое-же, как в программах Mathematica и Statistica. Просто если в качестве расстояний между элементами взять квадраты расстояний между ними, то действительно, расстояние Варда сведется к разнице между суммой квадратов отклонений элементов от центра объединенного кластера и суммой квадратов отклонений элементов двух объединяемых кластеров от центров этих кластеров. Это не совсем дисперсии, как Вы пытались написать ранее. Но дело не в этом. Просто метод Варда может применяться не только для квадратов расстояний, но и для любых способов расчета расстояний между элементами кластеризуемой совокупности, включая корреляционное расстояние и расстояние косинуса. Тогда первоначальный смысл дисперсионного анализа теряется, но смысл расстояния между кластерами все равно остается. Т.е. трактовка расстояния Варда как разница дисперсий не более чем частный случай метода Варда.
Brukvalub в сообщении #908756 писал(а):
В таком случае мне не удастся оказать вам помощь.
А уже и не надо - вот искомые коэффициенты$$
   \left(\frac{1}{n_A+n_B}-\frac{1}{n_A}\right)\sum_{i,j\in A}d_{ij}+\frac{2}{n_A+n_B}\sum_{i\in A,j\in B}d_{ij}+ \left(\frac{1}{n_A+n_B}-\frac{1}{n_B}\right)\sum_{i,j\in B}d_{ij}$$Если есть желание проверить, вот код для Математики:
генерируем матрицу расстояний и кластеризуем штатными средствами
Код:
Needs["HierarchicalClustering`"]
n = 9;
d = Round[Abs[1 - Correlation[RandomReal[{0, 1}, {n + 1, n}]]]*200];
cl = DirectAgglomerate[d, Linkage -> "Ward"];
DendrogramPlot[cl, LeafLabels -> (# &)]
cl[[3]]

считаем то-же расстояние по приведенной выше формуле
Код:
cs = ClusterSplit[cl, 2];
{A, B} = {ClusterFlatten[cs[[1]]], ClusterFlatten[cs[[2]]]};
na = Length[A];
nb = Length[B];
SSa = Sum[d[[i, j]], {i, A}, {j, A}];
SSb = Sum[d[[i, j]], {i, B}, {j, B}];
SSab = Sum[d[[i, j]], {i, A}, {j, B}];
(1/(na + nb) - 1/na) SSa + 2 SSab/(na + nb) + (1/(na + nb) - 1/nb) SSb


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group