Class Anderberg.Instance

  • Direct Known Subclasses:
    HACAM.Instance
    Enclosing class:
    Anderberg<O>

    public static class Anderberg.Instance
    extends AGNES.Instance
    Main worker instance of Anderberg's algorithm.
    Author:
    Erich Schubert
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected double[] bestd
      Cache: best distance
      protected int[] besti
      Cache: index of best distance
    • Constructor Summary

      Constructors 
      Constructor Description
      Instance​(Linkage linkage)
      Constructor.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected static void findBest​(double[] scratch, double[] bestd, int[] besti, int j)
      Find the best in a row of the triangular matrix.
      protected int findMerge()
      Perform the next merge step.
      protected static void initializeNNCache​(double[] scratch, double[] bestd, int[] besti)
      Initialize the NN cache.
      protected void merge​(double mindist, int x, int y)
      Execute the cluster merge.
      ClusterMergeHistory run​(ClusterDistanceMatrix mat, ClusterMergeHistoryBuilder builder)
      Run the main algorithm.
      protected static void updateCache​(double[] scratch, double[] bestd, int[] besti, int x, int y, int j, double d)
      Update the cache.
      protected void updateMatrix​(double mindist, int x, int y, int sizex, int sizey)
      Update the scratch distance matrix.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • bestd

        protected double[] bestd
        Cache: best distance
      • besti

        protected int[] besti
        Cache: index of best distance
    • Constructor Detail

      • Instance

        public Instance​(Linkage linkage)
        Constructor.
        Parameters:
        linkage - Linkage method
    • Method Detail

      • initializeNNCache

        protected static void initializeNNCache​(double[] scratch,
                                                double[] bestd,
                                                int[] besti)
        Initialize the NN cache.
        Parameters:
        scratch - Scratch space
        bestd - Best distance
        besti - Best index
      • findMerge

        protected int findMerge()
        Perform the next merge step.

        Due to the cache, this is now O(n) each time, instead of O(n*n).

        Overrides:
        findMerge in class AGNES.Instance
        Returns:
        x, for shrinking the working set.
      • merge

        protected void merge​(double mindist,
                             int x,
                             int y)
        Description copied from class: AGNES.Instance
        Execute the cluster merge.
        Overrides:
        merge in class AGNES.Instance
        Parameters:
        mindist - Distance that was used for merging
        x - First matrix position
        y - Second matrix position
      • updateMatrix

        protected void updateMatrix​(double mindist,
                                    int x,
                                    int y,
                                    int sizex,
                                    int sizey)
        Description copied from class: AGNES.Instance
        Update the scratch distance matrix.
        Overrides:
        updateMatrix in class AGNES.Instance
        Parameters:
        mindist - Minimum distance
        x - First matrix position
        y - Second matrix position
        sizex - Old size of first cluster
        sizey - Old size of second cluster
      • updateCache

        protected static void updateCache​(double[] scratch,
                                          double[] bestd,
                                          int[] besti,
                                          int x,
                                          int y,
                                          int j,
                                          double d)
        Update the cache.
        Parameters:
        scratch - Scratch matrix
        bestd - Best distance
        besti - Best index
        x - First cluster
        y - Second cluster, y < x
        j - Updated value d(y, j)
        d - New distance
      • findBest

        protected static void findBest​(double[] scratch,
                                       double[] bestd,
                                       int[] besti,
                                       int j)
        Find the best in a row of the triangular matrix.
        Parameters:
        scratch - Scratch matrix
        bestd - Best distances cache
        besti - Best indexes cache
        j - Row to update