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

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<BitVector>
              de.lmu.ifi.dbs.elki.algorithm.APRIORI

All Implemented Interfaces:

Algorithm<BitVector>, Loggable, Parameterizable

public class APRIORI
extends AbstractAlgorithm<BitVector>

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.

Author:

Arthur Zimek

Field Summary

private double	minfreq Holds the value of MINFREQ_PARAM.
static OptionID	MINFREQ_ID OptionID for MINFREQ_PARAM
private DoubleParameter	MINFREQ_PARAM 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_PARAM.
static OptionID	MINSUPP_ID OptionID for MINSUPP_PARAM
private IntParameter	MINSUPP_PARAM Parameter to specify the threshold for minimum support as minimally required number of transactions, must be an integer equal to or greater than 0.
private AprioriResult	result The result.
private Map<BitSet,Integer>	support Keeps the support of all evaluated bitsets.

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

optionHandler

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug

Constructor Summary

APRIORI()
Provides the apriori algorithm, adding parameters MINFREQ_PARAM and MINSUPP_PARAM to the option handler additionally to parameters of super class.

Method Summary

protected BitSet[]	frequentItemsets(BitSet[] candidates, Database<BitVector> database) Returns the frequent BitSets out of the given BitSets with respect to the given database.
Description	getDescription() Returns a description of the algorithm.
AprioriResult	getResult() Returns the result of the algorithm.
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(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.
protected void	runInTime(Database<BitVector> database) The run method encapsulated in measure of runtime.
String[]	setParameters(String[] args) Calls AbstractAlgorithm#setParameters(args) and sets additionally the values of the parameters MINFREQ_PARAM and MINSUPP_PARAM.

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

description, isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getAttributeSettings, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, getAttributeSettings, getParameters, getPossibleOptions, inlineDescription

Field Detail

MINFREQ_ID

public static final OptionID MINFREQ_ID

OptionID for MINFREQ_PARAM

MINFREQ_PARAM

private final DoubleParameter MINFREQ_PARAM

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_PARAM).

Key: -apriori.minfreq

minfreq

private double minfreq

Holds the value of MINFREQ_PARAM.

MINSUPP_ID

public static final OptionID MINSUPP_ID

OptionID for MINSUPP_PARAM

MINSUPP_PARAM

private final IntParameter MINSUPP_PARAM

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_PARAM - setting MINSUPP_PARAM is slightly preferable over setting MINFREQ_PARAM in terms of efficiency.

Key: -apriori.minsupp

minsupp

private int minsupp

Holds the value of MINSUPP_PARAM.

result

private AprioriResult result

The result.

support

private Map<BitSet,Integer> support

Keeps the support of all evaluated bitsets.

Constructor Detail

APRIORI

public APRIORI()

Provides the apriori algorithm, adding parameters MINFREQ_PARAM and MINSUPP_PARAM to the option handler additionally to parameters of super class.

Method Detail

runInTime

protected void runInTime(Database<BitVector> database)
                  throws IllegalStateException

Description copied from class: AbstractAlgorithm

The run method encapsulated in measure of runtime. An extending class needs not to take care of runtime itself.

Specified by:

runInTime in class AbstractAlgorithm<BitVector>

Parameters:

database - the database to run the algorithm on

Throws:

IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

See Also:

Algorithm.run(de.lmu.ifi.dbs.elki.database.Database)

prune

protected BitSet[] prune(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:

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(BitSet[] candidates,
                                    Database<BitVector> database)

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

Parameters:

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

getResult

public AprioriResult getResult()

Description copied from interface: Algorithm

Returns the result of the algorithm.

Returns:

the result of the algorithm

See Also:

Algorithm.getResult()

getDescription

public Description getDescription()

Description copied from interface: Algorithm

Returns a description of the algorithm.

Returns:

a description of the algorithm

See Also:

Algorithm.getDescription()

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Calls AbstractAlgorithm#setParameters(args) and sets additionally the values of the parameters MINFREQ_PARAM and MINSUPP_PARAM.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class AbstractAlgorithm<BitVector>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])