de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical

Class CLINK<O>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,PointerHierarchyRepresentationResult>

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.SLINK<O>

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.CLINK<O>

Type Parameters:

O - the type of DatabaseObject the algorithm is applied on

All Implemented Interfaces:

Algorithm, HierarchicalClusteringAlgorithm, DistanceBasedAlgorithm<O>

@Reference(authors="D. Defays",
           title="An Efficient Algorithm for the Complete Link Cluster Method",
           booktitle="The Computer Journal 20.4",
           url="https://doi.org/10.1093/comjnl/20.4.364",
           bibkey="DBLP:journals/cj/Defays77")
 @Alias(value="Defays")
public class CLINK<O>
extends SLINK<O>

CLINK algorithm for complete linkage.

This algorithm runs in O(n²) time, and needs only O(n) memory. The results can differ from the standard algorithm in unfavorable ways, and are order-dependent (Defays: "Modifications of the labeling permit us to obtain different minimal superior ultrametric dissimilarities"). Unfortunately, the results are usually perceived to be substantially worse than the more expensive algorithms for complete linkage clustering. This arises from the fact that this algorithm has to add the new object to the existing tree in every step, instead of being able to always do the globally best merge.

Reference:

D. Defays
An Efficient Algorithm for the Complete Link Cluster Method
In: The Computer Journal 20.4

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CLINK.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG The logger for this class.

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
CLINK(DistanceFunction<? super O> distanceFunction) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	clinkstep3(DBIDRef id, DBIDArrayIter i, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m) Third step: Determine the values for P and L
private void	clinkstep4567(DBIDRef id, ArrayDBIDs ids, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m) Fourth to seventh step of CLINK: find best insertion
private void	clinkstep8(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m) Update hierarchy.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected void	process(DBIDRef id, ArrayDBIDs ids, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m) CLINK main loop, based on the SLINK main loop.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.SLINK

getInputTypeRestriction, run

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm

getDistanceFunction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

run

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.HierarchicalClusteringAlgorithm

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

Constructor Detail

CLINK

public CLINK(DistanceFunction<? super O> distanceFunction)

Constructor.

Parameters:

distanceFunction - Distance function

Method Detail

process

protected void process(DBIDRef id,
                       ArrayDBIDs ids,
                       DBIDArrayIter it,
                       int n,
                       WritableDBIDDataStore pi,
                       WritableDoubleDataStore lambda,
                       WritableDoubleDataStore m)

CLINK main loop, based on the SLINK main loop.

Overrides:

process in class SLINK<O>

Parameters:

id - Current object

ids - All objects

it - Array iterator

n - Last object to process at this run

pi - Parent

lambda - Height

m - Distance

clinkstep3

private void clinkstep3(DBIDRef id,
                        DBIDArrayIter i,
                        int n,
                        WritableDBIDDataStore pi,
                        WritableDoubleDataStore lambda,
                        WritableDoubleDataStore m)

Third step: Determine the values for P and L

Parameters:

id - the id of the object to be inserted into the pointer representation

i - Iterator

n - Stopping position

pi - Pi data store

lambda - Lambda data store

m - Distance data store

clinkstep4567

private void clinkstep4567(DBIDRef id,
                           ArrayDBIDs ids,
                           DBIDArrayIter it,
                           int n,
                           WritableDBIDDataStore pi,
                           WritableDoubleDataStore lambda,
                           WritableDoubleDataStore m)

Fourth to seventh step of CLINK: find best insertion

Parameters:

id - Current objct

ids - All objects

it - Iterator

n - Index threshold

pi - Parent data store

lambda - Height data store

m - Distance data store

clinkstep8

private void clinkstep8(DBIDRef id,
                        DBIDArrayIter it,
                        int n,
                        WritableDBIDDataStore pi,
                        WritableDoubleDataStore lambda,
                        WritableDoubleDataStore m)

Update hierarchy.

Parameters:

id - Current object

it - Iterator

n - Last object to process

pi - Parent data store

lambda - Height data store

m - Distance data store

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Overrides:

getLogger in class SLINK<O>

Returns:

the static logger