1
$\begingroup$

I have a sparse set of points with unpredictable locations. I need a way of "scoring" each set of points such that clustering is rewarded. My working case is actually one dimensional, but a two dimensional use case may come up later.

Here's an example: Data A contains points at -2, 1, 5, 7. Data B has points at -10, 0, 20, 6. A and B are independent of each other and have not had clustering applied. Ideally, after clustering, A would have clusters (-2, 1) and (5, 7). There is more clustering in A so I would like it scored higher. Bonus points if the algorithm allows the points to have variable values so that in some cases, if points are 100 units apart but each of the points has a high value, that set of points will rate higher than a set of points 10 units apart with much lower values.

EDIT: My current idea is to use a clustering algorithm to figure out the center of each cluster and it figure out which points occupy the cluster. I would then score each cluster finding the mean of the distances squared (EDIT: Apparently this is called "variance.").

$\endgroup$
  • $\begingroup$ Without more information, your proposed approach seems perfectly reasonable. $\endgroup$ – Suresh Venkat Jul 7 '11 at 23:54
2
$\begingroup$

For the one dimensional case, you can use the variance.

For the higher dimensions, you can generalize the variance by first computing a mean point and then computing the sum of the square of the distance between each point and the mean squared followed by a division the sum by the number of points. This division by the number of points (which also happens in the variance) is the difference between the solution you have suggested and what I am recommending. This division allows for a fair comparison of clustering between sets of points of different sizes.

For $n$ points with mean point $m$, the computation is $\frac{1}{n} \sum_{i=1}^n \operatorname{dist}(m, p_i)^2$.

$\endgroup$
  • $\begingroup$ This seems as though it assumes there is only a single cluster. In my Set A example, I was intending to show -2 and 1 as a cluster and 5 adn 7 as another cluster. I could apply a clustering algorithm then compute the variance of each, but something tha works in one fell swoop would be great. EDIT: I'm thinking I will use variance in conjunction with bisection clustering. $\endgroup$ – Eric Pruitt Jul 10 '11 at 5:06
  • $\begingroup$ @Eric Pruitt Yes, I agree. This answer is based on the way I read your question; that the sets of numbers that you want to compare have already been created. $\endgroup$ – Tyson Williams Jul 11 '11 at 12:36
  • $\begingroup$ The sets were intended to be full data sets, not pre-computed clusters. EDIT: I modified the OP. $\endgroup$ – Eric Pruitt Jul 11 '11 at 12:40

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.