Progetto di Sistemi ad Agenti
2012/2013
Peoples:
• Michele Carillo
• Benedetto Cosentino
• Francesco Milone
• Sebastiano Porciello
• Francesco Raia
• Flavio Serrapica
• Carmine Spagnuolo
2
Overview
• Architettura e Problematiche progettuali
• TF-IDF
• JUNG
3
Architettura
4
ESNA: Architettura
Obiettivi:
• Disaccoppiamento tra Engine di ESNA e la componente di
Visualization
• Consentire l’esecuzione da linea di comando e da GUI
permettendo in entrambi i casi di avviare la visualizzazione
• Utilizzo della programmazione multi-thread per realizzare il
modello basato su agenti
5
ESNA: Architettura
Engine
•
•
•
•
SNA
Util
GUI
AgentBased
Model
Visualization
Execution
SNA
A
A
G
A
A
A
6
ESNA: Architettura-GUI
7
ESNA: Architettura-GUI
8
ESNA: Architettura
Focus su AgentBasedModel e Util
• AgentBasedModel:
o Definizione: un sistema di calcolo che utilizza unità specializzate
chiamate agenti. Un agente ha uno stato, possiede una
competenza, ed è in grado di avviare e reagire agli eventi. A volte
tali agenti possono essere anche chiamati oggetti. Un oggetto è
un termine generico che comprende un elemento di calcolo e uno
stato locale. Esso può essere visto come un concetto o come la
struttura tecnica che è alla base del paradigma di
programmazione orientato agli oggetti.
o Nella swarm intelligence gli agenti rappresentano singoli individui
di un gruppo capace di interagire.
9
ESNA: Architettura
•
Focus su AgentBasedModel e Util.
AgentBasedModel:
• Intuizione: dato che gli agenti
per i nostri scopi hanno un
certo obiettivo e comportano
un elevato carico
computazionale possiamo
mappare ogni agente ad un
singolo Thread e mantenere
la struttura AgentBased.
• Agent(Interface)
o GoogleAgent
o ForwardAgent
• StateModel
10
ESNA: Architettura
GoogleAgent:
• Thread
• Obiettivo: dato un insieme S di keywords trova k
link “utili” da google.com e genera altrettanti ForwardAgent,
0 < k ≤ DELTA_LINKS
• Consideriamo un link “utile” quando non compare in un insieme di
link non analizzabili: facebook, twitter, gmail, google, bing, etc
o GoogleAgent per la verifica sui link utili, utilizza CheckSites presente
nel package Util
- CheckSites è una struttura dati che carica N siti web da un file
esponendo il metodo check(url) che in O(1) verifica la presenza del
link
11
ESNA: Architettura
ForwardAgent:
• Thread - Obiettivo: valutazione della positività e il sentimento del sito
associato alla URL per cui viene creato
• Behaviour:
o Calcola X come l’insieme dei link della pagina e T come l’insieme delle
frasi della pagina
o Se |X|>DELTA_LINKS, calcola X’ come un sottoinsieme random di X tale
che |X’| = DELTA_LINKS, X=X’
o Se |T|<DELTA_SENTENCES e |X|>0, sceglie a caso una nuova URL e ripete
il procedimento altrimenti termina
o Calcola il valore p=(|X|+|T|*2)/(DELTA_LINKS+2*DELTA_SENTENCES)
o Calcola gli insiemi Y risultante dalla sentiment analysis e P dall’analisi
della positività
o Eventualmente aggiunge se stesso alla componente grafica
o Memorizza I valori di Y e P
o Valuta p per ogni link trovato nella pagina al fine di decidere se generare
nuovi agenti per ogni link
12
Search Util
La costruzione del Network prevede che ogni nodo deve eseguire
una richiesta all’engine di Google per ottenere dei link.
È possibile procedere in due modi:
• Request: eseguire richieste HTTP utilizzando il metodo GET a
www.google.com/search?q=keywords e parsare il risultato al fine di
estrapolare i link della pagina. (Negli ultimi mesi Google ha cambiato il
layout di recupero dei link rendendolo del tutto dinamico, quindi è
necessario valutare tutte le ancore della pagina.)
• API: utilizzare le API fornite dall’engine Google per eseguire le richieste,
tali API consentono di ottenere risposta in JSON. (Anche se sono
disponibili delle librerie per i più conosciuti linguaggi, tutte in versione
beta e alpha.)
13
Search Util
Problemi riscontrati:
• Request: presenta, al di fuori di un elevato costo
computazionale, il problema sul limite di richieste eseguibili da
un programma. Dopo un certo numero di richieste, anche se
intervallate da pause che simulano l’interazione reale di un
utente, non è più possibile eseguire richieste dato che si viene
inseriti in una black list che non dipende solo da ip e useragent.
• API: presenta un vincolo imposto da google sul numero di
richieste che è possibile effettuare in un giorno da un
programma che viene identificato da una key-app generata su
un account google.
14
Search Util
Soluzioni:
• Utilizzare Bing. È stata subito scartata a causa di problemi riscontrati
in entrambe le metodologie:
o Request: i nodi devono eseguire una particolare query che
consente di prelevare tutti i link che puntano ad una pagina, se
con Google ciò funziona egregiamente, con Bing da risultati
sperimentali si nota che non é possibile garantire la correttezza
dei risultati.
o API: sono presenti gli stessi problemi di google.
Once you have enabled billing, you will
continue to receive 100 free queries per day.
However, you will be billed for all additional
requests at the rate of $5 per 1000 queries,
for up to 10,000 queries per day.
15
Search Util
Soluzioni:
• Modificare la semantica delle richieste eseguendo su ogni nodo
normali richieste HTTP per una URL ed estrarre i link dalla
pagina che costituiranno i link entranti nel nodo della semantica
originale (ATTUALE SOLUZIONE):
o Per eseguire le richieste si utilizza una libreria chiamata
Jsoup che utilizzando un semplice client HTTP
(ApacheHTTPClient), una volta eseguita una richiesta per
una URL, produce un oggetto Document che consente la
navigazione della pagina utilizzando la struttura DOM, in
questo modo non viene solo semplificata l’estrazione dei
link ma anche delle frasi
16
TF-IDF
17
TF-IDF: Term Frequency–Inverse Document Frequency
Term Frequency–Inverse Document Frequency è una
statistica numerica che riflette quanto una parola sia
importante in un documento:
• La classe che implementava TF-IDF è stata riscritta in Java:
o Riutilizzare lo script già esistente in Python implicava creare una
ulteriore classe (sempre in Python) che istanziasse ed utilizzasse la
classe TFIDF
o Per poter eseguire uno script Python in Java è necessaria l’aggiunta
di numerose classi che offrivano solo un interprete Python per
Java.
18
TF-IDF: Term Frequency–Inverse Document Frequency
In Python
• Costruttore con parametri opzionali:
__init__(self, corpus_filename = None, stopword_filename =
None, DEFAULT_IDF = 1.5)
In Java
• Costruttore Java:
public TFIDF()
public TFIDF(String corpus_filename, String stopword_filename,
float idf_default)
• Si introduce una variabile
public final static double DEFAULT_IDF = 1.5 ;
19
TF-IDF: Term Frequency–Inverse Document Frequency
In Python
• Corpo del costruttore (inizializzazione variabili):
self.term_num_docs = {}
self.stopwords = []
In Java
• Corpo del costruttore:
term_num_docs = new HashMap<String, Integer>();
stopwords = new ArrayList<String>();
20
TF-IDF: Term Frequency–Inverse Document Frequency
In Python
• Metodo get_tokens
return re.findall(r"<a.*?/a>|<[^\>]*>|[\w'@#]+", str.lower())
In Java
• Metodo get_tokens
Pattern pat = Pattern.compile("<a.*?/a>|<[^\\\\>]*>|[\\w'@#]+");
Matcher match = pat.matcher(line.toLowerCase());
while(match.find())
{
// tmp è un ArrayList<String>();
if(tmp.contains(match.group()))
Continue;
Else
tmp.add(match.group());
}
21
TF-IDF: Term Frequency–Inverse Document Frequency
In Python
• Ordinamento decrescente di una lista[Key,element]
sorted(tfidf.items(), key=itemgetter(1), reverse=True)
In Java
• Ordinamento decrescente di una lista[Key,element]
TreeMap<String, Double> sortedMap = new TreeMap<String,
Double>(tfidf);
con tfidf: HashMap<String,Integer>
22
TF-IDF: Term Frequency–Inverse Document Frequency
In Python
• Creazione di un set
tokens_set = set(tokens) #tokens è una lista di Stringhe
In Java
• Creazione di un set
HashSet<String> set_words = new HashSet<String>();
23
TF-IDF: Term Frequency–Inverse Document Frequency
In Python
• Metodo:
add_input_document
self.num_docs += 1
words = set(self.get_tokens(input))
for word in words:
if word in self.term_num_docs:
self.term_num_docs[word] += 1
else:
self.term_num_docs[word] = 1
In Java
• Metodo:
add_input_document
num_docs += 1;
String[] words = get_tokens(input_line);
int frequency = 0;
for(String w : words)
{
if(term_num_docs.containsKey(w))
frequency =
term_num_docs.get(w) + 1;
Else
frequency = 1;
term_num_docs.put(w, frequency);
}
24
TF-IDF: Term Frequency–Inverse Document Frequency
In Python
• Metodo
save_corpus_to_file(self, idf_filename, stopword_filename,
STOPWORD_PERCENTAGE_THRESHOLD = 0.01)
In Java
• Metodo
public void save_corpus_to_file(String destination_corpus_file,
String destinatio_stopword_filename, double STOPW_THRESHOLD)
public void save_corpus_to_file(String destination_corpus_file,
String destinatio_stopword_filename)
• Introduzione di una variabile:
public final static double STOPWORD_PERCENTAGE_THRESHOLD =
0.01;
25
JUNG:
Java Universal
Network
Framework
26
JUNG: Java Universal Network/Graph Framework
Framework per la modellazione, l’analisi, e la visualizzazione
di grafi:
•
•
•
•
Framework object-oriented per ogni tipo di grafo
Open source (Licenza BSD)
Scritto in java
Grafici dinamici
Facilities offerte dal framework:
• Vari Layout che permettono di visualizzare il grafo senza
preoccuparsi delle coordinate (x,y) dei vertici
• Implementazione di molti algoritmi su grafo, tra cui: Clustering,
Massimo Flusso, Distanza tra due vertici, Page Rank, etc.
27
Visualizzazione Network
• La classe ViewNetwork.java si occupa della visualizzazione del
network costruito dalla parte engine. Le scelte architetturali
prevedono una netta separazione tra engine e visualization
quindi ViewNetwork realmente è un wrapper per la
visualizzazione utilizzabile in engine
• Metodi:






Init(): inizializza la classe e tutte le componenti.
Start(): fa partire il processo di visualizzazione
addVert(id): inserisce un nodo da visualizzare
addEdge(u, v): inserisce un arco tra il nodo u ed il nodo v
stopVisualization(): ferma il processo di visualizzazione
Process(): aggiorna la visualizzazione del grafo
28
Visualizzazione Network
Classe ViewNetwork
• La classe espone un unico metodo che astrae l’inserimento di
un nodo nella visualizzazione:
addGraphicComponent(Agent agent)
• Il metodo prende in input un’istanza della classe Agent e
provvede alla creazione di un nuovo nodo e un nuovo arco dal
nodo stesso verso il padre
29
Costruzione di un Network
30
Costruzione di un Network
31
Prossimi passi…
32