Как визуализировать (дендрограмму) словарь иерархических элементов?

Это мой первый опыт визуализации иерархических данных в формате словаря с помощью Python. Последняя часть данных выглядит так:

d = {^2820: [^391, ^1024], ^2821: [^759, 'w', ^118, ^51], ^2822: [^291, 'o'], ^2823: [^25, ^64], ^2824: [^177, ^2459], ^2825: [^338, ^1946], ^2826: [^186, ^1511], ^2827: [^162, 'i']}

Итак, у меня есть индексы в списках, ссылающиеся на ключи (индекс) словаря. Я полагаю, что это можно использовать в качестве базовой структуры для визуализации, поправьте меня, если я ошибаюсь. Символы в данных являются «конечными узлами/листами», которые не относятся к какому-либо индексу.

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

import networkx as nx
import matplotlib.pyplot as plt

d = {^2820: [^391, ^1024], ^2821: [^759, 'w', ^118, ^51], ^2822: [^291, 'o'], ^2823: [^25, ^64], ^2824: [^177, ^2459], ^2825: [^338, ^1946], ^2826: [^186, ^1511], ^2827: [^162, 'i']}

G = nx.Graph(d)
nx.draw(G)
plt.show()

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

Дендрограмма

ОБНОВИТЬ

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

# original sequence: a,b,c,d,b,c,a,b,c,d,b,c
d = {^1: ['b', 'c'], ^2: ['a', ^1, 'd', ^1], 'S': [^2, ^2]}
G = nx.Graph(d)
nx.draw_spring(G, node_size=300, with_labels=True)

NetworkX draw_spring nx.Graph

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

NetworkX draw_spring nx.DiGraph

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

d = {'a': [], 'b': [], 'c': [], 'd': [], ^1: ['b', 'c'], ^2: ['a', ^1, 'd', ^1], 'S': [^2, ^2]}

python dictionary graph networkx dendrogram
person MarkokraM    schedule 18.02.2016    source источник
comment
Предоставьте образец желаемого результата.   -  person albert    schedule 18.02.2016
comment
Предоставленный образец вывода, к сожалению, я не могу быть более конкретным на данный момент. Придет с лучшим после поиска большего.   -  person MarkokraM    schedule 18.02.2016
comment
Это может быть отправной точкой: nxn.se/post /90198924975/   -  person albert    schedule 18.02.2016
comment
@albert ссылка не работает, не могли бы вы обновить ссылку?   -  person Ehsan Sadr    schedule 25.09.2017
comment
@EhsanSadr: обновленную ссылку см. Снимок, сделанный WebArchive   -  person albert    schedule 26.09.2017
comment
Мне очень жаль, но кто-нибудь может объяснить, что означают ^1, ^2 и т. д.? Это недопустимый синтаксис Python, но все здесь, похоже, воспринимают это спокойно... почему?   -  person David M. Perlman    schedule 07.04.2021

Ответы (1)


arrow_upward
4
arrow_downward

Одна из идей состоит в том, чтобы использовать функция dendrogram SciPy для построения дендрограммы. Для этого вам просто нужно создать матрицу связей Z, которая описана в документации функция SciPy linkage. Каждая строка [x, y, w, z] матрицы связей Z описывает вес w, при котором x и y сливаются в корневое поддерево с z листьями.

Чтобы продемонстрировать, я создал простой пример с использованием небольшой дендрограммы с тремя листьями, как показано ниже: < img src="https://i.stack.imgur.com/erSTg.png" alt="пример дендрограммы">

Я создал эту визуализацию с помощью следующего кода:

# Load required modules
import networkx as nx
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram

# Construct the graph/hierarchy
d           = { 0: [1, 'd'], 1: ['a', 'b', 'c'], 'a': [], 'b': [], 'c': [], 'd': []}
G           = nx.DiGraph(d)
nodes       = G.nodes()
leaves      = set( n for n in nodes if G.out_degree(n) == 0 )
inner_nodes = [ n for n in nodes if G.out_degree(n) > 0 ]

# Compute the size of each subtree
subtree = dict( (n, [n]) for n in leaves )
for u in inner_nodes:
    children = set()
    node_list = list(d[u])
    while len(node_list) > 0:
        v = node_list.pop(0)
        children.add( v )
        node_list += d[v]

    subtree[u] = sorted(children & leaves)

inner_nodes.sort(key=lambda n: len(subtree[n])) # <-- order inner nodes ascending by subtree size, root is last

# Construct the linkage matrix
leaves = sorted(leaves)
index  = dict( (tuple([n]), i) for i, n in enumerate(leaves) )
Z = []
k = len(leaves)
for i, n in enumerate(inner_nodes):
    children = d[n]
    x = children[0]
    for y in children[1:]:
        z = tuple(subtree[x] + subtree[y])
        i, j = index[tuple(subtree[x])], index[tuple(subtree[y])]
        Z.append([i, j, float(len(subtree[n])), len(z)]) # <-- float is required by the dendrogram function
        index[z] = k
        subtree[z] = list(z)
        x = z
        k += 1

# Visualize
dendrogram(Z, labels=leaves)
plt.show()

Следует отметить несколько ключевых моментов:

  1. Дайте структуру данных d, я использую ориентированный граф NetworkX (DiGraph). Направленность важна, поэтому мы можем определить, какие узлы являются leaves (нет дочерних элементов -> исходящая степень нуля) и inner_nodes (два или более дочерних узла -> ненулевая исходящая степень).
  2. Обычно каждому ребру в вашей дендрограмме присваивается некоторый вес, но в вашем примере весов не было. Вместо этого я использовал количество листьев в поддереве с корнем в каждом внутреннем узле n в качестве веса для n.
  3. Если внутренний узел имеет более двух дочерних узлов, вам необходимо добавить «фиктивные» внутренние узлы, поскольку каждая строка матрицы связей объединяет два узла вместе. Вот почему я пишу for y in children[1:]: и т. д.

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

person mdml    schedule 19.02.2016
comment
Это точно на правильном пути! Я также искал решение, как рассчитать веса, потому что их действительно нет в моих данных. Ваши простые образцы данных работают нормально, но в моей структуре данных все еще есть некоторые части, которые еще не учитываются. Вы видите, почему этот ввод дает ту же ошибку значения кластера: d {'a': [], ^1: ['b', 'c'], ^2: ['a', ^1, 'd', ^1], 'b': [], 'c': [], 'd': []} Мой ввод также может быть: d {'a': [], ^1: ['b', ' c'], ^2: ['a', ^1, 'd', ^1], 'b': [], 'c': [], 'd': [], 'S': [^ 2, ^2]}, что даст ту же ошибку. Это потому, что повторяются ^1 и ^2? - person MarkokraM; 20.02.2016
comment
@MarkokraM Задайте другой вопрос. Вы спросили о дендограммах, поэтому mdml ответил о дендограммах. - person erip; 20.02.2016
comment
@erip На самом деле я спрашивал, как лучше всего визуализировать мои данные. Дендрограмма была хорошим кандидатом, но похоже, что она не подходит, по крайней мере, не с функцией, предоставляемой scipy.cluster.hierarchy. Структура данных связи имеет ограничения, указанные в моем первом комментарии. mdml, подтвердите, пожалуйста, так ли это? Я готов принять ответ, если в вашем ответе указано ограничение структуры данных, соответствующее моему образцу в части UPDATE. - person MarkokraM; 22.02.2016
comment
@MarkokraM: Да, я думаю, что повторяющиеся ^1 и ^2 вызывают ошибку. Структура данных d представляет собой карту от родителя к дочерним элементам, поэтому я не уверен, как узел может быть указан дважды. Вы можете уточнить? - person mdml; 23.02.2016