weka.core.neighboursearch.balltrees

Class MedianDistanceFromArbitraryPoint

java.lang.Object

weka.core.neighboursearch.balltrees.BallSplitter

weka.core.neighboursearch.balltrees.MedianDistanceFromArbitraryPoint

All Implemented Interfaces:

Serializable, OptionHandler, RevisionHandler, TechnicalInformationHandler

public class MedianDistanceFromArbitraryPoint
extends BallSplitter
implements TechnicalInformationHandler

Class that splits a BallNode of a ball tree using Uhlmann's described method.

For information see:

Jeffrey K. Uhlmann (1991). Satisfying general proximity/similarity queries with metric trees. Information Processing Letters. 40(4):175-179.

Ashraf Masood Kibriya (2007). Fast Algorithms for Nearest Neighbour Search. Hamilton, New Zealand.

BibTeX:

 @article{Uhlmann1991,
    author = {Jeffrey K. Uhlmann},
    journal = {Information Processing Letters},
    month = {November},
    number = {4},
    pages = {175-179},
    title = {Satisfying general proximity/similarity queries with metric trees},
    volume = {40},
    year = {1991}
 }
 
 @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 value for the random number generator.
  (default: 17)

Version:

$Revision: 1.2 $

Author:

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

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected Random	m_Rand Random number generator for selecting an abitrary (random) point.
protected int	m_RandSeed Seed for random number generator.

Fields inherited from class weka.core.neighboursearch.balltrees.BallSplitter

m_DistanceFunction, m_Instances, m_Instlist

Constructor Summary

Constructors

Constructor and Description
MedianDistanceFromArbitraryPoint() Constructor.
MedianDistanceFromArbitraryPoint(int[] instList, Instances insts, EuclideanDistance e) Constructor.

Method Summary

Modifier and Type	Method and Description
String[]	getOptions() Gets the current settings of the object.
int	getRandomSeed() Returns the seed value of random number generator.
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.
String	globalInfo() Returns a string describing this nearest neighbour search algorithm.
Enumeration	listOptions() Returns an enumeration describing the available options.
protected int	partition(double[] array, int[] index, int l, int r, int indexStart) Partitions the instances around a pivot.
String	randomSeedTipText() Returns the tip text for this property.
protected int	select(double[] array, int[] indices, int left, int right, int indexStart, int k) Implements computation of the kth-smallest element according to Manber's "Introduction to Algorithms".
void	setOptions(String[] options) Parses a given list of options.
void	setRandomSeed(int seed) Sets the seed for random number generator.
void	splitNode(BallNode node, int numNodesCreated) Splits a ball into two.

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

correctlyInitialized, setEuclideanDistanceFunction, setInstanceList, setInstances

Methods inherited from class java.lang.Object

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

Field Detail

m_RandSeed

protected int m_RandSeed

Seed for random number generator.

m_Rand

protected Random m_Rand

Random number generator for selecting an abitrary (random) point.

Constructor Detail

MedianDistanceFromArbitraryPoint

public MedianDistanceFromArbitraryPoint()

Constructor.

MedianDistanceFromArbitraryPoint

public MedianDistanceFromArbitraryPoint(int[] instList,
                                        Instances insts,
                                        EuclideanDistance e)

Constructor.

Parameters:

instList - The master index array.

insts - The instances on which the tree is (or is to be) built.

e - The Euclidean distance function to use for splitting.

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

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

listOptions

public Enumeration listOptions()

Returns an enumeration describing the available options.

Specified by:

listOptions in interface OptionHandler

Overrides:

listOptions in class BallSplitter

Returns:

an enumeration of all the available options.

setOptions

public void setOptions(String[] options)
                throws Exception

Parses a given list of options. Valid options are:

 -S <num>
  The seed value for the random number generator.
  (default: 17)

Specified by:

setOptions in interface OptionHandler

Overrides:

setOptions in class BallSplitter

Parameters:

options - the list of options as an array of strings

Throws:

Exception - if an option is not supported

getOptions

public String[] getOptions()

Gets the current settings of the object.

Specified by:

getOptions in interface OptionHandler

Overrides:

getOptions in class BallSplitter

Returns:

an array of strings suitable for passing to setOptions

setRandomSeed

public void setRandomSeed(int seed)

Sets the seed for random number generator.

Parameters:

seed - The seed value to set.

getRandomSeed

public int getRandomSeed()

Returns the seed value of random number generator.

Returns:

The random seed currently in use.

randomSeedTipText

public String randomSeedTipText()

Returns the tip text for this property.

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui.

splitNode

public void splitNode(BallNode node,
                      int numNodesCreated)
               throws Exception

Splits a ball into two.

Specified by:

splitNode in class BallSplitter

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.

Throws:

Exception - If there is some problem in splitting the given node.

partition

protected int partition(double[] array,
                        int[] index,
                        int l,
                        int r,
                        int indexStart)

Partitions the instances around a pivot. Used by quicksort and kthSmallestValue.

Parameters:

array - The array of distances of the points to the arbitrarily selected point.

index - The master index array containing indices of the instances.

l - The relative begining index of the portion of master index array that should be partitioned.

r - The relative end index of the portion of master index array that should be partitioned.

indexStart - The absolute begining index of the portion of master index array that should be partitioned.

Returns:

the index of the middle element (in the master index array, i.e. index of the index of middle element).

select

protected int select(double[] array,
                     int[] indices,
                     int left,
                     int right,
                     int indexStart,
                     int k)

Implements computation of the kth-smallest element according to Manber's "Introduction to Algorithms".

Parameters:

array - Array containing the distances of points from the arbitrarily selected.

indices - The master index array containing indices of the instances.

left - The relative begining index of the portion of the master index array in which to find the kth-smallest element.

right - The relative end index of the portion of the master index array in which to find the kth-smallest element.

indexStart - The absolute begining index of the portion of the master index array in which to find the kth-smallest element.

k - The value of k

Returns:

The index of the kth-smallest element

getRevision

public String getRevision()

Returns the revision string.

Specified by:

getRevision in interface RevisionHandler

Overrides:

getRevision in class BallSplitter

Returns:

the revision