Dbscan - maximum cluster size limit

Question

In my understanding of DBSCAN, you can specify epsilon, say, 100 meters, and - since DBSCAN takes into account reachability density and not direct reachability density when searching for clusters - it ends with a cluster in which the maximum distance between any two points is> 100 meters. In a more extreme opportunity, perhaps you can set the epsilon to 100 meters and end up with a cluster of 1 kilometer: see [2] [6] in this array of images from scikit learn for an example of when this might happen. (I am more than willing to say that I am a complete idiot and misunderstanding of DBSCAN if this happens here.)

Is there an algorithm based on density, like DBSCAN, but taking into account some threshold for the maximum distance between any two points in the cluster?

Answer 1

DBSCAN does not really impose a total size limit on the cluster.

The epsilon value is best interpreted as the gap size separating two clusters (which can contain no more than minpts-1 objects).

I suppose you are not even looking for clustering: clustering is the task of discovering the structure in the data . The structure can be simpler (for example, k-means) or complex (such as clusters of arbitrary shape detected by hierarchical clustering and k-means).

Perhaps you are looking for vector quantization — reducing the data set to a smaller set of representatives — or set the cover — finding the optimal coverage for that set — instead.

However, I also get the impression that you are not sure what you need and why.

The length of a DBSCAN is that it has a mathematical definition of structure in the form of components related to density. This is a strong and (with the exception of some rare cases of boundary) well-defined mathematical concept, and the DBSCAN algorithm is an optimally efficient algorithm for detecting this structure.

However, attainability of direct density does not determine a useful structure (partition). It just does not break data into disjoint sections.

If you don’t need such a strong structure (that is, you do not cluster as in “structure detection”, but just want to compress your data, as in vector quantization), you can give a “dissection of the dome”, try. This can be seen as a pre-processing step designed for clustering. In essence, this is similar to DBSCAN, except that it uses two epsilon values, and the structure is not guaranteed to be optimal in any case, but will depend heavily on the ordering of your data. If you then pre-process it properly, it can be useful. If you are not in a distributed setup, a dome leak is at least as expensive as a full DBSCAN operation. Due to the lack of requirements (in particular, "clusters" can overlap, and objects must belong to several "clusters"), they are easier to parallelize.

Oh, and you can also just look for hierarchical clustering with full binding . If you cut the dendrogram at the desired height, the resulting clusters should have the desired maximum distance between any two objects. The only problem is that hierarchical clustering is usually O(n^3) , meaning it does not scale for large data sets. DBSCAN runs in O(n log n) in good implementations (with index support).