Class 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
    • 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 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