alexisfacques/node-fpgrowth

FPGrowth Algorithm implementation in TypeScript / JavaScript.

Node-FPGrowth

FPGrowth Algorithm frequent itemset mining algorithm implementation in TypeScript / JavaScript.

Getting Started

Installing

This is a Node.js module available through the npm registry.

Installation is done using the npm install command:

npm install --save node-fpgrowth

Example of use

In your TypeScript project, import and use FPGrowth as follows. Same example with a JavaScript syntax is available here.

import { FPGrowth, Itemset } from 'node-fpgrowth';

let transactions: number[][] = [
    [1,3,4],
    [2,3,5],
    [1,2,3,5],
    [2,5],
    [1,2,3,5]
];

// Execute FPGrowth with a minimum support of 40%. Algorithm is generic.
let fpgrowth: FPGrowth<number> = new FPGrowth<number>(.4);

// Returns itemsets 'as soon as possible' through events.
fpgrowth.on('data', (itemset: Itemset<number>) => {
    // Do something with the frequent itemset.
    let support: number = itemset.support;
    let items: number[] = itemset.items;
});

// Execute FPGrowth on a given set of transactions.
fpgrowth.exec(transactions)
    .then( (itemsets: Itemset<number>[]) => {
      // Returns an array representing the frequent itemsets.
    });

Node-FPGrowth is compatible with browserify and webpack. Alternatively, you can import/serve the browserified fpgrowth-client.js file found in the dist folder:

<script src="./dist/fpgrowth-client.js"></script>
<script>
  var transactions = [
      [1, 3, 4],
      [2, 3, 5],
      [1, 2, 3, 5],
      [2, 5],
      [1, 2, 3, 5]
  ];

  var fpg = new fpgrowth.FPGrowth(.4);

  fpg.exec(transactions, function (itemsets) {
      console.log(`Finished executing FPGrowth. ${itemsets.length} frequent itemset(s) were found.`);
  });
</script>

Building from source

• Clone this repository:

  git clone https://github.com/alexisfacques/Node-FPGrowth.git
  cd Node-FPGrowth

• Install the project's dependencies with:

  npm install

• Compile the module's sources to executable JavaScript:

  npm run tsc

• This should run the example bundled with the module:

  npm test

• This should recreate a browserified version, ./dist/fpgrowth-client.js, of the module:

  npm run browserify

License

This project is licensed under the MIT License - see the LICENSE file for details.

node-fpgrowth's Issues

It doen't compile

node-fpgrowth/dist/fpgrowth.d.ts(1,23): error TS2688: Cannot find type definition file for 'node'.
node-fpgrowth/dist/fpgrowth.d.ts(15,22): error TS2420: Class 'FPGrowth' incorrectly implements interface 'IFPGrowthEvents'.
Property 'on' is missing in type 'FPGrowth'.

Make this module runnable in the browser

Hi @alexisfacques!

This is very good work! I would like to use it in the frontend and there is an error of process.hrtime is not a function, because process is undefined.

I patched it by hand with the help of browser-process-hrtime, but I need to make this simple patch permanent.
What about including a runtime environment check in your code?
I could renounce the execution time anyway, but I failed to edit your Typescript code in my fork until here.

Regards!
noVaSon

Memory optimisations

Hey @alexisfacques , thanks a lot for such a nice library!
In my experiments, I have around 50-60k transactions and the algorithm stops working after some time, the process crashes with an OOM error. I have 16GB of RAM and it is all getting utilized by the library.
I understand that it's the nature of this algorithm to be inefficient in memory, but do you see any chances to make it work on a regular laptop? Some kinds of tweaks or optimizations maybe. Or use some external tools (such as databases, and file systems) for storing temporary results after each step.

Feat: Get related items of a given item order by support

Currently it gives me all possible itemsets.
What I want is a function that accepts an item and returns all its pairs (excluding itself) sorted in order of support
getRelatedItems(item, maxItems?)

var transactions = [
[1, 3, 4],
[2, 3, 5],
[1, 2, 3, 5],
[2, 5],
[1, 2, 3, 5]
];
getRelatedItems(1) // Output: [3, 5, 2]
getRelatedItems(2) // Output: [5, 3, 1]
getRelatedItems(3) // Output: [5, 2, 1]
getRelatedItems(4) // Output: []
getRelatedItems(5) // Output: [2, 3, 1]