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 [1/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...
Author: adeneche
Date: Sun Sep 27 18:20:42 2009
New Revision: 819365
URL: http://svn.apache.org/viewvc?rev=819365&view=rev
Log:
MAHOUT-122 Decision Forests Reference Implementation
Added:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/Bagging.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DFUtils.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DecisionForest.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/ErrorEstimate.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/DefaultTreeBuilder.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/TreeBuilder.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/ForestPredictions.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MeanTreeCollector.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MultiCallback.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/PredictionCallback.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/SingleTreePredictions.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Data.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataConverter.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataLoader.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataUtils.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Dataset.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DescriptorUtils.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Instance.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Condition.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Equals.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/GreaterOrEquals.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Lesser.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/node/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/node/CategoricalNode.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/node/Leaf.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/node/MockLeaf.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/node/Node.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/node/NumericalNode.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/ref/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/ref/SequentialBuilder.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/split/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/split/DefaultIgSplit.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/split/IgSplit.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/split/OptIgSplit.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/split/Split.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/tools/
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/tools/Describe.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/builder/
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/builder/DefaultTreeBuilderTest.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/data/
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/data/DataConverterTest.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/data/DataLoaderTest.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/data/DataTest.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/data/DatasetTest.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/data/DescriptorUtilsTest.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/data/Utils.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/node/
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/node/NodeTest.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/DefaultIgSplitTest.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/df/split/OptIgSplitTest.java
lucene/mahout/trunk/examples/src/main/java/org/apache/mahout/df/
lucene/mahout/trunk/examples/src/main/java/org/apache/mahout/df/BreimanExample.java
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/Bagging.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/Bagging.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/Bagging.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/Bagging.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,80 @@
+/**
+ * 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 java.util.Arrays;
+import java.util.Random;
+
+import org.apache.mahout.df.builder.TreeBuilder;
+import org.apache.mahout.df.callback.PredictionCallback;
+import org.apache.mahout.df.data.Data;
+import org.apache.mahout.df.node.Node;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Builds a tree using bagging
+ */
+public class Bagging {
+
+ private static final Logger log = LoggerFactory.getLogger(Bagging.class);
+
+ protected final TreeBuilder treeBuilder;
+
+ protected final Data data;
+
+ protected final boolean[] sampled;
+
+ public Bagging(TreeBuilder treeBuilder, Data data) {
+ this.treeBuilder = treeBuilder;
+ this.data = data;
+ sampled = new boolean[data.size()];
+ }
+
+ /**
+ * Builds one tree
+ *
+ * @param treeId tree identifier
+ * @param rng
+ * @param callback
+ * @return
+ * @throws RuntimeException if the data is not set
+ */
+ public Node build(int treeId, Random rng, PredictionCallback callback) {
+ log.debug("Bagging...");
+ Arrays.fill(sampled, false);
+ Data bag = data.bagging(rng, sampled);
+
+ log.debug("Building...");
+ Node tree = treeBuilder.build(rng, bag);
+
+ // predict the label for the out-of-bag elements
+ if (callback != null) {
+ log.debug("Oob error estimation");
+ for (int index = 0; index < data.size(); index++) {
+ if (sampled[index] == false) {
+ int prediction = tree.classify(data.get(index));
+ callback.prediction(treeId, index, prediction);
+ }
+ }
+ }
+
+ return tree;
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DFUtils.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DFUtils.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DFUtils.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DFUtils.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,168 @@
+/**
+ * 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 java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.mahout.df.node.Node;
+import org.apache.mahout.ga.watchmaker.OutputUtils;
+
+/**
+ * Utility class that contains various helper methods
+ */
+public class DFUtils {
+
+ /**
+ * Writes an Node[] into a DataOutput
+ *
+ * @param out
+ * @param array
+ * @throws IOException
+ */
+ public static void writeArray(DataOutput out, Node[] array)
+ throws IOException {
+ out.writeInt(array.length);
+ for (Node w : array) {
+ w.write(out);
+ }
+ }
+
+ /**
+ * Reads a Node[] from a DataInput
+ *
+ * @param in
+ * @return
+ * @throws IOException
+ */
+ public static Node[] readNodeArray(DataInput in) throws IOException {
+ int length = in.readInt();
+ Node[] nodes = new Node[length];
+ for (int index = 0; index < length; index++) {
+ nodes[index] = Node.read(in);
+ }
+
+ return nodes;
+ }
+
+ /**
+ * Writes a double[] into a DataOutput
+ *
+ * @param out
+ * @param array
+ * @throws IOException
+ */
+ public static void writeArray(DataOutput out, double[] array)
+ throws IOException {
+ out.writeInt(array.length);
+ for (double value : array) {
+ out.writeDouble(value);
+ }
+ }
+
+ /**
+ * Reads a double[] from a DataInput
+ *
+ * @param in
+ * @return
+ * @throws IOException
+ */
+ public static double[] readDoubleArray(DataInput in) throws IOException {
+ int length = in.readInt();
+ double[] array = new double[length];
+ for (int index = 0; index < length; index++) {
+ array[index] = in.readDouble();
+ }
+
+ return array;
+ }
+
+ /**
+ * Writes an int[] into a DataOutput
+ *
+ * @param out
+ * @param array
+ * @throws IOException
+ */
+ public static void writeArray(DataOutput out, int[] array) throws IOException {
+ out.writeInt(array.length);
+ for (int value : array) {
+ out.writeInt(value);
+ }
+ }
+
+ /**
+ * Reads an int[] from a DataInput
+ *
+ * @param in
+ * @return
+ * @throws IOException
+ */
+ public static int[] readIntArray(DataInput in) throws IOException {
+ int length = in.readInt();
+ int[] array = new int[length];
+ for (int index = 0; index < length; index++) {
+ array[index] = in.readInt();
+ }
+
+ return array;
+ }
+
+ /**
+ * Return a list of all files in the output directory
+ *
+ * @param fs
+ * @param outputPath
+ * @return
+ * @throws IOException
+ * @throws RuntimeException if no file is found
+ */
+ public static Path[] listOutputFiles(FileSystem fs, Path outputPath)
+ throws IOException {
+ Path[] outfiles = OutputUtils.listOutputFiles(fs, outputPath);
+ if (outfiles.length == 0) {
+ throw new IOException("No output found !");
+ }
+
+ return outfiles;
+ }
+
+ /**
+ * Formats a time interval in milliseconds to a String in the form
+ * "hours:minutes:seconds:millis"
+ *
+ * @param milli
+ * @return
+ */
+ public static String elapsedTime(long milli) {
+ long seconds = milli / 1000;
+ milli = milli % 1000;
+
+ long minutes = seconds / 60;
+ seconds = seconds % 60;
+
+ long hours = minutes / 60;
+ minutes = minutes % 60;
+
+ return hours + "h " + minutes + "m " + seconds + "s " + milli;
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DecisionForest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DecisionForest.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DecisionForest.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/DecisionForest.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,152 @@
+/**
+ * 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 java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import org.apache.mahout.df.callback.PredictionCallback;
+import org.apache.mahout.df.data.Data;
+import org.apache.mahout.df.data.DataUtils;
+import org.apache.mahout.df.data.Instance;
+import org.apache.mahout.df.node.Node;
+
+/**
+ * Represents a forest of decision trees.
+ */
+public class DecisionForest {
+
+ protected final List<Node> trees;
+
+ protected DecisionForest() {
+ trees = new ArrayList<Node>();
+ }
+
+ public DecisionForest(List<Node> trees) {
+ assert trees != null && !trees.isEmpty() : "trees argument must not be null or empty";
+
+ this.trees = trees;
+ }
+
+ public List<Node> getTrees() {
+ return trees;
+ }
+
+ /**
+ * Classifies the data and calls callback for each classification
+ *
+ * @param data
+ * @param callback
+ */
+ public void classify(Data data, PredictionCallback callback) {
+ assert callback != null : "callback must not be null";
+
+ if (data.isEmpty())
+ return; // nothing to classify
+
+ for (int treeId = 0; treeId < trees.size(); treeId++) {
+ Node tree = trees.get(treeId);
+
+ for (int index = 0; index < data.size(); index++) {
+ int prediction = tree.classify(data.get(index));
+ callback.prediction(treeId, index, prediction);
+ }
+ }
+ }
+
+ /**
+ * predicts the label for the instance
+ *
+ * @param rng Random number generator, used to break ties randomly
+ * @param instance
+ * @return -1 if the label cannot be predicted
+ */
+ public int classify(Random rng, Instance instance) {
+ int[] predictions = new int[trees.size()];
+
+ for (Node tree : trees) {
+ int prediction = tree.classify(instance);
+ if (prediction != -1)
+ predictions[prediction]++;
+ }
+
+ if (DataUtils.sum(predictions) == 0)
+ return -1; // no prediction available
+
+ return DataUtils.maxindex(rng, predictions);
+ }
+
+ /**
+ * Mean number of nodes per tree
+ *
+ * @return
+ */
+ public long meanNbNodes() {
+ long sum = 0;
+
+ for (Node tree : trees) {
+ sum += tree.nbNodes();
+ }
+
+ return sum / trees.size();
+ }
+
+ /**
+ * Total number of nodes in all the trees
+ *
+ * @return
+ */
+ public long nbNodes() {
+ long sum = 0;
+
+ for (Node tree : trees) {
+ sum += tree.nbNodes();
+ }
+
+ return sum;
+ }
+
+ /**
+ * Mean maximum depth per tree
+ *
+ * @return
+ */
+ public long meanMaxDepth() {
+ long sum = 0;
+
+ for (Node tree : trees) {
+ sum += tree.maxDepth();
+ }
+
+ return sum / trees.size();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj==null || !(obj instanceof DecisionForest))
+ return false;
+
+ DecisionForest rf = (DecisionForest)obj;
+
+ return trees.size() == rf.trees.size() && trees.containsAll(rf.trees);
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/ErrorEstimate.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/ErrorEstimate.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/ErrorEstimate.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/ErrorEstimate.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,82 @@
+/**
+ * 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;
+
+/**
+ * various methods to compute from the output of a random forest
+ */
+public class ErrorEstimate {
+
+ public static double errorRate(int[] labels, int[] predictions) {
+ assert labels.length == predictions.length : "labels.length != predictions.length";
+
+ double nberrors = 0; // number of instance that got bad predictions
+ double datasize = 0; // number of classified instances
+
+ for (int index = 0; index < labels.length; index++) {
+ if (predictions[index] == -1)
+ continue; // instance not classified
+
+ if (predictions[index] != labels[index])
+ nberrors++;
+
+ datasize++;
+ }
+
+ return nberrors / datasize;
+ }
+
+ /**
+ * Counts the number of classified instances (prediction != -1)
+ * @param predictions
+ * @return
+ */
+ public static int nbPredicted(int[] predictions) {
+ int nbpredicted = 0;
+
+ for (int index = 0; index < predictions.length; index++) {
+ if (predictions[index] != -1)
+ nbpredicted++;
+ }
+
+ return nbpredicted;
+ }
+
+ /**
+ * Counts the number of instance that got bad predictions
+ *
+ * @param labels
+ * @param predictions
+ * @return
+ */
+ public static int nbErrors(int[] labels, int[] predictions) {
+ assert labels.length == predictions.length : "labels.length != predictions.length";
+
+ int nberrors = 0;
+
+ for (int index = 0; index < labels.length; index++) {
+ if (predictions[index] == -1)
+ continue; // instance not classified
+
+ if (predictions[index] != labels[index])
+ nberrors++;
+ }
+
+ return nberrors;
+ }
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/DefaultTreeBuilder.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/DefaultTreeBuilder.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/DefaultTreeBuilder.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/DefaultTreeBuilder.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,131 @@
+/**
+ * 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.builder;
+
+import java.util.Arrays;
+import java.util.Random;
+
+import org.apache.commons.lang.ArrayUtils;
+import org.apache.mahout.df.data.Data;
+import org.apache.mahout.df.data.Dataset;
+import org.apache.mahout.df.data.conditions.Condition;
+import org.apache.mahout.df.node.CategoricalNode;
+import org.apache.mahout.df.node.Leaf;
+import org.apache.mahout.df.node.Node;
+import org.apache.mahout.df.node.NumericalNode;
+import org.apache.mahout.df.split.IgSplit;
+import org.apache.mahout.df.split.OptIgSplit;
+import org.apache.mahout.df.split.Split;
+
+/**
+ * Builds a Decision Tree <br>
+ * Based on the algorithm described in the "Decision Trees" tutorials by Andrew
+ * W. Moore, available at:<br>
+ * <br>
+ * http://www.cs.cmu.edu/~awm/tutorials
+ */
+public class DefaultTreeBuilder extends TreeBuilder {
+
+ /** number of attributes to select randomly at each node */
+ protected int m = 1;
+
+ /** IgSplit implementation */
+ protected IgSplit igSplit;
+
+ public DefaultTreeBuilder() {
+ igSplit = new OptIgSplit();
+ }
+
+ public void setM(int m) {
+ this.m = m;
+ }
+
+ public void setIgSplit(IgSplit igSplit) {
+ this.igSplit = igSplit;
+ }
+
+ @Override
+ public Node build(Random rng, Data data) {
+
+ if (data.isEmpty())
+ return new Leaf(-1);
+ if (data.isIdentical())
+ return new Leaf(data.majorityLabel(rng));
+ if (data.identicalLabel())
+ return new Leaf(data.get(0).label);
+
+ int[] attributes = randomAttributes(data.dataset, rng, m);
+
+ // find the best split
+ Split best = null;
+ for (int attr : attributes) {
+ Split split = igSplit.computeSplit(data, attr);
+ if (best == null || best.ig < split.ig)
+ best = split;
+ }
+
+ if (data.dataset.isNumerical(best.attr)) {
+ Data loSubset = data.subset(Condition.lesser(best.attr, best.split));
+ Node loChild = build(rng, loSubset);
+
+ Data hiSubset = data.subset(Condition.greaterOrEquals(best.attr,
+ best.split));
+ Node hiChild = build(rng, hiSubset);
+
+ return new NumericalNode(best.attr, best.split, loChild, hiChild);
+ } else { // CATEGORICAL attribute
+ double[] values = data.values(best.attr);
+ Node[] childs = new Node[values.length];
+
+ for (int index = 0; index < values.length; index++) {
+ Data subset = data.subset(Condition.equals(best.attr, values[index]));
+ childs[index] = build(rng, subset);
+ }
+
+ return new CategoricalNode(best.attr, values, childs);
+ }
+ }
+
+ /**
+ * Randomly selects m attributes to consider for split, excludes IGNORED and
+ * LABEL attributes
+ *
+ * @param dataset
+ * @param rng
+ * @param m number of attributes to select
+ * @return
+ */
+ protected static int[] randomAttributes(Dataset dataset, Random rng, int m) {
+ assert m <= dataset.nbAttributes() : "m > num attributes";
+
+ int[] result = new int[m];
+ int rvalue;
+
+ Arrays.fill(result, -1);
+
+ for (int index = 0; index < m; index++) {
+ do {
+ rvalue = rng.nextInt(dataset.nbAttributes());
+ } while (ArrayUtils.contains(result, rvalue));
+
+ result[index] = rvalue;
+ }
+
+ return result;
+ }
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/TreeBuilder.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/TreeBuilder.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/TreeBuilder.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/builder/TreeBuilder.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,39 @@
+/**
+ * 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.builder;
+
+import java.util.Random;
+
+import org.apache.mahout.df.data.Data;
+import org.apache.mahout.df.node.Node;
+
+/**
+ * Abstract base class for TreeBuilders
+ */
+public abstract class TreeBuilder {
+
+ /**
+ * Builds a Decision tree using the training data
+ *
+ * @param rng random-numbers generator
+ * @param data training data
+ * @return root Node
+ */
+ public abstract Node build(Random rng, Data data);
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/ForestPredictions.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/ForestPredictions.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/ForestPredictions.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/ForestPredictions.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,89 @@
+/**
+ * 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.callback;
+
+import java.util.Arrays;
+import java.util.Random;
+
+import org.apache.mahout.df.data.DataUtils;
+
+/**
+ * Collects a forest's predictions
+ */
+public class ForestPredictions extends PredictionCallback {
+
+ /** predictions[n][label] = number of times instance n was classified 'label' */
+ public final int[][] predictions;
+
+ public ForestPredictions(int nbInstances, int nblabels) {
+ predictions = new int[nbInstances][];
+ for (int index = 0; index < predictions.length; index++) {
+ predictions[index] = new int[nblabels];
+ }
+ }
+
+ @Override
+ public void prediction(int treeId, int instanceId, int prediction) {
+ if (prediction != -1)
+ predictions[instanceId][prediction]++;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null || !(obj instanceof ForestPredictions))
+ return false;
+
+ ForestPredictions fp = (ForestPredictions) obj;
+
+ if (predictions.length != fp.predictions.length) {
+ return false;
+ }
+
+ for (int i = 0; i < predictions.length; i++) {
+ if (!Arrays.equals(predictions[i], fp.predictions[i])) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ /**
+ * compute the prediction for each instance. the prediction of an instance is
+ * the index of the label that got most of the votes
+ *
+ * @param rng
+ * @return
+ */
+ public int[] computePredictions(Random rng) {
+ int[] result = new int[predictions.length];
+ Arrays.fill(result, -1);
+
+ for (int index = 0; index < predictions.length; index++) {
+ if (DataUtils.sum(predictions[index]) == 0)
+ continue; // this instance has not been classified
+
+ result[index] = DataUtils.maxindex(rng, predictions[index]);
+ }
+
+ return result;
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MeanTreeCollector.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MeanTreeCollector.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MeanTreeCollector.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MeanTreeCollector.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,65 @@
+/**
+ * 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.callback;
+
+import org.apache.mahout.df.data.Data;
+
+/**
+ * Computes the error rate for each tree, and returns the mean of all the trees
+ */
+public class MeanTreeCollector extends PredictionCallback {
+
+ /** number of errors for each tree */
+ protected final int nbErrors[];
+
+ /** number of predictions for each tree */
+ protected final int nbPredictions[];
+
+ protected final Data data;
+
+ public MeanTreeCollector(Data data, int nbtrees) {
+ nbErrors = new int[nbtrees];
+ nbPredictions = new int[nbtrees];
+ this.data = data;
+ }
+
+ public double meanTreeError() {
+ double sumerror = 0.0;
+
+ for (int treeId = 0; treeId < nbErrors.length; treeId++) {
+ if (nbPredictions[treeId] == 0)
+ continue; // this tree has 0 predictions
+
+ sumerror += (double) nbErrors[treeId] / nbPredictions[treeId];
+ }
+
+ return sumerror / nbErrors.length;
+ }
+
+ @Override
+ public void prediction(int treeId, int instanceId, int prediction) {
+ if (prediction == -1)
+ return;
+
+ nbPredictions[treeId]++;
+
+ if (data.get(instanceId).label != prediction)
+ nbErrors[treeId]++;
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MultiCallback.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MultiCallback.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MultiCallback.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/MultiCallback.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,38 @@
+/**
+ * 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.callback;
+
+
+/**
+ * Combines many callbacks, that will be called when a prediction is done.
+ */
+public class MultiCallback extends PredictionCallback {
+
+ protected final PredictionCallback[] callbacks;
+
+ public MultiCallback(PredictionCallback... callbacks) {
+ this.callbacks = callbacks;
+ }
+
+ @Override
+ public void prediction(int treeId, int instanceId, int prediction) {
+ for (PredictionCallback callback : callbacks)
+ callback.prediction(treeId, instanceId, prediction);
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/PredictionCallback.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/PredictionCallback.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/PredictionCallback.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/PredictionCallback.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,34 @@
+/**
+ * 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.callback;
+
+
+/**
+ * Called each time an instance has been classified
+ */
+public abstract class PredictionCallback {
+
+ /**
+ * called when an instance has been classified
+ *
+ * @param treeId tree that classified the instance
+ * @param instanceId classified instance
+ * @param prediction predicted label
+ */
+ public abstract void prediction(int treeId, int instanceId, int prediction);
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/SingleTreePredictions.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/SingleTreePredictions.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/SingleTreePredictions.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/callback/SingleTreePredictions.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,49 @@
+/**
+ * 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.callback;
+
+import java.util.Arrays;
+
+/**
+ * Collects the predictions for a single tree
+ */
+public class SingleTreePredictions extends PredictionCallback {
+
+ /** predictions[n] = 'label' predicted for instance 'n' */
+ public final int[] predictions;
+
+ /** used to assert that all the predictions belong to the same tree */
+ private Integer treeId;
+
+ public SingleTreePredictions(int nbInstances) {
+ predictions = new int[nbInstances];
+ Arrays.fill(predictions, -1);
+ }
+
+ @Override
+ public void prediction(int treeId, int instanceId, int prediction) {
+ if (this.treeId == null) {
+ this.treeId = treeId;
+ } else {
+ assert this.treeId == treeId : "the predictions does not belong to the same tree";
+ }
+
+ predictions[instanceId] = prediction;
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Data.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Data.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Data.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Data.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,341 @@
+/**
+ * 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.data;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.hadoop.fs.FSDataInputStream;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.mahout.common.FileLineIterator;
+import org.apache.mahout.df.data.conditions.Condition;
+
+/**
+ * Holds a list of vectors and their corresponding Dataset. contains various
+ * operations that deals with the vectors (subset, count,...)
+ *
+ */
+public class Data {
+
+ protected final List<Instance> instances;
+
+ public final Dataset dataset;
+
+ public Data(Dataset dataset, List<Instance> instances) {
+ this.dataset = dataset;
+ this.instances = new ArrayList<Instance>(instances);
+ }
+
+ /**
+ * Returns the number of elements
+ *
+ * @return
+ */
+ public int size() {
+ return instances.size();
+ }
+
+ /**
+ * Returns true is this data contains no element
+ *
+ * @return
+ */
+ public boolean isEmpty() {
+ return instances.isEmpty();
+ }
+
+ /**
+ * Returns true is this data contains the specified element.
+ *
+ * @param v element whose presence in this list if to be searched
+ * @return
+ */
+ public boolean contains(Instance v) {
+ return instances.contains(v);
+ }
+
+ /**
+ * Returns the index of the first occurrence of the element in this data
+ *
+ * @param v element to search for
+ * @return -1 if the element is not found
+ */
+ public int indexof(Instance v) {
+ return instances.indexOf(v);
+ }
+
+ /**
+ * Returns the element at the specified position
+ *
+ * @param index index of element to return
+ * @return the element at the specified position
+ * @throws IndexOutOfBoundsException if the index is out of range
+ */
+ public Instance get(int index) {
+ return instances.get(index);
+ }
+
+ /**
+ * Returns the subset from this data that matches the given condition
+ *
+ * @param condition
+ * @return
+ */
+ public Data subset(Condition condition) {
+ List<Instance> subset = new ArrayList<Instance>();
+
+ for (Instance instance : instances) {
+ if (condition.isTrueFor(instance))
+ subset.add(instance);
+ }
+
+ return new Data(dataset, subset);
+ }
+
+ /**
+ * Returns a random subset without modifying the current data
+ *
+ * @param rng Random number generator
+ * @param ratio [0,1]
+ * @return
+ */
+ public Data rsubset(Random rng, double ratio) {
+ List<Instance> subset = new ArrayList<Instance>();
+
+ for (Instance instance : instances) {
+ if (rng.nextDouble() < ratio)
+ subset.add(instance);
+ }
+
+ return new Data(dataset, subset);
+ }
+
+ /**
+ * if data has N cases, sample N cases at random -but with replacement.
+ *
+ * @param rng
+ * @return
+ */
+ public Data bagging(Random rng) {
+ int datasize = size();
+ List<Instance> bag = new ArrayList<Instance>(datasize);
+
+ for (int i = 0; i < datasize; i++) {
+ bag.add(instances.get(rng.nextInt(datasize)));
+ }
+
+ return new Data(dataset, bag);
+ }
+
+ /**
+ * if data has N cases, sample N cases at random -but with replacement.
+ *
+ * @param rng
+ * @param sampled indicating which instance has been sampled
+ *
+ * @return sampled data
+ */
+ public Data bagging(Random rng, boolean[] sampled) {
+ int datasize = size();
+ List<Instance> bag = new ArrayList<Instance>(datasize);
+ int index;
+
+ for (int i = 0; i < datasize; i++) {
+ index = rng.nextInt(datasize);
+ bag.add(instances.get(index));
+ sampled[index] = true;
+ }
+
+ return new Data(dataset, bag);
+ }
+
+ /**
+ * Splits the data in two, returns one part, and this gets the rest of the
+ * data. <b>VERY SLOW!</b>
+ *
+ * @param rng
+ * @param ratio ratio of data to return
+ * @return
+ */
+ public Data rsplit(Random rng, int subsize) {
+ List<Instance> subset = new ArrayList<Instance>(subsize);
+
+ for (int i = 0; i < subsize; i++) {
+ subset.add(instances.remove(rng.nextInt(instances.size())));
+ }
+
+ return new Data(dataset, subset);
+ }
+
+
+ /**
+ * checks if all the vectors have identical attribute values
+ *
+ * @return true is all the vectors are identical or the data is empty<br>
+ * false otherwise
+ */
+ public boolean isIdentical() {
+ if (isEmpty())
+ return true;
+
+ Instance instance = get(0);
+ for (int attr = 0; attr < dataset.nbAttributes(); attr++) {
+ for (int index = 1; index < size(); index++) {
+ if (get(index).get(attr) != instance.get(attr))
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+
+ /**
+ * checks if all the vectors have identical label values
+ *
+ * @return
+ */
+ public boolean identicalLabel() {
+ if (isEmpty())
+ return true;
+
+ int label = get(0).label;
+ for (int index = 1; index < size(); index++) {
+ if (get(index).label != label)
+ return false;
+ }
+
+ return true;
+ }
+
+ /**
+ * finds all distinct values of a given attribute
+ *
+ * @param attr
+ * @return
+ */
+ public double[] values(int attr) {
+ Set<Double> result = new HashSet<Double>();
+
+ for (Instance instance : instances) {
+ result.add(instance.get(attr));
+ }
+
+ double[] values = new double[result.size()];
+
+ int index = 0;
+ for (Double value : result) {
+ values[index++] = value;
+ }
+
+ return values;
+ }
+
+ public Data clone() {
+ return new Data(dataset, new ArrayList<Instance>(instances));
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null || !(obj instanceof Data))
+ return false;
+
+ Data data = (Data)obj;
+
+ return instances.equals(data.instances) && dataset.equals(data.dataset);
+ }
+
+ /**
+ * extract the labels of all instances
+ *
+ * @return
+ */
+ public int[] extractLabels() {
+ int[] labels = new int[size()];
+
+ for (int index = 0; index < labels.length; index++) {
+ labels[index] = get(index).label;
+ }
+
+ return labels;
+ }
+
+
+ /**
+ * extract the labels of all instances from a data file
+ *
+ * @param dataset
+ * @param fs file system
+ * @param path data path
+ * @return
+ */
+ public static int[] extractLabels(Dataset dataset, FileSystem fs, Path path) throws IOException {
+ FSDataInputStream input = fs.open(path);
+ FileLineIterator iterator = new FileLineIterator(input);
+
+ int[] labels = new int[dataset.nbInstances()];
+ DataConverter converter = new DataConverter(dataset);
+
+ int index = 0;
+
+ while (iterator.hasNext()) {
+ labels[index++] = converter.convert(0, iterator.next()).label;
+ }
+
+ iterator.close();
+
+ return labels;
+ }
+ /**
+ * finds the majority label, breaking ties randomly
+ *
+ * @param data
+ * @return the majority label value
+ */
+ public int majorityLabel(Random rng) {
+ // count the frequency of each label value
+ int[] counts = new int[dataset.nblabels()];
+
+ for (int index = 0; index < size(); index++) {
+ counts[get(index).label]++;
+ }
+
+ // find the label values that appears the most
+ return DataUtils.maxindex(rng, counts);
+ }
+
+ /**
+ * Counts the number of occurrences of each label value
+
+ * @param counts will contain the results, supposed to be initialized at 0
+ */
+ public void countLabels(int[] counts) {
+ for (int index = 0; index < size(); index++) {
+ counts[get(index).label]++;
+ }
+ }
+
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataConverter.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataConverter.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataConverter.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataConverter.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,72 @@
+/**
+ * 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.data;
+
+import java.util.StringTokenizer;
+
+import org.apache.commons.lang.ArrayUtils;
+import org.apache.mahout.matrix.DenseVector;
+
+/**
+ * Converts String to Instance using a Dataset
+ */
+public class DataConverter {
+
+ protected final Dataset dataset;
+
+ public DataConverter(Dataset dataset) {
+ this.dataset = dataset;
+ }
+
+ public Instance convert(int id, String string) {
+ // all attributes (categorical, numerical), ignored, label
+ int nball = dataset.nbAttributes() + dataset.getIgnored().length + 1;
+
+ StringTokenizer tokenizer = new StringTokenizer(string, ", ");
+ if (tokenizer.countTokens() != nball) {
+ throw new RuntimeException("Wrong number of attributes in the string");
+ }
+
+ int nbattrs = dataset.nbAttributes();
+ DenseVector vector = new DenseVector(nbattrs);
+
+ int aId = 0;
+ int label = -1;
+ for (int attr = 0; attr < nball; attr++) {
+ String token = tokenizer.nextToken();
+
+ if (ArrayUtils.contains(dataset.getIgnored(), attr)) {
+ continue; // IGNORED
+ }
+
+ if (attr == dataset.getLabelId()) {
+ label = dataset.labelCode(token);
+ } else if (dataset.isNumerical(aId)) {
+ vector.set(aId++, Double.parseDouble(token));
+ } else {
+ vector.set(aId, dataset.valueOf(aId, token));
+ aId++;
+ }
+ }
+
+ if (label == -1)
+ throw new RuntimeException("Label not found!");
+
+ return new Instance(id, vector, label);
+ }
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataLoader.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataLoader.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataLoader.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataLoader.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,269 @@
+/**
+ * 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.data;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Scanner;
+import java.util.StringTokenizer;
+
+import org.apache.hadoop.fs.FSDataInputStream;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.mahout.df.data.Dataset.Attribute;
+import org.apache.mahout.matrix.DenseVector;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Converts the input data to a Vector Array using the information given by the
+ * Dataset.<br>
+ * Generates for each line a Vector that contains :<br>
+ * <ul>
+ * <li> double parsed value for NUMERICAL attributes </li>
+ * <li> int value for CATEGORICAL and LABEL attributes </li>
+ * </ul>
+ * <br>
+ * adds an IGNORED first attribute that will contain a unique id for each
+ * instance, which is the line number of the instance in the input data
+ */
+public class DataLoader {
+
+ private static final Logger log = LoggerFactory.getLogger(DataLoader.class);
+
+ /**
+ * Converts a comma-separated String to a Vector.
+ *
+ * @param id unique id for the current instance
+ * @param attrs attributes description
+ * @param values used to convert CATEGORICAL attribute values to Integer
+ * @param string
+ * @return null if there are missing values '?'
+ */
+ protected static Instance parseString(int id, Attribute[] attrs,
+ List<String>[] values, String string) {
+ StringTokenizer tokenizer = new StringTokenizer(string, ", ");
+ if (tokenizer.countTokens() != attrs.length) {
+ log.error(id + ": " + string);
+ throw new RuntimeException("Wrong number of attributes in the string");
+ }
+
+ // extract tokens and check is there is any missing value
+ String[] tokens = new String[attrs.length];
+ for (int attr = 0; attr < attrs.length; attr++) {
+ String token = tokenizer.nextToken();
+
+ if (attrs[attr].isIgnored())
+ continue;
+
+ if ("?".equals(token))
+ return null; // missing value
+
+ tokens[attr] = token;
+ }
+
+ int nbattrs = Dataset.countAttributes(attrs);
+
+ DenseVector vector = new DenseVector(nbattrs);
+
+ int aId = 0;
+ int label = -1;
+ for (int attr = 0; attr < attrs.length; attr++) {
+ if (attrs[attr].isIgnored())
+ continue;
+
+ String token = tokens[attr];
+
+ if (attrs[attr].isNumerical()) {
+ vector.set(aId++, Double.parseDouble(token));
+ } else { // CATEGORICAL or LABEL
+ // update values
+ if (values[attr] == null)
+ values[attr] = new ArrayList<String>();
+ if (!values[attr].contains(token))
+ values[attr].add(token);
+
+ if (attrs[attr].isCategorical()) {
+ vector.set(aId++, values[attr].indexOf(token));
+ } else { // LABEL
+ label = values[attr].indexOf(token);
+ }
+ }
+ }
+
+ if (label == -1)
+ throw new RuntimeException("Label not found!");
+
+ return new Instance(id, vector, label);
+ }
+
+ /**
+ * Loads the data from a file
+ *
+ * @param dataset
+ * @param fs file system
+ * @param fpath data file path
+ * @return
+ * @throws Exception if any problem is encountered
+ */
+
+ @SuppressWarnings("unchecked")
+ public static Data loadData(Dataset dataset, FileSystem fs, Path fpath) throws Exception {
+ FSDataInputStream input = fs.open(fpath);
+ Scanner scanner = new Scanner(input);
+
+ List<Instance> instances = new ArrayList<Instance>();
+
+ DataConverter converter = new DataConverter(dataset);
+
+ while (scanner.hasNextLine()) {
+ String line = scanner.nextLine();
+ if (line.isEmpty()) {
+ log.warn(instances.size() + ": empty string");
+ continue;
+ }
+
+ Instance instance = converter.convert(instances.size(), line);
+ if (instance == null) {
+ // missing values found
+ log.warn(instances.size() + ": missing values");
+ continue;
+ }
+
+ instances.add(instance);
+ }
+
+ scanner.close();
+
+ return new Data(dataset, instances);
+ }
+
+ /**
+ * Loads the data from a String array
+ *
+ * @param dataset
+ * @param data
+ * @return
+ * @throws Exception if any problem is encountered
+ */
+ @SuppressWarnings("unchecked")
+ public static Data loadData(Dataset dataset, String[] data) throws Exception {
+ List<Instance> instances = new ArrayList<Instance>();
+
+ DataConverter converter = new DataConverter(dataset);
+
+ for (String line : data) {
+ if (line.isEmpty()) {
+ log.warn(instances.size() + ": empty string");
+ continue;
+ }
+
+ Instance instance = converter.convert(instances.size(), line);
+ if (instance == null) {
+ // missing values found
+ log.warn(instances.size() + ": missing values");
+ continue;
+ }
+
+ instances.add(instance);
+ }
+
+ return new Data(dataset, instances);
+ }
+
+ /**
+ * Generates the Dataset by parsing the entire data
+ * @param descriptor attributes description
+ * @param fs file system
+ * @param path data path
+ * @return
+ * @throws IOException
+ */
+ @SuppressWarnings("unchecked")
+ public static Dataset generateDataset(String descriptor, FileSystem fs, Path path)
+ throws Exception {
+ Attribute[] attrs = DescriptorUtils.parseDescriptor(descriptor);
+
+ FSDataInputStream input = fs.open(path);
+ Scanner scanner = new Scanner(input);
+
+ // used to convert CATEGORICAL attribute to Integer
+ List<String>[] values = new List[attrs.length];
+
+ int id = 0;
+ while (scanner.hasNextLine()) {
+ String line = scanner.nextLine();
+ if (line.isEmpty()) {
+ continue;
+ }
+
+ if (parseString(id, attrs, values, line) != null) {
+ id++;
+ }
+ }
+
+ scanner.close();
+
+ return new Dataset(attrs, values, id);
+ }
+
+ /**
+ * Generates the Dataset by parsing the entire data
+ * @param descriptor attributes description
+ * @param data
+ * @return
+ * @throws Exception
+ */
+ @SuppressWarnings("unchecked")
+ public static Dataset generateDataset(String descriptor, String[] data) throws Exception {
+ Attribute[] attrs = DescriptorUtils.parseDescriptor(descriptor);
+
+ // used to convert CATEGORICAL and LABEL attributes to Integer
+ List<String>[] values = new List[attrs.length];
+
+ int id = 0;
+ for (int index = 0; index < data.length; index++) {
+ if (data[index].isEmpty()) {
+ continue;
+ }
+
+ if (parseString(id, attrs, values, data[index]) != null) {
+ id++;
+ }
+ }
+
+ return new Dataset(attrs, values, id);
+ }
+
+ /**
+ * constructs the data
+ *
+ * @param attrs attributes description
+ * @param vectors data elements
+ * @param values used to convert CATEGORICAL attributes to Integer
+ * @return
+ * @throws RuntimeException if no LABEL is found in the attributes description
+ */
+ protected static Data constructData(Attribute[] attrs,
+ List<Instance> vectors, List<String>[] values) {
+ Dataset dataset = new Dataset(attrs, values, vectors.size());
+
+ return new Data(dataset, vectors);
+ }
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataUtils.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataUtils.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataUtils.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DataUtils.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,101 @@
+/**
+ * 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.data;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+/**
+ * Helper methods that deals with data lists and arrays of values
+ */
+public class DataUtils {
+
+ /**
+ * Computes the sum of the values
+ *
+ * @param values
+ * @return
+ */
+ public static int sum(int[] values) {
+ int sum = 0;
+ for (int value : values) {
+ sum += value;
+ }
+
+ return sum;
+ }
+
+ /**
+ * foreach i : array1[i] += array2[i]
+ * @param array1
+ * @param array2
+ */
+ public static void add(int[] array1, int[] array2) {
+ assert array1.length == array2.length : "array1.length != array2.length";
+
+ for (int index = 0; index < array1.length; index++) {
+ array1[index] += array2[index];
+ }
+ }
+
+ /**
+ * foreach i : array1[i] -= array2[i]
+ * @param array1
+ * @param array2
+ */
+ public static void dec(int[] array1, int[] array2) {
+ assert array1.length == array2.length : "array1.length != array2.length";
+
+ for (int index = 0; index < array1.length; index++) {
+ array1[index] -= array2[index];
+ }
+ }
+
+ /**
+ * return the index of the maximum of the array, breaking ties randomly
+ *
+ * @param rng used to break ties
+ * @param values
+ * @return index of the maximum
+ */
+ public static int maxindex(Random rng, int[] values) {
+ int max = 0;
+ List<Integer> maxindices = new ArrayList<Integer>();
+
+ for (int index = 0; index < values.length; index++) {
+ if (values[index] > max) {
+ max = values[index];
+ maxindices.clear();
+ maxindices.add(index);
+ } else if (values[index] == max) {
+ maxindices.add(index);
+ }
+ }
+
+ int bestind;
+ if (maxindices.size() > 1) {
+ // break ties randomly
+ bestind = maxindices.get(rng.nextInt(maxindices.size()));
+ } else {
+ bestind = maxindices.get(0);
+ }
+
+ return bestind;
+ }
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Dataset.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Dataset.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Dataset.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Dataset.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,325 @@
+/**
+ * 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.data;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.List;
+
+import org.apache.commons.lang.ArrayUtils;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.fs.FSDataInputStream;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.io.Writable;
+import org.apache.hadoop.io.WritableUtils;
+import org.apache.mahout.df.DFUtils;
+
+/**
+ * Contains informations about the attributes.
+ *
+ */
+public class Dataset implements Writable {
+
+ /**
+ * Attributes type
+ */
+ public enum Attribute {
+ IGNORED, NUMERICAL, CATEGORICAL, LABEL;
+
+ public boolean isNumerical() {
+ return this == NUMERICAL;
+ }
+
+ public boolean isCategorical() {
+ return this == CATEGORICAL;
+ }
+
+ public boolean isLabel() {
+ return this == LABEL;
+ }
+
+ public boolean isIgnored() {
+ return this == IGNORED;
+ }
+ }
+
+ private Attribute[] attributes;
+
+ /** all distinct labels */
+ private String[] labels;
+
+ /** list of ignored attributes */
+ private int[] ignored;
+
+ /** distinct values (CATEGORIAL attributes only) */
+ private String[][] values;
+
+ /** index of the label attribute in the original data */
+ private int labelId;
+
+ /** number of instances in the dataset */
+ private int nbInstances;
+
+ public int nblabels() {
+ return labels.length;
+ }
+
+ public int getLabelId() {
+ return labelId;
+ }
+
+ public int nbInstances() {
+ return nbInstances;
+ }
+
+ /**
+ * Returns the code used to represent the label value in the data
+ *
+ * @param label label's value to code
+ * @return label's code
+ */
+ public int labelCode(String label) {
+ return ArrayUtils.indexOf(labels, label);
+ }
+
+ public String getLabel(int code) {
+ return labels[code];
+ }
+
+ /**
+ * Converts a token to its corresponding int code for a given attribute
+ * @param attr attribute's index
+ * @param token
+ * @return
+ */
+ public int valueOf(int attr, String token) {
+ if (isNumerical(attr)) {
+ throw new RuntimeException("Only for CATEGORICAL attributes");
+ }
+ if (values == null) {
+ throw new RuntimeException("Values not found");
+ }
+
+ return ArrayUtils.indexOf(values[attr], token);
+ }
+
+ public int[] getIgnored() {
+ return ignored;
+ }
+
+ protected Dataset() {
+ }
+
+ /**
+ * Should only be called by a DataLoader
+ *
+ * @param attrs attributes description
+ * @param values distinct values for all CATEGORICAL attributes
+ * @param nbInstances
+ */
+ protected Dataset(Attribute[] attrs, List<String>[] values, int nbInstances) {
+ validateValues(attrs, values);
+
+ int nbattrs = countAttributes(attrs);
+
+ // the label values are set apart
+ attributes = new Attribute[nbattrs];
+ this.values = new String[nbattrs][];
+ ignored = new int[attrs.length - (nbattrs + 1)]; // nbignored = total - (nbattrs + label)
+
+ int ind = 0;
+ labelId = -1;
+ int ignoredId = 0;
+ for (int attr = 0; attr < attrs.length; attr++) {
+ if (attrs[attr].isIgnored()) {
+ ignored[ignoredId++] = attr;
+ continue;
+ }
+
+ if (attrs[attr].isLabel()) {
+ if (labelId != -1) {
+ throw new RuntimeException("Label found more than once");
+ }
+ labelId = attr;
+ continue;
+ }
+
+ if (attrs[attr].isCategorical()) {
+ this.values[ind] = new String[values[attr].size()];
+ values[attr].toArray(this.values[ind]);
+ }
+
+ attributes[ind++] = attrs[attr];
+ }
+
+ if (labelId == -1) {
+ throw new RuntimeException("Label not found");
+ }
+
+ labels = new String[values[labelId].size()];
+ values[labelId].toArray(labels);
+
+ this.nbInstances = nbInstances;
+ }
+
+ /**
+ * Counts the number of attributes, except IGNORED and LABEL
+ *
+ * @param attrs
+ * @return number of attributes that are not IGNORED or LABEL
+ */
+ protected static int countAttributes(Attribute[] attrs) {
+ int nbattrs = 0;
+
+ for (int attr = 0; attr < attrs.length; attr++) {
+ if (attrs[attr].isNumerical() || attrs[attr].isCategorical())
+ nbattrs++;
+ }
+
+ return nbattrs;
+ }
+
+ protected static void validateValues(Attribute[] attrs, List<String>[] values) {
+ assert attrs.length == values.length : "attrs.length != values.length";
+
+ for (int attr = 0; attr < attrs.length; attr++) {
+ if (attrs[attr].isCategorical())
+ assert values[attr] != null : "values not found for attribute N° "
+ + attr;
+ }
+ }
+
+ /**
+ * Number of attributes
+ *
+ * @return
+ */
+ public int nbAttributes() {
+ return attributes.length;
+ }
+
+ /**
+ * Is this a numerical attribute ?
+ *
+ * @param attr index of the attribute to check
+ * @return true if the attribute is numerical
+ */
+ public boolean isNumerical(int attr) {
+ return attributes[attr].isNumerical();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null || !(obj instanceof Dataset))
+ return false;
+
+ Dataset dataset = (Dataset) obj;
+
+ if (!Arrays.equals(attributes, dataset.attributes)) {
+ return false;
+ }
+
+ if (!Arrays.equals(labels, dataset.labels)) {
+ return false;
+ }
+
+ for (int attr = 0; attr < nbAttributes(); attr++) {
+ if (!Arrays.equals(values[attr], dataset.values[attr])) {
+ return false;
+ }
+ }
+
+ return labelId == dataset.labelId && nbInstances == dataset.nbInstances;
+ }
+
+ /**
+ * Loads the dataset from a file
+ * @param fs
+ * @param path
+ * @return
+ * @throws IOException
+ */
+ public static Dataset load(Configuration conf, Path path) throws IOException {
+ FileSystem fs = path.getFileSystem(conf);
+
+ FSDataInputStream input = fs.open(path);
+
+ Dataset dataset = Dataset.read(input);
+ input.close();
+
+ return dataset;
+ }
+
+ public static Dataset read(DataInput in) throws IOException {
+ Dataset dataset = new Dataset();
+
+ dataset.readFields(in);
+ return dataset;
+ }
+
+ public void readFields(DataInput in) throws IOException {
+ int nbAttributes = in.readInt();
+ attributes = new Attribute[nbAttributes];
+ for (int attr = 0; attr < nbAttributes; attr++) {
+ String name = WritableUtils.readString(in);
+ attributes[attr] = Attribute.valueOf(name);
+ }
+
+ labels = WritableUtils.readStringArray(in);
+
+ ignored = DFUtils.readIntArray(in);
+
+ // only CATEGORICAL attributes have values
+ values = new String[nbAttributes][];
+ for (int attr = 0; attr < nbAttributes; attr++) {
+ if (attributes[attr].isCategorical()) {
+ values[attr] = WritableUtils.readStringArray(in);
+ }
+ }
+
+ labelId = in.readInt();
+ nbInstances = in.readInt();
+ }
+
+ public void write(DataOutput out) throws IOException {
+ out.writeInt(attributes.length); // nb attributes
+ for (Attribute attr:attributes) {
+ WritableUtils.writeString(out, attr.name());
+ }
+
+ WritableUtils.writeStringArray(out, labels);
+
+ DFUtils.writeArray(out, ignored);
+
+ // only CATEGORICAL attributes have values
+ for (String[] vals : values) {
+ if (vals != null) {
+ WritableUtils.writeStringArray(out, vals);
+ }
+ }
+
+ out.writeInt(labelId);
+ out.writeInt(nbInstances);
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DescriptorUtils.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DescriptorUtils.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DescriptorUtils.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/DescriptorUtils.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,116 @@
+/**
+ *
+ */
+package org.apache.mahout.df.data;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.StringTokenizer;
+
+import org.apache.mahout.df.data.Dataset.Attribute;
+
+/**
+ * Contains various methods that deal with descriptor strings
+ */
+public class DescriptorUtils {
+
+ /**
+ * Exception throwed when parsing a descriptor
+ *
+ */
+ @SuppressWarnings("serial")
+ public static class DescriptorException extends Exception {
+ public DescriptorException(String msg) {
+ super(msg);
+ }
+ }
+
+ /**
+ * Parses a descriptor string and generates the corresponding array of Attributes
+ *
+ * @param descriptor
+ * @return
+ * @throws DescriptorException if a bad token is encountered
+ */
+ public static Attribute[] parseDescriptor(String descriptor) throws DescriptorException {
+ StringTokenizer tokenizer = new StringTokenizer(descriptor);
+ Attribute[] attributes = new Attribute[tokenizer.countTokens()];
+
+ for (int attr = 0; attr < attributes.length; attr++) {
+ String token = tokenizer.nextToken().toUpperCase();
+ if ("I".equals(token))
+ attributes[attr] = Attribute.IGNORED;
+ else if ("N".equals(token))
+ attributes[attr] = Attribute.NUMERICAL;
+ else if ("C".equals(token))
+ attributes[attr] = Attribute.CATEGORICAL;
+ else if ("L".equals(token)) {
+ attributes[attr] = Attribute.LABEL;
+ } else
+ throw new DescriptorException("Bad Token : " + token);
+ }
+
+ return attributes;
+ }
+
+ /**
+ * Generates a valid descriptor string from a user-friendly representation.<br>
+ * for example "3 N I N N 2 C L 5 I" generates "N N N I N N C C L I I I I I".<br>
+ * this useful when describing datasets with a large number of attributes
+ * @param description
+ * @return
+ * @throws DescriptorException
+ */
+ public static String generateDescriptor(String description) throws DescriptorException {
+ StringTokenizer tokenizer = new StringTokenizer(description, " ");
+ List<String> tokens = new ArrayList<String>();
+
+ while (tokenizer.hasMoreTokens()) {
+ tokens.add(tokenizer.nextToken());
+ }
+
+ return generateDescriptor(tokens);
+ }
+
+ /**
+ * Generates a valid descriptor string from a list of tokens
+ * @param tokens
+ * @return
+ * @throws DescriptorException
+ */
+ public static String generateDescriptor(List<String> tokens) throws DescriptorException {
+ StringBuffer descriptor = new StringBuffer();
+
+ int multiplicator = 0;
+ int number;
+
+ for (String token : tokens) {
+ try {
+ // try to parse an integer
+ number = Integer.parseInt(token);
+
+ if (number <= 0) {
+ throw new DescriptorException("Multiplicator ("+number+") must be > 0");
+ }
+ if (multiplicator > 0) {
+ throw new DescriptorException("A multiplicator cannot be followed by another multiplicator");
+ }
+
+ multiplicator = number;
+ } catch (NumberFormatException e) {
+ // token is not a number
+ if (multiplicator == 0) {
+ multiplicator = 1;
+ }
+
+ for (int index=0;index<multiplicator; index++) {
+ descriptor.append(token).append(' ');
+ }
+
+ multiplicator = 0;
+ }
+ }
+
+ return descriptor.toString().trim();
+ }
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Instance.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Instance.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Instance.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/Instance.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,80 @@
+/**
+ * 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.data;
+
+import org.apache.mahout.matrix.Vector;
+
+/**
+ * Represents one data instance.
+ */
+public class Instance {
+
+ /** instance unique id */
+ public final int id;
+
+ /** attributes, except LABEL and IGNORED */
+ protected final Vector attrs;
+
+ /**
+ * instance label code.<br>
+ * use Dataset.labels to get the real label value
+ *
+ */
+ public final int label;
+
+ public Instance(int id, Vector attrs, int label) {
+ this.id = id;
+ this.attrs = attrs;
+ this.label = label;
+ }
+
+ /**
+ * Return the attribute at the specified position
+ *
+ * @param index position of the attribute to retrieve
+ * @return value of the attribute
+ */
+ public double get(int index) {
+ return attrs.getQuick(index);
+ }
+
+ /**
+ * Set the value at the given index
+ *
+ * @param index
+ * @param value a double value to set
+ */
+ public void set(int index, double value) {
+ attrs.set(index, value);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null || !(obj instanceof Instance))
+ return false;
+
+ Instance instance = (Instance)obj;
+
+ return id == instance.id && label == instance.label && attrs.equals(instance.attrs);
+
+ }
+
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Condition.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Condition.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Condition.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Condition.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,70 @@
+/**
+ * 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.data.conditions;
+
+import org.apache.mahout.df.data.Instance;
+
+/**
+ * Condition on Instance
+ */
+public abstract class Condition {
+
+ /**
+ * Returns true is the checked instance matches the condition
+ *
+ * @param instance checked instance
+ * @return true is the checked instance matches the condition
+ */
+ public abstract boolean isTrueFor(Instance instance);
+
+ /**
+ * Condition that checks if the given attribute has a value "equal" to the
+ * given value
+ *
+ * @param attr
+ * @param value
+ * @return
+ */
+ public static Condition equals(int attr, double value) {
+ return new Equals(attr, value);
+ }
+
+ /**
+ * Condition that checks if the given attribute has a value "lesser" than the
+ * given value
+ *
+ * @param attr
+ * @param value
+ * @return
+ */
+ public static Condition lesser(int attr, double value) {
+ return new Lesser(attr, value);
+ }
+
+ /**
+ * Condition that checks if the given attribute has a value "greater or equal"
+ * than the given value
+ *
+ * @param attr
+ * @param value
+ * @return
+ */
+ public static Condition greaterOrEquals(int attr, double value) {
+ return new GreaterOrEquals(attr, value);
+ }
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Equals.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Equals.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Equals.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Equals.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,41 @@
+/**
+ * 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.data.conditions;
+
+import org.apache.mahout.df.data.Instance;
+
+/**
+ * True if a given attribute has a given value
+ */
+public class Equals extends Condition {
+
+ protected final int attr;
+
+ protected final double value;
+
+ public Equals(int attr, double value) {
+ this.attr = attr;
+ this.value = value;
+ }
+
+ @Override
+ public boolean isTrueFor(Instance instance) {
+ return instance.get(attr) == value;
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/GreaterOrEquals.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/GreaterOrEquals.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/GreaterOrEquals.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/GreaterOrEquals.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,41 @@
+/**
+ * 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.data.conditions;
+
+import org.apache.mahout.df.data.Instance;
+
+/**
+ * True if a given attribute has a value "greater or equal" than a given value
+ */
+public class GreaterOrEquals extends Condition {
+
+ protected final int attr;
+
+ protected final double value;
+
+ public GreaterOrEquals(int attr, double value) {
+ this.attr = attr;
+ this.value = value;
+ }
+
+ @Override
+ public boolean isTrueFor(Instance v) {
+ return v.get(attr) >= value;
+ }
+
+}
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Lesser.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Lesser.java?rev=819365&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Lesser.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/df/data/conditions/Lesser.java Sun Sep 27 18:20:42 2009
@@ -0,0 +1,41 @@
+/**
+ * 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.data.conditions;
+
+import org.apache.mahout.df.data.Instance;
+
+/**
+ * True if a given attribute has a value "lesser" than a given value
+ */
+public class Lesser extends Condition {
+
+ protected final int attr;
+
+ protected final double value;
+
+ public Lesser(int attr, double value) {
+ this.attr = attr;
+ this.value = value;
+ }
+
+ @Override
+ public boolean isTrueFor(Instance instance) {
+ return instance.get(attr) < value;
+ }
+
+}