12
$\begingroup$

I have some data points, each containing 5 vectors of agglomerated discrete results, each vector's results generated by a different distribution, (the specific kind of which I am not sure, my best guess is Weibull, with shape parameter varying somewhere around exponential to power law (1 to 0, roughly).)

I am looking to use a clustering algorithm like K-Means to put each data point into groups based on the attributes of its 5 component distributions. I was wondering if there are any established distance metrics that would be elegant for these purposes. I have had three ideas so far, but I'm not a seasoned statistician (more of a beginning data-mining computer scientist) so I have little idea how far I am off track.

  1. Since I don't know exactly what kind of distributions I'm dealing with, my brute-force approach to the problem was to chop each of the distributions (I have 5 per point) into each of its respective discrete data values (I pad each corresponding one to the same length with zeros at the end) and use each of these values as a separate attribute for the data point itself. I tried using both Manhattan distance and Euclidean distance as metrics based on these attributes, for both the PDF and CDF.

  2. Again, since I don't know what kinds of distributions I have, I figured that if I was going to measure the distance between the overall distributions I could use some sort of non-parametric test pairwise between distributions, such as the KS-test, to find the likelihood that the given distributions were generated by different PDFs. I thought that my first option (above) using the Manhattan distance would be a sort of upper bound on what I might get using this approach (since the KS statistic is the max absolute value of the difference of the CDFs, where Manhattan distance is the sum of the absolute values of the differences in the PDFs). I then considered combining the different KS-Statistics or P-values within each data point, probably using Euclidean distance, but possibly just taking the max of all of these values.

  3. Lastly, in an effort to use what little I can interpret about the shape of the distributions, I thought I might try estimating the parameters of the distributions as fit into a Weibull curve. I could then cluster the distributions based on differences in the two parameters of the Weibull distribution, lambda and k (scale and shape), probably normalized according to the variance of these parameters or something of the sort. This is the only case where I thought I might have an idea of how to normalize the parameters.

So my question is, what measure/methods would you recommend for clustering of distributions? Am I even on the right track with any of these? Is K-Means even a good algorithm to use?

Edit: Clarification of data.

Each data point (each object Obj that I want to cluster) actually literally contains 5 vectors of data. I know there are exactly 5 phases that these objects can be in. We'll say (for the purposes of simplification) that each vector is of length N.

Each one of these vectors (call it vector i) is a probability distribution with integer x-values of 1 through N, where each corresponding y-value represents the probability of measuring value x in phase i of the object Obj. N is then the maximum x-value I expect to measure in any phase of the object (this is not actually a fixed number in my analysis).

I determine these probabilities in the following manner:

  1. I take a single Obj and put it in phase i for k trials, taking a measurement at each trial. Each measurement is a single whole number. I do this for each of 5 phases of a single object, and in turn for each object. My raw measurement data for a single object might look like:

    Vector 1. [90, 42, 30, 9, 3, 4, 0, 1, 0, 0, 1]

    Vector 2. [150, 16, 5, 0, 1, 0, 0, 0, 0, 0, 0]

    ...

    Vector 5. [16, ... ..., 0]

  2. Then I normalize each of the vectors on its own, with respect to the total number of measurements in that given vector. This gives me a probability distribution in that vector, where each corresponding y-value represents the probability of measuring value x in phase i.

$\endgroup$
  • 1
    $\begingroup$ It is not clear to me how your data points can "contain" the distributions. Could you give an example? Furthermore Weibull is not a discrete probability distribution, so some extra clarification would be desirable. $\endgroup$ – mpiktas Jul 18 '11 at 7:58
  • $\begingroup$ @mpiktas: Each data point represents an object which has 5 different phases. The behavior of each phase of the object can theoretically be represented by a continuous probability distribution function, but my data only contains discrete samples. The Weibull distribution is probably the "theoretical" function behind my data, but the data itself is only measurements of density over discrete intervals. $\endgroup$ – machine yearning Jul 18 '11 at 8:04
4
$\begingroup$

(Computational) Information Geometry is a field which deals exactly with these kind of problems. K-means has an extension called Bregman k-means which use divergences (whose squared Euclidean of the standard K-means is a particular case, but also Kullback-Leibler). A given divergence is associated to a distribution, e.g. squared Euclidean to Gaussian.

You can also have a look on the work of Frank Nielsen, for example

You can also have a look on Wasserstein distances (optimal transport), mentioned as Earth Mover Distance in a previous post.

$\endgroup$
2
$\begingroup$

In their paper on the EP-Means algorithm, Henderson et al review approaches to this problem and give their own. They consider:

  1. Parameter clustering - determine parameters for the distributions based on prior knowledge of the distribution, and cluster based on those parameters
    • note that here, you could actually use any functional on the data, not just parameter estimates, which is useful if you know your data comes from different distributions
  2. Histogram binning - separate the data into bins, and consider each bin as a dimension to be used in spatial clustering
  3. EP-Means (their approach) - define distributional centroids (mixture of all distributions assigned to a cluster) and minimize the sum of the squares of the Earth Mover's Distance (something like the expected value of the $L^1$ distance between CDFs) between the distributional centroids and the distributions assigned to that cluster.

Another technique that I've used with success is to cluster all the observed points from all the distributions individually, and then assign to distribution i the soft probability corresponding with the proportion of its points which end up in each cluster. On the downside, it's much harder to separate distributions that way. On the upside, it kind of auto-regularizes and assumes that all distributions are the same. I would only use it when that regularization property is desired, though.

$\endgroup$
  • 1
    $\begingroup$ Welcome to our site! Note that you can use Latex markup here by putting text inside dollar signs, e.g. $i$ produces $i$, or $l_2$ produces $l_2$, which can make it easier to express yourself $\endgroup$ – Silverfish Sep 12 '16 at 22:02
1
$\begingroup$

You should proceed in two steps. (1) Data reduction and (2) Clustering.

For step (1), you should carefully inspect your data and determine a reasonable probability distribution for your data. You seem to have thought about this step already. The next step is to estimate the parameters of these distributions. You might fit a model separately for each unit to be clustered, or it may be appropriate to use a more sophisticated model such as a generalized linear mixed model.

For step (2), you can then cluster based on these parameter estimates. At this stage you should have a small number of parameter estimates per unit. As described in the answer to this post, you can then cluster on these parameter estimates.

This answer is necessarily somewhat vague -- there is no "canned" solution here, and a great deal of statistical insight is needed for each step to select from a nearly infinite number of methods that may be relevant, depending on your unique problem. The statement of your question shows that you have self-tought yourself a good deal of statistical knowledge, which is commendable, but you still have some fundamental misunderstandings of core statistical concepts, such as the distinction between a probability distribution and observations from a probability distribution. Consider taking/auditing a mathematical statistics course or two.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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