wwl - 2 years ago 123
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
``````

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download