How can I simulate feature tolerances in DBSCAN to see how the clusters change?

Question

I am performing clustering based on the DBSCAN algorithm on a 3-dimensional data set. After running the algorithm, I get X clusters as a result. What I want to do is to see how the clusters behave if I am more "tolerant" towards one specific feature (say, I allow a range of values +/- 10%), meaning that I cannot simply increase epsilon since this has an effect on all dimensions. So, basically, my objective is to simulate various clusterings, each with different tolerances depending on which feature I allow to be tolerant.

Is this possible at all using DBSCAN?

Answer 1

There are uncertain clustering algorithms that do exactly this.

In particular (since you are interested in DBSCAN):

• FDBSCAN ("Fuzzy DBSCAN")

  Kriegel, H. P., & Pfeifle, M. (2005, August). Density-based clustering of uncertain data. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining (pp. 672-677). ACM.

• Several versions of "uncertain k-means" (not DBSCAN).
• Representative clustering (which can be used with DBSCAN)

  Züfle, A., Emrich, T., Schmid, K. A., Mamoulis, N., Zimek, A., & Renz, M. (2014, August). Representative clustering of uncertain data. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 243-252). ACM.

This approach is probably very intersting to you, because it not only randomizes the data (to reflect uncertainty), but then runs DBSCAN (or any other clustering algorithm) multiple times. Then a meta-clustering step is done to find the "most typical" (i.e. consensus) clustering, as well as alternatives. This way, you can explore the most likely clustering, but also alternate solutions that are less frequent.

There are implementations of these and related algorithms available in ELKI 0.7.0:

Schubert, E., Koos, A., Emrich, T., Züfle, A., Schmid, K. A., & Zimek, A. (2015). A framework for clustering uncertain data. Proceedings of the VLDB Endowment, 8(12), 1976-1979.

but it is not easy to use. You need to setup a filter to "uncertainify" the data. You need to specify what kind (e.g. a box, or a Gaussian) and how much uncertainty you want to add to which attributes, too. And of course, how many samples you can afford to run (each of which is about as expensive as a single run of the basic algorithm on exact data). All in all, you probably have to set two dozen of parameters, unfortunately.

An easier approach is to use weighted distances:

But less weight on one dimension to increase tolerance.

The weighted Euclidean distance is as follows: $$d(x,y) := \sum_i \omega_i (x_i-y_i)^2$$ where $\omega_i$ is the weight of each dimension. You can set $\omega_i=0.9$ for one dimension and keep all others at $1$, or try to adjust them by increasing their weight to $1.0 + 0.1/(d-1)$ where $d$ is the total number of dimensions, such that $\sum \omega_i = d$ remains constant. Linear feature weighting is equivalent to scaling your data set, and often it is faster to do this just once in preprocessing!