кластерный анализ

[AndreyL]

Дамы и Господа!

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

[Brukvalub]

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

[AndreyL]

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

-- Вт сен 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$, но как его найти?

[AndreyL]

В приведенном примере расстояние Варда равно
$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 --

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

[AndreyL]

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

$$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$ зависят только от количества элементов в кластерах. Вот только как найти эти коэффициенты?

[Brukvalub]

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

[AndreyL]

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

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