Package elki.clustering.hierarchical

Class Anderberg.Instance

java.lang.Object

elki.clustering.hierarchical.AGNES.Instance

elki.clustering.hierarchical.Anderberg.Instance

Direct Known Subclasses:

HACAM.Instance

Enclosing class:

Anderberg<O>

public static class Anderberg.Instance
extends AGNES.Instance

Main worker instance of Anderberg's algorithm.

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field	Description
protected double[]	bestd	Cache: best distance
protected int[]	besti	Cache: index of best distance

Fields inherited from class elki.clustering.hierarchical.AGNES.Instance

builder, end, linkage, mat

Constructor Summary

Constructors

Constructor	Description
Instance(Linkage linkage)	Constructor.

Method Summary

Modifier and Type	Method	Description
protected static void	findBest(double[] scratch, double[] bestd, int[] besti, int j)	Find the best in a row of the triangular matrix.
protected int	findMerge()	Perform the next merge step.
protected static void	initializeNNCache(double[] scratch, double[] bestd, int[] besti)	Initialize the NN cache.
protected void	merge(double mindist, int x, int y)	Execute the cluster merge.
ClusterMergeHistory	run(ClusterDistanceMatrix mat, ClusterMergeHistoryBuilder builder)	Run the main algorithm.
protected static void	updateCache(double[] scratch, double[] bestd, int[] besti, int x, int y, int j, double d)	Update the cache.
protected void	updateMatrix(double mindist, int x, int y, int sizex, int sizey)	Update the scratch distance matrix.

Methods inherited from class elki.clustering.hierarchical.AGNES.Instance

shrinkActiveSet

Methods inherited from class java.lang.Object

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

Field Detail

bestd

protected double[] bestd

Cache: best distance

besti

protected int[] besti

Cache: index of best distance

Constructor Detail

Instance

public Instance(Linkage linkage)

Constructor.

Parameters:

linkage - Linkage method

Method Detail

run

public ClusterMergeHistory run(ClusterDistanceMatrix mat,
                               ClusterMergeHistoryBuilder builder)

Description copied from class: AGNES.Instance

Run the main algorithm.

Overrides:

run in class AGNES.Instance

Parameters:

mat - Distance matrix

builder - Result builder

Returns:

Cluster history

initializeNNCache

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

Initialize the NN cache.

Parameters:

scratch - Scratch space

bestd - Best distance

besti - Best index

findMerge

protected int findMerge()

Perform the next merge step.

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

Overrides:

findMerge in class AGNES.Instance

Returns:

x, for shrinking the working set.

merge

protected void merge(double mindist,
                     int x,
                     int y)

Description copied from class: AGNES.Instance

Execute the cluster merge.

Overrides:

merge in class AGNES.Instance

Parameters:

mindist - Distance that was used for merging

x - First matrix position

y - Second matrix position

updateMatrix

protected void updateMatrix(double mindist,
                            int x,
                            int y,
                            int sizex,
                            int sizey)

Description copied from class: AGNES.Instance

Update the scratch distance matrix.

Overrides:

updateMatrix in class AGNES.Instance

Parameters:

mindist - Minimum distance

x - First matrix position

y - Second matrix position

sizex - Old size of first cluster

sizey - Old size of second cluster

updateCache

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

Update the cache.

Parameters:

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 static void findBest(double[] scratch,
                               double[] bestd,
                               int[] besti,
                               int j)

Find the best in a row of the triangular matrix.

Parameters:

scratch - Scratch matrix

bestd - Best distances cache

besti - Best indexes cache

j - Row to update