I've got some big datasets of images (a few million each), and I would like to cluster them according to images' visual similarities. I've extracted a feature vector for each image; the space of feature representations is the one I would like to cluster in practice. However, I've had some difficulties because of the following constraints:
- there's no way I can know the number of clusters in advance;
- the clustering algorithm must be stable (it must not be order-dependent);
- I don't want to be affected by the chaining effect (i.e. elongated clusters, where very different images could be linked through a series of small transformation - morphing);
- I would like the solution to be scalable (e.g. by using Apache Spark) or, even better, incremental (online) and efficient. I guess that this last point could be addressed by a streaming clustering algorithm
Given all of these constraints, I am struggling to tackle the problem. All ready-to-go algorithms in Spark MLlib require the number of clusters beforehand. Single Linkage or DBSCAN algorithms are subjected to the chaining effect (see "density reachability" definition in density-based algorithms).
If I had an approximated scalable solution, I think I would be satisfied. I can give up on some of the above constraints if the solution is efficient. To me, it seems that scalable clustering is a hot research topic (I haven't found off-the-shelf solutions).
Of course, I'm not asking for the perfect answer, but I would like to receive some suggestions if some of you have encountered similar challenges before. I've tried some hierarchical clustering techniques, other than Single Linkage (e.g. Ward's method), but the time/space complexity (O(N^2)) required is too expensive for my datasets; furthermore, it isn't intuitive how to parallelize them.
Local Sensitive Hashing seems to hold some interesting properties, however, it seems more suitable for kNN search rather than clustering.
I read this paper: A Scalable Hierarchical Clustering Algorithm Using Spark but, unfortunately, it uses Single Linkage, thus, falling into the chaining effect, which I want to avoid.
Also, this article: Detecting image similarity using Spark, LSH, and TensorFlow seems to be pretty interesting but it doesn't give much insight into the practical clustering details.