Um Algoritmo Eficiente para Detecção de Exceções em Bases Reais de Alta Dimensionalidade

• Carlos H. C. Teixeira UFMG
• Gustavo H. Orair UFMG
• Wagner Meira Jr. UFMG

Resumo

A Mineração de Exceções tem sido uma área de pesquisa que possui interessantes aplicações em diferentes domínios, variando desde a limpeza de dados à detecção de fraudes. Neste trabalho, propomos um algoritmo eficiente e escalável baseado em distância para a mineração de exceções em grandes bases de dados de alta dimensionalidade. Nosso algoritmo realiza um particionamento dos dados e ordena os objetos candidatos a exceção reduzindo significativamente o número de comparações entre objetos. Avaliamos diferentes heurísticas de ordenação em um conjunto abrangente de bases de dados reais e sintéticas. Os resultados mostram que nosso algoritmo obtém um ganho de até 52% em relação ao estado da arte.

Referências

Bay, S. D., Kibler, D., Pazzani, M. J., and Smyth, P. (2000). The uci kdd archive of large data sets for data mining research and experimentation. SIGKDD Explor. Newsl., 2(2):81–85.

Bay, S. D. and Schwabacher, M. (2003). Mining distance-based outliers in near linear time with randomization and a simple pruning rule. In 9th ACM SIGKDD Int. Conf. on Knowledge Discovery on Data Mining.

Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509–517.

Ester, M., Kriegel, H. P.and Sander, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial fatabases with noise. In In Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining. AAAI Press.

Ghoting, A., Parthasarathy, S., and Otey, M. E. (2005). Fast mining of distance-based outliers in high-dimensional datasets. 6th SIAM Int. Conf. on Data Mining.

Hartigan, J. A. and Wong, M. A. (1979). A K-means clustering algorithm. Applied Statistics, 28:100–108.

Huang, Z. (1998). Extensions to the k-means algorithm for clustering large data sets with categorical values. Data Min. Knowl. Discov., 2(3):283–304.

Knorr, E. M. and Ng, R. T. (1999). Finding intensional knowledge of distance-based outliers. In VLDB ’99: 25th Int. Conf. on Very Large Data Bases, pages 211–222, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.

Ord, K. (1996). Outliers in statistical data : V. barnett and t. lewis, 1994, 3rd edition, (john wiley & sons, chichester), isbn 0-471-93094. Int. Journal of Forecasting, 12(1):175–176.

Projeto Tamandua (2006). Projeto Tamandua. [link].

Ramaswamy, S., Rastogi, R., and Shim, K. (2000). Efficient algorithms for mining outliers from large data sets. In SIGMOD ’00: Proc. ACM SIGMOD Int. Conf. on Management of data, pages 427–438, New York, NY, USA. ACM Press.

Roussopoulos, N., Kelley, S., and Vincent, F. (1995). Nearest neighbor queries. In SIGMOD ’95: ACM SIGMOD Int. Conf. on Management of data, pages 71–79, New York, NY, USA. ACM.

Zhang, T., Ramakrishnan, R., and Livny, M. (1996). Birch: an efficient data clustering method for very large databases. SIGMOD Rec., 25(2):103–114.