Package elki.clustering.kmedoids

Class FastPAM<O>

  • Type Parameters:
    O - vector datatype
    All Implemented Interfaces:
    Algorithm, ClusteringAlgorithm<Clustering<MedoidModel>>, KMedoidsClustering<O>
    Direct Known Subclasses:
    FastCLARA, FasterPAM
    @Priority(102)
@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 FastPAM<O>
extends FastPAM1<O>
    FastPAM: An improved version of PAM, that is usually O(k) times faster. This class incorporates the benefits of FastPAM1, but in addition it tries to perform multiple swaps in each iteration (FastPAM2), which can reduce the total number of iterations needed substantially for large k, if some areas of the data are largely independent.

    There is a tolerance parameter, which controls how many additional swaps are performed. When set to 0, it will only execute an additional swap if it appears to be independent (i.e., the improvements resulting from the swap have not decreased when the first swap was executed). We suggest to rather leave it at the default of 1, which means to perform any additional swap that gives an improvement. We could not observe a tendency to find worse results when doing these additional swaps, but a reduced runtime.

    Because of the speed benefits, we also suggest to use a linear-time initialization, such as the k-means++ initialization or the proposed LAB (linear approximative BUILD, the third component of FastPAM) initialization, and try multiple times if the runtime permits.

    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

    • Field Detail

      • LOG

        private static final Logging LOG
        The logger for this class.

      • KEY

        private static final java.lang.String KEY
        Key for statistics logging.

      • fasttol

        protected double fasttol
        Tolerance for fast swapping behavior (may perform worse swaps).

    • Constructor Detail

      • FastPAM

        public FastPAM​(Distance<? super O> distance,
               int k,
               int maxiter,
               KMedoidsInitialization<O> initializer)
        Constructor.
        Parameters:
        distance - distance function
        k - k parameter
        maxiter - Maxiter parameter
        initializer - Function to generate the initial means

      • FastPAM

        public FastPAM​(Distance<? super O> distance,
               int k,
               int maxiter,
               KMedoidsInitialization<O> initializer,
               double fasttol)
        Constructor.
        Parameters:
        distance - distance function
        k - k parameter
        maxiter - Maxiter parameter
        initializer - Function to generate the initial means
        fasttol - Tolerance for fast swapping

    • Method Detail

      • run

        public Clustering<MedoidModel> run​(Relation<O> relation,
                                   int k,
                                   DistanceQuery<? super O> distQ)
        Description copied from interface: KMedoidsClustering
        Run k-medoids clustering with a given distance query.
        Not a very elegant API, but needed for some types of nested k-medoids.
        Specified by:
        run in interface KMedoidsClustering<O>
        Overrides:
        run in class FastPAM1<O>
        Parameters:
        relation - relation to use
        k - Number of clusters
        distQ - Distance query to use
        Returns:
        result

      • getLogger

        protected Logging getLogger()
        Description copied from class: PAM
        Get the static class logger.
        Overrides:
        getLogger in class FastPAM1<O>