moa.classifiers.lazy.neighboursearch

Class NearestNeighbourSearch

java.lang.Object

moa.classifiers.lazy.neighboursearch.NearestNeighbourSearch

All Implemented Interfaces:

Serializable

Direct Known Subclasses:

KDTree, LinearNNSearch

public abstract class NearestNeighbourSearch
extends Object
implements Serializable

Abstract class for nearest neighbour search. All algorithms (classes) that do nearest neighbour search should extend this class.

Version:

$Revision: 8034 $

Author:

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

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	NearestNeighbourSearch.MyHeap A class for a heap to store the nearest k neighbours to an instance.
protected class	NearestNeighbourSearch.MyHeapElement A class for storing data about a neighboring instance.
protected class	NearestNeighbourSearch.NeighborList A class for a linked list to store the nearest k neighbours to an instance.
protected class	NearestNeighbourSearch.NeighborNode A class for storing data about a neighboring instance.

Field Summary

Fields

Modifier and Type	Field and Description
protected DistanceFunction	m_DistanceFunction the distance function used.
protected weka.core.Instances	m_Instances The neighbourhood of instances to find neighbours in.
protected int	m_kNN The number of neighbours to find.
protected boolean	m_MeasurePerformance Should we measure Performance.

Constructor Summary

Constructors

Constructor and Description
NearestNeighbourSearch() Constructor.
NearestNeighbourSearch(weka.core.Instances insts) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	addInstanceInfo(weka.core.Instance ins) Adds information from the given instance without modifying the datastructure a lot.
static void	combSort11(double[] arrayToSort, int[] linkedArray) sorts the two given arrays.
String	distanceFunctionTipText() Returns the tip text for this property.
DistanceFunction	getDistanceFunction() returns the distance function currently in use.
abstract double[]	getDistances() Returns the distances of the k nearest neighbours.
weka.core.Instances	getInstances() returns the instances currently set.
boolean	getMeasurePerformance() Gets whether performance statistics are being calculated or not.
String	globalInfo() Returns a string describing this nearest neighbour search algorithm.
abstract weka.core.Instances	kNearestNeighbours(weka.core.Instance target, int k) Returns k nearest instances in the current neighbourhood to the supplied instance.
String	measurePerformanceTipText() Returns the tip text for this property.
abstract weka.core.Instance	nearestNeighbour(weka.core.Instance target) Returns the nearest instance in the current neighbourhood to the supplied instance.
protected static int	partition(double[] arrayToSort, double[] linkedArray, int l, int r) Partitions the instances around a pivot.
static void	quickSort(double[] arrayToSort, double[] linkedArray, int left, int right) performs quicksort.
void	setDistanceFunction(DistanceFunction df) sets the distance function to use for nearest neighbour search.
void	setInstances(weka.core.Instances insts) Sets the instances.
abstract void	update(weka.core.Instance ins) Updates the NearNeighbourSearch algorithm for the new added instance.

Methods inherited from class java.lang.Object

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

Field Detail

m_Instances

protected weka.core.Instances m_Instances

The neighbourhood of instances to find neighbours in.

m_kNN

protected int m_kNN

The number of neighbours to find.

m_DistanceFunction

protected DistanceFunction m_DistanceFunction

the distance function used.

m_MeasurePerformance

protected boolean m_MeasurePerformance

Should we measure Performance.

Constructor Detail

NearestNeighbourSearch

public NearestNeighbourSearch()

Constructor.

NearestNeighbourSearch

public NearestNeighbourSearch(weka.core.Instances insts)

Constructor.

Parameters:

insts - The set of instances that constitute the neighbourhood.

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

distanceFunctionTipText

public String distanceFunctionTipText()

Returns the tip text for this property.

Returns:

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

getDistanceFunction

public DistanceFunction getDistanceFunction()

returns the distance function currently in use.

Returns:

the distance function

setDistanceFunction

public void setDistanceFunction(DistanceFunction df)
                         throws Exception

sets the distance function to use for nearest neighbour search.

Parameters:

df - the new distance function to use

Throws:

Exception - if instances cannot be processed

measurePerformanceTipText

public String measurePerformanceTipText()

Returns the tip text for this property.

Returns:

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

getMeasurePerformance

public boolean getMeasurePerformance()

Gets whether performance statistics are being calculated or not.

Returns:

true if the measure performance is calculated

nearestNeighbour

public abstract weka.core.Instance nearestNeighbour(weka.core.Instance target)
                                             throws Exception

Returns the nearest instance in the current neighbourhood to the supplied instance.

Parameters:

target - The instance to find the nearest neighbour for.

Returns:

the nearest neighbor

Throws:

Exception - if the nearest neighbour could not be found.

kNearestNeighbours

public abstract weka.core.Instances kNearestNeighbours(weka.core.Instance target,
                                     int k)
                                                throws Exception

Returns k nearest instances in the current neighbourhood to the supplied instance.

Parameters:

target - The instance to find the k nearest neighbours for.

k - The number of nearest neighbours to find.

Returns:

the k nearest neighbors

Throws:

Exception - if the neighbours could not be found.

getDistances

public abstract double[] getDistances()
                               throws Exception

Returns the distances of the k nearest neighbours. The kNearestNeighbours or nearestNeighbour needs to be called first for this to work.

Returns:

the distances

Throws:

Exception - if called before calling kNearestNeighbours or nearestNeighbours.

update

public abstract void update(weka.core.Instance ins)
                     throws Exception

Updates the NearNeighbourSearch algorithm for the new added instance. P.S.: The method assumes the instance has already been added to the m_Instances object by the caller.

Parameters:

ins - the instance to add

Throws:

Exception - if updating fails

addInstanceInfo

public void addInstanceInfo(weka.core.Instance ins)

Adds information from the given instance without modifying the datastructure a lot.

Parameters:

ins - the instance to add the information from

setInstances

public void setInstances(weka.core.Instances insts)
                  throws Exception

Sets the instances.

Parameters:

insts - the instances to use

Throws:

Exception - if setting fails

getInstances

public weka.core.Instances getInstances()

returns the instances currently set.

Returns:

the current instances

combSort11

public static void combSort11(double[] arrayToSort,
              int[] linkedArray)

sorts the two given arrays.

Parameters:

arrayToSort - The array sorting should be based on.

linkedArray - The array that should have the same ordering as arrayToSort.

partition

protected static int partition(double[] arrayToSort,
            double[] linkedArray,
            int l,
            int r)

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

Parameters:

arrayToSort - the array of doubles to be sorted

linkedArray - the linked array

l - the first index of the subset

r - the last index of the subset

Returns:

the index of the middle element

quickSort

public static void quickSort(double[] arrayToSort,
             double[] linkedArray,
             int left,
             int right)

performs quicksort.

Parameters:

arrayToSort - the array to sort

linkedArray - the linked array

left - the first index of the subset

right - the last index of the subset