weka.core.neighboursearch.balltrees

Class BottomUpConstructor

java.lang.Object

weka.core.neighboursearch.balltrees.BallTreeConstructor

weka.core.neighboursearch.balltrees.BottomUpConstructor

All Implemented Interfaces:

java.io.Serializable, OptionHandler, RevisionHandler, TechnicalInformationHandler

public class BottomUpConstructor
extends BallTreeConstructor
implements TechnicalInformationHandler

The class that constructs a ball tree bottom up.

BibTeX:

 @techreport{Omohundro1989,
    author = {Stephen M. Omohundro},
    institution = {International Computer Science Institute},
    month = {December},
    number = {TR-89-063},
    title = {Five Balltree Construction Algorithms},
    year = {1989}
 }
 

Valid options are:

 -N <value>
  Set maximum number of instances in a leaf node
  (default: 40)

 -R
  Set internal nodes' radius to the sum 
  of the child balls radii. So that it 
 contains the child balls.

Version:

$Revision: 1.3 $

Author:

Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
BottomUpConstructor() Creates a new instance of BottomUpConstructor.

Method Summary

Modifier and Type	Method and Description
int[]	addInstance(BallNode node, Instance inst) Adds an instance to the ball tree.
BallNode	buildTree() Builds the ball tree bottom up.
Instance	calcPivot(weka.core.neighboursearch.balltrees.BottomUpConstructor.TempNode node1, weka.core.neighboursearch.balltrees.BottomUpConstructor.TempNode node2, Instances insts) Calculates the centroid pivot of a node based on its two child nodes.
double	calcRadius(weka.core.neighboursearch.balltrees.BottomUpConstructor.TempNode n1, weka.core.neighboursearch.balltrees.BottomUpConstructor.TempNode n2) Calculates the radius of a node based on its two child nodes.
java.lang.String	getRevision() Returns the revision string.
TechnicalInformation	getTechnicalInformation() Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.
java.lang.String	globalInfo() Returns a string describing this nearest neighbour search algorithm.

Methods inherited from class weka.core.neighboursearch.balltrees.BallTreeConstructor

containChildBallsTipText, getContainChildBalls, getMaxDepth, getMaxInstancesInLeaf, getMaxRelativeLeafRadius, getNumLeaves, getNumNodes, getOptions, listOptions, maxInstancesInLeafTipText, maxRelativeLeafRadiusTipText, setContainChildBalls, setEuclideanDistanceFunction, setInstanceList, setInstances, setMaxInstancesInLeaf, setMaxRelativeLeafRadius, setOptions

Methods inherited from class java.lang.Object

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

Constructor Detail

BottomUpConstructor

public BottomUpConstructor()

Creates a new instance of BottomUpConstructor.

Method Detail

globalInfo

public java.lang.String globalInfo()

Returns a string describing this nearest neighbour search algorithm.

Returns:

a description of the algorithm for displaying in the explorer/experimenter gui

getTechnicalInformation

public TechnicalInformation getTechnicalInformation()

Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.

Specified by:

getTechnicalInformation in interface TechnicalInformationHandler

Returns:

the technical information about this class

buildTree

public BallNode buildTree()
                   throws java.lang.Exception

Builds the ball tree bottom up.

Specified by:

buildTree in class BallTreeConstructor

Returns:

The root node of the tree.

Throws:

java.lang.Exception - If there is problem building the tree.

addInstance

public int[] addInstance(BallNode node,
                         Instance inst)
                  throws java.lang.Exception

Adds an instance to the ball tree.

Specified by:

addInstance in class BallTreeConstructor

Parameters:

node - The root node of the tree.

inst - The instance to add to the tree.

Returns:

The new master index array after adding the instance.

Throws:

java.lang.Exception - Always as BottomUpConstructor does not allow addition of instances after batch construction.

calcPivot

public Instance calcPivot(weka.core.neighboursearch.balltrees.BottomUpConstructor.TempNode node1,
                          weka.core.neighboursearch.balltrees.BottomUpConstructor.TempNode node2,
                          Instances insts)
                   throws java.lang.Exception

Calculates the centroid pivot of a node based on its two child nodes.

Parameters:

node1 - The first child node.

node2 - The second child node.

insts - The instance on which the tree is to be built.

Returns:

The centre/pivot of the node.

Throws:

java.lang.Exception - If there is some problem calculating the centre/pivot of the node.

calcRadius

public double calcRadius(weka.core.neighboursearch.balltrees.BottomUpConstructor.TempNode n1,
                         weka.core.neighboursearch.balltrees.BottomUpConstructor.TempNode n2)
                  throws java.lang.Exception

Calculates the radius of a node based on its two child nodes.

Parameters:

n1 - The first child node.

n2 - The second child node.

Returns:

The calculated radius of the the node.

Throws:

java.lang.Exception - If there is some problem in calculating the radius.

getRevision

public java.lang.String getRevision()

Returns the revision string.

Specified by:

getRevision in interface RevisionHandler

Overrides:

getRevision in class BallTreeConstructor

Returns:

the revision