Ruby implementation of FP-Growth
FP-Growth is an algorithm used for mining frequent pattern in an item set. Such pattern are then used to build association rules. Literature example is { Potatoes, Onions } => { Burger } or { Beer, Chips } => { Dippers }.
FP-Growth is known as a solution for Mining without Candidate generation (http://dl.acm.org/citation.cfm?id=335372). Main alternative to FP-Growth is A Priori which is a pretty much a naive solution. A Priori consist in generating candidate then scanning the database looking for them.
FP-Growth solution is about reducing the database in one simple Tree Structure : The FP-Tree. The FP-Tree make easy to extract frequent pattern from it. Then FP-Growth algorithm is about Extracting pattern from the tree, starting by the smallest, at the leafs of the tree and then making them grow until every pattern has been found.
FP-Growth is about working on a very large number of transactions. The FpTree building is a single pass linear operation. Most of the time, FP-Growth operation is a 0(h²) operation, where h is the height of the Tree. By design, the height is the maximal length of the pattern.
Worst case is a DataSet with long transactions and where each item is significantly frequent. Such a tree is very big and reduction factor is very low. Performances would be... not what you expect ^^
Imagine a web app allowing you to connect to other users. Such a website want to help the user to engage with other. It will scan relationship of users and make suggestions like : "People who connect with following persons often connect with thoses persons".
Imagine a commercial website showing some products to the users. It will scan users actions and make suggestions like : "People who like this products often like this other one !"
Those applications are now easy thanks to fpgrowth for Ruby !
Add this line to your application's Gemfile:
gem 'fpgrowth'
And then execute:
$ bundle install
Or install it yourself as:
$ gem install fpgrowth
Just do it :
transactions = [['a', 'b'], ['b'], ['b', 'c'], ['a', 'b']]
patterns = FpGrowth.mine(transactions)Build a tree from transactions and mine it
transactions = [['a', 'b'], ['b'], ['b', 'c'], ['a', 'b']]
fp_tree = FpGrowth::FpTree.build(transactions)
FpGrowth::Miner.td_fp_growth(fp_tree)By default, threshold for an item to be considered as "frequent" is 1% of the transactions. You can edit the threshold when building the tree. We recommend using a threshold around 1%. The larger is the number of transactions, the smaller should be the threshold. If tree is too large, you should use a higher threshold.
transactions = [['a', 'b'], ['b'], ['b', 'c'], ['a', 'b']]
fp_tree = FpGrowth::FpTree.build(transactions, 30)
# 30 stands for 30% of transactions. Here, 'c' would be pruned.
FpGrowth::Miner.td_fp_growth(fp_tree)If you want to avoid worst case, then you should make it a Bonzai !
transactions = [['a', 'b'], ['b'], ['b', 'c'], ['a', 'b']]
fp_tree = FpGrowth::FpTree.build(transactions, 30)
bonzai = fp_tree.to_bonzai(20)
FpGrowth::Miner.td_fp_growth(bonzai)20 stands for a hardness of 20%. It mean that a node is cut from the tree if it's not greater than 20% of it's father support.
There is two variant of FP-Growth. The first one is the TopDown, it's the most efficient, in most cases. For some reasons, it's alternative, the classical FpGrowth, it might be more efficient on a very small set. Use it this way :
transactions = [['a', 'b'], ['b'], ['b', 'c'], ['a', 'b']]
patterns = FpGrowth.fp_growth(transactions)or
transactions = [['a', 'b'], ['b'], ['b', 'c'], ['a', 'b']]
fp_tree = FpGrowth::FpTree.build(transactions, 30)
bonzai = fp_tree.to_bonzai(20)
FpGrowth::Miner.fp_growth(bonzai)You can find in the test repository a few concrete example on Open Data.
We are going to experiment an alternative way of building the tree, which may be more efficient.
We are also going to experiment TD-FPGrowth(M) and TD-FPGrowth(C). Those are pruning-mining algorithm based on TopDown FPGrowth.
- Fork it
- Create your feature branch (
git checkout -b my-new-feature) - Commit your changes (
git commit -am 'Add some feature') - Push to the branch (
git push origin my-new-feature) - Create new Pull Request