You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by ro...@apache.org on 2009/10/20 13:32:37 UTC
svn commit: r827037 - in
/lucene/mahout/trunk/core/src/main/java/org/apache/mahout:
classifier/bayes/mapreduce/common/ fpm/pfpgrowth/ fpm/pfpgrowth/convertors/
fpm/pfpgrowth/convertors/integer/ fpm/pfpgrowth/convertors/string/
fpm/pfpgrowth/fpgrowth/
Author: robinanil
Date: Tue Oct 20 11:32:36 2009
New Revision: 827037
URL: http://svn.apache.org/viewvc?rev=827037&view=rev
Log:
Some code cleanup for MAHOUT 0.2
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/classifier/bayes/mapreduce/common/BayesFeatureOutputFormat.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorMapper.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorReducer.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/PFPGrowth.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/ParallelFPGrowthReducer.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TopKPatternsOutputConvertor.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TransactionIterator.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerStringOutputConvertor.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerTupleIterator.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringOutputConvertor.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringTupleIterator.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/TopKStringPatterns.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPGrowth.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTree.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTreeDepthCache.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FrequentPatternMaxHeap.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/Pattern.java
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/classifier/bayes/mapreduce/common/BayesFeatureOutputFormat.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/classifier/bayes/mapreduce/common/BayesFeatureOutputFormat.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/classifier/bayes/mapreduce/common/BayesFeatureOutputFormat.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/classifier/bayes/mapreduce/common/BayesFeatureOutputFormat.java Tue Oct 20 11:32:36 2009
@@ -56,7 +56,6 @@
return "trainer-wordFreq/" + name;
else if(key.stringAt(0).equals(BayesConstants.DOCUMENT_FREQUENCY))
return "trainer-termDocCount/" + name;
- else throw new RuntimeException("Unrecognized Tuple: " + key);
}
else if(key.length() == 2)
{
@@ -64,10 +63,8 @@
return "trainer-featureCount/" + name;
else if(key.stringAt(0).equals(BayesConstants.LABEL_COUNT))
return "trainer-docCount/" + name;
- else throw new RuntimeException("Unrecognized Tuple: " + key);
}
- else
- throw new RuntimeException("Unrecognized Tuple: " + key);
+ throw new RuntimeException("Unrecognized Tuple: " + key);
}
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorMapper.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorMapper.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorMapper.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorMapper.java Tue Oct 20 11:32:36 2009
@@ -23,7 +23,8 @@
import org.apache.mahout.fpm.pfpgrowth.convertors.string.TopKStringPatterns;
import java.io.IOException;
-import java.util.*;
+import java.util.ArrayList;
+import java.util.List;
/**
*
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorReducer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorReducer.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorReducer.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/AggregatorReducer.java Tue Oct 20 11:32:36 2009
@@ -22,7 +22,7 @@
import org.apache.mahout.common.Parameters;
import org.apache.mahout.fpm.pfpgrowth.convertors.string.TopKStringPatterns;
import java.io.IOException;
-import java.util.*;
+import java.util.Iterator;
/**
*
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/PFPGrowth.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/PFPGrowth.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/PFPGrowth.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/PFPGrowth.java Tue Oct 20 11:32:36 2009
@@ -57,45 +57,33 @@
*
*/
public class PFPGrowth {
- private static final Logger log = LoggerFactory.getLogger(PFPGrowth.class);
-
public static Pattern SPLITTER = Pattern.compile("[ ,\t]*[,|\t][ ,\t]*");
- /**
- *
- * @param params params should contain input and output locations as a string
- * value, the additional parameters include minSupport(3),
- * maxHeapSize(50), numGroups(1000)
- * @throws IOException
- * @throws ClassNotFoundException
- * @throws InterruptedException
- */
- public static void runPFPGrowth(Parameters params) throws IOException,
- InterruptedException, ClassNotFoundException {
- startParallelCounting(params);
- startGroupingItems(params);
- startParallelFPGrowth(params);
- startAggregating(params);
- }
+ private static final Logger log = LoggerFactory.getLogger(PFPGrowth.class);
/**
- * Converts a given Map in to a String using DefaultStringifier of Hadoop
+ * Generates the fList from the serialized string representation
*
- * @param map
+ * @param params
+ * @param key
* @param conf
- * @return string representation of the map
+ * @return Deserialized Feature Frequency List
* @throws IOException
*/
- private static String serializeMap(Map<String, Long> map, Configuration conf)
- throws IOException {
+ public static List<Pair<String, Long>> deserializeList(Parameters params,
+ String key, Configuration conf) throws IOException {
+ List<Pair<String, Long>> list = new ArrayList<Pair<String, Long>>();
conf
.set(
"io.serializations",
"org.apache.hadoop.io.serializer.JavaSerialization,org.apache.hadoop.io.serializer.WritableSerialization");
- DefaultStringifier<Map<String, Long>> mapStringifier = new DefaultStringifier<Map<String, Long>>(
- conf, GenericsUtil.getClass(map));
- String serializedMapString = mapStringifier.toString(map);
- return serializedMapString;
+
+ DefaultStringifier<List<Pair<String, Long>>> listStringifier = new DefaultStringifier<List<Pair<String, Long>>>(
+ conf, GenericsUtil.getClass(list));
+ String serializedString = listStringifier.toString(list);
+ serializedString = params.get(key, serializedString);
+ list = listStringifier.fromString(serializedString);
+ return list;
}
/**
@@ -105,7 +93,7 @@
* @param params
* @param key
* @param conf
- * @return
+ * @return Deserialized Group List
* @throws IOException
*/
public static Map<String, Long> deserializeMap(Parameters params, String key,
@@ -125,97 +113,11 @@
}
/**
- * Serializes the fList and returns the string representation of the List
- *
- * @param list
- * @param conf
- * @return
- * @throws IOException
- */
- private static String serializeList(List<Pair<String, Long>> list,
- Configuration conf) throws IOException {
- conf
- .set(
- "io.serializations",
- "org.apache.hadoop.io.serializer.JavaSerialization,org.apache.hadoop.io.serializer.WritableSerialization");
- DefaultStringifier<List<Pair<String, Long>>> listStringifier = new DefaultStringifier<List<Pair<String, Long>>>(
- conf, GenericsUtil.getClass(list));
- String serializedListString = listStringifier.toString(list);
- return serializedListString;
- }
-
- /**
- * Generates the fList from the serialized string representation
- *
- * @param params
- * @param key
- * @param conf
- * @return
- * @throws IOException
- */
- public static List<Pair<String, Long>> deserializeList(Parameters params,
- String key, Configuration conf) throws IOException {
- List<Pair<String, Long>> list = new ArrayList<Pair<String, Long>>();
- conf
- .set(
- "io.serializations",
- "org.apache.hadoop.io.serializer.JavaSerialization,org.apache.hadoop.io.serializer.WritableSerialization");
-
- DefaultStringifier<List<Pair<String, Long>>> listStringifier = new DefaultStringifier<List<Pair<String, Long>>>(
- conf, GenericsUtil.getClass(list));
- String serializedString = listStringifier.toString(list);
- serializedString = params.get(key, serializedString);
- list = listStringifier.fromString(serializedString);
- return list;
- }
-
- /**
- * Count the frequencies of various features in parallel using Map/Reduce
- *
- * @param params
- * @throws IOException
- * @throws InterruptedException
- * @throws ClassNotFoundException
- */
- public static void startParallelCounting(Parameters params)
- throws IOException, InterruptedException, ClassNotFoundException {
-
- Configuration conf = new Configuration();
- conf.set("pfp.parameters", params.toString());
-
- String input = params.get("input");
- Job job = new Job(conf, "Parallel Counting Driver running over input: "
- + input);
- job.setJarByClass(PFPGrowth.class);
-
- job.setOutputKeyClass(Text.class);
- job.setOutputValueClass(LongWritable.class);
-
- FileInputFormat.addInputPath(job, new Path(input));
- Path outPath = new Path(params.get("output") + "/parallelcounting");
- FileOutputFormat.setOutputPath(job, outPath);
-
- FileSystem dfs = FileSystem.get(outPath.toUri(), conf);
- if (dfs.exists(outPath)) {
- dfs.delete(outPath, true);
- }
-
- job.setInputFormatClass(TextInputFormat.class);
- job.setMapperClass(ParallelCountingMapper.class);
- job.setCombinerClass(ParallelCountingReducer.class);
- job.setReducerClass(ParallelCountingReducer.class);
- job.setOutputFormatClass(SequenceFileOutputFormat.class);
-
- job.waitForCompletion(true);
-
- }
-
- /**
* read the feature frequency List which is built at the end of the Parallel
* counting job
*
* @param params
- * @return
+ * @return Feature Frequency List
* @throws IOException
*/
public static List<Pair<String, Long>> readFList(Parameters params)
@@ -284,6 +186,66 @@
}
/**
+ *
+ * @param params params should contain input and output locations as a string
+ * value, the additional parameters include minSupport(3),
+ * maxHeapSize(50), numGroups(1000)
+ * @throws IOException
+ * @throws ClassNotFoundException
+ * @throws InterruptedException
+ */
+ public static void runPFPGrowth(Parameters params) throws IOException,
+ InterruptedException, ClassNotFoundException {
+ startParallelCounting(params);
+ startGroupingItems(params);
+ startParallelFPGrowth(params);
+ startAggregating(params);
+ }
+
+ /**
+ * Run the aggregation Job to aggregate the different TopK patterns and group
+ * each Pattern by the features present in it and thus calculate the final Top
+ * K frequent Patterns for each feature
+ *
+ * @param params
+ * @throws IOException
+ * @throws InterruptedException
+ * @throws ClassNotFoundException
+ */
+ public static void startAggregating(Parameters params) throws IOException,
+ InterruptedException, ClassNotFoundException {
+
+ Configuration conf = new Configuration();
+ params.set("fList", "");
+ params.set("gList", "");
+ conf.set("pfp.parameters", params.toString());
+
+ String input = params.get("output") + "/fpgrowth";
+ Job job = new Job(conf, "PFP Aggregator Driver running over input: "
+ + input);
+ job.setJarByClass(PFPGrowth.class);
+
+ job.setOutputKeyClass(Text.class);
+ job.setOutputValueClass(TopKStringPatterns.class);
+
+ FileInputFormat.addInputPath(job, new Path(input));
+ Path outPath = new Path(params.get("output") + "/frequentPatterns");
+ FileOutputFormat.setOutputPath(job, outPath);
+
+ job.setInputFormatClass(SequenceFileInputFormat.class);
+ job.setMapperClass(AggregatorMapper.class);
+ job.setCombinerClass(AggregatorReducer.class);
+ job.setReducerClass(AggregatorReducer.class);
+ job.setOutputFormatClass(SequenceFileOutputFormat.class);
+
+ FileSystem dfs = FileSystem.get(outPath.toUri(), conf);
+ if (dfs.exists(outPath)) {
+ dfs.delete(outPath, true);
+ }
+ job.waitForCompletion(true);
+ }
+
+ /**
* Group the given Features into g groups as defined by the numGroups
* parameter in params
*
@@ -320,32 +282,29 @@
}
/**
- * Run the Parallel FPGrowth Map/Reduce Job to calculate the Top K features of
- * group dependent shards
+ * Count the frequencies of various features in parallel using Map/Reduce
*
* @param params
* @throws IOException
* @throws InterruptedException
* @throws ClassNotFoundException
*/
- public static void startParallelFPGrowth(Parameters params)
+ public static void startParallelCounting(Parameters params)
throws IOException, InterruptedException, ClassNotFoundException {
Configuration conf = new Configuration();
conf.set("pfp.parameters", params.toString());
String input = params.get("input");
- Job job = new Job(conf, "PFP Growth Driver running over input" + input);
+ Job job = new Job(conf, "Parallel Counting Driver running over input: "
+ + input);
job.setJarByClass(PFPGrowth.class);
- job.setMapOutputKeyClass(LongWritable.class);
- job.setMapOutputValueClass(IntegerTuple.class);
-
job.setOutputKeyClass(Text.class);
- job.setOutputValueClass(TopKStringPatterns.class);
+ job.setOutputValueClass(LongWritable.class);
FileInputFormat.addInputPath(job, new Path(input));
- Path outPath = new Path(params.get("output") + "/fpgrowth");
+ Path outPath = new Path(params.get("output") + "/parallelcounting");
FileOutputFormat.setOutputPath(job, outPath);
FileSystem dfs = FileSystem.get(outPath.toUri(), conf);
@@ -354,53 +313,94 @@
}
job.setInputFormatClass(TextInputFormat.class);
- job.setMapperClass(ParallelFPGrowthMapper.class);
- job.setReducerClass(ParallelFPGrowthReducer.class);
+ job.setMapperClass(ParallelCountingMapper.class);
+ job.setCombinerClass(ParallelCountingReducer.class);
+ job.setReducerClass(ParallelCountingReducer.class);
job.setOutputFormatClass(SequenceFileOutputFormat.class);
job.waitForCompletion(true);
+
}
/**
- * Run the aggregation Job to aggregate the different TopK patterns and group
- * each Pattern by the features present in it and thus calculate the final Top
- * K frequent Patterns for each feature
+ * Run the Parallel FPGrowth Map/Reduce Job to calculate the Top K features of
+ * group dependent shards
*
* @param params
* @throws IOException
* @throws InterruptedException
* @throws ClassNotFoundException
*/
- public static void startAggregating(Parameters params) throws IOException,
- InterruptedException, ClassNotFoundException {
+ public static void startParallelFPGrowth(Parameters params)
+ throws IOException, InterruptedException, ClassNotFoundException {
Configuration conf = new Configuration();
- params.set("fList", "");
- params.set("gList", "");
conf.set("pfp.parameters", params.toString());
- String input = params.get("output") + "/fpgrowth";
- Job job = new Job(conf, "PFP Aggregator Driver running over input: "
- + input);
+ String input = params.get("input");
+ Job job = new Job(conf, "PFP Growth Driver running over input" + input);
job.setJarByClass(PFPGrowth.class);
+ job.setMapOutputKeyClass(LongWritable.class);
+ job.setMapOutputValueClass(IntegerTuple.class);
+
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(TopKStringPatterns.class);
FileInputFormat.addInputPath(job, new Path(input));
- Path outPath = new Path(params.get("output") + "/frequentPatterns");
+ Path outPath = new Path(params.get("output") + "/fpgrowth");
FileOutputFormat.setOutputPath(job, outPath);
- job.setInputFormatClass(SequenceFileInputFormat.class);
- job.setMapperClass(AggregatorMapper.class);
- job.setCombinerClass(AggregatorReducer.class);
- job.setReducerClass(AggregatorReducer.class);
- job.setOutputFormatClass(SequenceFileOutputFormat.class);
-
FileSystem dfs = FileSystem.get(outPath.toUri(), conf);
if (dfs.exists(outPath)) {
dfs.delete(outPath, true);
}
+
+ job.setInputFormatClass(TextInputFormat.class);
+ job.setMapperClass(ParallelFPGrowthMapper.class);
+ job.setReducerClass(ParallelFPGrowthReducer.class);
+ job.setOutputFormatClass(SequenceFileOutputFormat.class);
+
job.waitForCompletion(true);
}
+
+ /**
+ * Serializes the fList and returns the string representation of the List
+ *
+ * @param list
+ * @param conf
+ * @return Serialized String representation of List
+ * @throws IOException
+ */
+ private static String serializeList(List<Pair<String, Long>> list,
+ Configuration conf) throws IOException {
+ conf
+ .set(
+ "io.serializations",
+ "org.apache.hadoop.io.serializer.JavaSerialization,org.apache.hadoop.io.serializer.WritableSerialization");
+ DefaultStringifier<List<Pair<String, Long>>> listStringifier = new DefaultStringifier<List<Pair<String, Long>>>(
+ conf, GenericsUtil.getClass(list));
+ String serializedListString = listStringifier.toString(list);
+ return serializedListString;
+ }
+
+ /**
+ * Converts a given Map in to a String using DefaultStringifier of Hadoop
+ *
+ * @param map
+ * @param conf
+ * @return Serialized String representation of the GList Map
+ * @throws IOException
+ */
+ private static String serializeMap(Map<String, Long> map, Configuration conf)
+ throws IOException {
+ conf
+ .set(
+ "io.serializations",
+ "org.apache.hadoop.io.serializer.JavaSerialization,org.apache.hadoop.io.serializer.WritableSerialization");
+ DefaultStringifier<Map<String, Long>> mapStringifier = new DefaultStringifier<Map<String, Long>>(
+ conf, GenericsUtil.getClass(map));
+ String serializedMapString = mapStringifier.toString(map);
+ return serializedMapString;
+ }
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/ParallelFPGrowthReducer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/ParallelFPGrowthReducer.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/ParallelFPGrowthReducer.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/ParallelFPGrowthReducer.java Tue Oct 20 11:32:36 2009
@@ -61,7 +61,7 @@
private int minSupport = 3;
@Override
- public void reduce(LongWritable key, Iterable<IntegerTuple> values,
+ protected void reduce(LongWritable key, Iterable<IntegerTuple> values,
Context context) throws IOException {
FPGrowth<Integer> fpGrowth = new FPGrowth<Integer>();
fpGrowth
@@ -77,7 +77,7 @@
}
@Override
- public void setup(Context context) throws IOException, InterruptedException {
+ protected void setup(Context context) throws IOException, InterruptedException {
super.setup(context);
Parameters params = Parameters.fromString(context.getConfiguration().get(
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TopKPatternsOutputConvertor.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TopKPatternsOutputConvertor.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TopKPatternsOutputConvertor.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TopKPatternsOutputConvertor.java Tue Oct 20 11:32:36 2009
@@ -26,7 +26,7 @@
import org.apache.mahout.fpm.pfpgrowth.fpgrowth.FrequentPatternMaxHeap;
import org.apache.mahout.fpm.pfpgrowth.fpgrowth.Pattern;
-final public class TopKPatternsOutputConvertor<AttributePrimitive> implements
+public final class TopKPatternsOutputConvertor<AttributePrimitive> implements
OutputCollector<Integer, FrequentPatternMaxHeap> {
private OutputCollector<AttributePrimitive, List<Pair<List<AttributePrimitive>, Long>>> collector = null;
@@ -41,7 +41,7 @@
}
@Override
- final public void collect(Integer key, FrequentPatternMaxHeap value)
+ public final void collect(Integer key, FrequentPatternMaxHeap value)
throws IOException {
List<Pair<List<AttributePrimitive>, Long>> perAttributePatterns = new ArrayList<Pair<List<AttributePrimitive>, Long>>();
for (Pattern itemSet : value.getHeap()) {
@@ -50,7 +50,7 @@
frequentPattern.add(reverseMapping.get(itemSet.getPattern()[j]));
}
Pair<List<AttributePrimitive>, Long> returnItemSet = new Pair<List<AttributePrimitive>, Long>(
- frequentPattern, itemSet.getSupport());
+ frequentPattern, itemSet.support());
perAttributePatterns.add(returnItemSet);
}
collector.collect(reverseMapping.get(key), perAttributePatterns);
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TransactionIterator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TransactionIterator.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TransactionIterator.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/TransactionIterator.java Tue Oct 20 11:32:36 2009
@@ -26,7 +26,7 @@
private Iterator<List<AttributePrimitive>> iterator = null;
- int[] transactionBuffer = null;
+ private int[] transactionBuffer = null;
public TransactionIterator(Iterator<List<AttributePrimitive>> iterator,
Map<AttributePrimitive, Integer> attributeIdMapping) {
@@ -36,12 +36,12 @@
}
@Override
- public boolean hasNext() {
+ public final boolean hasNext() {
return iterator.hasNext();
}
@Override
- public int[] next() {
+ public final int[] next() {
List<AttributePrimitive> transaction = iterator.next();
int index = 0;
for (AttributePrimitive Attribute : transaction) {
@@ -57,7 +57,7 @@
}
@Override
- public void remove() {
+ public final void remove() {
iterator.remove();
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerStringOutputConvertor.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerStringOutputConvertor.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerStringOutputConvertor.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerStringOutputConvertor.java Tue Oct 20 11:32:36 2009
@@ -28,9 +28,9 @@
public final class IntegerStringOutputConvertor implements
OutputCollector<Integer, List<Pair<List<Integer>, Long>>> {
- OutputCollector<Text, TopKStringPatterns> collector = null;
+ private OutputCollector<Text, TopKStringPatterns> collector = null;
- List<String> featureReverseMap = null;
+ private List<String> featureReverseMap = null;
public IntegerStringOutputConvertor(
OutputCollector<Text, TopKStringPatterns> collector,
@@ -40,7 +40,7 @@
}
@Override
- final public void collect(Integer key, List<Pair<List<Integer>, Long>> value)
+ public final void collect(Integer key, List<Pair<List<Integer>, Long>> value)
throws IOException {
String StringKey = featureReverseMap.get(key);
List<Pair<List<String>, Long>> stringValues = new ArrayList<Pair<List<String>, Long>>();
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerTupleIterator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerTupleIterator.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerTupleIterator.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/integer/IntegerTupleIterator.java Tue Oct 20 11:32:36 2009
@@ -31,18 +31,18 @@
}
@Override
- final public boolean hasNext() {
+ public final boolean hasNext() {
return iterator.hasNext();
}
@Override
- final public List<Integer> next() {
+ public final List<Integer> next() {
IntegerTuple transaction = iterator.next();
return transaction.getEntries();
}
@Override
- final public void remove() {
+ public final void remove() {
iterator.remove();
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringOutputConvertor.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringOutputConvertor.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringOutputConvertor.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringOutputConvertor.java Tue Oct 20 11:32:36 2009
@@ -26,7 +26,7 @@
public final class StringOutputConvertor implements
OutputCollector<String, List<Pair<List<String>, Long>>> {
- OutputCollector<Text, TopKStringPatterns> collector = null;
+ private OutputCollector<Text, TopKStringPatterns> collector = null;
public StringOutputConvertor(
OutputCollector<Text, TopKStringPatterns> collector) {
@@ -34,7 +34,7 @@
}
@Override
- final public void collect(String key, List<Pair<List<String>, Long>> value)
+ public final void collect(String key, List<Pair<List<String>, Long>> value)
throws IOException {
collector.collect(new Text(key), new TopKStringPatterns(value));
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringTupleIterator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringTupleIterator.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringTupleIterator.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/StringTupleIterator.java Tue Oct 20 11:32:36 2009
@@ -31,18 +31,18 @@
}
@Override
- final public boolean hasNext() {
+ public final boolean hasNext() {
return iterator.hasNext();
}
@Override
- final public List<String> next() {
+ public final List<String> next() {
StringTuple transaction = iterator.next();
return transaction.getEntries();
}
@Override
- final public void remove() {
+ public final void remove() {
iterator.remove();
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/TopKStringPatterns.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/TopKStringPatterns.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/TopKStringPatterns.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/convertors/string/TopKStringPatterns.java Tue Oct 20 11:32:36 2009
@@ -40,15 +40,15 @@
frequentPatterns.addAll(patterns);
}
- final public Iterator<Pair<List<String>, Long>> iterator() {
+ public final Iterator<Pair<List<String>, Long>> iterator() {
return frequentPatterns.iterator();
}
- final public List<Pair<List<String>, Long>> getPatterns() {
+ public final List<Pair<List<String>, Long>> getPatterns() {
return frequentPatterns;
}
- final public TopKStringPatterns merge(TopKStringPatterns pattern, int heapSize) {
+ public final TopKStringPatterns merge(TopKStringPatterns pattern, int heapSize) {
List<Pair<List<String>, Long>> patterns = new ArrayList<Pair<List<String>, Long>>();
Iterator<Pair<List<String>, Long>> myIterator = frequentPatterns.iterator();
Iterator<Pair<List<String>, Long>> otherIterator = pattern.iterator();
@@ -96,7 +96,7 @@
}
@Override
- final public void readFields(DataInput in) throws IOException {
+ public final void readFields(DataInput in) throws IOException {
frequentPatterns.clear();
int length = in.readInt();
for (int i = 0; i < length; i++) {
@@ -114,7 +114,7 @@
}
@Override
- final public void write(DataOutput out) throws IOException {
+ public final void write(DataOutput out) throws IOException {
out.writeInt(frequentPatterns.size());
for (Pair<List<String>, Long> pattern : frequentPatterns) {
out.writeInt(pattern.getFirst().size());
@@ -128,7 +128,7 @@
}
@Override
- final public String toString() {
+ public final String toString() {
StringBuilder sb = new StringBuilder();
String sep = "";
for (Pair<List<String>, Long> pattern : frequentPatterns) {
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPGrowth.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPGrowth.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPGrowth.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPGrowth.java Tue Oct 20 11:32:36 2009
@@ -53,154 +53,136 @@
private static final Logger log = LoggerFactory.getLogger(FPGrowth.class);
- /**
- * Create FPTree with node counts incremented by addCount variable given the
- * root node and the List of Attributes in transaction sorted by support
- *
- * @param TransactionTree object to which the transaction has to be added to
- * @param myList List of transactions sorted by support
- * @param addCount amount by which the Node count has to be incremented
- * @param minSupport the MutableLong value which contains the current value(dynamic) of support
- * @param attributeFrequency the list of attributes and their frequency
- * @return the number of new nodes added
- */
- final private int treeAddCount(FPTree tree, int[] myList, int addCount,
- MutableLong minSupport, long[] attributeFrequency) {
- int temp = FPTree.ROOTNODEID;
- int ret = 0;
- boolean addCountMode = true;
- int child = -1;
- for (int attribute : myList) {
- if (attributeFrequency[attribute] < minSupport.intValue())
- return ret;
- if (addCountMode) {
- child = tree.childWithAttribute(temp, attribute);
- if (child == -1) {
- addCountMode = false;
- } else {
- tree.addCount(child, addCount);
- temp = child;
- }
- }
- if (!addCountMode) {
- child = tree.createNode(temp, attribute, addCount);
- temp = child;
- ret++;
- }
- }
+ public static List<Pair<String, TopKStringPatterns>> readFrequentPattern(
+ FileSystem fs, Configuration conf, Path path) throws IOException {
+ List<Pair<String, TopKStringPatterns>> ret = new ArrayList<Pair<String, TopKStringPatterns>>();
+ Text key = new Text();
+ TopKStringPatterns value = new TopKStringPatterns();
+ SequenceFile.Reader reader = new SequenceFile.Reader(fs, path, conf);
+ // key is feature value is count
+ while (reader.next(key, value)) {
+ ret.add(new Pair<String, TopKStringPatterns>(key.toString(),
+ new TopKStringPatterns(value.getPatterns())));
+ }
return ret;
-
}
- private FrequentPatternMaxHeap generateSinglePathPatterns(FPTree tree, int K,
- MutableLong minSupportMutable) {
- FrequentPatternMaxHeap frequentPatterns = new FrequentPatternMaxHeap(K);
+ /**
+ * Generate the Feature Frequency list from the given transaction whose
+ * frequency > minSupport
+ *
+ * @param transactions Iterator over the transaction database
+ * @param minSupport minSupport of the feature to be included
+ * @return the List of features and their associated frequency as a Pair
+ * @throws IOException
+ */
+ public final List<Pair<AttributePrimitive, Long>> generateFList(
+ Iterator<List<AttributePrimitive>> transactions, int minSupport)
+ throws IOException {
- int tempNode = FPTree.ROOTNODEID;
- Pattern frequentItem = new Pattern();
- while (true) {
- if (tree.childCount(tempNode) == 0) {
- break;
- } else {
- if (tree.childCount(tempNode) > 1) {
- log.info("This should not happen {} {}", tree.childCount(tempNode),
- tempNode);
- }
- tempNode = tree.childAtIndex(tempNode, 0);
- if (tree.count(tempNode) < minSupportMutable.intValue()) {
- continue;
- }
- frequentItem.add(tree.attribute(tempNode), tree.count(tempNode));
+ final Map<AttributePrimitive, MutableLong> AttributeSupport = new HashMap<AttributePrimitive, MutableLong>();
+ int count = 0;
+ while (transactions.hasNext()) {
+ List<AttributePrimitive> transaction = transactions.next();
+ for (AttributePrimitive attribute : transaction) {
+ if (AttributeSupport.containsKey(attribute) == false)
+ AttributeSupport.put(attribute, new MutableLong(1));
+ else
+ AttributeSupport.get(attribute).increment();
+ count++;
}
}
- if (frequentItem.length > 0) {
- frequentPatterns.insert(frequentItem);
- }
-
- return frequentPatterns;
- }
-
- private void traverseAndBuildConditionalFPTreeData(int firstConditionalNode,
- MutableLong minSupportMutable, FPTree conditionalTree, FPTree tree) {
-
- // Build Subtable
- int conditionalNode = firstConditionalNode;
+ List<Pair<AttributePrimitive, Long>> fList = new ArrayList<Pair<AttributePrimitive, Long>>();
+ for (Entry<AttributePrimitive, MutableLong> e : AttributeSupport.entrySet())
+ fList.add(new Pair<AttributePrimitive, Long>(e.getKey(), e.getValue()
+ .longValue()));
+ Collections.sort(fList, new Comparator<Pair<AttributePrimitive, Long>>() {
- while (conditionalNode != -1) {
- long nextNodeCount = tree.count(conditionalNode);
- int pathNode = tree.parent(conditionalNode);
- int prevConditional = -1;
+ @Override
+ public int compare(Pair<AttributePrimitive, Long> o1,
+ Pair<AttributePrimitive, Long> o2) {
+ int ret = o2.getSecond().compareTo(o1.getSecond());
+ if (ret != 0)
+ return ret;
+ return o1.getFirst().compareTo(o2.getFirst());
+ }
- while (0 != pathNode) { // dummy root node
- int attribute = tree.attribute(pathNode);
- if (tree.getHeaderSupportCount(attribute) < minSupportMutable
- .intValue()) {
- pathNode = tree.parent(pathNode);
- continue;
- }
- // update and increment the headerTable Counts
- conditionalTree.addHeaderCount(attribute, nextNodeCount);
+ });
- int conditional = tree.conditional(pathNode);
- // if its a new conditional tree node
+ return fList;
+ }
- if (conditional == 0) {
- tree.setConditional(pathNode, conditionalTree.createConditionalNode(
- attribute, 0));
- conditional = tree.conditional(pathNode);
- conditionalTree.addHeaderNext(attribute, conditional);
- } else {
- conditionalTree.setSinglePath(false);
- }
+ /**
+ * Generate Top K Frequent Patterns for every feature in returnableFeatures
+ * given a stream of transactions and the minimum support
+ *
+ * @param transactionStream Iterator of transaction
+ * @param frequencyList list of frequent features and their support value
+ * @param minSupport minimum support of the transactions
+ * @param K Number of top frequent patterns to keep
+ * @param returnableFeatures set of features for which the frequent patterns
+ * are mined. If the set is null, then top K patterns for every
+ * frequent item (an item whose support> minSupport) is generated
+ * @param output The output collector to which the the generated patterns are
+ * written
+ * @throws IOException
+ */
+ public final void generateTopKFrequentPatterns(
+ Iterator<List<AttributePrimitive>> transactionStream,
+ List<Pair<AttributePrimitive, Long>> frequencyList,
+ long minSupport,
+ int K,
+ Set<AttributePrimitive> returnableFeatures,
+ OutputCollector<AttributePrimitive, List<Pair<List<AttributePrimitive>, Long>>> output)
+ throws IOException {
- if (prevConditional != -1) { // if there is a child element
- conditionalTree.setParent(prevConditional, conditional);
- }
+ Map<Integer, AttributePrimitive> reverseMapping = new HashMap<Integer, AttributePrimitive>();
+ Map<AttributePrimitive, Integer> attributeIdMapping = new HashMap<AttributePrimitive, Integer>();
- conditionalTree.addCount(conditional, nextNodeCount);
- prevConditional = conditional;
+ int id = 0;
+ for (Pair<AttributePrimitive, Long> feature : frequencyList) {
+ AttributePrimitive attrib = feature.getFirst();
+ Long frequency = feature.getSecond();
+ if (frequency.longValue() < minSupport)
+ continue;
+ attributeIdMapping.put(attrib, Integer.valueOf(id));
+ reverseMapping.put(Integer.valueOf(id++), attrib);
+ }
- pathNode = tree.parent(pathNode);
+ final long[] attributeFrequency = new long[attributeIdMapping.size()];
+ for (Pair<AttributePrimitive, Long> feature : frequencyList) {
+ AttributePrimitive attrib = feature.getFirst();
+ Long frequency = feature.getSecond();
+ if (frequency.longValue() < minSupport)
+ break;
+ attributeFrequency[attributeIdMapping.get(attrib)] = frequency
+ .longValue();
+ }
- }
- if (prevConditional != -1) {
- conditionalTree.setParent(prevConditional, FPTree.ROOTNODEID);
- if (conditionalTree.childCount(FPTree.ROOTNODEID) > 1
- && conditionalTree.singlePath()) {
- conditionalTree.setSinglePath(false);
+ log.info("Number of unique items {}", frequencyList.size());
+ Set<Integer> returnFeatures = new HashSet<Integer>();
+ if (returnableFeatures.isEmpty() == false) {
+ for (AttributePrimitive attrib : returnableFeatures) {
+ if (attributeIdMapping.containsKey(attrib)) {
+ returnFeatures.add(attributeIdMapping.get(attrib));
+ log.info("Adding Pattern {}=>{}", attrib, attributeIdMapping
+ .get(attrib));
}
}
- conditionalNode = tree.next(conditionalNode);
+ } else {
+ for (int j = 0; j < attributeIdMapping.size(); j++)
+ returnFeatures.add(j);
}
- tree.clearConditional();
- conditionalTree.reorderHeaderTable();
-
- }
-
- final private FrequentPatternMaxHeap mergeHeap(
- FrequentPatternMaxHeap frequentPatterns,
- FrequentPatternMaxHeap returnedPatterns, int attribute, long count,
- boolean addAttribute, boolean subPatternCheck) {
- TreeSet<Pattern> myHeap = returnedPatterns.getHeap();
- Iterator<Pattern> it = myHeap.iterator();
+ log.info("Number of unique pruned items {}", attributeIdMapping.size());
+ generateTopKFrequentPatterns(new TransactionIterator<AttributePrimitive>(
+ transactionStream, attributeIdMapping), attributeFrequency, minSupport,
+ K, reverseMapping.size(), returnFeatures,
+ new TopKPatternsOutputConvertor<AttributePrimitive>(output,
+ reverseMapping));
- while (it.hasNext()) {
- Pattern pattern = it.next();
- long support = Math.min(count, pattern.getSupport());
- if (frequentPatterns.addable(support)) {
- pattern.add(attribute, count);
- frequentPatterns.insert(pattern, subPatternCheck);
- }
- }
- if (frequentPatterns.addable(count) && addAttribute) {
- Pattern p = new Pattern();
- p.add(attribute, count);
- frequentPatterns.insert(p, subPatternCheck);
- }
- return frequentPatterns;
}
/**
@@ -215,7 +197,7 @@
* @return Top K Frequent Patterns for each feature and their support
* @throws IOException
*/
- final private Map<Integer, FrequentPatternMaxHeap> fpGrowth(FPTree tree,
+ private final Map<Integer, FrequentPatternMaxHeap> fpGrowth(FPTree tree,
MutableLong minSupportMutable, int K, Set<Integer> requiredFeatures,
TopKPatternsOutputConvertor<AttributePrimitive> outputCollector)
throws IOException {
@@ -237,41 +219,126 @@
minSupportValue = Math.max(minSupportValue, minSupport.intValue() / 2);
log.info("Found {} Patterns with Least Support {}", Patterns
- .get(attribute).count, Patterns.get(attribute).least.support);
+ .get(attribute).count(), Patterns.get(attribute).leastSupport());
}
log.info("Tree Cache: First Level: Cache hits={} Cache Misses={}",
treeCache.getHits(), treeCache.getMisses());
return Patterns;
}
- final private FrequentPatternMaxHeap growth(FPTree tree,
- MutableLong minSupportMutable, int K, FPTreeDepthCache treeCache,
- int level, int currentAttribute) {
+ private FrequentPatternMaxHeap generateSinglePathPatterns(FPTree tree, int K,
+ MutableLong minSupportMutable) {
FrequentPatternMaxHeap frequentPatterns = new FrequentPatternMaxHeap(K);
- FrequentPatternMaxHeap returnedPatterns = null;
-
- int i = Arrays.binarySearch(tree.getHeaderTableAttributes(),
- currentAttribute);
- if (i < 0)
- return frequentPatterns;
-
- for (int j = tree.getHeaderTableCount(); i < j; i++) {
- int attribute = tree.getAttributeAtIndex(i);
- long count = tree.getHeaderSupportCount(attribute);
- if (count < minSupportMutable.intValue())
- continue;
-
- FPTree conditionalTree = treeCache.getFirstLevelTree(attribute);
- if (conditionalTree.isEmpty()) {
- traverseAndBuildConditionalFPTreeData(tree.getHeaderNext(attribute),
- minSupportMutable, conditionalTree, tree);
- }
-
- if (attribute == currentAttribute) {
- returnedPatterns = growthTopDown(conditionalTree, minSupportMutable, K,
- treeCache, level + 1, true, currentAttribute);
- frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
+ int tempNode = FPTree.ROOTNODEID;
+ Pattern frequentItem = new Pattern();
+ while (true) {
+ if (tree.childCount(tempNode) == 0) {
+ break;
+ } else {
+ if (tree.childCount(tempNode) > 1) {
+ log.info("This should not happen {} {}", tree.childCount(tempNode),
+ tempNode);
+ }
+ tempNode = tree.childAtIndex(tempNode, 0);
+ if (tree.count(tempNode) < minSupportMutable.intValue()) {
+ continue;
+ }
+ frequentItem.add(tree.attribute(tempNode), tree.count(tempNode));
+ }
+ }
+ if (frequentItem.length() > 0) {
+ frequentPatterns.insert(frequentItem);
+ }
+
+ return frequentPatterns;
+ }
+
+ /**
+ * Internal TopKFrequentPattern Generation algorithm, which represents the
+ * AttributePrimitives as integers and transforms features to use only
+ * integers
+ *
+ * @param transactions Transaction database Iterator
+ * @param attributeFrequency array representing the Frequency of the
+ * corresponding attribute id
+ * @param minSupport minimum support of the pattern to be mined
+ * @param K Max value of the Size of the Max-Heap in which Patterns are held
+ * @param featureSetSize number of features
+ * @param returnFeatures the id's of the features for which Top K patterns
+ * have to be mined
+ * @param topKPatternsOutputCollector the outputCollector which transforms the
+ * given Pattern in integer format to the corresponding
+ * AttributePrimitive Format
+ * @return Top K frequent patterns for each attribute
+ * @throws IOException
+ */
+ private final Map<Integer, FrequentPatternMaxHeap> generateTopKFrequentPatterns(
+ Iterator<int[]> transactions,
+ long[] attributeFrequency,
+ long minSupport,
+ int K,
+ int featureSetSize,
+ Set<Integer> returnFeatures,
+ TopKPatternsOutputConvertor<AttributePrimitive> topKPatternsOutputCollector)
+ throws IOException {
+
+ FPTree tree = new FPTree(featureSetSize);
+ for (int i = 0; i < featureSetSize; i++) {
+ tree.addHeaderCount(i, attributeFrequency[i]);
+ }
+
+ // Constructing initial FPTree from the list of transactions
+ MutableLong minSupportMutable = new MutableLong(minSupport);
+ int nodecount = 0;
+ int attribcount = 0;
+ int i = 0;
+ while (transactions.hasNext()) {
+ int[] transaction = transactions.next();
+ Arrays.sort(transaction);
+ attribcount += transaction.length;
+ nodecount += treeAddCount(tree, transaction, 1, minSupportMutable,
+ attributeFrequency);
+ i++;
+ if (i % 10000 == 0) {
+ log.info("FPTree Building: Read {} Transactions", i);
+ }
+ }
+
+ log.info("Number of Nodes in the FP Tree: {}", nodecount);
+
+ return fpGrowth(tree, minSupportMutable, K, returnFeatures,
+ topKPatternsOutputCollector);
+ }
+
+ private final FrequentPatternMaxHeap growth(FPTree tree,
+ MutableLong minSupportMutable, int K, FPTreeDepthCache treeCache,
+ int level, int currentAttribute) {
+ FrequentPatternMaxHeap frequentPatterns = new FrequentPatternMaxHeap(K);
+ FrequentPatternMaxHeap returnedPatterns = null;
+
+ int i = Arrays.binarySearch(tree.getHeaderTableAttributes(),
+ currentAttribute);
+ if (i < 0)
+ return frequentPatterns;
+
+ for (int j = tree.getHeaderTableCount(); i < j; i++) {
+ int attribute = tree.getAttributeAtIndex(i);
+ long count = tree.getHeaderSupportCount(attribute);
+ if (count < minSupportMutable.intValue())
+ continue;
+
+ FPTree conditionalTree = treeCache.getFirstLevelTree(attribute);
+ if (conditionalTree.isEmpty()) {
+ traverseAndBuildConditionalFPTreeData(tree.getHeaderNext(attribute),
+ minSupportMutable, conditionalTree, tree);
+ }
+
+ if (attribute == currentAttribute) {
+
+ returnedPatterns = growthTopDown(conditionalTree, minSupportMutable, K,
+ treeCache, level + 1, true, currentAttribute);
+ frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
attribute, count, true, true);
} else {
returnedPatterns = growthTopDown(conditionalTree, minSupportMutable, K,
@@ -291,7 +358,7 @@
return frequentPatterns;
}
- final private FrequentPatternMaxHeap growthTopDown(FPTree tree,
+ private final FrequentPatternMaxHeap growthBottomUp(FPTree tree,
MutableLong minSupportMutable, int K, FPTreeDepthCache treeCache,
int level, boolean conditionalOfCurrentAttribute, int currentAttribute) {
FrequentPatternMaxHeap frequentPatterns = new FrequentPatternMaxHeap(K);
@@ -304,19 +371,18 @@
else {
int attribute = tree.getAttributeAtIndex(index);
long count = tree.getHeaderSupportCount(attribute);
- if (count < minSupportMutable.intValue())
+ if (count < minSupportMutable.longValue())
return frequentPatterns;
}
}
if (tree.singlePath()) {
return generateSinglePathPatterns(tree, K, minSupportMutable);
}
- for (int i = 0; i < tree.getHeaderTableCount(); i++) {
+ for (int i = tree.getHeaderTableCount() - 1; i >= 0; i--) {
int attribute = tree.getAttributeAtIndex(i);
long count = tree.getHeaderSupportCount(attribute);
if (count < minSupportMutable.longValue())
continue;
-
FPTree conditionalTree = treeCache.getTree(level);
if (conditionalOfCurrentAttribute == true) {
@@ -324,28 +390,28 @@
minSupportMutable, conditionalTree, tree);
returnedPatterns = growthBottomUp(conditionalTree, minSupportMutable,
K, treeCache, level + 1, true, currentAttribute);
- frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
- attribute, count, true, true);
+ frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
+ attribute, count, true, false);
} else {
if (attribute == currentAttribute) {
traverseAndBuildConditionalFPTreeData(tree.getHeaderNext(attribute),
minSupportMutable, conditionalTree, tree);
returnedPatterns = growthBottomUp(conditionalTree, minSupportMutable,
K, treeCache, level + 1, true, currentAttribute);
+
frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
attribute, count, true, false);
-
} else if (attribute > currentAttribute) {
traverseAndBuildConditionalFPTreeData(tree.getHeaderNext(attribute),
minSupportMutable, conditionalTree, tree);
returnedPatterns = growthBottomUp(conditionalTree, minSupportMutable,
K, treeCache, level + 1, false, currentAttribute);
frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
- attribute, count, false, true);
-
+ attribute, count, false, false);
}
}
+
if (frequentPatterns.isFull()) {
if (minSupportMutable.intValue() < frequentPatterns.leastSupport()) {
minSupportMutable.setValue(frequentPatterns.leastSupport());
@@ -356,7 +422,7 @@
return frequentPatterns;
}
- final private FrequentPatternMaxHeap growthBottomUp(FPTree tree,
+ private final FrequentPatternMaxHeap growthTopDown(FPTree tree,
MutableLong minSupportMutable, int K, FPTreeDepthCache treeCache,
int level, boolean conditionalOfCurrentAttribute, int currentAttribute) {
FrequentPatternMaxHeap frequentPatterns = new FrequentPatternMaxHeap(K);
@@ -369,18 +435,19 @@
else {
int attribute = tree.getAttributeAtIndex(index);
long count = tree.getHeaderSupportCount(attribute);
- if (count < minSupportMutable.longValue())
+ if (count < minSupportMutable.intValue())
return frequentPatterns;
}
}
if (tree.singlePath()) {
return generateSinglePathPatterns(tree, K, minSupportMutable);
}
- for (int i = tree.getHeaderTableCount() - 1; i >= 0; i--) {
+ for (int i = 0; i < tree.getHeaderTableCount(); i++) {
int attribute = tree.getAttributeAtIndex(i);
long count = tree.getHeaderSupportCount(attribute);
if (count < minSupportMutable.longValue())
continue;
+
FPTree conditionalTree = treeCache.getTree(level);
if (conditionalOfCurrentAttribute == true) {
@@ -388,28 +455,28 @@
minSupportMutable, conditionalTree, tree);
returnedPatterns = growthBottomUp(conditionalTree, minSupportMutable,
K, treeCache, level + 1, true, currentAttribute);
-
frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
- attribute, count, true, false);
+ attribute, count, true, true);
+
} else {
if (attribute == currentAttribute) {
traverseAndBuildConditionalFPTreeData(tree.getHeaderNext(attribute),
minSupportMutable, conditionalTree, tree);
returnedPatterns = growthBottomUp(conditionalTree, minSupportMutable,
K, treeCache, level + 1, true, currentAttribute);
-
frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
attribute, count, true, false);
+
} else if (attribute > currentAttribute) {
traverseAndBuildConditionalFPTreeData(tree.getHeaderNext(attribute),
minSupportMutable, conditionalTree, tree);
returnedPatterns = growthBottomUp(conditionalTree, minSupportMutable,
K, treeCache, level + 1, false, currentAttribute);
frequentPatterns = mergeHeap(frequentPatterns, returnedPatterns,
- attribute, count, false, false);
+ attribute, count, false, true);
+
}
}
-
if (frequentPatterns.isFull()) {
if (minSupportMutable.intValue() < frequentPatterns.leastSupport()) {
minSupportMutable.setValue(frequentPatterns.leastSupport());
@@ -420,194 +487,126 @@
return frequentPatterns;
}
- /**
- * Internal TopKFrequentPattern Generation algorithm, which represents the
- * AttributePrimitives as integers and transforms features to use only
- * integers
- *
- * @param transactions Transaction database Iterator
- * @param attributeFrequency array representing the Frequency of the
- * corresponding attribute id
- * @param minSupport minimum support of the pattern to be mined
- * @param K Max value of the Size of the Max-Heap in which Patterns are held
- * @param featureSetSize number of features
- * @param returnFeatures the id's of the features for which Top K patterns
- * have to be mined
- * @param topKPatternsOutputCollector the outputCollector which transforms the
- * given Pattern in integer format to the corresponding
- * AttributePrimitive Format
- * @return Top K frequent patterns for each attribute
- * @throws IOException
- */
- final private Map<Integer, FrequentPatternMaxHeap> generateTopKFrequentPatterns(
- Iterator<int[]> transactions,
- long[] attributeFrequency,
- long minSupport,
- int K,
- int featureSetSize,
- Set<Integer> returnFeatures,
- TopKPatternsOutputConvertor<AttributePrimitive> topKPatternsOutputCollector)
- throws IOException {
+ private final FrequentPatternMaxHeap mergeHeap(
+ FrequentPatternMaxHeap frequentPatterns,
+ FrequentPatternMaxHeap returnedPatterns, int attribute, long count,
+ boolean addAttribute, boolean subPatternCheck) {
-
-
- FPTree tree = new FPTree(featureSetSize);
- for (int i = 0; i < featureSetSize; i++) {
- tree.addHeaderCount(i, attributeFrequency[i]);
- }
+ TreeSet<Pattern> myHeap = returnedPatterns.getHeap();
+ Iterator<Pattern> it = myHeap.iterator();
- //Constructing initial FPTree from the list of transactions
- MutableLong minSupportMutable = new MutableLong(minSupport);
- int nodecount = 0;
- int attribcount = 0;
- int i = 0;
- while (transactions.hasNext()) {
- int[] transaction = transactions.next();
- Arrays.sort(transaction);
- attribcount += transaction.length;
- nodecount += treeAddCount(tree, transaction, 1, minSupportMutable,
- attributeFrequency);
- i++;
- if (i % 10000 == 0) {
- log.info("FPTree Building: Read {} Transactions", i);
+ while (it.hasNext()) {
+ Pattern pattern = it.next();
+ long support = Math.min(count, pattern.support());
+ if (frequentPatterns.addable(support)) {
+ pattern.add(attribute, count);
+ frequentPatterns.insert(pattern, subPatternCheck);
}
}
-
- log.info("Number of Nodes in the FP Tree: {}", nodecount);
-
- return fpGrowth(tree, minSupportMutable, K, returnFeatures,
- topKPatternsOutputCollector);
+ if (frequentPatterns.addable(count) && addAttribute) {
+ Pattern p = new Pattern();
+ p.add(attribute, count);
+ frequentPatterns.insert(p, subPatternCheck);
+ }
+ return frequentPatterns;
}
- /**
- * Generate the Feature Frequency list from the given transaction whose
- * frequency > minSupport
- *
- * @param transactions Iterator over the transaction database
- * @param minSupport minSupport of the feature to be included
- * @return the List of features and their associated frequency as a Pair
- * @throws IOException
- */
- final public List<Pair<AttributePrimitive, Long>> generateFList(
- Iterator<List<AttributePrimitive>> transactions, int minSupport)
- throws IOException {
+ private void traverseAndBuildConditionalFPTreeData(int firstConditionalNode,
+ MutableLong minSupportMutable, FPTree conditionalTree, FPTree tree) {
- final Map<AttributePrimitive, MutableLong> AttributeSupport = new HashMap<AttributePrimitive, MutableLong>();
- int count = 0;
- while (transactions.hasNext()) {
- List<AttributePrimitive> transaction = transactions.next();
- for (AttributePrimitive attribute : transaction) {
- if (AttributeSupport.containsKey(attribute) == false)
- AttributeSupport.put(attribute, new MutableLong(1));
- else
- AttributeSupport.get(attribute).increment();
- count++;
- }
- }
- List<Pair<AttributePrimitive, Long>> fList = new ArrayList<Pair<AttributePrimitive, Long>>();
- for (Entry<AttributePrimitive, MutableLong> e : AttributeSupport.entrySet())
- fList.add(new Pair<AttributePrimitive, Long>(e.getKey(), e.getValue()
- .longValue()));
- Collections.sort(fList, new Comparator<Pair<AttributePrimitive, Long>>() {
+ // Build Subtable
+ int conditionalNode = firstConditionalNode;
- @Override
- public int compare(Pair<AttributePrimitive, Long> o1,
- Pair<AttributePrimitive, Long> o2) {
- int ret = o2.getSecond().compareTo(o1.getSecond());
- if (ret != 0)
- return ret;
- return o1.getFirst().compareTo(o2.getFirst());
- }
+ while (conditionalNode != -1) {
+ long nextNodeCount = tree.count(conditionalNode);
+ int pathNode = tree.parent(conditionalNode);
+ int prevConditional = -1;
- });
+ while (0 != pathNode) { // dummy root node
+ int attribute = tree.attribute(pathNode);
+ if (tree.getHeaderSupportCount(attribute) < minSupportMutable
+ .intValue()) {
+ pathNode = tree.parent(pathNode);
+ continue;
+ }
+ // update and increment the headerTable Counts
+ conditionalTree.addHeaderCount(attribute, nextNodeCount);
- return fList;
- }
+ int conditional = tree.conditional(pathNode);
+ // if its a new conditional tree node
- /**
- * Generate Top K Frequent Patterns for every feature in returnableFeatures
- * given a stream of transactions and the minimum support
- *
- * @param transactionStream Iterator of transaction
- * @param frequencyList list of frequent features and their support value
- * @param minSupport minimum support of the transactions
- * @param K Number of top frequent patterns to keep
- * @param returnableFeatures set of features for which the frequent patterns
- * are mined. If the set is null, then top K patterns for every
- * frequent item (an item whose support> minSupport) is generated
- * @param output The output collector to which the the generated patterns are
- * written
- * @throws IOException
- */
- final public void generateTopKFrequentPatterns(
- Iterator<List<AttributePrimitive>> transactionStream,
- List<Pair<AttributePrimitive, Long>> frequencyList,
- long minSupport,
- int K,
- Set<AttributePrimitive> returnableFeatures,
- OutputCollector<AttributePrimitive, List<Pair<List<AttributePrimitive>, Long>>> output)
- throws IOException {
+ if (conditional == 0) {
+ tree.setConditional(pathNode, conditionalTree.createConditionalNode(
+ attribute, 0));
+ conditional = tree.conditional(pathNode);
+ conditionalTree.addHeaderNext(attribute, conditional);
+ } else {
+ conditionalTree.setSinglePath(false);
+ }
- Map<Integer, AttributePrimitive> reverseMapping = new HashMap<Integer, AttributePrimitive>();
- Map<AttributePrimitive, Integer> attributeIdMapping = new HashMap<AttributePrimitive, Integer>();
+ if (prevConditional != -1) { // if there is a child element
+ conditionalTree.setParent(prevConditional, conditional);
+ }
- int id = 0;
- for (Pair<AttributePrimitive, Long> feature : frequencyList) {
- AttributePrimitive attrib = feature.getFirst();
- Long frequency = feature.getSecond();
- if (frequency.longValue() < minSupport)
- continue;
- attributeIdMapping.put(attrib, Integer.valueOf(id));
- reverseMapping.put(Integer.valueOf(id++), attrib);
- }
+ conditionalTree.addCount(conditional, nextNodeCount);
+ prevConditional = conditional;
- final long[] attributeFrequency = new long[attributeIdMapping.size()];
- for (Pair<AttributePrimitive, Long> feature : frequencyList) {
- AttributePrimitive attrib = feature.getFirst();
- Long frequency = feature.getSecond();
- if (frequency.longValue() < minSupport)
- break;
- attributeFrequency[attributeIdMapping.get(attrib)] = frequency
- .longValue();
- }
+ pathNode = tree.parent(pathNode);
- log.info("Number of unique items {}", frequencyList.size());
+ }
+ if (prevConditional != -1) {
+ conditionalTree.setParent(prevConditional, FPTree.ROOTNODEID);
+ if (conditionalTree.childCount(FPTree.ROOTNODEID) > 1
+ && conditionalTree.singlePath()) {
+ conditionalTree.setSinglePath(false);
- Set<Integer> returnFeatures = new HashSet<Integer>();
- if (returnableFeatures.isEmpty() == false) {
- for (AttributePrimitive attrib : returnableFeatures) {
- if (attributeIdMapping.containsKey(attrib)) {
- returnFeatures.add(attributeIdMapping.get(attrib));
- log.info("Adding Pattern {}=>{}", attrib, attributeIdMapping
- .get(attrib));
}
}
- } else {
- for (int j = 0; j < attributeIdMapping.size(); j++)
- returnFeatures.add(j);
+ conditionalNode = tree.next(conditionalNode);
}
-
- log.info("Number of unique pruned items {}", attributeIdMapping.size());
- generateTopKFrequentPatterns(new TransactionIterator<AttributePrimitive>(
- transactionStream, attributeIdMapping), attributeFrequency, minSupport,
- K, reverseMapping.size(), returnFeatures,
- new TopKPatternsOutputConvertor<AttributePrimitive>(output,
- reverseMapping));
+ tree.clearConditional();
+ conditionalTree.reorderHeaderTable();
}
- public static List<Pair<String, TopKStringPatterns>> readFrequentPattern(
- FileSystem fs, Configuration conf, Path path) throws IOException {
-
- List<Pair<String, TopKStringPatterns>> ret = new ArrayList<Pair<String, TopKStringPatterns>>();
- Text key = new Text();
- TopKStringPatterns value = new TopKStringPatterns();
- SequenceFile.Reader reader = new SequenceFile.Reader(fs, path, conf);
- // key is feature value is count
- while (reader.next(key, value)) {
- ret.add(new Pair<String, TopKStringPatterns>(key.toString(),
- new TopKStringPatterns(value.getPatterns())));
+ /**
+ * Create FPTree with node counts incremented by addCount variable given the
+ * root node and the List of Attributes in transaction sorted by support
+ *
+ * @param TransactionTree object to which the transaction has to be added to
+ * @param myList List of transactions sorted by support
+ * @param addCount amount by which the Node count has to be incremented
+ * @param minSupport the MutableLong value which contains the current
+ * value(dynamic) of support
+ * @param attributeFrequency the list of attributes and their frequency
+ * @return the number of new nodes added
+ */
+ private final int treeAddCount(FPTree tree, int[] myList, int addCount,
+ MutableLong minSupport, long[] attributeFrequency) {
+ int temp = FPTree.ROOTNODEID;
+ int ret = 0;
+ boolean addCountMode = true;
+ int child = -1;
+ for (int attribute : myList) {
+ if (attributeFrequency[attribute] < minSupport.intValue())
+ return ret;
+ if (addCountMode) {
+ child = tree.childWithAttribute(temp, attribute);
+ if (child == -1) {
+ addCountMode = false;
+ } else {
+ tree.addCount(child, addCount);
+ temp = child;
+ }
+ }
+ if (!addCountMode) {
+ child = tree.createNode(temp, attribute, addCount);
+ temp = child;
+ ret++;
+ }
}
+
return ret;
+
}
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTree.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTree.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTree.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTree.java Tue Oct 20 11:32:36 2009
@@ -21,21 +21,21 @@
public class FPTree {
- final public static int DEFAULT_CHILDREN_INITIAL_SIZE = 2;
+ public final static int DEFAULT_CHILDREN_INITIAL_SIZE = 2;
- final public static int DEFAULT_HEADER_TABLE_INITIAL_SIZE = 4;
+ public final static int DEFAULT_HEADER_TABLE_INITIAL_SIZE = 4;
- final public static int DEFAULT_INITIAL_SIZE = 8;
+ public final static int DEFAULT_INITIAL_SIZE = 8;
- final public float GROWTH_RATE = 1.5f;
+ public final static int ROOTNODEID = 0;
- final public static int ROOTNODEID = 0;
+ private final static int HEADERTABLEBLOCKSIZE = 2;
- final private static int HEADERTABLEBLOCKSIZE = 2;
+ private final static int HT_LAST = 1;
- final private static int HT_LAST = 1;
+ private final static int HT_NEXT = 0;
- final private static int HT_NEXT = 0;
+ public final float GROWTH_RATE = 1.5f;
private int[] attribute;
@@ -43,10 +43,10 @@
private int[] conditional;
- private int[] headerTableAttributes;
-
private long[] headerTableAttributeCount;
+ private int[] headerTableAttributes;
+
private int headerTableCount = 0;
private int[] headerTableLookup;
@@ -96,7 +96,7 @@
createRootNode();
}
- final public void addChild(int parentNodeId, int childnodeId) {
+ public final void addChild(int parentNodeId, int childnodeId) {
int length = childCount[parentNodeId];
if (length >= nodeChildren[parentNodeId].length) {
resizeChildren(parentNodeId);
@@ -109,7 +109,7 @@
}
}
- final public boolean addCount(int nodeId, long nextNodeCount) {
+ public final boolean addCount(int nodeId, long nextNodeCount) {
if (nodeId < nodes) {
this.nodeCount[nodeId] += nextNodeCount;
return true;
@@ -117,12 +117,12 @@
return false;
}
- final public void addHeaderCount(int attribute, long count) {
+ public final void addHeaderCount(int attribute, long count) {
int index = getHeaderIndex(attribute);
headerTableAttributeCount[index] += count;
}
- final public void addHeaderNext(int attribute, int nodeId) {
+ public final void addHeaderNext(int attribute, int nodeId) {
int index = getHeaderIndex(attribute);
if (headerTableProperties[index][HT_NEXT] == -1) {
headerTableProperties[index][HT_NEXT] = nodeId;
@@ -133,22 +133,22 @@
}
}
- final public int attribute(int nodeId) {
+ public final int attribute(int nodeId) {
return this.attribute[nodeId];
}
- final public int childAtIndex(int nodeId, int index) {
+ public final int childAtIndex(int nodeId, int index) {
if (childCount[nodeId] < index) {
return -1;
}
return nodeChildren[nodeId][index];
}
- final public int childCount(int nodeId) {
+ public final int childCount(int nodeId) {
return childCount[nodeId];
}
- final public int childWithAttribute(int nodeId, int childAttribute) {
+ public final int childWithAttribute(int nodeId, int childAttribute) {
int length = childCount[nodeId];
for (int i = 0; i < length; i++) {
if (attribute[nodeChildren[nodeId][i]] == childAttribute)
@@ -157,27 +157,27 @@
return -1;
}
- final public void clear() {
+ public final void clear() {
nodes = 0;
headerTableCount = 0;
Arrays.fill(headerTableLookup, -1);
createRootNode();
}
- final public void clearConditional() {
+ public final void clearConditional() {
for (int i = nodes - 1; i >= 0; i--)
conditional[i] = 0;
}
- final public int conditional(int nodeId) {
+ public final int conditional(int nodeId) {
return this.conditional[nodeId];
}
- final public long count(int nodeId) {
+ public final long count(int nodeId) {
return nodeCount[nodeId];
}
- final public int createConditionalNode(int attribute, long count) {
+ public final int createConditionalNode(int attribute, long count) {
if (nodes >= this.attribute.length) {
resize();
}
@@ -195,7 +195,7 @@
return childNodeId;
}
- final public int createNode(int parentNodeId, int attribute, long count) {
+ public final int createNode(int parentNodeId, int attribute, long count) {
if (nodes >= this.attribute.length) {
resize();
}
@@ -216,7 +216,7 @@
return childNodeId;
}
- final public int createRootNode() {
+ public final int createRootNode() {
childCount[nodes] = 0;
next[nodes] = -1;
parent[nodes] = 0;
@@ -228,47 +228,47 @@
return childNodeId;
}
- final public int getAttributeAtIndex(int index) {
+ public final int getAttributeAtIndex(int index) {
return headerTableAttributes[index];
}
- final public int getHeaderNext(int attribute) {
+ public final int getHeaderNext(int attribute) {
int index = getHeaderIndex(attribute);
return headerTableProperties[index][HT_NEXT];
}
- final public long getHeaderSupportCount(int attribute) {
+ public final long getHeaderSupportCount(int attribute) {
int index = getHeaderIndex(attribute);
return headerTableAttributeCount[index];
}
- final public int[] getHeaderTableAttributes() {
+ public final int[] getHeaderTableAttributes() {
int[] attributes = new int[headerTableCount];
System.arraycopy(headerTableAttributes, 0, attributes, 0, headerTableCount);
return attributes;
}
- final public int getHeaderTableCount() {
+ public final int getHeaderTableCount() {
return headerTableCount;
}
- final public int next(int nodeId) {
- return next[nodeId];
+ public final boolean isEmpty() {
+ return nodes <= 1;
}
- final public boolean isEmpty() {
- return nodes <= 1;
+ public final int next(int nodeId) {
+ return next[nodeId];
}
- final public int parent(int nodeId) {
+ public final int parent(int nodeId) {
return parent[nodeId];
}
- final public void reorderHeaderTable() {
+ public final void reorderHeaderTable() {
Arrays.sort(headerTableAttributes, 0, headerTableCount);
}
- final public boolean setConditional(int nodeId, int conditional) {
+ public final boolean setConditional(int nodeId, int conditional) {
if (nodeId < nodes) {
this.conditional[nodeId] = conditional;
return true;
@@ -276,7 +276,7 @@
return false;
}
- final public boolean setNext(int nodeId, int next) {
+ public final boolean setNext(int nodeId, int next) {
if (nodeId < nodes) {
this.next[nodeId] = next;
return true;
@@ -284,7 +284,7 @@
return false;
}
- final public boolean setParent(int nodeId, int parent) {
+ public final boolean setParent(int nodeId, int parent) {
if (nodeId < nodes) {
this.parent[nodeId] = parent;
@@ -299,15 +299,15 @@
return false;
}
- final public void setSinglePath(boolean bit) {
+ public final void setSinglePath(boolean bit) {
singlePath = bit;
}
- final public boolean singlePath() {
+ public final boolean singlePath() {
return singlePath;
}
- final private int getHeaderIndex(int attribute) {
+ private final int getHeaderIndex(int attribute) {
if (attribute >= headerTableLookup.length)
resizeHeaderLookup(attribute);
int index = headerTableLookup[attribute];
@@ -326,7 +326,7 @@
return index;
}
- final private void resize() {
+ private final void resize() {
int size = (int) (GROWTH_RATE * nodes);
if (size < DEFAULT_INITIAL_SIZE)
size = DEFAULT_INITIAL_SIZE;
@@ -357,7 +357,7 @@
System.arraycopy(oldConditional, 0, this.conditional, 0, nodes);
}
- final private void resizeChildren(int nodeId) {
+ private final void resizeChildren(int nodeId) {
int length = childCount[nodeId];
int size = (int) (GROWTH_RATE * (length));
if (size < DEFAULT_CHILDREN_INITIAL_SIZE)
@@ -367,7 +367,7 @@
System.arraycopy(oldNodeChildren, 0, this.nodeChildren[nodeId], 0, length);
}
- final private void resizeHeaderLookup(int attribute) {
+ private final void resizeHeaderLookup(int attribute) {
int size = (int) (attribute * GROWTH_RATE);
int[] oldLookup = headerTableLookup;
headerTableLookup = new int[size];
@@ -375,7 +375,7 @@
System.arraycopy(oldLookup, 0, this.headerTableLookup, 0, oldLookup.length);
}
- final private void resizeHeaderTable() {
+ private final void resizeHeaderTable() {
int size = (int) (GROWTH_RATE * (headerTableCount));
if (size < DEFAULT_HEADER_TABLE_INITIAL_SIZE)
size = DEFAULT_HEADER_TABLE_INITIAL_SIZE;
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTreeDepthCache.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTreeDepthCache.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTreeDepthCache.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FPTreeDepthCache.java Tue Oct 20 11:32:36 2009
@@ -25,12 +25,12 @@
public static int firstLevelCacheSize = 5;
- final private ArrayList<FPTree> treeCache = new ArrayList<FPTree>();
+ private final ArrayList<FPTree> treeCache = new ArrayList<FPTree>();
- final private LeastKCache<Integer, FPTree> firstLevelCache = new LeastKCache<Integer, FPTree>(
+ private final LeastKCache<Integer, FPTree> firstLevelCache = new LeastKCache<Integer, FPTree>(
firstLevelCacheSize);
- final public FPTree getTree(int level) {
+ public final FPTree getTree(int level) {
while (treeCache.size() < level + 1) {
FPTree cTree = new FPTree();
treeCache.add(cTree);
@@ -44,7 +44,7 @@
private int misses = 0;
- final public FPTree getFirstLevelTree(int attr) {
+ public final FPTree getFirstLevelTree(int attr) {
Integer attribute = Integer.valueOf(attr);
if (firstLevelCache.contains(attribute)) {
hits++;
@@ -57,11 +57,11 @@
}
}
- final public int getHits() {
+ public final int getHits() {
return hits;
}
- final public int getMisses() {
+ public final int getMisses() {
return misses;
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FrequentPatternMaxHeap.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FrequentPatternMaxHeap.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FrequentPatternMaxHeap.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/FrequentPatternMaxHeap.java Tue Oct 20 11:32:36 2009
@@ -26,49 +26,62 @@
/**
* {@link FrequentPatternMaxHeap} keeps top K Attributes in a TreeSet
*
- * @param <T>
*/
public class FrequentPatternMaxHeap {
- TreeSet<Pattern> set = null;
-
- HashMap<Long, Set<Pattern>> patternIndex = null;
-
- Pattern least = null;
-
- int maxSize = 0;
-
- int count = 0;
-
private Comparator<Pattern> treeSetComparator = new Comparator<Pattern>() {
@Override
- final public int compare(Pattern cr1, Pattern cr2) {
- long support2 = cr2.getSupport();
- long support1 = cr1.getSupport();
+ public final int compare(Pattern cr1, Pattern cr2) {
+ long support2 = cr2.support();
+ long support1 = cr1.support();
int length2 = cr2.length();
int length1 = cr1.length();
if (support1 == support2) {
- if (length1 == length2) {//if they are of same length and support order randomly
+ if (length1 == length2) {// if they are of same length and support order
+ // randomly
return 1;
} else
return length2 - length1;
} else {
- if( support2 - support1 >0)
+ if (support2 - support1 > 0)
return 1;
- else return -1;
+ else
+ return -1;
}
}
};
+ private int count = 0;
+
+ private Pattern least = null;
+
+ private int maxSize = 0;
+
+ private HashMap<Long, Set<Pattern>> patternIndex = null;
+
+ private TreeSet<Pattern> set = null;
+
public FrequentPatternMaxHeap(int numResults) {
maxSize = numResults;
set = new TreeSet<Pattern>(treeSetComparator);
}
- final public void insert(Pattern frequentPattern) {
+ public final boolean addable(long support) {
+ if (count < maxSize)
+ return true;
+ if (least.support() > support)
+ return false;
+ return true;
+ }
+
+ public final TreeSet<Pattern> getHeap() {
+ return set;
+ }
+
+ public final void insert(Pattern frequentPattern) {
insert(frequentPattern, true);
}
- final public void insert(Pattern frequentPattern, boolean subPatternCheck) {
+ public final void insert(Pattern frequentPattern, boolean subPatternCheck) {
if (subPatternCheck)// lazy initialization
{
if (patternIndex == null)
@@ -81,24 +94,42 @@
Pattern evictedItem = set.pollLast();
least = set.last();
if (subPatternCheck)
- patternIndex.get(evictedItem.support).remove(evictedItem);
+ patternIndex.get(evictedItem.support()).remove(evictedItem);
}
}
- } else {
- if (addPattern(frequentPattern, subPatternCheck)){
- count++;
- if(least != null) {
- int cmp = treeSetComparator.compare(least, frequentPattern);
+ } else {
+ if (addPattern(frequentPattern, subPatternCheck)) {
+ count++;
+ if (least != null) {
+ int cmp = treeSetComparator.compare(least, frequentPattern);
if (cmp < 0)
least = frequentPattern;
- else if(cmp == 0)
+ else if (cmp == 0)
return;
- }
- else if (least == null)
+ } else if (least == null)
least = frequentPattern;
}
}
}
+
+ public final int count(){
+ return count;
+ }
+
+ public final boolean isFull() {
+ return count == maxSize;
+ }
+
+ public final long leastSupport() {
+ if (least == null)
+ return 0;
+ return least.support();
+ }
+
+ @Override
+ public final String toString() {
+ return super.toString();
+ }
final private boolean addPattern(Pattern frequentPattern,
boolean subPatternCheck) {
@@ -106,7 +137,7 @@
set.add(frequentPattern);
return true;
} else {
- Long index = Long.valueOf(frequentPattern.support);
+ Long index = Long.valueOf(frequentPattern.support());
if (patternIndex.containsKey(index)) {
Set<Pattern> indexSet = patternIndex.get(index);
boolean replace = false;
@@ -149,31 +180,4 @@
}
}
}
-
- final public TreeSet<Pattern> getHeap() {
- return set;
- }
-
- final public boolean addable(long support) {
- if (count < maxSize)
- return true;
- if (least.support > support)
- return false;
- return true;
- }
-
- @Override
- final public String toString() {
- return super.toString();
- }
-
- final public boolean isFull() {
- return count == maxSize;
- }
-
- final public long leastSupport() {
- if (least == null)
- return 0;
- return least.support;
- }
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/Pattern.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/Pattern.java?rev=827037&r1=827036&r2=827037&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/Pattern.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/fpm/pfpgrowth/fpgrowth/Pattern.java Tue Oct 20 11:32:36 2009
@@ -17,74 +17,25 @@
package org.apache.mahout.fpm.pfpgrowth.fpgrowth;
-import java.io.Serializable;
import java.util.Arrays;
-public class Pattern implements Serializable {
-
- private static final long serialVersionUID = 8698199782842762173L;
-
- private int hashCode;
-
- private boolean dirty = true;
-
- @Override
- public int hashCode() {
- final int prime = 31;
- if (dirty == false)
- return hashCode;
- int result = 1;
- result = prime * result + Arrays.hashCode(pattern);
- result = prime * result + Long.valueOf(support).hashCode();
- hashCode = result;
- return result;
- }
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null)
- return false;
- if (getClass() != obj.getClass())
- return false;
- Pattern other = (Pattern) obj;
- if (length != other.length)
- return false;
- if (support != other.support)
- return false;
- if (!Arrays.equals(pattern, other.pattern))
- return false;
- return true;
- }
+public class Pattern {
public static int DEFAULT_INITIAL_SIZE = 2;
public static float GROWTH_RATE = 1.5f;
- int[] pattern;
-
- long[] supportValues;
+ private boolean dirty = true;
- int length = 0;
+ private int hashCode;
- long support = Long.MAX_VALUE;
+ private int length = 0;
- public long getSupport() {
- return this.support;
- }
-
- final public Object[] getPatternWithSupport() {
- return new Object[] { this.pattern, this.supportValues };
- }
+ private int[] pattern;
- final public int[] getPattern() {
- return this.pattern;
- }
+ private long support = Long.MAX_VALUE;
- final public int length() {
- return this.length;
- }
+ private long[] supportValues;
public Pattern() {
this(DEFAULT_INITIAL_SIZE);
@@ -98,7 +49,7 @@
dirty = true;
}
- final public void add(int id, long support) {
+ public final void add(int id, long support) {
if (length >= pattern.length)
resize();
this.pattern[length] = id;
@@ -107,29 +58,45 @@
dirty = true;
}
- final private void resize() {
- int size = (int) (GROWTH_RATE * length);
- if (size < DEFAULT_INITIAL_SIZE)
- size = DEFAULT_INITIAL_SIZE;
- int[] oldpattern = pattern;
- long[] oldSupport = supportValues;
- this.pattern = new int[size];
- this.supportValues = new long[size];
- System.arraycopy(oldpattern, 0, this.pattern, 0, length);
- System.arraycopy(oldSupport, 0, this.supportValues, 0, length);
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (getClass() != obj.getClass())
+ return false;
+ Pattern other = (Pattern) obj;
+ if (length != other.length)
+ return false;
+ if (support != other.support)
+ return false;
+ if (!Arrays.equals(pattern, other.pattern))
+ return false;
+ return true;
+ }
+
+ public final int[] getPattern() {
+ return this.pattern;
+ }
+
+ public final Object[] getPatternWithSupport() {
+ return new Object[] { this.pattern, this.supportValues };
}
@Override
- final public String toString() {
- int[] arr = new int[length];
- System.arraycopy(pattern, 0, arr, 0, length);
- return Arrays.toString(arr) + "-" + support;
+ public int hashCode() {
+ final int prime = 31;
+ if (dirty == false)
+ return hashCode;
+ int result = 1;
+ result = prime * result + Arrays.hashCode(pattern);
+ result = prime * result + Long.valueOf(support).hashCode();
+ hashCode = result;
+ return result;
}
- final public boolean isSubPatternOf(Pattern frequentPattern) {// Patterns are
- // in the sorted
- // order of
- // their ids
+ public final boolean isSubPatternOf(Pattern frequentPattern) {
int[] otherPattern = frequentPattern.getPattern();
int otherLength = frequentPattern.length();
int otherI = 0;
@@ -152,4 +119,31 @@
}
+ public final int length() {
+ return this.length;
+ }
+
+ public final long support() {
+ return this.support;
+ }
+
+ @Override
+ public final String toString() {
+ int[] arr = new int[length];
+ System.arraycopy(pattern, 0, arr, 0, length);
+ return Arrays.toString(arr) + "-" + support;
+ }
+
+ private final void resize() {
+ int size = (int) (GROWTH_RATE * length);
+ if (size < DEFAULT_INITIAL_SIZE)
+ size = DEFAULT_INITIAL_SIZE;
+ int[] oldpattern = pattern;
+ long[] oldSupport = supportValues;
+ this.pattern = new int[size];
+ this.supportValues = new long[size];
+ System.arraycopy(oldpattern, 0, this.pattern, 0, length);
+ System.arraycopy(oldSupport, 0, this.supportValues, 0, length);
+ }
+
}