fastcluster.h File Reference

Go to the source code of this file.

Enumerations
enum	hclust_fast_methods {   HCLUST_METHOD_SINGLE = 0 , HCLUST_METHOD_COMPLETE = 1 , HCLUST_METHOD_AVERAGE = 2 , HCLUST_METHOD_MEDIAN = 3 ,   HCLUST_METHOD_SVF_BEST = 4 }

Functions
void	cutree_k (int n, const int *merge, int nclust, int *labels)
void	cutree_cdist (int n, const int *merge, double *height, double cdist, int *labels)
int	hclust_fast (int n, double *distmat, int method, int *merge, double *height)

Enumeration Type Documentation

hclust_fast_methods

enum hclust_fast_methods

Enumerator
HCLUST_METHOD_SINGLE
HCLUST_METHOD_COMPLETE
HCLUST_METHOD_AVERAGE
HCLUST_METHOD_MEDIAN
HCLUST_METHOD_SVF_BEST

Definition at line 65 of file fastcluster.h.

{
    // single link with the minimum spanning tree algorithm (Rohlf, 1973)
    HCLUST_METHOD_SINGLE = 0,
    // complete link with the nearest-neighbor-chain algorithm (Murtagh, 1984)
    HCLUST_METHOD_COMPLETE = 1,
    // complete link with the nearest-neighbor-chain algorithm (Murtagh, 1984)
    HCLUST_METHOD_AVERAGE = 2,
    // median link with the generic algorithm (Müllner, 2011)
    HCLUST_METHOD_MEDIAN = 3,
    // To indicate to try all methods and pick the best.
    HCLUST_METHOD_SVF_BEST = 4
};

Function Documentation

cutree_cdist()

void cutree_cdist	(	int	n,
		const int *	merge,
		double *	height,
		double	cdist,
		int *	labels
	)

Definition at line 116 of file fastcluster.cpp.

{
 
    int k;
 
    for (k=0; k<(n-1); k++)
    {
        if (height[k] >= cdist)
        {
            break;
        }
    }
    cutree_k(n, merge, n-k, labels);
}

cutree_k()

void cutree_k	(	int	n,
		const int *	merge,
		int	nclust,
		int *	labels
	)

Definition at line 37 of file fastcluster.cpp.

{
 
    int k,m1,m2,j,l;
 
    if (nclust > n || nclust < 2)
    {
        for (j=0; j<n; j++) labels[j] = 0;
        return;
    }
 
    // assign to each observable the number of its last merge step
    // beware: indices of observables in merge start at 1 (R convention)
    std::vector<int> last_merge(n, 0);
    for (k=1; k<=(n-nclust); k++)
    {
        // (m1,m2) = merge[k,]
        m1 = merge[k-1];
        m2 = merge[n-1+k-1];
        if (m1 < 0 && m2 < 0)   // both single observables
        {
            last_merge[-m1-1] = last_merge[-m2-1] = k;
        }
        else if (m1 < 0 || m2 < 0)   // one is a cluster
        {
            if(m1 < 0)
            {
                j = -m1;
                m1 = m2;
            }
            else j = -m2;
            // merging single observable and cluster
            for(l = 0; l < n; l++)
                if (last_merge[l] == m1)
                    last_merge[l] = k;
            last_merge[j-1] = k;
        }
        else   // both cluster
        {
            for(l=0; l < n; l++)
            {
                if( last_merge[l] == m1 || last_merge[l] == m2 )
                    last_merge[l] = k;
            }
        }
    }
 
    // assign cluster labels
    int label = 0;
    std::vector<int> z(n,-1);
    for (j=0; j<n; j++)
    {
        if (last_merge[j] == 0)   // still singleton
        {
            labels[j] = label++;
        }
        else
        {
            if (z[last_merge[j]] < 0)
            {
                z[last_merge[j]] = label++;
            }
            labels[j] = z[last_merge[j]];
        }
    }
}

hclust_fast()

int hclust_fast	(	int	n,
		double *	distmat,
		int	method,
		int *	merge,
		double *	height
	)

Definition at line 156 of file fastcluster.cpp.

{
 
    // call appropriate clustering function
    cluster_result Z2(n-1);
    if (method == HCLUST_METHOD_SINGLE)
    {
        // single link
        MST_linkage_core(n, distmat, Z2);
    }
    else if (method == HCLUST_METHOD_COMPLETE)
    {
        // complete link
        NN_chain_core<METHOD_METR_COMPLETE, t_float>(n, distmat, NULL, Z2);
    }
    else if (method == HCLUST_METHOD_AVERAGE)
    {
        // best average distance
        double* members = new double[n];
        for (int i=0; i<n; i++) members[i] = 1;
        NN_chain_core<METHOD_METR_AVERAGE, t_float>(n, distmat, members, Z2);
        delete[] members;
    }
    else if (method == HCLUST_METHOD_MEDIAN)
    {
        // best median distance (beware: O(n^3))
        generic_linkage<METHOD_METR_MEDIAN, t_float>(n, distmat, NULL, Z2);
    }
    else
    {
        return 1;
    }
 
    int* order = new int[n];
    if (method == HCLUST_METHOD_MEDIAN)
    {
        generate_R_dendrogram<true>(merge, height, order, Z2, n);
    }
    else
    {
        generate_R_dendrogram<false>(merge, height, order, Z2, n);
    }
 
    delete[] order; // only needed for visualization
 
    return 0;
}