Словарь Python — объединение конечных узлов ниже порогового значения

Ниже приведен упрощенный пример дерева решений (dict()), которое я обучал на Python:

tree= {'Age': {'> 55': 0.4, '< 18': {'Income': {'high': 0, 'low': 0.2}}, 
               '18-35': 0.25, '36-55': {'Marital_Status': {'single': {'Income': 
               {'high': 0, 'low': 0.1}}, 'married': 0.05}}}}

Числа в листовых узлах (поля) представляют вероятность появления метки класса (например, TRUE) в этом узле. Визуально дерево выглядит так:

введите здесь описание изображения

Я пытаюсь написать общий алгоритм постобрезки, который объединяет узлы со значениями меньше 0.3 в их родительские узлы. Таким образом, результирующее дерево с порогом 0.3 будет выглядеть следующим образом:

введите здесь описание изображения

Обратите внимание, что на втором рисунке узел Income в Age<18 теперь объединен с корневым узлом Age. И Age=36-55, Marital_Staus был объединен в Age, поскольку сумма всех его листовых узлов (на нескольких уровнях) меньше 0,3.

Это неполный псевдокод, который я придумал (пока):

def post_prune  (dictionary, threshold):

    for k in dictionary.keys():

        if isinstance(dictionary[k], dict): # interim node

            post_prune(dictionary[k], threshold)

        else: # leaf node

            if dictionary[k]> threshold:
                pass
            else:
                to_do = 'delete this node'

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

Спасибо.

P.S: Я не буду использовать конечный результат для классификации, так что такая обрезка (косметически) работает.


python-2.7 dictionary pruning decision-tree
person Zhubarb    schedule 10.07.2014    source источник
comment
self.post_prune(dictionary[k], threshold) Это метод класса? Затем вы должны добавить параметр self в сигнатуру метода.   -  person tobias_k    schedule 11.07.2014
comment
да, но я упростил это здесь. Я изменил его, чтобы теперь он был последовательным.   -  person Zhubarb    schedule 11.07.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете попробовать что-то вроде этого:

def simplify(tree, threshold):
    # simplify tree bottom-up
    for key, child in tree.items():
        if isinstance(child, dict):
            tree[key] = simplify(child, threshold)
    # all child-nodes are leafs and smaller than threshold -> return max
    if all(isinstance(child, str) and float(child) <= threshold 
           for child in tree.values()):
        return max(tree.values(), key=float)
    # else return tree itself
    return tree

Пример:

>>> tree= {'Age': {'> 55': '0.4', '18-35': '0', \
                   '< 18': {'Income': {'high': '0', 'low': '0.2'}}, \
                   '36-55': {'Marital_Status': {'single': {'Income': {'high': '0', 'low': '0.1'}}, \
                                                'married': '0.3'}}}}
>>> simplify(tree, 0.2)
{'Age': {'> 55': '0.4', '< 18': '0.2', '18-35': '0', 
         '36-55': {'Marital_Status': {'single': '0.1', 'married': '0.3'}}}}

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

def simplify(tree, threshold):
    # simplify tree bottom-up
    for key, child in tree.items():
        if isinstance(child, dict):
            tree[key] = simplify(child, threshold)
    # all child-nodes are leafs and sum smaller than threshold -> return sum
    if all(isinstance(child, str) for child in tree.values()) \
           and sum(map(float, tree.values())) <= threshold:
        return str(sum(map(float, tree.values())))
    # else return tree itself
    return tree
person tobias_k    schedule 11.07.2014
comment
Большое спасибо за ваш ответ, я внес небольшое изменение в условие листового узла, чтобы сделать его более общим. Я написал что-то похожее на это, но проблема в следующем: скажем, консолидация первого прохода от '< 18': {'Income': {'high': '0', 'low': '0.2'}} до '< 18': '0.2' может открыть больше возможностей для консолидации на более высоком уровне. Является ли этот код достаточно общим или он выполняет только один проход? - person Zhubarb; 11.07.2014
comment
Да, из-за восходящей рекурсии он сначала упростит нижние уровни, прежде чем пытаться упростить более высокие. Попробуйте сами: просто превысьте пороговое значение, например 0.3 или 1.0. - person tobias_k; 11.07.2014