Class GreedyKCenter<O>

  • Type Parameters:
    O - Object type to cluster
    All Implemented Interfaces:
    Algorithm, ClusteringAlgorithm<Clustering<SimplePrototypeModel<O>>>

    @Title("Greedy K-center Clustering")
    @Reference(authors="T. F. Gonzalez",title="Clustering to Minimize the Maximum Intercluster Distance",booktitle="Theoretical Computer Science, 38",url="https://doi.org/10.1016/0304-3975(85)90224-5",bibkey="DBLP:journals/tcs/Gonzalez85") @Reference(authors="D. S. Hochbaum, D. B. Shmoys",title="A unified approach to approximation algorithms for bottleneck problems",booktitle="Journal of the ACM, 33 (3), 1986",url="https://doi.org/10.1145/5925.5933",bibkey="DBLP:journals/jacm/HochbaumS86")
    public class GreedyKCenter<O>
    extends java.lang.Object
    implements ClusteringAlgorithm<Clustering<SimplePrototypeModel<O>>>
    Greedy algorithm for k-center algorithm also known as Gonzalez clustering, or farthest-first traversal.

    The first cluster center is chosen arbitrarily. The remaining are always chosen such as to maximize the distance to their current cluster.

    Reference:

    T. F. Gonzalez:
    Clustering to Minimize the Maximum Intercluster Distance
    Theoretical Computer Science, 38, 1985

    D. S. Hochbaum, D. B. Shmoys
    A unified approach to approximation algorithms for bottleneck problems
    Journal of the ACM, 33 (3), 1986

    Since:
    0.8.0
    Author:
    Robert Gehde, Erich Schubert
    • Field Detail

      • LOG

        private static final Logging LOG
        Class logger
      • distance

        Distance<? super O> distance
        Distance function
      • k

        int k
        number of clusters
      • rand

        RandomFactory rand
        Random factory for choosing the first element.
    • Constructor Detail

      • GreedyKCenter

        public GreedyKCenter​(int k,
                             Distance<? super O> distance,
                             RandomFactory rand)
        Constructor.
        Parameters:
        k - number of clusters
        distance - distance function to use
        rand - random factory