Buenos Aires, mayo de 2016Eduardo Poggi
Text Mining
¿TM? Aproximación NLP Herramientas Reducción a técnicas de ML supervisado Ejemplos
Text Mining
¿TM? Aproximación NLP Herramientas Reducción a técnicas de ML supervisado Ejemplos
¿TM?
Text mining es extraer información interesante y no obvia de texto sin estructura, para poder encontrar patrones, tendencias de datos, asociaciones entre entidades, y reglas predictivas.
Marti Hearst: “text mining is the discovery by computer of new,
previously unknown information, by automatically extracting information from different written resource”.
¿TM?
Tenemos mucho texto y poca información, que está escondida...
¿Quién es autoridad en qué tema? ¿Qué temas están creciendo en importancia? emails, chats, libros online, comentarios de productos
¿Qué leo? ¿Con qué se relaciona? ¿Tiene el texto un sesgo a favor o en contra de algo o
alguien? ¿Quién escribió el texto?
No es: Recuperación de información Reordenación cosmética de datos previamente conocidos ¿Aprendizaje automático a partir de ejemplos ya
clasificados?
¿TM?
Incluye: Minado de conceptos Minado de opiniones Descubrimiento de relaciones Descubrimiento de comportamiento de palabras Descubrimiento de la semántica de las palabras
La frontera es poco clara: ¿qué pasa con los modelos que aprenden de ejemplos
clasificados?
¿TM?
¿TM?
¿Por qué surge ahora? Avances en NLP Avances en hardware Explosión de la Web Digitalización masiva de datos Avances en recuperación de datos
¿TM?
En algunos campos (biología por ejemplo) el 80% del conocimiento está en papers.
Humanos no escalan: se pueden leer 20 papers por semana, mietras PubMed agregó 2500!
De acuerdo a Gartner, hasta el 85% de información empresarial es no estructurada.
¿TM?
TM es más complicado que Data Mining porque: Las computadoras no pueden leer (comprender) texto. El texto no tiene estructura bien definida (campos).
Identificar entidades Identificar relaciones
Un documento trata varios temas. El significado de las palabras es ambiguo y depende del
contexto y del idioma. Posible explosión combinatoria de conexiones
potencialmente válidas. No está conectado con otros tipos de conocimiento
Casi siempre ejemplos no clasificados Rango de resultados totalmente desconocido Falta de abstracción
Alta dimensionalidad Difícil de interpretar
Usualmente, volumen de input desconocido
¿TM?
Aplicaciones: En su manera más simple, agregado de columnas para
mejorar precisión de mining. Detección de importancia de emails (spam). Clustering de documentos (vivisimo.com). Redirección de un documento a un experto (routing). Creación de mapas de tópicos (www.leximancer.com). Minería de tendencias y opiniones (blogpulse). Extracción de ontologías y de entidades
(opencalais.com). Resumen de documentos. Descubrimientos de relaciones por citas y links. Determinación de autoria.
¿TM?
Ejemplo: A partir de títulos y abstracts de artículos de medicina se
encuentran relaciones causales entre síntomas, drogas y efectos.
Dolores de cabeza causados por migraña El estrés se asocia con la migraña El estrés provoca pérdida de magnesio
El magnesio es un bloqueador del canal de calcio natural Los bloqueadores del canal de calcio evitan algunas migrañas Niveles altos de magnesio inhiben la depresión cortical
extendida La depresión cortical extendida se encuentra en migrañas
¿TM?
Necesidades de información más sofisticadas Detectar sentimientos respecto a un producto, candidato,
política, etc, en medios de comunicación colectivos (foros, blogs, etc).
Respuestas a preguntas vs recuperación de documentos. Resumen de múltiples documentos vs listados. Explicitar la estructura conceptual de los documentos de
un cierto tipo. Traducción automática.
Aproximación
Recuperación de Datos vs Recuperación de Información
Text Mining
¿TM? Aproximación NLP Herramientas Reducción a técnicas de ML supervisado Ejemplos
Aproximaciones
Dos aproximaciones extremas: Sólo sintáctica Sólo analítica
Un gradiente de aproximaciones híbridas: Tratamiento sintáctico con uso de herramientas
Aproximación
Cada documento se representa por una serie de términos.
Un término es una palabra o grupo de palabras útiles para describir el contenido del documento.
Todos los términos son independientes entre sí, lo que implica que puedo calcular la importancia de cada término en un documento independientemente de los otros (la independencia no es cierta, pero en la práctica funciona).
El peso wij de un término ti en un documento dj es proporcional a la importancia de ese término.
Aproximación
Existen varias aproximaciones a la representación de la información:
Bag of Words: cada palabra constituye una posición de un vector y el valor corresponde con el nº de veces que ha aparecido.
N-gramas o frases: permite tener en cuenta el orden de las palabras. Trata mejor frases negativas “... excepto ...”, “... pero no...”, que tomarían en otro caso las palabras que le siguen como relevantes.
Representación relacional (primer orden): permite detectar patrones más complejos (si la palabra X está a la izquierda de la palabra Y en la misma frase...).
Categorías de conceptos. Casi todos se enfrentan con el “vocabulary problem”. Tienen
problemas con la sinonimia y quasi-sinonimia (comunicado, declaración) , la polisemia (bomba), los lemas (descubrir, descubrimiento), etc.
Aproximación
Todos los términos de todos los documentos en la colección tienen un índice i único. i es siempre igual para t en todos los documentos.
wij > 0 si ti es un término en dj, 0 caso contrario dj.
Si hay N términos en total en la colección, un documento dj es un vector de dimensión N:
Documento dj=[w1j, w2j, w3j, ... wNj] (la mayoria de los wij van a ser 0).
Aproximación
Controlar el vocabulario es fundamental para evitar la explosión de términos.
Palabras mal escritas. Diferencias sintácticas sin diferencias semánticas
significativas.
Aproximación
Representar a las palabras como “cadenas fonéticas”. Cada palabra de sonido similar debería mapearse al misma cadena.
Soundex. Valor Componentes de grupo en castellano:
0 <- S C Z 1 <- V B 2 <- LL Y 3 <- G J X 4 <- K Q C 5 <- P 6 <- D 7 <- R 8 <- L 9 <- M N Ñ <- Ñ F <- F
Aproximación
Stemming: Las palabras que tienen un prefijo común, en general, se
refieren a conceptos relacionados. Por ejemplo:
“triángulo”, “triangular”, “triangulación” “secretario”, “secretaria”, “secretariado”.
Stemming es reducir palabras a su parte común (tallo) quitando los finales (hojas).
Stemming reduce el vocabulario, aumentando posibles coincidencias, pero esto no es necesariamente mejor recuperación.
Los límites depende del problema a resolver. Por ejemplo, llevar los verbos al infinitivo o algo intermedio o dejarlos como estar.
Aproximación
Distancia (Levenshtein)
Aproximación
Colocación: Dos o mas palabras que corresponden al nombre de algo
o a una manera de llamar cosas: “ciencia ficción”, “disco rígido”, “software libre”
El significado no se deduce de las partes (por ejemplo “yerba mala”).
¿Juntas por casualidad? Co-locación significa que ciertas palabras no son
independientes entre sí. ¿Cómo decidir si están juntas por casualidad, o en
realidad están relacionadas? Medidas de Colocación más usadas: Intersección, Jackard,
Dice, Información mutua, Tests de Colocación: X2 Características Deseables:
Que tenga un máximo y mínimo definido, para poder interpretar el valor.
Que no sea muy sensible a eventos raros. Que tenga una justificación (casi siempre probabilística)
Text Mining
¿TM? Aproximación NLP Herramientas: Reducción a técnicas de ML supervisado Ejemplos
NLP
Comprensión automática del lenguaje humano: Desambiguación de sentidos Análisis sintáctico Resolución de co-referencia Interpretación semántica de oraciones
NLP – ejemplo 1
Ejemplo con diálogo hombre-máquina H: cuáles son los horarios de buses a Mar del Plata para
mañana? M: 7:30, 8, 8:30, 9, 10, 11, …
Desambiguación de sentidos: Mañana = próximo día Mañana = primera parte del día
NLP – ejemplo 1
Ejemplo con diálogo hombre-máquina H: cuáles son los horarios de los buses Mar del Plata para
mañana? M: 7:30, 8, 8:30, 9, 10, 11, …
Análisis sintáctico: Horarios __ de __ buses
__ los __ a __ Mar_del_Plata
NLP – ejemplo 1
Ejemplo con diálogo hombre-máquina H: cuáles son los horarios de los buses Mar del Plata para
mañana? M: 7:30, 8, 8:30, 9, 10, 11, …
Resolución de co-referencia: Horarios __ de __ buses
__ los __ desde __ Buenos_Aires __ a __ Mar_del_Plata
NLP – ejemplo 1
Ejemplo con diálogo hombre-máquina H: cuáles son los horarios de los buses Mar del Plata para
mañana? M: 7:30, 8, 8:30, 9, 10, 11, …
Interpretación semántica de oraciones: Fecha: 24-jun-2008 (today()) Medio_de_transporte: bus Desde: Buenos_Aires Hasta: Mar_del_Plata Horarios: ?
NLP y Text Mining
Limitaciones: recursos del conocimiento lingüístico Poca cobertura Recursos de conocimiento estático Poca adaptación a entornos específicos
Que aporta: Generalización de fenómenos lingüísticos
Se sufre menos la escasez de datos Representación teóricamente más adecuada
Mayor interpretabilidad Conexión con bases de conocimiento extra-textuales
NLP - Arquitectura básica
1. Reconocimiento de idioma2. Segmentación de palabras,
oraciones, secciones3. Análisis morfológico
1. Detección de palabras especiales
2. Asignación de etiquetas3. Desambiguación de
etiquetas4. Análisis sintáctico
1. Constituyentes básicos o chunks
2. Estructura de oración3. Funciones gramaticales,
roles temáticos5. Análisis semántico
1. Léxico2. Proposicional
elgatocomewiskas
El gato come whiskas.
1. Reconocimiento de idioma2. Segmentación de palabras,
oraciones, secciones3. Análisis morfológico
1. Detección de palabras especiales
2. Asignación de etiquetas3. Desambiguación de
etiquetas4. Análisis sintáctico
1. Constituyentes básicos o chunks
2. Estructura de oración3. Funciones gramaticales,
roles temáticos5. Análisis semántico
1. Léxico2. Proposicional
NLP - Arquitectura básica
El – DA0MS0gato – NCMS000
come – VMIP3S0, VMPP2S0whiskas – NCMS000, VMP00SM
NLP - Arquitectura básica
1. Reconocimiento de idioma2. Segmentación de palabras,
oraciones, secciones3. Análisis morfológico
1. Detección de palabras especiales
2. Asignación de etiquetas3. Desambiguación de etiquetas
4. Análisis sintáctico1. Constituyentes básicos o
chunks2. Estructura de oración3. Funciones gramaticales, roles
temáticos5. Análisis semántico
1. Léxico2. Proposicional
El – DA0MS0gato – NCMS000come – VMIP3S0
whiskas – NCMS000
NLP - Arquitectura básica
1. Reconocimiento de idioma2. Segmentación de palabras,
oraciones, secciones3. Análisis morfológico
1. Detección de palabras especiales
2. Asignación de etiquetas3. Desambiguación de etiquetas
4. Análisis sintáctico1. Constituyentes básicos o
chunks2. Estructura de oración3. Funciones gramaticales, roles
temáticos5. Análisis semántico
1. Léxico2. Proposicional
grupo_nominal(el gato)grupo__verbal (come)
grupo_nominal(whiskas)
NLP - Arquitectura básica
1. Reconocimiento de idioma2. Segmentación de palabras,
oraciones, secciones3. Análisis morfológico
1. Detección de palabras especiales
2. Asignación de etiquetas3. Desambiguación de etiquetas
4. Análisis sintáctico1. Constituyentes básicos o
chunks2. Estructura de oración3. Funciones gramaticales, roles
temáticos5. Análisis semántico
1. Léxico2. Proposicional
• Oración• SN
• Especificador - el• grupo_nominal - gato
• SV• grupo_verbal - come• SN
• grupo_nominal - whiskas
1. Reconocimiento de idioma2. Segmentación de palabras,
oraciones, secciones3. Análisis morfológico
1. Detección de palabras especiales
2. Asignación de etiquetas3. Desambiguación de
etiquetas4. Análisis sintáctico
1. Constituyentes básicos o chunks
2. Estructura de oración3. Funciones gramaticales,
roles temáticos5. Análisis semántico
1. Léxico2. Proposicional
NLP - Arquitectura básica
• Oración• SN SUJETO - AGENTE
• Especificador - el• grupo_nominal - gato
• SV PREDICADO• grupo_verbal - come• SN OBJETO - TEMA
• grupo_nominal - whiskas
1. Reconocimiento de idioma2. Segmentación de palabras,
oraciones, secciones3. Análisis morfológico
1. Detección de palabras especiales
2. Asignación de etiquetas3. Desambiguación de
etiquetas4. Análisis sintáctico
1. Constituyentes básicos o chunks
2. Estructura de oración3. Funciones gramaticales,
roles temáticos5. Análisis semántico
1. Léxico2. Proposicional
NLP - Arquitectura básica
• El gato: • entidad –> ser vivo –> animal -
> felino doméstico determinado• Come:
• acción -> voluntaria -> …• Whiskas:
• marca comercial -> entidad -> inanimado -> comestible -> pescado
1. Reconocimiento de idioma2. Segmentación de palabras,
oraciones, secciones3. Análisis morfológico
1. Detección de palabras especiales
2. Asignación de etiquetas3. Desambiguación de
etiquetas4. Análisis sintáctico
1. Constituyentes básicos o chunks
2. Estructura de oración3. Funciones gramaticales,
roles temáticos5. Análisis semántico
1. Léxico2. Proposicional
NLP - Arquitectura básica
EXISTE gato(X) AND EXISTE comida(Y) AND come(X,Y)
NLP
Arquitectura simbólicas Un humano desarrolla reglas de análisis y/o diccionarios El conocimiento codificado en las reglas y diccionarios se
aplica mediante un analizador automático Arquitecturas probabilísticas
Uno o más humanos analizan una muestra representativa de lenguaje natural (corpus acotado)
Se aplica un proceso de inferencia de conocimiento (reglas y/o diccionarios) a esta muestra
El conocimiento obtenido automáticamente en forma de reglas y diccionarios, a menudo probalísticos, se aplica mediante un analizador automático
Text Mining
¿TM? Aproximación NLP Herramientas:
Colocaciones Diccionarios Lexicones Tesauros
Reducción a técnicas de ML supervisado Ejemplos
Herramientas: Colocación – Dice, Jackard
Herramientas: Colocación – Pointwise Mutual Information
Herramientas: Colocación – Test de colocación
Test de Hipótesis: Determinar si hay suficiente evidencia para determinar que algo no ocurrió por casualidad.
• Hipóthesis Nula H0= independencia de palabras: P(w1w2) = P(w1)P(w2) Se computa la probabilidad P = p del evento asumiendo
que H0 es cierta. Rechazamos H0 si al nivel de significancia a si p<0.05;
sino, no rechazamos H0.
Herramientas: Colocación – X2
Herramientas: Lexicones
Un Lexicón es un diccionario ampliado en el que se registran las palabras que utiliza un hablante donde se especifican los rasgos idiosincráticos de las piezas léxicas (palabras).
En un diccionario tradicional, las entradas se identifican mediante una forma base o "canónica" de la palabra.
Esta forma canónica varía según el idioma: Los verbos en inglés se representan mediante la raíz no flexionada,
mientras en francés o español se representan con el infinitivo del verbo.
Además de la definición estos diccionarios tradicionales incluyen en cada entrada información adicional como la pronunciación, la categoría gramatical o su etimología.
En un lexicón se incluyen formas flexionadas de las palabras, es decir, listas de palabras con todas las formas e información gramaticales correspondiente, por ejemplo, contendría las palabras: comer, comida, comiendo, comido por separado, como unidades diferenciadas.
Herramientas: Lexicones
Las unidades léxicas distinguen tres tipos de rasgos:
Formales: contienen información sobre el tipo de palabra de la que se trata (sustantivo, verbo, preposición), sobre el contexto sintáctico en el que pueden aparecer y sobre el tipo de flexión que requieren.
Semánticos: contienen información sobre la estructura argumental requerida por una unidad léxica (un verbo como "destruir" requiere un agente que destruya y un tema a ser destruido), sobre las propiedades inherentes de cada unidad (un nombre como "niño" tiene rasgos [+humano] [+contable] etc.).
Fonológicos: Contiene la información necesaria para asignarle representación fonética a la unidad.
Herramientas: Lexicones
Según su naturaleza, las unidades del lexicón pueden distinguirse entre:
Categorías léxicas o abiertas: son aquellas que poseen carácter referencial (las que designan procesos, propiedades, acciones o entidades). Se caracterizan por formar un inventario abierto (no existe un número específico y limitado para estas unidades). Los sustantivos, los verbos y los adjetivos son representantes canónicos de este tipo de unidades léxicas.
Categorías funcionales o cerradas: son aquellas que sólo poseen significado gramatical (son fundamentales para la generación de una oración pero que, sin embargo, no tienen significado referencial). Se caracterizan por formar un inventario cerrado. Las conjunciones y los artículos son representantes de este tipo de unidad.
Herramientas: Lexicones - wordnet.princeton.edu: “bank”
Noun S: (n) bank (sloping land (especially the slope beside a body of water)) "they pulled the canoe
up on the bank"; "he sat on the bank of the river and watched the currents" S: (n) depository financial institution, bank, banking concern, banking company (a financial
institution that accepts deposits and channels the money into lending activities) "he cashed a check at the bank"; "that bank holds the mortgage on my home"
S: (n) bank (a long ridge or pile) "a huge bank of earth" S: (n) bank (an arrangement of similar objects in a row or in tiers) "he operated a bank of
switches" S: (n) bank (a supply or stock held in reserve for future use (especially in emergencies)) S: (n) bank (the funds held by a gambling house or the dealer in some gambling games) "he
tried to break the bank at Monte Carlo" S: (n) bank, cant, camber (a slope in the turn of a road or track; the outside is higher than the
inside in order to reduce the effects of centrifugal force) S: (n) savings bank, coin bank, money box, bank (a container (usually with a slot in the top) for
keeping money at home) "the coin bank was empty" S: (n) bank, bank building (a building in which the business of banking transacted) "the bank is
on the corner of Nassau and Witherspoon" S: (n) bank (a flight maneuver; aircraft tips laterally about its longitudinal axis (especially in
turning)) "the plane went into a steep bank" Verb
S: (v) bank (tip laterally) "the pilot had to bank the aircraft" S: (v) bank (enclose with a bank) "bank roads" S: (v) bank (do business with a bank or keep an account at a bank) "Where do you bank in this
town?" S: (v) bank (act as the banker in a game or in gambling) S: (v) bank (be in the banking business) S: (v) deposit, bank (put into a bank account) "She deposits her paycheck every month" S: (v) bank (cover with ashes so to control the rate of burning) "bank a fire" S: (v) trust, swear, rely, bank (have confidence or faith in) "We can trust in God"; "Rely on your
friends"; "bank on your good education"; "I swear by my grandmother's recipes"
Herramientas: Tesauros
Listado de palabras o términos empleados para representar conceptos.
Adquiere al menos dos significados relacionados: En el campo de la literatura, es una lista de palabras con
significados similares o sinónimos, habitualmente acompañada por otra lista de antónimos. Un ejemplo sería un tesauro dedicado a un campo especializado, que contiene la jerga que se emplea en dicho campo del conocimiento.
En el campo de la bibliotecología o de las Ciencias de la Información, un tesauro es una lista que contiene los "términos" empleados para representar los conceptos, temas o contenidos de los documentos, con miras a efectuar una normalización terminólogica que permita mejorar el canal de acceso y comunicación entre los usuarios y las Unidades de Información (biblioteca, archivo o centros de documentación).
No es la función de un tesauro definir las palabras, esta función es propia del diccionario. Sin embargo, muchos tesauros contienen definiciones de los términos que emplean, con el fin de que el usuario del tesauro no tenga dudas al seleccionar un término.
Herramientas: Tesauros
En líneas generales, un tesauro comprende lo siguiente:
Un listado de términos preferidos, que se los ordena en forma alfabética, temática y jerárquicamente.
Un listado de sinónimos de esos términos preferidos, llamados descriptores, con la leyenda "úsese (término preferido)" o una indicación similar.
Una jerarquía o relaciones entre los términos. Esto se expresa con la identificación de "términos más generales" y "términos más restringidos".
Las definiciones de los términos, para facilitar la selección de los mismos por parte del usuario
Y un conjunto de reglas para usar el tesauro.
Herramientas: Tesauros
Descriptores Un descriptor es cada uno de los términos o expresiones
escogidos entre un conjunto de sinónimos o cuasi sinónimos para representar (en calidad de término preferido) generalmente de manera unívoca, un concepto susceptible de aparecer con cierta frecuencia en los documentos indexables y en las consultas que se realicen.
El descriptor corresponde normalmente a la etiqueta de un concepto y es la unidad mínima de significado que integra un tesauro o una lista de descriptores.
Suele acompañarse de una nota de alcance o, menos usualmente, de una definición en los casos que el mero registro del término puede provocar problemas de ambigüedad en su interpretación.
Es el término por el cual efectivamente se indexará y por el cual se recuperarán los documentos referidos a su temática.
Herramientas: Tesauros – thesaurus.reference.com: “bank”
Synonym Collection v1.1 Main Entry: bank Part of Speech: verb Synonyms: acclivity, anthill, banco, bay, bench, brew, brink, coast, dike, dune,
edge, elevation, embank, embankment, fence, heap up, hill, levee, margin, mass, mound, pile, pile up, platform, ramp, ridge, rive, river, row, sand, shallow, shelf, shore, slope, stack, stage, strand, tier
Roget's II: The New Thesaurus Main Entry: depend Part of Speech: phrasal verb Definition: To place trust or confidence in. Synonyms: believe in, count on, depend on, reckon on, rely on, trust
Roget's II: The New Thesaurus Main Entry: heap Part of Speech: noun Definition: A group of things gathered haphazardly. Synonyms: agglomeration, cumulus, drift, hill, mass, mess, mound, mountain,
pile, shock, stack, tumble Roget's II: The New Thesaurus
Main Entry: heap Part of Speech: verb Definition: To put into a disordered pile. Synonyms: drift, hill, lump, mound, pile, stack
Text Mining
¿TM? Aproximación NLP Herramientas Reducción a técnicas de ML supervisado Ejemplos
Reducción a técnicas de ML supervisado
Reducir algunos problemas básicos de TM como problemas de clasificación en ML.
A partir del corpus construir un dataset con: Datos estructurados de contexto. Datos estructurales del texto. Bag of words del texto.
Hasta validación adecuada: Hacer resampling por filas y/o columnas. Aplicar diferentes métodos y evaluarlos. Ensamblar modelos compuestos y validarlos.
Reducción a técnicas de ML supervisado
id C e1 … ej i1 … … ik w1 … wn
1
2
…
m
Estru
ctura
dos
Estru
ctura
les
BoW
Reducción a técnicas de ML supervisado
Construir el BoW: Armar matriz de documentos x indicadores. Recorrer todos los documentos del Corpus.
Calcular y persistir indicadores: Párrafos por documento. Oraciones por párrafo. Signos de puntuación por párrafo y oración. Palabras por párrafo y oración. …
Identificar términos. Simplificar términos. Construir el diccionario de términos (+B&W lists).
Armar matriz documentos x términos (BoW). Recorrer todos los documentos del Corpus.
Calcular y persistir indicador por documento y término.
Reducción a técnicas de ML supervisado1. Te engañas si me quieres
confundir esta canción desesperada no tiene orgullo ni moral se trata sólo de poder dormir sin discutir con la almohada dónde está el bien, dónde está el mal.
2. La guerra que se acerca estallará mañana lunes por la tarde y tú en el cine sin saber quién es el malo mientras la ciudad se llana de árboles que arden y el cielo aprende a envejecer.
3. Ni los vientos son cuatro, ni siete los colores, y los zarzales crecen junto con las flores.
4. Y el sol sólo es el sol si brilla en ti. La lluvia sólo lluvia si te moja al caer. Cada niño es el tuyo, cada hembra, tu mujer.
id Clase #Sent #Simb #W …
1 A 1 2 33
2 A 1 1 37
3 B 1 3 17
4 B 3 5 29
Reducción a técnicas de ML supervisado1. Te engañas si me quieres
confundir esta canción desesperada no tiene orgullo ni moral se trata sólo de poder dormir sin discutir con la almohada dónde está el bien, dónde está el mal.
2. La guerra que se acerca estallará mañana lunes por la tarde y tú en el cine sin saber quién es el malo mientras la ciudad se llena de árboles que arden y el cielo aprende a envejecer.
3. Ni los vientos son cuatro, ni siete los colores, y los zarzales crecen junto con las flores.
4. Y el sol sólo es el sol si brilla en ti. La lluvia sólo lluvia si te moja al caer. Cada niño es el tuyo, cada hembra, tu mujer.
1. engañas si quieres confundir canción desesperada no tiene orgullo ni moral trata sólo poder dormir sin discutir almohada dónde está bien dónde está mal
2. guerra acerca estallará mañana lunes tarde cine sin saber quién es malo mientras ciudad llena de árboles arden cielo aprende envejecer
3. ni vientos son cuatro ni siete colores zarzales crecen junto flores.
4. sol sólo es sol si brilla lluvia sólo lluvia moja caer niño es hembra mujer
Reducción a técnicas de ML supervisado1. Te engañas si me quieres
confundir esta canción desesperada no tiene orgullo ni moral se trata sólo de poder dormir sin discutir con la almohada dónde está el bien, dónde está el mal.
2. La guerra que se acerca estallará mañana lunes por la tarde y tú en el cine sin saber quién es el malo mientras la ciudad se llena de árboles que arden y el cielo aprende a envejecer.
3. Ni los vientos son cuatro, ni siete los colores, y los zarzales crecen junto con las flores.
4. Y el sol sólo es el sol si brilla en ti. La lluvia sólo lluvia si te moja al caer. Cada niño es el tuyo, cada hembra, tu mujer.
1. almohada bien canción confundir desesperada discutir dónde dormir engaña está mal moral ni no orgullo poder quieres si sin sólo tiene trata
2. acerca aprende árboles arden cielo cine ciudad envejecer es estallará guerra llena lunes malo mañana mientras
3. colores con crecen cuatro flores junto ni siete son vientos zarzales
4. brilla cada caer es hembra lluvia moja mujer niño sol sólo
Reducción a técnicas de ML supervisado1. almohada bien canción
confundir desesperada discutir dónde dormir engañas está mal moral ni no orgullo poder quieres si sin sólo tiene trata
2. acerca aprende árboles arden cielo cine ciudad envejecer es estallará guerra llena lunes malo mañana mientras
3. colores con crecen cuatro flores junto ni siete son vientos zarzales
4. brilla cada caer es hembra lluvia moja mujer niño sol sólo
1. almohada bien canción confundir desesperada discutir dónde dormir engañar mal moral NEG orgullo poder POS querer ser sólo tener tratar
2. acerca aprender árbol arder cielo cine ciudad envejecer estallar guerra lunes llenar malo mañana mientras ser
3. color crecer cuatro flor junto NEG ser siete viento zarzal
4. brillar cada caer hembra lluvia mojar mujer niño ser sol sólo
Reducción a técnicas de ML supervisado
Id acerca almohada
aprender … ser tratar zarzal
1 1 1 1
2 1 1 1
3 1 1
4 1
Reducción a técnicas de ML supervisado
id C e1 … ej i1 … … ik w1 … wn
1
2
…
m
Resampling: columnas y/o filas
Text Mining
¿TM? Aproximación NLP Herramientas Reducción a técnicas de ML supervisado Ejemplos
Ejemplos
Clasificando Texto con NB Técnicas levemente supervisadas
Aumento de lexicones Aumento de ontologías Aumento de gramáticas
Técnicas no supervisada Descubrimiento de traducciones Descubrimiento de clases de palabras Enriquecimiento de lexicones
Ejemplo: Consideremos documentos de texto o de hipertexto T,
que se pueden clasificar en varias clases (ej: interesante, no-interesante) o en diferentes temas.
Definimos un atributo ai como cada posición i de cada palabra en el texto.
Clasificando Texto con NB
Debemos hacer la siguiente suposición FALSA: la probabilidad de una palabra es independiente de sus
precedentes y sus siguientes. Es decir, los P(ai|vj) son independientes entre sí. Falso, por ejemplo, con las palabras “por” y “ejemplo”.
Pero este supuesto no es tan grave en general y nos permite, utilizar el clasificador NB.
Clasificando Texto con NB
||
1},{)|()·(arg
T
ijiij
nosívNB vtaPvPmaxv
j
A primera vista, parece que: P(vj) es fácil de determinar (la proporción de documentos de
cada clase). P(ai=wk|vj), sin embargo, requeriría millones de casos para
tener una estimación. Otra suposición (más razonable):
las probabilidades son independientes de la posición Quitando las primeras y últimas, la probabilidad que una
palabra aparezca en la posición 45 es la misma que en la 87. Esto quiere decir que:
Lo que supone estimar únicamente las P(wk|vj). Es decir, la probabilidad de aparición de cada palabra según la clase.
Clasificando Texto con NB
mkjivwaPvwaP jkmjki ,,, todopara )|()|(
Volvemos a adoptar un m-estimado:
Donde n es el número total de posiciones de palabras en los ejemplos de entrenamiento (documentos) donde la clase es vj. En otras palabra, la suma de las longitudes (en nº de palabras) de todos los documentos de la clase vj.
Donde nk es el número de veces que se ha encontrado en estos documentos de la clase vj.
|Voc| es el número de palabras del lenguaje considerado (inglés, castellano, o lenguajes informáticos). Voc puede ser un subconjunto (se pueden eliminar palabras muy usuales: preposiciones, artículos, verbos muy comunes, etc.)
Clasificando Texto con NB
||1
||||
1||)|(
Vocnn
VocnVoc
Vocn
mnmpnvwP k
kk
jk
Otro problema es que todos los documentos deberían ser de la misma longitud para que fueran comparables.
A la hora de calcular NB los documentos cortos se replican hasta llegar a una longitud suficiente L, y/o los documentos largos se truncan aleatoriamente (se eligen L palabras al azar)
También se pueden eliminar palabras que aparecen muy pocas veces en los textos.
Clasificando Texto con NB
Dado E el conjunto de documentos de texto V: conjunto de clases v1, v2, ...,. Voc := palabras de E (w1, w2, ...) Calcular P(vj) y P(wk|vj) Para cada clase vj en V hacer:
docsj := subconjunto de E de la clase vj. P(vj) := | docsj | / | E | textj := concatenación de todos los elementos de docsj n := el número total de posiciones de palabras distintas en
textj Para cada palabra wk en Voc
nk := número de veces la palabra wk aparece en textj
Clasificando Texto con NB
||1)|(
VocnnvwP k
jk
Una vez aprendidas las probabilidades, simplemente se trata de aplicar el clasificador:
CLASIFY_NAIVE_BAYES_TEXT(Doc) Retorna la clase estimada para el documento Doc. (ai denota la palabra encontrada en la posición i de Doc). positions = todas las posiciones de palabra en Doc que
contienen palabras que se encuentran en Voc. Retorna vNB, donde
También sirve para categorizar (en vez de tomar el máximo, se puede elegir las clases que superen un límite, o las n más probables)
Clasificando Texto con NB
positionsi
jijVv
NB vaPvPvj
)|()·(maxarg
Aumento de lexicones
Reglas morfológicas para crear diccionarios para tagging Se caracterizan los diferentes paradigmas de palabras por
sus rasgos morfológicos (escucho, escuchas, escuchamos) En corpus, se encuentran todas las ocurrencias de una
palabra: Se identifica la raíz hipotetizando diferentes opciones dadas las
formas encontradas, mediante un árbol de sufijos (trie) Se asigna cada raíz a uno o más paradigmas, con diferente
fiabilidad, usando formas inambiguas del paradigma Si es necesario, se obtienen más ejemplos (pesados) de la web
Útil solamente para lenguas con rica morfología flexiva Desventajas: hay que construir los paradigmas a mano
Aumento de lexicones
Co-ocurrencia con otras palabras para obtener bolsas de palabras temáticas
Partimos de un pequeño diccionario temático donde cada tema está asociado a un conjunto de palabras (tenis -> raqueta, red, set)
Usamos palabras inambiguas (ej: sólo aparecen en una sola categoría)
Buscamos palabras que co-ocurren significativamente más con las palabras inambiguas de un tema (o con documentos asignados a un tema) (ej: Nalbandián)
Incorporamos estas palabras como indicadoras de tema (posiblemente, pensando su indicatividad con su ambigüedad)
Útil para categorización de textos, desmabiguación de sentidos, inducción de mapas conceptuales
Desventajas: es necesario tener un inventario de temas pre-definido
Patrones sintácticos para descubrir hipónimos e hipernóminos
N es_un N, N es_un _tipo_de N, N pertenece_a N (tigre es_un felino, Ernesto pertenece_a Docentes) Útil: si tenemos un corpus donde estos patrones
se dan significativamente: diccionarios, textos didácticos
Desventajas: alcance limitado, conocimiento típicamente enciclopédico (vs sentido común), multiplicidad de patrones posiblemente ambiguos
Co-ocurrencia para determinar adjunción a una ontología
Usando técnicas basadas en desambiguación de sentidos dada una palabra ambigua p de la ontología
Para todos los sentidos de p, buscamos otras palabras que estén asignadas únicamente a uno de sus sentidos (o hipo-sentidos o hiper-sentidos)
Recuperamos de la web la co-ocurrencia de p con cada una de la palabras ambiguas
Pesamos los sentidos de p por su co-ocurrencia con estas palabras ambiguas
Desventajas: la palabra tiene que estar previamente descrita en la ontología, escasez de palabras ambiguas
Co-ocurrencia para determinar adjunción a una ontología
Usando técnicas basadas en tematización Caracterizamos una rama de la ontología por las palabras
que se encuentran en ella, pensando la contribución de su palabra por su ocurrencia en otras ramas
Dadas las palabras de un documento que se encuentran en la ontología, determinamos la rama mayoritaria de un documento
Encontramos las palabras que no están en la ontología y que ocurren significativamente más con una rama que con el resto y las incorporamos a la ontología
Desventajas: las diferentes ramas de una ontología pueden co-existir en un mismo documento, cobertura desigual de las ontologías
Aumento de gramáticas
Bootstraping Pequeño recurso inicial (gramática o corpus) Se analiza un corpus mayor Se toman en cuenta los ejemplos con mayor fiabilidad Se aprende una gramática mayor
Co-training Pequeño recurso inicial (gramática o corpus) Se aprenden dos gramáticas diferentes Se analiza un corpus mayor Se toman en cuenta los ejemplos analizados igual por las
dos gramáticas Se aprenden gramáticas mayores
Traducción automática estadística Corpus paralelos (corpus con el mismo significado
en dos lenguas distintas: normativa del parlamento europeo)
Alineación: identificar correspondencias entre segmentos cada vez más chicos de los dos textos
Correspondencias entre palabras o secuencias de cada lengua:
palabra – palabra palabra – {} {} – palabra palabra palabra – palabra palabra palabra – palabra palabra
Asignamos una fiabilidad a cada correspondencia, según la cantidad de veces que la hemos visto en el corpus
Interpolación de modelos de diferente longitud y fiabilidad
Descubrimiento de clases de palabras
Caracterizar cada palabra p como un vector n-dimensional
Cada dimensión se corresponde con una de las palabras que ocurren en el texto
La dimensión n del vector que caracteriza a la palabra p contienen la probabilidad de co-ocurrencia de la palabra p con la palabra de la dimensión n
Descubrimiento de clases de palabras
Texto: “El gato come pescado. El pescado vive en el mar. El mar
está lleno de agua. A los gatos no les gusta el agua. A los gatos les gusta el pescado.”
Palabras a caracterizar: A El agua. come de el en está gato gatos gusta les lleno
los mar mar. no pescado pescado. Vive A El agua come de el en está gato gatos gusta les lleno
los mar no pescado vive a agua come de el está gato gatos gusta lleno los mar no
pescado vive a agua come de el está gato gusta les lleno los mar no
pescado vive agua come gato gusta lleno mar pescado vive
Descubrimiento de clases de palabras
agua come gato gusta lleno mar pescado vive
agua 1 1 1 1
come 1 1
gato 1 1 2 2
gusta 1 2 1
lleno 1 1
mar 1 1 1 1
pescado 1 2 1 1 1
vive 1 1 1
Descubrimiento de clases de palabras
Usar técnicas de clustering para encontrar grupos de significados
Determinar que vectores está más cercanos según un criterio de distancia matemática
Determinar que palabras está más cercanas según un criterio de distancia matemática
Determinar que palabras se parecen más entre si según un criterio de distancia matemática
Descubrimiento de clases de palabras
Cuestiones a tener en cuenta en clustering Selección de características (dimensión de los
vectores) Ni muchas, ni pocas Adecuadas al objetivo que pretendemos conseguir
Trabajar suficientes instancias de cada objeto para obtener representatividad estadística
Selección del criterio de distancia entre vectores Distancia euclídea: el más simple Coseno: el más usado con los mejores resultados Divergencia de Kullback-Leibler: no es una distancia sino
una diferencia de distribuciones de probabilidad También se pueden usar técnicas más sofisticadas,
como la descomposición de valores singulares
Enriquecimiento de lexicones
Problema inicial: la información de los lexicones computacionales es insuficientes para aplicaciones de conocimiento profundo
Objetivo: asociar a los ítems de los lexicones información sobre comportamiento respecto a las palabras circundantes
Obtener ocurrencias en corpus de las palabras que queremos enriquecer (ej: verbos) posiblemente analizadas (ej: análisis sintáctico, semántico)
Caracterizar las palabras-objetivo como vectores Aplicar técnicas de clustering o bootstraping para
encontrar clases de palabras con el mismo comportamiento sintáctico-semántico
Aprender un clasificador a partir de estas clases y estos ejemplos
Aplicarlo a palabras semejantes pero antes no vistas
Bootstraping para desambiguar sentidos
Se obtiene una lista de decisión de los ejemplos etiquetados
Reglas de asociación por clase Ordenadas por fiabilidad Basadas en las palabras de la oración
Se clasifican los ejemplos sin etiquetar Los ejemplos que se pueden clasificar pasan a los
etiquetados Se itera hasta que no se clasifiquen nuevos
ejemplos Si quedan ejemplos son clasificar
Se asigna a todos los ejemplos del documento el mismo sentido
Se itera
Web Mining
Web Mining se refiere al proceso global de descubrir información o conocimiento potencialmente útil y previamente desconocido a partir de datos de la Web.
Web Mining combina objetivos y técnicas de distintas áreas:
Information Retrieval (IR) Natural Language Processing (NLP) Data Mining (DM) Databases (DB) WWW research Agent Technology
¿Está la Información de la Web lo suficientemente estructurada para facilitar minería de datos efectiva?
Fases Descubrimiento de recursos: localización de documentos
relevantes o no usuales en la red. Ésta es la función de índices buscadores (extraen contenido en palabras, zona del documento, idioma) e índices temáticos (clasifican los documentos).
Extracción de información: extraer determinada información a partir de un documento, ya sea HTML, XML, texto, ps, PDF, LaTeX, FAQs, ....
Generalización: descubrir patrones generales a partir de sitios web individuales: clustering, asociaciones entre documentos.
Análisis, validación e interpretación de los patrones.
Web Mining
Dos aproximaciones: Recuperación de Información: :
Disparado por consulta (query-triggered) Es el objetivo de numerosas herramientas: buscadores e
índices. Las herramientas son clásicas estadísticas y ad-hoc....
Extracción de Información: Disparado por datos (data-triggered) Es una visión más ambiciosa del Web Mining Las herramientas son más generales y de aprendizaje
automático. IR persigue seleccionar documentos relevantes
mientras que IE persigue extraer hechos relevantes a partir de los documentos.
Web Mining
No sólo se requiere información relevante sino información de calidad o autorizada.
Para ello es importantísimo no analizar los documentos de forma inconexa, sino analizar su red de enlaces
Mucha información está en enlaces entrantes: muchas páginas no se autodescriben.
Ej: una página puede ser clasificada por los enlaces que le llegan (referentes), que suelen ir acompañados de una pequeña descripción de la página o junto a otros enlaces similares (clustering).
También (no tanta) información sobre la página se encuentra en enlaces salientes.
Web Mining
Web Content Mining: extraer información del contenido de los documentos en la web.
Se puede clasificar a su vez en: Text Mining: si los documentos son textuales (planos). Hypertext Mining: si los documentos contienen enlaces a otros
documentos o a sí mismos. Markup Mining: si los docs. son semiestructurados (con marcas). Multimedia Mining: para imágenes, audio, vídeo, ...
Web Structure Mining: se intenta descubrir un modelo a partir de la topología de
enlaces de la red. Este modelo puede ser útil para clasificar o agrupar documentos
Web Usage Mining: se intenta extraer información (hábitos, preferencias, etc. de los
usuarios o contenidos y relevancia de documentos) a partir de las sesiones y comportamientos de los usuarios y navegantes.
Web Mining
Las técnicas varían dependiendo del tipo de documento:
Text Mining: técnicas de recuperación de información (IR) fundamentalmente. Técnicas estadísticas y lingüísticas.
Hypertext Mining: no sólo se refiere a enlaces entre documentos sino también intro-documentos (OEM). Se ha de construir un grafo de referencias...
Markup Mining: La información de las marcas contiene información (HTML: secciones, tablas, negritas: relevancia, cursiva, etc., XML: mucho más...).
Multimedia Mining: algunos trabajos sobre bibliotecas de imágenes.
Web Content Mining
Extracción de Información a partir de XML. Distintos Objetivos:
Schema Extraction: Por esquema entendemos algo similar a un DTD o un XML-Schema, aunque representado con otros formalismos (programas lógicos, grafos, ...)
Dataguides: Especie de resumen estructurado de datos semiestructurados, a veces aproximado.
Multi-Layer-Databases (MLDB): Hay distintos niveles de granularidad en el esquema extraído. Se pueden construir lo que se denominan MLDBs, en la que cada capa se obtiene por generalizaciones de capas inferiores
Clasificación: Un documento XML (sin OIDs) es un árbol...
XML Mining
La cosa se complica si es XML con OIDs. La estructura del documento se debe representar como
un grafo y no como un árbol. Esto también puede ocurrir con documentos HTML u
otros que utilizan el Modelo de Intercambio de Objetos (OEM)
Grafo: Los nodos del grafo son los objetos, que están formados
de un identificador (oid) y un valor que puede ser atómico (entero, cadena, gif, html, ...) o referencia, denotado por un conjunto de pares (etiquetas, oid).
Las aristas del grafo están etiquetadas.
XML Mining
Ejemplo:
XML Mining
·oid1
·oid2
biblioteca
·oid5
·oid6
libro librolibro
...
‘El Quijote’oid9
título
escritor
·oid3
·oid4
escritor
‘Ausias March’
oid8
nombre
‘Cervantes’oid7
escrito_por
es_autor_de
nombre
Aparece el problema de “datos recursivos”
Equivalencia documento XML con una estructura relacional. El XML del ejemplo anterior:
XML Mining
<biblioteca oid= “&oid2” escritor= “&oid3 &oid4” libro= “&oid5 &oid6”> <escritor oid=“&oid3” es_autor_de=“&oid5 &oid6” nombre= “&oid7”> </escritor><escritor oid=“&oid4” es_autor_de=“&oid15” nombre= “&oid8”> </escritor><libro oid=“&oid5” escrito_por=“&oid3” titulo= “&oid9”> </libro><libro oid=“&oid6” .... ><nombre oid=“&oid7” > Cervantes </nombre><nombre oid=“&oid8” > Ausias March </nombre><titulo oid=“&oid9” > El Quijote </titulo>...</biblioteca>
obj value&oid7 “Cervantes”&oid8 “Ausias March”&oid9 “El Quijote”
... ...
source label dest&oid1 “biblioteca” &oid2&oid2 “escritor” &oid3&oid2 “escritor” &oid4&oid2 “libro” &oid5&oid2 “libro” &oid6&oid3 “es_autor_de” &oid5&oid3 “es_autor_de” &oid6&oid3 “nombre” &oid7&oid4 “es_autor_de” &oid15&oid4 “nombre” &oid8&oid5 “escrito_por” &oid3&oid5 “titulo” &oid9
... ... ...
Expresado relacionalmente:
eduardo-poggi
http://ar.linkedin.com/in/eduardoapoggi
https://www.facebook.com/eduardo.poggi
@eduardoapoggi
Bibliografía
Bramer, Max (2007): ‘Principles of Data Mining’, C15, Text Mining.
Presentaciones de Fernando Das Neves, FCEN 2009.
Alonso i Alemany, Laura (2008): Material de curso sobre Text Mining. SADIO, marzo de 2008.
Bibliografía
Desambiguar sentidos: Dan Yarowsky 1995: Unsupervised Word Sens Disambiguation Rivaling Supervised Methods. ACL95
Descubrimiento de sentido mediante clustering: Pantel, P and Lin, D 2002: Discovering Word Senses from Text. KDD02.
Descubrimiento de sentido mediante grafos: Veronis, J 2004: HyperLex: Lexical Cartograpy for information Retrieval. Computer, Speech and Language, 18.
Traducción automática estadísitica: Knight, Kevin: Statistical MT Handbook. Adquisición de paráfrasis: Barzilay, R and McKeown, K 2001: Extracting
paraphrases from a parallel corpus. ACL. Asociación de pares pregunta-respuesta: Echihabi, A and Marcu, D 2003: A
noisy-channel approach to question answering. Proceedings of 41st Annual Meeting of ACL, Sapporo, Japan.
Inducción de estructura: Sola, Z et all 2005: Unsupervised learning of natural languages. PNAS
Inducción de plantillas: Mark, Dagan and Shamir 2002: Cross-component Clustering for Template Induction. TextML 2002.
Minado de opiniones: Overview of the TREC 2006 Blog Track. Reconocimiento no supervisado de entidades con nombre: Turney, Matwin
2006: Unsupervised Named-Entity Recognition: generating gazetteers and resolvinf ambiguity. 16th Canadian Conference on AI.
Reconocimiento de relaciones entre entidades: Hasegawa et all 2004: Discovering Relations among Named Entities from Large Corpora. ACL.
Revistas (números especiales): Número Especial sobre Web Mining, June 2000, Vol. 2, nº1
de la revista ACM SIGKDD Explorations, Newsletter of the ACM Special Interest Group on Knowledge Discovery and Data Mining
Número Especial sobre Recommender Systems, Communications of the ACM, Vol. 40, no. 3, 1997.
Número Especial sobre Personalization, Communications of the ACM, Vol. 43, no. 8, 2000.
Páginas web: Información sobre XML y leng. de consulta:
http://www.w3.org/ Información sobre Web Mining: http://www.webminer.com/ Información sobre Intercambio de Conocimiento:
Standards and Industry Associations for Data Mining and Decision Support: http://www.kdnuggets.com/websites/standards.html
Bibliografía