de.lmu.ifi.dbs.elki.algorithm
Class APRIORI

java.lang.Object
  de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<AprioriResult>
      de.lmu.ifi.dbs.elki.algorithm.APRIORI

All Implemented Interfaces:

Algorithm, InspectionUtilFrequentlyScanned, Parameterizable

@Title(value="APRIORI: Algorithm for Mining Association Rules")
@Description(value="Searches for frequent itemsets")
@Reference(authors="R. Agrawal, R. Srikant",
           title="Fast Algorithms for Mining Association Rules in Large Databases",
           booktitle="Proc. 20th Int. Conf. on Very Large Data Bases (VLDB \'94), Santiago de Chile, Chile 1994",
           url="http://www.acm.org/sigmod/vldb/conf/1994/P487.PDF")
public class APRIORI
extends AbstractAlgorithm<AprioriResult>

Provides the APRIORI algorithm for Mining Association Rules.

Reference:
R. Agrawal, R. Srikant: Fast Algorithms for Mining Association Rules in Large Databases.
In Proc. 20th Int. Conf. on Very Large Data Bases (VLDB '94), Santiago de Chile, Chile 1994.

Nested Class Summary

static class

APRIORI.Parameterizer Parameterization class.

Field Summary

private static Logging	logger The logger for this class.
private double	minfreq Holds the value of MINFREQ_ID.
static OptionID	MINFREQ_ID Optional parameter to specify the threshold for minimum frequency, must be a double greater than or equal to 0 and less than or equal to 1.
private int	minsupp Holds the value of MINSUPP_ID.
static OptionID	MINSUPP_ID Parameter to specify the threshold for minimum support as minimally required number of transactions, must be an integer equal to or greater than 0.

Constructor Summary

APRIORI(double minfreq)
Constructor with minimum frequency.

APRIORI(int minsupp)
Constructor with minimum support.

Method Summary

protected BitSet[]	frequentItemsets(Map<BitSet,Integer> support, BitSet[] candidates, Relation<BitVector> database) Returns the frequent BitSets out of the given BitSets with respect to the given database.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected BitSet[]	join(BitSet[] frequentItemsets) Returns a set of BitSets generated by joining pairs of given BitSets (relying on the given BitSets being sorted), increasing the length by 1.
protected BitSet[]	prune(Map<BitSet,Integer> support, BitSet[] candidates, int size) Prunes a given set of candidates to keep only those BitSets where all subsets of bits flipping one bit are frequent already.
AprioriResult	run(Database database, Relation<BitVector> relation) Performs the APRIORI algorithm on the given database.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

makeParameterDistanceFunction, run

Methods inherited from class java.lang.Object

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

Field Detail

logger

private static final Logging logger

The logger for this class.

MINFREQ_ID

public static final OptionID MINFREQ_ID

Optional parameter to specify the threshold for minimum frequency, must be a double greater than or equal to 0 and less than or equal to 1. Alternatively to parameter MINSUPP_ID).

MINSUPP_ID

public static final OptionID MINSUPP_ID

Parameter to specify the threshold for minimum support as minimally required number of transactions, must be an integer equal to or greater than 0. Alternatively to parameter MINFREQ_ID - setting MINSUPP_ID is slightly preferable over setting MINFREQ_ID in terms of efficiency.

minfreq

private double minfreq

Holds the value of MINFREQ_ID.

minsupp

private int minsupp

Holds the value of MINSUPP_ID.

Constructor Detail

APRIORI

public APRIORI(double minfreq)

Constructor with minimum frequency.

Parameters:

minfreq - Minimum frequency

APRIORI

public APRIORI(int minsupp)

Constructor with minimum support.

Parameters:

minsupp - Minimum support

Method Detail

run

public AprioriResult run(Database database,
                         Relation<BitVector> relation)
                  throws IllegalStateException

Performs the APRIORI algorithm on the given database.

Parameters:

database - the Database to run APRIORI on

relation - the Relation to process

Returns:

the AprioriResult learned by this APRIORI

Throws:

IllegalStateException

prune

protected BitSet[] prune(Map<BitSet,Integer> support,
                         BitSet[] candidates,
                         int size)

Prunes a given set of candidates to keep only those BitSets where all subsets of bits flipping one bit are frequent already.

Parameters:

support - Support map

candidates - the candidates to be pruned

size - size of the database

Returns:

a set of BitSets where all subsets of bits flipping one bit are frequent already

join

protected BitSet[] join(BitSet[] frequentItemsets)

Returns a set of BitSets generated by joining pairs of given BitSets (relying on the given BitSets being sorted), increasing the length by 1.

Parameters:

frequentItemsets - the BitSets to be joined

Returns:

a set of BitSets generated by joining pairs of given BitSets, increasing the length by 1

frequentItemsets

protected BitSet[] frequentItemsets(Map<BitSet,Integer> support,
                                    BitSet[] candidates,
                                    Relation<BitVector> database)

Returns the frequent BitSets out of the given BitSets with respect to the given database.

Parameters:

support - Support map.

candidates - the candidates to be evaluated

database - the database to evaluate the candidates on

Returns:

the frequent BitSets out of the given BitSets with respect to the given database

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<AprioriResult>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<AprioriResult>

Returns:

the static logger