FPGrowth Presentation

17
L’algoritmo FPGrowth Marco Montanari Francesco Salbaroli

Transcript of FPGrowth Presentation

Page 1: FPGrowth Presentation

L’algoritmo FPGrowth

Marco MontanariFrancesco Salbaroli

Page 2: FPGrowth Presentation

Cosa è FPGrowth?

Come funziona?

A cosa serve?

La nostra implementazione

I Dataset

Page 3: FPGrowth Presentation

E’ un Associatore

E’ basato sul concetto di Apriori, con alcune differenze:

Non genera tutte le possibili soluzioni e le valuta in seguito (Generate and test)

Minimizza l’occupazione di memoria

Page 4: FPGrowth Presentation

Fase 1: Ricerca del Frequent Item Set1. Innanzitutto è necessario trovare il set di termini frequenti

del database e calcolarne il supporto. 2. Ordinato il set in ordine decrescente, si ottiene L,la lista di

termini frequenti.

Fase 2: Creazione dell’albero 1. Per ogni transazione T nel database gli elementi della

transazione vengono ordinati secondo L. 2. Detta T=[p|P], si controlla che il nodo radice non abbia già

l’elemento p tra i suoi figli. 1. Se è così, il nodo viene aggiunto e viene invocato un metodo

ricorsivo per l’aggiunta della coda P a p. 2. In caso contrario la coda P viene aggiunta direttamente

all’elemento p già presente.

Page 5: FPGrowth Presentation

procedure FP_growth (Tree, a)

if Tree contains a single path P then

for each combination (denoted as b) of the nodes in the path P

generate pattern with support = minimum support of nodes in b;

else for each in the header of Tree {

generate pattern b = with support = .support;

construct b 's conditional pattern base and then b 's conditional FP_tree Treeb;

if then

call FP_growth (Treeb, b);

}

Fase 3: FPGtowth

Page 6: FPGrowth Presentation

Viene utilizzato in modo massiccio nella valutazione di cosa mostrare al cliente in ambiti di commercio sia elettronico che non (Basket analysis): La relazione evidenziata

è infatti del tipo “chi ha fatto questo ha fatto anche quest’altro con questa probabilità”

Page 7: FPGrowth Presentation

Offre un framework che permette di

Semplificare l’accesso ai dati

Semplificare la gestione del plugin

Non occuparsi dei particolari poco interessanti quali la GUI e l’interazione con l’utente

Page 8: FPGrowth Presentation
Page 9: FPGrowth Presentation

inst = tuples.nextElement();

Enumeration<Attribute> attributes = inst.enumerateAttributes();

String tid = inst.stringValue(attributes.nextElement());

ArrayList<String> list = new ArrayList<String>();

while (attributes.hasMoreElements()) {

Attribute item = attributes.nextElement();

tmp = inst.stringValue(item);

StringTokenizer tok = new StringTokenizer(tmp,";");

while(tok.hasMoreElements()) {

String element = tok.nextToken();

list.add(element);

}

}

m_itemSet.sortExternalVector(list);

if(m_verbose) {

System.out.print("Elementi ordinati di TID "+tid+": ");

for (String string : list) {

System.out.print(string);

}

System.out.println();

}

m_tree.addTransaction(list);

for(String item : m_itemSet.getInvertedSortedSet()) {

Vector<TreeNode> nodes = TreeNodeManager.getInstance().getNodes(item);

CandidateRootTreeNode tmpSubTree = new CandidateRootTreeNode();

for (TreeNode node : nodes) {

tmpSubTree.addSubTree(node);

}

if (m_verbose) {

System.out.println("Unpruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

tmpSubTree.prune(item, m_calcMinSupport);

if (m_verbose) {

System.out.println("Pruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

toStringResult = toStringResult.concat(tmpSubTree.wekaToString());

if (m_verbose) {

System.out.println("WekaToString:");

System.out.println(tmpSubTree.wekaToString());

}

}

Page 10: FPGrowth Presentation

inst = tuples.nextElement();

Enumeration<Attribute> attributes = inst.enumerateAttributes();

String tid = inst.stringValue(attributes.nextElement());

ArrayList<String> list = new ArrayList<String>();

while (attributes.hasMoreElements()) {

Attribute item = attributes.nextElement();

tmp = inst.stringValue(item);

StringTokenizer tok = new StringTokenizer(tmp,";");

while(tok.hasMoreElements()) {

String element = tok.nextToken();

list.add(element);

}

}

m_itemSet.sortExternalVector(list);

if(m_verbose) {

System.out.print("Elementi ordinati di TID "+tid+": ");

for (String string : list) {

System.out.print(string);

}

System.out.println();

}

m_tree.addTransaction(list);

for(String item : m_itemSet.getInvertedSortedSet()) {

Vector<TreeNode> nodes = TreeNodeManager.getInstance().getNodes(item);

CandidateRootTreeNode tmpSubTree = new CandidateRootTreeNode();

for (TreeNode node : nodes) {

tmpSubTree.addSubTree(node);

}

if (m_verbose) {

System.out.println("Unpruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

tmpSubTree.prune(item, m_calcMinSupport);

if (m_verbose) {

System.out.println("Pruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

toStringResult = toStringResult.concat(tmpSubTree.wekaToString());

if (m_verbose) {

System.out.println("WekaToString:");

System.out.println(tmpSubTree.wekaToString());

}

}

Page 11: FPGrowth Presentation

inst = tuples.nextElement();

Enumeration<Attribute> attributes = inst.enumerateAttributes();

String tid = inst.stringValue(attributes.nextElement());

ArrayList<String> list = new ArrayList<String>();

while (attributes.hasMoreElements()) {

Attribute item = attributes.nextElement();

tmp = inst.stringValue(item);

StringTokenizer tok = new StringTokenizer(tmp,";");

while(tok.hasMoreElements()) {

String element = tok.nextToken();

list.add(element);

}

}

m_itemSet.sortExternalVector(list);

if(m_verbose) {

System.out.print("Elementi ordinati di TID "+tid+": ");

for (String string : list) {

System.out.print(string);

}

System.out.println();

}

m_tree.addTransaction(list);

for(String item : m_itemSet.getInvertedSortedSet()) {

Vector<TreeNode> nodes = TreeNodeManager.getInstance().getNodes(item);

CandidateRootTreeNode tmpSubTree = new CandidateRootTreeNode();

for (TreeNode node : nodes) {

tmpSubTree.addSubTree(node);

}

if (m_verbose) {

System.out.println("Unpruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

tmpSubTree.prune(item, m_calcMinSupport);

if (m_verbose) {

System.out.println("Pruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

toStringResult = toStringResult.concat(tmpSubTree.wekaToString());

if (m_verbose) {

System.out.println("WekaToString:");

System.out.println(tmpSubTree.wekaToString());

}

}

Page 12: FPGrowth Presentation

inst = tuples.nextElement();

Enumeration<Attribute> attributes = inst.enumerateAttributes();

String tid = inst.stringValue(attributes.nextElement());

ArrayList<String> list = new ArrayList<String>();

while (attributes.hasMoreElements()) {

Attribute item = attributes.nextElement();

tmp = inst.stringValue(item);

StringTokenizer tok = new StringTokenizer(tmp,";");

while(tok.hasMoreElements()) {

String element = tok.nextToken();

list.add(element);

}

}

m_itemSet.sortExternalVector(list);

if(m_verbose) {

System.out.print("Elementi ordinati di TID "+tid+": ");

for (String string : list) {

System.out.print(string);

}

System.out.println();

}

m_tree.addTransaction(list);

for(String item : m_itemSet.getInvertedSortedSet()) {

Vector<TreeNode> nodes = TreeNodeManager.getInstance().getNodes(item);

CandidateRootTreeNode tmpSubTree = new CandidateRootTreeNode();

for (TreeNode node : nodes) {

tmpSubTree.addSubTree(node);

}

if (m_verbose) {

System.out.println("Unpruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

tmpSubTree.prune(item, m_calcMinSupport);

if (m_verbose) {

System.out.println("Pruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

toStringResult = toStringResult.concat(tmpSubTree.wekaToString());

if (m_verbose) {

System.out.println("WekaToString:");

System.out.println(tmpSubTree.wekaToString());

}

}

Page 13: FPGrowth Presentation

inst = tuples.nextElement();

Enumeration<Attribute> attributes = inst.enumerateAttributes();

String tid = inst.stringValue(attributes.nextElement());

ArrayList<String> list = new ArrayList<String>();

while (attributes.hasMoreElements()) {

Attribute item = attributes.nextElement();

tmp = inst.stringValue(item);

StringTokenizer tok = new StringTokenizer(tmp,";");

while(tok.hasMoreElements()) {

String element = tok.nextToken();

list.add(element);

}

}

m_itemSet.sortExternalVector(list);

if(m_verbose) {

System.out.print("Elementi ordinati di TID "+tid+": ");

for (String string : list) {

System.out.print(string);

}

System.out.println();

}

m_tree.addTransaction(list);

for(String item : m_itemSet.getInvertedSortedSet()) {

Vector<TreeNode> nodes = TreeNodeManager.getInstance().getNodes(item);

CandidateRootTreeNode tmpSubTree = new CandidateRootTreeNode();

for (TreeNode node : nodes) {

tmpSubTree.addSubTree(node);

}

if (m_verbose) {

System.out.println("Unpruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

tmpSubTree.prune(item, m_calcMinSupport);

if (m_verbose) {

System.out.println("Pruned candidate tree:");

System.out.println(""+ tmpSubTree);

}

toStringResult = toStringResult.concat(tmpSubTree.wekaToString());

if (m_verbose) {

System.out.println("WekaToString:");

System.out.println(tmpSubTree.wekaToString());

}

}

Page 14: FPGrowth Presentation

I due dataset selezionati sono

Il dataset dimostrativo del paper

Un dataset legato ad un ipotetico negozio di DVD, con acquisti effettuati da utenti di vario genere e con diversi interessi di argomento o attori

Page 15: FPGrowth Presentation

FP-Growth Apriori

Pro Contro Pro Contro

Minimizza la ricerca di nodi

Grande quantità di

memoria per mantenere

tutti i percorsi possibili.

Ricerca completamente tutte le

combinazioni

Ricerca completamente tutte le

combinazioni

E’ necessario esplorare tutto

l’albero più volte, quindi da un

punto di vista temporale

diventa molto oneroso

n=5

n=15

n=25

n=35

Tempo di esecuzioneSi osserva come le performancedegradino non tanto all’aumentaredella dimensione delle transazioni,quanto più che altro all’aumentaredel loro numero.

Page 16: FPGrowth Presentation

FP-Growth Apriori

Pro Contro Pro Contro

Minimizza la ricerca di nodi

Grande quantità di

memoria per mantenere

tutti i percorsi possibili.

Ricerca completamente tutte le

combinazioni

Ricerca completamente tutte le

combinazioni

E’ necessario esplorare tutto

l’albero più volte, quindi da un

punto di vista temporale

diventa molto oneroso

n=5

n=15

n=25

n=35

Tempo di esecuzioneSi osserva come le performancedegradino non tanto all’aumentaredella dimensione delle transazioni,quanto più che altro all’aumentaredel loro numero.

Sarebbe stato interessante usare

un cubo OLAP…

Page 17: FPGrowth Presentation