File Exchange

image thumbnail

Graph Agglomerative Clustering (GAC) toolbox

version 1.4 (85.9 KB) by

A better alternative to conventional algorithms, such as k-means, spectral clustering and linkage

31 Downloads

Updated

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.

Comments and Ratings (14)

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**)’:

sandberry

Thanks

Amir

Amir (view profile)

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

lei

lei (view profile)

Ling

Ling (view profile)

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...

Wei Zhang

Wei Zhang (view profile)

Please check out latest version at github which supports compiling mex files in linux.
https://github.com/waynezhanghk/gactoolbox

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.

Wei Zhang

Wei Zhang (view profile)

@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.

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

Wei Zhang

Wei Zhang (view profile)

@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.

om

om (view profile)

Ben

Ben (view profile)

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

Wei Zhang

Wei Zhang (view profile)

@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.

Updates

1.4

update description

1.4

Update link to github

1.2

We provide MATLAB implementation of structural descriptor based clustering and MATLAB-C++ mixed implementation of graph degree linkage.

1.1

add a missing file
gacPartialMin_triu_c.cpp

MATLAB Release
MATLAB 7.10 (R2010a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Win prizes and improve your MATLAB skills

Play today