edu.cmu.sphinx.alignment.tokenizer

Class DecisionTree

java.lang.Object

edu.cmu.sphinx.alignment.tokenizer.DecisionTree

public class DecisionTree
extends java.lang.Object

Implementation of a Classification and Regression Tree (CART) that is used more like a binary decision tree, with each node containing a decision or a final value. The decision nodes in the CART trees operate on an Item and have the following format:

   NODE feat operand value qfalse
 

Where feat is an string that represents a feature to pass to the findFeature method of an item.

The value represents the value to be compared against the feature obtained from the item via the feat string. The operand is the operation to do the comparison. The available operands are as follows:

• < - the feature is less than value
• =- the feature is equal to the value
• >- the feature is greater than the value
• MATCHES - the feature matches the regular expression stored in value
• IN - [[[TODO: still guessing because none of the CART's in Flite seem to use IN]]] the value is in the list defined by the feature.

[[[TODO: provide support for the IN operator.]]]

For < and >, this CART coerces the value and feature to float's. For =, this CART coerces the value and feature to string and checks for string equality. For MATCHES, this CART uses the value as a regular expression and compares the obtained feature to that.

A CART is represented by an array in this implementation. The qfalse value represents the index of the array to go to if the comparison does not match. In this implementation, qtrue index is always implied, and represents the next element in the array. The root node of the CART is the first element in the array.

The interpretations always start at the root node of the CART and continue until a final node is found. The final nodes have the following form:

   LEAF value
 

Where value represents the value of the node. Reaching a final node indicates the interpretation is over and the value of the node is the interpretation result.

Constructor Summary

Constructors

Constructor and Description
DecisionTree(java.io.BufferedReader reader, int nodes) Creates a new CART by reading from the given reader.
DecisionTree(java.net.URL url) Creates a new CART by reading from the given URL.

Method Summary

Modifier and Type	Method and Description
void	dumpDot(java.io.PrintWriter out) Dump the CART tree as a dot file.
protected java.lang.String	dumpDotNodeColor(edu.cmu.sphinx.alignment.tokenizer.DecisionTree.Node n)
protected java.lang.String	dumpDotNodeShape(edu.cmu.sphinx.alignment.tokenizer.DecisionTree.Node n)
protected edu.cmu.sphinx.alignment.tokenizer.DecisionTree.Node	getNode(java.lang.String type, java.util.StringTokenizer tokenizer, int currentNode) Gets the node based upon the type and tokenizer.
java.lang.Object	interpret(Item item) Passes the given item through this CART and returns the interpretation.
protected void	parseAndAdd(java.lang.String line) Creates a node from the given input line and add it to the CART.
protected java.lang.Object	parseValue(java.lang.String string) Coerces a string into a value.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DecisionTree

public DecisionTree(java.net.URL url)
             throws java.io.IOException

Creates a new CART by reading from the given URL.

Parameters:

url - the location of the CART data

Throws:

java.io.IOException - if errors occur while reading the data

DecisionTree

public DecisionTree(java.io.BufferedReader reader,
                    int nodes)
             throws java.io.IOException

Creates a new CART by reading from the given reader.

Parameters:

reader - the source of the CART data

nodes - the number of nodes to read for this cart

Throws:

java.io.IOException - if errors occur while reading the data

Method Detail

dumpDot

public void dumpDot(java.io.PrintWriter out)

Dump the CART tree as a dot file.

The dot tool is part of the graphviz distribution at http://www.graphviz.org/. If installed, call it as "dot -O -Tpdf *.dot" from the console to generate pdfs.

Parameters:

out - The PrintWriter to write to.

dumpDotNodeColor

protected java.lang.String dumpDotNodeColor(edu.cmu.sphinx.alignment.tokenizer.DecisionTree.Node n)

dumpDotNodeShape

protected java.lang.String dumpDotNodeShape(edu.cmu.sphinx.alignment.tokenizer.DecisionTree.Node n)

parseAndAdd

protected void parseAndAdd(java.lang.String line)

Creates a node from the given input line and add it to the CART. It expects the TOTAL line to come before any of the nodes.

Parameters:

line - a line of input to parse

getNode

protected edu.cmu.sphinx.alignment.tokenizer.DecisionTree.Node getNode(java.lang.String type,
                                                                       java.util.StringTokenizer tokenizer,
                                                                       int currentNode)

Gets the node based upon the type and tokenizer.

Parameters:

type - NODE or LEAF

tokenizer - the StringTokenizer containing the data to get

currentNode - the index of the current node we're looking at

Returns:

the node

parseValue

protected java.lang.Object parseValue(java.lang.String string)

Coerces a string into a value.

Parameters:

string - of the form "type(value)"; for example, "Float(2.3)"

Returns:

the value

interpret

public java.lang.Object interpret(Item item)

Passes the given item through this CART and returns the interpretation.

Parameters:

item - the item to analyze

Returns:

the interpretation