Function to construct binary decision tree

Question

Suppose I have the following tree structure:

type Tree =
  | Branch of (string*string) * (Tree*Tree)
  | Leaf of float

For example, it could look something like this:

Branch (("X1",">4.5"), (Branch (("X2",">4.5"), (Leaf 3.4, Leaf 5.5)), Branch (("X3",">4.5"), (Leaf 6.5, Leaf 4.5))))

What would be the essential parts of a function to create a tree like this (from data, randomly, or whatever)? I know my question is similar to how to make a tree from a given data with F#, but I'm having the hardest time translating to my tree.

Edit: I'm trying to build a decision tree, and I started with the tree here which looks like this:

type DecisionTreeNode = 
  // Attribute name and value / child node list 
  | DecisionNode of string * (string * DecisionTreeNode) seq 
  // Decision and corresponding evidence 
  | Leaf of bool * Record seq

However, mine is a regression tree, so it should have leafs of float, and I only want binary splits, so I thought I could use tuple instead of seq for the nodes. After looking at that tree again, I'm wondering if mine should look like this:

type Tree = 
  | Branch of string*((string*Tree)*(string*Tree))
  | Leaf of float

What specific part are you stuck on? SO is not here for write all my code questions — John Palmer, Jan 13 '14 at 02:58

score 2 · Answer 1 · answered Jan 13 '14 at 14:49

I have not worked with decision trees, but after reading your requirements

binary splits

leafs of float

looking at the example in the link and looking at some examples of images using Google search,

I would use:

type Tree =
| Branch of string*(string*Tree)*(string*Tree)
| Leaf of float

and match a node using

match node with
| Branch (decision, (v1,l), (v2,r)) -> // Do something
| Leaf value -> // Do something

And you would compare against the values v1 or v2 and choose the appropriate branch, l or r.

Note: I removed the () around ((string*Tree)*(string*Tree)) so that you could use

Branch (decision, (v1,l), (v2,r)) instead of
Branch (decision, ((v1,l), (v2,r)))

Note also that I have not tested or compiled this code, but it should get you started.

This got me going in the right direction, but what I was really after is given in my answer. Is this the correct way to handle this? I want points to be given fairly. — rytido, Jan 14 '14 at 17:56

rytido · Answer 2 · 2014-01-14T17:57:11.283

I figured out what I was originally after. A function like this (with "while i>0" logic replaced with whatever you create the tree from) which is based on the tree structure given in the answer from @GuyCoder:

type Tree =
| Branch of string*(string*Tree)*(string*Tree)
| Leaf of float

let rec buildTree i =
    if i<1 then Leaf 1.
    else Branch ("Branch", ("Condition1", (buildTree (i-1))), ("Condition1", (buildTree (i-1))))

Function to construct binary decision tree

2 Answers2