Learning rules in data stream mining: algorithms and applications

Abstract

En esta tesis, se propone un algoritmo completamente online basado en el aprendizaje de reglas para clasificación en flujos de datos, CLAST. El algoritmo aprende dinámicamente una población de reglas que conjuntamente representan la solución al problema. Las reglas son una forma legible de representación del conocimiento que representan relaciones entre variables y, en consecuencia, ofrecen la posibilidad de alcanzar un considerable nivel de detalle de interpretabilidad. Comparada con otros clasificadores de flujos de datos, la propuesta obtiene resultados muy competitivos en términos de precisión predictiva en los experimentos llevados a cabo. En problemas reales con tasas de llegada muy altas e inmensos volúmenes de datos suele ser difícil encontrar datos que estén completamente etiquetados y estructurados. Por lo tanto, exploramos otros paradigmas de aprendizaje, distintos al supervisado, que permitan evitar la dependencia de la disponibilidad a tiempo de las etiquetas. En esta línea, se realizan dos propuestas algorítmicas. La primera de ellas es Fuzzy-CSar-AFP; una propuesta de aprendizaje no supervisado para extracción directa de reglas de asociación en flujos de datos (association stream mining). Se trata de una propuesta online, que procesa los datos uno a uno en el momento de su llegada, y es capaz de construir y mantener directamente las reglas de asociación, sin necesidad de una etapa previa de identificación de itemsets frecuentes. La última de las propuestas, PAST, consiste en un método semi-supervisado que extiende los dos enfoques anteriores al combinar la capacidad de extraer conocimiento del etiquetado de los datos con la capacidad para aprender de datos no etiquetados. En términos de precisión predictiva, el método presenta un buen rendimiento en los experimentos realizados; mejorando los resultados obtenidos utilizando solo datos etiquetados. Esto significa que el algoritmo es capaz de extraer conocimiento de los datos no etiquetados que le permite mejorar su comprensión del problema. Adicionalmente, se estudia la viabilidad de la extracción de reglas de asociación en flujos de datos en dos aplicaciones reales. La primera de las aplicaciones se basa en datos sobre uso del smartphone, mientras que en el segundo casos se explotan flujos de tweets de contenido político. En ambos casos, el análisis de las reglas de asociación generadas resulta muy útil para comprender lo que va ocurriendo a lo largo del tiempo, aportándonos un conocimiento que será muy complicado obtener de otra manera.

In this thesis, a fully online algorithm based on learning rules for classification in data streams, CLAST, is proposed. The algorithm dynamically learns a population of rules that together represent the solution to the problem. Rules are a legible knowledge representation form that represent relationships between variables and, consequently, offer the possibility of reaching a considerable level of interpretability detail. Compared to other data stream classifiers, the proposal obtains very competitive results in the experiments carried out. In real-world problems with very high arrival rates and immense volumes of data is often difficult to fi nd data that are completely labeled and structured. Therefore, we explore other learning paradigms, besides supervised learning, that allow us to avoid dependence on timely available labels. In this line, two algorithmic proposals are made. The rst one is Fuzzy-CSar-AFP; an unsupervised learning proposal for direct extraction of association rules in data streams (association stream mining). It is an online proposal, which processes the data one by one at the time of arrival, and is able to directly build and maintain association rules, without the need for a previous stage of frequent itemset identi cation. The last of the proposals, PAST, consists of a semi-supervised method that extends the two previous approaches by combining the ability to extract knowledge from the data labeling with the ability to learn from unlabeled data. In terms of predictive ability, the method presents a good performance in the experiments conducted; improving the results obtained using only labeled data. This means that the algorithm is able to extract knowledge from unlabeled data that allows it to improve its understanding of the problem. Moreover, the viability of association rule extraction in data streams is studied in two real applications. The rst application is based on smartphone usage data, while the second one exploits streams of tweets with political content. In both cases, the analysis of the generated association rules is very useful to understand what is happening over time, providing knowledge that would otherwise be very diffcult to obtain.