tree

package
Version: v0.0.0-...-dbea759 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 23, 2018 License: MIT Imports: 6 Imported by: 0

Documentation

Overview

Package tree defines a regression tree

Index

Constants

View Source
const ErrCannotPredictFromEmptySet = PredictionError("cannot make prediction for empty set")

ErrCannotPredictFromEmptySet is the error returned when trying to build a prediction based on an empty set of data.

View Source
const ErrCannotPredictFromSample = PredictionError("no prediction available for this kind of sample")

ErrCannotPredictFromSample is the error returned by the Predict method of a tree when the prediction cannot be made because the tree itself cannot make a prediction for that kind of sample, as opposed to cases where values for a feature cannot be obtained for example.

Variables

This section is empty.

Functions

This section is empty.

Types

type Node

type Node struct {
	// An ID to identify the node
	ID string
	// The ID for the parent of the node in the tree
	ParentID string
	// An slice with the IDs of the nodes directly under this node
	SubtreeIDs []string
	// The prediction for samples that satisfied node constraints from the root of the
	// tree up to this node.
	Prediction *Prediction
	// The constraint this node imposes on samples.
	// For growing trees it is the criterion that applied to the parent node's set produces
	// this node's set.
	// For fully-grown trees it is the constraint on the evaluated feature that when
	// satisfied by the evaluated sample selects the current node to continue predicting a
	// a sample or testing the tree against it (unless it is an undefined feature constraint,
	// then it should be the last criterion against which to test).
	FeatureCriterion feature.Criterion
	// The feature on which nodes directly under this node must impose a constraint.
	// For growing trees it is the feature that splits the data into sets for the nodes
	// below, whereas for fully-grown trees it is the feature to ask about next on the
	// sample being predicted or tested against.
	SubtreeFeature feature.Feature
}

Node is a node of the tree

func (*Node) String

func (n *Node) String() string

type NodeStore

type NodeStore interface {
	// Create takes a node and stores it for the
	// first time in the store, creating an ID for
	// it and setting it for the node. It returns
	// an error if the node cannot be stored.
	Create(ctx context.Context, n *Node) error
	// Get takes an id and returns the node in the
	// store with that id (or nil if it cannot be
	// found) or an error if the store cannot be
	// queried
	Get(ctx context.Context, id string) (*Node, error)
	// Store takes a node already existing in the store
	// and updates it on the store. It expect the node
	// to have an ID which it will not alter. It returns
	// an error if the update cannot be performed.
	Store(ctx context.Context, n *Node) error
	// Delete takes a node already existing in the store
	// and deletes it on the store. It returns an error
	// if the node exist but the deletion cannot be
	// performed.
	Delete(ctx context.Context, n *Node) error
	// Close closes the store, implementations should
	// freeing any resources in use as well as ensure
	// any pending changes are applied before returning
	// (unless the context expires). It returns an error
	// if the Close cannot be completed (because of the
	// context or another error)
	Close(ctx context.Context) error
}

NodeStore is an interface to manage a store where nodes can be created, retrieved, updated and deleted.

All it methods take a context that may allow cancelling the operation (thus forcing the return of an error) if the implementation allows it.

func NewMemoryNodeStore

func NewMemoryNodeStore() NodeStore

NewMemoryNodeStore returns an implementation of NodeStore with the process memory space as underlying backend

type Prediction

type Prediction struct {
	// contains filtered or unexported fields
}

Prediction represents a prediction made by a decission regression Tree

func NewPrediction

func NewPrediction(probs map[string]float64, weight int) *Prediction

NewPrediction takes a map[string]float64 with the probabilities of each value in the prediction and an integer with the number of samples in the set from which those probabilities were computed and returns a prediction representing those values.

func NewPredictionFromSet

func NewPredictionFromSet(ctx context.Context, s set.Set, f feature.Feature) (*Prediction, error)

NewPredictionFromSet takes a context, a set and a feature and returns a prediction for the feature based on the (training) data in the set or an error if there are no samples in the set, or the set cannot be queried

func (*Prediction) PredictedValue

func (p *Prediction) PredictedValue() (value string, prob float64)

PredictedValue returns a string with the most probable value and a float64 with its prevalence

func (*Prediction) Probabilities

func (p *Prediction) Probabilities() map[string]float64

Probabilities returns a map of string to float64 containing the probabilities of each available value

func (*Prediction) ProbabilityOf

func (p *Prediction) ProbabilityOf(value string) float64

ProbabilityOf takes a string value and returns the float64 probability of that value according to the prediction.

func (*Prediction) String

func (p *Prediction) String() string

func (*Prediction) Weight

func (p *Prediction) Weight() int

Weight returns the weight of the prediction: an int equal to the number of samples in the set from which the prediction was made

type PredictionError

type PredictionError string

PredictionError represents an error related with predictions

func (PredictionError) Error

func (pe PredictionError) Error() string

type Tree

type Tree struct {
	NodeStore
	RootID       string
	ClassFeature feature.Feature
}

Tree represents a a regression tree. It is composed of a NodeStore where all its nodes are stored, the id for the root node of the tree and the classFeature it is able to predict.

func New

func New(rootID string, nodeStore NodeStore, classFeature feature.Feature) *Tree

New takes the ID for the root Node, a NodeStore and a class feature and returns a tree composed of the nodes in the NodeStore connected to the node with the given root ID that to predict the given feature.

func (*Tree) Predict

func (t *Tree) Predict(ctx context.Context, s feature.Sample) (*Prediction, error)

Predict takes a sample and returns a prediction according to the tree and an error if the prediction could not be made.

func (*Tree) String

func (t *Tree) String() string

func (*Tree) Test

func (t *Tree) Test(ctx context.Context, s set.Set) (float64, int, error)

Test takes a context.Context, a Set and a class Feature and returns three values:

* the prediction success rate of the tree over the given Set for the classFeature
* the number of failing predictions for the set because of ErrCannotPredictFromSample errors
* an error if a prediction could not be set for reasons other than the tree not
  being able to do so. If this is not nil, the other values will be 0.0 and 0
  respectively

func (*Tree) Traverse

func (t *Tree) Traverse(ctx context.Context, bottomup bool, f func(context.Context, *Node) error) error

Traverse takes a context, bottomup boolean and an error-returning function that takes a context and a node as parameters, and goes through the tree running the function with the context and every traversed node. Traverse will call the function with a parent node before calling it for its children if bottomup is false, and call it after its children if bottomup is true. If the given context times out or is cancelled, the context error is returned. If a node cannot be retrieved from the tree's node store, the obtained error is returned. If the call to the function returns an error, the traversing is aborted and the error is returned. Otherwise, when the traversing is over, nil is returned.

Directories

Path Synopsis
Package json provides functions that marshall/unmarshall a tree.Tree as/from JSON
Package json provides functions that marshall/unmarshall a tree.Tree as/from JSON

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL