Repositorio Institucional de Documentos

Proyecto Fin de Carrera Evaluation of a Hierarchical Taxonomy Preparation Method for Document Classification Autora Sara Gracia Hernández Director Dr. Wolf-Tilo Balke Ponente Dr. Eduardo Mena Escuela de Ingeniería y Arquitectura Septiembre 2013 I II AGRADECIMIENTOS A mi madre Paqui y a mi hermana Beatriz por confiar en mí; a mi padre Miguel Ángel por darme fuerzas desde la distancia; a Eduardo por ser la constante de mi vida; a mis abuelos y mis tíos por apoyarme siempre , a mis amigas por tantos momentos vividos a mis amigos Erasmus, por este gran año, y para terminar, a mi director Simon Barthel, que pese a las dificultades del idioma, ha tenido paciencia y me ha guiado en el trabajo. III IV Evaluation of a Hierarchical Taxonomy Preparation Method for Document Classification RESUMEN Para la realización de entornos virtuales de investigación en el campo de las matemáticas, el acceso de manera óptima a la literatura de conocimiento matemático es fundamental. El continuo crecimiento de información ha provocado que el acceso a los segmentos relevantes sea prácticamente imposible, además de ocasionar que el proceso de clasificación de los documentos por parte tanto de los centros de información y las bibliotecas sea cada día más difícil y complejo. La base de datos “Zentralblatt Mathematik” de FIZ Karksruhe y el portal Get-Info del TIB Hannover reciben diariamente grandes cantidades de documentos matemáticos y usan el método de clasificación MSC (Mathematical Subject Classification) para indexarlos de forma manual. Debido a esta sobrecarga de información, es necesario apoyar el trabajo de los bibliotecarios para el trabajo de indexación diario. Por esta razón, el proyecto , dentro del cual se sitúa este Proyecto Final de Carrera, investiga procesos automatizados para la indexación de contenido basado en taxonomías e información contextual en el campo de las matemáticas. Los objetivos de este proyecto han sido evaluar una aproximación para la introducción de superclases sobre la clasificación MSC, implementar el método y evaluarlo con datos de una biblioteca digital matemática, para mejorar el rendimiento global de la clasificación y a su vez, examinar la estructura de la taxonomía MSC. El acceso a la biblioteca digital matemática se ha realizado a través de un corpus de datos perteneciente a un subconjunto de una librería digital matemática. Este corpus está en formato JSON, y está formado por documentos, categorías (MSC) y términos, los cuales son la base del algoritmo que se ha desarrollado. El algoritmo está definido en el paper "Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning". Se ha implementado en MATLAB y consiste en la creación de dos matrices base y en aplicar una serie de técnicas de descomposición sobre ellas, entre las que se encuentran principalmente SVD (Singular Value Decomposition) y GSVD (Generalized Singular Value Decomposition) , para la creación de un vector integrado normalizado, el cual se clusteriza para la obtención del k-particionamiento de categorías. La idea principal del método es aprovechar la información complementaria que se encuentra en ambas matrices, siendo los documentos el puente entre las categorías y los términos, para conseguir un clustering de categorías más razonable y eficaz. Para determinar el número de óptimo de clusters se ha aplicado la técnica Intra-Cluster Distance Measure y para realizar el clustering de categorías se ha usado la función KMEANS. Una vez que el algoritmo ha sido implementado, el siguiente paso es la construcción de la taxonomía jerárquica; para ello, el algoritmo se aplica de forma recursiva para obtener la jerarquía de categorías. Para evaluar el algoritmo, se han realizado las siguientes aproximaciones, y se han comparado los resultados con la clasificación de categorías MSC.  Subconjunto del corpus de datos  Categorías del primer nivel de MSC  Subconjunto de categorías, con el mismo primer nivel  Subconjuntos de categorías bien definidos V VI INDICE 1. Introducción............................................................................................................................. 1 1.1 Motivación …………............................................................................................... 2 1.2 Contexto de desarrollo............................................................................................... 3 1.3 Objetivos del proyecto ............................................................................................... 5 1.4 Estructura de la memoria ........................................................................................... 6 2. Análisis del Problema.............................................................................................................. 9 2.1 Algoritmo CBSGC………………………………………………………………… 9 2.2.1 Antecedentes…………………………………………………………… 9 2.2.2Coclustering basado en Documento – Término………………………… 10 2.2.3 Coclustering basado en Categoría-Documento………………………… 11 2.2.4 Problema SVD y GSVD……………………………………………........ 12 2.2.5 Pasos del algoritmo……………………………………………………… 13 2.2 Corpus de Datos……………………………………………………………………… 15 3. Diseño………………………………………………………………………………………...... 17 3.1 Corpus de Datos……………………………………………………………………... 17 3.2 Variables y Vectores…………………………………………………………………. 18 3.3 Matrices……………………………………………………………………………... 21 3.4 k-particionamiento………………………………………………………………… 23 4. Implementación……………………………………………………………………………... 25 4.1 Lenguaje de Programación……………………………………………………….... 25 4.2 Lectura del Fichero………………………………………………………………… 26 4.3 Algoritmo……………………………………………………………………………. 27 4.4 Taxonomía Jerárquica………………………………………………………………. 32 5. Resultados Obtenidos…………………………………………………………………………. 35 5.1 Experimento 1………………………………………………………………………. 35 5.2 Experimento 2………………………………………………………………………. 38 5.3 Experimento 3………………………………………………………………………. 40 5.4 Experimento 4………………………………………………………………………. 41 5.5 Análisis de los resultados............................................................................................. 45 6. Conclusiones………………………………………………………………………………… 47 6.1 Consecución de Objetivos………………………………………………………..... 47 6.2 Valoración Personal………………………………………………………………… 48 7. Bibliografía……………………………………………………………………………………. 49 Anexos…………………………………………………………………………………………. 51 A. Paper “Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning”……………………………… 53 VII B. Clasificación MSC………………………………………………………………..... 65 C. SVD y GSVD……………………………………………………………………........ 69 D. Corpus de Datos…………………………………………………………………........ 73 E. Clustering – k-means……………………………………………………………........ 77 F. Algoritmo CBSGC......................................................................................................... 93 G. Gestión del Proyecto………………………………………………………………...... 95 Índice de Figuras…………………………………………………………………………............. 97 Índice de Tablas………………………………………………………………………………… 99 1 1. INTRODUCCIÓN Este Proyecto Final de Carrera surge de la necesidad de facilitar el trabajo a los bibliotecarios de documentación matemática en su trabajo diario de indexación de documentos. Esta necesidad surge principalmente debido al incremento de información que ocurre hoy en día, lo cual afecta de forma directa a los proveedores de esta. El propósito de este proyecto es obtener una primera aproximación para intentar sustituir el trabajo manual de indexación de documentación matemática hecho por expertos, para poder realizar la clasificación de forma automática de acuerdo a la clasificación MSC. Los primeros experimentos han mostrado que los clasificadores para el primer nivel de las taxonomías tienen una pérdida en el rendimiento global, en comparación con el trabajo manual hecho por los expertos. Es aquí donde este proyecto final de carrera cobra sentido, su propósito es analizar si se pueden obtener mejores resultados si introducimos superclases en la taxonomía como un primer nivel de clasificación, para profundizar después en la jerarquía. El trabajo realizado en este proyecto ha consistido en evaluar una aproximación para la introducción de superclases sobre la clasificación MSC, implementar el método y evaluarlo con datos de una biblioteca digital matemática, para mejorar el rendimiento global de la clasificación y a su vez, examinar la estructura de la taxonomía MSC. Como fuente de datos, se ha accedido a un corpus de datos perteneciente a una la biblioteca matemática digital. Este corpus de datos está formado por documentos, categorías (MSC) y términos, los cuales son la base del algoritmo que se ha implementado para conseguir el propósito del proyecto. Este algoritmo está definido en el paper "Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning" (para más información sobre el mismo consultar Anexo A). Consiste en la creación de dos matrices base y en aplicar una serie de técnicas de descomposición sobre ellas, para la creación de un vector integrado normalizado, el cual se clusteriza para la obtención del k-particionamiento de categorías. La idea principal del método es aprovechar la información complementaria que se encuentra en ambas matrices, siendo los documentos el puente entre las categorías y los términos, para conseguir un clustering de categorías más razonable y eficaz. . Una vez que el algoritmo ha sido implementado, el siguiente paso es la construcción de la taxonomía jerárquica y su posterior análisis. 8 9 2. ANÁLISIS DEL PROBLEMA Este capítulo consta de dos apartados, en el primero se va presentar el algoritmo Consistent Bipartite Spectral Graph Copartitioning definido en el paper "Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning” , con el cual se pretende conseguir una primera aproximación para el cálculo de superclases en la taxonomía. En el segundo apartado se va a analizar el corpus de datos con el que se va a trabajar para poder realizar la categorización de los documentos. 2.1 Algoritmo CBSGC (Consistent Bipartite Spectral Graph Copartitioning) Antes de centrarnos en el algoritmo, se va a hacer una breve introducción sobre la base en la que se apoya este, que nos servirá para poder entender qué hace y cómo funciona. En primer lugar se introducirá la representación de los documentos, la cual es necesaria para poder presentar el problema de coclustering de documento-término, en segundo lugar las categorías, las cuales sirven para representar el problema de coclustering categoría-documento, a continuación se explicará en qué consiste el problema Singular Value Decomposition y el problema Generalized Singular Value Decomposition y finalmente se abordará el algoritmo CBSGC. 2.2.1 Antecedentes Existen diferentes métodos para abordar el problema de la clasificación multiclase. Una de las estrategias que se puede seguir son las máquinas de soporte vectorial, que utilizan la estrategia one-against-rest. La idea es construir un modelo capaz de predecir si un nuevo dato, cuya categoría se desconoce, pertenece a una categoría o a la otra. Este tipo de clasificadores trabajan bien cuando el número de categorías es pequeño, pero desde hace varios años, el problema de las escalas de la clasificación multiclase se está viendo incrementada. Debido a la gran magnitud de datos, trabajar con métodos que se basan en información plana, hacen que la escalabilidad del método se vea afectada y que los tiempos de cómputo y de entrenamiento se vean afectados. Para abordar este problema se propone el uso de la estructura jerárquica interna existente entre las categorías para dividir la tarea de clasificación. Como resultado se obtiene una máquina 10 de soporte vectorial jerárquica, en la que cada categoría hijo es entrenado para ser distinguido con otras categorías con el mismo padre. Sin embargo, no todos los corpus de datos tienen una taxonomía jerárquica dada de forma explícita, por lo que en muchos casos este tipo de clasificación no se puede llevar a cabo. Para afrontar este problema, se necesita extraer una jerárquica de los datos y usarla para organizar los clasificadores jerárquicos, es decir, pre-procesar el corpus de datos para prepararlo para realizar la clasificación jerárquica La solución adoptada y propuesta en este paper consiste en usar un grafo bipartito para representar la relación existente entre categorías y documentos, y usar otro para representar la relación entre documentos y términos, y a continuación particionar ambos grafos consistentemente resolviendo un problema de descomposición en valores singulares generalizado (GSVD). 2.2.2 Coclustering basado en Documento – Término La idea en la que se basa el coclustering de documentostérminos es tratar los términos de cada documento como si fueran características. es la representación de los documentos existentes en el corpus y los términos. A partir de esto, podemos representar la relación entre documentos y términos con un grafo bipartito no direccionado (ver figura 3). Este grafo lo representamos con el triplete , donde E representa el conjunto de aristas y D y T los conjuntos de vértices pertenecientes a documentos y términos respectivamente. Un eje existe si y solo si el termino tiene una ocurrencia en el documento y su peso es igual a la frecuencia del término. Con la información de este grafo construiremos la matriz de adyacencia B, la cual representará la relación documentos – términos. Figura 3: Grafo Bipartito Documento - Término 11 En esta matriz cada elemento representará el peso de la arista que se corresponde a la ocurrencia de los términos, y si no existe valdrá 0. 2.2.3 Coclustering basado en Categoría – Documento Para el coclustering de categoría-documento introducimos un nuevo componente, las categorías. A cada documento se le asignaran un grupo de categorías pertenecientes al conjunto , donde m es el número de total de categorías. Podemos representar la relación entre categorías y documentos nuevamente con un grafo bipartito no direccionado (ver figura 4). En este caso el conjunto de aristas E del grafo será Con la información de este grafo construiremos la matriz de adyacencia A, la cual representará la relación categorías – documentos. En esta matriz, las filas corresponden a categorías y las columnas a documentos. Cada elemento indica la correlación entre el documento y la categoría . Si el documento pertenece a k categorías , los pesos serán , y los otros elementos de la columna th de la matriz serán 0. Figura 4: Grafo Bipartito Categoría - Documento 12 2.2.4 Problemas SVD y GSVD La idea principal del algoritmo es encontrar una partición de los vértices de los grafos bipartitos (ver figura 3 y figura 4), tal que el corte (línea de puntos roja), suponiendo que el conjunto total de vértices V que componen el grafo, se particiona en dos subconjuntos y (en nuestro caso sería, si nos centramos en el grafo documento-término y = T, siendo D y T conjuntos de vértices pertenecientes a los documentos y términos respectivamente), pueda ser minimizado 6 . En diferentes publicaciones 7 8 9 , se ha probado que valor propio asociado con el segundo valor propio menor del problema de valores propios generalizados produce un embedding óptimo de la partición de los vértices que minimiza el corte. Este tipo de problema, después de una serie de deducciones que no competen al propósito de este proyecto, se puede transformar en un problema de descomposición en valores singulares. Aplicando SVD se quiere conseguir iterativamente refinar la partición de cada grafo con la información contenida en el otro, de esta manera, el estado estacionario tendrá la misma partición de documentos en ambos grafos y el clustering resultante de categorías será más razonable y eficaz. Al aplicar SVD sobre el grafo bipartito de documentostérminos (ver figura 3) y sobre el gde de categorías – documentos (ver figura 4) se espera que el particionamiento de documentos en ambos sea el mismo, en cambio esto no ocurre así, por lo que nuestro problema no sería consistente; este problema de inconsistencia se debe sobre todo a que las propiedades para crear las matrices base (ver apartado Pasos del Algoritmo) que sirven de entrada al problema SVD son diferentes. Para solucionar este problema, se propone no usar un embedding óptimo en cada grafo, para de esta manera, intentar conseguir que ambos sean consistentes. Aunque la partición de cada grafo no es la óptima, cuando se consideran los dos grafos como un todo, el resultado de particionamiento es más eficaz. Esto se consigue aplicando GSVD en lugar de SVD 6 En la teoría de grafos, un corte mínimo de un gráfico es un corte cuyo corte conjunto tiene el menor número de elementos o la suma más pequeña de pesos posibles. 7 I.S. Dhillon, “Coclustering Documents and Words Using Bipartite Spectral Graph Partitioning,” Proc. SIGKDD ’01, 2001. 8 G.H. Golub and C.F.V. Loan, Matrix Computations, third ed. Johns Hopkins Univ. Press, 1996. 9 J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, pp. 888-905, 2000. 13 Con esta función se consigue, dándole como entrada las matrices A y B normalizadas (matrices ver apartado Pasos del Algoritmo) que la matriz X resultante represente el particionamiento de documentos que reúne las restricciones de ambos grafos, y que las matrices U y V integren el particionamiento de categorías y términos respectivamente. De esta manera, conseguimos que el resultado garantice consistencia. En el anexo C se tratan estos dos problemas en mayor profundidad. 2.2.5 Pasos del algoritmo El algoritmo parte de la creación de las dos matrices que representan el coclustering de documentos –términos y coclustering de categorías –documentos. Estas matrices se normalizan y se les aplica GSVD. Dado que las condiciones de GSVD son menos restrictivas que las de SVD, y que la información que devuelve GSVD no es explícita, hay que encontrar la manera de poder acceder a esa información, eso se consigue aplicando una transformación lineal. Después de esto aplicamos SVD, para poder descomponer la matriz resultante en dos matrices, una que representa el embedding de términos y la otra el categorías, y a continuación las refinamos nuevamente con una nueva transformación lineal. Una vez que tenemos estas dos últimas matrices, se crean los vectores normalizados integrados, y se aplica clustering para obtener el k-particionamiento deseado. El algoritmo CBSGC arriba descrito, se traduce en los siguientes pasos: 1. Creación de las matrices A y B. Matriz A: Cada elemento indica la correlación entre el documento y la categoría . Si el documento pertenece a k categorías, los valores serán , y los otros elementos de la columna th de la matriz serán 0. Matriz B: Cada elemento representará el peso de la arista que se corresponde a la ocurrencia de los términos, y si no existe valdrá 0. 2. Creación de las matrices normalizadas de A y B: y . Para ello, antes es necesario crear las matrices Matriz : Matriz diagonal donde Matriz : Matriz diagonal donde Matriz : Matriz diagonal donde 14 Matriz : Matriz diagonal donde Matriz : Matriz : 3. Aplicar GSVD a y , para obtener las matrices U, X, V, C y S 4. Para poder utilizar de una forma útil la información de las matrices que devuelve GSVD hay que realizar una transformación lineal adecuada. Para ello creamos la matriz H Matriz 5. Una vez creada la matriz H, aplicamos SVD sobre ella para obtener las matrices y 6. Con estas dos nuevas matrices y realizamos una transformación lineal para refinar U y V , creando y Matriz = Matriz 7. Para realizar el k-particionamiento, seleccionaremos vectores columna de las matrices y , y para formar los vectores normalizados integrados. 8. En el último paso, realizaremos el clustering de y de para conseguir el kparticionamiento de categorías y términos, aunque para el propósito de nuestro algoritmo, el único que utilizaremos será el de categorías. Una vez creado el algoritmo, para construir la taxonomía jerárquica, hay que repetir todo el procedimiento, esta vez seleccionando los nuevos clusters como las clases de nivel superior , en lugar de todas las categorías, hasta que el valor de k sea igual a uno, es decir, que sea una hoja. 15 2.2 Corpus de Datos El corpus de datos que vamos a utilizar está formado por un subconjunto de documentación matemática perteneciente a opiniones y resúmenes de artículos, provenientes de las bases de datos del ZentralBlatt Math del Fiz Karhsruhe y del Get-Info Portal del TIB de Hannover. Para trabajar con este tipo de documentos, tenemos acceso a una serie de ficheros, los cuales están formados por reseñas de documentos matemáticos. Cada uno de estos documentos está catalogado dentro de una serie de categorías pertenecientes a la codificación MSC, y las reseñas de cada uno de ellos, formarán los términos de cada documento. Tenemos acceso a tres tipos diferentes de ficheros ( para información más detallada, consultar Anexo D): el primero con las reseñas en formato texto, el segundo con los términos de las reseñas codificados numéricamente y con su número de ocurrencias y la tercera igual que la anterior, pero con las ocurrencias por término normalizadas. Va a ser este tercer fichero el que vamos a usar para desarrollar el algoritmo, ya que la información que aporta, es la que mejor se adapta a este, y los resultados que se obtendrán, al estar normalizados los términos, serán más fiables. En este fichero, cada línea del mismo es una estructura JSON que representa un documento. Esta estructura consta de dos partes, en la primera encontramos la metadata, compuesta por un identificador de documento y el identificador de las categorías a las que pertenece en formato MSC, y en la segunda, el contenido del documento, representado por identificadores de términos y sus ocurrencias. En la figura 5 podemos ver un ejemplo de un documento que podemos encontrar en el fichero. Como podemos ver está compuesto por un identificador de documento, un conjunto de categorías en codificación MSC y una lista de términos con sus ocurrencias normalizadas. Figura 5: Ejemplo de documento matemático 16 17 3. DISEÑO En este tercer capítulo se explica el diseño que se ha establecido, partiendo del análisis que se ha realizado en el punto anterior sobre el paper matemático utilizado y sobre los ficheros que contienen el corpus de datos, para poder implementar el algoritmo CBSGC. Este algoritmo sirve para realizar la categorización de documentos, y para evaluar y analizar según diferentes si se pueden obtener mejores resultados si introducimos superclases en la taxonomía como un primer nivel de clasificación, para profundizar después en la jerarquía. Este capítulo consta de cuatro secciones: en la primera se abordará el diseño del corpus de datos, en la segunda las variables y vectores necesarios para crear las matrices del tercer apartado, y finalmente, el k-particionamiento. 3.1 Corpus de Datos Cada línea de los ficheros de datos que forman el corpus de datos está en formato JSON y presenta la siguiente estructura: [["1039.35023", ["35B45","35B65","35J25"]], {"8":0.15249857033260467,…}] Para poder trabajar con este contenido se ha diseñado una estructura que engloba la información. Cada documento estará formado por su identificador, las categorías a las que pertenece y una lista de términos. Con esta información podremos acceder a toda la información que aporta el fichero, para poder luego acceder a información concreta que servirá para crear las matrices A y B. Figura 6: Estructura de los datos del fichero 24 Para crear la taxonomía jerárquica, hay que repetir el algoritmo recursivamente, hasta que cada subconjuntos este formado por una sola categoría. En la siguiente figura se muestra el diagrama de flujo de la construcción de la taxonomía, nuevamente en el apartado Implementaciones se abordara este tema. Figura 7: Diagrama de flujo de la construcción de la jerarquía 25 4. IMPLEMENTACION Este cuarto capítulo aborda la etapa de implementación del proyecto; ha sido la etapa más complicada y duradera, nos hemos enfrentado a problemas de falta de memoria por parte de nuestro ordenador y a un cambio en el lenguaje de programación, ambos problemas, además de retrasar el proyecto considerablemente, han ocasionado que se haya tenido que dar un nuevo enfoque a la etapa de diseño, y que uno de los objetivos del proyecto, la creación de superclases sobre la taxonomía definida, no se haya podido llevar a cabo. Este capítulo consta de cuatros secciones: en la primera se tratará el lenguaje de programación, en la segunda la lectura del fichero del corpus de datos, en la tercera la implementación del algoritmo, lo cual incluye vectores, matrices y la parte de clustering, junto a la creación de la curva Je-k y finalmente, la creación de la taxonomía. 4.1 Lenguaje de Programación En un primer momento, este proyecto final de carrera iba a ser implementado en su totalidad en Python, porque es el lenguaje utilizado para implementar los proyectos del proyecto y además, porque tiene características que lo hacen adecuado para este tipo de problema, como lo es el trabajo con matrices y las librerías que posee para clasificación y minería de datos, como Orange y NumPy, o la existencia de la distribución Enthought. El problema con Python es que no tiene implementada la función GSVD, la cual es indispensable para poder realizar el algoritmo. Para solucionar este contratiempo, se intentaron diferentes alternativas, con la finalidad de conseguir usar Python para desarrollar el proyecto: usar “mlabwrap”, que es un bridge de Python a Matlab, que permite que Python vea a Matlab como una librería, ya que Matlab sí que tiene la función GSVD; esta solución no se pudo llevar a cabo ya que el wrapper está obsoleto, y no se consiguió que funcionara con las nuevas versiones de Python; y la segunda solución que se propuso fue acceder a librerías LAPACK, para que Python pudiera utilizar la función GSVD de allí, pero estaba también obsoleta. Debido a estos inconvenientes, se decidió que el proyecto fuera realizado en su totalidad en Matlab, ya que posee en sus librerías las funciones SVD y GSVD, y además tiene funciones de clasificación y minería de datos, y está preparado para trabajar con matrices. 26 4.2 Lectura del fichero Para leer el fichero, se ha utilizado la función parse_json() . Con esta función función se va a leer cada línea del fichero y se transformará el contenido de las estructuras JSON de nuestro fichero normalizado, a estructuras para poder trabajar en MATLAB. nfile = 'exp-train_proj-abs_vec-conf9-min-3_norm'; fid = fopen(nfile,'r'); InputText=textscan(fid,'%s',1,'delimiter','\n',); mat = parse_json(InputText{1}{1}); En mat tendremos la estructura JSON guardada en dos celdas, una para el identificador y otra para las categorías, y una estructura, que contendrá los términos y sus ocurrencias normalizadas. Esta estructura es la base para la construcción de los vectores y matrices necesarios para la implementación del algoritmo y la construcción de la taxonomía jerárquica. mat = {1x2 cell} [1x1 struct] Para accede al identificador del documento mat{1}{1} = 1039.35023 Para acceder a sus categorías mat{1}{2} = '35B45' '35B65' '35J25' Para acceder a sus términos mat{2} = alpha_8: 0.1525 alpha_1765: 0.1525 alpha_1850: 0.1525 alpha_3108: 0.1525 … Se puede observar que los identificadores de los términos, a diferencia de cómo aparecen en el corpus de datos (identificador numérico) aquí aparecen representados por el string “alpha” seguido de un valor numérico. Esto es así ya que en Matlab no se pueden declarar identificadores numéricos, por lo que se ha optado por añadir un string constante a todos los términos para su declaración. Para acceder al valor real se ha implementado la función alpha2num.m, la cual dado un string “alpha_x” devuelve el integer “x” 27 4.3 Algoritmo En este apartado se va a abordar la implementación del algoritmo. Se ha divido en tres apartados: implementaciones de los vectores, de las matrices y por último, el k-particionamiento de categorías. 4.3.1 Vectores En este apartado se va a describir cómo se han implementado las funciones para la creación de los vectores. La tabla 7 muestra todas las funciones relacionadas con vectores que permiten el acceso a la información del fichero, junto a su descripción, los parámetros que tienen de entrada y los resultados que generan. En la tabla existen dos tipos de funciones: las que sirven para obtener datos intermedios, las cinco primeras funciones que aparecen en la tabla y las que crean los vectores base para poder crear las matrices A y B, todas las que empieza su identificador con v. Como se puede observar hay funciones muy similares, se diferencian solamente en alguno de sus parámetros; esta solución de diseño se ha adoptado debido a la falta de memoria de nuestro ordenador y debido a las limitaciones que presenta la función GSVD, puesto que no acepta como entrada matrices dispersas, convirtiéndose así en nuestro cuello de botella. Este problema de memoria hace que no hayamos podido trabajar con el corpus de datos completo, restringe tanto el tamaño de las matrices con las que se puede trabajar, que los resultados que podemos obtener con el corpus de datos que acepta hace que los resultados no sean concluyentes, y que se hayan tenido que buscar otras alternativas para la categorización de los documentos. Dada esta limitación, en lugar de trabajar con el fichero entero, se han propuesto tres soluciones diferentes para poder sacar resultados: trabajar con todas las categorías pero seleccionando solo su primer nivel, seleccionar categorías pertenecientes al mismo primer nivel, es decir, un subconjunto de categorías que empiecen mismo código y por último, con categorías de un subconjunto concreto. Con estas soluciones, se pretende analizar el algoritmo y la estructura de la codificación MSC, y ver si podría funcionar en futuras investigaciones para ahondar más en el tema, ya que tras la finalización de este proyecto, no se ha llegado a resultados concluyentes. Para llevar a cabo estas nuevas soluciones, se han tenido que modificar las funciones diseñadas en un primer momento, para adaptarlas a las nuevas necesidades. La función más importante que se ha añadido, es la que crea el vector vid, encargada de seleccionar un número N de documentos que pertenecen a las categorías seleccionadas, creando una indexación de categorías con documentos. Con esta función aparte de conseguir terminar la ejecución del 28 algoritmo, y por lo tanto resultados, hacemos que cada categoría que queramos categorizar, tenga el mismo número de repeticiones en el corpus, y de esta manera asegurar, que los resultados obtenidos sean los más homogéneos posibles. DESCRIPCIÓN Input Output countcatdoc1() Cuenta las categorías de un documento dada la posición del documento posdoc, ndocs ncatdoc countcatdoc2() Cuenta las categorías de un documento dado el identificador del documento iddoc, vd ncatdoc countdocs() Cuenta el número de documentos del fichero nfile ndocs poscat() Dada una categoría y el vector con todas las categorías, devuelve su posición categoría, vc poscat iddoc() Dado una posición del fichero, devuelve su identificador nfile, pos iddoc vmaxtermvtt() Devuelve el término máximo y mínimo del fichero, y cuenta el número de términos totales nfile, ndocs, vid nter, ntter vcat() Crea un vector con las categorías, cuenta las categorías diferentes y las totales. Dependiendo de los parámetros s y c, selecciona las categorías con 5 dígitos o con 2. nfile, s, ca, categoría vc,ncat ntcat vcat1doc() Crea un vector con el número de categorías por documento nfile, ndocs vcd vccategory() Crea vectores de número de categorías y categorías por documento, dependiendo de la categoría que se quiera utilizar vcc, categoría vccindex vcdindex vccategorydef() Crea vectores con el número de categorías y categorías por documento, para un subconjunto de categorías dado. vcc, vc vccindex vcdindex vctindex() Cuenta el número total de categorías pertenecientes a un subconjunto dado vid, vccindex, ndocs ncattotalindex vdocs() Crea un vector con los identificadores de todos los documentos nfile, ndocs vd vectvtt() Crea un vector con todos los términos que aparecen en el fichero nfile,vid, ndocs vtt vindexdoc() Crea un vector con los identificadores de los documentos que pertenecen a un conjunto de categorías que pertenecen al mismo primer nivel. Se seleccionan un número de documentos por categoría según el valor de maxDC. vc,vcc, maxDC, ca,vtd vid vindexdocdef() Crea un vector con los identificadores de los documentos que pertenecen a un conjunto de categorías pertenecientes a un subconjunto dado. Se seleccionan un número de documentos por categoría según el valor de maxDC. vc,vcc, maxDC, vtd vid vter1doc() Crea un vector con el numero de términos por documento nfile, ndocs vtd vterms() Crea un vector con el número de términos totales nter vt 29 Tabla 7: Funciones para implementar los vectores 4.3.2 Matrices En este apartado se va a describir cómo se han implementado las matrices necesarias parar realizar la categorización de documentos; en el apartado de Diseño se han presentado 19 matrices diferentes, en cambio en este apartado simplemente nos vamos a centrar en la creación de la matriz A y B, y en la normalización de ambas, ya que el resto, aparte de basarse en estas, su implementación simplemente se basa en aplicarles transformaciones lineales, o aplicarles la función GSVD o SVD. Para la creación de las matrices A y B se han tenido que recorren los diferentes vectores de categorías, documentos y términos, que hemos implementado, para ir completándolas, para ver su definición consultar apartado Pasos del Algoritmo. Debido a que son matrices de gran tamaño, rellenarlas enteras no es factible, por lo que se ha optado por crear matrices dispersas, para ello en lugar de rellenar todas las posiciones, hemos tenido que crear tres vectores, uno para los índices, otro para las columnas y el último para los datos; vectores I , J y D. Debido al cambio de diseño, por problemas de falta de memoria tanto en relación al número de documentos, de categorías y de términos, las matrices de tamaño máximo que permite nuestro ordenador tratar son de apenas diez mil datos por diez mil, si comparamos esto con el fichero de más de cien mil datos, o con los casi cuarenta mil términos, vemos que va a ser imposible complementar los cálculos. Esta gran limitación se ha visto reflejado a la hora de crear las matrices, ya que no podemos utilizar toda la información que hay almacenada en los vectores representando el corpus, sino que hemos tenido que ir seleccionando la información que cumple ciertas características, por ejemplo, términos con un número mayor de ocurrencias, o documentos que posean unas ciertas categorías. Para la implementación de las matrices diagonales , se ha necesitado primero tener implementadas las matrices A y B, ya que se basan en la información que contienen estas. Al igual que con las matrices A y B, se han tenido que crear matrices dispersas de estas cuatro matrices, debido a sus dimensiones. Para ahorrar memoria se han definido los tamaños de los vectores que forman las matrices dispersas, declarándolos al principio de la función, ya que Matlab al crear vectores que crecen de vocurrencesterm() Crea dos vectores, uno con las ocurrencias de cada término, y el otro con los términos cuya ocurrencia están en un intervalo dado nter, vtt, min max vocter, vtercoc 30 forma dinámica, el aprovechamiento que hace de memoria no es bueno, y ralentiza mucho el proceso. Una vez creadas estas seis matrices, el resto de las matrices , se crean a partir de estas. La definición de cada una de ellas se puede ver en el apartado Análisis del Problema, en el punto Pasos del Algoritmo, su implementación es inmediata puesto que o bien la transformación lineal consiste en multiplicar matrices, o bien aplicar a una o varias matrices una función predefinida de Matlab (GSVD o SVD) Uno de los mayores contratiempos de este proyecto ha sido el tiempo invertido en la creación de las matrices, debido a las dimensiones de estas y al depender cada una de tantas variables hace que no se pueda paralelizar su creación , hacen que los tiempos medios para la creación rondara para cada prueba de tres a cuatro horas. Esto sumado a la limitación de la memoria, ha hecho que no se puedan realizar trabajos en paralelo, incrementando todavía más el periodo de pruebas, además ha habido muchas veces que tras haber creado las matrices iniciales, al aplicar GSVD, ya que este necesita como entradas las matrices en formato completo, se ha producido error de memoria, por lo que se ha tenido que volver a aplicar el algoritmo acotando más la información. 4.3.3 K-particionamiento En este apartado se va a describir cómo se ha implementado el k-particionamiento de categorías, y cómo se han obtenido e interpretado los resultados. Este proceso está formado por tres partes: creación y dibujo de la curva Je-k, elección de los posibles puntos de inflexión y testeo del clustering con diferentes valores. Para la implementación de la curva Je-k , tenemos que aplicar kmeans al vector integrado normalizado resultante de aplicar CBSGC. Para esta función hemos elegidos los parámetros siguientes: para el cálculo de la distancia, la distancia Euclídea de los puntos; acción por defecto en el caso de que no se pueda realizar clustering con éxito, singleton, que crea un nuevo cluster que consiste en el punto más lejando de su centroide; y el parámetro replicates, que indica el número de veces que queremos que se repita el clustering, igual a 200. En el anexo E, están las pruebas que se han realizado para seleccionar estos parámetros como los mejores para nuestro problema [idxa,Ca] = kmeans(wa,i,'Distance','sqEuclidean','emptyaction', 'singleton','Replicates',200); Una vez que se obtiene el vector vJe, que tiene para cada posible valor de k, el valor de Je, se dibuja la gráfica y se aproxima mediante el comando de Matlab cftool 31 Figura 8: Ejemplo de Curva Je-k Figura 9: Aproximación de la curva Je-k Como se puede observar la elección del punto de inflexión no es inmediato, por ello se han implementado las funciones findpeakgraph.m y testingk.m. La primera selecciona los picos de la gráfica devolviendo a qué categoría se refieren y cuál es su valor Je, y la segunda para cada valor seleccionado aplica clustering, devolviendo un vector con el clustering resultante de cada posible valor de k y las categorías que estarían en cada cluster. 32 4.4 Taxonomía Jerárquica En este último apartado se va a tratar la implementación de la taxonomía jerárquica. Una vez que se ha construido el algoritmo, y que se ha seleccionado el valor óptimo de k para realizar el clustering, hay que volver a aplicar el algoritmo hasta crear el árbol completo. Para ello se han implementado dos funciones nuevas newAAs.m y newvc.m. La primera crea tantas nuevas matrices A y PA como clusters tenemos en el paso anterior, y las normaliza para conseguir matrices , y la segunda crea vectores con las nuevas categorías que tendrá cada nueva matriz A. Para volcar los resultados de la taxonomía se ha creado un procedimiento que rellena un fichero con los resultados que se van obteniendo %--------------------------------------------------------------------- function [ taxonomy ] = createtaxonomy( taxonomy, nivel,k ,C,leaf,vc) %TAXONOMIA it creates the taxonomy % and fill a text file with the information %----------------------------------------------------------------------- A continuación se muestra un ejemplo de fichero resultado: Figura 10: Ejemplo de fichero resultado 4.4.1 Paralelizar Taxonomía Hemos optado por la opción de paralelizar la creación de la taxonomía, ya que al ser una estructura jerárquica en la que cada nuevo subárbol no entra en conflicto con la creación de los otros, es la opción más rápida de la que disponemos en contraposición con la opción de crearla de manera secuencial. Matlab nos ofrece diferentes formas de paralelizar código: el comando parfor, que ejecuta un loop de forma paralela, la herramiento Matlabpool que habilita clusters para que sean usados en paralelo, y el modo Interactive Parallel mode (pmode) que permite trabajar de forma interactiva, con un trabajo desarrollado en paralelo, simultáneamente en varios laboratorios. 33 Para la creación de nuestra taxonomía vamos a optar por el uso de la herramienta Matlabpool. Esta función se usa para reservar un número de “workers” de Matlab, bien para la ejecución de un bucle parfor o para paralelizar código (SPMD = simple program multiple data). Si matlabpool no se está ejecutando, el bucle parfor o spmd se ejecutarán en serie en el cliente, ya que matlabpool es el que inicia la sesión en paralelo y si no se arranca no se ejecutará como tal. En nuestro código vamos a hacer uso de ambas órdenes: PARFOR que ejecuta un bucle FOR de forma paralela y SPMD que ejecuta regiones de código de forma paralela. Si se pudieran paralelizar todos los bucles del código, es decir cambiar los bucles FOR por bucles PARFOR, éste sería mucho más eficiente y se reduciría el tiempo de computo de forma considerable, pero debido a las dependencias existentes entre las variables, hace que esto no sea posible, y por consiguiente, que la paralelización no se pueda realizar en la gran mayoría de ellos. Este cambio sería positivo, sobre todo, en la creación de los vectores y de las matrices, ya que es ahí donde se pierde más tiempo de cálculo, debido sobre todo al tener que recorrer el fichero del corpus para la creación de los vectores y de recorrer los vectores para la creación de las matrices. Para la creación de la taxonomía vamos a hacer uso de la paralelización mediante la orden SPMD. Cada vez que ejecutemos el algoritmo CBSGC en un subconjunto de los datos, será una región SPMD la cual se ejecutará de forma simultánea, es decir, iremos creando nuestra taxonomía jerárquica ejecutando en la medida de lo posible, cada nuevo subconjunto de hojas de forma paralela. Esta limitación viene por el procesador del ordenador que vamos a usar para la creación de la taxonomía. El ordenador que se ha usado es un Packard Bell Easynote TJ66 un procesador Intel Core 2 Duo P8700 ( 2,53 Ghz, FSB 1066 Mhz, 3 Mb. de cache ) con una memoria de 4 Gb. DDR2 a 800 Mhz. Disponemos de 2 núcleos físicos, y 4 núcleos lógicos. Por lo que se podrán realizar cuatro cálculos en paralelos, sin que perdamos eficiencia. Si quisiéramos realizar más operaciones en paralelo, veríamos afectada la velocidad, en lugar de agilizar el proceso, este se vea ralentizado, ya que la capacidad se vería atenuada por un factor de tres. 40 5.3 Experimento 3 En este tercer experimento, se va a trabajar con categorías que empiezan por el mismo código de primer nivel. Al igual que en el anterior experimento, se van a indexar alrededor de 200 documentos por categoría, dependiendo del número de categorías que tenga cada nivel, ya que si no se producen error por falta de memoria. Se han hecho pruebas para cada una de las 63 categorías diferentes que posee nuestro corpus, aunque solo vamos a comentar un par que nos han parecido más relevantes, la categoría 39 y la 85. En la figura 19 podemos ver la tabla con el clustering hecho para las categorías que empiezan por 39, y dos gráficas, Je-k curve y la aproximación de la misma. Vemos que hay tres grupos, por lo que se esperaría que el valor de k=3, en cambioha seleccionado k=4 como el valor óptimo para realizar el clustering y se han dividido las categorías según esta división. Podemos ver que divide las categorías bien para el tercer nivel en el caso de A y B, con algún pequeño error en el caso de B, pero que nuevamente la categoría -06 la clusteriza aparte junto con la terminada en xx (en MSC las categorías que terminan en xx significan que no están en ninguna de las categorías definidas, pero que pertenece al grupo), y que la categoría -02 es un grupo aparte. Figura 19: Clustering y grafica Je-k de la categoría 39 En la figura 20 está la tabla con el clustering para las categorías que empiezan por 85, junto a las gráficas Je-k y su aproximación. En esta gráfica se espera que el valor de k=2, y así es, pero al realizar la división de categorías, vemos que agrupa todas juntas excepto a la -06 y a la terminada 41 el xx. Si probamos con los siguientes valores de k, cada uno de los valores – {00,..,06} lo sitúa en un cluster aparte. Figura 20: Clustering y grafica Je-k de la categoría 85 5.4 Experimento 4 En este cuarto y último experimento, se va a trabajar con grupos de categorías definidos. Vamos a probar si el algoritmo es capaz de distinguir diferentes subconjuntos de categorías, dándole a cada grupo de categorías el mismo número de documentos. Hemos realizado 40 pruebas, cogiendo diferentes subconjuntos de categorías, que pertenezcan a la misma área, a áreas diferentes, que traten temas similares o no, etc. A continuación vamos a comentar las que nos han parecido más relevantes. En la figura 21, podemos observar como para dos subconjuntos el algoritmo es capaz de distinguir entre la categoría 20 y la 39; en cambio en la figura 22 que también tiene dos subconjuntos, hay una categoría que termina -06 y otra en xx, tal y como ha pasado en los experimentos anteriores, nuevamente han sido agrupadas en clusters aparte. 42 Figura 21: Prueba PA15 -Clustering y grafica Je-k para dos subconjuntos Figura 22: Prueba PC12 -Clustering y grafica Je-k para dos subconjuntos 43 En la figura 23, se ha hecho el experimento con tres subconjuntos. Vemos que el algoritmo es capaz de distinguir entre la categoría 91 y las otras dos, en cambio entre la categoría 93 y 94, tiene problemas. Cuantas más categorías añadimos a los subconjuntos, más problemas empieza a tener. Figura 23: Prueba PC23 -Clustering y grafica Je-k para tres subconjuntos En la figura 24, se ha hecho el experimento con cuatro subconjuntos, esta vez con categorías que terminan en -06. Seleccionamos k=3, y vemos como las categorías que terminan en -06 se agrupan juntas, la 26 con la 30, y la 53 con la 56. Figura 24: Clustering con k=5 para prueba PC32 Figura 23: Prueba PC32 -Clustering y grafica Je-k para cuatro subconjuntos Figura 24: Prueba PC32 -Clustering y grafica Je-k para cuatro subconjuntos 44 Si en lugar de seleccionar k=3, seleccionamos k=4, vemos que el nuevo cluster es para la categoría que terminar en XX, en lugar de separar las categorías 26 de la 60, o la 53 de la 57. Figura 25: Prueba PC32 con k=5 Por último, en la figura 26, vemos uno de los experimentos con cinco subconjuntos. Cuantas más categorías añadimos a los subconjuntos, más problemas empieza a tener, las categorías 01 y 12 es capaz de diferenciarlas, pero con el resto tiene problemas. Cuantas más categorías tenemos, menos documentos podemos indexar por cada una, en este caso solo 100, ya que si no, no se podía completar los cálculos. Figura 26: Prueba PC41 -Clustering y grafica Je-k para cinco subconjuntos 45 5.5 Análisis de los resultados Aunque no se han podido completar los resultados con todo el corpus de datos, lo cual era indispensable para poder crear un nivel de superclases sobre la taxonomía predefinida, se han podido obtener resultados esperanzadores aplicando este algoritmo. Lo más importante a destacar es que todas las categorías que pertenecen a los grupos categoría – {00, 01, 02, 03, 04, 06}, pesa más su pertenencia a una colección o a un histórico, que el hecho que sean de álgebra o de funciones reales, por lo que cada una de ellas podría ser una nueva clase. Las categorías que terminan en codificación -99 o –XX, son categorías que se engloban dentro de una categoría, pero que no tienen lugar dentro de las subcategorías existentes; el algoritmo tiende siempre a separarlas en grupos aparte. Sería conveniente estudiarlas más, para crear un nuevo grupo. Las categorías que pertenecen a temas generales, tienden a clasificarse juntas, aunque dentro de lo general tengan en particular algo relacionado con las matemáticas. Se han hecho muchas más pruebas, y en la gran mayoría los resultados han sido siempre similares. Los resultados dependen del número de ficheros que contengan una cierta categoría, y por tanto del número de términos con el que se puede trabajar. Hay categorías que están en muchos ficheros, en cambio otras apenas aparecen, esto condiciona la solución, ya que de algunas tenemos mucha información aportada por los términos, y en otras casi nada. Para poder obtener mejores resultados habría que evaluar este algoritmo con un ordenador mucho más potente, que pueda hacer frente a los tamaños de las matrices que se requieren e implementar una función Generalized Singular Value Decomposition que pueda trabajar con matrices dispersas, ya que sino el problema se ve muy afectado. Para concluir se puede decir, que aunque no se ha podido probar con grandes volúmenes de datos, los resultados obtenidos son bastante buenos y esperanzadores; y que habría que hacer un estudio más profundo de la codificación MSC o bien analizar mejor las reseñas que se hacen en los documentos matemáticos. 46 47 6. CONCLUSIONES En este último capítulo se resumen la consecución de objetivos y la valoración personal del trabajo llevado a cabo en este Proyecto Fin de Carrera. 6.1 Consecución de objetivos El éxito en la realización del proyecto debe analizarse desde la perspectiva de la adecuación de los resultados a los objetivos iniciales, así que vamos a recordarlos y comprobaremos si el proyecto desarrollado los cumple:  Evaluar una aproximación para la introducción de superclases la clasificación MSC  Implementar el algoritmo descrito en el paper "Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning”  Evaluar el algoritmo con datos de una biblioteca digital matemática  Examinar la estructura de la taxonomía MSC para mejorar el rendimiento global de la clasificación Aunque uno de los objetivos principales del proyecto era realización de una aproximación para la introducción de superclases sobre la taxonomía, debido a los problemas que hemos tenido con la falta de memoria, no se han podido completar los cálculos con todo el corpus de datos, por lo que no se han podido obtener las superclases esperadas, pero se han obtenido resultados esperanzadores. El algoritmo se ha implementado con éxito, y se ha evaluado según diferentes aproximaciones: subconjuntos del corpus de datos, categorías del primer nivel de MSC, subconjuntos de categorías, con el mismo primer nivel y subconjuntos de categorías bien definidos. Se ha examinado la estructura de la taxonomía MSC, y se ha observado que la clasificación no es perfecta o bien que la anotación que se hace sobre los documentos no es la adecuada y con las pruebas realizadas, se han probado que en un futuro se podría mejorar el rendimiento global de la clasificación, sobre todo analizando mejor las categorías que pertenecen al grupo – {00,01,02,03,04,06} e intentar localizar mejor aquellas que terminan en -XX Dado que no se ha podido completar completamente el objetivo de este proyecto, debido a la limitación de memoria, se propone como posible trabajo futuro implementar la función GSVD para datos dispersos, y una vez que esto se consiga, se podrá evaluar con más datos y analizar si la clasificación resultante es mejor. 48 6.2 Valoración Personal Este proyecto se ha desarrollado en una universidad extranjera, dentro del marco del programa Erasmus. Sumado al reto que supone realizar un proyecto final de carrera, hay que sumar la dificultad que ha presentado hacerlo en otro idioma, y tener que lidiar con los requisitos que se piden en otras universidades. Personalmente, me encuentro contenta con el trabajo que he realizado, aunque he tenido muchas dificultades para poder realizarlo, he sabido solventarlas, buscando soluciones, y sacando el proyecto adelante. 49 7. BIBLIOGRAFÍA [Paper implementado] Hierar-chical taxonomy preparation for text categorization using consistent bipartite spectral graph copartitioning http://research.microsoft.com/pubs/131500/TKDE-FINAL-01490532.pdf [Papers consultados] Co-clustering documents and words using Bipartite Spectral Graph Partitioning http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.2909&rep=rep1&type=pdf Exploiting confusion matrices for automatic generation of topic hierarchies and scaling up multiway classifiers http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.6404&rep=rep1&type=pdf Topic hierarchy generation via linear discriminant projection. http://www.researchgate.net/publication/221301366_Topic_hierarchy_generation_via_line ar_discriminant_projection A comparative study on feature selection in Text Categorization http://faculty.cs.byu.edu/~ringger/Winter2007-CS601R-2/papers/yang97comparative.pdf Data Clustering http://www.cs.rutgers.edu/~mlittman/courses/lightai03/jain99data.pdf [MSC web] Página web del MSC http://www.ams.org/mathscinet/msc/msc2010.html [SVD web] Páginas web sobre Singular Value Decomposition http://www.mate.unlp.edu.ar/practicas/70_18_0911201012951.pdf http://www.ehu.es/izaballa/Ana_Matr/Apuntes/lec3.pdf http://www.utdallas.edu/~herve/Abdi-SVD2007-pretty.pdf http://www.ling.ohio-state.edu/~kbaker/pubs/Singular_Value_Decomposition_Tutorial.pdf [GSVD web] Páginas web sobre Generalized Singular Value Decomposition http://www.utdallas.edu/~herve/Abdi-SVD2007-pretty.pdf http://www.mathworks.es/es/help/matlab/ref/gsvd.html http://www.netlib.org/lapack/lug/node36.html [PYTHON web] Tutoriales de Python http://docs.python.org/2/tutorial/ [MATLAB web] Página web de Matlab www.mathworks.com/ 56 57 58 59 60 61 62 63 64 65 ANEXO B. Clasificación MSC Este anexo trata sobre la clasificación MSC. Para crear la taxonomía jerárquica en base a nuestros documentos matemáticas, vamos a utilizar categorías englobadas dentro del sistema de clasificación alfanumérica MSC, en concreto de la versión MSC2010. Mathematics Subject Classification (MSC) El MSC es un sistema de clasificación jerárquico alfanumérico, producido en base a la cobertura de las dos principales bases de datos de matemáticas, Mathematical Reviews y Zentralblatt MATH. Es utilizado en muchas revistas matemáticas. La versión actual es MSC2010. El sistema consta de tres niveles de estructura, y se puede clasificar en base a dos, tres o cinco dígitos, dependiendo del número de niveles que se utilicen para clasificar El primer nivel está representado por un número de dos dígitos, el segundo por una letra, y el tercero por otro número de dos dígitos Primer nivel En el nivel superior existen 64 disciplinas matemáticas etiquetadas con un número único de 2 dígitos. En este nivel además de encontrarse las áreas básicas de la investigación matemática, están las categorías de "Historia y Biografía", "Educación Matemática", y categorías con similitudes con diferentes ciencias. Segundo nivel Los códigos del segundo nivel se representan son una sola letra del alfabeto. Representan áreas específicas relacionadas por el primer nivel de la disciplina. Los códigos de segundo nivel pueden variar de una disciplina a otra. Además en este nivel se encuentra el código especial “-“, el cual se utiliza para tipos específicos de materiales 72 73 ANEXO D. Corpus de Datos En este anexo complementa al apartado “Corpus de Datos” de la memoria. Se va a explicar cómo es el fichero que contiene el corpus de datos, qué formato tiene, qué información nos aporta y cómo lo vamos a leer para poder trabajar en MATLAB con él. Descripción del Corpus Tal y cómo se ha mencionado en la memoria, el propósito de este PFC es ayudar a la organización de documentos matemáticos; para realizar esta labor hay que trabajar con el contenido de estos, ya que analizando la información contenida en sus términos, podremos ser capaces de extraer la información necesaria para poder crear una estructura jerárquica por categorías (MSC, Mathematics Subject Classification). Para realizar esta labor, dispongo de tres ficheros con documentos, los tres describen el corpus de datos con el que voy a trabajar, aunque representan su contenido de maneras diferentes. El primero contiene las descripciones de los documentos, el segundo representa las ocurrencias por términos de cada documento y el último contiene las ocurrencias de cada documento pero en formato normalizado. Para aplicar el algoritmo con el que he trabajado, únicamente he usado el contenido del último de estos tres ficheros: “exp-train_proj-abs_vec-conf9-min-3.json”, ya que tiene la información que necesito en formato normalizado. Estructura del fichero Cada línea del fichero es una estructura JSON que representa a un documento. Esta estructura consta de dos partes, en la primera encontramos la metadata, compuesta por un identificador de documento y el identificador de las categorías a las que pertenece en formato MSC, y en la segunda, el contenido del documento, representado por identificadores de términos y sus ocurrencias. Será la forma de representar esta segunda parte de la estructura lo que va a variar de un fichero a otro. En el fichero “exp-train_proj-abs.json” aparece en formato de texto, en cambio en los otros dos aparecen los términos denotados con identificadores junto a las ocurrencias 74 de cada uno, en “exp-train_proj-abs_vec-conf9-min-3.json” el número de ocurrencias, y en “exp-train_proj-abs_vec-conf9-min-3_norm.json” el número de ocurrencias normalizadas, teniendo en cuenta toda la información del resto de documentos. A continuación se muestra para cada fichero, la estructura de los documentos. Fichero “exp-train_proj-abs.json” [ [ "1039.35023", %Identificador Documento ["35B45","35B65","35J25"] %categorías a las que pertenece ], [ "The authors consider the following elliptic problem $$ \\lambda u(x)-\\Delta u(x)-Lu(x)=f(x), \\ x\\in S_d,\\quad D_i^2u(x)=0,\\ x\\in S_d\\cap\\{x_i=0,1\\},\\ i=1,\\ldots,d $$ where $S_d$ is the $d$-dimensional hypercube $[0,1]^d,$ $\\lambda$ is a positive constant and $L$ is a second order differential operator. They prove that if the coefficients are of class $C^{k+\\delta}(S_d),$ with $k=0,1$ and $\\delta\\in(0,1),$ then the problem admits a unique solution $u$ belonging to $C^{k+2+\\delta}(S_d).$" ] %Contenido del documento en formato de texto ] Fichero “exp-train_proj-abs_vec-conf9-min-3.json” [ [ "1039.35023",%Identificador de documento ["35B45","35B65","35J25"] %categorías a las que pertenece ], { "8":1.0, %Identificador término : Ocurrencia en documento "3370":1.0,"5161":1.0,"5866":1.0,"7805":1.0,"8492":1.0,"8799" :1.0,"9225":1.0,"10970":1.0,"11188":1.0,"11566":1.0,"11583":1 .0,"12915":1.0,"12964":1.0,"13893":1.0,"15191":1.0,"17269":1. 0,"17361":3.0,"23037":1.0,"23096":1.0,"24444":1.0,"24807":2.0 ,"24959":1.0,"27119":1.0,"28302":1.0,"30075":1.0,"30077":1.0, "31345":1.0 } % Lista de términos con sus ocurrencias ] 75 Fichero “exp-train_proj-abs_vec-conf9-min-3_norm.json” [ [ "1039.35023",%Identificador de documento ["35B45","35B65","35J25"] %categorías a las que pertenece ], { "8":0.15249857033260467, % Identificador término % Ocurrencias normalizadas "1765":0.15249857033260467,"1850":0.15249857033260467,"3108": 0.15249857033260467,"3309":0.15249857033260467,"3370":0.15249 857033260467,"5161":0.15249857033260467,"5866":0.152498570332 60467,"7805":0.15249857033260467,"8492":0.15249857033260467," 8799":0.15249857033260467,"9225":0.15249857033260467,"10970": 0.15249857033260467,"11188":0.15249857033260467,"11566":0.152 49857033260467,"11583":0.15249857033260467,"12915":0.15249857 033260467,"12964":0.15249857033260467,"13893":0.1524985703326 0467,"15191":0.15249857033260467,"17269":0.15249857033260467, "17361":0.457495710997814,"23037":0.15249857033260467,"23096" :0.15249857033260467,"24444":0.15249857033260467,"24807":0.30 499714066520933,"24959":0.15249857033260467,"27119":0.1524985 7033260467,"28302":0.15249857033260467,"30075":0.152498570332 60467,"30077":0.15249857033260467,"31345":0.15249857033260467 } % Lista de términos con sus ocurrencias normalizadas ] El contenido del fichero con el que se ha trabajado sería semejante al que se muestra a continuación (contenido del fichero “prueba.json”, el cual ha servido como punto de partida para el trabajo con el corpus de datos real) [["1039.35023",["35B45","35B65","35J25"]],{"8":0.15249857033260467,"13":0 .15249857033260467}] [["1043.83040",["83F05","83C75","83C15"]],{"9":0.13801311186847084,"1":0. 06900655593423542,"3":0.13801311186847084}] [["1047.65001",["35B45","35B65","83F05","83C75"]],{"9":0.4082482904638631 ,"13":0.4082482904638631}] [["1048.5048",["35J25"]],{"2":0.19245008972987526,"5":0.19245008972987526 ,"9":0.19245008972987526,"12":0.19245008972987526}] [["1049.14014",["35B45","35B65","35J25","14K22"]],{"6":0.2236067977499789 6,"4":0.22360679774997896}] [["1049.14032",["83F05","83C75"]],{"7":0.20412414523193154,"10":0.2041241 4523193154,"11":0.20412414523193154}] [["1052.14069",["83F05","83C75","83C15"]],{"7":0.10273309938750283,"1":0. 10273309938750283,"2":0.10273309938750283}] [["1053.65002",["35B45","35B65"]],{"2":0.4082482904638631,"12":0.40824829 04638631,"13":0.4082482904638631}] [["1054.5099",["35B45","35B65","83F05"]],{"11":0.040291148201269014,"1":0 .040291148201269014,"2":0.16116459280507606}] [["1054.62005",["35B45","35B65","83F05"]],{"9":0.22086305214969307,"4":0. 3312945782245396,"3":0.11043152607484653}] 76 Este corpus de datos está compuesto por 10 documentos, 7 categorías y 13 términos Documentos = {'1039.35023' '1043.83040' '1047.65001' '1048.5048' '1049.14014' '1049.14032' '1052.14069' '1053.65002' '1054.50990' '1054.62005'} Categorías = {'35B45' '35B65' '35J25' '83F05' '83C75' '83C15’ '14K22'} Términos = {1 2 3 4 5 6 7 8 9 10 11 12 13} Para obtener la información anterior de manera automática se ha tenido que leer el fichero, creando para ello estructuras en Matlab y vectores, Todo esto está explicado en el apartado de Diseño de esta memoria. 77 ANEXO E. Clustering-Kmeans Este anexo trata sobre el clustering con kmeans. Está formado por dos apartados, en el primero encontramos la definición de kmeans y la función en MATLAB, en el segundo apartado hemos realizado pruebas para decidir qué parámetros de esta función son los mejores para aplicarlos a nuestra implementación. Definición Para la obtención de la partición de las categorías y de los términos, vamos a hacer uso de la función k-means que nos ofrece MATLAB. k -means es un método de agrupamiento, que tiene como objetivo la partición de un conjunto n en k grupos en el que cada observación pertenece al grupo más cercano a la media. Si buscamos la descripción de k-means en MATLAB, obtendremos lo siguiente: Syntax [IDX,C,sumd,D] = kmeans(X,k) Description IDX = kmeans(X,k) partitions the points in the n-by-p data matrix X into k clusters. This iterative partitioning minimizes the sum, over all clusters, of the within-cluster sums of point-to-cluster-centroid distances. Rows of X correspond to points, columns correspond to variables. kmeans returns an n-by-1 vector IDX containing the cluster indices of each point. By default, kmeans uses squared Euclidean distances. When X is a vector, kmeans treats it as an n-by-1 data matrix, regardless of its orientation. [IDX,C] = kmeans(X,k) returns the k cluster centroid locations in the k-by-p matrix C. [IDX,C,sumd] = kmeans(X,k) returns the within-cluster sums of point-to-centroid distances in the 1-by-k vector sumd. [IDX,C,sumd,D] = kmeans(X,k) returns distances from each point to every centroid in the n-by-k matrix D. 78 Parámetros Parameter Value 'distance' Distance measure, in p-dimensional space. kmeans minimizes with respect to this parameter.kmeans computes centroid clusters differently for the different supported distance measures. 'sqEuclidean' Squared Euclidean distance (default). Each centroid is the mean of the points in that cluster. 'cityblock' Sum of absolute differences, i.e., the L1 distance. Each centroid is the component-wise median of the points in that cluster. 'cosine' One minus the cosine of the included angle between points (treated as vectors). Each centroid is the mean of the points in that cluster, after normalizing those points to unit Euclidean length. 'correlation' One minus the sample correlation between points (treated as sequences of values). Each centroid is the component-wise mean of the points in that cluster, after centering and normalizing those points to zero mean and unit standard deviation. 'Hamming' Percentage of bits that differ (only suitable for binary data). Each centroid is the component-wise median of points in that cluster. 'emptyaction' Action to take if a cluster loses all its member observations. 'error' Treat an empty cluster as an error (default). 'drop' Remove any clusters that become empty. kmeans sets the corresponding return values in C and D to NaN. 'singleton' Create a new cluster consisting of the one point furthest from its centroid. 'onlinephase' Flag indicating whether kmeans should perform an online update phase in addition to a batch update phase. The online phase can be time consuming for large data sets, but guarantees a solution that is a local minimum of the distance criterion, that is, a partition of the data where moving any single point to a different cluster increases the total sum of distances. 'on' Perform online update (default). 'off' Do not perform online update. 'options' Structure specifying options for the iterative algorithm used to 79 Parameter Value minimize the fitting criteria. Create the options structure with statset. Applicable statset parameters are: Display Level of display output. Choices are ‘off'(default), ‘iter', and‘final'. MaxIter Maximum number of iterations allowed. The default is 100. UseParallel If true and if a matlabpool of the Parallel Computing Toolbox™ is open, compute in parallel. If the Parallel Computing Toolbox is not installed, or a matlabpool is not open, computation occurs in serial mode. Default is default, meaning serial computation. UseSubstreams Set to true to compute in parallel in a reproducible fashion. Default is false. To compute reproducibly, set Streams to a type allowing substreams: 'mlfg6331_64' or 'mrg32k3a'. Streams A RandStream object or cell array of such objects. If you do not specify Streams, kmeans uses the default stream or streams. If you choose to specify Streams, use a single object except in the case:  You have an open MATLAB® pool  UseParallel is true  UseSubstreams is false In that case, use a cell array the same size as the MATLAB pool. If a MATLAB pool is not open, then Streams must supply a single random number stream. 'replicates' Number of times to repeat the clustering, each with a new set of initial cluster centroid positions.kmeans returns the solution with the lowest value for sumd. You can supply 'replicates' implicitly by supplying a 3D array as the value for the 'start' parameter. 'start' Method used to choose the initial cluster centroid positions, sometimes known as seeds. 'sample' Select k observations from X at random (default). 'uniform' Select k points uniformly at random from the range of X. Not valid with Hamming distance. 'cluster' Perform a preliminary clustering phase on a random 10% subsample of X. This preliminary phase is 80 Parameter Value itself initialized using 'sample'. Matrix k-by-p matrix of centroid starting locations. In this case, you can pass in [] for k, and kmeans infers k from the first dimension of the matrix. You can also supply a 3-D array, implying a value for the'replicates' parameter from the array's third dimension. Tabla G1: Parámetros función kmeans en Matlab Para la elección de los parámetros correctos en nuestros datos, se ha probado con diferentes combinaciones hasta obtener la partición deseada. Las pruebas se han hecho sobre el corpus de datos de prueba, donde las categorías son las siguientes:{'35B45' '35B65' '35J25' '83F05' '83C75' '83C15’ '14K22'} y donde sabemos que la taxonomía resultante es: root 35 83 14 '35B45''35B65''35J25' '83F05''83C75''83C15’ '14K22' Tabla G2: Taxonomía jerárquica de ejemplo Pruebas El primer parámetro a modificar va a ser ‘distance’, ya que es el parámetro más restrictivo, lo que nos va a facilitar futuras combinaciones. Cada uno de los posibles métodos a aplicar realizan la medida de las distancias entre puntos, pero con diferentes técnicas: Distancia Euclídea, City Block, Cosenos, Correlation y Hamming. Para representar los datos se han creado dos tipos de tablas; en la primera se representan los valores que tiene cada uno de los parámetros que están siendo utilizados cuando ejecutamos la función kmeans de Matlab, y en la segunda mostramos para cada valor de K ( que será el número de clusters en el que queremos k-particionar nuestros datos) su vector IDX, el cual representa los índices de pertenencia de cada dato, es decir, el contenido de este vector nos indica a qué cluster pertenecerán los datos; el valor de 81 Je, que es el valor mínimo de la función objetivo del algoritmo y la gráfica K-Je, que nos servirá para calcular el valor óptimo de K. Distancia Euclídea Parámetros Valor Distance 'sqEuclidean' Emptyaction 'error' Onlinephase ‘on’ options ‘Display’’off’ replicates 0 start ‘sample’ K 1 2 3 4 5 6 7 IDX 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 1 3 3 3 2 1 1 4 2 2 2 3 1 4 5 3 3 3 2 3 3 2 4 1 5 6 2 1 4 5 6 3 7 Je 0.8631 0.0612 0.8545 0.0163 0.0179 0.0000 0 Gráfica k-Je City Block Parámetros Valor Distance 'cityblock' Emptyaction 'error' Onlinephase ‘on’ options ‘Display’’off’ replicates 0 start ‘sample’ 88 K 1 2 3 4 5 6 7 IDX 1 1 1 1 1 1 1 2 2 2 1 1 1 2 3 3 3 2 2 2 1 1 1 4 2 2 2 3 1 1 2 5 3 3 4 3 3 2 4 1 5 6 2 1 4 5 6 3 7 Je 0.8631 0.0612 0.3775 0.0163 0.0057 0.0000 0 Gráfica k-Je City Block Para la medida City Block vamos a realizar los mismos pasos que hemos hecho con la Distancia Euclídea, y veremos que los resultados son similares. Si el valor de replicates es cero, se obtienen muchas soluciones diferentes, en cambio si fijamos su valor, obtenemos la solución correcta. Parámetros Valor Distance ‘cityblock’ Emptyaction ‘drop’ ‘singleton’ Onlinephase ‘on’ options ‘Display’’off’ replicates 0 start ‘sample’ Resultado 1 K 1 2 3 4 5 6 7 IDX 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 1 3 3 3 2 1 1 1 4 3 2 1 1 1 2 5 3 3 4 5 5 4 2 1 3 6 2 1 4 5 6 3 7 Je 1.1106 0.0653 1.2753 1.7585 0.0057 0 0 89 Gráfica k-Je Resultado 2 K 1 2 3 4 5 6 7 IDX 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 2 1 3 3 2 4 4 2 3 3 3 1 1 1 2 5 3 3 4 5 5 4 2 1 3 6 2 1 4 5 6 3 7 Je 1.1106 0.0653 1.7627 0.0180 0.0057 0 0 Gráfica k-Je Resultado 3 K 1 2 3 4 5 6 7 IDX 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 2 3 3 3 1 1 1 4 2 2 2 3 1 4 5 3 3 3 2 3 3 2 4 1 5 6 2 1 4 5 6 3 7 Je 1.1106 0.0653 0.5597 0.0180 0.00057 0.0000 0 90 Gráfica k-Je Resultado 4 K 1 2 3 4 5 6 7 IDX 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 2 3 1 1 2 4 4 4 3 1 2 4 4 4 4 3 1 2 5 3 3 2 4 1 5 6 2 1 4 5 6 3 7 Je 1.1106 0.0653 1.7627 17585 0.8777 0.0000 0 Gráfica k-Je Resultado 5 K 1 2 3 4 5 6 7 IDX 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 2 3 1 1 2 4 4 4 3 2 2 4 4 4 2 3 1 1 5 3 3 2 4 1 5 6 2 1 4 5 6 3 7 Je 1.1106 0.0653 1.7627 0.5459 0.0057 0.0000 0 91 Gráfica k-Je Fijando el valor de replicates a un valor superior a cinco, el resultado que obtenemos es constante en cada ejecución. En nuestro caso coincide con el resultado 3, cuando el valor de replicates era cero. Parámetros Valor Distance ‘cityblock’ Emptyaction ‘drop’ ‘singleton’ Onlinephase ‘on’ options ‘Display’’off’ replicates >5 start ‘sample’ K 1 2 3 4 5 6 7 IDX 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 2 3 3 3 1 1 1 4 2 2 2 3 1 4 5 3 3 3 2 3 3 2 4 1 5 6 2 1 4 5 6 3 7 Je 1.1106 0.0653 0.5597 0.0180 0.00057 0.0000 0 Gráfica k-Je Dependiendo del número de datos por el que este compuesto el corpus con el que vamos a trabajar, habrá que incrementar el número de replicados, ya que habrá que repetir varias veces los cálculos hasta obtener una buena aproximación al valor 92 óptimo. Aumentar este valor incrementará el tiempo de cómputo, pero es una penalización que hay que asumir, para conseguir un buen resultado. Analizando los resultados que hemos obtenido para ambos métodos, podemos ver que cuando aumentamos el número de replicates para ambos, los dos convergen a una solución, pero con la Distancia Euclídea, el resultado correcto se consigue con menos iteraciones. También se puede observar, que en ambos métodos cuando el valor de replicates es cero, se obtienen diferentes soluciones, pero hay una diferencia bastante significativa, aplicando Distancia Euclídea, el punto de inflexión para todas las posibles alternativas siempre ha sido con tres clusters, en cambio con City Block la elección varía entre tres y cuatro clusters. Por estas dos razones principalmente, se ha decidido que para nuestro corpus de datos, se va a aplicar kmeans con Distancia Euclídea, y con un valor de replicates lo suficientemente alto como para que el resultado sea correcto, pero intentando a la vez que la penalización por tiempo de cálculo reste efectividad al algoritmo; además como emptyaction se usará singleton ,en lugar de error o drop, esto es, en el caso que haya clusters vacíos, en vez de tratarlos como error o eliminarlos, se creará un nuevo cluster con los puntos más alejados; esto se comprobará con los datos del corpus, ya que con los datos de prueba no se aprecian las diferencias de tratar con uno u otro. Se ha decidido no usar drop, ya que existe un bug en la función kmeans de Matlab, que provoca un error de ejecución. Undefined function or variable "idxBest". Error in kmeans (line 331) idx = idxBest; 93 ANEXO F. Algoritmo CBSGC %--------------------------------------------------------------------- %Creación de los vectores y las variables %--------------------------------------------------------------------- nfile = 'taxo.json'; s = 2; ca=0; maxDC = 100; %--------------------------------------------------------------------- [ndocs] = countdocs(nfile) [vd] = vdocs (nfile,ndocs) [vtd] = vter1doc(nfile,ndocs) [vcd] = vcat1doc(nfile,ndocs) [vc,vcc,ncat,ntcat] = vcat(nfile,ndocs,2,0,'') [vid] = vindexdoc (vc,vcc,maxDC,0) [vttd, nter,ntter,~] = maxtermvtt(nfile,ndocs,vid) [vtt] = vectvtt(nfile,vid,ndocs) [vt] = vterms (nter) [vocter,vtercoc] = ocurrencesterm(nter,vtt,0,2000) [vccindex,vcdindex] = vcindex(vcc,s,ca) [ncattotalindex] = vctindex(vid,vccindex,ndocs) [vc,ncat,ntcat] = vcat(nfile,0,1,''); 'creado vector categorias' [vcc,vcd] = vccategory(vcc,''); 'creado vcc y vcd' [vid] = vindexdoc (vc,vcc,100,1,vtd); 'indexandos documentos' [~,c] = size(vid); ndocs = c; [ncattotal] = vctindex(vid,vcc,ndocs); 'calculado numero total categorias' [vtt] = vectvtt(nfile,vid,ndocs); 'creado vtt' [nter,ntter,~] = maxtermvtt(nfile,ndocs,vid); 'calculado numero terminos' [vocter,vtercoc] = ocurrencesterm(nter,vtt,0,500); 'calculados vectores de ocurrencias' %--------------------------------------------------------------------- %Creación de las matrices %--------------------------------------------------------------------- [SparseA,IA,JA,DA] = MatrizA(vid,vc,vcd,vcc,ncat,ncattotal,ndocs); 'matriz A' [~,IPA,JPA,DPA] = MatrizPA(IA,DA,ncat); 'matriz PA' [SparseRA,~,~,~] = MatrizRA(JA,DA,ndocs); 'matriz RA' [AA] = MatrizAA(SparseRA,SparseA, IPA,JPA,DPA); 'matriz AA' [SparseB,IB, JB, DB] = MatrizB(vid,vtd,vttd, ndocs,vtercoc,vocter); 'matriz B' [~,IPB,JPB,DPB] = MatrizPB(IB,DB,ndocs); 'matriz PB' [~,IRB,JRB,DRB] = MatrizRB(JB,DB,vtercoc); 'matriz RB' [BB] = MatrizBB(SparseB, IPB,JPB,DPB,IRB,JRB,DRB); 'matriz BB' 94 [U,V,X,C,S] = fGSVD( AA,BB); 'GSVD' [H] = MatrizH( C,X,S ); 'H' [UH, ~, VH] = fSVD(H); 'SVD' [US] = fLinearTrans( U,UH); 'transformacion lineal' %--------------------------------------------------------------------- %K-particionamiento %--------------------------------------------------------------------- vJe = JeCurve(ncat,IPA,JPA,DPA,US,0); plotJeCurve( vJe,ncat) [vpeaks,vkopt] = findpeakgraph(vJe,18); [ vtotal ] = testingK(vc,vkopt,US,IPA,JPA,DPA); save matvect BB DPA JPA IPA SparseA US ncat ncattotal ndocs ntcat nter ntter vJe vtotal vc vid vocter vtercoc vtt vcc vcd %--------------------------------------------------------------------- %Repetimos, hasta llegar a la raiz la funcion CBSGC %--------------------------------------------------------------------- [vMatrixnAA,vMatrixnPA,t] = newAAs(kopt,SparseA,US,IPA,JPA,DPA,ndocsindex [vMatrixvc,vMatrizncat] = newvc( vc, idxa,kopt) %La matriz B permanece constante, el resto de las matrices %hay que recalcularlas [U2,V2,X2,C2,S2] = fGSVD( vMatrixnAA(1),BB); [H2] = MatrizH( C2,X2,S2 ) [UH2, SH2, VH2] = fSVD(H2); [US2,VS2] = fLinearTrans( U2,UH2,V2,VH2); vJe = JeCurve(kopt,vMatrixnPA(1),US2); plotJeCurve( vJe,kopt ); [vpeaks,vkopt] = findpeakgraph(vJe,18); [ vtotal ] = testingK(vMatrixvc(1),vkopt,US2,IPA2,JPA2,DPA2); %--------------------------------------------------------------------- 95 ANEXO G. Gestión del Proyecto Figura G1: Diagrama de Gantt para la gestión del proyecto En la figura anterior se muestra la evolución temporal del proyecto mediante un diagrama de Gantt. Podemos ver que la parte de implementación es la que mayor tiempo nos ha llevado, seguido de cerca de las pruebas. La memoria ocupa la mayoría del tiempo debido a que se ha ido realizando a lo largo del desarrollo del proyecto. Podemos ver también que hay una tapa de rediseño y de modificación de la implementación, esto se debe, tal y como se ha comentado a lo largo de la memoria, a los problemas de falta de memoria. Se ha llevado un diario de trabajo, en el que cada día se escribía que se ha hecho, que problemas se han encontrado, posibles soluciones pensadas y trabajo pendiente para el siguiente día; este documento se ha complementado con un diario en el que se apuntaban todas las páginas de internet consultadas, los emails mandados con el director y todos los comandos que se iban aprendiendo de Matlab. 96 En la siguiente figura se muestra el tiempo dedicado a cada parte del proyecto. Figura G2: Gráfico que representa las horas invertidas El número de horas invertidas en cada fase, aproximadamente se refleja en la siguiente tabla. Figura G3: División del trabajo en horas 97 INDICE DE FIGURAS Figura 1: Esquema de llegada e indexación de documentos por bibliotecarios ……………………… 2 Figura 2: Proceso de llegada de datos y ejecución del algoritmo……………………………....... 4 Figura 3: Grafo Bipartito Documento – Término………………………………………………… 10 Figura 4: Grafo Bipartito Categoría – Documento…………………………………………… 11 Figura 5: Ejemplo de documento matemático……………………………………………………. 15 Figura 6: Estructura de los datos del fichero………………………………………………........... 17 Figura 7: Diagrama de flujo de la construcción de la jerarquía……………………………… 23 Figura 8: Ejemplo de la curva Je-k.................................................................................................. 31 Figura 9: Aproximación de la curva Je-k........................................................................................ 31 Figura 10: Ejemplo de fichero resultado....................................................................................... 32 Figura 11: Categorías pertenecientes a un subconjunto de cien documentos random.................... 36 Figura 12: Curva Je-k pertenecientes a un subconjunto de cien documentos random.................... 36 Figura 13: Clustering con k=3 y k=5............................................................................................... 37 Figura 14: Clustering k=5 dividido por áreas MSC......................................................................... 37 Figura 15: División por áreas según MSC...................................................................................... 38 Figura 16: Curva y aproximación de la curva Je-k para el experimento 2..................................... 38 Figura 17: Clustering para k=3 y k=4 para el experimento 2........................................................ 39 Figura 18: Clustering para k=4 con división por áreas............................................................... 39 Figura 19: Clustering y grafica Je-k de la categoría 39.................................................................. 40 Figura 20: Clustering y grafica Je-k de la categoría 85.................................................................. 41 Figura 21: Prueba PA15 -Clustering y grafica Je-k para dos subconjuntos.................................. 42 Figura 22: Prueba PC12 -Clustering y grafica Je-k para dos subconjuntos.................................. 42 Figura 23: Prueba PC23 -Clustering y grafica Je-k para tres subconjuntos................................... 43 Figura 24: Prueba PC32 -Clustering y grafica Je-k para cuatro subconjuntos............................. 43 Figura 25: Prueba PC32 con k=5................................................................................................... 44 Figura 26: Prueba PC41 -Clustering y grafica Je-k para cinco subconjuntos.............................. 44 Figura C1: Teorema SVD.............................................................................................................. 69 Figura C2: Ejemplo matrices A y B.............................................................................................. 70 Figura C3: Matrices resultantes ................................................................................... 70 Figura C4: Teorema GSVD........................................................................................................... 71 Figura G1: Diagrama de Gantt para la gestión del proyecto........................................................ 95 Figura G2: Gráfico que representa las horas invertidas................................................................ 96 Figura G3: División del trabajo en horas........................................................................................ 96