Università di Pisa Facoltà di Ingegneria
Corso di Laurea Specialistica in Ingegneria Informatica per la Gestione d'Azienda
Progettazione e realizzazione di un algoritmo per
l'analisi del linguaggio naturale basata sul
paradigma emergente
Relatori: Laureando: Prof. Gigliola Vaglini Claudio Atzeni Ing. Mario G.C.A. Cimino
Ing. Alessio Bechini
Indice generale
1Introduzione...5
1.1Controllo grammaticale tradizionale ed emergente...5
1.2Evoluzione del Web in ambito linguistico...7
1.3Obbiettivo della tesi...9
1.4Specifica dei requisiti...10
1.5Glossario...13
1.6Organizzazione della tesi...14
2Metodi e tecniche per la creazione del sistema...15
2.1Tecniche di ricerca in Google...15
2.2Cenni sul Data Mining...17
2.3Cenni sul Text Mining...19
2.4Cenni sul clustering...21
2.5Le espressioni regolari...21
3Progettazione...23
3.1Descrizione del sistema...23
3.1.1Creazione degli n-grammi e gestione dell'inciso...26
3.2Progettazione dell'algoritmo di elaborazione...28
3.3Realizzazione dei moduli di supporto...32
3.3.1Modulo dei servizi...33
3.3.2Modulo per la gestione dei nomi e numeri...33
3.3.3Modulo degli snippet...34
3.4Modulo per il clustering...35
3.5Formattazione del testo e gestione delle lingue...36
3.6Modulo per il rimpiazzo...36
3.7Interfacciamento con l'utente...38
4Implementazione...39
4.1Visione generale...39
4.2Realizzazione della struttura dati...40
4.2.1Realizzazione della classe Ngram...41
4.2.2Realizzazione della classe Segement...42
4.2.3Realizzazione della classe Phrase...43
4.3Realizzazione del servizio di ricerca delle occorrenze nel motore di ricerca...44
4.4Realizzazione del modulo di gestione nomi ...45
4.5Realizzazione del modulo di gestione numeri...46
4.6Realizzazione del Modulo della normalizzazione dei rapporti...46
4.7Realizzazione del Modulo delle distanze logaritmiche...47
4.8Realizzazione del modulo degli snippet...48
4.9Realizzazione dell'algoritmo di validazione...49
4.10Realizzazione del modulo di clustering...51
4.11Realizzazione del modulo di rimpiazzo...53
4.12Realizzazione del Modulo Manager...56
5Test...58
5.1Test sulle frasi corrette...59
5.2Test sulle frasi errate...63
6Conclusioni e sviluppi futuri...70
1 Introduzione
1.1 Controllo grammaticale tradizionale ed emergente
L’approccio tradizionale per la realizzazione di software di controllo grammaticale per il linguaggio naturale si basa su modelli che provengono dalla linguistica computazionale. In tale ambito, ci si concentra su formalismi descrittivi del funzionamento del linguaggio naturale, tali che si possano trasformare in programmi eseguibili dai computer. Similmente, l’approccio didattico tradizionale per l’insegnamento delle lingue si basa sulle regole della grammatica; una successione finita di regole necessarie alla corretta costruzione di frasi, sintagmi e parole. In sostanza, in entrambi gli approcci si adopera un paradigma prescrittivo o normativo, in cui la correzione dell’uso della lingua si basa su regole già determinate preliminarmente da un gruppo di studiosi del settore. Dal punto di vista ingegneristico tale approccio si definisce top-down, e richiede la codifica nel software di regole esplicite stabilite da esperti di dominio. Questo approccio ha diversi limiti: (a) per cogliere le varie eccezioni e sfumature della lingua naturale occorre modellare un’ampia casistica di eccezioni; (b) ci sono lingue che non sono strutturabili in tal modo; (c) è difficile rincorrere l’evoluzione moderna delle lingue naturali (es. influenze di lingue straniere e termini gergali che identificano una tendenza). Consideriamo invece la lingua naturale quale fenomeno sociale emergente, che non prevede alcuna elicitazione di regole. Infatti, la maggioranza delle persone parla correntemente la propria lingua senza ricordare in modo esplicito le regole
grammaticali, ma semplicemente tenendo a mente degli esempi e formulando frasi smontando e rimontando tali esempi. Un individuo medio ha in memoria qualche migliaio di termini e modi di dire, ed al posto delle regole grammaticali adopera semplici regole di interscambio dei termini di tali modi di dire. Ad esempio, sa che “Francesco” e “Fernanda” hanno la medesima valenza in termini strutturali. Nei corsi moderni di insegnamento delle lingue, ci si basa molto sull’uso della medesima in vari contesti, per consentire l’emergere di tale consapevolezza di interscambio. Per l’analisi del testo e per il suo controllo esistono due paradigmi in letteratura: uno detto cognitivista e l’altro emergente. Nel paradigma cognitivista si fa riferimento a un certo grado di conoscenza del linguaggio; seguendo questo paradigma, possono essere adottati due approcci: il primo, quello più convenzionale, è detto approccio simbolico, e consiste nel prendere in considerazione una grammatica, sulla base di cui stabilire la validità e la correttezza di un testo. Questa soluzione, però, presenta degli svantaggi. Oltre al fatto di dipendere dalla lingua usata (un sistema per l’italiano non è valido, per esempio, per la lingua inglese), uno strumento che si basa su una grammatica non tiene conto dell’evoluzione cui inevitabilmente una lingua va incontro: la grammatica è infatti composta da un insieme di regole statiche. Oltre a ciò, va tenuto conto del fatto che un linguaggio può essere usato in maniera differente a seconda del contesto (scritto, parlato, ecc.), mentre una grammatica tiene conto prevalentemente del contesto scritto e solo in misura minore degli altri scenari di utilizzo. Per ovviare a questi inconvenienti, si può adottare un altro approccio, sempre facente parte del paradigma cognitivista: l’approccio statistico. Esso consiste nell’analizzare il linguaggio usato comunemente, ad esempio attraverso dei documenti, per ricavarne un modello matematico dei fenomeni linguistici. A
differenza dell’approccio precedente, in questo caso la conoscenza del linguaggio è contenuta negli indici statistici progettati. In entrambi i casi, occuparsi dei diversi contesti significherebbe rendere i modelli non gestibili, per la grande varietà e dinamicità presente nei linguaggi. Il paradigma emergente è ben diverso, in quanto l’analisi del testo non fa uso di regole grammaticali relative al linguaggio usato. Applicando il paradigma emergente al linguaggio, ne risulta che un certo modo di esprimersi è tanto più adeguato quanto più viene adoperato. Questo tipo di validità però non è indipendente dal contesto e dalla comunità in cui viene adoperato il linguaggio: possiamo infatti avere frasi molto comuni nelle conversazioni e poco usate nei testi, così come espressioni arcaiche formalmente corrette ma obsolete. Cade pertanto il concetto formale di correttezza, e viene sostituito da quello di adeguatezza: un modo di esprimersi è inadeguato se non appartiene a nessun cluster in nessun contesto. Nella progettazione di software che analizza i periodi con tale approccio occorrono nuovi paradigmi funzionali e architetturali, e un’ampia casistica, quest’ultima è fornita dal Web.
1.2 Evoluzione del Web in ambito linguistico
Il Web è diventato, con il passare degli anni, il più grande repository di dati esistente, con stime recenti di più di 500 miliardi di documenti online. Blog, Wiki, Pagine Web “Classiche”, sono solo alcuni esempi di cosa oggi contenga il Web. La dimensione partecipativa del cosiddetto Web 2.0 rende questo fenomeno ancora più complesso, amplificando la possibilità di relazione fra persone attraverso la proiezione online delle relazioni sociali ed economiche. Lo stile del Web 2.0 si deve valutare non solo in
base ai contenuti linguistici ma anche in base agli ‘oggetti’, disegni, immagini, loghi che vengono affiancati ai testi e che vengono ‘offerti’ al visitatore delle pagine web (insieme a musica, video, testi, foto, consigli, test, disegni ecc.). L’aumento del grado di interattività, condivisione e partecipazione degli utenti nella creazione di contenuti fa aumentare il grado di consapevolezza della socialità della rete e del ruolo attivo di chi si trova on-line. Il web, in sostanza, sta funzionando come una lente di ingrandimento che mette in evidenza qualcosa che peraltro è sempre esistito: la differenza di registro tra un uso formale della lingua e il linguaggio utilizzato per conversare, ovviamente tutto ciò viene trasferito nella scrittura, un ambito in cui siamo meno propensi a incontrare e accettare registri informali. In conclusione, con il web fenomeni abbastanza comuni, e che manifestano la varietà funzionale delle lingue, si sono improvvisamente rovesciati sotto gli occhi di tutti noi con un’abbondanza di dati e una persistenza finora mai registrate e che ci appaiono innaturali (infatti questo genere di interazioni perlopiù restava relegata ad un uso orale).
1.3 Obbiettivo della tesi
L'obbiettivo di questa tesi è di progettare un sistema che riconosca eventuali errori grammaticali, senza nessun tipo di analisi logica o grammaticale, ma col solo uso dei servizi che il web mette a disposizione. A tale scopo, il sistema sarà sviluppato da un'architettura modulare, dove ogni modulo svolgerà la propria funzione al fine di realizzare una soluzione di facile parametrizzazione e riutilizzo. Ciò che si vuole ottenere sarà una rappresentazione di una frase da validare, per mezzo di una semplice visualizzazione di una parola o un insieme di parole che il sistema considererà errate. Il primo passo sarà quello di suddividere la frase in elementi, costituiti dai termini di cui è composta, tenendo conto anche della presenza di nomi propri e/o numeri. Si presuppone che ogni parola sia scritta correttamente e che le frasi terminino con un segno di interpunzione forte. I vari elementi ottenuti vengono poi raggruppati in sequenze parzialmente sovrapposte, attraverso un processo di partizionamento. Segue poi un processo di sostituzione, che ha il compito sostituire termini particolari con espressioni equivalenti: è il caso, ad esempio, dei numeri, dei nomi propri e degli incisi. Fatto ciò, si esegue una ricerca nel Web per ciascuna partizione prodotta. La modalità di base per farlo consiste nell’uso di un motore di ricerca nel quale si sfrutterà il numero di occorrenze restituite per ogni n-gramma. Nel sistema che si andrà a creare, tendenzialmente, si andranno a comparare il numero di occorrenze ottenute in diversi livelli di n-grammi (per esempio i quadrigrammi con i trigrammi). Oltre all'utilizzo del numero di occorrenze, si procedere con l'analisi degli snippet, ossia brevi estratti dai documenti contenuti nelle pagine dei risultati. Il sistema, attraverso l'utilizzo dei risultati dall'analisi del
numero di occorrenze e dell'elaborazione degli snippet, valuterà gli n-grammi presi in considerazione. Successivamente, attraverso un algoritmo di clustering, si cercheranno quelli errati. In seguito con un approccio bottom-up, si andrà a verificare quali bigrammi conducono a risultati errati, come se si scorressero i nodi di un albero, anche se non si arriverà sino alle foglie, ovvero gli ungrammi, dato che non è presente nessun legame tra parole adiacenti. Dopo aver trovato i bigrammi errati, si cercherà attraverso un sistema di rimpiazzo di correggere gli eventuali errori, e spetterà all'utente a considerare la compiutezza fra le alternative proposte.
1.4 Specifica dei requisiti
Di seguito si è stilato l'elenco dei requisiti a cui il sistema si dovrà appoggiare e i quali, più avanti, verranno visti più in dettaglio e successivamente sviluppati:
1. Il sistema faccia uso del web e dei servizi che mette a disposizione. 2. Il sistema deve essere strutturato in modo che:
a) identifichi la presenza di virgole e inciso all'interno della frase. b) suddivida la frase in segmenti per una elaborazione più adeguata. c) riconosca la presenza di nomi
d) riconosca la presenza di numeri
3. Il sistema deve avere un approccio emergente, quindi:
a) non deve fare affidamento a nessuna grammatica e quindi non utilizzare nessun tipo di strumento di analisi lessico-grammaticale.
b) non deve mantenere nessun tipo di informazione da interrogazioni precedenti.
4. Il sistema analizza un periodo per volta. 5. Si usa il linguaggio di programmazione Java. Si fanno inoltre i seguenti presupposti:
1. Ogni frase deve terminare con simboli di interpunzione forti (punto, punto di domanda, ecc.).
2. All'interno della frase sono ammesse solo le virgole.
3. Ogni parola della frase è considerata corretta dal punto di vista ortografico. 4. Vista la non classificazione dei termini ogni parola e considerata alla stregua
delle altre.
Il requisito “1” specifica che nel verificare la correttezza della frase si dovranno utilizzare gli strumenti presenti nel web, ma come è specificato nel requisito “3” non si potranno utilizzare servizi che qualifichino in qualche modo ogni singola parola. Per questo si valuterà solo dell'uso che se ne fa all'interno dei documenti presenti nel Web, dato che quest'ultimo contiene un'immensa quantità di documenti scritti. Oltre ad avere il vantaggio di come le parole vengono utilizzate e si legano tra di loro, abbiamo anche quello di avere un sistema che si adegua al mutare all'uso di determinati termini vecchi o nuovi che siano. Un'analisi di questo tipo possiamo averla grazie all'uso di uno dei motori di ricerca più usati al mondo, cioè Google. L'utilizzo di ulteriori motori di ricerca è superfluo dato che i risultati che si ottengono da un motore ricerca è simile ad un altro; sia nel numero di occorrenze che nelle pagine visualizzate.
Detto questo andiamo ad analizzare cosa deve fare il sistema quando riceve una frase da analizzare come è descritto nel punto “2”. Prima di tutto identifica la posizione delle virgole in modo da suddividere in segmenti la frase, per esempio analizzando
la frase: “Ascoltava sua mamma che cantava una canzone, e scriveva una poesia.” la frase verrà suddivisa in due segmenti:
• Ascoltava sua mamma che cantava una canzone • e scriveva una poesia
Ogni periodo verrà gestito uno indipendentemente dall'altro, mentre per la gestione dell'inciso, avremo una suddivisione in tre periodi con fusione del primo e del terzo periodo, per esempio analizzando la frase: “I ragazzi, che hanno giocato a carte, hanno
vinto tremila euro.”, quindi otterremo due segmenti: • I ragazzi hanno vinto tremila euro
• che hanno giocato a carte
Oltre a suddividere la frase adeguatamente, come accennato nel punto “2.c”, dovremo verificare la presenza di numeri e nomi in modo di fare una ricerca generalizzata, perché il periodo “Alberto ha giocato a carte” possa essere trattato in ugual maniera rispetto alla proposizione “Davide ha giocato a carte”; stesso discorso va fatto con i numeri rappresentati con le cifre. Ci si prefigge un approccio di tipo emergente, come specificato dal requisito “3”, ciò implica, in primo luogo che il sistema non debba fare affidamento su alcuna grammatica precodificata, come richiesto al punto “3a”. Pertanto, non verrà fatto alcun tipo di controllo inerente al rispetto delle regole grammaticali o di un opportuno modello del linguaggio, né prima, né dopo l’interrogazione del motore di ricerca. In altre parole, non ci si basa su alcuna regola preesistente, ma si tiene conto esclusivamente dei risultati forniti dal motore di ricerca. In questo modo, ci si assicura di seguire un paradigma emergente, in maniera poi da potersi avvalere di un diverso approccio. Il punto “3b”, specifica
che il controllore deve essere stateless, ossia senza memoria tra un’esecuzione e l’altra. Le informazioni raccolte per una frase, non devono essere riutilizzate per quella successiva, per la quale invece si deve ripartire da un punto privo di qualsiasi conoscenza. Per questo motivo si può parlare di algoritmo basato su un’evoluzione, in quanto il sistema acquisisce nuove conoscenze nell’arco di una singola esecuzione, ma non di apprendimento, dato che tali conoscenze vengono perse al termine dell’analisi di una frase. È anche rispettando questo requisito che si opta la scelta di un paradigma emergente a scapito di quello cognitivista: collezionando informazioni sulle ricerche già effettuate, si fornirebbe infatti, per le esecuzioni successive, un grado di conoscenza non nullo al sistema, ciò che invece ci si prefigge è che il sistema sia incorporato nel Web, mantenendo un’essenza agnostica. Quanto finora affermato ci conduce al punto “4” che è strettamente collegato ai punti precedentemente analizzati, in cui viene precisato che si analizza un periodo per volta e quindi l'elaborazione di una frase non deve influenzare l'altra.
1.5 Glossario
1. Termine (parola): è la più piccola parte in cui è divisibile una frase. 2. N-gramma: è una sequenza di n termini.
3. Segmento: nell’ambito di questa tesi, è ciascuna delle porzioni in cui la frase da analizzare è suddivisa dalle virgole, non necessariamente di senso compiuto.
4. Livello di n-gramma: prende in considerazione tutti gli n-grammi composti dalla stessa quantità di termini, in cui è suddivisa una frase o un segmento.
5. Inciso: è una proposizione (detta “incidentale”) o un sintagma che si colloca all’interno di un’altra proposizione; di solito è racchiuso tra virgole, parentesi o
lineette.
6. Occorrenze: numero di risultati restituiti da un motore di ricerca coincidenti esattamente con la sequenza di termini contenuta nella stringa di ricerca.
7. Snippet: porzione di un documento web visualizzata dai motori di ricerca, contenente una breve descrizione (che include le parole richieste) e un collegamento al documento stesso.
8. Albero: rappresentazione di una frase e dei legami sintattici in essa contenuti attraverso la radice (un termine) sino ad arrivare alle possibili radici (n-grammi). 9. Web Scraping: metodo di trattamento di un documento HTML come un file di testo, in cui vengono estrapolati dati utili per una successiva elaborazione.
1.6 Organizzazione della tesi
Nel capitolo 2 saranno trattati aspetti teorici e pratici che verranno utilizzati per la creazione dell'algoritmo di elaborazione e i suoi moduli. In particolare, si intende fornire al lettore, sia pure senza pretesa di esaustività, una panoramica sugli strumenti utilizzati che porteranno il sistema al suo risultato finale. Successivamente, nel capitolo 3, verrà spiegato dall'algoritmo di valutazione al funzionamento di ogni singolo modulo e il risultato che ognuno di loro apporta al sistema. Nel capitolo 4 saranno trattati in modo più approfondito tutti i moduli in merito alla programmazione. Nel capitolo 5 si presenteranno i risultati ottenuti, cercando di motivare per ogni singola frase, il comportamento del sistema. Infine, nel capitolo 6 si esporranno i risultati esposti ottenuti per tracciare le conclusioni e le possibili linee di ricerca future.
2 Metodi e tecniche per la creazione del sistema
In questo capitolo saranno descritte le tecniche e i metodi utilizzati per lo sviluppo di questa tesi, partendo dalla creazione di una stringa di ricerca all'interno di Google, per arrivare a come estrarre informazioni e dati nei testi, e infine giungere ad una loro elaborazione.
2.1 Tecniche di ricerca in Google
Tra i principali e più diffusi motori di ricerca che rendono rintracciabili i siti e i loro contenuti, troviamo Google. La sua caratteristica è quella di selezionare i risultati di ricerca valutando l’importanza di ogni pagina web con metodi matematici, in base ad un’elaborazione molto veloce che utilizza 500 milioni di variabili e 2 miliardi di termini. Questa tecnologia, chiamata Pagerank, controlla non solo il contenuto della pagina web, ma verifica anche altri eventuali siti che hanno un link verso quella pagina: in base alla quantità ed al tipo di link, la pagina riceve una valutazione in base alla quale occupa un relativo posto nella classifica del risultato ottenuto, questo rende possibile che le prime pagine di ogni ricerca siano quelle più rilevanti. Per ogni singola ricerca, affiancate alle parole che stiamo cercando, si possono inserire caratteri speciali o sostitutivi che rendono possibile una ricerca più accurata. Di seguito quelle principali:
• Gli operatori booleani AND (&) e OR (|): il primo per includere in ogni singolo risultato tutte le parole presenti nella stringa di ricerca mentre il secondo è sufficiente che ne sia presente solo una (Es. dog AND cat, dog & cat)
• L'operatore di negazione (-): il quale serve a escludere un certo termine dalla ricerca (Es. dog -cat)
• Serie di parole racchiuse tra doppi apici: ponendo una serie di termini tra doppi apici, otterremo come risultato l'insieme delle pagine in cui sono presenti tutte le parole che fanno parte della stringa di ricerca, le quali siano anche posizionate allo stesso modo (Es. “The dog is in my house”)
• Generalizzazione di un intervallo di numeri: nel caso si volesse generalizzare la ricerca dei numeri all'interno di un stringa di ricerca, si può scrivere “1..” al posto del numero, facendo così si prenderanno in considerazione tutti i numeri da 1 all'infinito, mentre scrivendo 2..6 consideriamo nella ricerca tutti i numeri compresi tra 2 a 6.
• Generalizzazione di parola o di una serie di parole: sostituendo un termine all'interno della stringa di ricerca in modo che sia attaccato alla parola adiacente, si otterrà la generalizzazione del termine che è stato sostituito. Un asterisco costituisce la generalizzare di una singola parola, due asterischi ne generalizzeranno due e così via. Per esempio, se scriviamo “The* is in my house”, ci troverà tutti i documenti in cui tra “The” e “is in my house” sia presente una generica parola.
2.2 Cenni sul Data Mining
Il Web è un enorme deposito di informazioni, contenute in tanti documenti di forma differente. Quando vi è la possibilità di accedere ad informazioni, strutturate o non, le casistiche di studio divengono innumerevoli così come le relazioni osservabili, mentre la quantità di dati, essendo continuamente aggiornata, risulta difficilmente numerabile. Il problema principale del Data Mining è rappresentato da un potenziale rischio: ovvero che una tale abbondanza di dati non consenta in realtà l’estrazione dell’informazione utile. Viceversa, la statistica viene tradizionalmente considerata un’analisi primaria (sperimentale) dei dati raccolti per verificare ipotesi specifiche, consentendo a quest'ultima di essere classificata come un’analisi (confermativa) condotta dall’alto, ovvero una verifica o valutazione d’ipotesi; il Data Mining invece è considerato generalmente come un tipo di analisi secondaria (osservazionale) dei dati raccolti per altre ragioni. Per quanto detto poc'anzi, il Data Mining viene classificato come analisi (esplorativa) condotta dal basso, un processo di generazione d’ipotesi e di conoscenze, che lo rende un processo complesso d’identificazione dei dati di tendenza, strutture, modelli o trend validi, potenzialmente utili ed infine comprensibili che consentano all’utente di prendere decisioni cruciali.
In prima analisi, l'approccio al problema esige una risposta alle seguenti domande: • Cosa si sta cercando?
• Quali tipi di relazioni si intende trovare?
• La soluzione che si sta cercando è in linea con i reali obiettivi?
• Si desidera costruire un modello per scopi previsionali oppure si è interessati ad indagare su andamenti e associazioni?
• Quale tipo di relazione esiste tra i dati che si vogliono elaborare? • Che relazione c'è tra diversi tipi di dati?
• In che forma sono disponibili i dati?
Dopo aver risposto a queste domande, ed in seguito all'avvenuta raccolta dei dati, va affrontato il problema della preparazione degli stessi, ovvero, si dovrà andare a cercare una correlazione fra di essi. Quanto detto, implica la determinazione di quelle porzioni di dati che risultano più appropriate per gli scopi dell’analisi. In seguito alla preparazioni dei dati, ci si potrebbe rendere conto che le fluttuazioni numeriche sono troppo alte, in tal caso sarà opportuno ricorrere alla tecnica della normalizzazione, al fine di evitare che le misure basate su distanze rendano il risultato finale troppo sbilanciato; tale scopo può essere raggiunto mediante funzioni apposite che riducano quei valori troppo alti in modo da rendere più fruibile l'utilizzo dei dati stessi. Esistono vari tipi di normalizzazione che implicano diversi processi che prevedono differenti modalità di calcolo, che vanno da quello che consiste nel dividere tutti i dati per il valore massimo a quello che prevede l'utilizzo della scala logaritmica per giungere, infine, all'utilizzo di specifiche funzioni chiamate sigmoidi; alla famiglia di tali funzioni, sono riconducibili la gaussiana, l'arcotangente, la tangente iperbolica e la funzione logistica. Le funzioni sigmoidi impiegate per la normalizzazione dei dati vantano alcune proprietà positive, fra le quali possiamo enumerare il fatto che la forma della curva sta a indicare che, indipendentemente dai valori di ingresso, il valore di uscita è necessariamente contenuto entro certi limiti ben noti (-1 e 1 per la tangente iperbolica e l'arcotangente, da 0 a 1 per la logistica). Per valori di input piccoli, l'inclinazione della curva è praticamente costante e assume valori di output bassi. Man mano che il valore degli input si avvicinano alla soglia i valori di output iniziano a crescere sino a raggiungere il livello massimo.
Giunti a questo punto, i dati sono pronti per essere elaborati ed occorre dunque costruire un modello che ci permetta di applicare ad essi uno specifico algoritmo al fine di estrapolarne le tendenze, le quali potranno essere dedotte attraverso l'ausilio di un processo di validazione con l'utilizzo di determinati dati campione che
serviranno a testare la bontà del modello, dalla cui risposta dipenderanno le modifiche da effettuare al fine di ottenere il risultato sperato.
2.3 Cenni sul Text Mining
Con il Text Mining si possono applicare tecniche di raffinamento su testo non strutturato, che è quello che il nostro sistema si prefigge. Nel nostro caso abbiamo operazioni che possono essere effettuate sia sulla frase di partenza che nelle pagine ottenute nelle varie ricerche.
Di seguito vengono illustrate alcune operazioni possibili :
• Tokenization: E' uno dei primissimi passi di qualsiasi processo di analisi del linguaggio: divide il testo sorgente in unità chiamate token di cui ciascuna è una parola o qualcos'altro (tipo un numero,un segno di punteggiatura, una data, ecc.). Il trattamento della punteggiatura può variare a seconda che si voglia o meno mantenere l'informazione relativa: la scelta più frequente prevede di conservare i confini di frase (i punti), e non la struttura interna (le virgole). In inglese il confine di token è rappresentato dal whitespace (spazio, tabulazione, inizio di riga), ma tale informazione non è sempre disponibile né sufficiente: si pensi alle forme apostrofate, all'hyphenation (as es.: 'coperate' è una parola, ma '26-year-old' no), alle abbreviazioni (in cui il punto non è token a sé stante), ai casi in cui lo spazio non rappresenta confine di parola (as es.: 'New York'). Si tenga presente che l'Inglese per giunta è una delle lingue che pone meno problemi in quanto, a differenza delle maggiori lingue asiatiche le quali non inseriscono spazi fra parole, e alcune lingue europee che fanno
ampio uso della composizione generando stringhe uniche che corrispondono a più parole, non presenta questo tipo di problematiche.
• Stemming: Processo che estrae la radice di una parola, rimuovendo affissi e desinenze (ad es. 'inhibits', 'inhibition', 'inibited' hanno la radice comune 'inhibit-'). Spesso l'operazione di stemming si limita a troncare la parola mediante un'analisi morfologica semplificata che non è sempre corretta (ad es.: 'ridendo', 'ridere', 'rideva' sono ricondotte correttamente a 'ride-' ma anche 'risate', 'riso' e 'risaia' possono essere ricondotte erroneamente a 'ris-').
• Finding Collactions: Una collocation è un'espressione, dotata di significato, che consiste di due o più parole e corrisponde a una qualche uso idiomatico (ad es.: ìmettere in moto', 'da cima a fondo').
• N-grams: Un n-gram è una sequenza generica di n parole. Gli n-gram più frequentati sono quelli in cui n varia da 2 a 4: rispettivamente bigramma, trigramma, quadrigramma. La differenza rispetto alle collocation è che gli n-gram non necessariamente corrispondono a un uso idiomatico: spesso infatti rappresentano costruzioni sintattiche comuni come, ad esempio, <preposizione + articolo>, Non sono cioè, necessariamente portatori di informazione semantica.
• Name Recognition: identifica tutti i nomi propri di persona o luogo o organizzazione, tutte le date e le somme di denaro. Il processo dipende debolmente dal dominio e si basa su elementi ortografici (uso delle maiuscole o di simboli e numeri).
2.4 Cenni sul clustering
Il clustering è una tecnica che si può applicare per qualsiasi problema di Data mining ed è un processo che, dato un certo numero di elementi, li raggruppa in insiemi, detti anche cluster. Il criterio è di raggruppare entità che siano simili tra loro più di quanto siano simili a entità di altri gruppi, ovvero, in termini statistici, ottenere classi minimizzando la variabilità interna e massimizzando la variabilità rispetto agli altri gruppi. Questa procedura richiede una serie di decisioni di riferimento le quali vanno dalle variabili di classificazione alla misura di prossimità tra le unità, dalla tecnica di raggruppamento delle entità al numero di gruppi entro il quale ripartire le entità e infine anche all'eventuale integrazione di altri metodi di analisi. Le tecniche possono essere fondamentalmente di analisi gerarchica e analisi non gerarchica: le prime individuano gruppi gerarchizzabili, le seconde no. Le tecniche di analisi non gerarchica (quelle che interessano a noi) si distinguono in base al tipo di classi generate: classi mutuamente esclusive (partizioni) o classi sovrapposte; per applicare questo tipo di analisi si deve stabilire in partenza il numero di cluster da generare, o impostare l'analisi in modo da ottenere soluzioni che prevedono un numero variabile di cluster. Spesso viene adottato il K-means, che riduce i costi computazionali ma offre prestazioni peggiori rispetto ad altri algoritmi, ma per il nostro caso sarà più che sufficiente.
2.5 Le espressioni regolari
Le espressioni regolari rappresentano uno strumento molto potente per lavorare sulle stringhe. Possono essere utilizzate, sia per convalidare i dati, sia per effettuare
ricerche all’interno di un testo. La sintassi di questo pseudo-linguaggio è molto flessibile e consente di creare espressioni in base alle proprie esigenze. Nel linguaggio di programmazione Java, che sarà quello usato per lo sviluppo di questa tesi, è stato introdotto il package java.util.regex composto dalle classi Pattern e Matcher che permettono di validare una stringa, o ricercare un testo al suo interno, a partire da un’espressione regolare. Per definire un’espressione regolare è necessario conoscere alcune regole base:
• (…) → le parentesi tonde identificano dei gruppi di caratteri
• […] → le parentesi quadre identificano intervalli e classi di caratteri
• + → indica una o più occorrenze
• ^ → identifica l'inizio di una riga; inoltre all'inizio di un gruppo nega il gruppo stesso
3 Progettazione
3.1 Descrizione del sistema
Il sistema deve lavorare in modo da trovare uno o più errori all'interno degli n-grammi presi in considerazione. Per fare ciò si è deciso di fare una comparazione di n-grammi di differente livello a una data sovrapposizione. Come è normale che sia se abbiamo il numero di occorrenze di un certo n-gramma, un livello di n-grammi di minore dimensioni avrà un numero di occorrenze minore; e in questo si è deciso di puntare sullo sviluppo della validazione di una frase. Per fare ciò si è deciso di puntare su due differenti confronti, il primo compara la distanza tra n-grammi di differente livello, il secondo sulla proporzione di riduzione complessiva tra un livello di n-grammi e un altro.
Si è scelto di suddividere il sistema in tre parti: • pre-elaborazione
• elaborazione • post-elaborazione
Nella fase pre-elaborazione saranno verificate la presenza di nomi e numeri, con dovuta sostituzione per la generalizzazione della ricerca, successivamente si andrà a creare la struttura dati che si baserà sull'effettiva composizione della frase, la quale sarà suddivisa prima in segmenti e poi in n-grammi a seconda della configurazione desiderata (dimensione n-grammi e sovrapposizione). Una volta ottenuta la struttura della nostra frase da 'elaborare' ne verrà creata un'altra di un livello
inferiore, che chiameremo 'campione'.
Una volta ottenute entrambe le strutture, si passa alla fase di elaborazione nella quale verranno effettuati i calcoli (singolarmente, per ogni segmento della frase) che comprendono le due comparazioni infine, per rendere omogenei i risultati, si è optato di normalizzare i dati, in modo da rendere più pratica la clusterizzazione, al fine di rendere i risultati ottenuti compresi tra 0 e 1. Ottenuti i risultati si esegue l'analisi degli snippet, utilizzando la stringa di ricerca in cui siano presenti tutti gli ngrammi e si controllerà la presenza di ogni singolo ngramma in ogni pagina di ricerca ottenuta, della quale si calcolerà la loro percentuale di frequenza. Fatto ciò, da quella percentuale verranno aumentati i risultati ottenuti in precedenza. Una volta ottenuto il risultato finale per ogni ngramma, attraverso l'algoritmo di clusterizzazione si individueranno gli ngrammi errati e quelli corretti. Con gli ngrammi errati si scenderà di livello, come per interrogare una struttura ad albero, scomponendo l'ngramma nei suoi sottogrammi; ottenendo due 'n-1'grammi per volta, i quali verranno comparati sino ad arrivare ai bigrammi, scartando quello con valore più alto, e tenendo quello con valore più basso.
Figura 1 - Sopra: 'struttura di elaborazione' (quadrigrammi). Sotto: 'struttura campione' (trigrammi).
Dopo la fase di elaborazione si passa a quella di post-elaborazione, nella quale si cercherà di correggere l'errore, generalizzando i termini errati all'interno di una porzione del segmento. Dato che le parole che risultano errate sono due, prima si fa la ricerca con una e poi con l'altra. Quest'operazione consisterà nel trovare le parole più frequenti all'interno degli snippet con l'utilizzo di una determinata stringa di ricerca, che vadano a sostituire la parola errata. La parole così ottenute andranno mostrate all'utente; successivamente sarà l'utente stesso a riscontrare tra le parole proposte quella corretta.
3.1.1 Creazione degli n-grammi e gestione dell'inciso
Per procedere alla creazione degli n-grammi, innanzitutto bisogna prelevare, dai parametri, il numero di termini che compongono ogni n-gramma e il numero di termini che si sovrappongono tra n-grammi adiacenti. Dopo aver eliminato dalla frase il punto di interpunzione forte, va controllata la presenza e il numero di eventuali virgole poiché, come succede spesso in presenza di una virgola, si può generare una diversa interpretazione del periodo, e creare un'unica proposizione può portare a un'errore sintattico. Prendendo come esempio le due frasi qua sotto, la presenza o l'assenza della virgola fa cambiare completamente l'interpretazione della frase, nella prima si intende che il modo in cui ha studiato Marcello non è come ci si aspettava, però si intende che in un modo o nell'altro Marcello ha studiato. Invece nella seconda si precisa che Marcello non ha studiando e che tutti se lo aspettavano.
• Marcello non ha studiato come tutti ci aspettavamo. • Marcello non ha studiato, come tutti ci aspettavamo.
Quindi nella prima frase si avrà un unico segmento e si avrà un'unica analisi, invece nella seconda si suddivide un due segmenti e si faranno due analisi separate.
• Marcello non ha studiato • come tutti ci aspettavamo
La situazione è ancora differente se c'è la presenza di due virgole, dato che siamo in presenza di un inciso. Come si potrebbe presupporre dall'esempio precedente, la presenza di due virgole dovrebbe portare alla creazione di tre segmenti. Dal punto di vista linguistico l'inciso è una frase inserita all’interno di un’altra frase con cui non forma una struttura sintattica, questo invece non avviene tra il primo e il blocco dopo
l'inciso, dove tra i due c'è un legame sintattico.
• Il mio migliore amico, che è un grande tennista, ha vinto molti tornei.
Nella frase qui sopra separando l'inciso dal resto della frase, e formando due segmenti diventerà:
• Il mio migliore amico ha vinto molti tornei • che è un grande tennista
Dopo aver creato i segmenti si effettuerà la suddivisione di ognuno di loro i n-grammi (struttura da elaborare). Ricordando che per l'analisi si utilizzerà anche il livello di grammi diminuito di uno (struttura campione), si potrà avere che un n-gramma potrà avere minimo due termini e massimo tutti i termini che compongono il segmento. Se andassimo a considerare la suddivisione con dimensione minima, cioè due termini, avremo che la struttura campione sarà composta dai monogrammi; un'elaborazione del genere, però, non è plausibile dato che nei monogrammi non c'è legame tra termini adiacenti. Invece se andassimo a considerare dimensioni di ngrammi troppo alti, rischieremo di avere un numero di occorrenze molto basse o pressoché nulle, le quali vanificherebbero una qualsiasi elaborazione restituendo tutti i termini dei vari segmenti errati. Quindi, come accennato sul paragrafo del Text Mining sulla suddivisione in n-grammi, sono quelli composti da 2 a 4 termini che sono più usati e danno una sufficiente informazione sintattica. Dato che si è escluso di usare i bigrammi, per la suddivisione in ngrammi si andranno a considerare i trigrammi e i quadrigrammi.
Per quanto riguarda la sovrapposizione, nella configurazione proposta di suddivisione in ngrammi, si può optare da uno a tre termini di sovrapposizione. Più
è alto il numero di termini di sovrapposizione più quadrigrammi verranno creati. Quindi se si avesse la sovrapposizione di un termine, nell'eventualità di un errore verrà identificato in un quadrigramma, invece se i termini di sovrapposizione fossero tre si potrebbero presentare da due a tre quadrigrammi; il tutto dovrebbe funzionare come una lente d'ingrandimento. In seguito a tali considerazioni si è optato per una sovrapposizione media; cioè di due termini.
3.2 Progettazione dell'algoritmo di elaborazione
Come specificato nel capitolo precedente, l'algoritmo prende due livelli di n-grammi, in cui ogni livello si differenzia di un termine rispetto all'altro. Prendendo ad esempio la seguente frase:
You can get us all at the same time this way
e prendendo in considerazione i quadrigrammi (struttura da elaborare) con due termini sovrapposti, verranno accoppiati con i trigrammi (struttura campione) con un termine sovrapposto, otterremo le seguenti suddivisioni:
4 termini;2 di sovrapposizione 3 termini; 1 di sovrapposizione
You can get us You can get
get us all at get us all
all at the same all at the
the same time this the same time same time this way time this way
Come si può notare l'ultimo elemento dei quadrigrammi ha tre termini di sovrapposizione rispetto al precedente; questa rappresenta una forzatura dato che a noi interessa che il trigramma accoppiato differisca di un termine. Una volta ottenuti gli
n-grammi voluti, si estrae il numero di occorrenze per ognuno di loro dalle pagine di ricerca.
Frase corretta
4 termini;2 di sovrapposizione 3 termini; 1 di sovrapposizione You can get us:1.16E7 You can get:5.89E8 get us all at:203000.0 get us all:615000.0 all at the same:7.19E7 all at the:7.48E7 the same time this:7.69E7 the same time:4.66E8 same time this way:3.67E7 time this way:6.03E7
Invece nella tabella seguente abbiamo la stessa frase, con la differenza che è stato inserito un errore, 'these' al posto di 'this'.
Frase errata
4 termini;2 di sovrapposizione 3 termini; 1 di sovrapposizione You can get us:1.16E7 You can get:5.89E8 get us all at:203000.0 get us all:615000.0 all at the same:7.19E7 all at the:7.48E7 the same time these:1.55E7 the same time:4.66E8
same time these way:9 time these way:1820000
Come si può notare la proporzionalità tra gli n-grammi nella frase corretta è più stretta, usando una scala logaritmica in base dieci e facendo la differenza tra i valori della frase campione con quella da elaborare, ci si rende di più conto della differenza. E questi saranno i risultati ottenuti:
Frase corretta Frase errata
You can get us:1.70 You can get us:1.70 get us all at:0.48 get us all at:0.48 all at the same:0.01 all at the same:0.01 the same time this:0.78 the same time these:1.4 same time this way:0.21 same time these way:5.26
molto alto rispetto agli altri, si è notato che quando l'n-gramma è corretto il valore si aggira tra 0 e 2.5, mentre valori più alti identificavano un n-gramma errato. Prendendo come soglia il valore 2.5 si è scelto di utilizzare come funzione di normalizzazione l'arcocotangente dal momento che vogliamo ottenere valori prossimi a uno con numeri che si avvicinano allo zero e valori che tendono a zero quando questi aumentano.
y=π arccot (2 x s)
Dove s è la soglia, tale che se fosse uguale a x la funzione darebbe 0,5. Effettuando la normalizzazione, si otterranno i seguenti risultati.
Frase corretta Frase erratta
You can get us:0.61 You can get us:0.61 get us all at:0.87 get us all at:0.87 all at the same:0.99 all at the same:0.99 the same time this:0.80 the same time these:0.65 same time this way:0.94 same time these way:0.35
Però può succedere che in presenza di un errore, tra quadrigramma e trigramma, si presenti un numero di occorrenze basse, ottenendo così una valore che potrebbe far risultare il quadrigramma corretto (per esempio: 1000 il quadrigramma e 100 il trigramma, ottenendo così il valore del logaritmo pari a 1). Perciò si è deciso di accoppiare il risultato della distanza logaritmica con un una normalizzazione dei rapporti tra le occorrenze tra i quadrigrammi e i trigammi. In questo caso il comportamento dei dati è l'opposto di quello della normalizzazione precedente, dal momento che valori di occorrenze basse corrispondono alla presenza di un possibile quadrigramma errato; al contrario, a valori molto alti di occorrenze corrisponderà la presenza di un quadrigramma corretto. In questo caso si utilizzerà un'altra funzione sigmoide, cioè l'arcotangente.
y=π arctan (2 x
s)
Per la scelta della soglia si è deciso di impostarla come il valore atteso minimo di proporzione che si ha fra gli n-grammi accoppiati. Quindi si calcolano i rapporti per ogni
coppia e si fa la media dei valori ottenuti, e col valore ottenuto si divide il valore minimo degli n-grammi della struttura campione, e questo sarà il valore di soglia della funzione arcotangente.
Utilizzando le due frasi di prova otterremmo i seguenti risultati:
Frase corretta (val. soglia: 231562) Frase errata (val. soglia: 6) You can get us:0.98 You can get us:0.99
get us all at:0.45 get us all at:0.99 all at the same:0.99 all at the same:0.99 the same time this:0.99 the same time these:0.99 same time this way:0.99 same time these way:0.60
Dopo aver ottenuto i valori dalle due normalizzazioni si effettua la media tra le due, ottenendo così il valore finale. Quindi essi si incrementeranno di una percentuale data dai valori ottenuti dal modulo degli snippet e successivamente andranno processati tramite un algoritmo di clustering che separerà i quadrigrammi che risulteranno corretti, da quelli errati. Infine, da quest'ultimi, verrà costruito un albero sino ad arrivare ai bigrammi e scegliere quale sia quello errato.
3.3 Realizzazione dei moduli di supporto
Si è deciso di creare dei moduli in modo da rendere le varie componenti che vanno a creare il sistema il più indipendente possibile. Ogni modulo ha la propria funzione e verrà avviato a seconda dello stato in cui si trova il sistema, ovvero che sia in fase di pre-elaborazione, durante l'elaborazione o in fase di post-elaborazione.
3.3.1 Modulo dei servizi
Nel modulo dei servizi abbiamo funzionalità che sono comuni a tutti gli altri moduli, tra le quali troviamo:
• La funzione che gestisce le accentate per l'utilizzo della lingua italiana.
• La funzione che prende in ingresso un url e restituisce la pagina HTML corrispondente in formato testuale; per un'eventuale elaborazione di Web Scraping.
• Varie funzioni di matching che contano e cercano all'interno di testi determinate stringhe.
• Una funzione che trasforma un vettori di termini in un segmento o frase; aggiungendo tra un termine e l'altro il whitespace.
• Una funzione che cerca il numero di occorrenze da una ricerca effettuata su Google.
3.3.2 Modulo per la gestione dei nomi e numeri
Può capitare che in certe frasi siano presenti nomi, e noi vogliamo che il nostro algoritmo li elabori in modo generale, poiché come accennato nei requisiti, se in una frase è presente un nome, questo deve essere trattato come se ne fosse presente un altro qualsiasi. Si è deciso di trattare come nomi tutte quelle parole che si trovano all'interno della frase e iniziano con la maiuscola, ma che allo stesso tempo sia un
nome proprio di persona. Per fare ciò ci affidiamo a un sito (http://www.behindthename.com) che ci dice se una parola è un nome proprio o no, utilizzando il metodo del Web Scraping. Nel caso venga trovato un nome, ovunque esso sia all'interno della frase, verrà sostituito con il carattere speciale “*”, il quale nel motore di ricerca di Google verrà trattato come una parola qualsiasi, generalizzandone la ricerca. Stesso discorso deve essere fatto con i numeri, ma in questo caso invece di utilizzare un sito, sarà sviluppata una funzione apposita che riconoscerà all'interno della frase qualsiasi numero costituito da cifre, il quale verrà sostituito con la stringa “1..”, in modo da generalizzarlo.
3.3.3 Modulo degli snippet
Il modulo degli snippet fa sempre utilizzo del motore di ricerca di Google, ma con la differenza che va ad elaborare le descrizione di ogni risultato proposto (gli snippet sono quelle poche righe di testo visualizzate sotto ogni risultato di ricerca ). Il modulo si occuperà di cercare di analizzare il numero di pagine richieste dall'utente, e successivamente sempre col Web Scraping, andrà a conteggiare la presenza degli eventuali n-grammi del segmento, presenti nelle varie descrizioni di ogni pagina. Se per esempio si vorrà cercare il risultato ottenuto col quadrigramma “all at the same” in ogni documento si andrà a cercare il numero in cui questa scritta compare in ogni pagina:
<b>all at the same</b>
Il numero di descrizioni per pagina è quasi sempre dieci, quindi il numero totale di casi da considerare sarà:
N° risultato totali=N° pagine*10
Quindi per ogni n-gramma sarà effettuata una media tra i risultati ottenuti e il numero di descrizioni totali; nonché la loro percentuale di frequenza.
3.4 Modulo per il clustering
Il clusterineg verrà effettuato sui valori finali i quali saranno compresi tra zero e uno, dove gli n-grammi che hanno valori vicino allo zero vengono considerati errati, mentre quelli vicini all'uno sono considerati corretti. Quindi si userà un semplice algorimo K-means con due vettori cluster uno che conterrà gli n-grammi corretti e l'altro gli n-grammi errati e come centroidi iniziali si considereranno per il primo, il valore uno e per il secondo lo zero. Per ogni iterazione si calcolerà la distanza dei valori finali dai centroidi e a seconda della distanza minima tra i due centroidi verrà assegnato ad uno o all'altro vettore cluster. Dopo che a tutti i valori saranno assegnati a un vettore cluster, i centroidi verranno ricalcolati con le medie dei valori degli elementi che compongono ogni vettore cluster. L'algoritmo si fermerà quando i
Figura 5: Esempio di ricerca di una parola errata col modulo di rimpiazzo
centroidi da un'iterazione all'altra non cambiano.
3.5 Formattazione del testo e gestione delle lingue
Il motore di ricerca di Google esegue una codifica UTF-8, quindi non vengono identificati i caratteri speciali e dal momento che si è optato per elaborare frasi italiane e inglesi, in entrambe le lingue si andrà a gestire solo il carattere apostrofo, mentre solo per quelle italiane anche tutte le lettere accentate. Questo verrà implementato tramite un servizio, nominato in precedenza, che non appena prima di effettuare un qualsiasi tipo di operazione di Web Scraping eseguirà questa conversione, per esempio l'apostrofo verrà sostituito con il seguente codice: '.
3.6 Modulo per il rimpiazzo
Una possibile gestione della parole che il sistema riconosce errate, può essere ottenuta attraverso l'analisi delle parole stesse, però tale processo potrebbe rivelarsi piuttosto impervio, dal momento che si dovrebbe far uso di tecniche di stemming e non è detto che la creazione di una soluzione simile dia il risultato sperato, quindi si è cercato di ottenere un risultato accettabile utilizzando il sistema “Generalizzazione di parola o di una serie di parole” attraverso una delle tecniche di utilizzo di Google e descritto nel paragrafo 2.1.
Siamo dunque nella fase di post-elaborazione e utilizzeremo sia i bigrammi ottenuti in fase di elaborazione, che i parametri impostati dall'utente per il funzionamento di questo modulo, i quali saranno:
• Numero casi che si vogliono visualizzare
Il numero di termini da utilizzare nella ricerca non deve essere ne troppo basso ne troppo alto, poiché se fossero troppi c'è la possibilità che non si ottenga neanche un risultato; al contrario, se fossero in numero limitato si finirebbe per generalizzare eccessivamente non ottenendo alcun risultato attendibile.
Per l'effettiva stringa di ricerca si è scelto di porre il termine da rimpiazzare al centro della stessa qualora ciò fosse possibile, cosa che non può accadere se la parola da sostituire è posizionata a fine o a inizio segmento.
Prendendo in considerazione la seguente frase: • A year ago I was so different.
Aggiungendo degli errori a inizio, al centro e al termine della frase, in un'eventuale ricerca correttiva con tre termini; si avrebbero i seguenti risultati:
1. A inizio frase → An year ago I was so different. → “*year ago” 2. Al centro della frase → A year ago I were so different. → “I* so” 3. A fine della frase → A year ago I was so differents. → “was so*.”
Una volta effettuata la ricerca, si cercheranno tra gli snippet della pagina di ricerca ottenuta i termini che sostituiscano la parola errata, i quali verranno ordinati in base alla loro frequenza. Il numero di casi da visualizzare saranno quelli che l'utente avrà impostato.
Prendendo in esempio la frase:
• I suspect they're better at these stage than the same time last year
L'errore è in “these” e utilizzando Google si può vedere che nei risultati c'è la presenza della sua versione corretta “this”.
È anche possibile ottenere risultati che non hanno nulla a che fare con il contesto del segmento che andiamo ad analizzare.
3.7 Interfacciamento con l'utente
Per interfacciarsi con l'utente ci sarà un modulo apposito nel quale il programma chiederà l'inserimento della frase da analizzare e tutti i parametri che serviranno alla sua elaborazione, dai quali dovrà estrapolare le informazioni che consentiranno all'utente di stabilire se la frase sia corretta o meno, e nel caso fosse errata, quali bigrammi sono errati e tramite il modulo di rimpiazzo le alternative per ogni parola che fa parte dei bigrammi errati.
Figura 6: Esempio di ricerca di una parola errata col modulo di rimpiazzo
4 Implementazione
4.1 Visione generale
Come specificato nei requisiti, l’implementazione del codice avviene tramite il linguaggio Java, utilizzando l'ambiente di sviluppo integrato multi-linguaggio Eclipse.
Si è scelto di suddividere le classi e quindi creare tre package per rendere più adeguato l'ordine delle classi. Il package 'datapackege' contiene le classi che si occupano di generare la struttura dati, nel package ' modulespackage' troviamo i vari moduli che si occuperanno dell'elaborazione della frase e infine nello 'startpackage' c'è la classe ManagerModule che permette l'avvio del sistema e gestisce l'interfacciamento con l'utente.
4.2 Realizzazione della struttura dati
Per strutturare la frase si è optato per la sviluppo di tre classi, dove vengono rappresentate rispettivamente: frase, segementi e n-grammi. La loro struttura e il legame che c'è tra di loro è rappresentato dal seguente diagramma UML.
Da come si evince dal diagramma, un elemento Phrase può contenere più elementi Segment e a sua volta essa contiene più elementi Ngram. In Segment oltre ad avere elementi di Ngram che rappresentano il segmento stesso, abbiamo anche elementi Ngram che rappresentano i bigrammi che alla fine dell'elaborazione risulteranno errati.
4.2.1 Realizzazione della classe Ngram
Ogni elemento Ngram conterrà al suo interno un vettore (words) delle parole di cui è
composto, una variabile booleana (isCorrect) che servirà ad impostare e riconoscere
se l'n-gramma è corretto o meno. La variabile occurrence che conterrà il numero di
occorrenze dell'n-gramma e le altre variabili serviranno per contenere i dati intermedi e finali durante il processo di elaborazione.
Nel metodo del costruttore, verranno inizializzate alcune variabili, tra cui verrà assegnato all'n-gramma il suo numero di occorrenze.
public class Ngram { String[] words; boolean isCorrect; double occurrence; double norm_threshold_value; double log_distance_value; double snippets; double final_value;
public Ngram (int a, int b, String[] nGram) throws Exception{
snippets=0;
words=new String[nGram.length];
System.arraycopy(nGram , 0, words , 0, nGram.length);
occurrence=ServicesModule.searchNgram(ServicesModule.arrayToText(nGram)); }...
4.2.2 Realizzazione della classe Segement
Come detto precedentemente un elemento Segment contiene sia gli n-grammi (nGrams) che lo compongono, che i bigrammi (wrongBigrams) che risulteranno errati durante l'elaborazione. Oltre a contenere tutte le parole che compongono il segmento, abbiamo il numero di termini che compone ogni n-gramma (weight_ngram)
e quanti termini sovrapposti (overlap) ci sono tra due n-grammi adiacenti.
Nel suo costruttore c'è un ciclo for che creerà un certo numero di n-grammi a seconda della lunghezza del segmento rispettando il numero di sovrapposizione -qualora ciò fosse possibile - in quanto, come detto in precedenza, può avvenire che l'ultimo elemento potrebbe avere più elementi sovrapposti di quelli desiderati.
public class Segment { String[] words;
int overlap; int weight_ngram; Ngram[] nGrams; Ngram[] wrongBigrams;
public Segment (String token, int words_per_ngram, int overlap_pass) throws Exception{
words = token.split(" ");
String[] nGram= new String[words_per_ngram];
overlap=overlap_pass;
if(words.length>3) weight_ngram=words_per_ngram; else weight_ngram=3;
weight_ngram=words_per_ngram;
nGrams=new Ngram[(int) (Math.ceil((double) (words.length-weight_ngram)/ (weight_ngram-overlap))+1)];
int a=0;
int b=weight_ngram-1;
for(int i=0;i<nGrams.length-1;i++){
System.arraycopy(words, a, nGram , 0, words_per_ngram);
nGrams[i]= new Ngram(nGram); a+=(weight_ngram)-overlap; b=a+(weight_ngram-1); }
System.arraycopy(words, words.length-weight_ngram, nGram , 0, words_per_ngram);
nGrams[nGrams.length-1]=new Ngram(words.length-weight_ngram,words.length -1,nGram);
4.2.3 Realizzazione della classe Phrase
Un elemento Phrase conterrà al suo interno uno o più elementi Segment a seconda delle virgole che saranno contenute nella frase di partenza. Come già spiegato precedentemente in presenza di un inciso, la frase non sarà suddivisa in due segmenti e non in tre, e all'interno della variabile aside sarà contenuto il numero di
elemento in cui il primo segmento e il terzo segmento saranno fusi.
Nel costruttore innanzitutto verrà pulita la frase da simbolo di interpunzione forte, dopodiché verranno creati un numero di elementi tanti quante sono le virgole aumentate di uno.
public class Phrase { Segment[] Segments; String[] words; int nSegments; int aside=0;
public Phrase (String token, int words_per_ngram, int overlap_pass) throws Exception{
String[] splittedPhrase;
String[] punctuation={".","?","!"};
for(int i=0;i<punctuation.length;i++) token=token.replace(punctuation[i], "");
nSegments=ServicesModule.countMatching(token, ",")+1;
words=new String[token.split(" ").length];
words=token.split(" ");
splittedPhrase=token.split(","); if(nSegments==3){
//presenza di inciso
nSegments--;
aside=splittedPhrase[0].split(" ").length;//indice ultimo elemento prima dell'inciso
splittedPhrase[0]+=splittedPhrase[2]; }
Segments=new Segment[nSegments]; for(int i=0;i<nSegments;i++){
if(splittedPhrase[i].charAt(0)==' ')
splittedPhrase[i]=splittedPhrase[i].substring(1,
splittedPhrase[i].length()); Segments[i]=new Segment(splittedPhrase[i], words_per_ngram, overlap_pass);
} }...
4.3 Realizzazione del servizio di ricerca delle occorrenze nel motore
di ricerca
La funzione readFileAsStringToHtml, tramite l'utilizzo di un User Agent che prende come ingresso un url, restituirà la pagina HTML la quale verrà successivamente convertita in testo per facilitare le operazioni d Web Scraping.
La funzione searchGoogle prende in ingresso un url, il quale servirà esclusivamente a estrarre in una pagina di ricerca in Google il numero di occorrenze di un determinato n-gramma. Tramite la funzion readFileAsStringToHtml avrò la pagina HTML trasformata in testo e tramite le espressioni regolari andrò a ricavare il numero di occorrenze.
public static double searchGoogle(String url) throws IOException{ String htmlString = ServicesModule.readFileAsStringToHtml(url); String regexpForSpanTag = "About ([^*<]+) results<";
String results=ServicesModule.Matching(htmlString, regexpForSpanTag); if (results==null) {
regexpForSpanTag = ">([^*<]+) results</div"; results=Matching(htmlString, regexpForSpanTag); }
if(results==null || htmlString.contains(">No results found for <") || htmlString.contains(">Showing results for<") || htmlString.contains("did not match any documents. <")) return 0;
double out = new Double (results.replace(",", "")); return out ;
}
public static String readFileAsStringToHtml(String appUrl) throws IOException{
StringBuilder fileData = new StringBuilder(5000); URL url = new URL(appUrl);
URLConnection yc = url.openConnection();
yc.addRequestProperty("User-Agent", "Mozilla/25.0"); yc.connect();
BufferedReader in = new BufferedReader(new InputStreamReader(yc.getInputStream()));
String inputLine;
while ((inputLine = in.readLine()) != null) fileData.append(inputLine);
in.close();
return fileData.toString(); }
Invece la funzione searchNgram costruirà l'url per la ricerca di un qualsiasi n-gramma, e utilizzerà le funzioni precedenti per ottenere il numero di occorrenze.
4.4 Realizzazione del modulo di gestione nomi
Siamo in fase di pre-elaborazione quindi abbiamo la frase ancora non strutturata, infatti la funzione prende solo una stringa in ingresso che corrisponde alla frase completa. La prima cosa che si fa è creare un vettore che contiene ogni parola della frase, dopodiché ci sarà un ciclo for che scansionerà il vettore creato e tramite il sito nominato nel paragrafo 3.2.2 controllerà se quel termine si trova nel database. Dato che si considera solo l'utilizzo della lingua italiana e inglese, oltre al controllo sulla presenza del nome, controllerà se quest'ultimo appartiene a una delle due lingue. Dopo aver verificato che sia un nome, la parola viene sostituita, all'interno della frase, con il carattere di generalizzazione asterisco; infine la funzione restituirà la frase generalizzata.
public static String replaceName(String token) throws IOException{ String word;
String[] words=token.split(" "); String result;
for (int i = 0;i<words.length;i++){
if(words[i].charAt(0)==ServicesModule.returnWord(token, i).toUpperCase().charAt(0)){
word=ServicesModule.returnWord(token, i);
String url = "http://www.behindthename.com/name/" + word; String htmlString = ServicesModule.readFileAsStringToHtml(url); if(!htmlString.contains("was not
found")&&(htmlString.contains("Italian")|| htmlString.contains("English"))) token=token.replace(ServicesModule.returnWord(token, i), "*");
}
} return token; }
public static double searchNgram(String token) throws Exception{ String rawToken=token;
token=token.replace(" ", "+");
String url = "http://www.google.com/search?hl=en&q=\"" + token + "\"&meta=&gws_rd=ssl";
return searchGoogle(url); }
4.5 Realizzazione del modulo di gestione numeri
In questo modulo avverrà la gestione dei numeri all'interno della frase. Come per il modulo di gestione dei nomi, viene creato un vettore i cui elementi sono le singole parole. Attraverso un ciclo for verrà verificato, tramite l'uso di un'espressione regolare, se quella parola è un numero. Se la verifica va a buon fine il numero viene sostituito con la stringa di generalizzazione dei numeri “1..”. Dopo effettuata la sostituzione di tutti i numeri la funzione restituirà la frase generalizzata.
4.6 Realizzazione del Modulo della normalizzazione dei rapporti
In questo modulo si calcolerà la proporzione che c'è tra due livelli di n-grammi, infatti la funzione prenderà in ingresso il segmento da elaborare e il segmento campione. Prima di tutto si cerca il minimo (min) tra le occorrenze del segmento campione, attraverso il primo ciclo for. Successivamente, nel secondo ciclo for verranno calcolati la somma dei rapporti (modifier) tra gli ngrammi campione e quelli da elaborare. Fatto ciò si calcola la media dei rapporti, dividendo il numero ottenuto col numero di n-grammi di cui è composto il segmento. Ora col valore ottenuto dividiamo il valore minimo degni n-grammi campione, ottenuto in precedenza, con il valore della variabile modifier e così otterremo il valore della
public static String checkNumbers (String token){
String[] words=token.split(" "); String result;
for(int i=0; i<words.length;i++)
if (words[i].matches("\\d+")) words[i]="1.."; result=ServicesModule.arrayToText(words); return result;
soglia per la normalizzazione dei valori di occorrenze degli n-grammi da elaborare. E infine le occorrenze degli n-grammi da elaborare saranno normalizzati con la funzione arcotangente.
4.7 Realizzazione del Modulo delle distanze logaritmiche
In questo modulo come in quello precedente si dovranno comparare il numero di occorrenze tra n-grammi di livelli differenti, e anche qui abbiamo in ingresso il segmento da elaborare e quello campione, con la differenza che la soglia e fissa, e quindi si calcola direttamente i logaritmo del rapporto tra i due n-grammi, normalizzandolo con la funzione arcocotangente. Nella funzione del rapporto tra occorrenze nel logaritmo si è aggiunto 0.00316 al numeratore e 1 al denominatore sia per evitare domini inesistenti, ma soprattutto per forzare di ottenere -2.5, il quale col valore assoluto diventa 2.5, quando in entrambe le strutture abbiamo 0 numero di
public static void NormThreshold(Segment sgmnt, Segment sgmnt_sample){ double x;
double norm_value;
double min=sgmnt_sample.return_nGram(0).returnOccurrence(); double modifier=0;;
double threshold;
for(int i=1; i<sgmnt_sample.tot_nGrams();i++){
if (sgmnt_sample.return_nGram(i).returnOccurrence()<min && sgmnt_sample.return_nGram(i).returnOccurrence()!=0)
min=sgmnt_sample.return_nGram(i).returnOccurrence(); }
for(int i=0; i<sgmnt.tot_nGrams();i++){
if (sgmnt.return_nGram(i).returnOccurrence()!=0){ modifier+=(sgmnt_sample.return_nGram(i).returnOccurrence()/sgmnt.return_nGra m(i).returnOccurrence()); } } threshold=min/(modifier*sgmnt.tot_nGrams()); for(int i=0;i<sgmnt.tot_nGrams();i++){ x=sgmnt.return_nGram(i).returnOccurrence(); norm_value=(2/Math.PI)*(Math.atan(x/threshold));
sgmnt.return_nGram(i).setNormalizationValue(norm_value); }
occorrenze. È l'unico caso da forzare dato che il logaritmo è negativo tra 0 e 1, ma dato che il numero di occorrenze è un intero non avremo mai valori che si trovano in quell'intervallo.
4.8 Realizzazione del modulo degli snippet
La funzione di questo modulo prende in ingesso il segmento e il numero di pagine in cui si vogliono analizzare gli snippet.
Viene creata una stringa di ricerca composta dalle parole che compongono l'n-gramma, raccolte tra doppi apici, e ognuna di esse separate dall'OR.
Di questa stringa si effettuerà la ricerca del numero massimo di pagine di risultati possibili, e il numero ottenuto verrà confrontato col numero di pagine da analizzare impostate dall'utente. Nel caso il numero di pagine possibili fosse minore di quello inserito dall'utente, verranno analizzate solo il numero di pagine possibili, perché altrimenti analizzerebbe più volte l'ultima pagina di ricerca. Dopo aver ottenuto il numero di pagine da analizzare, verrà scansionata ogni pagina e ne verrà verificata la presenza di ogni n-gramma. Viene effettuato un conteggio, e verrà assegnata il numero percentuale di presenza ad ogni n-gramma.
public static void LogDistances (Segment sgmnt, Segment sgmnt_sample){ double value;
for(int i=0; i<sgmnt.tot_nGrams();i++){
value=Math.abs(((Math.log10((sgmnt_sample.return_nGram(i).returnOccurrence ()+0.00316)/(sgmnt.return_nGram(i).returnOccurrence()+1))))); value=(2/Math.PI)*(Math.PI/2-Math.atan(value/2.5)); sgmnt.return_nGram(i).setLogDistanceValue(value); } }
