The ClusterEvaluator compares the cluster centers directly to compute
the inter-cluster density whereas the CDbwEvaluator computes it by
counting the representative points which are within 2 stds (really stdI
+ stdJ) from the center of a line segment between the closest
representative points of their respective clusters. These are very
different approaches and should be expected to yield different values.
The ClusterEvaluator uses the algorithm from "Mahout in Action". I don't
know which is "more accurate", the CDbw approach is certainly more
sophisticated as it is measuring the density of representative points in
the inter-cluster region. Pick your poison.
You know, you can run all the clustering algorithms in sequential mode
(-xm sequential) to improve performance if the data you are munching is
not too huge. The same is true for the representative points
calculations. See TestClusterEvaluator.testRepresentativePoints() for an
example of this.
On 9/30/10 8:08 AM, Derek O'Callaghan wrote:
Sorry, I forgot to mention that I was also running ClusterEvaluator
along with CDbwEvaluator yesterday. I was getting inter < intra with
the former, and the reverse with the latter, and even allowing for the
fact that they're different algorithms I was a bit suspicious of this.
However, I'd also turned off KMeans to speed up the process while
debugging, and was running CDbw directly on the generated Canopies.
I've run it today with Canopy + KMeans and 10 representative points
per cluster, and the results look better that lastnight, e.g.
CDbw = 178.90082114134046
Intra-cluster density = 0.26970259013839315
Inter-cluster density = 0.2517752232288567
Separation = 663.326299719779
I reran with Canopy only (to double-check) and this generated the
following (I assume overlapping canopies are causing inter to be
greater than intra):
CDbw = 97.38825072133858
Intra-cluster density = 0.23594531216994152
Inter-cluster density = 0.9859430197400473
Separation = 412.7577268888219
To confirm: it's running much better now than before, as the
successful KMeans evaluation above includes the cluster with the
identical points which are marginally different from the centre.
Thanks for all the help on this.
@Jeff: is ClusterEvaluator useful too, or should CDbwEvaluator be
considered more accurate?
On 29/09/10 20:51, Jeff Eastman wrote:
The CDbw intra-cluster density calculation uses the average std of
all the clusters in its normalization and produces an average of the
per-cluster intra-cluster densities so it's likely the other, looser
clusters are degrading that result.
CDbw is not a panacea either. The Dirichlet unit test, for example,
produces a very low metric despite clustering over the same data set
that the DisplayDirichlet uses. That clustering finds almost exactly
the parameters of the input data set (try it), but the clusters
overlap and that messes with CDbw density calculations which reward
mostly non-overlapping clusters.
I'm happy that the Online accumulator works better. I will plug it in
in my next commit and tweak the unit tests to accept its values.
On 9/29/10 2:59 PM, Ted Dunning wrote:
That slight difference case is exactly where the running sums approach
fails. I think that you found the problem.
Your suspicion about inter being larger than intra confuses me.
Isn't that
just another way of saying that clusters are very tight?
On Wed, Sep 29, 2010 at 11:19 AM, Derek
O'Callaghan<[email protected]
wrote:
I just stepped through invalidCluster(), and it seems that there's
a slight
difference between the centre and the other points, so it returns
false. I
was positive that there was no difference when I stepped through it
last, I
must have overlooked something, sorry about that.
I just tried the OnlineGaussianAccumulator and it does run better,
in that
I get values for the 4 metrics. One thing I need to check is why the
inter-density is so much bigger than the intra-, I'm getting the
following
values:
CDbw = 68.51761788802385
Intra-cluster density = 0.3734803797950363
Inter-cluster density = 3.474415557178534
Separation = 183.4570745741071
When using RunningSums and ignoring the identical points cluster, I
get a
similar issue in that inter = ~1.5, with intra = ~0.15. I have to
leave for
the evening, I'll look into it tomorrow to see if I can determine
if it's
correct.
Thanks again.
On 29/09/10 18:55, Jeff Eastman wrote:
If all of the representative points for that cluster are
identical then
they are also identical to the cluster center (the first
representative
point) and should be pruned. I'm wondering why this was not
detected in
invalidCluster, can you investigate that? You may also want to
plug in an
instance of the new OnlineGaussianAccumulator to see if it does
any better.
It is likely to me much more stable than the RunningSums...
On 9/29/10 1:45 PM, Derek O'Callaghan wrote:
Thanks for that Jeff. I tried the changes and get the same result as
expected. FYI I've investigated further and it seems that all of
the points
in the affected cluster are identical, so it ends up as more or
less the
same problem we had last week with clusters with total points< #
representative points, in that there are duplicate representative
points. In
this case total> # representative, but the end result is the same.
I'm wondering if the quickest and easiest solution is to simply
ignore
such clusters, i.e. those that currently generate a NaN std? I'm
not sure if
it's the "correct" approach though...
On 29/09/10 17:37, Jeff Eastman wrote:
Hi Derek,
I've committed some changes which will hopefully help in fixing
this
problem but which do not yet accomplish that. As you can see
from the new
CDbw test (testAlmostSameValueCluster) I tried creating a test
cluster with
points identical to the cluster center but with one which
differed from it
by Double.MIN_NORMAL in one element. That test failed to
duplicate your
issue.
The patch also factors out the std calculation into an
implementor of
GaussianAccumulator. I factored the current std calculations out of
CDbwEvaluator into RunningSumsGaussianAccumulator and all the
tests produced
the same results as before. With the new
OnlineGaussianAccumulator plugged
in, the tests all return slightly different results but still no
NaNs.
I still have not added priors and I'm not entirely sure where to do
that. I've committed the changes so you can see my quandary.
OnlineGaussianAccumulator is still a work in progress but, since
it is never
used it is in the commit for your viewing.
Jeff
On 9/29/10 11:13 AM, Derek O'Callaghan wrote:
Thanks Jeff, I'll try out the changes when they're committed. I
tried a
couple of things locally (removing the clusters/setting a small
prior), but
I ended up with inter-density> intra-density, so I suspect
I've slipped up
somewhere. I'll hold off on it for now.
On 29/09/10 13:48, Jeff Eastman wrote:
Hi Derek,
That makes sense. With the very, very tight cluster that your
clustering produced you've uncovered an instability in that
std calculation.
I'm going to rework that method today to use a better
algorithm and will add
a small prior in the process. I'm also going to add a unit
test to reproduce
this problem first. Look for a commit in a couple of hours.
On 9/29/10 8:02 AM, Derek O'Callaghan wrote:
Hi Jeff,
FYI I checked the problem I was having in CDbwEvaluator with
the same
dataset from the ClusterEvaluator thread, the problem is
occurring in the
std calculation in CDbwEvaluator.computeStd(), in that
s2.times(s0).minus(s1.times(s1)) generates negative values
which then
produce NaN with the subsequent SquareRootFunction(). This
then sets the
average std to NaN later on in intraClusterDensity(). It's
happening for the
cluster I have with the almost-identical points.
It's the same symptom as the problem last week, where this was
happening when s0 was 1. Is the solution to ignore these
clusters, like the
s0 = 1 clusters? Or to add a small prior std as was done for
the similar
issue in NormalModel.pdf()?
Thanks,
Derek
On 28/09/10 20:28, Jeff Eastman wrote:
Hi Ted,
The clustering code computes this value for cluster radius.
Currently, it is done with a running sums approach (s^0,
s^1, s^2) that
computes the std of each vector term using:
Vector std = s2.times(s0).minus(s1.times(s1)).assign(new
SquareRootFunction()).divide(s0);
For CDbw, they need a scalar, average std value, and this is
currently computed by averaging the vector terms:
double d = std.zSum() / std.size();
The more I read about it; however, the less confident I am
about
this approach. The paper itself seems to indicate a
covariance approach, but
I am lost in their notation. See page 5, just above
Definition 1.
www.db-net.aueb.gr/index.php/corporate/content/download/227/833/file/HV_poster2002.pdf
