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.
-
Constructor Summary
Constructors Constructor Description AlternateRefinement(KMedoidsInitialization<O> inner, int maxiter)
Constructor.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods 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 meansstatic boolean
findMedoid(DBIDs ids, DistanceQuery<?> distQ, IntegerDataStore assignment, int j, DBIDArrayMIter miter, double[] cost)
Find the best medoid of a given fixed set.
-
-
-
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 interfaceKMedoidsInitialization<O>
- Parameters:
k
- Parameter kids
- 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 idsdistQ
- Distance queryassignment
- Cluster assignmentj
- Cluster numbermiter
- 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 iteratorids
- All objectsdistQ
- Distance queryassignment
- Output: clusterscost
- Output: cost per cluster- Returns:
- Cost (and "clusters" is changed)
-
-