File Exchange

image thumbnail

Graph Agglomerative Clustering (GAC) toolbox

version (117 KB) by Wayne Zhang
A better alternative to conventional algorithms, such as k-means, spectral clustering and linkage


Updated 01 Jul 2019

From GitHub

View Version History

View license on GitHub

Gactoolbox is a summary of our research of agglomerative clustering on a graph. Agglomerative clustering, which iteratively merges small clusters, is commonly used for clustering because it is conceptually simple and produces a hierarchy of clusters. Classical agglomerative clustering algorithms, such as average linkage and DBSCAN, were widely used in many areas. Those algorithms, however, are not designed for clustering on a graph. This toolbox implements the following algorithms for agglomerative clustering on a directly graph.
1) Structural descriptor based algorithms (gacCluster.m). We define a cluster descriptor based on the graph structure, and each merging is determined by maximizes the increment of the descriptor. Two descriptors, including zeta function and path integral, are implemented. You can also design new descriptor (creating functions similar to gacPathEntropy.m and gacPathCondEntropy.m) and develop new algorithms with our code.
2) Graph degree linkage (gdlCluster.m). It is a simple and effective algorithm, with better performance than normalized cuts and spectral clustering, and is faster.

Cite As

W. Zhang, X. Wang, D. Zhao, and X. Tang. Graph Degree Linkage: Agglomerative Clustering on a Directed Graph. ECCV 2012.

W. Zhang, D. Zhao, and X. Wang. Agglomerative clustering via maximum incremental path integral. Pattern Recognition, 46 (11): 3056-3065, 2013.

Comments and Ratings (15)

serg sh

mex -O gacOnelink_c.cpp
Building with 'g++'.
Error using mex /waynezhanghk-gactoolbox-53508ce/gdlfiles/gacOnelink_c.cpp: In function ‘void mexFunction(int, mxArray**, int, const mxArray**)’:




On the newer version of Xcode and g++ or clang++ (C++ 11), you should change certain lines to cast : {static_cast<int>(outputClusters.size())}



In the implementation, should we feed a dense graphW matrix other than a sparse matrix? Since there is a lot of zeros if the graph is constructed by the knn strategy, full(graphW) will waste a lot of storage...

Wayne Zhang

Please check out latest version at github which supports compiling mex files in linux.

Jing Shao

Thanks for the code. BTW, I find that in your algorithm, the group number must be determined, but not adaptive, like meanshift, right? Could you please give me some suggestions to improve your algorithm if I can not provide a determined group number? Thank you very much.

Wayne Zhang

@Gerard: you can record the merging in each iteration to get dendogram (in gdlMerging_c.m). I didn't implement that but it should be simple to add.

Gerard Sanromà

Thanks for the code. Is there any way of obtaining the dendogram of the whole merging process ?

Wayne Zhang

@Ben: there's an example included in readme.txt
it's simple, you only need to compute distance_matrix by yourself. E.g., you can download MNIST data from the link in my paper, and compute Euclidean distance matrix. distance_matrix is n x n if there're n samples. groupNumber is number of clusters. K is for K-NN graph.



Could you provide even a very simple example of how to use your code? That would be appreciated!

Wayne Zhang

@Tallha Akram: will post some example in the future. can u post your error message?

Tallha Akram

Can you please give some sample code, i have used distance matrix from spectral clustering, but only got an error.

MATLAB Release Compatibility
Created with R2010a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!