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, setMaxRelativeLeafRadius
public MiddleOutConstructor()
public java.lang.String globalInfo()
public TechnicalInformation getTechnicalInformation()
getTechnicalInformation
in interface TechnicalInformationHandler
public BallNode buildTree() throws java.lang.Exception
buildTree
in class BallTreeConstructor
java.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.Exception
public 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 BallTreeConstructor
node
- 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 BallTreeConstructor
num
- 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 BallTreeConstructor
insts
- The instances on which to build the ball tree.public void setInstanceList(int[] instList)
setInstanceList
in class BallTreeConstructor
instList
- 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 Randomizable
public void setSeed(int seed)
setSeed
in interface Randomizable
seed
- The seed.public java.util.Enumeration<Option> listOptions()
listOptions
in interface OptionHandler
listOptions
in class BallTreeConstructor
public 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 OptionHandler
setOptions
in class BallTreeConstructor
options
- the list of options as an array of stringsjava.lang.Exception
- if an option is not supportedpublic java.lang.String[] getOptions()
getOptions
in interface OptionHandler
getOptions
in class BallTreeConstructor
public 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 RevisionHandler
getRevision
in class BallTreeConstructor