2

I want to implement simple classification tree (binary classification) using Mathematica.

How can I implement a binary tree in Mathematica? Is there is a symbol for doing that?

Mr.Wizard
  • 24,179
  • 5
  • 44
  • 125
Omar Osama
  • 1,401
  • 3
  • 19
  • 29
  • 3
    Leonid is _the_ expert on data structures in Mma here. I remember he posted at least two good answers, but now I can find only one http://stackoverflow.com/questions/6097071/tree-data-structure-in-mathematica. Try searching his answers – Dr. belisarius Jul 03 '11 at 15:25

3 Answers3

2

Among the new objects in MMA 8 are TreeGraph, CompleteKaryTree, and KaryTree. The latter two objects give binary trees by default. I don't know how efficient they are for intensive computation but they do seem well-suited for displaying classifications. And there are many predicates and options for manipulating and displaying them.

Here's an example of a classification tree from [Breiman, L. Classification and Regression Trees: Chapman & Hall/CRC, 1984.]. It concerns 3 questions to determine whether a cardiac patient is likely to die within 30 days if not treated.

KaryTree[9, 2, 
   VertexLabels -> {1 -> "Blood pressure > 91 ?", 2 -> "Age > 62.5?", 
                    4 -> "Sinus tachycardia ?", 8 -> "< 30 days"}, 
   EdgeLabels -> {1 \[UndirectedEdge] 2 -> "yes", 
                  1 \[UndirectedEdge] 3 -> "no", 2 \[UndirectedEdge] 4 -> "yes", 
                  2 \[UndirectedEdge] 5 -> "no", 4 \[UndirectedEdge] 8 -> "yes", 
                  4 \[UndirectedEdge] 9 -> "no"}, ImagePadding -> 20]

Classification graph

I'd like to get rid of the two unused nodes on the right, but have not figured out a an elegant way to do it. So I think I'll post a simple question about that on SO.

DavidC
  • 3,056
  • 1
  • 20
  • 30
2

I'd say it depends on what you want to do with the data structure.

You can exploit the fact that Mathematica expressions themselves are trees.

If only the leaf nodes are relevant, then use nested lists, e.g. {{1, {2, 3}}, 4}. If the other node need to carry some data too, then you can use something like this:

tree[1][tree[2][a, b], tree[3][c, tree[4][d, e]]]

See the structure like this:

{{1, {2, 3}}, 4} // TreeForm
tree[1][tree[2][a, b], tree[3][c, tree[4][d, e]]] // TreeForm

The next question is how to implement algorithm X on such a data structure.

Szabolcs
  • 24,728
  • 9
  • 85
  • 174
  • thank you .. but you really opened a critical point .. how to implement CARTs ?!?! .. It even might don't need trees .. :D I will understand optimizing issues concerned with CARTs and I the picture will be more clear .. thank you man – Omar Osama Jul 03 '11 at 18:20
  • Can you please explain what is CART? – Szabolcs Jul 04 '11 at 07:30
  • @Szabolcs See http://en.wikipedia.org/wiki/Decision_tree_learning Also see http://us.akinator.com/ for what I suspect is an example. – Daniel Lichtblau Jul 04 '11 at 15:20
1

Personally I don't quite know, but there appears to be an article about the very subject on the Wolfram site, found here. It might not answer your question, but it will hopefully give you some insight!

Jakob Streipel
  • 244
  • 1
  • 9