[
https://issues.apache.org/jira/browse/MAHOUT-890?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13155489#comment-13155489
]
tom pierce commented on MAHOUT-890:
-----------------------------------
I'm attaching another patch which adds a second FP-Growth implementation. This
code has a few difference with the current FPG implementation. It does not
avoid creating objects or recursion, so it may be more heap/stack hungry. It
also does not output lists of top-k freq patterns for each item; instead it
outputs top-k frequent patterns containing items more frequent than the current
target item (note that top-k sets per item can be post-processed from this
data). The union of all per-item itemsets should be the same, and I've
included a test which demonstrates this for the retail.dat dataset.
This code handles the FPGsynth.dat dataset without trouble, and I've added a
flag that lets you try out the new code by adding a "-2" to the commandline, in
either MR or sequential mode (running "mahout fpg" will use the existing code
by default). I hope people will try them out against each other.
If this implementation is adopted we can add some itemset pruning (per the Li
paper), and we can add a post-processor to generate top-k per item patterns, if
there are users relying on that functionality. I deferred these for now, so
that running the implementations side-by-side would be very straightforward.
> Performance issue in FPGrowth
> -----------------------------
>
> Key: MAHOUT-890
> URL: https://issues.apache.org/jira/browse/MAHOUT-890
> Project: Mahout
> Issue Type: Bug
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.6
> Reporter: tom pierce
> Attachments: addSynth.patch, logtrees.patch, simpleFPG.patch,
> smallexample.dat
>
>
> I've encountered a dataset which indicates there is probably a performance
> bug lurking in the FPGrowth implementation. This set may be a bit of an
> unusual target for FPG - there's a relatively modest number itemsets, and
> many items with a Zipfy distribution. I am attaching a patch
> (addSynth.patch) to add a similar dataset as
> core/src/test/resources/FPGsynth.dat.
> FPGsynth.dat can take minutes or a few hours to process, depending on how it
> is grouped out to machines. If run in sequential mode, or with "-g 50" it
> will take considerable time. Most reducers/"anchor items" are processed
> quickly, but a small number take a handful of minutes, and one or two take a
> long time. If you experiment with this data, I suggest using '-s 50 -regex
> "[ ]+"'.
> Digging into this, I've found that the tree pruning code sometimes creates
> surprising trees. One oddity I've observed is 0-count nodes, sometimes with
> non-zero children. The other is that sometimes subtrees seem to get
> repeated. I'm attaching a sample input file (smallexample.dat, use the
> whitespace regex with this one, too) and a patch which adds some logging in
> pruneFPTree and growthBottomUp which will print out some interesting trees
> when run with the smallexample.dat input.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
