3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ you can try to estimate the optimum num of clusters for a subset of the whole dataset using any cluster estimation metric (eg sillouete score) $\endgroup$
    – Nikos M.
    Commented Jan 25, 2021 at 17:49
  • 1
    $\begingroup$ Agree with @NikosM, that you can use the elbow method or calculate something like a silhouette score - datascience.stackexchange.com/questions/10891/…. Yes you have to run this some number of times, thus adding and additional multiplicative factor to your time complexity, but you have to give something up. Need something easier? Using the square root of n clusters is a simple rule of thumb. Otherwise, I think you are trying to have your cake and eat it too. $\endgroup$
    – AN6U5
    Commented Jan 27, 2021 at 1:18

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.