wwl wwl - 28 days ago 16
Python Question

Recursive programming in decision tree

I'm programming a decision tree in python.

tree
is an object which has a true branch
tb
and false branch
fb
. Only root nodes have the attribute
results
.

results
is a dictionary containing count of each target variable (i.e. dependent variable) at the node. I'm working on a binary classification problem, so an example would be a dictionary
{0: 25, 1: 9}
.

I want to create a function
findrootnodes(tree)
which iterates through the tree, down to the root nodes. It should return the list rootnodes. Each element of the list should contain a dictionary. So an example of a decision tree with four root nodes would be
[{0: 25, 1: 9}, {0: 2, 1: 65}, {0: 2, 1: 7}, {0: 52, 1: 4}]
.

How can I do this? My current code is below, but the issue is that it always returns an empty list. If I bring rootnodes out of the function, Python complains that the local variable rootnodes is referenced before it is instantiated.

def findrootnodes(tree):
rootnodes = []
if tree.results != None:
rootnodes += tree.results
else:
findrootnodes(tree.tb)
findrootnodes(tree.fb)
return rootnodes

Answer

In your findrootnodes function, you never change the value of rootnodes for non-result nodes. That is, when you call findrootnodes, you first set:

rootnodes = []

Assuming that the initial node has no results, you then run:

    findrootnodes(tree.tb)
    findrootnodes(tree.fb)

...neither of which changes the value of rootnodes. And then you return rootnodes, which is still an empty list.

I think that what you actually want is:

def findrootnodes(tree):   
    rootnodes = []
    if tree.results != None:
        rootnodes.append(tree.results)
    else: 
        rootnodes.extend(findrootnodes(tree.tb))
        rootnodes.extend(findrootnodes(tree.fb))
    return rootnodes

Note that I've changed your += here to .append(...), because of this:

>>> x = []
>>> x += {'key': 'value'}
>>> x
['key']

Trying to add a dictionary to a list via += will treat the dictionary as an iterable, which Python will iterate over just the keys.

Comments