Arcabouço para detecção online de outliers para algoritmos de agrupamento em fluxos contínuos de dados

Abstract

Avanços da tecnologia acarretam na geração rápida e contínua de massivas quantida- des de dados. Tal cenário requer a criação de algoritmos de agrupamento incremen- tais para extração de conhecimento. Entre as restrições impostas a esses algoritmos, os mesmos devem ser capazes de detectar e tratar possíveis outliers que chegam ao fluxo. O arcabouço desenvolvido nesse trabalho apresenta uma estratégia para a restrição de tratamento e detecção de outliers na componente online dos algoritmos de agrupamento de fluxo de dados. A principal contribuição da proposta em estudo é a capacidade de validar possíveis outliers detectados previamente, com o intuito de manter um modelo sempre atualizado e com qualidade. Para isso, todos os potenci- ais outliers são armazenados em uma memória auxiliar que de tempos em tempos é verificada, agrupando seus objetos, validando os micro-grupos formados por inliers e inserindo-os no modelo. Todos os objetos restantes que não foram validados, são mantidos na memória auxiliar até que se tornem válidos ou obsoletos. Em seguida, objetos obsoletos são removidos. Este trabalho também propõe o CluStreamOD, uma extensão do algoritmo de agrupamento CluStream, que aplica a estratégia em estudo em sua componente online, para tratar outliers. Os experimentos realizados mostram a eficácia do CluStreamOD para detecção e tratamento online de outliers do fluxo em comparação com CluStream, e a potencialidade da abordagem proposta para ser aplicada em outros algoritmos de fluxo de dados baseados em micro-grupos.

Advances in technology have led to the rapid and continuous generation of massive amounts of data. Such a scenario requires the creation of incremental clustering algorithms for knowledge extraction. Among the constraints imposed on these al- gorithms, they must be able to detect and treat possible outliers that arrive at the flow. The framework developed in this work presents a strategy for the restriction of treatment and detection of outliers in the online component of the clustering algorithms in data stream. The main contribution of the proposal under study is the ability to validate possible outliers previously detected, in order to maintain a model that is always updated and with quality. For this, all the potential outliers are stored in an auxiliary memory when for time to time is verified, clustering its objects, validating the formed micro-clusters by inserting them into the model. All remaining objects that have not been validated are held in auxiliary memory until they become valid or obsolete. Then obsolete objects are removed. This work also proposes the CluStreamOD, an extension of the CluStream clustering algorithm, which applies the strategy under study in its component online, to treat outliers. Experiments carried out show the efficacy of the CluStreamOD for online detection and treatment of the outliers in the data streams compared to CluStream, and the potentiality of the proposed approach to be applied in other algorithms in data stream based on micro-clusters.