Text Mining

Giorno dopo giorno prendiamo sempre più coscienza dell’enorme mole di dati disponibile in formato digitale nei contesti più svariati. Tale quantità di dati risulta essere in continua ascesa, favorita da tecnologie sempre più utilizzate quali internet. Questo rapido aumento di informazioni a prima vista sembra apportare solo vantaggi, ma non è difficile comprendere che con l’incremento della quantità di informazioni disponibili aumentano in proporzione anche gli sforzi che occorrono per riuscire a separare l’utile dall’inutile.

Tali difficoltà emergenti portano alla forte richiesta di software in grado di processare documenti contenenti informazioni non strutturate. Purtroppo l’offerta di tali software è per ora estremamente limitata soprattutto se si considera la proporzione esistente tra informazioni strutturate e non strutturate. Un’idea indicativa di quanto detto si può trarre dalla Figura 1.

Figura 1 – Confronto tra tipi di dati e rispettivi software in grado di processarli

Il text mining si occupa per l’appunto di descrivere le tecnologie grazie alle quali è possibile ottenere un forte aiuto nel trarre informazioni da documenti non strutturati. A seconda degli obiettivi che si desiderano raggiungere e dalle tecniche utilizzate, possiamo identificare:

  • Document Classification
  • Information Retrieval
  • Clustering and Organizing Documents
  • Information Extraction

Al fine di offrire una breve panoramica sul text mining, sarà brevemente descritta ciascuna delle suddette tecniche.

Task del text mining

Document Classification

Per document classification o text Categorization si intende l’insieme delle tecniche atte ad associare ad un documento un topic. In altre parole si crea un folder per ogni topic e per ogni documento si identifica il folder corrispondente. Un esempio è mostrato in Figura 2:

Figura 2 – Schematizzazione dell’operazione di Document Classification

Tale tecnica opera sostanzialmente tramite algoritmi supervisionati. Questi ultimi utilizzano una grande quantità di esempi (patterns) composti da un documento e il relativo topic, al fine di indurre nel sistema una regola generale in modo da permettergli, al termine dell’addestramento, di classificare anche documenti mai esaminati in precedenza.
Numerosi sono i campi di applicazione di tali tecniche. Essi vanno dalla catalogazione dei documenti al fine di semplificarne la ricerca, al forwarding automatico delle mail nei vari dipartimenti di una compagnia, al riconoscimento di mail SPAM nella posta in arrivo etc…

Information retrieval

L’information retrieval è senza dubbio la tecnica più utilizzata dai motori di ricerca su internet. Lo scopo è quello di identificare un insieme di documenti dato un insieme di WORD. In una tipica istanza di un Search Engine infatti un utente definisce un set di parole che vengono matched con tutti i documenti disponibili e vengono restituiti quelli corrispondenti al best match.

Una generalizzazione del caso precedente è rappresentata dal Document Matcher, nel quale l’utente non fornisce in input un piccolo insieme di word ma un intero documento. In questo viene fatto il match tra il documento fornito in input e i documenti disponibili. In output si ottengono solo quelli che implementano il best match.

Un concetto particolarmente importante è la similarity measure. Due documenti vengono confrontati misurando il loro grado di similitudine che ovviamente dipende fortemente dalla particolare misura di distanza che viene adottata. A seconda del significato associato al concetto di distanza il risultato può essere più o meno soddisfacente. Una delle fasi critiche di questa metodologia risiede appunto nella scelta del modo di calcolo della distanza. Può essere infatti arduo definire la distanza tra due oggetti generici. Quanto detto è mostrato schematicamente nella Figura 3:

Figura 3 – Schematizzazione del processo di information retrieval

Clustering and Organizing Documents

La rappresentazione di informazione tramite il processo di clustering è molto simile a quella vista nel caso del Document classification con la differenza che mentre in quest’ultimo l’addestramento avveniva grazie alla creazione da parte di un esperto di una serie di folders, basata sulla conoscenza dei topic specifici, l’utilizzo di questa tecnica invece non prevede la creazione preventiva di folder né la specificazione di topic o di esempi. Il sistema, come mostrato in Figura 2.4, provvederà al raggruppamento delle entità basandosi sul concetto di distanza tra essi. Siccome dato un insieme di documenti esistono numerosi modi di raggruppamento, questa tecnica si preannuncia meno potente rispetto all’assegnazione delle label tramite un esperto, ma può apportare vantaggi nel caso in cui non si conosca a priori la struttura che caratterizza un insieme di documenti. Ad esempio, analizzando le parole chiave che caratterizzano i singoli cluster, un’azienda può estrarre informazioni sui propri clienti.

Gli algoritmi utilizzati per la realizzazione di tale tecnica sono del tipo “non supervisionato”.

Per le sue caratteristiche intrinseche questa tecnica risulta molto utile nell’ambito del data mining, dove i dati, prevalentemente di tipo numerico, sono già strutturati. In tal caso è relativamente semplice definire il concetto di distanza tra oggetti; risulta invece meno efficace e più ardua attuazione nel caso di documenti testuali.

Figura 4 –Schematizzazione del processo di Clustering di una collezione di documenti

Information Extraction

L’obiettivo principale dell’Information Extraction è quello di prelevare informazioni da un documento di tipo non strutturato e riportarle in modo strutturato. Un semplice esempio di questa tecnica è mostrato in Figura 2.5.

Figura 5 – Esempio di Information Extraction

Questa tecnica trova numerose applicazioni: tra le più note troviamo la creazione di database quantitativi a partire da documenti in forma non strutturata.

Processo di Mining di un Testo

Prima di poter effettuare il maining di un documento occorre passare per una serie di fasi che portano da un documento non strutturato ad uno strutturato. Ognuna di queste fasi nasconde insidie è può essere la causa di risultati poco soddisfacenti. È possibile sintetizzare tale procedura attraverso i passi mostrati in Figura 6.

 

Figura 6 – Passi di un processo di Mining di un testo

Collecting Documents

Rappresenta il primo passo da compiere. In questa fase vanno scelti i documenti rappresentativi ai fini dell’addestramento. Questa fase risulta essere molto importante in quanto anche un ottimo processo di apprendimento effettuato su documenti non indicativi può portare a risultati del tutto insoddisfacenti.

Documents Standardization

La fase di Collecting ci fornirà un insieme di documenti rappresentativo, ma non tutti i documenti potrebbero avere lo stesso formato. Giusto per citarne alcuni, potremmo trovarci di fronte a documenti scritti e salvati in un formato proprietario (Word, Excel…), in semplice formato testo o codice ASCII, documenti scannerizzati e quindi sottoforma di immagini etc…
È molto importante ai fini della gestione dei dati a disposizione, adottare un unico formato. Un linguaggio particolarmente efficiente e molto diffuso è XML (Extensible Markup Language) grazie al quale diversi tag possono essere adottati al fine di specificare attributi quali titolo, autore, corpo del testo ed altri. Un esempio di documento descritto in linguaggio XML può essere il seguente:

 

Figura 7 – Esempio di documento standardizzato usando XML

L’importanza di identificare le parti di un documento risiede nella possibilità di selezionare le stesse per generare una descrizione quantitativa del testo (features).

Tokenization

A questo punto, supponendo di disporre di una collezione di documenti in formato XML, siamo pronti ad analizzare il testo (non strutturato) per identificarne le features utili.

Il primo passo da compiere nel manipolare il testo, consiste nel segmentare l’insieme di caratteri in WORDS o più precisamente in TOKENS. Ogni TOKEN è un’istanza di un TYPE per cui il numero dei differenti TOKENS è molto maggiore del numero dei TYPES. Questo significa che per ogni type possono esserci più token uguali.

In termini formali ci si riferisce alla frequenza di occorrenza del TYPE, sebbene, essendo meno rigorosi, è accettato anche riferirsi alla frequenza di occorrenza di un TOKEN.

Il processo di tokenization è banale per un umano ma può divenire anche molto complesso per un calcolatore. Il problema risiede nel fatto che determinati caratteri possono essere Token Delimiters oppure no in dipendenza della specifica applicazione considerata. Caratteri come  Spazio, Tab,  Newline vengono assunti essere sempre e comunque Token Delimiters. Per altri caratteri la situazione è differente e in molti casi controversa.

Caratteri come: ( )  < >  !  ?  “ sono sicuramente Token Delimiters ma occasionalmente possono essere Tokens.

A seconda del contesto (environment) caratteri come . ,  :  –  ‘ possono essere o no Token delimiters; ad esempio il punto di fine periodo è diverso dal punto che separa le cifre decimali in un numero, oppure il segno “-” è diverso se usato come trattino in un testo o come separatore tra prefisso e numero di telefono o ancora come segno davanti ad un numero.

Un tokenizer ottimizzato deve essere realizzato dipendentemente dalla tipologia di testo che deve essere trattata.

Inoltre, appare evidente che il tokenizer dipende dalla lingua dei testi che devono essere trattati.

Esistono diversi tokenizer disponibili nel WEB

http://www.codeproject.com/cpp/cplexxer.asp

http://lists.xml.org/archives/xml-dev/199807/msg00363.html

http://www.devincook.com/goldparser

Lemmization

Lo scopo principale della fase di lemmization è quello di ridurre drasticamente il numero di type da trattare. Questa riduzione ha un doppio effetto benevolo sull’analisi del testo. In primo luogo il minor numero di type agevola la fase di addestramento limitando la necessità di risorse sia in termini di tempo che di spazio; un secondo effetto che si può ottenere da tale riduzione risiede nel fatto che accorpando parole con radice simile e quindi presumibilmente con significato simile, un eventuale analisi statistica sarebbe da considerare più affidabile.

Non è semplice realizzare un software che riesca in modo corretto ad effettuare lo stemming di un documento in quanto fortemente dipendente dalla lingua e dal contesto.

Alcuni stemmers possono trovarsi ai seguenti indirizzi:

http://www.ils.unc.edu/keyes/java/porter/

http://maya.cs.depaul.edu/~classes/ds575/tools.html

http://www.tel.fer.hr/users/mtopol/jezix/source-code-intro.html

http://snowball.tartarus.org/texts/introduction.html

http://www.marketingshift.com/2005/01/free-word-stemming-algorithm-code.cfm

http://snowball.tartarus.org/

Vector Generation

Durante la fase di Vector Generation, si tenta di dare una forma strutturata al documento originale. In particolare, ove non vi sia importanza nell’ordine dei token, la soluzione più promettente sembra essere quella di generare una matrice che presenti sulle righe i documenti adottati per il training set e sulle colonne i type. L’intersezione tra una riga ed una colonna può conservare l’informazione relativa alla presenza di una determinata parola all’interno di un certo documento. Questa informazione può essere di tipo binario o di tipo statistico. Nel primo caso si andrà a porre uguale ad uno il valore della cella rappresentante l’intersezione tra un documento ed un type se tale type è presente almeno una volta all’interno del documento in oggetto; nel secondo caso si parla di frequenza (assoluta o relativa) del termine all’interno del documento.

Se si sta tentando di risolvere un problema di classificazione documentale, la matrice in questione ha bisogno di una ulteriore colonna che associ ad ogni documento una categoria.

La dimensione di questa matrice inciderà fortemente sulle prestazioni del sistema. In particolare è necessario giungere a un trade-off tra la precisione che si vuole ottenere ed il tempo a disposizione per l’addestramento anche in funzione della potenza di calcolo di cui si dispone. Può essere utile ridurre a tal proposito le dimensioni di questa matrice adottando le tecniche di stemming presentante al punto precedente.

Feature Generation

L’ultima fase da affrontare per passare da una rappresentazione non strutturata ad una strutturata, trattabile con metodi quantitativi, è la Feature Generation.

La natura ed il significato delle features ottenute tramite la fase di Feature Generation chiaramente dipendono dalla tipologia del task di text mining che deve essere affrontato.

Questa fase alla fine si risolve in uno di questi tre meccanismi di learning:

  • Classificazione Supervisionata
  • Clustering o Classificazione Non Supervisionata
  • Reinforcement Learning.
1 Stella2 Stelle3 Stelle4 Stelle5 Stelle (Nessun voto ancora)
Loading...
You can leave a response, or trackback from your own site.

Leave a Reply

*