Exploração das propriedades de hubness para detecção ...· Lista de tabelas Tabela 1 – Comparação

  • View
    217

  • Download
    0

Embed Size (px)

Text of Exploração das propriedades de hubness para detecção ...· Lista de tabelas Tabela 1 –...

Explorao das propriedades de hubness para

deteco semissupervisionada de outliers em dados

de alta dimenso

Lucimeire Alves da Silva

Universidade Federal de UberlandiaFaculdade de Computacao

Programa de Pos-Graduacao em Ciencia da Computacao

Uberlndia2017

Lucimeire Alves da Silva

Explorao das propriedades de hubness para

deteco semissupervisionada de outliers em dados

de alta dimenso

Dissertao de mestrado apresentada aoPrograma de Ps-graduao da Faculdadede Computao da Universidade Federal deUberlndia como parte dos requisitos para aobteno do ttulo de Mestre em Cincia daComputao.

rea de concentrao: Cincia da Computao

Orientadora: Maria Camila Nardini Barioni

Uberlndia2017

Dados Internacionais de Catalogao na Publicao (CIP)

Sistema de Bibliotecas da UFU, MG, Brasil.

S586e

2017

Silva, Lucimeire Alves da, 1990-

Explorao das propriedades de hubness para deteco

semissupervisionada de outliers em dados de alta dimenso / Lucimeire

Alves da Silva. - 2017.

88 f. : il.

Orientador: Maria Camila Nardini Barioni.

Dissertao (mestrado) - Universidade Federal de Uberlndia,

Programa de Ps-Graduao em Cincia da Computao.

Disponvel em: http://dx.doi.org/10.14393/ufu.di.2017.51

Inclui bibliografia.

1. Computao - Teses. 2. Minerao de dados (Computao) -

Teses. 3. Inteligncia artificial - Processamento de dados - Teses. I.

Barioni, Maria Camila Nardini. II. Universidade Federal de Uberlndia.

Programa de Ps-Graduao em Cincia da Computao. III. Ttulo.

CDU: 681.3

Dedico este trabalho ao meu noivo, Luciano Lopes; aos meus pais, Rosemeire e Lucio; a minhairm, Gabriela; aos meus avs, Maria e Ildefonso e aos meus tios, Vicelma e Edio,

por todo apoio, amor e incentivo durante cada desafio.

Agradecimentos

Agradeo...A Deus, por minha vida e por me dar sabedoria e perseverana para enfrentar todos

os desafios e sempre ter foras para persistir no meu crescimento independente dosempecilhos encontrados.

Aos meus pais Rosemeire e Lucio pela minha educao, pela dedicao, apoio, con-fiana, carinho e amor em todos os momentos.

minha sempre irmzinha Gabriela que me motiva a ser sempre melhor do quesou, para ser sempre o seu exemplo favorito.

Aos meus avs Maria Izabel e Ildefonso pelo amparo e amor incondicionais emtodos os momentos.

Aos meus tios e padrinhos Vicelma e Edio pela confiana no meu potencial e porserem sempre meus exemplos.

Ao meu noivo Luciano, com quem sempre posso contar verdadeiramente, por terme apoiado tanto durante este projeto, principalmente emocionalmente. Voc me deumuita fora, tranquilidade, suporte, paz, alegria e amor. Te amo.

Aos meus colegas e amigos que fizeram parte dessa fase da minha vida, que diretae indiretamente contriburam nesse objetivo da minha vida profissional.

Aos professores e funcionrios do PPGCO-UFU, que so responsveis pela manu-teno e crescimento do curso, em especial ao secretrio da PPGCO Erisvaldo que estsempre muito prximo aos alunos e de prontido para nos auxiliar.

CAPES e ao CNPq pela ajuda financeira durante 12 meses desse projeto.

Professora Dr. Sandra pelo apoio no meu ingresso no mestrado, por me apre-sentar uma das reas que mais me interessa no mbito da computao e pelo exemplode dedicao absoluta a profisso.

Em especial, minha orientadora Professora Dr. Maria Camila pelo apoio, pro-fissionalismo, tranquilidade e orientao em todos os momentos da realizao destetrabalho. Acredito que a profisso de professor deve ser respeitada e glorificada, porser o profissional responsvel pelo incentivo e divulgao do conhecimento na socie-dade, dessa forma muito obrigada por toda pacincia e tempo dedicado em me ajudarnesse projeto e no meu crescimento profissional.

Eu Acredito, que s vezes so as pessoas que ningum espera nada que fazem as coisas queningum consegue imaginar.

(Alan Turing)

Resumo

Com o crescente aumento da quantidade de dados armazenados, a rea de mine-rao de dados tornou-se imprescindvel para que seja possvel manipular e extrairconhecimento a partir desses dados. Grande parte dos trabalhos nessa rea focamem encontrar padro nos dados, porm os dados fora do padro (anomalias) tambmpodem agregar muito no conhecimento do conjunto de dados em estudo. O estudo, odesenvolvimento e o aprimoramento de tcnicas de deteco de outliers so objetivosimportantes e tm se mostrado til em diversos cenrios, como: deteco de fraudes,deteco de intruso e monitoramento de condies mdicas entre outros. O trabalhoapresentado aqui descreve um novo mtodo para deteco semissupervisionada de ou-tliers em dados com alta dimensionalidade. Os experimentos realizados com diversosconjuntos de dados reais indicam a superioridade do mtodo proposto em relao aosmtodos da literatura selecionados como linha de base.

Palavras-chave: Outliers. Deteco semissupervisionada de Outliers. Anlise de da-dos em alta dimenso. Hubness. Minerao de dados. Aprendizado de Mquina.Semissuperviso.

Abstract

With the increase in the amount of data stored, the area of data mining has becomeessential for it to be possible to manipulate and extract knowledge from these data.Much of the work in this area focuses on finding patterns in the data, but non-standarddata (anomalies) can also add much to the knowledge of the data set under study.The study, development and enhancement of outliers detection techniques are impor-tant objectives and have proven useful in several scenarios, such as: fraud detection,intrusion detection and monitoring of medical conditions, among others. The paperpresented here describes a novel method for semi-supervised detection of outliers inhigh dimensional data. Experiments with several real datasets indicate the superio-rity of the proposed method in relation to the literature methods selected as the baseline.

Keywords: Outliers. Semi-supervised detection of outliers. Data mining. High-dimensional Data Analysis. Hubness.

Lista de ilustraes

Figura 1 Exemplos de Deteco de Padres e Candidatos a Outliers. Os outliersso identificados pela seta em (a), (b) e (c), para (a) o padro est nadisposio das amostras, (b) o padro est relacionado a alternanciaencontrada de acordo com a forma das amostras e em (c) o padroesta associado a forma dos elemntos. Porm, em (d) no possvelidentificar um padro e consequentemente a identificao de outlierstorna-se impraticvel. . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Figura 2 Etapas da abordagem proposta em (DANESHPAZHOUH; SAMI,2015). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Figura 3 Etapas da abordagem proposta em (DUONG; HAI, 2016). . . . . . . 35Figura 4 Etapas da abordagem proposta em (DANESHPAZHOUH; SAMI,

2013). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Figura 5 O outlier pode ser perdido na maioria dos subespaos escolhidos

aleatoriamente em casos com alta dimensionalidade (adaptado de(AGGARWAL, 2013)).Neste caso, as instncias A e B mudam declassificao a partir das perspectivas (a), (b), (c) e (d). . . . . . . . . . 38

Figura 6 Boxplot e suas informaes adaptada de (OTT; LONGNECKER, 2010) 46Figura 7 Fluxograma do processo de deteco semissupervisionada de outliers. 52Figura 8 Representao da regio de borda, aproximao inferior e superior

adaptada de [(PETERS, 2006)] . . . . . . . . . . . . . . . . . . . . . . . 57Figura 9 Representao do grfico da preciso em relao a revocao . . . . . 65Figura 10 Representao do grfico da preciso em relao a variao da vizi-

nhana k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66Figura 11 Representao do grfico da preciso em relao a revocao . . . . . 66Figura 12 Representao do boxplot da distribuio dos dados em anlise . . . 68

Lista de tabelas

Tabela 1 Comparao entre os trabalhos correlatos a proposta de trabalho. . . 43Tabela 2 Relao entre Outliers e Inliers encontrados comparado com os reais

categorizados na base em estudo . . . . . . . . . . . . . . . . . . . . . 44Tabela 3 Conjuntos de dados considerados nos experimentos. . . . . . . . . . 63Tabela 4 Conjunto de dados Wisconsin breast cancer modificado. . . . . . . . . . 64Tabela 5 Resultados dos experimentos, considerando a AUC. Os valores su-

blinhados destacam os melhores desempenhos. . . . . . . . . . . . . 67Tabela 6 Resultados da acurcia para diferentes quantidades de amostras po-

sitivas como entrada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Lista de siglas

ABOD Angle-Based Outlier Detection

FRSSOD Fuzzy Rough Semi-Supervised Outlier Detection

SOUTH-N Semi-supervised OUTlier detection based on Hubness Neighborhood

LOF Local Outlier Factor

SSODPU Semi-Supervised Outlier Detection with Positive and Unlabeled Data

Lista de smbolos

X = {x1; ...; xn} Conjunto de dadosk Vizinhana para clculo dos K vizinhos mais prximos

Nk(x) Pontuao hubness da instncia x considerando a vizinhana K

IC Intervalo de Confiana

Sumrio

1 INTRODUO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251.2 Organizao da dissertao . . . . . . . . . . . . . . . . . . . . . . . . 26

2 CONCEITOS FUNDAMENTAIS E TRABALHOS CORRELATOS . 272.1 Deteco de Outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.2 Mtodos de Deteco de Outliers . . . . . . . . . . . . . . . . . . . . . 302.2.1 Abordagem Supervisionada . . . . . . . . . . . . . . . . . . . . . .