[
https://issues.apache.org/jira/browse/MAHOUT-890?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13162849#comment-13162849
]
tom pierce commented on MAHOUT-890:
-----------------------------------
Thanks for the feedback. I agree with your thinking on tests, but I'm not sure
what makes the most sense here. I have an example set where the current
implementation seems to produce correct output, it just takes an unreasonable
amount of time (4+ hours on a small set). I'll be happy to provide a unit
test, though. Unit testing the tree manipulations on a smaller scale is
problematic because the intent and invariants are not obvious.
For what it's worth, I actually spent more time than I'd like to admit trying
to understand and fix the current implementation before resorting to a rewrite.
My motivation for creating an alternate implementation was that I have a real
dataset (of reasonable size) where the current implementation effectively fails
to complete. I've submitted a bug report, example data that demonstrates the
long-execution problem, a toy example that can demonstrate evidence of
tree-manipulation behavior that is almost certainly bad (but it is still not
clear to me how to fix it), and I've also shown a naive implementation that
completes quickly on the same data.
On the topic of top-k patterns, I do not understand why it is desirable to
repeatedly mine the same candidates/patterns. The current implementation will
find pattern "a b c" 3 times, when it could be found once and post-processed to
create complete per-item lists. It seems needlessly inefficient (especially if
you don't care about per-item lists). The way the code is structured, it is
done this way even in mapreduce mode, even though the input itemsets are pruned
in such a way that postprocessing is necessary anyway.
You're right that there are a lot of boxed primitives in the patch; I also
didn't pack the tree into an array representation. I aimed for simple/quick to
get it working; the boxed primitives in particular should be pretty easy to
eliminate.
> 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: MAHOUT-890.patch, 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
