Python: Mapping data up a hierarchy

user_16377721 0
Viewed 59

Suppose I have a dataframe that maps a child-level address to a more macro level address:

Child Child's Level Parent Parent's Level
Pivet Drive Street Little Whinging Town
Little Whinging Town England Country
England Country Europe Continent
State Street Street New York City
New York City USA Country
USA Country North America Continent

I have a second dataframe that list down each person's address, but that address may be stated at different hierarchical level

Name Address Continent?
Adam Pivet Drive
Mary New York
Dave State Street

How can I fill up the continent column in the 2nd dataframe using python?

A naive way is to either turn the 1st dataframe into a dictionary and repeatedly map upwards, or to just repeatedly merge the two dataframes. However, this does not scale up well once I've millions of rows for both dataframes, especially since every record does not start from the same level in the hierarchy.

I've previously filled up the continent column using a graph database (Neo4j), but I can't seem to google any hint on how to do this using python instead.

pandas python
1 Answers

Graph DB is born to handle case like this, if you want to handle it under relational-db/dataframe(they are the same), you can't avoid the query with many outer-joins. The concept hidden here is how to store and retrieve a tree-like data structure in relational db. You can treat dataframe like a table in db.

Here I use the Union-Find algorithm to handle this, notice that I didn't use the other level info except for Continet, which may be a buggy if Two Continets contain places of the same name under different levels, or under the same level. The following codes are just some demo thoughts, but it works for the demo data you provided, may not work well for your entire dataset:

import pandas as pd
from collections import defaultdict

df = pd.DataFrame({'Child': ['Pivet Drive', 'Little Whinging', 'England', 'State Street', 'New York', 'USA'],
                   "ChildLevel": ['Street', 'Town', 'Country', 'Street', 'City', 'Country'],
                   "Parent": ['Little Whinging', 'England', 'Europe', 'New York', 'USA', 'North America'],
                   "ParentLevel": ['Town', 'Country', 'Continent', 'City', 'Country', 'Continent']})

df_to_fill = pd.DataFrame({
    'Name': ['Adam', 'Mary', 'Dave'],
    'Address': ['Pivet Drive', 'New York', 'State Street'],
})

child_parent_value_pairs = df[["Child", "Parent"]].values.tolist()

tree = lambda: defaultdict(tree)
G = tree()
for child, parent in child_parent_value_pairs:
    G[child][parent] = 1
    G[parent][child] = 1

E = [(G[u][v], u, v) for u in G for v in G[u]]
T = set()
C = {u: u for u in G}  # C stands for components
R = {u: 0 for u in G}


def find(C, u):
    if C[u] != u:
        C[u] = find(C, C[u])  # Path compression
    return C[u]


def union(C, R, u, v):
    u = find(C, u)
    v = find(C, v)
    if R[u] > R[v]:
        C[v] = u
    else:
        C[u] = v

    if R[u] == R[v]:
        R[v] += 1


for __, u, v in sorted(E):
    if find(C, u) != find(C, v):
        T.add((u, v))
        union(C, R, u, v)

all_continents = set(df[df['ParentLevel'] == 'Continent']['Parent'].tolist())
continent_lookup = {find(C, continent): continent for continent in all_continents}

df_to_fill['Continent'] = df_to_fill['Address'].apply(lambda x: continent_lookup.get(find(C, x), None))

print(df_to_fill)

Output:

   Name       Address      Continent
0  Adam   Pivet Drive         Europe
1  Mary      New York  North America
2  Dave  State Street  North America
user_58400620
Related