Class FastPAM1<O>

  • Type Parameters:
    O - vector datatype
    All Implemented Interfaces:
    Algorithm, ClusteringAlgorithm<Clustering<MedoidModel>>, KMedoidsClustering<O>
    Direct Known Subclasses:
    FastPAM

    @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")
    @Priority(-100)
    public class FastPAM1<O>
    extends PAM<O>
    FastPAM1: A version of PAM that is O(k) times faster, i.e., now in O((n-k)²). The change here feels pretty small - we handle all k medoids in parallel using an array. But this means the innermost loop only gets executed in O(1/k) of all iterations, and thus we benefit on average.

    This acceleration gives exactly (assuming perfect numerical accuracy) the same results as the original PAM. For further improvements that can affect the result, see also FastPAM, which is recommended for usage in practice.

    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.
    • Constructor Detail

      • FastPAM1

        public FastPAM1​(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
    • 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 PAM<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 PAM<O>