public class MiddleOutConstructor extends BallTreeConstructor implements Randomizable, TechnicalInformationHandler
@inproceedings{Moore2000,
address = {San Francisco, CA, USA},
author = {Andrew W. Moore},
booktitle = {UAI '00: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence},
pages = {397-405},
publisher = {Morgan Kaufmann Publishers Inc.},
title = {The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data},
year = {2000}
}
@mastersthesis{Kibriya2007,
address = {Hamilton, New Zealand},
author = {Ashraf Masood Kibriya},
school = {Department of Computer Science, School of Computing and Mathematical Sciences, University of Waikato},
title = {Fast Algorithms for Nearest Neighbour Search},
year = {2007}
}
Valid options are:
-S <num> The seed for the random number generator used in selecting random anchor. (default: 1)
-R Use randomly chosen initial anchors.
| Constructor and Description |
|---|
MiddleOutConstructor()
Creates a new instance of MiddleOutConstructor.
|
| Modifier and Type | Method and Description |
|---|---|
int[] |
addInstance(BallNode node,
Instance inst)
Adds an instance to the tree.
|
BallNode |
buildTree()
Builds a ball tree middle out.
|
Instance |
calcPivot(weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list1,
weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list2,
Instances insts)
Calculates the centroid pivot of a node based on the list of points that it
contains (tbe two lists of its children are provided).
|
Instance |
calcPivot(weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode node1,
weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode node2,
Instances insts)
/** Calculates the centroid pivot of a node based on its two child nodes
(if merging two nodes).
|
double |
calcRadius(weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list1,
weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list2,
Instance pivot,
Instances insts)
Calculates the radius of a node based on the list of points that it
contains (the two lists of its children are provided).
|
double |
calcRadius(weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode n1,
weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode n2)
Calculates the radius of a node based on its two child nodes (if merging
two nodes).
|
void |
checkIndicesList(weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list,
int startidx,
int endidx)
Checks whether if the points in an index list are in some specified of the
master index array.
|
java.lang.String[] |
getOptions()
Gets the current settings of this BallTree MiddleOutConstructor.
|
java.lang.String |
getRevision()
Returns the revision string.
|
int |
getSeed()
Returns the seed for random number generator.
|
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.
|
java.lang.String |
initialAnchorRandomTipText()
Returns the tip text for this property.
|
boolean |
isInitialAnchorRandom()
Gets whether if the initial anchor is chosen randomly.
|
java.util.Enumeration<Option> |
listOptions()
Returns an enumeration describing the available options.
|
java.lang.String |
printInsts(int startIdx,
int endIdx)
For printing indices in some given portion of the master index array.
|
java.lang.String |
printList(weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList points)
For printing indices in a given point list.
|
java.lang.String |
seedTipText()
Returns the tip text for this property.
|
void |
setInitialAnchorRandom(boolean randomInitialAnchor)
Sets whether if the initial anchor is chosen randomly.
|
void |
setInstanceList(int[] instList)
Sets the master index array that points to instances in m_Instances, so
that only this array is manipulated, and m_Instances is left untouched.
|
void |
setInstances(Instances insts)
Sets the instances on which the tree is to be built.
|
void |
setInterAnchorDistances(java.util.Vector<weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode> anchors,
weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode newAnchor,
java.util.Vector<double[]> anchorDistances)
Sets the distances of a supplied new anchor to all the rest of the previous
anchor points.
|
void |
setMaxInstancesInLeaf(int num)
Sets the maximum number of instances allowed in a leaf.
|
void |
setOptions(java.lang.String[] options)
Parses a given list of options.
|
void |
setPoints(weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode node,
int startIdx,
int endIdx,
int[] indices)
Sets the points of an anchor node.
|
void |
setSeed(int seed)
Sets the seed for random number generator (that is used for selecting the
first anchor point randomly).
|
boolean |
stealPoints(weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode newAnchor,
java.util.Vector<weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode> anchors,
java.util.Vector<double[]> anchorDistances)
Removes points from old anchors that are nearer to the given new anchor and
adds them to the list of points of the new anchor.
|
containChildBallsTipText, getContainChildBalls, getMaxDepth, getMaxInstancesInLeaf, getMaxRelativeLeafRadius, getNumLeaves, getNumNodes, maxInstancesInLeafTipText, maxRelativeLeafRadiusTipText, setContainChildBalls, setEuclideanDistanceFunction, setMaxRelativeLeafRadiuspublic MiddleOutConstructor()
public java.lang.String globalInfo()
public TechnicalInformation getTechnicalInformation()
getTechnicalInformation in interface TechnicalInformationHandlerpublic BallNode buildTree() throws java.lang.Exception
buildTree in class BallTreeConstructorjava.lang.Exception - If there is problem building the tree.public void setPoints(weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode node,
int startIdx,
int endIdx,
int[] indices)
node - The node in which the points are needed to be set.startIdx - The start of the portion in the given index array (the
master index array).endIdx - The end of the portion in the given index array.indices - The index array.public void setInterAnchorDistances(java.util.Vector<weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode> anchors,
weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode newAnchor,
java.util.Vector<double[]> anchorDistances)
throws java.lang.Exception
anchors - The old anchor points.newAnchor - The new anchor point.anchorDistances - The vector to store the distances of newAnchor to
each of the old anchors.java.lang.Exception - If there is some problem in calculating the distances.public boolean stealPoints(weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode newAnchor,
java.util.Vector<weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode> anchors,
java.util.Vector<double[]> anchorDistances)
newAnchor - The new anchor.anchors - The old anchors.anchorDistances - The distances of new anchor to each of the old
anchors.public Instance calcPivot(weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode node1, weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode node2, Instances insts)
node1 - The first child.node2 - The second child.insts - The set of instances on which the tree is being built (as
dataset header information is required).public Instance calcPivot(weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list1, weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list2, Instances insts)
list1 - The point index list of first child.list2 - The point index list of second child.insts - The insts object on which the tree is being built (for header
information).public double calcRadius(weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode n1,
weka.core.neighboursearch.balltrees.MiddleOutConstructor.TempNode n2)
n1 - The first child of the node.n2 - The second child of the node.java.lang.Exceptionpublic double calcRadius(weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list1,
weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list2,
Instance pivot,
Instances insts)
list1 - The point index list of first child.list2 - The point index list of second child.pivot - The centre/pivot of the node.insts - The instances on which the tree is being built (for header
info).public int[] addInstance(BallNode node, Instance inst) throws java.lang.Exception
addInstance in class BallTreeConstructornode - The root of the tree to which the instance is to be added.inst - The instance to add to the tree.java.lang.Exception - Always as this implementation of MiddleOutConstructor
doesn't support addition of instances after batch construction of
the tree.public void setMaxInstancesInLeaf(int num)
throws java.lang.Exception
setMaxInstancesInLeaf in class BallTreeConstructornum - The maximum number of instances allowed in a leaf.java.lang.Exception - If the num is < 2, as the method cannot work for < 2
instances.public void setInstances(Instances insts)
setInstances in class BallTreeConstructorinsts - The instances on which to build the ball tree.public void setInstanceList(int[] instList)
setInstanceList in class BallTreeConstructorinstList - The master index array.public java.lang.String initialAnchorRandomTipText()
public boolean isInitialAnchorRandom()
public void setInitialAnchorRandom(boolean randomInitialAnchor)
randomInitialAnchor - Should be true if the first anchor is to be
chosen randomly.public java.lang.String seedTipText()
public int getSeed()
getSeed in interface Randomizablepublic void setSeed(int seed)
setSeed in interface Randomizableseed - The seed.public java.util.Enumeration<Option> listOptions()
listOptions in interface OptionHandlerlistOptions in class BallTreeConstructorpublic void setOptions(java.lang.String[] options)
throws java.lang.Exception
-S <num> The seed for the random number generator used in selecting random anchor. (default: 1)
-R Use randomly chosen initial anchors.
setOptions in interface OptionHandlersetOptions in class BallTreeConstructoroptions - the list of options as an array of stringsjava.lang.Exception - if an option is not supportedpublic java.lang.String[] getOptions()
getOptions in interface OptionHandlergetOptions in class BallTreeConstructorpublic void checkIndicesList(weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList list,
int startidx,
int endidx)
throws java.lang.Exception
list - The point list.startidx - The start of the portion in master index array.endidx - The end of the portion in master index array.java.lang.Exception - If some point in the point list is not in the specified
portion of master index array.public java.lang.String printInsts(int startIdx,
int endIdx)
startIdx - The start of the portion in master index array.endIdx - The end of the portion in master index array.public java.lang.String printList(weka.core.neighboursearch.balltrees.MiddleOutConstructor.MyIdxList points)
points - The point list.public java.lang.String getRevision()
getRevision in interface RevisionHandlergetRevision in class BallTreeConstructor