PDF de programación - Clasificadores Supervisados basados en Patrones Emergentes para Base de Datos con Clases Desbalanceadas

Clasificadores Supervisados basados en Patrones Emergentes

para Bases de Datos con Clases Desbalanceadas

Octavio Loyola González, José Francisco Martínez Trinidad, Milton García Borroto

Reporte Técnico No. CCC-14-004

14 de Octubre del 2014

c⃝ Coordinación de Ciencias Computacionales

INAOE

Luis Enrique Erro 1
Sta. Ma. Tonantzintla,
72840, Puebla, México.

Clasificadores Supervisados basados en Patrones Emergentes para Bases de

Datos con Clases Desbalanceadas

Octavio Loyola González *1,2, José Francisco Martínez Trinidad1, Milton García Borroto3
1Coordinación de Ciencias Computacionales, Instituto Nacional de Astrofísica, Óptica y
Electrónica. Luis Enrique Erro # 1, Santa María Tonantzintla, Puebla, México, C.P. 72840

2Centro de Bioplantas, Universidad de Ciego de Ávila. Carretera a Morón Km 9, Ciego de Ávila,

3Instituto Superior Politécnico “José Antonio Echeverría”. Calle 114 # 11901, Marianao, La

Cuba, C.P. 69450

{octavioloyola, fmartine}@inaoep.mx

Habana, Cuba, C.P. 19390
{mgarciab}@ceis.cujae.edu.cu

Resumen

La clasificación supervisada es una rama del reconocimiento de patrones que encuentra la relación entre
objetos no etiquetados y un conjunto de objetos previamente etiquetados, con el propósito de asignarles
una etiqueta a los objetos no etiquetados. En muchas tareas de clasificación, una alta eficacia no es la
única característica deseada; el clasificador y sus resultados deben ser entendibles por los expertos en el
dominio de aplicación. Para esto, una opción consiste en construir clasificadores interpretables a partir de
patrones que relacionan o diferencian a los objetos. Además, en clasificación supervisada, frecuentemente
aparecen problemas donde la cantidad de objetos que pertenecen a una clase es significativamente mayor
que la cantidad de objetos que pertenecen a otra clase. Frecuentemente, la clase minoritaria es la más
importante pero es difícil identificarla, ya que podría estar asociada a casos excepcionales o porque la
adquisición de estos datos es muy complicada. En esta propuesta de investigación doctoral se plantea
desarrollar algoritmos para la extracción y clasificación basada en patrones emergentes para problemas
con clases desbalanceadas. Como resultados preliminares se muestra una primera solución al problema
mediante la aplicación de métodos de re-muestreo. Además, se presenta un estudio acerca de las medidas
de calidad, para patrones emergentes, más utilizadas en la literatura en el contexto de los clasificadores
basados en patrones; así como el desempeño de las mismas para guiar la selección de un método de filtrado
de patrones emergentes.

Palabras Clave.— Clasificación Supervisada, Patrones Emergentes, Desbalance de Clases.

*Tel. +52 222 2663100 (Ext. 8310); +53 33 224026

Índice

1. Introducción

2. Conceptos básicos

2.1. Representación de objetos
.
.
. .
2.2. Patrones Emergentes
.
.
.
.
2.3. Desbalance . .
.
2.4. Matriz de Costo .
.
.
.
.
2.5. Validación de los resultados .

.
.
.

.
.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
. . . . . . . . . . . . . . . . . . . . . . .
. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.

. .

. .

. .

. .

3

4
5
5
5
6
7

9
3. Trabajos Relacionados
9
.
.
3.1. Nivel de datos . .
3.2. Modificación de algoritmos .
. 11
3.3. Matrices de costo .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
.
3.4. Características intrínsecas de los datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

. .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.

. . . . . . . . . . . . . . . . . . . . . . . .

. .

. .

. .

.

.

.

.

.

.

.

.

.

4. Propuesta

.

.

.
.

.
.

.
.

4.1. Motivación . .
.
.
4.2. Problema a resolver .
.
4.3. Preguntas de investigación .
.
4.4. Objetivo general .
.
.
4.5. Objetivos particulares . .
.
.
4.6. Contribuciones
4.7. Metodología . .
.
.
.
.
4.8. Cronograma . .

.
.
.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.

.

.

. .

. .

. .

. .

15
. 15
. 16
. 16
. 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
. 17
. 17
. 20

. . . . . . . . . . . . . . . . . . . . . . .
. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. .
. .
. . . . . . . . . . . . . . . . . . . . . . .

. .
. .

. .
. .

. .
. .

. .
. .

5. Resultados preliminares

20

5.1. Aplicación de métodos de re-muestreo al problema de clasificación supervisada basada en

patrones emergentes en bases de datos con clases desbalanceadas . . . . . . . . . . . . . . . 21
. . . . . . . . . . . . . . . . 27

5.2. Comparación de medidas de calidad para patrones emergentes

6. Conclusiones

33

1.

Introducción

La clasificación supervisada aparece en múltiples aplicaciones como: detección de fraudes, bioinformáti-
ca, medicina, agricultura y biología, entre muchas otras (Dong, 2012a). Los clasificadores supervisados
operan usualmente sobre la información suministrada por un conjunto de objetos, instancias, ejemplos o
prototipos de entrenamiento que poseen una etiqueta de clase previamente asignada. A este conjunto de ob-
jetos etiquetados se le llama conjunto de entrenamiento y la información que ellos proporcionan es utilizada
para la clasificación de nuevos objetos (Ruiz-Shulcloper, 2008).

En muchas tareas de clasificación supervisada, una alta eficacia no es la única característica deseada; el
clasificador debe ser entendible por los expertos del dominio de aplicación (García-Borroto et al., 2012).
Para esto, una opción consiste en construir clasificadores interpretables por los especialistas a partir de
patrones extraídos de los objetos del conjunto de entrenamiento, de tal manera que el resultado final pueda
interpretarse a partir de los patrones asociados a cada clase.

En los últimos años, el problema de clasificación supervisada con clases desbalanceadas ha sido aborda-
do con gran interés por la comunidad científica debido a que aparece en varias aplicaciones prácticas. Por
ejemplo, la detección de transacciones bancarias fraudulentas es uno de los problemas con gran desbalance
de clases (Wei et al., 2013; Bhattacharyya et al., 2011; Zhang et al., 2004). En este tipo de base de datos
pueden existir cinco transacciones fraudulentas por cada 300,000 transacciones reales que se hacen en un
día (Wei et al., 2013). Además, la detección debe hacerse en tiempo real dado que el tiempo es muy breve
para hacer efectiva una transacción bancaria. Otros estudios y aplicaciones pueden encontrarse en el campo
de la medicina para la detección de microcalsificaciones en imágenes de mamografías (M.n and Shesha-
dri, 2012), sistemas para la toma de decisiones médicas (Jackowski et al., 2012), detección de infecciones
intrahospitalarias (Cohen et al., 2006), trastornos hepáticos y del páncreas (Li et al., 2010), entre muchas
otras. También, se han reportado otros trabajos relacionados con bases de datos reales para la predicción de
secuencias de proteínas (Al-shahib et al., 2005), estrategias de marketing (Ling and Li, 1998), servicios de
suscripciones (Burez and den Poel, 2009), predicción de los niveles de ozono (Tsai et al., 2009) y reconoci-
miento de rostros (Yang et al., 2004). Varios de estos trabajos utilizan algoritmos de extracción de patrones
emergentes para tratar de extraer conceptos que sean interpretables por los especialistas.

Trabajar con clases desbalanceadas puede implicar un sesgo en los clasificadores basados en patrones,
priorizando la clase mayoritaria y realizando una mala clasificación de aquellos objetos que pertenecen a
la clase minoritaria (López et al., 2013; Fernández et al., 2010). Algunas razones que pueden justificar este
comportamiento son las siguientes (López et al., 2013; Burez and den Poel, 2009):

1. El uso de medidas de desempeño globales para guiar el proceso de aprendizaje puede proporcionarle

una ventaja a la clase mayoritaria.

2. Los patrones que predicen la clase minoritaria son a menudo altamente especializados y por lo tanto
su cobertura1 es muy baja, en consecuencia, éstos se descartan en favor de patrones más generales que
predicen la clase mayoritaria.

1Cantidad de objetos que son descritos por el patrón.

3

3. Pequeños grupos de objetos de la clase minoritaria se pueden identificar como ruido y, por lo tanto,
podrían ser erróneamente descartados por el clasificador. Por otro lado, algunos ejemplos ruidosos
reales pueden degradar la identificación de la clase minoritaria, ya que ésta tiene un menor número de
objetos.

La comunidad científica internacional ha trazado tres estrategias fundamentales para mitigar las dificul-
tades que aparecen en la clasificación supervisada al trabajar con bases de datos con clases desbalanceadas
(López et al., 2013, 2014a; Krawczyk et al., 2014). Estas estrategias se agrupan en las siguientes categorías:

Nivel de Datos. Re-muestreo de la base de datos para balancear las clases. Consiste en alcanzar un balance
entre las clases mediante la eliminación de objetos de la clase mayoritaria (sub-muestreo) (López
et al., 2014a; Albisua et al., 2013; Charte et al., 2013; Li et al., 2010) o la inclusión de objetos en la
clase minoritaria (sobre-muestreo) (Menardi and Torelli, 2014; López et al., 2014b; Soda, 2011; Weiss
et al., 2007; Luengo et al., 2011; Chawla, 2010; Chawla et al., 2002). El sub-muestreo puede excluir
algunos objetos representativos o valiosos para entrenar el clasificador. En cambio, el sobre-muestreo
incluye objetos artificiales que pueden sobre-entrenar al clasificad