ca.pfv.spmf.algorithms.frequentpatterns.dci_closed_optimized

Class AlgoDCI_Closed_Optimized

java.lang.Object

ca.pfv.spmf.algorithms.frequentpatterns.dci_closed_optimized.AlgoDCI_Closed_Optimized

public class AlgoDCI_Closed_Optimized
extends java.lang.Object

This is the optimized implementation of the "DCI_Closed" algorithm. The DCI_Closed algorithm finds all closed itemsets in a transaction database.

DCI_Closed was initially proposed in this article:

Lucchese, C., Orlando, S. & Perego, Raffaele (2004), DCI_Closed: a fast and memory efficient algorithm to mine frequent closed itemsets, Proc. 2nd IEEE ICDM Workshop on Frequent Itemset Mining Implementations at ICDM 2004.

Note: My implementation assumes that there is no item named "0".

My implementation include several optimization:
- the use of a bit matrix (as described in the TKDE paper)
- projecting the database (as described in the TKDE paper)
- intersecting bit by bit and stop at first different bit for inclusion check (similar to what is described in the TKDE paper, but check bits instead of words)

But more optimizations could be done:
- intersecting word by word and stop at first different word for inclusion check (described in the TKDE paper)
- reorder columns of the matrix (described in the TKDE paper)
- reusing results of previous bitwise intersections (described in the TKDE paper)
- changing for a breath-first DCI-like approach for dense datasets (as described in the TKDE paper)
- ...
- remove elements from postsets and use a linkedlist for postsets.
- closedset could be an array.
- etc.

Some of these further optimizations would need to use a custom BitSet class instead of the BitSet class of Java, because the BitSet class of Java does not let us iterate over the words inside the BitSet directly.

See Also:

BitMatrix

Constructor Summary

Constructors

Constructor and Description
AlgoDCI_Closed_Optimized() Default constructor

Method Summary

Modifier and Type	Method and Description
void	runAlgorithm(java.lang.String input, java.lang.String output, int minsup) Run the algorithm.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AlgoDCI_Closed_Optimized

public AlgoDCI_Closed_Optimized()

Default constructor

Method Detail

runAlgorithm

public void runAlgorithm(java.lang.String input,
                         java.lang.String output,
                         int minsup)
                  throws java.io.IOException

Run the algorithm.

Parameters:

input - the path of an input file (transaction database).

output - the path of the output file for writing the result

minsup - a minimum support threshold

Throws:

java.io.IOException - exception if error while writing/reading files