| java.lang.Object
 weka.core.neighboursearch.kdtrees.KDTreeNodeSplitter
weka.core.neighboursearch.kdtrees.MedianOfWidestDimension
| MedianOfWidestDimension | | public class MedianOfWidestDimension extends KDTreeNodeSplitter implements TechnicalInformationHandler(Code) | |
The class that splits a KDTree node based on the median value of a dimension in which the node's points have the widest spread.
For more information see also:
Jerome H. Friedman, Jon Luis Bentley, Raphael Ari Finkel (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematics Software. 3(3):209-226.
BibTeX:
@article{Friedman1977,
author = {Jerome H. Friedman and Jon Luis Bentley and Raphael Ari Finkel},
journal = {ACM Transactions on Mathematics Software},
month = {September},
number = {3},
pages = {209-226},
title = {An Algorithm for Finding Best Matches in Logarithmic Expected Time},
volume = {3},
year = {1977}
}
author:
Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
version:
$Revision: 1.1 $ |
| Method Summary | |
| 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. | | public String | globalInfo()
Returns a string describing this nearest neighbour search algorithm. | | protected int | partition(int attIdx, int[] index, int l, int r)
Partitions the instances around a pivot. | | public int | select(int attIdx, int[] indices, int left, int right, int k)
Implements computation of the kth-smallest element according
to Manber's "Introduction to Algorithms". | | public void | splitNode(KDTreeNode node, int numNodesCreated, double[][] nodeRanges, double[][] universe)
Splits a node into two based on the median value of the dimension
in which the points have the widest spread. |
| getTechnicalInformation | | public TechnicalInformation getTechnicalInformation()(Code) | | 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.
the technical information about this class |
| globalInfo | | public String globalInfo()(Code) | | Returns a string describing this nearest neighbour search algorithm.
a description of the algorithm for displaying in theexplorer/experimenter gui |
| partition | | protected int partition(int attIdx, int[] index, int l, int r)(Code) | | Partitions the instances around a pivot. Used by quicksort and
kthSmallestValue.
Parameters:
attIdx - The attribution/dimension based on which the instances should be partitioned.
Parameters:
index - The master index array containing indices of the instances.
Parameters:
l - The begining index of the portion of master index array that should be partitioned.
Parameters:
r - The end index of the portion of master index array that should be partitioned. the index of the middle element |
| select | | public int select(int attIdx, int[] indices, int left, int right, int k)(Code) | | Implements computation of the kth-smallest element according
to Manber's "Introduction to Algorithms".
Parameters:
attIdx - The dimension/attribute of the instances in which to find the kth-smallest element.
Parameters:
indices - The master index array containing indices of the instances.
Parameters:
left - The begining index of the portion of the master index array in which to find the kth-smallest element.
Parameters:
right - The end index of the portion of the master index array in which to find the kth-smallest element.
Parameters:
k - The value of k The index of the kth-smallest element |
| splitNode | | public void splitNode(KDTreeNode node, int numNodesCreated, double[][] nodeRanges, double[][] universe) throws Exception(Code) | | Splits a node into two based on the median 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.
Parameters:
node - The node to split.
Parameters:
numNodesCreated - The number of nodes that so far have beencreated for the tree, so that the newly created nodes are assigned correct/meaningful node numbers/ids.
Parameters:
nodeRanges - The attributes' range for the points insidethe node that is to be split.
Parameters:
universe - The attributes' range for the whole point-space.
throws:
Exception - If there is some problem in splitting thegiven node. |
|
|