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

Class AnderbergHierarchicalClustering<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.AnderbergHierarchicalClustering<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm, HierarchicalClusteringAlgorithm, DistanceBasedAlgorithm<O>

@Reference(authors="M. R. Anderberg",
           title="Hierarchical Clustering Methods",
           booktitle="Cluster Analysis for Applications")
public class AnderbergHierarchicalClustering<O>
extends AbstractDistanceBasedAlgorithm<O,PointerHierarchyRepresentationResult>
implements HierarchicalClusteringAlgorithm

This is a modification of the classic AGNES algorithm for hierarchical clustering using a nearest-neighbor heuristic for acceleration. Instead of scanning the matrix (with cost O(n^2)) to find the minimum, the nearest neighbor of each object is remembered. On the downside, we need to check these values at every merge, and it may now cost O(n^2) to perform a merge, so there is no worst-case advantage to this approach. The average case however improves from O(n^3) to O(n^2), which yields a considerable improvement in running time. This optimization is attributed to M. R. Anderberg. Reference:

M. R. Anderberg
Hierarchical Clustering Methods
Cluster Analysis for Applications
ISBN: 0120576503

Author:

Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
(package private) LinkageMethod	linkage Current linkage method in use.
private static Logging	LOG Class logger

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
AnderbergHierarchicalClustering(DistanceFunction<? super O> distanceFunction, LinkageMethod linkage) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	findBest(int size, double[] scratch, double[] bestd, int[] besti, int j)
protected int	findMerge(int size, double[] scratch, DBIDArrayIter ix, DBIDArrayIter iy, double[] bestd, int[] besti, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableIntegerDataStore csize) Perform the next merge step.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private static void	initializeNNCache(double[] scratch, double[] bestd, int[] besti) Initialize the NN cache.
protected void	merge(int size, double[] scratch, DBIDArrayIter ix, DBIDArrayIter iy, double[] bestd, int[] besti, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableIntegerDataStore csize, double mindist, int x, int y) Execute the cluster merge.
PointerHierarchyRepresentationResult	run(Database db, Relation<O> relation) Run the algorithm
private void	updateCache(int size, double[] scratch, double[] bestd, int[] besti, int x, int y, int j, double d) Update the cache.
protected void	updateMatrix(int size, double[] scratch, DBIDArrayIter ij, double[] bestd, int[] besti, WritableDoubleDataStore lambda, WritableIntegerDataStore csize, double mindist, int x, int y, int sizex, int sizey) Update the scratch distance matrix.

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

getDistanceFunction

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

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

Class logger

linkage

LinkageMethod linkage

Current linkage method in use.

Constructor Detail

AnderbergHierarchicalClustering

public AnderbergHierarchicalClustering(DistanceFunction<? super O> distanceFunction,
                               LinkageMethod linkage)

Constructor.

Parameters:

distanceFunction - Distance function to use

linkage - Linkage method

Method Detail

run

public PointerHierarchyRepresentationResult run(Database db,
                                       Relation<O> relation)

Run the algorithm

Parameters:

db - Database

relation - Relation

Returns:

Clustering hierarchy

initializeNNCache

private static void initializeNNCache(double[] scratch,
                     double[] bestd,
                     int[] besti)

Initialize the NN cache.

Parameters:

scratch - Scatch space

bestd - Best distance

besti - Best index

findMerge

protected int findMerge(int size,
            double[] scratch,
            DBIDArrayIter ix,
            DBIDArrayIter iy,
            double[] bestd,
            int[] besti,
            WritableDBIDDataStore pi,
            WritableDoubleDataStore lambda,
            WritableIntegerDataStore csize)

Perform the next merge step. Due to the cache, this is now O(n) each time, instead of O(n*n).

Parameters:

size - Data set size

scratch - Scratch space.

ix - First iterator

iy - Second iterator

bestd - Best distance

besti - Index of best distance

pi - Parent storage

lambda - Lambda (join distance) storage

csize - Cluster sizes

Returns:

x, for shrinking the working set.

merge

protected void merge(int size,
         double[] scratch,
         DBIDArrayIter ix,
         DBIDArrayIter iy,
         double[] bestd,
         int[] besti,
         WritableDBIDDataStore pi,
         WritableDoubleDataStore lambda,
         WritableIntegerDataStore csize,
         double mindist,
         int x,
         int y)

Execute the cluster merge.

Parameters:

size - Data set size

scratch - Scratch space.

ix - First iterator

iy - Second iterator

bestd - Best distance

besti - Index of best distance

pi - Parent storage

lambda - Lambda (join distance) storage

csize - Cluster sizes

mindist - Distance that was used for merging

x - First matrix position

y - Second matrix position

updateMatrix

protected void updateMatrix(int size,
                double[] scratch,
                DBIDArrayIter ij,
                double[] bestd,
                int[] besti,
                WritableDoubleDataStore lambda,
                WritableIntegerDataStore csize,
                double mindist,
                int x,
                int y,
                int sizex,
                int sizey)

Update the scratch distance matrix.

Parameters:

size - Data set size

scratch - Scratch matrix.

ij - Iterator to reuse

bestd - Best distance

besti - Index of best distance

lambda - Lambda (join distance) storage

csize - Cluster sizes

mindist - Distance that was used for merging

x - First matrix position

y - Second matrix position

sizex - Old size of first cluster

sizey - Old size of second cluster

updateCache

private void updateCache(int size,
               double[] scratch,
               double[] bestd,
               int[] besti,
               int x,
               int y,
               int j,
               double d)

Update the cache.

Parameters:

size - Working set size

scratch - Scratch matrix

bestd - Best distance

besti - Best index

x - First cluster

y - Second cluster, y < x

j - Updated value d(y, j)

d - New distance

findBest

protected void findBest(int size,
            double[] scratch,
            double[] bestd,
            int[] besti,
            int j)

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<PointerHierarchyRepresentationResult>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<PointerHierarchyRepresentationResult>

Returns:

the static logger