GreedyKCenter (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

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, 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

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

Field Summary

Fields
Modifier and Type	Field	Description
`(package private) Distance<? super O>`	`distance`	Distance function
`(package private) int`	`k`	number of clusters
`private static Logging`	`LOG`	Class logger
`(package private) RandomFactory`	`rand`	Random factory for choosing the first element.

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
  - 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
- 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 interface Algorithm
    
    Returns:
    
    Type restriction