jminhep.algorithms

Class HierarchicalAlg

java.lang.Object

jminhep.algorithms.HierarchicalAlg

public class HierarchicalAlg
extends java.lang.Object

Carry out pairwise agglomerations. For n items, therefore there are n-1 agglomerations. Represent the cluster labels is an nxn cluster label matrix. Column no. n will be the singleton labels, 1 to n. Column no. n-1 will have n-1 unique values (or label sequence numbers). Column no. n-2 will have n-2 unique values. Column no. 1 will have the value 1 only, implying that all n items are in one cluster.

ClustMat is our agglomeration "engine". It looks after labeling only, and is independent of any agglomerative clustering criterion.

Other utility methods:

Dissim ... calculate dissimilarity matrix
getNNs ... get nearest neighbors and associated nearest neighbor dissimilarities
getSpaces ... helping in output formating
printMatrix ... print matrix of doubles, or integers
printVect ... print vector of doubles, or integers

main does the following:

1. Calculate pairwise dissimilarities, and determines nearest neighbors and corresponding dissimilarities. (Squared Euclidean distance used.)
2. Determines the closest nearest neighbors.
3. Carries out an agglomeration in ClustMat.
4. Updates the pairwise dissimilarity matrix, and then, on the basis of this, the nearest neighbors, and the nearest neighbor dissimilarities.
5. Repeats while no. of clusters is greater than 2.

Constant MAXVAL is used in, resp., dissimilarities and nearest neighbor dissimilarities, to indicate when items are processed and no longer exist as singletons.
Note also how flag = 1 denotes an active observation, and flag = 0 denotes an inactive one (since it has been agglomerated). It is not necessary to use the flag since exceptionally high dissimilarities will signify inactive observations. However the use of flag is helpful computationally.

Step 5 here determines the agglomerative clustering criterion. We are currently using the minimum variance method. It is indicated in the code where to change to use other agglomerative criteria.

Output cluster labels using original sequence numbers. The ordering of observations is not such that a dendrogram can be directly constructed. However the cluster labels do allow selections and further inter and intra cluster processing of the input data.

Field Summary

Fields

Modifier and Type	Field and Description
static double	MAXVAL

Constructor Summary

Constructors

Constructor and Description
HierarchicalAlg(DataHolder data) Build a hierarchical algorithm.

Method Summary

Modifier and Type	Method and Description
static double[][]	calcDissim(int nrow, int ncol, double[] mass, double[][] A) Method Dissim, calculates dissimilarity n x n array
static void	calClustMat(int nrow, int[][] clusters, int clust1, int clust2, int ncl) Method ClustMat, updates cluster structure matrix following an agglomeration
DataHolder	getCenters() Returns cluster centers
int	getClusters() Get number of clusters
double	getCompactness() This method returns the Compactness and Separation measure of cluster validity (see Fuzzy Algorithms With Applications to Image Processing and Pattern Recognition, Zheru Chi, Hong Yan, Tuan Pham, World Scientific, pp.
int	getError() Get error: 0 looks OK
java.lang.String	getName() Get description
static void	getNNs(int nrow, int[] flag, double[][] diss, int[] nn, double[] nndiss) Method getNNs, determine NNs and NN dissimilarities
int[]	getNumberPoints() Returns the number of points in each cluster
void	getResult() Get cluster results (should be called after run method)
static java.lang.String	getSpaces(int n)
void	run()
void	runBest()
void	setClusters(int N) Sets number of clusters

Methods inherited from class java.lang.Object

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

Field Detail

MAXVAL

public static final double MAXVAL

See Also:

Constant Field Values

Constructor Detail

HierarchicalAlg

public HierarchicalAlg(DataHolder data)

Build a hierarchical algorithm.

Parameters:

data - input data

Method Detail

getError

public int getError()

Get error: 0 looks OK

Returns:

int

getCompactness

public double getCompactness()

This method returns the Compactness and Separation measure of cluster validity (see Fuzzy Algorithms With Applications to Image Processing and Pattern Recognition, Zheru Chi, Hong Yan, Tuan Pham, World Scientific, pp. 93)

setClusters

public void setClusters(int N)

Sets number of clusters

Parameters:

N - int - number of clusters

getClusters

public int getClusters()

Get number of clusters

Returns:

clusters

getResult

public void getResult()

Get cluster results (should be called after run method)

getCenters

public DataHolder getCenters()

Returns cluster centers

Returns:

DataHolder with cluster centers

getNumberPoints

public int[] getNumberPoints()

Returns the number of points in each cluster

Returns:

int[] getNumberPoints

calcDissim

public static double[][] calcDissim(int nrow,
                                    int ncol,
                                    double[] mass,
                                    double[][] A)

Method Dissim, calculates dissimilarity n x n array

Parameters:

nrow - integer row dimension

ncol - integer column dimension

A - floating row/column matrix

Returns:

Adiss floating n x n dissimilarity array

getNNs

public static void getNNs(int nrow,
                          int[] flag,
                          double[][] diss,
                          int[] nn,
                          double[] nndiss)

Method getNNs, determine NNs and NN dissimilarities

Parameters:

nrow - row dimension or number of observations (input)

flag - =1 for active observation, = 0 for inactive one (input)

diss - dissimilarity matrix (input)

nn - nearest neighbor sequence number (calculated)

nndiss - nearest neigbor dissimilarity (calculated)

calClustMat

public static void calClustMat(int nrow,
                               int[][] clusters,
                               int clust1,
                               int clust2,
                               int ncl)

Method ClustMat, updates cluster structure matrix following an agglomeration

Parameters:

nrow - row dimension or number of observations (input)

clusters - list of agglomerations, stored as array of pairs of cluster sequence numbers (input, and updated)

clust1 - first agglomerand (input)

clust2 - second agglomerand (input)

ncl - number of clusters remaining (input)

getSpaces

public static java.lang.String getSpaces(int n)

run

public void run()

runBest

public void runBest()

getName

public java.lang.String getName()

Get description

Returns:

String