Lezioni 12 13

Lezione 12-13

Il principale obbiettivo di questa lezione è quello di incominciare a vedere come l’ information si vada a collegare ai discorsi che abbiamo fatto fino a questo punto,che sono sostanzialmente su come è strutturato il web,e avevamo posto attenzione su come questi elementi sono importanti per definire la rilevanza di alcuni nodi all’ interno del web e vedremo come questo diventi uno dei principali ostacoli quando dobbiamo tracciare il web. In parte il problema di tracciare le risorse in web può essere ridotto a quello di costruire un software,che solitamente vengono chiamati crawler,che sia in grado di navigare attraverso il web automaticamente e che sia in grado di tenere traccia di tutte le varie risorse che sono disponibili. Questo solitamente serve ai motori di ricerca per poi indicizzare dei contenuti costruendo degli indici,ma può anche servire per altri scopi,ad esempio può essere utile per studiare la struttura del web oppure per delle statistiche. Sappiamo che questo genere di software possono avere diversi nomi,uno di questi è spider. Solitamente hanno nomi diversi in base a cosa effettivamente fanno, quelli che hanno il compito di navigare in modo random attraverso la rete vengono riferiti con il nome di crawler.
Un primo problema da affrontare è quello della scalabilità nel momento in cui andremo a sviluppare un software di questo tipo,ovvero ci serve capire quale è il numero di pagine al di la del quale il nostro programma inizierà ad avere problemi e quindi no sarà più in grado di uscire da una certa area della rete in cui ha iniziato a navigare. In generale il problema della scalabilità dipende da strategie di percorrenza dei collegamenti,da strategie che il nostro software usa.
L’ architettura di base deve avere una componente che contenga una serie di url che si vogliono scaricare,che in alcuni casi sono date a priori,anche se più comunemente si vuole che questa lista via via si aggiorni. Dopo di che dovremmo trasformare le url in un numero ip e utilizzare questo per scaricare i documenti che ci serviranno per varie cose ,ma di base ci serve per ottenere nuove collegamenti. Andremo successivamente ad estrarre e analizzare i link contenuti all’ interno delle pagine che ci serviranno per aggiornare la nostra lista url.
Un’ altro elemento che non può mancare in nessun software di questo tipo è il fatto che dovremo verificare se abbiamo già visitato varie pagine.
A lezione abbiamo visto un esempio da architettura di uno dei primi crawler che sia stato descritto in modo analitico su letteratura di ricerca,quindi diverso da crawler industriali e descritti in modo sommario.Questo nuovo crawler si chiama Mercato ed è uno degli antenati di quelli oggi disponibili.
Questa architettura è composta da una parte che contiene la lista delle url,che di solito viene chiamato url frontier e da una parte che sia in grado di scorrere la lista di aree url da scaricare al componente successivo. Dovremo anche tenere in memoria questa lista che può essere ricondotta al problema di ottimizzazione di scalabilità. Se si riesce a mantenere una lista abbastanza grande abbiamo un vantaggio.
Non bisogna tralasciare il fatto che l’ accesso alla memoria ha un costo computazionale e le due scelte antitetiche sono mantenere la lista su memoria di ram,o su memoria di massa. Nel primo caso abbiamo vantaggi di accesso in lettura,nel secondo caso abbiamo il vantaggio della dimensione della lista.
A questo punto abbiamo un secondo componente che si occuperà di scaricare i nostri documenti e si interfaccerà con internet conoscendo i protocolli di comunicazione di internet,su tutti http e conoscendo modi particolari di definire e costruire dei collegamenti,ad esempio oggi sono molto diffuse le api. Un buon modulo di gestione di gestione del download,dovrà conoscere la struttura e la forma di alcune api particolarmente utilizzate.
Ovviamente anche in questo punto ci sono degli elementi di ottimizzazione che possono essere messi in gioco. Avremo sicuramente bisogno di fare riferimento a un dns.
È importante specificare che ovviamente noi potremmo essere interessati solo ad un certo tipo di contenuti, nel nostro caso saranno le pagine html.
Una volta scaricati i documenti dobbiamo analizzarli e da questi estrarre i link,tenendo presente che avrò dei problemi di normalizzazione delle url , quando da url relative le devo trasformare in assolute.
Se noi vogliamo indicizzare i documenti,bisogna tenere presente che esistono diversi tipi di indicizzazione,ad esempio quella generica e quella particolare. Nella sezione del modulo che si occupa di analizzare i documenti e estrarre i link ,abbiamo un modulo di input stream, che sostanzialmente ci dice come uno dei problemi che ha un qualsiasi crawler,sia la gestione in parallelo dell’ analisi dei nostri documenti,nel senso che dovremo gestire in parallelo più di un documento alla volta.
Un’ altro problema tipico è quello di verificare le url che abbiamo già visitato,quindi ce il solito problema di mantenimento della lista. Ovviamente si possono fare delle misure empiriche su quanto dovranno essere ampie queste liste,in proporzione alla dimensione stimata di web che si pensa di andare ad indicizzare.
In base agli obbiettivi che si anno di indicizzazione,al tipo di risorse che vogliamo indicizzare e al tipo di sottocomunità del web che ci interessa analizzare noi potremmo avere strategie di navigazione più o meno funzionali. Di base la strategia di lettura più semplice è quella dove in ampiezza vado ad analizzare il grafo delle mie relazioni.
Inizialmente il problema più sentito fu quello della scalabilità ;come implementare un crawler che fosse scalabile ,in grado di navigare all’ interno di molti url e non finire all’ interno di circoli viziosi.
I limiti di scalabilità possono essere limiti legati alle risorse (capacità di gestione del dns .url …),oppure possono essere limiti nella capacità di uscire da circoli viziosi che possiamo vedere come vincoli locali nel nostro spazio di ricerca.
Le strategie di navigazione sono strategie che ci interessano perché strategie diverse si adottano meglio a strutture diverse. Questo è il succo e il concetto che ci permetterà di collegarci con quanto fatto fino ad ora . Ce una strategia di relazione che mi dice come relazionare le url che devo navigare e la politica più semplice è quella fifo,che è una strategia di aggiornamento. Ci sono strategie di parallelizizione e queste sono molto importanti in questo ambito,ci sono poi strategie per il rispetto delle regole di pliteness.
Per quanto riguarda la selezione,si è pensato di dare più importanza alle pagine che nel web hanno una maggiore rilevanza. Ci sono strategie di path-ascending che sfruttano la struttura degli schemi degli url per avere una informazione su dove andare a cercare ulteriori risorse.
Un’ altra strategia importante è quella che prende il nome di page rank. Per quanto riguarda questa strategia,ci possono essere due approcci,o si una propria page rank,o si può fare riferimento ad una informazione esterna che mi dice quali sono le pagine con il page rank più alto.
Per le strategie di aggiornamento le due misure per definirlo sono freshness e age,cioè quanto una risorsa è fresca e quanto è datata.
Per la politica di aggiornamento, possiamo avere la politica più semplice ,che è quella dove si definisce un criterio uniforme per tutti,oppure può essere proporzionale alla velocità di aggiornamento. Se una risorsa viene aggiornata molto spesso definirò un suo valore di aging freschness diverso.
Degli studi, hanno mostrato, come la politica di aggiornamento proporzionale alla frequenza di aggiornamento di una risorsa,nel tempo,funzione peggio rispetto all’ aggiornamento uniforme,perché sostanzialmente si va a dedicare più attenzione a delle risorse che vengono aggiornate frequentemente. Quindi la politica migliore è quella di penalizzare quelle risorse con una frequenza di aggiornamento molto alta.
Di base tutti i discorsi fatti sulle strategie sono nati per affrontare il problema della scalabilità ovvero come rendere questi software scalabili. Si è notato però che queste regole avevano una influenza importante sul comportamento del crawler ,quindi la capacità di indicizzare,a quali strutture il crawler era in grado di adeguarsi e quali potevano metterlo in crisi.
La politica utilizzata dal crowler può influenzare notevolmente il risultato che noi abbiamo nel momento in cui andiamo a costruire la mappa delle risorse.
È importante dire che in una rete direzionata come il web,dove i collegamenti hanno una specifica direzione,giocano un ruolo fondamentale i nodi che sono collegati tra di loro. La rilevanza che viene data a questi nodi,dipende dalle politiche dei crawler e può avere effetti sulla mappa del web che si andrà a definire.
È interessante dire che sono stati fatti dei lavori in torno al 2000 riguardanti la produzione i focused crawler. Lavori relativi sostanzialmente a selezionare le risorse in base a criteri il più possibile semplice legati ai contenuti delle risorse. Il più possibili semplici,perché si voleva mantenere l’ efficienza computazionale di tutto il software entro livelli accettabili,e quindi sono stati proposti diversi metodi,come guardare semplicemente le url ,oppure considerare il testo come semplici vettori di parole e cercare di fare dei confronti tra questi. Questi sono stati gli approcci tradizionalmente usati.
La differenza tra gli approcci inizialmente studiati e questi tipi di approcci,sta nel fatto che nel primo caso ci si concentra sulla risorsa,mentre nel secondo caso ci si concentra su dove è collocata la risorsa all’ interno del contesto che andiamo ad analizzare.
Una nozione sicuramente fondamentale è quella di densità,che è definita come il rapporto tra il numero massimo di archi all’ interno di un grafo e il numero che riscontriamo nella rete,tenendo conto della differenza che ce se si parla di grafo orientato e non orientato.
L’ idea di comunità può essere legato al fatto che la densità di quell’ area deve essere maggiore rispetto alla densità che quell’ area ha nei confronti del complemento.
Questa nozione permette inoltre di definire un ordine gerarchico,perché il sotto cluster di un cluster avrà anche lui questa proprietà e potrà contenere al suo interno degli altri sotto cluster.
È importante definire la differenza tra modelli crisp e modelli multivalenti. Nel caso del modello crisp,un nodo appartiene ad un certo livello solo ad una comunità,mentre nel modello multivalente un nodo può appartenere a più di una comunità.
Questo diventa particolarmente importante nel momento in cui non si vuole limitare l’ esplorazione ad uno spazio specifico. Quindi nel momento in cui progettiamo un crawler abbiamo sempre la necessità di muoverci nello spazio,quindi identificare delle aree di confine tra comunità è importante e la doppia appartenenza è una definizione immediata di confine.
Possiamo avere definizione più forti e più deboli di comunità. Una definizione forte è quella che ci dice che il grado dei nodi all’ interno della comunità deve essere maggiore del grado che questi nodi hanno con i nodi esterni alla comunità. Una definizione forte va a restringere le aree che andremo ad identificare.
Una definizione più debole potrebbe non considerare il fatto che il grado di ogni singolo nodo deve essere maggiore all’ interno rispetto che all’ esterno,ma semplicemente fare una somma globale;il numero globale dei gradi all’ interno della comunità sia maggiore rispetto a quello esterno e con una definizione di questo tipo siamo in grado di identificare delle comunità in modo più ampio e siamo anche in grado di identificare nodi che possono appartenere a più di una comunità.
Un’ altra definizione è quella di modularità, che è legata al rapporto che ho tra i nodi che posso riscontrare in un area e il numero di archi data una certa probabilità.
È importante distinguere due tipi di archi,quelli espliciti e quelli impliciti. Non esiste un nodo univoco per differenziare le due tipologie. L arco esplicito sarà un arco che possiamo andare ad identificare in una certa base di dati,implicito è un arco che noi deriviamo tramite delle regole.
Molto spesso il successo di una analisi,dipende dipende dalla capacità di identificare delle relazioni non molto evidenti.
Il poter definire delle relazioni esplicite,mi permette di aumentare la mia capacità di analisi.
Un modo per analizzare una struttura è quello di valutare la similarità tra nodi. Una misura di similarità è data dall’ intersezione fratto l’ unione e questa misura si può generalizzare attraverso una funzione.
Vi sono diverse misure che si utilizzano per generalizzare la nozione di similarità. Le più utilizzate sono l’ indice di citazione e l’ indice di citazione comune. Il primo riguarda tutti i nodi che citano sia la risorsa A che quella B,mentre il secondo riguarda le citazioni che sia A che B hanno in comune. Quindi questo è un modo per andare a definire delle relazioni esplicite.
Man mano che si naviga si va a costruire una base di conoscenza e si definisce la struttura della nostra rete e su quella si comincia fare delle analisi di identificazione di comunità. Nel momento in cui avremo definito una comunità,saremo interessati ad esplorare questa in modo più approfondito,quindi il nostro crawler dovrà inizialmente cercare di navigare in modo ampio uno spazio,rimanendo in superficie e utilizzare questa navigazione per costruire una mappa della struttura.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License