Repositorio Institucional de Documentos

Proyecto Fin de Carrera Ingenier´ıa en Inform´atica SISTEMA ANALIZADOR Y RECOMENDADOR DE BLOGS Luis Latasa Yuste Director: Gregorio de Miguel Casado Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza Zaragoza, Septiembre de 2011 Resumen La naturaleza libre de Internet ha propiciado que la b´usqueda y seguimiento eficaces de informaci´on especializada se constituya en una tarea cada vez m´as compleja de abordar, debido esencialmente a su crecimiento masivo y sostenido. Este proyecto aborda la creaci´on de un prototipo software que facilita la suscripci´on del usuario a sitios web determinados para recibir de forma proactiva, notificaciones sobre textos objeto de inter´es. El sistema se entrena a partir de un conjunto de casos de entrenamiento y la retroalimentaci´on progresiva producida por la incorporaci´on de las nuevas lecturas que el usuario cataloga como de inter´es. El idioma de los textos a analizar y recomendar ser´a el castellano, debido a su riqueza ling¨u´ıstica. La presente memoria contiene el trabajo realizado en los siguientes aspectos: Una b´usqueda de informaci´on relacionada con los aspectos b´asicos del proyecto, en la que se abordan aspectos ling¨u´ısticos propios del castellano que permiten explotar informaci´on invariante en el lenguaje, algoritmia para procesamiento de lenguaje natural en el contexto del an´alisis y catalogaci´on de textos, aspectos relacionados con la escalabilidad para la gesti´on de grandes flujos de informaci´on, y cuestiones de paralelismo propias de la implementaci´on de sistemas de informaci´on. El estudio preliminar de estas cuestiones ha permitido elaborar una propuesta de arquitectura del sistema que organiza en bloques funcionales el tratamiento de la informaci´on, los flujos de datos y las posibilidades de paralelizaci´on. Esto ha conducido a una implementaci´on de un prototipo del sistema, para el que se ha realizado una evaluaci´on en cuanto a escalabilidad mediante un conjunto de experimentos ejecutados en plataformas computacionales heterog´eneas. Como ´ultima secci´on de la parte principal de la memoria se proponen las conclusiones extra´ıdas del trabajo. Finalmente, los anexos de la memoria recogen informaci´on espec´ıfica sobre la algoritmia de Aprendizaje utilizada as´ı como las decisiones concretas de dise˜no e implementaci´on. i ii Agradecimientos A Gregorio de Miguel, por haberme brindado la oportunidad de hacer este proyecto, por tu ayuda en todo momento, por tus consejos y tus charlas en Skype para resolver todas mis dudas. Al Proyecto TIN2008-06582-C03-02 - “Secuencias Simb´olicas: An´alisis, Aprendizaje, Miner´ıa y Evoluci´on”, del Ministerio de Ciencia e Innovaci´on, y al Grupo de Ingenier´ıa de Sistemas de Eventos Discretos (GISED), por el soporte prestado para la realizaci´on del trabajo. A Laura, mi bella doctora, por este a˜no y medio, por estar segura en todo momento de que iba a poder con todo, por darme ´animos y porque cuando se est´a agobiado, una sonrisa amable es lo que m´as se agradece. A mis amigos del CPS, por todos los buenos momentos, las risas y los caf´es que han hecho de mi carrera los mejores a˜nos de mi vida. A Elisa, Miguel ´ Angel y Mar´ıa, por los caf´es en el Anika’s, las cervezas en “Casa Chen” y tantos otros ratos de risas. Hab´eis sido mi momento de liberaci´on en muchas tardes de estudio. A mi familia, por vuestro ´animo, apoyo incondicional y confianza en que mi trabajo llegar´ıa a buen puerto. Como no, a mi t´ıo Fran por tus consejos y comentarios en la elaboraci´on de esta memoria. Muy en especial, a mis padres, porque aunque a veces hay´ais sido un poco “pesadillas”, me record´ais que las cosas no se hacen solas. Por vuestro cari˜no, por escucharme y aconsejarme, por todo lo que durante toda mi vida hab´eis hecho por m´ı. Y, por supuesto, a todos los que olvido nombrar. ¡Muchas gracias a todos! iii iv ´ Indice general Resumen I Agradecimientos III 1. Introducci´on 1 1.1. Motivaci´on .................................. 1 1.2. Objetivos del proyecto y estructura de la memoria ............ 2 2. Estado del arte 5 2.1. An´alisis ling¨u´ıstico .............................. 5 2.2. Tecnolog´ıas para la creaci´on de sitios Web ................. 6 2.3. T´ecnicas en aprendizaje orientadas a la clasificaci´on de textos ...... 7 3. Propuesta de la arquitectura del sistema 9 3.1. Procesamiento ling¨u´ıstico .......................... 10 3.2. Algoritmia de aprendizaje .......................... 12 3.3. Gesti´on de flujos de informaci´on ...................... 12 3.4. Paralelizaci´on de tareas ........................... 13 4. Prototipo del sistema 15 4.1. Primera aproximaci´on ............................ 15 4.2. Elecci´on de las tecnolog´ıas .......................... 16 5. Implementaci´on 19 5.1. Implementaci´on de la vista ......................... 19 5.1.1. La p´agina web ............................ 19 5.1.2. El control de p´agina web ...................... 20 5.2. Implementaci´on del control: Motor de recomendaciones .......... 20 5.2.1. El recomendador ........................... 21 5.2.2. La m´aquina SVM ........................... 21 5.2.3. El lematizador ............................ 22 v vi ´ Indice general 5.2.4. El m´odulo de comunicaci´on con el diccionario de Zirano ..... 22 5.3. Implementaci´on del modelo: Capa de acceso a datos ........... 22 5.4. Paralelizaci´on de tareas ........................... 24 6. Evaluaci´on del prototipo. Experimentos 27 6.1. Descripci´on del experimento ......................... 27 6.1.1. Conjunto de datos de entrada .................... 27 6.1.2. Presentaci´on del hardware ...................... 28 6.2. Descripci´on de los resultados ........................ 29 7. Organizaci´on del proyecto 33 8. Gesti´on del Proyecto y Conclusiones 35 Anexos 37 A. Manual de usuario 39 A.1. Estructura de la p´agina ........................... 39 A.2. Gesti´on de blogs ............................... 40 A.3. Entrenamiento del sistema .......................... 40 A.3.1. Gesti´on de categor´ıas de textos ................... 41 A.3.2. Gesti´on de textos de ejemplo .................... 42 A.3.3. Entrenamiento del sistema ...................... 43 A.4. Recomendaciones ............................... 44 B. Relaci´on de clases del sistema 47 C. La M´aquina de Vectores de Soporte 49 C.1. Introducci´on .................................. 49 C.2. Las funciones Kernel ............................. 51 C.3. El SubString Kernel ............................. 52 D. La p´agina web 55 D.1. La carpeta Web Content ........................... 56 D.1.1. La carpeta base ............................ 56 D.1.2. Los archivos XML .......................... 57 D.1.3. Las carpetas blog y svm ....................... 57 D.1.4. Proceso de construcci´on de una pantalla .............. 58 D.2. El m´odulo Java de gesti´on .......................... 59 ´ Indice general vii E. El motor de recomendaciones 61 E.1. El paquete recomendaciones ......................... 62 E.1.1. La interfaz remota .......................... 62 E.1.2. El recomendador ........................... 63 E.1.3. La excepci´on BCatalogException .................. 66 E.1.4. El actualizador ............................ 67 E.2. El paquete svm ................................ 67 E.2.1. El paquete original de Weka ..................... 68 E.2.2. Matriz de clasificadores binarios .................. 68 E.2.3. La clase BinarySMO ......................... 68 E.2.4. El m´etodo BuildClassifier ...................... 69 E.2.5. El m´etodo DistributionForInstance ................. 70 E.2.6. Modificaciones realizadas al algoritmo original .......... 71 E.3. Clase Zirano .................................. 74 E.4. El paquete ´util ................................ 75 E.4.1. Interfaz para el manejo de blogs .................. 75 E.4.2. Manejo de c´odigo HTML ...................... 76 E.4.3. Utilidades de conversi´on ....................... 77 E.4.4. La clase es Stemmer ......................... 78 F. El sistema de gesti´on de la persistencia 79 F.1. La base de datos ............................... 79 F.2. El paquete de acceso a datos ........................ 81 G. La paralelizaci´on de tareas en detalle 85 G.1. Paralelismo en el Kernel SSK ........................ 85 G.2. Paralelismo en la clase BinarySMO ..................... 87 G.2.1. El m´etodo buildClassifier ...................... 88 G.2.2. El m´etodo SVMOutput ....................... 90 G.3. Paralelismo en la clase SMO ......................... 91 G.4. Consideraciones sobre las alternativas ................... 92 G.5. Implementaci´on de las mejoras ....................... 93 H. Evaluaci´on del prototipo. Experimentos 95 Bibliograf´ıa 103 6´ Indice general Repasados estos conceptos clave, se pasa a comentar algunas de las herramientas para el procesamiento del lenguaje natural que se han encontrado: Diccionarios online: De acceso p´ublico, facilitan mucha informaci´on sobre una palabra: significado, sin´onimos, familia l´exica a la que pertenece, informaci´on sobre su etimolog´ıa, e incluso foros de discusi´on en los que se discute sobre su correcto uso. Algunos ejemplos de estos diccionarios son el ofrecido por la Real Academia Espa˜nola [3], o WordReference [4], un sitio web en el que se pueden encontrar diccionarios de traducci´on entre m´ultiples idiomas, y que contienen adem´as un foro para resolver dudas entre sus usuarios. Diccionario ideol´ogico de Zirano: Tambi´en de acceso p´ublico y gratuito, Zirano [5] ofrece la posibilidad de buscar palabras tanto para obtener su significado como para obtener su campo conceptual. Dada una palabra, sugiere una lista de ideas a la que puede estar asociada, y, tras elegir una de ellas, proporciona un conjunto de palabras relacionadas. 2.2. Tecnolog´ıas para la creaci´on de sitios Web Debido a la relaci´on del proyecto con Internet ha sido necesario de un estudio de las distintas alternativas existentes para la creaci´on de sitios web. Se definen a continuaci´on algunos t´erminos relacionados con las tecnolog´ıas que se asocian a la gesti´on de informaci´on que son objeto de inter´es del proyecto. Sistema de gesti´on de contenidos: (CMS, del ingl´es Content Management System). Proporciona una interfaz de administraci´on en la que el propietario del sitio puede a˜nadir contenidos, gestionar los men´us laterales, insertar enlaces a otras p´aginas, cambiar la apariencia de la web, etc. Los CMS est´an creados para ser utilizados sin necesidad de poseer conocimientos de inform´atica. El propietario puede modificar el sitio web con un simple clic y a˜nadir contenidos como si de un procesador de textos se tratase. Blog: Es un tipo de CMS en el que los textos publicados aparecen estructurados uno tras otro en la p´agina principal. Se utiliza frecuentemente cuando lo que se pretende es dar continuidad en el tiempo, dar a conocer hechos que pueden estar relacionados y mostrar esa relaci´on. Wordpress [6] y Blogspot [7] son algunos de los servicios gratuitos de creaci´on de blogs m´as importantes en la actualidad. Post: Coloquialmente se llama post a un texto que se publica en un blog. De esta forma se deja que el t´ermino p´agina se refiera a una secci´on independiente, ´ Indice general 7 mostrada en exclusividad (sin otros posts ni p´aginas debajo ni encima). As´ı, una misma web puede tener p´aginas independientes, estar estructurada como blog (un post debajo de otro), o utilizar una estructura mixta. En cuanto a las herramientas para la creaci´on de sitios web, existe una gran variedad de alternativas gratuitas. Se comentan a continuaci´on algunas de ellas, orientadas tanto a usuarios sin conocimientos t´ecnicos de inform´atica como a desarrolladores. Herramientas de usuario: Un usuario sin conocimientos t´ecnicos inform´aticos puede crear un blog registr´andose en Blogspot [7] o en Wordpress [6]. Tras registrarse en el servicio y obtener un nombre de usuario y contrase˜na, puede entrar en su panel de administraci´on y empezar a publicar. Herramientas para usuarios intermedios: Para un nivel mayor de personalizaci´on, existen CMS disponibles para descarga que pueden instalarse en el servidor web que el usuario tenga contratado. Este tipo de instalaci´on proporciona al usuario la posibilidad de modificar el c´odigo fuente, crear sus propias extensiones, o instalar otras existentes para a˜nadir funcionalidades que no vienen por defecto. Algunos de estos CMS son Xoops [8], Joomla [9], PHP-Nuke [10] o la versi´on instalable de Wordpress [11], todos ellos gratuitos. Herramientas para programadores: En ocasiones un programador puede necesitar desarrollar su propio CMS. Existen frameworks gratuitos que pueden ser utilizados como punto de partida para el desarrollo. Un ejemplo de este tipo de software es CodeIgniter [12], escrito en PHP y basado en el patr´on de dise˜no MVC (Model-View-Controller). Incluye, entre otras utilidades, las de criptograf´ıa, compresi´on de archivos etc. 2.3. T´ecnicas en aprendizaje orientadas a la clasificaci´on de textos Buscando documentaci´on acerca de las distintas t´ecnicas en aprendizaje orientadas a la clasificaci´on de textos, se ha encontrado abundante documentaci´on al respecto. Existen t´ecnicas de Data Mining mediante las cuales se obtiene informaci´on no trivial a partir del an´alisis exhaustivo de muchos datos de ejemplo disponibles. El Data Mining puede aplicarse a diferentes tipos de datos como enteros, n´umeros en coma flotante, cadenas de texto y otros objetos m´as avanzados, como se explica en el libro Data Mining: Concepts and Techniques [13]. 8´ Indice general Entre las muchas t´ecnicas de Data Mining, se encuentra el uso de las M´aquinas de Vectores de Soporte, (SVM, del ingl´es Support Vector Machine) basadas en la separaci´on de los datos de ejemplo a trav´es de hiperplanos calculados mediante las llamadas funciones Kernel. Algunos de los textos de inter´es en los que se ha inspirado este proyecto son los siguientes: 1. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond [14]: Introduce conceptos necesarios para comprender el funcionamiento de las m´aquinas SVM, profundizando en los fundamentos matem´aticos subyacentes y aportando demostraciones, ilustraciones y ejemplos. 2. Kernels for Structured Data [15]. 3. Pairwise Classification as an Ensemble Technique [16]: En este art´ıculo se detalla la construcci´on de un clasificador SVM multiclase a partir de un conjunto de clasificadores SVM binarios. 4. Text Classification using String Kernels [17]: Profundiza en el comportamiento de los Kernels de comparaci´on de cadenas de texto e introduce optimizaciones que pueden aplicarse para obtener mejores resultados. 5. Lambda pruning: an approximation of the string subsequence kernel for practical SVM classification and redundancy clustering [18]: Este art´ıculo expone las mejoras obtenidas al incluir en el algoritmo tradicional de an´alisis de secuencias de caracteres un sistema de poda, que disminuye el tiempo necesario para procesar dos cadenas de texto. Como se comenta en apartados posteriores, todos ellos han sido utilizados como punto de partida en la implementaci´on de los m´odulos que componen el sistema. Cap´ıtulo 3 Propuesta de la arquitectura del sistema El sistema se estructura en tres bloques funcionales principales que permiten separar la interfaz de usuario, el motor de recomendaciones y el sistema de gesti´on de la persistencia, de forma que abordar cada uno de ellos separadamente facilite la construcci´on del prototipo. La figura 3.1 muestra un esquema con dichos bloques funcionales, cuya funci´on se define a continuaci´on. Figura 3.1: Esquema simplificado de la arquitectura del sistema. El bloque de interfaz interact´ua con el usuario, ofreci´endole las siguientes funcionalidades: Gesti´on de subscripciones a blogs de inter´es, incluyendo alta, listado y cancelaci´on. Gesti´on de las categor´ıas de los textos. Los nuevos textos ser´an recomendados si el sistema determina que pertenecen a alguna de ellas. 9 10 ´ Indice general Gesti´on de los textos de ejemplo. A˜nadir uno nuevo supone asociarlo a una de las categor´ıas citadas. Entrenamiento del sistema para que sea capaz de predecir la categor´ıa a la que pertenece el texto nuevo. Visualizaci´on y validaci´on de las recomendaciones de textos ofrecidas al usuario. El motor de recomendaciones es el bloque principal del sistema y se encarga de: Recoger y validar los datos procedentes de la interfaz de usuario. Obtener los textos para su posterior an´alisis. Comprobar peri´odicamente si, en los blogs de inter´es del usuario, hay textos nuevos y recomend´arselos en caso de estar relacionados con sus temas elegidos. Administrar la m´aquina de aprendizaje que, tras ser entrenada, ser´a capaz de predecir la categor´ıa a la que pertenecen los nuevos textos encontrados. Interactuar con el sistema de gesti´on de la persistencia para el almacenamiento de la informaci´on utilizada y necesaria para el sistema. Por ´ultimo, el sistema de persistencia permite guardar: Los resultados de los an´alisis. El estado de la m´aquina de aprendizaje. Toda la informaci´on de los textos que se analicen. Otra informaci´on que pueda ser interesante conservar por temas de rendimiento. Almacena datos de configuraci´on necesarios para el arranque del sistema. 3.1. Procesamiento ling¨u´ıstico La naturaleza del proyecto requiere que el sistema sea capaz de procesar textos atendiendo a sus contenidos e identificar los temas que tratan. No resulta pr´actico determinar la similitud entre dos textos considerando n´umero de caracteres que tienen en com´un. Los campos conceptuales son de utilidad en este contexto, puesto que son conjuntos de palabras con significados relacionados que pueden ser utilizados para detectar semejanzas en los temas tratados en los textos. ´ Indice general 11 En este primer prototipo los campos conceptuales se calculan en el momento de creaci´on de una nueva categor´ıa. El sistema proporcionar´a un campo conceptual asociado a las palabras que forman el nombre de la categor´ıa. De esta forma, ”pol´ıtica“ llevar´ıa asociadas palabras como partido, ideolog´ıa, parlamento y otras que el usuario podr´a a˜nadir seg´un sus preferencias. El proceso de obtenci´on del campo a partir de una determinada lista de palabras es muy importante, ya que el conjunto obtenido se utilizar´a como base durante la fase de entrenamiento. Hay que tener en cuenta que la inclusi´on de palabras poco relacionadas as´ı como un n´umero reducido de ellas distorsionar´an las predicciones. A continuaci´on se detalla el proceso de creaci´on de una nueva categor´ıa y el c´alculo del campo conceptual: 1. El usuario introduce las palabras clave. 2. Se obtienen los campos de cada una de ellas por separado. Para ello pueden emplearse diccionarios online, bases de datos o cualquier otra herramienta disponible. 3. Cada una de las palabras que forman los campos obtenidos pasa por un lematizador, que se encarga de eliminar los morfemas de la palabra, para quedarse con la ra´ız o lexema. As´ı se dispone de la esencia de cada palabra, invariante a los mecanismos de composici´on y derivaci´on inherentes a la Lengua Castellana. 4. Con los campos conceptuales lematizados de cada palabra se calcula el campo resultante. Este proceso no es trivial porque si el sistema es demasiado restrictivo se obtiene un conjunto final muy reducido, y por tanto poco relevante. Siendo demasiado flexible, por el contrario, se obtiene un resultado con excesivas palabras que, adem´as disminuir el rendimiento durante el proceso de an´alisis posterior, introduce palabras poco relacionadas. En este prototipo el campo total se calcula como la uni´on de los campos individuales, aunque cada contexto de aplicaci´on puede requerir un criterio diferente para mejorar los resultados en la predicci´on. El campo conceptual constituye un caso de entrenamiento para la categor´ıa creada y ser´a utilizado como un ejemplo m´as a la hora de realizar el aprendizaje y las predicciones. De esta forma se parte de una base adecuada que permite el an´alisis de contenidos de inter´es, pues se dispone de un conjunto de palabras relacionadas que pueden encontrarse en los textos relacionados con dicha categor´ıa. 12 ´ Indice general 3.2. Algoritmia de aprendizaje El sistema a construir requiere un m´etodo para distinguir diferentes tipos de textos atendiendo a su contenido. Este prototipo har´a uso de algoritmos de aprendizaje supervisado. Estos algoritmos completan una serie de operaciones necesarias para poder realizar predicciones: 1. Recepci´on de datos de ejemplo: El algoritmo requiere que le sean proporcionados datos de ejemplo de las diferentes clases que va a reconocer. La cantidad de estos datos, as´ı como su relevancia, condicionar´a considerablemente la precisi´on de las predicciones. 2. Fase de entrenamiento: Una vez le son facilitados los datos de ejemplo, se realiza una serie de ajustes internos, que permiten a la m´aquina de aprendizaje aprender a distinguir nuevos elementos. 3. Fase de predicci´on : Finalizado el entrenamiento, el algoritmo es capaz de determinar la clase a la que m´as se asemeja un nuevo dato. Como puede verse, los algoritmos de aprendizaje supervisado son muy adecuados para este proyecto, en el que el usuario asociar´a un conjunto de textos a sus respectivas categor´ıas, y el sistema se encargar´a de recomendarle nuevos textos cuando determine que est´an relacionados con los temas de su inter´es. El problema abordado en este proyecto encaja perfectamente en este tipo de algoritmos puesto que el usuario proporciona al sistema los textos de ejemplo y las categor´ıas a las que pertenecen, el sistema se entrena en funci´on de los datos recibidos, y a partir de ese momento predice la categor´ıa de los nuevos textos publicados para recomendarlos, si procede, al usuario. 3.3. Gesti´on de flujos de informaci´on El motor de recomendaciones se encarga de, ante la necesidad de disponer de datos que todav´ıa no haya manejado, obtener dicha informaci´on del mundo exterior (Internet). ´ Indice general 13 Las comunicaciones con el mundo exterior requieren tiempo para solicitar los datos y esperar a que sean proporcionados. Este tiempo, para nada despreciable, hace necesario almacenar toda la informaci´on recibida que pueda ser utilizada de nuevo si la penalizaci´on para obtenerla es elevada. Tambi´en es aconsejable almacenar los resultados del c´alculo de relaci´on entre dos textos, ya que es un dato invariante que se emplear´a repetidamente a lo largo del tiempo. Para abordar el problema, el motor de recomendaciones enviar´a al sistema de gesti´on de la persistencia los textos, los campos conceptuales obtenidos y el resultado de los an´alisis. Todo este proceso se detalla en el apartado 4. Otra ventaja importante del almacenamiento de datos es la disponibilidad de la informaci´on inmediatamente despu´es del arranque del sistema tras un cese en su funcionamiento. El sistema puede dejar de funcionar temporalmente por un fallo en la red o en la m´aquina donde se ejecute. Disponer de los datos almacenados evita la necesidad de calcularlos de nuevo. 3.4. Paralelizaci´on de tareas Las tareas internas que el sistema realiza para analizar los textos y predecir el grado de relevancia de los nuevos contenidos publicados requieren c´alculos intensivos y tiempo para ejecutarlos. Por ello resulta ventajoso paralelizar estas operaciones. Despu´es de un estudio de la naturaleza de cada una de ellas, se han encontrado los siguientes puntos en los que un trabajo en paralelo mejorar´a los tiempos de ejecuci´on. Obtenci´on del campo conceptual: En esta tarea la consulta de un diccionario de gran tama˜no puede puede requerir mucho tiempo. Tambi´en es posible que lo que se quiera sea calcular el campo asociado a varias palabras para luego determinar el conjunto total. Puesto que la obtenci´on de cada campo individual es una operaci´on independiente, pueden ejecutarse las consultas individuales en paralelo y luego fusionar los resultados, reduciendo as´ı el tiempo total de ejecuci´on de la tarea. Entrenamiento y predicci´on en la m´aquina de aprendizaje: Aun siendo la operaci´on de entrenamiento bastante poco frecuente, lleva consigo una gran penalizaci´on. Con muchos casos de ejemplo y muchas clases de datos, puede requerir varios minutos, o incluso horas. En cuanto a la predicci´on, desgraciadamente es 14 ´ Indice general bastante m´as utilizada que la anterior, ya que se ejecuta cada vez que haya contenidos nuevos en cualquiera de los blogs en los que el usuario se haya subscrito. ´ Este es pues otro contexto en que existe la posibilidad de introducir mejoras en cuanto a la paralelizaci´on de la algoritmia asociada al entrenamiento y a la predicci´on. Cap´ıtulo 4 Prototipo del sistema En este apartado se presenta el prototipo del sistema, comentando en primer lugar las decisiones previas tomadas para transformar la figura 3.1 en el modelo a implementar. El proceso de refinamiento se lleva a cabo en varias fases. Primero se introducen algunas consideraciones que determinan la ubicaci´on de los bloques del sistema, despu´es se elige el algorimo de aprendizaje y posteriormente las tecnolog´ıas a utilizar. 4.1. Primera aproximaci´on El esquema inicial, mostrado en la figura 3.1 encaja perfectamente con el patr´on de dise˜no MVC (del ingl´es, Model-View-Controller). ´ Este ser´a pues el punto de partida para el desarrollo del prototipo, ya que separa la interfaz de usuario, el control y el sistema de gesti´on de la persistencia de forma que es posible su desarrollo de forma independiente. Debido a la potencia de c´alculo necesaria para llevar a cabo las tareas de entrenamiento y predicci´on de la m´aquina de aprendizaje, se prev´e que, aunque el desarrollo y las pruebas b´asicas se lleven a cabo en un ordenador personal, la implantaci´on real de un sistema de estas caracter´ısticas requerir´a de un entorno de procesamiento mucho m´as potente como, por ejemplo, una granja de servidores. As´ı, se plantea desde un primer momento la escalabilidad como requerimiento en todos los aspectos de dise˜no e implementaci´on que se puedan considerar. En este sentido, se prev´e que en lugar de una aplicaci´on de escriterio, el usuario acceder´a a una p´agina web que se comunicar´a con el motor de recomendaciones. Esta estructuraci´on hace que el sistema sea accesible desde cualquier lugar, requiriendo solamente un navegador web instalado, en lugar de otro software especializado. 15 22 ´ Indice general La modificaci´on consiste en crear un clasificador binario encargado de reconocer cada una de las clases de entrenamiento. Hay pues tantos clasificadores binarios como clases. Si cualquiera de estos clasificadores determina que el nuevo dato pertenece a la clase que reconoce, el nuevo texto se recomienda al usuario. En caso contrario se descarta, pues no es un texto de inter´es. Adicionalmente se a˜nade soporte para el trabajo en paralelo en las tareas de entrenamiento y predicci´on, que se explica en el apartado 5.4. 5.2.3. El lematizador El lematizador extrae la ra´ız de una palabra, como se ha comentado en el apartado 2.1. Es una clase obtenida en SourceForge [31] que implementa el algoritmo de Porter [32]. No se han requerido modificaciones en su algoritmo original. 5.2.4. El m´odulo de comunicaci´on con el diccionario de Zirano Para la obtenci´on de los campos conceptuales se ha implementado un m´odulo que interact´ua con el diccionario de Zirano. Su tarea principal consiste en simular la navegaci´on que realizar´ıa un visitante en su p´agina web para obtener una lista de todas las palabras relacionadas con la introducida por el usuario. El proceso simulado consta de las siguientes fases: 1. El usuario introduce la palabra de su inter´es. 2. La la p´agina de Zirano sugiere una lista de ideas o acepciones relacionadas con esa palabra. 3. El usuario navega por las diferentes acepciones sugeridas y, para cada una de ellas, obtiene un conjunto de palabras relacionadas. Este m´odulo realiza un recorrido por todas las ideas sugeridas, hasta extraer un n´umero suficiente de palabras relacionadas. 5.3. Implementaci´on del modelo: Capa de acceso a datos En este subapartado se resume la implementaci´on de la capa de acceso a datos. ´ Indice general 23 Figura 5.3: Estructura del m´odulo de acceso a datos. Cabe resaltar la penalizaci´on derivada de la descarga de un texto desde internet. Esta operaci´on requiere un tiempo considerable y por ese motivo los textos descargados no se eliminan de la base de datos, sino que permanecen en el sistema, a modo de cache. Una recomendaci´on o un caso de ejemplo har´an pues referencia a un texto ya guardado. Pueden borrarse las recomendaciones pero no los textos a los que hacen alusi´on, de forma que si se vuelve a a˜nadir de nuevo una recomendaci´on o un caso de ejemplo no es necesario descargarlo. La figura 5.4 muestra las distintas tablas existentes en la base de datos, as´ı como las relaciones entre ellas. En el paquete DAO existen ocho clases encargadas de interactuar con las tablas de la base de datos con las que est´an relacionadas. Las clases son las siguientes: BlogDao: Para inserci´on, listado y borrado de blogs de inter´es. ClaseDao: Gestiona el almacenamiento de las clases de entrenamiento. ClasificadorDao: Ofrece m´etodos para el almacenamiento en disco de la SVM. ConceptosDao: Para la gesti´on de palabras, ra´ıces y campos conceptuales. EntrenamientoDao: Gestiona el almacenamiento los datos de entrenamiento del sistema. InfoDao: Para el manejo de la tabla de informaci´on del sistema. PostDao: Ofrece operaciones de inserci´on de nuevos textos en la base de datos as´ı como de listado. Por motivos comentados al principio de este subapartado no se ofrecen operaciones de eliminaci´on. 24 ´ Indice general Figura 5.4: Esquema de la base de datos. Recomendaci´onDao: Gestiona la tabla de recomendaciones. Para una explicaci´on m´as detallada, ver Anexo F. 5.4. Paralelizaci´on de tareas Como se ha mencionado en el apartado 3.4, existen varios actividades en el sistema que pueden realizarse en paralelo para obtener mejoras en tiempo. Para este primer prototipo se decidi´o centrarse en las relacionadas con la m´aquina de aprendizaje, m´as concretamente en las operaciones de entrenamiento y predicci´on. El trabajo en paralelo puede introducirse en cualquiera de los tres niveles del clasificador SVM implementado, tal y como ilustra la figura 5.5. Pueden hacerse c´alculos simult´aneos en la funci´on de comparaci´on del Kernel SSK, en las operaciones de entre- ´ Indice general 25 namiento y predicci´on de las m´aquinas SVM binarias, o en el clasificador final. Cada una de estas alternativas se explica en los p´arrafos siguientes. Figura 5.5: Niveles de paralelizaci´on de la m´aquina SVM. En la funci´on de comparaci´on de dos cadenas, en la clase StringKernel de Weka, hay un punto concreto donde pueden lanzarse c´alculos en paralelo. Como se explica en el apartado G.5 del Anexo G, para calcular el grado de semejanza normalizado, se realizan tres llamadas a la funci´on Kernel que son independientes entre ellas. Los resultados obtenidos se multiplican y dividen entre ellos, pero nada impide realizar los c´alculos en paralelo guardando los resultados en variables temporales para operar despu´es con ellas. En el nivel superior al Kernel se encuentran las m´aquinas SVM binarias. El m´etodo de entrenamiento realiza iteraciones, en las que se invoca repetidamente al Kernel y se ajustan coeficientes internos antes de volver a iterar. Es imposible lanzar en paralelo las diferentes iteraciones, pues una iteraci´on necesita los resultados de todas las anteriores. Sin embargo, en cada iteraci´on se realizan varias llamadas a la funci´on Kernel independientes, que s´ı se pueden ejecutar al mismo tiempo. Lo mismo ocurre con el m´etodo de predicci´on, que realiza comparaciones (invocaciones al Kernel) entre el dato nuevo y cada uno de los vectores de soporte, para construir un resultado. Pueden lanzarse dichas comparaciones en paralelo e ir acumulando los resultados en una variable temporal, para luego realizar c´alculos con ella y generar el resultado que ser´a devuelto. 26 ´ Indice general ´ Estos son los puntos paralelizables a este nivel. Por ´ultimo, las diferentes m´aquinas SVM binarias pueden trabajar en paralelo ya que cada una dispone de su copia individual del conjunto de datos de entrenamiento. Cada una de ellas genera, tanto en el proceso de entrenamiento como en el de predicci´on resultados independientes de las dem´as, y por tanto pueden ejecutarse simult´aneamente. La decisi´on de qu´e puntos paralelizar y cuales no, no es trivial. Tratar los tres niveles supone la creaci´on de un n´umero elevado de tareas. Implementar s´olo los dos inferiores proporciona mejores tiempos al aumentar el n´umero de datos de ejemplo, y s´olo el superior proporciona mejores tiempos al aumentar el n´umero de clases diferentes. El grado de paralelismo utilizado en cada nivel deber´ıa ser ajustado teniendo en cuenta la cantidad y variedad de textos que el usuario vaya a manejar. En este prototipo se decidi´o implementar los dos niveles superiores. Al entrenar y predecir todas las m´aquinas SVM binarias realizan sus c´alculos en paralelo y crean, seg´un sea necesario, nuevas tareas para ejecutar las invocaciones al Kernel SSK. Queda pendiente para ampliaciones futuras la inclusi´on de trabajo en paralelo en el nivel inferior. Para la implementaci´on de estas mejoras, se han a˜nadido objetos de la clase ExecutorService [33], inclu´ıda en el paquete Concurrent de Java, al clasificador SVM. Estos objetos administran conjuntos de tareas (implementaciones de la interfaz Runnable [34]), con la ventaja de que los hilos de ejecuci´on creados no se destruyen al finalizar la tarea, sino que son reutilizados seg´un quedan libres. Se evita as´ı la creaci´on continua de hilos de ejecuci´on, con su correspondiente penalizaci´on de tiempo. Cap´ıtulo 6 Evaluaci´on del prototipo. Experimentos La naturaleza masiva del c´alculo asociado al entrenamiento y a la predicci´on utilizando m´aquinas SVM ha planteado como requerimiento, desde un primer momento, la necesidad de dise˜nar el sistema con la m´axima escalabilidad posible. As´ı, el estudio del comportamiento paralelo de los procesos m´as intensivos en c´alculo se ha materializado en un conjunto de experimentos que se han ejecutado en distintas plataformas computacionales. 6.1. Descripci´on del experimento El almacenamiento de un texto de prueba introducido por el usuario requiere que el sistema descargue su c´odigo y lo procese para eliminar etiquetas HTML. Pero, debido a la gran cantidad de formatos de p´agina web que existen y a que los lectores pueden escribir sus comentarios, resulta muy dif´ıcil eliminar completamente la informaci´on ajena al texto de inter´es. Esto influye negativamente en la calidad de las predicciones y requiere una mejora del algoritmo de filtrado. Por ese motivo los experimentos realizados se centran en la influencia de la paralelizaci´on sobre las tareas del sistema, concretamente en las operaciones internas de la m´aquina SVM. Las mejoras en tiempo observadas son independientes de la calidad de los textos de ejemplo y por tanto pueden extraerse conclusiones de mayor inter´es. 6.1.1. Conjunto de datos de entrada Se han creado 4 clases de entrenamiento, que son las categor´ıas de las que el usuario desea mantenerse informado. ´ Estas son: pol´ıtica,deportes,econom´ıa ytecnolog´ıa. 27 28 ´ Indice general Para cada una de ellas, existen 5 art´ıculos de ejemplo relacionados extra´ıdos de las versiones online de los peri´odicos Heraldo de Arag´on[35], Marca[36] y El Pa´ıs[37] El experimento consiste en un entrenamiento y una predicci´on de un art´ıculo nuevo, obteniendo tiempos de ejecuci´on secuencial y de ejecuciones paralelas con un n´umero variable de procesadores. Se pretende estudiar la mejora en tiempo obtenida al ejecutar el c´odigo en tres entornos distintos, tanto en su versi´on secuencial como empleando el m´aximo n´umero de procesadores disponibles. 6.1.2. Presentaci´on del hardware Para el lanzamiento del experimento se dispone de tres m´aquinas diferentes que se detallan a continuaci´on. En primer lugar, mi ordenador portatil, al que en adelante se llamar´a “Portatil”, que tiene las siguientes caracter´ısticas: Procesador AMD Athlon 64 X2 dual-core QL-60. Tipo de m´aquina: x86. Sistema Operativo: Windows 7. N´umero de CPUs: 2. Frecuencia de procesador: 1.9 GHz. Memoria total: 4GB. En segundo lugar, se han realizado pruebas en Cluster Hermes [38] del Instituto de Investigaci´on de Ingenier´ıa de Arag´on (I3A) de la Universidad de Zaragoza. Concretamente, se ha utilizado la m´aquina Selene2 bajo Condor[39], con las siguientes caracter´ısticas: Nodo: selene2.hermes.cps.unizar.es Tipo de m´aquina: x86. Sistema Operativo: Linux. Versi´on del Sistema Operativo: 2.6.18-238.5.1.el5. N´umero de CPUs: 48 Frecuencia de procesador: 2200 MHz. ´ Indice general 29 Memoria total: 99004784.000 KB Tama˜no de Swap total: 102399984.000 KB Por ´ultimo, Gregorio de Miguel me ofreci´o la posibilidad de lanzar el experimento en su ordenador. Esta m´aquina se llamar´a “Goyo” en adelante y tiene las siguientes caracteristicas. Procesador: Intel Core i7 920 Tipo de m´aquina: x86. Sistema Operativo: Windows 7 64 bits. N´umero de CPUs: 4x2 (2 hilos por CPU). Frecuencia de procesador: 3.95 GHz. Memoria total: 6GB. Se ha preparado un script para ejecutar los experimentos en las distintas m´aquinas. En primer lugar se lanza un servidor que carga los datos necesarios para su funcionamiento y queda a la espera de conexiones entrantes. A continuaci´on se lanza un cliente que solicita el entrenamiento del sistema y una predicci´on de un texto nuevo. Finalizadas ambas tareas, cliente y servidor finalizan su ejecuci´on. Para el caso del nodo Selene2, los t´ecnicos que dan soporte a los usuarios de Hermes han preparado un script .sub para Condor, que puede consultarse en el Anexo H. 6.2. Descripci´on de los resultados Las tablas 6.1 y6.2 muestran los tiempos obtenidos para cada una de las operaciones por separado. Cabe resaltar las diferencias entre las m´aquinas que han intervenido en el proceso de pruebas de escalabilidad, lo que dificulta la extracci´on de conclusiones. Cuadro 6.1: Tiempo del entrenamiento ejecutado en las distintas m´aquinas. PORTATIL (2 CPUs) GOYO (8 CPUs) SELENE2 (48 CPUs) SECUENCIAL 2601 909 900 MAXIMO CPUs 1470 186 109 Las figuras 6.1 y6.2 ilustran gr´aficamente los resultados de las tablas anteriores. En ambas se representa, para cada m´aquina, los tiempos obtenidos en ejecucions secuenciales y paralelas. 30 ´ Indice general Cuadro 6.2: Tiempo de la predicci´on ejecutada en las distintas m´aquinas. PORTATIL (2 CPUs) GOYO (8 CPUs) SELENE2 (48 CPUs) SECUENCIAL 164 59 145 MAXIMO CPUs 171 57 134 Figura 6.1: Resultados de operacion de entrenamiento para cada una de las m´aquinas. En el entrenamiento, el tiempo de c´alculo va disminuyendo conforme aumenta el n´umero de procesadores disponibles, especialmente en el caso de mi ordenador port´atil en el que duplicar el n´umero de procesadores disminuye el tiempo de c´alculo casi a la mitad. Por otra parte, la operaci´on de predicci´on obtiene peores resultados. En mi ordenador port´atil, trabajar con dos procesadores produce tiempos de ejecuci´on mayores que trabajar secuencialmente. Las otras dos m´aquinas obtienen mejoras poco significativas de tiempo. La figura 6.3 muestra las mejora en tiempo obtenida en cada una de las tres m´aquinas en las operaciones de entrenamiento y predicci´on. La mejora en tiempos obtenida es menor a lo que se esperaba durante la implementaci´on del paralelismo. Esto de debe a diversos factores, entre los que se pueden encontrarse los siguientes: 1. Compartici´on de unidad de punto flotante: Si un n´ucleo de la m´aquina s´olo dispone de una unidad de punto flotante que los distintos hilos de ejecuci´on pueden necesitar utilizar al mismo tiempo, se producen esperas hasta que dicha unidad ´ Indice general 31 Figura 6.2: Resultados de operacion de predicci´on para cada una de las m´aquinas. Figura 6.3: SpeedUp obtenido en las diferentes m´aquinas. queda libre. Este caso se da en procesadores multihilo, en los que se comparten algunas unidades funcionales. En este proyecto, en el que el c´alculo con n´umeros reales es intenso, este hecho puede producirse frecuentemente. 2. Compartici´on de memoria cache: Los hilos de ejecuci´on comparten alg´un nivel de cache, como el L3, de manera que al haber varias tareas en paralelo 38 Anexo A Manual de usuario BCatalog es un sistema de recomendaci´on de blogs que notifica al usuario cuando alguno de sus sitios favoritos publica contenidos relacionados con temas de su inter´es. Para el manejo del sistema el usuario dispone de una p´agina web muy intuitiva. De esta forma no se requiere ning´un software instalado en su ordenador a excepci´on de un navegador web, pudiendo as´ı mantenerse informado en casa, en el trabajo o en cualquier lugar donde se encuentre. En los apartados siguientes se resume toda la informaci´on necesaria para empezar a obtener recomendaciones y se muestran capturas de pantalla que facilitar´an la comprensi´on del lector y su familiarizaci´on con la aplicaci´on. A.1. Estructura de la p´agina La p´agina web est´a formada por tres zonas principales con las que el usuario puede interactuar, tal como se ilustra en la figura A.1: Figura A.1: Estructura de la p´agina. 39 40 1. El men´u de navegaci´on superior presenta las secciones de la p´agina web. A trav´es de este men´u el usuario puede visualizar las recomendaciones propuestas, gestionar sus blogs favoritos y entrenar al sistema para que empiece a recomendarle nuevos contenidos. 2. El men´u izquierdo presenta las subsecciones existentes en la secci´on del men´u superior seleccionada. 3. La zona de contenido muestra el texto y los formularios correspondientes a cada secci´on. A.2. Gesti´on de blogs Seleccionando la opci´on Blogs del men´u superior se accede a la pantalla de gesti´on de las subcripciones. Todas las operaciones disponibles aparecen juntas en esta secci´on, para la c´omoda manipulaci´on de los blogs favoritos del usuario. Las acciones que pueden realizarse aparecen reflejadas en la figura A.2, y son las siguientes: Figura A.2: Gesti´on de subscripciones a blogs. 1. A˜nadir una subscripci´on a un blog 2. Ver el listado de subscripciones en curso. 3. Cancelar una subscripci´on. BCatalog dejar´a de recomendar el blog seleccionado. A.3. Entrenamiento del sistema En la secci´on Entrenamientos est´an disponibles todas las acciones necesarias para que el sistema aprenda las preferencias del usuario en cuanto a temas de inter´es se 41 refiere. El usuario proporcionar´a a BCatalog un conjunto de textos de ejemplo para cada uno de los temas de los que desee recibir notificaciones. El proceso de entrenamiento del sistema se lleva a cabo en dos fases tras las cuales BCatalog estar´a listo para empezar a analizar los blogs seleccionados en busca de nuevos contenidos relacionados. Estas tareas son accesibles desde el men´u lateral de la p´agina web, como ilustra la figura A.3. Es importante que el sistema vuelva a entrenarse a lo largo del tiempo a˜nadiendo nuevos textos de ejemplo que pueden ser introducidos manualmente o bien ser recomendaciones que el usuario considere acertadas. A continuaci´on se enumeran las distintas fases del entrenamiento, que se describen en detalle en los subapartados siguientes: 1. Creaci´on de las categor´ıas de inter´es del usuario (ej: econom´ıa). 2. Introducci´on de textos de ejemplo, especificando la categor´ıa a la que pertenecen. 3. Entrenamiento del sistema. Figura A.3: Entrenamiento del sistema. A.3.1. Gesti´on de categor´ıas de textos La gesti´on de categor´ıas puede realizarse desde la pantalla Administrar clases de entrenamiento, en el men´u lateral izquierdo, una vez seleccionada la opci´on Entrenamientos del men´u superior. Esta pantalla es muy similar a la de gesti´on de blogs, introducida en el apartado A.2 y ofrece las siguientes acciones a realizar, que aparecen en la figura A.4: 1. A˜nadir una clase de entrenamiento (categor´ıa a la que puede pertenecer un texto). 42 Figura A.4: Gesti´on de clases de entrenamiento. 2. Ver el listado de las clases existentes 3. Eliminar una clase de entrenamiento. A.3.2. Gesti´on de textos de ejemplo Una vez definidas las clases de textos que el sistema va a manejar, el siguiente paso es a˜nadir casos de ejemplo de cada una de las clases. Pueden pertenecer, o no, a los blogs a los que el usuario se ha subscrito. Con estos textos BCtalog aprender´a a identificar las preferencias del usuario, y por lo tanto es necesario que los ejemplos introducidos sean lo m´as relevantes posible para asegurar la calidad de las recomendaciones. Figura A.5: Inserci´on de un nuevo texto de ejemplo. Para la introducci´on de los datos de ejemplo la p´agina web proporciona la pantalla Nuevo caso de entrenamiento. En ella, el usuario deber´a introducir la direcci´on URL donde se encuentra el texto y seleccionar la categor´ıa a la que pertenece, de entre las ya creadas anteriormente. Este proceso se ilustra en la figura A.5. 43 La pantalla Administrar casos de entrenamiento ofrece un listado de todos los ejemplos almacenados hasta el momento mostrados por categor´ıas, como puede verse en la figura A.6. Junto a cada caso de ejemplo se ofrece la opci´on de borrarlo si el usuario decide que no le interesa que est´e asociado a esa cagegor´ıa. Figura A.6: Gesti´on de textos de ejemplo. Es importante comentar que en este listado aparecen tanto los ejemplos introducidos por el usuario como aquellas recomendaciones que el usuario haya aceptado. A.3.3. Entrenamiento del sistema Completadas las fases anteriores el usuario puede entrenar al sistema desde la pantalla Gesti´on de SVM, mostrada en la figura A.7, que es accesible desde el men´u lateral. BCatalog iniciar´a el proceso de entrenamiento de su m´aquina de aprendizaje. Este proceso puede requerir un tiempo para ser completado. A partir de ese momento, BCatalog visitar´a peri´odicamente los blogs favoritos del usuario, descargar´a y analizar´a los nuevos contenidos y recomendar´a, si procede, su lectura al usuario. Esta pantalla, ofrece adicionalmente la posibilidad de introducir la URL de un texto cualquiera, y solicitar a BCatalog que lo analice y a˜nada la correspondiente recomendaci´on. Con esta utilidad el usuario puede comprobar el funcionamiento del sistema y la calidad de las predicciones. 44 Figura A.7: Entrenamiento del sistema y predicci´on. A.4. Recomendaciones Cuando BCatalog determine que los nuevos textos est´an lo suficientemente relacionados con las preferencias del usuario, a˜nadir´a nuevas recomendaciones que el usuario podr´a ver cada vez que ingrese en la p´agina y hasta que las acepte o rechace. En la pantalla Principal, que aparece en la figura A.8 y es accesible desde el men´u de navegaci´on superior, aparecer´a un listado con las recomendaciones no pendientes de verificaci´on. Cada recomendaci´on tiene su correspondiente bot´on para informar a BCatalog de si es o no del agrado del usuario. Figura A.8: Ejemplo de recomendaciones propuestas por el sistema. 45 En caso de que el usuario est´e satisfecho con las recomendaciones, pasar´an a formar parte de los textos de ejemplo y ser´an tenidas en cuenta cuando el sistema vuelva a entrenarse. En caso contrario la recomendaci´on desaparecer´a. 46 Anexo B Relaci´on de clases del sistema En este apartado se detallan las clases que el sistema maneja para realizar las tareas de an´alisis y recomendaci´on de textos publicados en blogs de inter´es del usuario. Todas ellas se incluyen en el paquete Entities, presente tanto en la vista como en el motor de recomendaciones. La figura B.1 ilustra las cinco clases y sus atributos. El significado de cada uno de ellos se detalla a continuaci´on: Figura B.1: Clases almacenadas por el sistema. 47 54 Anexo D La p´agina web La p´agina web constituye la interfaz de comunicaci´on entre el usuario y BCatalog. El m´odulo de vista est´a pues formado por dicha p´agina y una serie de herramientas que recogen los datos proporcionados, contactan con el motor de recomendaciones y muestran al usuario la informaci´on devuelta por ´este. La figura D.1 ilustra la estructura interna del m´odulo vista, y los componentes que forman tanto la p´agina web como el bloque Java que procesa los datos. Figura D.1: Estructura del m´odulo de vista. 55 56 La carpeta Web Content se estructura en subcarpetas y contiene todos los archivos necesarios para el funcionamiento de la p´agina web. El cap´ıtulo D.1 detalla cada uno de estos elementos, entre los que se incluyen los siguientes: 1. La carpeta base, que contiene la plantilla de las pantallas que componen la web. 2. Distintos archivos XML[40] necesarios para la configuraci´on de la p´agina. 3. La carpeta blog, que incluye las pantallas asociadas a la gesti´on de blogs. 4. La carpeta svm, en la que se encuentran las pantallas relacionadas con el aprendizaje del sistema. El m´odulo Java incluye dos paquetes que forman una jerarqu´ıa por niveles, explicada en mayor profundidad en el apartado D.2. Estos paquetes son: 1. El paquete beans, que recoge los datos procedentes de la p´agina web y almacena la informaci´on devuelta por motor de recomendaciones y que ser´a mostrada al usuario en respuesta a sus peticiones. 2. El paquete servicio que recibe los datos del paquete beans, env´ıa la petici´on al motor de recomendaciones y devuelve los resultados al nivel superior. D.1. La carpeta Web Content La carpeta Web Content contiene los archivos HTML de la p´agina web, la plantilla que define la estructura de las pantallas ser´an mostradas al usuario, una serie de archivos XML que configuran el comportamiento del servidor y el archivo index.xhtml que es el punto de entrada por defecto a la p´agina. D.1.1. La carpeta base En el desarrollo de p´aginas web resulta muy ´util separar el estilo de la p´agina del contenido din´amico generado como resultado a las peticiones del usuario. Con ello se consigue una divisi´on de tarea que facilita la depuraci´on de errores, el trabajo entre miembros del equipo de desarrollo y las posibles ampliaciones del sistema a construir. ´ Esta es la raz´on de la existencia de la carpeta base, en la que se especifican por separado la plantilla de la p´agina web (fichero template.xhtml), los estilos que personalizan su apariencia (carpeta css) y las im´agenes que aparecer´an en la p´agina a mostrar al usuario (carpeta images). 57 El fichero template.xhtml define la estructura de la p´agina, las zonas de la pantalla donde se pueden colocar contenidos din´amicamente. Es en ´el donde se especifica que la pantalla estar´a formada por una cabecera con el logotipo de la aplicaci´on, un men´u superior de navegaci´on, uno lateral y una zona central principal para mostrar informaci´on al usuario. El contenido de cada una de las zonas no aparece en este archivo, sino que se incluir´a posteriormente dependiendo de la p´agina solicitada. Esta forma de trabajo es similar a la utilizada en los lenguajes de programaci´on, en las que determinados ficheros con c´odigo pueden incluirse en otros donde vayan a ser utilizados. Los colores, el tipo y tama˜no de la fuente, las dimensiones de las zonas que componen la pantalla y todas las dem´as propiedades relacionadas con el estilo del sitio web se implementan por separado en el archivo style.css, ubicado en la carpeta css. La carpeta images contiene las im´agenes mostradas en la p´agina resultado, como son el logotipo de la aplicaci´on, la imagen de la cabecera superior y otras que se utilizan como fondo en las distintas zonas de la pantalla. D.1.2. Los archivos XML Para el correcto funcionamiento de la p´agina web se requieren fundamentalmente dos archivos que configuran el comportamiento del sitio ante la actividad del usuario. Estos archivos se encuentran en la carpeta WEB-INF, y se comentan a continuaci´on: 1. faces-config.xml: Especifica los objetos Java que manejar´an la informaci´on intercambiada entre el usuario y el sistema. Este fichero indica a JSF qu´e campos de los formularios HTML ha de asociar a qu´e objetos Java para su manipulaci´on posterior. Incluye adem´as reglas de navegaci´on que especifican a qu´e p´agina se ha de redirigir al usuario cuando realice cada acci´on de las ofrecidas en la p´agina web. 2. web.xml: Aporta informaci´on al servidor web, como la p´agina principal por defec- to, la extensi´on en que acaban las direcciones URL de cada una de las secciones (seccion.html, seccion.jsf o cualquier otra que se decida) y otras indicaciones de utilidad. D.1.3. Las carpetas blog y svm Por ´ultimo, las carpetas blog ysvm contienen archivos con el c´odigo HTML propio de cada secci´on existente en la p´agina web. Es importante destacar que el c´odigo que 58 aparece en cada uno de estos archivos define ´unicamente el contenido de cada una de las zonas de la pantalla especificadas en el fichero template.xhtml. Para obtener codidigo final, el servidor realizar´a una serie de operaciones que se comentan en el apartado D.1.4 La carpeta blog contiene un ´unico archivo llamado gestion.xhtml, en el que se encuentra el c´odigo para generar los formularios para a˜nadir, listar y borrar los blogs a los que el usuario quiere subscribirse. La carpeta svm contiene los siguientes archivos que implementan las pantallas para gestionar el aprendizaje y entrenamiento de BCatalog: 1. index.xhtml: Es el punto de entrada a la secci´on de gesti´on de aprendizaje del sistema. 2. gestion clases.xhtml: La pantalla que ofrece al usuario la creaci´on de una categor´ıa para sus textos de ejemplo. 3. nuevo entrenamiento.xhtml: La pantalla para la inserci´on de textos de ejemplo. 4. gestion entrenamiento.xhtml: La pantalla que muestra el listado de textos de ejemplo agrupados por categor´ıas. 5. svm.xhtml: La pantalla desde la que se puede entrenar al sistema. D.1.4. Proceso de construcci´on de una pantalla Como se ha mencionado repetidas veces a lo largo de este apartado, el estilo, la estructura de la p´agina web, las im´agenes y el contenido se implementan por separado. La generaci´on del c´odigo HTML final que ser´a enviado de vuelta al usuario y que el navegador web interpretar´a para mostrarle la pantalla pertinente, se realiza en los siguientes pasos: 1. Cargar el c´odigo HTML contenido en el archivo template.xhtml. 2. Incluirle el archivo de estilos que se especifica en el. 3. Completar el contenido de cada zona de la pantalla con el c´odigo que aparece en el archivo correspondiente a la secci´on solicita. 4. Una vez ensambladas las piezas que componen el c´odigo final, se env´ıa el resultado al usuario. 59 D.2. El m´odulo Java de gesti´on El m´odulo Java de gesti´on est´a formado por dos paquetes que trabajan como un sistema por niveles que la informaci´on va atravesando en su recorrido de ida y vuelta entre el ordenador del usuario y el motor de recomendaciones. El paquete beans constituye el nivel superior. Contiene dos clases, BlogVista ySvm- Vista. Cada una de ellas incluye objetos donde JSF almacena los datos procedentes del usuario y los devueltos por el motor de recomendaciones. Este paquete comprueba la existencia de los datos que recibe y los pasa al nivel inferior. El nivel inferior lo implementa el paquete servicio, que es el encargado de interactuar con el motor de recomendaciones. Incluye las clases BlogServicio ySvmServicio, que ofrecen m´etodos que sus hom´ologas del nivel superior pueden invocar. Estas clases se encargan de enviar la petici´on al motor de recomendaciones y esperar los resultados o una excepci´on en caso de haber alg´un error en los par´ametros proporcionados. Si se recibe una excepci´on, ´esta se propaga hasta el nivel superior, donde se construye un mensaje de error que ser´a enviado al usuario para informarle del problema. Por ´ultimo, el m´odulo Java de gesti´on incluye un paquete de utilidades para la validaci´on de datos, la interfaz del servidor remoto RMI que contiene los m´etodos que ofrece el motor de recomendaciones y un paquete con las clases que maneja el sistema, ya comentadas en el apartado B. 60 Anexo E El motor de recomendaciones El motor de recomendaciones es el bloque principal del sistema. Se implementa como un objeto remoto RMI, puesto que con esta herramienta de Java se construyen servidores como objetos cuyos m´etodos pueden ser invocados por el cliente. Esta idea se ha introducido ya en el apartado 4.2, Elecci´on de las tecnolog´ıas. Figura E.1: Estructura del motor de recomendaciones. Para que un objeto pueda ser utilizado como un objeto remoto, es necesario que cumpla una serie de requisitos, que son los siguientes: 1. Los m´etodos que ofrezca al cliente tienen que estar definidos en una interfaz, y la clase a la que pertenece el objeto debe implementarlos todos. 2. Esta interfaz debe heredar de la clase Remote, contenida en el paquete RMI. 61 62 3. El cliente debe disponer de una copia de la interfaz, para conocer los m´etodos que puede invocar. No necesita su implementaci´on, ya que es informaci´on privada del servidor. 4. Para que el objeto sea accesible por otras m´aquinas hay que darlo de alta en el registro RMI. Este bloque contiene adem´as m´odulos auxiliares, que se ilustran en la figura E.1. En los siguientes apartados se profundiza en cada uno de estos m´odulos, los paquetes Java que los implementan, las clases que contienen y los m´etodos m´as relevantes de cada una de ellas. E.1. El paquete recomendaciones Este apartado contiene la interfaz remota, la clase Recomendador, la excepci´on propia BCatalogException y la clase Actualizador, encargada de la revisi´on de los blogs en busca de nuevos contenidos. E.1.1. La interfaz remota La interfaz remota contiene solamente los prototipos de los m´etodos que el recomendador debe implementar. El listado completo de estos m´etodos puede verse en el bloque de c´odigo E.1. Puesto que el c´odigo fuente es de f´acil comprensi´on y est´a suficientemente comentado, no son necesarias explicaciones adicionales. C´odigo E.1: CatalogInterface. 1public interface CatalogInterface extends java . rmi . Remote { 2 3// Gestion de blogs 4void nuevoBlog ( String url ) throws Exception ; 5public ArrayList <Blog > listadoBlogs () throws Exception ; 6public void borrarBlog ( int id) throws Exception ; 7 8// Gestion de clases de entrenamiento 9void nuevaClase ( String urul ) throws Exception ; 10 public ArrayList <Clase > listadoClases () throws Exception ; 11 public void borrarClase ( int id ) throws Exception ; 12 13 // Gestion de textos de ejemplo (datos de entrenamiento ) 14 public void nuevoEntrenamiento ( String url , int clase ) throws Exception ; 63 15 public ArrayList < Entrenamiento > listadoEntrenamientos () throws Exception ; 16 public void borrarEntrenamiento ( int postId , int claseId ) throws Exception ; 17 18 // Operaciones sobre la SVM 19 public void entrenar () throws Exception ; 20 public void predecir ( String url ) throws Exception ; 21 22 // Gestion de recomendaciones 23 public void aceptarRecomendacion ( int postId ) throws Exception ; 24 public void rechazarRecomendacion ( int postId ) throws Exception ; 25 public ArrayList < Recomendacion > listadoRecomendaciones () throws Exception ; 26 } E.1.2. El recomendador La clase Recomendador es el punto de entrada al programa y por tanto incluye su propio m´etodo main. Cuando el programa inicia su ejecuci´on, crea el objeto del servidor proporcion´andole los par´ametros recibidos por l´ınea de comandos. Dicho servidor queda bloqueado a la espera de nuevas conexiones entrantes. El bloque de c´odigo E.2 muestra un resumen del m´etodo main. C´odigo E.2: M´etodo main del recomendador. 1public static void main ( String [] args ) { 2 3// Crea el servidor remoto 4try { 5new Catalog ( args ); 6 7} catch ( Exception re) { 8System .out . println (re ); 9System .exit (1) ; 10 } 11 12 // Pone el servidor a la espera 13 Object sync = new Object (); 14 synchronized(sync) { 70 29 ... 30 31 // Entrena cada BinarySMO 32 m_classifiers [i ][j]. buildClassifier (data , i, j, 33 m_fitLogisticModels , 34 m_numFolds , m_randomSeed ); 35 } 36 } 37 } E.2.5. El m´etodo DistributionForInstance El m´etodo DistributionForInstance es el encargado de predecir la clase a la que pertenece un nuevo dato desconocido. Para ello invoca el m´etodo SVMOutput de cada clasificador BinarySMO. Cada objeto BinarySMO se encarga de predecir a cu´al de las clases que compara es m´as probable que pertenezca el nuevo dato. Por tanto, cada invocaci´on al m´etodo SVMOutput sirve para asignar votos a cada una de las clases. El resultado que se devuelve es el porcentaje de votos que cada una de las clases existentes ha obtenido en la predicci´on. Este proceso de asignaci´on de votos puede verse en el bloque de c´odigo E.8. C´odigo E.8: M´etodo DistributionForInstance. 1public double [] distributionForInstance ( Instance inst ) throws Exception { 2 3// Comprobaciones iniciales 4... 5 6// Crea un vector donde almacenar los votos para cada clase 7double [] result = new double [ inst . numClasses () ]; 8 9// Para cada BinarySMO , ejecuta el metodo SVMOutput 10 for ( int i = 0; i < inst . numClasses (); i++) { 11 for ( int j = i + 1; j < inst . numClasses (); j++) { 12 if (( m_classifiers [i][j]. m_alpha != null ) || 13 ( m_classifiers [i][j]. m_sparseWeights != null )) { 14 double output = m_classifiers [i][j ]. SVMOutput (-1 , inst ); 71 15 16 // En funcion del resultado , asigna el voto 17 // a una u otra clase . 18 if ( output > 0) { 19 result [j] += 1; 20 } else { 21 result [i] += 1; 22 } 23 } 24 } 25 } 26 27 // Normaliza el resultado para que 28 // el resultado quede expresado en % 29 Utils . normalize ( result ); 30 31 return result; 32 } E.2.6. Modificaciones realizadas al algoritmo original En este apartado se describen las modificaciones que se requieren para adaptar el c´odigo implementado por Weka al problema tratado en este proyecto. La implementaci´on original presenta un inconveniente importante. Dado un conjunto de clases de entrenamiento, el m´etodo de predicci´on devuelve un conjunto con las probabilidades de que el nuevo texto pertenezca a cada una de las clases, pero presupone que pertenece a alguna de ellas. Seg´un este modelo, BCatalog no puede determinar que un nuevo texto no pertenece a ninguna de las clases y que por tanto no es del inter´es del usuario. A continuaci´on se detallan cada una de las decisiones tomadas para la modificaci´on del c´odigo inicial: Primero, los objetos BinarySMO ya no comparan dos clases de entremiento. En su lugar, cada uno de ellos se especializa en reconocer los objetos de una clase. Por este motivo la matriz de nxn clasificadores binarios se convierte en un vector de nde estos objetos. En cuanto al proceso de entrenamiento, los BinarySMO reconocen dos clases ficticias. Una clase es la llamada “SI”, que contiene los elementos del conjunto de datos inicial que pertenecen a la clase de la que se encargan. La otra clase es “NO”, que contiene 72 todos los dem´as. Esto quiere decir que todos los clasificadores binarios manejar´an todos los datos de entrenamiento, pero cada uno de ellos los tratar´a de manera diferente. El bloque de c´odigo E.9 ilustra esta nueva forma de entrenamiento. C´odigo E.9: M´etodo BuildClassifier adaptado. 1public void buildClassifier ( Instances insts ) throws Exception { 2 3// Comprobaciones iniciales 4... 5 6m_classIndex = insts . classIndex () ; 7m_classAttribute = insts . classAttribute () ; 8 9// Extrae los textos 10 ArrayList < String > textos = new ArrayList < String >(); 11 12 for ( Instance inst : insts ) { 13 String nueva = inst . stringValue (0) ; 14 textos .add ( nueva ); 15 } 16 17 ArrayList < Attribute > atributos = crearAttributes (textos); 18 19 // Crea los datasets para cada clasiffier 20 Instances [] subsets = new Instances [ insts . numClasses () ]; 21 22 for (int i=0; i< subsets . length ; i ++) { 23 ArrayList < String > clases = new ArrayList < String >(); 24 // Recorremos el conjunto de datos inicial , utilizando los 25 // valores de las clases SI y NO como corresponda 26 for ( Instance inst : insts ) { 27 if ( inst . value (1) == i) clases . add("SI"); 28 else clases . add("NO"); 29 } 30 subsets [i] = crearDataSet ( atributos , textos , clases ); 31 } 32 33 // Crea los clasificadores binarios 34 m_classifiers = new MiBinarySMO [ insts . numClasses () ]; 35 36 for ( int i = 0; i < subsets .length; i ++) { 73 37 m_classifiers [i] = new MiBinarySMO (); 38 } 39 40 // Entrena los clasificadores binarios 41 for (int i=0; i< subsets . length ; i ++) { 42 m_classifiers [i ]. buildClassifier ( subsets [i], 0, 1, 43 m_fitLogisticModels , 44 m_numFolds , m_randomSeed ); 45 } 46 } Por su parte, el proceso de predicci´on tambi´en es ligeramente distinto al original. Cada clasificador binario determina si el nuevo objeto pertenece a su clase ficticia “SI”. El nuevo resultado contendr´a tantas componentes con valor 1.0 como categor´ıas con las que el nuevo texto est´e relacionadas. Si el texto no est´a relacionado con ninguna de las clases de entrenamiento, el vector contendr´a nvalores 0.0. El bloque de c´odigo E.10 ilustra el nuevo m´etodo de predicci´on: C´odigo E.10: M´etodo DistributionForInstance adaptado. 1public double [] distributionForInstance ( Instance inst ) throws Exception { 2 3// Comprobaciones iniciales 4... 5 6double [] result = new double [ inst . numClasses () ]; 7 8for (int i = 0; i < inst. numClasses (); i++) { 9if (( m_classifiers [i]. m_alpha != null ) || 10 ( m_classifiers [i]. m_sparseWeights != null )) { 11 double output = m_classifiers [i]. SVMOutput ( -1 , inst ); 12 13 // Si el texto esta relacionado , se incrementa la componente 14 // correspondiente en el vector de resultados . 15 if ( output <= 0) { 16 result [i] = 1; 17 } else { 18 result[i] = 0 74 19 } 20 } 21 } 22 23 return result; 24 } E.3. Clase Zirano La clase Zirano ofrece un ´unico m´etodo que, dada una palabra, obtiene una lista de palabras relacionadas que extrae de la p´agina web de Zirano. Cuando un usuario quiere obtener esta lista de ideas a trav´es de la p´agina web, tiene que realizar una serie de pasos para localizar las palabras que le interesan. Los pasos son los siguientes: 1. Introduce la palabra de su elecci´on. 2. La web le ofrece un conjunto de ideas con las que se puede relacionar su palabra. 3. El usuario navega entre esas opciones, obteniendo para cada una un conjunto de palabras relacionadas. El m´etodo obtenerIdea simula esta navegaci´on, de forma que la web de Zirano devuelva los resultados que devolver´ıa a un usuario que recorriera todas las ideas relacionadas con su palabra. Para ello, realiza las siguientes operaciones: 1. Descarga la p´agina inicial de Zirano, y almacena la cookie que ´esta le envia. Dicha cookie identifica al usuario cuya navegaci´on se est´a simulando, y por tanto ser´a enviada en cada transacci´on a modo de identificador. 2. Se env´ıa a la web la palabra de la que se quiere obtener el campo conceptual. 3. La web responde con un listado de ideas a las que puede estar relacionadas. Se analiza y procesa el c´odigo HTML de la respuesta para obtener un listado de enlaces a los que enviar las siguientes peticiones. 4. Cada uno de los enlaces obtenidos constituye una petici´on a la web de un listado de palabras relacionadas con una idea en concreto. 5. Ante una de estas peticiones, la web responde con un listado de palabras que el m´etodo va almacenando. El c´odigo HTML de estas nuevas respuestas se filtra para quedarse ´unicamente con el listado de palabras. 75 6. Una vez completadas las peticiones para todas las ideas, o alcanzado un n´umero m´aximo de palabras almacenadas, la navegaci´on termina y el m´etodo devuelve los resultados. E.4. El paquete ´util Por ´ultimo se introducen algunas utilidades creadas para facilitar la implementaci´on del resto de m´odulos. E.4.1. Interfaz para el manejo de blogs En este apartado se explica c´omo el sistema obtiene los textos de Internet. Para poder implementarse esta funcionalidad se precisa de alguna herramienta que permita conocer qu´e textos forman la p´agina y cuando fueron publicados. Una herramienta ´util que existe para este cometido son los archivos XLM llamados Sitemap.xml [42], que incluyen la informaci´on, como su direcci´on URL, su t´ıtulo, su frecuencia de actualizaci´on o su fecha de publicaci´on. Un ejemplo del contenido de dichos archivos es el que aparece en el c´odigo E.11. C´odigo E.11: Ejemplo de sitemap.xml. 1<?xml version =" 1.0 " encoding ="UTF -8"?> 2<urlset 3xmlns =" http: // www . sitemaps . org/ schemas / sitemap /0.9" > 4<url > 5<loc >http: // www . example. com /</ loc > 6<lastmod >2005 -01 -01 </ lastmod > 7<changefreq >monthly </ changefreq > 8<priority >0.8 </ priority > 9</url > 10 </urlset> La existencia de este archivo no es obligatoria aunque s´ı muy recomendable, pues facilita la accesibilidad de la p´agina web y mejora el posicionamiento en los buscadores. A pesar de la gran variedad de sitios web que el usuario puede estar interesado en leer, este proyecto se centra en los desarrollados utilizando el CMS Wordpress, ya que todos ellos contienen un Sitemap y se puede localizar con facilidad aunque pueda estar guardado con otro nombre. 76 Por esta raz´on se ha creado una interfaz Java que permite la obtenci´on del Sitemap y su manipulaci´on, y una implementaci´on concreta para las p´aginas desarrolladas con Wordpress. Los m´etodos ofrecidos por esta interfaz aparecen en el c´odigo E.12. C´odigo E.12: ManejoBlogInterface. 1public interface ManejoBlogInterface { 2 3// Devuelve true si el blog tiene un Sitemap valido 4public boolean isValido (); 5 6// Obtiene una lista de Posts publicados despues de la fecha " limite" 7public ArrayList <Post > obtenerPosts ( Date limite ); 8 9// Descarga de nuevo el archivo sitemap . xml 10 public void actualizarSiteMap (); 11 } E.4.2. Manejo de c´odigo HTML Para el manejo de c´odigo HTML se ha creado una clase que ofrece m´etodos que otras clases pueden necesitar, y que se comentan a continuaci´on: La clase Zirano, que se detalla en el apartado E.3 necesita simular la navegaci´on efectuada por un usuario que desea obtener un campo conceptual. En el proceso, un navegador web intercambiar´ıa una cookie con el servidor de Zirano. Este intercambio se implementa con el m´etodo obtenerCookie. La descarga del c´odigo HTML de una p´agina web se realiza mediante el m´etodo obtenerHTML que recibe como par´ametros, adem´as de su direcci´on URL, un n´umero m´aximo de intentos de descarga tras los cuales se aborta la operaci´on y se devuelve un error. El m´etodo obtenerPagina devuelve un objeto de tipo Post, con el t´ıtulo, la direcci´on URL y el texto filtrado de la p´agina descargada. El m´etodo filtrarHTML se utiliza para eliminar las etiquetas HTML y l´ıneas en blanco de la cadena que recibe como par´ametro. El resultado es una cadena de texto que contiene el texto plano de la p´agina, y que es utilizada por la m´aquina de aprendizaje. 77 De ah´ı la importancia de la eficacia de este m´etodo, pues es necesario que el texto a analizar contenga la m´ınima cantidad de informaci´on no relacionada con ´el. El bloque de c´odigo E.13 contiene los prototipos de cada uno de los m´etodos: C´odigo E.13: Clase HTML. 1public class HTML { 2 3public static Post obtenerPagina ( String url) throws CatalogException { ... } 4 5protected static String obtenerHTML ( 6String direccionUrl , String cookie , int intentos ) { ... } 7 8protected static String obtenerCookie ( String direccionUrl , int intentos ) { ... } 9 10 public static String filtrarHTML (String html) { ... } 11 } E.4.3. Utilidades de conversi´on La clase Conversiones incluye los m´etodos para convertir datos de distintos tipos que han sido necesarias en algunos m´odulos del sistema. El c´odigo E.14 muestra los prototipos de dichos m´etodos. C´odigo E.14: Clase Conversiones. 1public class Conversiones { 2 3// Devuelve el double representado por la cadena s 4public static double atof(String s) { ... } 5 6// Devuelve el entero representado por la cadena s 7public static int atoi ( String s) { ... } 8 9// Devuelve la representacion en forma de cadena de la fecha d 10 public static String datetostring (Date d) { ... } 11 // Devuelve la fecha representada por la cadena s 12 78 13 public static Date stringtodate ( String s) { ... } 14 } E.4.4. La clase es Stemmer La clase Stemmer implementa el lematizador que calcula la ra´ız de una palabra. Se basa en el algoritmo de Porter[32], y es utilizada por el sistema cuando se calculan los campos conceptuales. Es importante mencionar que la clase se descarg´o de un foro de internet en el que alguien preguntaba donde pod´ıa conseguir una implementaci´on de un lematizador en Java. En al c´odigo fuente no aparece la p´agina web del autor, as´ı que no puedo incluir su referencia. Seg´un se explicaba en aquel foro, se trata de una traducci´on de la implementaci´on escrita en PHP[43] que puede descargarse de SourceForge [31]. Anexo F El sistema de gesti´on de la persistencia En este apartado se explica en detalle la estructura del sistema de gesti´on de la persistencia, que incluye una base de datos donde se almacena la informaci´on necesaria para el funcionamiento del sistema y un conjunto de clases Java que ofrecen una interfaz de comunicaci´on con ella. El apartado F.1 contiene la explicaci´on sobre la estructura de la base de datos y una serie de consideraciones previas que justifican la existencia de sus tablas. En el apartado F.2 se introducen las clases que manejan la base de datos y se concreta con qu´e tablas interacciona cada una de ellas. F.1. La base de datos La base de datos se aloja en un servidor MySQL, y contiene 9 tablas donde se almacenan los blogs, los textos manejados por el sistema, la informaci´on referente a palabras y campos conceptuales, las clases de entrenamiento, los textos de ejemplo, las recomendaciones y otra informaci´on necesaria para el funcionamiento del sistema. Su estructura completa puede verse en la figura F.1, que muestra todas las tablas existentes, los campos que las forman y c´omo se relacionan unas tablas con otras. Para obtener esta estructura final ha sido necesario tener en cuenta algunas consideraciones que se comentan a continuaci´on. La descarga de un texto desde internet requiere conectarse a un servidor web externo para solicitarle el c´odigo HTML de la p´agina donde aparece dicho texto. El c´odigo HTML recibido hay que filtrarlo para eliminar informaci´on que no sea relevante y 79 86 Figura G.1: Niveles de paralelizaci´on de la m´aquina SVM. dos cadenas, y los otros dos se utilizan para normalizar el resultado, como ilustra la ecuaci´on C.2 en el anexo C,La M´aquina de Vectores de Soporte. El bloque de c´odigo G.1 contiene el c´odigo Java que compara las dos cadenas y normaliza el resultado obtenido para que est´e comprendido entre 0 y 1. C´odigo G.1: C´odigo paralelizable en la clase StringKernel 1public double normalizedKernel ( char [] s , char [] t){ 2 3// Compara cada cadena consigo misma 4double k1 = unnormalizedKernel (s, s); 5double k2 = unnormalizedKernel (t, t); 6 7// Calcula el factor de normalizacion 8double normTerm = Math. sqrt( k1*k2 ); 9 10 // Compara una cadena con otra y devuelve 11 // el resultado normalizado 12 return unnormalizedKernel (s, t) / normTerm ; 13 } 87 Estudiando el m´etodo unnormalizedKernel en profundidad puede comprobarse que en ning´un momento modifica las cadenas que recibe como par´ametros. Por ello, y dado que las tres invocaciones a este m´etodo utilizan datos que no dependen unos de otros, pueden ejecutarse en paralelo. El bloque de c´odigo G.2 muestra una ligera modificaci´on del c´odigo anterior, a la que ya se le puede introducir el trabajo en paralelo: C´odigo G.2: C´odigo paralelizable en la clase StringKernel 1public double normalizedKernel ( char [] s , char [] t){ 2 3// Compara cada cadena consigo misma 4double k1 = unnormalizedKernel (s, s); 5double k2 = unnormalizedKernel (t, t); 6 7// Compara una cadena con otra 8double k3 = unnormalizedKernel (s,t); 9 10 // LAS TRES LLAMADAS ANTERIORES 11 // PUEDEN LANZARSE EN PARALELO . 12 // CUANDO TODAS TERMINEN PUEDE 13 // EJECUTARSE EL CODIGO A CONTINUACION 14 15 // Calcula el factor de normalizacion 16 double normTerm = Math. sqrt( k1*k2 ); 17 18 // Devuelve el resultado de la comparacion 19 // normalizado . 20 return k3 / normTerm ; 21 } Tras esta modificaci´on menor en el c´odigo original pueden crearse tres objetos de la clase Thread de Java, asignarles a cada uno una de las llamadas al m´etodo unnormalizedKernel y esperar a que todos terminen para generar el resultado a devolver. G.2. Paralelismo en la clase BinarySMO En este apartado se introducen las modificaciones que se pueden realizar en el c´odigo de la clase BinarySMO para implementar la paralelizaci´on de sus tareas de entrenamiento y predicci´on. 88 Es la parte m´as complicada de este proceso, pues se trata de trabajos iterativos y no siempre puede asegurarse de que las diferentes iteraciones sean independientes entre ellas, de forma que el orden de ejecuci´on no altere los resultados. En el apartado G.2.1 se profundiza en el estudio del c´odigo del m´etodo buildClassifier realizado. Por otra parte, el estudio del m´etodo SVMOutput se comenta en el apartado G.2.2. G.2.1. El m´etodo buildClassifier En el m´etodo buildClassifier se realiza una b´usqueda de los vectores de soporte que el clasificador utilizar´a en la fase de predicci´on. Esta b´usqueda se lleva a cabo de forma incremental, utilizando en cada iteraci´on los vectores encontrados hasta ese momento y utiliz´andolos para encontrar otros nuevos. El bloque de c´odigo G.3 muestra el bucle principal del m´etodo. Como puede verse, no hay un n´umero fijo de iteraciones, sino que en funci´on de los resultados se van asignando valores a las variables numChanged yexamineAll. Por ese motivo las iteraciones no pueden ejecutarse en paralelo. C´odigo G.3: Resumen del m´etodo BuildClassifier 1public synchronized void buildClassifier ( Instances insts ...) throws Exception { 2 3// Ajustes iniciales 4... 5 6// Bucle de busqueda 7while (( numChanged > 0) || examineAll ) { 8numChanged = 0; 9 10 if ( examineAll ) { 11 for (int i = 0; i < m_alpha .length; i ++) { 12 if (examineExample(i)) { 13 numChanged ++; 14 } 15 } 16 } else { 17 ... 18 } 19 } 89 20 21 // Ajustes finales 22 ... 23 } Dentro de cada iteraci´on, el m´etodo examineExample se ejecuta un n´umero fijo de veces, pues el valor de m alpha.length no se modifica ni en ese bucle ni dentro del m´etodo. Por tanto las iteraciones de este bucle interno podr´ıan ejecutarse en paralelo, si no fuera porque dentro del m´etodo se utilizan variables cuyos valores se van modificando a lo largo de las iteraciones del bucle principal. Por ese motivo se descarta esta segunda opci´on de paralelizaci´on. El m´etodo examineExample contiene ajustes iniciales y una llamada al m´etodo takeStep. El bloque de c´odigo G.4 muestra las acciones m´as relevantes ejecutadas por cada uno de ellos. C´odigo G.4: Resumen de los m´etodos examineExample y TakeStep 1protected boolean examineExample ( int i2 ) throws Exception { 2 3// Comprobaciones iniciales 4... 5 6return takeStep (i1 , i2 , F2); 7} 8 9 10 protected boolean takeStep (int i1 , int i2 , double F2) throws Exception { 11 12 // Comprobaciones iniciales 13 ... 14 15 // Llamadas al Kernel que son 16 // paralelizables 17 k11 = m_kernel . eval (i1 , i1 , m_data . instance ( i1)); 18 k12 = m_kernel . eval (i1 , i2 , m_data . instance ( i1)); 19 k22 = m_kernel . eval (i2 , i2 , m_data . instance ( i2)); 20 21 // Mas ajustes 22 ... 90 23 24 // Llamadas al metodo de prediccion 25 // paralelizables 26 f1 = SVMOutput (i1 , m_data . instance (i1 )); 27 f2 = SVMOutput (i2 , m_data . instance (i2 )); 28 29 // Ajuste de vectores de soporte 30 if (a1 > 0) { 31 m_supportVectors . insert (i1); 32 } 33 ... 34 35 // Otros ajustes 36 for ( int j = m_I0. getNext ( -1) ; j != -1; j = m_I0 . getNext (j)) { 37 if ((j != i1 ) && (j != i2)) { 38 m_errors [j] += 39 y1 * (a1 - alph1 ) * m_kernel . eval (i1 , j, m_data . instance ( i1)) + 40 y2 * (a2 - alph2 ) * m_kernel . eval (i2 , j, m_data . instance ( i2)); 41 } 42 } 43 44 return true; 45 } Las invocaciones al Kernel y al m´etodo SVMOutput pueden ser ejecutadas en paralelo puesto que s´olo reciben par´ametros de entrada y no hay dependencias de escritura. En cambio, los ajustes iniciales y la actualizaci´on de los vectores de soporte dependen entre iteraciones. Del p´arrafo anterior se puede deducir que no pueden realizarse invocaciones paralelas al m´etodo examineExample, pero s´ı es posible ejecutar al mismo tiempo algunas de sus operaciones internas. G.2.2. El m´etodo SVMOutput El m´etodo SVMOutput es el m´etodo que ejecuta la tarea de predicci´on en un objeto BinarySMO. En su interior se realizan una serie de comprobaciones iniciales y, tras ellas, se invoca al Kernel SSK para que compare el nuevo dato con cada uno de los vectores de soporte conocidos. El resultado de cada comparaci´on se utiliza para ir acumulando 91 el resultado devuelto. El resumen de este m´etodo puede verse en el bloque de c´odigo G.5 C´odigo G.5: Resumen del m´etodo SVMOutput 1public double SVMOutput ( int index , Instance inst ) throws Exception { 2 3// Comprobaciones iniciales 4... 5 6double result = 0; 7 8// Compara con cada vector de soporte 9// y acumula el resultado 10 11 for ( int i = m_supportVectors . getNext ( -1); i != -1; 12 i = m_supportVectors . getNext (i)) { 13 result += m_class [i] * m_alpha [i] * m_kernel . eval (index , i, inst ); 14 } 15 16 // Ultimo ajuste del resultado y devolucion 17 result -= m_b ; 18 19 return result; 20 } Las iteraciones del bucle son independientes entre s´ı. La variable result va acumulando el resultado en cada iteraci´on y la unica precauci´on necesaria es que la consulta de su valor y la actualizaci´on se hagan en exclusi´on mutua. Teniendo en cuenta ese detalle no hay ning´un inconveniente en que las invocaciones al Kernel se hagan en paralelo. G.3. Paralelismo en la clase SMO La clase SMO es el clasificador SVM que BCatalog utiliza para aprender las preferencias del usuario y recomendarle lecturas de su inter´es. Durante la operaci´on de entrenamiento del clasificador se crean tantos clasificadores binarios como clases de entrenamiento, proporcionando a cada uno una copia del conjunto de datos de ejemplo debidamente etiquetados. 92 Entrenar el sistema consisiste pues en entrenar cada uno de los objetos BinarySMO. Puesto que reciben una copia propia del conjunto de datos pueden entrenarse en paralelo sin necesidad de ning´un mecanismo de control ni otras medidas para garantizar la correcci´on de los entrenamientos individuales. La fase de predicci´on se realiza de la misma manera. Una vez entrenados dichos objetos, el m´etodo distributionForInstance ofrecido por el clasificador SVM invoca al m´etodo SVMOutput de los clasificadores binarios y opera con los resultados. Todas estas invocaciones tambi´en pueden realizarse en paralelo para obtener mejoras en los tiempos de ejecuci´on. G.4. Consideraciones sobre las alternativas Es importante conocer los efectos que cada una de las alternativas de paralelizaci´on producir´an en el rendimiento del sistema. A continuaci´on se introducen los beneficios estimados de cada una de ellas: La paralelizaci´on de tareas a nivel m´as bajo, en el m´etodo de evaluaci´on del Kernel SSK, supone mejoras tanto en operaciones de entrenamiento como de predicci´on. Como se ha comentado, con esta alternativa se realizan tres c´alculos en paralelo, y por tanto el tiempo de ejecuci´on de una evaluaci´on queda en teor´ıa acotado por el m´aximo de los tiempos de estos tres c´alculos. Por contra, si se implementan otras alternativas se crean demasiadas tareas en paralelo y es posible que los efectos producidos por esta alternativa se vean reducidos al crear y destruir los hilos de ejecuci´on. La segunda alternativa de paralelizaci´on, los m´etodos ofrecidos por los objetos BinarySMO obtiene mejores resultados al aumentar el n´umero de datos de ejemplo, puesto que se ejecutan en paralelo buena parte de las invocaciones al Kernel SSK. Un inconveniente de esta alternativa es que si varios de estos objetos trabajan al mismo tiempo el n´umero hilos de ejecuci´on aumenta significativamente. Este inconveniente se agrava si se combina con la alternativa anterior. La tercera alternativa de paralelizaci´on consiste en que los objetos BinarySMO trabajen en paralelo, como se ha comentado en el apartado G.3. Esta alternativa resulta ventajosa si el n´umero de clases de entrenamiento (clases de inter´es del usuario) aumenta. Cuantas m´as clases, mayor n´umero de entrenamientos y predicciones se ejecutan al mismo tiempo. 93 La elecci´on de qu´e niveles de paralelismo implementar no es trivial, pues depende del n´umero de clases de entrenamiento, de la cantidad de textos de ejemplo y de la potencia de c´alculo disponible en la m´aquina en la que se ejecuta el sistema. La soluci´on optima requiere un estudio del servicio que se desea ofrecer y de las infraestructuras disponibles. En la construcci´on de este prototipo se ha decidido implementar los dos niveles superiores, dejando la paralelizaci´on de la funci´on de evaluaci´on del Kernel SSK para implementaciones futuras. G.5. Implementaci´on de las mejoras Para la implementaci´on de las mejoras propuestas se ha a˜nadido un objeto CachedThreadPool a los objetos SMO yBinarySMO. La clase CachedThreadPool [44] implementa un gestor de tareas concurrentes. Cuando se le solicita que ejecute un trabajo en paralelo crea un hilo de ejecuci´on y le asigna la tarea. Cuando ´este termina se encarga de destruirlo de forma transparente al programador. Una ventaja importante que proporciona es la reutilizaci´on de hilos de ejecuci´on una vez terminan su trabajo de forma que no sea necesario crearlos de nuevo ante una nueva solicitud de trabajo. Esta caracter´ıstica ayuda a reducir la penalizaci´on en tiempo derivadas de la creaci´on y destrucci´on de nuevos hilos de ejecuci´on puesto que s´olo se crean cuando no hay ningun hilo disponible, y se destruyen cuando pasado un tiempo un hilo no recibe tareas a ejecutar. Los objetos CachedThreadPool pueden recibir cualquier objeto que implemente la interface Runnable, como por ejemplo objetos de la clase Thread,Task oFutureTask[45]. La clase FutureTask ejecuta un bloque de c´odigo en paralelo y proporciona un m´etodo con el que se puede recuperar el resultado de su tarea. Es la implementaci´on elegida en este prototipo puesto que el c´odigo a ejecutar en paralelo consiste en m´etodos que devuelven un resultado. Introducidas las herramientas a utilizar, se pasa a describir el proceso de modificaci´on del c´odigo fuente. El bloque de c´odigo G.6 muestra la versi´on secuencial inicial y, a continuaci´on, el c´odigo que resulta de la inclusi´on de paralelismo. 94 C´odigo G.6: Ejemplo de paralelizaci´on de c´odigo 1// INVOCACION SECUENCIAL 2k11 = m_kernel . eval (i1 , i1 , m_data . instance ( i1)); 3k12 = m_kernel . eval (i1 , i2 , m_data . instance ( i1)); 4k22 = m_kernel . eval (i2 , i2 , m_data . instance ( i2)); 5 6// INVOCACION EN PARALELO 7 8// Crea FutureTasks que devuelven 9// valores de tipo double 10 FutureTask < Double > t11 , t12 , t22; 11 12 // Asigna a cada FutureTask la tarea 13 // a realizar 14 t11 = new FutureTask < Double >( 15 new TareaEval (m_kernel , i1 , i1 , 16 m_data. instance ( i1))); 17 t12 = new FutureTask < Double >( 18 new TareaEval (m_kernel , i1 , i2 , 19 m_data. instance ( i1))); 20 t22 = new FutureTask < Double >( 21 new TareaEval (m_kernel , i2 , i2 , 22 m_data. instance ( i2))); 23 24 // Envia las tareas al gestor 25 executor . submit (t11 ); 26 executor . submit (t12 ); 27 executor . submit (t22 ); 28 29 // Recoge los resultados 30 k11 = t11 .get () ; 31 k12 = t12 .get () ; 32 k22 = t22 .get () ; En primer lugar se crean los objetos FutureTask, que ejecutar´an tareas que devuelven datos de tipo Double con los resultados de la operaci´on. Estas tareas se env´ıan al gestor de tareas, llamado executor en el c´odigo. Por ´ultimo se almacenan los resultados conforme las tareas van terminando. Anexo H Evaluaci´on del prototipo. Experimentos En este apartado se incluye informaci´on de inter´es relacionada con los experimentos realizados sobre el sistema. Esta informaci´on incluye: 1. El script que lanza los experimentos: Lanza el servidor y el cliente y, tras la ejecuci´on de la tarea, finaliza ambos procesos. El servidor se lanza tanto en modo secuencial como en paralelo. Ver bloque de c´odigo H.1. 2. El script .sub necesario para la ejecuci´on bajo Condor. Ver bloque de c´odigo H.2. 3. Salida producida por Condor: Las estad´ısticas generadas por Condor en la ejecuci´on del experimento en la m´aquina Selene2. Ver bloque de c´odigo H.3. 4. Salida producida por BCatalog: Informaci´on generada por BCatalog para el trazado de ejecuci´on. Ver bloque de c´odigo H.4. 5. Uso de memoria y CPU en Windows: Capturas de pantalla en ejecuciones secuencial y paralela en la m´aquina de Gregorio de Miguel. Ver figuras H.1 yH.2. 95 102 ´ Indice de figuras D.1. Estructura del m´odulo de vista. ....................... 55 E.1. Estructura del motor de recomendaciones. ................. 61 F.1. Estructura de la base de datos. ....................... 80 F.2. Estructura del paquete DAO. ........................ 82 G.1. Niveles de paralelizaci´on de la m´aquina SVM. ............... 86 H.1. Uso de memoria y CPU en ejecuci´on secuencial. .............. 99 H.2. Uso de memoria y CPU en ejecuci´on paralela. ............... 99 Bibliograf´ıa [1] J. J. Merelo and F. Tricas, “M´etrica de la blogosfera. algunas medidas y relaciones en la blogosfera hispana,” Telos: Cuadernos de comunicaci´on e innovaci´on, vol. 65, pp. 101–104, 2005. [2] H. Liu, P. S. Yu, N. Agarwal, and T. Suel, “Guest editors’ introduction: Social computing in the blogosphere,” IEEE Internet Computing, vol. 14, no. 2, pp. 12– 14, 2010. [3] “Real Academia Espa˜nola.” http://www.rae.es/rae.html. [4] “Word Reference.” http://www.wordreference.com. [5] “Diccionario Ideol´ogico de Zirano.” http://www.zirano.com. [6] “Servicio de Blogs Wordpress.” http://www.wordpress.com. [7] “Servicio de Blogs BlogSpot.” http://www.blogspot.com. [8] “CMS Xoops.” http://www.xoops.org. [9] “CMS Joomla.” http://www.joomla.org. [10] “CMS PHP-Nuke.” http://www.phpnuke.org. [11] “WordPress, versi´on de descarga.” http://www.wordpress.org. [12] “FrameWork MVC CodeIgniter.” http://www.codeigniter.com. [13] J. Han and M. Kamber, Data Mining: Concepts and Techniques. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2005. [14] B. Scholkopf and A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. Cambridge, MA, USA: MIT Press, 2001. [15] T. Gartner, J. W. Lloyd, and P. A. Flach, “Kernels for structured data,” SIGKDD EXPLORATIONS, vol. 5, pp. 49–58, 2002. 103 104 Bibliograf´ıa [16] J. F¨urnkranz, “Pairwise classification as an ensemble technique,” in Proceedings of the 13th European Conference on Machine Learning (ECML-02) (T. Elomaa, H. Mannila, and H. Toivonen, eds.), vol. 2430 of Lecture Notes in Artificial Intelligence, (Helsinki, Finland), pp. 97–110, Springer-Verlag, 2002. [17] H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, C. Watkins, and B. Scholkopf, “Text classification using string kernels,” Journal of Machine Learning Research, vol. 2, pp. 563–569, 2002. [18] A. K. Seewald and F. Kleedorfer, “Lambda pruning: an approximation of the string subsequence kernel for practical svm classification and redundancy clustering,” Adv. Data Analysis and Classification, vol. 1, no. 3, pp. 221–239, 2007. [19] “Lenguaje de programaci´on Java.” http://java.com/es/. [20] “Servidor Web Apache.” http://www.apache.org. [21] “Extensi´on Tomcat para Apache.” http://tomcat.apache.org. [22] “Est´andar HTML.” http://www.w3.org/html. [23] “Est´andar CSS.” http://www.w3.org/css. [24] “Java Beans, Java Entreprise Edition.” http://www.oracle.com/technetwork/ java/javase/tech/index-jsp-138795.html. [25] “Java Server Faces.” http://www.oracle.com/technetwork/java/javaee/ javaserverfaces-139869.html. [26] “Java RMI.” http://www.oracle.com/technetwork/java/javase/tech/ index-jsp-136424.html. [27] “Clasificadores Weka.” http://www.cs.waikato.ac.nz/ml/weka/. [28] “Bases de datos MySQL.” http://http://www.mysql.com/. [29] “Driver Java DataBase Connection.” http://www.oracle.com/technetwork/ java/javase/tech/index-jsp-136101.html. [30] “Clase Thread de Java.” http://download.oracle.com/javase/1.4.2/docs/ api/java/lang/Thread.html. [31] “Lematizador para idioma Espa˜nol.” http://stemmer-es.sourceforge.net/. [32] “Algoritmo de lematizaci´on de Porter.” http://tartarus.org/~martin/ PorterStemmer/. Bibliograf´ıa 105 [33] “Interface ExecutorService de Java.” http://download.oracle.com/javase/1, 5.0/docs/api/java/util/concurrent/ExecutorService.html. [34] “Interface Runnable de Java.” http://download.oracle.com/javase/1,5.0/ docs/api/java/util/concurrent/ExecutorService.html. [35] “Diario Heraldo de Arag´on.” http://www.heraldo.es. [36] “Peri´odico deportivo Marca.” http://www.marca.es. [37] “Diario El Pa´ıs.” http://www.elpais.com. [38] “Cluster Hermes. Universidad de Zaragoza.” http://web.hermes.cps.unizar. es/ganglia/. [39] “Proyecto Condor.” http://www.cs.wisc.edu/condor/. [40] “Est´andar XML.” http://www.w3.org/XML/. [41] “Librer´ıa JArgs.” http://jargs.sourceforge.net. [42] “Archivo SiteMap.xml.” http://www.w3.org/WAI/sitemap.html. [43] “Lenguaje PHP.” http://www.php.net. [44] “Clase CachedThreadPool de Java.” http://download.oracle.com/ javase/1.5.0/docs/api/java/util/concurrent/Executors.html# newCachedThreadPool(). [45] “Clase FutureTask de Java.” http://download.oracle.com/javase/1.5.0/ docs/api/java/util/concurrent/FutureTask.html.