Class MidPointOfWidestDimension
- java.lang.Object
-
- moa.classifiers.lazy.neighboursearch.kdtrees.KDTreeNodeSplitter
-
- moa.classifiers.lazy.neighboursearch.kdtrees.MidPointOfWidestDimension
-
- All Implemented Interfaces:
Serializable
public class MidPointOfWidestDimension extends KDTreeNodeSplitter
The class that splits a KDTree node based on the midpoint value of a dimension in which the node's points have the widest spread.
For more information see also:
Andrew Moore (1991). A tutorial on kd-trees. BibTeX:@techreport{Moore1991, author = {Andrew Moore}, booktitle = {University of Cambridge Computer Laboratory Technical Report No. 209}, howpublished = {Extract from PhD Thesis}, title = {A tutorial on kd-trees}, year = {1991}, HTTP = {http://www.autonlab.org/autonweb/14665.html} }
- Version:
- $Revision: 8034 $
- Author:
- Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
- See Also:
- Serialized Form
-
-
Field Summary
-
Fields inherited from class moa.classifiers.lazy.neighboursearch.kdtrees.KDTreeNodeSplitter
m_EuclideanDistance, m_Instances, m_InstList, m_NormalizeNodeWidth, MAX, MIN, WIDTH
-
-
Constructor Summary
Constructors Constructor Description MidPointOfWidestDimension()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description String
globalInfo()
Returns a string describing this nearest neighbour search algorithm.protected int
rearrangePoints(int[] indices, int startidx, int endidx, int splitDim, double splitVal)
Re-arranges the indices array such that the points <= to the splitVal are on the left of the array and those > the splitVal are on the right.void
splitNode(KDTreeNode node, int numNodesCreated, double[][] nodeRanges, double[][] universe)
Splits a node into two based on the midpoint value of the dimension in which the points have the widest spread.-
Methods inherited from class moa.classifiers.lazy.neighboursearch.kdtrees.KDTreeNodeSplitter
correctlyInitialized, getOptions, listOptions, setEuclideanDistanceFunction, setInstanceList, setInstances, setNodeWidthNormalization, setOptions, widestDim
-
-
-
-
Method Detail
-
globalInfo
public String globalInfo()
Returns a string describing this nearest neighbour search algorithm.- Returns:
- a description of the algorithm for displaying in the explorer/experimenter gui
-
splitNode
public void splitNode(KDTreeNode node, int numNodesCreated, double[][] nodeRanges, double[][] universe) throws Exception
Splits a node into two based on the midpoint value of the dimension in which the points have the widest spread. After splitting two new nodes are created and correctly initialised. And, node.left and node.right are set appropriately.- Specified by:
splitNode
in classKDTreeNodeSplitter
- Parameters:
node
- The node to split.numNodesCreated
- The number of nodes that so far have been created for the tree, so that the newly created nodes are assigned correct/meaningful node numbers/ids.nodeRanges
- The attributes' range for the points inside the node that is to be split.universe
- The attributes' range for the whole point-space.- Throws:
Exception
- If there is some problem in splitting the given node.
-
rearrangePoints
protected int rearrangePoints(int[] indices, int startidx, int endidx, int splitDim, double splitVal)
Re-arranges the indices array such that the points <= to the splitVal are on the left of the array and those > the splitVal are on the right.- Parameters:
indices
- The master index array.startidx
- The begining index of portion of indices that needs re-arranging.endidx
- The end index of portion of indices that needs re-arranging.splitDim
- The split dimension/attribute.splitVal
- The split value.- Returns:
- The startIdx of the points > the splitVal (the points belonging to the right child of the node).
-
-