4
$\begingroup$

I have two groups of points, and the lenth of them may be different.I want to know which group of points connects more strongly, are there any existing algorithms for this?

Here are two groups of points, group1 has 13 points, group2 has 10 : 

group1={{8, -2}, {10, -2}, {6, -2}, {9, -1}, {5, -2}, {5, -3}, {9, -2}, {7, \
-1}, {7, -3}, {7, -3}, {2, -1}, {9, -4}, {2, -2}};
group2={{9, -3}, {3, -4}, {10, -3}, {10, -4}, {12, -2}, {8, -4}, {7, -1}, \
{9, -1}, {8, -2}, {13, -3}};

enter image description here

First I prefered to caculate the average point of each group, than get summation of all the distances between each point and the average one. But look at the picture, the most left one labeled "far away" of the yellow group is a particular case, it should contribute less to the result. Now I'm stuck here.

This may be a mathematical problem, but I'm going to solve it in mma, so I post it here.Thanks guys.

Edit:

All the points are on integer coordinates.

Improve this question
$\endgroup$
9
  • $\begingroup$ You could define a function penalizing such points, for instance the sum of the pairwise distances like Total@Flatten@ Table[EuclideanDistance[group1[[i]], group1[[j]]], {i, Length[group1] - 1}, {j, i + 1, Length[group1]}]. Then the group with the smallest value is the most connected. $\endgroup$ – b.gates.you.know.what Oct 15 '12 at 12:11
  • $\begingroup$ @b.gatessucks As I methioned above some pointes are special, I don't want to consider all points equally, special method for special case. $\endgroup$ – withparadox2 Oct 15 '12 at 12:24
  • 1
    $\begingroup$ @paradox2 You'll have to express how those points are special then. When do you define a point to be "far away"? $\endgroup$ – jVincent Oct 15 '12 at 12:31
  • $\begingroup$ @jVincent It also confused me, I can notice which one is special after drawing the picture. I just wonder how to do it in mathematic, may be every point of a group should have a different weight $\endgroup$ – withparadox2 Oct 15 '12 at 12:37
  • $\begingroup$ So your points lie on an integer grid, and "connectedness" corresponds to the points being at horizontally, vertically or diagonally adjacent positions? $\endgroup$ – celtschk Oct 15 '12 at 12:43
5
$\begingroup$

This is a possible cohesion measure. Please note that your problem isn't defined enough in mathematical terms, so perhaps you are looking for a statistical measure like Variance[] or StandardDeviation[]. Anyway:

cohessionCoef[pts_] := 
  Mean[Flatten[Function[{x}, Table[1/EuclideanDistance[#, i], {i, x}]]
       [Nearest[Complement[pts, {#}], #, 8]] & /@ pts]];

So,

cohessionCoef[RandomReal[1, {10, 2}]]
(*
-> 2.1
*)
cohessionCoef[RandomReal[.1, {10, 2}]]
(*
-> 26
*)

Some results over an integer grid:

Mathematica graphics

For your points:

GraphicsGrid[{ListPlot[#, AxesOrigin -> {0, 0}, PlotRange -> {{0, 15}, {-5, 0}}, 
                       PlotStyle -> {PointSize[Large], Red}], 
             Text[Style[N@(cohessionCoef@#), Large, Bold]]} & /@ {group1, group2}, 
Frame -> All]

Mathematica graphics

Edit

Relaxing the Cohesion coefficient so that far away outliers weight much less. A new param is introduced to select what is an outlier:

cohessionCoefRelaxed[pts_, cutoff_] := 
 Module[{dists}, 
  dists = Flatten[
    Function[{x}, Table[1/EuclideanDistance[#, i], {i, x}]][
       Nearest[Complement[pts, {#}], #, 8]] & /@ pts];
  Mean[If[# < cutoff Mean[dists], Mean[dists], #] & /@ dists]
  ]

N@cohessionCoefRelaxed[group2, #] & /@ Range[0, 1.5, .2]
(*
-> {0.404961, 0.404961, 0.421522, 0.463869, 0.488118, 0.493764, 0.489538, 0.480034}
*)

So,increasing the cutoff you get almost the same cohesion for group1 and group2

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think I understand you. But I am wondering if there is a way to let some points have different weights, e.g. there are 10 points, 9 of them have the same coordinates, only one is far away. If ignoring the special one, this group of points should connect strongly, and the result will decrease if taking that one in consideration.But if a lower weight is given to the special point the result won't decrease so much, and this is what I want.Sorry for so much text:) $\endgroup$ – withparadox2 Oct 15 '12 at 13:49
  • $\begingroup$ @paradox2 This method "weights" each point by its mean distance to its nearest 8 neighbors $\endgroup$ – Dr. belisarius Oct 15 '12 at 13:50
  • $\begingroup$ Yes, the current answer may be what I want, I am not sure if it is what I need $\endgroup$ – withparadox2 Oct 15 '12 at 14:03
  • $\begingroup$ @paradox2 updating with a kind of cutoff distance. Wait a few mins $\endgroup$ – Dr. belisarius Oct 15 '12 at 14:07
4
$\begingroup$

Concern about "far away" points sounds to me like concern about outliers. I would suggest experimenting with the L1 norm, which is more robust in the presence of outliers. Using squared norms such as EuclideanDistance allows outliers to artificially shift the cluster centre, thereby distorting distances of points from that centre. For example, the code by b.gatessucks may be altered to:

Total@Flatten@Table[Norm[{group1[[i]] - group1[[j]]}, 1], 
 {i,Length[group1]-1}, {j,i+1,Length[group1]}]

Alternatively, one could use FindClusters with different distance functions. See the documentation FindClusters > Options > DistanceFunction. The number of clusters returned is a measure of the cohesion of the input group of points. For example,

FindClusters[group1,DistanceFunction->(Norm[#1-#2,1]&)]

returns one cluster (the entire group of points), whereas the same command for group2 returns four clusters.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ DistanceFunction -> ManhattanDistance is also convenient $\endgroup$ – rm -rf♦ Oct 15 '12 at 15:34

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.