hex.tree

Class DHistogram

java.lang.Object

water.Iced

hex.tree.DHistogram

All Implemented Interfaces:

java.io.Externalizable, java.io.Serializable, java.lang.Cloneable, water.Freezable

public final class DHistogram
extends water.Iced

A Histogram, computed in parallel over a Vec.

A DHistogram bins every value added to it, and computes a the vec min and max (for use in the next split), and response mean and variance for each bin. DHistograms are initialized with a min, max and number-of- elements to be added (all of which are generally available from a Vec). Bins run from min to max in uniform sizes. If the DHistogram can determine that fewer bins are needed (e.g. boolean columns run from 0 to 1, but only ever take on 2 values, so only 2 bins are needed), then fewer bins are used.

DHistogram are shared per-node, and atomically updated. There's an add call to help cross-node reductions. The data is stored in primitive arrays, so it can be sent over the wire.

If we are successively splitting rows (e.g. in a decision tree), then a fresh DHistogram for each split will dynamically re-bin the data. Each successive split will logarithmically divide the data. At the first split, outliers will end up in their own bins - but perhaps some central bins may be very full. At the next split(s) - if they happen at all - the full bins will get split, and again until (with a log number of splits) each bin holds roughly the same amount of data. This 'UniformAdaptive' binning resolves a lot of problems with picking the proper bin count or limits - generally a few more tree levels will equal any fancy but fixed-size binning strategy.

Support for histogram split points based on quantiles (or random points) is available as well, via _histoType.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DHistogram.NASplitDir Split direction for missing values.

Field Summary

Fields

Modifier and Type	Field and Description
water.Key	_globalQuantilesKey
boolean	_hasQuantiles
SharedTreeModel.SharedTreeParameters.HistogramType	_histoType
byte	_isInt
double	_maxEx
protected double	_maxIn
double	_min
protected double	_min2
double	_minSplitImprovement
java.lang.String	_name
char	_nbin
long	_seed
double[]	_splitPts
double	_step
double[]	_w

Constructor Summary

Constructors

Constructor and Description
DHistogram(java.lang.String name, int nbins, int nbins_cats, byte isInt, double min, double maxEx, double minSplitImprovement, SharedTreeModel.SharedTreeParameters.HistogramType histogramType, long seed, water.Key globalQuantilesKey)

Method Summary

Methods

Modifier and Type	Method and Description
static int[]	activeColumns(DHistogram[] hist)
void	add(DHistogram dsh)
void	add0(DHistogram dsh)
int	bin(double col_data)
double	binAt(int b)
double	bins(int b)
double	find_maxEx()
static double	find_maxEx(double maxIn, int isInt)
double	find_maxIn()
double	find_min()
DTree.Split	findBestSplitPoint(int col, double min_rows)
void	incr0(int b, double y, double w)
void	incr1(int b, double y, double yy)
void	init()
static DHistogram[]	initialHist(water.fvec.Frame fr, int ncols, int nbins, DHistogram[] hs, long seed, SharedTreeModel.SharedTreeParameters parms, water.Key[] globalQuantilesKey)
static DHistogram	make(java.lang.String name, int nbins, byte isInt, double min, double maxEx, long seed, SharedTreeModel.SharedTreeParameters parms, water.Key globalQuantilesKey)
int	nbins()
void	setMaxIn(double max)
void	setMin(double min)
java.lang.String	toString()
void	updateSharedHistosAndReset(hex.tree.ScoreBuildHistogram.LocalHisto lh, double[] ws, double[] cs, double[] ys, int[] rows, int hi, int lo)
double	var(int b) compute the sample variance within a given bin

Methods inherited from class water.Iced

asBytes, clone, copyOver, frozenType, read, readExternal, readJSON, reloadFromBytes, toJsonString, write, writeExternal, writeJSON

Methods inherited from class java.lang.Object

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

Field Detail

_name

public final transient java.lang.String _name

_minSplitImprovement

public final double _minSplitImprovement

_isInt

public final byte _isInt

_nbin

public char _nbin

_step

public double _step

_min

public final double _min

_maxEx

public final double _maxEx

_w

public double[] _w

_min2

protected double _min2

_maxIn

protected double _maxIn

_histoType

public SharedTreeModel.SharedTreeParameters.HistogramType _histoType

_splitPts

public transient double[] _splitPts

_seed

public final long _seed

_hasQuantiles

public transient boolean _hasQuantiles

_globalQuantilesKey

public water.Key _globalQuantilesKey

Constructor Detail

DHistogram

public DHistogram(java.lang.String name,
          int nbins,
          int nbins_cats,
          byte isInt,
          double min,
          double maxEx,
          double minSplitImprovement,
          SharedTreeModel.SharedTreeParameters.HistogramType histogramType,
          long seed,
          water.Key globalQuantilesKey)

Method Detail

activeColumns

public static int[] activeColumns(DHistogram[] hist)

setMin

public void setMin(double min)

setMaxIn

public void setMaxIn(double max)

bin

public int bin(double col_data)

binAt

public double binAt(int b)

nbins

public int nbins()

bins

public double bins(int b)

init

public void init()

add

public void add(DHistogram dsh)

find_min

public double find_min()

find_maxIn

public double find_maxIn()

find_maxEx

public double find_maxEx()

find_maxEx

public static double find_maxEx(double maxIn,
                int isInt)

initialHist

public static DHistogram[] initialHist(water.fvec.Frame fr,
                       int ncols,
                       int nbins,
                       DHistogram[] hs,
                       long seed,
                       SharedTreeModel.SharedTreeParameters parms,
                       water.Key[] globalQuantilesKey)

make

public static DHistogram make(java.lang.String name,
              int nbins,
              byte isInt,
              double min,
              double maxEx,
              long seed,
              SharedTreeModel.SharedTreeParameters parms,
              water.Key globalQuantilesKey)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

var

public double var(int b)

compute the sample variance within a given bin

Parameters:

b - bin id

Returns:

sample variance (>= 0)

incr0

public void incr0(int b,
         double y,
         double w)

incr1

public void incr1(int b,
         double y,
         double yy)

add0

public void add0(DHistogram dsh)

findBestSplitPoint

public DTree.Split findBestSplitPoint(int col,
                             double min_rows)

updateSharedHistosAndReset

public void updateSharedHistosAndReset(hex.tree.ScoreBuildHistogram.LocalHisto lh,
                              double[] ws,
                              double[] cs,
                              double[] ys,
                              int[] rows,
                              int hi,
                              int lo)