Implementing decision trees using Python


#1

I'm attempting to solve the classic knapsack problem using decision trees and getting stuck with an error. I tried playing around with the print statements and got information that one of the helper function is not working correctly but I'm unable to rectify it. Can someone help?

Posting my original code:

class BinaryTree(object):
    def __init__(self,value):
        self.value = value
        self.leftBranch = None
        self.rightBranch = None
        self.parent = None

    def setLeftBranch(self,node):
        self.leftBranch = node

    def setRightBranch(self,node):
        self.rightBranch = node

    def setParent(self,parent):
        self.parent = parent

    def getValue(self):
        return self.value

    def getLeftBranch(self):
        return self.leftBranch

    def getRightBranch(self):
        return self.rightBranch

    def getParent(self):
        return self.parent

    def __str__(self):
        return self.value



def buildDTree(sofar,todo):
    '''sofar: list of things that I have already decided to add when I got to 
    this node. todo: list of things I still have to consider '''
    if len(todo) == 0:
        return BinaryTree(sofar)
    else:
        withelt = buildDTree(sofar +todo[0], todo[1:])
        withoutelt = buildDTree(sofar, todo[1:])
        here = BinaryTree(sofar)
        here.setLeftBranch(withelt)
        here.setRightBranch(withoutelt)
        return here

def DFSDTree(root,valueFcn, constraintFcn):
    stack = [root]
    visited = 0
    best = None
    while len(stack) > 0:
        visited += 1
        print stack[0].getValue()
        if constraintFcn(stack[0].getValue()):
            if best == None:
                best = stack[0]
            elif valueFcn(stack[0].getValue()) > valueFcn(best.getValue()):
                best = stack[0]
            temp = stack.pop(0)
            if temp.getRightBranch():
                stack.insert(0,temp.getRightBranch())
                print stack[0].getValue()
            if temp.getLeftBranch():
                stack.insert(0,temp.getLeftBranch())
                print stack[0].getValue()
        else:
            stack.pop(0)
    print 'visited', visited
    return best

def sumValues(lst):
    vals = [e[0] for e in lst]
    return sum(vals)

def WeightsBelow10(lst):
    wts = [e[1] for e in lst]
    #print type(wts)
    #print wts
    return sum(wts) <= 10

Here's how I'm testing it. What I can clearly see is that when [6,3] is passed to the constraintFcn as an argument, the constraintFcn which is WeightsBelow10 isn't able to execute because the line wts = [e[1] for e in lst] doesn't work as there is no indexing possible with 3 which is of type int and not a list. How do we rectify this?

foo = DFSDTree(treeTest, sumValues, WeightsBelow10)
[]
[]
[6, 3]
[6, 3]
Traceback (most recent call last):

  File "<ipython-input-33-f01be6de33be>", line 1, in <module>
    foo = DFSDTree(treeTest, sumValues, WeightsBelow10)

  File "C:/Users/pvatsa/.spyder2/6.00.1x Files/knapsack_problem.py", line 61, in DFSDTree
    if constraintFcn(stack[0].getValue()):

  File "C:/Users/pvatsa/.spyder2/6.00.1x Files/knapsack_problem.py", line 83, in WeightsBelow10
    wts = [e[1] for e in lst]

TypeError: 'int' object has no attribute '__getitem__'

#2

I read your question as "I'm trying to do something I know is impossible, how do I fix it?" ..just reconsider what you want to do and do that instead? What's stopping you? And, if your question is only about a two line long function, what's all the rest for?


#3

That's not what the question is. It is definitely possible and I've been trying to work with this for a while now. Like I said, there is some error in the helper function which is passed as an argument here and I'm looking for some help to resolve that.
Rest = classes and functions where the objects of these classes are passed as parameters effectively to solve a problem
two-line function: is where I've located the problem in my code but I can't seem to think of a way to solve that problem.

Hope that clarifies.


#4

As you said, you can reproduce this problem with a single line. Everything else is just noise.

[e[1] for e in [6, 3]]

There is nearly no code there. Find out what it's doing and compare to what you want it to do.

You've narrowed it down. If you don't know what it does, then you know what you need to look up.


#5

Yup, but I'm unable to figure out how to look that up. I need to populate the variable with a list of [1] indexed values from the input list argument. so e[1] should give me 3 but the problem is e is an integer and not a list in itself. So indexing won't work.
Now, how do I do what is to be done to get e as a list or basically input to the function as a list of lists in the context of the larger optimization that I'm trying to do.


#6

Why would e ever be a list? And which list would it be?

Seems like you're using list comprehension without knowing what it does at all, and that you just need to consider what operations you need to apply in that function because you're being very vague.

You ask about one line that is independent of the other 152 lines you posted. You title your topic after what your code does, but the problem you want to solve has nothing to do with that.

Just get to the point, and be specific. And if you're able to solve the knapsack problem then this seems to be the most trivial thing ever. But instead you ask "how do I rectify this" instead of explaining what you want to make happen. You're just asking others to write the solution to your undefined problem.

Think before you ask. Think about how you ask.


#7

Ah, here is where the "noise" part will come to your aid if you see. So the idea is that e is the element of a list that will keep on growing as I continue to traverse down the tree. e will be a list of two values: the value and the weight (in knapsack context). I've to extract the latter part, that is the weight component and evaluate for an expression and if true well do something about. If e is not a list, I won't get the weight of the existing collection of items in the bag and will never be able to perform the evaluation on the next step.

That's what I'm not able to comprehend as to how to do that.

BTW, I'm not asking anyone to solve the problem for me. I've explained what I've done so far and where I'm exactly getting stuck. I've tried to tell the context so that if someone wants then can understand the backdrop of what I'm trying to do.

If you get off your high horse and try to see where I'm coming from instead of making snap opinions, it will do all a world of good.

As an "esteemed" moderator, feel free to bring down this topic if it's that useless.


#8

So now the problem is that another argument should have been given to the function? The original question seems to be specifically about the helper function, but now you seem to be saying it's not about that at all, but the code that's calling it.


#9

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.