ALMA MATER STUDIORUM ` UNIVERSITA DEGLI STUDI DI BOLOGNA ` Seconda Facolta` di FACOLTA DI INGEGNERIA Corso di Laurea in INGEGNERIA DEI SISTEMI E DELLE TECNOLOGIE DELL’INFORMAZIONE CLASSIFICAZIONE DI DOCUMENTI PRE-ELABORATI CON TECNICHE DI STEMMING Elaborata nel corso di: SISTEMI INFORMATIVI DISTRIBUITI Tesi di Laurea di: Relatore: ALESSANDRO PIRELLI Prof. GIANLUCA MORO Co-relatore: Ing ROBERTO PASOLINI ANNO ACCADEMICO 2012-2013 SESSIONE SESSIONE IV Indice 1 Introduzione 1 2 Introduzione al Text Mining 3 2.1 Elaborazione del linguaggio naturale . . . . . . . . . . . . . 3 2.1.1 Cenni storici . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.2 Le diverse unit`a di analisi del testo . . . . . . . . . . 7 2.1.3 Un metodo per l’analisi automatica dei testi . . . . . 8 2.1.4 Analisi lessicale e analisi testuale . . . . . . . . . . . 10 2.1.5 La produttivit`a delle parole . . . . . . . . . . . . . . 11 2.2 Morfologia e dizionari . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 Definizioni utili . . . . . . . . . . . . . . . . . . . . . 13 2.2.2 I corpora . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.3 La lemmatizzazione . . . . . . . . . . . . . . . . . . . 16 3 Stato dell’arte sugli algoritmi di clustering del testo 19 3.1 Selezione delle funzioni e metodi di trasformazione per il testo 22 3.1.1 Metodi di selezione . . . . . . . . . . . . . . . . . . . 22 3.1.2 Metodi basati su LSI . . . . . . . . . . . . . . . . . . 26 3.1.3 Fattorizzazione di matrici non negative . . . . . . . . 28 3.2 Algoritmi per il clustering basati sulla distanza . . . . . . . . 29 3.2.1 Algoritmi agglomerativi e gerarchici di clustering . . 30 3.2.2 Algoritmi di partizionamento basati sulla distanza . . 33 3.2.3 Un Approccio ibrido: Il metodo Scatter-Gather . . . 34 4 Analisi delle forme grafiche (parole) 39 4.1 Radici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 Desinenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 iii 4.2.1 Suffissi . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.2 Prefissi . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2.3 Parti invariabili . . . . . . . . . . . . . . . . . . . . . 42 5 Processi per l’estrazione degli stem 47 5.1 Svantaggi nell’automatizzazione dello stemming . . . . . . . 48 5.2 Algoritmo di Porter . . . . . . . . . . . . . . . . . . . . . . . 51 5.3 Algoritmo di Lovins . . . . . . . . . . . . . . . . . . . . . . . 57 6 Classificazione del testo 61 6.1 Definizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.1.1 Classificazione mono/multi label . . . . . . . . . . . . 62 6.1.2 Classificazione basata sulle categoria o sui documenti 62 6.2 Approccio Machine Learning nella classificazione del testo . 63 6.2.1 Training set, Test set e di validazione . . . . . . . . . 64 6.2.2 Informazioni tecniche di recupero e classificazione del testo . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.3 Metodo di classificazione classico . . . . . . . . . . . . . . . 65 6.3.1 Algoritmi di classificazione . . . . . . . . . . . . . . . 65 6.3.2 Risultati ottenuti con il metodo classico . . . . . . . 67 6.4 Un nuovo approccio: Metodo Statistico . . . . . . . . . . . . 70 6.4.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 71 6.4.2 Risultati ottenuti con il metodo statistico . . . . . . . 74 7 Conclusioni 79 Bibliografia 80 iv Capitolo 1 Introduzione L’obiettivo del text mining `e studiare metodi e algoritmi per estrarre auto- maticamente conoscenza da testo non strutturato, come pagine web, email, forum e documenti in generale, utile per classificare o raggruppare docu- menti in base ai contenuti. Le applicazioni del text mining sono numerose. Una parte fondamentale nel text mining `e la pre-elaborazione del testo per generare variabili, note con il termine di feature, rilevanti per le fasi succes- sive di analisi, modellazione ed estrazione di conoscenza utile rispetto agli obiettivi prefissati. Tra le possibili pre-elaborazioni c’`e lo stemming delle parole, ossia il proces- so di riduzione della parola alla sua radice che non corrisponde in generale alla radice morfologica, i.e. al lemma. La creazione di algoritmi di stem- ming fa parte dell’area dell’informatica che si occupa dell’elaborazione del linguaggio naturale ed `e impiegata anche nei motori di ricerca per riscrivere le interrogazioni degli utenti. Nella tesi vengono messi a confronto due algoritmi che eseguono il pro- cesso di lemmatizzazione, ovvero la trasformazione di qualsiasi parola in forma ridotta, alla corrispettiva forma presente nel vocabolario per velociz- zare il processo di clustering, in particolare l’algoritmo derivato dallo studio di Lovins [34] e l’algoritmo iterativo di Porter [42]. Sono testati entrambi gli algoritmi menzionati sia nella versione completa e sia in quella parziale, ossia in quest’ultimo caso eseguendo solo alcuni dei passaggi previsti dal- l’intero algoritmo. Dopo la pre-elaborazione vengono condotti esperimenti applicando algoritmi tradizionali di classificazione all’insieme dei documen- ti. Infine questi risultati di classificazione elaborati con algoritmi classici 1 sono confronti con un nuovo metodo di classificazione introdotto in ques- ta tesi, basato sull’individuazione di associazioni statistiche tra parole di documenti diversi che trattano e che non trattano il medesimo argomento. 2 Capitolo 2 Introduzione al Text Mining L’applicazione della statistica per l’analisi dei testi in linguaggio naturale risale agli anni ’60, ma grazie al rapido aumento della disponibilit`a di testi digitali (Zampolli, Calzolari 1995) e alle pubblicazioni di testi in internet, quindi gi`a pronti per l’analisi, ha reso il processo di analisi automatica dei testi sempre piu` interessante, sia dal punto di vista accademico, che dal punto di vista commerciale. Inizialmente le soluzioni sviluppate si basavano principalmente sulla sta- tistica, ma vengono introdotte metodologie diverse, provenienti da varie discipline, come la linguistica e l’umanistica [7]. Si `e quindi passati da un metodo di tipo linguistico, a uno di tipo lessicale, arrivando a un analisi di tipo testuale o infine lessico-testuale. 2.1 Elaborazione del linguaggio naturale La linguistica computazionale `e l’applicazione dell’informatica alla linguis- tica teorica e applicata. Essa studia i problemi teorici e applicativi relativi al linguaggio naturale e al suo uso nell’informatica. Lo sviluppo si sviluppa in due ambiti, cio`e nella realizzazione di: • strumenti informatici per lo studio e la ricerca sul linguaggio; • applicazioni informatiche di largo uso (correttori ortografici, informa- tion retrieval) che sfruttano competenze linguistiche applicate all’in- formatica. 3 Per linguaggio naturale si intendono tutte le lingue utilizzate per la co- municazione verbale fra gli esseri umani. Il termine naturale nasce come contrapposizione a linguaggio formale, inteso come linguaggio artificiale completamente formalizzato e, possibilmente, privo di ambiguit`a, di cui viene fatto largo uso in informatica (ad esempio, tutti i vari linguaggi di programmazione sono linguaggi formali). 2.1.1 Cenni storici Storicamente, l’elaborazione del linguaggio naturale si suddivide tra diverse discipline, prendendo diversi nomi: • Linguistica computazionale; • Elaborazione del linguaggio naturale; • Riconoscimento del parlato; • Neurolinguistica; ognunadellequalipromossadaunadisciplinachestudiaaspettidiversi, dal- lalinguisticaallapsicologia, passandodall’informaticae dall’elettronica[53]. 1940-1950 - II guerra mondiale Vengono presentati i primi modelli applicabili all’informatica, • Automi a stati finiti; – teoria dei linguaggi formali (algebra e teoria degli insiemi per la formalizzazione dei linguaggi); – Chomsky,Backus,Naur(grammaticheBNFperlaformalizzazione dei linguaggi). • Algoritmi probabilistici per il riconoscimento del parlato – Sviluppodellateoriadell’informazione(Shannon),chenonriguar- da la forma o il contenuto, ma si basa sulle procedure di trasmis- sione e ricevimento: 4 ∗ rumorosit`a del canale; ∗ codifica e decodifica; ∗ entropia di un linguaggio. La Machine Translation `e una delle prime applicazioni desiderate (soprat- tutto a scopi militari, durante la Guerra Fredda). Due paradigmi in contrapposizione Nel dopo guerra, vengono sviluppati due paradigmi che analizzano i lin- guaggi su aspetti duali: • Simbolico; • Stocastico. Il primo studia il linguaggio naturale tramite regole e grammatiche. Ven- gono utilizzate fortemente le regole. Si sviluppa quindi la teoria dei lin- guaggi formali (algoritmi di parsing top-down e bottom-up). Appaiono i primi esempi di intelligenza artificiale (teorie logiche, sviluppo di sistemi domanda-risposta tramite pattern matching, ricerca di keyword e semplici euristiche). Il secondo parte da documenti reali e li analizza per estrarre le ”regole” probabilistiche che li regolano. Uso debole delle regole, che possono es- sere trasgredite. Metodo bayesiano, tramite uso di dizionari e corpora. Riconoscimento di testi scritti tramite lo sviluppo dell’OCR. Aumentano i paradigmi Con il passare del tempo, fra gli anni ’70 e ’80, vengono sviluppati nuovi paradigmi, osservando nuovi aspetti delle problematiche dell’elaborazione linguistica naturale: • Stocastico; • Logic-based; • Natural language under standing; • Discourse modelling. 5 Vengono proposti gli Hidden Markov Model (HMM), modelli stocastici in cui si assume che il sistema sia modellato da un processo di Markov con stati inosservati (hidden). Si unificano le strutture in feature (si riconoscono le interconnessioni tra le parti del discorso, in modo piu` performante rispetto alle grammatiche context-free). Terry Winograd sviluppa SHRDLU, uno dei primi programmi per computer per la comprensione di un linguaggio. Appaionoleprimeanalisidellesottostrutturedeldiscorso, conlarisoluzione automatica dei riferimenti. Empiricismo e FSModels Negli anni ’80 ci sono pochi finanziamenti per il campo dell’elaborazione del linguaggio naturale. L’uso della rappresentazione denotativa aveva ostaco- lato tutta l’intelligenza artificiale e i pochi risultati avevano fatto perdere fiducia ai finanziatori. La logica`e troppo limitata rispetto alla realt`a: rende impossibile risolvere alcuni problemi. Sono quindi necessarie altre rappre- sentazioni. L’uso delle grammatiche `e troppo lento per fornire buoni risul- tati: scrivere una grammatica completa ed efficace per una lingua richiede anni, ma la lingua si evolve molto piu` in fretta. • Ritorno all’utilizzo dei modelli a stati finiti, per la fonologia, la mor- fologia e la sintassi; • Ritorno all’empiricismo: lavori di IBM per il riconoscimento del par- lato basandosi su modelli probabilistici; approcci datadriven (ossia piu` incentrati su dati preesistenti che non su un modello) per il POS tagging, il parsing e l’annotazione, per la risoluzione delle ambiguit`a. • Natural Language Generation. I due campi si incontrano L’approccio simbolico e quello stocastico si stanno riunendo. Le difficolt`a incontrate con il primo trovano nuove vie di soluzione. Si uniscono ad un pesante uso delle metodologie data-driven e dei modelli probabilistici. Nascono nuovi ambiti applicativi, come il Web, e nuove possibilit`a dovute all’aumentata capacit`a di elaborazione dei sistemi. 6