Class AlternateRefinement<O>

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

    @Reference(authors="M. Eug\u00e9nia Captivo",title="Fast primal and dual heuristics for the p-median location problem",booktitle="European Journal of Operational Research 52(1)",url="https://doi.org/10.1016/0377-2217(91)90336-T",bibkey="doi:10.1016/0377-2217(91)90336-T") @Reference(authors="F. E. Maranzana",title="On the location of supply points to minimize transport costs",booktitle="Journal of the Operational Research Society 15.3",url="https://doi.org/10.1057/jors.1964.47",bibkey="doi:10.1057/jors.1964.47")
    public class AlternateRefinement<O>
    extends java.lang.Object
    implements KMedoidsInitialization<O>
    Meta-Initialization for k-medoids by performing one (or many) k-means-style iteration. Such iterations have been used by by Maranzana, Reynolds, and are the core of Park and Jun's approach for k-medoids.

    Captivo is an early author to propose integrating "alternate" into "greedy" for initialization, whereas the others only considered this as an algorithm of its own. But since the quality of this heuristic is much worse than the interchange heuristics, its better suited as initialization. Captivo's method is available as GreedyG. This implementation simply uses the "alternate" heuristic to refine initial medoids obtained by some other heuristic.

    Reference:

    M. Eugénia Captivo
    Fast primal and dual heuristics for the p-median location problem
    European Journal of Operational Research 52(1)

    Since:
    0.8.0
    Author:
    Erich Schubert
    • Field Detail

      • LOG

        private static final Logging LOG
        Class logger.
      • maxiter

        int maxiter
        Maximum number of refinement iterations.
    • Constructor Detail

    • Method Detail

      • findMedoid

        public static boolean findMedoid​(DBIDs ids,
                                         DistanceQuery<?> distQ,
                                         IntegerDataStore assignment,
                                         int j,
                                         DBIDArrayMIter miter,
                                         double[] cost)
        Find the best medoid of a given fixed set.
        Parameters:
        ids - Object ids
        distQ - Distance query
        assignment - Cluster assignment
        j - Cluster number
        miter - Medoid iterator, pointing to the current medoid (modified)
        cost - Prior cost, of the current assignment / cost[j] is output
        Returns:
        true if the medoid changed.
      • assignToNearestCluster

        public static double assignToNearestCluster​(DBIDArrayIter miter,
                                                    DBIDs ids,
                                                    DistanceQuery<?> distQ,
                                                    WritableIntegerDataStore assignment,
                                                    double[] cost)
        Compute the initial cluster assignment.
        Parameters:
        miter - Medoids iterator
        ids - All objects
        distQ - Distance query
        assignment - Output: clusters
        cost - Output: cost per cluster
        Returns:
        Cost (and "clusters" is changed)