Package elki.clustering.kcenter
Class GreedyKCenter<O>
- java.lang.Object
-
- elki.clustering.kcenter.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, 1985D. 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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
GreedyKCenter.Par<O>
Parameterization class-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Constructor Summary
Constructors Constructor Description GreedyKCenter(int k, Distance<? super O> distance, RandomFactory rand)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.Clustering<SimplePrototypeModel<O>>
run(Relation<O> relation)
Perform greedy k-center clustering on the relation.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface elki.clustering.ClusteringAlgorithm
autorun
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
Class logger
-
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 clustersdistance
- distance function to userand
- random factory
-
-
Method Detail
-
run
public Clustering<SimplePrototypeModel<O>> run(Relation<O> relation)
Perform greedy k-center clustering on the relation.- Parameters:
relation
- data to cluster- Returns:
- clustering
-
getInputTypeRestriction
public TypeInformation[] getInputTypeRestriction()
Description copied from interface:Algorithm
Get the input type restriction used for negotiating the data query.- Specified by:
getInputTypeRestriction
in interfaceAlgorithm
- Returns:
- Type restriction
-
-