in reply to Re^2: Finding The Best Cluster Problem
in thread Finding The Best Cluster Problem

You beat me to it, but my reading of the requirement (inevitably) produces 9 equal subsets with an size of 1 and an average of 1. D'oh!

However, I'm now confused by how you can have a centroid of an irregularly shaped set, given discrete values?

Actually, I think I'm completely lost by your meaning now. Could you give an example of two subsets, their relative densities, and how you calculated them?

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Replies are listed 'Best First'.
Re^4: Finding The Best Cluster Problem
by neversaint (Deacon) on May 16, 2007 at 13:57 UTC
    Dear BrowserUK,
    Could you give an example of two subsets, their relative densities, and how you calculated them?
    Let's say we have two cluster C1 and C2 
    C1 = (s2,s3,m3,w3), with centroid(z) = s2

sim(s2,s3)=0.5
sim(s2,m3)=0.3
sim(s2,w3)=0.36
----------------+
   Total = 0.96
   |C1| = 4
Density = Total/|C1| = 0.96/4 = 0.24

we skip including this: sim(s2,s2)=1
We never compare a centroid with itself.

    [download]
    And C2 
    C2 = (s3,m1,w3), with centroid(z) = w3

sim(w3,s3)=0.4
sim(w3,m1)=0.5
----------------+
   Total = 0.9
   |C2| = 3
Density = Total/|C2| = 0.9/3= 0.3

    [download]


    ---
    neversaint and everlastingly indebted.......
[reply]
[d/l]
[select]

      Okay, but the problem is that you are asking for a single maximised cluster. But by my logic, (and the references I've looked at for 'clustering algorithms'), suggest that that doesn't make much sense, without some heuristic that allows you to exclude a value and improve the 'score' of what remains. Otherwise the best single cluster is the one that contains everything.

      For example, this footnote from step 4 of the algorithm description here:

      (*) Of course there is no point in having all the N items grouped in a single cluster but, once you have got the complete hierarchical tree, if you want k clusters you just have to cut the k-1 longest links.
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

In Section Seekers of Perl Wisdom