keel.Algorithms.Subgroup_Discovery.SDMap.FPTree

Class AssocRuleMining

java.lang.Object

keel.Algorithms.Subgroup_Discovery.SDMap.FPTree.AssocRuleMining

Direct Known Subclasses:

TotalSupportTree

public class AssocRuleMining
extends java.lang.Object

Set of utilities to support various Association Rule Mining (ARM)

Since:

JDK1.6

Version:

1.0

Author:

Written by Frans Coenen (University of Liverpool) 09/01/2003, Modified by Frans Coenen (University of Liverpool) 03/02/2005, Modified by Nicola Flugy Papa (Politecnico di Milano) 24/03/2009

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	AssocRuleMining.RuleNode Inner class for storing linked list of ARs or CARs as appropriate.

Field Summary

Fields

Modifier and Type	Field and Description
protected double	confidence % confidence.
protected int[][]	conversionArray 2-D array used to renumber columns for input data in terms of frequency of single attributes (reordering will enhance performance for some ARM algorithms).
protected short[][]	dataArray 2-D aray to hold input data from data file.
protected myDataset	dataset Dataset.
protected boolean	isOrderedFlag Flag to indicate whether input data has been sorted or not.
protected boolean	isPrunedFlag Flag to indicate whether input data has been sorted and pruned or not.
protected double	minSupport Minimum support value in terms of number of rows.
protected int	numCols Number of columns.
protected int	numOneItemSets The number of one itemsets (singletons).
protected int	numRows Number of rows.
protected short[]	reconversionArray 1-D array used to reconvert input data column numbers to their original numbering where the input data has been ordered to enhance computational efficiency.
protected AssocRuleMining.RuleNode	startRulelist The reference to start of the rule list.
protected double	support % support.

Constructor Summary

Constructors

Constructor and Description
AssocRuleMining(myDataset ds, double sup, double conf) Constructor to process dataset and parameters.

Method Summary

Modifier and Type	Method and Description
protected short[]	complement(short[] itemSet1, short[] itemSet2) Returns complement of first itemset with respect to second itemset.
protected short[]	copyItemSet(short[] itemSet) Makes a copy of a given itemSet.
protected int[][]	countSingles() Counts number of occurrences of each single attribute in the input data.
protected void	defConvertArrays(int[][] countArray) Defines conversion and reconversion arrays.
protected int	getNumSupOneItemSets() Gets number of supported single item sets (note this is not necessarily the same as the number of columns/attributes in the input set).
java.util.ArrayList<AssociationRule>	getRulesSet() It constructs a rules set once the algorithm has been carried out.
void	idInputDataOrdering() Reorders input data according to frequency of single attributes.
protected void	insertRuleintoRulelist(short[] antecedent, short[] consequent, double confidenceForRule, double supportForRule, double supportForAntecedent) Inserts an (association/classification) rule into the linkedlist of rules pointed at by startRulelist.
protected boolean	notMemberOf(short number, short[] itemSet) Checks whether a particular element/attribute identified by a column number is not a member of the given item set.
protected void	orderFirstNofCountArray(int[][] countArray, int endIndex) Bubble sorts first N elements in count array produced by countSingles method so that array is ordered according to frequency of single items.
void	outputDataArray() Outputs stored input data set; initially read from input data file, but may be reordered or pruned if desired by a particular application.
protected void	outputItemSet(short[] itemSet) Outputs a given item set.
void	outputRules() Outputs contents of rule linked list (if any) assuming that the list represents a set of ARs.
void	outputRules(AssocRuleMining.RuleNode ruleList) Outputs given rule list.
protected short[]	realloc1(short[] oldItemSet, short newElement) Resizes given item set so that its length is increased by one and appends new element (identical to append method)
protected short[]	realloc2_new(short[] oldItemSet, short newElement) Resizes given array so that its length is increased by one element and new element added to front
protected short[]	realloc2(short[] oldItemSet, short newElement) Resizes given array so that its length is increased by one element and new element added to front
protected short[]	reallocInsert(short[] oldItemSet, short newElement) Resizes given item set so that its length is increased by one and new element inserted.
void	recastInputData() Recasts the contents of the data array so that each record is ordered according to conversion array.
void	recastInputDataAndPruneUnsupportedAtts() Recasts the contents of the data array so that each record is ordered according to ColumnCounts array and excludes non-supported elements.
protected short	reconvertItem(short item) Reconvert single item if appropriate.
protected short[]	reconvertItemSet(short[] itemSet) Reconverts given item set according to contents of reconversion array.
protected short[]	removeElementN(short[] oldItemSet, int n) Removes the nth element/attribute from the given item set.
protected void	sortItemSet(short[] itemSet) Sorts an unordered item set.
protected double	twoDecPlaces(double number) Converts given real number to real number rounded up to two decimal places.

Methods inherited from class java.lang.Object

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

Field Detail

startRulelist

protected AssocRuleMining.RuleNode startRulelist

The reference to start of the rule list.

dataArray

protected short[][] dataArray

2-D aray to hold input data from data file. Note that within the data array records are numbered from zero, thus rexcord one has index 0 etc.

conversionArray

protected int[][] conversionArray

2-D array used to renumber columns for input data in terms of frequency of single attributes (reordering will enhance performance for some ARM algorithms).

reconversionArray

protected short[] reconversionArray

1-D array used to reconvert input data column numbers to their original numbering where the input data has been ordered to enhance computational efficiency.

numCols

protected int numCols

Number of columns.

numRows

protected int numRows

Number of rows.

support

protected double support

% support.

minSupport

protected double minSupport

Minimum support value in terms of number of rows.

Set when input data is read and the number of records is known,

confidence

protected double confidence

% confidence.

numOneItemSets

protected int numOneItemSets

The number of one itemsets (singletons).

dataset

protected myDataset dataset

Dataset.

isOrderedFlag

protected boolean isOrderedFlag

Flag to indicate whether input data has been sorted or not.

isPrunedFlag

protected boolean isPrunedFlag

Flag to indicate whether input data has been sorted and pruned or not.

Constructor Detail

AssocRuleMining

public AssocRuleMining(myDataset ds,
                       double sup,
                       double conf)

Constructor to process dataset and parameters.

Parameters:

ds - The instance of the dataset for dealing with its records

sup - The user-specified minimum support for the mined association rules

conf - The user-specified minimum confidence for the mined association rules

Method Detail

idInputDataOrdering

public void idInputDataOrdering()

Reorders input data according to frequency of single attributes.

Example, given the data set:

    1 2 5
    1 2 3
    2 4 5
    1 2 5
    2 3 5
    

This would produce a countArray (ignore index 0):

    +---+---+---+---+---+---+
    |   | 1 | 2 | 3 | 4 | 5 |
    +---+---+---+---+---+---+
    |   | 3 | 5 | 2 | 1 | 4 |
    +---+---+---+---+---+---+
    

Which sorts to:

    +---+---+---+---+---+---+
    |   | 2 | 5 | 1 | 3 | 4 |
    +---+---+---+---+---+---+
    |   | 5 | 4 | 3 | 2 | 1 |
    +---+---+---+---+---+---+
    

Giving rise to the conversion Array of the form (no index 0):

    +---+---+---+---+---+---+
    |   | 3 | 1 | 4 | 5 | 2 |
    +---+---+---+---+---+---+
    |   | 3 | 5 | 2 | 1 | 4 |
    +---+---+---+---+---+---+
    

Note that the second row here are the counts which no longer play a role in the conversion exercise. Thus to the new column number for column 1 is column 3 (i.e. the first vale at index 1). The reconversion array of the form:

    +---+---+---+---+---+---+
    |   | 2 | 5 | 1 | 3 | 4 |
    +---+---+---+---+---+---+           
    

countSingles

protected int[][] countSingles()

Counts number of occurrences of each single attribute in the input data.

Returns:

2-D array where first row represents column numbers and second row represents support counts.

orderFirstNofCountArray

protected void orderFirstNofCountArray(int[][] countArray,
                                       int endIndex)

Bubble sorts first N elements in count array produced by countSingles method so that array is ordered according to frequency of single items.

Used when ordering classification input data.

Parameters:

countArray - The 2-D array returned by the countSingles method.

endIndex - the index of the Nth element.

defConvertArrays

protected void defConvertArrays(int[][] countArray)

Defines conversion and reconversion arrays.

Parameters:

countArray - The 2-D array sorted by the orderCcountArray method.

recastInputData

public void recastInputData()

Recasts the contents of the data array so that each record is ordered according to conversion array.

Proceed as follows: 1) For each record in the data array. Create an empty new itemSet array. 2) Place into this array attribute/column numbers that correspond to the appropriate equivalents contained in the conversion array. 3) Reorder this itemSet and return into the data array.

recastInputDataAndPruneUnsupportedAtts

public void recastInputDataAndPruneUnsupportedAtts()

Recasts the contents of the data array so that each record is ordered according to ColumnCounts array and excludes non-supported elements.

Proceed as follows: 1) For each record in the data array. Create an empty new itemSet array. 2) Place into this array any column numbers in record that are supported at the index contained in the conversion array. 3) Assign new itemSet back into to data array

getNumSupOneItemSets

protected int getNumSupOneItemSets()

Gets number of supported single item sets (note this is not necessarily the same as the number of columns/attributes in the input set).

Returns:

Number of supported 1-item sets

reconvertItemSet

protected short[] reconvertItemSet(short[] itemSet)

Reconverts given item set according to contents of reconversion array.

Parameters:

itemSet - the fgiven itemset.

Returns:

the reconverted itemset.

reconvertItem

protected short reconvertItem(short item)

Reconvert single item if appropriate.

Parameters:

item - the given item (attribute).

Returns:

the reconvered item.

insertRuleintoRulelist

protected void insertRuleintoRulelist(short[] antecedent,
                                      short[] consequent,
                                      double confidenceForRule,
                                      double supportForRule,
                                      double supportForAntecedent)

Inserts an (association/classification) rule into the linkedlist of rules pointed at by startRulelist.

The list is ordered so that rules with highest confidence are listed first. If two rules have the same confidence the new rule will be placed after the existing rule. Thus, if using an Apriori approach to generating rules, more general rules will appear first in the list with more specific rules (i.e. rules with a larger antecedent) appearing later as the more general rules will be generated first.

Parameters:

antecedent - the antecedent (LHS) of the rule.

consequent - the consequent (RHS) of the rule.

confidenceForRule - the associated confidence value.

supportForRule - the associated support value.

supportForAntecedent - the antecedent support value.

reallocInsert

protected short[] reallocInsert(short[] oldItemSet,
                                short newElement)

Resizes given item set so that its length is increased by one and new element inserted.

Parameters:

oldItemSet - the original item set

newElement - the new element/attribute to be inserted

Returns:

the combined item set

realloc1

protected short[] realloc1(short[] oldItemSet,
                           short newElement)

Resizes given item set so that its length is increased by one and appends new element (identical to append method)

Parameters:

oldItemSet - the original item set

newElement - the new element/attribute to be appended

Returns:

the combined item set

realloc2

protected short[] realloc2(short[] oldItemSet,
                           short newElement)

Resizes given array so that its length is increased by one element and new element added to front

Parameters:

oldItemSet - the original item set

newElement - the new element/attribute to be appended

Returns:

the combined item set

realloc2_new

protected short[] realloc2_new(short[] oldItemSet,
                               short newElement)

Resizes given array so that its length is increased by one element and new element added to front

Parameters:

oldItemSet - the original item set

newElement - the new element/attribute to be appended

Returns:

the combined item set

removeElementN

protected short[] removeElementN(short[] oldItemSet,
                                 int n)

Removes the nth element/attribute from the given item set.

Parameters:

oldItemSet - the given item set.

n - the index of the element to be removed (first index is 0).

Returns:

Revised item set with nth element removed.

complement

protected short[] complement(short[] itemSet1,
                             short[] itemSet2)

Returns complement of first itemset with respect to second itemset.

Parameters:

itemSet1 - the first given item set.

itemSet2 - the second given item set.

Returns:

complement if itemSet1 in itemSet2.

sortItemSet

protected void sortItemSet(short[] itemSet)

Sorts an unordered item set.

Parameters:

itemSet - the given item set.

notMemberOf

protected boolean notMemberOf(short number,
                              short[] itemSet)

Checks whether a particular element/attribute identified by a column number is not a member of the given item set.

Parameters:

number - the attribute identifier (column number).

itemSet - the given item set.

Returns:

true if first argument is not a member of itemSet, and false otherwise

copyItemSet

protected short[] copyItemSet(short[] itemSet)

Makes a copy of a given itemSet.

Parameters:

itemSet - the given item set.

Returns:

copy of given item set.

outputDataArray

public void outputDataArray()

Outputs stored input data set; initially read from input data file, but may be reordered or pruned if desired by a particular application.

outputItemSet

protected void outputItemSet(short[] itemSet)

Outputs a given item set.

Parameters:

itemSet - the given item set.

outputRules

public void outputRules()

Outputs contents of rule linked list (if any) assuming that the list represents a set of ARs.

outputRules

public void outputRules(AssocRuleMining.RuleNode ruleList)

Outputs given rule list.

Parameters:

ruleList - the given rule list.

twoDecPlaces

protected double twoDecPlaces(double number)

Converts given real number to real number rounded up to two decimal places.

Parameters:

number - the given number.

Returns:

the number to two decimal places.

getRulesSet

public java.util.ArrayList<AssociationRule> getRulesSet()

It constructs a rules set once the algorithm has been carried out.

Returns:

An array of association rules having both minimum confidence and support