ads:
ESTRATÉGIAS PARA DESENVOLVIMENTO DE SISTEMAS DE MÚLTIPLOS
CLASSIFICADORES EM APRENDIZADO SUPERVISIONADO
Leonardo Ponte Daister
DISSERTAÇÃO SUBMETIDA AO CORPO DOCENTE DA COORDENAÇÃO DOS
PROGRAMAS DE PÓS-GRADUAÇÃO DE ENGENHARIA DA UNIVERSIDADE
FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS NECESSÁRIOS
PARA A OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIAS EM ENGENHARIA
CIVIL.
Aprovada por:
Prof. José Luis Drummond Alves, D.Sc.
Prof. Carlos Cristiano Hasenclever Borges, D.Sc.
Prof. Nelson Francisco Favilla Ebecken, D.Sc.
Prof. Raul Fonseca Neto, D.Sc.
RIO DE JANEIRO, RJ – BRASIL
DEZEMBRO DE 2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ii
DAISTER, LEONARDO PONTE
Estratégias para desenvolvimento de
sistemas de múltiplos classificadores em
aprendizado supervisionado [Rio de Janeiro]2007
VIII, 98p., 29,7 cm (COPPE/UFRJ,
M.Sc., Engenharia Civil, 2007)
Dissertação – Universidade Federal do Rio
de Janeiro, COPPE.
1. Aprendizado Supervisionado
2
. Sistemas de Múltiplos Classificadores
3
. Clusterização
4
. Máquina de Vetor Suporte
I. COPPE/UFRJ II. Título (série)
ads:
iii
"Não é a experiência, a mãe de todas as artes e ciências, que engana as
pessoas, mas, sim, a imaginação que lhes promete o que a experiência não lhes pode
dar. A experiência é inocente; os nossos desejos vãos e insanos é que são
criminosos. Distinguindo a mentira da verdade, a experiência nos ensina a perseverar
em direção do que é possível, e não esperar, pela ignorância, atingir o que é
inatingível, a fim de que não sejamos compelidos, vendo a nossa esperança por terra,
a entregar-nos ao desespero".
Leonardo Da Vinci
Aos meus pais,
Luiz Antonio Nogueira Daister e Sandra Maria da Ponte Daister
e a minha avó Ida da Ponte.
iv
Agradecimentos
Aos professores da UFRJ, José Luis Drummond Alves, Nelson Francisco
Favilla Ebecken, Alexandre Evsukoff, Carlos Luiz Nunes dos Santos, pelo auxilio
durante o curso de mestrado na COPPE.
Ao professor do LNCC, Carlos Cristiano Hasenclever Borges por todo o auxilio
e paciência durante todo o processo de desenvolvimento dessa dissertação.
A todos os amigos e colegas da COPPE em especial ao amigo Frank Jencik o
qual me apresentou a COPPE. Agradeço também, a todo o corpo técnico e
administrativo do PEC.
A todos que de alguma forma me ajudaram ou me motivaram no
desenvolvimento desta dissertação.
A Deus por ter me dado forças para superar todos os obstáculos.
v
Resumo da Dissertação apresentada à COPPE/UFRJ como parte dos requisitos
necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)
ESTRATÉGIAS PARA DESENVOLVIMENTO DE SISTEMAS DE MÚLTIPLOS
CLASSIFICADORES EM APRENDIZADO SUPERVISIONADO
Leonardo Ponte Daister
Dezembro/2007
Orientadores: José Luis Drummond Alves
Carlos Cristiano Hasenclever Borges
Programa: Engenharia Civil
Métodos baseados na combinação de classificadores tem sido alvo de
interesse crescente em problemas de aprendizado supervisionado. Geralmente,
objetivam gerar sistemas de classificação mais robustos em relação aos
classificadores individuais envolvidos. Apresenta-se aqui, estudos e desenvolvimentos
de modelos de sistemas de múltiplos classificadores visando um maior entendimento
de seu comportamento bem como apresentar estratégias eficientes e viáveis de serem
aplicadas em problemas de classificação. Especificamente, um modelo de sistema de
múltiplos classificadores hierárquico é introduzido, onde aproveita-se as características
específicas de cada classificador individual, dentre eles as máquinas de vetor suporte,
de forma a se ter melhor desempenho computacional do sistema. Exemplos numéricos
em bancos de dados reais e sintéticos são apresentados para atestar a eficiência das
estratégias desenvolvidas.
vi
Abstract of Dissertation presented to COPPE/UFRJ as a partial fulfillment of the
requirements for the degree of Master of Science (M.Sc.)
STRATEGIES FOR DEVELOPMENT OF ENSEMBLE CLASSIFIER SYSTEMS FOR
SUPERVISED LEARNING
Leonardo Ponte Daister
December/2007
Advisors: José Luis Drummond Alves
Carlos Cristiano Hasenclever Borges
Department: Civil Engineering
Methods based on ensemble classifier systems applied on supervised machine
learning problems are subject to an intensive research effort. One presents here,
studies and developments of ensemble classifier models in order to obtain better
understanding of its behavior and introduce practical and efficient strategies.
Specifically, one introduces a hierarchical ensemble classifier system that improves the
utilization of the individual classifiers involved, e.g., support vector machines, to
diminish the necessary computational effort. Numerical examples using simulated and
real data are performed in order to attest the efficiency of the developed strategies.
vii
Índice
INTRODUÇÃO..............................................................................................................1
CAPÍTULO2.................................................................................................................6
Problemadeclassificação.....................................................................................................6
2.1. Introduçãoedefinições.................................................................................................6
2.2. MáquinasdeVetoresSuporte‐SVM.............................................................................8
2.2.2. Margemflexível(SoftMargin)...............................................................................11
2.2.3. ClassificaçãoNão‐linear.........................................................................................12
2.2.4. PrincipaisvantagensedesvantagensdoSVM.......................................................13
2.3. K‐NearestNeighbors‐KNN..........................................................................................14
2.3.2. PrincipaisvantagensedesvantagensdoalgoritmoKNN.......................................16
2.4. KMEANS.......................................................................................................................17
2.4.1. PrincipaisvantagensedesvantagensdoKMEANS:...............................................20
CAPÍTULO3..............................................................................................................21
Sistemasbaseadosemmúltiplosclassificadores...................................................................21
3.1. Introdução...................................................................................................................21
3.2. Montagemdeclassificadoresbaseadosemdados......................................................26
3.3. Sistemasdeclassificaçãobaseadosemparâmetros....................................................28
3.4. Combinaçãodeclassificadores....................................................................................29
CAPÍTULO4..............................................................................................................33
Estratégiasnão‐hierárquicasehierárquicasparasistemasdemúltiplosclassificadores.........33
viii
4.1. Introdução...................................................................................................................33
4.2. Consideraçõesiniciais..................................................................................................34
4.3. Sistemasdemúltiplosclassificadoreshierárquicos.....................................................36
4.3.1. Combinaçãodeclassificadores..............................................................................37
4.3.2. Definiçãodosclassificadoresindividuais...............................................................41
4.4. Sistemasdemúltiplosclassificadoreshierárquicos.....................................................45
4.4.1. Umaestratégiadepré‐combinação.......................................................................46
4.4.2. Hierarquianaaplicaçãodosclassificadores...........................................................48
4.4.3. Complementaçãodosubconjuntodetreinamento...............................................49
4.4.4. Algoritmodosistemademúltiplosclassificadoreshierárquico............................51
CAPÍTULO5..............................................................................................................53
ResultadosExperimentais....................................................................................................53
5.1. Basesdedadosutilizadas:...........................................................................................53
5.2. Metodologiaexperimental:.........................................................................................54
5.2.1. SistemaNãoHierárquico:......................................................................................55
5.2.2. SistemaHierárquico:..............................................................................................64
5.3. BancosArtificiais..........................................................................................................70
5.3.1. AnálisedeDadosSujeitoaRuído..........................................................................84
CAPÍTULO6..............................................................................................................91
ConclusõesePerspectivas....................................................................................................91
REFERÊNCIAS:..........................................................................................................95
1
Capítulo 1
Introdução
Aprendizado de máquina é uma área da Inteligência Artificial onde procura-se
o desenvolvimento de sistemas que baseados em procedimentos automáticos, tem
como objetivo obter um ganho de desempenho na tarefa executada com a experiência
adquirida com a manipulação de dados relativos ao problema tratado [25].
De uma forma geral, pode-se dividir as estratégias de aprendizado de máquina
em aprendizado supervisionado e aprendizado não-supervisionado [14],[38]. No caso
de aprendizado supervisionado os dados, também denominados de exemplos ou
instâncias, são rotulados em classes diretamente vinculadas ao problema estudado.
Pode-se então, ter uma noção concreta do desenvolvimento do classificador ou indutor
da hipótese de predição baseada no desempenho alcançado nos dados disponíveis
para treinamento, ou seja, no chamado conjunto de treinamento.
Tratando-se de aprendizado não-supervisionado, instâncias não rotuladas
geralmente são categorizadas de acordo com agregamentos, geralmente obtidos
2
baseando-se em propriedades geométricas dos dados. Estes agregamentos,
denominados clusters, representam uma distribuição dos dados onde espera que se
obtenham informações relevantes para discriminar e categorizar os grupos detectados
na amostra tratada. Atualmente, estratégias conhecidas como semi-supervisionadas
vem sendo utilizadas, visando aproveitar propriedades relativas aos dois modelos de
forma efetiva [2],[21].
Enfoca-se aqui, o trato de problemas em aprendizado supervisionado,
buscando analisar e desenvolver sistemas de classificação onde leva-se em conta a
contribuição de diversos classificadores individuais ou base, de uma forma adequada,
para que se obtenha uma melhor qualidade de predição com um nível maior de
robustez. Tais sistemas são designados por sistemas de múltiplos classificadores [27].
Questões relacionadas à manipulação dos dados no treinamento dos classificadores
individuais, escolha de classificadores que devam ser incluídos no sistema e, como
considerar a contribuição de cada classificador treinado, são cruciais para que se
tenha sistemas de múltiplos classificadores eficientes.
A motivação principal para construção de sistemas de classificação está
diretamente relacionada ao fato que classificadores, em geral, apresentam pontos
fortes e limitações no processo de generalização, devido a características intrínsecas
da sua construção bem como ao tipo de dados que serão classificados. Torna-se
então, tarefa árdua e complexa uma pré-definição do classificador que garanta
resultados de predição eficientes para o problema tratado. Objetiva-se com sistemas
de múltiplos classificadores contornar de uma forma robusta possíveis escolhas não
eficientes de classificadores individuais evitando o comprometimento da hipótese
gerada para a predição.
3
Pode-se citar, inicialmente, que entre os classificadores individuais incluídos no
desenvolvimento dos sistemas de classificação foi selecionada a
técnica de
aprendizado de máquina denominada classificador
SVM (Support Vector Machines)
ou Máquinas de Vetores Suporte [9], em virtude de ser considerado bastante robusto e
eficiente quando utilizada com a parametrização ótima, apresentando bons resultados
em aplicações consideradas complexas [22]. Além disto, possui um desenvolvimento
teórico matemático bem embasado. Outras ferramentas de aprendizado
supervisionado e não-supervisionado serão também utilizadas sendo prontamente
justificado o motivo de suas inclusões como componentes dos sistemas de múltiplos
classificadores apresentados. Especificamente, tais justificativas são relacionadas a
características complementares ao classificador SVM apresentadas pelos demais
classificadores individuais.
Em termos teóricos, o funcionamento de sistemas de múltiplos classificadores
está diretamente relacionado ao número de classificadores individuais envolvidos em
sua construção [3],[33]. A consideração de um número expressivo de classificadores
individuais aumenta a garantia de um melhor funcionamento de um sistema e
classificação e, ao mesmo tempo, diminui a relevância no processo utilizado para
efetivamente combinar os resultados dos classificadores individuais envolvidos.
Primeiramente, busca-se aqui, a análise de modelos de sistemas de
classificação envolvendo um número mínimo ou, pelo menos, poucos classificadores
individuais. Aspectos relativos à melhor escolha dos classificadores individuais e
vantagem na geração de tais sistemas de classificação restritos são analisadas, bem
como as a conseqüências desta limitação. Enfoca-se, principalmente, as principais
formas de combinação entre os classificadores individuais, fator relevante para o bom
4
funcionamento de sistemas restritos, buscando-se soluções adequadas para os
sistemas de classificação propostos.
Em uma segunda etapa, esforços são concentrados na estratégia de
treinamento dos classificadores individuais entre os sistemas de classificação
apresentados. Modelos tradicionais não-hierárquicos são comumente usados e, se
caracterizam por não apresentarem nenhuma influência na seqüência de treinamento
adotada para os classificadores individuais. Ou seja, resultados de modelos não-
hierárquicos são independentes da ordem de aplicação dos classificadores individuais.
Destaca-se então, um modelo hierárquico onde busca-se uma maior eficiência em
relação ao esforço computacional despendido para a geração do sistema, evitando
perda na capacidade de predição obtida. Para isto, componentes de técnicas de
aprendizado não-supervisionado são considerados no modelo de sistema de
classificação hierárquico.
Com o desenvolvimento de sistemas de múltiplos classificadores, pretende-se
obter uma classificação mais robusta e confiável, principalmente em problemas de
classificação considerados complexos, tornar a classificação menos dependente da
escolha de parâmetros e, particularmente no caso do uso do classificador SVM, obter
uma estratégia que complemente as suas características. Adiciona-se a estes
objetivos, a busca de uma maior eficiência computacional viabilizada pela construção
de sistemas de múltiplos classificadores hierárquicos.
A seguir, apresenta-se uma pequena descrição dos tópicos a serem expostos
no trabalho. No capítulo 2, uma apresentação formal do problema de classificação e
os modelos de aprendizado supervisionado e não-supervisionado utilizados são
descritos.
5
A seguir, apresenta-se no capítulo 3, as principais técnicas de sistemas de
múltiplos classificadores bem como suas características. No capítulo 4, são
desenvolvidos os modelos de sistemas de múltiplos classificadores utilizados.
Experimentos numéricos em dados reais e sintéticos são realizados, visando
atestar a eficiência dos sistemas de classificação apresentados, no capítulo 5.
Finalmente, no capítulo 6, são delineadas as principais conclusões obtidas, assim
como algumas perspectivas para futuros desenvolvimentos.
6
Capítulo 2
Problema de classificação
2.1. Introdução e definições
Em aprendizado supervisionado, tem-se associado um problema de
classificação, onde amostras denominadas de treinamento, formadas pelo conjunto de
dados de entrada conhecidos associados às suas correspondentes respostas pré-
classificadas (rótulos ou dados de saída). Após a etapa denominada de treinamento,
onde obtém-se a hipótese de predição gerada pelo classificador, o objetivo é
classificar novas amostras, ainda não rotuladas de forma correta. Define-se, então, o
vetor , que representa o vetor de atributos e que determina a classe ou
rótulo discreto associado a .
Chama-se instâncias ou exemplos ao par , onde é assumido uma
distribuição de probabilidade para o espaço das instâncias rotuladas. Uma
amostragem é o conjunto de instâncias rotuladas independentes e distribuídas
identicamente:
7
,
,
,
,...,
,
Portanto, a hipótese gerada pelo classificador é um mapeamento entre o
chamado espaço dos atributos e o espaço discreto das classes ou rótulos do
problema:
Na prática, geralmente, obtém-se uma indução baseada no mapeamento
determinado por um classificador aplicado a um conjunto de treinamento
. De forma
mais específica, será considerado o seguinte conjunto de dados de treinamento:
,
|
1 ,
,
1,1
(2.1)
onde
é o vetor composto de atributos da ésima amostra entre as existentes
e
é a classe correspondente entre duas possíveis. Ou seja, limita-se a definição ao
caso de atributos reais e classificação binária.
Cada classificador tem características especificas:
• tipo de dados;
• parametrização;
• desempenho computacional.
A seguir, apresentam-se algumas estratégias para aprendizado supervisionado
e não-supervisionado que serão utilizadas nos sistemas de múltiplos classificadores. A
motivação para a escolha das estratégias descritas está diretamente relacionada às
vantagens e desvantagens que também são apresentadas.
8
2.2. Máquinas de Vetores Suporte - SVM
A técnica SVM, foi introduzida por Vapnik (1992), formulada com todas as
demonstrações matemáticas em seu livro de 1995 [36] e, em 1998, descrita em outro
livro de sua autoria, com maiores detalhes [37].
SVM é uma técnica de aprendizado de máquina, fundamentada nos princípios
indutivos da minimização do risco estrutural. Estes princípios são provenientes da
teoria do aprendizado estatístico, a qual está baseada no fato de que o erro da técnica
de aprendizagem junto aos dados de validação (erro de generalização) é limitado pelo
erro de treinamento mais um termo que depende da dimensão VC (dimensão Vapnik e
Chervonenkis) [35]. A dimensão VC é uma medida da capacidade ou força de
expressão de uma família de funções classificadoras obtidas por meio de um algoritmo
de aprendizagem.
De forma geral, o classificador SVM implementa um mapeamento não-linear
(executado por um produto interno kernel escolhido a priori) dos dados de entrada
para um espaço característico de alta-dimensão, em que um hiperplano ótimo é
construído para separar os dados linearmente em duas classes. Quando os dados de
treinamento são separáveis, o hiperplano ótimo no espaço característico é aquele que
apresenta a máxima margem de separação. Para dados de treinamento em que as
amostras das duas classes apresentam superposição (dados não separáveis), uma
generalização deste conceito é utilizada. Outras boas referências sobre o assunto
podem ser encontradas em Burges [9], Cristianini & Shawe-Taylor [12], Gunn [13]
Haykin [17], e Semolini [34].
9
O treinamento do SVM consiste em um problema de otimização quadrático que
é atrativo pela garantia da convergência para um mínimo global da superfície de erro
(exceto quando algum problema de precisão numérica está presente), onde o erro
refere-se à diferença entre a resposta desejada e a saída da SVM.
No caso de classificações binárias, é comum que sejam realizadas através da
obtenção de uma função discriminante
com a seguinte estratégia: as
amostras são designadas para a classe positiva, se 0, e caso contrário, para a
classe negativa. No caso particular em que as classes são linearmente separáveis, a
superfície de decisão será representada por um hiperplano na forma :
0 (2.2)
onde,
, é o vetor normal ao hiperplano, e ¸ é o intercepto.
Assim pode-se aplicar a seguinte estratégia de decisão:
0 1 (2.3)
0 1 (2.4)
Para descrever o lugar geométrico dos hiperplanos separadores, será utilizada
a seguinte forma canônica (onde o vetor
e o escalar b são re-escalados de tal
maneira a atender as desigualdades):
1 1 (2.5)
1 1 (2.6)
A seguir, é apresentada a notação compacta para as desigualdades:
1 (2.7)
Para um dado vetor normal
e intercepto b, a separação entre o hiperplano
0 e o dado de entrada mais perto é chamada de margem de
separação denotada por . Sempre que for possível obter um > 0, existirão infinitos
10
hiperplanos, dentre os quais busca-se um hiperplano particular em que a margem de
separação é maximizada. De acordo com esta condição, a superfície de decisão é
dita ser o hiperplano ótimo e a técnica de aprendizado de máquina utilizado para a
determinação deste hiperplano é denominada SVM, sendo que os dados de
treinamento que se encontram à distância do hiperplano são chamados vetores-
suporte. Apresenta-se a seguir a formulação primal para o problema convexo.
Forma Primal
O problema é definido pela minimização de na forma:
min
1
2
1,1
(2.8)
A estratégia do tratamento lagrangeano [9] permite que o problema de
otimização convexo seja formulado na forma dual, que tornou-se padrão na teoria do
classificador SVM, pois com a representação dual, é possível trabalhar em um espaço
de alta dimensão, devido ao número de parâmetros ajustados não depender do
número de atributos que estão sendo utilizados. Freqüentemente tende a ser mais fácil
de ser resolvida do que na forma primal, à qual apresenta restrições de desigualdade
difíceis de serem resolvidas mostradas na equação (2.8). A seguir, demonstra-se a
conversão da forma primal para a forma dual.
11
Forma dual
Colocando-se a regra de classificação em sua forma dual tem-se que a
classificação é função dos vetores suporte. O dual do SVM pode ser mostrado assim:
sujeitoa0
e
0
(2.9)
onde o uma condição constitui uma representação dual para o vetor de peso em
termos do conjunto de treinamento:
(2.10)
2.2.2. Margem flexível (Soft Margin)
Em 1995, Corinna Cortes e Vladimir Vapnik [11] apresentaram uma idéia de
margem máxima modificada que permite um ajuste para instâncias mal classificadas.
O método de margem flexível escolherá um hiperplano que divide os exemplos tão
completamente quanto possível, enquanto maximiza a margem
1
1 (2.18)
.
12
A função objetiva é aumentada então por uma função que penaliza não-zero
, e a otimização se torna um comércio fora entre uma margem grande, e uma
penalidade de erro pequena. Se a função de penalidade é linear, a equação acima
agora se transforma em:
talque
1
1
(2.19)
Esta restrição junto com o objetivo de minimizar a norma de
pode ser
resolvido usando multiplicadores de Lagrange. A vantagem fundamental de uma
função de penalidade linear é que as variáveis frouxas desaparecem do problema
dual, com o C constante que só se aparece como uma restrição adicional nos
multiplicadores de Lagrange. Funções de penalidade não-lineares foram usadas,
particularmente reduzir o efeito de outliers no classificador, mas a menos que sejam
tomados os devidos cuidados, o problema fica não convexo, e assim é
consideravelmente mais difícil de achar uma solução global.
2.2.3. Classificação Não-linear
O algoritmo ótimo de hiperplano original proposto por Vladimir Vapnik em 1963
era um classificador linear. Porém, em 1992, Bernhard Boser, Isabelle Guyon e Vapnik
[8] propuseram uma estratégia para criar classificadores não-lineares aplicando a
técnica denominada de kernel para hiperplanos de máxima margem.
O algoritmo resultante é formalmente semelhante, a não ser que todo produto
escalar é substituído por uma função kernel não-linear. Isto permite ao algoritmo
13
ajustar o hiperplano de máxima margem no espaço de característica transformado. A
transformação é não-linear em um espaço de maior dimensão.
Se o kernel usado for uma função gaussiana de base radial, o espaço de
característica correspondente é um espaço de Hilbert, de dimensão infinita.
Alguns kernels comuns incluem:
• Polinomial (homogêneo):
,
(2.20)
onde a parâmetro d (grau do polinômio) é especificado a priori pelo usuário.
• Polinomial:
,
1
(2.21)
• Função de base radial (RBF) Gaussiana:
,
exp
(2.22)
• Perceptron:
,
tanh
,paraalguns
nãotodos
0e 0
(2.23)
2.2.4. Principais vantagens e desvantagens do SVM
Vantagens:
• Generaliza bem até mesmo se for treinado com um número pequeno de
exemplos;
• Pouco sensível a distribuição de probabilidade dos dados
14
• Minimiza o erro de classificação empírico;
• Maximiza a margem geométrica
Desvantagens:
• Necessidade de determinar valor de parâmetro C;
• Dificuldade na escolha do kernel mais adequado;
• Esforço computacional é bastante alto.
2.3. K-Nearest Neighbors - KNN
O KNN é um algoritmo de aprendizagem supervisionado que se utiliza de uma
técnica de instâncias baseadas no aprendizado, também amplamente conhecida e
emprega no conceito de NN Nearest Neighbors [14],[38]. Neste trabalho, será usado
para a atividade de classificação.
O cálculo das distâncias é o ponto central do KNN. O propósito deste
algoritmo é classificar um objeto novo, baseado em atributos e treinamento de
amostras. Os classificadores não usam nenhum modelo para ajustar, ele é somente
baseado em memória. Dado um ponto de questão, acha-se nn números de objetos ou
(pontos treinando). A classificação é obtida através de votação majoritária.
O algoritmo do KNN é muito simples e de fácil implementação. Seu
desempenho é bastante considerável. E possui a vantagem de ser flexível a ponto de
possibilitar várias alterações e por isso é base e métrica para muitos estudos na área
de Classificação. A tarefa de classificação consiste em associar elementos a uma
15
classe, e identificar a qual classe pertence uma dada instância. O algoritmo trabalha
baseado na distância mínima entre os exemplos em questão e o conjunto de
treinamento, para determinar os vizinhos mais próximos. Depois de agrupados, os
vizinhos mais próximos, leva-se a maioria simples para a formação da predição.
O KNN necessita de um conjunto de elementos especial, o chamado conjunto
de treinamento, onde é conhecida a classe e o vetor de atributos de cada elemento.
Para fins de avaliação utiliza-se também um conjunto de testes que é um conjunto
destacado do conjunto de treinamento. Na prática o conjunto de testes pretende
simular requisições do mundo real a fim de especular o percentual de acerto do
classificador, onde um acerto ocorre quando um elemento é classificado como a
classe a qual ele realmente pertence.
Funcionamento do KNN
O KNN classifica um dado elemento de acordo com os vizinhos mais próximos,
onde nn 1 . O algoritmo vai calcular a distância do elemento dado para cada
elemento da base de treinamento e então ordenar os elementos da base de
treinamento do mais próximo ao de maior distância. Dos elementos ordenados
seleciona-se apenas os nn primeiros, que servem de parâmetro para a regra de
classificação. Exemplo: se utiliza-se nn = 1, seleciona-se apenas o elemento do
treinamento mais próximo da instância que se pretende classificar. Já se utilizarmos
nn=5, serão utilizados os cinco elementos mais próximos da instância e a
determinação da classe é baseada nas classes dos cinco elementos determinados.
16
Pseudo-código: KNN
Início
Leia os conjuntos de treinamento S
tr
e conjunto de teste S
ts
;
Calcule a distância de x para cada elemento da base de treinamento
Ordene os elementos a partir da menor distância em relação a x
Selecione os nn mais próximos de x
Use uma regra de classificação
,
Fim
Fim
onde a função de uma regra de classificação é decidir qual a classe de um elemento
cujos nn vizinhos são aqueles passados como parâmetro. Para tanto ela faz uso das
classes de cada um dos nn elementos. Para tal foi utilizada a votação majoritária,
onde, classifica o elemento testado como a classe que está em maior número entre os
nn elementos (vizinhos mais próximos).
2.3.2. Principais vantagens e desvantagens do algoritmo KNN
Vantagens:
• Simples de ser implementado;
• Eficiente para conjuntos de treinamento grandes;
• Robusto em relação à presença de ruído nos dados ;
• Facilidade de ser aplicado em grupos de atributos.
17
Desvantagens:
• Necessidade de determinação do parâmetro K;
• Dificuldade na definição da métrica a ser usada;
• Necessidade de computar distância de cada amostra em relação a
todas as amostras do conjunto de treinamento.
2.4. KMEANS
Simplesmente KMEANS clustering (agrupamento) é um algoritmo para
classificar ou se agrupar objetos baseado em atributos, características em um nc
número de grupos [14], [38]. A idéia do algoritmo é fornecer uma classificação de
informações de acordo com os próprios dados, baseada em análises e comparações
entre os seus valores numéricos. Assim, o algoritmo fornecerá uma classificação
automática sem a necessidade de supervisão humana, ou seja, sem pré-classificação
existente. Por causa desta característica, o KMEANS é considerado como um
algoritmo de mineração de dados (data mining) não supervisionado.
O passo básico de agrupar do KMEANS é simples. No princípio é determinado
o número de agrupamentos nc e assumi-se o centróide ou centro destes
agrupamentos. Pode-se considerar qualquer objeto como o centróide inicial ou o
primeiro nc em seqüência também pode servir como o centróide inicial. A seguir pode-
se observar o algoritmo do KMEANS.
18
Pseudo-código: KMEANS
Início
Leia os conjuntos de treinamento S
tr
e conjunto de teste S
ts
Defina o número de centróides (nc)
Determine randomicamente a posição dos nc centróides
Repita
Determine a distância de cada objeto aos centróides
Agrupe o objeto baseado em distância mínima.
Atualize a posição de cada centróide
Fim
Fim
Abaixo pode-se observar o fluxograma de funcionamento do KMEANS
Figura. 2.2 fluxograma KMEANS
INICIO
NÚMERO DE
CLUSTE
RS
CENTRÓIDE
DISTÂNCIA DOS OBJETOS PARA
O CENTRÓIDE
AGRUPAMENTO BASEADO NA
DI
S
TAN
C
IA M
Í
NIMA
NENHUM OBJETO SE
MOVE PARA AGRUPAR?
FIM
19
Assim, conforme observa-se na figura 2.2, definido o número de clusters para
os dados considerados, passa-se a determinação dos centróides de tais clusters e a
seguir define-se a qual cluster cada uma das instâncias deve pertencer de acordo com
a distância mínima da instância em relação aos centróides considerados. Procede-se
a atualização dos centróides, repetindo este processo até que nenhum dado seja
movido de cluster.
Nota-se que desta maneira se obtém uma classificação que coloca cada ponto
em apenas uma classe, portanto pode se dizer que este algoritmo faz uma
classificação rígida (hard clustering). Outros algoritmos trabalham com o conceito de
classificação soft onde existe uma métrica que diz o quanto cada ponto pertence a tal
classe.
Existem muitas aplicações do agrupador KMEANS, variações não-
supervisionadas que aprendem, em uma rede neural, reconhecimentos de padrão,
análise de classificação artificial inteligente, processando de imagens, visão de
máquina, etc. A princípio, se existem vários objetos e cada objeto tem vários atributos
e é possível classificar tais objetos baseado nestes atributos, então pode-se aplicar
este algoritmo. Cada objeto é representado por um ponto de atributo que é um
exemplo ao algoritmo e é nomeado automaticamente a um do agrupamento. Isto é
chamado de “não-supervisionado que aprende” porque o algoritmo automaticamente
só classifica o objeto baseado nos critérios foram dados (distância mínima para o
centróide). Não é necessário supervisionar o programa dizendo que a classificação
estava correta ou errada. O processo de aprendizagem depende dos exemplos de
treinamento que alimentam ao algoritmo.
20
2.4.1. Principais vantagens e desvantagens do KMEANS:
Vantagens:
• Eficaz em grandes grupos de dados;
• Geralmente converge em poucas iterações.
Desvantagens:
• O número de clusters, nc, deve ser determinado previamente;
• Sensível a condição inicial (principalmente em conjunto de dados pequenos);
• Agrupamento muito sensível a diferença de dimensão entre os atributos;
• Não é robusto a outliers;
• Forma de agrupamento depende da métrica utilizada.
No próximo capítulo, veremos as principais técnicas de sistemas de múltiplos
classificadores bem como suas características.
21
Capítulo 3
Sistemas baseados em múltiplos
classificadores
3.1. Introdução
Resultados obtidos através de técnicas de aprendizado supervisionado têm sua
qualidade dependente de diversos fatores que nem sempre podem ser completamente
conhecidos ou controlados. Número de instâncias em cada classe, características de
distribuição de cada atributo bem como o nível de complexidade do espaço dos
atributos tendem a dificultar a escolha de um classificador que venha a ter um
desempenho favorável nos dados disponíveis. Paralelamente, pode-se acrescentar
que, além de se definir um classificador que tenha um desempenho eficiente em
relação ao grupo de dados analisados, é também tarefa árdua e complexa definir
parâmetros adequados que sejam efetivos para tal classificador.
Uma idéia que vem crescendo na comunidade de inteligência computacional é
justamente a utilização da combinação de diversos modelos de aprendizado de
22
máquina, agregados de forma a gerar um sistema de classificação onde se tenha o
resultado de predição deste sistema, superior a predição obtida por cada método de
classificação utilizado individualmente. Intuitivamente, pode-se pensar em tais
sistemas como sendo uma consulta a diversos especialistas separadamente e, de
alguma forma, compilar suas opiniões visando chegar a uma decisão final mais
acurada que reflita o pensamento da maioria dos envolvidos.
Estes sistemas de classificação aparecem na literatura com nomenclaturas
diferentes podendo-se destacar: sistemas de múltiplos classificadores, sistemas
baseados em montagem de classificadores, sistemas de classificadores combinados,
fusão de classificadores, entre outros [27]. Independente do nome utilizado, busca-se
sempre definir uma forma eficiente de se obter resultados mais robustos em relação a
um classificador isolado. Esta robustez pode ser entendida também, como uma forma
de se garantir uma maior confiabilidade na previsão de dados diferenciados/complexos
que necessitem passar por um processo de classificação.
Sistemas de múltiplos classificadores têm se mostrados benéficos em diversas
aplicações indicando que, combinados adequadamente, resultados de classificadores
individuais, podem gerar sistemas que claramente tem desempenho superior, pelo
menos, ao obtido pelo classificador menos apto. Logicamente, busca-se montar um
sistema de múltiplos classificadores, objetivando um ganho real na eficiência dos
classificadores envolvidos de uma forma geral.
Diversas são as formas de se obter um sistema de múltiplos classificadores.
Visando tornar mais claro os modelos mais usuais, utiliza-se a seguinte taxonomia:
• modelos baseados em dados;
23
• modelos baseados nos parâmetros de indução;
Nos modelos baseados em dados, variam-se os dados de treinamento,
geralmente através de alguma estratégia estatística, para gerar cada classificador
individual ou base que irá compor o sistema de múltiplos classificadores. Nesta classe
de modelos, é comum utiliza-se o mesmo classificador/indutor, inclusive com os
mesmos parâmetros, nos diversos conjuntos de treinamento para gerar as hipóteses
individuais de classificação. O que se tem, é um ajuste do classificador obtido em
relação ao grupo de dados utilizados para treiná-lo. Os diversos conjuntos de
treinamentos gerados ficam limitados, logicamente, aos elementos existentes no
conjunto de treinamento disponível inicialmente.
Nos modelos baseados nos parâmetros do indutor ou classificador considera-
se a variação de parâmetros internos e externos de classificadores para a obtenção
dos classificadores base. Como parâmetros internos, entendem-se parâmetros
necessários de serem definidos para a utilização de um classificador pré-determinado
como, por exemplo, o número de vizinhos no KNN ou o kernel utilizado no SVM. Os
parâmetros externos estão relacionados ao indutor utilizado onde, mudando-se este
parâmetro muda-se o modelo de classificador a ser aplicado.
No primeiro caso, os sistemas baseados nos parâmetros do indutor buscam
combinar resultados obtidos por classificadores treinados com parâmetros internos
diferentes, para gerar o sistema final de classificação. Assim, mantém-se fixo o
conjunto de treinamento, buscando o diferencial de desempenho entre os
classificadores individuais baseado na mudança de seus parâmetros intrínsecos. Com
a dificuldade de se obter parâmetros ótimos dos classificadores, este modelo de
sistema de classificação busca, através da utilização de diversos grupos de
24
parâmetros pré-definidos, um espectro mais amplo do desempenho do classificador,
visando diminuir a influência de uma escolha não muito adequada dos parâmetros,
que irão gerar a indução deste classificador específico.
A outra forma de obtenção do sistema de classificação baseados em
parâmetros do indutor é determinar, para a geração da fusão de classificadores, não
somente um modelo de classificador mas a combinação de diversos tipos de
classificadores, obtidos, também, com os mesmos dados de treinamento. Uma idéia, é
utilizar de classificadores com características complementares, para se ter um
desempenho mais abrangente nas hipóteses geradas. Finalizando, é importante
ressaltar que não se encontra explicitamente esta taxonomia na literatura. Porém,
nota-se claramente que os modelos já desenvolvidos são facilmente enquadrados
nestas categorias. Recentemente, já se pode identificar casos considerados como
híbridos [24].
Logicamente, tais combinações não são garantia de se ter um sistema de
classificação mais eficiente. Os conceitos envolvidos são intuitivamente justificáveis,
mas sem a certeza de se ter um desempenho melhor do sistema gerado em relação
aos obtidos pelos classificadores individuais envolvidos. Em termos teóricos, tem-se
que a probabilidade de classificação incorreta de um sistema de múltiplos
classificadores é governada por [3],[16],[33]:
1
(3.1)
25
onde, este somatório se aproxima de 1 quando ∞,
, e se aproxima de 0 se
. Ou seja, quanto maior o número T de classificadores envolvidos maior a
probabilidade de se ter erros menores. Nota-se porém, que os classificadores devem
ter um nível mínimo na qualidade de predição.
Apesar da equação (3.1) ser um indicativo que sistemas de múltiplos
classificadores tendem a ter desempenho superior a classificadores individuais, deve-
se ressaltar que, um fator primordial para que se tenha um desempenho adequado do
sistema é a forma ao qual se combina os resultados obtidos individualmente. Tanto
nos sistemas baseados em dados quanto nos sistemas baseados em classificadores,
é crucial a escolha do mecanismo de combinação, podendo uma estratégia mal
elaborada, provocar resultados não competitivos em relação aos classificadores
individuais. Geralmente, nos modelos baseados em dados, tal estratégia é parte
constituinte do algoritmo do sistema de classificação, não indicando que se tenha
autonomia para sua modificação que pode, inclusive, comprometer fortemente a
qualidade dos resultados. No caso de modelos baseados em classificadores, tal
associação não é tão forte, existindo diversas possibilidades para a combinação dos
resultados individuais. Porém, isto não indica que a influência de tal escolha seja
menos importante do que dos sistemas baseados em dados, sendo também fator de
relevância para o nível na qualidade da predição obtida.
Apresenta-se a seguir, os principais modelos de sistemas de montagem de
classificadores baseados em dados, baseados em parâmetros dos classificadores,
bem como as formas mais usuais para combinação dos classificadores individuais.
26
3.2. Montagem de classificadores baseados em dados
Como visto anteriormente, são necessários dois itens para se gerar um sistema
de classificação:
• uma estratégia de diversidade para gerar classificadores individuais;
• uma forma de se combinar os classificadores individuais gerados.
Nos classificadores baseados em dados, a diversidade dos classificadores
individuais é obtida por meio da variação nos dados do conjunto de treinamento. É de
interesse que os classificadores de base gerados, tenham diferenças entre si que
sejam interessantes para a montagem do sistema final de classificação [28]. Para isto,
é crucial que a estratégia de geração dos dados de treinamento seja definida, de
forma a propiciar diversidade entre os classificadores individuais, que possa ser
utilizadas eficientemente quando submetida à estratégia de combinação. Os principais
modelos de montagem de classificadores baseados em dados são descritos a seguir.
Breiman [4],[5] desenvolveu o chamado sistema bagging para classificação.
Acrônimo de bootstrap aggregating o algoritmo é bastante simples, intuitivo e
apresenta resultados interessantes. A diversidade na geração dos dados se dá através
da geração randômica, com reposição, dos conjuntos de treinamentos que serão
utilizados no treinamento dos classificadores base. É necessário que se defina
previamente quantos conjuntos de treinamento serão gerados determinando assim, o
número de classificadores utilizados na combinação final.
Quanto à forma de combinação, o modelo utilizado no algoritmo bagging é o
considerado mais simples e intuitivo. Denominado votação pela maioria ou majoritária
(majority voting), define o resultado da combinação dos classificadores, pela classe
27
que foi designada pela maioria dos classificadores base para determinada instância.
Esta forma de combinação, como será visto, é utilizada em diversos outros sistemas
de classificação pela sua simplicidade de implementação e relativa eficiência.
Existem alguns variantes do algoritmo bagging como o chamado Random
Forest [6] desenvolvido especificamente para uso com árvores de decisão e o
algoritmo conhecido como Pasting Small Votes direcionado para uso em bancos de
dados muito grandes [7].
Buscando comprovar que um classificador de baixo desempenho, pode ter seu
desempenho aprimorado por meio de um sistema de classificação, Shapire [31]
apresenta um novo modelo de sistema de classificação baseado em dados.
Considera-se um classificador de baixo desempenho, aquele cujo resultado na
predição aproxima-se quase de uma escolha randômica entre as possíveis classes.
Esta idéia ousada, deu origem ao algoritmo conhecido por boosting. Baseia-se na
definição de pesos para as instâncias do conjunto de treinamento que, inicialmente,
possuem o mesmo valor que vão sendo atualizados de acordo com o grau de
dificuldade que apresentam para a predição dos classificadores desenvolvidos. A cada
iteração, com um conjunto de pesos fixados para os dados de treinamento, gera-se
um novo classificador que será utilizado na combinação e servirá, também, para a
atualização dos pesos das instâncias da próxima iteração.
Em 1997 Freund e Schapire apresentaram o algoritmo AdaBoost [15] que
causou grande impacto na área de aprendizado de máquina. É considerado uma
versão mais geral do algoritmo de boosting. Diversas versões do AdaBoost foram
desenvolvidas, podendo-se citar o AdaBosst.M1 para problemas multi-classes e
AdaBoost.R específico para problemas de regressão.
28
Em [1], compara-se o desempenho dos algoritmos de bagging e boosting ,
considerando algumas variantes. Modelos híbridos, onde combinam-se diferentes
estratégias baseadas em dados, podem ser construídos visando sempre um melhor
desempenho do sistema de classificação gerado. Em [24], utiliza-se a combinação de
dois modelos baseados em dados, a saber, bagging e boosting para gerar um sistema
de classificação final.
3.3. Sistemas de classificação baseados em parâmetros
Nesta classe de sistemas de classificação, busca-se a diversidade dos
classificadores bases através de mudanças nos parâmetros que irão gerar a hipótese
de classificação. Cada grupo de parâmetros escolhidos irá determinar um classificador
base. Por exemplo, caso se defina como classificador o SVM, pode-se gerar diversos
classificadores base modificando o valor do parâmetro C, bem como o tipo de kernel
aplicado. Em relação aos dados de treinamento, geralmente são utilizados os mesmos
para a obtenção dos classificadores base. Nota-se que, diferentemente dos modelos
baseados em dados, este tipo de sistema não tem regras ou algoritmos bem definidos.
Podem-se imaginar diversas possibilidades que poderiam definir um sistema de
classificação específico. A única regra que direciona tais montagens é dada pela
equação (3.1), que indica que, quanto maior o número de classificadores base
compondo o sistema de classificação, melhor será sua predição. Desta forma,
diversos modelos de sistemas de classificação desta categoria podem ser
considerados [10],[23],[26],[29].
29
Como nos modelos de sistemas de classificação baseados em dados, a
maioria dos modelos baseados nos parâmetros de indução utiliza, para a combinação
dos classificadores para a predição final, a votação majoritária [29], [30] e a votação
majoritária com peso. Notam-se algumas tentativas de definição dos pesos de forma
que torne a predição mais efetiva. Por considerar essencial, para o bom
funcionamento do sistema de classificação, a forma de combinação, comenta-se a
seguir sobre os modelos mais apreciados.
3.4. Combinação de classificadores
Como descrito anteriormente, um passo fundamental para que se tenha um
sistema de classificação, é a definição da forma como os classificadores individuais
serão combinados. Mostra-se aqui, mais formalmente, como funcionam os dois
modelos mais conhecidos, a saber: votação majoritária e votação majoritária com
peso, além de apresentar alguns outros modelos que também se destacam. De uma
forma geral, a combinação é aplicada utilizando os
,1,..., classificadores
individuais para definir a qual classe uma determinada instancia x deve ser
predita.
No caso da votação majoritária tal predição é feita da forma:
1
:
30
(3.2)
indicando que a classe que será predita para a instancia x é a mais freqüente
classe predita para x por todos os possíveis
classificadores individuais. Esta
combinação é aplicada em todo conjunto de teste, definindo a classe para cada um de
seus componentes ou outra instância que necessite ser classificada. No algoritmo de
bagging é utilizada esta votação majoritária simples para combinação dos
classificadores base.
Um outro modelo de combinação bastante utilizado é a votação majoritária com
peso, onde tem-se:
:
(3.3)
com
sendo pesos determinados para cada um dos
,i1,…,T
classificadores individuais. Não existe uma regra considerada unânime para a
definição dos valores
. Geralmente, tomam-se seus valores proporcionais ao nível
de acerto de cada classificador individual, seguido de um processo de normalização.
Baseia-se na idéia de aumentar a influência dos classificadores individuais, que
tenham mostrado maior eficiência para o conjunto de treinamento utilizado.
Novamente, a predição é definida pela classe que obtiver a maior soma dos
pesos dos classificadores individuais a ela associada para a instância avaliada.
Não se tem garantia que a votação majoritária com peso apresente resultados
melhores do que a votação majoritária simples. Intuitivamente, espera-se que, com
pesos proporcionais a capacidade de cada classificador base, tem-se a expectativa de
31
uma predição mais eficiente. Logicamente, tais pesos são obtidos baseados no
conjunto de treinamento utilizado e, nem sempre, o mesmo padrão de distribuição das
amostras é acompanhado pelo conjunto de teste, que deve ser predito.
Encontram-se outras formas consideradas eficientes para a definição dos
valores de
. Por exemplo, o algoritmo de boosting que tem para os pesos:
log
1
(3.4)
onde
é o erro no conjunto de treinamento que irá gerar o i-ésimo
classificador base. Esta mesma forma pode ser utilizada para casos onde se tem a
combinação baseada em parâmetros do classificador. Outras formas de se utilizar os
pesos
para a combinação de classificadores são consideradas. Como BKS
proposto por Huang e Suen [19], [20].
Diversos estudos comparativos mostram que geralmente é difícil apontar qual
estratégia para se gerar um sistema de classificação é mais adequada [1],[10],[23].
Nota-se que, apesar do algoritmo boosting mostrar sempre um bom
desempenho evitando overfitting [32], não se pode afirmar que determinada estratégia
seja mais eficiente dependendo muito do problema que está sendo tratado.
Apresentou-se neste capitulo, as diversas possibilidades e variantes para
construção de sistemas de múltiplos classificadores e as versões mais usuais em
aprendizado de máquina. Buscou-se ressaltar as propriedades e características mais
32
marcantes de cada modelo, visando uma melhor compreensão e entendimento do
funcionamento das técnicas de fusão de classificadores. Tal informação tem com
objetivo embasar e justificar as contribuições presentes neste trabalho que serão
apresentadas a seguir.
33
Capítulo 4
Estratégias não-hierárquicas e hierárquicas
para sistemas de múltiplos classificadores
4.1. Introdução
Técnicas disponíveis para criação de sistemas de classificadores múltiplos têm
como fundamento básico para indicar um funcionamento superior em relação à
utilização de classificadores individuais a equação (3.1) que determina a probabilidade
de predição do novo sistema em relação aos seus componentes individuais.
Logicamente este é um resultado teórico que nem sempre consegue-se verificar na
prática. Como visto no capítulo anterior, para que se tenha uma diminuição na
influência dos diversos componentes que viabilizam a construção do sistema de
classificadores, deve-se ter um número muito grande de classificadores (tendendo ao
infinito) na composição do sistema, bem como, exige-se que cada classificador base
tenha um nível mínimo de acerto nas predições em relação à base de dados utilizada.
Na prática, geralmente, pode-se garantir somente o nível de predição mínima para os
classificadores base usados na geração do sistema de classificação.
34
O uso de um número crescente de classificadores individuais pode trazer
dificuldades e transtornos principalmente em termos de custo computacional. Além
disto, não é tarefa trivial garantir diversidade necessária para geração de
classificadores individuais relevantes. Torna-se basicamente inócuo a composição do
sistema com classificadores base similares ou redundantes.
Portanto, tem-se como objetivo para os sistemas que serão construídos, a
flexibilização da necessidade definida na equação (3.1), que indica que deve-se ter um
número muito grande de classificadores base para a construção de um sistema
eficiente. Na prática, a maioria dos sistemas de classificação apresentados são
montados com poucos classificadores individuais, porém, sem que se tome nenhuma
providência específica visando analisar se o desempenho do sistema apresentado terá
ou não comprometimento.
Na seção seguinte, apresentam-se as considerações iniciais e justificativas que
irão pavimentar as estratégias utilizadas nos sistemas de classificação desenvolvidos.
A seguir, parte-se para um detalhamento e caracterização dos diversos algoritmos de
classificadores múltiplos utilizados.
4.2. Considerações iniciais
Como visto, sistemas de classificação adequados devem ser construídos com
alto número de classificadores individuais para que se tenha desempenho eficiente.
Logicamente, é necessário que tais classificadores individuais, tenham um nível de
diversidade tal que permita gerar combinações de resultados que viabilizem mudanças
no processo de classificação em direção ao resultado correto para a predição de uma
35
nova amostra apresentada. Notadamente, este aspecto é de difícil controle podendo
comprometer ate mesmo sistemas com um número considerável de classificadores
individuais.
Busca-se aqui, desenvolver sistemas de classificação baseados em duas
premissas:
• utilização de poucos classificadores base;
• uso eficiente da capacidade computacional.
No caso do primeiro item, torna-se primordial uma análise mais cuidadosa dos
efeitos da restrição de classificadores individuais no sistema de classificação e como
pode-se, independente desta restrição, obter resultados eficientes na predição de
dados.
Em relação ao segundo item, visa-se obter um sistema de classificação que
tenha uma eficiência computacional maior em relação ao que chamamos de sistemas
padrão de múltiplos classificadores. Tal sistema será viabilizado por meio de um
procedimento que será denominado sistema de classificação hierárquico. Desta forma,
os sistemas de múltiplos classificadores tradicionais ou padrões serão denominados
de não-hierárquicos. Entende-se por hierárquico uma forma pré-estabelecida de
aplicação dos dados ou de classificadores visando algum tipo de ganho, a saber,
computacional ou de qualidade de resposta.
Apresentam-se a seguir, os modelos desenvolvidos para classificação, de
acordo com os objetivos determinados acima. Primeiramente, serão descritos os
modelos chamados de não-hierárquicos, onde se busca contornar a limitação no
36
número de classificadores base e, a seguir, os modelos hierárquicos, que buscam
agregar uma maior eficiência ao sistema de classificação, sem comprometimento da
qualidade de predição.
4.3. Sistemas de múltiplos classificadores hierárquicos
A restrição no número de classificadores base na construção de sistemas de
múltiplos classificadores, deve ser analisada por ir contra as expectativas de
construção de tais sistemas, como visto anteriormente. Esta limitação pode interferir
diretamente na qualidade da ferramenta desenvolvida. Além da necessidade um nível
mínimo de predição para os classificadores individuais, prevista em teoria, identifica-se
dois elementos de fundamental importância para o desempenho de um sistema de
múltiplos classificadores:
• a estratégia de combinação dos classificadores;
• a diversidade de cada classificador base.
Ambos aspectos tem sua influência diluída, quando se opta pela construção de
sistemas de classificação que não infringem a exigência de se ter um número
expressivo de classificadores base. Porém, quando se trabalha na construção de um
sistema de classificação que envolva poucos classificadores, estes itens passam a ter
uma importância direta e crucial no desempenho do sistema gerado. A detecção
desta influência é fácil de ser comprovada na prática, onde, verifica-se a dificuldade
de correção da predição final quando se tem classificadores individuais com predição
invertida ou que, pelas condições de treinamento adotadas, não há adequação para o
treinamento do modelo de classificador utilizado na geração do sistema de
37
classificação. Mostra-se a seguir, como foi considerado cada um destes itens na
construção dos sistemas de múltiplos classificadores não-hierárquicos.
4.3.1. Combinação de classificadores
As técnicas de votação majoritária e votação majoritária com pesos, são as
referências principais e os métodos mais utilizados na combinação dos classificadores
base. Isto se dá, pelas suas comprovadas eficiências em obter resultados de
qualidade superior a classificadores individuais, conforme descrito anteriormente.
Com a restrição adotada no número de classificadores base, a aplicação de ambos os
modelos é prevista, buscando um processo que garanta um desempenho eficiente.
Define-se aqui, o conceito de eficiência em predição de sistemas de múltiplos
classificadores, como sendo a obtenção de qualidade superior no resultado de
predição do sistema de classificação, em relação aos classificadores base que
participam da sua construção. Tem-se que, tal medida pode ser utilizada para atestar
uma robustez do procedimento de criação do sistema de classificação em relação aos
componentes usados para construí-lo.
Primeiramente, a análise é voltada para a definição do número mínimo ou
necessário de classificadores individuais, para que se tenha um processo de votação.
Para isto, sem comprometimento da generalização, assume-se que as classes
serão restritas na seguinte forma:
1,1
(4.1)
onde, toma-se somente duas classes para o problema de classificação
supervisionada 11. Adota-se tais valores, ao invés de, por exemplo,
38
0,1 por ser comum sua utilização nos classificadores SVM, que irão compor o
sistema desenvolvido. Além disto, mapeamentos entre os valores que definem as
classes são triviais.
Visto isto, a votação majoritária para tal problema teria como número mínimo
de classificadores definidos em 3 classificadores base. A utilização de 2
classificadores levaria ao empate, caso a predição fosse diferente entre os
classificadores base, tornando inócua sua aplicação como fator de decisão na
predição. Considerando os classificadores bases como
,
tem-se então:
unanimidade: a classe é adotada;
não-unanimidade: sendo adotada a
classe
para a instância ;
Fica então, a votação majoritária:
1
(4.2)
com . sendo a função que retorna o sinal da expressão considerada.
Pode-se considerar, inclusive, que para criação de sistemas de classificação
efetivos, usando votação majoritária com número restrito de classificadores, é
adequado a utilização de número impar de classificadores individuais, evitando assim
situações não conclusivas de empate. Estes sistemas serão denominados de votação
majoritária assimétrica, por permitirem o desequilíbrio no número de classes preditas
para uma determinada amostra. O efeito de empate tende a diminuir quando se
39
considera um número expressivo de classificadores individuais, chegando ao ponto
de não ser necessário providências adicionais à sua aplicação.
No caso da votação majoritária com peso, com a utilização de 3 classificadores
base é natural que se tenha:
1
(4.3)
com
sendo os pesos, assumidos como proporcionais ao nível de acerto de cada
classificador como é tradicional. Deve-se ressaltar, que a votação majoritária só tem
efeito de atuação em casos de não unanimidade. Analisando então, a equação (4.3)
em um caso de não unanimidade, onde 2 classificadores base determinam uma classe
(
,
) e o restante (
) a outra classe, a inversão da classe majoritária só se daria
caso:
(4.4)
Esta desigualdade é muito difícil de ocorrer na prática, pois implica que um
classificador tenha o dobro de eficiência em relação aos outros. Assim, tem-se que o
resultado da votação majoritária e da votação majoritária com peso, geralmente seria
o mesmo, na maioria dos casos. A questão levantada é quando, ou até mesmo se,
vale a pena inverter a classificação para a classe minoritária. Dificilmente consegue-
se uma resposta efetiva para esta questão. Pode-se então, de uma forma empírica,
adotar um limite mais flexível para a mudança, através da introdução da variável
0,1 que define o seguinte processo de votação:
40
1
(4.5)
onde multiplica a composição relacionada aos classificadores menos efetivos.
Valores de baixos, indicam um favorecimento da classe minoritária e, valores
tendendo ao valor máximo buscam conservar a classe majoritária. Esta, então, será a
votação majoritária com peso adotada.
A dificuldade na definição adequada do valor de e, a necessidade de um
sistema de combinação que tenha um comportamento diferenciado e, se possível,
mais eficiente baseado em pesos, leva a construção de um sistema de combinação
simétrico, ou seja, com um número par de classificadores base. A introdução dos
pesos na votação, torna muito difícil que haja empate, mesmo utilizando número par
de classificadores. A vantagem de um procedimento de combinação simétrico está no
melhor aproveitamento da informação carregada nos pesos
, gerando uma predição
mais diretamente relacionada à capacidade individual de cada classificador envolvido.
Apesar de poder ser efetivada com 2 classificadores base, optou-se por utilizar 4
classificadores na votação majoritária simétrica:
1
(4.6)
Espera-se que, a votação majoritária com peso simétrica traga ganhos na
predição por propiciar um ajuste na predição, aproximando do que se espera em
relação ao desempenho de cada classificador base, que compõe o sistema de
múltiplo de classificadores.
41
4.3.2. Definição dos classificadores individuais
Definida as formas de combinação dos classificadores para a construção do
modelo de sistema de múltiplos classificadores, faz-se necessário, então, determinar
como serão construídos os classificadores bases que irão compor o sistema.
Primeiramente, optou-se pela geração dos classificadores baseados nos parâmetros
de indução, ao invés de utilizar o modelo baseado em dados. Como a composição do
sistema é obtida com um número restrito de classificadores, espera-se ser capaz de
gerar um nível maior de diversidade entre os classificadores participantes, por meio
de um modelo baseado em parâmetros de indução. Por se limitar ao conjunto de
treinamento para gerar os classificadores, os modelos baseados em dados
necessitam, geralmente, de um grande número iterações ou classificadores
individuais para obterem um nível adequado de efetividade. Além do mais, tais
modelos geralmente são determinados por algoritmos fechados onde seus passos
devem ser seguidos com fidelidade para obter sucesso, diminuindo assim a
flexibilidade na composição de novos modelos.
Nos modelos baseados em parâmetros, como visto, pode-se utilizar um tipo de
classificador fixo, gerando classificadores bases com variações em valores de
parâmetros internos ou classificadores diferentes, com parâmetros internos fixados
inicialmente. A restrição buscada no número de classificadores base, leva diretamente
para a construção dos classificadores base utilizando-se de técnicas de classificação
diferentes. Esta escolha mostra-se natural por permitir uma maior diversidade, nas
hipóteses de classificação que serão construídas para cada classificador individual.
Espera-se que tais hipóteses devam ter um nível razoável de predição, para que se
tenha sucesso no sistema, ou seja, diversidade sem qualidade para sistemas restritos
42
são altamente comprometedores para o resultado final do sistema de múltiplos
classificadores.
Visto isto, é necessário definir 3 classificadores que sejam: i)
comprovadamente eficientes; ii) diferentes entre si, na sua estratégia de gerar
hipóteses de predição. Fica claro que os 2 classificadores, SVM e KNN, possuem
estas propriedades, conforme descrito anteriormente, podendo ser aproveitados
diretamente.
Como terceiro classificador base, optou-se pelo clusterizador KMEANS,
também descrito anteriormente, utilizado em aprendizado não-supervisionado. Não é
novidade a aplicação de um algoritmo para clusterização em problemas de
classificação. O modo mais comum para isto, é a associação de cada cluster a uma
classe específica, através de uma votação majoritária aplicada nos elementos do
cluster onde, a classe predominante rotula o cluster. Problemas usuais para esta
adaptação estão relacionados à geração de clusters somente designados a uma
classe, limitação da generalização das hipóteses, entre outros, que refletem na
qualidade da predição. Ou seja, espera-se que seus resultados sejam menos
eficientes em relação aos obtidos por técnicas mais específicas de classificação, como
os previamente definidos SVM e KNN. Porém, não se pode negar a forma diversa de
se obter a hipótese predição do KMEANS em comparação com o SMV e KNN.
Pode-se questionar, então, a opção por adotar uma técnica para aprendizado
não-supervisionado em um problema de aprendizado supervisionado. Principalmente,
levando-se em conta a gama de possíveis opções mais ortodoxas que se apresentam
na extensa literatura de aprendizado supervisionado. Justifica-se, inicialmente, tal
43
escolha pela possibilidade de aplicação do KMEANS uma forma mais flexível em
relação ao comumente encontrado. Este uso baseia-se na hipótese que:
/#
(4.7)
com #. sendo a cardinalidade de um conjunto. Ou seja, aumentar a relação
entre o número de clusters e classes é fundamental para o desempenho do KMEANS
aplicado em aprendizado supervisionado. Experimentos empíricos buscarão atestar
esta correlação.
Porém, a justificativa mais relevante para a utilização do KMEANS como
classificador base, será apresentada na construção do modelo hierárquico, onde suas
propriedades são essenciais para o funcionamento do método.
Necessita-se ainda, se definir como seria obtido um quarto classificador base,
necessário para o caso de se aplicar a votação majoritária com peso simétrica. Esta
definição foi determinada de uma forma prática, onde buscou-se determinar qual dos 3
classificadores utilizados, apresenta as principais variações no nível de predição em
relação aos seu principais parâmetros internos. Considerou-se como parâmetros
internos:
• SVM: kernel adotado e constante C;
• KNN: número de vizinhos (nv);
• KMEANS: número de clusters adotado (nc);
44
Outros parâmetros poderiam ser considerados como, por exemplo, a métrica
utilizada para o KMEANS e KNN. Porém, nos testes, ficou claro que o SVM sofria as
maiores variações, principalmente com a mudança do kernel utilizado. Assim,
determinou-se que, necessitando-se de 4 classificadores bases, 2 versões do SVM
seriam adotadas. A seguir, apresenta-se o pseudo-código do sistema de múltiplos
classificadores não-hierárquicos.
Pseudo-código: sistema de múltiplos classificadores não-hierárquicos
Início
Leia os conjuntos de treinamento S
tr
e conjunto de teste S
ts
;
Defina os classificadores base;
Defina os parâmetros dos classificadores base;
Treine os classificadores base usando o conjunto S
tr
;
Calcule os pesos
de cada classificador base para aplicação da
votação majoritária;
Aplique a votação majoritária (simétrica ou assimétrica) no conjunto S
ts
;
Fim.
Ficam então, os modelos de sistemas de múltiplos classificadores não-
hierárquicos definidos. Parte-se agora para os chamados modelos hierárquicos, onde
busca-se, principalmente, um desempenho computacional superior em relação aos
modelos não-hierárquicos.
45
4.4. Sistemas de múltiplos classificadores hierárquicos
A utilização de sistemas de múltiplos classificadores, tem como objetivo
principal gerar predições mais robustas combinando classificadores de forma a
otimizar a eficiência individual dos classificadores envolvidos para o tipo de dado em
questão. Pode também ser aplicado visando refinar o resultado obtido por um
classificador usado inicialmente [18].
Nos modelos tradicionais, aqui denominados não-hierárquicos, baseados em
parâmetros, existe um alto nível de paralelismo na geração do sistema. Este
paralelismo pode ser aproveitado na etapa de treinamento, através do treinamento
simultâneo dos diversos classificadores base envolvidos, pois o conjunto de
treinamento é o mesmo para todos. Somente no momento da predição é necessário
uma sincronia, onde deve-se ter os dados de todos os classificadores individuais para
o processo de combinação adotado. Logicamente, estratégias para balanceamento de
cargas são necessárias, principalmente quando adota-se modelos diferentes de
classificadores base implicando em diferentes tempos de treinamento.
Porém, é muito incomum encontrar na literatura modelos de múltiplos
classificadores paralelos. Na prática, todo o processo de treinamento é feito
serialmente, onde um a um vão sendo definidos as hipóteses dos classificadores de
base que serão utilizados na montagem do sistema.
Busca-se aqui, uma forma mais eficiente na construção do sistema de múltiplos
classificadores, através de um modelo racional de construção dos classificadores base
onde leva-se em conta:
• características específicas dos classificadores envolvidos;
46
• custo computacional para treinamento dos classificadores envolvidos;
• estratégia utilizada na combinação dos classificadores base.
Além disto, objetiva-se manter o nível de predição que se alcança, utilizando-se
os mesmos classificadores, em um modelo tradicional ou não-hierárquico equivalente.
A construção do modelo hierárquico será totalmente baseada no modelo não-
hierárquico apresentado anteriormente. Ou seja, requer-se as mesmas características
de construção que foram enfocadas na construção do modelo não-hierárquico como,
por exemplo, a restrição no número de classificadores base e o uso dos modelos de
combinação previamente definidos.
4.4.1. Uma estratégia de pré-combinação
Apresenta-se aqui, uma estratégia denominada de pré-combinação, viável de
ser implementada no modelo de multi-classificadores desenvolvido anteriormente.
Baseia-se na utilização prévia da votação majoritária, que deve ser aplicada
antes do término do treinamento de todos os classificadores base, necessários na
montagem do sistema. A idéia será exposta diretamente no sistema definido por 3
classificadores
,
, e
.
Primeiramente, ordena-se a seqüência em que será obtida os classificadores
base, de acordo com critérios que serão tratados adiante. Supondo que a ordem seja
a apresentada, obter-se-ia primeiro
seguido de
e finalmente
.
47
Findo o treinamento de
e
aplica-se a pré-combinação por meio da
votação majoritária gerando o subconjunto de treinamento hierárquico
definido
por:
|
(4.8)
Assim, o subconjunto de treinamento que será utilizado para treinar o
classificador
, é determinado pelas instâncias do conjunto de treinamento original
que não obtiveram unanimidade de classificação, em relação aos dois classificadores
já treinados. Porém, não se tem a garantia que a predição está correta. Na utilização
da votação majoritária, o resultado desta classificação não mudaria, independente da
classificação determinada pelo terceiro classificador para estas instâncias. Portanto, a
classificação obtida poderia ser modificada com a aplicação da votação majoritária
com peso. Porém, a idéia principal desta estratégia é filtrar o conjunto de treinamento,
de forma a retirar as instâncias que tenham fortes evidências de pertencerem a
determinada classe. Assume-se então, que estes exemplos são os mais simples de
serem classificados, sendo dispensados de participarem do treinamento do
classificador que falta para completar o sistema de classificação. Inicialmente, não se
tem uma noção adequada da porcentagem de instâncias do conjunto de treinamento
que irão compor o subconjunto de treinamento. Esta avaliação é importante pois,
dependendo da quantidade de exemplos no subconjunto de treinamento, pode-se ter
um comprometimento no treinamento do último classificador.
Outras escolhas podem ser feitas para a montagem do subconjunto de
treinamento. Algumas foram testadas, porém, a definida acima apresentou os
melhores resultados inicialmente.
48
4.4.2. Hierarquia na aplicação dos classificadores
Conforme definido e justificado anteriormente, os classificadores utilizados no
sistema de múltiplos classificadores desenvolvido são: SVM, KNN, e KMEANS sendo,
este último, adaptado para aplicação em aprendizado supervisionado.
Objetiva-se agora, definir a ordem de treinamento dos classificadores, para a
aplicação da pré-combinação e obtenção do subconjunto de treinamento utilizado no
último classificador. Leva-se em conta principalmente nesta ordenação, as
propriedades dos três classificadores envolvidos, em conjunto com a meta a ser
alcançada por este sistema hierárquico, a saber:
• preservação da qualidade de resposta do sistema não-hierárquico;
• ganho computacional.
Estes dois itens analisados em conjunto, levam a quase uma unicidade na
escolha da ordenação dos classificadores. Baseado nas vantagens e desvantagens de
cada classificador, vistas anteriormente, tem-se para o SVM:
• custo computacional elevado;
• boa capacidade de generalização, mesmo com poucas instâncias;
Ou seja, é altamente interessante, que o SVM seja utilizado como último
classificador, visto que seu custo computacional depende diretamente do número de
instâncias do conjunto de treinamento. Assim, utilizando-se o subconjunto de
treinamento, com um número menor de instâncias, seu custo será reduzido. Espera-se
que não haja comprometimento na qualidade da predição do SVM, justamente devido
49
a sua característica de funcionar bem com conjunto de treinamento considerados
pequenos.
Os dois classificadores iniciais utilizados na pré-combinação, KNN e KMEANS,
são bem mais eficientes computacionalmente em relação ao SVM, proporcionando
uma avaliação rápida do conjunto de treinamento. Além disto, devido as suas
estratégias de gerar as hipóteses de predição serem conceitualmente bem diferentes,
a classificação de uma instância na mesma classe pelos dois modelos, torna a
hipótese da instância pertencer a tal classe mais robusta.
4.4.3. Complementação do subconjunto de treinamento
O formato de construção do subconjunto de treinamento tem como principal
inconveniente, a falta de controle no número de instâncias que serão aproveitadas do
conjunto de treinamento original. A expectativa é que com o aumento de complexidade
dos dados a serem classificados, maior deva ser o subconjunto de treinamento. Dois
fatos devem ser levados em conta: i) problemas que gerem subconjuntos de
treinamentos pequenos podem tornar a aplicação do SVM pouco efetiva; ii) a
informação perdida com os dados excluídos do conjunto de treinamento pode dificultar
a generalização do SVM, apesar do mesmo ser eficiente na generalização, mesmo
com poucos dados.
Uma possível solução para evitar subconjuntos de treinamentos com número
inexpressivo de instâncias seria simplesmente definir uma restrição para o valor
mínimo de amostras que devam compor o subconjunto de treinamento. O
complemento com dados do próprio conjunto de treinamento, quando o subconjunto
50
apresentasse valor inferior ao mínimo, seria efetuado. Difícil portanto, garantir se, os
dados excluídos eram cruciais para uma boa generalização do SVM.
Visando tratar estes dois aspectos conjuntamente na geração do subconjunto
de treinamento, propõe-se aqui, uma complementação dos dados do subconjunto de
treinamento, não baseado na inclusão de dados excluídos do conjunto original de
treinamento mas, no aproveitamento das informações geradas pelo classificador
KMEANS, já aplicado. Sendo um clusterizador, apesar de adaptado para problemas
de classificação, tem como dados de saída os centros dos nc clusters que foram
solicitados.
Tais centros podem ser vistos como uma instância representativa do cluster
associado. Assim, a adição destas instâncias sintéticas ao subconjunto de treinamento
proporciona, além da complementação numérica do subconjunto de treinamento, uma
complementação das informações relacionadas aos dados excluídos, por meio da
representatividade dos centros dos clusters em relação a estes dados.
Trabalha-se aqui, com problemas de classificação binária. Isto implica que
nc=2, possivelmente seria insuficiente para uma complementação adequada do
subconjunto de treinamento. Assim, passa a ser essencial para o funcionamento do
sistema de múltiplos classificadores hierárquico, que o algoritmo KMEANS tenha um
bom desempenho para nc > 2, mesmo para problemas com somente duas classes.
51
4.4.4. Algoritmo do sistema de múltiplos classificadores
hierárquico
Finaliza-se este capítulo, com a apresentação do algoritmo do sistema de
múltiplos classificadores hierárquico desenvolvido. É importante ressaltar que, o uso
do subconjunto de treinamento hierárquico, é feito para o treinamento do classificador
SVM. Porém, depois de treinado todos os classificadores, o procedimento de
aplicação da votação majoritária com pesos assimétrica ou simétrica é efetuada
normalmente, visando obter uma predição mais eficiente em relação às predições dos
classificadores individuais envolvidos. Lista-se, a seguir, o pseudo-código do sistema
de múltiplos classificadores hierárquico.
Pseudo-código: sistema de múltiplos classificadores hierárquico
Início
Leia os conjuntos de treinamento S
tr
e conjunto de teste S
ts
;
Defina os parâmetros nv, nc e kernel dos classificadores base;
Treine o primeiro classificador C
KNN
usando o conjunto S
tr
;
Treine o segundo classificador C
KMEANS
usando o conjunto S
tr
e obtendo
os centros dos clusters
;
Determine o subconjunto de treinamento S
trh
de acordo com a definição
(4.8);
Defina
;
Treine o classificador C
SVM
usando o conjunto S
trh
;
Calcule os pesos
de cada classificador base para aplicação da
votação majoritária;
Aplique a votação majoritária (simétrica ou assimétrica) no conjunto S
ts
;
Fim.
52
A seguir, experimentos numéricos são realizados visando verificar a eficiência
dos modelos para classificação através dos sistemas de múltiplos classificadores
apresentados. Testes em dados reais bem como em dados sintéticos serão
executados para, não somente, obter resultados sobre a qualidade de resposta dos
modelos mas, também, aumentar o entendimento de suas formas de funcionamento.
53
Capítulo 5
Resultados Experimentais
Este capítulo tem o objetivo de avaliar os componentes do sistema proposto,
bem como o sistema como um todo.
Para as avaliações foram utilizadas 10 bases de dados diferentes, dentre elas,
4 bases foram retiradas do repositório de dados UCI (Blake e Merz, 1998) e as outras
6 são bancos de dados criados artificialmente.
As bases de dados foram escolhidas de forma a representar diversos tipos de
problemas. A diversidade de bases de dados escolhidas tem como objetivo garantir
uma melhor estimativa da capacidade de aprendizado do sistema.
5.1. Bases de dados utilizadas:
Banco Instâncias Atributos Inst. Faltantes Classes
sonar 208 60 0 2
ionosphere 351 34 0 2
breast-w 699 9 16 2
diabetes 768 8 0 2
Tabela 5.1: bases de dados
54
5.2. Metodologia experimental:
Dois modelos de sistema de classificação baseados em uma estratégia de
ensemble foram desenvolvidos. Ambos definem uma classificação semi-
supervisionada e são comparados entre si e em relação a um classificador SVM. O
primeiro sistema baseia-se em um processo de voto majoritário (majority voting), onde
a classificação do dado é definida pelo consenso dos resultados obtidos de forma
independente pelos classificadores envolvidos. No segundo modelo, utiliza-se uma
estratégia hierárquica, de forma que cada classificador atue nos dados de difícil
classificação dos demais. Testes realizados visando atestar a eficiência dos sistemas
de classificação apresentados serão demonstrados nos próximos capítulos.
Os resultados para todos os sistemas foram obtidos utilizando-se o sistema de
validação cruzada (treinamento e teste) com 10 rodadas. Sendo assim os resultados
apresentados são a média dos resultados obtidos nas 10 rodadas.
O tempo de execução exibido para cada sistema é a média dos resultados das
10 rodadas. Não foi levado em consideração o tempo necessário para determinar os
parâmetros para cada sistema, assim, o valor de tempo exibe, em média, o tempo
gasto para a execução dom sistema uma vez que seus parâmetros tenham sido
determinados. Os experimentos foram realizados em um microcomputador com
processador Intel® Core™ 2 Duo 4400 de 2.00Ghz, com 2047Mb de memória RAM,
no Sistema operacional Windows® XP 32 Bits, através de Scripts programados no
Matlab® 7.0 (R.14).
55
5.2.1. Sistema Não Hierárquico:
Primeiramente foi criado um sistema de classificação de dados utilizando-se 3
“classificadores” conhecidos o K-means, o KNN e o próprio SVM.
Nesse sistema escolhemos os parâmetros necessários para os testes, dentre
esses parâmetros estão:
• k : escolha do numero de rodadas da validação cruzada.
• nn : escolha do número de vizinhos para o KNN;
• nc : escolha do número de clusters para o K-means;
• kernel : escolha do kernel utilizado pelo SVM (linear, gaussiano).
• nr : escolha do nível de ruído utilizado;
Para a escolha do nn, o número de vizinhos para o KNN, foi realizado um
teste, variando o número de vizinhos de 1 até 15 vizinho e chegou-se a conclusão que
embora o resultado não varie muito o número que mostrou-se adequado de vizinhos,
foi definido como “7”. Nas figuras a seguir pode-se observar que o número de vizinho
“7” nem sempre é a melhor opção, mas como a variação é pequena, e também de
pouca influencia, foi o número que se mostrou mais estável para todos os bancos.
Abaixo segue o gráfico demonstrando os testes realizados:
56
Figura5.1:variável nn para algoritmo KNN banco sonar
Figura 5.2:variável nn para algoritmo KNN banco ionosphere
57
Figura 5.3:variável nn para algoritmo KNN banco breast-w
Figura 5.4:variável nn para algoritmo KNN banco diabetes
Assim como foi feito um teste para a escolha do nn, também foi realizado um
teste similar para a escolha do nc, o número de clusters para o K-means. Foi realizado
um teste, variando o número de clusters de 2 até 20 e chegou-se a conclusão que
58
embora o resultado não varie muito o número ótimo de clusters foi definido como “7”.
Abaixo segue o gráfico demonstrando os testes realizados:
Figura 5.5:variável nc para algoritmo KMEANS banco sonar
Figura 5.6:variável nc para algoritmo KMEANS banco ionosphere
59
Figura 5.7:variável nc para algoritmo KMEANS banco breast-w
Figura 5.8:variável nc para algoritmo KMEANS banco diabetes
60
Após a definição dos parâmetros é executado teste de onde são retirados os
resultados contendo a média de acerto de cada classificador das 10 rodadas, a média
do seu tempo de execução nas 10 rodadas.
Com os resultados de cada um dos classificadores é executada uma votação
majoritária, onde a classificação do dado é definida pelo consenso dos resultados
obtidos de forma independente pelos classificadores envolvidos. Assim pode-se
avaliar o desempenho de cada classificador e no final o resultado escolhido pelo voto
majoritário, bem como seus tempos de execução.
Esses primeiros testes foram realizados com 2 “kernels” diferentes. Pois uma
escolha complicada na aplicação do SVM é a escolha do kernel adequada para cada
tipo de dado. Dois dos mais utilizados são o linear, o mais simples, e o kernel
gaussiano . Buscando mostrar a diferença de desempenho que ocorre com a
utilização do kernel, testes serão realizados utilizados estes dois modelos.
Nas tabelas abaixo podemos ver o comportamento dos classificadores nos 4
bancos de dados retirados do UCI.
Banco: sonar
NÂO HIERÁRQUICO
LINEAR
NÂO HIERÁRQUICO
GAUSSIANO
KNN 73.1% 73.1%
KMEANS 65.4% 55.8%
SVM 76.9% 81.3%
VM 76.4% 77.9%
VMP 76.4% 77.9%
Tempo médio KNN 0.00 s. 0.00 s.
Tempo médio KMEANS 0.03 s. 0.04 s.
Tempo médio SVM 2.24 s. 2.53 s.
Tempo médio total 2.27 s. 2.58 s.
Tabela 5.2: banco sonar 208 instâncias
61
Banco:
ionosphere
NÂO HIERÁRQUICO
LINEAR
NÂO HIERÁRQUICO
GAUSSIANO
KNN 83.8% 83.8%
KMEANS 85.2% 86.0%
SVM 85.5% 95.4%
VM 85.5% 87.7%
VMP 85.5% 87.7%
Tempo médio KNN 0.00 s. 0.01 s.
Tempo médio KMEANS 0.03 s. 0.04 s.
Tempo médio SVM 8.28 s. 9.27 s.
Tempo médio total 8.32 s. 9.32 s.
Tabela 5.3: banco ionosphere 351 instâncias
Banco: breast-w
NÂO HIERÁRQUICO
LINEAR
NÂO HIERÁRQUICO
GAUSSIANO
KNN 96.7% 96.7%
KMEANS 97.1% 97.0%
SVM 96.4% 96.9%
VM 96.9% 97.3%
VMP 96.9% 97.3%
Tempo médio KNN 0.01 s. 0.02 s.
Tempo médio KMEANS 0.04 s. 0.05 s.
Tempo médio SVM 60.09 s. 58.72 s.
Tempo médio total 60.15 s. 58.79 s.
Tabela 5.4: banco breast-w 699 instâncias
Banco: diabetes
NÂO HIERÁRQUICO
LINEAR
NÂO HIERÁRQUICO
GAUSSIANO
KNN 73.4% 73.4%
KMEANS 66.9% 68.4%
SVM 76.0% 70.6%
VM 74.6% 72.5%
VMP 74.6% 72.5%
Tempo médio KNN 0.02 s. 0.02 s.
Tempo médio KMEANS 0.07 s. 0.08 s.
Tempo médio SVM 65.10 s. 128.76 s.
Tempo médio total 65.19 s. 128.86 s.
Tabela 5.5: banco diabetes 768 instâncias
62
Podemos observar o comportamento de cada classificador individualmente e
também no caso do SVM podemos ver a diferença entre o uso do kernel linear e do
kernel gaussiano
Baseado no sistema anterior, buscando-se um maior aprimoramento dos
resultados foi criado um sistema com peso onde se busca maior robustez no resultado
apresentado pelo processo de voto majoritário (majority voting). Que anteriormente,
como explicado no capítulo anterior, tínhamos 3 classificadores e um sistema de peso
simples, agora continuamos com os 3 primeiros classificadores e adicionamos ao
sistema o que chamaremos de SVM2, que nada mas é do que o classificador SVM
utilizando-se do kernel gaussiano, para podermos inverter o resultado quando o
classificador mais confiável estiver contrario aos outros.
Espera-se, com essa mudança um ganho no resultado final, nas tabelas a
seguir veremos os resultados desse novo modelo:
Banco: sonar
NÂO HIERÁRQUICO SIMÉTRICO
KNN 73.1%
KMEANS 65.4%
SVM
linea
r
76.9%
SVM
Gauss
87.5%
VM 74.5%
VMP 83.7%
Tempo médio KNN 0.01 s
Tempo médio KMEANS 0.04 s
Tempo médio SVM
linea
r
2.25 s
Tempo médio SVM
Gauss
2.60 s
Tempo médio total 4.90 s
Tabela 5.6: banco sonar 208 instâncias
63
Banco: ionosphere
NÂO HIERÁRQUICO SIMÉTRICO
KNN
83.8%
KMEANS 86.9%
SVM
linea
r
85.5%
SVM
Gauss
95.4%
VM 85.8%
VMP 90.9%
Tempo médio KNN 0.00 s.
Tempo médio KMEANS 0.04 s.
Tempo médio SVM
linea
r
8.44 s.
Tempo médio SVM
Gauss
9.39 s.
Tempo médio total 17.88 s.
Tabela 5.7: banco ionosphere 351 instâncias
Banco: breast-w
NÂO HIERÁRQUICO SIMÉTRICO
KNN 96.7%
KMEANS 96.4%
SVM
linea
r
96.4%
SVM
Gauss
96.9%
VM 96.4%
VMP 97.3%
Tempo médio KNN 0.02 s.
Tempo médio KMEANS 0.06 s
Tempo médio SVM
linea
r
61.03 s.
Tempo médio SVM
Gauss
59.43 s.
Tempo médio total 120.54 s.
Tabela 5.8: banco breast-w 699 instâncias
Banco: diabetes
NÂO HIERÁRQUICO SIMÉTRICO
KNN 73.4%
KMEANS 66.8%
SVM
linea
r
76.0%
SVM
Gauss
70.6%
VM 74.5%
VMP 76.6%
Tempo médio KNN 0.03 s.
Tempo médio KMEANS 0.10 s.
Tempo médio SVM
linea
r
66.19 s.
Tempo médio SVM
Gauss
137.73 s.
Tempo médio total 203.92 s.
Tabela 5.9: banco diabetes 768 instâncias
64
Note que a um ganho significativo neste novo modelo comparado ao anterior,
dependendo do banco de dados utilizado, obtivemos ganhos de até 7 pontos
percentuais. Como no exemplo do banco “sonar” onde no percentual de acerto no
processo de voto majoritário com peso (WMV) passou de 76.4% no modelo de peso
simples, para 83.7% no novo modelo de peso.
5.2.2. Sistema Hierárquico:
Baseado nos modelos anteriores foi desenvolvido um modelo hierárquico, já
explicado no capitulo anterior, onde são enviados para o classificador SVM apenas os
dados em que os dois primeiros classificadores (KNN e K-Means) não obtiverem
concordância na classificação, ou seja os dados duvidosos. Espera-se desse novo
modelo um ganho significativo em custo computacional com uma significativa
diminuição no tempo total, mantendo-se o nível de robustez já alcançado. A seguir as
tabelas com os resultados desse novo modelo:
Banco: sonar
HIERÁRQUICO ASSIMÉTRICO
KNN 73.1%
KMEANS 62.0%
SVM
linea
r
66.3%
SVM
Gauss
VM 75.0%
VMP 75.0%
Tempo médio KNN 0.05 s
Tempo médio KMEANS 0.04 s
Tempo médio SVM
linea
r
0.29 s
Tempo médio SVM
Gauss
Tempo médio total 0.39 s
Instâncias enviadas SVM 35.15%
Tabela 5.10: banco sonar 208 instâncias
65
Banco: iosophere
HIERÁRQUICO ASSIMÉTRICO
KNN 83.8%
KMEANS 86.3%
SVM
linea
r
63.8%
SVM
Gauss
VM 85.8%
VMP 85.8%
Tempo médio KNN 0.07 s
Tempo médio KMEANS 0.05 s
Tempo médio SVM
linea
r
0.09 s
Tempo médio SVM
Gauss
Tempo médio total 0.21 s
Instâncias enviadas SVM 9.53%
Tabela 5.11: banco ionosphere 351 instâncias
Banco: breast-w
HIERÁRQUICO ASSIMÉTRICO
KNN
96.7%
KMEANS
96.7%
SVM
linea
r
93.4%
SVM
Gauss
VM
96.7%
VMP
96.7%
Tempo médio KNN
0.21 s
Tempo médio KMEANS
0.08 s
Tempo médio SVM
linea
r
0.07 s
Tempo médio SVM
Gauss
Tempo médio total
0.36 s
Instâncias enviadas SVM
3.67%
Tabela 5.12: banco breast-w 699 instâncias
Banco: diabetes
HIERÁRQUICO ASSIMÉTRICO
KNN 73.4%
KMEANS 67.1%
SVM
linea
r
74.9%
SVM
Gauss
VM 73.0%
VMP 73.0%
Tempo médio KNN 0.22 s
Tempo médio KMEANS 0.12 s
Tempo médio SVM
linea
r
1.46 s
Tempo médio SVM
Gauss
Tempo médio total 1.80 s
Instâncias enviadas SVM 22.57%
Tabela 5.13: banco diabetes 768 instâncias
Como era esperado, ouve um ganho significativo em custo computacional com
uma significativa diminuição no tempo total, mantendo-se o nível de robustez já
66
alcançado, superando expectativas. Mesmo em um banco de dados de difícil
classificação e com muitos dados, como é o caso do exemplo do banco “diabetes”
nota-se claramente essa conclusão, onde o tempo de execução caiu de gigantescos
65.19 segundos para mínimos 1.80 segundos e ainda com níveis similares de acertos.
Seguindo nosso padrão adotado agora serão feitos testes no modelo
hierárquico com 4 classificadores, possibilitando assim inverter o resultado quando o
classificador mais confiável estiver contrario aos outros. Espera-se também desse
novo modelo um ganho significativo em custo computacional com uma significativa
diminuição no tempo total, mantendo-se o nível de robustez já alcançado. A seguir as
tabelas com os resultados desse novo modelo:
Banco: sonar
HIERÁRQUICO SIMÉTRICO
KNN 73.1%
KMEANS 60.1%
SVM
linea
r
67.3%
SVM
Gauss
71.6%
VM 76.0%
VMP 77.9%
Tempo médio KNN 0.03 s
Tempo médio KMEANS 0.03 s
Tempo médio SVM
linea
r
0.27 s
Tempo médio SVM
Gauss
0.30 s
Tempo médio total 0.63 s
Instâncias enviadas SVM 35.47%
Tabela 5.14: banco sonar 208 instâncias
Banco: ionosphere
HIERÁRQUICO SIMÉTRICO
KNN 83.8%
KMEANS 85.5%
SVM
linea
r
65.0%
SVM
Gauss
40.5%
VM 85.5%
VMP 85.8%
Tempo médio KNN 0.08 s
Tempo médio KMEANS 0.05 s
Tempo médio SVM
linea
r
0.07 s
Tempo médio SVM
Gauss
0.09 s
Tempo médio total 0.28 s
Instâncias enviadas SVM 11.49%
Tabela 5.15: banco ionosphere 351 instâncias
67
Banco breast-w
HIERÁRQUICO SIMÉTRICO
KNN 96.7%
KMEANS 95.7%
SVM
linea
r
78.1%
SVM
Gauss
56.8%
VM 96.3%
VMP 96.0%
Tempo médio KNN 0.21 s
Tempo médio KMEANS 0.09 s
Tempo médio SVM
linea
r
0.07 s
Tempo médio SVM
Gauss
0.11 s
Tempo médio total 0.47 s
Instâncias enviadas SVM 3.56%
Tabela 5.16: banco breast-w 699 instâncias
Banco: diabetes
HIERÁRQUICO SIMÉTRICO
KNN 73.4%
KMEANS 66.7%
SVM
linea
r
75.0%
SVM
Gauss
65.1%
VM 73.4%
VMP 74.1%
Tempo médio KNN 0.22 s
Tempo médio KMEANS 0.10 s
Tempo médio SVM
linea
r
1.51 s
Tempo médio SVM
Gauss
1.83 s
Tempo médio total 3.66 s
Instâncias enviadas SVM 22.56%
Tabela 5.17: banco diabetes 768 instâncias
Note que ouve um ganho significativo em custo computacional com uma
significativa diminuição no tempo total, mantendo-se o nível de robustez já alcançada.
Utilizando-se novamente do exemplo do banco de dados “diabetes” pode-se observar,
que o tempo de execução caiu 203.92 segundos para 3.66 segundos, o que
representa uma redução de 92,5% de tempo e ainda com níveis similares de acertos.
Nos resultados apresentados nas tabelas a seguir o sistema hierárquico
simétrico será executado sem os centros dos clusters, obtidos pelo algoritmo
KMEANS, as instâncias enviadas ao SVM. Logo espera-se uma diminuição no número
68
percentual de acertos. Estes testes serão demonstrados apenas no sistema
hierárquico simétrico, pois seu desempenho foi satisfatório e tomo-se como padrão a
utilização dos centros.
Banco: sonar
HIERÁRQUICO SIMÉTRICO
KNN 73.1%
KMEANS 58.7%
SVM
linea
r
65.9%
SVM
Gauss
66.3%
VM 73.1%
VMP 75.5%
Tempo médio KNN 0.04 s
Tempo médio KMEANS 0.06 s
Tempo médio SVM
linea
r
0.26 s
Tempo médio SVM
Gauss
0.30 s
Tempo médio total 0.66 s
Instâncias enviadas SVM 29.27%
Tabela 5.14: banco sonar 208 instâncias
Banco: ionosphere
HIERÁRQUICO SIMÉTRICO
KNN 83.8%
KMEANS 82.9%
SVM
linea
r
57.5%
SVM
Gauss
40.5%
VM 83.0%
VMP 83.9%
Tempo médio KNN 0.07 s
Tempo médio KMEANS 0.05 s
Tempo médio SVM
linea
r
0.12 s
Tempo médio SVM
Gauss
0.12 s
Tempo médio total 0.36 s
Instâncias enviadas SVM 7.31%
Tabela 5.19: banco ionosphere 351 instâncias
69
Banco breast-w
HIERÁRQUICO SIMÉTRICO
KNN 96.7%
KMEANS 95.7%
SVM
linea
r
77.1%
SVM
Gauss
55.7%
VM 94.6%
VMP 95.2%
Tempo médio KNN 0.15 s
Tempo médio KMEANS 0.07 s
Tempo médio SVM
linea
r
0.11 s
Tempo médio SVM
Gauss
0.10 s
Tempo médio total 0.43 s
Instâncias enviadas SVM 2.26%
Tabela 5.20: banco breast-w 699 instâncias
Banco: diabetes
HIERÁRQUICO SIMÉTRICO
KNN 73.4%
KMEANS 66.7%
SVM
linea
r
73,0%
SVM
Gauss
63.1%
VM 71.4%
VMP 72.1%
Tempo médio KNN 0.22 s
Tempo médio KMEANS 0.16 s
Tempo médio SVM
linea
r
1.53 s
Tempo médio SVM
Gauss
2.12 s
Tempo médio total 4.03 s
Instâncias enviadas SVM 21.30 %
Tabela 5.21.: banco diabetes 768 instâncias
Conforme o esperado, nota-se que com a retirada dos centros dos cluster
ocorre uma queda nos valores percentuais dos acertos, por essa razão se adotou-se
como padrão o envio dos centros dos clusters, juntamente com as instâncias
escolhidas para o SVM.
70
5.3. Bancos Artificiais
Com o aprendizado adquirido nos testes anteriores agora serão feitos testes
em bancos criados artificialmente buscando testar e entender por meio de visualização
o comportamento do sistema hierárquico e tentar justificar o seu bom funcionamento.
Para a seqüência de testes a seguir foram criados 6 bancos artificiais. Os
bancos são gerados usando-se uma distribuição gaussiana randômica para geração
das classes. Visando a analise de desempenho em situações distintas do
posicionamento do centróide para geração das classes adota-se:
• C1: centro classe 1: (x,y) = (-1,-1); centro classe 2: (x,y) = (1,1);
• C2: centro classe 1: (x,y) = (-1,-1); centro classe 2: (x,y) = (1,1);
Espera-se que para os exemplos gerados de acordo com os centróides C2
tenham um nível de dificuldade maior na predição por estarem mais próximos gerando
uma região maior de sobreposição entre as classes do que a obtida quando utiliza-se
como centro das classes os valores em C1. Complementa-se a geração dos bancos
artificiais para verificação de desempenho dos algoritmos desenvolvidos variando-se o
número de instâncias entre os bancos utilizando-se 200, 400 e 800 instâncias , sendo
metade referente a cada uma das classes. A tabela abaixo descreve os bancos
artificiais testados
Banco Instâncias Atributos Classes
BAC1.1
200 2 2
BAC1.2
400 2 2
BAC1.3
800 2 2
BAC2.1
200 2 2
BAC2.2
400 2 2
BAC2.3
800 2 2
Tabela 5.18 Bancos Artificiais
71
A seguir serão apresentados os bancos artificiais testados no primeiro modelo
com suas imagens de visualização e em seguida suas respectivas tabelas de
resultados:
Fig 5.9: banco artificial centro C1 e 200 instâncias – BAC1.1
Banco: BAC1.1
NÂO HIERÁRQUICO SIMÉTRICO
KNN 69.5%
KMEANS 70.0%
SVM
linea
r
69.5%
SVM
Gauss
70.6%
VM 70.5%
VMP 72.0%
Tempo médio KNN 0.01 s
Tempo médio KMEANS 0.03 s
Tempo médio SVM
linea
r
2.03 s
Tempo médio SVM
Gauss
2.33 s
Tempo médio total 4.39 s
Tabela 5.19: banco artificial centro C1 e 200 instâncias – BAC1.1
72
Fig 5.10: banco artificial centro C1 e 400 instâncias – BAC1.2
Banco:
BAC1.2
NÂO HIERÁRQUICO SIMÉTRICO
KNN 74.0%
KMEANS 68.5%
SVM
linea
r
72.0%
SVM
Gauss
65.8%
VM 73.0%
VMP 75.3%
Tempo médio KNN 0.01 s
Tempo médio KMEANS 0.04 s
Tempo médio SVM
linea
r
10.85 s
Tempo médio SVM
Gauss
12.14 s
Tempo médio total 23.04 s
Tabela 5.20: banco artificial centro C1 e 400 instâncias – BAC1.2
73
Fig 5.11: banco artificial centro C1 e 400 instâncias – BAC1.3
Banco:
BAC1.3
NÂO HIERÁRQUICO SIMÉTRICO
KNN 68.6%
KMEANS 66.9%
SVM
linea
r
70.5%
SVM
Gauss
65.6%
VM 69.6%
VMP 70.8%
Tempo médio KNN 0.02 s
Tempo médio KMEANS 0.10 s
Tempo médio SVM
linea
r
73.62 s
Tempo médio SVM
Gauss
80.47 s
Tempo médio total 154.20 s
Tabela 5.21: banco artificial centro C1 e 400 instâncias – BAC1.3
74
Fig 5.12: banco artificial centro C2 e 200 instâncias – BAC1.1
Banco: BAC2.1
NÂO HIERÁRQUICO SIMÉTRICO
KNN 87.5%
KMEANS 85.5%
SVM
linea
r
88.0%
SVM
Gauss
83.5%
VM 88.5%
VMP 89.5%
Tempo médio KNN 0.01 s
Tempo médio KMEANS 0.02 s
Tempo médio SVM
linea
r
2.07 s
Tempo médio SVM
Gauss
2.31 s
Tempo médio total 4.41 s
Tabela 5.22: banco artificial centro C2 e 200 instâncias – BAC1.1
75
Fig 5.13: banco artificial centro C2 e 400 instâncias – BAC2.2
Banco: BAC2.2
NÂO HIERÁRQUICO SIMÉTRICO
KNN 89.8%
KMEANS 85.8%
SVM
linea
r
88.0%
SVM
Gauss
87.3%
VM 89.5%
VMP 90.5%
Tempo médio KNN 0.01 s
Tempo médio KMEANS 0.05 s
Tempo médio SVM
linea
r
11.39 s
Tempo médio SVM
Gauss
12.48 s
Tempo médio total 23.94 s
Tabela 5.23: banco artificial centro C2 e 400 instâncias – BAC2.2
76
Fig 5.14: banco artificial centro C2 e 800 instâncias – BAC2.3
Banco: BAC2.3
NÂO HIERÁRQUICO SIMÉTRICO
KNN 88.3%
KMEANS 86.9%
SVM
linea
r
89.5%
SVM
g
auss
86.1%
VM 89.1%
VMP 89.8%
Tempo médio KNN 0.02 s
Tempo médio KMEANS 0.10 s
Tempo médio SVM
linea
r
76.55 s
Tempo médio SVM
g
auss
83.10 s
Tempo médio total 159.78 s
Tabela 5.24: banco artificial centro C2 e 800 instâncias – BAC2.3
77
Agora serão apresentados os bancos artificiais testados no segundo modelo o
modelo Hierárquico, onde são enviados para o classificador SVM apenas os dados em
que os dois primeiros classificadores (KNN e K-Means) não obtiverem concordância
na classificação, ou seja, os dados duvidosos.
Espera-se desse modelo um ganho significativo em custo computacional com
uma significativa diminuição no tempo total, mantendo-se o nível de robustez já
alcançado.
Nas tabelas abaixo seguem os respectivos bancos com suas imagens de
visualização e em seguida suas respectivas tabelas de resultados:
Fig 5.15: banco artificial centro C1 e 200 instâncias – BAC1.1
78
Fig 5.16: comparativo instâncias enviadas ao SVM BAC 1.1
Banco:
BAC1.1
HIERÁRQUICO SIMÉTRICO
KNN 70.0%
KMEANS 66.0%
SVM
linea
r
67.5%
SVM
g
auss
71.5%
VM 68.0%
VMP 72.0%
Tempo médio KNN 0.03 s
Tempo médio KMEANS 0.03 s
Tempo médio SVM
linea
r
0.22 s
Tempo médio SVM
g
auss
0.27 s
Tempo médio total 0.55 s
Instâncias enviadas SVM 26.89%
Tabela 5.25: banco artificial centro C1 e 200 instâncias – BAC1.1
79
Fig 5.17: banco artificial centro C1 e 400 instâncias – BAC1.2
Fig 5.18: comparativo instâncias enviadas ao SVM BAC 1.2
Banco: BAC1.2
HIERÁRQUICO SIMÉTRICO
KNN 68.8%
KMEANS 70.0%
SVM
linea
r
70.3%
SVM
g
auss
67.5%
VM 70.3%
VMP 71.0%
Tempo médio KNN 0.05 s
Tempo médio KMEANS 0.29 s
Tempo médio SVM
linea
r
0.35 s
Tempo médio SVM
g
auss
0.75 s
Tempo médio total 1.44 s
Instâncias enviadas SVM 15.92%
Tabela 5.26: banco artificial centro C1 e 400 instâncias – BAC1.2
80
Fig 5.19: banco artificial centro C1 e 800 instâncias – BAC1.3
Fig 5.20: comparativo instâncias enviadas ao SVM BAC 1.2
Banco: BAC1.3
HIERÁRQUICO SIMÉTRICO
KNN 72.8%
KMEANS 72.4%
SVM
linea
r
72.6%
SVM
g
auss
73.0%
VM 73.6%
VMP 74.6%
Tempo médio KNN 0.15 s
Tempo médio KMEANS 0.09 s
Tempo médio SVM
linea
r
1.06 s
Tempo médio SVM
g
auss
1.22 s
Tempo médio total 2.52 s
Instâncias enviadas SVM 17.11%
Tabela 5.27: banco artificial centro C1 e 800 instâncias – BAC1.3
81
Fig 5.21: banco artificial centro C2 e 200 instâncias – BAC2.1
Fig 5.22: comparativo instâncias enviadas ao SVM BAC 2.1
Banco: BAC2.1
HIERÁRQUICO SIMÉTRICO
KNN 91.0%
KMEANS 88.5%
SVM
linea
r
89.5%
SVM
g
auss
88.0%
VM 90.0%
VMP 91.5%
Tempo médio KNN 0.02 s
Tempo médio KMEANS 0.05 s
Tempo médio SVM
linea
r
0.08 s
Tempo médio SVM
g
auss
0.15 s
Tempo médio total 0.30 s
Instâncias enviadas SVM 12.61%
Tabela 5.28: banco artificial centro C2 e 200 instâncias – BAC2.1
82
Fig 5.23: banco artificial centro C2 e 400 instâncias – BAC2.2
Fig 5.24: comparativo instâncias enviadas ao SVM BAC 2.2
Banco: BAC2.2
HIERÁRQUICO SIMÉTRICO
KNN 89.0%
KMEANS 84.8%
SVM
linea
r
87.0%
SVM
g
auss
87.8%
VM 88.8%
VMP 89.8%
Tempo médio KNN 0.05 s
Tempo médio KMEANS 0.06 s
Tempo médio SVM
linea
r
0.16 s
Tempo médio SVM
g
auss
0.20 s
Tempo médio total 0.47 s
Instâncias enviadas SVM 10.78%
Tabela 5.29: banco artificial centro C2 e 400 instâncias – BAC2.2
83
Fig 5.25: banco artificial centro C2 e 800 instâncias – BAC2.3
Fig 5.26: comparativo instâncias enviadas ao SVM BAC 2.3
Banco: BAC2.3
HIERÁRQUICO SIMÉTRICO
KNN 86.9%
KMEANS 85.4%
SVM
linea
r
86.5%
SVM
g
auss
86.8%
VM 87.8%
VMP 88.3%
Tempo médio KNN 0.16 s
Tempo médio KMEANS 0.12 s
Tempo médio SVM
linea
r
0.30 s
Tempo médio SVM
g
auss
0.36 s
Tempo médio total 0.93 s
Instâncias enviadas SVM 7.93%
Tabela 5.27: banco artificial centro C2 e 800 instâncias – BAC2.3
84
Note que assim como ocorreu nos exemplos anteriores, ouve um ganho
significativo em custo computacional com uma significativa diminuição no tempo total,
mantendo-se o nível de robustez já alcançado.
5.3.1. Análise de Dados Sujeito a Ruído
Agora serão apresentados os resultados dos mesmos bancos (artificiais), com
exceção do primeiro modelo visto que o segundo modelo mostrou-se mais eficaz, logo,
só serão realizados testes com o modelo Hierárquico Simétrico. Porém agora os
resultados serão modificados pois nestes novos testes adiciona-se ruído gaussiano
em níveis de 0.2 e 0.4 respectivamente:
Fig 5.28: banco artificial centro C1 e 200 instâncias – BAC1.1
Nível de ruído: 20% 40%
Banco: BAC1.1 BAC1.1
HIERÁRQUICO SIMÉTRICO HIERÁRQUICO SIMÉTRICO
KNN 69.5% 72.5%
KMEANS 72.5% 74.0%
SVM
linea
r
74.0% 75.0%
SVM
g
auss
69.0% 74.5%
VM 71.5% 75.5%
VMP 73.0% 76.5%
Tempo médio KNN 0.03 s 0.02 s
Tempo médio KMEANS 0.05 s 0.03 s
Tempo médio SVM
linea
r
0.21 s 0.15 s
Tempo médio SVM
g
auss
0.18 s 0.17 s
Tempo médio total 0.47 s 0.36 s
Instâncias enviadas SVM 20.00 % 17.67 %
Tabela 5.31:banco artificial centro C1 e 200 instâncias – BAC1.1
85
Fig 5.29: banco artificial centro C1 e 400 instâncias – BAC1.2
Nível de ruído: 20% 40%
Banco: BAC1.2 BAC1.2
HIERÁRQUICO SIMÉTRICO HIERÁRQUICO SIMÉTRICO
KNN 73.8% 73.0%
KMEANS 73.0% 72.8%
SVM
linea
r
71.3% 65.3%
SVM
g
auss
73.8% 72.5%
VM 73.8% 75.0%
VMP 75.8% 75.8%
Tempo médio KNN 0.06 s 0.05 s
Tempo médio KMEANS 0.06 s 0.08 s
Tempo médio SVM
linea
r
0.38 s 0.30 s
Tempo médio SVM
g
auss
0.41 s 0.36 s
Tempo médio total 0.92 s 0.79 s
Instâncias enviadas SVM 18.28 % 16.22 %
Tabela 5.32: banco artificial centro C1 e 400 instâncias – BAC1.2
86
Fig 5.30: banco artificial centro C1 e 800 instâncias – BAC1.3
Nível de ruído: 20% 40%
Banco: BAC1.3 BAC1.3
HIERÁRQUICO SIMÉTRICO HIERÁRQUICO SIMÉTRICO
KNN 72.9% 70.5%
KMEANS 72.5% 70.5%
SVM
linea
r
66.9% 67.3%
SVM
g
auss
71.3% 68.4%
VM 74.6% 69.6%
VMP 74.6% 71.3%
Tempo médio KNN 0.15 s 0.15 s
Tempo médio KMEANS 0.09 s 0.11 s
Tempo médio SVM
linea
r
0.84 s 1.53 s
Tempo médio SVM
g
auss
0.84 s 1.74 s
Tempo médio total 2.06 s 3.53 s
Instâncias enviadas SVM 15.04 % 20.67 %
Tabela 5.33: banco artificial centro C1 e 800 instâncias – BAC1.3
87
Fig 5.31: banco artificial centro C2 e 200 instâncias – BAC2.1
Nível de ruído: 20% 40%
Banco: BAC2.1 BAC2.1
HIERÁRQUICO SIMÉTRICO HIERÁRQUICO SIMÉTRICO
KNN 86.5% 84.5%
KMEANS 82.0% 85.5%
SVM
linea
r
84.5% 83.5%
SVM
g
auss
86.0% 84.0%
VM 85.0% 85.5%
VMP 86.0% 86.5%
Tempo médio KNN 0.02 s 0.02 s
Tempo médio KMEANS 0.04 s 0.04 s
Tempo médio SVM
linea
r
0.10 s 0.06 s
Tempo médio SVM
g
auss
0.15 s 0.06 s
Tempo médio total 0.31 s 0.18 s
Instâncias enviadas SVM 15.00 % 11.28 %
Tabela 5.34: banco artificial centro C2 e 200 instâncias – BAC2.1
88
Fig 5.32: banco artificial centro C2 e 400 instâncias – BAC2.2
Nível de ruído: 20% 40%
Banco: BAC2.2 BAC2.2
HIERÁRQUICO SIMÉTRICO HIERÁRQUICO SIMÉTRICO
KNN 88.8% 87.3%
KMEANS 86.8% 85.8%
SVM
linea
r
84.5% 85.8%
SVM
g
auss
87.5% 86.8%
VM 90.0% 88.0%
VMP 89.5% 88.3%
Tempo médio KNN 0.06 s 0.05 s
Tempo médio KMEANS 0.07 s 0.05 s
Tempo médio SVM
linea
r
0.18 s 0.14 s
Tempo médio SVM
g
auss
0.21 s 0.16 s
Tempo médio total 0.51 s 0.40 s
Instâncias enviadas SVM 10.39 % 9.97 %
Tabela 5.35: banco artificial centro C2 e 400 instâncias – BAC2.2
89
Fig. 5.33: banco artificial centro C2 e 800 instâncias – BAC2.3
Nível de ruído: 20% 40%
Banco: BAC2.3 BAC2.3
HIERÁRQUICO SIMÉTRICO HIERÁRQUICO SIMÉTRICO
KNN 82.6% 87.1%
KMEANS 84.0% 87.5%
SVM
linea
r
84.3% 83.3%
SVM
g
auss
82.4% 85.5%
VM 84.3% 87.8%
VMP 84.4% 88.4%
Tempo médio KNN 0.15 s 0.15 s
Tempo médio KMEANS 0.11 s 0.11 s
Tempo médio SVM
linea
r
0.68 s 0.30 s
Tempo médio SVM
g
auss
0.75 s 0.35 s
Tempo médio total 1.69 s 0.92 s
Instâncias enviadas SVM 13.22 % 7.67 %
Tabela 5.36: banco artificial centro C2 e 800 instâncias – BAC2.3
90
Analisando os resultados obtidos da adição de ruídos nos bancos artificiais,
nota-se um comportamento não esperado nos níveis de predição obtidos. Ou seja, a
influência dos dados poluídos não se apresentou tão comprometedora como era
previsto. Logicamente, tal fato não ocorreu somente nos sistemas de múltiplo
classificadores apresentados, mas em todos os classificadores individuais utilizados.
Um aprofundamento maior em relação às implicações de dados ruidosos em
problemas de aprendizado supervisionado é necessário para que se tenha conclusões
mais detalhadas sobre como a predição é afetada quando aplicada em banco de
dados com ruídos
91
Capítulo 6
Conclusões e Perspectivas
Neste trabalho, diversas análises e desenvolvimentos relacionados a técnicas
para aprendizado supervisionado baseadas em múltiplos classificadores foram
apresentados. Buscou-se a compreensão das características determinantes para
construção de um sistema de múltiplos classificadores eficiente, de forma que, tais
conhecimentos direcionassem as estratégias utilizadas na determinação,
principalmente, do modelo de sistema de classificação utilizado, na escolha efetiva dos
classificadores envolvidos e na estratégia para combinação dos classificadores base
para gerar os sistemas de classificação considerados.
Pode-se assumir que foram determinados modelos de sistemas de
classificação denominados restritos, com número reduzido de classificadores base,
que podem ser categorizados em relação: i) a forma de combinação dos
classificadores individuais e ii) estratégia para treinamento dos classificadores
individuais.
Em relação à forma de combinação dos classificadores, apresenta-se a
chamada combinação assimétrica, onde três classificadores são combinados por meio
de uma votação majoritária com peso, construída especificamente para este tipo de
92
sistema com número de classificadores restritos. Foi adotada em opção a votação
majoritária padrão. Visando um melhor aproveitamento das informações contidas nos
pesos da votação majoritária, um modelo de combinação denominado simétrico foi
apresentado, com o objetivo de se ter um melhor ajuste no processo de combinação
dos classificadores envolvidos.
Quanto à forma de treinamento adotada para gerar o sistema de classificação,
foram utilizadas o modelo tradicional, denominado não-hierárquico e apresentou-se
uma estratégia de construção do sistema de classificação hierárquica, onde, baseado
nas características dos classificadores individuais envolvidos, define-se uma
ordenação específica para o treinamento visando, principalmente, uma maior
eficiência computacional sem perda na qualidade de predição do sistema.
A escolha dos classificadores individuais para a geração do modelo hierárquico
é crucial para o bom funcionamento da estratégia. Optou-se por adotar modelos com
características complementares ao classificador SVM, tido como bastante eficiente. A
escolha recaiu nos conhecidos KNN e no clusterizador KMEANS, adaptado para
aprendizado supervisionado. Porém, a motivação para o uso do algoritmo KMEANS
não está somente em seu potencial para aprendizado supervisionado mas,
principalmente, no aproveitamento, de uma forma específica, dos resultados
provenientes do aprendizado não supervisionado. Baseia-se na utilização das
informações relativas aos centros dos clusters gerados, para complementar o
subconjunto de treinamento definido pelo procedimento hierárquico. Pode-se então,
categorizar o modelo de classificação hierárquico como sendo semi-supervisionado.
Experimentos numéricos em dados reais e sintéticos foram desenvolvidos
visando verificar o desempenho das diversas estratégias para sistemas de múltiplos
93
classificadores desenvolvidas. Tais experimentos evidenciaram que, em relação aos
modelos de combinação utilizados, a votação majoritária simétrica mostrou-se a mais
eficiente de uma forma geral. Porém, a técnica de combinação assimétrica específica
para sistemas restritos também mostrou-se efetiva em relação a votação majoritária
padrão.
Os testes também mostraram um desempenho de acordo com o esperado em
relação ao modelo hierárquico. O esforço computacional foi reduzido drasticamente e,
em geral, sem perda no nível da predição alcançada, se comparado ao modelo não-
hierárquico. O aproveitamento do algoritmo KMEANS como técnica de aprendizado
supervisionado e não supervisionado mostrou-se essencial para obtenção destes
resultados.
Expectativas confirmadas na utilização de sistemas de múltiplos
classificadores, bem como para as contribuições apresentadas, vem indicar que tais
estratégias são viáveis e devem ser aplicadas na prática. Porém, espera-se que novos
aprimoramentos teóricos e experimentais evidenciem ainda mais a importância destes
sistemas em aprendizado supervisionado.
Considera-se importante o desenvolvimento de estudos mais específicos em
relação a outras estratégias para escolha dos dados de treinamento do classificador
que finaliza o procedimento na classificação hierárquica, no caso, o SVM. Acredita-se
que, dependendo do banco analisado, podem-se ter métodos mais eficientes para a
escolha de tais dados.
94
Pretende-se ainda, efetuar a extensão dos algoritmos apresentados para
problemas multi-classes. Porém, não se espera grandes variações em relação aos
níveis de resultados obtidos na classificação binária.
Constatada a importância da votação majoritária com peso, novos estudos
estão previstos visando o desenvolvimento de uma estratégia local para determinação
dos pesos e não baseada no comportamento global do classificador base.
Aplicações em casos mais complexos dos sistemas de múltiplo classificadores
desenvolvidos como, por exemplo, bancos desbalanceados também devem ser
avaliados.
95
Referências:
[1] BAUER E., KOHAVI R., An empirical comparison of voting classification
algorithms: bagging, boosting, and variants. Machine Learning, vv, 1-38, Kluwer
Academic Publishers, Boston. (1998)
[2] BLUM A., MITCHELL T., Combining labeled and unlabeled data with co-
training. In Proceedings of the Conference on Computational Learning Theory.
ACM Press, New York, NY, (1998).
[3] BOLAND P. J., Majority system and the Condorcet jury theorem. Statistician,
vol. 38, no. 3, pp 181-189, (1989).
[4] BREIMAN L., Bagging predictors. Machine Learning, vol. 24, no. 2, pp 123-140
(1996).
[5] BREIMAN L., Arcing classifiers. Annals of Statistics, vol. 26, no. 3, pp. 801-849,
(1998).
[6] BREIMAN L., Random forests. Machine Learning, vol. 45, no. 1, pp. 5–32, Oct.
(2001).
[7] BREIMAN L., Pasting small votes for classification in large databases and on-
line. Machine Learning, vol. 36, pp. 85–103, (1999).
[8] BOSER B. E., GUYON I. M., VAPNIK V. N., A training algorithm for optimal
margin classifiers. In D. Haussler, editor, 5th Annual ACM Workshop on COLT,
Pittsburgh, PA, ACM Press, (1992).
[9] BURGES C.J.C, A tutorial on support vectors machine for pattern recognition.
Data Mining Knowledge Discovery 2, pp. 121-167, Kluwer Academic Publisher,
Boston, (1998).
[10] CARUANA R., MIZIL A. N., CREW G., KSIKES A., Ensemble from libraries of
96
models. Department of Computer Science, Proceedings of the 21
st
.
International Conference on Machine Learning, Banff, Canada (2004).
[11] CORTES C., VAPNIK V.N., Support-vector network. Machine Learning, 20,
(1995)
[12] CRISTIANINI N., SHAWE-TAYLOR J., An introduction to support vector
machines and other Kernel-based learning methods. Cambridge University
Press, (2000).
[13] GUNN S., Support vector machines for classification and regression. Faculty of
Engineering, Science and Mathematics School of Electronics and Computer
Science, (1998).
[14] DUDA R. O., HART P. E., STORK D. G. Pattern classification. 2 Ed. John
Wiley & Sons, Inc., New York, 2001.
[15] FREUND Y., SCHAPIRE R.E., Decision theoretic generalization of on-line
learning and an application to boosting. Journal of Computer and System
Sciences, vol. 55, no. 1, pp. 119-139, (1997).
[16] HANSEN L., SALAMON P., Neural networks ensembles. IEEE Trans. Pattern
Anal. March. Intell. 12 pp. 993-1001, (1990).
[17] HAYKIN S., Neural Networks: A comprehensive foundation. 2nd edition,
Prentice-Hall, (1999).
[18] HUA Z. , WANG Y., Xu X., ZHANG B., LIANG L., Predicting corporate
financial distress based on integration of support vector machine and logistic
regression. Expert Systems with Applications, vol. 33, pp. 434-440, (2007).
[19] HUANG Y.S., SUEN C.Y., Behavior knowledge space method for combination
of multiple classifiers. Proc. of IEEE Computer Vision and Pattern Recognition,
pp. 347-352, (1993).
[20] HUANG Y.S., SUEN C.Y., A method of combining multiple experts for
recognition of unconstrained handwritten numerals. IEEE Transactions on
97
Pattern Analysis and Machine Intelligence, vol. 17, no. 1, pp. 90-94, (1995).
[21] JEONG K., XU J., ERDOGMUS D., PRINCIPE C., A new classifier based on
information theoretic learning with unlabeled data. Neural Networks, vol. 18, pp.
719-726, (2005).
[22] JOACHIMS T., Transdutive inference for text classification using support
vectors machines. In Proceedings of ICML-99, 16
th
International Conference on
Machine Learning, pp. 200-209. Morgan Kaufmann Publishers, San Francisco,
CA, (1999).
[23] KIM H., PANG S., JE H., KIM D., BANG S. Y., Constructing support vector
machine ensemble. Pattern Recognition, vol.36, pp. 2757-2767, (2003).
[24] KOTSIANTIS S. B., PINTELAS P. E., Combining bagging and boosting.
International Journal of Computational Intelligence Vol. 1, no. 4, pp. 324-333,
(2004).
[25] MITCHELL T., Machine learning. McGraw Hill, (1997).
[26] NANNI l., LUMINI A., Ensemblator: an ensemble of classifiers for reliable
classification of biological data. Science Direct, Pattern Recognition Letters 28,
pp. 622-630, (2007).
[27] POLICAR R.,
Ensemble based systems in decision making.
IEEE Circuits and Systems Magazine, vol. 6, no. 3, pp. 21-45, (2006).
[28] ROSEN B., Ensemble learning using decorrelated neural networks. Connection
Science, vol. 8, no. 3, pp. 373-384, (1996).
[29] RUTA D., GABRYS B., Classifier selection for majority voting. Information
Fusion, vol. 6, pp 63-81, (2005).
[30] RUTA D., GABRYS B., A theoretical analysis of majority voting errors for
multiple classifier systems. Pattern Analysis and Applications 5 (4), pp. 333-
350, (2002).
[31] SCHAPIRE R.E., The strength of weak learn ability. Machine Learning , vol. 5,
98
no. 2, pp. 197-227, (1990).
[32] SCHAPIRE R.E, FREUND Y., BARTLLET P., LEE W.S., Boosting the margin:
a new explanation for the effectiveness of voting methods. Annals of Statistics,
vol. 26, no. 5, pp. 1651-1686, (1998).
[33] SHAPLEY L., GROFMAN, B., Optimizing group judgmental accuracy in the
presence of independencies. Public Choice(historical Archive), vol. 43, no. 3,
pp. 329-343, (1984).
[34] SEMOLINI R., Support vector machines, inferência transdutiva e o problema
de classificação. Dissertação Mestrado, Universidade Estadual de Campinas,
(2002).
[35] VAPNIK, V.N., CHERVONENKIS, A., On the uniform convergence of relative
frequencies of events to their probabilities. Theoretical Probability and Its
Applications, vol. 17, pp. 264-280, (1971).
[36] VAPNIK V.N., The nature of statistical learning theory. Springer, (1995).
[37] VAPNIK V. N., Statistical learning theory. John Wiley and Sons, New York,
(1998).
[38] WEBB A.R., Statistical pattern recognition. Second Edition, John Wiley & Sons,
(2002).
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
