# Can I represent a non-boolean function with a TREE?

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.

-

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.

-
Thanks for your response Matt and with the link you provided.I'm gonna read it. –  Michelle Dec 3 '12 at 18:39
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. –  Michelle Dec 3 '12 at 19:01
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 –  Michelle Dec 3 '12 at 19:06
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! –  Matt Krause Dec 6 '12 at 18:57