Package elki.clustering.hierarchical

Class MiniMax.Instance

java.lang.Object

elki.clustering.hierarchical.AGNES.Instance

elki.clustering.hierarchical.MiniMax.Instance

Direct Known Subclasses:

MiniMaxAnderberg.Instance, MiniMaxNNChain.Instance

Enclosing class:

MiniMax<O>

public static class MiniMax.Instance
extends AGNES.Instance

Main worker instance of MiniMax.

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field	Description
protected it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs>	clusters	Map to cluster members
protected DistanceQuery<?>	dq	Distance query function
protected DBIDArrayIter	ix	Iterators into the object ids.
protected DBIDArrayIter	iy	Iterators into the object ids.
protected DBIDArrayMIter	protiter	Iterator into prototype cache

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

builder, end, linkage, mat

Constructor Summary

Constructors

Constructor	Description
Instance()	Constructor.

Method Summary

Modifier and Type	Method	Description
private static double	findMax(DistanceQuery<?> dq, DBIDIter i, DBIDs cy, double maxDist, double minMaxDist)	Find the maximum distance of one object to a set.
protected int	findMerge()	Perform the next merge step in AGNES.
private static double	findPrototype(DistanceQuery<?> dq, DBIDs cx, DBIDs cy, DBIDVar prototype, double minMaxDist)	Find the prototypes.
private static double	findPrototypeSingleton(DistanceQuery<?> dq, DBIDs cx, DBIDRef cy, DBIDVar prototype)	Find the prototypes.
protected void	merge(int x, int y)	Merges two clusters given by x, y, their points with smallest IDs, and y to keep
ClusterMergeHistory	run(ClusterDistanceMatrix mat, ClusterMergeHistoryBuilder builder)	Run the main algorithm.
ClusterPrototypeMergeHistory	run(ArrayDBIDs ids, ClusterDistanceMatrix mat, ClusterMergeHistoryBuilder builder, DistanceQuery<?> dq, DBIDArrayMIter prots)
protected void	updateEntry(int x, int y)	Update entry at x,y for distance matrix distances
protected void	updateMatrices(int c)	Update the entries of the matrices that contain a distance to c, the newly merged cluster.

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

merge, shrinkActiveSet, updateMatrix

Methods inherited from class java.lang.Object

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

Field Detail

clusters

protected it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters

Map to cluster members

protiter

protected DBIDArrayMIter protiter

Iterator into prototype cache

dq

protected DistanceQuery<?> dq

Distance query function

ix

protected DBIDArrayIter ix

Iterators into the object ids.

iy

protected DBIDArrayIter iy

Iterators into the object ids.

Constructor Detail

Instance

public Instance()

Constructor.

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

run

public ClusterPrototypeMergeHistory run(ArrayDBIDs ids,
                                        ClusterDistanceMatrix mat,
                                        ClusterMergeHistoryBuilder builder,
                                        DistanceQuery<?> dq,
                                        DBIDArrayMIter prots)

findMerge

protected int findMerge()

Description copied from class: AGNES.Instance

Perform the next merge step in AGNES.

Overrides:

findMerge in class AGNES.Instance

Returns:

the index that has disappeared, for shrinking the working set

merge

protected void merge(int x,
                     int y)

Merges two clusters given by x, y, their points with smallest IDs, and y to keep

Parameters:

x - first cluster to merge

y - second cluster to merge

updateMatrices

protected void updateMatrices(int c)

Update the entries of the matrices that contain a distance to c, the newly merged cluster.

Parameters:

c - the cluster to update distances to

updateEntry

protected void updateEntry(int x,
                           int y)

Update entry at x,y for distance matrix distances

Parameters:

x - index of cluster, x > y

y - index of cluster, y < x

findPrototype

private static double findPrototype(DistanceQuery<?> dq,
                                    DBIDs cx,
                                    DBIDs cy,
                                    DBIDVar prototype,
                                    double minMaxDist)

Find the prototypes.

Parameters:

dq - Distance query

cx - First set

cy - Second set

prototype - Prototype output variable

minMaxDist - Previously best distance.

Returns:

New best distance

findPrototypeSingleton

private static double findPrototypeSingleton(DistanceQuery<?> dq,
                                             DBIDs cx,
                                             DBIDRef cy,
                                             DBIDVar prototype)

Find the prototypes.

Parameters:

dq - Distance query

cx - First set

cy - Singleton object

prototype - Prototype output variable

Returns:

New best distance

findMax

private static double findMax(DistanceQuery<?> dq,
                              DBIDIter i,
                              DBIDs cy,
                              double maxDist,
                              double minMaxDist)

Find the maximum distance of one object to a set.

Parameters:

dq - Distance query

i - Current object

cy - Set of candidates

maxDist - Known maximum to others

minMaxDist - Early stopping threshold

Returns:

Maximum distance