BRUNO LAMBERTUCCI ARAÚJO ALBERTO
ABORDAGENS DE PRÉ-PROCESSAMENTO DE DADOS
EM PROBLEMAS DE CLASSIFICAÇÃO COM CLASSES
DESBALANCEADAS
Dissertação apresentada ao Curso de
Mestrado em Modelagem Matemática e
Computacional do Centro Federal de
Educação Tecnológica de Minas Gerais,
como requisito parcial à obtenção do título
de Mestre em Modelagem Matemática e
Computacional.
Área de concentração:
Sistemas Inteligentes
Orientador:
Prof. Dr. Paulo Eduardo Maciel de Almeida
Centro Federal de Educação Tecnológica de Minas Gerais
MESTRADO EM MODELAGEM MATEMÁTICA E COMPUTACIONAL
CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS
DIRETORIA DE PESQUISA E PÓS-GRADUAÇÃO
Belo Horizonte – MG
agosto de 2012
1 / 101
Folha de aprovação do projeto. Esta folha será fornecida
pelo Programa de Pós-Graduação e deverá substituir esta.
2 / 101
Resumo
Conjuntos de dados conhecidos e bem condicionados, bem como aqueles provenientes
de bases de dados reais, apresentam diversos problemas de representatividade. Grande
quantidade de ruído e inconsistências, excesso de valores desconhecidos e classes
desbalanceadas, ou seja, uma grande desproporção entre as distribuições das classes são
exemplos desses problemas. Se estes dados forem identificados e tratados antes de
serem fornecidos a um algoritmo de classificação, essa tarefa pode se tornar mais
efetiva. A identificação e tratamento preliminar desses dados antes que sejam fornecidos
a um algoritmo de classificação são conhecidos na literatura como uma fase de préprocessamento de dados. Sabe-se que esta é muito extensa e envolve a identificação e
tratamento de diversos tipos de problemas que podem existir em uma base de dados. E
apenas uma quantidade limitada de trabalhos encontrados na literatura tem-se
preocupado com as causas de problemas relacionados ao desbalanceamento de classes
em problemas de classificação. Nesse trabalho, uma análise formal e experimental sobre
a natureza do problema de desbalanceamento de classes é proposta com base na teoria
de Aprendizado de Máquina e Decisão Bayesiana. Seguindo uma abordagem de préprocessamento de dados, foram investigados e aplicados métodos de reamostragem de
dados no espaço de entrada, que incluem sobreamostragem da classe minoritária,
subamostragem da classe majoritária e a combinação de ambas as técnicas para
melhorar os resultados de classificação e assim obter taxas de acerto elevadas,
principalmente em relação à classe minoritária. Testes estatísticos também foram
aplicados aos resultados experimentais obtidos com dados reais e sintéticos para mostrar
a eficiência dos métodos investigados. Como resultado do trabalho, contribuições foram
dadas para provar, entre elas, que Redes Neurais Artificiais induzidas por determinados
cojuntos de treinamento desbalanceados e sobrepostos tendem a produzir classificadores
que favorecem a classe com maior probabilidade de ocorrência.
Palavras-chave: aprendizado de máquina, classificação de padrões, pré-processamento
de dados, desbalanceamento de classes.
3 / 101
Abstract
Well-conditioned and known data sets as well as artificial and real databases present
several representativeness problems. Lots of noise and inconsistencies, excessive
missing data and unbalanced classes, i.e. a large disparity between the classes
distributions are examples of these problems. If these problems are identified and
addressed before the data are supplied to a classification algorithm, the classification
task can be made more effective. Identification and treatment of these preliminary data
before it is delivered to a classification algorithm is known in literature as a preprocessing of data. It is known that this phase is very extensive and involves the
identification and treatment of various types of problems that may manifest in the
data. And only a limited amount of studies in the literature has been concerned with the
causes of problems related to class imbalance in classification problems. In this work, a
experimental and formal analysis of the nature of the problem of class imbalance is
proposed based on the theory of machine learning. Following an approach to preprocessing data, methods have been investigated and used for resampling the data in the
input space, including oversampling of the class minority and majority class of
subsampling combination of both techniques to improve the classification results and
thus obtain high hit rates, especially in relation to the minority class. Statistical tests
were applied to experimental results obtained with artificial and real data to illustrate
the efficiency of the mechanisms investigated. As a result of the work, contributions
were made to prove, through the approaches investigated and proposed, for example,
that artificial neural networks induced by unbalanced training sets overlap and tend to
produce classifiers that favor the class with highest probability
Keywords: machine learning, pattern recognition, data preprocessing, class imbalance.
4 / 101
Lista de Figuras
Figura 1 - Hierarquia do aprendizado indutivo
Figura 2 - Estrutura de uma rede MLP
Figura 3 - Exemplo de uma rede MLP
Figura 4 - Abordagem Embedded (Adaptado de Kohavi and John, 1997)
Figura 5 - Abordagem Filtro (Adaptado de John et al., 1994).
Figura 6 - Abordagem Wrapper (Adaptado de Kohavi & John, 1997).
Figura 7 - Nível alto entre as classes: (a) Com conhecimento a priori das distribuições e;
(b) Sem conhecimento a priori das distribuições.
Figura 8 - Pequena sobreposição entre as classes: (a) Com conhecimento a priori das
distribuições e; (b) Sem conhecimento a priori das distribuições.
Figura 9 - Curva ROC
Figura 10 - Grupos de exemplos descritos no método OSS
Figura 11 - Novo conjunto de dados após remoção de ligações TOMEK
Figura 12 - Visualização do processo de reamostragem do NBD
Figura 13 - Regra de decisão f (x) com espaço de entrada χ = ℜ 0 ∪ ℜ1
Figura 14 - Variação na proporção de exemplos positivos vs. AUC
Figura 15 - Variação no centro (média) da classe minoritária vs. AUC
Figura 16 - Proporção de exemplos da classe negativa vs. AUC: (a) e proporção vs.
Gmean (b), ambos para k = 0
Figura 17 - Proporção de exemplos da classe negativa vs. Gmean para k = 2
Figura 18 - Proporção de exemplos da classe negativa vs. AUC para k = 2
Figura 19 - Diagrama DC representando os resultados do teste post-hoc de Nemenyi
para a métrica AUC. Os grupos de algoritmos que não são significativamente diferentes
(para α = 0.05) encontram-se conectados por traços horizontais.
Figura 20 - Diagrama DC representando os resultados do teste post-hoc de Nemenyi
para a métrica Gmean. Os grupos de algoritmos que não são significativamente
diferentes (para α = 0.05) encontram-se conectados por traços horizontais.
Lista de Tabelas
Tabela 1 - Características das bases de dados A utilizadas
Tabela 2 - Características das bases de dados B utilizadas
Tabela 3 - Matriz de confusão para problema de duas classes
5 / 101
Tabela 4 - Comparação de AUC (%) obtidos pelos algoritmos MLP, MLP+SMOTE,
MLP+SMOTE+TOMEK e MLP+NBD sobre as 10 bases de dados. Em negrito, os
melhores valores encontrados.
Tabela 5 - Comparação de Gmean (%) obtidos pelos algoritmos MLP, MLP+SMOTE,
MLP+SMOTE+TOMEK e MLP+NDB sobre as 10 bases de dados. Em negrito, os
melhores valores encontrados.
Tabela 6 - Ranks médios obtidos pelos algoritmos MLP, MLP+SMOTE,
MLP+SMOTE+TOMEK e MLP+NDB para as métricas Gmean e AUC. As duas últimas
colunas da Tabela mostram os correspondentes valores das estatísticas FF e p-valor
referentes ao teste de Friedman.
Lista de abreviaturas
AM
Aprendizado de Máquina
AG
Algoritmos Genéticos
AUC
Area Under ROC Curve
CNL
Cleaning Nearest Rule
CNN
Condensed Nearest Neighbor Rule
DN
Detecção de Novidade
ENN
Edited Nearest Neighbor Rule
KNN
K-Nearest Neighbours
MLP
MultiLayer Perceptron
NBD
Detecção de Bordas de Novidade
OSS
One-Side Selection
RBF
Radial Basis Function
ROC
Relative Operating Characteristic
SE
Sensibilidade
ES
Especificidade
SMOTE
Synthetic Minority Oversampling Technique
TFN
Taxa de falso negativo
TFP
Taxa de falso positivo
TVN
Taxa de verdadeiro negativo
TVP
Taxa de verdadeiro positivo
WWE
Weighted Wilson’s Editing
6 / 101
Sumário
Resumo......................................................................................................................... 3
Abstract ........................................................................................................................ 4
Lista de Figuras ............................................................................................................ 5
Lista de Tabelas ............................................................................................................ 5
Lista de abreviaturas ..................................................................................................... 6
1.
2
Introdução ............................................................................................................. 9
1.1
Caracterização do problema ............................................................................ 9
1.2
Objetivos ........................................................................................................ 9
1.3
Metodologia ................................................................................................. 10
1.4
Principais contribuições ................................................................................ 19
1.5
Organização do trabalho ............................................................................... 20
Aprendizado de Máquina .................................................................................... 22
2.1
Considerações iniciais................................................................................... 22
2.2
Aprendizado de Máquina Indutivo por Exemplos.......................................... 22
2.3
Paradigmas de Aprendizado de Máquina Supervisionado .............................. 26
2.3.1
Paradigma Estatístico ............................................................................. 26
2.3.2
Paradigma Simbólico ............................................................................. 27
2.3.3
Paradigma Conexionista ........................................................................ 28
2.3.4
Paradigma Evolutivo.............................................................................. 31
2.3.5
Paradigma instance-based...................................................................... 32
2.4
3
4
Considerações finais ..................................................................................... 32
Pré-processamento de dados ................................................................................ 34
3.1
Considerações iniciais................................................................................... 34
3.2
Tarefas dependentes de domínio ................................................................... 34
3.3
Problemas típicos.......................................................................................... 35
3.4
Transformação de dados ............................................................................... 40
3.5
Considerações finais ..................................................................................... 41
Desbalanceamento de classes .............................................................................. 43
4.1
Considerações iniciais................................................................................... 43
4.2
Natureza do problema de classes desbalanceadas .......................................... 44
4.3
Métricas de avaliação.................................................................................... 47
4.4
Conjuntos desbalanceados e aprendizado sensível ao custo ........................... 53
7 / 101
4.5
4.5.1
OSS (One-Sided Selection) ..................................................................... 56
4.5.2
SMOTE (Synthetic Minority Oversampling Technique) .......................... 58
4.6
5
Considerações finais ..................................................................................... 61
Detecção de Bordas de Novidade (NBD) ............................................................. 62
5.1
Formulação do método NBD ........................................................................ 64
5.2
Experimentos ................................................................................................ 67
5.2.1
Experimento 1 ....................................................................................... 68
5.2.2
Experimento 2 ....................................................................................... 71
5.2.3
Experimento 3 ....................................................................................... 75
5.3
6
Métodos para balanceamento de classes ........................................................ 55
Considerações finais ..................................................................................... 79
Conclusões .......................................................................................................... 81
6.1
Principais contribuições ................................................................................ 81
6.2
Objetivos alcançados, hipóteses aceitas e rejeitadas ...................................... 82
6.3
Trabalhos futuros .......................................................................................... 83
Referências bibliográficas ........................................................................................... 87
8 / 101
1. Introdução
1.1
Caracterização do problema
Já faz muito tempo que a comunidade científica que pesquisa na área de
Aprendizado de Máquina (AM) tem utilizado repositórios de dados, tais como o
repositório da Universidade da Califórnia em Irvine (UCI) (Blake, C. L., and Merz, C.
J., 1998), para avaliar propostas de melhorias e novos sistemas de aprendizado. Embora
a utilidade desses repositórios seja reconhecida pelos pesquisadores da área (Pyle, D.,
1999; Hall, M., 2009), os repositórios de dados normalmente apresentam dados
previamente manipulados, sem muitas das características originalmente encontradas
quando de suas construções.
No entanto, ao contrário dos conjuntos de dados provenientes destes
repositórios, bases de dados reais apresentam diversos problemas, tais como grande
quantidade de ruído e inconsistências, excesso de valores desconhecidos, conjunto de
dados com classes desbalanceadas, entre outros. Se estes problemas fossem
identificados e tratados antes dos dados serem fornecidos a um algoritmo de
classificação (Pyle, D., 1999; Hall, M., 2009), provavelmente a tarefa de classificação
seria mais bem sucedida.
Os sistemas de aprendizado têm uma necessidade urgente pela validação dos
métodos de tratamento de dados amplamente utilizados pela comunidade de AM (Pyle,
D. 1999) e, possivelmente, pelo desenvolvimento e avaliação de novos métodos. No
projeto de sistemas de aprendizado existe uma fase que tem como finalidade melhorar a
qualidade dos dados. Essa fase é conhecida como pré-processamento e seu objetivo
principal é a identificação e remoção de problemas presentes nos dados antes que os
métodos de classificação sejam aplicados. Pode-se também estar interessado em extrair
conhecimento a priori destes antes mesmos da construção de classificadores. Ou ainda,
pode-se estar interessado em alterar sua estrutura, por exemplo, por meio da alteração
de sua distribuição. As ações realizadas na fase de pré-processamento visam preparar os
dados para que a fase seguinte, geralmente a classificação, seja mais efetiva.
1.2
Objetivos
Este trabalho tem como objetivo geral fazer uma investigação sobre as causas e
efeitos do desbalanceamento de classes em conjuntos de dados de treinamento
9 / 101
utilizados em tarefas de classificação no contexto de AM. Sabe-se que a fase de préprocessamento de dados é muito extensa e envolve a identificação e tratamento de
diversos tipos de problemas que podem se manifestar nos dados, entre eles o
desbalanceamento de classes. Nesse trabalho, uma análise experimental e empírica
sobre a natureza deste problema é proposta com base na teoria de Aprendizado de
Máquina e Decisão Bayesiana (Hart, P. E., 1968).
Para alcançar esse objetivo geral, seguindo a abordagem proposta, foram
definidos os seguintes objetivos específicos:
1) Investigar na literatura os principais métodos de balanceamento de classes utilizados
em pré-processamento de conjuntos de dados anteriormente a tarefas de
classificação de padrões no contexto de AM;
2) Propor um novo método de reamostragem de dados no espaço de entrada, intitulado
NBD, que incluem sobreamostragem da classe minoritária, subamostragem da
classe majoritária e/ou a combinação de ambas as técnicas de forma a melhorar os
resultados da aplicação dos métodos de balanceamento de classes investigados na
literatura e utilizados neste trabalho. Melhorar os resultados da literatura significa
obter de taxas de acerto elevadas inclusive para a classe minoritária;
3) Realizar experimentos com bases de dados provenientes de repositórios clássicos da
literatura (Blake, C. L. and Merz, C. J., 1998) e também bases de dados de
problemas reais como forma de validar os métodos de balanceamento de classes
investigados na literatura e utilizados neste trabalho. Comparar esses resultados com
aquele alcançado pelo novo método de reamostragem proposto tendo em vista o
aumento da taxa de classificação correta da classe minoritária;
4) Realizar testes estatísticos junto aos resultados experimentais obtidos como forma
de validar a eficiência do novo método proposto;
5) Verificar, a partir dos métodos investigados e do novo método proposto, que Redes
Neurais Artificiais induzidas por determinados conjuntos de treinamento
desbalanceados tendem a produzir classificadores que favorecem a classe com maior
probabilidade de ocorrência.
1.3
Metodologia
O balanceamento de classes pode ser compreendido como uma readequação do
conjunto de treinamento através de mecanismos de reamostragem de dados no espaço
de entrada, que incluem sobreamostragem da classe minoritária, subamostragem da
10 / 101
classe majoritária ou a combinação de ambas as técnicas. A sobreamostragem é baseada
na replicação de exemplos preexistentes (sobreamostragem com substituição) ou na
geração de dados sintéticos. No primeiro caso, a seleção de exemplos a serem
replicados
pode
ser
aleatória
(sobreamostragem
aleatória)
ou
direcionada
(sobreamostragem informativa). Já a subamostragem envolve a eliminação de exemplos
da classe majoritária. Os exemplos a serem eliminados podem ser escolhidos
aleatoriamente (subamostragem aleatória) ou a partir de alguma informação a priori
(subamostragem
informativa).
sobreamostragem
possuírem
Apesar
o
mesmo
das
técnicas
objetivo,
elas
de
subamostragem
introduzem
e
diferentes
características ao novo conjunto de treinamento que podem algumas vezes dificultar o
aprendizado de sistemas de classificação de padrões.
Este trabalho partiu das seguintes hipóteses:
1. Conjuntos de treinamento balanceados melhoram simultaneamente as taxas de
acerto de classificação para ambas as classes.
2. Conjuntos de treinamento desbalanceados não são os únicos responsáveis pelo
baixo desempenho de classificadores de padrão, mas também o grau de
sobreposição entre as classes.
3. As distribuições das classes que ocorrem naturalmente, ou seja, sem qualquer
tipo de pré-processamento, são as melhores para o aprendizado.
4. Penalizações com base na proporção dos padrões no conjunto de treinamento
permitem obter modelos equilibrados (equidistantes das distribuições),
compensando o viés imposto pela classe majoritária.
Em relação à metodologia adotada, a pesquisa é caracterizada como uma
pesquisa exploratória, pois tem a finalidade de avaliar quais teorias ou conceitos
existentes podem ser aplicados a um determinado problema ou se novas teorias e
conceitos devem ser desenvolvidos ou aprimorados.
Quanto aos procedimentos adotados, a pesquisa é definida, em grande parte,
como experimental e empírica, sendo realizada em ambientes de simulação por meio do
Matlab 8.10.0 Software (Matlab, 2008) e WEKA Data Mining Software (Hall, M. et al.,
2009) visando caracterizar o comportamento de cada método de balanceamento
investigado.
Inicialmente neste trabalho, são investigados os principais conceitos a respeito
de aprendizado de máquina indutivo, aprendizado supervisionado, não supervisionado e
semi-supervisionado. Os principais paradigmas de aprendizado são também
11 / 101
investigados, tais como o Estatístico, Simbólico, Conexionista, Evolutivo e Instancebased. Em seguida, também com base na literatura, é explicada a diferença entre tarefas
de classificação fracamente e fortemente dependentes de domínio. São discutidos
também os problemas típicos encontrados em conjunto de dados, introduzindo o
problema de desbalanceamento de classes.
Em relação ao problema de desbalanceamento de classes, este mereceu destaque
em uma seção exclusiva para discussão do tema. Foram tratadas nessa seção alguns dos
métodos de pré-processamento de dados mais utilizados para solucionar o problema de
aprender com conjuntos de dados com classes desbalanceadas. A natureza do problema
de classes desbalanceadas é, portanto analisada com base nas teorias de Decisão
Bayesiana e Aprendizado de Máquina e são apresentadas as principais métricas da
literatura para análise do desempenho de classificadores, tendo como foco as métricas:
área sob a curva ROC (Relative Operating Characteristic) conhecida como AUC (Area
Under ROC Curve) e Gmean (Kubat et al., 1998).
Em seguida, a partir da análise dos principais métodos na literatura para
balanceamento de classes, é formulado então um novo método para balanceamento de
classes com alta sobreposição intitulado Detecção de Bordas de Novidade (NBD). O
NBD melhora os resultados de classificação da literatura investigada em termos de taxas
de acerto, principalmente para a classe minoritária. O método é baseado em
subamostragem e sobreamostragem guiada pela informação da densidade em torno dos
exemplos de treinamento inter-classe e intra-classe. O NBD utiliza esta informação de
densidade para identificar principalmentes casos raros (novidades) em regiões de menor
densidade e também exemplos que pertencem à região próxima à superfície de
separação.
Em seguida, o método NBD proposto é testado através de três experimentos
computacionais, os quais têm o propósito de validar ou descartar as hipóteses
levantadas. Os três experimentos tem como características:
1) Conjuntos de dados sintéticos gerados a partir de duas distribuições gaussianas
unidimensionais e a representação do modelo de classificação ótimo de Bayes
para uma tarefa de classificação binária. Esse experimento buscou esclarecer os
motivos pelas quais nem sempre o desbalanceamento de classe é o responsável pela
piora no desempenho de algoritmos de aprendizagem utilizados para tarefas de
classificação;
12 / 101
2) Comportamento de métodos da literatura que promovem o balanceamento de
dados com sobreposição entre as classes em termos das métricas de avaliação
de desempenho AUC e Gmean. Este experimento buscou abordar o
desbalanceamento em classes altamente sobrepostas e os resultados da classificação
utilizando duas métricas bastante utilizadas na literatura;
3) Eficiência das técnicas investigadas e do algoritmo que implementa o método
NBD proposto. É proposto um estudo experimental com onze bases de dados, um
classificador base e dois métodos da literatura para confrontar com o algoritmo
NBD. Testes estatísticos acompanham a análise dos resultados de classificação após
a utilização dos métodos de balanceamento.
Para a realização do 1º experimento, conforme detalhado ao longo do texto desta
dissertação, foram gerados, a partir de duas distribuições gaussianas unidimensionais
com média
µ , desvio padrão
σ , quatro conjuntos de dados sintéticos
C : ℜ n → {1,2,3,4} e a representação de um modelo de classificação ótimo de Bayes.
Cada conjunto é composto portanto de duas classes, cada qual com um atributo e dois
parâmetros de ajuste: a proporção de exemplos de cada uma delas e a distância entre os
centros das classes. A proporção de exemplos em cada classe nos permite analisar o
desempenho de algoritmos de aprendizado em situações com diferentes graus de
desbalanceamento entre as classes. Por convenção, os índices 0 e 1 representam,
respectivamente, as classes majoritária (negativa) e minoritária (positiva). No primeiro
conjunto, o centro (média) de cada gaussiana é o mesmo para ambas as classes e iniciase com o valor igual a 10 ( µ1 = µ 2 = 10 ). Para os conjuntos seguintes, a distância entre
os centros de cada classe é incrementada em uma unidade até o máximo de 12
( µ1 = 10 → µ 2 = 22 ). Cada conjunto possui 100 exemplos, com 20 diferentes
proporções de casos em cada classe, variando entre 4,7% e 50% os exemplos
pertencentes à classe positiva. A escolha pela distribuição gaussiana unidimensional
representar apenas um atributo e quatro conjuntos foi devido à facilidade de
compreensão pelo leitor em relação ao problema e também devido à simplificação dos
cálculos, aproximações estatísticas e análises gráficas sem perda de informação devido à
essa generalização. Funções gaussianas, além de serem utilizadas como aproximação de
várias outras distribuições estatísticas, simplificam o cálculo da AUC para o modelo
ótimo de Bayes. Para o cálculo da AUC, foi utilizado o algoritmo descrito em Fawcett
(Fawcett, T., 2006), que soma sucessivas áreas de trapézios formados na construção da
13 / 101
curva ROC. Para executar o experimento utilizou-se um modelo de classificação
bayesiano assumindo um perfeito conhecimento com respeito às distribuições de
probabilidade. Nesse caso, portanto, um modelo de classificação ótimo de Bayes. Os
resultados foram avaliados utilizando-se a AUC.
Uma vez investigada empiricamente no 1º experimento a hipótese de que a
sobreposição de exemplos entre as classes é um fator que potencializa o problema de
classes desbalanceadas, é então investigado no 2º experimento o comportamento de
métodos que promovem o balanceamento de dados com sobreposição entre as classes.
Como os conjuntos cujas distâncias entre os centróides maiores do que 3 não
apresentaram diferenças significativas em termos da AUC e Gmean, a investigação foi
concentrada em centróides com distâncias menores do que 2 e em intervalos menores,
focando portanto classes altamente desbalanceadas e sobrepostas. Foram construídos
cinco novos conjuntos de dados através do mesmo processo descrito no experimento
anterior. Tais conjuntos encontram-se listados na Tabela 1 juntamente com suas
características: número de exemplos positivos ( N1 ), número de exemplos negativos
( N 2 ) e razão de desbalanceamento N1 / ( N1 + N 2 ) . Os métodos de balanceamento
utilizados foram: SMOTE (Chawla et al., 2002), sobreamostragem aleatória e
subamostragem aleatória que foram executados sobre essas bases até que a proporção
final de exemplos entre as classes se equivalesse.
Tabela 1 – Características das bases de dados utilizadas no 1º e 2º experimentos
#
Base de
dados
N1
N2
N1
( N1 + N 2 )
1
2
3
4
5
6
7
8
9
BD500
BD333
BD250
BD200
BD167
BD111
BD059
BD039
BD015
100
100
100
100
100
100
100
100
100
100
200
300
400
500
800
1600
2500
6400
0.5000
0.3333
0.2500
0.2000
0.1667
0.1111
0.0588
0.0386
0.0154
Em particular nesse experimento foram sugeridas novas distâncias entre os
centroides das classes: k = 0 ; k = 0.5 ; k = 1 ; k = 2 . Como o interesse voltou-se para a
investigação de conjuntos de dados altamente desbalanceados e com sobreposição entre
14 / 101
as classes, foram restringidas as análises para os nove seguintes conjuntos com 50%,
33.33%, 25%, 20%, 16,67%, 11,11%, 5,88%, 3,85% e 1,54% de exemplos da classe
minoritária, comparando-os com conjunto de dados naturalmente balanceados. A
proporção de 50% utilizada teve o caráter apenas de ser uma referência para as demais,
visto que era esperada uma AUC oscilando em torno de 50%. A mesma não foi,
portanto representada graficamente. Esses conjuntos tiveram exemplos removidos ou
acrescentados, conforme cada um dos três métodos utilizados, até que a proporção de
exemplos entre as classes fosse igualada. Outra particularidade do experimento foi a
utilização de uma rede MultiLayer Perceptron (MLP) como classificador base e não
mais o classificador ótimo de Bayes devido ao objetivo principal da pesquisa se
concentrar neste tipo de classificador largamente utilizado na literatura (Alberto, B. L.
A.; Almeida, P. E. M., 2009), (Alberto, B. L. A., 2007), (Alberto et al., 2011) com bases
de dados reais similares a este trabalho.
Os dados de treinamento foram gerados a partir de distribuições gaussianas
unimodais com variâncias unitárias. A rede utilizada como classificador base possui
topologia 1 : h : 1 e função de ativação do tipo tangente hiperbólica em todas as
unidades. Todos os métodos de balanceamento foram associados às MLPs baseados na
minimização do erro global. A MLP possui regra de aprendizado baseada no gradiente
com termo de momentum, com parâmetros ρ = 0.2 e η = 0.3 . Na execução de um
algoritmo particular sobre um dado caso de treinamento/teste, o procedimento de busca
em grid com stratified 10-fold cross validation (Van Gestel, T. et al., 2004) foi
empregado (sobre o subconjunto de treinamento) para obtenção do número ótimo de
neurônios h∗ na camada escondida da rede. O conjunto inicial de parâmetros candidatos
foi ho = {1 : 3 : 13} . A busca em grid contou com apenas um refinamento ao redor do
parâmetro ótimo h0∗ selecionado na iteração 0. O conjunto de parâmetros candidatos na
iteração 1 foi h1 = {h0∗ − 2 : 1 : h0∗ + 2} . Para os algoritmos SMOTE, sobreamostragem
aleatória e subamostragem aleatória a busca em grid foi aplicada após os dados de
treinamento
terem
sido
modificados
por
suas
respectivas
estratégias
de
sobreamostragem e subamostragem. Para o SMOTE, o número de vizinhos mais
próximos foi configurado como 5 (Batista, G. E. A. P. A., et al., 2004).
Com intuito de se obter representatividade nos resultados dos algoritmos
testados, foram geradas 10 permutações aleatórias para cada base de dados. Cada
permutação foi então dividida em subconjuntos de treinamento (2/3) e teste (1/3) de
15 / 101
uma maneira estratificada, garantindo em cada uma delas a mesma razão de
desbalanceamento da base de dados original. Com esse procedimento, foram produzidos
10 diferentes casos de treinamento/teste para cada base de dados. Dessa forma, para um
algoritmo particular, o desempenho médio e σ foram calculados sobre 10 execuções
(treinamento/teste), com as métricas de desempenho AUC e Gmean escolhidas.
Por fim, no 3º experimento, a eficiência das técnicas investigadas no
experimento anterior e a do método NBD proposto, bem como dos algoritmos que os
implementam neste trabalho, é colocado à prova em um estudo experimental realizado
sobre bases de dados sintéticas e reais com diferentes razões de desbalanceamento e
sobreposição, à exceção dos métodos de subamostragem aleatória e sobreamostragem
aleatória que deram lugar ao método SMOTE+TOMEK LINKS (Batista, G. E. A. P. A.,
et al.,2004) com intuito de testar outros métodos utilizados na literatura. Os
desempenhos foram comparados e testes estatísticos de significância foram empregados
para a análise dos resultados, seguidos de uma discussão sobre as propriedades dos
algoritmos utilizados nos experimentos. Foram selecionadas, ao todo, oito bases de
dados do repositório UCI (Blake, C. L. and Merz, C. J. 1998) e duas bases reais com
diferentes graus de desbalanceamento, juntamente com suas características conforme
apresentado na Tabela 2: número de atributos, número de exemplos positivos, número
de exemplos negativos, número total de atributos e percentual de exemplos da classe
minoritária.
#total de
exemplos
%Classe
minoritária
Pima
Breast Cancer
SPECTF Heart
Glass
Image
Car
Yeast
Abalone
Energia
Meteorologia
#exemplos
negativos
1
2
3
4
5
6
7
8
9
10
Base de dados
#exemplos
positivos
#
#atributos
Tabela 2 – Características das bases de dados utilizadas no 3º experimento
8
33
44
10
24
6
8
8
120
16
268
47
55
29
238
69
51
32
900
15
500
151
212
185
1762
1659
1433
4145
124233
12340
768
198
267
214
2000
1728
1484
4177
125133
12370
34,90%
23,70%
20,60%
13,60%
11,90%
4,00%
3,40%
0,80%
0,72%
0,12%
16 / 101
1) Pima Diabetes (Pima). Pacientes diabéticos do sexo feminino com pelo menos,
21 anos e com herança genética da tribo indígena Pima. A tarefa é tentar
predizer mulheres que têm tendências hereditárias ao Diabetes.
2) Breast Cancer. Acompanhamento de casos de câncer de mama. Pacientes
consecutivamente atendidos desde 1984. Incluem somente os casos que exibem
o câncer de mama invasivo e sem evidência de metástases no momento do
diagnóstico.
3) SPECTF Heart. Diagnóstico de doença cardíaca a partir da análise de imagens
obtidas pelo método Single Proton Emission Computed Tomography (SPECT).
Cada um dos pacientes é classificado em duas categorias.
4) Glass. Estudo da classificação de tipos de vidro motivado por investigações
criminais. Na cena do crime, o vidro pode ser usado como prova, se ele for
identificado corretamente.
5) Image Segmentation (Image). Banco de dados de sete imagens ao ar livre. As
imagens foram segmentadas a mão para criar uma classificação para cada pixel.
6) Car. Exemplos de informações coletadas por entrevistas feitas com motoristas
sobre alguns requisitos fundamentais na avaliação de um carro: valor de compra,
manutenção, número de portas, etc.
7) Yeast. Base de dados para previsão de localização de proteína de fermentos.
8) Abalone. Informações diversas sobre vários exemplos de abalone (um molusco)
nas quais se tenta predizer a sua idade, o que é um trabalho demorado feito por
análise de microscópio.
9) Inspeção de energia (Energia). Informações a respeito de consumidores de
energia elétrica, tais como: (i) consumo mensal de energia em kWh/mês; (ii)
resultados de inspeções executadas em consumidores com suspeita de
irregularidades e fraudes no consumo de energia e; (iii) solicitações de serviços
por estes consumidores junto a uma distribuidora de energia elétrica brasileira
(Alberto, B. L. A.; Almeida, P. E. M., 2009), (Alberto, B. L. A., 2007), (Alberto,
B. L. A. et al., 2011). Este conjunto de dados representa duas classes distintas:
unidades consumidoras de energia elétrica com ou sem irregularidades e fraudes
no consumo de energia.
10) Meteorologia. Histórico de dados de uma estação meteorológica localizada na
cidade de Belo Horizonte, incluindo medições de 15 em 15 minutos a respeito
da temperatura, velocidade do vento, umidade, pressão atmosférica e radiação
17 / 101
solar no raio de influência, na região da Pampulha, da estação meteorológica em
questão. Esses dados são utilizados para predizer a ocorrência ou não de eventos
climáticos extremos.
Diferentemente das bases sintéticas (Blake, C. L. and Merz, C. J. 1998) acima
encontradas na literatura, as bases 9 e 10 dizem respeito a dados reais coletados e
armazenados em seu estado natural e portanto sem qualquer pré-processamento.
Na base de dados Energia, por questões legais e de uso para pesquisa científica,
o nome da distribuidora foi omitido, bem como as informações que identificam as
unidades consumidoras em análise. Já a base de dados Meteorologia foi cedida para uso
científico e de pesquisa pelo Centro de Desenvolvimento em Tecnologia Nuclear
(CDTN), o qual possui uma estação meteorológica com 13 anos de dados
meteorológicos históricos da região da Pampulha.
Todas as bases de dados passaram pelos seguintes estágios de préprocessamento: atributos categóricos foram expandidos para os correspondentes vetores
binários e, em seguida, cada atributo normalizado para o intervalo [−1, 1]. Bases de
dados contendo c > 2 classes foram reduzidas à classificação binária usando um dos
procedimentos a seguir: (i) escolha de um dos rótulos para representar a classe positiva
(ou de interesse) e união dos demais rótulos para compor a classe negativa. Para o
algoritmo NBD os parâmetros min θ e max θ foram ajustados em 0.5 e k = 5 . Para
SMOTE e SMOTE+TOMEK LINKS, o número de vizinhos mais próximos foi
configurado como 5 (Batista et al., 2004)
Visando a obter representatividade nos resultados dos algoritmos testados, foram
geradas 10 permutações aleatórias para cada base de dados. Cada permutação foi então
dividida em subconjuntos de treinamento (2/3) e teste (1/3) de uma maneira
estratificada, garantindo em cada um deles a mesma razão de desbalanceamento da base
de dados original. Com esse procedimento, foram produzidos 10 diferentes casos de
treinamento/teste para cada base de dados. Dessa forma, para um algoritmo particular, o
desempenho médio e desvio-padrão foram calculados sobre 10 execuções (casos de
treinamento/teste), com métricas AUC e Gmean.
O objetivo geral do 3º experimento foi testar a eficiência do algoritmo NBD,
comparando-o com os métodos investigados na literatura que podem ser combinados
com redes MLP, ou seja, que podem usar MLP como classificador base. São eles:
SMOTE e SMOTE + TOMEK-LINKS (Batista et al., 2004). Além disso, uma rede MLP
pura (MLP), ou seja, sem qualquer estratégia para lidar com dados desbalanceados, foi
18 / 101
também testada dentro das mesmas condições. A topologia e parâmetros adotados para
a rede MLP foi a mesma da descrita no segundo experimento.
Por fim, para encerrar o trabalho, é aberta uma discussão a respeitos dos
resultados alcançados em relação aos objetivos ora traçados e as principais
contribuições efetuadas para o meio científico, tecnológico e para os grupos de pesquisa
do CEFET-MG. Os trabalhos futuros também são apresentados bem como uma
generalização do método NBD para outras aplicações e conjuntos de dados
desbalanceados.
1.4
Principais contribuições
Entre as principais contribuições deste trabalho está uma análise experimental,
empírica e formal sobre a natureza do problema de desbalanceamento de classes
seguindo uma abordagem de pré-processamento de dados com base na teoria de
Aprendizado de Máquina e Decisão Bayesiana (Hart, P. E., 1968). Esta análise é
corroborada por meio de experimentos computacionais com bases de dados sintéticas e
reais pelos quais são investigados, caracterizados e validados alguns dos mais recentes e
eficientes métodos de balanceamento de classes presentes na literatura em problemas de
classificação de padrões (Alberto, B. L. A., 2007).
Com intuito de confrontar os métodos da literatura investigados e melhorar seus
resultados em termos de taxas de acerto, principalmente para a classe minoritária, foi
proposto um novo método intitulado Detecção de Bordas de Novidade (NBD). Este
método é baseado em subamostragem e sobreamostragem guiada pela informação da
densidade em torno dos exemplos de treinamento inter-classe e intra-classe. O NBD
utiliza esta informação de densidade para identificar principalmente casos raros
(novidades) em regiões de menor densidade e também exemplos que pertencem à região
próxima à superfície de separação. O processo de eliminação e síntese de exemplos
dessas regiões melhora a distribuição dos conjuntos de treinamento para que um
classificador possa estimar uma melhor superfície de separação. Com isso, é possível
contribuir para a melhoria dos resultados de classificação com taxas de acerto elevadas,
principalmente em relação à classe minoritária. Testes estatísticos aplicados aos
resultados experimentais obtidos puderam mostrar a eficiência do NBD ao ser
confrontado com os métodos investigados na literatura.
19 / 101
Resultados
intermediários
deste
trabalho
encontram-se
publicados
nacionalmente em (Alberto, B. L. A.; Almeida, P. E. M.; Durães, R. L., 2008), (Alberto,
B. L. A. e Almeida, P. E. M., 2009) e (Alberto, B. L. A. et al., 2011).
Torna-se mais claro, a partir da caracterização formal e experimental
apresentada, que soluções como o método NBD para o problema de classes
desbalanceadas devem considerar critérios alternativos para modificações das
distribuições de probabilidade (a priori) a partir de suas estratégias de reamostragem de
dados. Essa observação ajuda a entender o sucesso empírico de alguns métodos da
abordagem de pré-processamento de dados.
1.5
Organização do trabalho
Esta dissertação está organizada da seguinte forma:
Seção 2: Aprendizado de Máquina
Nesta seção é feita uma investigação sobre o Aprendizado de Máquina com
ênfase no Aprendizado Indutivo por exemplos, incluindo conceitos de
aprendizado supervisionado, não supervisionado e semi supervisionado. São
descritos também os paradigmas de aprendizagem mais conhecidos na literatura.
Seção 3: Pré-processamento de dados
Nesta seção é realizado um estudo sobre os desafios que surgem na fase de préprocessamento de dados em Aprendizado de Máquina. Seleção de atributos,
tratamento de valores desconhecidos e desbalanceamento de classes são
problemas típicos resumidamente descritos nesta seção.
Seção 4: Desbalanceamento de classes
Na seção 4 é detalhado o problema de aprendizado com classes desbalanceadas.
São discutidos aspectos teóricos e experimentais sobre os principais métodos,
principalmente aqueles utilizados para classes com alto grau de sobreposição.
Seção 5: Detecção de Bordas de Novidade (NBD)
A seção 5 apresenta um novo método de balanceamento de classes proposto
neste trabalho, a Detecção de Bordas de Novidade (NBD). As subseções desta
seção apresentam os principais experimentos computacionais realizados. Foram
20 / 101
executados três experimentos com diferentes bases de dados e métodos
investigados da literatura, incluindo uma comparação com o método NBD.
Seção 6: Conclusões e trabalhos futuros
Na seção 6 são descritos as conclusões deste trabalho e as propostas de
continuidade na forma de trabalhos futuros.
21 / 101
2
Aprendizado de Máquina
2.1
Considerações iniciais
Aprendizado de Máquina é uma área de pesquisa em Inteligência Computacional
em que são estudadas técnicas que permitem ao computador adquirir “conhecimento” a
partir de dados de maneira automática (Mitchell, T. M., 1997), (Almeida, P. E. M.;
Meireles, M. R. G.; Simões, M. G., 2003). Em AM, um dos paradigmas de aprendizado
mais utilizados é o indutivo, no qual parte-se de exemplos para induzir conceitos gerais
a respeito de um dado contexto. Nesta seção são descritas várias dessas abordagens que
podem ser utilizadas pelos sistemas de aprendizado, entre elas o aprendizado por
indução, foco deste trabalho. O aprendizado indutivo permite obter novos
conhecimentos a partir de exemplos previamente observados. Entretanto, ele é um dos
mais desafiadores, pois o conhecimento gerado ultrapassa os limites das premissas, e
não existem garantias de que esse conhecimento seja verdadeiro.
Esta seção está organizada da seguinte forma: na seção 2.2 são apresentados os
principais conceitos a respeito de Aprendizado de Máquina Indutivo, aprendizado
supervisionado, não supervisionado e semi-supervisionado. Na seção 2.3 os principais
paradigmas de aprendizado são investigados, tais como o Estatístico, Simbólico,
Conexionista, Evolutivo e Instance-based. Por fim, na seção 2.5, as considerações
finais.
2.2
Aprendizado de Máquina Indutivo por Exemplos
Indução é a forma de inferência lógica que permite que conclusões gerais sejam
obtidas de exemplos particulares. Já o aprendizado indutivo é o processo de inferência
indutiva (Shaw, M. J. and Gentry, J. A., 1990) realizada sobre fatos, situações ou casos
observados, os quais são fornecidos ao aprendiz por um professor. Um tipo de
aprendizado indutivo é o Aprendizado Indutivo por Exemplos, cuja tarefa é induzir
descrições gerais de conceitos utilizando exemplos específicos desses conceitos
(Michalski, R. S. Carbonell and Mitchell, T. M., 1983). Uma definição do problema de
aprendizado de conceitos utilizando exemplos pode ser encontrada em Bratko, I. (1990):
Definição. Seja λ o conjunto universal dos objetos, isto é, todos os objetos que
o aprendiz pode encontrar. Não existe limite, a princípio, para a cardinalidade de λ .
Um conceito β pode ser formalizado como sendo um subconjunto de objetos em λ .
22 / 101
Assim β ⊂ λ e aprender um conceito β significa aprender a reconhecer objetos em
λ . Ou seja, uma vez que o conceito β é aprendido, para qualquer objeto x ∈ λ o
sistema é capaz de reconhecer se x ∈ β .
Pela definição é importante notar que o conceito aprendido deve ser útil não
apenas para reconhecer corretamente os exemplos utilizados para aprender o conceito
β , mas também para reconhecer corretamente se qualquer exemplo pertence ou não ao
conceito aprendido.
Em AM, o aprendiz é um sistema computacional frequentemente denotado por
sistema de aprendizado, algoritmo de aprendizado, ou simplesmente indutor. Um
sistema de aprendizado é um sistema computacional que toma decisões baseado em
experiências acumuladas contidas em casos resolvidos com sucesso (Weiss, S. M. and
Kulikowski, C. A., 1991).
O aprendizado indutivo por exemplos pode ser dividido em aprendizado
supervisionado e não supervisionado (Russel, S. and Norvig, P., 2003). No aprendizado
supervisionado é fornecido ao sistema de aprendizado um conjunto de exemplos, sendo
E = {E1 , E 2 ,..., E N } e cada exemplo E i ∈ E possui um rótulo associado. Esse rótulo
define a qual classe o exemplo pertence. Pode-se dizer de uma maneira mais formal que
cada exemplo é representado pela Equação 1:
r
(1)
Ei = ( xi , yi )
r
Na qual xi é um vetor de valores que representam as características, ou atributos, do
exemplo Ei e; yi é o valor da classe desse exemplo. O objetivo do aprendizado
r
supervisionado é induzir um mapeamento geral dos vetores x para valores y . Portanto,
o sistema de aprendizado deve construir um modelo y = f ( x) de uma função
desconhecida f também chamada de função conceito que permite predizer valores y
para exemplos previamente não vistos.
Entretanto, o número de exemplos utilizados para a criação do modelo não é, na
maioria dos casos, suficiente para caracterizar completamente essa função f . Na
realidade, os sistemas de aprendizado são capazes de induzir uma função h que
r
r
aproxima f , ou seja, h( x) ≈ f ( x) . Nesse caso, h é chamada de hipótese sobre a
função conceito f .
23 / 101
Em aprendizado supervisionado, o atributo classe y pode ser um atributo
qualitativo que assume um conjunto de valores discretos C = {C1 , C2 ,...,C N } ou um
atributo quantitativo que assume um conjunto de valores reais. No primeiro caso,
r
assumindo que os valores x correspondem a pontos em um espaço M-dimensional ℜ M ,
o objetivo do aprendizado é encontrar uma função h que aproxima a função
f : ℜ M → C . Nesse caso, a hipótese h é denominada classificador, e a tarefa de
aprendizado é denominada classificação. No segundo caso, o atributo classe é
quantitativo, o qual pode assumir um conjunto de valores reais. O objetivo do
aprendizado é encontrar uma função h que aproxima a função f : ℜ M → ℜ . Neste
caso, a hipótese h é denominada regressor, e a tarefa de aprendizado é denominada
regressão.
No aprendizado não supervisionado é fornecido ao sistema de aprendizado um
r
conjunto de exemplos E , no qual cada exemplo consiste somente de valores x , não
incluindo a informação sobre a classe y . O objetivo é construir um modelo que procura
por regularidades nos exemplos, formando agrupamentos ou clusters de exemplos com
características similares. A abordagem utilizada pelo aprendizado não supervisionado,
especificamente no processo de clustering, sofre de algumas limitações significantes.
Diferentemente do que ocorre com o aprendizado supervisionado, os resultados de um
processo de clustering não fornecem uma explicação ou descrição, mas apenas clusters.
Porém, muitas vezes, não se está interessado apenas nos clusters, mas também em
alguma explicação ou descrição conceitual dos exemplos que foram agrupados em um
mesmo cluster, o que não é uma tarefa fácil. Dessa forma, existe a preferência, sempre
que exista a possibilidade, de se escolher aprendizado supervisionado. Entretanto, em
muitos casos do mundo real, o número de exemplos rotulados é muito pequeno, quando
não inexistente, e modelos preditivos induzidos a partir de um pequeno conjunto de
exemplos rotulados apresentam, geralmente, baixa precisão.
O aprendizado semi-supervisionado, uma área de pesquisa em AM, consiste em
utilizar algoritmos que aprendem a partir de exemplos rotulados e não rotulados. A
grande motivação para esse tipo de aprendizado se dá pelo fato de exemplos não
rotulados existirem em abundância e exemplos rotulados serem geralmente escassos.
Além disso, a rotulação de exemplos pode ser custosa, como nos casos de identificação
de fraudes, indexação de vídeo, categorização de textos e diagnósticos médicos, entre
outros. Uma outra motivação é que classificadores induzidos exclusivamente a partir de
24 / 101
um pequeno conjunto de exemplos rotulados, geralmente, não apresentam boa precisão.
A ideia do aprendizado semi-supervisionado é então utilizar os poucos exemplos
rotulados para se obter informações sobre o problema e utilizá-las para guiar o processo
de aprendizado a partir dos exemplos não rotulados (Bruce, R., 2001).
Aprendizado semi-supervisionado pode ser utilizado tanto em tarefas de
classificação como em tarefas de clustering. Em uma classificação semi-supervisionada,
a ideia é rotular, com uma certa margem de segurança, alguns dos exemplos no conjunto
de exemplos não rotulados, os quais são posteriormente utilizados durante a fase de
treinamento do classificador, frequentemente resultando em uma classificação mais
precisa (Blum, A. L. and Mitchell, T. M., 1998). Já em clustering semi-supervisionado,
os exemplos rotulados são utilizados no processo de formação dos clusters, servindo
geralmente como um conhecimento preliminar e resultando em melhores clusters.
Vários algoritmos de clustering semi-supervisionados têm sido propostos. A
maioria deles tem como base algum algoritmo existente na literatura, o qual é
modificado para tratar exemplos rotulados e não rotulados. Nesses algoritmos, os
exemplos rotulados são utilizados para guiar o processo de formação dos clusters, como
nos algoritmos COP–k-means (Wagstaff, R. et al., 2001), SEEDED–k-means e
CONSTRAINED–k-means (Basu, S. et al., 2002). A Figura 1 apresenta a hierarquia do
aprendizado indutivo.
Aprendizado
Indutivo
Aprendizado
Supervisionado
Classificação
Aprendizado NãoSupervisionado
Aprendizado SemiSupervisionado
Regressão
Figura 1 – Hierarquia do aprendizado indutivo (Adaptado de Haykin, S., 1998)
O foco deste trabalho é o aprendizado supervisionado. Uma ênfase maior será
dada aos problemas de classificação, embora alguns métodos propostos possam também
ser utilizados para problemas de regressão.
25 / 101
2.3
Paradigmas de Aprendizado de Máquina Supervisionado
Em AM existem vários paradigmas capazes de aprender a partir de um conjunto
de dados ou exemplos. No caso de AM supervisionado, um requisito básico para todos
paradigmas é que o conceito a ser aprendido deve estar relacionado com casos
observados, ou seja, cada exemplo deve estar rotulado com a classe a qual pertence. A
seguir são apresentados os paradigmas mais conhecidos na literatura.
2.3.1 Paradigma Estatístico
Pesquisadores em estatística têm criado diversos métodos de classificação e
regressão, muitos deles semelhantes aos métodos empregados em AM. Destaca-se neste
caso o Aprendizado Bayesiano (Duda, R. O. et al., 2001) que utiliza um modelo
probabilístico baseado no conhecimento prévio do problema utilizando exemplos de
treinamento para determinar a probabilidade final de uma hipótese.
Como regra geral, técnicas estatísticas tendem a focar tarefas em que todos os
atributos têm valores contínuos ou ordinais. Frequentemente assumem que os valores de
atributos estão normalmente distribuídos, e então usam os dados fornecidos para
determinar média, variância e covariância da distribuição. Muitos deles também são
paramétricos, assumindo alguma forma de modelo ou distribuição, e então encontrando
valores apropriados para os parâmetros do modelo a partir de dados. Por exemplo, um
classificador linear assume que as classes podem ser expressas como combinação linear
dos valores dos atributos, e então procura uma combinação linear particular que forneça
a melhor aproximação sobre o conjunto de dados. Entretanto, a pressuposição feita a
respeito da forma de distribuição dos dados pode não se verificar, especialmente em
distribuições multimodais. Essa dificuldade pode ser superada com o uso de técnicas
não paramétricas, em que a estimação da função de densidade de probabilidade é feita
apenas com base nos exemplos do conjunto de treinamento. Entre elas, duas têm sido
utilizadas para problemas de classificação: a das janelas de Parzen e a dos k vizinhos
mais próximos. O modelo de mistura de Gaussianas (Duda, R. O. et al., 2001) é uma
extensão da técnica de janelas de Parzen (Parzen, E., 1962), que consiste em uma
combinação linear de distribuições normais. Sua estratégia baseia-se na criação de
hipercubos de aresta hn centrados em cada um dos exemplos. A partir do número de
exemplos localizados no interior de cada hipercubo e de seu volume é possível calcular
a função de densidade de probabilidade. A largura da janela hn é o parâmetro que
26 / 101
determina o grau de generalização. Outra importante abordagem estatística não
paramétrica é a dos k vizinhos mais próximos (KNN, do inglês K Nearest Neighbors)
(Cover, T. M. and Hart, P. E., 1967). A principal diferença com relação às janelas de
Parzen está no fato de que KNN não utiliza uma largura de janela fixa hn . Em vez disso,
cada janela com centro em um exemplo cresce até o momento em que nela estiverem
contidos k exemplos. A classe de um novo exemplo x será aquela a que pertencerem à
maior parte dos k exemplos mais próximos de x . Assim, nas regiões em que a
densidade dos dados for maior, o tamanho das janelas será menor. Esse comportamento
gera fronteiras de decisão que assumem o formato de células de Voronoi (Hart, P. E.,
1968).
2.3.2 Paradigma Simbólico
Os sistemas de aprendizado simbólico buscam aprender construindo
representações simbólicas de um conceito por meio da análise de exemplos e
contraexemplos desse conceito. As representações simbólicas estão tipicamente na
forma de alguma expressão lógica, árvores de decisão, regras de decisão ou redes
semânticas.
Atualmente, entre as representações simbólicas mais estudas estão as árvores e
regras de decisão. É atribuído a Morgan e Messenger (1973) o desenvolvimento original
dos métodos para a indução de árvores de decisão. O método de indução de árvores de
decisão a partir de dados empíricos, conhecido como particionamento recursivo, foi
investigado por pesquisadores da área de AM e estatística. Os sistemas ID3 (Quinlan, J.
R., 1986) e C4.5 (Quinlan, J. R., 1987a) (Quinlan, J. R., 1987b) para indução de árvores
de decisão tiveram uma importante contribuição sobre a pesquisa em AM. É
interessante observar que sistemas de árvores de classificação e regressão (Breiman, L.
et al., 1984) foram desenvolvidos independentemente por estatísticos durante
praticamente o mesmo período que o ID3, no final dos anos 70.
Os trabalhos com indução de regras de decisão surgiram com a simples tradução
das árvores de decisão para regras, com a poda realizada sobre as regras, tal abordagem
surgiu no trabalho de Quinlan, J. R. (1987a). Posteriormente, foram criados métodos
que induziam regras diretamente a partir dos dados, um exemplo desse trabalho pode ser
encontrado em Michalski, R. T. et al. (1986). Um grande levantamento dos principais
sistemas indutores de regras de decisão pode ser encontrado em Fürnkranz J. (1999).
27 / 101
2.3.3 Paradigma Conexionista
Redes Neurais Artificiais (RNA) (Haykin, S., 1998) podem ser vistas como uma
técnica de AM inspirada no funcionamento do cérebro. Assim como os neurônios
biológicos ligam-se uns aos outros para receber, processar e transportar sinais através de
uma rede complexa, o neurônio artificial, unidade fundamental das RNA, também é
responsável por receber um conjunto de sinais, processá-los e emitir um sinal de saída.
Sua representação envolve unidades interconectadas, daí o termo conexionismo.
Capacidade de aprendizado, generalização e desempenho são características que
as tornam muito úteis para reconhecimento e classificação de padrões, principalmente
aqueles cujas características se modificam ou se adaptam ao ambiente com o passar do
tempo. Umas das principais arquiteturas de RNA utilizadas são os Perceptrons de
Múltiplas Camadas (MLP), os quais vêm obtendo sucesso em tarefas de classificação
nas mais diversas aplicações (Almeida, P. E. M.; Meireles, M. R. G.; Simões, M. G.
(2003), (Alberto, B. L. A.; Almeida, P. E. M.; Durães, R. L., 2008), (Alberto, B. L. A.;
Almeida, P. E. M., 2009) e (Alberto, B. L. A. et al., 2011). Suas principais
características são:
•
O modelo de cada neurônio da rede inclui uma função de ativação não linear;
•
A rede possui uma ou mais camadas de neurônios ocultos (camada escondida) que
extraem as características mais significativas dos padrões de entrada;
•
A rede possui alto grau de conectividade determinado pelas sinapses da rede (rede
totalmente conectada).
Uma rede MLP, em sua forma geral, é representada pela camada de entrada, as
camadas intermediárias (ou camadas ocultas) e a camada de saída. A Figura 2 apresenta
um exemplo de MLP. Um treinamento supervisionado típico desta rede utiliza o
algoritmo Backpropagation, o qual consiste em duas etapas:
•
Um padrão é apresentado às unidades da camada de entrada, processado pelas
camadas intermediárias e sua resposta é então produzida na camada de saída, onde o
erro é calculado (diferença entre a resposta real e a resposta desejada);
•
Este erro é propagado a partir da camada de saída até a camada de entrada, e os
pesos das conexões das unidades das camadas internas vão sendo modificados.
28 / 101
camada escondida
camada de saída
camada de entrada
x1
y1
xn
y2
Figura 2: Estrutura típica de uma rede MLP
Seja uma rede MLP com n entradas, uma camada escondida com h unidades
(neurônios) e uma camada de saída contendo uma única unidade, conforme a Figura 3.
O valor de saída obtido na unidade escondida s da rede, devido à apresentação de um
vetor de entrada x = {x1 , x2 ,..., xn } , é dado pela Equação 2:
n
z s = φ (u s ) = φ (∑ wsr xr ) ,
(2)
r =0
sendo wsr um peso entre a unidade escondida s e a unidade de entrada r e φ (.) a
função de ativação. Similarmente, o valor obtido na unidade de saída da rede é
calculado com base nas saídas emitidas pelas unidades escondidas, na qual ws
representa um peso entre o neurônio de saída e a unidade escondida s . O termo bias é
considerado como uma unidade (entrada escondida) extra com valor igual a 1.
w10
M
x1
w10
xr
wsr
xn
M
whn
w0
z1
zs
zh
ws
fˆ
wn
Figura 3: Exemplo de uma rede MLP
Dado o conjunto de dados T = {( x(i ), y (i )) | i = 1...N } , com y (i ) denotando o
rótulo (saída desejada) para cada vetor de entrada x(i ) ∈ ℜ n , o sinal de erro (estimado
29 / 101
na saída da rede) para o i-ésimo exemplo de treinamento é dado por e(i ) = y (i ) − fˆ (i ) .
Com base nessa expressão, a função custo somatório dos erros quadráticos sobre o
conjunto T pode ser definida conforme as Equações 3 e 4:
h
fˆ = φ (v) = φ (∑ ws z s ) ,
(3)
s =0
J ( w) =
1 N 2
∑ e (i)
2 i =1
∀x(i ) ∈ T ,
(4)
o qual w representando o vetor que armazena todos os parâmetros (pesos e bias) da
rede. A regra de aprendizado do algoritmo Backpropagation padrão é baseada no
método do gradiente descendente (Luenberger, D., 1984). Os parâmetros da rede são
inicializados com valores aleatórios e atualizados, a cada iteração (época), na direção
oposta do vetor gradiente, conforme as Equações 5 e 6:
∆w = −ηg ( w) ,
(5)
wnovo = wanterior + ∆wanterior ,
(6)
com g ( w) sendo o vetor gradiente da função custo (Equação 4) em relação ao vetor de
pesos corrente w e η uma constante positiva (taxa de aprendizado) que indica o
tamanho do termo de atualização (Equação 6) aplicado a cada época de treinamento. O
vetor gradiente g ( w) é dado pela derivada parcial da função custo (Equação 4) em
relação ao peso arbitrário da rede w1 conforme a Equação 7:
1 N ∂e 2 (i )
∂J
= ∑
∂w1 2 i =1 ∂w1
N
= ∑ e(i )
i =1
∂e(i )
.
∂w1
(7)
A metáfora biológica com as conexões neurais do sistema nervoso tem
interessado muitos pesquisadores e fornecido diversas discussões sobre os méritos e as
limitações dessa abordagem de aprendizado. Em particular, as analogias com a biologia
têm levado muitos pesquisadores a acreditar que as redes neurais possuem um grande
potencial na resolução de problemas que requerem intenso processamento sensorial
humano, tais como visão e reconhecimento de voz.
As pesquisas em redes neurais foram iniciadas com o trabalho pioneiro de
McCulloch e Pitts em 1943. McCulloch era um psiquiatra e pesquisou por 20 anos uma
forma de representar um evento no sistema nervoso. Pitts era um jovem pesquisador e
começou a trabalhar com McCulloch em 1942. Praticamente 15 anos após a publicação
30 / 101
de McCulloch e Pitts, Rosemblatt (1958) apresentou o Perceptron, cuja grande
contribuição foi a prova do teorema de convergência. Mas, no livro Perceptron, Minsky
e Papert (1969) demonstraram a existência de limites fundamentais nos perceptrons de
uma camada. A pesquisa na área ficou praticamente interrompida até que Hopfield
(1982) utilizou a ideia de uma função de energia para compreender os cálculos
realizados em redes recorrentes com conexões sinápticas simétricas.
Talvez mais do que qualquer outra publicação, o artigo de Hopfield em 1982 e o
trabalho de Rumelhart, D.E. e J.L. McClelland (1986) foram as publicações que mais
influenciaram para o ressurgimento do interesse sobre redes neurais na década de 80.
2.3.4 Paradigma Evolutivo
Este paradigma faz uma analogia com a teoria de Darwin, na qual somente os
mais adaptados sobrevivem. A partir dos trabalhos originais de Holland, J. H. (1975)
pôde-se definir um classificador evolutivo como uma população de elementos de
classificação que competem entre si para realizar uma tarefa de predição. Os elementos
de desempenho fraco são descartados e os mais fortes proliferam produzindo variações
sobre eles próprios. Os sistemas de classificação foram originalmente propostos por
Holland como sistemas capazes de perceber e classificar os acontecimentos em seu
ambiente e reagir a eles apropriadamente.
Para a construção de tais sistemas é
necessário: (i) um ambiente; (ii) receptores que informam ao sistema sobre o que está
ocorrendo; (iii) elementos que permitam ao sistema manipular o seu ambiente e; (iv) o
sistema em si, geralmente, um sistema do tipo caixa preta numa primeira abordagem.
Geralmente os classificadores evolutivos são formados por algoritmos, também
conhecidos como Algoritmos Genéticos – AG (Koza, J. R. 1992; Goldberg, D. E., 1989;
Norvig, P. and Russel, S., 1995) que implementam mecanismos de evolução natural
incluindo cruzamento, mutação e aptidão para sobrevivência. O técnica de AG trabalha
com populações de indivíduos e deriva o seu comportamento de uma metáfora do
processo evolutivo natural. Isto é obtido pela criação em um computador de uma
população de indivíduos representados por cromossomas, em essência um conjunto de
strings de caracteres análogos aos cromossomas de quatro bases (timina, guanina,
adenosina e citosina) existentes no DNA natural. Os indivíduos na população são então
submetidos a um processo de evolução.
31 / 101
2.3.5 Paradigma instance-based
Uma forma de classificar um dado é associá-lo a uma classe cujos exemplos são
similares a este dado. Essa filosofia exemplifica os sistemas instance-based, os quais
classificam casos nunca vistos utilizando exemplos similares conhecidos (Kibler, D. and
Langley, P. 1988). As principais características dos sistemas instance-based são:
Lembrança dos exemplos de treinamento. Se todos os exemplos forem memorizados,
o classificador pode se tornar lento e difícil de manusear. O ideal é reter casos comuns
que juntos resumam toda a informação importante. Uma segunda solução reside em
construir estruturas capazes de indexar os exemplos e responder consultas sobre os
exemplos mais semelhantes de forma rápida. Exemplos dessas estruturas são as MTrees (Ciaccia, P.; Patella, M. and Zezula, P., 1997) e as Slim-Trees (Jr., C. T.; Traina,
A.; Seeger, B. and Faloutsos, C., 2000).
Medida de similaridade entre os exemplos. Se todos os atributos forem quantitativos,
pode-se calcular a distância entre dois casos utilizando a distância euclidiana, por
exemplo. Quando alguns atributos não são quantitativos, essa interpretação de distância
se torna mais problemática. Além do mais, se existem atributos irrelevantes, dois casos
similares podem aparentar serem muito diferentes pois eles podem possuir valores
diferentes em atributos sem importância. Stanfill, C. e Waltz, O. (1986) desenvolveram
um método sensível ao contexto para alterar a escala dos atributos de forma que as
medidas de distância fiquem mais robustas.
Relação entre um novo exemplo e os exemplos armazenados. Para classificar um
novo exemplo existem diversas alternativas. Uma delas consiste em usar um único
exemplo, o qual é o mais próximo do novo exemplo, para classificá-lo. Uma segunda
alternativa consiste em usar vários exemplos. Nessa alternativa, pode-se levar em
consideração os diferentes graus de similaridade entre cada um e o novo exemplo na
determinação de sua classe. A segunda alternativa é geralmente mais utilizada por ser
mais robusta a erros nos dados.
2.4
Considerações finais
Alguns paradigmas de AM vêm sendo estudados constantemente, tais como o
paradigma simbólico, estatístico, instance-based, conexionista e genético. O
aprendizado pode ser realizado de maneira supervisionada, não supervisionada ou semisupervionada. O aprendizado supervisionado é feito como se houvesse o auxílio de um
tutor, responsável por informar a resposta desejada em cada situação. No aprendizado
32 / 101
não supervisionado, não existem rótulos que indiquem a que classe cada exemplo
pertence. Já no semi-supervisionado os poucos exemplos rotulados para se obter
informações sobre o problema são utilizados para guiar o processo de aprendizado a
partir dos exemplos não rotulados.
33 / 101
3
Pré-processamento de dados
3.1
Considerações iniciais
Este capítulo está organizado da seguinte forma: na seção 3.2 é explicada a
diferença entre tarefas fracamente e fortemente dependentes de domínio. Na seção 3.3
são discutidos os problemas típicos encontrados em conjunto de dados, introduzindo o
problema de desbalanceamento de classes. Em seguida na seção 3.4 é apresentada a
importante tarefa de transformação dos dados a fim de superar limitações existentes nos
algoritmos que são empregados para extração de características. Por fim, a seção 3.5
apresenta as considerações finais.
3.2
Tarefas dependentes de domínio
O pré-processamento de dados em AM é frequentemente tido como sendo uma
tarefa que envolve uma grande quantidade de conhecimento do domínio do problema
em que se dá a investigação. Coletar dados geralmente é uma tarefa complexa e muitas
vezes os dados coletados são de qualidade questionável, ou seja, possuem informações
incorretas e imprecisas. Embora muitos dos algoritmos utilizados em AM tenham sido
projetados para manipular dados em tais situações, espera-se que esses algoritmos
gerem resultados mais precisos caso a maioria dos problemas presentes nos dados tenha
sido removida ou corrigida cuidadosamente.
Geralmente, pré-processamento de dados é um processo semi-automático, ou
seja, depende da capacidade de um especialista humano em identificar os problemas
presentes nos dados, além de sua natureza, e utilizar os métodos mais apropriados para
solucionar cada um dos problemas. As tarefas realizadas por métodos empregados na
fase de pré-processamento são divididas em dois grupos (Fayaad, U. et al., 1996):
Tarefas fortemente dependentes do conhecimento no domínio do problema. Essas
tarefas somente podem ser efetivamente realizadas com o uso de conhecimento
específico do problema. Um método automático pode eventualmente ser empregado
para realizar uma tarefa fortemente dependente desse conhecimento, entretanto, esse
método depende que um conhecimento específico seja fornecido por um especialista.
Como exemplo de tarefa fortemente dependente do domínio pode-se citar a verificação
de coerência dos dados. Para realizar tais análises é normalmente necessário conhecer as
restrições das variáveis consideradas. Por exemplo, valores negativos ou com mais de
34 / 101
quatro dígitos não são permitidos para variáveis que tratam de idade ou peso de uma
pessoa. Dessa forma, a partir do conhecimento dessas limitações, é possível utilizar um
método automático que encontre problemas de incoerência nos dados. Mesmo sendo
automático, tal método depende de conhecimento do domínio, ou seja, do conhecimento
do contexto em que os dados estão inseridos. Por este motivo, essas tarefas são
denominadas fortemente dependentes de conhecimento do domínio do problema.
Tarefas fracamente dependentes do conhecimento do domínio do problema. Essas
tarefas podem ser realizadas por métodos que extraem dos próprios dados as
informações necessárias para tratar o problema de pré-processamento de dados. Se por
um lado essas tarefas ainda dependem de conhecimento da aplicação, pois é necessário,
por exemplo, selecionar o método mais adequado para tratar o problema de préprocessamento de dados, por outro lado essas tarefas podem ser realizadas por métodos
com menor dependência de um especialista no problema que aquelas que dependem
fortemente de conhecimento do domínio. Das tarefas fracamente dependentes de
conhecimento no domínio do problema pode-se citar o tratamento de valores
desconhecidos, a seleção de atributos, a identificação de valores extremos, o tratamento
de conjuntos de dados com classes desbalanceadas, detecção de ruídos, entre outras.
Frequentemente, essas tarefas podem ser tratadas com o uso de conhecimento do
contexto do problema. Por exemplo, as falhas no processo de aquisição de dados que
geram valores desconhecidos para uma determinada aplicação podem ser identificadas e
corrigidas a partir da interpolação de valores ausentes. Entretanto, na ausência de
conhecimento do problema, essas tarefas de pré-processamento podem ser realizadas
com o uso de métodos automáticos.
3.3
Problemas típicos
As tarefas de pré-processamento de dados fracamente dependentes do domínio
da aplicação podem ser geralmente solucionadas por métodos que extraem do próprio
conjunto de dados as informações necessárias para tratar o problema. Essas tarefas são o
principal foco deste trabalho e são brevemente descritas a seguir:
Tratamento de valores desconhecidos. Um problema comum em pré-processamento
de dados é o tratamento de valores desconhecidos. Muitas técnicas têm sido aplicadas,
sendo algumas delas bastante simples, como a substituição dos valores desconhecidos
pela média ou moda do atributo ou simplesmente interpolando valores ausentes.
Entretanto, outras técnicas mais elaboradas podem ser implementadas e avaliadas
35 / 101
experimentalmente. Por exemplo, podem-se substituir os valores desconhecidos por
valores previstos utilizando um algoritmo de aprendizado.
Identificação e descrição de valores extremos. Valores extremos são dados que
aparentemente não seguem o mesmo padrão dos demais. Estatísticos têm pesquisado
por métodos de identificação de valores extremos, uma vez que esses valores podem
distorcer os resultados obtidos por diversos métodos paramétricos (Barnett, V. and
Lewis, T., 1994). Entretanto, valores extremos precisam ser tratados com cuidado, uma
vez que casos que possuem valores extremos que, a princípio, parecem ser dados
incorretos, podem ser dados válidos. Na realidade, os casos com valores extremos
podem representar a informação mais interessante, pela qual o especialista humano está
procurando. Diversos métodos para identificar valores extremos foram propostos por
pesquisadores de AM, tais como, o método de filtro (Brodley, C. E. and Friedl, M. A.,
1999) e de aprendizado instanced-based, como por exemplo Ligações Tomek (Tomek,
I., 1976).
Tratamento de conjuntos de dados com classes desbalanceadas. Conjuntos com
classes desbalanceadas são aqueles que possuem uma grande desproporção entre o
número de exemplos pertencentes a cada classe. A maioria dos algoritmos de AM tem
dificuldades de criar um modelo que classifique com precisão os exemplos de classes
minoritárias. Uma forma de solucionar esse problema é utilizar uma distribuição das
amostras que forneça um desempenho aceitável de classificação para as classes
minoritárias. Seleção Unilateral foi utilizada por Kubat, M. e Matwin , S. (1997) para
balancear um conjunto de dados contendo informações colhidas de fotos de satélites.
Chawla, N. V. et al. (2002) combina os métodos de subamostragem e sobreamostragem
e, ao invés de fazer sobreamostragem pela simples replicação de exemplos da classe
minoritária, o faz pela interpolação de exemplos da classe minoritária que estão
próximos. Dessa forma, o overfitting é contornado e as fronteiras de decisão para a
classe minoritária são estendidas no espaço de exemplos da classe majoritária. Muitos
outros trabalhos também analisaram o problema de aprender sobre conjunto de dados
desbalanceados (Pazzani, M. et al., 1994; Ling, C. X. and Li, C., 1998; Kubat, M. and
Matwin, S., 1997; Fawcett, T. and Provost, F., 1997; Kubat, M. and Matwin, S., 1998;
Japkowicz, N. and Stephen, S., 2002).
Seleção de atributos. Seleção de atributos é um problema muito importante em AM
(Blum, A. L. amd Langley, P., 1997; John, G., Kohavi, R. and Pfleger, K., 1994). Ele
consiste em encontrar um subconjunto de atributos no qual o algoritmo de AM utilizado
36 / 101
em tarefas de classificação irá se concentrar. Existem diversas razões que justificam o
uso de métodos para seleção de atributos. As principais são (Lee, H. D., Monard, M. C.
and Baranauskas, J. A., 1999):
1. Muitos algoritmos de AM não funcionam bem com uma grande quantidade de
atributos, dessa forma, seleção de atributos pode melhorar o desempenho desses
algoritmos;
2. Com um número menor de atributos o conhecimento induzido por algoritmos de
AM é, frequentemente, mais compreensível;
3. Alguns domínios possuem um alto custo de coletar dados, nesses casos métodos de
seleção de atributos podem diminuir o custo da aplicação.
Existem diversas abordagens propostas para selecionar um subconjunto de
atributos. De uma forma geral, podem-se dividir as abordagens mais utilizadas em
seleção de atributos de dados em embedded, filtro e wrapper (Lee, H. D.; Monard, M.
C. and Baranauskas, J. A., 1999). Outra abordagem denominada híbrida constitui uma
combinação, quer seja de diversas maneiras de interação entre o critério de avaliação e o
algoritmo básico de indução, quer seja de diferentes critérios de avaliação. Um desses
algoritmos híbridos utiliza boosting (Freund, Y. and Schapire, R. E., 1997) e incorpora
algumas características da abordagem wrapper em um filtro. As três primeiras
abordagens, embedded, filtro e wrapper, são descritas a seguir.
1. Abordagem Embedded: nessa abordagem a tarefa de seleção dos atributos é
realizada internamente pelo próprio algoritmo de aprendizado. Em outras palavras,
a seleção de um subconjunto de atributos está embutida no algoritmo de AM
conforme apresentado na Figura 4.
Subconjunto de atributos
Indutor
Conjunto de treinamento
Conjunto de testes
Estimativa de desempenho
Classificador
Figura 4 – Abordagem Embedded
(Adaptado de John, G., Kohavi, R. and Pfleger, K., 1994)
37 / 101
2. Abordagem Filtro: nessa abordagem é introduzido um processo separado, o qual
ocorre antes da aplicação do algoritmo de aprendizado propriamente dito conforme
Figura 5. A ideia é filtrar atributos irrelevantes antes do aprendizado ocorrer (John,
G., Kohavi, R. and Pfleger, K., 1994). Esse passo de pré-processamento considera
características gerais do conjunto de dados para selecionar alguns atributos e
excluir outros. Sendo assim, métodos de Filtro são independentes do algoritmo de
aprendizado que, simplesmente, receberá como entrada o conjunto de exemplos
descrito utilizando somente o subconjunto de atributos importantes fornecido pelo
filtro.
Subconjunto de atributos
Filtro
Conjunto de
treinamento reduzido
Conjunto de treinamento
Remover
atributos
Indutor
Conjunto de testes
Conjunto de
teste reduzido
Classificador
Estimativa de
desempenho
Figura 5 – Abordagem Filtro
(Adaptado de John, G., Kohavi, R. and Pfleger, K., 1994)
3. Abordagem Wrapper: essa abordagem também ocorre externamente ao algoritmo
básico de aprendizado, porém utilizando tal algoritmo como uma “caixa preta” para
analisar, a cada interação, o subconjunto de atributos em questão conforme
apresentado na Figura 6. Em outras palavras, métodos Wrapper geram um
subconjunto de atributos selecionado do conjunto de treinamento, e utilizam a
precisão resultante do classificador induzido para avaliar o subconjunto de atributos
em questão. Esse processo é repetido para cada subconjunto de atributo até que o
critério de parada determinado seja satisfeito.
38 / 101
Estimativa de desempenho
Conjunto de
treinamento
Conjunto de
treinamento
com menos
atributos
Busca por
atributos
Indutor
Estimativa de
desempenho
Indutor
Classificador
Conjunto de testes
Figura 6 – Abordagem Wrapper
(Adaptado de John, G., Kohavi, R. and Pfleger, K., 1994)
Um argumento utilizado com muita frequência para apoiar a utilização de
abordagem Wrapper é que o mesmo algoritmo de aprendizado que vai usar o
subconjunto de atributos selecionado deve prover uma estimativa melhor de precisão
que um outro algoritmo (John, G., Kohavi, R. and Pfleger, K., 1994). Porém, a maior
desvantagem dos métodos Wrapper é o custo computacional, o qual resulta da execução
do algoritmo de aprendizado para avaliar cada subconjunto de atributos a ser
considerado (Pila, A. D. 2001; Lee, H. D., Monard, M. C. and Baranauskas, J. A., 1999;
Kohavi, R. and Pfleger, K., 1994).
Construção de atributos. Os atributos podem ser considerados inadequados para a
tarefa de aprendizado quando são fracamente ou indiretamente relevantes,
condicionalmente relevantes ou medidos de modo inapropriado (Baranauskas, J. A.,
Monard, M. C. and Horst, P. S., 1999; Lee, H. D., Monard, M. C. and Baranauskas, J.
A., 1999). Se os atributos utilizados para a descrição do conjunto de dados são
inadequados, os algoritmos de AM utilizados em tarefas de classificação provavelmente
criarão classificadores imprecisos ou excessivamente complexos (Bloedorn, E. and
Michalski, R. S, 1998). Atributos fracamente, indiretamente ou condicionalmente
relevantes podem ser individualmente inadequados, entretanto, esses atributos podem
ser convenientemente combinados gerando novos atributos que podem mostrar-se
altamente representativos para a descrição de um conceito. O processo de construção de
39 / 101
novos atributos é conhecido como construção de atributos ou indução construtiva
(Michalski, R. S., 1978; Bloedorn, E. and Michalski, R. S., 1998). Assim, a construção
de atributos é o processo de composição de atributos ditos primitivos, produzindo-se
novos atributos possivelmente relevantes para a descrição de um conceito. De uma
forma bastante ampla, o processo de indução construtiva pode ser dividido em duas
abordagens: a automática e a guiada pelo usuário. A indução construtiva automática
consiste em um processo de construção de atributos guiada automaticamente pelo
método de construção. Geralmente, os atributos construídos são avaliados em relação
aos dados, e podem ser descartados ou integrados ao conjunto de dados. A indução
construtiva guiada pelo usuário utiliza o conhecimento do usuário ou do especialista no
domínio para guiar a composição dos atributos.
3.4
Transformação de dados
O principal objetivo desta tarefa é transformar a representação dos dados a fim
de superar quaisquer limitações existentes nos algoritmos que serão empregados para a
extração de padrões. De uma forma geral, a decisão de quais transformações são
necessária depende do algoritmo que será utilizado para a classificação (Durães, R. L.,
2009). Algumas das transformações mais comuns são:
Normalização. Consiste em transformar os valores dos atributos de seus intervalos
originais para um intervalo específico, como, por exemplo, [-1,1] ou [0,1]. Esse tipo de
transformação é especialmente valioso para os métodos que calculam distâncias entre
atributos. Por exemplo, um método como o k-vizinhos mais próximos tende a dar mais
importância para os atributos que possuem um intervalo maior de valores. Outros
métodos como RNA são reconhecidamente melhor treinadas quando os valores dos
atributos são pequenos. Entretanto, normalização não é de grande utilidade para a
maioria dos métodos que induzem representações simbólicas, tais como árvores de
decisão e regras de decisão, uma vez que a normalização tende a diminuir a
compreensibilidade do modelo gerado por tais algoritmos.
Discretização de atributos quantitativos. Muitos algoritmos possuem a limitação de
trabalhar somente com atributos qualitativos. Entretanto, muitos conjuntos de dados
possuem atributos quantitativos, e para que esses algoritmos possam ser aplicados é
necessário utilizar algum método que transforma um atributo quantitativo em atributo
qualitativo, ou seja, em faixas de valores. Diversos métodos de discretização de
atributos foram propostos pela comunidade. Uma descrição geral desses métodos pode
40 / 101
ser encontrada em (Dougherty, J., Kohavi, R. and Sahami, M., 1995; Kohavi, R. and
Sahami, M., 1996).
Transformação de atributos qualitativos em quantitativos. Alguns algoritmos não
são capazes de manipular atributos qualitativos. Dessa forma, é necessário converter os
atributos qualitativos em atributos quantitativos. Existem diversas abordagens para
realizar essa transformação dependendo das características e limitações de cada
algoritmo. De uma forma geral, atributos qualitativos sem ordem inerente, tal como
verde, amarelo e vermelho, podem ser mapeados arbitrariamente para o formato
numérico. Entretanto, esse mapeamento acaba por criar uma ordem nos valores do
atributo que não é real. Atributos qualitativos ordinais, tal como pequeno, médio e
grande, podem ser mapeados para valores numéricos de forma a manter a ordem dos
valores, por exemplo pequeno = 1, médio = 2 e grande = 3. Alguns especialistas em
RNA aconselham criar um nó de entrada para cada valor de um atributo qualitativo, ou
seja, um atributo qualitativo com p valores diferentes deve ser desmembrado em p
atributos binários. Cada novo atributo binário representa um único valor do atributo
original. Esse mapeamento é feito sempre que o valor de p não seja grande,
tipicamente 2 < p < 5 . Caso p = 2 , então é feito um mapeamento de tal forma que um
dos valores do atributo quantitativo represente um valor baixo (tipicamente zero) e o
outro valor represente um valor alto (tipicamente 1).
3.5
Considerações finais
Algoritmos de AM são uma alternativa muito interessante para muitos
problemas em classificação de padrões. Entretanto, a maioria das pesquisas em AM
trata problemas bem definidos, com conjuntos de dados pequenos, bem comportados e
relativamente bem preparados para a tarefa. Além disso, os objetivos da tarefa de
aprendizado estão bem definidos, tal como maximizar a taxa de acerto dos modelos de
classificação.
Para muitos domínios de aplicação, como por exemplo o diagnóstico de doenças
raras, é comum que exista uma grande desproporção entre a quantidade de exemplos
rotulados em cada uma das classes presentes. Nesses casos, é muito simples projetar um
classificador que possua alta precisão, através de um sistema que responda com a classe
majoritária para qualquer novo caso. Entretanto, classificar precisamente a classe
minoritária é frequentemente o maior objetivo de tais aplicações.
41 / 101
Muitos dos sistemas de AM tradicionais não estão preparados para aprender
conceitos que classifiquem ambas as classes, com precisão, sob tais condições. Como
resultado do aprendizado, frequentemente obtém-se uma alta precisão de classificação
para a classe majoritária e uma inaceitável precisão para a classe minoritária.
Esta seção apresentou a diferença entre tarefas fracamente e fortemente
dependentes de domínio e uma breve descrição dos problemas típicos encontrados em
conjunto de dados, introduzindo o problema de desbalanceamento de classes.
42 / 101
4
Desbalanceamento de classes
4.1
Considerações iniciais
Muitos aspectos podem influenciar o desempenho de um modelo de
classificação criado por um sistema de aprendizado supervisionado. Um desses aspectos
está correlacionado com a diferença entre o número de exemplos pertencentes a cada
uma das classes. Quando essa diferença é grande, os sistemas de aprendizado podem
encontrar dificuldades em induzir o conceito relacionado à classe minoritária. Nessas
condições, modelos de classificação que são otimizados em relação à precisão têm
tendência de criar modelos triviais, que quase sempre predizem a classe majoritária.
Entretanto, em muitos dos problemas reais, uma grande desproporção no número de
casos pertencentes a cada uma das classes é comum. Por exemplo, na detecção de
fraudes em chamadas telefônicas (Fawcett, T. and Provost, F. J., 1997) e transações
realizadas com cartões de crédito (Pednault, E. P. D., Rosen, B. K. and Apte, C., 2000),
o número de transações legítimas é muito maior que o de transações fraudulentas. Na
modelagem de risco de seguros, apenas uma pequena porcentagem dos segurados
reclama suas apólices em um dado período.
Outros exemplos de domínios com um desbalanceamento intrínseco entre as
classes podem ser encontrados na literatura. Além disso, em muitas aplicações, não se
sabe qual é a proporção exata de exemplos pertencentes a cada classe ou se essa
proporção pode variar no tempo. Muitos sistemas de aprendizado, nessas circunstâncias,
não estão preparados para induzir modelos de classificação que possam predizer
acertadamente as classes minoritárias. Frequentemente, esses modelos têm uma boa
precisão na classificação da classe majoritária, mas a precisão para a classe minoritária
não é aceitável. O problema é ainda maior quando o custo associado a uma classificação
errônea para a classe minoritária é muito maior que o custo de uma classificação errônea
para a classe majoritária. Infelizmente, esta é a norma e não a exceção para a maioria
das aplicações com conjuntos de dados desbalanceados, pois geralmente a classe
minoritária é a de maior interesse.
Nesta seção são discutidos alguns dos métodos de pré-processamento de dados
mais utilizados para solucionar o problema de aprender com conjuntos de dados com
classes desbalanceadas. Ele está organizado da seguinte forma: na seção 4.2 a natureza
do problema de classes desbalanceadas é analisada com base nas teorias de Decisão
43 / 101
Bayesiana e Aprendizado de Máquina. Na seção 4.3 são apresentadas as principais
métricas da literatura para análise do desempenho de classificadores, tendo como foco
as métricas: área sob a curva ROC (ROC - Relative Operating Characteristic) conhecida
como AUC (Area Under ROC Curve) e Gmean (Kubat et al., 1998). Na seção 4.4 é
abordado, embora não seja o foco deste trabalho, um importante tópico relativo ao
aprendizado sensível ao custo. Sistemas de aprendizado sensíveis ao custo visam
reduzir o custo de classificação incorreta dos exemplos, ao invés do erro de
classificação, estes últimos tipicamente vistos em grande parte dos sistemas de
aprendizado tradicionais. Na seção 4.5, uma das principais desta dissertação, são
descritos os principais métodos na literatura para balanceamento de classes a partir dos
estudos e investigações realizadas. E por fim, na seção 4.6, as considerações finais.
4.2
Natureza do problema de classes desbalanceadas
Com base nas teorias de Decisão Bayesiana (Berger, J. 1985; Duda, R. O. et al.,
2000) e Aprendizado Estatístico (Vapnik, V. N., 1995, 1998) pode ser demonstrado que
o problema de desbalanceamento de classes surge como uma consequência direta da
minimização de um critério baseado no erro global, tendo como principal atenuante o
nível de sobreposição (ruído) das distribuições. Este problema, como é conhecido em
AM, surge principalmente porque os algoritmos convencionais assumem diferentes
erros como igualmente importantes, supondo que as distribuições são relativamente
equilibradas (He, H. and Garcia, E. A., 2009), (Monard, M. and Batista, G. E. A. P. A.,
2002). Embora essa estratégia possa produzir modelos com elevadas taxas de acurácia
global, ela frequentemente tende a prejudicar a identificação de exemplos pertencentes a
grupos raros que, na maioria dos casos, representam os grupos de interesse. Uma
caracterização teórica para o problema de classes desbalanceadas pode ser encontrada
em (Berger, J. 1985; Duda, R. O. et al., 2000), (Bishop, C. M., 2006) e (Vapnik, V. N.,
1995).
Além do desequilíbrio entre as distribuições, outro fator determinante para o
problema em questão é o nível de incerteza (ruído) associado à tarefa de classificação.
Estudos experimentais conduzidos em Japkowicz, M. e Stephen, S. (2002) e Prati, R. C.
et al. (2004) mostraram que, para uma razão fixa de desbalanceamento, um aumento no
nível de sobreposição das classes pode diminuir significativamente o número de
classificações positivas corretas. Khoshgoftaar, T. M. et al. (2010) realizaram uma
investigação empírica sobre o impacto causado pela combinação ruído +
44 / 101
desbalanceamento no aprendizado de modelos baseados em redes MLP e RBF (Haykin,
S., 1998).
As conclusões obtidas nos estudos supracitados permitem explicar porque, para
determinadas aplicações, pequenas razões de desbalanceamento podem comprometer
mais a capacidade de reconhecimento da classe positiva do que as grandes. Além disso,
elas ajudam a compreender a razão da insensibilidade ao desbalanceamento
normalmente observada em domínios separáveis, os quais as classes representam
clusters bem definidos no espaço de entrada.
Para ilustrar essa ideia, considere um problema de decisão simples mostrado na
Figura 7(a,b). O problema está relacionado a construir um modelo de classificação para
um problema de apenas um atributo e duas classes: positiva e negativa. As
probabilidades condicionais para ambas as classes são dadas por funções gaussianas
unidimensionais com variância igual a unidade. O valor médio do atributo para a classe
negativa está uma unidade deslocado para a direita.
No problema representado na Figura 7(a), o objetivo é construir um modelo de
classificação bayesiano assumindo um perfeito conhecimento com respeito às
distribuições de probabilidade. Nesse caso, é possível construir o modelo de
classificação ótimo de Bayes. A linha vertical representa a divisão ótima entre as
classes, segundo o critério de Bayes. Nessas condições, o modelo ótimo não é alterado,
não importando o quão desbalanceado é o conjunto de exemplos.
0.35
0.35
0.3
0.3
0.25
0.25
P ro b a b ilit y
0.4
P ro b a b ilit y
0.4
0.2
0.2
0.15
0.15
0.1
0.1
0.05
0.05
0
0
2
4
6
8
10
Atribute X
12
(a)
14
16
18
20
0
0
2
4
6
8
10
Atribute X
12
14
16
18
20
(b)
Figura 7 – Nível alto de sobreposição entre as classes: (a) com conhecimento a priori
das distribuições e; (b) sem conhecimento a priori das distribuições (Matlab, 2008).
45 / 101
Em contrapartida, na Figura 7(b) é apresentado o mesmo problema, só que agora
não se conhece de antemão as distribuições a priori. Em outras palavras, as distribuições
devem ser estimadas a partir dos dados. Caso haja uma grande desproporção entre as
classes, é provável que os algoritmos de aprendizado produzam estimativas ruins para
as classes com poucos exemplos. Na Figura 7(b) em particular, a variância é
superestimada em duas unidades (linha contínua) ao invés da variância em uma unidade
(linha tracejada). Ou seja, conhecendo-se de antemão as probabilidades condicionais
(uma restrição dificilmente aplicável em problemas do mundo real) de maneira que seja
possível construir o modelo ideal de Bayes, a distribuição de exemplos entre as classes
não representa um problema. Em contrapartida, quando se utiliza somente os dados
disponíveis para estimar os parâmetros e esses dados não são suficientes para gerar
estimativas confiáveis, classes desbalanceadas podem ser um problema na indução de
modelos para a classificação de exemplos.
Consideremos agora um problema ligeiramente diferente, mostrado na Figura
8(a,b). Novamente, o problema é composto por um único atributo e duas classes que
seguem uma distribuição gaussiana, mas a média dos valores desse atributo para a
classe negativa está agora quatro (ao invés de uma) unidades à direita da classe positiva.
Assim como na Figura 7(a), na Figura 8(a) é representado o cenário em que é completo
o conhecimento sobre as distribuições de probabilidade. Já na Figura 8(b) é
representado o cenário em que o algoritmo de aprendizado deve estimar esses valores
somente com os dados disponíveis. Pelas mesmas razões descritas anteriormente,
quando é assumido o perfeito conhecimento a respeito das distribuições, o modelo
ótimo de Bayes não é afetado pela distribuição de exemplos entre as classes. Entretanto,
no caso em que não se conhece a priori essas distribuições, o modelo final é afetado.
Note que, uma vez que as médias dos valores do atributo para as duas classes estão mais
distantes, as classes estão mais separadas. Isso é equivalente a dizer que existe uma
menor sobreposição entre as classes. Observe que, por esse motivo, o efeito do
desbalanceamento entre as classes é menor do que no caso com uma maior sobreposição
de classes.
46 / 101
0.35
0.35
0.3
0.3
0.25
0.25
P r o b a b i lit y
0.4
P ro b a b ilit y
0.4
0.2
0.2
0.15
0.15
0.1
0.1
0.05
0.05
0
0
2
4
6
8
10
Atribute X
12
14
16
18
20
0
0
(a)
2
4
6
8
10
Atribute X
12
14
16
18
20
(b)
Figura 8 – Pequena sobreposição entre as classes: (a) Com conhecimento a priori das
distribuições e; (b) Sem conhecimento a priori das distribuições (Matlab, 2008).
Note também que mesmo que a distância entre as linhas verticais pontilhadas e
contínuas sejam semelhantes, a área entre elas e a curva de distribuição de probabilidade
é maior na Figura 7(b) do que na Figura 8(b). Isso é equivalente a dizer que o número
de exemplos classificados incorretamente no primeiro caso é maior do que o número de
exemplos classificados incorretamente no segundo caso. Esse é um indicativo de que o
desbalanceamento entre as classes não é o único responsável pelo baixo desempenho em
problemas desbalanceados, mas também o grau de sobreposição entre as classes. Nas
seções seguintes é apresentada uma série de experimentos com conjuntos de dados
sintéticos com intuito de confirmar essa hipótese.
4.3
Métricas de avaliação
Normalmente, a avaliação de desempenho de classificadores é feita com base em
taxas de erro. Em problemas de classificação com uma ou duas classes, o desempenho
de um modelo de classificação geralmente pode ser medido utilizando matrizes de
confusão. Uma matriz de confusão define a probabilidade de identificação correta de
exemplos do perfil de cada classe (classe positiva e classe negativa). A Tabela 3
apresenta a matriz de confusão em sua forma geral para o problema de classificação de
duas classes.
47 / 101
Tabela 3 – Matriz de confusão para problema de duas classes (Fawcett, T., 2006)
Classe positiva
Classe negativa
Predição positiva
Predição negativa
Verdadeiro positivo (VP)
Falso positivo (FP)
Falso negativo (FN)
Verdadeiro negativo (VN)
Complementar à taxa de erro ( TE R ), outra medida de desempenho para
avaliação de classificadores é a acurácia ( ACC ) na classificação. A acurácia é definida
como a relação entre a quantidade de classificações corretas em relação a todas as
classificações, conforme apresentado na Equação 8:
ACC =
VP + VN
VP + VN
=
AP + AN VP + FN + FP + VN
(8)
A taxa de erro na classificação é definida como TE R = 1 − ACC .
Os elementos ao longo da diagonal principal da matriz de confusão representam
as decisões corretas: número de verdadeiros positivos ( VP ) e verdadeiros negativos
( VN ). Os elementos fora dessa diagonal representam os erros cometidos: número de
falsos positivos ( FP ) e falsos negativos ( FN ).
Essa metodologia é justificada pela formulação padrão do aprendizado que visa
à minimização da probabilidade do erro global. Para problemas desbalanceados, no
entanto, a acurácia não fornece informação adequada sobre a capacidade de
discriminação de um classificador em relação a cada uma das classes em separado.
Considere, por exemplo, um conjunto de dados em que a classe minoritária é
representada por apenas 5% das observações. Um classificador com acurácia de 95%
pode ser diretamente obtido por simplesmente classificar todo exemplo como
pertencente à classe majoritária. Apesar da elevada taxa de acurácia obtida, tal
classificador torna-se inútil se o objetivo principal é a identificação de exemplos raros.
Na matriz de confusão pode ser observado que a distribuição entre as classes é o
relacionamento entre a primeira e a segunda linha. Assim, qualquer medida de
desempenho que utilize valores de ambas as colunas será, necessariamente, sensível à
desproporção entre as classes. Métricas como precisão, taxa de erro, entre outras,
utilizam valores de ambas as linhas da matriz de confusão. Com estas quantidades
definidas, podem-se definir as Equações 9 e 10 para as medidas de sensibilidade ( S E ) e
especificidade ( E S ) (Fawcett, T., 2006):
48 / 101
VP
VP
=
AP VP + FN
(9)
VN
VN
=
AN VN + FP
(10)
SE =
ES =
Sensibilidade e especificidade são conceitos amplamente utilizados em testes de
classificação com duas classes. No contexto deste trabalho, S E é a probabilidade de
classificar corretamente um exemplo do perfil da classe positiva, ou seja, a taxa de VP
( TV P ). A Es é a probabilidade de classificar corretamente um exemplo da classe
negativa, ou seja, a taxa de VN ( TV N ). Essas duas medidas são interdependentes na
medida em que uma maior sensibilidade, ou seja, uma identificação mais confiável de
elementos do perfil da classe positiva leva naturalmente a uma menor especificidade,
uma vez que elementos da classe negativa serão identificados com menor frequência.
Normalmente, a avaliação de classificadores é feita com base em taxas de erro,
o que permite uma comparação direta com as taxas de erro de classificadores
tradicionais. Métricas como acurácia, sensibilidade, especificidade e taxas de erro,
utilizam valores de ambas as linhas da matriz de confusão e havendo uma mudança na
distribuição de classes, os valores dessas métricas também mudarão, mesmo que o
desempenho global do modelo não melhore. Um fato contra o uso da taxa de erro é que
essa métrica considera os diferentes erros de classificação como igualmente
importantes. Em domínios nos quais o erro de classificação é relevante, uma matriz de
custo pode ser utilizada. Esta define os custos de classificações errôneas, isto é, uma
penalidade pela incursão de uma falha para cada possível erro do modelo. Nesse caso, o
objetivo do modelo é minimizar os custos de classificação ao invés da taxa de erro. Por
exemplo, um paciente doente diagnosticado com câncer erroneamente é “menos
problemático” que outro diagnosticado sem câncer, mas que realmente apresenta a
doença. Um método alternativo para a avaliação do desempenho desses algoritmos é a
análise de curvas ROC (Relative Operating Characteristic), a qual representa o
compromisso entre a sensibilidade no eixo y e a taxa de falsos positivos no eixo x
( 1 − Es ), conforme mostra a Figura 9.
49 / 101
SE
SE
1
A
1
B
C
D
1 − Es
Es
0
0
Figura 9: Curva ROC ( S E vs. 1 − Es )
Para conjuntos de dados com classes desbalanceadas, uma medida de
desempenho mais apropriada deve desasociar os erros, ou acertos, ocorridos para cada
classe. A partir da Tabela de matriz de confusão é possível derivar quatro medidas de
desempenho que medem o desempenho de classificação nas clases negativa e positiva
independentemente, elas são:
Taxa de falso negativo. É a porcentagem de casos positivos classificados
incorretamente como pertencentes à classe negativa
TFN =
FN
VP + FN
(11)
Taxa de falso positivo. É a porcentagem de casos negativos classificados
incorretamente como pertencentes à classe positiva
TFP =
FP
FP + VN
(12)
Taxa de verdadeiro negativo. É a porcentagem de casos negativos classificados
corretamente como pertencentes à classe negativa;
TV N =
VN
= 1 − TFP
FP + VN
(13)
Taxa de verdadeiro positivo. É a porcentagem de casos positivos classificados
corretamente como pertencentes à classe positiva.
TV P =
VP
= 1 − TFN
VP + FN
(14)
Essas quatro medidas de desempenho possuem a vantagem de serem
independentes do custo e das probabilidades a priori das classes. O principal objetivo de
qualquer classificador é minimizar as taxas de falso positivo e de falso negativo, ou, de
50 / 101
forma similar, maximizar as taxas de verdadeiro positivo e verdadeiro negativo.
Entretanto, para a maioria das aplicações do mundo real, existe uma relação de perda e
ganho entre FN e FP, ou, de forma similar, entre VN e VP.
Conforme apresentado na Figura 9, a curva ROC é uma curva da sensibilidade
em função da especificidade e pode ser utilizada para analisar a relação entre FN e FP,
ou VN e VP para um determinado classificador. Rebatido, esse gráfico se transforma na
curva ROC, mostrada à direita da Figura 9, em que a taxa de verdadeiros positivos é
traçada em função da taxa de falsos negativos. A situação ideal é aquela em que há
somente verdadeiros positivos, representada pela linha reta horizontal A . A diagonal
D , por outro lado, indica a situação em que a escolha é aleatória. As curvas B e C
representam situações mais comuns, em que B representa um melhor resultado quando
comparada a C . A partir de um gráfico ROC é possível calcular uma medida geral de
qualidade, a área sob a curva (AUC - Area Under the ROC Curve). A AUC é a fração da
área total que se situa sob a curva ROC. Essa medida é equivalente a diversas outras
medidas estatísticas para a avaliação de modelos de classificação (Hand, D. and Till, R.,
2001). A medida AUC efetivamente fatora o desempenho do classificador sobre todos
os custos e distribuições.
Um ponto em um gráfico ROC domina outro se esse ponto estiver acima e a
esquerda do outro, isto é, tem uma taxa mais alta de verdadeiros positivos e uma taxa
mais baixa de falsos positivos. Se um ponto B domina um ponto C , B terá um menor
custo esperado do que C para todos os possíveis custos e distribuições de classes. Um
modelo de classificação k domina outro modelo w se todos os pontos da curva de w
estão abaixo da curva k . Caso isso não ocorra, o melhor modelo para uma faixa de
valores pode ser derivado utilizando-se o método Convex Hull (Fawcett, T. 2004).
Convex hull (casca convexa) é a envoltória dos pontos das curvas dos classificadores em
um gráfico ROC. Um classificador é potencialmente ótimo se, e somente se, sua curva
ROC se sobrepõe à Convex Hull. Em resumo, um gráfico ROC permite ao analista
analisar a dominância de um modelo em relação aos demais. Por outro lado, a utilização
do método Convex Hull permite escolher modelos potencialmente ótimos e também
permite identificar faixas de dominância.
Além das curvas ROC e da área sobre a curva são utilizadas na literatura
diversas outras métricas, entre elas:
51 / 101
Recall (R) é equivalente à taxa de verdadeiros positivos ( TVP ) e denota a razão entre o
número de exemplos positivos corretamente classificados e o número total de exemplos
positivos originais:
R = S E = TV P =
VP
VP + FN
(15)
Precision (P) corresponde à razão entre o número de exemplos positivos corretamente
classificados e o número total de exemplos identificados como positivos pelo
classificador:
P=
VP
VP + FP
(16)
Fmeasure considera somente o desempenho para a classe positiva. Ela é calculada a
partir das métricas adotadas em Recuperação de Informação: Recall e Precision (Tan,
P. N. et al., 2005):
Fmeasure =
(1 + β ) ⋅ R ⋅ P
β2 ⋅R+P
(17)
Onde β é usado para ajustar a importância relativa entre Recall e Precision.
Tipicamente, β = 1 .
Gmean foi proposta por Kubat, M. et al. (1998) e corresponde à média geométrica entre
a sensibilidade ( S E ) ou taxa de verdadeiros positivos ( TV P ) e especificidade ( E S ) ou
taxa de verdadeiros negativos ( TV N ):
Gmean = S E ⋅ E S ou Gmean = TV P ⋅ TV N
(18)
Gmean mede o desempenho equilibrado de um classificador em relação às taxas de
acertos de ambas as classes (Sun, Y. et al., 2007). Valores elevados de Gmean refletem
taxas de acerto elevadas e equilibradas para ambas as classes.
Curvas Precision-Recall (PR) medem o desempenho de classificadores treinados com
dados altamente desbalanceados. Diferentemente das curvas ROC, que na presença de
conjuntos de dados altamente desbalanceados podem apresentar uma visão um tanto que
otimista da evolução do desempenho de classificadores, as curvas PR podem apresentar
uma representação mais informativa deste desempenho (Davis, J. and Goadrich, M.,
2006) por identificar mudanças tanto no número de falsos positivos quanto de
verdadeiro positivos.
52 / 101
Curvas de Custo (Cost Curves) é outra alternativa às curvas ROC uma vez que estas
últimas falham ao não prover intervalos de confiança para o desempenho de
classificadores e não serem habilitadas para inferir a significância estatística de
desempenho de diferentes classificadores. Falham também por assumirem custos
(perdas) iguais para os diferentes erros de classificação, visando assim à minimização
de um critério que corresponde à probabilidade do erro global de classificação (ou taxa
de erro esperado) (Holte, R. C. and Drummond, C., 2006).
4.4
Conjuntos desbalanceados e aprendizado sensível ao custo
Como mencionado anteriormente, um classificador induzido a partir de um
conjunto de dados com classes desbalanceadas possui, tipicamente, uma taxa de erro
baixa para a classe majoritária, e uma taxa de erro demasiadamente alta para a classe
minoritária. O problema surge quando o custo de classificação incorreta da classe
minoritária é muito superior ao custo de classificação incorreta da classe majoritária.
Nessa situação, o desafio está em classificar precisamente a classe minoritária, com o
objetivo de reduzir o custo total do classificador.
Um sistema de aprendizado sensível ao custo pode ser utilizado em aplicações
nas quais os custos de classificação incorreta são conhecidos. Sistemas de aprendizado
sensíveis ao custo visam reduzir o custo de classificação incorreta dos exemplos, ao
invés do erro de classificação. No entanto, alguns sistemas de aprendizado não são
capazes de integrar informações de custo em seu processo de aprendizado. Entretanto,
existe um método simples e geral para tornar qualquer sistema de aprendizado sensível
ao custo para um problema de duas classes (Breiman, L. et al., 1984). Esse método
baseia-se em modificar a distribuição das classes no conjunto de treinamento de forma a
aumentar o número de exemplos da classe mais custosa. Suponha que a classe positiva é
cinco vezes mais custosa que a classe negativa. Se o número de exemplos positivos é
artificialmente aumentado por um fator de cinco, então o sistema de aprendizado,
visando reduzir o erro de classificação, irá induzir um classificador que tende evitar
cometer erros na classe positiva, uma vez que qualquer erro nessa classe é penalizado
cinco vezes mais.
Elkan, C. (2001) demonstra uma alternativa de como encontrar a proporção de
exemplos positivos e negativos de forma a fazer classificações sensíveis ao custo ótimas
para um problema de duas classes. Ainda, Domingos, P. (1999) apresenta um método
geral para fazer qualquer sistema de aprendizado sensível ao custo com a vantagem de
53 / 101
ser aplicável a problemas que possuem qualquer número de classes. Dessa forma,
classes desbalanceadas e aprendizado sensível ao custo estão relacionados entre si.
Uma forma de aprender com conjuntos com classes desbalanceadas é treinar um
sistema sensível ao custo com o custo da classe minoritária maior que o da classe
majoritária. Outra forma de fazer com que um sistema de aprendizado se torne sensível
ao custo é alterar intencionalmente a distribuição das classes no conjunto de
treinamento.
Uma grande parte dos métodos que tratam conjuntos de dados com classes
desbalanceadas visa melhorar o desempenho da classe minoritária por meio do
desbalanceamento de classes do conjunto de dados. Dessa forma, a classe minoritária se
torna mais custosa e espera-se que ela seja melhor classificada. Desse ponto de vista,
dois cenários podem ser identificados. No primeiro, existe uma grande quantidade de
dados e o problema pode ser entendido como qual proporção de exemplos positivos e
negativos é melhor para o aprendizado. No segundo, com os dados escassos, como
descartar exemplos negativos ou duplicar exemplos positivos sem introduzir distorções
no processo de aprendizado. O problema de determinar qual proporção de exemplos
positivos e negativos é a melhor para o aprendizado vai além do problema de aprender
com conjuntos de dados com classes desbalanceadas. A comunidade de AM tem
assumido implicitamente que as distribuições das classes que ocorrem naturalmente são
as melhores para o aprendizado. Entretanto, uma vez que o aprendizado com as
distribuições naturais das classes tem fornecido resultados ruins para conjuntos de dados
com classes desbalanceadas, essa suposição começou a ser estudada mais a fundo. A
princípio, a proporção de classes que fornece o melhor resultado no aprendizado varia
entre os diferentes conjuntos de dados. Devido à complexidade dos dados e dos
algoritmos que analisam esses dados, não é possível dizer previamente qual distribuição
de classes irá fornecer o melhor resultado. Entretanto, é possível estabelecer algumas
diretrizes gerais.
Weiss, S. M. e Provost, F. (2001) realizaram um estudo sobre a influência da
proporção de exemplos positivos e negativos no aprendizado. Esse estudo analisa o
cenário no qual existe uma grande quantidade de dados, entretanto, por motivos de
restrição computacional, o conjunto de treinamento deve ser limitado a um certo
número de exemplos. Nesse cenário, qual distribuição de classes deve ser a melhor para
o aprendizado?
Utilizando a AUC como medida de desempenho, Weiss e Provost
mostraram que a distribuição ótima das classes geralmente contém entre 50% e 9% dos
54 / 101
exemplos da classe minoritária. Também, alocar 50% dos exemplos de treinamento para
a classe minoritária, mesmo quando não fornece resultados ótimos, apresenta resultados
que não são piores, e que frequentemente são superiores, aos resultados obtidos com a
distribuição natural das classes.
4.5
Métodos para balanceamento de classes
Na abordagem de pré-processamento de dados, o objetivo do balanceamento é
modificar por meio de mecanismos de reamostragem do conjunto de treinamento, os
dados no espaço de entrada. Estes incluem sobreamostragem da classe minoritária,
subamostragem da classe majoritária ou a combinação de ambas as técnicas.
A sobreamostragem é baseada na replicação de exemplos preexistentes
(sobreamostragem com substituição) ou na geração de dados sintéticos. No primeiro
caso, a seleção de exemplos a serem replicados pode ser aleatória (sobreamostragem
aleatória) ou direcionada (sobreamostragem informativa). Com relação à geração de
dados sintéticos, a técnica de interpolação é comumente usada, como por exemplo, no
conhecido método SMOTE (Synthetic Minority Oversampling Technique) proposto em
Chawla, N. V. et al. (2002).
Já a subamostragem envolve a eliminação de exemplos da classe majoritária. Os
exemplos a serem eliminados podem ser escolhidos aleatoriamente (subamostragem
aleatória) ou a partir de alguma informação a priori (subamostragem informativa). O
algoritmo OSS (One-Sided Selection), proposto em Kubat, M. e Matwin, S. (1997), é
considerado um exemplo de subamostragem informativa. Existe também a combinação
desses métodos com técnicas clássicas de limpeza de dados, tais como a CNN (Hart, P.
E., 1968), ENN (Wilson, D., 1972) e Tomek links (Tomek, I., 1976) e suas variações
como CNL (Laurikkala, L., 2001).
Apesar das técnicas de subamostragem e sobreamostragem possuírem o mesmo
propósito, elas introduzem diferentes características ao novo conjunto de treinamento
que podem algumas vezes, dificultar o aprendizado (Drummond, C. and Holte, R.,
2003; He, H. and Garcia, E. K. 2009; Mease, D. et al., 2007). Por exemplo, no caso de
subamostragem aleatória, o principal problema é a possível perda de informação
causada pela eliminação de exemplos representativos da classe majoritária.
Subamostragem informativa tenta solucionar esse problema por eliminar uma fração
menos representativa como, por exemplo, exemplos redundantes, ruidosos e/ou
55 / 101
próximos à fronteira de separação entre as classes. Cabe ressaltar, entretanto, que a
escolha de critérios adequados para selecionar esses exemplos não é uma tarefa fácil.
Dentre os principais métodos de reamostragem na literatura podemos citar:
4.5.1 OSS (One-Sided Selection)
Originalmente proposto por Kubat, M. e Matwin, S. (1997) e também conhecido
como Seleção Unilateral, é um método de subamostragem informativa. Após selecionar
um subconjunto representativo da classe majoritária e combiná-lo com todos os
exemplos da classe minoritária, o método OSS usa técnicas de limpeza para obter
agrupamentos bem definidos para ambas as classes. A combinação de exemplos da
classe minoritária é obtida pela manutenção dos exemplos da classe minoritária, uma
vez que tais exemplos são muito raros para serem perdidos, ainda que alguns deles seja
ruído. O subconjunto representativo da classe majoritária é obtido através da remoção
criteriosa de exemplos pertencentes à classe majoritária. Tal remoção criteriosa consiste
em detectar e remover, através de heurísticas, exemplos que são menos confiáveis.
Essas heurísticas tornam-se mais eficazes quando os exemplos são divididos em quatro
grupos distintos:
1. Exemplos rotulados erroneamente (ruído). Por exemplo, os exemplos da classe
majoritária (‘+’) situados à direita, no canto superior, da região de decisão da Figura 10;
2. Exemplos redundantes. Tais exemplos podem ser representados por outros exemplos
que já estão no conjunto. Por exemplo, os exemplos que estão longe da borda de
decisão, como os localizados na parte inferior esquerda da Figura 10;
3. Exemplos próximos à borda de decisão. Esses exemplos são pouco confiáveis, pois
mesmo uma pequena quantidade de ruído em alguns valores de seus atributos pode
colocá-los na região de decisão errada;
4. Exemplos seguros. São aqueles que não estão muito próximos da borda de decisão
nem muito distantes dela, esses exemplos devem ser mantidos para o aprendizado.
56 / 101
12
Exemplos positivos
ruído
10
8
seguros
x2
6
4
redundantes
2
0
próximos a borda de
decisão
-2
-2
0
2
4
6
8
10
12
x1
Figura 10 – Grupos de exemplos descritos no método OSS (Matlab, 2008)
A técnica de Seleção Unilateral busca criar um conjunto de treinamento que
consista somente de exemplos seguros. Desta forma, exemplos da classe majoritária
incorretamente rotulados, exemplos muito próximos à borda de decisão e exemplos
redundantes devem ser eliminados. Exemplos situados na borda de decisão e exemplos
incorretamente rotulados podem ser detectados através do conceito de ligações Tomek
(Tomek, I., 1976), conforme definido a seguir:
Dados dois exemplos x e y , de forma que cada um pertença a uma classe
diferente. Seja a distância entre x e y denotada por d ( x, y ) , então o par ( x, y ) é
chamado de ligação Tomek caso não exista um exemplo z tal que d ( x, z ) < d ( x, y ) ou
d ( y, z ) < d ( y, x) . Exemplos que participam de ligações Tomek ou estão próximos à
borda de decisão ou são ruído. A Figura 11 ilustra o novo conjunto de exemplos obtido
após a remoção de exemplos da classe majoritária que formam ligações Tomek no
conjunto original de exemplos da Figura 10.
57 / 101
12
Exemplos positivos
10
8
x2
6
4
2
0
-2
-2
0
2
4
6
8
10
12
x1
Figura 11 – Novo conjunto de dados após remoção de ligações Tomek (Matlab, 2008)
Para remover exemplos redundantes pode-se ainda criar um subconjunto
consistente, C , do conjunto original de exemplos S . Por definição, um conjunto C ⊂ S
é consistente com S se, utilizando-se o algoritmo 1-vizinho-mais-próximo (1-NN) ele
corretamente classifica os exemplos de S (Hart, P. E., 1968). Essa abordagem é
geralmente conhecida como regra do vizinho mais próximo condensada (Condensed
Nearest Neighbor Rule - CNN). Como o objetivo não é encontrar o menor subconjunto
consistente possível, mas apenas fazer com que o número de exemplos da classe
majoritária diminua, foi proposta em Kubat, M. e Matwin, S. (1997) uma variação da
técnica original criada em Hart, P. E. (1968) para encontrar subconjuntos consistentes.
A ideia é selecionar aleatoriamente um exemplo da classe majoritária juntamente com
todos os exemplos da classe minoritária e movê-los para um conjunto C . Então, utilizase uma regra 1-NN com os exemplos em C para novamente classificar os exemplos em
S . Todos os exemplos de S que forem incorretamente classificados são movidos para
C.
4.5.2 SMOTE (Synthetic Minority Oversampling Technique)
Originalmente proposto por Chawla, N. V. et al. (2002), o método SMOTE é
baseado em sobreamostragem informativa e cria novos exemplos da classe minoritária
por meio da interpolação de exemplos da classe minoritária que se encontram próximos.
58 / 101
Especificamente, para um subconjunto S ' pertencente a S , considere o k-
vizinho-mais-próximo para cada exemplo x i pertencente a S ' , para algum número
inteiro especificado k ; o k-vizinho-mais-próximo é definido como elemento de S ' se a
distância euclidiana entre ele e x i em consideração exibir uma menor magnitude ao
longo do espaço n-dimensional x . Para criar um exemplo sintético, seleciona-se
aleatoriamente um dos seus k-vizinhos-mais-próximos, então multiplica a diferença
entre o correspondente valor por um número aleatório entre [0,1], e finalmente, adiciona
este novo valor ao subconjunto S ' conforme a Equação 19:
x = xi + ( yi − xi ) * δ
(19)
Onde xi ∈ S ' é um exemplo da classe minoritária em consideração; y i é um dos
seus k-vizinhos-mais-próximos de x i ; y i ∈ S ' e; δ ∈ [0,1] é um número aleatório.
Portanto, o resultado do exemplo sintético gerado de acordo com a Equação 19 é um
ponto ao longo da reta que une o ponto x i em consideração com um dos k-vizinhos-
mais-próximos escolhidos aleatoriamente (He, H. and Garcia, E. A., 2009).
O método SMOTE é encontrado na literatura também em combinação com
métodos de limpeza. Em Batista, G. E. A. P. A. et al. (2004), a combinação dos
métodos SMOTE e Tomek links justifica-se pelo fato de que o SMOTE não considera a
vizinhança em relação à outra classe durante o processo de interpolação. Assim ele
tende a aumentar o grau de sobreposição para elementos ruidosos e próximos à borda.
Com o objetivo de melhorar a definição dos agrupamentos de dados no conjunto de
treinamento, foi proposta a aplicação do método para a identificação de ligações Tomek
após a aplicação do método SMOTE. Diferentemente da aplicação de ligações Tomek
como método de subamostragem, nesse caso (como o conjunto de dados foi
previamente balanceado com exemplos “sintéticos”) são removidos exemplos de ambas
as classes.
Também em Batista, G. E. A. P. A. et al. (2004) é proposta uma combinação
dos métodos SMOTE e ENN (Wilson, D., 1972) justificando-se também pelo fato de
que o SMOTE não considera a vizinhança em relação à outra classe durante o processo
de interpolação. Entretanto, ENN tende a remover mais exemplos do que as ligações
Tomek, promovendo uma maior limpeza no conjunto de dados. Similarmente ao método
SMOTE + Tomek Links, ENN é utilizado para remover exemplos de ambas as classes.
Então qualquer exemplo cuja classificação seja diferente de seus três vizinhos mais
59 / 101
próximos é eliminado. O método ENN faz subamostragem dos dados de forma contrária
à maneira em que é feito a subamostragem no método CNN (Hart, P. E., 1968) e
consiste na eliminação de todos os objetos que são mal classificados por seus k-
vizinhos-mais-próximos (KNN). O método ENN faz subamostragem do conjunto de
entrada S retirando todo caso Ei ∈ S cuja classe diverge da classe predita pelos k-
vizinhos-mais-próximos. Se nem todos os k-vizinhos são da mesma classe, a
determinação da classe predita pode ser feita pela classe mais frequente ou por uma
ponderação das classes em função da importância relativa de cada uma delas. Esse
processo remove tanto os casos ruidosos quanto os casos limítrofes, de forma a
propiciar um limiar de decisão ao mesmo tempo em que a vizinhança da classe de
interesse é limpa.
Outras combinações também pode ser encontrada na literatura como também em
Batista, G. E. A. P. A. et al. (2004) que utiliza CNN + Ligações Tomek invertendo
portanto os passos da Seleção Unilateral. Neste caso, foi identificado que ligações
Tomek são computacionalmente custosas e ela é mais efetiva se aplicada em um
conjunto reduzido. Cabe ainda citar outros métodos listados na literatura a respeito de
reamostragem baseada em sobreamostragem e subamostragem com limpezas de dados,
entre eles:
Cluster-based Oversampling. Nickerson, A. et al. (2001) propõem uma abordagem para
minimizar o problema de classes e exemplos raros. A abordagem proposta sugere a
utilização de sobreamostragem não somente da classe minoritária, mas também dos
exemplos raros. A ideia é agrupar os dados de treinamento em clusters e, então,
balancear a distribuição de seus exemplos. Inicialmente utilizou-se a técnica não
supervisionada de agrupamento PDDP (Boley, D. L., 1997) para formar os grupos de
cada classe e depois fazer sobreamostragem de cada um desses grupos. De acordo com
Weiss, S. M. (2004), casos raros não são facilmente identificáveis, mas métodos de
aprendizagem não supervisionada como clustering, ajudam na identificação desses
casos, sendo que eles podem se apresentar como pequenos clusters dentro de uma
classe. Em classificadores, casos raros potencialmente se apresentam como pequenos
disjuntos, que são conceitos aprendidos que cobrem poucos casos do conjunto de
treinamento.
60 / 101
Cleaning Nearest Rule (CNL). O método CNL de Laurikkala, J. (2001) utiliza a ideia
do método ENN (Wilson, D. 1972) para encontrar (através de subamostragem) os dados
ruidosos que não pertencem à classe de interesse e, logo em seguida, fazer limpeza do
limiar da vizinhança da classe de interesse. Surgiu da observação de que o método de
limpeza CNN (Hart, P. E., 1968) utilizado no método de subamostragem OSS (Kubat,
M. and Matwin, S., 1997) era sensível a ruídos. Laurikkala, J. (2001) atribuiu essa
sensibilidade ao erro de classificação ocasionado pelo algoritmo 1-NN do OSS que
adicionava ruídos ao conjunto consistente. Mesmo removendo os casos ruidosos com
Tomek links, os resultados com OSS não foram satisfatórios possivelmente por causa do
CNN.
Weighted Wilson’s Editing (WWE). Intensifica o método ENN eliminando um número
maior de exemplos da classe majoritária cujo rótulo difere da maioria de seus k-
vizinhos-mais-próximos (Barandela, R. et al., 2004).
Balance Cascade. O algoritmo Balance Cascade, por sua vez, usa uma estratégia
iterativa de geração de um ensemble de classificadores para a escolha dos exemplos a
serem removidos (Liu, X. Y. et al., 2009).
4.6
Considerações finais
Em AM diversos fatores podem influenciar no desempenho de um classificador
induzido por um sistema de aprendizado. Entre eles, um fator que pode levar a um
desempenho inapropriado e que tem recebido relativamente pouca atenção da
comunidade ocorre quando existe uma grande diferença na quantidade de exemplos de
cada classe. Neste caso, o sistema de aprendizado pode encontrar dificuldades no
aprendizado do conceito referente à classe representada pela minoria dos exemplos.
Para muitos domínios de aplicação, como em diagnóstico de doenças raras, é comum
que exista uma grande desproporção entre a quantidade de exemplos rotulados em cada
uma das classes presentes. Nesses casos, é muito simples projetar um classificador que
possua alta precisão, através de um sistema que responda com a classe majoritária para
qualquer novo caso. Entretanto, classificar precisamente a classe minoritária é
frequentemente o maior objetivo de tais aplicações.
61 / 101
5
Detecção de Bordas de Novidade (NBD)
Apesar das técnicas clássicas de reamostragem por sobreamostragem e
subamostragem
possuírem
o
mesmo
princípio,
elas
geralmente
introduzem
características diferentes ao novo conjunto de treinamento que podem dificultar o
aprendizado (Drummond, C. and Holte, R., 2003). No caso de subamostragem aleatória,
por exemplo, o principal problema é a possível perda de informação causada pela
exclusão de exemplos representativos da classe majoritária. A subamostragem
informativa tenta solucionar esse problema eliminando uma parcela menos
representativa como, por exemplo, exemplos redundantes, ruidosos e/ou próximos à
fronteira de separação entre as classes. No caso de sobreamostragem, nem sempre o seu
uso melhora de forma significativa o reconhecimento da classe minoritária (Breiman, L.
et al.,1984; Chawla, N. V. et al., 2002; Mease, D. et al., 2007).
O aumento da
variância, por exemplo, causado por técnicas de geração de dados sintéticos que não
consideram a vizinhança entre as classes, como é o caso do método SMOTE (He, H. and
Garcia, E. A., 2009) pode trazer problemas. Adaptações têm sido propostas para guiar o
processo de interpolação adotado tendo em vista superar essa limitação (Han, H. et al.,
2005; He, H. et al., 2008) e produzir determinadas “limpezas” nos dados tais como
Tomek Links (Tomek, I. 1976) e ENN (Wilson, D., 1972).
Alguns estudos experimentais utilizando técnicas de reamostragem sobre RNA
foram propostos com melhora significativa (Huang et al., 2006; Japkowicz, N., 2000)
(Lan, J., Hu, M.Y., Patuwo, E. and Zhang, G.P., 2010) (Zhou, Z. H. and Liu, X. Y.,
2006) do desempenho de classificação sobre dados desbalanceados e também com
pouca melhora significativa (Alejo, R. et al., 2006; Khoshgoftaar, T. M. et al., 2010).
Embora essas estratégias possam produzir modelos com elevadas taxas de
acurácia global, elas frequentemente tendem a prejudicar a identificação de exemplos
pertencentes a grupos raros que, na maioria dos casos, representam os grupos de
interesse. Esses grupos ou exemplos raros também são conhecidos como novidades. E
no contexto deste trabalho, a habilidade de identificar esses casos raros ou simplesmente
novidades dá-se o nome de Detecção de Novidade (DN)1. DN é a capacidade que tem
um algoritmo de identificar novos perfis até então desconhecidos, na medida em que são
recebidos novos dados (Alberto, B. L. A., 2007). Na abordagem tradicional, o
1
Em inglês, Novelty Detection
62 / 101
classificador só pode atribuir o exemplo a uma das classes que ele conhece. Essa
limitação pode levar a decisões inadequadas em uma série de situações nas quais o
modelo aprendido não mais representa a atual distribuição dos dados em classes. O
conceito de DN pode auxiliar na solução desse problema, identificando situações em
que um tratamento alternativo se faz necessário.
Do ponto de vista de AM, o ponto central do problema de DN está na maneira
pela qual o classificador distingue um exemplo que pertence a um perfil normal (classes
conhecidas), bem adequado ao modelo, de outro que apresenta características novas,
diferenciando-as, portanto de ruídos. A descoberta de novos perfis nos dados pode
apontar para o surgimento de novas classes, alertar para mudanças de regime, ou ainda
indicar a presença de dados anômalos ou incorretos. Várias abordagens têm sido
propostas para detectar novidade por meio de diversas técnicas de AM (Albrecht et al.,
2000), (Bishop, C. M., 1994), (Japkowicz, N. et al., 1995), (Markou, M. and Singh, S.,
2003a,b), (Ypma, A. and Duin, R. P. W., 2000), (Wong, M. L. D. et al., 2005),
(Zorriassatine, F. et al., 1995).
Esta seção está organizada da seguinte forma: na seção 5.1 é apresentada a
formulação matemática por traz do novo método intitulado NBD. Na seção 5.2 são
apresentados os resultados dos experimentos a contar na subseção 5.2.1 com o 1º
experimento com conjuntos de dados sintéticos gerados a partir de duas distribuições
gaussianas unidimensionais e a representação do modelo de classificação ótimo de
Bayes para uma tarefa de classificação binária. Esse experimento buscou esclarecer os
motivos pelas quais nem sempre o desbalanceamento de classe é o responsável pela
piora no desempenho de algoritmos de aprendizagem utilizados para tarefas de
classificação. Os resultados experimentais mostraram que a complexidade do conjunto
de dados é também medida fortemente pelo grau de sobreposição entre as classes. Na
subseção 5.2.2, os resultados do 2º experimento são comentados e mostram o
comportamento de métodos da literatura que promovem o balanceamento de dados com
sobreposição entre as classes em termos das métricas de avaliação de desempenho AUC
e Gmean. Por fim, na seção 5.2.3, a realização do 3º e último experimento apresenta a
eficiência das técnicas investigadas e do algoritmo que implementa o método NBD
proposto. É então proposto um estudo experimental com onze bases de dados, um
classificador base e dois métodos da literatura para confrontar com o algoritmo NBD.
Testes estatísticos acompanham a análise dos resultados de classificação após a
utilização dos métodos de balanceamento.
63 / 101
5.1
Formulação do método NBD
Tendo em vista a extrema dependência da distribuição dos dados de treinamento
para que melhores resultados sejam alcançados em problemas de classificação cujas
classes possuam elevado grau de sobreposição e desbalanceamento, a presença de ruído
precisa ser considerada. Na maior parte das técnicas de AM, esse problema é tratado por
meio de um parâmetro que flexibiliza a descrição, permitindo que uma fração dos
exemplos do conjunto de treinamento fique além das fronteiras de decisão (Tax, D. M.,
2001). Para minimizar esse problema e de acordo com o contexto deste trabalho é então
proposto o método de Detecção de Bordas de Novidade (NBD).
O método NBD é baseado em subamostragem e sobreamostragem guiada pela
informação da densidade em torno dos exemplos de treinamento inter-classe e intraclasse. Essa informação torna possível para o algoritmo NBD identificar ruídos e casos
raros (novidades) em regiões de menor densidade e também exemplos que pertencem à
região de sobreposição entre as classes (próximas à superfície de separação). O processo
de eliminação e síntese de exemplos dessas regiões melhora a distribuição dos
conjuntos de treinamento para que um classificador possa estimar uma melhor
superfície de separação. O NBD possui parâmetros que permite ajustar a intensidade do
processo de reamostragem de acordo com o grau de desbalanceamento e sobreposição
entre as classes.
Para obter a informação sobre a densidade, o método NBD define um grau de
importância para cada exemplo do conjunto de treinamento. Esta informação é
calculada a partir dos k-vizinhos-mais-próximos de acordo com a distância de
Mahalanobis do exemplo avaliado conforme a Equação 20:
ig ( xic ) =
Cc
C p + Cn
,
(20)
onde xic corresponde ao i-ésimo exemplo de treinamento da classe c , podendo c = p
(classe minoritária, positiva) ou c = n (classe majoritária, negativa). C p corresponde ao
número de vizinhos positivos de xic e Cn ao número de vizinhos negativos. Para um
dado exemplo positivo, ig ( xip ) evolui a proporção de exemplos positivos entre os k-
vizinhos-mais-próximos de xip . Portanto, se ig ( xip ) ≈ 1 , pode-se afirmar que xip está na
região com alta densidade de exemplos positivos. A mesma ideia vale para o caso de
exemplos negativos.
64 / 101
Para exemplos da classe majoritária xin , o grau de importância ig ( xin ) é
utilizado para encontrar exemplos ruidosos que ocupam áreas de sobreposição entre as
classes e também isolar exemplos pertencentes a regiões da classe minoritária. Assim, o
método NBD estabelece uma regra de detecção e exclusão desses exemplos. Esta regra
depende de um parâmetro ou limiar max θ para ajustar a intensidade do processo de
reamostragem de acordo com o grau de desbalanceamento e sobreposição entre as
classes:
Se ig ( x in ) < max θ então xin é excluído
Se ig ( x in ) ≥ max θ então xin não é excluído
O limiar max θ é definido no intervalo de [0,1] e determina a intensidade do
processo de reamostragem. Quanto mais alto o valor de max θ , mais exemplos da
classe negativa serão excluídos. E nos casos de altos níveis de desbalanceamento e
sobreposição entre classes, valores de max θ próximos a 1 são sugeridos dado que é
provável a existência de um grande número de exemplos negativos em regiões
pertencentes à classe positiva. Já em situações cujos níveis de desbalanceamento e
sobreposição entre classes são menores, valores de max θ próximos a 0 são
recomendados.
Para exemplos da classe minoritária xip , o grau de importância ig ( xip ) é também
utilizado para sintetizar novos exemplos. Se ig ( xip ) é considerado válido pelo NBD, um
p
novo exemplo x i é criado da seguinte forma:
a) Para cada atributo contínuo cf, seu valor é calculado baseado na média dos
cf-valores dos Cp-vizinhos-mais-próximos e o exemplo xip ;
x
p
i
∑
(cf ) =
Cp
j =1
x jp (cf ) + xip (cf )
C p +1
(21)
b) Cada atributo nominal nf assume o valor mais frequentemente observado entre
os nf-valores dos Cp-vizinhos-mais-próximos e o exemplo xip ;
c) Caso contrário, se ig ( xip ) não é válido, xip é considerado ruído ou outlier, e um
novo exemplo não poderia ser criado em sua vizinhança. A regra para os
65 / 101
exemplos positivos é baseada no parâmetro ou limiar min θ e é definida da
seguinte forma:
Se ig ( x ip ) < min θ então x ip não é excluído
p
Se ig ( xip ) ≥ min θ então x i é criado
O parâmetro min θ define o grau de validade dos exemplos positivos no espaço
de entrada e é similar ao max θ , tendo ambos os valores entre [0,1] . Quanto menor for o
limiar min θ , maior será a probabilidade de exemplos positivos localizados em regiões
de sobreposição entre as classes serem considerados válidos e utilizados para gerar
p
novos exemplos sintéticos x i . O limiar min θ , no entanto não deve ser muito próximo
de 0 a fim de assegurar que exemplos distantes da superfície de separação pertencentes
à classe positiva não gerem novos exemplos sintéticos. A cada iteração do algoritmo
NBD, um novo exemplo de treinamento é analisado. O algoritmo termina quando as
classes estão balanceadas, ou seja, a proporção de exemplos entre as classes é igual. O
efeito causado pelo algoritmo em conjuntos de dados desbalanceados pode ser
visualizado na Figura 12. Exemplos majoritários (‘o’) em regiões onde prevalecem
exemplos minoritários (‘+’) são eliminados. Partindo do gráfico à esquerda para o
central é mostrado o resultado da aplicação da sobreamostragem sobre os exemplos da
classe minoritária. O gráfico à direita representa o resultado da subamostragem sobre a
classe majoritária, a partir do conjunto de dados resultantes do processo anterior de
sobreamostragem.
12
12
12
10
10
10
8
8
8
6
6
6
4
4
4
2
2
2
0
0
0
-2
-2
-2
0
2
4
6
8
10
12
-2
-2
0
2
4
6
8
10
12
-2
0
2
4
6
8
10
12
Figura 12 – Visualização do processo de reamostragem do NBD (Matlab, 2008)
66 / 101
A distância de Mahalanobis foi a medida de distancia escolhida, diferentemente
da distância Euclidiana encontrada nos métodos dos k-vizinhos-mais-próximos
investigados na literatura (Barandela, R. et al., 2004; Batista, G. E. A. P. A. et al., 2004;
Kubat, M. and Matwin, S., 1997; Zhang, J. and Mani, I., 2003). Essa decisão corrige
algumas das limitações da distância euclidiana, pois leva em consideração
automaticamente a escala dos eixos coordenados e leva em consideração a correlação
entre as características. Entretanto, dependendo do tamanho do conjunto de treinamento,
as matrizes de covariância podem ser difíceis de computar (complexidade O 2 ) pois
cresce de forma quadrática com o número de características.
A distância de Mahalanobis foi utilizada para medir a distância entre um
exemplo
xic
e uma classe (cluster) de exemplos cuja média é dada por
µc = {µ1 , µ 2 , µ3 ,..., µ n } e que possua uma matriz de covariância dada por
∑
. Neste
caso, a distância é dada pela Equação 22:
d (i, c) = ( xic − µc )T ∑ ( xic − µc )
−1
(22)
Conceitualmente, é como se estivéssemos avaliando a pertinência de um
exemplo não só por sua distância ao centro da classe, mas também pela distribuição do
mesmo, determinando assim a distância do exemplo xic em termos de uma comparação
com o desvio padrão da classe. Quanto maior for o valor desta distância, maior o
número de desvios padrões que um exemplo esta distante do centro da classe, e menor
sua chance de ser um exemplo da mesma. A detecção de novidades é um dos usos mais
comuns da distância de Mahalanobis, pois um valor alto determina que um exemplo
esteja a vários desvios padrões do centro (já computadas todas as diferenças axiais) e,
por conseguinte, é provavelmente uma novidade.
5.2
Experimentos
A realização de experimentos com conjuntos de dados reais muitas vezes não é
adequada para fornecer resultados consistentes em termos de qual abordagem de
balanceamento de classes é melhor para determinado conjunto de dados. Isso ocorre
devido ao não conhecimento a respeito de como os dados foram gerados e, portanto na
dificuldade em se testar hipóteses específicas. A importância de se utilizar conjunto de
dados sintéticos neste caso está relacionada à facilidade de manipulação de suas
características tais como número de classes e atributos, quantidade de ruído,
67 / 101
distribuições, entre outros. Desta forma, facilitam-se os testes de hipótese, estudos
experimentais e análises de desempenho de classificação através da comparação com
outros métodos da literatura.
5.2.1 Experimento 1
Em tarefas de classificação binária (duas classes) é comum considerar que as
entradas x sejam vetores de características em algum espaço X ⊆ ℜ n e as saídas
assumam somente dois valores simbólicos, ou seja, y ∈Y = {0,1} , correspondendo a
duas classes. Assim, cada função arbitrária f (x) pertencente à classe de funções
f : ℜ n → {0,1} torna-se uma regra de decisão capaz de dividir o espaço de entrada x
em duas regiões disjuntas, denotadas por ℜ 0 e ℜ1 . A Figura 13 ilustra um problema de
classificação binária em que as densidades conjuntas das classes p( x, y = k ) são
representadas por distribuições unidimensionais. Uma regra de decisão f (x) divide o
espaço de entrada em duas regiões disjuntas, tal que X = ℜ 0 ∪ ℜ1 .
0.45
p(x,y=0)
0.4
f(x)
0.35
0.3
0.25
0.2
p(x,y=1)
0.15
0.1
0.05
x
0
8
10
12
Ro
14
16
18
20
R1
Figura 13 – Regra de decisão f (x) com espaço de entrada X = ℜ 0 ∪ ℜ1
A decisão sobre a classificação de um dado exemplo de entrada x(i ) é feita com
base no índice da região ℜ j do espaço de entrada em que x(i ) está localizado. O limite
entre as regiões de decisão é conhecido como superfície de decisão (ou separação)
(Cherkassky, V. and Mulier, F., 2007).
68 / 101
A Figura 14 resume os resultados da variação na proporção de exemplos
positivos vs. AUC para quatro diferentes distâncias entre os centros das classes. Em
relação ao ajuste da distância entre os centros das classes, esse parâmetro nos permite
controlar a quantidade de sobreposição entre as mesmas e, portanto a dificuldade de se
classificar corretamente cada exemplo. A Figura 15 resume os resultados da variação
dessa distância vs. AUC para quatro diferentes proporções de exemplos da classe
minoritária (50%; 16%; 9% e; 6,2%). Testes com diversas outras distâncias entre os
centros das classes mostraram-se similares às apresentadas na Figura 14 e, portanto
foram suprimidas para facilitar a interpretação gráfica. Considere a curva em que a
classe positiva está 3 unidades deslocada da classe negativa.
Variação da proporção de exemplos vs. AUC
1
0.9
1
3
6
9
A UC [% ]
0.8
0.7
0.6
0.5
0.4
0
2
4
6
8
10
12
Proporção de exemplos positivos [%]
14
16
18
20
Figura 14 – Variação na proporção de exemplos positivos vs. AUC
Observe que os modelos induzidos para essa distância têm um ótimo
desempenho, com AUC maior que 90%, mesmo que a proporção de exemplos da classe
minoritária seja somente 4,7% (equivalente a x = 20 no gráfico da Figura 14) dos casos.
Observe também que o desbalanceamento ocasiona pouca variação à AUC quando as
classes estão mais afastas (conjuntos cuja distância entre os centros de cada classe é de
3, 6 e 9 unidades), ou seja, quando há pouca sobreposição entre elas, além de apresentar
valores elevados de AUC (nestes casos, superiores a 90%). A maior variação de AUC é
percebida quando se tem mais sobreposição entre as classes, como pode ser visto
69 / 101
quando os centros de cada classe possuem valores iguais, independentemente da
variação na proporção de exemplos de cada classe ( 1 < x < 20 , que corresponde o
intervalo de 50% a 4,7% de desbalanceamento). Conjuntos de dados cujas classes estão
mais afastas (cuja distância entre os centros de cada classe é de 3, 6 e 9 unidades)
apresentam regiões onde o limiar de decisão θ apresenta maior AUC, otimizando
portanto a razão de verossimilhança (Equação 23):

1 se
f ( x) = 
0 caso
p( x | y = 1) > θ
p( x | y = 0)
contrário
(23)
Note que a razão entre as probabilidades a priori p( y = 1) / p( y = 0) das classes
está implícita no limiar de decisão θ (threshold). Assim, variar o limiar θ implica em
variar a razão entre as prioris. Portanto, o limiar θ controla a proporção de exemplos da
classe positiva corretamente classificados versus a proporção de exemplos da classe
negativa incorretamente classificados
Já na Figura 15, está representada a variação de distâncias entre os centros das
classes versus a AUC dos modelos induzidos pelo classificador ótimo de Bayes em
função de 4 diferentes proporções de exemplos (50%; 16%; 9% e; 6,2%).
Variação da proporção de exemplos vs. AUC
1
50%
16%
9%
6,2%
0.9
AUC[%]
0.8
0.7
0.6
0.5
0.4
0
2
4
6
Distância entre centróides
8
10
12
Figura 15 – Variação no centro (média) da classe minoritária vs. AUC
Pode ser observado que o pior desempenho em termos de AUC ocorre onde a
distância entre os centros das classes é igual a 0.5 (maior sobreposição). Neste caso, a
piora é significativamente alta em relação aos conjuntos de dados mais desbalanceados,
70 / 101
mas melhora conforme a distância entre os centros aumenta até o limiar de decisão θ
ótimo. A diferença entre o desempenho do algoritmo para conjuntos de dados com
distância entre os centros maior que 5 unidades e menor que 8 é estatisticamente
insignificante, independente de quantos exemplos pertencem à classe minoritária. Esses
resultados estão de acordo com a hipótese de que o problema de desbalanceamento
entre as classes é maior quando existe uma alta sobreposição entre as classes.
Trabalhos semelhantes investigados na literatura (Drummond, C. and Holte, R.,
2003) (Hulse, J. V.; Khoshgoftaar T. M.; Napolitano, M., 2007), (Cherkassky, V. and
Mulier, F. 2007), (Monard, M. e Batista, G. 2002), (Xu-Ying Liu, Jianxin Wu, and ZhiHua Zhou, 2008) também conduzem a esta conclusão de que o desbalanceamento entre
as classes nem sempre é o responsável pela piora no desempenho de algoritmos de
aprendizagem utilizados para tarefas de classificação. Nestes trabalhos, pôde-se concluir
que o problema é dependente da complexidade dos conjuntos de dados, descrita como a
quantidade de subgrupos em que as classes estão divididas, e da quantidade de
exemplos das classes.
Comparando-os com os resultados aqui relatados no primeiro experimento,
pode-se concluir, de forma similar, que nem sempre o desbalanceamento de classe é o
responsável pela piora no desempenho de algoritmos de aprendizagem utilizados para
tarefas de classificação. No entanto, com os resultados experimentais aqui apresentados
pode-se dizer que a complexidade do conjunto de dados é também medida fortemente
pelo grau de sobreposição entre as classes.
5.2.2 Experimento 2
Para uma melhor visualização dos resultados do segundo experimento foram
apresentados gráficos, em diferentes escalas, para AUC e Gmean médios para diversos
centroides. Como esperado, os valores da AUC (Figura 16a) e Gmean (Figura 16b) para
distâncias próximas a zero oscilam em torno de 50% (devido a variações aleatórias).
71 / 101
AUC vs. % de exemplos da classe negativa (k=0)
0.65
MLP+SUB+OVER
MLP+SMOTE
MLP+SUB
MLP
0.6
A U C [% ]
0.55
0.5
0.45
0.4
0
5
10
15
20
25
30
35
Proporção de exemplos da classe negativa [%]
(a)
G-mean vs. % de exemplos da classe negativa (k=0)
0.7
MLP+SUB+OVER
MLP+SMOTE
MLP+SUB
MLP
0.6
0.5
G -m e a n [ % ]
0.4
0.3
0.2
0.1
0
0
5
10
15
20
Proporção de exemplos da classe negativa [%]
25
30
35
(b)
Figura 16 – Proporção de exemplos da classe negativa vs. AUC: (a) e proporção vs.
Gmean (b), ambos para k = 0
72 / 101
No experimento, a maior influência do desbalanceamento entre as classes ocorre
quando a distância entre os centros é de 2 ( k = 2 ) conforme apresentado na Figura 17 e
na Figura 18. No caso da Figura 17 que considera a métrica Gmean, percebe-se uma
maior diferença entre a curva do classificador puro (MLP) e as curvas do mesmo
classificador após a aplicação dos métodos investigados. Para conjuntos de treinamento
altamente desbalanceados (proporção entre as classes de 1,54%, por exemplo), verificase que a Gmean para o classificador puro é igual a 0.4132 e 0.8320 em média para o
classificador balanceado com os métodos investigados (sendo que a subamostragem
aleatória apresenta resultados ligeiramente melhores em relação aos demais métodos
para proporção entre as classes < 3,85%). À medida que a proporção de exemplos da
classe negativa aumenta (ou seja, à medida que o desbalanceamento diminui no
conjunto de treinamento), observa-se uma melhoria de Gmean para o classificador puro,
muito embora o mesmo não alcance resultados melhores quando aplicados os métodos
SMOTE, subamostragem aleatória e sobreamostragem aleatória. Outra observação no
experimento é o valor máximo de Gmean alcançado quando a desproporção de
exemplos no conjunto de treinamento é aproximadamente 11% (Gmean = 0.8780). O
mesmo ocorre com AUC, Figura 18, nessa desproporção (0.9568)
G-mean vs. % de exemplos da classe negativa (k=0)
0.9
0.85
0.8
0.75
G -m e a n [ % ]
0.7
0.65
0.6
0.55
0.5
MLP+SUB+OVER
MLP+SMOTE
MLP+SUB
MLP
0.45
0.4
0
5
10
15
20
Proporção de exemplos da classe negativa [%]
25
30
35
Figura 17 – Proporção de exemplos da classe negativa vs. Gmean para k = 2
73 / 101
No caso da Figura 18 que considera a métrica AUC, não se percebe uma maior
distância entre a curva do classificador puro (MLP) e as curvas do mesmo classificador
após a aplicação dos métodos investigados. No entanto, para conjuntos de treinamento
altamente desbalanceados (proporção entre as classes de 1,54%, por exemplo), verificase que a AUC para o classificador puro é igual a 0.9135 e 0.9531 para o classificador
balanceado com o método de subamostragem aleatória (o de melhor resultado dentre os
demais métodos). Independente da proporção de exemplos da classe negativa (ou seja,
independente do grau de desbalanceamento do conjunto de treinamento), observa-se
melhores AUC para o classificador depois de aplicados os métodos investigados.
AUC vs. % de exemplos da classe negativa (k=0)
0.96
MLP+SUB+OVER
MLP+SMOTE
MLP+SUB
MLP
0.95
0.94
A U C [% ]
0.93
0.92
0.91
0.9
0.89
0.88
0
5
10
15
20
Proporção de exemplos da classe negativa [%]
25
30
35
Figura 18 – Proporção de exemplos da classe negativa vs. AUC para k = 2
Em resumo, nesta seção pudemos afirmar que:
• A aplicação de métodos de reamostragem seja sobreamostragem aleatória,
subamostragem aleatória (ou a combinação deles) ou SMOTE melhoram e
equilibram as taxas de acerto para ambas as classes em conjuntos de dados,
independentemente no grau de desbalanceamento. Quanto maior o grau de
desbalanceamento dos conjuntos de dados, melhor é o desempenho (em relação
à métrica Gmean) do classificador quando aplicados esses métodos;
74 / 101
• Para conjuntos de dados mais balanceados (tipicamente aqueles com grau de
balanceamento > 25%), o método de sobreamostragem com subamostragem
(MLP+OVER+SUB) reflete taxa de acerto mais elevada e equilibrada para
ambas as classes;
• Para conjuntos de dados menos balanceados (tipicamente aqueles com grau de
desbalanceamento < 5%), o método de subamostragem (MLP+SUB) reflete taxa
de acerto mais elevada e equilibrada para ambas as classes.
5.2.3 Experimento 3
As Tabelas 4 e 5 apresentam, respectivamente, os valores de AUC e Gmean
obtidos pelos algoritmos MLP, MLP+SMOTE, MLP+SMOTE+TOMEK e MLP+NBD
sobre as 10 bases de dados. As médias e desvios-padrão (estes últimos entre parênteses)
foram calculados sobre 10 diferentes casos de teste. Os melhores (maiores) valores
encontram-se em negrito.
Tabela 4 – Comparação de AUC (%) obtida pelos algoritmos MLP, MLP+SMOTE,
MLP+SMOTE+TOMEK e MLP+NBD sobre as 10 bases de dados. Em negrito, os
melhores valores encontrados.
Base de
dados
MLP
MLP+
MLP+
MLP+
SMOTE
SMOTE+TOMEK
NBD
PIMA
0.8045(0.0509) 0.8383(0.0386)
0.8067(0.0571)
0.8612(0.0223)
WPBC
0.7431(0.0532) 0.7269(0.0544)
0.6421(0.0722)
0.7204(0.0209)
HEART
0.7199(0.0648) 0.7287(0.0625)
0.7478(0.0587)
0.7755(0.0743)
IMAGE
0.9810(0.0254) 0.9911(0.0222)
0.9855(0.0269)
0.9966(0.0395)
GLASS
0.9121(0.0834) 0.9582(0.0472)
0.9712(0.0873)
0.9689(0.0487)
CAR
0.9673(0.0947) 0.9929(0.0172)
0.9960(0.0048)
0.9920(0.0294)
YEAST
0.8241(0.0572) 0.8400(0.0576)
0.8289(0.0543)
0.8340(0.0648)
ABALONE
0.6183(0.0587) 0.6523(0.0782)
0.8444(0.0365)
0.8087(0.0449)
METEOROL 0.7006(0.0257) 0.7249(0.0626)
0.7304(0.0356)
0.7398(0.0172)
0.8474(0.0487)
0.8522(0.0212)
ENERGIA
0.8402(0.0187) 0.8312(0.0532)
75 / 101
Tabela 5 – Comparação de Gmean (%) obtido pelos algoritmos MLP, MLP+SMOTE,
MLP+SMOTE+TOMEK e MLP+NDB sobre as 10 bases de dados. Em negrito, os
melhores valores encontrados.
Base de
MLP
dados
MLP+
MLP+
MLP+
SMOTE
SMOTE+TOMEK
NBD
PIMA
0.7052(0.0818)
0.7617(0,0631)
0.7268(0.1018)
0.8122(0.0067)
WPBC
0.6468(0.1846)
0.6292(0.0012)
0.6202(0.0245)
0.6012(0.0181)
HEART
0.5689(0.1423)
0.5976(0.0854)
0.6234(0.0115)
0.7362(0.0100)
IMAGE
0.9414(0.0467)
0.9360(0.0521)
0.9212(0.0366)
0.9512(0.0120)
GLASS
0.8851(0.0112)
0.8422(0.0523)
0.8918(0.0821)
0.9002(0.0066)
CAR
0.8139(0.0236)
0.8345(0.0345)
0.9102(0.0124)
0.9246(0.0521)
YEAST
0.4154(0.1211)
0.6267(0.1048)
0.6777(0.1736)
0.6456(0.1267)
ABALONE
0.7144(0.0569)
0.3623(0.2351)
0.6833(0.0236)
0.8156(0.0123)
METEOROL
0.7088(0.0045)
0.7297(0.0566)
0.7789(0.0321)
0.7565(0.0021)
ENERGIA
0.7134(0.0320)
0.7166(0.0423)
0.7321(0.0529)
0.8112(0.0011)
Como a maioria dos resultados apresentou pequena diferença numérica entre as
médias e a magnitude dos desvios foram aplicados testes estatísticos para se obter
conclusões sobre os desempenhos dos mesmos uma vez da dificuldade de distinção dos
algoritmos testados.
O teste não paramétrico de Friedman (Friedman, M., 1937), (Friedman, M.,
1940) foi selecionado para verificar se os algoritmos MLP, MLP+SMOTE,
MLP+SMOTE+TOMEK e MLP+NDB são significativamente diferentes. Testes não
paramétricos são mais indicados que seus correlatos paramétricos (Paired t-test,
ANOVA), desde que eles não assumam distribuições normais ou homogeneidade de
variância para os scores obtidos sobre inúmeras bases de dados (Demsar, J., 2006). O
teste de Friedman é indicado principalmente em aplicações de AM para comparação de
dois ou mais classificadores sobre múltiplas bases de dados e métricas de avaliação,
pois apresentam maior probabilidade de rejeição da hipótese nula.
No teste de Friedman, dados K algoritmos avaliados sobre N bases de dados,
com seus ranks médios R j , j = 1,2,..., K , assume-se a hipótese nula H 0 de que todos os
algoritmos são equivalentes, tal que seus ranks médios devem ser iguais. O teste de
Friedman cria um rank dos algoritmos para cada base de dados separadamente. O
76 / 101
algoritmo de melhor pontuação recebe o rank 1, o segundo melhor o rank 2 e, assim por
diante. Em caso de empates, ranks médios são atribuídos. Nesse caso, a estatística FF
(Equação 24) é distribuída segundo a distribuição F com K − 1 e ( K − 1)( N − 1) graus de
liberdade, onde:
FF =
χ F2 =
( N − 1) χ F2
(24)
N ( K − 1) − χ F2
12 N 
K ( K + 1) 2 
 ∑ R 2j −


K ( K + 1)  j
4

(25)
No experimento, N = 10 e K = 4 e então, 3 e 27 são os graus de liberdade para o
numerador e o denominador, respectivamente. De acordo com a Tabela de Valores
Críticos consultada (Demsar, J., 2006) da distribuição F , H 0 é rejeitada, a um nível de
significância
α de 5%, quando
FF >2,960.
A Tabela 6 lista os ranks médios obtidos pelos algoritmos para as métricas
Gmean e AUC. As duas últimas colunas da Tabela 6 mostram as correspondentes
estatísticas FF e p-valor calculadas para o teste de Friedman. De acordo com os valores
dessas estatísticas, a hipótese nula H 0 de ranks iguais pode ser rejeitada a um nível
significância de 5%, o que indica que os algoritmos são significativamente diferentes
para ambas as métricas analisadas.
Tabela
6:
Ranks
médios
obtidos
pelos
algoritmos
MLP,
MLP+SMOTE,
MLP+SMOTE+TOMEK e MLP+NDB para as métricas Gmean e AUC. As duas últimas
colunas da Tabela mostram os correspondentes valores das estatísticas FF e p-valor
referentes ao teste de Friedman.
Base de
dados
MLP
MLP+
SMOTE
MLP+
SMOTE+TOMEK
MLP+
NBD
FF
p-valor
AUC
3.60
2.50
2.20
1.70
5.706
5.2 x10−8
Gmean
3.20
2.90
2.30
1.60
3.857
1.2 x10−6
Em seguida, o teste post-hoc de Nemenyi (Demsar, J., 2006) (Nemenyi, P., 1963)
pode ser aplicado para comparar os algoritmos no formato “um-contra-um”. No teste de
Nemenyi, é feita uma avaliação se os ranks médios de dois algoritmos diferem de um
valor chamado Diferença Crítica (DC) conforme a Equação 26.
77 / 101
DC = qα
K ( K + 1)
6N
(26)
A diferença é considerada significativa com nível de confiança de 1 − α . De
acordo com a Tabela de Valores Críticos para o teste de Nemenyi (Demsar, J., 2006), a
constante q 0.05 para K = 4 é 2.569, tal que CD é 1.483. Esse valor é o mesmo para
ambas as métricas, Gmean e AUC. Os resultados do teste post-hoc para as métricas
Gmean e AUC encontram-se graficamente representados nos diagramas de Diferença
Crítica (DC) (Demsar, J., 2006) das Figuras 19 e 20, respectivamente.
No eixo superior de cada diagrama DC, os ranks médios dos algoritmos foram
marcados em ordem decrescente, com o melhor algoritmo ficando mais à esquerda.
Além disso, os grupos de algoritmos que não são significativamente diferentes (para α =
0.05), isto é, cujas diferenças entre ranks médios não superam CD = 1.483, foram
interligados por traços horizontais em negrito.
7
6.5
MLP+
SMOTE+
TOMEK
6
5.5
MLP
5
4.5
MLP+NBD
4
1
1.5
MLP+SMOTE
2
2.5
3
3.5
4
Figura 19: Diagrama DC representando os resultados do teste post-hoc de Nemenyi para
a métrica AUC. Os grupos de algoritmos que não são significativamente diferentes (para
α = 0.05) encontram-se conectados por traços horizontais.
Analisando os resultados do teste post-hoc para a métrica AUC, pode-se concluir
que MLP é significativamente pior que MLP+NBD. Já os métodos MLP+SMOTE,
MLP+SMOTE+TOMEK e MPL+NBD aparentam possuir desempenhos equivalentes.
Além disso, os dados não são suficientes para concluir se MLP+SMOTE e
MLP+SMOTE+TOMEK possuem desempenho equivalente à MLP ou à MLP+NBD.
Pode-se afirmar apenas que NBD é significativamente melhor que MLP. Cabe ressaltar,
no entanto, que as diferenças entre os ranks médios de MLP e MLP+SMOTE+TOMEK
(3.60 − 2.20 = 1,40) é muito próximo do valor crítico CD = 1.483 para α = 0.05. Isso
78 / 101
sugere que diferenças significativas entre MLP e MLP+SMOTE+TOMEK pode ser
encontrada para valores maiores de significância do teste post-hoc, tal como α = 0.10.
7
6.5
MLP+
SMOTE+
TOMEK
6
5.5
MLP
5
4.5
MLP+SMOTE
MLP+NBD
4
1
1.5
2
2.5
3
3.5
4
Figura 20: Diagrama DC representando os resultados do teste post-hoc de Nemenyi para
a métrica Gmean. Os grupos de algoritmos que não são significativamente diferentes
(para α = 0.05) encontram-se interligados por traços horizontais em negrito.
Com relação à métrica Gmean, o teste post-hoc nos permite concluir que MLP é
significativamente pior que MLP+NBD. Os dados também parecem indicar que
MLP+SMOTE,
MLP+SMOTE+TOMEK
e
MPL+NBD
possuem
desempenhos
equivalentes. Uma analogia pode ser feita em relação ao grupo MLP, MLP+SMOTE e
MLP+SMOTE+TOMEK. Cabe ressaltar novamente que as diferenças entre os ranks
médios de MLP+NBD e os demais métodos possuem valores críticos distantes o
bastante (para α = 0.05) que poderiam sugerir diferenças significativas para valores
maiores de significância do teste post-hoc, tal como α = 0.15.
Os testes estatísticos oriundos do terceiro experimento mostram que o algoritmo
MLP+NBD proposto neste trabalho é igualmente eficiente, sendo capaz de melhorar
significativamente o desempenho médio de MLPs puras sobre dados desbalanceados e
sobrepostos. Os ganhos de desempenho em termos de Gmean revelam que MLP+NBD
pode ser usado para obter taxas de acerto elevadas e equilibradas para ambas as classes.
5.3
Considerações finais
Esta seção apresentou a formulação matemática e experimentos relativos ao
novo método proposto neste trabalho e intitulado NBD. Três experimentos foram
executados: o primeiro experimento com conjuntos de dados sintéticos gerados a partir
de duas distribuições gaussianas unidimensionais e a representação do modelo de
classificação ótimo de Bayes para uma tarefa de classificação binária. O segundo
79 / 101
experimento apresentou o comportamento de métodos da literatura que promovem o
balanceamento de dados com sobreposição entre as classes em termos das métricas de
avaliação de desempenho AUC e Gmean. E o terceiro experimento apresentou a
eficiência das técnicas investigadas e do algoritmo que implementa o método NBD
proposto.
Os resultados dos testes de significância sinalizam que MLP+NBD possui, em
determinados cenários, desempenho superior aos tradicionais métodos de reamostragem
(SMOTE e SMOTE+TOMEK) para ambas as métricas analisadas. Embora não se possa
afirmar que MLP+NBD é significativamente (para α = 0.05) melhor que SMOTE e
SMOTE+TOMEK, o teste post-hoc conduz a afirmação de que ele pode ser superior
para níveis de significância próximos de 5%. Além disso, as diferenças elevadas entre
os ranks médios de MLP+NBD e os demais métodos sugerem superioridade deste
método a um nível maior de significância do teste post-hoc como, por exemplo, 10%. É
possível especular também que a superioridade de MLP+NBD sobre tais métodos de
reamostragem possa ser alcançada através de um aumento do número de exemplos de
dados no experimento.
80 / 101
6
Conclusões
Esta dissertação abordou alguns aspectos teóricos e práticos para o problema do
aprendizado indutivo com classes desbalanceadas e sobrepostas. Foi mostrado que o
viés induzido pelo desequilíbrio das distribuições surge intrinsecamente da minimização
de um critério baseado na taxa de erro global, tendo como fator atenuante o nível de
sobreposição entre as classes.
As abordagens discutidas fornecem subsídios para compreensão dos princípios
que regem as soluções até então propostas para o problema e servem como guia para o
desenvolvimento de novos métodos de balanceamento de classes. Soluções promissoras
para o problema de classes desbalanceadas devem considerar critérios alternativos para
seleção de modelos, os quais devem refletir as necessidades do domínio de aplicação em
foco. Essa observação ajuda a entender o sucesso empírico de variações de técnicas de
sobreamostragem e subamostragem, as quais provocam readaptações indiretas nas
classes ao modificarem as distribuições de probabilidade (a priori) a partir de suas
estratégias de reamostragem de dados.
Esta seção é apresenta as principais contribuições na seção 6.1. Na seção 6.2 são
apresentados os objetivos específicos alcançados e as hipóteses levantadas inicialmente
no trabalho. Discorre-se aqui sobre a aceitação ou rejeição dessas, amparadas pelos
experimentos e pesquisas realiadas ao longo do trabalho. Por fim, na seção 6.3, uma
apresentação dos trabalhos futuros.
6.1
Principais contribuições
Uma das mais importantes contribuições obtidas durantes os experimentos
realizados é que não é possível afirmar que determinado método é significativamente
melhor que outro, a um nível de confiança de 5%. Contudo, esses métodos não
implicam que classificadores podem não aprender a partir de dados altamente
desbalanceados. Ao contrário, os experimentos e a revisão da literatura mostraram que
classificadores induzidos por certos conjuntos desbalanceados são comparáveis a
classificadores induzidos com o mesmo conjunto de dados balanceado por técnicas de
reamostragem. No entanto, pode-se afirmar que ao balancear os conjuntos de dados
desbalanceados utilizados neste trabalho geralmente e na maior parte das vezes melhora
o desempenho de classificadores baseado em redes neurais do tipo MLP.
81 / 101
Como a distribuição das classes varia com a aplicação desses métodos de
reamostragem, métricas de aferição de desempenho também podem apresentar
resultados diferentes mesmo considerando o mesmo classificador. Isso pode ser muito
problemático quando se compara o desempenho de diferentes algoritmos de
aprendizagem sobre bases de dados diferentes por causa da inconsistência de
representação do desempenho. Em outras palavras, a presença de desbalanceamento de
classes torna difícil a análise quanto às métricas de avaliação são sensíveis à
distribuição dos dados. Por exemplo, ao contrário da acurácia e taxa de erro, as métricas
Precision e Recall não são sensíveis a mudanças na distribuição dos dados.
De outro lado, apesar de Recall não ser dependente da distribuição, seu uso
exclusivo pode trazer resultados equivocados, uma vez que não traz informação de
quantos exemplos são incorretamente classificados como positivos. Da mesma forma, o
uso exclusivo de Precision não permite afirmar quantos exemplos positivos são
classificados incorretamente. No entanto, quando usados corretamente, podem
efetivamente avaliar o desempenho da classificação em cenários de aprendizagem
desequilibrados. Portanto, utilizar uma única métrica de avaliação não é suficiente para
lidar com problemas de aprendizagem desequilibrada. É necessário avaliar a pertinência
não só da acurácia, como também, AUC, PR, Cost Curve, Precision e Recall.
6.2
Objetivos alcançados, hipóteses aceitas e rejeitadas
Do ponto de vista das hipóteses levantadas durante a pesquisa, pode-se aceitar a
partir dos resultados alcançados que, de uma forma geral, conjuntos de treinamento
balanceados melhoram simultaneamente as taxas de acerto de classificação para ambas
as classes e que conjuntos de treinamento desbalanceados não são os únicos
responsáveis pelo baixo desempenho de classificadores de padrão, mas também o grau
de sobreposição entre as classes.
Em relação as hipóteses específicas e considerando as bases de dados
utilizadas, pôde-se:
1. Aceitar a hipótese de que conjuntos de treinamento balanceados melhoram
simultaneamente as taxas de acerto de classificação para ambas as classes;
2. Aceitar a hipótese de que conjuntos de treinamento desbalanceados não são os
únicos responsáveis pelo baixo desempenho de classificadores de padrão, mas
também o grau de sobreposição entre as classes;
82 / 101
3. Rejeitar a hipótese de que as distribuições das classes que ocorrem
naturalmente são as melhores para o aprendizado;
4. Aceitar a hipótese de que penalizações com base na proporção dos padrões no
conjunto de treinamento permitem obter modelos equilibrados (equidistantes das
distribuições), compensando o viés imposto pela classe majoritária.
Em relação aos objetivos específicos, a partir das bases de dados utilizadas,
pôde-se concluir que:
• Foi alcançado o objetivo específico de investigar na literatura os principais
métodos de balanceamento de classes utilizados em pré-processamento de
conjuntos de dados anteriormente a tarefas de classificação de padrões;
• Foi alcançado o objetivo específico de propor um novo método de
reamostragem de dados no espaço de entrada, que inclui sobreamostragem da
classe minoritária, subamostragem da classe majoritária ou a combinação de
ambas as técnicas de forma a melhorar os resultados da aplicação dos métodos
de balanceamento de classes investigados na literatura e neste trabalho;
• Foi alcançado o objetivo específico de realizar experimentos com bases de
dados provenientes de repositórios clássicos da literatura e também bases de
dados de problemas reais como forma de validar os métodos de balanceamento
de classes investigados na literatura e utilizados neste trabalho;
• Foi alcançado o objetivo específico de realizar testes estatísticos junto aos
resultados experimentais obtidos como forma de validar a eficiência do novo
método proposto;
• Foi alcançado o objetivo específico de provar, a partir dos métodos
investigados e do novo proposto, que RNA induzidas por conjuntos de
treinamento desbalanceados tendem a produzir classificadores que favorecem a
classe com maior probabilidade de ocorrência.
6.3
Trabalhos futuros
Como trabalhos futuros podemos destacar as seguintes investigações e estudos a
serem realizados a partir dos resultados alcançados neste trabalho, entre eles:
83 / 101
Compreensão teórica sobre os princípios e as consequências do treinamento com
classes altamente desbalanceadas e sobrepostas. Atualmente, a maioria dos esforços
na pesquisa em aprendizagem com classes desbalanceadas foca no desenvolvimento de
algoritmos específicos e/ou estudos de caso; apenas uma quantidade muito limitada foca
na compreensão teórica e nos fundamentos matemáticos sobre os princípios e as
consequências deste problema. Por exemplo, embora quase todos os algoritmos
apresentados na literatura afirmem ser capazes de melhorar a precisão da classificação
sobre certas condições, existem certas situações em que a aprendizagem sobre conjuntos
de dados originais pode fornecer um melhor desempenho. Este fato levanta uma questão
importante: até que ponto métodos para classes desbalanceadas, para determinadas
bases de dados, podem ajudar no aprendizado? Esta é uma questão fundamental e crítica
neste domínio por várias razões. Primeiro, suponha que existam (ou existirão) técnicas
ou metodologias que significativamente superam outras na maior parte (ou, idealmente,
todas) em domínios aplicáveis. Logo, estudos rigorosos sobre quais efeitos tais métodos
produzem são fundamentais para a compreensão do problema em questão. Em segundo
lugar, como essas metodologias e análises de dados podem ser aplicadas a problemas
reais com dados reais? Assim, as consequências desta questão crítica têm amplos efeitos
no avanço da área.
Aprendizagem incremental em fluxos de dados desbalanceados. Métodos
tradicionais de aprendizagem estáticos exigem que o conjunto de dados esteja
disponível no momento do treinamento, a fim de se desenvolver os limites de decisão.
No entanto, em muitas aplicações reais, tais como em mineração na web, redes de
sensores, sistemas multimídia, entre outros, os dados brutos se tornam disponíveis
continuamente através de uma aprendizagem (possivelmente infinita) por tempo
indeterminado (Ozawa, S.; Pang, S.; Kasabov. N., 2008), (Leite, D. F.; Costa Jr., P.;
Gomide, F. A. C., 2009). Portanto, novos entendimentos, princípios, metodologias,
algoritmos e ferramentas são necessários para tratar do aprendizado nesses cenários de
fluxo de dados contínuo de forma eficiente para transformar dados em informações úteis
e representação do conhecimento para apoiar os processos de tomada de decisão.
Embora a importância da mineração em fluxo de dados tenha atraído cada vez mais
atenção recentemente (Leite, D. F.; Costa Jr., P.; Gomide, F. A. C., 2010), (Lughofer,
E., 2008), (Angelov, P. and Zhou, X., 2006) a atenção dada aos dados desbalanceados
em fluxo contínuo fluxos tem sido bastante limitada. Além disso, no que se refere à
84 / 101
aprendizagem incremental de fluxos de dados desbalanceados, muitas questões
importantes precisam ser ainda abordadas, tais como: como podemos ajustar a
aprendizagem de forma autônoma? Devemos considerar o reequilíbrio do conjunto de
dados durante o período de aprendizagem incremental? Se sim, como podemos
conseguir isso? Como podemos acumular experiência anterior e usar conhecimento
para melhorar a aprendizagem adaptativa a partir de dados novos? A compreensão
concreta e exploração ativa nestas áreas podem avançar significativamente o
desenvolvimento da tecnologia para cenários do mundo real de aprendizagem
incremental (Li, Y.; Xu, L. G.; Morphett, J. and Jacobs, R.,2003), (Lughofer, E., 2008),
(Bouchachia, A.; Gabrys, B.; Sahel, Z., 2007).
Cálculo do limiar ótimo max θ e min θ do método NBD. O método NBD proposto é
baseado em subamostragem e sobreamostragem guiada pela informação da densidade
em torno dos exemplos de treinamento inter-classe e intra-classe. O algoritmo que
computa o NBD possui parâmetros que permitem o ajustar a intensidade do processo de
reamostragem de acordo com o grau de desbalanceamento e sobreposição entre as
classes. Este parâmetro é ajustado empiricamente pelo usuário do método conforme
recomendação descrita neste trabalho, mas pode, através de novas heurísticas, otimizar
o processo de eliminação e síntese de exemplos de regiões altamente desbalanceadas e
sobrepostas de forma a melhorar a distribuição dos conjuntos de treinamento para que
um classificador possa estimar uma melhor superfície de separação através de valores
ótimos de min θ e max θ .
DN sob o ponto de vista de classificação para uma classe (C1C) para problemas
com conjuntos de treinamento altamente desbalanceados e sobrepostos. Tendo em
vista as limitações de técnicas tradicionais de AM para a tarefa de classificação com
conjuntos de treinamento altamente desbalanceados e sobrepostos no que diz respeito à
identificação de novos perfis nos dados, várias abordagens de C1C (presença, na fase de
treinamento, de elementos de apenas um perfil) têm contribuído em diversos domínios
de aplicação para permitir a DN. Por outro lado, a grande massa de dados que passou a
se acumular a partir dos avanços das TICs (Tecnologias da Informação e Comunicação),
representa um grande desafio às técnicas computacionais, o que tem motivado uma
crescente expansão na utilização de técnicas de AM, principalmente em bases de dados
reais como as utilizadas nos experimentos referentes a histórico de dados
85 / 101
meteorológicos para previsão de eventos climáticos extremos e a histórico de inspeções
realizadas em consumidores de energia elétrica com suspeita de irregularidades ou
falhas na medição de consumo de energia (Alberto, B. L. A.; Almeida, P. E. M., 2009),
(Alberto, B. L. A., 2007). Acredita-se que técnicas de DN podem contribuir
positivamente na solução dessa classe de problemas que caracterizam-se por enormes
bases de dados altamente desbalanceadas e sobrepostas, permitindo, por exemplo, a
detecção de mudanças nos perfis de consumo de energia elétrica ou de eventos
climáticos extremos que possam estar associados ao aparecimento de uma nova classe
ou mesmo a ocorrência de concept drift (alteração do perfil normal) (Klinkenberg, R.,
2004). Propõe-se, portanto como trabalho futuro investigar novas abordagens para
problemas reais por meio de técnicas de C1C desbalanceadas para a DN. O foco
principal está na aplicação em problemas de previsão de eventos climáticos extremos e
falhas/fraudes no consumo de energia elétrica. Além da DN, um novo desafio a ser
perseguido é o da identificação da origem da novidade, aspecto muito pouco explorado
em trabalhos de DN. Um elemento identificado como membro de um novo perfil pode
indicar o aparecimento de uma nova classe, a ocorrência de concept drift, ou ainda se
tratar de ruído ou de um dado inválido.
86 / 101
Referências bibliográficas
[01] Alberto, B. L. A. (2007) Classificação de padrões por meio de uma abordagem de
Detecção de Novidade utilizando Redes Neurais Artificiais. Monografia do Curso de
Especialização em Automação Industrial, Programa de Pós-Graduação em Engenharia
Elétrica da UFMG, Belo Horizonte – MG.
[02] Alberto, B. L. A. e Almeida, P. E. M. (2009) Serviços solicitados por
consumidores atendidos em baixa tensão junto às distribuidoras de energia elétrica:
formação de clusters com suspeita de irregularidades utilizando Mapas AutoOrganizáveis. In XXXII Congresso Nacional de Matemática Aplicada e Computacional,
v.2, ISSN 1984-820X, pp. 796-796.
[03] Alberto, B. L. A.; Martinez, C. L.; Vale, C. E. S.; Pappa, G. L.; Ferreira, R. A. C.
(2011) Um sistema inteligente para seleção de unidades consumidoras com suspeita de
irregularidades no consumo de energia elétrica. In X Congresso Brasileiro de
Inteligência Computacional.
[04] Alberto, B. L. A.; Almeida, P. E. M.; Duarte, R. L. (2008) Inteligência
Computacional nas Distribuidoras de Energia Elétrica: evolução tecnológica, aplicações
e impactos na redução das perdas não técnicas. In XVIII Seminário Nacional de
Distribuição de Energia Elétrica.
[05] Albrecht, S., Busch, J., Kloppenburg, M., Metze, F. and Tavan, P. (2000)
Generalized radial basis function networks for classification and novelty detection: Selforganization of optimal bayesian decision. In Neural Networks, Vol. 13, No. 10, pp.
1075–1093.
[06] Alejo, R.; Garcia, V.; Sotoca, J.; Mollineda, R. and Sanchez, J. (2006). Improving
the classification accuracy of RBF and MLP neural networks trained with imbalanced
samples. In Intelligent Data Engineering and Automated Learning IDEAL 2006 , vol.
4224 of Lecture Notes in Computer Science, 464–471, Springer Berlin / Heidelberg.
87 / 101
[07] Almeida, P. E. M.; Meireles, M. R. G.; Simões, M. G. (2003). A Comprehensive
Review for Industrial Applicability of Artificial Neural Networks. In IEEE Transactions
on Industrial Electronics, New York, NY, v. 50, n. 3, p. 585-601.
[08] Angelov, P. and Zhou, X. (2006). Evolving fuzzy systems from data streams in
real-time. In International Symposium on Evolving Fuzzy Systems, pages 29–35.
[09] Baranauskas, J. A., Monard, M. C. and Horst, P. S. (1999). Evaluation of CN2
Induced Rules Using Feature Selection. In Argentine Symposium on Artificial
Inteligence (ASAI/JAIIO/SADIO), Buenos Aires, Argentina, pp. 141-154.
[10] Barandela, R., Valdovinos, R.M., Sanchez, J. S. and Ferri, F.J. (2004) The
imbalanced training sample problem: Under or over sampling? In Structural, Syntactic,
and Statistical Pattern Recognition, vol. 3138 of Lecture Notes in Computer Science,
806–814, Springer Berlin / Heidelberg, 2004
[11] Barnett, V. and Lewis, T. (1994). Outliers in Statistical Data. New York, NY: John
Wiley and Sons.
[12] Basu, S.; Bilenko, M. and Raymond, J. M. (2004). Integrating Constraints and
Metric Learning in Semi-Supervided Clustering. In Proceedings of the 21st
International Conference on Machine Learning. ICML-2004, pp. 81-88.
[13] Batista, G.E.A.P.A., Prati, R.C. and Monard, M.C. (2004). A study of the behavior
of several methods for balancing machine learning training data. In SIGKDD Explor.
Newsl., 6, 20–29.
[14] Batista, G.E.A.P.A and Monard, M.C. (2002). A Study of K-Nearest Neighbour as
an Imputation Method. In A. Abrahan, J. R. del Solar, and M. Koppen (eds.), Soft
Computing Systems: Design, Management and Applications, Santiago, Chile, pp. 251-
260. IOS Press.
[15] Berger, J. (1985). Statistical Decision Theory and Bayesian Analysis. Springer,
2nd.
88 / 101
[16] Bishop, C. M. (2006). Pattern Recognition and Machine Learning (Information
Science and Statistics), Springer.
[17] Bishop, C. M. (1994). Novelty detection and neural network validation, In IEEE
Proceedings on Vision, Image and Signal Processing, Vol. 141, No. 4, pp. 217–222.
[18] Blake, C. L., and Merz, C. J. (1998). UCI repository of machine learning databases,
University of California, Irvine, CA . www.ics.uci.edu/∼mlearn/MLRepository.html
[19] Bloedorn, E. and Michalski, R. S. (1998). Data-Driven Construtive Induction. In
IEEE Intelligent Systems 13(2), 30-37.
[20] Blum, A. L. and Mitchell, T. M. (1998) Combining labeled and unlabeled data with
cotraining. In Proceedings of the Eleventh Annual Conference on Computational
Learning Theory pages 92–100, New York, USA, ACM Press.
[21] Blum, A. L. and Langley, P. (1997). Selection of Relevant Features and Examples
in Machine Learning. Artificial Intelligence 97, 245-271.
[22] Boley, D. L. (1997) Principal direction divisive partitioning. Tech. Rep. TR-97056, University of Minnesota, Minneapolis, MN.
[23] Bouchachia, A.; Gabrys, B.; Sahel, Z. (2007). Overview of some incremental
learning algorithms. In IEEE International Fuzzy Systems Conference, pp: 1-6
[24] Bratko, I. (1990). Prolog Programming for Artificial Intelligence. Addison-Wesley.
[25] Breiman, L.; Friedman, J.; Olshen, R. and Stone, C. (1984). Classification and
Regression Trees. Pacific Grove, CA: Wadsworth and Books.
[26] Brodley, C. E. and Friedl, M. A. (1999). Identifying Mislabeled Training Data. In
Journal od Artificial Intelligence Research 11. 131-167.
89 / 101
[27] Bruce, R. (2001) A bayesian approach to semi-supervised learning. In Mitsuru
Ishizuka and Abdul Satter, editors, Proceedings of the Sixth Natural Language
Processing Pacific Rim Symposium — NLPRS-2001, pages 57– 64, Tokyo, Japan,
Springer Verlag.
[28] Bunkhumpornpat, C.; Sinapiromsaran, K.; Lursinsap, C. (2003) Safe-LevelSynthetic Minority Over-Sampling Technique for handling the class impalanced
problem. Department of Mathematics, Faculty of Science, Chulalongkorn University.
[29] Chawla, N.V., Bowyer, K.W. and Kegelmeyer, P.W. (2002). Smote: Synthetic
minority over-sampling technique. Journal of Artificial Intelligence Research, 16, 321–
357.
[30] Chawla, N. V., Japkowicz, N. and Kotcz, A. (2003) Procedings of the ICML’2003
Workshop on Learning from Imbalanced Data Sets.
[31] Chawla, N. V., Japkowicz, N. and Kotcz, A. (2002) Special issues on Learning
from Imbalanced Data Sets. ACM SIGKDD Explorations, V.6, p.1-6.
[32] Chawla, N. V., Bowyer, K. W., Hall, L. O., and Kegelmeyer, W. P. (2002). Smote:
Synthetic minority over-sampling technique. In Journal of Artificial Intelligence
Research, 16:321–357.
[33] Cherkassky, V. and Mulier, F. (2007). Learning from data. In John Wiley and Sons,
2nd.
[34] Ciaccia, P., Patella, M., Zezula, P. (1997). M-Tree: Na Efficient Access Method for
Similarity Search in Metric Spaces. In International Conference on Very Large Data
Bases, pp. 426-435
[35] Cover, T. M. and Hart, P. E. (1967). Nearest neighbor pattern classification. In
IEEE Transactions on Information Theory, 13(1):21-27.
90 / 101
[36] Davis, J. and Goadrich, M. (2006) The Relationship between Precision-Recall and
ROC Curves, In Proc. Int’l Conf. Machine Learning, pp. 233-240.
[37] Demsar, J. (2006). Statistical comparisons of classifiers over multiple data sets. In
Journal of Machine Learning Research, 7, 1–30
[38] Dietterich, T. G. (1997a). Approximate Statistical Tests for Comparing Supervised
Classification Learning Algorithms. In Neural Computation, 10(7):1895–1924.
[39] Domingos, P. (1999). MetaCost: A General Method for Making Classifiers CostSensitive. In Knowledge Discovery and Data Mining, pp. 155-164.
[40] Dougherty, J., Kohavi, R. and Sahami, M. (1995). Supervised and Unsupervised
Discretization of Continuous Features. In A. Priedits and Russell (Eds.), In XII
International Conference in Machine Learning, San Francisco, CA, pp. 194-202.
Morgan Kaufmann.
[41] Drummond, C. and Holte, R. (2003). C4.5, class imbalance, and cost sensitivity:
Why under-sampling beats over-sampling. In Working Notes of the ICML Workshop
Learning from Imbalanced Data Sets
[42] Duda, R. O.; Hart, P. E. and Stork, D. G. (2001). Pattern Classification (2nd
Edition). Wiley-Interscience.
[43] Durães, R. L. (2009) Validação de Modelos Baseados em RNA Utilizando Análise
estatística de Dados e Lógica Fuzzy. Dissertação apresentada ao Programa de PósGraduação em Modelagem Matemática e Computacional do CEFET-MG, Belo
Horizonte – MG.
[44] Elkan, C. (2001). The foundations of cost-sensitive learning. In Proceedings of the
Seventeenth International Joint Conference on Artificial Intelligence, IJCAI , 973–978.
[45] Fayyad, U.; Piatetsky-Shapiro, G. and Smyth, P. (1996). From Data Mining to
Knowledge Discovery in Databases. In AI Maganize, pp. 37-54.
91 / 101
[46] Fawcett, T. (2006). An introduction to ROC analysis. Pattern Recogn. Lett., 861–
874.
[47] Fawcett, T. (2004). ROC Graphs: Notes and Practical Considerations. Machine
Learning.
[48] Fawcett, T. and Provost, F. J. (1997). Adaptive Fraud Detection. Data Mining and
Knowledge Discovery 1(3), 291-316.
[49] Filho, J. A. S. (2006) Utilização de redes neurais artificiais em classificação
autônoma de peças metálicas empregando imagens radiográficas aplicáveis a sistemas
IVA. Dissertação apresentada ao Programa de Pós-Graduação em Modelagem
Matemática e Computacional do CEFET-MG, Belo Horizonte – MG, 2006.
[50] Freund, Y. and Schapire, R. E. (1997). A decision-theoretic generalization of online learning and an application to boosting. In Journal Computing Systems Science
55(1):119-139.
[51] Friedman, M. (1940). A comparison of alternative tests of significance for the
problem of m rankings. In The Annals of Mathematical Statistics, 11, 86–92.
[52] Friedman, M. (1937). The use of ranks to avoid the assumption of normality
implicit in the analysis of variance. In Journal of the American Statistical Association,
pp. 675–701.
[53] Furnkranz, J. (1999). Separate-and-conquer Rule Learning. Artificial Intelligence.
Review 13(1), pp 3-54.
[54] Garnett, R.; Roberts, S. J. (2008). Learning from Data Streams with Concept Drift.
Technical Report PARG-08-01, Dept. of Engineering Science, University of Oxford,
Jun., 64p.
[55] Goldberg, D. E. (1989) Genetic Algorithms in Search, Optimization, and Machine
Learning. EUA: Addison-Wesley.
92 / 101
[56] Han, H., Wang, W. Y. and Mao, B. H. (2005). Borderline-smote: A new
oversampling method in imbalanced data sets learning. In Advances in Intelligent
Computing, vol. 3644 of Lecture Notes in Computer Science, 878–887, Springer Berlin,
Heidelberg.
[57] Hand, D. & Till, R. (2001). A simple generalisation of the area under the ROC
curve for multiple class classification problems. In Machine Learning., 45, 171–186.
[58] Hall, M.; Frank, E.; Holmes, G.; Pfahringer, B.; Reutemann, P.; Witten, I. H.
(2009). The WEKA Data Mining Software: An Update. SIGKDD Explorations, volume
11, Issue 1.
[59] Hart, P. E. (1968). The condensed nearest neighbor rule. In IEEE Transactions on
Information Theory. IT-14:515-516.
[60] Haykin, S. (1998). Neural Networks: A Comprehensive Foundation. Prentice Hall,
2nd edition.
[61] He, H. and Garcia, E.A. (2009). Learning from imbalanced data. IEEE
Transactions on Knowledge and Data Engineering, 21, 1263–1284.
[62] Holland, J. H. (1975). Adaptation in natural and artificial systems. The University
of Michigan Press, Ann Arbor, MI, USA.
[63] Hosmer, D. W. and Lemeshow, S. (1989) Applied Logistic Regression, John Wiley
& Sons Inc.
[64] Holte, R. C. and Drummond, C. (2006) Cost Curves: An Improved Method for
Visualizing Classifier Performance, In Machine Learning, vol. 65, no. 1, pp. 95-130.
[65] Holte, R. C. and Drummond, C. (2005) Cost-Sensitive Classifier Evaluation, In
Proc. Int’l Workshop Utility-Based Data Mining, pp. 3-9.
93 / 101
[66] Hopfield, J. J. (1982). Neural Networks and Physical Systems with Emergent
Collective Computational Abilities. National Academy of Sciences of the USA, pp.
2554-2558.
[67] Huang, Y.M., Hung, C.M. and Jiau, H.C. (2006). Evaluation of neural networks
and data mining methods on a credit assessment task for class imbalance problem.
Nonlinear Analysis: Real World Applications, 7, 720 – 747.
[68] Hulse, J. V.; Khoshgoftaar, T. M.; Napolitano, A. (2007) Experimental
Perspectives on Learning from Imbalanced Data. In Proceedings of the 24th
International Conference on Machine Learning, Corvallis, OR.
[69] Japkowicz, N. (2000). Learning from imbalanced data sets: A comparison of
various strategies. In AAAI Conference on Artificial Intelligence, 10–15, AAAI Press.
[70] Japkowicz, N., Myers, C., Gluck, M. (1995) A novelty detection approach to
classification, In: Proceedings of 14th IJCAI Conference, Montreal, Canada, pp. 518–
523.
[71] Japkowicz, N. and Stephen, S. (2002). The class imbalance problem: A systematic
study. Intelligent Data Analysis, 6(5):429–449.
[72] John, G., Kohavi, R. and Pfleger, K. (1994). Irrelevant Features and the Subset
Selection Problem. In M. Kaufmann (ed.), In Proceedings of the Eleventh International
Conference on Machine Learning, San Francisco, CA, pp. 167-173.
[73] Jr., C. T., Traina, A., Seeger, B. and Faloutsos, C. (2000). Slim-trees: High
Performance Metric Tress Minimizing Overlap Between Nodes. In Conference on
Extending Database Technology. EDBT’2000, pp. 51-65
[74] Khoshgoftaar, T. M.; Hulse, J.V. and Napolitano, A. (2010). Supervised neural
network modeling: An empirical investigation into learning from imbalanced data with
labeling errors. IEEE Trans. on Neural Networks, 21, 813–830.
94 / 101
[75] Kibler, D. and Langley, P. (1998). Machine Learning as an Experimental Science.
Machine Learning 3(1),5-8.
[76] Klinkenberg, R. (2004). Learning drifting concepts: Example selection vs. example
weighting. Intelligent Data Analysis, Special Issue on Incremental Learning Systems
Capable of Dealing with Concept Drift, 8(3):281–300.
[77] Kohavi, R. (1997). Wrappers for Feature Subset Selection. Artificial Intelligence
97, 273-324.
[78] Kohavi, R. and Sahami, M. (1996). Error-Based and Entropy-Based Discretization
of Continuous Features. In Second International Conference on Knowledge Discovery
and Data Mining (KDD-96), Portland, OR, pp. 114-119. American Association for
Artificial Intelligence.
[79] Koza, J. R.. (1992) Genetic Programming: On the Programming of Computers by
Means of Natural Selection. [S.l.]: MIT Press, 1992.
[80] Kubat, M. and Matwin, S. (1997). Addressing the curse of imbalanced training
sets: one-sided selection. In Proc. 14th International Conference on Machine Learning,
179–186, Morgan Kaufmann.
[81] Kubat, M., Holte, R. C., and Matwin, S. (1998). Machine learning for the detection
of oil spills in satellite radar images. In Machine Learning, 30(2-3):195–215.
[82] Lan, J., Hu, M.Y., Patuwo, E. and Zhang, G.P. (2010). An investigation of neural
network classifiers with unequal misclassification costs and group sizes. Decis. Support
Syst., 48, 582–591.
[83] Laurikkala, J. (2001). Improving Identification of Difficult Small Classes by
Balancing Class Distribution. University of Tampere.
95 / 101
[84] Lee, H. D., Monard, M. C. and Baranauskas, J. A. (1999). Empirical Comparison
of Wrapper and Filter Approaches for Feature Subset Selection. Technical Report 94,
ICMC-USP.
[85] Leite, D. F.; Costa Jr., P.; Gomide, F. A. C. (2009). Evolving Granular
Classification Neural Networks. In International Joint Conference on Neural Networks,
1:1736-1743.
[86] Leite, D. F.; Costa Jr., P.; Gomide, F. A. C. (2010). Evolving Granular Neural
Networks for Semisupervised Data Stream Classification. In World Congress on
Computational Intelligence (submitted), 2010.
[87] Li, Y.; Xu, L. G.; Morphett, J. and Jacobs, R. (2003). On incremental and robust
subspace learning. Pattern Recognition, 37:1509–1518.
[88] Ling, C. X. and Li, C. (1998). Data Mining for Direct Mining: Problems and
Solutions. In Forth International Conference on Knownledge Discovery and Data
Mining, pp. 73-79.
[89] Liu, X.Y., Wu, J. & Zhou, Z.H. (2009). Exploratory undersampling for class
imbalance learning. IEEE Trans. on Sys. Man Cyber. Part B, 39, 539–550.
[90] Luenberger, D. (1984). Linear and Nonlinear Programming. Addison-Wesley,
Reading, 2nd edn.
[91] Lughofer, E. (2008). Extensions of vector quantization for incremental clustering.
Pattern Recognition, 41(3):995 – 1011. Part Special issue: Feature Generation and
Machine Learning for Robust Multimodal Biometrics.
[92] Markou, M. e Singh, S. (2003) Novelty detection: A review, part i: Statistical
approaches, In Signal Processing, No. 83, pp. 2481–2497.
[93] Markou, M. e Singh, S. (2003) Novelty detection: A review, part ii: Neural
network based approaches”, In Signal Processing, No. 83, pp. 2499–2521.
96 / 101
[94] Marsland, S. (2003) Novelty detection in learning systems, In Neural Computing
Surveys, No. 3, 2003, pp. 157–195.
[95] Matlab (2008). Version 8.10.0 (R2008a). The MathWorks Inc., Natick,
Massachusetts.
[96] Mazurowski, M. A., Habas, P. A., Zurada, J. M., Lo, J. Y., Baker, J. A. & Tourassi,
G. D. (2008). Training neural network classifiers for medical decision making: The
effects of imbalanced datasets on classification performance. Neural Networks, 21, 427–
436.
[97] Monard, M. and Batista, G. E. A. P. A. (2002). Learning with skewed class
distribution. In Advances in Logic, Artificial Intelligence and Robotics, 173–180, IOS
Press.
[98] Mease, D.; Wyner, A.J. and Buja, A. (2007). Boosted classification trees and class
probability/quantile estimation. J. Mach. Learn. Res., 8, 409–439.
[99] Michalski, R. S.; Mozetic, I.; Hong, J. and Lavrac, N. (1986). The Multi-purpose
Incremental Learning System AQ15 and its Testing Application to Three Medical
Domains. In Fifth Annual National Conference on Artificial Intelligence, pp 1041-1045.
[100] Michalski, R. S.; Carbonell, J. G. and Mitchell, T. M. (1983). Machine Learning:
An Artificial Intelligence Approach. Tioga Publishing Company.
[101] Michalski, R. S. (1978). Pattern Recognition as Knowledge-Guided Computer
Induction. Technical Report 927, Department of Computer Science, University of
Illinois, Urbana-Champaign.
[101] Minsky, M. L. and Papert, S. A. (1969). Perceptrons. MIT Press.
[102] Mitchell, T. (1997). Machine Learning. McGraw Hill.
97 / 101
[103] Morgan, J. and Messenger, R. (1973). THAID: A Sequential Search Program for
the Analysis of Nominal Scale Dependent Variables. Technical report, Institute for
Social Research, University of Michigan.
[104] Nemenyi, P. (1963). Distribution-free multiple comparisons. Ph.D. thesis,
Princeton University.
[105] Nickerson, A.; Japkowicz, N & Millos, E. (2001). Using Unsupervised Learning
to Guide Rezampling in Imbalanced Data Sets. In Proceedings of the 8th Internacional
Workshop on AI and Statistics. Key West, p. 261-265
[106] Norvig, P. and Russel, S. (1986) Artificial Intelligence: A Modern Aproach.
Upper Saddle River, NJ, EUA: Prentice Hall, 1995.
[107] Ozawa, S., Pang, S., Kasabov, N. (2008). Incremental Learning of Chunk Data for
Online Pattern Classification Systems. In IEEE Trans. on Neural Networks, 19(6):
1061-1074.
[108] Parzen, E. (1962). On the estimation of a probability density function and mode.
In Annals of Mathematical Statistics, 33:1065-1076.
[109] Pazzani, M., Merz, C., Murphy, P., Ali, K., Hume, T. and Brunk, C. (1994).
Reducing Misclassification Costs. In XI International Conference in Machine Learning,
pp. 217-225.
[110] Pednault, E. P. D., Rosen, B. K. and Apte, C. (2000). Handling Imbalanced Data
Sets in Insurance Risk Modeling. Technical Report RC-21731, IBM Research Report.
[111] Pila, A. D. and Monard, M. C. (2002). Rules Induced by Symbolic Learning
Algorithms Using Rough Sets Reducts for Selecting Features: An Empirical
Comparison with other Filters. In A. Zapico and J. M. Santos (Eds.), In Proceedings
Argentine Symposium on Artificial Intelligence, ASAI’2002, Santa Fé, Argentina, pp.
206-217.
98 / 101
[112] Prati, R.C., Batista, G.E.A.P.A., Monard, M.C. (2004) Class imbalance versus
class overlaping: An analysis of a learning system behaviour. In Mexican International
Conference on Artificial Intelligence (MICAI'2004), volume 2972 of LNAI., Mexico
City (Mexico), Springer, pp. 312-321.
[113] Pyle, D. (1998). Data Preparation for Data Mining. Morgan Kaufmann Publishers,
Inc.
[114] Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning. 81-106.
Readings in Machine Learning.
[115] Quinlan, J. R. (1987a). Generating Production Rules from Decisions Trees. In
Proceedings of the Tenth International Joint Conference on Artificial Intelligence, Italy,
pp 304-307
[116] Quinlan, J. R. (1987b). Simplifying Decision Trees. In International Journal of
Man-Machine Studies, pp 221-23427.
[117] Rosenblatt, F. (1958). The Perceptron: A Probabilistic Model for Information
Storage and Organization in the Brain. Psycological Review.
[118] Rumelhart, D.E., J.L. McClelland and the PDP Research Group (1986). Parallel
Distributed Processing: Explorations in the Microstructure of Cognition. Volume 1:
Foundations, Cambridge, MA: MIT Press.
[119] Russel, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach (2
ed.). Prentice Hall.
[120] Shaw, M. J. and Gentry, J. A. (1990). Inductive Learning for Risk Classification.
IEEE Expert: Intelligent Systems and Their Applications 5(1), 47-53
[121] Sheskin, D.J. (2007). Handbook of Parametric and Nonparametric Statistical
Procedures. Chapman & Hall/CRC, 4th edn.
99 / 101
[122] Stanfill, C. and Waltz, D. (1986). Instance-based learning algorithms. In
Communications of the ACM 12, 1213-1228.
[123] Sun, Y., Kamel, M.S., Wong, A.K.C. & Wang, Y. (2007). Cost-sensitive boosting
for classification of imbalanced data. Pattern Recognition, 40, 3358–3378.
[124] Tan, P.N., Steinbach, M. & Kumar, V. (2005). Introduction to Data Mining,
(First Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
[125] Tax, D. M. J. (2001). One-class classification - Concept-learning in the absence of
counterexamples. PhD thesis, Delf University of Technology, Faculty of Information
Technology and Systems.
[126] Tomek, I. (1976). Two modifications of CNN. In IEEE Trans. Systems, Man, and
Cybernetics, 6, 769–772.
[127] Van Gestel, T., Suykens, J.A.K., Baesens, B., Viaene, S., Vanthienen, J., Dedene,
G., De Moor, B. and Vandewalle, J. (2004). Benchmarking least squares support vector
machine classifiers. In Machine Learning, 54, 5–32.
[128] Vapnik, V. (1998). Statistical Learning Theory. Wiley-Interscience.
[129] Vapnik, V.N. (1995). The nature of statistical learning theory. Springer-Verlag
New York, Inc.
[130] Wagstaff, K.; Cardie, C.; Rogers, S. and Schroedl, S. (2001) Constrained k-means
clustering with background knowledge. In Proceedings of the Eighteenth International
Conference on Machine Learning, ICML-2001, pages 577–584, Williamstown, MA,
USA.
[131] Weiss, S. M. (2004). Mining with rarity: a unifying framework. SIGKDD Explor.
Newsl., 6, 7–19.
100 / 101
[132] Weiss, S. M. and Provost, F. (2001). The Effect of Class Distribution on
Classifier Learning: An Empirical Study. Technical Report ML-TR-44, Rutgers
University, Department of Computer Science.
[133] Weiss, S. M. and Kulikowski, C. A. (1991). Predictive Data Mining: A Practical
Guide. San Francisco, CA: Morgan Kaufmann.
[134] Wilson, D. (1972). Asymptotic properties of nearest neighbor rules using edited
data. IEEE Trans. Systems, Man, and Cybernetics, 2, 408–421.
[135] Wong, M.L.D., Jack, L.B., Nandi, A.K. (2005) Modified self-organising map for
automated novelty detection applied to vibration signal monitoring. In Signal
Processing and Communications Group, Department of Electrical Engineering and
Electronics, The University of Liverpool, Brownlow Hill, Liverpool, UK.
[136] Ypma, A. e Duin, R. P. W. (200) Novelty detection using Self-Organizing Maps.
In Pattern Recognition Group, 2000, Faculty of Applied Physics Delft University of
Technology.
[137] Zhang, J. & Mani, I. (2003). Knn approach to unbalanced data distributions: A
case study involving information extraction. In Proceedings of the ICML’2003
workshop on learning from imbalanced datasets.
[138] Zhou, Z.H. and Liu, X.Y. (2006). Training cost-sensitive neural networks with
methods addressing the class imbalance problem. In IEEE Transactions on Knowledge
and Data Engineering, 18, 63–77.
[139] Zorriassatine, F.; Al-Habaibeh, A.; Parkin, R. M.; Jackson, M. R. and Coy, J.
(1995) Novelty detection for practical pattern recognition in condition monitoring of
multivariate processes: a case study, In Springer-Verlag London Limited, vol. 25, pp.
954–963.
101 / 101