Package elki.clustering.hierarchical

Class CLINK<O>

java.lang.Object

elki.clustering.hierarchical.SLINK<O>

elki.clustering.hierarchical.CLINK<O>

Type Parameters:

O - the type of DatabaseObject the algorithm is applied on

All Implemented Interfaces:

Algorithm, HierarchicalClusteringAlgorithm

@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("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	Description
static class	CLINK.Par<O>	Parameterization class.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

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

Fields inherited from class elki.clustering.hierarchical.SLINK

distance

Constructor Summary

Constructors

Constructor	Description
CLINK(Distance<? super O> distance)	Constructor.

Method Summary

Modifier and Type	Method	Description
private void	clinkstep3(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)	Update hierarchy.
protected Logging	getLogger()	Get the (static) class logger.
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 elki.clustering.hierarchical.SLINK

convertOutput, getInputTypeRestriction, run

Methods inherited from class java.lang.Object

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

Methods inherited from interface elki.clustering.hierarchical.HierarchicalClusteringAlgorithm

autorun

Field Detail

LOG

private static final Logging LOG

The logger for this class.

Constructor Detail

CLINK

public CLINK(Distance<? super O> distance)

Constructor.

Parameters:

distance - 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(DBIDArrayIter i,
                        int n,
                        WritableDBIDDataStore pi,
                        WritableDoubleDataStore lambda,
                        WritableDoubleDataStore m)

Third step: Determine the values for P and L

Parameters:

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)

Update hierarchy.

Parameters:

id - Current object

it - Iterator

n - Last object to process

pi - Parent data store

lambda - Height data store

getLogger

protected Logging getLogger()

Description copied from class: SLINK

Get the (static) class logger.

Overrides:

getLogger in class SLINK<O>