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 at 8:13
  • Hi Elias, I'm using DBSCAN currently, though I'm open to try others. – user1478842 Feb 3 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 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.

You might be able to check on paper that your function satisfies the four axioms of a distance function (see the Wikipedia article above); if that is not possible, you could at least check it by looping over your test set.

  • There are occasionally pairs of items like this, where x1≠x2 and the distance is close to zero but rarely exactly zero and if so a small decimal number could be added. I just checked, it doesn't satisfy the four axioms at all. How important is it that they are satisfied? Should the clustering technique be changed or should the distance function be adapted into something more distance-like? – user1478842 Feb 5 at 3:37
  • The 10 weighted measures are things like jaccard similarity of a bag of properties and a variation of euclidean distance. It is definitely capturing the major groupings by virtue of its richness, the results are very good even though it's unsupervised and barely fine-tuned. It went very far with the feature extraction but now I'm trying to make better use of the data. – user1478842 Feb 5 at 3:37
  • I find it hard to judge to what extent DBSCAN (and your implementation of it) relies on the four axioms of a distance function. In general though, violation of these axioms seems to make things a lot more complicated. See for example this paper: link. Have you tried reducing the complexity of your distance? You could try using the average of your distance functions (with fixed weights), that should be a proper distance function again. – Elias Strehle Feb 5 at 7:43
  • This is a useful suggestion, I will try this and see how it affects the performance. However, I am concerned that because my distance function is exploiting many features and adaptively adjusting adjusting itself to what is known about the problem domain, that there it is unwise to throw all this information away. Perhaps something like [this] (arxiv.org/pdf/1710.10655.pdf) would be appropriate, it attempts to adjust the distance matrix to fix triangle inequalities. – user1478842 Feb 5 at 16:50
  • 1
    I've investigated Affinity Propagation and it seems that it can handle general notions of similarity and doesn't assume triangular equality. So I think my next task is to build and evaluate the performance of the following: (1) DBSCAN with a simpler more metric-like distance function (2) DBSCAN with the original distance function but with a metric-repair process applied to the distance matrix (3) Affinity Propagation with the original unmodified distance function – user1478842 Feb 5 at 16:58

I suggest trying to learn distributed representation of HTML code, build an embedding matrix for tags, use some RNN auto-encoder like this to learn elements. thus you end up with some low-level dimensionality, clustering in that latent space will be more efficient and effective.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.