Tiny question on this. Would it be OK to use Java's UnsupportedOperationException instead of Commons Lang's NotImplementedException? Just seems more standard.

Integrated in Mahout-Quality #863 (See https://builds.apache.org/hudson/job/Mahout-Quality/863/)
MAHOUT-597: Applied patch to support kernels in MeanShift. All tests run.

jeastman : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1131504
Files :

• /mahout/trunk/core/src/main/java/org/apache/mahout/common/kernel
• /mahout/trunk/integration/src/test/java/org/apache/mahout/clustering/cdbw/TestCDbwEvaluator.java
• /mahout/trunk/core/src/main/java/org/apache/mahout/clustering/meanshift/MeanShiftCanopy.java
• /mahout/trunk/core/src/main/java/org/apache/mahout/clustering/meanshift/MeanShiftCanopyClusterer.java
• /mahout/trunk/core/src/test/java/org/apache/mahout/clustering/meanshift/TestMeanShift.java
• /mahout/trunk/core/src/main/java/org/apache/mahout/common/commandline/DefaultOptionCreator.java
• /mahout/trunk/examples/src/main/java/org/apache/mahout/clustering/display/DisplayMeanShift.java
• /mahout/trunk/integration/src/test/java/org/apache/mahout/clustering/TestClusterEvaluator.java
• /mahout/trunk/integration/src/test/java/org/apache/mahout/clustering/TestClusterDumper.java
• /mahout/trunk/core/src/main/java/org/apache/mahout/common/kernel/NormalKernelProfile.java
• /mahout/trunk/core/src/main/java/org/apache/mahout/common/kernel/TriangularKernelProfile.java
• /mahout/trunk/examples/src/main/java/org/apache/mahout/clustering/syntheticcontrol/meanshift/Job.java
• /mahout/trunk/core/src/main/java/org/apache/mahout/clustering/meanshift/MeanShiftCanopyDriver.java
• /mahout/trunk/core/src/main/java/org/apache/mahout/clustering/meanshift/MeanShiftCanopyConfigKeys.java
• /mahout/trunk/core/src/main/java/org/apache/mahout/common/kernel/IKernelProfile.java

r1131504 committed this patch after fixing conflicts caused by the delay. All tests run

Should have committed it earlier. It has a few conflicts now but I'm on it for 0.6 for sure.

Jeff it looks like you approve of the patch – seems like something to be worked in for 0.6 then.

This looks excellent, and the change in #1 clearly fixes a major bug. Nice work with the kernels too.

This is a proposal for implementing various types of kernels with the means shift algorithm. The following changes were introduced:

1. The original algorithm was changed: Previously when one cluster "touched" other clusters its centroid was computed only based on the centroids of the clusters it touched, but not based on his centroid itself. Now before calculating the shift I one more line was added which makes the cluster observe his personal centroid:

public boolean shiftToMean(MeanShiftCanopy canopy)

With this modification also a problem with convergence of the algorithm is resolved, when there are 2 clusters left which are within their T1 boundaries and not within their T2 boundaries. In this cases their centroids will switch from one another until infinity.
With this modification, however, the number of iterations until convergence increased slightly.
This change was necessary in order to introduce the other types of "soft" kernels.

2. IKernelProfile interface was introduced which has the methods:
public double calculateValue(double distance, double h);
public double calculateDerivativeValue(double distance, double h);

The first one is not used by the current implementations, because the value of the kernel profile - k - is not needed in calculating the meanshift, rather the value of the derivative of the kernel profile - g - is used.

3. Currenlty 2 implementations are created:
TriangularKernelProfile with calculated value:
@Override
public double calculateDerivativeValue(double distance, double h)

This profile covers the cases that are currently covered by the meanshift algorithm implementation

In addition NormalKernelProfile was created with calculated value:
@Override
public double calculateDerivativeValue(double distance, double h)

4. The merging of canopies now uses the kernel profile

public void mergeCanopy(MeanShiftCanopy aCanopy, Collection<MeanShiftCanopy> canopies) {
MeanShiftCanopy closestCoveringCanopy = null;
double closestNorm = Double.MAX_VALUE;
for (MeanShiftCanopy canopy : canopies) {
double norm = measure.distance(canopy.getCenter(), aCanopy.getCenter());
double weight = kernelProfile.calculateDerivativeValue(norm, t1);
if(weight > 0.0)

if (norm < t2 && ((closestCoveringCanopy == null) || (norm < closestNorm)))

}
if (closestCoveringCanopy == null)

else

}

5. The MeanShiftCanopy is modified so that its touch method includes also the weight with which the clusters should observe each other. This weight was calculated based on the kernel profile in use

void touch(MeanShiftCanopy canopy, double weight)

6. Some other modifications were made which were necessary to compile the code and to make the tests pass

With the so changed algorithm the following observations can be made:

1. Using NormalKernel "blurs" the cluster boundaries. I.e. the cluster content is more intermixed
2. The following procedure for estimating T2 and convergence delta can be used:

• bind convergence delta = T2 / 2
• When you decrease T2 the number of iterations increases and the number of resulting clusters after convergence decreases
• You come to a moment when you decrease T2 the number of iterations increases, but the number of resulting clusters remains unchanged. This is the point with the best value for T2
  3. In case of Normal kernel what you give as T1 is in fact the standard deviation of a normal distribution, so the radius of the window will be T1^2