I’ve got several thousand observations in approximately 300-dimensional space, in a relatively sparse matrix (typically 30 non-zero dimensions per observation). I'm using a clustering algorithm (so far have been working with DBSCAN) to identify clusters, though my primary interest is not in the assignment of points to clusters, but rather the number of clusters and the number of noise points (observations that do not fit in clusters), and comparing the # of clusters and # of noise points across different subsets of the data.

I have three questions. I'm putting them all in this one post because they are closely related, but I'm a newcomer here, so please let me know if I should separate into three topics.

  1. What is the appropriate distance metric to use in this high-dimensional space?
  2. Pros and cons of converting my (continuous) data to binary data?
  3. Is there a natural statistical test for comparing the number of clusters, and number of noise points, across subsets of the data?

On question 1: I’ve read some papers (e.g. Aggarwal et al., "On the Surprising Behavior of Distance Metrics in High Dimensional Space", and Klawonn et al., "What are Clusters in High Dimensions and are they Difficult to Find?") on the concentration of norms phenomenon in high dimensional spaces (as well as the hubness phenomenon, which I don’t understand as well as concentration of norms, but I get that it causes problems). So I’m thinking about using a quasi-norm distance metric, like something in the Minkowski family of norms but with 0<p<1 (and specifically, probably p=0.5). I understand that using fractional norms “spreads” space, which helps with the concentration of norms issue. But I am also aware that fractional norms don’t satisfy the triangle inequality (in fact the triangle inequality is reversed).

What I do not understand is the implication of the failure to satisfy the triangle inequality. This prior question indicates that "If the triangle inequality is an important quality to have in your research, then fractional metrics are not going to be tremendously useful," but I am not clear how to think about whether the triangle inequality is an important quality to have in my setting. So this is really the meat of question 1: in what settings might it be inappropriate to use a distance metric in which the triangle inequality is reversed?

On question 2: I have continuous measures (between zero and one) in all 300 dimensions, but I am not entirely confident in the continuous measures – there may be underlying measurement issues that make them not fully comparable. So, one option is to convert all positive values to 1 (and keep 0 values at 0). But then I am not sure if there is something fundamentally wrong with using clustering algorithms (that are primarily used for non-binary data) to cluster binary data. (I know that I could be using another method to identify pairwise distances across binary vectors, like the Jaccard similarity measure. But in my setting, given my focus on # of clusters and # of noise points, clustering seems more intuitive than pairwise comparisons.)

On the other hand, while I am not necessarily confident that (e.g.) 0.02 is different from 0.025, I can be pretty sure that 0.02 is different from 0.7. So another option is to use the continuous measures, especially since 0.025 is likely to end up ‘near’ 0.02 whereas 0.7 is more likely to end up as a noise point (depending on the values in other dimensions, of course, and probably even with the “space spreading” effect of using lp-norm-distances with p<1). So, question 2 basically boils down to pros and cons of making these continuous data binary, and using DBSCAN (or other standard clustering algorithms) on binary data.

On question 3: As I mentioned, my goal is not so much to identify similar clusters, as to identify the number of clusters and the number of noise points – i.e., observations that don’t fall into clusters. More specifically, I would like to demonstrate whether the number of clusters and number of noise points is different in different subsets of the data. (Note that the dimensions that define subsets are not used in the clustering algorithm; e.g., one comparison might be between the "before year 2010" and the "after year 2010" subset, but "year" is not one of the dimensions I am using when I run DBSCAN.)

Is there a recommended way to evaluate, statistically, whether two subsets have a different number of clusters, or number of noise points? For instance, one method that occurred to me is “run DBSCAN, identify # of clusters and # of noise points, run 10000 bootstrap replications” and make “# of noise points” the statistic of interest. But I'm kind of a novice on bootstrapping, so I don't really know how this would work or whether it is appropriate.

  • 1
    $\begingroup$ Make smaller questions, don't put everything into one. Your data is not high-dimensional if most values are 0. The intrinsic dimensionality will be less than 30 in your case, and the curse of dimensionality for distances will not apply. Don't rely on clustering results for automation. A single additional record can drastically change the clustering result. $\endgroup$ – Has QUIT--Anony-Mousse Feb 21 '18 at 8:12