I've got a huge similarity matrix(more precisely it's about 30000x30000 in size, and it's not a sparse matrix) now I wanted to see that what is the most efficient way I could cluster its data points, btw the value for each (i,j) index of the matrix is a real number between 0 and 1 and the number of clusters is not known beforehand, so what algorithms/methods do you suggest?(That is more efficient computationally for such a matrix)
You might try FACADE (Fast and Automatic Clustering Approach to Data Engineering). It runs in O(n log n) time. It clusters the data naturally using a K nearest neighbors algorithm. The latest code can process n-dimensional data.
I would recommend K-means from this implementations: http://scikit-learn.org/stable/modules/clustering.html#clustering or DBScan. There is a version called Mini-Batch K-means with is intended for such needs as yours but it dose not work on preciomputed similarity matrix
Matching pursuit is a type of sparse approximation which involves finding the " best matching" projections of multidimensional data onto an over-complete ..
The best results will probably be using AHC. A c++ implementation should be able to handle that. An alternate could be to try implementing it using Map-Reduce.
For handling large similarity matrix, I think you may try Non-negative Matrix Factorization, which has a linear time complexity. However, the number of clusters should be set beforehand.
If the number of clusters is really very difficult to tune. Unfortunately, to my knowledge, there is no adequately efficient clustering methods. You may have a try of DBSCAN algorithm or its variants, which has a quadratic time complexity and its parameters are difficult to tune in practice. Affinity Propagation may be also a choice, but it requires specific format of the inputs.
In view that similarity matrix could be modeled as a graph. You may also check for feasible spectral clustering algorithms. But it may be difficult for the graph theoretical algorithms to handle the input matrix having more than 10k rows.
Good luck!
To cluster the data you can use FCM (fuzzy c-means) or k-means as suggested
above. Since the searching space is huge, it's a good idea to employ an optimatization technique like PSO (particle swarm optimization) or psc (particle swarm culstering).
I Think Rough C means or K-means can give good result.
But the dataset is large, so you can use Genetic Algorithm or PSO based K-means Clustering Algorithm. There are different PSO based Clustering algorithms are available that can give best result compared to other algorithms.
You might check out this tool http://wortschatz.informatik.uni-leipzig.de/~cbiemann/software/CW.html of Chris Biemann. You'll just need to translate your matrix into a connectivity graph. It's fast and decides itself on the optimal number of clusters.
You can uses db scan algo wich is an unsupervized clustering approach and relies on density for clustering.
You might try FACADE (Fast and Automatic Clustering Approach to Data Engineering). It runs in O(n log n) time. It clusters the data naturally using a K nearest neighbors algorithm. The latest code can process n-dimensional data.
goto course archive of Introduction to data science of Washitgton state University on coursera (its free) you will find a new and very efficient way to clusters by similarity matrix
I would recommend using hierarchical clustering. You can easily try it using Matlab, scipy or any other scripting language that you are familiar with. The key here is to choose the right cutoff (matrix value for i,j) that best describes your problem. In addition, your matrix size is not huge at all so you should not really worry about the computation time.
Given that you have the similarity matrix and efficiency is your primary concern try leader clustering. One of the fastest although it is sample order dependent and only generates spherical clusters. If you know your data and have a good idea of what a reasonable distance threshold is you could get pretty good results. If your willing to pay a little more computational cost then hierarchical clustering would also do the trick but you will have the issue of where to prune the dendrogram to get the right clusters.
Due to the fact that you don't know the number of clusters beforehand, maybe you want to try out sorting your matrix by similarity in order to see more structure in your matrix. My application was quite different I guess but here's what we have done. If you are interested I also attached the MatLab Program I wrote for sorting the matrix.
Article Indications for different types of brittle failure due to ac...
You can use use out-of-core clustering methods. Available in literature.
It really depends on what you're after. IF this is part of some project that you're doing, then the questions would be: how long can you wait vs how good an answer you want?
If this is to be used in some research publication, then the real questions is...what is the time complexity of generating the similarity matrix in the first place? Given your size, I assume the original data matrix had 30K rows so you're already in the O(m^2n) for m rows and n columns original matrix. In which case, using hierarchical clustering wouldn't hurt the overall complexity.
There are smart codes (including parallel) for hierarchical clustering or you could write your own. The advantage here is
1. you are more likely to get a better result (accuracy)
2. you can look at the dendrogram and choose your cut-off point.
Otherwise, use some of the other fast methods like pkwik, a variant of k-means (using similarities from your pre-computed table instead of mean), or some other method mentioned above,
Pl. consult the paper in link
https://pdfs.semanticscholar.org/e374/1f0e745846073ff242029338135e740b2477.pdf
I would suggest you to go with HDBSCAN. With "pre-computed" parameter, it provides clustering on pair wise distance matrix. Compared to DBSCAN the algorithm is computationally faster. Adding on, HDBSCAN also provides soft clustering and probability of each point to be in the specified cluster.
I am leaving a link here for your further reference .
https://hdbscan.readthedocs.io/en/latest/basic_hdbscan.html @ Hassan Abedi
- Badges
- Science topic