DISSERTAÇÃO_AnáliseCombinaçãoClassificadores

Prévia do material em texto

Análise de Combinação de
Classificadores usando uma Abordagem
Multiobjetivo baseada em Acurácia e
Número de Classificadores
Sandro Luiz Jailson Lopes Tinôco
Universidade Federal de Ouro Preto
Dissertação submetida ao
Instituto de Ciências Exatas e Biológicas
Universidade Federal de Ouro Preto
para obtenção do título de Mestre em Ciência da Computação
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Catalogação: sisbin@sisbin.ufop.br 
 
 
 
 
T587a Tinôco, Sandro Luiz Jailson Lopes. 
 Análise de combinação de classificadores usando uma abordagem multiobjetivo 
baseada em acurácia e número de classificadores [manuscrito] / Sandro Luiz Jailson 
Lopes Tinôco – 2013. 
 
 115 f.: il. color.; grafs.; tabs. 
 
 Orientador: Prof. Dr. David Menotti Gomes. 
 
 Dissertação (Mestrado) - Universidade Federal de Ouro Preto. Instituto de Ciências 
Exatas e Biológicas. Departamento de Computação. Programa de Pós-graduação em 
Ciência da Computação. 
 Área de concentração: Recuperação e Tratamento da Informação. 
 
 1. Sensoriamento remoto - Teses. 2. Programação linear - Teses. 3. Sistemas de 
recuperação da informação – Códigos numéricos - Teses. I. Gomes, David Menotti. II. 
Universidade Federal de Ouro Preto. III. Título. 
 
Análise de Combinação de Classificadores usando uma
Abordagem Multiobjetivo baseada em Acurácia e
Número de Classificadores
Resumo
O Sensoriamento Remoto é uma forma de obter informações sobre a Terra a partir
do espaço, com a finalidade de melhorar a gestão dos recursos naturais, o uso da terra
e a proteção do meio ambiente. Esse campo do conhecimento tem se beneficiado dos
diversos avanços tecnológicos dentre os quais pode ser citada a imagem hiperespectral.
Este tipo de imagem pode ser composto por centenas de bandas, cada uma delas cor-
respondendo a uma determinada faixa do espectro eletromagnético. Pode-se perceber
a riqueza de informação que tal imagem pode fornecer, conduzindo a uma análise mais
precisa. No entanto, para tratar esse volume de informações, tanto em qualidade quanto
em quantidade, é necessária a utilização de algoritmos e métodos que consigam tirar
proveito de toda a informação fornecida. Uma tarefa comum na análise desses dados é
a geração de mapas temáticos a partir da classificação da cobertura terrestre. Tradici-
onalmente, procura-se desenvolver diferentes algoritmos de classificação e depois aquele
que apresenta o melhor desempenho, ou seja maior acurácia, é escolhido. Este tipo de
metodologia pode acarretar em perdas de importantes informações contidas nos clas-
sificadores descartados. Uma forma de se evitar isso, que tem sido bastante estudada
e utilizada atualmente, é a combinação de múltiplas abordagens de classificação e a
consequente produção de mapas temáticos mais precisos. No presente trabalho, é feita
a combinação de doze abordagens de classificação, obtidas usando três representações
de dados e quatro algoritmos de aprendizagem diferentes. As representações de dados
usadas são a Pixelwise, Extended Morphological Profiles (EMP) e Feature Extraction by
i
Genetic Algorithms (FEGA), que foram classificadas com os algoritmos de aprendiza-
gem Support Vector Machines (SVM) com kernel Radial Basis Function (RBF) e kernel
Linear, K-Nearest Neighbor (KNN) e Multilayer Perceptron Neural Network (MLP).
O método de combinação proposto é baseado em uma combinação linear ponderada,
em que um Programa Linear Inteiro (PLI) encontra os pesos para cada abordagem de
classificação utilizada e é denominado Weighted Linear Combination optimized by In-
teger Linear Programming (WLC-ILP). Para analisar os resultados obtidos, o método
proposto foi comparado a outros métodos de combinação como o Weighted Linear Com-
bination optimized by Genetic Algorithm (WLC-GA) e, os tradicionais, como Majority
Vote (MV) e Average Rule. O (WLC-ILP) superou os resultados dos métodos (MV)
e Average Rule e obteve resultados similares ao (WLC-GA), porém, dez vezes mais
rápido que este. Uma questão ainda em aberto está relacionada a quantos e quais clas-
sificadores de um conjunto utilizar, de forma a obter uma acurácia mais precisa. Não se
sabe ao certo o que faz uma combinação produzir resultados, ainda que não seja sempre
garantido, melhores do que um único classificador. Alguns autores apontam a diver-
sidade de um conjunto como fator principal de êxito de um combinador, no entanto,
não existe uma definição formal, amplamente aceita do que seja diversidade. Uma vez
que é desejável produzir melhores acurácias utilizando o menor número de classificado-
res possível, um Algoritmo Genético Multiobjetivo apresenta-se como meio adequado
para realização desta tarefa. Assim, uma análise e seleção de abordagens de classifica-
ção a serem combinadas por meio de um Algoritmo Genético Multiobjetivo é proposta
neste trabalho, no domínio de imagens hiperespectrais. Ressalta-se que, até o momento,
não foi encontrado na literatura, o emprego desta técnica em classificação de imagens
hiperespectrais de sensoriamento remoto.
ii
Analysis of Classifiers Combiner using a Multiobjective
Approach: based on Accuracy and Number of Classifiers.
Abstract
The Remote Sensing is a form’s information extraction about the Earth from space,
with the aim of improving the management of natural resources, land use and envi-
ronmental protection. This field of knowledge has benefited from many technological
advances among which may be mentioned the hyperspectral image. This type of image
can be composed of hundreds of bands, each corresponding to a particular range of the
electromagnetic spectrum. One can realize the wealth of information that can provide
such an image, leading to a more precise analysis. However, to handle this volume
of information, both in quality and quantity, and required the use of algorithms and
methods which are able to extract the information provided. A common task in data
analysis is the generation of thematic maps from the classification of land cover. Tra-
ditionally, we try to develop different ranking algorithms and then the one that has
the best performance, i.e., higher accuracy is chosen. This type of methodology may
result in loss of important information contained in discarded classifiers. One way to
avoid this, which has been widely studied and used today, is the combination of multiple
approaches to classification and consequent production of thematic maps more accu-
rate. In this study, the combination is done twelve classification approaches, obtained
by using three data representations and four different learning algorithms. Data re-
presentations used are Pixelwise, Extended Morphological Profiles (EMP) and Feature
Extraction by Genetic Algorithms (FEGA), who were classified with the learning al-
gorithms Support Vector Machines (SVM) with kernel Radial Basis Function (RBF)
e kernel Linear, K-Nearest Neighbor (KNN) and Multilayer Perceptron Neural Network
iii
(MLP). The method of combination proposed is based on a weighted linear combina-
tion, where Linear Programming is the weight for each classification approach is used
and referred Weighted Linear Combination optimized by Linear Programming (WLC-
ILP). To analyze the results obtained, the proposed method was compared to other
methods such as the combination Weighted Linear Combination optimized by Genetic
Algorithm (WLC-GA), and the traditional, as Majority Vote (MV) and Average Rule.
The Weighted Linear Combination optimized by Integer Linear Programming (WLC-
ILP) surpassed the results of the methods (MV) and Average Rule and obtained similar
results (WLC-GA), however, ten times faster than this. A still open issue is relatedto
how many and which use a set of classifiers in order to obtain a more precise accuracy.
No one knows for sure what causes a combination produce results, though not always
guaranteed, better than a single classifier. Some authors indicate the diversity of a set
as the main factor of success of a combiner, however, there is no formal definition, it
is widely accepted that the diversity. Since it is desirable to produce better accuracies
using the minimum number of classifiers as possible, an multiobjective genetic algorithm
is presented as a means suitable for this task. Thus, an analysis and selection classifica-
tion approaches to be combined by using a multiobjective genetic algorithm is proposed
in this work in the field of spectral images. It is noteworthy that, to date, not found
in the literature, the use of this technique in the classification of hyperspectral remote
sensing images.
iv
Declaração
Esta dissertação é resultado de meu próprio trabalho, exceto onde referência explícita é
feita ao trabalho de outros, e não foi submetida para outra qualificação nesta nem em
outra universidade.
Sandro Luiz Jailson Lopes Tinôco
v
Agradecimentos
Agradeço a todos que me ajudam direta ou indiretamente neste trabalho.
Agradeço a minha família, pelo aconchego.
Agradeço aos professores, pela preocupação.
Agradeço aos amigos, pelos conselhos.
Agradeço ao David, meu orientador.
Agradeço à UFOP e Ouro Preto, pelos ensinamentos.
Agradeço aos esquecidos não mencionados explicitamente aqui.
Agradeço ao Coordenadoria de Aperfeiçoamento de Pessoal de Ensino Superior (CA-
PES).
Muito Obrigado.
vii
Prefácio
A representação visual da informação desempenha um papel fundamental na vida do
ser humano. No dia-a-dia, as imagens assumem as mais diversas funções como, por
exemplo, representações gráficas em placas de sinalização, o registro fotográfico para
recordação posterior ou, ainda, na manifestação do sentimento em obras de arte. À
medida que se desenvolvem novas tecnologias, surgem novas formas de utilização de
imagens, aumentando sua área de abrangência aos mais diversos campos científicos.
O Sensoriamento Remoto é uma importante área do conhecimento que se utiliza
da representação visual, com a finalidade de obter informações sobre o planeta Terra.
A importância de tais informações reside no fato de que elas auxiliam o homem na
gestão dos recursos naturais, no uso da terra e na proteção do meio ambiente. Pode-se
perceber que a quantidade de dados gerada nesse processo, devido â extensão das áreas
imageadas, também é extensa, tornando a análise manual, uma tarefa quase impossível.
Além disso, a tecnologia desenvolvida para obter essas imagens pode gerar dados que
devem ser processados com a utilização de algoritmos que sejam capazes de aproveitar
o máximo da informação presente neles.
Uma forma de transformar essa informação em conhecimento útil é gerar mapas
temáticos, que são a representação de elementos específicos como, por exemplo, caracte-
rísticas do solo, vegetação entre outros. Diferentes mapas temáticos podem auxiliar em
uma tomada de decisão específica na gestão dos recursos disponíveis. Assim, no presente
projeto, imagens de sensoriamento remoto são classificadas por algoritmos e por métodos
que combinam esses algoritmos visando produzir mapas temáticos mais precisos.
ix
Sumário
Lista de Figuras xv
Lista de Tabelas xix
1 Introdução 1
1.1 Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Organização do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Revisão Bibliográfica 7
2.1 Abordagens de Classificação Hiperespectrais: Representações . . . . . . . 7
2.1.1 Representação Espectral . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Representação Espectral-Espacial . . . . . . . . . . . . . . . . . . 9
2.2 Combinação de Classificadores . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Avaliação da Combinação de Classificadores . . . . . . . . . . . . . . . . 13
3 Fundamentação Teórica 15
3.1 Algoritmos de Aprendizagem de Máquina . . . . . . . . . . . . . . . . . . 15
3.1.1 K-Nearest Neighbor (KNN) . . . . . . . . . . . . . . . . . . . . . 16
3.1.2 Multilayer Perceptron Neural Network (MLP) . . . . . . . . . . . 16
3.1.3 Support Vector Machines(SVM) . . . . . . . . . . . . . . . . . . . 17
3.2 Método de Combinação de Classificadores . . . . . . . . . . . . . . . . . 17
3.3 Otimização Combinatória . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.1 Programação Linear Inteira . . . . . . . . . . . . . . . . . . . . . 21
3.3.2 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.3 Otimização Multiobjetivo . . . . . . . . . . . . . . . . . . . . . . 25
4 Metodologia 29
4.1 Conjunto de Abordagens de Classificação Base . . . . . . . . . . . . . . . 29
4.2 Weighted Linear Combination optimized by Integer Linear Programming
(WLC-ILP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Otimização Multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3.1 Algoritmos Multiobjetivos . . . . . . . . . . . . . . . . . . . . . . 34
4.3.2 Algoritmo Genético Multiobjetivo proposto . . . . . . . . . . . . . 35
5 Experimentos 37
5.1 Bases de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Critérios de Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.1 Protocolo de Treinamento, Validação e Teste . . . . . . . . . . . . 40
5.2.2 Medidas de Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3 Configuração dos Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3.1 Parâmetros das Abordagens de Classificação Base . . . . . . . . . 43
5.3.2 Parâmetros dos Métodos de Combinação . . . . . . . . . . . . . . 44
5.3.3 Algoritmo Genético Multiobjetivo . . . . . . . . . . . . . . . . . . 45
5.4 Esquemas de Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
xii
6 Resultados e Discussões 47
6.1 Base de Dados Indian Pines . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.1.1 Análise dos Resultados do Método de Combinação WLC-ILP . . . 47
6.1.2 Análise dos Resultados do Algoritmo Genético Multiobjetivo . . . 53
6.2 Base de Dados Pavia University . . . . . . . . . . . . . . . . . . . . . . . 53
6.2.1 Análise dos Resultados do Método de Combinação WLC-ILP . . . 54
6.2.2 Análise dos Resultados do Algoritmo Genético Multiobjetivo . . . 56
7 Conclusões e Trabalhos Futuros 59
7.1 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
A Apêndice 61
A.1 Modelo para resolução do Programa Linear do Método WLC-ILP . . . . 61
A.2 Resultados dos Experimentos do Método WLC-ILP . . . . . . . . . . . . 63
A.2.1 Base de Dados Indian Pines . . . . . . . . . . . . . . . . . . . . . 63
A.2.2 Base de Dados Pavia Universtiy . . . . . . . . . . . . . . . . . . . 63
A.3 Resultados dos Experimentos com o Algoritmo Genético Multiobjetivo
proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
A.3.1 Base de Dados Indian Pines . . . . . . . . . . . . . . . . . . . . . 64
A.3.2 Base de Dados Pava University . . . . . . . . . . . . . . . . . . . 64
Referências Bibliográficas 75
xiii
Lista de Figuras
3.1 Perfil de Decisão. Modificado de (Kuncheva, 2004). . . . . . . . . . . . . 19
3.2 Processo de modelagem. Modificado de (Goldbarg and Luna, 2000). . . . 20
3.3 Representação gráfica da região admissível (área colorida de verde) e
de pontos extremos (B, C, E, F) do Algoritmo Simplex. Modificado
de (Goldbarg and Luna, 2000). . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 Fronteira de Pareto. Modificado de (Deb, 2011).. . . . . . . . . . . . . 26
3.5 Representação gráfica de um problema multiobjetivo função f2 (Schaffer,
1985).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.6 Fronteira de Pareto para a função f2 (Schaffer, 1985).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.1 Diagrama WLC-ILP
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Representação do genoma, 1 significa presença e 0 ausência de determi-
nada abordagem de classificação.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Fluxograma do Algoritmo Genético baseado na Fronteira de Pareto pro-
posto.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.1 Base de dados AVIRIS - Indian Pines.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Base de Dados ROSIS - Pavia University . . . . . . . . . . . . . . . . . 40
6.1 Média (asterisco) e intervalo de confiança (barra vertical) de Overall
Accuracy (OA) no conjunto de testes para a base de dados Indian Pi-
nes com conjuntos de treinamento 10%, 15%, 20% e 25% de amostras,
para o Esquema de Avaliação 1, em que todas as abordagens são usadas.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Média (asterisco) e intervalo de confiança (barra vertical) de OA no con-
junto de testes para a base de dados Indian Pines com diferentes conjuntos
de treinamento 10%, 15%, 20% e 25% de amostras, para o Esquema de
Avaliação 2, em que as quatro melhores abordagens são retiradas.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.3 Média (asterisco) e intervalo de confiança (barra vertical) de OA no con-
junto de testes para a base de dados Indian Pines com diferentes conjuntos
de treinamento 10%, 15%, 20% e 25% de amostras, para o Esquema de
Avaliação 3, em que as quatro piores abordagens são retiradas.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.4 Comparação entre os mapas temáticos do Indian Pines obtidos através da
classificação com o melhor classificador Extended Morphological Profiles
(EMP)-Support Vector Machines (SVM) e pelo métodos de combinação
Weighted Linear Combination optimized by Genetic Algorithm (WLC-
GA) e WLC-ILP com todas as abordagens base, com 20% de amostras
de treinamento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.5 Tempo de execução (em segundos) do WLC-ILP e WLC-GA na base de
dados Indian Pines com diferentes conjuntos de treinamento 10%, 15%,
20% e 25% de amostras, para o Esquema de Avaliação 1, em que as todas
as abordagens base são usadas.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.6 Fronteira de Pareto com 25% dos dados de treinamento, para a base dados
AVIRIS - Indian Pines sobre 12 classificadores.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
xvi
6.7 Média (asterisco) e intervalo de confiança (barra vertical) de OA no con-
junto de testes para a base de dados Pavia University com conjuntos de
treinamento 10%, 15%, 20% e 25% de amostras, para o Esquema de Ava-
liação 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.8 Média (asterisco) e intervalo de confiança (barra vertical) de OA no con-
junto de testes para a base de dados Pavia University com diferentes
conjuntos de treinamento 10%, 15%, 20% e 25% de amostras, para o Es-
quema de Avaliação 2.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.9 Média (asterisco) e intervalo de confiança (barra vertical) de OA no con-
junto de testes para a base de dados Pavia University com diferentes
conjuntos de treinamento 10%, 15%, 20% e 25% de amostras, para o Es-
quema de Avaliação 3.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.10 Comparação entre os mapas temáticos do Indian Pines obtidos através
da classificação com o melhor classificador EMP-SVM e pelo métodos de
combinação WLC-GA e WLC-ILP com todas as abordagens base, com
20% de amostras de treinamento. . . . . . . . . . . . . . . . . . . . . . . 57
6.11 Tempo de execução (em segundos) do WLC-ILP e WLC-GA na base de
dados Pavia University com diferentes conjuntos de treinamento 10%,
15%, 20% e 25% de amostras, para o Esquema de Avaliação 1, em que as
todas as abordagens base são usadas.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.12 Fronteira de Pareto com 10% dos dados de treinamento, para a base dados
Pavia University sobre 12 classificadores.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
A.1 Fronteira de Pareto para a base de dados Indian Pines, com 10%, 15%,
20% e 25% de amostras de treinamento. . . . . . . . . . . . . . . . . . . 73
A.2 Fronteira de Pareto para a base de dados Pavia University, com 10%,
15%, 20% e 25% de amostras de treinamento. . . . . . . . . . . . . . . . 74
xvii
Lista de Tabelas
4.1 Abordagens de Classificação. . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.1 Número de amostras por classe para o Indian Pines dataset. . . . . . . . 39
5.2 Número de amostras por classe para o Pavia University dataset. . . . . . 40
6.1 Tempo de execução (em segundos) do WLC-ILP e WLC-GA na base de
dados Indian Pines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.2 Tempo de execução (em segundos) do WLC-ILP e WLC-GA na base de
dados Pavia Universty. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
A.1 Resultados para a base de dados Indian Pines das abordagens individuais:
10% amostras de Validação, 10% amostras de Treinamento e 50% de amostras
de Testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
A.2 Resultados para a base de dados Indian Pines das abordagens individuais:
15% amostras de Validação, 15% amostras de Treinamento e 50% de amostras
de Testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
A.3 Resultados para a base de dados Indian Pines das abordagens individuais:
20% amostras de Validação, 20% amostras de Treinamento e 50% de amostras
de Testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
A.4 Resultados para a base de dados Indian Pines das abordagens individuais:
25% amostras de Validação, 25% amostras de Treinamento e 50% de amostras
de Testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
A.5 Resultados para a base de dados Pavia Universtiy das abordagens indivi-
duais: 10% amostras de Validação, 10% amostras de Treinamento e 50% de
amostras de Testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
A.6 Resultados para a base de dados Pavia Universtiy das abordagens indivi-
duais: 15% amostras de Validação, 15% amostras de Treinamento e 50% de
amostras de Testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
A.7 Resultados para a base de dados Pavia Universtiy das abordagens indivi-
duais: 20% amostras de Validação, 20% amostras de Treinamento e 50% de
amostras de Testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
A.8 Resultados para a base de dados Pavia Universtiy das abordagens indivi-
duais: 25% amostras de Validação, 25% amostras de Treinamento e 50% de
amostras de Testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
xx
“É improfícuo fazer-se com mais o que pode ser feito com menos.”
— William de Ockham
Nomenclatura
AA Average Accuracy
AG Algoritmo Genético
AGM Algoritmo Genético Multiobjetivo
a-MRF adaptative Markov Random Fields
AIS Airborne Imaging Spectrometer
AM Aprendizagem de Máquina
AVIRIS Airborne Visible Infra-Red Imaging Spectrometer
CA Class Accuracy
DBFE Decision Boundary Feature Extraction
DP DecisionProfile
EE Elemento Estruturante
EM Expectation Maximization
EMP Extended Morphological Profiles
FEGA Feature Extraction by Genetic Algorithms
GALIB GAlib: A C++ Library of Genetic Algorithm Components
GDA Generalized Discriminant Analysis
HIAT Hyperspectral Image Analysis Toolbox
HSEG Hierachical Segmentation
xxi
IC Intervalo Confiança
ICA Independent Component Analysis
KFDA Kernel Fisher Discriminant Analysis
KNN K-Nearest Neighbor
KNWFE Kernel Nonparametric Weighted Feature Extraction
KPCA Kernel Principal Component Analysis
LIBSVM A Library for Support Vector Machines
LDA Linear Discriminant Analysis
MCS Multiple Classification System
MV Majority Vote
MRF Markov Random Fields
ML Maximum Likelihood
MM Morfologia Matemática
MP Morphological Profile
MLP Multilayer Perceptron Neural Network
MSSC Multiple Spectral-Spatial Classifier
MSF Minimum Spanning Forest
NLPCA Nonlinear Principal Component Analysis
NWFE Nonparametric Weighted Feature Extraction
OA Overall Accuracy
PC Principal Component
PCs Principal Components
PCA Principal Component Analysis
PLI Programação Linear Inteira
xxii
PR Post Regularization
RBF Radial Basis Function
RBFNN Radial Basis Function Neural Networks
Reg-AB Regularized AdaBoost
Reg-RBFNN Regularized Radial Basis Function Neural Networks
ROSIS Reflective Optics System Imaging Spectrometer
RFS Random Feature Selection
RN Rede Neuronal
RNA Rede Neuronal Artificial
SR Sensoriamento Remoto
SVM Support Vector Machines
SVDSS Singular Value Decomposition Band Subset Selection
WLC-GA Weighted Linear Combination optimized by Genetic Algorithm
WLC-ILP Weighted Linear Combination optimized by Integer Linear Programming
xxiii
Caṕıtulo 1
Introdução
Sensoriamento Remoto (SR) pode ser definido, de forma mais abrangente, como a aqui-
sição de informações sobre um objeto sem estar em contato físico com ele, ou seja, são
técnicas para a coleta de imagens ou outras formas de dados, que serão posteriormente
tratados e analisados, sobre um objeto a partir de medições feitas à distância do ob-
jeto (Elachi and Van Zyl, 2006). (Lillesand, 2006) define SR como a ciência e a arte
de obter informações sobre um objeto, área ou fenômeno através da análise de dados
adquiridos por um dispositivo que não está em contato com o objeto, área ou fenômeno
sob investigação. O Sensoriamento Remoto Espacial, objeto do presente trabalho, de
acordo coma Resolução 41/65 da Organização das Nações Unidas (ONU, 1986), é concei-
tuado como uma forma de obter informações sobre a Terra a partir do espaço, utilizando
as propriedades das ondas eletromagnéticas emitidas, refletidas ou difracionadas pelos
objetos sensoriados, com a finalidade de melhorar a gestão dos recursos naturais, o uso
da terra e a proteção do meio ambiente. É uma tecnologia que envolve um conjunto de
programas e equipamentos para auxiliar o homem em suas observações sobre o planeta.
Essa coleta de dados e informações de objetos através da medição de sinais à longas
distâncias (Prasad et al., 2011), geralmente, é feita por meio de sensores transportados
em aviões ou em satélites (Plaza et al., 2009).
Nas últimas décadas novos instrumentos de imageamento começaram a ser desen-
volvidos. Como exemplo, pode ser citado o sensor Airborne Visible Infra-Red Imaging
Spectrometer (AVIRIS), que cobre uma faixa de espectro eletromagnético que vai de
0, 4 µm a 2, 5 µm, com resolução espectral de 10 nm, contendo mais de duzentas ban-
das (canais) espectrais (Green et al., 1998). Com isso, o imageamento espectroscópico
tem permitido avanços na análise e interpretação de materiais sobre a superfície terres-
1
1. INTRODUÇÃO
tre (Plaza et al., 2009), fornecendo imagens compostas de algumas dezenas até centenas
de bandas espectrais (Plaza et al., 2009; Tarabalka, 2010). Cada banda espectral repre-
senta a reflectância (quantidade de energia refletida) de um material em um determinado
comprimento de onda. Então, a resposta espectral para cada posição (canal) do pixel
fornece uma imagem denominada hiperespectral ou hipercubo (Chang, 2007). Imagens
hiperespectrais são uma evolução das imagens multiespectrais, formadas por quatro a
sete canais espectrais, e permitem analisar materiais que não podem ser identificados
por estas devido a baixa resolução dos dados multiespectrais (Chang, 2007; Plaza et al.,
2009).
Dados de SR tem sido usados para vários propósitos, como: gestão de grandes ca-
tástrofes, planejamento e gerenciamento urbano, monitoramento ambiental, agricultura,
silvicultura, etc. (Benediktsson et al., 2007; Chang, 2007; Prasad et al., 2011). Na mai-
oria dessas aplicações, uma análise automática é requerida (Benediktsson et al., 2007)
permitindo grandes avanços, principalmente para a interpretação (classificação) dos di-
versos materiais terrestres (Chang, 2007; Prasad et al., 2011). A primeira etapa consiste
de uma classificação de cada pixel da imagem (Benediktsson et al., 2007). Nessa etapa,
como em todos os projetos de reconhecimento de padrões, objetiva-se obter o melhor
desempenho de classificação possível. Tradicionalmente, depois de avaliados, escolhe-se
o esquema com o melhor desempenho, como solução final para o problema de classifica-
ção (Kittler et al., 1998).
No entanto, tem-se observado que, nos classificadores descartados, os conjuntos de
padrões mal classificados não se sobrepõem, sugerindo que os mesmos poderiam oferecer
informação complementar que poderiam melhorar o desempenho do classificador esco-
lhido (Kittler et al., 1998). Essa complementaridade pode ser obtida usando representa-
ções diferentes de uma mesma entrada (Alpaydin, 1998). Além disso, em sensoriamento
remoto, existem dados que fornecem informação espacial com resoluções entre 1 e 30
metros por pixel (Chang, 2007), o que representa uma grande capacidade de distinguir
estruturas de objetos complexos, podendo aumentar a acurácia na classificação. Com
a intenção de elevar o número de acertos na classificação, diversos autores propõem a
junção da informação espectral com a informação espacial (espectral-espacial) (Chang,
2007; Plaza et al., 2009; Prasad et al., 2011).
No presente projeto, é proposto um método consensual para combinar classificadores,
utilizando uma combinação linear ponderada das probabilidades de saída de cada abor-
dagem de classificação. Essa proposta utiliza Programação Linear Inteira (PLI) para
encontrar os pesos de cada abordagem de classificação, e é denominada de Weighted
2
1. INTRODUÇÃO
Linear Combination by Integer Linear Programming WLC-ILP (Tinôco et al., 2013).
As abordagens usadas na combinação foram construídas de forma a constituírem
um conjunto diverso (Polikar, 2006) e com informação complementar (Alpaydin, 1998).
Para isso, são usadas as representações de dados Pixelwise (Melgani and Bruzzone, 2004)
que utiliza apenas informação espectral; EMP (Benediktsson et al., 2005), que utiliza
informação espacial extraída através de operações morfológicas e Feature Extraction
by Genetic Algorithms (FEGA) (Santos et al., 2012c), que usa Algoritmo Genético
(AG) para selecionar características. Para a classificação, são utilizados algoritmos de
aprendizagem tradicionais na literatura como SVM (Melgani and Bruzzone, 2004),
com kernel Radial Basis Function (RBF) e kernel Linear , Multilayer Perceptron Neural
Network (MLP) (Benediktsson et al., 2005) e K-Nearest Neighbor (KNN) (Cover and
Hart, 1967). De forma, que o conjunto de classificadores para combinação contém 12
abordagens de classificação.
A segunda proposta deste trabalho visa analisar combinações de classificadores atra-
vés de um Algoritmo Genético Multiobjetivo (AGM) baseado na Fronteira de Pareto.
Alguns autores apontam a diversidade do conjunto de classificadores como fator deter-
minante para o sucesso da combinação de classificadores (Polikar, 2006), no entanto,
não existe uma definição formal de diversidade amplamente aceita (dos Santos et al.,
2006; Gabrysa and Rutab, 2006; Kuncheva, 2004; Kuncheva and Whitaker, 2003).En-
tão, através de um AGM, que realiza uma busca dentro do espaço de soluções possíveis,
pretende-se obter combinações mais eficientes (menores) mantendo-se ou melhorando a
eficácia (acurácia) de classificação.
Os experimentos foram realizados nas bases de dados de Sensoriamento Remoto
Indian Pines e Pavia University, imagens hiperespectrais obtidas pelos sensores AVI-
RIS (Green et al., 1998) e Reflective Optics System Imaging Spectrometer (ROSIS)
(Gege et al., 1998), respectivamente. Para verificar a eficiência do método de combina-
ção proposto, o WLC-ILP foi comparado com métodos de combinação como WLC-GA
e, tradicionais, como Majority Vote (MV) e Average rule.
1.1 Justificativa
A quantidade de dados gerada por Sensoriamento Remoto é muito grande, o que torna
uma análise manual uma tarefa impossível. Além disso, os dados adquiridos neste sis-
3
1. INTRODUÇÃO
tema, possuem uma riqueza de informação que deve ser bem aproveitada, como é o caso
das imagens hiperespecrais. Faz-se necessário, então, o uso de métodos e algoritmos
que consigam tirar proveito de tal informação de maneira eficiente. A combinação de
classificadores tem sido bastante empregada, de maneira geral, com o objetivo de uti-
lizar toda a informação disponível, uma vez que a utilização de um único classificador
não consegue abranger todo o espaço de classificação. Combinar classificadores leva à
questão de como conseguir o máximo de acurácia, qual característica o algoritmo de
aprendizagem deve possuir para isso e qual a quantidade de elementos que o conjunto a
ser combinado deve ter.
Um método, como AGM, que consiga relacionar máxima acurácia e menor número de
classificadores, está alinhado a metodologias clássicas de investigação como o Principio
da Parcimônia ou Navalha de Occam (Agarwal et al., 2011), que preceituam que não se
deve fazer com mais que pode ser feito eficientemente com menos. A Navalha de Occam
considera que, havendo mais de uma solução ou explicação para um problema, deve-se
escolher a solução ou explicação mais simples, desde que esta solução (mais simples)
resolva satisfatoriamente o problema (Blumer et al., 1987; Nunez et al., 2004). Este
princípio, um dos principais critérios científicos de todos os tempos, que tem as leis de
Newton e as equações de Maxwell do electromagnetismo como exemplos de sua aplica-
bilidade, também tem sido aplicado no desenvolvimento de mecanismos computacionais
de descoberta de conhecimento (Blumer et al., 1987).
1.2 Objetivos
1 Propor uma forma de combinação de múltiplas abordagens de classificação,
usando PLI, que é mais rápida, como alternativa ao WLC-GA (Santos et al.,
2013) que usa AG.
2 Comparar o método proposto com métodos tradicionais da literatura e com
o WLC-GA.
3 Produzir mapas temáticos que sejam o mais precisos possível.
4 Analisar combinação de múltiplas abordagens de classificação.
5 Apresentar um método para obter combinações de classificadores mais eficientes
(menores) mantendo-se a eficácia (acurácia) através de um AGM baseado na Fron-
teira de Pareto.
4
1. INTRODUÇÃO
1.3 Contribuições
1 Utilização de PLI para encontrar pesos adequados de cada abordagem de clas-
sificação para uma combinação ponderada aplicada à imagens hiperespectrais de
sensoriamento remoto.
2 Apresentar um método para análise de combinações de classificadores em imagens
hiperespectrais de sensoriamento remoto, até o momento não empregado nesta
área, conforme literatura pesquisada.
1.4 Organização do Texto
O texto desta dissertação encontra-se organizado da seguinte forma. No Capítulo 1 é
feita a contextualização do problema e da solução proposta. O Capítulo 2 apresenta uma
revisão bibliográfica sobre o estado da arte de métodos de classificação com ênfase àqueles
usados em imagens hiperespectrais de sensoriamento remoto. O Capítulo 3 apresenta
os conceitos e fundamentos dos algoritmos e métodos utilizados na abordagem proposta
neste trabalho. No Capítulo 4 é mostrado como as base de dados foram tratadas e os
algoritmos propostos foram construídos. O Capítulo 5 mostra como os experimentos
foram configurados e realizados. No Capítulo 6, os resultados obtidos são apresentados
e analisados. No Capítulo 7 uma conclusão e discussão sobre trabalhos futuros são
realizados.
5
6
Caṕıtulo 2
Revisão Bibliográfica
Este capítulo apresenta o estudo prospectivo realizado com a finalidade de conhecer
o estado da arte e os principais conceitos da literatura técnica relacionados ao desen-
volvimento do projeto proposto. Tipos de representações de dados e os algoritmos de
aprendizagem utilizados para classificá-los são apresentados. São mostrados, ainda, mé-
todos de combinação de classificadores e conceitos relacionados à sua eficiência
2.1 Abordagens de Classificação Hiperespectrais: Re-
presentações
Nesta Seção, são apresentadas duas formas de se utilizar a informação para classificação
de dados. Uma que leva em consideração somente a informação contida em cada pixel,
a representação espectral. E outra que relaciona a informação de cada pixel à do pixel
vizinho, a representação espectral-espacial.
2.1.1 Representação Espectral
A tarefa de classificação de imagens hiperespectrais de sensoriamento remoto consiste
basicamente em atribuir um rótulo específico a cada um dos pixels que formam a
imagem. A classificação que se baseia apenas na informação espectral é denominada
de Pixelwise e cada pixel é considerado uma amostra cujo conjunto de características é
seu espectro (Tarabalka, 2010). Uma vez que imagens hiperespectrais apresentam alta
7
2. REVISÃO BIBLIOGRÁFICA
dimensionalidade, são necessários algoritmos de aprendizagem capazes de se adequarem
a essa situação (Plaza et al., 2009).
Neste sentido, tem-se mostrado que algoritmos de aprendizagem baseados em ker-
nel são mais eficazes que os tradicionais métodos de aprendizagem. Métodos baseados
em kernel transformam os dados originais para um novo espaço de características onde
se consegue uma melhor separação entre as classes. (Melgani and Bruzzone, 2004)
aplicaram o algoritmo de aprendizagem SVM a imagens hiperespectrais, o qual se re-
velou uma efetiva e poderosa ferramenta para a interpretação desses dados, superando
métodos tradicionais como: Regularized Radial Basis Function Neural Networks (Reg-
RBFNN) e KNN. (Camps-Valls and Bruzzone, 2005) analisaram e compararam, em
relação à interpretação de dados hiperespectrais, vários algoritmos baseados em kernel
como Reg-RBFNN, SVM, Kernel Fisher Discriminant Analysis (KFDA), e Regularized
AdaBoost (Reg-AB). Esse estudo revelou a superioridade do algoritmo SVM que, desde
então, tem sido apontado por diversos autores por causa de seu bom comportamento
face à escassez e alta dimensionalidade das amostras de treinamento. Sua eficácia é
considerada como referência em vários trabalhos da literatura (Tarabalka, 2010).
De maneira geral, rotular grandes quantidades de dados é um trabalho difícil, e no
domínio de imagens hiperespectrais de sensoriamento remoto é necessário ainda um tra-
balho de campo, o que dificulta a produção de dados com referência. Com a finalidade de
minimizar o problema da escassez de dados hiperespectrais rotulados, técnicas de apren-
dizagem ativa combinadas à aprendizagem semi-supervisionada estão sendo cada vez
mais utilizadas. Combinando informações de amostras rotuladas e não rotuladas, amos-
tras que maximizam o ganho de informação na etapa de aprendizado são identificadas
permitindo maior robustez na classificação mesmo utilizando conjuntos de treinamento
pequenos (Li et al., 2011, 2010; Tuia and Camps-Valls, 2011).
A escassez de dados hiperespectrais rotulados gera, ainda, um outro problema:
quanto maior a dimensionalidade, maior será o número de amostras de treinamento
necessárias ao bom desempenho do algoritmo de aprendizagem (Alpaydin, 2010; Mit-
chell, 1997). É importante salientar que dimensionalidade é o conjunto de características
presentes nos dados. Métodos de seleção e extração de características têm o objetivo de
manter, até mesmomelhorar, o poder de discriminação dos dados ao mesmo tempo que
procura diminuir o conjunto de características.
(Kuo et al., 2009) compararam os principais métodos de extração de características
discutidos na literatura utilizando diferentes tipos de classificadores: SVM, Maximum
8
2. REVISÃO BIBLIOGRÁFICA
Likelihood (ML) e KNN em diversas configurações de amostragem de treinamento.
Neste trabalho, foi apresentado o Kernel Nonparametric Weighted Feature Extraction
(KNWFE) um método que se utiliza de propriedades dos métodos kernel-based para es-
tender o tradicional Nonparametric Weighted Feature Extraction (NWFE). O KNWFE
foi comparado com diversos métodos lineares e não-lineares de extração de características
presentes na literatura técnica, são eles: Principal Component Analysis (PCA), Kernel
Principal Component Analysis (KPCA), Independent Component Analysis (ICA),
Linear Discriminant Analysis (LDA), kernel-based LDA ou Generalized Discriminant
Analysis (GDA), Decision Boundary Feature Extraction (DBFE) e o tradicional NWFE.
O KNWFE apresentou o melhor desempenho, em termos de acurácia, do que os demais
métodos, entretanto, não houve um classificador em comum que obtivesse o melhor de-
sempenho em todas as condições de testes realizados. Encontrar a melhor combinação
- extração de características + classificador - que possua a melhor acurácia em todas as
bases de dados, é um problema considerado de difícil tratamento (Bakos and Gamba,
2011; Kuo et al., 2009).
Outra maneira de reduzir a dimensionalidade nos dados é conhecida como seleção de
características (Bishop, 2006) na qual, diferentemente da extração, não há nenhum tipo
de transformação nos dados originais. Existem, basicamente, dois tipos de seleção de
características: filter e wrapper. Abordagens do tipo wrapper conduzem uma busca uti-
lizando informação proveniente de um classificador (Bishop, 2006), como nos trabalhos
de (Bazi and Melgani, 2006; Pal and Foody, 2010; Pedergnana et al., 2012). Abor-
dagens filter (Santos et al., 2012a; Velez-Reyes and Jimenez, 1998; Velez-Reyes et al.,
2000; Yu and Liu, 2003) são completamente independentes do processo de classifica-
ção. Algoritmos baseados em abordagens wrapper tendem a produzir subconjuntos mais
adequados para o classificador, embora, em sua maioria, sejam mais lentos que aqueles
baseados em filter (Bishop, 2006; Kohavi and John, 1997).
2.1.2 Representação Espectral-Espacial
Outra forma de melhorar o desempenho da classificação consiste em acrescentar infor-
mação espacial à espectral, obtendo-se, assim uma informação contextual, para inter-
pretação de imagens hiperespectrais de sensoriamento remoto (Tarabalka et al., 2010c;
Zhon and Wang, 2010). Uma primeira estratégia para isso modela informações con-
textuais nas estruturas intrínsecas dos classificadores (Jackson and Landgrebe, 2002;
Neher and Srivastava, 2005; Sarkar et al., 2002). As informações contextuais podem
9
2. REVISÃO BIBLIOGRÁFICA
ainda regularizar um mapa temático produzido usando um filtro da maioria, e os pixels
desse mapa serem novamente rotulados conforme sua vizinhança, processo conhecido
como Post Regularization (PR) (Tarabalka et al., 2009b). (Tilton, 1998) propõe um
método baseado em crescimento de regiões, para a segmentação de imagens multies-
pectrais, Hierachical Segmentation (HSEG), em que uma segmentação hierárquica é
realizada iterativamente rotulando pixels de acordo com a região mais semelhante. O
método HSEG foi estendido ao domínio das imagens hiperespectrais (Tilton et al., 2006)
fornecendo resultados promissores.
Outro método de segmentação de imagens é Watershed uma técnica de morfologia
matemática para segmentação de imagens (Facon, 1996; Serra, 1982). (Tarabalka et al.,
2010b) propuseram uma extensão desse algoritmo ao domínio das imagens hiperespec-
trais em que regiões segmentadas da imagem hiperespectral são combinadas usando MV,
com uma classificação Pixelwise usando SVM. Usando essa abordagem, mapas temá-
ticos com regiões mais homogêneas são obtidos (Tarabalka et al., 2008, 2010b). Um
problema desse algoritmo é a oversegmentation (Tarabalka et al., 2010b). Para mi-
nimizar esse problema (Tarabalka et al., 2009a) propuseram controlar a segmentação
por um conjunto de pixels denominado sementes que são selecionadas através do SVM
com saída probabilística. Foram reportados índices de acurácia superiores à aborda-
gem tradicional, no entanto, a desvantagem da nova abordagem é que a escolha das
sementes é muito dependente do desempenho na classificação Pixelwise (Fauvel et al.,
2012). Para aumentar a confiabilidade das sementes selecionadas, (Tarabalka et al.,
2010a) propuseram uma abordagem baseada em Multiple Classification System (MCS).
Usando o esquema de MV, essa nova abordagem, denominada de Multiple Spectral-
Spatial Classifier (MSSC), seleciona automaticamente as sementes que são comuns entre
os vários classificadores.
Algoritmos de segmentação como HSEG (Tilton, 1998), Watershed (Tarabalka et al.,
2010c), ISODATA (Tarabalka et al., 2009a), Expectation Maximization (EM) (Tara-
balka et al., 2009a) e Minimum Spanning Forest (MSF) (Tarabalka et al., 2010b) têm
sido bastante usados para a regularização de uma classificação do tipo Pixelwise, no
domínio das imagens hiperespectrais de sensoriamento remoto. Esses métodos são for-
temente dependentes da classificação Pixelwise e falhas nesta etapa podem ocasionar
classificações errôneas em regiões da imagem.
Uma estratégia, para unir informação espacial e espectral, incorpora informação con-
textual nas características extraídas da imagem. Informação espacial e espectral são
combinadas em um só vetor de características às quais algum algoritmo de aprendiza-
10
2. REVISÃO BIBLIOGRÁFICA
gem pode ser aplicado posteriormente (Benediktsson et al., 2005; Fauvel et al., 2008,
2009; Plaza et al., 2009). (Shen and Lia, 2011) propuseram uma abordagem baseada
na 3-D Gabor-Wavelet para a classificação Pixelwise para unir a informação espectral e
espacial, em que cada pixel é representado por uma informação extraída pela Wavelet
de Gabor. Essa abordagem apresentou elevados índices de acurácia mesmo utilizando
poucas amostras de treinamento.
Uma clássica abordagem probabilística para modelar informação contextual/espa-
cial (Plaza et al., 2009) é a Markov Random Fields (MRF), sobre a qual existe uma
extensa literatura (Jackson and Landgrebe, 2002; Neher and Srivastava, 2005; Salzens-
tein and Collet, 2006). (Tarabalka et al., 2010d) propuseram a integração de SVM
e MRF ( SVM-MRF) na qual uma classificação Pixelwise usando SVM probabilístico é
realizada e, em seguida, refinada através de uma regularização usando MRF. Algumas
limitações desse método foram tratadas por (Zhang et al., 2011) adaptative Markov
Random Fields (a-MRF), elevando os índices de acurácia em relação ao ( SVM-MRF)
originalmente proposto.
Uma alternativa para modelar informação espectral-espacial aplicada em imagens
multi-espectrais e hiperespectrais é conhecida como EMP (Fauvel et al., 2012; Plaza
et al., 2009) que se baseia em operações morfológicas (Fauvel et al., 2012) de fecha-
mento e abertura por reconstrução (Serra, 1982) criando o chamado Morphological
Profile (MP) (Benediktsson et al., 2005). Em uma primeira etapa, algum método de
extração de características é aplicado mantendo a informação espectral e, também, di-
minuindo o número total de canais da imagem que serão utilizados na construção de
cada MP (Benediktsson et al., 2005; Fauvel et al., 2012; Plaza et al., 2009). Em seguida,
efetua-se uma operação morfológica (abertura ou fechamento por reconstrução) sobre
cada MP, utilizando um Elemento Estruturante (EE) de vários tamanhos diferentes.
Os MP dessa segunda etapa são concatenados juntamente com as características extraí-
das na primeira etapa, assim, informações espectrais-espaciais são codificadas em um
único conjunto de características formando então o EMP (Benediktsson et al., 2005).
A classificação pode ser feita, então, utilizando um algoritmode aprendizagem para
aprender e inferir sobre esse novo conjunto de características. Em (Benediktsson et al.,
2005) essa tarefa foi realizada com MLP. Tradicionalmente o algoritmo de extração
de características PCA tem sido empregado com EMP (Benediktsson et al., 2005), no
entanto, existem outros estudos que propõem o uso de outros algoritmos, tais como
ICA (Dalla Mura et al., 2011; Palmason et al., 2005), KPCA (Fauvel et al., 2009) e
PCA não linear (Nonlinear Principal Component Analysis (NLPCA)) (Licciardi et al.,
11
2. REVISÃO BIBLIOGRÁFICA
2012), que apresentaram resultados significativamente melhores em relação ao PCA.
Ainda, (Fauvel et al., 2008) propuseram a aplicação de algoritmos supervisionados de
extração de características, como DBFE e NWFE, sobre os dados hiperespectrais origi-
nais e também sobre o EMP, obtendo um novo conjunto mais compacto e discriminativo
de características do que aquele produzido pelo EMP.
2.2 Combinação de Classificadores
Existem, basicamente, duas estratégias para combinar classificadores: fusão e seleção.
Na fusão, supõe-se que cada classificador tem o conhecimento de todo o espaço de carac-
terísticas, já, na seleção, cada classificador conhece bem determinada parte do espaço e é
responsável pelos objetos desta parte. O projeto de seleção de classificadores garante ao
menos a mesma acurácia de treinamento do melhor classificador individual (Kuncheva,
2004).
Em dados de sensoriamento remoto, alguns estudos apontam a associação, ou fu-
são, de múltiplos sensores como uma técnica adequada para agregar mais informações
(Benediktsson and Kanellopoulos, 1999; Briem et al., 2002; Luo and Kay, 1989). (Bene-
diktsson and Swain, 1992; Benediktsson et al., 1997) avaliaram métodos de combinação
consensual (consensus theoretic methods) (Kuncheva, 2004) para classificação de dados
de sensoriamento remoto de múltiplas fontes. Foram investigados diferentes métodos
estatísticos lineares e também não-linear baseado em Rede Neuronal (RN) com a fina-
lidade de encontrar pesos mais adequados para as regras de combinações consensuais.
Ainda utilizando dados de múltiplas fontes, outros métodos de combinação estão sendo
utilizados (Alpaydin, 2010; Kittler et al., 1998; Kuncheva, 2004), como bagging (Brei-
man, 1996), boosting (Schapire, 1989), stacked generalization (Wolpert, 1992) e casca-
ding (Kaynak and Alpaydin, 2000).
O uso de métodos de combinação de classificadores em dados de sensoriamento re-
moto tem acontecido no domínio de imagens hiperespectrais. (Fauvel, 2007) utilizou a
teoria dos conjuntos fuzzy e (Lee and Ersoy, 2007) usaram RN consensuais e hierárquicas
para produzir múltiplos classificadores. (Marpu et al., 2009) utilizaram Class-Dependent
Neural Networks e a medida de distância Bhattacharya para seleção das características
que melhor identificam determinada classe. Nesta linha, (Waske et al., 2010), usando
Random Feature Selection (RFS), SVM e a regra de combinação MV, investigaram como
a acurácia da classificação dessas imagens é influenciada pelo número de características
12
2. REVISÃO BIBLIOGRÁFICA
e o tamanho do conjunto de classificadores. (Santos et al., 2013) propõem combinar
classificadores por meio de uma regra de soma ponderada e que encontra os pesos utili-
zando um AG. Os resultados obtidos foram superiores aos de regras de combinação como
Média e MV. Uma alternativa ao AG, proposta neste trabalho, é a utilização de um PLI
para encontrar os pesos. A acurácia dos mapas temáticos produzidos pelas abordagens
mencionadas foi superior àquela obtida por sistemas de classificação que usam apenas
um classificador.
2.3 Avaliação da Combinação de Classificadores
Como visto na Seção 2.2, tem-se obtido excelentes resultados combinando classificado-
res. Existem três razões que possibilitam a construção de bons conjuntos de classifi-
cadores (Polikar, 2006). A primeira razão é estatística. O algoritmo de aprendizagem
pode ser percebido como uma busca, no espaço de hipóteses H, pelas melhores hipóteses.
Ocorre um problema estatístico quando a quantidade de dados de treinamento disponível
é muito menor que o tamanho do espaço de hipóteses. Com isso algoritmos diferentes
podem fornecer uma mesma acurácia sobres estes dados de treinamento. Combinando
estes algoritmos reduz-se o risco de escolher um classificador ruim (Dietterich, 2000).
A segunda razão é computacional. Muitos algoritmos de aprendizagem realizam busca
local ficando sujeitos a estacionarem em um ótimo local. Nos casos em que há muitos
dados de treinamento, isso pode acontecer, impedindo que o algoritmo encontre a me-
lhor hipótese. Uma combinação desses algoritmos pode fornecer uma aproximação da
função desconhecida melhor que um único classificador (Dietterich, 2000). A terceira
razão é representacional. Pode acontecer que o espaço do classificador não contenha o
classificador ótimo. Por exemplo, se o classificador ótimo é não-linear, mas o classifica-
dor escolhido é linear, este não será capaz de encontrar a solução ótima do problema.
No entanto, um conjunto de classificadores lineares pode aproximar qualquer fronteira
de decisão (Dietterich, 2000; Kuncheva, 2004). Algoritmos de aprendizagem falham nes-
tas três questões, então, métodos de combinação tem a promessa de reduzir, e talvez
eliminar, estas falhas (Dietterich, 2000).
Alguns autores apontam que a questão chave para o melhor desempenho da com-
binação de classificadores em relação à utilização de um único classificador é a diver-
sidade (Kuncheva, 2004; Polikar, 2006). Classificadores individuais cometem erros em
diferentes instâncias. Então se cada classificador comete erros diferentes, uma com-
13
2. REVISÃO BIBLIOGRÁFICA
binação destes classificadores pode reduzir o erro total (Polikar, 2006). Um conjunto
formado por tais classificadores, isto é, cujas fronteiras de decisão são adequadamente
diferentes umas das outras, é dito diverso (Polikar, 2006). Em (Brown and Kuncheva,
2010), os autores propõem o conceito de “boa” e “má” diversidade, para a regra MV.
Um valor maior da “boa” diversidade reduz o erro da MV, ao passo que um valor maior
de “má” diversidade aumenta o erro. Contudo, não existe uma definição estrita de diver-
sidade amplamente aceita (Brown and Kuncheva, 2010; Kuncheva and Whitaker, 2003).
Além disso, ainda não está clara qual a relação entre diversidade e acurácia (Brown and
Kuncheva, 2010; dos Santos et al., 2006).
(Gabrysa and Rutab, 2006) usaram diversidade para reduzir o erro de generalização e
concluíram que esta não é uma boa medida para encontrar combinação de classificadores
com bom resultado. O desempenho da combinação de classificadores depende de uma
seleção cuidadosa dos classificadores a serem combinados. Uma forma de saber qual a
melhor combinação, ou seja, quantos e quais classificadores utilizar, seria realizar cada
combinação possível dentro de um dado conjunto de classificadores. Pode-se observar
que para um número grande de classificadores, esta tarefa demandaria um alto custo
computacional, pois, existem 2n − 1 combinações possíveis, então, para um número de
classificadores n = 12, seriam 4095 possibilidades. Outra forma, visto que o espaço de
busca é grande, poderia ser a utilização de algoritmos que otimizam a busca, como os
Algoritmos Evolucionários. Ressalta-se que, além do desempenho em termos de acurácia,
é interessante que se obtenha também uma combinação com um conjunto menor de
classificadores. Dada a característica do problema, em que se busca, por um lado,
maximizar a precisão e, por outro, minimizar o número de classificadores, uma possível
solução é usar um AGM (dos Santos et al., 2006).
14
Caṕıtulo 3
Fundamentação Teórica
Este capítulo apresenta os conceitos e fundamentos dos algoritmos e métodos utilizados
na abordagem proposta neste trabalho. São detalhados algoritmos de aprendizagem de
máquina tradicionais como KNN, SVM e MLP. Conceitos relacionados à Combinação
de Classificadores são apresentados. São mostradas, também, duas formas de tratar
problemasde otimização: Programação Linear e Otimização Multiobjetivo.
3.1 Algoritmos de Aprendizagem de Máquina
Aprendizagem de Máquina (AM) é um campo de pesquisa da Inteligência Artificial so-
bre o qual existe uma vasta literatura (Alpaydin, 2010; Bishop, 2006; Duda et al., 1995;
Mitchell, 1997; Scholkopf and Smola, 2001; Theodoridis and Koutroumbas, 2003). Algo-
ritmos de AM são métodos capazes, entre outras habilidades, de extrair conhecimento a
partir de amostras de dados e, em geral, são utilizados de modo a gerar classificadores
para um conjunto de amostras. Por classificação entende-se o processo de atribuir, a
uma determinada informação, o rótulo da classe a qual ela pertence (Russell and Norvig,
2003). Com isso em vista, as técnicas de AM visam induzir, a partir de um conjunto
de treinamento, um classificador que deve ser capaz de prever a classe de quaisquer
amostras do domínio em que ele foi treinado. Nesta seção serão apresentados os concei-
tos básicos de três algoritmos de aprendizagem bem conhecidos na literatura que serão
utilizados neste trabalho: KNN, MLP e SVM.
15
3. FUNDAMENTAÇÃO TEÓRICA
3.1.1 K-Nearest Neighbor (KNN)
O algoritmo KNN (Cover and Hart, 1967) classifica novas amostras de acordo com as
K amostras do conjunto de treinamento mais próximas a essas novas amostras. O KNN
usa uma medida de distância para definir a semelhança (proximidade) de uma amostra
com outra, o que pode ser aplicado aos pixels (amostras) de imagens hiperespectrais, que
estão em algum espaço de característica (Duda et al., 1995; Mitchell, 1997). Dado um
conjunto de n pares {(x1, θ1) ,...,(xn, θn)}, em que xi toma valores de um espaço X, e θi
toma valores de um conjunto 1, 2, ...,M . Considera-se cada θi como o índice da categoria
a que pertence o i-ésimo indivíduo, e cada xi o resultado de um conjunto de medições
feitas sobre aquele indivíduo. Se é dado um novo par (x, θ), no qual apenas o valor de x é
conhecido e deseja-se estimar θ a partir do conjunto de pontos classificados corretamente,
x
′
n ∈ {x1, x2, ..., xn} é o vizinho mais próximo de x se min d(xi, x) = d(x
′
n, x), com
i = 1, 2, ..., n. A regra vizinho mais próximo decide que x pertence à categoria θ′n de seu
vizinho mais próximo x′n (Cover and Hart, 1967). A distância d é determinada por uma
métrica de similaridade, geralmente a distância Euclidiana. Apesar de sua simplicidade,
o KNN apresenta um bom desempenho, mas possui algumas desvantagens (Mitchell,
1997) como alto custo computacional para calcular a distância entre a nova amostra e
todas outras do conjunto de treinamento; baixa precisão em espaços de características
muito elevados e dificuldade em se definir o melhor valor do parâmetro K.
3.1.2 Multilayer Perceptron Neural Network (MLP)
Uma Rede Neuronal Artificial (RNA) de múltiplas camadas, ou MLP, é composta por
um conjunto de nós fonte os quais representam a camada de entrada ( input layer),
uma ou mais camadas escondidas ( hidden layer), e uma camada de saída ( output
layer) (Duda et al., 1995; Mitchell, 1997). MLP é uma generalização da RNA Percep-
tron comum (Mitchell, 1997), e ao contrário desta, é capaz de aprender funções não
lineares. Cada neurônio escondido utiliza uma função de transferência para mapear o
espaço de entrada, então, outras camadas podem aprender as características mapeadas
como simples discriminantes lineares. Padrões não lineares são aprendidos como linea-
res e o resultado é que regiões no espaço de características são associadas à uma classe
específica. Assim, uma nova amostra pode ser rotulada de acordo com a região à qual
pertence. À medida que mais camadas são acrescentadas à MLP, maior a interação
neuronal proporcionada, e melhores separações podem ser feitas no espaço de caracte-
rísticas. Desta forma, a MLP pode construir variados limites de decisões no espaço de
16
3. FUNDAMENTAÇÃO TEÓRICA
características, determinando diferentes categorias (Duda et al., 1995). Na construção
de uma MLP existem alguns aspectos que devem receber atenção especial como a es-
colha do tipo de função de transferência, o número de camadas escondidas e neurônios
em cada camada, que determinam a complexidade da RNA e devem ser especificados de
acordo com o problema a ser tratado.
3.1.3 Support Vector Machines(SVM)
No algoritmo de aprendizado SVM, a classificação se baseia na separação das classes
através de margens (Alpaydin, 2010). Assim, o objeto de busca do treinamento do SVM
consiste em encontrar um hiperplano separador ótimo, ou seja, aquele em que a distân-
cia de separação entre as margens de cada classe são máximas. As amostras que estão
situadas sobre as margens são as mais informativas para a criação do limite de decisão
da classificação e são chamadas de vetores suporte (Alpaydin, 2010; Duda et al., 1995;
Scholkopf and Smola, 2001). Uma característica interessante do SVM é a função de ker-
nel que tem a finalidade de projetar os vetores de características (amostras) de entrada
em um espaço de características maior no qual se consegue tratar problemas que se
encontram em espaços não linearmente separáveis (Scholkopf and Smola, 2001). À me-
dida que o espaço da dimensão do problema aumenta, aumenta também a probabilidade
desse problema se tornar linearmente separável. Além disso, a habilidade de separar
dados com distribuição não linear depende da escolha da função kernel, e que deve ser
analisada de acordo com o domínio do problema (Alpaydin, 2010; Duda et al., 1995;
Scholkopf and Smola, 2001). Os kernels mais usados são: Linear, Polynomial e RBF.
3.2 Método de Combinação de Classificadores
O principal objetivo em combinar múltiplos classificadores é produzir uma decisão fi-
nal que seja melhor que aquela produzida por um único classificador (Kittler et al.,
1998; Kuncheva, 2004; L.I. Kuncheva and Duin, 2001). Dependendo da metodologia de
representação de características empregada, as abordagens de combinação podem ser
divididas em duas categorias (Alpaydin, 1998):
• Representação única: os dados de treinamento possuem a mesma representação
para todos os classificadores.
17
3. FUNDAMENTAÇÃO TEÓRICA
• Múltiplas representações: os dados de treinamento possuem diferentes representa-
ções para diferentes classificadores.
Algumas abordagens, como boosting (Schapire, 1989) e bagging (Breiman, 1996), apli-
cam N conjuntos distintos de treinamento, retirados de dados de representação única,
a um único tipo de algoritmo de aprendizagem, para produzirem N diferentes modelos
mais adequados para combinação. Pode-se, ainda, produzir diferentes modelos de um
mesmo algoritmo de aprendizagem através da variação de algum parâmetro. Múltiplas
representações que caracterizam um mesmo conjunto de dados podem proporcionar di-
ferentes resultados de classificação quando utilizadas em um mesmo tipo de algoritmo
de aprendizagem. No entanto, o desempenho da combinação de múltiplos classificadores
depende de quanto os dados são correlacionados (Alpaydin, 1998; Kuncheva, 2004), isto
é, as abordagens de classificação devem produzir erros e acertos o mais independentes
possível.
De maneira geral, classificadores podem produzir saídas do tipo hard ou soft. Saídas
do tipo hard produzem um único valor para cada uma das amostras rotuladas, condi-
zente com o número identificador da classe. Nas saídas do tipo soft, tem-se o chamado
grau de confiança (Kuncheva, 2004) para cada classe, produzindo mais informação para
pós-processamento (Alpaydin, 1998; Kittler et al., 1998; Kuncheva, 2004) e que serão
empregadas no presente trabalho. As saídas do tipo soft podem ser valores fuzzy, pro-
babilidades a posteriori, graus de certeza ou confiança, entre outros (Kuncheva, 2004).
Assim, existem c valores associados à c classes, a partir dos quais, regras consensuais
podem ser aplicadas para uma combinação mais efetiva. Para tal, constrói-se primeira-
mente o chamado Decision Profile (DP) (Kuncheva, 2004) ilustrado na Figura 3.1.
Matematicamente, o DP para um dada amostra x pode ser definido como uma matriz
L × c : P (x) = [D1(x),D2(x), ..., DL(x)]T , em que L é o número de classificadores e c
o número de classes. Cada predição (saída soft) é representada por um vetor Di(x) =
[di,1(x), ..., di,c(x)], em que di,j(x) é o grau de confiança do classificador Di para a classe
j (Kuncheva, 2004).
Apesar de ser o mais simples (Kittler et al., 1998; Kuncheva, 2004), o método de
combinação MV é bastante utilizado na interpretação de imagens hiperespectrais de
sensoriamento remoto (Licciardi et al., 2009; Tarabalka et al., 2010a). Nesse método, a
classe majoritária dentre as L atribuições é conferida a amostra a ser rotulada. É um
método democrático, mas o MV trabalha com atribuições do tipo hard que não usa toda
a informação disponível como as saídas do tipo soft fazem. Métodos de combinação
18
3. FUNDAMENTAÇÃO TEÓRICA
Figura 3.1: Perfil de Decisão. Modificado de (Kuncheva, 2004).
que usam uma única coluna do DP(x) por vez, são conhecidos como Class-Conscious
combiners (Kuncheva, 2004) ou consensus theoretic methods (Benediktsson and Swain,
1992). Abaixo são apresentados algumas destas regras:
• Maximum (Max): µj(x) =maxi {di,j(x) }
• Minimum (Min): µj(x) =mini {di,j(x) }
• Average (Aveg): µj(x) = 1LΣ
L
i=1 {di,j(x) }
• Product (Prod): µj(x) = ΠLi=1 {di,j(x) }
em que, dado uma amostra x, µj(x) é o novo grau de confiança para a classe j. Essas
regras consensuais são chamadas não-treináveis pelo fato de não precisarem da estimação
de nenhum parâmetro, como por exemplo, o peso do classificador. Após construção
adequada de novos valores de confiança (regras consensuais + DP), para cada amostra
de entrada, uma atribuição do tipo hard pode ser efetuada a partir do maior valor de
confiança cujo índice representará a categoria ou classe atribuída a uma dada amostra.
3.3 Otimização Combinatória
Otimização é o processo de tentar encontrar a melhor solução possível para um problema.
Uma etapa importante deste processo consiste na construção de um modelo que pode
ser entendido como uma representação simplificada da realidade (Goldbarg and Luna,
19
3. FUNDAMENTAÇÃO TEÓRICA
2000). Constrói-se um modelo, reunindo símbolos representando objetos, de acordo com
certas regras, para formar uma estrutura que corresponde ao sistema do mundo real em
estudo (Dantzig, 1965), como representado na Figura 3.2.
Figura 3.2: Processo de modelagem. Modificado de (Goldbarg and Luna,
2000).
É necessário, então, traduzir adequadamente este modelo, o que é chamado de for-
mulação. Na fase de formulação do modelo são definidos os tipos de variáveis e o nível
de relação entre elas, as representações das restrições e das funções de desempenho de-
nominadas de funções objetivo (Goldbarg and Luna, 2000). Uma formulação geral de
um Problema de Otimização pode ser representada por:
Max ou Min : f(x), (função objetivo)
Sujeito a
gi(x) > 0, i = 1, 2, ...,m; (restrições de desigualdade)
hj(x) = 0, j = 1, 2, ..., p; (restrições de igualdade)
em que m e p determinam o número de desigualdade e igualdade, respectivamente.
Devem ser destacados alguns conceitos importantes:
• Variável de Decisão: as variáveis de decisão são aquelas para as quais existe liber-
dade de escolha dos valores que irão receber, ou seja, elas podem se alterar durante
o processo de otimização. Podem ser contínuas (reais), inteiras ou discretas. No
modelo acima, é representada por x.
• Restrições: são funções de igualdade ou desigualdade que definem o conjunto de
20
3. FUNDAMENTAÇÃO TEÓRICA
soluções válidas: gi(x) e hi(x).
• Espaço de Busca ou Região Viável: É o conjunto, espaço ou região na qual estão
as soluções possíveis ou viáveis do problema e é caracterizado pelas variáveis de
restrição.
• Função Objetivo ou de Avaliação: É a função que se quer otimizar (maximizar ou
minimizar). Pode ter uma ou mais variáveis.
• Ponto Ótimo: É o ponto, caracterizado pelo vetor x∗ = (x1, x2, ..., xn), formado
pelas variáveis de decisão que maximizam (ou minimizam) a Função Objetivo e
satisfazem as restrições.
• Valor Ótimo: É o valor da função objetivo f(x∗) no ponto ótimo.
• Solução Ótima: É o par formado pelo ponto ótimo e valor ótimo [x∗, f(x∗)].
Existem várias formas de resolver problemas de otimização, entre as quais, Algoritmos
Paralelos, Programação por Restrições, Teoria dos Grafos, Algoritmos Aproximados, e
as que serão utilizadas no presente trabalho, Programação Linear e uma meta-heurística
denominada AGM.
3.3.1 Programação Linear Inteira
Um Programa Linear Inteiro é um modelo de otimização em que a função objetivo é
linear nas variáveis e as restrições consistem em igualdades e desigualdades lineares. Um
sistema pode ser representado por um modelo de PLI se possuir as seguintes caracterís-
ticas (Dantzig, 1965; Goldbarg and Luna, 2000):
• Proporcionalidade: a quantidade de recursos consumidos ou fornecidos por uma
atividade deve ser sempre proporcional ao nível de atividade. A quantidade de
atividade é denominada de nível de atividade. Assim, se o nível de atividade
dobrar, o fluxo de recursos também deve dobrar.
• Não-Negatividade: não é possível haver quantidades de atividades negativas.
• Aditividade: o custo total é a soma das parcelas de cada atividade.
• Separabilidade: pode-se identificar a quantidade de fluxo de recursos para cada
atividade separadamente.
21
3. FUNDAMENTAÇÃO TEÓRICA
Uma vantagem do modelo de PLI é que existem algoritmos extremamente eficien-
tes para sua solução. Dentre eles, destaca-se o algoritmo Simplex (Luenberger, 2003;
Papadimitriou and Steiglitz, 1998), desenvolvido por (Dantzig, 1965), que será visto a
seguir.
Simplex
Esse algoritmo tem um conceito simples e, por isso mesmo, eficiente. A partir de uma
solução viável do sistema de equações (restrições do Programa Linear), o Simplex vai
identificando novas soluções viáveis de valor igual ou melhor que a corrente. Ele possui
dois critérios importantes: um que permite sempre encontrar novos e melhores vértices
da envoltória convexa do problema e outro que consegue determinar se o vértice escolhido
é ou não ótimo (Goldbarg and Luna, 2000).
Uma descrição detalhada do algoritmo pode ser encontrada em (Dantzig, 1965)
e (Goldbarg and Luna, 2000). A seguir são apresentadas algumas considerações im-
portantes e os passos gerais do funcionamento do Simplex, retirado de (Hillier and Lie-
berman, 2010):
• Variáveis Básicas (VB): m variáveis para as quais os sistema é resolvido.
• Variáveis Não Básicas (VNB): o restante das variáveis.
• Solução Básica (SB): solução cujos valores das VNB são nulos.
• Solução Básica Admissível (SBA): SB com todas as VB maiores ou iguais a zero.
• SBA não degenerada: SBA em que as VB são maiores que zero.
• SBA degenerada: SBA em que uma ou mais VB são nulas.
• Base admissível: uma base que corresponde a uma SBA.
• Conjunto Convexo: se o segmento de linha que junta qualquer par de pontos em
um conjunto, tal conjunto é dito convexo.
• em um conjunto convexo, um ponto x ∈ X é ponto extremo (PE), se e somente
se constituir uma SBA do problema de PLI.
• o conjunto dos vértices de um politopo X = {x : Ax = b, x ≥ 0, x ∈ Rn }
corresponde ao conjunto de soluções básicas admissíveis.
22
3. FUNDAMENTAÇÃO TEÓRICA
• o conjunto dos PE da região admissível (área colorida de verde na Figura 3.3)
corresponde ao conjunto das SBA e são ambos não vazios, desde que a região
admissível seja não vazia. Cada SBA é equivalente a um PE (pontos B, C, E,
F da Figura 3.3), mas podem existir várias SBA correspondendo ao mesmo PE,
neste caso o Programa Linear é degenerado.
Figura 3.3: Representação gráfica da região admissível (área colorida de verde)
e de pontos extremos (B, C, E, F) do Algoritmo Simplex. Modificado de (Gold-
barg and Luna, 2000).
Propriedades dos pontos extremos admissíveis :
1 Se existe apenas uma solução ótima, então tem de ser um PE admissível.
2 Se existem várias soluções ótimas, então pelo menos duas são PE admissíveis ad-
jacentes.
3 Existe um número finito de PE admissíveis.
4 Se um PE admissível não tem PE admissíveis adjacentes melhores, entãoesse PE
é ótimo.
23
3. FUNDAMENTAÇÃO TEÓRICA
Levando-se em conta somente os PE admissíveis, as propriedades 1 e 2, mostram que
a busca por uma solução ótima pode ser reduzida e existe um número finito de soluções
a considerar conforme propriedade 3. Pela propriedade 4 pode-se testar se um PE é
ótimo ou não.
O método Simplex utiliza essas quatro propriedades dos pontos extremos admissíveis,
apenas examinando poucos PE admissíveis e parando se um deles é ótimo. De maneira
iterativa, o algoritmo move-se do PE admissível atual para um melhor PE admissível,
até que a solução atual não tenha nenhum PE admissível adjacente melhor. O método
Simplex segue seguintes passos:
• Passo 1: Começar com um PE admissível. Qualquer PE admissível pode ser
adotada como solução inicial, no entanto, uma boa hipótese para a SBA inicial
será considerar as variáveis de folga como VB e as originais como VNB.
• Passo 2: Mover para um melhor PE admissível adjacente, quantas vezes forem
necessárias. Neste passo uma VNB é convertida em uma VB (denominada variável
básica de entrada), ao mesmo tempo que uma VB é convertida em uma VNB
(variável básica de saída) e, então, identificar a nova SBA.
• Passo 3: Testar se PE admissível atual é ótimo, conforme a propriedade 4.
3.3.2 Algoritmo Genético
Inicialmente propostos por (Goldberg, 1989), AG são baseados no processo da seleção
natural e nos mecanismos da genética. São algoritmos de busca: dado um conjunto
de elementos, deseja-se encontrar os que melhor atendam a certas condições.Os AG
transformam uma população de indivíduos, de acordo com uma função de aptidão, numa
nova geração de indivíduos usando os princípios da genética e sobrevivência dos mais
aptos, pela aplicação de operações tais como seleção, recombinação e mutação. Cada
indivíduo na população representa uma solução em potencial para um dado problema.
O AG procura a solução (indivíduo) que seja muito boa ou a melhor (soluções ótimas ou
sub-ótimas) para o problema analisado a partir da criação de populações de indivíduos
cada vez mais aptos, que otimizam (maximizam ou minimizam) a função objetivo de
interesse (Brownlee, 2011; Goldberg, 1989; Mitchell, 1998; Weise, 2008).
É importante entender algumas definições relacionadas com os AG, como:
24
3. FUNDAMENTAÇÃO TEÓRICA
• Cromossomo ou Genoma: Sequência linear de caracteres representando alguma
informação relativa às variáveis do problema. Cada cromossomo representa uma
solução do problema.
• Gen ou Gene: É a unidade básica do cromossomo. Cada cromossomo tem um
certo número de gens, cada um descrevendo uma certa variável do problema.
• População: Conjunto de cromossomos ou soluções.
• Geração: O número de iterações que algoritmo deve executar.
• Operações Genéticas: Operações que o Algoritmo Genético realiza sobre os cro-
mossomos.
• Espaço de Busca ou Região Viável: É o conjunto, espaço ou região que compreende
as soluções possíveis ou viáveis do problema a ser otimizado. Deve ser caracteri-
zado pelas funções de restrição, que definem as soluções viáveis do problema a ser
resolvido.
• Função Objetivo ou de Avaliação: É a função que se quer otimizar. Ela fornece
a qualidade de uma solução candidata, ou seja, a informação numérica do desem-
penho de cada cromossomo na população.
3.3.3 Otimização Multiobjetivo
Alguns problemas do mundo real apresentam um conjunto de objetivos a serem otimiza-
dos, muitas vezes, conflitantes entre si, ou seja, a melhoria de um tem como consequência
a degeneração do outro. Assim, não existe uma solução ótima única e sim um conjunto
de soluções. Diz-se que as soluções são ótimas quando não existem outras soluções no
espaço de busca melhores do que elas considerando simultaneamente todos os objetivos.
Um problema multiobjetivo tem a forma (Deb, 2011):
Max ou Min fm(x), m = 1, 2, ...,M,
restrita a gj(x) ≥ 0, j = 1, 2, ..., J,
hk(x) = 0, k = 1, 2, ..., K,
x
(L)
i 6 xi 6 x
(U)
i , i = 1, 2, ..., n,
25
3. FUNDAMENTAÇÃO TEÓRICA
em que x é o vetor de n variáveis de decisão x = (x1, x2, ..., xn)T , x(L)i e x
(U)
i , representam
o valor mínimo e máximo que xi pode assumir, gj e hk são denominadas funções de
restrição.
As funções de restrição e de limite caracterizam a região factível na qual deve es-
tar inserida a solução factível x. A solução será não factível se não pertencer à região
factível. Na otimização multiobjetivo as funções objetivos constituem um espaço multi-
dimensional denominado espaço de objetivos, Z ⊂ RM , além do espaço de variáveis de
decisão da otimização mono-objetivo. Existe um ponto z ∈ RM no espaço de objetivos,
f(x) = z = (z1, z2, ..., zM)T para cada solução x no espaço de variáveis de decisão.
Em otimização multiobjetivo, as soluções ótimas podem ser definidas a partir do
conceito matemático de ordenação parcial, chamado dominação. Diz-se que solução x1
domina a solução x2 (representado por x1 � x2), se ambas as condições a seguir são
verdadeiras:
• A solução x1 é não pior que x2 em todos os objetivos. Ainda, as soluções são
comparadas baseando-se nos valores de sua função objetivo (ou local dos pontos
correspondentes no espaço objetivo z1 e z2).
• A solução x1 é estritamente melhor que x2 em ao menos um objetivo.
Figura 3.4: Fronteira de Pareto. Modificado de (Deb, 2011).
Utilizando essa definição, pode-se estabelecer se um ponto domina outro ou não em
conjunto de dados como o representado na Figura 3.4. Se um ponto não é dominado por
nenhum outro ponto do conjunto, ele é chamado de não dominado. Os pontos 3, 5 e 6 da
Figura 3.4 são não dominados e formam o conjunto solução do problema. É importante
26
3. FUNDAMENTAÇÃO TEÓRICA
ressaltar que a melhora de um objetivo tem como consequência alguma perda em outro
objetivo, então, o que se busca é um equilíbrio entre os pontos não dominados, não
sendo possível definir uma solução ótima única. Este conjunto de soluções, quando vi-
sualizado, forma uma fronteira denominada fronteira de não dominação. Considerando
todos os pontos pertencentes ao espaço de busca, aqueles pontos que formam a fron-
teira de não dominação, são denominados soluções ótimas de Pareto. Tomando-se por
base um problema de minimização, formalmente, pode-se definir um conjunto ótimo de
Pareto (Ehrgott, 2005):
Definição Uma solução factível x̂ ∈ X é chamada eficiente ou ótima de Pareto, se não há
outro x ∈ X tal que f(x) ≤ f(x̂). Se x̂ é eficiente, f(x̂) é chamado ponto não
dominado. Se x1, x2 ∈ X e f(x2) 6 f(x1) diz-se que x1 domina , x2 e f(x1)
domina f(x2). O conjunto de todas as soluções eficientes x̂ ∈ X é denotada por
XE e é chamado conjunto eficiente. O conjunto de todos pontos não dominados
ŷ = f(x̂) ∈ Y , em que x̂ ∈ XE, é denotado por YN chamado de conjunto não
dominado.
As propriedades da relação de dominância são (Ehrgott, 2005):
1 Não é reflexiva. Uma solução não pode ser dominada por si mesma;
2 Não é simétrica, ou seja, x � y não implica que y � x;
3 Transitiva, dado que se x � y e y � z então x � z.
Como exemplo do emprego das definições apresentadas, pode ser citado um pro-
blema de otimização multiobjetivo proposto por (Schaffer, 1985), denominado fun-
ção f2. Consta de duas funções g e h que devem ser simultaneamente minimizadas:
f2 = (g(x), h(x)) sendo g(x) = x2 e h(x) = (x− 2)2.
A representação gráfica das funções objetivo g e h pode ser vista na Figura 3.5,
na qual pode-se identificar, no intervalo [0, 2], o espaço das soluções ótimas de Pareto.
Dentro do intervalo [0, 2] verifica-se que as funções objetivo g e h são conflitantes entre
si, ou seja, enquanto uma cresce a outra diminui de valor. A Figura 3.6, mostra as
soluções ótimas de Pareto, em um gráfico construído no espaço das funções objetivo.
27
3. FUNDAMENTAÇÃO TEÓRICA
Figura 3.5: Representação gráfica de um problema multiobjetivo função
f2 (Schaffer, 1985).
Figura 3.6: Fronteira de Pareto para a função f2 (Schaffer, 1985).
28
Caṕıtulo 4
Metodologia
Com a finalidade de se obter combinações de classificadores mais eficientes (menores)
mantendo-se a eficácia (acurácia)