Как найти предка и родительские узлы из дендрограммы в MATLAB

У меня есть вывод Z из алгоритма связи в MATLAB.

Структура вывода Z приведена по этой ссылке https://uk.mathworks.com/help/stats/linkage.html (прокрутите вниз до вывода)

Я пытаюсь найти генеалогию внутренних узлов и листьев дендрограммы. Генеалогия определяется как упорядоченный набор внутренних узлов, соединяющих лист i (внутренний узел α_h) с корнем α_1. Я также хочу иметь возможность найти родительский узел — это узел w из v, в котором w непосредственно предшествует v на пути от корня к v. Кто-нибудь захочет объяснить, как я могу сделать это с помощью MATLAB?

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

Пример

Генеалогия листа 3 — это G(3)={α_7, α_2, α_1}, а генеалогия внутреннего узла α_7 — это G(α_7)={α_7, α_2, α_1}. Пример для родителей: родительским узлом α_7 является α_2, который я обозначаю как g(α_2)=α_7. Я знаю, что индексация дерева с учетом вывода Z из иерархической кластеризации отличается от изображения, поэтому код, который согласуется с тем, как дендрограмма индексируется Z, абсолютно хорош. Я просто забочусь о том, чтобы вывод был правильным для дендрограммы.

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


matlab dendrogram
person Ansh    schedule 06.03.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Небольшой пример проясняет ситуацию:

X = [1,2,4,5,8]';    
D = pdist(X);
L = linkage(D, 'ward');
dendrogram(L, 'labels', cellfun(@num2str, num2cell(X), 'uniform', false));

Если вы добавите четвертый столбец к L с помощью

L(:, end+1) = (size(L, 1) + (1 : size(L, 1)));

тогда каждая строка L имеет записи ["номер узла", "номер узла", "слияние на уровне", "номер родителя"].

Таким образом, корневой узел всегда L (конец, конец), выходной узел имеет номер до размера (X, 1), внутренние узлы имеют номера больше, чем размер (X, 1).

В вашем примере L будет выглядеть примерно так:

L = [...
    9, 10, 1, 10; % 10 = alpha_9
    5,  6, 2, 11; % 11 = alpha_8
    3,  4, 3, 12; % 12 = alpha_7
    1,  2, 4, 13; % 13 = alpha_6
    7, 12, 5, 14; % 14 = alpha_5
    8, 15, 6, 15; % 15 = alpha_4
   16, 11, 7, 16; % 16 = alpha_3
   14, 13, 8, 17; % 17 = alpha_2
   18, 17, 9, 18; % 18 = alpha_1
   ];
dendrogram(L);

Обратите внимание, что метки уже верны по построению.

person JoergVanAken    schedule 07.03.2017
comment
Приносим извинения за поздний ответ. А, теперь я вижу. Итак, с генеалогией мне просто нужно теперь выполнить поиск в последнем столбце расширенной версии L, поскольку родитель предыдущего родителя будет в генеалогии соответствующего листового узла? - person Ansh; 14.03.2017
comment
Да все верно. Не могли бы вы принять мой ответ, если он отвечает на ваш вопрос? Спасибо :-) - person JoergVanAken; 15.03.2017
comment
Да, я приму это сейчас. Спасибо вам за помощь! - person Ansh; 16.03.2017