CloudForest: github.com/ryanbressler/CloudForest Index | Files | Directories

package CloudForest

import "github.com/ryanbressler/CloudForest"

Package CloudForest implements ensembles of decision trees for machine learning in pure Go (golang to search engines). It allows for a number of related algorithms for classification, regression, feature selection and structure analysis on heterogeneous numerical/categorical data with missing values. These include:

* Breiman and Cutler's Random Forest for Classification and Regression

* Adaptive Boosting (AdaBoost) Classification

* Gradiant Boosting Tree Regression

* Entropy and Cost driven classification

* L1 regression

* Feature selection with artificial contrasts

* Proximity and model structure analysis

* Roughly balanced bagging for unbalanced classification

The API hasn't stabilized yet and may change rapidly. Tests and benchmarks have been performed only on embargoed data sets and can not yet be released.

Library Documentation is in code and can be viewed with godoc or live at: http://godoc.org/github.com/ryanbressler/CloudForest

Documentation of command line utilities and file formats can be found in README.md, which can be viewed fromated on github: http://github.com/ryanbressler/CloudForest

Pull requests and bug reports are welcome.

CloudForest was created by Ryan Bressler and is being developed in the Shumelivich Lab at the Institute for Systems Biology for use on genomic/biomedical data with partial support from The Cancer Genome Atlas and the Inova Translational Medicine Institute.

Goals

CloudForest is intended to provide fast, comprehensible building blocks that can be used to implement ensembles of decision trees. CloudForest is written in Go to allow a data scientist to develop and scale new models and analysis quickly instead of having to modify complex legacy code.

Data structures and file formats are chosen with use in multi threaded and cluster environments in mind.

Working with Trees

Go's support for function types is used to provide a interface to run code as data is percolated through a tree. This method is flexible enough that it can extend the tree being analyzed. Growing a decision tree using Breiman and Cutler's method can be done in an anonymous function/closure passed to a tree's root node's Recurse method:

t.Root.Recurse(func(n *Node, innercases []int) {

	if (2 * leafSize) <= len(innercases) {
		SampleFirstN(&candidates, mTry)
		best, impDec := fm.BestSplitter(target, innercases, candidates[:mTry], false, allocs)
		if best != nil && impDec > minImp {
			//not a leaf node so define the splitter and left and right nodes
			//so recursion will continue
			n.Splitter = best
			n.Pred = ""
			n.Left = new(Node)
			n.Right = new(Node)

			return
		}
	}

This allows a researcher to include whatever additional analysis they need (importance scores, proximity etc) in tree growth. The same Recurse method can also be used to analyze existing forests to tabulate scores or extract structure. Utilities like leafcount and errorrate use this method to tabulate data about the tree in collection objects.

Stackable Interfaces

Decision tree's are grown with the goal of reducing "Impurity" which is usually defined as Gini Impurity for categorical targets or mean squared error for numerical targets. CloudForest grows trees against the Target interface which allows for alternative definitions of impurity. CloudForest includes several alternative targets:

EntropyTarget : For use in entropy minimizing classification
RegretTarget  : For use in classification driven by differing costs in mis-categorization.
L1Target      : For use in L1 norm error regression (which may be less sensitive to outliers).
OrdinalTarget : For ordinal regression

Additional targets can be stacked on top of these target to add boosting functionality:

GradBoostTarget : For Gradient Boosting Regression
AdaBoostTarget  : For Adaptive Boosting Classification

Efficient Splitting

Repeatedly splitting the data and searching for the best split at each node of a decision tree are the most computationally intensive parts of decision tree learning and CloudForest includes optimized code to perform these tasks.

Go's slices are used extensively in CloudForest to make it simple to interact with optimized code. Many previous implementations of Random Forest have avoided reallocation by reordering data in place and keeping track of start and end indexes. In go, slices pointing at the same underlying arrays make this sort of optimization transparent. For example a function like:

func(s *Splitter) SplitInPlace(fm *FeatureMatrix, cases []int) (l []int, r []int)

can return left and right slices that point to the same underlying array as the original slice of cases but these slices should not have their values changed.

Functions used while searching for the best split also accepts pointers to reusable slices and structs to maximize speed by keeping memory allocations to a minimum. BestSplitAllocs contains pointers to these items and its use can be seen in functions like:

func (fm *FeatureMatrix) BestSplitter(target Target,
	cases []int,
	candidates []int,
	extraRandom bool,
	allocs *BestSplitAllocs) (s *Splitter, impurityDecrease float64)

func (f *Feature) BestSplit(target Target,
	cases *[]int,
	parentImp float64,
	randomSplit bool,
	allocs *BestSplitAllocs) (bestNum float64, bestCat int, bestBigCat *big.Int, impurityDecrease float64)

For categorical predictors, BestSplit will also attempt to intelligently choose between 4 different implementations depending on user input and the number of categories. These include exhaustive, random, and iterative searches for the best combination of categories implemented with bitwise operations against int and big.Int. See BestCatSplit, BestCatSplitIter, BestCatSplitBig and BestCatSplitIterBig.

All numerical predictors are handled by BestNumSplit which relies on go's sorting package.

Parallelism and Scaling

Training a Random forest is an inherently parallel process and CloudForest is designed to allow parallel implementations that can tackle large problems while keeping memory usage low by writing and using data structures directly to/from disk.

Trees can be grown in separate go routines. The growforest utility provides an example of this that uses go routines and channels to grow trees in parallel and write trees to disk as the are finished by the "worker" go routines. The few summary statistics like mean impurity decrease per feature (importance) can be calculated using thread safe data structures like RunningMean.

Trees can also be grown on separate machines. The .sf stochastic forest format allows several small forests to be combined by concatenation and the ForestReader and ForestWriter structs allow these forests to be accessed tree by tree (or even node by node) from disk.

For data sets that are too big to fit in memory on a single machine Tree.Grow and FeatureMatrix.BestSplitter can be reimplemented to load candidate features from disk, distributed database etc.

Missing Values

By default cloud forest uses a fast heuristic for missing values. When proposing a split on a feature with missing data the missing cases are removed and the impurity value is corrected to use three way impurity which reduces the bias towards features with lots of missing data:

I(split) = p(l)I(l)+p(r)I(r)+p(m)I(m)

Missing values in the target variable are left out of impurity calculations.

This provided generally good results at a fraction of the computational costs of imputing data.

Optionally, feature.ImputeMissing or featurematrixImputeMissing can be called before forest growth to impute missing values to the feature mean/mode which Brieman [2] suggests as a fast method for imputing values.

This forest could also be analyzed for proximity (using leafcount or tree.GetLeaves) to do the more accurate proximity weighted imputation Brieman describes.

Experimental support is provided for 3 way splitting which splits missing cases onto a third branch. [2] This has so far yielded mixed results in testing.

At some point in the future support may be added for local imputing of missing values during tree growth as described in [3]

[1] http://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm#missing1

[2] https://code.google.com/p/rf-ace/

[3] http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.aoas/1223908043&page=record

Main Structures

In CloudForest data is stored using the FeatureMatrix struct which contains Features.

The Feature struct implements storage and methods for both categorical and numerical data and calculations of impurity etc and the search for the best split.

The Target interface abstracts the methods of Feature that are needed for a feature to be predictable. This allows for the implementation of alternative types of regression and classification.

Trees are built from Nodes and Splitters and stored within a Forest. Tree has a Grow implements Brieman and Cutler's method (see extract above) for growing a tree. A GrowForest method is also provided that implements the rest of the method including sampling cases but it may be faster to grow the forest to disk as in the growforest utility.

Prediction and Voting is done using Tree.Vote and CatBallotBox and NumBallotBox which implement the VoteTallyer interface.

Index

Package Files

NPtarget.go adaboosttarget.go adacosttarget.go arff.go catballotbox.go catmap.go densecatfeature.go densenumfeature.go densitytarget.go dentropytarget.go doc.go entropytarget.go featureinterfaces.go featurematrix.go forestreader.go forestwriter.go forrest.go gradboostclasstarget.go gradboosttarget.go hdistancetarget.go l1target.go libsvm.go node.go numadaboostingtarget.go numballotbox.go ordinaltarget.go regrettarget.go sampeling.go sklearn_tree.go sortablefeature.go splitallocations.go splitter.go sumballotbox.go transduction.go tree.go utils.go voter.go wrftarget.go

func BuildScikitTree Uses

func BuildScikitTree(depth int, n *Node, sktree *ScikitTree)

BuildScikkitTree currentelly only builds the split threshold and node structure of a sickit tree from a Cloudforest tree specified by root node

func Expit Uses

func Expit(x float64) (out float64)

func FriedmanScore Uses

func FriedmanScore(allocs *BestSplitAllocs, l, r *[]int) (impurityDecrease float64)

func Logit Uses

func Logit(x float64) float64

func NewRunningMeans Uses

func NewRunningMeans(size int) *[]*RunningMean

NewRunningMeans returns an initalized *[]*RunningMean.

func ParseAsIntOrFractionOfTotal Uses

func ParseAsIntOrFractionOfTotal(term string, total int) (parsed int)

ParseAsIntOrFractionOfTotal parses strings that may specify an count or a percent of the total for use in specifying paramaters. It parses term as a float if it contains a "." and as an int otherwise. If term is parsed as a float frac it returns int(math.Ceil(frac * float64(total))). It returns zero if term == "" or if a parsing error occures.

func ParseFloat Uses

func ParseFloat(s string) float64

func SampleFirstN Uses

func SampleFirstN(deck *[]int, samples *[]int, n int, nconstants int)

SampleFirstN ensures that the first n entries in the supplied deck are randomly drawn from all entries without replacement for use in selecting candidate features to split on. It accepts a pointer to the deck so that it can be used repeatedly on the same deck avoiding reallocations.

func SampleWithReplacment Uses

func SampleWithReplacment(nSamples int, totalCases int) (cases []int)

SampleWithReplacment samples nSamples random draws from [0,totalCases) with replacement for use in selecting cases to grow a tree from.

func WriteArffCases Uses

func WriteArffCases(data *FeatureMatrix, cases []int, relation string, outfile io.Writer) error

WriteArffCases writes the specified cases from the provied feature matrix into an arff file with the given relation string.

func WriteLibSvm Uses

func WriteLibSvm(data *FeatureMatrix, targetn string, outfile io.Writer) error

func WriteLibSvmCases Uses

func WriteLibSvmCases(data *FeatureMatrix, cases []int, targetn string, outfile io.Writer) error

type AdaBoostTarget Uses

type AdaBoostTarget struct {
    CatFeature
    Weights []float64
}

AdaBoostTarget wraps a numerical feature as a target for us in Adaptive Boosting (AdaBoost)

func NewAdaBoostTarget Uses

func NewAdaBoostTarget(f CatFeature) (abt *AdaBoostTarget)

NewAdaBoostTarget creates a categorical adaptive boosting target and initializes its weights.

func (*AdaBoostTarget) Boost Uses

func (t *AdaBoostTarget) Boost(leaves *[][]int) (weight float64)

Boost performs categorical adaptive boosting using the specified partition and returns the weight that tree that generated the partition should be given.

func (*AdaBoostTarget) ImpFromCounts Uses

func (target *AdaBoostTarget) ImpFromCounts(cases *[]int, counter *[]int) (e float64)

ImpFromCounts recalculates gini impurity from class counts for us in intertive updates.

func (*AdaBoostTarget) Impurity Uses

func (target *AdaBoostTarget) Impurity(cases *[]int, counter *[]int) (e float64)

Impurity is an AdaCosting that uses the weights specified in weights.

func (*AdaBoostTarget) SplitImpurity Uses

func (target *AdaBoostTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

SplitImpurity is an AdaCosting version of SplitImpurity.

func (*AdaBoostTarget) UpdateSImpFromAllocs Uses

func (target *AdaBoostTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type AdaCostTarget Uses

type AdaCostTarget struct {
    CatFeature
    Weights []float64
    Costs   []float64
}

AdaCostTarget wraps a numerical feature as a target for us in Cost Sensitive Adaptive Boosting (AdaC2.M1)

"Boosting for Learning Multiple Classes with Imbalanced Class Distribution" Yanmin Sun, Mohamed S. Kamel and Yang Wang

See equations in slides here: http://people.ee.duke.edu/~lcarin/Minhua4.18.08.pdf

func NewAdaCostTarget Uses

func NewAdaCostTarget(f CatFeature) (abt *AdaCostTarget)

NewAdaCostTarget creates a categorical adaptive boosting target and initializes its weights.

func (*AdaCostTarget) Boost Uses

func (t *AdaCostTarget) Boost(leaves *[][]int) (weight float64)

Boost performs categorical adaptive boosting using the specified partition and returns the weight that tree that generated the partition should be given.

func (*AdaCostTarget) ImpFromCounts Uses

func (target *AdaCostTarget) ImpFromCounts(cases *[]int, counter *[]int) (e float64)

ImpFromCounts recalculates gini impurity from class counts for us in intertive updates.

func (*AdaCostTarget) Impurity Uses

func (target *AdaCostTarget) Impurity(cases *[]int, counter *[]int) (e float64)

Impurity is an AdaCosting that uses the weights specified in weights.

func (*AdaCostTarget) SetCosts Uses

func (target *AdaCostTarget) SetCosts(costmap map[string]float64)

RegretTarget.SetCosts puts costs in a map[string]float64 by feature name into the proper entries in RegretTarget.Costs.

func (*AdaCostTarget) SplitImpurity Uses

func (target *AdaCostTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

SplitImpurity is an AdaCosting version of SplitImpurity.

func (*AdaCostTarget) UpdateSImpFromAllocs Uses

func (target *AdaCostTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type Bagger Uses

type Bagger interface {
    Sample(samples *[]int, n int)
}

type BalancedSampler Uses

type BalancedSampler struct {
    Cases [][]int
}

BalancedSampler provides for random sampelign of integers (usually case indexes) in a way that ensures a balanced presence of classes.

func NewBalancedSampler Uses

func NewBalancedSampler(catf *DenseCatFeature) (s *BalancedSampler)

NeaBalancedSampler initalizes a balanced sampler that will evenly balance cases between the classes present in the provided DesnseeCatFeature.

func (*BalancedSampler) Sample Uses

func (s *BalancedSampler) Sample(samples *[]int, n int)

Sample samples n integers in a balnced-with-replacment fashion into the provided array.

type BestSplitAllocs Uses

type BestSplitAllocs struct {
    L              []int //Allocated to size
    R              []int
    M              []int
    LM             []int //Used to point at other array
    RM             []int
    MM             []int
    Left           *[]int  //left cases for potential splits
    Right          *[]int  //right cases for potential splits
    NonMissing     *[]int  //non missing cases for potential splits
    Counter        *[]int  //class counter for counting classes in splits used alone of for missing
    LCounter       *[]int  //left class counter sumarizing (mean) splits
    RCounter       *[]int  //right class counter sumarizing (mean) splits
    Lsum           float64 //left value for sumarizing splits
    Rsum           float64 //right value for sumarizing  splits
    Msum           float64 //missing value for sumarizing splits
    Lsum_sqr       float64 //left value for sumarizing splits
    Rsum_sqr       float64 //right value for sumarizing  splits
    Msum_sqr       float64 //missing value for sumarizing splits
    CatVals        []int
    SortVals       []float64
    Sorter         *SortableFeature //for learning from numerical features
    ContrastTarget Target
    Rnd            *rand.Rand //prevent contention on global rand source
}

BestSplitAllocs contains reusable allocations for split searching and evaluation. Seprate instances should be used in each go routing doing learning.

func NewBestSplitAllocs Uses

func NewBestSplitAllocs(nTotalCases int, target Target) (bsa *BestSplitAllocs)

NewBestSplitAllocs initializes all of the reusable allocations for split searching to the appropriate size. nTotalCases should be number of total cases in the feature matrix being analyzed.

type BoostingTarget Uses

type BoostingTarget interface {
    Target
    Boost(partition *[][]int, preds *[]string) (weight float64)
}

BoostingTarget augments Target with a "Boost" method that will be called after each tree is grown with the partion generated by that tree. It will return the weigh the tree should be given and boost the target for the next tree.

type CatBallot Uses

type CatBallot struct {
    Mutex sync.Mutex
    Map   map[int]float64
}

CatBallot is used insideof CatBallotBox to record catagorical votes in a thread safe manner.

func NewCatBallot Uses

func NewCatBallot() (cb *CatBallot)

NewCatBallot returns a pointer to an initalized CatBallot with a 0 size Map.

type CatBallotBox Uses

type CatBallotBox struct {
    *CatMap
    Box []*CatBallot
}

CatBallotBox keeps track of votes by trees in a thread safe manner.

func NewCatBallotBox Uses

func NewCatBallotBox(size int) *CatBallotBox

NewCatBallotBox builds a new ballot box for the number of cases specified by "size".

func (*CatBallotBox) Tally Uses

func (bb *CatBallotBox) Tally(i int) (predicted string)

Tally tallies the votes for the case specified by i as if it is a Categorical or boolean feature. Ie it returns the mode (the most frequent value) of all votes.

func (*CatBallotBox) TallyError Uses

func (bb *CatBallotBox) TallyError(feature Feature) (e float64)

TallyError returns the balanced classification error for categorical features.

1 - sum((sum(Y(xi)=Y'(xi))/|xi|))

where Y are the labels Y' are the estimated labels xi is the set of samples with the ith actual label

Case for which the true category is not known are ignored.

func (*CatBallotBox) Vote Uses

func (bb *CatBallotBox) Vote(casei int, pred string, weight float64)

Vote registers a vote that case "casei" should be predicted to be the category "pred".

type CatFeature Uses

type CatFeature interface {
    Feature
    CountPerCat(cases *[]int, counter *[]int)
    MoveCountsRtoL(allocs *BestSplitAllocs, movedRtoL *[]int)
    CatToNum(value string) (numericv int)
    NumToCat(i int) (value string)
    Geti(i int) int
    Puti(i int, v int)
    Modei(cases *[]int) int
    Mode(cases *[]int) string
    Gini(cases *[]int) float64
    GiniWithoutAlocate(cases *[]int, counts *[]int) (e float64)
    EncodeToNum() (fs []Feature)
    OneHot() (fs []Feature)
}

CatFeature contains the methods of Feature plus methods needed to implement diffrent types of classification. It is usually embeded by classification targets to provide access to the underlying data.

type CatMap Uses

type CatMap struct {
    Map  map[string]int //map categories from string to Num
    Back []string       // map categories from Num to string
}

CatMap is for mapping categorical values to integers. It contains:

Map  : a map of ints by the string used for the category
Back : a slice of strings by the int that represents them

And is embedded by Feature and CatBallotBox.

func (*CatMap) CatToNum Uses

func (cm *CatMap) CatToNum(value string) (numericv int)

CatToNum provides the int equivalent of the provided categorical value if it already exists or adds it to the map and returns the new value if it doesn't.

func (*CatMap) NCats Uses

func (cm *CatMap) NCats() (n int)

NCats returns the number of distinct catagories.

func (*CatMap) NumToCat Uses

func (cm *CatMap) NumToCat(i int) (value string)

NumToCat returns the catagory label that has been assigned i

type CodedRecursable Uses

type CodedRecursable func(*Node, *[]int, int, int) (int, interface{}, int)

type DEntropyTarget Uses

type DEntropyTarget struct {
    CatFeature
    Costs []float64
}

DEntropyTarget wraps a categorical feature for use in entropy driven classification as in Ross Quinlan's ID3 (Iterative Dichotomizer 3) with a the entropy modified to use "disutility entropy"

I = - k Sum ri * pi * log(pi)

func NewDEntropyTarget Uses

func NewDEntropyTarget(f CatFeature) *DEntropyTarget

NewDEntropyTarget creates a RefretTarget and initializes DEntropyTarget.Costs to the proper length.

func (*DEntropyTarget) FindPredicted Uses

func (target *DEntropyTarget) FindPredicted(cases []int) (pred string)

func (*DEntropyTarget) ImpFromCounts Uses

func (target *DEntropyTarget) ImpFromCounts(total int, counts *[]int) (e float64)

func (*DEntropyTarget) Impurity Uses

func (target *DEntropyTarget) Impurity(cases *[]int, counts *[]int) (e float64)

DEntropyTarget.Impurity implements categorical entropy as sum(pj*log2(pj)) where pj is the number of cases with the j'th category over the total number of cases.

func (*DEntropyTarget) SetCosts Uses

func (target *DEntropyTarget) SetCosts(costmap map[string]float64)

NewDEntropyTarget.SetCosts puts costs in a map[string]float64 by feature name into the proper entries in NewDEntropyTarget.Costs.

func (*DEntropyTarget) SplitImpurity Uses

func (target *DEntropyTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

DEntropyTarget.SplitImpurity is a version of Split Impurity that calls DEntropyTarget.Impurity

func (*DEntropyTarget) UpdateSImpFromAllocs Uses

func (target *DEntropyTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type DenseCatFeature Uses

type DenseCatFeature struct {
    *CatMap
    CatData      []int
    Missing      []bool
    Name         string
    RandomSearch bool
    HasMissing   bool
}

DenseCatFeature is a structure representing a single feature in a feature matrix. It contains: An embedded CatMap (may only be instantiated for cat data)

NumData   : A slice of floates used for numerical data and nil otherwise
CatData   : A slice of ints for categorical data and nil otherwise
Missing   : A slice of bools indicating missing values. Measure this for length.
Numerical : is the feature numerical
Name      : the name of the feature

func (*DenseCatFeature) Append Uses

func (f *DenseCatFeature) Append(v string)

Append will parse and append a single value to the end of the feature. It is generally only used during data parseing.

func (*DenseCatFeature) BestBinSplit Uses

func (f *DenseCatFeature) BestBinSplit(target Target,
    cases *[]int,
    parentImp float64,
    maxEx int,
    leafSize int,
    a *BestSplitAllocs) (bestSplit int, impurityDecrease float64, constant bool)

BestBinSplit performs an exhaustive search for the split that minimizes impurity in the specified target for categorical features with 2 categories. It expects to be provided for cases fir which the feature is not missing.

This implementation follows Brieman's implementation and the R/Matlab implementations based on it use exhaustive search for when there are less than 25/10 categories and random splits above that.

Searching is implemented via bitwise operations vs an incrementing or random int (32 bit) for speed but will currently only work when there are less then 31 categories. Use one of the Big functions above that.

The best split is returned as an int for which the bits corresponding to categories that should be sent left has been flipped. This can be decoded into a splitter using DecodeSplit on the training feature and should not be applied to testing data without doing so as the order of categories may have changed.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*DenseCatFeature) BestCatSplit Uses

func (f *DenseCatFeature) BestCatSplit(target Target,
    cases *[]int,
    parentImp float64,
    maxEx int,
    leafSize int,
    allocs *BestSplitAllocs) (bestSplit int, impurityDecrease float64, constant bool)

BestCatSplit performs an exhaustive search for the split that minimizes impurity in the specified target for categorical features with less then 31 categories. It expects to be provided for cases fir which the feature is not missing.

This implementation follows Brieman's implementation and the R/Matlab implementations based on it use exhaustive search for when there are less than 25/10 categories and random splits above that.

Searching is implemented via bitwise operations vs an incrementing or random int (32 bit) for speed but will currently only work when there are less then 31 categories. Use one of the Big functions above that.

The best split is returned as an int for which the bits corresponding to categories that should be sent left has been flipped. This can be decoded into a splitter using DecodeSplit on the training feature and should not be applied to testing data without doing so as the order of categories may have changed.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*DenseCatFeature) BestCatSplitBig Uses

func (f *DenseCatFeature) BestCatSplitBig(target Target, cases *[]int, parentImp float64, maxEx int, leafSize int, allocs *BestSplitAllocs) (bestSplit *big.Int, impurityDecrease float64, constant bool)

BestCatSplitBig performs a random/exhaustive search to find the split that minimizes impurity in the specified target. It expects to be provided for cases fir which the feature is not missing.

Searching is implemented via bitwise on Big.Ints to handle large n categorical features but BestCatSplit should be used for n <31.

The best split is returned as a BigInt for which the bits corresponding to categories that should be sent left has been flipped. This can be decoded into a splitter using DecodeSplit on the training feature and should not be applied to testing data without doing so as the order of categories may have changed.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*DenseCatFeature) BestCatSplitIter Uses

func (f *DenseCatFeature) BestCatSplitIter(target Target, cases *[]int, parentImp float64, leafSize int, allocs *BestSplitAllocs) (bestSplit int, impurityDecrease float64, constant bool)

BestCatSplitIter performs an iterative search to find the split that minimizes impurity in the specified target. It expects to be provided for cases fir which the feature is not missing.

Searching is implemented via bitwise ops on ints (32 bit) for speed but will currently only work when there are <31 categories. Use BigInterBestCatSplit above that.

The best split is returned as an int for which the bits corresponding to categories that should be sent left has been flipped. This can be decoded into a splitter using DecodeSplit on the training feature and should not be applied to testing data without doing so as the order of categories may have changed.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*DenseCatFeature) BestCatSplitIterBig Uses

func (f *DenseCatFeature) BestCatSplitIterBig(target Target, cases *[]int, parentImp float64, leafSize int, allocs *BestSplitAllocs) (bestSplit *big.Int, impurityDecrease float64, constant bool)

BestCatSplitIterBig performs an iterative search to find the split that minimizes impurity in the specified target. It expects to be provided for cases fir which the feature is not missing.

Searching is implemented via bitwise on integers for speed but will currently only work when there are less categories then the number of bits in an int.

The best split is returned as an int for which the bits corresponding to categories that should be sent left has been flipped. This can be decoded into a splitter using DecodeSplit on the training feature and should not be applied to testing data without doing so as the order of categories may have changed.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*DenseCatFeature) BestSplit Uses

func (f *DenseCatFeature) BestSplit(target Target,
    cases *[]int,
    parentImp float64,
    leafSize int,
    randomSplit bool,
    allocs *BestSplitAllocs) (codedSplit interface{}, impurityDecrease float64, constant bool)

BestSplit finds the best split of the features that can be achieved using the specified target and cases. It returns a Splitter and the decrease in impurity.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*DenseCatFeature) Copy Uses

func (f *DenseCatFeature) Copy() Feature

Copy returns a copy of f.

func (*DenseCatFeature) CopyInTo Uses

func (f *DenseCatFeature) CopyInTo(copyf Feature)

CopyInTo coppoes the values of the feature into a new feature...doesn't copy CatMap, name etc.

func (*DenseCatFeature) CountPerCat Uses

func (target *DenseCatFeature) CountPerCat(cases *[]int, counts *[]int)

CountPerCat puts per catagory counts in the supplied counter. It is designed for use in a target and doesn't check for missing values.

func (*DenseCatFeature) DecodeSplit Uses

func (f *DenseCatFeature) DecodeSplit(codedSplit interface{}) (s *Splitter)

DecodeSplit builds a splitter from the numeric values returned by BestNumSplit or BestCatSplit. Numeric splitters are decoded to send values <= num left. Categorical splitters are decoded to send categorical values for which the bit in cat is 1 left.

func (*DenseCatFeature) EncodeToNum Uses

func (f *DenseCatFeature) EncodeToNum() (fs []Feature)

EncodeToNum returns numerical features doing simple binary encoding of Each of the distinct catagories in the feature.

func (*DenseCatFeature) FilterMissing Uses

func (f *DenseCatFeature) FilterMissing(cases *[]int, filtered *[]int)

FilterMissing loops over the cases and appends them into filtered. For most use cases filtered should have zero length before you begin as it is not reset internally

func (*DenseCatFeature) FindPredicted Uses

func (f *DenseCatFeature) FindPredicted(cases []int) (pred string)

FindPredicted takes the indexes of a set of cases and returns the predicted value. For categorical features this is a string containing the most common category and for numerical it is the mean of the values.

func (*DenseCatFeature) GetName Uses

func (f *DenseCatFeature) GetName() string

GetName returns the name of the feature.

func (*DenseCatFeature) GetStr Uses

func (f *DenseCatFeature) GetStr(i int) string

GetStr returns the class label for the i'th case.

func (*DenseCatFeature) Geti Uses

func (f *DenseCatFeature) Geti(i int) int

Geti returns the int encoding of the class label for the i'th case.

func (*DenseCatFeature) Gini Uses

func (target *DenseCatFeature) Gini(cases *[]int) (e float64)

Gini returns the gini impurity for the specified cases in the feature gini impurity is calculated as 1 - Sum(fi^2) where fi is the fraction of cases in the ith catagory.

func (*DenseCatFeature) GiniWithoutAlocate Uses

func (target *DenseCatFeature) GiniWithoutAlocate(cases *[]int, counts *[]int) (e float64)

GiniWithoutAlocate calculates gini impurity using the supplied counter which must be a slice with length equal to the number of cases. This allows you to reduce allocations but the counter will also contain per category counts.

func (*DenseCatFeature) GoesLeft Uses

func (f *DenseCatFeature) GoesLeft(i int, splitter *Splitter) bool

GoesLeft tests if the i'th case goes left according to the supplid Spliter.

func (*DenseCatFeature) ImpFromCounts Uses

func (target *DenseCatFeature) ImpFromCounts(total int, counts *[]int) (e float64)

ImpFromCounts recalculates gini impurity from class counts for us in intertive updates.

func (*DenseCatFeature) Impurity Uses

func (target *DenseCatFeature) Impurity(cases *[]int, counter *[]int) (e float64)

Impurity returns Gini impurity or mean squared error vs the mean for a set of cases depending on weather the feature is categorical or numerical

func (*DenseCatFeature) ImputeMissing Uses

func (f *DenseCatFeature) ImputeMissing()

ImputeMissing imputes the missing values in a feature to the mean or mode of the feature.

func (*DenseCatFeature) IsMissing Uses

func (f *DenseCatFeature) IsMissing(i int) bool

IsMissing returns weather the given case is missing in the feature.

func (*DenseCatFeature) Length Uses

func (f *DenseCatFeature) Length() int

Length returns the number of cases in the feature.

func (*DenseCatFeature) MissingVals Uses

func (f *DenseCatFeature) MissingVals() bool

MissingVals returns weather the feature has any missing values.

func (*DenseCatFeature) Mode Uses

func (f *DenseCatFeature) Mode(cases *[]int) (m string)

Mode returns the mode category feature for the cases specified.

func (*DenseCatFeature) Modei Uses

func (f *DenseCatFeature) Modei(cases *[]int) (m int)

Modei returns the mode category feature for the cases specified.

func (*DenseCatFeature) MoveCountsRtoL Uses

func (target *DenseCatFeature) MoveCountsRtoL(allocs *BestSplitAllocs, movedRtoL *[]int)

MoveCoutsRtoL moves the by case counts from R to L for use in iterave updates.

func (*DenseCatFeature) OneHot Uses

func (f *DenseCatFeature) OneHot() (fs []Feature)

func (*DenseCatFeature) PutMissing Uses

func (f *DenseCatFeature) PutMissing(i int)

PutMissing sets the given case i to be missing.

func (*DenseCatFeature) PutStr Uses

func (f *DenseCatFeature) PutStr(i int, v string)

PutStr set's the i'th case to the class label v.

func (*DenseCatFeature) Puti Uses

func (f *DenseCatFeature) Puti(i int, v int)

Puti puts the v't class label encoding into the ith case.

func (*DenseCatFeature) Shuffle Uses

func (f *DenseCatFeature) Shuffle()

Shuffle does an inflace shuffle of the specified feature

func (*DenseCatFeature) ShuffleCases Uses

func (f *DenseCatFeature) ShuffleCases(cases *[]int, allocs *BestSplitAllocs)

ShuffleCases does an inplace shuffle of the specified cases

func (*DenseCatFeature) ShuffledCopy Uses

func (f *DenseCatFeature) ShuffledCopy() Feature

ShuffledCopy returns a shuffled version of f for use as an artificial contrast in evaluation of importance scores. The new feature will be named featurename:SHUFFLED

func (*DenseCatFeature) Span Uses

func (target *DenseCatFeature) Span(cases *[]int, counts *[]int) float64

Span counts the number of distincts cats present in the specified cases.

func (*DenseCatFeature) Split Uses

func (f *DenseCatFeature) Split(codedSplit interface{}, cases []int) (l []int, r []int, m []int)

Split does an inplace split from a coded spli value which should be an int or Big.Int with bit flags representing which class labels go left.

func (*DenseCatFeature) SplitImpurity Uses

func (target *DenseCatFeature) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

SplitImpurity calculates the impurity of a split into the specified left and right groups. This is defined as pLi*(tL)+pR*i(tR) where pL and pR are the probability of case going left or right and i(tl) i(tR) are the left and right impurities.

Counter is only used for categorical targets and should have the same length as the number of categories in the target.

func (*DenseCatFeature) SplitPoints Uses

func (f *DenseCatFeature) SplitPoints(codedSplit interface{}, cs *[]int) (int, int)

SplitPoints reorders cs and returns the indexes at which left and right cases end and begin The codedSplit whould be an int or Big.Int with bits set to indicate which classes go left.

func (*DenseCatFeature) UpdateSImpFromAllocs Uses

func (target *DenseCatFeature) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type DenseNumFeature Uses

type DenseNumFeature struct {
    NumData    []float64
    Missing    []bool
    Name       string
    HasMissing bool
}

DenseNumFeature contains dense float64 training data, possibly with missing values.

func (*DenseNumFeature) Append Uses

func (f *DenseNumFeature) Append(v string)

Append will parse and append a single value to the end of the feature. It is generally only used during data parseing.

func (*DenseNumFeature) BestNumSplit Uses

func (f *DenseNumFeature) BestNumSplit(target Target,
    cases *[]int,
    parentImp float64,
    leafSize int,
    randomSplit bool,
    allocs *BestSplitAllocs) (codedSplit interface{}, impurityDecrease float64, constant bool)

BestNumSplit searches over the possible splits of cases that can be made with f and returns the one that minimizes the impurity of the target and the impurity decrease.

It expects to be provided cases for which the feature is not missing.

It searches by sorting the cases by the potential splitter and then evaluating each "gap" between cases with non equal value as a potential split.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*DenseNumFeature) BestSplit Uses

func (f *DenseNumFeature) BestSplit(target Target,
    cases *[]int,
    parentImp float64,
    leafSize int,
    randomSplit bool,
    allocs *BestSplitAllocs) (codedSplit interface{}, impurityDecrease float64, constant bool)

BestSplit finds the best split of the features that can be achieved using the specified target and cases. It returns a Splitter and the decrease in impurity.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*DenseNumFeature) Copy Uses

func (f *DenseNumFeature) Copy() Feature

Copy returns a copy of f.

func (*DenseNumFeature) CopyInTo Uses

func (f *DenseNumFeature) CopyInTo(copyf Feature)

CopyInTo copies the values and missing state from one numerical feature into another.

func (*DenseNumFeature) DecodeSplit Uses

func (f *DenseNumFeature) DecodeSplit(codedSplit interface{}) (s *Splitter)

Decode split builds a splitter from the numeric values returned by BestNumSplit or BestCatSplit. Numeric splitters are decoded to send values <= num left. Categorical splitters are decoded to send categorical values for which the bit in cat is 1 left.

func (*DenseNumFeature) Error Uses

func (target *DenseNumFeature) Error(cases *[]int, predicted float64) (e float64)

Error returns the Mean Squared error of the cases specified vs the predicted value. Only non missing cases are considered.

func (*DenseNumFeature) FilterMissing Uses

func (f *DenseNumFeature) FilterMissing(cases *[]int, filtered *[]int)

FilterMissing loops over the cases and appends them into filtered. For most use cases filtered should have zero length before you begin as it is not reset internally

func (*DenseNumFeature) FindPredicted Uses

func (f *DenseNumFeature) FindPredicted(cases []int) (pred string)

Find predicted takes the indexes of a set of cases and returns the predicted value. For categorical features this is a string containing the most common category and for numerical it is the mean of the values.

func (*DenseNumFeature) Get Uses

func (f *DenseNumFeature) Get(i int) float64

Get returns the value in the i'th posiiton. It doesn't check for missing values.

func (*DenseNumFeature) GetName Uses

func (f *DenseNumFeature) GetName() string

GetName returns the name of the feature.

func (*DenseNumFeature) GetStr Uses

func (f *DenseNumFeature) GetStr(i int) (value string)

Get str returns the string representing the value in the i'th position. It returns NA if tehe value is missing.

func (*DenseNumFeature) GoesLeft Uses

func (f *DenseNumFeature) GoesLeft(i int, splitter *Splitter) bool

GoesLeft checks if the i'th case goes left according to the supplied spliter.

func (*DenseNumFeature) Impurity Uses

func (target *DenseNumFeature) Impurity(cases *[]int, counter *[]int) (e float64)

Impurity returns Gini impurity or mean squared error vs the mean for a set of cases depending on weather the feature is categorical or numerical

func (*DenseNumFeature) ImputeMissing Uses

func (f *DenseNumFeature) ImputeMissing()

ImputeMissing imputes the missing values in a feature to the mean or mode of the feature.

func (*DenseNumFeature) IsMissing Uses

func (f *DenseNumFeature) IsMissing(i int) bool

IsMissing checks if the value for the i'th case is missing.

func (*DenseNumFeature) Length Uses

func (f *DenseNumFeature) Length() int

Length returns the length of the feature.

func (*DenseNumFeature) Less Uses

func (f *DenseNumFeature) Less(i int, j int) bool

Less checks if the value of case i is less then the value of j.

func (*DenseNumFeature) Mean Uses

func (target *DenseNumFeature) Mean(cases *[]int) (m float64)

Mean returns the mean of the feature for the cases specified

func (*DenseNumFeature) MissingVals Uses

func (f *DenseNumFeature) MissingVals() bool

MissingVals checks if the feature has any missing values.

func (*DenseNumFeature) Mode Uses

func (f *DenseNumFeature) Mode(cases *[]int) (m float64)

Mode returns the mode category feature for the cases specified

func (*DenseNumFeature) NCats Uses

func (f *DenseNumFeature) NCats() int

NCats returns the number of catagories, 0 for numerical values.

func (*DenseNumFeature) Norm Uses

func (f *DenseNumFeature) Norm(i int, v float64) float64

Norm defines the norm to use to tell how far the i'th case if from the value v

func (*DenseNumFeature) Predicted Uses

func (f *DenseNumFeature) Predicted(cases *[]int) float64

Predicted returns the prediction (the mean) that should be made for the supplied cases.

func (*DenseNumFeature) Put Uses

func (f *DenseNumFeature) Put(i int, v float64)

Put inserts the value v into the i'th position of the feature.

func (*DenseNumFeature) PutMissing Uses

func (f *DenseNumFeature) PutMissing(i int)

PutMissing set's the i'th value to be missing.

func (*DenseNumFeature) PutStr Uses

func (f *DenseNumFeature) PutStr(i int, v string)

PutStr parses a string and puts it in the i'th position

func (*DenseNumFeature) Shuffle Uses

func (f *DenseNumFeature) Shuffle()

Shuffle does an inplace shuffle of the specified feature

func (*DenseNumFeature) ShuffleCases Uses

func (f *DenseNumFeature) ShuffleCases(cases *[]int, allocs *BestSplitAllocs)

ShuffleCases does an inplace shuffle of the specified cases

func (*DenseNumFeature) ShuffledCopy Uses

func (f *DenseNumFeature) ShuffledCopy() Feature

ShuffledCopy returns a shuffled version of f for use as an artificial contrast in evaluation of importance scores. The new feature will be named featurename:SHUFFLED

func (*DenseNumFeature) Span Uses

func (f *DenseNumFeature) Span(cases *[]int, counter *[]int) (span float64)

Span returns the lengh along the real line spaned by the specified cases

func (*DenseNumFeature) Split Uses

func (f *DenseNumFeature) Split(codedSplit interface{}, cases []int) (l []int, r []int, m []int)

Split does an inplace slit from a coded split (a float64) and returns slices pointing into the origional cases slice.

func (*DenseNumFeature) SplitImpurity Uses

func (target *DenseNumFeature) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

SplitImpurity calculates the impurity of a split into the specified left and right groups. This is defined as pLi*(tL)+pR*i(tR) where pL and pR are the probability of case going left or right and i(tl) i(tR) are the left and right impurities.

Counter is only used for categorical targets and should have the same length as the number of categories in the target.

func (*DenseNumFeature) SplitPoints Uses

func (f *DenseNumFeature) SplitPoints(codedSplit interface{}, cs *[]int) (int, int)

SplitPoints returns the last left and first right index afeter reordering the cases slice froma float64 coded split.

func (*DenseNumFeature) SumAndSumSquares Uses

func (target *DenseNumFeature) SumAndSumSquares(cases *[]int) (sum float64, sum_sqr float64)

func (*DenseNumFeature) UpdateSImpFromAllocs Uses

func (target *DenseNumFeature) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type DensityTarget Uses

type DensityTarget struct {
    Features *[]Feature
    N        int
}

DensityTarget is used for density estimating trees. It contains a set of features and the count of cases.

func (*DensityTarget) FindPredicted Uses

func (target *DensityTarget) FindPredicted(cases []int) string

DensityTarget.FindPredicted returns the string representation of the density in the region spaned by the specified cases.

func (*DensityTarget) GetName Uses

func (target *DensityTarget) GetName() string

func (*DensityTarget) Impurity Uses

func (target *DensityTarget) Impurity(cases *[]int, counter *[]int) (e float64)

DensityTarget.Impurity uses the impurity measure defined in "Density Estimating Trees" by Parikshit Ram and Alexander G. Gray

func (*DensityTarget) NCats Uses

func (target *DensityTarget) NCats() int

func (*DensityTarget) SplitImpurity Uses

func (target *DensityTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

DensityTarget.SplitImpurity is a density estimating version of SplitImpurity.

func (*DensityTarget) UpdateSImpFromAllocs Uses

func (target *DensityTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type EntropyTarget Uses

type EntropyTarget struct {
    CatFeature
}

EntropyTarget wraps a categorical feature for use in entropy driven classification as in Ross Quinlan's ID3 (Iterative Dichotomizer 3).

func NewEntropyTarget Uses

func NewEntropyTarget(f CatFeature) *EntropyTarget

NewEntropyTarget creates a RefretTarget and initializes EntropyTarget.Costs to the proper length.

func (*EntropyTarget) ImpFromCounts Uses

func (target *EntropyTarget) ImpFromCounts(total int, counts *[]int) (e float64)

func (*EntropyTarget) Impurity Uses

func (target *EntropyTarget) Impurity(cases *[]int, counts *[]int) (e float64)

EntropyTarget.Impurity implements categorical entropy as sum(pj*log2(pj)) where pj is the number of cases with the j'th category over the total number of cases.

func (*EntropyTarget) SplitImpurity Uses

func (target *EntropyTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

EntropyTarget.SplitImpurity is a version of Split Impurity that calls EntropyTarget.Impurity

func (*EntropyTarget) UpdateSImpFromAllocs Uses

func (target *EntropyTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type Feature Uses

type Feature interface {
    Span(cases *[]int, counter *[]int) float64
    NCats() (n int)
    Length() (l int)
    GetStr(i int) (value string)
    IsMissing(i int) bool
    MissingVals() bool
    GoesLeft(i int, splitter *Splitter) bool
    PutMissing(i int)
    PutStr(i int, v string)
    SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)
    UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)
    Impurity(cases *[]int, counter *[]int) (impurity float64)
    FindPredicted(cases []int) (pred string)
    BestSplit(target Target,
        cases *[]int,
        parentImp float64,
        leafSize int,
        randomSplit bool,
        allocs *BestSplitAllocs) (codedSplit interface{}, impurityDecrease float64, constant bool)
    DecodeSplit(codedSplit interface{}) (s *Splitter)
    ShuffledCopy() (fake Feature)
    Copy() (copy Feature)
    CopyInTo(copy Feature)
    Shuffle()
    ShuffleCases(cases *[]int, allocs *BestSplitAllocs)
    ImputeMissing()
    GetName() string
    Append(v string)
    Split(codedSplit interface{}, cases []int) (l []int, r []int, m []int)
    SplitPoints(codedSplit interface{}, cases *[]int) (lastl int, firstr int)
}

Feature contains all methods needed for a predictor feature.

func ParseFeature Uses

func ParseFeature(record []string) Feature

ParseFeature parses a Feature from an array of strings and a capacity capacity is the number of cases and will usually be len(record)-1 but but doesn't need to be calculated for every row of a large file. The type of the feature us inferred from the start of the first (header) field in record: "N:"" indicating numerical, anything else (usually "C:" and "B:") for categorical

type FeatureMatrix Uses

type FeatureMatrix struct {
    Data       []Feature
    Map        map[string]int
    CaseLabels []string
}

FeatureMatrix contains a slice of Features and a Map to look of the index of a feature by its string id.

func LoadAFM Uses

func LoadAFM(filename string) (fm *FeatureMatrix, err error)

LoadAFM loads a, possible zipped, FeatureMatrix specified by filename

func ParseAFM Uses

func ParseAFM(input io.Reader) *FeatureMatrix

Parse an AFM (annotated feature matrix) out of an io.Reader AFM format is a tsv with row and column headers where the row headers start with N: indicating numerical, C: indicating categorical or B: indicating boolean For this parser features without N: are assumed to be categorical

func ParseARFF Uses

func ParseARFF(input io.Reader) *FeatureMatrix

ParseARFF reads a file in weka'sarff format: http://www.cs.waikato.ac.nz/ml/weka/arff.html The relation is ignored and only catagorical and numerical variables are supported

func ParseLibSVM Uses

func ParseLibSVM(input io.Reader) *FeatureMatrix

func (*FeatureMatrix) AddContrasts Uses

func (fm *FeatureMatrix) AddContrasts(n int)

AddContrasts appends n artificial contrast features to a feature matrix. These features are generated by randomly selecting (with replacement) an existing feature and creating a shuffled copy named featurename:SHUFFLED.

These features can be used as a contrast to evaluate the importance score's assigned to actual features.

func (*FeatureMatrix) BestSplitter Uses

func (fm *FeatureMatrix) BestSplitter(target Target,
    cases *[]int,
    candidates *[]int,
    mTry int,
    oob *[]int,
    leafSize int,
    force bool,
    vet bool,
    evaloob bool,
    extraRandom bool,
    allocs *BestSplitAllocs,
    nConstantsBefore int) (bestFi int, bestSplit interface{}, impurityDecrease float64, nConstants int)

BestSplitter finds the best splitter from a number of candidate features to slit on by looping over all features and calling BestSplit.

leafSize specifies the minimum leafSize that can be be produced by the split.

Vet specifies weather feature splits should be penalized with a randomized version of themselves.

allocs contains pointers to reusable structures for use while searching for the best split and should be initialized to the proper size with NewBestSplitAlocs.

func (*FeatureMatrix) ContrastAll Uses

func (fm *FeatureMatrix) ContrastAll()

ContrastAll adds shuffled copies of every feature to the feature matrix. These features are generated by randomly selecting (with replacement) an existing feature and creating a shuffled copy named featurename:SHUFFLED.

These features can be used as a contrast to evaluate the importance score's assigned to actual features. ContrastAll is particularly useful vs AddContrast when one wishes to identify [pseudo] unique identifiers that might lead to over fitting.

func (*FeatureMatrix) EncodeToNum Uses

func (fm *FeatureMatrix) EncodeToNum() *FeatureMatrix

func (*FeatureMatrix) ImputeMissing Uses

func (fm *FeatureMatrix) ImputeMissing()

ImputeMissing imputes missing values in all features to the mean or mode of the feature.

func (*FeatureMatrix) LoadCases Uses

func (fm *FeatureMatrix) LoadCases(data *csv.Reader, rowlabels bool)

LoadCases will load data stored case by case from a cvs reader into a feature matrix that has allready been filled with the coresponding empty features. It is a lower level method generally called after inital setup to parse a fm, arff, csv etc.

func (*FeatureMatrix) OneHot Uses

func (fm *FeatureMatrix) OneHot() *FeatureMatrix

func (*FeatureMatrix) StripStrings Uses

func (fm *FeatureMatrix) StripStrings(target string)

func (*FeatureMatrix) WriteCases Uses

func (fm *FeatureMatrix) WriteCases(w io.Writer, cases []int) (err error)

WriteCases writes a new feature matrix with the specified cases to the the provided writer.

type Forest Uses

type Forest struct {
    //Forest string
    Target    string
    Trees     []*Tree
    Intercept float64
}

Forest represents a collection of decision trees grown to predict Target.

func GrowRandomForest Uses

func GrowRandomForest(fm *FeatureMatrix,
    target Target,
    candidates []int,
    nSamples int,
    mTry int,
    nTrees int,
    leafSize int,
    maxDepth int,
    splitmissing bool,
    force bool,
    vet bool,
    evaloob bool,
    importance *[]*RunningMean) (f *Forest)

type ForestReader Uses

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

ForestReader wraps an io.Reader to reads a forest. It includes ReadForest for reading an entire forest or ReadTree for reading a forest tree by tree. The forest should be in .sf format see the package doc's in doc.go for full format details. It ignores fields that are not use by CloudForest.

func NewForestReader Uses

func NewForestReader(r io.Reader) *ForestReader

NewForestReader wraps the supplied io.Reader as a ForestReader.

func (*ForestReader) ParseRfAcePredictorLine Uses

func (fr *ForestReader) ParseRfAcePredictorLine(line string) map[string]string

ParseRfAcePredictorLine parses a single line of an rf-ace sf "stochastic forest" and returns a map[string]string of the key value pairs.

func (*ForestReader) ReadForest Uses

func (fr *ForestReader) ReadForest() (forest *Forest, err error)

ForestReader.ReadForest reads the next forest from the underlying reader. If io.EOF or another error is encountered it returns that.

func (*ForestReader) ReadTree Uses

func (fr *ForestReader) ReadTree() (tree *Tree, forest *Forest, err error)

ForestReader.ReadTree reads the next tree from the underlying reader. If the next tree is in a new forest it returns a forest object as well. If an io.EOF or other error is encountered it returns that as well as any partially parsed structs.

type ForestWriter Uses

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

ForestWriter wraps an io writer with functionality to write forests either with one call to WriteForest or incrementally using WriteForestHeader and WriteTree. ForestWriter saves a forest in .sf format; see the package doc's in doc.go for full format details. It won't include fields that are not use by CloudForest.

func NewForestWriter Uses

func NewForestWriter(w io.Writer) *ForestWriter

NewForestWriter returns a pointer to a new ForestWriter.

func (*ForestWriter) DescribeMap Uses

func (fw *ForestWriter) DescribeMap(input map[string]bool) string

DescribeMap serializes the "left" map of a categorical splitter.

func (*ForestWriter) WriteForest Uses

func (fw *ForestWriter) WriteForest(forest *Forest)

WriteForest writes an entire forest including all headers.

func (*ForestWriter) WriteForestHeader Uses

func (fw *ForestWriter) WriteForestHeader(nforest int, target string, intercept float64)

WrieTreeHeader writes only the header line for a tree.

func (*ForestWriter) WriteNode Uses

func (fw *ForestWriter) WriteNode(n *Node, path string)

WriteNode writes a single node but not it's children. WriteTree will be used more often but WriteNode can be used to grow a large tree directly to disk without storing it in memory.

func (*ForestWriter) WriteNodeAndChildren Uses

func (fw *ForestWriter) WriteNodeAndChildren(n *Node, path string)

WriteNodeAndChildren recursively writes out the target node and all of its children. WriteTree is preferred for most use cases.

func (*ForestWriter) WriteTree Uses

func (fw *ForestWriter) WriteTree(tree *Tree, ntree int)

WriteTree writes an entire Tree including the header.

func (*ForestWriter) WriteTreeHeader Uses

func (fw *ForestWriter) WriteTreeHeader(ntree int, target string, weight float64)

WrieTreeHeader writes only the header line for a tree.

type GradBoostClassTarget Uses

type GradBoostClassTarget struct {
    *GradBoostTarget
    Actual    NumFeature
    Pred      NumFeature
    LearnRate float64
    Prior     float64
    Pos_class string
}

GradBoostClassTarget wraps a numerical feature as a target for us in Two Class Gradiant Boosting Trees.

It should be used with SumBallotBox and expit transformed to get class probabilities.

func NewGradBoostClassTarget Uses

func NewGradBoostClassTarget(f CatFeature, learnrate float64, pos_class string) (gbc *GradBoostClassTarget)

func (*GradBoostClassTarget) Boost Uses

func (f *GradBoostClassTarget) Boost(leaves *[][]int, preds *[]string) (weight float64)

BUG(ryan) does GradBoostingTarget need seperate residuals and values?

func (*GradBoostClassTarget) FindPredicted Uses

func (f *GradBoostClassTarget) FindPredicted(cases []int) (pred string)

func (*GradBoostClassTarget) Intercept Uses

func (f *GradBoostClassTarget) Intercept() float64

func (*GradBoostClassTarget) Predicted Uses

func (f *GradBoostClassTarget) Predicted(cases *[]int) float64

func (*GradBoostClassTarget) Update Uses

func (f *GradBoostClassTarget) Update(cases *[]int, predicted float64)

Update updates the underlying numeric data by subtracting the mean*weight of the specified cases from the value for those cases.

type GradBoostTarget Uses

type GradBoostTarget struct {
    NumFeature
    LearnRate float64
    Mean      float64
}

GradBoostTarget wraps a numerical feature as a target for us in Gradiant Boosting Trees.

It should be used with the SumBallotBox.

func NewGradBoostTarget Uses

func NewGradBoostTarget(f NumFeature, learnrate float64) (gbc *GradBoostTarget)

func (*GradBoostTarget) Boost Uses

func (f *GradBoostTarget) Boost(leaves *[][]int, preds *[]string) (weight float64)

BUG(ryan) does GradBoostingTarget need seperate residuals and values?

func (*GradBoostTarget) Impurity Uses

func (target *GradBoostTarget) Impurity(cases *[]int, counter *[]int) (e float64)

Impurity returns Gini impurity or mean squared error vs the mean for a set of cases depending on weather the feature is categorical or numerical

func (*GradBoostTarget) Intercept Uses

func (f *GradBoostTarget) Intercept() float64

func (*GradBoostTarget) SplitImpurity Uses

func (target *GradBoostTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

Friedman MSE slit improvment score from from equation 35 in "Greedy Function Approximation: A Gradiet Boosting Machine" Todo...what should the parent impurity be

func (*GradBoostTarget) Sum Uses

func (target *GradBoostTarget) Sum(cases *[]int) (sum float64)

func (*GradBoostTarget) Update Uses

func (f *GradBoostTarget) Update(cases *[]int, predicted float64)

Update updates the underlying numeric data by subtracting the mean*weight of the specified cases from the value for those cases.

func (*GradBoostTarget) UpdateSImpFromAllocs Uses

func (target *GradBoostTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

type HDistanceTarget Uses

type HDistanceTarget struct {
    CatFeature
    Pos_class string
}

HDistanceTarget wraps a categorical feature for use in Hellinger Distance tree growth.

func NewHDistanceTarget Uses

func NewHDistanceTarget(f CatFeature, pos_class string) *HDistanceTarget

NewHDistanceTarget creates a RefretTarget and initializes HDistanceTarget.Costs to the proper length.

func (*HDistanceTarget) FindPredicted Uses

func (target *HDistanceTarget) FindPredicted(cases []int) (pred string)

func (*HDistanceTarget) HDist Uses

func (target *HDistanceTarget) HDist(lcounts *[]int, rcounts *[]int) (d float64)

func (*HDistanceTarget) Impurity Uses

func (target *HDistanceTarget) Impurity(cases *[]int, counts *[]int) (e float64)

HDistanceTarget.Impurity

func (*HDistanceTarget) SplitImpurity Uses

func (target *HDistanceTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) float64

HDistanceTarget.SplitImpurity is a version of Split Impurity that calls HDistanceTarget.Impurity

func (*HDistanceTarget) UpdateSImpFromAllocs Uses

func (target *HDistanceTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) float64

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type L1Target Uses

type L1Target struct {
    NumFeature
}

L1Target wraps a numerical feature as a target for us in l1 norm regression.

func (*L1Target) Error Uses

func (target *L1Target) Error(cases *[]int, predicted float64) (e float64)

L1Target.MeanL1Error returns the Mean L1 norm error of the cases specified vs the predicted value. Only non missing cases are considered.

func (*L1Target) Impurity Uses

func (target *L1Target) Impurity(cases *[]int, counter *[]int) (e float64)

L1Target.Impurity is an L1 version of impurity returning L1 instead of squared error.

func (*L1Target) SplitImpurity Uses

func (target *L1Target) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

L1Target.SplitImpurity is an L1 version of SplitImpurity.

func (*L1Target) UpdateSImpFromAllocs Uses

func (target *L1Target) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type Leaf Uses

type Leaf struct {
    Cases []int
    Pred  string
}

Leaf is a struct for storing the index of the cases at a terminal "Leaf" node along with the Numeric predicted value.

type NPTarget Uses

type NPTarget struct {
    CatFeature
    Posi  int
    Alpha float64
    Kappa float64
}

NPTarget wraps a categorical feature for use in experimental approximate Neyman-Pearson (NP) classification...constraints and optimization are done on percision false positive/negative rate.

It uses an impurity measure with a soft constraint from the seccond family presented in

"Comparison and Design of Neyman-Pearson Classifiers" Clayton Scott, October 2005

http://www.stat.rice.edu/~cscott/pubs/npdesign.pdf

N(f) = κ max((R0(f) − α), 0) + R1(f)

Where f is the classifer, R0 is the flase positive rate R1 is the false negative rate, α is the false positive constraint and k controls the cost of violating this constraint and β is a constant we can ignore as it subtracts out in diffrences.

The vote assigned to each leaf node is a corrected mode where the count of the positive/constrained label is corrected by 1/α. Without this modification constraints > .5 won't work since nodes with that many negatives false positives won't vote positive.

func NewNPTarget Uses

func NewNPTarget(f CatFeature, Pos string, Alpha, Kappa float64) *NPTarget

NewNPTarget wraps a Categorical Feature for NP Classification. It accepts a string representing the contstrained label and floats Alpha and Kappa representing the constraint and constraint weight.

func (*NPTarget) FindPredicted Uses

func (target *NPTarget) FindPredicted(cases []int) (pred string)

FindPredicted does a mode calulation with the count of the positive/constrained class corrected.

func (*NPTarget) ImpFromCounts Uses

func (target *NPTarget) ImpFromCounts(t int, counter *[]int) (e float64)

ImpFromCounts recalculates gini impurity from class counts for us in intertive updates.

func (*NPTarget) Impurity Uses

func (target *NPTarget) Impurity(cases *[]int, counter *[]int) (e float64)

NPTarget.Impurity implements an impurity that minimizes false negatives subject to a soft constrain on fale positives.

func (*NPTarget) SplitImpurity Uses

func (target *NPTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

SplitImpurity is a version of Split Impurity that calls NPTarget.Impurity

func (*NPTarget) UpdateSImpFromAllocs Uses

func (target *NPTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l to avoid recalulatign the entire split impurity.

type Node Uses

type Node struct {
    CodedSplit interface{}
    Featurei   int
    Left       *Node
    Right      *Node
    Missing    *Node
    Pred       string
    Splitter   *Splitter
}

A node of a decision tree. Pred is a string containing either the category or a representation of a float (less then ideal)

func (*Node) Climb Uses

func (n *Node) Climb(c func(*Node))

vist each child node with the supplied function

func (*Node) CodedRecurse Uses

func (n *Node) CodedRecurse(r CodedRecursable, fm *FeatureMatrix, cases *[]int, depth int, nconstantsbefore int)

func (*Node) Recurse Uses

func (n *Node) Recurse(r Recursable, fm *FeatureMatrix, cases []int, depth int)

Recurse is used to apply a Recursable function at every downstream node as the cases specified by case []int are split using the data in fm *Featurematrix. Recursion down a branch stops when a a node with n.Splitter == nil is reached. Recursion down the Missing branch is only used if n.Missing!=nil. For example votes can be tabulated using code like:

t.Root.Recurse(func(n *Node, cases []int) {
	if n.Left == nil && n.Right == nil {
		// I'm in a leaf node
		for i := 0; i < len(cases); i++ {
			bb.Vote(cases[i], n.Pred)
		}
	}
}, fm, cases)

type NumAdaBoostTarget Uses

type NumAdaBoostTarget struct {
    NumFeature
    Weights    []float64
    NormFactor float64
}

NumNumAdaBoostTarget wraps a numerical feature as a target for us in (Experimental) Adaptive Boosting Regression.

func NewNumAdaBoostTarget Uses

func NewNumAdaBoostTarget(f NumFeature) (abt *NumAdaBoostTarget)

func (*NumAdaBoostTarget) Boost Uses

func (t *NumAdaBoostTarget) Boost(leaves *[][]int) (weight float64)

AdaBoostTarget.Boost performs numerical adaptive boosting using the specified partition and returns the weight that tree that generated the partition should be given. Trees with error greater then the impurity of the total feature (NormFactor) times the number of partions are given zero weight. Other trees have tree weight set to:

weight = math.Log(1 / norm)

and weights updated to:

t.Weights[c] = t.Weights[c] * math.Exp(t.Error(&[]int{c}, m)*weight)

These functions are chosen to provide a rough analog to catagorical adaptive boosting for numerical data with unbounded error.

func (*NumAdaBoostTarget) Impurity Uses

func (target *NumAdaBoostTarget) Impurity(cases *[]int, counter *[]int) (e float64)

NumAdaBoostTarget.Impurity is an AdaBoosting that uses the weights specified in NumAdaBoostTarget.weights.

func (*NumAdaBoostTarget) SplitImpurity Uses

func (target *NumAdaBoostTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

NumAdaBoostTarget.SplitImpurity is an AdaBoosting version of SplitImpurity.

func (*NumAdaBoostTarget) UpdateSImpFromAllocs Uses

func (target *NumAdaBoostTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type NumBallotBox Uses

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

Keeps track of votes by trees. Voteing is thread safe.

func NewNumBallotBox Uses

func NewNumBallotBox(size int) *NumBallotBox

Build a new ballot box for the number of cases specified by "size".

func (*NumBallotBox) Tally Uses

func (bb *NumBallotBox) Tally(i int) (predicted string)

func (*NumBallotBox) TallyError Uses

func (bb *NumBallotBox) TallyError(feature Feature) (e float64)

TallyScore returns the squared error (unexplained variance) divided by the data variance.

func (*NumBallotBox) TallyNum Uses

func (bb *NumBallotBox) TallyNum(i int) (predicted float64)

TallyNumerical tallies the votes for the case specified by i as if it is a Numerical feature. Ie it returns the mean of all votes.

func (*NumBallotBox) TallyR2Score Uses

func (bb *NumBallotBox) TallyR2Score(feature Feature) (e float64)

Tally score returns the R2 score or coefichent of determination.

func (*NumBallotBox) TallySquaredError Uses

func (bb *NumBallotBox) TallySquaredError(feature Feature) (e float64)

TallySquareError returns the error of the votes vs the provided feature. For categorical features it returns the error rate For numerical features it returns mean squared error. The provided feature must use the same index as the feature matrix the ballot box was constructed with. Missing values are ignored. Gini impurity is not used so this is not for use in rf implementations.

func (*NumBallotBox) Vote Uses

func (bb *NumBallotBox) Vote(casei int, pred string, weight float64)

Vote parses the float in the string and votes for it

type NumFeature Uses

type NumFeature interface {
    Feature
    Get(i int) float64
    Put(i int, v float64)
    Predicted(cases *[]int) float64
    Mean(cases *[]int) float64
    Norm(i int, v float64) float64
    Error(cases *[]int, predicted float64) (e float64)
    Less(i int, j int) bool
    SumAndSumSquares(cases *[]int) (float64, float64)
}

NumFeature contains the methods of Feature plus methods needed to implement diffrent types of regression. It is usually embeded by regression targets to provide access to the underlying data.

type OrdinalTarget Uses

type OrdinalTarget struct {
    NumFeature
    // contains filtered or unexported fields
}

OrdinalTarget wraps a numerical feature as a target for us in ordinal regression. Data should be represented as positive integers and the Error is embeded from the embeded NumFeature.

func NewOrdinalTarget Uses

func NewOrdinalTarget(f NumFeature) (abt *OrdinalTarget)

NewOrdinalTarget creates a categorical adaptive boosting target and initializes its weights.

func (*OrdinalTarget) FindPredicted Uses

func (target *OrdinalTarget) FindPredicted(cases []int) (pred string)

func (*OrdinalTarget) Impurity Uses

func (target *OrdinalTarget) Impurity(cases *[]int, counter *[]int) (e float64)

OrdinalTarget.Impurity is an ordinal version of impurity using Mode instead of Mean for prediction.

func (*OrdinalTarget) Mode Uses

func (f *OrdinalTarget) Mode(cases *[]int) (m float64)

func (*OrdinalTarget) Predicted Uses

func (f *OrdinalTarget) Predicted(cases *[]int) float64

func (*OrdinalTarget) SplitImpurity Uses

func (target *OrdinalTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

OrdinalTarget.SplitImpurity is an ordinal version of SplitImpurity.

func (*OrdinalTarget) UpdateSImpFromAllocs Uses

func (target *OrdinalTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type Recursable Uses

type Recursable func(*Node, []int, int)

Recursable defines a function signature for functions that can be called at every down stream node of a tree as Node.Recurse recurses up the tree. The function should have two parameters, the current node and an array of ints specifying the cases that have not been split away.

type RegretTarget Uses

type RegretTarget struct {
    CatFeature
    Costs []float64
}

RegretTarget wraps a categorical feature for use in regret driven classification. The ith entry in costs should contain the cost of misclassifying a case that actually has the ith category.

It is roughly equivelent to the ideas presented in:

http://machinelearning.wustl.edu/mlpapers/paper_files/icml2004_LingYWZ04.pdf

"Decision Trees with Minimal Costs" Charles X. Ling,Qiang Yang,Jianning Wang,Shichao Zhang

func NewRegretTarget Uses

func NewRegretTarget(f CatFeature) *RegretTarget

NewRegretTarget creates a RefretTarget and initializes RegretTarget.Costs to the proper length.

func (*RegretTarget) FindPredicted Uses

func (target *RegretTarget) FindPredicted(cases []int) (pred string)

FindPredicted does a mode calulation with the count of the positive/constrained class corrected.

func (*RegretTarget) ImpFromCounts Uses

func (target *RegretTarget) ImpFromCounts(t int, counter *[]int) (e float64)

ImpFromCounts recalculates gini impurity from class counts for us in intertive updates.

func (*RegretTarget) Impurity Uses

func (target *RegretTarget) Impurity(cases *[]int, counter *[]int) (e float64)

Impurity implements an impurity based on misslassification costs.

func (*RegretTarget) SetCosts Uses

func (target *RegretTarget) SetCosts(costmap map[string]float64)

RegretTarget.SetCosts puts costs in a map[string]float64 by feature name into the proper entries in RegretTarget.Costs.

func (*RegretTarget) SplitImpurity Uses

func (target *RegretTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

RegretTarget.SplitImpurity is a version of Split Impurity that calls RegretTarget.Impurity

func (*RegretTarget) UpdateSImpFromAllocs Uses

func (target *RegretTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l to avoid recalulatign the entire split impurity.

type RunningMean Uses

type RunningMean struct {
    Mean  float64
    Count float64
    // contains filtered or unexported fields
}

RunningMean is a thread safe strut for keeping track of running means as used in importance calculations. (TODO: could this be made lock free?)

func (*RunningMean) Add Uses

func (rm *RunningMean) Add(val float64)

Add add's 1.0 to the running mean in a thread safe way.

func (*RunningMean) Read Uses

func (rm *RunningMean) Read() (mean float64, count float64)

Read reads the mean and count

func (*RunningMean) WeightedAdd Uses

func (rm *RunningMean) WeightedAdd(val float64, weight float64)

WeightedAdd add's the specified value to the running mean in a thread safe way.

type ScikitNode Uses

type ScikitNode struct {
    LeftChild            int     `json:"left_child"`
    RightChild           int     `json:"right_child"`
    Feature              int     `json:"feature"`
    Threshold            float64 `json:"threshold"`
    Impurity             float64 `json:"impurity"`                //TODO(ryan): support this?
    NNodeSamples         int     `json:"n_node_samples"`          //TODO(ryan): support this?
    WeightedNNodeSamples float64 `json:"weighted_n_node_samples"` //TODO(ryan): support this?
}

type ScikitTree Uses

type ScikitTree struct {
    NFeatures   int           `json:"n_features"`
    NClasses    []int         `json:"n_classes"`
    NOutputs    int           `json:"n_outputs"`     //TODO(ryan): support other values
    MaxNClasses int           `json:"max_n_classes"` //TODO(ryan): support other values
    MaxDepth    int           `json:"max_depth"`
    NodeCount   int           `json:"node_count"`
    Capacity    int           `json:"capacity"`
    Nodes       []ScikitNode  `json:"nodes"`
    Value       [][][]float64 `json:"value"` //TODO(ryan): support actual values
    ValueStride int           `json:"value_stride"`
}

# Inner structures: values are stored separately from node structure, # since size is determined at runtime. cdef public SIZE_t max_depth # Max depth of the tree cdef public SIZE_t node_count # Counter for node IDs cdef public SIZE_t capacity # Capacity of tree, in terms of nodes cdef Node* nodes # Array of nodes cdef double* value # (capacity, n_outputs, max_n_classes) array of values cdef SIZE_t value_stride # = n_outputs * max_n_classes

func NewScikitTree Uses

func NewScikitTree(nFeatures int) *ScikitTree

type SecondaryBalancedSampler Uses

type SecondaryBalancedSampler struct {
    Total    int
    Counts   []int
    Samplers [][][]int
}

SecondaryBalancedSampler roughly balances the target feature within the classes of another catagorical feature while roughly preserving the origional rate of the secondary feature.

func NewSecondaryBalancedSampler Uses

func NewSecondaryBalancedSampler(target *DenseCatFeature, balanceby *DenseCatFeature) (s *SecondaryBalancedSampler)

NewSecondaryBalancedSampler returns an initalized balanced sampler.

func (*SecondaryBalancedSampler) Sample Uses

func (s *SecondaryBalancedSampler) Sample(samples *[]int, n int)

type SortableFeature Uses

type SortableFeature struct {
    //Feature NumFeature
    Vals  []float64
    Cases []int
}

SortableFeature is a wrapper for a feature and set of cases that satisfies the sort.Interface interface so that the case indexes in Cases can be sorted using sort.Sort

func (*SortableFeature) Len Uses

func (sf *SortableFeature) Len() int

Len returns the number of cases.

func (*SortableFeature) Less Uses

func (sf *SortableFeature) Less(i int, j int) bool

Less determines if the ith case is less then the jth case.

func (*SortableFeature) Load Uses

func (sf *SortableFeature) Load(vals *[]float64, cases *[]int)

Load loads the values of the cases into a cache friendly array.

func (*SortableFeature) Sort Uses

func (sf *SortableFeature) Sort()

Sort performs introsort + heapsort using the sortby sub package.

func (*SortableFeature) Swap Uses

func (sf *SortableFeature) Swap(i int, j int)

Swap exchanges the ith and jth cases.

type SparseCounter Uses

type SparseCounter struct {
    Map map[int]map[int]int
    // contains filtered or unexported fields
}

SparseCounter uses maps to track sparse integer counts in large matrix. The matrix is assumed to contain zero values where nothing has been added.

func (*SparseCounter) Add Uses

func (sc *SparseCounter) Add(i int, j int, val int)

Add increases the count in i,j by val.

func (*SparseCounter) WriteTsv Uses

func (sc *SparseCounter) WriteTsv(writer io.Writer)

WriteTsv writes the non zero counts out into a three column tsv containing i, j, and count in the columns.

type Splitter Uses

type Splitter struct {
    Feature   string
    Numerical bool
    Value     float64
    Left      map[string]bool
}

Splitter contains fields that can be used to cases by a single feature. The split can be either numerical in which case it is defined by the Value field or categorical in which case it is defined by the Left and Right fields.

func (*Splitter) Split Uses

func (s *Splitter) Split(fm *FeatureMatrix, cases []int) (l []int, r []int, m []int)

Split splits a slice of cases into left, right and missing slices without allocating a new underlying array by sorting cases into left, missing, right order and returning slices that point to the left and right cases.

type SumBallot Uses

type SumBallot struct {
    Mutex sync.Mutex
    Sum   float64
}

SumBallot is used insideof SumBallotBox to record sum votes in a thread safe manner.

func NewSumBallot Uses

func NewSumBallot() (cb *SumBallot)

NewSumBallot returns a pointer to an initalized SumBallot with a 0 size Map.

type SumBallotBox Uses

type SumBallotBox struct {
    Box []*SumBallot
}

SumBallotBox keeps track of votes by trees in a thread safe manner. It should be used with gradient boosting when a sum instead of an average or mode is desired.

func NewSumBallotBox Uses

func NewSumBallotBox(size int) *SumBallotBox

NewSumBallotBox builds a new ballot box for the number of cases specified by "size".

func (*SumBallotBox) Tally Uses

func (bb *SumBallotBox) Tally(i int) (predicted string)

Tally tallies the votes for the case specified by i as if it is a Categorical or boolean feature. Ie it returns the sum of all votes.

func (*SumBallotBox) TallyError Uses

func (bb *SumBallotBox) TallyError(feature Feature) (e float64)

TallyError is non functional here.

func (*SumBallotBox) TallyNum Uses

func (bb *SumBallotBox) TallyNum(i int) (predicted float64)

func (*SumBallotBox) Vote Uses

func (bb *SumBallotBox) Vote(casei int, pred string, weight float64)

Vote registers a vote that case "casei" should have pred added to its sum.

type Target Uses

type Target interface {
    GetName() string
    NCats() (n int)
    SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)
    UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)
    Impurity(cases *[]int, counter *[]int) (impurity float64)
    FindPredicted(cases []int) (pred string)
}

Target abstracts the methods needed for a feature to be predictable as either a catagroical or numerical feature in a random forest.

type TargetWithIntercept Uses

type TargetWithIntercept interface {
    Target
    Intercept() float64
}

type TransTarget Uses

type TransTarget struct {
    CatFeature
    Features  *[]Feature
    Unlabeled int
    Alpha     float64
    Beta      float64
    N         int
    MaxCats   int
}

TransTarget is used for semi supervised transduction trees [1] that balance compine supervised impurity with a purelly density based term.

I = I_supervised + alpha * I_unsupervised

I_supervised is called from the embeded CatFeature so that it can be Gini, Entropy, Weighted or any other of the existing non-boosting impurities. Boosting impurities could be implemented with minimal work.

I_unsupervised uses a density estimating term that differs from the one described in [1] and is instead based on the technique described in [2] which avoids some assumptions and allows a simple implementation.

[1] A. Criminisi, J. Shotton, and E. Konukoglu, "Decision Forests for Classification, Regression, Density Estimation, Manifold Learning and Semi-Supervised Learning" Microsoft Research technical report TR-2011-114

[2] Parikshit Ram, Alexander G. Gray, Density Estimation Trees http://research.microsoft.com/pubs/155552/decisionForests_MSR_TR_2011_114.pdf

One diffrence from [1] is that the unlabelled class is considered a standard class for I_supervised to allow once class problems.

func NewTransTarget Uses

func NewTransTarget(t CatFeature, fm *[]Feature, unlabeled string, alpha, beta float64, ncases int) *TransTarget

NewTransTarget returns a TransTarget using the supervised Impurity from the provided CatFeature t, Density in the specified Features fm (excluding any with the same name as t), considering the class label provided in "unlabeled" as unlabeled for transduction. Alpha is the weight of the unspervised term relative to the supervised and ncases is the number of cases that will be called at the root of the tree (may be depreciated as not needed).

func (*TransTarget) Density Uses

func (target *TransTarget) Density(cases *[]int, counter *[]int) (e float64)

TransTarget.Density uses an impurity designed to maximize the density within each side of the split based on the method in "Density Estimating Trees" by Parikshit Ram and Alexander G. Gray. It loops over all of the non target features and for the ones with non zero span calculates product(span_i)/(t*t) where t is the number of cases.

Refinements to this method might include t*t->t^n where n is the number of features with non zero span or other changes to how zero span features are handeled. I also suspect that this method handles numerical features for which diffrent splits will have diffrent total spans based on the distance between the points on either side of the split point better then categorical features for which the total span of a split will allways be the number of categories.

The origional paper also included N which is not used here.

func (*TransTarget) FindPredicted Uses

func (target *TransTarget) FindPredicted(cases []int) string

TransTarget.FindPredicted returns the prediction of the specified cases which is the majority class that is not the unlabeled class. A set of cases will only be predicted to be the ulabeled class if has no labeled points.

func (*TransTarget) Impurity Uses

func (target *TransTarget) Impurity(cases *[]int, counter *[]int) (e float64)

func (*TransTarget) SplitImpurity Uses

func (target *TransTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

TransTarget.SplitImpurity is a density estimating version of SplitImpurity.

func (*TransTarget) UpdateSImpFromAllocs Uses

func (target *TransTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l as in learning from numerical variables. Here it just wraps SplitImpurity but it can be implemented to provide further optimization.

type Tree Uses

type Tree struct {
    //Tree int
    Root   *Node
    Target string
    Weight float64
}

Tree represents a single decision tree.

func NewTree Uses

func NewTree() *Tree

NewTree initializes one node tree.

func (*Tree) AddNode Uses

func (t *Tree) AddNode(path string, pred string, splitter *Splitter)

AddNode adds a node a the specified path with the specified pred value and/or Splitter. Paths are specified in the same format as in rf-aces sf files, as a string of 'L' and 'R'. Nodes must be added from the root up as the case where the path specifies a node whose parent does not already exist in the tree is not handled well.

func (*Tree) GetLeaves Uses

func (t *Tree) GetLeaves(fm *FeatureMatrix, fbycase *SparseCounter) []Leaf

GetLeaves is called by the leaf count utility to gather statistics about the nodes of a tree including the sets of cases at "leaf" nodes that aren't split further and the number of times each feature is used to split away each case.

func (*Tree) Grow Uses

func (t *Tree) Grow(fm *FeatureMatrix,
    target Target,
    cases []int,
    candidates []int,
    oob []int,
    mTry int,
    leafSize int,
    maxDepth int,
    splitmissing bool,
    force bool,
    vet bool,
    evaloob bool,
    extraRandom bool,
    importance *[]*RunningMean,
    depthUsed *[]int,
    allocs *BestSplitAllocs)

Grow grows the receiver tree through recursion. It uses impurity decrease to select splitters at each node as in Brieman's Random Forest. It should be called on a tree with only a root node defined.

fm is a feature matrix of training data.

target is the feature to predict via regression or classification as determined by feature type.

cases specifies the cases to calculate impurity decrease over and can contain repeated values to allow for sampling of cases with replacement as in RF.

canidates specifies the potential features to use as splitters

mTry specifies the number of candidate features to evaluate for each split.

leafSize specifies the minimum number of cases at a leafNode.

splitmissing indicates if missing values should be split onto a third branch

vet indicates if splits should be penalized against a randomized version of them selves

func (*Tree) GrowJungle Uses

func (t *Tree) GrowJungle(fm *FeatureMatrix,
    target Target,
    cases []int,
    candidates []int,
    oob []int,
    mTry int,
    leafSize int,
    maxDepth int,
    splitmissing bool,
    force bool,
    vet bool,
    evaloob bool,
    extraRandom bool,
    importance *[]*RunningMean,
    depthUsed *[]int,
    allocs *BestSplitAllocs)

func (*Tree) Partition Uses

func (t *Tree) Partition(fm *FeatureMatrix) (*[][]int, *[]string)

Partition partitions all of the cases in a FeatureMatrix.

func (*Tree) StripCodes Uses

func (t *Tree) StripCodes()

StripCodes removes all of the coded splits from a tree so that it can be used on new catagorical data.

func (*Tree) Vote Uses

func (t *Tree) Vote(fm *FeatureMatrix, bb VoteTallyer)

Vote casts a vote for the predicted value of each case in fm *FeatureMatrix. into bb *BallotBox. Since BallotBox is not thread safe trees should not vote into the same BallotBox in parallel.

func (*Tree) VoteCases Uses

func (t *Tree) VoteCases(fm *FeatureMatrix, bb VoteTallyer, cases []int)

VoteCases casts a vote for the predicted value of each case in fm *FeatureMatrix. into bb *BallotBox. Since BallotBox is not thread safe trees should not vote into the same BallotBox in parallel.

type VoteTallyer Uses

type VoteTallyer interface {
    Vote(casei int, pred string, weight float64)
    TallyError(feature Feature) float64
    Tally(casei int) string
}

VoteTallyer is used to tabulate votes by trees and is implemented by feature type specific structs like NumBallotBox and CatBallotBox. Vote should register a cote that casei should be predicted as pred. TallyError returns the error vs the supplied feature.

type WRFTarget Uses

type WRFTarget struct {
    CatFeature
    Weights []float64
}

WRFTarget wraps a numerical feature as a target for us weigted random forest.

func NewWRFTarget Uses

func NewWRFTarget(f CatFeature, weights map[string]float64) (abt *WRFTarget)

NewWRFTarget creates a weighted random forest target and initializes its weights.

func (*WRFTarget) FindPredicted Uses

func (target *WRFTarget) FindPredicted(cases []int) (pred string)

FindPredicted finds the predicted target as the weighted catagorical Mode.

func (*WRFTarget) ImpFromCounts Uses

func (target *WRFTarget) ImpFromCounts(counter *[]int) (e float64)

ImpFromCounts recalculates gini impurity from class counts for us in intertive updates.

func (*WRFTarget) Impurity Uses

func (target *WRFTarget) Impurity(cases *[]int, counter *[]int) (e float64)

Impurity is Gini impurity that uses the weights specified in WRFTarget.weights.

func (*WRFTarget) SplitImpurity Uses

func (target *WRFTarget) SplitImpurity(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs) (impurityDecrease float64)

SplitImpurity is an weigtedRF version of SplitImpurity.

func (*WRFTarget) UpdateSImpFromAllocs Uses

func (target *WRFTarget) UpdateSImpFromAllocs(l *[]int, r *[]int, m *[]int, allocs *BestSplitAllocs, movedRtoL *[]int) (impurityDecrease float64)

UpdateSImpFromAllocs willl be called when splits are being built by moving cases from r to l to avoid recalulatign the entire split impurity.

Bugs

does GradBoostingTarget need seperate residuals and values?

does GradBoostingTarget need seperate residuals and values?

Directories

PathSynopsis
applyforest
growforest
leafcount
sortbyPackage sortby is a hybrid, non stable sort based on go's standard sort but with all less function and many swaps inlined to sort a list of ints by an acompanying list of floats as needed in random forest training.
statsPackage stats currentelly only implements a welch's t-test for importance score analysis in CloudForest.

Package CloudForest imports 15 packages (graph) and is imported by 10 packages. Updated 2016-12-02. Refresh now. Tools for package owners.