Package ML :: Package DecTree :: Module ID3

Module ID3

ID3 Decision Trees

contains an implementation of the ID3 decision tree algorithm
as described in Tom Mitchell's book "Machine Learning"

It relies upon the _Tree.TreeNode_ data structure (or something
  with the same API) defined locally to represent the trees

Functions

[hide private]

CalcTotalEntropy(examples, nPossibleVals)
Calculates the total entropy of the data set (w.r.t.

source code

GenVarTable(examples, nPossibleVals, vars)
Generates a list of variable tables for the examples passed in.

source code

ID3(examples, target, attrs, nPossibleVals, depth=0, maxDepth=-1, **kwargs)
Implements the ID3 algorithm for constructing decision trees.

source code

ID3Boot(examples, attrs, nPossibleVals, initialVar=None, depth=0, maxDepth=-1, **kwargs)
Bootstrapping code for the ID3 algorithm see ID3 for descriptions of the arguments If _initialVar_ is not set, the algorithm will automatically choose the first variable in the tree (the standard greedy approach).

source code

TestMultiTree()
Testing code for generating trees with more than 2 possible results...

source code

TestTree()
Testing code for trees with a single possible result...

source code

TestNamedTree()
testing code for named trees...

source code

Variables

[hide private]

Complex0 = 'F'

Complex16 = 'F'

Complex32 = 'F'

Complex64 = 'D'

Complex8 = 'F'

Float0 = 'f'

Float16 = 'f'

Float32 = 'f'

Float64 = 'd'

Float8 = 'f'

Int0 = '1'

Int16 = 's'

Int32 = 'i'

Int8 = '1'

absolute = <ufunc 'absolute'>

add = <ufunc 'add'>

arccos = <ufunc 'arccos'>

arccosh = <ufunc 'arccosh'>

arcsin = <ufunc 'arcsin'>

arcsinh = <ufunc 'arcsinh'>

arctan = <ufunc 'arctan'>

arctan2 = <ufunc 'arctan2'>

arctanh = <ufunc 'arctanh'>

bitwise_and = <ufunc 'bitwise_and'>

bitwise_or = <ufunc 'bitwise_or'>

bitwise_xor = <ufunc 'bitwise_xor'>

ceil = <ufunc 'ceil'>

conjugate = <ufunc 'conjugate'>

cos = <ufunc 'cos'>

cosh = <ufunc 'cosh'>

divide = <ufunc 'divide'>

divide_safe = <ufunc 'divide_safe'>

e = 2.71828182846

equal = <ufunc 'equal'>

exp = <ufunc 'exp'>

fabs = <ufunc 'fabs'>

floor = <ufunc 'floor'>

floor_divide = <ufunc 'floor_divide'>

fmod = <ufunc 'fmod'>

greater = <ufunc 'greater'>

greater_equal = <ufunc 'greater_equal'>

hypot = <ufunc 'hypot'>

invert = <ufunc 'invert'>

left_shift = <ufunc 'left_shift'>

less = <ufunc 'less'>

less_equal = <ufunc 'less_equal'>

log = <ufunc 'log'>

log10 = <ufunc 'log10'>

logical_and = <ufunc 'logical_and'>

logical_not = <ufunc 'logical_not'>

logical_or = <ufunc 'logical_or'>

logical_xor = <ufunc 'logical_xor'>

maximum = <ufunc 'maximum'>

minimum = <ufunc 'minimum'>

multiply = <ufunc 'multiply'>

negative = <ufunc 'negative'>

not_equal = <ufunc 'not_equal'>

pi = 3.14159265359

power = <ufunc 'power'>

remainder = <ufunc 'remainder'>

right_shift = <ufunc 'right_shift'>

sin = <ufunc 'sin'>

sinh = <ufunc 'sinh'>

sqrt = <ufunc 'sqrt'>

subtract = <ufunc 'subtract'>

tan = <ufunc 'tan'>

tanh = <ufunc 'tanh'>

true_divide = <ufunc 'true_divide'>

Function Details

[hide private]

CalcTotalEntropy(examples, nPossibleVals)

source code

Calculates the total entropy of the data set (w.r.t. the results)

**Arguments** 

 - examples: a list (nInstances long) of lists of variable values + instance
           values
 - nPossibleVals: a list (nVars long) of the number of possible values each variable
   can adopt.

**Returns**

  a float containing the informational entropy of the data set.

GenVarTable(examples, nPossibleVals, vars)

source code

Generates a list of variable tables for the examples passed in.

  The table for a given variable records the number of times each possible value
  of that variable appears for each possible result of the function.

**Arguments**

  - examples: a list (nInstances long) of lists of variable values + instance
            values

  - nPossibleVals: a list containing the number of possible values of
                 each variable + the number of values of the function.

  - vars:  a list of the variables to include in the var table


**Returns**

    a list of variable result tables. Each table is a Numeric array
      which is varValues x nResults

ID3(examples, target, attrs, nPossibleVals, depth=0, maxDepth=-1, **kwargs)

source code

Implements the ID3 algorithm for constructing decision trees.

From Mitchell's book, page 56

This is *slightly* modified from Mitchell's book because it supports
  multivalued (non-binary) results.

**Arguments**

  - examples: a list (nInstances long) of lists of variable values + instance
          values

  - target: an int

  - attrs: a list of ints indicating which variables can be used in the tree

  - nPossibleVals: a list containing the number of possible values of
               every variable.

  - depth: (optional) the current depth in the tree

  - maxDepth: (optional) the maximum depth to which the tree
               will be grown

**Returns**

 a DecTree.DecTreeNode with the decision tree

**NOTE:** This code cannot bootstrap (start from nothing...)
      use _ID3Boot_ (below) for that.

ID3Boot(examples, attrs, nPossibleVals, initialVar=None, depth=0, maxDepth=-1, **kwargs)

source code

Bootstrapping code for the ID3 algorithm

see ID3 for descriptions of the arguments

If _initialVar_ is not set, the algorithm will automatically
 choose the first variable in the tree (the standard greedy
 approach).  Otherwise, _initialVar_ will be used as the first
 split.

TestMultiTree()

source code

Testing code for generating trees with more than 2 possible results

TestTree()

source code

Testing code for trees with a single possible result

TestNamedTree()

source code

testing code for named trees