You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by ad...@apache.org on 2009/09/27 20:20:46 UTC
svn commit: r819365 [3/3] - in /lucene/mahout/trunk:
core/src/main/java/org/apache/mahout/df/
core/src/main/java/org/apache/mahout/df/builder/
core/src/main/java/org/apache/mahout/df/callback/
core/src/main/java/org/apache/mahout/df/data/ core/src/main...
Added: lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/DefaultIgSplitTest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/DefaultIgSplitTest.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/DefaultIgSplitTest.java (added)
+++ lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/DefaultIgSplitTest.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,86 @@
+/**
+ * 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.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.df.split;
+
+import static org.apache.mahout.df.data.Utils.double2String;
+import static org.apache.mahout.df.data.Utils.randomDescriptor;
+import static org.apache.mahout.df.data.Utils.randomDoublesWithSameLabel;
+
+import java.util.Random;
+
+import junit.framework.TestCase;
+
+import org.apache.mahout.df.data.Data;
+import org.apache.mahout.df.data.DataLoader;
+import org.apache.mahout.df.data.Dataset;
+import org.apache.mahout.df.data.Utils;
+import org.apache.mahout.df.split.DefaultIgSplit;
+
+public class DefaultIgSplitTest extends TestCase {
+
+ protected final int nbAttributes = 10;
+
+ public void testEntropy() throws Exception {
+ Random rng = new Random();
+ String descriptor = randomDescriptor(rng, nbAttributes);
+ int label = Utils.findLabel(descriptor);
+ double[][] temp;
+ String[] sData;
+ Data data;
+ Dataset dataset;
+ DefaultIgSplit iG;
+
+ // all the vectors have the same label (0)
+ temp = randomDoublesWithSameLabel(rng, descriptor, 100, 0);
+ sData = double2String(temp);
+ dataset = DataLoader.generateDataset(descriptor, sData);
+ data = DataLoader.loadData(dataset, sData);
+ iG = new DefaultIgSplit();
+
+ double expected = 0.0 - 1.0 * Math.log(1.0) / Math.log(2.0);
+ assertEquals(expected, iG.entropy(data));
+
+ // 50/100 of the vectors have the label (1)
+ // 50/100 of the vectors have the label (0)
+ for (int index = 0; index < 50; index++) {
+ temp[index][label] = 1.0;
+ }
+ sData = double2String(temp);
+ dataset = DataLoader.generateDataset(descriptor, sData);
+ data = DataLoader.loadData(dataset, sData);
+ iG = new DefaultIgSplit();
+
+ expected = 2.0 * -0.5 * Math.log(0.5) / Math.log(2.0);
+ assertEquals(expected, iG.entropy(data));
+
+ // 15/100 of the vectors have the label (2)
+ // 35/100 of the vectors have the label (1)
+ // 50/100 of the vectors have the label (0)
+ for (int index = 0; index < 15; index++) {
+ temp[index][label] = 2.0;
+ }
+ sData = double2String(temp);
+ dataset = DataLoader.generateDataset(descriptor, sData);
+ data = DataLoader.loadData(dataset, sData);
+ iG = new DefaultIgSplit();
+
+ expected = -0.15 * Math.log(0.15) / Math.log(2.0) - 0.35 * Math.log(0.35)
+ / Math.log(2.0) - 0.5 * Math.log(0.5) / Math.log(2.0);
+ assertEquals(expected, iG.entropy(data));
+ }
+}
Added: lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/OptIgSplitTest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/OptIgSplitTest.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/OptIgSplitTest.java (added)
+++ lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/OptIgSplitTest.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,58 @@
+/**
+ * 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.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.df.split;
+
+import java.util.Random;
+
+import org.apache.mahout.df.data.Data;
+import org.apache.mahout.df.data.Utils;
+import org.apache.mahout.df.split.DefaultIgSplit;
+import org.apache.mahout.df.split.IgSplit;
+import org.apache.mahout.df.split.OptIgSplit;
+import org.apache.mahout.df.split.Split;
+
+import junit.framework.TestCase;
+
+public class OptIgSplitTest extends TestCase {
+
+ protected final int nbAttributes = 20;
+
+ protected final int numInstances = 100;
+
+ public void testComputeSplit() throws Exception {
+ int n = 100;
+
+ IgSplit ref = new DefaultIgSplit();
+ IgSplit opt = new OptIgSplit();
+
+ Random rng = new Random(1L);
+ Data data = Utils.randomData(rng, nbAttributes, numInstances);
+
+ for (int nloop = 0; nloop < n; nloop++) {
+ int attr = rng.nextInt(data.dataset.nbAttributes());
+ // System.out.println("IsNumerical: " + data.dataset.isNumerical(attr));
+
+ Split expected = ref.computeSplit(data, attr);
+ Split actual = opt.computeSplit(data, attr);
+
+ assertEquals(expected.ig, actual.ig);
+ assertEquals(expected.split, actual.split);
+ }
+ }
+
+}
Added: lucene/mahout/trunk/examples/src/main/java/org/apache/mahout/df/BreimanExample.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/examples/src/main/java/org/apache/mahout/df/BreimanExample.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/examples/src/main/java/org/apache/mahout/df/BreimanExample.java (added)
+++ lucene/mahout/trunk/examples/src/main/java/org/apache/mahout/df/BreimanExample.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,237 @@
+/**
+ * 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.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.df;
+
+import org.apache.commons.cli2.CommandLine;
+import org.apache.commons.cli2.Group;
+import org.apache.commons.cli2.Option;
+import org.apache.commons.cli2.OptionException;
+import org.apache.commons.cli2.builder.ArgumentBuilder;
+import org.apache.commons.cli2.builder.DefaultOptionBuilder;
+import org.apache.commons.cli2.builder.GroupBuilder;
+import org.apache.commons.cli2.commandline.Parser;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.conf.Configured;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.util.Tool;
+import org.apache.hadoop.util.ToolRunner;
+import org.apache.mahout.common.CommandLineUtil;
+import org.apache.mahout.df.builder.DefaultTreeBuilder;
+import org.apache.mahout.df.callback.ForestPredictions;
+import org.apache.mahout.df.callback.MeanTreeCollector;
+import org.apache.mahout.df.callback.MultiCallback;
+import org.apache.mahout.df.data.Data;
+import org.apache.mahout.df.data.DataLoader;
+import org.apache.mahout.df.data.Dataset;
+import org.apache.mahout.df.ref.SequentialBuilder;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+import org.uncommons.maths.Maths;
+
+import java.util.Random;
+
+/**
+ * Test procedure as described in Breiman's paper.<br>
+ * <b>Leo Breiman: Random Forests. Machine Learning 45(1): 5-32 (2001)</b>
+ */
+public class BreimanExample extends Configured implements Tool {
+
+ private static final Logger log = LoggerFactory.getLogger(BreimanExample.class);
+
+ /** sum test error */
+ protected static double sumTestErr;
+
+ /** sum mean tree error */
+ protected static double sumTreeErr;
+
+ /** sum test error with m=1 */
+ protected static double sumOneErr = 0.0;
+
+ /** mean time to build a forest with m=log2(M)+1 */
+ protected static long sumTimeM;
+
+ /** mean time to build a forest with m=1 */
+ protected static long sumTimeOne;
+
+ /**
+ * runs one iteration of the procedure.
+ *
+ * @param data training data
+ * @param m number of random variables to select at each tree-node
+ * @param nbtrees number of trees to grow
+ * @throws Exception if an error occured while growing the trees
+ */
+ protected static void runIteration(Data data, int m, int nbtrees)
+ throws Exception {
+
+ final int dataSize = data.size();
+ final int nblabels = data.dataset.nblabels();
+
+ double oobM; // oob error estimate when m = log2(M)+1
+ double oobOne; // oob error estimate when m = 1
+
+ ForestPredictions errorM; // oob error when using m = log2(M)+1
+ ForestPredictions errorOne; // oob error when using m = 1
+ ForestPredictions testError; // test set error
+ MeanTreeCollector treeError; // mean tree error
+
+ Random rng = new Random(1L);
+
+ Data train = data.clone();
+ Data test = train.rsplit(rng, (int) (data.size() * 0.1));
+
+ int[] trainLabels = train.extractLabels();
+ int[] testLabels = test.extractLabels();
+
+ DefaultTreeBuilder treeBuilder = new DefaultTreeBuilder();
+
+ SequentialBuilder forestBuilder = new SequentialBuilder(rng, treeBuilder, train);
+
+ long time;
+
+ // grow a forest with m = log2(M)+1
+ errorM = new ForestPredictions(dataSize, nblabels);
+ treeBuilder.setM(m);
+
+ time = System.currentTimeMillis();
+ log.info("Growing a forest with m=" + m);
+ DecisionForest forestM = forestBuilder.build(nbtrees, errorM);
+ sumTimeM += System.currentTimeMillis() - time;
+
+ oobM = ErrorEstimate.errorRate(trainLabels, errorM.computePredictions(rng));
+
+ // grow a forest with m=1
+ errorOne = new ForestPredictions(dataSize, nblabels);
+ treeBuilder.setM(1);
+
+ time = System.currentTimeMillis();
+ log.info("Growing a forest with m=1");
+ DecisionForest forestOne = forestBuilder.build(nbtrees, errorOne);
+ sumTimeOne += System.currentTimeMillis() - time;
+
+ oobOne = ErrorEstimate.errorRate(trainLabels, errorOne.computePredictions(rng));
+
+ // compute the test set error (Selection Error), and mean tree error (One Tree Error),
+ // using the lowest oob error forest
+ testError = new ForestPredictions(dataSize, nblabels);
+ treeError = new MeanTreeCollector(train, nbtrees);
+
+ // compute the test set error using m=1 (Single Input Error)
+ errorOne = new ForestPredictions(dataSize, nblabels);
+
+ if (oobM < oobOne) {
+ forestM.classify(test, new MultiCallback(testError, treeError));
+ forestOne.classify(test, errorOne);
+ } else {
+ forestOne.classify(test,
+ new MultiCallback(testError, treeError, errorOne));
+ }
+
+ sumTestErr += ErrorEstimate.errorRate(testLabels, testError.computePredictions(rng));
+ sumOneErr += ErrorEstimate.errorRate(testLabels, errorOne.computePredictions(rng));
+ sumTreeErr += treeError.meanTreeError();
+ }
+
+ public static void main(String[] args) throws Exception {
+ int res = ToolRunner.run(new Configuration(), new BreimanExample(), args);
+ System.exit(res);
+ }
+
+ public int run(String[] args) throws Exception {
+
+ DefaultOptionBuilder obuilder = new DefaultOptionBuilder();
+ ArgumentBuilder abuilder = new ArgumentBuilder();
+ GroupBuilder gbuilder = new GroupBuilder();
+
+ Option dataOpt = obuilder.withLongName("data").withShortName("d").withRequired(true)
+ .withArgument(abuilder.withName("path").withMinimum(1).withMaximum(1).create())
+ .withDescription("Data path").create();
+
+ Option datasetOpt = obuilder.withLongName("dataset").withShortName("ds").withRequired(true)
+ .withArgument(abuilder.withName("dataset").withMinimum(1).withMaximum(1).create())
+ .withDescription("Dataset path").create();
+
+ Option nbtreesOpt = obuilder.withLongName("nbtrees").withShortName("t").withRequired(true)
+ .withArgument(abuilder.withName("nbtrees").withMinimum(1).withMaximum(1).create())
+ .withDescription("Number of trees to grow, each iteration").create();
+
+ Option nbItersOpt = obuilder.withLongName("iterations").withShortName("i").withRequired(true)
+ .withArgument(abuilder.withName("numIterations").withMinimum(1).withMaximum(1).create())
+ .withDescription("Number of times to repeat the test").create();
+
+ Option helpOpt = obuilder.withLongName("help").withDescription("Print out help")
+ .withShortName("h").create();
+
+ Group group = gbuilder.withName("Options").withOption(dataOpt).withOption(datasetOpt)
+ .withOption(nbItersOpt).withOption(nbtreesOpt).withOption(helpOpt).create();
+
+ Path dataPath;
+ Path datasetPath;
+ int nbTrees;
+ int nbIterations;
+
+ try {
+ Parser parser = new Parser();
+ parser.setGroup(group);
+ CommandLine cmdLine = parser.parse(args);
+
+ if (cmdLine.hasOption("help")) {
+ CommandLineUtil.printHelp(group);
+ return -1;
+ }
+
+ String dataName = cmdLine.getValue(dataOpt).toString();
+ String datasetName = cmdLine.getValue(datasetOpt).toString();
+ nbTrees = Integer.parseInt(cmdLine.getValue(nbtreesOpt).toString());
+ nbIterations = Integer.parseInt(cmdLine.getValue(nbItersOpt).toString());
+
+ dataPath = new Path(dataName);
+ datasetPath = new Path(datasetName);
+ } catch (OptionException e) {
+ System.err.println("Exception : " + e);
+ CommandLineUtil.printHelp(group);
+ return -1;
+ }
+
+ // load the data
+ FileSystem fs = dataPath.getFileSystem(new Configuration());
+ Dataset dataset = Dataset.load(getConf(), datasetPath);
+ Data data = DataLoader.loadData(dataset, fs, dataPath);
+
+ // take m to be the first integer less than log2(M) + 1, where M is the
+ // number of inputs
+ int m = (int) Math.floor(Maths.log(2, data.dataset.nbAttributes()) + 1);
+
+ for (int iteration = 0; iteration < nbIterations; iteration++) {
+ log.info("Iteration " + iteration);
+ runIteration(data, m, nbTrees);
+ }
+
+ log.info("********************************************");
+ log.info("Selection error : " + sumTestErr / nbIterations);
+ log.info("Single Input error : " + sumOneErr / nbIterations);
+ log.info("One Tree error : " + sumTreeErr / nbIterations);
+ log.info("");
+ log.info("Mean Random Input Time : " + DFUtils.elapsedTime(sumTimeM / nbIterations));
+ log.info("Mean Single Input Time : " + DFUtils.elapsedTime(sumTimeOne / nbIterations));
+
+ return 0;
+ }
+
+}