Clasificación semi-supervisada de series temporales

Résumé

Resulta difícil imaginar una rama de la ciencia en la que no aparezcan datos que puedan ser modelados como series temporales. Según su definición [1-3], las series temporales se obtienen mediante la medición de variables a través del tiempo. Por lo general, los datos almacenados a través del tiempo contienen información valiosa para su dominio de procedencia. Esto ha condicionado el surgimiento de una rama de la minería de datos que se encarga exclusivamente de las series temporales [4,5]. Uno de los enfoques de la minería de datos temporales consiste en adaptar los métodos tradicionales para tratar las series temporales como una clase especial de dato [6]. La clasificación constituye una de las principales tareas de la minería de datos y persigue como objetivo asociar datos con grupos predefinidos o clases. La mayoría de los algoritmos de clasificación asumen algún conocimiento de los datos o realizan fases de entrenamiento para estas clasificaciones. Muchos de los algoritmos de clasificación conocidos se han adaptado para ser utilizados con series temporales, entre ellos se destacan: los árboles de decisión [7], las máquinas de soporte vectorial [8] y los k vecinos más cercanos (kNN) [9]. En el dominio temporal resulta usual contar con grandes volúmenes de datos sin etiquetar [10,11]. Por el contrario, la obtención de datos etiquetados resulta, en ocasiones, un proceso que consume tiempo y esfuerzo de los expertos. La utilización durante el aprendizaje, tanto de datos etiquetados como no etiquetados, se conoce en la literatura como aprendizaje semi-supervisado [12]. El aprendizaje semi-supervisado constituye una opción factible para aquellos problemas donde existe un número limitado de datos etiquetados. Una de las primeras propuestas de este tipo de algoritmo, orientada a la clasificación de series temporales, es desarrollada por Wei y Keogh [13]. Esta se basa en un esquema de auto-etiquetado conocido como self-training [14]. A partir de ese momento surgen otras propuestas basadas en varios métodos de aprendizaje semi-supervisado adaptados para el tratamiento de series temporales [15]. Además del self-training existen otros métodos de auto-etiquetado [16] con características atractivas que hacen factible su aplicación al dominio temporal. Específicamente, los métodos de auto-etiquetado basados en múltiples clasificadores [17,18] ofrecen soluciones adecuadas y aún no se ha extendido su uso en la clasificación de datos temporales. Hasta el momento, los trabajos existentes sobre esta temática aún son escasos y poco concluyentes sobre cuáles enfoques resultan más efectivos para el trabajo con series temporales. Además, las características particulares de las series temporales añaden complejidad adicional a la tarea de clasificación, aspecto que debe tenerse en cuenta al estudiar la aplicabilidad de los métodos de auto-etiquetado en este dominio. La presente investigación se centra en el estudio, diseño y evaluación de métodos semi-supervisados de auto-etiquetado para abordar la clasificación de series temporales, considerando las características distintivas implicadas en el tratamiento de este tipo de dato. En ese sentido los objetivos planteados fueron: 1. Efectuar un estudio comparativo experimental entre varios métodos de auto-etiquetado de probada efectividad en aras de identificar cuáles ofrecen mejores resultados en la clasificación de series temporales. 2. Desarrollar un estudio sobre la influencia que ejerce la complejidad de los problemas temporales, desde el punto de vista de la clasificación, en el desempeño de los métodos de auto-etiquetado. 3. Proponer y validar criterios de parada para el algoritmo self-training, orientados al aprendizaje semi-supervisado de una clase, que resulten más efectivos en comparación con los reportados en la literatura. 4. Implementar un paquete de código abierto en lenguaje R para la aplicación de métodos de auto-etiquetado en la solución de problemas de clasificación semi-supervisada. La primera contribución de la tesis consiste en un estudio comparativo entre varias técnicas de auto-etiquetado donde se exploraron diversos clasificadores base adaptados específicamente al tratamiento de series temporales. Los resultados obtenidos permitieron alcanzar varias conclusiones sobre la aplicabilidad de este tipo de técnicas al dominio temporal. Respecto al desempeño de los clasificadores base, se ratificó el 1NN como una opción robusta en el contexto semi-supervisado por ofrecer las clasificaciones de mayor exactitud. Los restantes clasificadores base evaluados presentan resultados competitivos cuando se combinan sus hipótesis siguiendo un esquema de multiaprendizaje. Respecto a los métodos semi-supervisados evaluados, se destacaron particularmente tres métodos de auto-etiquetado: SETRED, tri-training y democratic. Estos métodos presentaron resultados significativamente superiores al resto en términos de sus capacidades tanto inductivas como transductivas. El enfoque multiclasificador, al que pertenecen los métodos tri-training y democratic, se destacó como una solución prometedora al problema de la clasificación semi-supervisada en el contexto de las series temporales. La segunda contribución de la tesis consiste en un estudio experimental acerca de la relación entre la complejidad asociada a los problemas de clasificación temporales y los resultados obtenidos por las técnicas de auto-etiquetado estudiadas. Como parte de dicho estudio se evaluaron varias medidas de complejidad, las cuales resultaron informativas sobre las características de los conjuntos de datos temporales incluso para conjuntos pequeños de ejemplos etiquetados. Como resultado de este estudio se constató una fuerte correlación entre la complejidad estimada y la exactitud obtenida mediante los métodos semi-supervisados evaluados. De esta forma se identificaron las medidas de complejidad más relevantes y en correspondencia los aspectos relacionados con la complejidad que ejercen mayor influencia en la clasificación obtenida. En cuanto a la competencia de los métodos semi-supervisados en relación a la complejidad de los conjuntos temporales, se identificaron los métodos tri-training y democratic por presentar un mejor comportamiento frente a problemas de baja complejidad. Por el contrario, el método SETRED se mostró competitivo al enfrentar problemas de mediana y alta complejidad. La tercera contribución de la tesis consiste en la propuesta de cinco criterios de parada para el algoritmo P1NNPU, el cual ha sido ampliamente utilizado en el dominio de las series temporales, específicamente para tratar la clasificación de problemas de una clase en el contexto semi-supervisado. Este algoritmo es una variante del self-training donde el criterio de parada juega un papel crucial para impedir la inclusión errónea de ejemplos negativos en la clase positiva. El uso de la técnica de análisis gráfico, aplicada a las distancias mínimas obtenidas por el clasificador base 1NN, resultó una técnica efectiva para identificar la frontera entre clases. Específicamente, de los cinco criterios propuestos se identificó el criterio SC4 como el más robusto a partir de la experimentación realizada. La capacidad transductiva del método CBD-GA-SC4 superó los métodos existentes del estado del arte, alcanzando resultados competitivos tanto para la distancia euclidiana como para DTW. Por último, todos los métodos semi-supervisados utilizados durante el desarrollo de la tesis se incorporaron en un paquete de R llamado ssc, el cual permite resolver problemas de clasificación tanto inductivos como transductivos. Dicho paquete resulta fácil de extender con nuevos algoritmos semi-supervisados y ofrece diferentes formas de introducir los datos de entrenamiento, incluyendo la especificación de funciones de distancias que se encuentren implementadas en otros paquetes de R. El paquete también incluye la posibilidad de definir nuevos clasificadores base lo cual añade flexibilidad a esta propuesta. Bibliografía 1. Chatfield, C.: The analysis of time series: an introduction. CHAPMAN & HALL/CRC Texts in Statistical Science. CRC press, sixth edition ed., 2013. 2. Shumway, R. H. y D. S. Stofer: Time series analysis and its applications: with R examples. Springer Science & Business Media, third ed., 2010, ISBN 978-1-4419-7864-6. 3. Hyndman, R. J. y G. Athanasopoulos: Forecasting: principles and practice. OTexts, 2012. https://www.otexts.org/fpp. 4. Fu, T.: A review on time series data mining. Engineering Applications of Artficial Intelligence, 24(1):164-181, 2011. 5. Esling, P. y C. Agon: Time-series Data Mining. ACM Comput. Surv., 45(1):12:1-12:34, Dic. 2012, ISSN 0360-0300. 6. Keogh, E. y S. Kasetty: On the need for time series data mining benchmarks: a survey and empirical demonstration. Data Mining and knowledge discovery, 7(4):349-371, 2003. 7. Douzal-Chouakria, A. y C. Amblard: Classi cation trees for time series. Pattern Recognition, 45(3):1076-1091, 2012, ISSN 0031-3203. 8. Zhang, D., W. Zuo, D. Zhang y H. Zhang: Time Series Classification Using Support Vector Machine with Gaussian Elastic Metric Kernel. En 20th International Conference on Pattern Recognition (ICPR), ICPR '10, págs. 29-32, Aug 2010. 9. Petitjean, F., G. Forestier, G. I. Webb, A. E. Nicholson, Y. Chen y E. Keogh: Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm. Knowledge and Information Systems, 47(1):1-26, 2016, ISSN 0219-3116. 10. Goldberger, A. L., L. A. Amaral, L. Glass, J. M. Hausdor , P. C. Ivanov, R. G. Mark, J. E. Mietus, G. B. Moody, C. Peng y H. E. Stanley: Physiobank, physiotoolkit, and physionet components of a new research resource for complex physiologic signals. Circulation, 101(23):e215-e220, 2000. 11. Bruno, G. y P. Garza: Temporal Pattern Mining for Medical Applications. Intelligent Systems Reference Library, 25:9-18, 2012. 12. Chapelle, O., B. Scholkopf y A. Zien: Semi-supervised learning, vol. 2. MIT Press Cambridge, 2006. 13. Wei, L. y E. Keogh: Semi-supervised Time Series Classi cation. En Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, págs. 748-753, 2006. 14. Yarowsky, D.: Unsupervised word sense disambiguation rivaling supervised methods. En Proceedings of the 33rd annual meeting on Association for Computational Linguistics, págs. 189-196. Association for Computational Linguistics, 1995. 15. Ratanamahatana, C. A. y D. Wanichsan: Stopping Criterion Selection for Efficient Semi-supervised Time Series Classifcation. En Lee, R. (ed.): Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, vol. 149 de Studies in Computational Intelligence, págs. 1-14. Springer Berlin Heidelberg, 2008, ISBN 978-3-540-70559-8. 16. Triguero, I., S. García y F. Herrera: Self-labeled techniques for semi-supervised learning: taxonomy, software and empirical study. Knowledge and Information Systems, 42(2):245-284, 2015, ISSN 0219-1377. 17. Zhou, Y. y S. Goldman: Democratic co-learning. En IEEE 16th International Conference on Tools with Artificial Intelligence (ICTAI), págs. 594-602. IEEE, Nov 2004. 18. Zhou, Z. y M. Li: Tri-training: exploiting unlabeled data using three classifiers. IEEE Transactions on Knowledge and Data Engineering, 17(11):1529-1541, Nov 2005, ISSN 1041-4347.