Proyecto de Mineria - NMF

AEA(Aplicaciones Empresariales Avanzadas)Grupo SIE

PROYECTO DE MINERIA:Busqueda de características independientes

(Factorización de matrices no negativas)

Alumnos: Carlos Meseguer Gimenez Versión 1.0Email: [email protected] de prácticas: Turno L 14:00 09 de mayo de 2009

Departamento Economía Financiera, Contabilidad y Marketing

Proyecto de mineria - NMF Versión 1.0

INDICE DE CONTENIDO

0. Introducción a la búsqueda de características independientes.0.1. ¿Qué es y para que sirve?0.2. Ventajas que aporta al Cliente

1. Compresión del Negocio1.1. Descripción de la naturaleza de los datos1.2. Objetivos de Minería

2. Compresión de los Datos2.1. Descripción de la fuente (ficheros, enlaces)2.2. Verificaciones de los datos, gráficos estadísticos, etc..

3. Preparación de los Datos3.1. Descripción sobre la manipulación de los datos3.2. Vista minable definitiva

4. Modelado4.1. Tipo de tarea de minería a realizar4.2. Técnica o técnicas utilizadas

5. Evaluación de los resultados5.1. Análisis de los resultados obtenidos de los modelos

6. Conclusiones del proyecto

Proyecto de mineria - NMFGrupo SIE

Alumno: Carlos MeseguerGrupo prácticas: Turno L 14:00 Pág. 2 Fecha:09/05/2009

http://www.sie.ua.es/



0. INTRODUCCIÓN A LA BÚSQUEDA DE CARACTERÍSTICAS INDEPENDIENTES.

0.1 ¿Qué es y para que sirve?

En este proyecto voy a tratar de extraer de forma automática y no supervisada las características que definen un conjunto de datos. Un ejemplo muy ilustrativo para este acercamiento a la minería es “el efecto de la fiesta ruidosa”, y no es más que interpretar la conversación en una fiesta, en la que muchas personas hablan, hay música y otros ruidos. Nuestra mente es capaz de aislar los diferentes sonidos e identificarlos como cosas diferentes, aunque nuestra “entrada de información” sean solo los oídos. Aplicando los algoritmos con los que vamos a trabajar a este problema, podríamos llegar a diferenciarlos con un ordenador.

En este caso, voy a trabajar con información sobre películas, estos datos son las sinopsis, críticas,etc de las mismas y el objetivo es lograr aislar los temas de los que tratan con únicamente estos textos.

0.2 Ventajas que aporta al Cliente

Con los resultados de este proceso, podríamos describir mejor las películas de una manera automática. Dando un valor añadido a la información que ya se tiene de las mismas. Algunas aplicaciones potenciales que podríamos darle son: generar directorios sin supervisión humana, añadir palabras clave para poder ofrecer resultados más sofisticados para búsquedas o utilizar estos resultados para relacionar las películas y usos en otros procesos útiles para el cliente.

1. COMPRESIÓN DEL NEGOCIO

1.1 Descripción de la naturaleza de los datos

Los datos provienen de la información disponible acerca de las películas del portal de cine cinecin.com y se componen de la siguiente información:

– Sinopsis de la película– Genero de la película– Críticas de la película– Comentarios de los visitantes del portal a la películaAunque es importante tener en cuenta la naturaleza de los mismos, ya que de los

cuatro tipos de datos, solo los dos primeros (sinopsis y genero) están disponibles para todas las películas, el resto, son opcionales.

Ademas, los comentarios no pasan ningún filtro, por lo que en algunas ocasiones, puedes ser, en principio, irrelevantes.






1.2 Objetivos de Minería

El objetivo del proyecto, es generar un numero determinado de características que nos permitan definir los temas de los que tratan las películas. Este numero podemos especificarlo en función de las necesides.

Es importante señalar, que definiendo n características, lo que estaríamos haciendo es definir todas las películas en base a esas n características. Por otro lado, cada una de las características se compone por una lista de palabras. Por ejemplo, si obtuviésemos que una de las características es “Conflicto, armas, dinero, petroleo,dictadura,censura”, podríamos decir que habla sobre la situación de oriente medio.

Por lo tanto, el objetivo es crear unos temas generales para las películas, por lo tanto, luego habría que analizar experimentalmente los resultados, para crear un numero suficientemente alto de categorías para que aporten algo de información y suficientemente bajo para que no sean demasiado concretas.

2. COMPRESIÓN DE LOS DATOS

2.1 Descripción de la fuente (ficheros, enlaces)

La fuente de datos es una base de datos que sigue el modelo ERR con la cual trabaja el portal de cine cinecin.com.

Vamos a trabajar sobre 1519 películas que tiene 503 comentarios y 333 críticas.

Sobre la información que voy a utilizar, cabe decir una cuantas cosas.

La sinopsis y el genero de las películas es una información aportada por las distribuidoras. Es la típica información que podemos encontrarnos detrás de los DVD's. Esta información es oficial y ademas, la mayor parte de las empresas del sector, manejan la misma. Puede ser importante tener en cuenta la oficialidad de los datos para valorar la veracidad de los resultados, ya que en este texto, por lo general, van a describir la película “demasiado” correctamente. Por otro lado, el vocabulario que se tiende a utilizar esta más acotado y generalmente da unas pinceladas generales, lo que ayuda al objetivo que tenemos.

Las críticas son colaboraciones de los visitantes del portal, que han sido supervisadas antes de ser añadidas. Tienen un estilo formal y están revisadas antes de añadirse, lo que es importante por el funcionamiento del algoritmo. Aproximadamente un 21 % de las películas tienen crítica y algunas de ellas, tienen varias.






Por último, están los comentarios, de toda la información es la más dispar. La fuente de los mismos son los visitantes, algunos son espontaneos y el único filtro que pasan es seguir unas reglas básicas de civismo y respeto, por lo que, como he comentado anteriormente, existe el riesgo, que en ocasiones sean irrelevantes. Aunque es el punto de contacto con la opinión real de los visitantes, por lo que por ello, he creído conveniente incluirlo en el proceso. Las películas con comentarios son aproximadamente el 18%. Aunque aquí el reparto no es homogéneo, ya que un 72% no tienen comentarios y las que tienen comentarios, tienden a acumular un numero alto de ellos.

2.2 Verificaciones de los datos, gráficos estadísticos, etc..

Los datos antes de llegar aquí, ya han pasado un proceso de filtrado y normalización. Ademas, por la naturaleza del algoritmo y al tratarse de textos, no ha sido necesario realizarles ningún proceso de verificación. Aunque para una mejor comprensión de los mismos por parte del lector, voy a dar unos cuantas datos sobre ellos.

Descripción Numero Porcentaje sobre el totalPelículas 1519 100%

Críticas 333 100%

Comentarios 503 100%

Películas con comentario 262 17,24%

Películas con más de 1 comentario 47 3,09%

Película con más de 5 comentarios 12 0,7%

Películas con más de 10 comentarios 4 0,26%

Películas con critica 324 21,32%

Películas con más de 1 crítica 13 0,8%






3. PREPARACIÓN DE LOS DATOS

3.1 Descripción sobre la manipulación de los datos

Como ya he comentado anteriormente, la fuente de datos es una base de datos mysql con un esquema relacional. El modelo de los mismos es el siguiente:

Aunque es una vista parcial del modelo completo, es bastante similar a un esquema en estrella, por lo que fácilmente podríamos atacar directamente los datos.

No obstante, si lo hiciésemos, al no tener la infraestructura necesaria, saturaríamos enormemente el servidor, por lo que para permitir un uso independiente he optado por introducir una fase intermedia, y así no atacar al motor mysql.

Mediante un simple script, he creado un fichero xml para cada película, el cual, sigue el estándar RSS. Aunque haber implementado un parser XML no es complicado, por motivos de tiempo he creído mejor opción usar un parser ya desarrollado, y de entre ellos, los que más rapidez ofrecían, eran los de RSS.

El susodicho fichero es muy simple. Los nombres de los archivos van de 1.xml al 1518.xml y su estructura interna es la siguiente:






<?xml version='1.0' encoding='ISO-8859-1' ?><rss version='2.0'>

<channel><title>

TITULO ( TITULO ORIGINAL)</title><link>

ID PELICULA</link>

</channel><item>

<title>TITULO (TITULO ORIGINAL)

</title><description>

GENEROSSINOPSISCRITICASCOMENTARIOS

</description></item>

</rss>

3.2 Vista minable definitiva

Lo que hacemos a continuación, es recorrer los ficheros, realizando un conteo de las palabras que aparecen en cada película. Esto lo vamos integrando en una matriz, en la que cada fila representa una película y cada columna representa una palabra. Por lo que el valor [i][j] de esta matriz, que llamaremos Matriz de películas, sera el numero de veces que aparece la palabra [j] en la película [i].






4. MODELADO

4.1 Tipo de tarea de minería a realizar

A partir de la matriz anterior, nuestro objetivo es extraer características independientes de cada película. Esto, no es otra cosa, que intentar hacer emerger los temas de los que tratan las películas.

Para lograr esto, lo que vamos a intentar es lograr dos matrices que multiplicadas, den un resultado lo más aproximado posible a la matriz de películas.

Estas matrices son la matriz de características y la matriz de pesos. Ambas con información muy interesante.

La primera, la matriz de características, nos va a generar los temas. Un tema no es otra cosa que una colección ponderada de palabras, es decir, nos va a decir como de importante es cada palabra para un tema en concreto. Tal vez sea importante dejar claro, que no vamos a obtener un nombre para el tema, sino que el tema estará definido por las palabras más importantes para el mismo.

La segunda, la matriz de pesos, nos va a decir la importancia que tiene cada una de las características anteriormente comentadas, para una película en concreto.

4.2 Técnica o técnicas utilizadas

El algoritmo que he utilizado para obtener estas matrices se llama factorización de matrices no negativas (Non negative matrix factorization) y es utilizado para el análisis de datos multivariante.

Este algoritmo toma como entrada la matriz de películas , el numero de iteraciones que queremos que haga (posteriormente ampliare esto), y el numero de características que queremos encontrar.

El algoritmo nos garantiza una solución, pero no nos permite acotar el error máximo que queremos, es decir, siempre nos da una solución, pero no necesariamente






tiene que ser útil. Cuantas más iteraciones hagamos, la solución obtenida sera mejor. De todas formas, en pocas iteraciones, el error decrece a un ritmo de orden similar a la inversa de la exponencial.

Aunque no voy a entar en los fundamentos matemáticos del algoritmo, si voy a explicar cual es su funcionamiento.

El proceso comienza generando la matriz de características y la matriz de pesos con unos valores aleatorios.

Tras esto, las multiplica y calcula la diferencia que hay entre el resultado y la matriz de películas. Para esto utilizamos una función de coste, que no es otra cosa que la distancia euclídea entre el resultado de la multiplicación y la matriz de películas que habíamos obtenido en un primer momento.

Para continuar el algoritmo necesita 4 matrices auxiliares, que llamaremos HN, HD, para la matriz de características y WN,WD para la matriz de pesos. Estas matrices se definen de la siguiente forma:

HN = Transpuesta(Matriz de pesos) x Matriz de PelículasHD = Transpuesta(Matriz de pesos) x Matriz de pesos x Matriz de CaracterísticasWN = Matriz de Películas x Transpuesta(Matriz de Características)WD = Matriz de pesos x Matriz de Características x Transpuesta(Matriz de Características)

Con estas matrices, reconstruye la matriz de características y la matriz de pesos hasta que la multiplicación de estas sea exactamente igual a la matriz de películas o haya realizado el proceso un numero n de veces, determinado al comienzo.

Para regenerar las matrices, hace el siguiente cálculo:

Matriz de características = Matriz de características x HN/HDMatriz de pesos = Matriz de pesos x WN/WD

En cada iteración, siempre se obtiene un mejor resultado, aunque el coste computacional es muy elevado, ya que multiplicar matrices es un proceso muy lento. Aquí tenemos un gran cuello de botella con el cálculo del error entre las dos matrices antes mencionadas. Por lo que para agilizar la ejecución, solo calculo el error finalizadas las iteraciones, consiguiendo así mayor velocidad. No es descartable que este “parche” pueda producir problemas.






5. EVALUACIÓN DE LOS RESULTADOS

5.1 Análisis de los resultados obtenidos de los modelos.

He realizado varias ejecuciones del algoritmo variando el numero de características y el numero de iteraciones del mismo, para poder comprar los resultados y así hacer una comparación de los resultados.

Concretamente he realizado tres ejecuciones, una buscando 20 características y realizando 5 iteraciones, otra con 40 características y también 5 iteraciones y por último buscando 100 características y con 10 iteraciones.

Debido a que realizar un analisis en profundidad de los resultados requeriría mucho tiempo, he optado por coger 4 películas representativas.

Por un lado, voy a analizar los resultados de la película con más críticas. Con esto obtendremos una muestra sobre como se comporta el algoritmo disponiendo de textos en un lenguaje formal.

Otro aspecto interesante a analizar, es como se comporta teniendo muchos textos pero que no han pasado filtros, por lo que analizare también la película con más comentarios.

Creo que también es importante analizar los resultados para la película que más consultas tiene, ya que nos puede servir de muestra para ver cuanto de interesante puede ser para los visitantes del portal.

Y por último, la película con menos visitas, que ademas no tiene ni comentarios ni críticas. Con esto podremos observar el comportamiento del algoritmo en la situación extrema, en la cual dispone del mínimo de información posible.

Las películas que cumplen los anteriores criterios son:Más críticas - MonstruosoMás comentarios - La niebla de Stephen King Menos visitas - Asesinato JustoMás visitas - Los Edukadores






Los datos obtenidos son los siguientes:



Monstruoso1 2 3

Datos Peso Característica Peso Característica Peso Característica

20 C. - 5 I. 24,4 19,1 16,7

40 C. - 4 I. 36,0 33,6 23,4

100 C. - 10 I. 108,5 99,3 80,7

'alatriste', 'visto', 'cuando', 'parece',

'mundo', 'monstruoso'

historia', 'guerra', 'joven',

'personajes', 'final', 'familia'

mundo', 'mucho', 'personajes',

'entre', 'bastante', 'tanto'

'monstruo', 'historia',

'monstruoso', 'todos', 'visto',

'buena'

'superman', 'final', 'entre', 'hasta', 'monstruoso',

'fiesta'

'barcelona', 'pelicula', 'cuando',

'historia', 'mundo', 'hasta'

'monstruo', 'monstruoso',

'fiesta', 'cloverfield', 'visto', 'bruja'

'monstruoso', 'blair', 'david',

'visto', 'mucho', 'fiesta'

'monstruo', 'monstruoso',

'bastante', 'cloverfield',

'pelicula', 'provoca'

La niebla de Stephen King1 2 3


20 C. - 5 I. 9,9 8,2 7,8

40 C. - 4 I. 16,7 12,3 11,6

100 C. - 10 I. 9,2 7,4 3,4



personajes', 'historia', 'hasta', 'culas', 'entre',

'cuenta'

culas', 'donde', 'guerra', 'final', 'decir', 'mundo'

historia', 'desde', 'buena', 'director',

'final', 'entre'

drama', 'desde', 'donde', 'tiene', 'cuando', 'culas'

espectador', 'leonor', 'aunque', 'donde', 'mucho',

'elijah'

guerra', 'esteban', 'islas', 'hechos', 'tiene', 'thriller'

sobre', 'documental',

'historia', 'mundial',

'muchas', 'armas'

stanley', 'shrek', 'guerra', 'trabajo', 'hijas', 'animaci'






Los Edukadores1 2 3


20 C. - 5 I. 4,2 3,6 3,1

40 C. - 4 I. 8,4 7,2 4,0

100 C. - 10 I. 28,2 15,1 12,0

tiene', 'comedia', 'donde', 'final',

'menos', 'mucho'

personajes', 'historia', 'hasta', 'culas', 'entre',

'cuenta'

tiene', 'alatriste', 'buena', 'mejor', 'parte', 'primera'

espectador', 'leonor', 'aunque', 'donde', 'mucho',

'elijah'

cuando', 'tiene', 'alatriste', 'puede', 'parece', 'aunque'

barcelona', 'pelicula', 'cuando',

'historia', 'mundo', 'hasta'

peter', 'garfio', 'wendy', 'viaje', 'james', 'donde'

dupree', 'mientras', 'amigo', 'trabajo', 'donde',

'molly'

cuando', 'entre', 'barrie', 'familia', 'sobre', 'durante'

Asesinato justo1 2 3


20 C. - 5 I. 0,3 0,2 0,2

40 C. - 4 I. 0,8 0,3 0,3

100 C. - 10 I. 2,5 1,3 1,3

mejor', 'hasta', 'hacer',

'superman', 'drama', 'tiempo'

barcelona', 'tiene', 'aunque',

'cuando', 'hasta', 'culas'



aunque', 'historia', 'superman',

'hacer', 'donde', 'alatriste'

personajes', 'mucho', 'todos',

'siempre', 'mundo', 'tanto'

cuando', 'polic', 'historia',

'phoenix', 'guerra', 'siempre'

scully', 'serie', 'mulder', 'extra', 'historia', 'relaci'

familia', 'guerra', 'entre', 'drama', 'islas', 'soldados'

gangster', 'parte', 'roberts', 'tambi',

'frank', 'personaje'




Al analizar estos datos, observamos varias cosas:

1. Subiendo mucho el numero de características corremos el riesgo de que se adapten en exceso a una película en concreto. Sobre todo a las que tienen mucha información. Esto podemos observarlo en la tabla de monstruoso, al ver por ejemplo, que en la fila de las 100 características, las palabras clave llegan a referirse en exclusiva al título de la película.

2. El algoritmo funciona como se espera en películas con muy poca información. No logra sacar características relevantes para ella. Debido a esto, no obtiene ninguna característica con un peso digno de consideración. Esto por un lado es bueno, ya que nos permite descartar información inútil, pero por otro lado, dejamos al margen a un volumen grande de las películas.

3. Con un numero pequeño de características, corremos el riesgo de que las mismas sean demasiado generales, y que realmente no se adapten bien a ningún conjunto de películas.

4. Según mi criterio, el mejor conjunto de datos obtenidos, es con 40 características, ya que obtenemos información relevante sin llegar a ser demasiado particular.

5. Obtenemos buenos resultados con las películas con un volumen de información medio-alto.






6. CONCLUSIONES DEL PROYECTO

Tras el análisis de los datos obtenidos con el algoritmo de factorización de matrices no negativas aplicado a la minería de texto para detectar los temas de los que tratan las películas creo que las expectativas se han cumplido moderadamente bien.

Para explotarlo de una manera seria, creo que habría que realizar un análisis con más detenimiento de los resultados obtenidos, aunque con la información actual creo que estoy en disposición de extrapolar algunas reflexiones interesantes.

Por un lado, creo que su aplicación seria ideal con una base de datos donde todas las películas tuviesen una cantidad de información relativamente homogenea, ya que sino, las que tienen más generan una condensación de características, lo que obliga, a que todas sean definidas en función de las primeras.

Habría que definir algún mecanismo automático para buscar el numero de características optimas.

Respecto al funcionamiento del algoritmo, habría que indagar sobre funciones más eficientes para medir la diferencia entre dos matrices, ya que el coste computacional de la que estamos usando es tremendo, haciendo de cuello de botella.

En cuanto a las posibles aplicaciones, son numerosas, por citar algunos ejemplos integrar los resultados en las búsquedas, categorizar las películas, ofrecer a los visitantes películas que tratan de temáticas similares, etc.




Documents

Proyecto de Mineria - NMF