de.lmu.ifi.dbs.elki.algorithm.itemsetmining

Class FPGrowth.FPTree

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.FPGrowth.FPNode

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.FPGrowth.FPTree

Enclosing class:

FPGrowth

public static class FPGrowth.FPTree
extends FPGrowth.FPNode

FP-Tree data structure

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) static interface	FPGrowth.FPTree.Collector Interface for collecting frequent itemsets found.

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.algorithm.itemsetmining.FPGrowth.FPNode

FPGrowth.FPNode.Translator

Field Summary

Fields

Modifier and Type	Field and Description
(package private) FPGrowth.FPNode[]	header Header table
(package private) int	nodes Number of nodes in the tree (statistics only).

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.itemsetmining.FPGrowth.FPNode

children, count, EMPTY_CHILDREN, INITIAL_SIZE, key, numchildren, parent, sibling

Constructor Summary

Constructors

Constructor and Description
FPTree(int items) Constructor.

Method Summary

Modifier and Type	Method and Description
void	extract(int minsupp, int minlength, int maxlength, boolean destruct, FPGrowth.FPTree.Collector col) Extract itemsets ending in the given item.
private void	extract(int minsupp, int minlength, int maxlength, int item, int[] postfix, int plen, int[] buf2, int[] buf3, boolean destruct, FPGrowth.FPTree.Collector col) Extract itemsets ending in the given item.
private void	extractLinear(int supp, int minlength, int maxlength, int item, int[] postfix, int plen, int[] buf2, FPGrowth.FPTree.Collector col) Extract itemsets from a linear tree.
void	insert(int[] buf, int i, int l, int weight) Insert an itemset into the tree.
void	logStatistics() Output some statistics to logging.
FPGrowth.FPNode	newNode(FPGrowth.FPNode parent, int label) Create a new node of the FP-tree, linking it into the header table.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.itemsetmining.FPGrowth.FPNode

appendTo, insert, reduceMemory

Methods inherited from class java.lang.Object

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

Field Detail

header

FPGrowth.FPNode[] header

Header table

nodes

int nodes

Number of nodes in the tree (statistics only).

Constructor Detail

FPTree

public FPTree(int items)

Constructor.

Parameters:

items - Number of items in header table

Method Detail

insert

public void insert(int[] buf,
                   int i,
                   int l,
                   int weight)

Insert an itemset into the tree.

Parameters:

buf - Buffer

i - Start position in buffer

l - End position in buffer

weight - Weight

newNode

public FPGrowth.FPNode newNode(FPGrowth.FPNode parent,
                               int label)

Create a new node of the FP-tree, linking it into the header table.

Parameters:

parent - Parent node

label - Node label

Returns:

New node

extract

public void extract(int minsupp,
                    int minlength,
                    int maxlength,
                    boolean destruct,
                    FPGrowth.FPTree.Collector col)

Extract itemsets ending in the given item.

Parameters:

minsupp - Minimum support

minlength - Minimum length

maxlength - Maximum length

destruct - Remove nodes

col - Itemset collector

extract

private void extract(int minsupp,
                     int minlength,
                     int maxlength,
                     int item,
                     int[] postfix,
                     int plen,
                     int[] buf2,
                     int[] buf3,
                     boolean destruct,
                     FPGrowth.FPTree.Collector col)

Extract itemsets ending in the given item.

Parameters:

minsupp - Minimum support

minlength - Minimum length

maxlength - Maximum length

item - Current item

postfix - Items to append

plen - Postfix length

buf2 - Scratch buffer

buf3 - Scratch buffer

destruct - Remove nodes

col - Itemset collector

extractLinear

private void extractLinear(int supp,
                           int minlength,
                           int maxlength,
                           int item,
                           int[] postfix,
                           int plen,
                           int[] buf2,
                           FPGrowth.FPTree.Collector col)

Extract itemsets from a linear tree.

Parameters:

supp - Current support

minlength - Minimum length

maxlength - Maximum length

item - Current item

postfix - Postfix for extracted itemsets

plen - Postfix length

buf2 - Scratch buffer

col - Output collector

logStatistics

public void logStatistics()

Output some statistics to logging.