Fast outlier detection using similarity self-join techniques (2021)
- Authors:
- Autor USP: CABRAL, EUGENIO FERREIRA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: DISPOSITIVOS ELETRÔNICOS; BANCO DE DADOS; ANÁLISE DE DADOS; MINERAÇÃO DE DADOS
- Keywords: Detecção de casos de exceção; Epsilon join; Hypercube ordering; Junção epsilon; Ordenação de hipercubos; Outlier detection
- Agências de fomento:
- Language: Inglês
- Abstract: A democratização dos dispositivos eletrônicos ao longo dos anos incentivou indivíduos e indústrias a produzirem dados a um baixo custo. Como consequência, a produção de dados aumentou globalmente em ritmo acelerado. Com essa produção de dados cada vez maior, as indústrias exigiram melhores ferramentas para encontrar padrões e melhorar seus processos de tomada de decisão. Alguns eventos em particular podem não encaixar em nenhum padrão e ainda assim trazerem informações importantes. São usualmente eventos raros que não correspondem à maioria dos dados, também conhecidos como anomalias, exceções ou outliers. Eles podem representar falhas, fraudes, invasões ou condições anormais em sistemas. Detectar esses eventos o quanto antes é crucial em aplicações reais, como finanças, redes sociais e controle de qualidade. Vários algoritmos fornecem excelentes resultados em termos de qualidade, porém na prática, se mostram ineficientes para lidar com dados volumosos. Abordagens mais eficientes pressupõem que uma exceção pode ser identificada buscando por instâncias similares, também conhecidas como vizinhas devido à proximidade espacial entre as instâncias. As estruturas de dados armazenam dados e realizam sucessivas operações de busca por vizinhança para obter informações sobre a densidade da vizinhança, a qual é usada na detecção de exceções. Essa operação tem sido muito pesquisada na comunidade de busca por similaridade ao longo dos anos. Nessa comunidade, é sabido que essas sucessivasoperações podem ser substituídas por uma junção por similaridade, mas essa observação não parece óbvia na literatura de detecção de casos de exceção porque praticamente todos algoritmos criam suas próprias estratégias de busca por similaridade. A junção por similaridade é uma operação que, dado dois conjuntos de dados e um limite de similaridade, o objetivo é encontrar todos os pares de instâncias similares. Porém, quando apenas um conjunto de dados é fornecido, essa operação é denominada auto-junção por similaridade. Os algoritmos para essa operação visam melhorar a eficiência em uma ampla gama de aplicações. Como casos de exceção são eventos raros e divergentes da maioria, instâncias com poucos pares podem ser uma exceção. Neste trabalho, propomos investigar como essa sobreposição de conceitos pode ser benéfica para melhorar o desempenho e a escalabilidade de algoritmos de detecção de exceção. Propomos dois novos algoritmos baseados em técnicas de junção por similaridade - ODSSJ e HySortOD. Os resultados experimentais sugerem que as soluções são 3 ordens de magnitude mais rápida que os algoritmos estado da arte existentes.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2021
- Data da defesa: 01.03.2021
-
ABNT
CABRAL, Eugenio Ferreira. Fast outlier detection using similarity self-join techniques. 2021. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2021. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29042021-111846/. Acesso em: 26 jan. 2026. -
APA
Cabral, E. F. (2021). Fast outlier detection using similarity self-join techniques (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29042021-111846/ -
NLM
Cabral EF. Fast outlier detection using similarity self-join techniques [Internet]. 2021 ;[citado 2026 jan. 26 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29042021-111846/ -
Vancouver
Cabral EF. Fast outlier detection using similarity self-join techniques [Internet]. 2021 ;[citado 2026 jan. 26 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29042021-111846/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
