Clustering with multiple distance measures

I'm trying to use clustering to automate a group-finding process with the aim of being able to automatically detect groups in unseen data. The data are html elements within any given webpage, this includes numerous features including spatial and visual information rendered from a web browser. The detected groups are usually semantically meaningful, for example a group of navigation links or a list of items in the main content area.

I've implemented a subtle distance measure that captures how similar or different these elements are and I'm passing these values to DBSCAN for clustering. So far it works quite well but I'm trying to think of ways to improve it.

The distance function is actually a weighted sum of 10 separate distance measures that capture different kinds of similarities and differences. I've weighted the more reliable and decisive measures higher than others. In theory, the measures that are weighted lower should only have an effect when they are congruent and are otherwise overpowered by the higher-weighted measures. Additionally each measurement function can itself amplify or attenuate it's own weight for a given item-pair, for example set its weight to zero if it is unsure and wants to abstain, or set it higher if it has found a similarity/difference that is particularly notable or reliable.

Although it's broadly working quite well, I've noticed that often one or two of the largest clusters should be further split. I've considered two methods for this: (a) attenuating the weights of measures that are mostly giving a low distance value within the cluster (thereby amplifying other measures with higher variance) and then rerunning DBSCAN or (b) searching clusters for subsets with large numbers of co-occurring features (e.g. some css class in the parent element and a particular font-size) and either splitting the cluster based on these, or adjusting the distance measures to reflect this apparent grouping and then rerunning the global DBSCAN with the adjusted values.

Currently it all works unsupervised but I'm open to manually creating a set of ground-truth data for improve it. Maybe then this could be used to optimize the weights in such a way that minimizes within-cluster distances and maximizes between-cluster distances? I also like the idea of running clustering multiple times, repeatedly adjusting the weights based on the variances of each measure within the cluster.

I'm looking for more ideas on how to optimize this, I would appreciate any input. I have seen some comments elsewhere that unsupervised clustering is only suitable for exploring data and not automating decisions, but I haven't been able to find a better way of finding these groups with my limited ML/data-science experience. Given all the time I've spent building this, the ideal thing would be to figure out a clever way of adaptively adjusting these weights in a more intelligent way.

• Welcome to the site! Which cluster algorithm do you use? – Elias Strehle Feb 3 '18 at 8:13
• Hi Elias, I'm using DBSCAN currently, though I'm open to try others. – user1478842 Feb 3 '18 at 18:15
• I was also thinking of trying a modified version of affinity propagation and wiggling the individual weights (and therefore the NxN similarity matrix) on each iteration, the idea being that maybe it'll converge in a way that's less sensitive to the weight values, because there may be no perfect values for these weights in general. I really should gather a test set that I can evaluate against so I can measure the effectiveness all these techniques. – user1478842 Feb 4 '18 at 2:54

This is just a wild guess, but I was wondering whether your custom distance function is indeed a distance function. In particular, your problem might occur because your distance function $d(x, y)$ does not separate observations: This is the case if there exist two observations $x_1$ and $x_2$ that are distinct, $x_1 \neq x_2$, but have zero distance, $d(x_1, d_2) = 0$. Then $x_1$ and $x_2$ would necessarily be put into the same cluster by your algorithm. If this happens for many observations in your test set, then you will observe large clusters.