1
$\begingroup$

Is it possible to define any useful entropy or conditional entropy which is based on the distance between datapoint(s) and cluster center(s), instead of basing on the number of points assigned to cluster like it is defined in for example to compute the v-measure ? I am not implying that I want an equivalent to v-measure, but I just wonder if it is possible and maybe useful to define a conditional entropy based on distances.

So, What I'm looking for is a kind of conditional entropy based on distances, which allow to have an idea about the "homogeneity" and "completeness" of clusters, with respect to distances.

$\endgroup$
4
  • $\begingroup$ Have a look at k-means. It does in fact use a kind of variance of distances from the cluster center. However, you should avoid overfitting. Any such measure is biased, when the algorithm you evaluate already optimized wrt. this measure. $\endgroup$ Feb 16 '12 at 9:18
  • $\begingroup$ I know how kmeans performs. What I was asking for is a kind of conditional entropy based on distances, which allow to have an idea about the "homogeneity" and "completeness" of clusters, with respect to distances. $\endgroup$
    – shn
    Feb 16 '12 at 10:23
  • $\begingroup$ @user995434, I cant answer cause I have never used it, but I can imagine just mapping entropy values to the distances. Entropy is a one-sided bounded measure, as the distances are [0,infty). so just make a 1-1 mapping of a definition that you make. I don't think that it will arise from the basic principles which are different, but it may work as a connected measure that you defined. $\endgroup$
    – Vass
    Feb 16 '12 at 12:44
  • $\begingroup$ @Vass an example of how you would do that, would be appreciated ^^ if you can. $\endgroup$
    – shn
    Feb 19 '12 at 21:15
1
$\begingroup$

As @Anony-Mousse commented, k-mean relate to minimizing entropy in its clustering algorithm (which uses the euclidean distance), as does the EM algorithm. The k-means is also based on the distance between data points as you would like.

Data points are usually in some system of coordinates which you are already working with, and the euclidean distance gives you the distance of the shortest path between them as a measure for differentiating homogeneity between clusters. But the algorithm which uses the measure is what assures completeness of the cluster, the measure it works with is assumed in the representation of the space of datapoints.

You could just say, that the distance between points is $k \log( d_{i,j} + 1 )$ where $d_{i,j}$ is the distance between points so that it resembles entropy measures. But since this is strictly monotonically increasing as a function the clustering will not change, but can affect the inferred number of clusters. It penalizes large distances from creating large effects with the logarithmic increase on the distance.

I believe that conditional entropy will be applicable only under a constrained space of datapoints. You would have then probabilities of points in clusters based maybe on a bootsrap measure or some Bayesian view with priors on placements. It would get complicated and is a separate question in itself. Without the constrained space to place probabilities on the distribution on points in relation to each other would need some normalization and therefor a constrained space unless some other definition can apply. The paper you link to for the V-measure uses this conditional entropy without euclidean distances it seems and more based on labeling. You could replace the conditional probability measures there to have distances rather than the ratios of class membership in equation (1) of the paper so that the inverse sum of distances is there.

$\endgroup$
7
  • $\begingroup$ Yes, V-measure uses a conditional entropy based on labeling (classes) and not distances. We can have distances rather than the ratios of class membership in this conditional entropy, but I don't know if its "meaning" will still the same (homogeneity and completeness). Another question would be: is it possible to compute a given conditional entropy H(X|Y) in an incremental manner ? i.e. update it each time a new datapoint x is considered. $\endgroup$
    – shn
    Feb 24 '12 at 13:41
  • $\begingroup$ @user995434, yes it will satisfy the same being a strict monotonic function just as it is for k-means. The conditional parameter, as I try to say in the question is a more intricate issue with more considerations. $\endgroup$
    – Vass
    Feb 24 '12 at 14:05
  • $\begingroup$ How would you compute the conditional entropy H(X|Y) in an incremental manner (update it each time a new datapoint x is considered) if the number of clusters (i.e. |Y|) is not fix (it may increase each time a new datapoint is added, or not) ? $\endgroup$
    – shn
    Feb 24 '12 at 15:24
  • $\begingroup$ @user995434, the only way I can imagine that is to place a Gaussian at each cluster center and find the conditional for a point to belong to it. $\endgroup$
    – Vass
    Feb 24 '12 at 15:26
  • $\begingroup$ hmm I don't really understand what you mean by placing a Gaussian at each cluster center and find the conditional for a point to belong to it ? Do you have an example ? $\endgroup$
    – shn
    Feb 24 '12 at 15:43

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.