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 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 Description protected DistanceFunction
m_DistanceFunction
the distance function used.protected 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 Description NearestNeighbourSearch()
Constructor.NearestNeighbourSearch(Instances insts)
Constructor.
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
addInstanceInfo(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.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 Instances
kNearestNeighbours(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 Instance
nearestNeighbour(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(Instances insts)
Sets the instances.abstract void
update(Instance ins)
Updates the NearNeighbourSearch algorithm for the new added instance.
-
-
-
Field Detail
-
m_Instances
protected 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(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 Instance nearestNeighbour(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 Instances kNearestNeighbours(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(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(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(Instances insts) throws Exception
Sets the instances.- Parameters:
insts
- the instances to use- Throws:
Exception
- if setting fails
-
getInstances
public 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 sortedlinkedArray
- the linked arrayl
- the first index of the subsetr
- 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 sortlinkedArray
- the linked arrayleft
- the first index of the subsetright
- the last index of the subset
-
-