Обход дерева решений на основе значений; итеративно входя в под-словари?

Question

У меня есть словарь, который представляет дерево решений:

{'Outlook': {'Overcast': 'Yes', 'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny': {'Temperature': {'Cool': 'Yes', 'Hot': 'No', 'Mild': 'No'}}}}

Визуализированный, он выглядит следующим образом:

Это дерево было сделано с некоторыми данными обучения и алгоритмом ID3; Я sh могу предсказать решение для примеров из моих данных тестирования:

Outlook   Temperature Humidity Wind    Decision
Sunny     Mild        Normal   Strong  Yes
Overcast  Mild        High     Strong  Yes
Overcast  Hot         Normal   Weak    Yes
Rain      Mild        High     Strong  No

Используя первый пример, грубое представление о порядке вещей проверяется:

Current dict 'outlook'
Examine 'outlook', found 'sunny':
  'sunny' is a dict, make current dict the 'sunny' subdict
  Examine 'temperature', found 'mild':
     'mild' is not a dict, return value 'no'  

I Я не уверен, как пройти словарь, как это, однако. У меня есть код для начала:

def fun(d, t):
    """
    d -- decision tree dictionary
    t -- testing examples in form of pandas dataframe
    """
    for _, e in t.iterrows():
        predict(d, e)

def predict(d, e):
    """
    d -- decision tree dictionary
    e -- a testing example in form of pandas series
    """
    # ?

В predict(), e можно получить как словарь:

print(e.to_dict())
# {'Outlook': 'Rain', 'Temperature': 'Cool', 'Humidity': 'Normal', 'Wind': 'Weak', 'Decision': 'Yes'}
print(e['Outlook'])
# 'Rain'
print(e['Decision'])
# 'Yes'
# etc

Я просто не знаю, как пройти через диктат. Мне нужно перебрать пример тестирования в порядке появления атрибутов в дереве решений, а не в порядке, в котором они появляются в примере тестирования.

Answer 1

Вы также можете реализовать это итеративно, просто отслеживая текущий дикт:

def predict(d, e):
    """
    d -- decision tree dictionary
    e -- a testing example in form of pandas series
    """
    c = d
    for k, v in e.iteritems():
        print(f"Current dict '{k}'")
        try:
            c = c[k][v]
        except KeyError:
            # Do something sensible here
            continue
        print(f"Examine '{k}', found '{v}': ")
        if isinstance(c, dict):
            print(f"'{v}' is a dict, make current dict the '{v}' subdict")
        else:
            print(f"'{v}' is not a dict, return {c}\n")
            return c

fun(data, test)

Результат:

Current dict 'Outlook'
Examine 'Outlook', found 'Sunny': 
'Sunny' is a dict, make current dict the 'Sunny' subdict
Current dict 'Temperature'
Examine 'Temperature', found 'Mild': 
'Mild' is not a dict, return No

Current dict 'Outlook'
Examine 'Outlook', found 'Overcast': 
'Overcast' is not a dict, return Yes

Current dict 'Outlook'
Examine 'Outlook', found 'Overcast': 
'Overcast' is not a dict, return Yes

Current dict 'Outlook'
Examine 'Outlook', found 'Rain': 
'Rain' is a dict, make current dict the 'Rain' subdict
Current dict 'Temperature'
Current dict 'Humidity'
Current dict 'Wind'
Examine 'Wind', found 'Strong': 
'Strong' is not a dict, return No

Answer 2

• Вам необходимо реализовать рекурсивное решение для поиска, пока вы не достигнете узла со строковым значением (это будет ваш конечный узел с решением "Да" или "Нет").

import pandas as pd

dt = {'Outlook': {'Overcast': 'Yes', 'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny': {'Temperature': {'Cool': 'Yes', 'Hot': 'No', 'Mild': 'No'}}}}

df = pd.DataFrame(data=[['Sunny', 'Mild', 'Normal', 'Strong', 'Yes']],columns=['Outlook', 'Temperature', 'Humidity', 'Wind', 'Decision'])

def fun(d, t):
    """
    d -- decision tree dictionary
    t -- testing examples in form of pandas dataframe
    """
    res = []
    for _, e in t.iterrows():
        res.append(predict(d, e))
    return res

def predict(d, e):
    """
    d -- decision tree dictionary
    e -- a testing example in form of pandas series
    """
    current_node = list(d.keys())[0]
    current_branch = d[current_node][e[current_node]]
    # if leaf node value is string then its a decision
    if isinstance(current_branch, str):
        return current_branch
    # else use that node as new searching subtree
    else:
        return predict(current_branch, e)

print(fun(dt, df))

вывод:

['Нет']