J'ai un grand ensemble de données qui représente une arborescence hiérarchique d'entreprises. Pour donner un exemple, je pourrais avoir quelque chose comme le suivant:
Child Parent 273500 273500 # The first row is the parent row 20574624 273500 # I want all children that belong to this parent node 1879450 20574624 # 18441258 20574624 19770000 20574624 19931554 20574624 20631784 20574624 20637582 20574624 20840426 20574624 20844632 20574624 20934910 20574624 20965442 20574624 21193122 20574624 2202652 1879450 # Now, I want all the children that belong to 1879450 18382902 1879450 # and so on 19780666 1879450 19933526 1879450 18352628 19770000 18000796 18352628 19681810 18352628 1359996 20574624 21194666 21193122
Comme vous pouvez le voir, la première ligne est le nœud parent.
Ce que je veux faire, c'est trier les données de telle manière qu'elles représentent en fait une hiérarchie où vous commencez par le haut et allez vers le bas de la hiérarchie. La raison pour laquelle je veux faire cela est que je veux calculer la hauteur de l'arbre. Pour ce faire, je dois d'abord construire l'arbre. Je sais déjà comment construire l'arbre en utilisant le package treelib . Mon problème maintenant est que si j'ai un grand ensemble de données composé de milliers de lignes, comment puis-je classer mes données de manière à pouvoir créer un arbre.
Ce que j'ai déjà essayé, c'est de trier la colonne Parent par les valeurs de la colonne Child en utilisant les .sort_values dans pandas. Ceci, cependant, n'a pas fonctionné comme je le souhaitais. J'ai également essayé de le faire avec le groupe par fonction et de donner en quelque sorte aux lignes un certain rang en fonction de cette question: pandas trie une colonne par valeurs dans une autre colonne .
Cela n'a pas fonctionné pour le grand ensemble de données.
Voici le résultat que je souhaite obtenir.
Child Parent 273500 273500 20574624 273500 2202652 1879450 19933526 1879450 18000796 18352628 18352628 19770000 1359996 20574624 1879450 20574624 18441258 20574624 20637582 20574624 20840426 20574624 20844632 20574624 20934910 20574624 20965442 20574624 21193122 20574624 21194666 21193122 19770000 20574624 19681810 18352628 19931554 20574624 18382902 1879450 19780666 1879450 20631784 20574624
Pour un si petit ensemble de données, on pourrait facilement le commander à la main. Mais pour les grands ensembles de données composés de milliers de lignes, cela peut être un peu fastidieux.
3 Réponses :
Je vais faire cela en Python vanilla plutôt qu'en utilisant des pandas. Fondamentalement, ce que vous voulez faire est de construire un ensemble d'arbres, puis de les parcourir à partir des nœuds racines de ces arbres.
Disons que vous avez déjà analysé les données et que vous pouvez commencer avec une liste processus code > de la structure List [Tuple [int, int]] .
[
(273500, 273500),
(20574624, 273500),
(1359996, 20574624),
(1879450, 20574624),
(2202652, 1879450),
(18382902, 1879450),
(19780666, 1879450),
(19933526, 1879450),
(18441258, 20574624),
(19770000, 20574624),
(18352628, 19770000),
(18000796, 18352628),
(19681810, 18352628),
(19931554, 20574624),
(20631784, 20574624),
(20637582, 20574624),
(20840426, 20574624),
(20844632, 20574624),
(20934910, 20574624),
(20965442, 20574624),
(21193122, 20574624),
(21194666, 21193122),
]
Nous pouvons représenter tous les nœuds de notre arbre comme Dict [int, List [int]] des relations parents-enfants. La méthode suivante peut être appelée sur le cadre en appelant sort_processes (df.values.tolist ()) . Le résultat peut être reconverti en pandas en appelant pandas.DataFrame (result, columns = ['Child', 'Parent']) :
from collections import defaultdict
from typing import Dict, List, Iterable, Tuple
def sort_processes(processes: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
# initialize the nodes
nodes: Dict[int, List[int]] = defaultdict(list)
for child, parent in processes:
nodes[parent].append(child)
# walk and yield pairs
def walk_tree(parent: int) -> Iterable[Tuple[int, int]]:
for child in sorted(nodes[parent]):
yield (child, parent)
# avoid infinite loops
if parent != child:
yield from walk_tree(child)
# start at top level parents
parents = [parent for child, parent in processes if parent == child]
return list(
pair for parent in sorted(parents) for pair in walk_tree(parent)
)
Appel de sort_processes (processus) Renvoie:
processes = [
(273500, 273500),
(20574624, 273500),
(2202652, 1879450),
(19933526, 1879450),
(18000796, 18352628),
(18352628, 19770000),
(1359996, 20574624),
(1879450, 20574624),
(18441258, 20574624),
(20637582, 20574624),
(20840426, 20574624),
(20844632, 20574624),
(20934910, 20574624),
(20965442, 20574624),
(21193122, 20574624),
(21194666, 21193122),
(19770000, 20574624),
(19681810, 18352628),
(19931554, 20574624),
(18382902, 1879450),
(19780666, 1879450),
(20631784, 20574624),
]
Je ne connais pas très bien le python vanille. Juste pour me lancer, dans mon cas particulier, devrais-je commencer par processes = List [Tuple [df. ['Child'], df. ['Parent']] Aussi que fait cette ligne: nodes: Dict [int, List [int]] = defaultdict (liste)
Chaque tuple est une ligne dans le dataframe. Devrait juste être df.values.tolist ()
@Eren defaultdict est un dictionnaire où si vous interrogez une clé qui n'existe pas encore, il créera une nouvelle valeur pour vous et la renverra. Dans ce cas, nous utilisons une liste vide comme valeur renvoyée. Le : Dict [int, List [int]] est un indice de type. Les conseils de type sont uniquement destinés à permettre à des outils comme mypy de vérifier votre code pour éviter les bogues. Il est recommandé de les utiliser, mais ils sont entièrement facultatifs et n'ont aucun impact fonctionnel.
Définissez la fonction suivante:
pd.DataFrame(getDescendants(hd, hd, 1), columns=['Child', 'Parent', 'Level'])
Récupérez ensuite l'identifiant du "Parent de tous les parents" (à partir de la ligne 0):
hd = df.iloc[0, 0]
et appelez la fonction ci-dessus:
def getDescendants(curr, par, level):
res = [[curr, par, level]]
children = df.query('Parent == @curr')
for n in children.Child:
if n != par:
deeper = getDescendants(n, curr, level + 1)
if len(deeper) > 0:
res.extend(deeper)
return res
Cette fonction fait encore plus. Il donne également le niveau de chaque personne dans le hiérarchie.
Si le "Parent de tous les parents" peut être situé dans n'importe quelle ligne (pas nécessairement dans le premier), une autre approche est nécessaire.
En supposant que le DataFrame source contient une arborescence de hiérarchie unique,
le nœud racine peut être lu comme suit: hd = df.query ('Parent == Child'). iloc [0,0] .
Puis générez l'arborescence hiérarchique comme ci-dessus.
S'il existe plusieurs arborescences hiérarchiques, alors:
df.query ('Parent == Child'). iloc [0] obtient une Série d'identifiants "racine". Cela fonctionne bien en effet. Le seul inconvénient pourrait être que vous devez donner la contribution du «parent de tous les parents». Et si cela n'avait pas été dans la ligne 0 p.e. Juste une petite chose. Dans l'ensemble, cela fonctionne incroyablement bien. Merci beaucoup. Appréciez-le.
Que fait l'iloc [0,0] dans "hd = df.query ('Parent == Child'). Iloc [0,0]"? Merci d'avance.
Notez que df.query ('Parent == Child') sélectionne des lignes pour chaque "racine" de la hiérarchie. Donc iloc [0,0] prend la ligne initiale (à partir de ces lignes) et de cette ligne - la colonne initiale (ID de personne).
Pour être sûr, 1. si je n'ai qu'une seule hiérarchie, alors df.query ('Parent == Child') me donne le nœud racine? 2 Si j'avais plusieurs hiérarchies, alors j'obtiendrais un tableau de tous les nœuds racine, puis l'iloc [0,0] me donnerait la première racine de ce tableau?
J'ai changé la dernière partie de ma réponse (un peu), j'espère que cela répondra à votre question.
Si j'ai bien compris que vous voulez un tri topologique , je vous suggère d'utiliser le une mise en œuvre dans networkx :
import networkx as nx import pandas as pd
Output strong >
result = df.set_index('parent').loc[order, :].dropna().reset_index().reindex(['child', 'parent'], axis=1)
Si vous voulez garder l'ordre des colonnes (['child', 'parent']) faites simplement: p >
parent child 0 273500 273500.0 1 273500 20574624.0 2 20574624 1359996.0 3 20574624 1879450.0 4 20574624 18441258.0 5 20574624 20637582.0 6 20574624 20840426.0 7 20574624 20844632.0 8 20574624 20934910.0 9 20574624 20965442.0 10 20574624 21193122.0 11 20574624 19770000.0 12 20574624 19931554.0 13 20574624 20631784.0 14 1879450 2202652.0 15 1879450 19933526.0 16 1879450 18382902.0 17 1879450 19780666.0 18 19770000 18352628.0 19 18352628 18000796.0 20 18352628 19681810.0 21 21193122 21194666.0
Assurez-vous d'importer les bibliothèques requises:
edges = df[df.child != df.parent].reset_index()
dg = nx.from_pandas_edgelist(edges, source='parent', target='child', create_using=nx.DiGraph)
order = list(nx.lexicographical_topological_sort(dg))
result = df.set_index('parent').loc[order, :].dropna().reset_index()
print(result)
J'obtiens l'erreur "Le graphe d'entrée n'est pas un type de graphe networkx". Pourriez-vous s'il vous plaît me dire quels paquets je dois importer en plus de networkx?
J'obtiens toujours l'erreur même si j'ai importé les deux packages.
J'avais besoin de mettre "create_using = nx.DiGraph ()" Les crochets après DiGraph ont fait l'affaire.
Curieux, y a-t-il une raison pour laquelle vous n'avez pas accepté cette réponse comme étant correcte? @Eren
Toutes les réponses sont correctes pour être honnête. Puis-je tous les accepter? Il n'y a aucune raison particulière de ne pas accepter celui-ci. @Erfan
df.sort_values (["Parent", "Child"])?@politicalscientist: vous êtes plus rapide que moi 4 secondes en commentaire :). J'ai supprimé le mien
Dans cet exemple spécifique, cette solution fonctionnera, mais en général, s'il existe un ensemble de données plus grand où les nombres ne sont pas dans un ordre croissant du niveau de l'arborescence au niveau de l'arborescence, cela ne fonctionnera pas. Je vais penser à un exemple plus large pour illustrer cela. Malheureusement, je ne peux pas télécharger le plus grand ensemble de données.