Class LAB<O>

  • Type Parameters:
    O - Object type for KMedoids initialization
    All Implemented Interfaces:
    KMeansInitialization, KMedoidsInitialization<O>

    @Reference(authors="Erich Schubert, Peter J. Rousseeuw",
               title="Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms",
               booktitle="Proc. 12th Int. Conf. Similarity Search and Applications (SISAP\'2019)",
               url="https://doi.org/10.1007/978-3-030-32047-8_16",
               bibkey="DBLP:conf/sisap/SchubertR19")
    public class LAB<O>
    extends java.lang.Object
    implements KMeansInitialization, KMedoidsInitialization<O>
    Linear approximative BUILD (LAB) initialization for FastPAM (and k-means).

    This is a O(nk) aproximation of the original PAM BUILD. For performance, it uses an O(sqrt(n)) sample to achieve linear run time. The results will be worse than those of BUILD, but provide a good starting point for FastPAM optimization.

    Reference:

    Erich Schubert, Peter J. Rousseeuw
    Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms
    Proc. 12th Int. Conf. Similarity Search and Applications (SISAP'2019)

    Since:
    0.7.5
    Author:
    Erich Schubert
    • Constructor Detail

      • LAB

        public LAB​(RandomFactory rnd)
        Constructor.
        Parameters:
        rnd - Random generator
    • Method Detail

      • getMinDist

        protected static double getMinDist​(DBIDArrayIter j,
                                           DistanceQuery<?> distQ,
                                           DBIDArrayIter mi,
                                           WritableDoubleDataStore mindist)
        Get the minimum distance to previous medoids.
        Parameters:
        j - current object
        distQ - distance query
        mi - medoid iterator
        mindist - distance storage
        Returns:
        minimum distance
      • shuffle

        private static void shuffle​(ArrayModifiableDBIDs ids,
                                    int ssize,
                                    int end,
                                    java.util.Random random)
        Partial Fisher-Yates shuffle.
        Parameters:
        ids - IDs to shuffle
        ssize - sample size to generate
        end - Valid range
        random - Random generator