爲每個終端節點提取路徑

Question

我有一個python嵌套的字典結構，如下所示。 這是一個小例子，但我有更大的例子，可以有不同級別的嵌套。

由此，我需要提取的列表，包括：

針對每個終端「葉」

1. 一個記錄節點
2. 的字符串，列表或對象，表示導致到邏輯路徑該節點
   • （例如 'nodeid_3：X < 0.500007和X < 0.279907'）

我花這個週末試圖讓一些工作的較大部分和我意識到那些我怎麼不好用遞歸。

# Extract json string 
json_string = booster.get_dump(with_stats=True, dump_format='json')[0] 

# Convert to python dictionary 
json.loads(json_string) 

{u'children': [{u'children': [ 
    {u'cover': 2291, u'leaf': -0.0611795, u'nodeid': 3}, 
    {u'cover': 1779, u'leaf': -0.00965727, u'nodeid': 4}], 
    u'cover': 4070, 
    u'depth': 1, 
    u'gain': 265.811, 
    u'missing': 3, 
    u'no': 4, 
    u'nodeid': 1, 
    u'split': u'X', 
    u'split_condition': 0.279907, 
    u'yes': 3}, 
    {u'cover': 3930, u'leaf': -0.0611946, u'nodeid': 2}], 
u'cover': 8000, 
u'depth': 0, 
u'gain': 101.245, 
u'missing': 1, 
u'no': 2, 
u'nodeid': 0, 
u'split': u'X', 
u'split_condition': 0.500007, 
u'yes': 1} 

Answer 1

你的數據結構是遞歸的。如果一個節點有一個孩子密鑰，那麼我們可以認爲它不是終端。

要分析您的數據，您需要一個跟蹤祖先的遞歸函數（路徑）。

我會實現這個類似：

def find_path(obj, path=None): 
    path = path or [] 
    if 'children' in obj: 
     child_obj = {k: v for k, v in obj.items() 
        if k in ['nodeid', 'split_condition']} 
     child_path = path + [child_obj] 
     children = obj['children'] 
     for child in children: 
      find_path(child, child_path) 
    else: 
     pprint.pprint((obj, path)) 

如果您撥打：

find_path(data) 

你得到3個結果：

({'cover': 2291, 'leaf': -0.0611795, 'nodeid': 3}, 
[{'nodeid': 0, 'split_condition': 0.500007}, 
    {'nodeid': 1, 'split_condition': 0.279907}]) 
({'cover': 1779, 'leaf': -0.00965727, 'nodeid': 4}, 
[{'nodeid': 0, 'split_condition': 0.500007}, 
    {'nodeid': 1, 'split_condition': 0.279907}]) 
({'cover': 3930, 'leaf': -0.0611946, 'nodeid': 2}, 
[{'nodeid': 0, 'split_condition': 0.500007}]) 

當然，你也可以更換調用pprint.pprint()由yield將此功能變成發電機：

def iter_path(obj, path=None): 
    path = path or [] 
    if 'children' in obj: 
     child_obj = {k: v for k, v in obj.items() 
        if k in ['nodeid', 'split_condition']} 
     child_path = path + [child_obj] 
     children = obj['children'] 
     for child in children: 
      # for o, p in iteration_path(child, child_path): 
      #  yield o, p 
      yield from iter_path(child, child_path) 
    else: 
     yield obj, path 

請注意使用yield from進行遞歸調用。您可以使用此生成象下面這樣：

for obj, path in iter_path(data): 
    pprint.pprint((obj, path)) 

你也可以改變的方式child_obj目標是建立以符合您的需求。

要保持對象的順序：反轉if條件：if 'children' not in obj: …。