PDF de programación - Detección de outliers en grandes bases de datos mediante aproximación basada en celdas

Detección de outliers en grandes bases de datos me-

diante aproximación basada en celdas



Adrián De Armas1, Mag. Bibiana D. Rossi1, Dr. Horacio Kuna2

1 Universidad Argentina de la Empresa, Facultad de Ingeniería y Ciencias Exactas, Buenos

Aires, Argentina.

[email protected], [email protected]

2 Universidad Nacional de Misiones, Facultad de Ciencias Exactas Químicas y Naturales.

Misiones. Argetina.

[email protected]



Resumen: Este artículo aborda la problemática de la detección de outliers en grandes bases de
datos. En base a la aproximación por celdas propuesta por Edwin Knorr y Raymond NG en 1998
en el trabajo “Algorithms for Mining Distance-Based Outliers in Large Datasets” se implemen-
taron distintas versiones del algoritmo que superan las limitaciones establecidas en el trabajo
original con modificaciones orientadas a mejorar la eficiencia y la utilización del algoritmo en
distintos escenarios.
Palabras clave: Outliers, celdas, algoritmos basados en distancia, grandes bases de datos, para-
lelización, determinación probabilística, FindAllOutsM.

1. Introducción

Un outlier es cualquier dato que parece estar fuera de lugar respecto al resto de los
datos. En la bibliografía pueden encontrarse sinónimos tales como excepción, contami-
nante, disidente, desvío, anomalía, valor discordante, sorprendente o inesperado[1].
Una de las definiciones más citadas es: “Un outlier es una observación que se desvía
tanto de otras observaciones que despierta la sospecha de haber sido generado por un
mecanismo diferente” [2].

Para algunas aplicaciones, los eventos raros son interesantes. Aplicaciones como la
detección de fraude con tarjeta de crédito y el monitoreo de actividades criminales en
el comercio electrónico se benefician con la detección de outliers. Por ejemplo, en el
comercio electrónico se espera la existencia de muchas transacciones de bajo valor, sin
embargo son los casos excepcionales (importe de la transacción, tipo de compra, hora
en que se realiza, ubicación o alguna combinación de las anteriores) lo que interesa
tanto para la detección de fraude o por motivos de marketing.

Distintos métodos de detección de outliers han sido propuestos. Métodos de análisis
de valores extremos, modelos estadísticos y probabilísticos, métodos basados en pro-
fundidad, desvío, ángulos o distancia son algunos de ellos. En este artículo se presentan
las mejoras significativas realizadas al algoritmo FindAllOutsM de aproximación por
celdas propuesto por Edwin Knorr y Raymond NG en 1998 [3].

El artículo se organiza de la siguiente manera: la sección 2 expone la problemática
para la detección de outlieres y presenta la estrategia basada en celdas. En la sección 3

ASSE 2015, 16º Simposio Argentino de Ingeniería de Software. 44 JAIIO - ASSE 2015 - ISSN: 2451-75931 se presentan las mejoras propuestas detallando las distintas implementaciones del algo-
ritmo logradas. Finalmente, la sección 4 se reseñan las conclusiones del trabajo.

2. Problemática actual

El tamaño del conjunto de datos y el número de dimensiones han comprobado ser
obstáculos claves para el análisis de los datos. La minería de datos provee algoritmos
que son escalables tanto en el tamaño del conjunto de datos como en las dimensiones
(variables) a evaluar [4].

La mayoría de los trabajos existentes sobre la detección de outliers yacen en el
campo de la estadística. Consistentemente, una centena de formas de detectar outliers
han sido desarrolladas para diferentes circunstancias, dependiendo de [5] [6]:

 La distribución de los datos
 Si los parámetros de la distribución son conocidos o no
 El número de outliers esperados
 El tipo de outliers esperados

Sin embargo, estas formas de detección presentan dos inconvenientes:

1. Casi todas son univariadas. Esta restricción hace que sean inaplicables para

grupos de datos multidimensionales.

2. Todas son basadas en la distribución de los datos. Existen numerosas situacio-
nes donde se desconoce si un atributo en particular sigue una distribución nor-
mal, una distribución gama, o cualquier otra, por lo cual, se deben realizar
pruebas extensas para encontrar una distribución que se ajuste al atributo.

En el año 1998 Edwing Knorr y Raymond NG publicaron el trabajo “Algorithms for
Mining Distance-Based Outliers in Large Datasets. Lo interesante de la propuesta de
Knorr y Raymond fue que la detección de outliers basados en la distancia de un objeto
a sus vecinos más cercanos, es no paramétrica, es decir, no se basa en alguna distribu-
ción específica [3][7] y se propone su uso para bancos de datos multivariados de 4, a lo
sumo 5 atributos.

Distintos métodos se han propuesto y discutido, a partir de entonces, para la detec-
ción paramétrica y no paramétrica de outliers como se puede leer en los trabajos refe-
renciados como [8][9][10][11][12].

2.1. Detección de outliers basada en celdas.

La detección de outliers basada en celdas, utiliza el método de determinación de
outliers por distancia. En este artículo se abordan los métodos basados en distancia
(Distance Based o DB) bajo la noción que un outlier se define como:

“Un objeto