You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by ss...@apache.org on 2014/04/18 13:13:29 UTC
svn commit: r1588439 - in /mahout/trunk: ./
core/src/main/java/org/apache/mahout/clustering/fuzzykmeans/
core/src/main/java/org/apache/mahout/clustering/kmeans/
core/src/main/java/org/apache/mahout/common/commandline/
core/src/test/java/org/apache/maho...
Author: ssc
Date: Fri Apr 18 11:13:29 2014
New Revision: 1588439
URL: http://svn.apache.org/r1588439
Log:
MAHOUT-1440 Add option to set the RNG seed for inital cluster generation in Kmeans/fKmeans
Modified:
mahout/trunk/CHANGELOG
mahout/trunk/core/src/main/java/org/apache/mahout/clustering/fuzzykmeans/FuzzyKMeansDriver.java
mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/KMeansDriver.java
mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/RandomSeedGenerator.java
mahout/trunk/core/src/main/java/org/apache/mahout/common/commandline/DefaultOptionCreator.java
mahout/trunk/core/src/test/java/org/apache/mahout/clustering/kmeans/TestRandomSeedGenerator.java
mahout/trunk/src/conf/fkmeans.props
mahout/trunk/src/conf/kmeans.props
Modified: mahout/trunk/CHANGELOG
URL: http://svn.apache.org/viewvc/mahout/trunk/CHANGELOG?rev=1588439&r1=1588438&r2=1588439&view=diff
==============================================================================
--- mahout/trunk/CHANGELOG (original)
+++ mahout/trunk/CHANGELOG Fri Apr 18 11:13:29 2014
@@ -2,6 +2,8 @@ Mahout Change Log
Release 1.0 - unreleased
+ MAHOUT-1440: Add option to set the RNG seed for inital cluster generation in Kmeans/fKmeans (Andrew Palumbo via ssc)
+
MAHOUT-1445: Create an intro for item based recommender (Nick Martin via ssc)
MAHOUT-1509: Invalid URL in link from "quick start/basics" page (Nick Martin, smarthi)
Modified: mahout/trunk/core/src/main/java/org/apache/mahout/clustering/fuzzykmeans/FuzzyKMeansDriver.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/clustering/fuzzykmeans/FuzzyKMeansDriver.java?rev=1588439&r1=1588438&r2=1588439&view=diff
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/clustering/fuzzykmeans/FuzzyKMeansDriver.java (original)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/clustering/fuzzykmeans/FuzzyKMeansDriver.java Fri Apr 18 11:13:29 2014
@@ -73,6 +73,7 @@ public class FuzzyKMeansDriver extends A
addOption(DefaultOptionCreator.emitMostLikelyOption().create());
addOption(DefaultOptionCreator.thresholdOption().create());
addOption(DefaultOptionCreator.methodOption().create());
+ addOption(DefaultOptionCreator.useSetRandomSeedOption().create());
if (parseArguments(args) == null) {
return -1;
@@ -97,15 +98,20 @@ public class FuzzyKMeansDriver extends A
DistanceMeasure measure = ClassUtils.instantiateAs(measureClass, DistanceMeasure.class);
if (hasOption(DefaultOptionCreator.NUM_CLUSTERS_OPTION)) {
- clusters = RandomSeedGenerator.buildRandom(getConf(),
- input,
- clusters,
- Integer.parseInt(getOption(DefaultOptionCreator.NUM_CLUSTERS_OPTION)),
- measure);
+ int numClusters = Integer.parseInt(getOption(DefaultOptionCreator.NUM_CLUSTERS_OPTION));
+
+ Long seed = null;
+ if (hasOption(DefaultOptionCreator.RANDOM_SEED)) {
+ seed = Long.parseLong(getOption(DefaultOptionCreator.RANDOM_SEED));
+ }
+
+ clusters = RandomSeedGenerator.buildRandom(getConf(), input, clusters, numClusters, measure, seed);
}
+
boolean runClustering = hasOption(DefaultOptionCreator.CLUSTERING_OPTION);
boolean runSequential = getOption(DefaultOptionCreator.METHOD_OPTION).equalsIgnoreCase(
DefaultOptionCreator.SEQUENTIAL_METHOD);
+
run(getConf(),
input,
clusters,
Modified: mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/KMeansDriver.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/KMeansDriver.java?rev=1588439&r1=1588438&r2=1588439&view=diff
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/KMeansDriver.java (original)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/KMeansDriver.java Fri Apr 18 11:13:29 2014
@@ -64,13 +64,14 @@ public class KMeansDriver extends Abstra
.withDescription(
"The k in k-Means. If specified, then a random selection of k Vectors will be chosen"
+ " as the Centroid and written to the clusters input path.").create());
+ addOption(DefaultOptionCreator.useSetRandomSeedOption().create());
addOption(DefaultOptionCreator.convergenceOption().create());
addOption(DefaultOptionCreator.maxIterationsOption().create());
addOption(DefaultOptionCreator.overwriteOption().create());
addOption(DefaultOptionCreator.clusteringOption().create());
addOption(DefaultOptionCreator.methodOption().create());
addOption(DefaultOptionCreator.outlierThresholdOption().create());
-
+
if (parseArguments(args) == null) {
return -1;
}
@@ -90,8 +91,14 @@ public class KMeansDriver extends Abstra
DistanceMeasure measure = ClassUtils.instantiateAs(measureClass, DistanceMeasure.class);
if (hasOption(DefaultOptionCreator.NUM_CLUSTERS_OPTION)) {
- clusters = RandomSeedGenerator.buildRandom(getConf(), input, clusters,
- Integer.parseInt(getOption(DefaultOptionCreator.NUM_CLUSTERS_OPTION)), measure);
+ int numClusters = Integer.parseInt(getOption(DefaultOptionCreator.NUM_CLUSTERS_OPTION));
+
+ Long seed = null;
+ if (hasOption(DefaultOptionCreator.RANDOM_SEED)) {
+ seed = Long.parseLong(getOption(DefaultOptionCreator.RANDOM_SEED));
+ }
+
+ clusters = RandomSeedGenerator.buildRandom(getConf(), input, clusters, numClusters, measure, seed);
}
boolean runClustering = hasOption(DefaultOptionCreator.CLUSTERING_OPTION);
boolean runSequential = getOption(DefaultOptionCreator.METHOD_OPTION).equalsIgnoreCase(
Modified: mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/RandomSeedGenerator.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/RandomSeedGenerator.java?rev=1588439&r1=1588438&r2=1588439&view=diff
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/RandomSeedGenerator.java (original)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/clustering/kmeans/RandomSeedGenerator.java Fri Apr 18 11:13:29 2014
@@ -55,14 +55,19 @@ public final class RandomSeedGenerator {
public static final String K = "k";
- private RandomSeedGenerator() {
+ private RandomSeedGenerator() {}
+
+ public static Path buildRandom(Configuration conf, Path input, Path output, int k, DistanceMeasure measure)
+ throws IOException {
+ return buildRandom(conf, input, output, k, measure, null);
}
-
+
public static Path buildRandom(Configuration conf,
Path input,
Path output,
int k,
- DistanceMeasure measure) throws IOException {
+ DistanceMeasure measure,
+ Long seed) throws IOException {
Preconditions.checkArgument(k > 0, "Must be: k > 0, but k = " + k);
// delete the output directory
@@ -81,7 +86,9 @@ public final class RandomSeedGenerator {
FileStatus[] inputFiles = fs.globStatus(inputPathPattern, PathFilters.logsCRCFilter());
SequenceFile.Writer writer = SequenceFile.createWriter(fs, conf, outFile, Text.class, ClusterWritable.class);
- Random random = RandomUtils.getRandom();
+
+ Random random = (seed != null) ? RandomUtils.getRandom(seed) : RandomUtils.getRandom();
+
List<Text> chosenTexts = Lists.newArrayListWithCapacity(k);
List<ClusterWritable> chosenClusters = Lists.newArrayListWithCapacity(k);
int nextClusterId = 0;
Modified: mahout/trunk/core/src/main/java/org/apache/mahout/common/commandline/DefaultOptionCreator.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/common/commandline/DefaultOptionCreator.java?rev=1588439&r1=1588438&r2=1588439&view=diff
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/common/commandline/DefaultOptionCreator.java (original)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/common/commandline/DefaultOptionCreator.java Fri Apr 18 11:13:29 2014
@@ -72,6 +72,8 @@ public final class DefaultOptionCreator
public static final String KERNEL_PROFILE_OPTION = "kernelProfile";
public static final String ANALYZER_NAME_OPTION = "analyzerName";
+
+ public static final String RANDOM_SEED = "randomSeed";
private DefaultOptionCreator() {}
@@ -280,6 +282,15 @@ public final class DefaultOptionCreator
.create()).withDescription("The number of clusters to create")
.withShortName("k");
}
+
+ public static DefaultOptionBuilder useSetRandomSeedOption() {
+ return new DefaultOptionBuilder()
+ .withLongName(RANDOM_SEED)
+ .withRequired(false)
+ .withArgument(new ArgumentBuilder().withName(RANDOM_SEED).create())
+ .withDescription("Seed to initaize Random Number Generator with")
+ .withShortName("rs");
+ }
/**
* Returns a default command line option for convergence delta specification.
Modified: mahout/trunk/core/src/test/java/org/apache/mahout/clustering/kmeans/TestRandomSeedGenerator.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/test/java/org/apache/mahout/clustering/kmeans/TestRandomSeedGenerator.java?rev=1588439&r1=1588438&r2=1588439&view=diff
==============================================================================
--- mahout/trunk/core/src/test/java/org/apache/mahout/clustering/kmeans/TestRandomSeedGenerator.java (original)
+++ mahout/trunk/core/src/test/java/org/apache/mahout/clustering/kmeans/TestRandomSeedGenerator.java Fri Apr 18 11:13:29 2014
@@ -1,4 +1,4 @@
-/**
+ /**
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
@@ -84,6 +84,35 @@ public final class TestRandomSeedGenerat
clusterCount++;
Cluster cluster = clusterWritable.getValue();
int id = cluster.getId();
+ assertTrue(set.add(id)); // Validate unique id's
+
+ Vector v = cluster.getCenter();
+ assertVectorEquals(RAW[id], v); // Validate values match
+ }
+
+ assertEquals(4, clusterCount); // Validate sample count
+ }
+
+ /** Be sure that the buildRandomSeeded works in the same way as RandomSeedGenerator.buildRandom */
+ @Test
+ public void testRandomSeedGeneratorSeeded() throws Exception {
+ List<VectorWritable> points = getPoints();
+ Job job = new Job();
+ Configuration conf = job.getConfiguration();
+ job.setMapOutputValueClass(VectorWritable.class);
+ Path input = getTestTempFilePath("random-input");
+ Path output = getTestTempDirPath("random-output");
+ ClusteringTestUtils.writePointsToFile(points, input, fs, conf);
+
+ RandomSeedGenerator.buildRandom(conf, input, output, 4, new ManhattanDistanceMeasure(), 1L);
+
+ int clusterCount = 0;
+ Collection<Integer> set = Sets.newHashSet();
+ for (ClusterWritable clusterWritable :
+ new SequenceFileValueIterable<ClusterWritable>(new Path(output, "part-randomSeed"), true, conf)) {
+ clusterCount++;
+ Cluster cluster = clusterWritable.getValue();
+ int id = cluster.getId();
assertTrue(set.add(id)); // validate unique id's
Vector v = cluster.getCenter();
@@ -93,9 +122,47 @@ public final class TestRandomSeedGenerat
assertEquals(4, clusterCount); // validate sample count
}
+ /** Test that initial clusters built with same random seed are reproduced */
+ @Test
+ public void testBuildRandomSeededSameInitalClusters() throws Exception {
+ List<VectorWritable> points = getPoints();
+ Job job = new Job();
+ Configuration conf = job.getConfiguration();
+ job.setMapOutputValueClass(VectorWritable.class);
+ Path input = getTestTempFilePath("random-input");
+ Path output = getTestTempDirPath("random-output");
+ ClusteringTestUtils.writePointsToFile(points, input, fs, conf);
+ long randSeed=1;
+
+ RandomSeedGenerator.buildRandom(conf, input, output, 4, new ManhattanDistanceMeasure(), randSeed);
+
+ int[] clusterIDSeq = new int[4];
+
+ /** run through all clusters once and set sequence of IDs */
+ int clusterCount = 0;
+ for (ClusterWritable clusterWritable :
+ new SequenceFileValueIterable<ClusterWritable>(new Path(output, "part-randomSeed"), true, conf)) {
+ Cluster cluster = clusterWritable.getValue();
+ clusterIDSeq[clusterCount] = cluster.getId();
+ clusterCount++;
+ }
+
+ /* Rebuild cluster and run through again making sure all IDs are in the same random sequence
+ * Needs a better test because in this case passes when seeded with 1 and 2 fails with 1, 3
+ * passes when set to two */
+ RandomSeedGenerator.buildRandom(conf, input, output, 4, new ManhattanDistanceMeasure(), randSeed); clusterCount = 0;
+ for (ClusterWritable clusterWritable :
+ new SequenceFileValueIterable<ClusterWritable>(new Path(output, "part-randomSeed"), true, conf)) {
+ Cluster cluster = clusterWritable.getValue();
+ // Make sure cluster ids are in same random sequence
+ assertEquals(clusterIDSeq[clusterCount], cluster.getId());
+ clusterCount++;
+ }
+ }
+
private static void assertVectorEquals(double[] raw, Vector v) {
assertEquals(raw.length, v.size());
- for (int i=0; i < raw.length; i++) {
+ for (int i = 0; i < raw.length; i++) {
assertEquals(raw[i], v.getQuick(i), EPSILON);
}
}
Modified: mahout/trunk/src/conf/fkmeans.props
URL: http://svn.apache.org/viewvc/mahout/trunk/src/conf/fkmeans.props?rev=1588439&r1=1588438&r2=1588439&view=diff
==============================================================================
--- mahout/trunk/src/conf/fkmeans.props (original)
+++ mahout/trunk/src/conf/fkmeans.props Fri Apr 18 11:13:29 2014
@@ -14,3 +14,4 @@
#cl|clustering = <cluster points if present>
#e|emitMostLikely = <emit most likely cluster if clustering. Default: true>
#t|threshold = <threshold if clustering and not emitMostLikely. Default: 0.0>
+#rs|randomSeed =<Value to seed RNG with if set>
\ No newline at end of file
Modified: mahout/trunk/src/conf/kmeans.props
URL: http://svn.apache.org/viewvc/mahout/trunk/src/conf/kmeans.props?rev=1588439&r1=1588438&r2=1588439&view=diff
==============================================================================
--- mahout/trunk/src/conf/kmeans.props (original)
+++ mahout/trunk/src/conf/kmeans.props Fri Apr 18 11:13:29 2014
@@ -9,4 +9,5 @@
#cl|clustering = <cluster points if present>
#dm|distance = <distance measure class name. Default: SquaredEuclideanDistanceMeasure>
#cd|convergenceDelta = <the convergence threshold. Default: 0.5>
-#r|numReduce = <the number of reduce tasks to launch. Default: 1>
\ No newline at end of file
+#r|numReduce = <the number of reduce tasks to launch. Default: 1>
+#rs|randomSeed =<Value to seed RNG with if set>
\ No newline at end of file