gov.sandia.cognition.learning.algorithm.tree

Class VectorThresholdHellingerDistanceLearner<OutputType>

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.learning.algorithm.tree.AbstractVectorThresholdMaximumGainLearner<OutputType>

gov.sandia.cognition.learning.algorithm.tree.VectorThresholdHellingerDistanceLearner<OutputType>

Type Parameters:

OutputType - The output category type for the training data.

All Implemented Interfaces:

BatchLearner<java.util.Collection<? extends InputOutputPair<? extends Vectorizable,OutputType>>,VectorElementThresholdCategorizer>, DimensionFilterableLearner, DeciderLearner<Vectorizable,OutputType,java.lang.Boolean,VectorElementThresholdCategorizer>, VectorThresholdLearner<OutputType>, CloneableSerializable, java.io.Serializable, java.lang.Cloneable

@PublicationReference(author={"David A. Cieslak","Nitesh V. Chawla"},
                      title="Increasing Skew Insensitivity of Decision Trees with Hellinger Distance",
                      type=TechnicalReport,
                      year=2008,
                      publication="Notre Dame University Computer Science and Engineering Technical Reports",
                      url="http://www.cse.nd.edu/Reports/2008/TR-2008-06.pdf")
public class VectorThresholdHellingerDistanceLearner<OutputType>
extends AbstractVectorThresholdMaximumGainLearner<OutputType>

A categorization tree decision function learner on vector data that learns a vector value threshold function using the Hellinger distance. The Hellinger distance is supposed to be less sensitive to skewed data than the more well known information gain method. It also behaves about the same as information gain on balanced data. Thus, it is thought that the Hellinger method may be superior to information gain.

For a given split (sets X and Y) for two categories (a and b)
d(X, Y) = sqrt( (sqrt(Xa / Na) - sqrt(Xb / Nb))^2
+ (sqrt(Ya / Na) - sqrt(Yb / Nb))^2)
where
Xa = number of a's in X,
Xb = number of b's in X,
Ya = number of a's in Y,
Yb = number of b's in Y,
Na = total number of a's (= Xa + Ya), and
Nb = total number of b's (= Xb + Yb).

The Hellinger distance ranges between 0 and sqrt(2), inclusive.

In a problem where there are more than two categories, the Hellinger distance is computed for each unique pair of categories and averaged to compute the Hellinger distance for that split.

Since:

3.0

Author:

Justin Basilico

See Also:

Serialized Form

Field Summary

Fields inherited from class gov.sandia.cognition.learning.algorithm.tree.AbstractVectorThresholdMaximumGainLearner

DEFAULT_MIN_SPLIT_SIZE, dimensionsToConsider, minSplitSize

Constructor Summary

Constructors

Constructor and Description
VectorThresholdHellingerDistanceLearner() Creates a new VectorThresholdHellingerDistanceLearner.
VectorThresholdHellingerDistanceLearner(int minSplitSize) Creates a new VectorThresholdHellingerDistanceLearner.

Method Summary

Modifier and Type	Method and Description
VectorThresholdHellingerDistanceLearner<OutputType>	clone() This makes public the clone method on the Object class and removes the exception that it throws.
double	computeSplitGain(DefaultDataDistribution<OutputType> baseCounts, DefaultDataDistribution<OutputType> positiveCounts, DefaultDataDistribution<OutputType> negativeCounts) Computes the split gain by computing the mean Hellinger distance for the given split.

Methods inherited from class gov.sandia.cognition.learning.algorithm.tree.AbstractVectorThresholdMaximumGainLearner

computeBestGainAndThreshold, computeBestGainAndThreshold, getDimensionsToConsider, getMinSplitSize, learn, setDimensionsToConsider, setMinSplitSize

Methods inherited from class java.lang.Object

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

Constructor Detail

VectorThresholdHellingerDistanceLearner

public VectorThresholdHellingerDistanceLearner()

Creates a new VectorThresholdHellingerDistanceLearner.

VectorThresholdHellingerDistanceLearner

public VectorThresholdHellingerDistanceLearner(int minSplitSize)

Creates a new VectorThresholdHellingerDistanceLearner.

Parameters:

minSplitSize - The minimum split size. Must be positive.

Method Detail

clone

public VectorThresholdHellingerDistanceLearner<OutputType> clone()

Description copied from class: AbstractCloneableSerializable

This makes public the clone method on the Object class and removes the exception that it throws. Its default behavior is to automatically create a clone of the exact type of object that the clone is called on and to copy all primitives but to keep all references, which means it is a shallow copy. Extensions of this class may want to override this method (but call super.clone() to implement a "smart copy". That is, to target the most common use case for creating a copy of the object. Because of the default behavior being a shallow copy, extending classes only need to handle fields that need to have a deeper copy (or those that need to be reset). Some of the methods in ObjectUtil may be helpful in implementing a custom clone method. Note: The contract of this method is that you must use super.clone() as the basis for your implementation.

Specified by:

clone in interface CloneableSerializable

Overrides:

clone in class AbstractVectorThresholdMaximumGainLearner<OutputType>

Returns:

A clone of this object.

computeSplitGain

public double computeSplitGain(DefaultDataDistribution<OutputType> baseCounts,
                               DefaultDataDistribution<OutputType> positiveCounts,
                               DefaultDataDistribution<OutputType> negativeCounts)

Computes the split gain by computing the mean Hellinger distance for the given split. The gain is equal to the distance since the base has a distance of 0.0 with itself.

Specified by:

computeSplitGain in class AbstractVectorThresholdMaximumGainLearner<OutputType>

Parameters:

baseCounts - The histogram of counts before the split.

positiveCounts - The counts on the positive side of the threshold.

negativeCounts - The counts on the negative side of the threshold.

Returns:

The split gain by computing the mean Hellinger distance for the given split.