INTRODUCCIÓN

Varias son las esferas de la vida real en las que es necesario realizar un proceso de clasificación. Para realizar el proceso de clasificación se necesita un conjunto de muestras etiquetadas (prototipos) lo suficientemente representativas, que sean capaces de emitir un juicio correcto acerca de la clase a la cual pertenece un nuevo objeto. Este conjunto de muestras etiquetadas se conoce en la literatura como conjunto de entrenamiento (Training Set, TS).

Los algoritmos de clasificación semi-supervisada o de aprendizaje semi-supervisado(Chapelle, Schölkopf, & Zien, 2006; Kalish, Rogers, Lang, & Zhu, 2011; Qiuhua, Xuejun, Hui, Stack, & Carin, 2009; Rohban & Rabiee, 2012; Settles, 2009; Zhou & Goldman, 2000)tienen como única información a priori pocas muestras de las clases presentes y cuentan con un conjunto numeroso de objetos no etiquetados que serán utilizados también en el proceso de clasificación. En procesos de aprendizaje semi-supervisado, se pueden cometer errores que más tarde ocasionarán a su vez fallos en la clasificación de nuevos objetos, ya que aprender de datos mal clasificados perjudica la funcionalidad de los algoritmos de clasificación, lo que demuestra la necesidad de aplicar estrategias de eliminación de los objetos ruidosos en las bases de datos.

Muchos algoritmos de detección de ruido trabajan sobre conjuntos de datos estáticos (algoritmos de edición), éstos tienden a obtener un conjunto de prototipos eliminando outliers, y no tienen en cuenta los cambios que se pueden ocasionar con el transcurso del tiempo(García, Derrac, Cano, & Herrera, 2012; Segata, Blanzieri, Delany, & Cunningham, 2010; F. Vázquez, Sánchez, & Pla, 2005; D. L. Wilson, 1972; D. R. Wilson & Martínez, 2000). Sin embargo, se deben tener en cuenta los cambios en la distribución de los datos que pueden ocurrir en el transcurso del tiempo, dando lugar a lo que sede nomina cambio de concepto (concept drift) (Bose, Van der Aalst, Žliobaitė, & Pechenizkiy, 2011; Klinkenberg, 2004).

En(Zhu et al., 2008) aparece un método para eliminar ruido en un flujo de datos, utilizando técnicas estadísticas como el margen de varianza máxima, y hace una comparación entre las técnicas de Filtrado Local (FL), Global (FG) y, Local y Global (FLyG). Este método tiene tres

limitaciones fundamentales: 1) necesita introducir un parámetro que indica el número de objetos que considera como ruidosos en la base de datos, esto en general, es un problema ya que es imposible conocer a priori cuán contaminados están los datos, 2) se necesita evaluar la función que caracteriza el principio del margen de varianza máxima muchas veces, lo que hace el proceso costoso y 3) los mejores resultados de su algoritmo se obtienen con el Filtrado FLyG, por lo que hace falta desarrollar tanto el filtrado local como el global.

En el presente trabajo, se muestra una nueva estrategia para la detección de ruido en flujos de datos mediante criterios de vecindad para eliminar las limitaciones del método propuesto en (Zhu et al., 2008) empleando un ensemble de dos clasificadores. Además, se hace una propuesta de un esquema de aprendizaje semi-supervisado que utiliza en la etapa del filtrado de las muestras, el método de limpieza de ruido propuesto.

MATERIALES Y MÉTODOS

Los métodos de limpieza de ruido en general, usan clasificadores entrenados de una porción de los datos de entrenamiento, para justificar las muestras excluidas. Esto puede ser posible para datos estáticos, pero en flujos de datos, es necesario tener en cuenta que ellos están sujetos a cambios en las diferentes distribuciones, por lo que es necesario definir estrategias para lidiar con esta problemática. Se pueden efectuar tres variantes para filtrar el flujo de datos:

1) El Filtrado Local (FL) realiza la limpieza de los datos localmente dentro de cada bloque, sin necesitar ningún otro bloque de datos, 2) Filtrado Global (FG) que utiliza clasificadores entrenados desde múltiples bloques para identificar el ruido y/o 3) Filtrado Local y Global (FLyG) que tiene en cuenta los objetos ruidosos según cada una de las dos estrategias anteriores.

En este trabajo, se modela el flujo de datos a través de los bloques que denotamos por de objetos etiquetados, provenientes de diversas fuentes. Para todos los objetos de cada bloque se aplica una regla de clasificación, y se verifica si la etiqueta asignada

al objeto coincide con la etiqueta que tiene originalmente, en caso que esto no ocurra, el objeto

se considera ruidoso y es eliminado.

Un problema de clasificación en general puede ser descrito en la siguiente forma:

Sean un conjunto de muestras etiquetadas (conjunto de entrenamiento) y un nuevo objeto que se quiere asignar a una de las clases tal que . Si son las probabilidades a posteriori de cada una de las clases, se debe asignar a la etiqueta que maximice el valor de la probabilidad anteriormente descrita, i. e.:

Una de las técnicas más empleadas para manejar los cambios de conceptos son los ensembles de clasificadores, mediante los cuales las salidas de varios clasificadores se combinan para tomar una decisión final. En nuestra estrategia se utiliza un producto de dos funciones y que representan estrategias de clasificación diferentes y luego se normaliza como se expresa en la Fórmula 2.

Dado un conjunto de entrenamiento y un objeto a clasificar, denotemos por al conjunto de los elementos de más cercanos (de acuerdo a las distancia Euclidiana) a ( - vecindad de en ) unido al conjunto de los elementos de que tienen a incluido en su

-vecindad, entonces se define:

donde representa la clase de y es el cardinal del conjunto . Por otro lado, para definir la probabilidad se tuvo en cuenta la cercanía de a las clases presentes, i.e.:

donde es un número positivo pequeño y

Es precisamente en el filtrado global, donde se considera el concept drift, que significa que se decanteno ignoren todos los bloques anteriores a uno dado. La idea de esta propuesta se basa en el hecho que si hay distribuciones de los datos muy antiguas, es aconsejable no tenerlas en cuenta, porque podría provocar criterios falsos acerca de la situación actual.Así, en un filtrado

global se utiliza un parámetro para determinar cuántos bloques anteriores a van a formar parte del conjunto de entrenamiento :

El algoritmo de detección de ruido en flujos de datos que se propone en este trabajo se muestra en la Figura 1.El conjunto de entrenamiento se constituye con los elementos de los bloques anteriores a que ya han sido aceptados como no ruidosos (Fórmula 5).

Aprendizaje semi-supervisado con limpieza de ruido

En aprendizaje semi-supervisado, se tiene un conjunto pequeño de muestras correctamente etiquetadas y un conjunto grande de objetos sin clase que necesitan ser etiquetados para luego ser utilizados como conjunto de entrenamiento, con el objetivo de clasificar nuevas muestras. Se considera que los objetos sin etiqueta llegan formando una secuencia de bloques y con algún clasificador, se asignan etiquetas a los objetos, modelando de esta forma un flujo de datos .

Entre los elementos etiquetados de cada bloque existen algunos ruidosos debido a errores en la clasificación, lo que puede ocasionar la aparición del cambio de conceptos. Una manera de detectar el concept drift es mediante la aplicación del método de detección de ruido utilizando únicamente los dos resultados más recientes como se explicó en la sección anterior. El esquema de aprendizaje semi-supervisado se resume en la Figura 2.Con esta nueva propuesta, constituye el conjunto de entrenamiento actual el conjunto obtenido, a diferencia de otros esquemas de aprendizaje semi-supervisado(F. D. Vázquez, Sánchez, & Pla, 2008).

Figura 1. y Figura 2.
Resumen del algoritmo de limpieza de ruido y Algoritmo de aprendizaje con limpieza de ruido

Por tanto, en dependencia de la funcionalidad del clasificador empleado en el paso 1.1, y de la aplicación del algoritmo de detección de ruido en el paso 1.2, así será la calidad del conjunto de entrenamiento obtenido en cada etapa.

Para desarrollar el paso 1.2 la primera vez, se selecciona un conjunto inicial de datos bien etiquetados que constituyen la experiencia existente acerca de la distribución de las clases, que sirve como conjunto de entrenamiento para etiquetar los objetos de y luego, decidir cuáles de ellos fueron mal etiquetados. La segunda vez, el conjunto de entrenamiento será la unión de y , para, desde entonces, utilizar los dos conjuntos de aceptados anteriores al bloque que se evalúa.

RESULTADOS Y DISCUSIÓN

En este epígrafe se muestran los resultados obtenidos de la experimentación realizada para probar el método propuesto, sobre bases de datos reales y sintéticos. Entre las bases de datos se tomaron G4 y G6, dos bases de datos sintéticas formadas por Gaussianas, la primera tiene 4 modos gaussianos con cierto grado de solapamiento, mientras que la segunda tiene 6 modos gaussianos, 4 de ellos muy solapados. El resto de las bases de datos fueron tomadas del repositorio UCI(Newman, Blake, Hettich, & Merz, 1998). En la Tabla 1 se exponen las principales características de estas colecciones de datos.

Tabla 1.

Características básicas de las bases de datos usadas

Se utilizó como medida de calidad la Precisión (ver Fórmula 6), donde es el conjunto de los objetos ruidosos detectados por el algoritmo y es el conjunto de los ruidosos reales:

Para simular el flujo de datos, cada una de las bases de datos fue dividida en 10 bloques de manera aleatoria, manteniendo la distribución de probabilidades de las clases, y de cada bloque del flujo de datos se seleccionó de manera aleatoria un porcentaje de objetos a los que se les alteró su correcta etiqueta de clase para simular la existencia de

objetos ruidosos en la base de datos. Con cada valor de se generaron cinco conjuntos

diferentes de objetos mal etiquetados. Los resultados son el promedio de las cinco ejecuciones realizadas del proceso indicado. El conjunto para cada se construyó tomando los valores de

En las Tabla 2 se muestran los porcentajes de precisión en la detección del ruido que se obtuvo para cada una de las bases de datos, es decir, el porcentaje de objetos verdaderamente ruidosos que el algoritmo detectó como ruidosos.

Nótese que en todos los casos el mayor porcentaje de aciertos se obtuvo con el Filtrado Global (en negrita), o sea, con el Filtrado FG se detecta el mayor porcentaje de objetos ruidosos, tanto cuando se considera un vecino como si se utilizan los tres vecinos más cercanos del objeto en análisis. Este es un resultado importante ya que disminuye el costo de la detección de ruido, pues no sería necesario realizar simultáneamente para cada bloque del flujo de datos un filtrado local y un filtrado global.

Obsérvese también, que cuando se tienen en cuenta los 3 vecinos de cada objeto (FG-3 o FLyG-3), los porcentajes son superiores, ya que se está utilizando una vecindad más amplia, lo cual garantiza una mayor precisión en la detección de objetos mal etiquetados.

Es de destacar, que sobre las bases de datos Cancer, Page, Pendigit y G4, con un 10% de datos mal etiquetados, considerando tres vecinos, se hace una limpieza de al menos el 90% de los objetos ruidosos con el filtrado FG. Para las bases de datos: Diabetes, Wave, Spam y G6, con un 10% de objetos ruidosos se detecta un 80% o más de los mismos. Sólo en el caso de la base de datos German, se obtuvieron porcentajes de detección de ruido inferiores.

Tabla 2.

Precisión en la detección de ruido. a) Bases de datos Cancer, German, Diabetes, Page, Phoneme y b) Wave, Pendigit, Spam, G4, G6

Para , se detectó alrededor del 50% de los objetos ruidosos, mientras que para

fueron eliminados alrededor del 40% de los objetos mal etiquetados, siempre que se aplica el filtrado global, lo que no ocurre con el filtrado FLyG con el cual los porcentajes de detección de ruido son mucho menores.

Es válido aclarar, que si cerca de la mitad de los ejemplos de la base de datos son ruidosos, hay una gran confusión entre los objetos ruidosos y los objetos con una etiquetada de clase correcta, lo que hace extremadamente difícil determinar cuáles son los objetos realmente ruidosos, se pueden observar en la Tablas 2 para este caso.

Influencia de la limpieza de ruido en aprendizaje semi-supervisado

Se evaluó la influencia de la estrategia de limpieza de ruido en un esquema de aprendizaje semi-supervisado utilizando los conjuntos de objetos aceptados como conjuntos de entrenamiento. Se seleccionó un conjunto de patrones bien etiquetados como conjunto de prueba (Test), determinando el porcentaje de clasificación correcta que los objetos aceptados como no ruidosos proporcionan al etiquetar los ejemplos del conjunto de prueba. En esta prueba, se emplearon los conjuntos de objetos aceptados del filtrado con las estrategias: FG y FLyG como conjunto de entrenamiento para clasificar el conjunto de prueba y comparamos los resultados obtenidos.

En la Tabla 3 se muestran los resultados de este experimento, con siendo el valor de mejores resultados en la detección de ruido. Se agregaron, además, dos experimentos cuyos resultados aparecen en las columnas nombradas SF (Sin Filtrado) y FP (Filtrado Perfecto), que significan: todos los bloques antes de ser filtrados, y, todos los bloques luego de haber eliminado el total de los objetos ruidosos, respectivamente. En negrita, marcamos los valores más significativos (mayores) del porcentaje de clasificación correcta. La columna BD significa base de datos, el símbolo αrepresenta el porcentaje de ruido presente.

Los resultados indican que en un esquema de aprendizaje, en el que se etiquetan objetos desconocidos, hasta un 20% de error en el etiquetado puede ser ¨corregido¨ eliminando un porcentaje alto de los objetos ruidosos, y así, los conjuntos de entrenamiento tendrían mayor calidad.

Tabla 3.

Porcentaje de clasificación correcta de los conjuntos de entrenamiento (k=3), a) Bases de datos Cancer, German, Diabetes, G4, G6 y b) Page, Phoneme, Wave, Pendigit, Spam

Puede verse, además, que cuando hay un 10% de objetos ruidosos, sobre las bases de datos: Cancer, German, Diabetes, G4, G6, Page, Wave, Pendigit y Spam, se obtiene un porcentaje de clasificación correcta superior o similar al que se obtiene cuando se realiza un filtrado perfecto. Esto significa, que es útil emplear la estrategia de detección de ruido para construir conjuntos de entrenamiento. Sólo con las bases de datos Page y Phoneme quedaron los porcentajes por debajo de los del filtrado perfecto, aunque sin una marcada diferencia en el caso del filtrado FG.

Cuando existe un 20% de objetos ruidosos en las bases de datos, también los resultados alcanzados con el método propuesto para la detección de ruido son buenos. Por ejemplo, sobre las bases de datos: German, Diabetes, G6 y Wave, los porcentajes de clasificación correcta son superiores o similares a los obtenidos con un filtrado perfecto. Para el resto de las bases de datos, los porcentajes se pueden considerar adecuados por su significado, ya que al realizar un filtrado se logra eliminar objetos ruidosos y disminuir el tamaño del conjunto de entrenamiento. Se pueden destacar los resultados que se han obtenido con las bases de datos: Cancer, G4, G6, Page, Pendigit, para las cuales, el porcentaje de clasificación correcta que proporcionan es igual o superior al 90% cuando hay un 20% o menos de error en las etiquetas de los objetos que forman los bloques. Esto garantiza que la estrategia de detección de ruido, es capaz de filtrar los bloques del flujo de datos de manera que los objetos aceptados como no ruidosos puedan ser empleados para clasificar objetos nuevos.

Obsérvese además, la diferencia de los porcentajes obtenidos después de la limpieza con relación a los obtenidos si no se aplica nuestra estrategia. Para la mayoría de las bases de datos, el porcentaje de clasificación correcta que se obtiene del conjunto de entrenamiento con ruido (sin aplicar el método de filtrado que aquí se propone) es por lo menos un 10% menor que cuando se utilizan los bloques filtrados.

Por ejemplo, sobre la base de datos cáncer, con un 10% de objetos ruidosos, sin aplicar limpieza de ruido, el porcentaje de clasificación correcta que proporciona el conjunto de entrenamiento es de un 87%. Sin embargo, después de haber detectado objetos ruidosos, el porcentaje de clasificación correcta aumenta hasta más de un 96%.

Los resultados, demuestran, además, que la estrategia de tener en cuenta el cambio de conceptos proporciona la construcción de conjuntos de entrenamiento adecuados sin necesidad de utilizar todos los objetos del flujo de datos.

El hecho de obtener buenos resultados cuando se tiene en cuenta el concept drift, además de la utilidad en sí que tiene este problema en la actualidad, es importante ya que se puede ir eliminando información no relevante en el contexto actual. Desde el punto de vista computacional es conveniente, ya que para realizar una clasificación, no es necesario utilizar todos los objetos que ya han sido procesados, sino los de la última generación.

También se puede mencionar el hecho de que cuando hay un porcentaje de error de 40% o 50% se detecta menor cantidad de objetos ruidosos, causado por la gran confusión que debe existir en este caso, pues habría casi el mismo número de objetos bien etiquetados que mal etiquetados. Igualmente, esto influye en los porcentajes de clasificación correcta. De todas formas, hay una reducción de los objetos mal etiquetados después de haber efectuado la estrategia.

CONCLUSIONES

En este trabajo se ha mostrado una nueva estrategia para la detección y limpieza de ruido en flujos de datos, empleando criterios de vecindad. En la nueva estrategia se utiliza un ensemble de dos clasificadores, para combinar los resultados que cada uno aporta en la etapa de clasificación. Este método se enfoca en el problema de la presencia del concept drift.

El método propuesto detecta automáticamente todos los objetos que considera ruidosos, no se limita a un porcentaje (este valor sólo se utiliza para simular la existencia de objetos ruidosos en el flujo de datos). Se emplea una estrategia muy simple (vecinos más cercanos).

Se realizaron los experimentos siguiendo los esquemas de los filtrados: FG y FLyG debido a que con el filtrado local (FL) no se tiene en cuenta el concept drift.

Como medida para establecer la calidad del proceso de limpieza de ruido se utilizó la precisión, analizándose el porcentaje de objetos ruidosos que el algoritmo detecta y, la calidad de los bloques luego del proceso de limpieza, para ser utilizados como conjuntos de entrenamiento en la clasificación de nuevas muestras.

De las dos estrategias de filtrado, los resultados en el procesamiento de los patrones demuestran que el filtrado FG es suficiente para detectar los objetos ruidosos. Esto es importante ya que así el proceso es menos costoso debido a que no hay que realizar el filtrado local.

El método más efectivo resultó ser el que se realiza tomando los tres vecinos más cercanos de cada objeto, lo cual demuestra que para detectar los objetos ruidosos es más conveniente verificar las etiquetas de otros objetos que rodean al que se está analizando, no sólo su vecino más cercano.

Otra cuestión a destacar es que para tener en cuenta el cambio de conceptos, sólo se emplearon dos bloques anteriores al analizado en cada etapa, esto contribuye con un ahorro computacional importante, además del hecho en sí que es tener en cuenta nada más los resultados más actuales para detectar nuevos objetos ruidosos o para clasificar objetos correctamente, desechando información fuera del contexto actual.

Los porcentajes alcanzados en cuanto al filtrado de objetos ruidosos, demuestran la validez del método aplicado, ya que se detecta un 80% o más de individuos mal etiquetados cuando hay hasta un 20% de error de clasificación. La importancia de este hecho está en la posibilidad de emplear el método en esquemas de aprendizaje semi-supervisado.

En cuanto a la calidad como conjuntos de entrenamiento de los bloques filtrados, los resultados en los casos de menos de un 30% de ruido son alentadores. Los mejores resultados se obtienen cuando hay un 10% de ruido, ya que los porcentajes son superiores a los que se obtienen con el filtrado perfecto y se demuestra que con un menor número de objetos se obtienen porcentajes de clasificación satisfactorios.

Como una aplicación de los resultados obtenidos en el esquema de detección de ruido en flujos de datos, se propuso un algoritmo de aprendizaje semi-supervisado para desechar los objetos ruidosos producto de la etapa de clasificación.

REFERENCIAS BIBLIOGRÁFICAS

1. Bose, R. P., Van der Aalst, J. C., Žliobaitė, I., & Pechenizkiy, M. (2011). Handling concept drift in process mining. Lecture Notes in Computer Science, 6741(Advanced Information Systems Engineering), 391-405.

2. Chapelle, O., Schölkopf, B., & Zien, A. (2006). Semi-supervised learning. Cambridge, Mass.: MIT Press.

3. García, S., Derrac, J., Cano, J., & Herrera, F. (2012). Prototype Selection for Nearest Neighbor Classification: Taxonomy and Empirical Study. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(3), 417-435.

4. Kalish, C. W., Rogers, T. T., Lang, J., & Zhu, X. (2011). Can semi-supervised learning explain incorrect beliefs about categories? Cognition, 120(1), 106-118.

5. Klinkenberg, R. (2004). Learning drifting concepts: examples selection vs. examples weighting. Intelligence Data Analysis, 8(3), 281-300.

6. Newman, D. J., Blake, C. L., Hettich, S., & Merz, C. J. (1998). UCI repository of machine learning databases. University of California, Irvine.

7. Qiuhua, L., Xuejun, L., Hui, L., Stack, J. R., & Carin, L. (2009). Semisupervised Multitask Learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(6), 1074– 1086.

8. Rohban, M. H., & Rabiee, H. R. (2012). Supervised neighborhood graph construction for semi-supervised classification. Pattern Recognition, 45(4), 1363-1372.

9. Segata, N., Blanzieri, E., Delany, S. J., & Cunningham, P. (2010). Noise reduction for instance-based learning with a local maximal margin approach. Journal of Intelligent Information Systems, 35(2), 301-331.

10. Settles, B. (2009). Active learning literature survey. Madison, USA: University of Wisconsin.

11. Vázquez, F., Sánchez, J. S., & Pla, F. (2005). A stochastic approach to Wilson’s editing algorithm. Pattern Recognition and Image Analysis. Lecture Notes on Computer Science, 3523, 35–42.

12. Vázquez, F. D., Sánchez, J. S., & Pla, F. (2008). Learning and forgetting with local Information of new objects. Progress in Pattern Recognition, Image Analysis and Applications. Lecture Notes on Computer Sciences. 5197, 261–268.

13. Wilson, D. L. (1972). Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems Man and Cibernetics, SMC-2(3), 408-421.

14. Wilson, D. R., & Martínez, T. R. (2000). Reduction techniques for instance based learning algorithms. Machine Learning, 38(3), 257–286.

15. Zhou, Y., & Goldman, S. (2000). Democratic Co-learning. Paper presented at the 16th IEEE International Conference on Tools with Artificial Intelligence, Boca Raton, Florida.

16. Zhu, X., Zhang, P., Wu, X., He, D., Zhang, C., & Shi, Y. (2008). Cleansing Noisy Data Streams. Paper presented at the Eighth IEEE International Conference on Data Mining, Pisa, Italy.

Notas