Post on 28-Jun-2015
L’algoritmo FPGrowth
Marco MontanariFrancesco Salbaroli
Cosa è FPGrowth?
Come funziona?
A cosa serve?
La nostra implementazione
I Dataset
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
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.
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
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à”
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
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());
}
}
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());
}
}
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());
}
}
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());
}
}
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());
}
}
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
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.
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…