For example, there are 4 objects. Each object has some elements. There are 3 clusters. Each element of each object belongs to some cluster. Clustering was done before, and we know only how many elements of each object belong to some cluster. How we can calculate the porbability of similarity of two objects?

         Cluster1  Cluster2  Cluster3
Object1    500       300        200
Object2    200       200        100
Object3    250       2500       1250       
Object4    190       210        300
  • $\begingroup$ You could normalize the distribution of elements over clusters for each object, then compare them using the KLD $\endgroup$ – Emre Mar 14 '15 at 0:34
  • $\begingroup$ First you need to define "similarity", then define some statistical model in order to define probabilities. Without those, this can go nowhere. $\endgroup$ – Spacedman Mar 16 '15 at 22:58

You can consider that the clusters are defined by a multinomial distribution with 4 classes. Thus you would identify the cluster as a vector of 4 probabilities, one for each class, and the sum of probabilities being 1.

In this form there are some tests and distance functions which can prove to be useful for you.

You can ask questions like "is the cluster 1 is different than the cluster 2?". In order to do that you can employ hypothesis testing, and specifically chi square independence test (wikipedia page here). You select from your table only the first 2 columns, compute the marginal totals, compute the estimated counts as $E_{ij} = rowsum_i * colsum_j / grandtotal$. Denoting with $O_{ij}$ the cell counts you can compute a test statistic with formula:

$$chi = \sum_{i=1}^4\sum_{j=1}^2\frac{(E_{ij}-O_{ij})^2}{E_{ij}}$$

This is known to has a chi square distribution with $(rows-1)(cols-1)=3$ degrees of freedom. Thus using the cumulative distribution of chi square you can compute the p-value as $1-cdf_{\chi_{3}^2}(chi)$. Now if p-value is smaller than any critical value you choose before test (like 0.05, 0.01 or so), you have a statistical proof that the clusters have a different distribution (this follows from the fact that your procedure tests for the independence of cluster and object distributions, which with short derivation is the same as saying the clusters have the same distribution).

To answer to the same type of question you can also employ G-test (wikipedia page here) or Fisher exact test (wikipedia page here).

Note also that all those tests can't prove that two clusters are the same. The logic behind the tests can be formulated as "we consider the distributions the same, as a natural state, accepted without other proofs, and if we see some exceptionally obvious differences, we can bring that as a proof that they are different indeed".

A different approach would be to build a distance between those two distributions. The advantage of a distance function would be that it could be used for comparisons and eventually some further algorithms based on distances. The drawback of a distance function is that it gives you no hint to answer the first type of questions like "are the differences between 2 distributions small enough in order to be explained by the natural noise in data?". Thus I have two candidates in mind.

First distance is the chi square distance. This type of distance gives a measure to the distance between two normalized histograms (or, put it simply, between two vectors of probabilities of the same size). Thus, if we denote with $cluster_i = (n_{i1}/n_i, n_{i2}/n_i, .., n_{ik}/n_i] = (p_{i1},p_{i2},..p_{ik})$, the distance between cluster i and j would be:

$$d(i,j) = \frac{1}{2}\sum_{k=1}^{4}\frac{(p_{ik}-p_{jk})^2}{p_{ik}-p_{jk}}$$

This distance function has the advantage that it is symmetric regarding $i$ and $j$. To be honest I rarely used it since I did not fully understand it's meaning. In general I use another function, described below.

The second distance function is mutual information (see wikipedia page here). The idea is similar with Kulback-Leibler divergence, however the KL distance is an oriented measure (measures how a distribution can be expressed through another one). The MI distance is a measure of mutual independence between two distributions. In your case the two distributions are two clusters, and the MI measures how dependent they are. I give formula just to illustrate the idea behind it. $$MI(x,y) = \sum_{x,y}p(x,y)log(\frac{p(x,y)}{p(x)p(y)})$$ You can see from the formula that when the two variables are independent, the quantity inside the logarithm is $1$, and as a consequence, the MI is $0$. As the difference grows, the function also grows. I will not derive what p means, see what I explained already for chi square test, since is very similar.


I'd go for this:

$S(object_i,object_j) = 1 - \frac{\sum_{k=1}^{N_c} |n_{object_i,cluster_k}-n_{object_j,cluster_k}|}{n_{object_i}+n_{object_j}}$

where $N_c$ is the number of clusters (here 3), $n_{object_i,cluster_k}$ is the number of elements of object $i$ that belong to cluster $k$ (here $n_{object_2,cluster_2}=200$) and $n_{object_i}$ is the total number of elements in object $i$ (sum of $i^{th}$ row).

I hope it helps :)


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.