Package elki.clustering.kmedoids.initialization

Class AlternateRefinement<O>

java.lang.Object

elki.clustering.kmedoids.initialization.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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	AlternateRefinement.Par<O>	Parameterization class.

Field Summary

Fields

Modifier and Type	Field	Description
private KMedoidsInitialization<O>	inner	Inner initialization.
private static Logging	LOG	Class logger.
(package private) int	maxiter	Maximum number of refinement iterations.

Constructor Summary

Constructors

Constructor	Description
AlternateRefinement(KMedoidsInitialization<O> inner, int maxiter)	Constructor.

Method Summary

Modifier and Type	Method	Description
static double	assignToNearestCluster(DBIDArrayIter miter, DBIDs ids, DistanceQuery<?> distQ, WritableIntegerDataStore assignment, double[] cost)	Compute the initial cluster assignment.
DBIDs	chooseInitialMedoids(int k, DBIDs ids, DistanceQuery<? super O> distQ)	Choose initial means
static boolean	findMedoid(DBIDs ids, DistanceQuery<?> distQ, IntegerDataStore assignment, int j, DBIDArrayMIter miter, double[] cost)	Find the best medoid of a given fixed set.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LOG

private static final Logging LOG

Class logger.

inner

private KMedoidsInitialization<O> inner

Inner initialization.

maxiter

int maxiter

Maximum number of refinement iterations.

Constructor Detail

AlternateRefinement

public AlternateRefinement(KMedoidsInitialization<O> inner,
                           int maxiter)

Constructor.

Method Detail

chooseInitialMedoids

public DBIDs chooseInitialMedoids(int k,
                                  DBIDs ids,
                                  DistanceQuery<? super O> distQ)

Description copied from interface: KMedoidsInitialization

Choose initial means

Specified by:

chooseInitialMedoids in interface KMedoidsInitialization<O>

Parameters:

k - Parameter k

ids - Candidate IDs.

distQ - Distance function

Returns:

List of chosen means for k-means

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)