0
$\begingroup$

I have a question in respect to tree representation of a non-Boolean function. Is there any problem in representing a function from space

Boolean->Limited Integer or
Limited Integer->Limited integer by a (decision) tree?

I don’t see any problem, but don’t find any remark about that on the net.

Thanks for your contributions

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Your question is somewhat unclear, but it sounds like you may be interested in CART: Classification and Regression Trees. Since Cosma Shalizi's lecture notes have a wealth of information, which I won't bother to reproduce here.

The basic idea, however, is that you can put whatever you want on the leaves. They can be binary decisions (i.e., in-class vs. out-of-class), a real value (e.g., 19.73). In theory, you could even let the decision tree choose between multiple regression models.

Similarly, the internal nodes can be pretty flexible. Traditionally, they're binary decisions, but they can be binary decisions on integers or real values (e.g., if $X>22.8$, do one thing, otherwise, do another). There are some extensions that do multiple splits at each node--I think one is called CHAID. You may also want to check out a related technique called MARS, which reportedly works well for all-numeric data. I haven't played with it much, but there are open source packages for python, matlab, and R.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your response Matt and with the link you provided.I'm gonna read it. $\endgroup$
    – Michelle
    Dec 3, 2012 at 18:39
  • $\begingroup$ I'm gonna read it. It seems to me that when we have a limited integer->limited integer space ,the cut point value for a decision on integers(3 in e.g. X>3) comes from the algorithm behind that decision tree(such as ID3 algo. which uses Fayyad irani Multi interval discretization in Weka implementation) and this number (3) is not necessarily in my feature values.In reverse if i depict a tree manually for representing my experience table(training dataset), i won't use this boundary split value,but i will use a multiple split at the node with equality comparison. $\endgroup$
    – Michelle
    Dec 3, 2012 at 19:01
  • $\begingroup$ My problem stems from that inequality sign ( lesser< or greater than>) that we use at a node for decision making. Does it come from that specific algorithm behind that tree? or we use it to convert a n-ary tree to a binary tree or it's a way to have a REDUCED Decision Diagram? I'm confused $\endgroup$
    – Michelle
    Dec 3, 2012 at 19:06
  • $\begingroup$ You've got right idea about how the tree is constructed. The reason that the break point might not be in the training set is because it's trying to find an optimal separation. For example, if your data looks like C1 = [ 1,2,3] and C2=[4,5,6], the biggest "margin" decision threshold is X>3.5. The choice of greater-than or less-than is probably implementation dependent, as you could just as easily say X<=3.5 and swap that node's children around. If you only want equality, you could obviously just treat them as strings or binary features, but I can't imagine that would help performance at all! $\endgroup$
    – Matt Krause
    Dec 6, 2012 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.