UNIVERSIDADE FEDERAL DE PERNAMBUCO
CENTRO DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
Tese de Doutorado
Agrupamento de Dados Simbólicos Intervalares
usando funções de Kernel
Anderson Fabiano B. F. da Costa
Recife - Pernambuco - Brasil
Agosto de 2011
UNIVERSIDADE FEDERAL DE PERNAMBUCO
CENTRO DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
Anderson Fabiano Batista Ferreira da Costa
Agrupamento de Dados Simbólicos Intervalares usando
funções de
Kernel
Tese apresentada à Coordenação do Programa de Pós-Graduação em
Ciência da Computação do Centro de Informática Universidade Federal de Pernambuco, em cumprimento às exigências do Programa de
Doutorado em Ciência da Computação.
Renata Souza, Dra.
Orientadora
Recife - Pernambuco - Brasil
Agosto de 2011
iv
Catalogação na fonte
Bibliotecária Jane Souto Maior, CRB4-571
Costa, Anderson Fabiano Batista Ferreira da
Agrupamento de dados simbólicos intervalares usando funções de Kenel /
Anderson Fabiano Batista Ferreira da Costa - Recife: O Autor, 2011.
xiv, 107 folhas: Il., fig., tab.
Orientador: Renata Maria Cardoso Rodrigues de Souza.
Tese (doutorado) - Universidade Federal de Pernambuco. CIn, Ciência da
Computação, 2011.
Inclui bibliografia e apêndice.
1. Ciência da Computação. 2 Inteligência Computacional. 3. Análise de dados
simbólicos. I. Souza, Renata Maria Cardoso Rodrigues de (orientadora). II. Título.
004
CDD (22. ed.)
MEI2011 – 187
A Deus por seu el apoio, à minha esposa Maria,
à meus pais Luiz e Valdete e meus irmãos Alysson,
Alessandro, Arllington e Juninho, DEDICO.
AGRADECIMENTOS
Primeiramente a Deus, por todos os propósitos que tem reservado para minha vida.
À minha esposa Maria, pelo seu incentivo, compreensão, companheirismo e carinho, sem
os quais as diculdades encontradas no decorrer deste trabalho não teriam sido superadas.
À minha mãe Valdete e aos meus irmãos Alysson, Alessandro, Arllington e Juninho pelos
ensinamentos de vida de grande valia que contribuíram sobremaneira na formação de meu
caráter.
Um agradecimento especial a professora Renata Souza pela orientação neste trabalho, bem
como pela participação valiosa em minha formação acadêmica e prossional. Agradeço a ela
pelos ensinamentos, conselhos e pela motivação mesmo nos momentos mais difíceis.
Aos membros da banca examinadora pelas contribuições e direcionamentos que vieram no
intuito de enriquecer este trabalho.
Aos meus companheiros de doutorado Marco, Jeísa, Reinaldo, Luciana, Carlos e Germano
pela nossa grande amizade e pelas discussões que resultaram em melhorias neste trabalho.
Ao meu parceiro de pesquisa e amigo Bruno Pimentel pela grande contribuição nas discussões técnicas e publicações durante o doutorado.
Aos amigos Daniella, César, Iana Daya, Petrônio, Mary Roberta, Alex, Ianna, José Antônio,
Luciana, Marcelo Siqueira e Kléber pelo grande incentivo e pela amizade cultivada entre nós.
A todos os outros amigos que contribuíram de maneira direta ou indireta para realização
deste trabalho.
RESUMO
A Análise de dados simbólicos (ADS) ou
Symbolic Data Analysis é uma nova abordagem na área
de descoberta automática de conhecimentos que visa desenvolver métodos para dados descritos
por variáveis onde existem conjuntos de categorias, intervalos ou distribuições de probabilidade.
O objetivo deste trabalho é estender métodos de agrupamento clássicos para dados simbólicos
intervalares baseados em funções de
kernel.
A aplicação de funções de
kernel
tem sido am-
plamente utilizado na classicação não supervisionada para dados clássicos e apresenta bons
resultados quando o conjunto apresenta uma disposição não-linear dos dados.
No entanto,
na literatura de ADS ainda necessita de métodos para identicar grupos não lineares.
hard )
trabalho engloba os paradigmas de agrupamento rígido (
agrupamentos utilizando as funções de
kernel
e difuso (
fuzzy ),
Este
e realiza tais
em um espaço de alta dimensão, conhecido como
espaço de características. Os métodos propostos neste trabalho consideram duas variantes comumente utilizadas em abordagens de
kernel, onde uma considera que o protótipo dos grupos
está denido neste espaço de características de alta dimensão e outra que considera o protótipo
denido no espaço original de entradas. Os métodos propostos são comparados com variações
do método K-médias existentes na literatura de ADS através de experimentos realizados com
dados simulados e dados reais intervalares fazendo uso do experimento Monte Carlo e métricas
estatísticas que evidenciam o desempenho superior dos métodos propostos.
Palavras-chave:
Análise de Dados Simbólicos, Agrupamento, Kernel, K-médias, Dados Sim-
bólicos do tipo Intervalo
ABSTRACT
Symbolic Data Analysis (SDA) is a new domain in the area of knowledge discovery that aims
to provide suitable methods for data described through multi-valued variables, where there are
sets of categories, intervals, or weight (probability) distributions. The objective of this work
is to extend classical clustering methods for symbolic interval data based on kernel functions.
The application of kernel functions have been widely used in unsupervised classication for data
classics and gives good results when the data set is presented in non-linear shapes. However,
the literature still needs ADS methods for identifying non-linear groups. This work includes
the hard and fuzzy clustering paradigms, and performs them using the kernel functions in a
high dimensional space, called feature space. The methods proposed in this paper considers two
approaches commonly used in kernel methods, where one, clustering in feature space, is made
by mapping each pattern using the non-linear function and then computing centroids in feature
space and another one look for centroids in input space. The proposed methods are compared
with K-means adaptive methods existing literature ADS through experiments with simulated
data and real data interval of the experiment using Monte Carlo and statistical metrics that
show a better performance of the proposed methods.
Keywords:
Symbolic Data Analysis, Clustering, Kernel, K-means, Interval data, Non-linear.
SUMÁRIO
Capítulo 1 Introdução
3
1.1
Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2
Organização da Tese
8
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Capítulo 2 Fundamentação Teórica
2.1
2.2
10
Análise de Agrupamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.1
Medidas de Similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.1.2
Métodos para Agrupamento de Dados
. . . . . . . . . . . . . . . . . . .
14
2.1.3
K-médias e suas extensões . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.1.3.1
K-médias
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.1.3.2
c-médias Difuso . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.1.3.3
Kernel K-médias
. . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.1.3.4
Kernel Difuso c-médias . . . . . . . . . . . . . . . . . . . . . . .
23
Análise de Agrupamento para Dados Simbólicos . . . . . . . . . . . . . . . . . .
23
2.2.1
Tabela de Dados Simbólicos
24
2.2.2
Tipos de Variáveis Simbólicas
2.2.3
Métodos para Agrupamento de Dados Simbólicos
. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
27
. . . . . . . . . . . . .
28
2.2.3.1
Métodos Hierárquicos
. . . . . . . . . . . . . . . . . . . . . . .
29
2.2.3.2
Métodos Particionais . . . . . . . . . . . . . . . . . . . . . . . .
30
Capítulo 3 Métodos de Agrupamento baseados em funções Kernel para Dados
Simbólicos Intervalares
36
Sumário
x
Kernel
3.1
Funções de
3.2
Métodos baseados em
3.3
para Intervalos . . . . . . . . . . . . . . . . . . . . . . . . . .
kernel
para particionamento no espaço de características .
39
3.2.1
Método K-médias (MKM-EC) . . . . . . . . . . . . . . . . . . . . . . . .
40
3.2.2
Método c-médias difuso (McM-EC) . . . . . . . . . . . . . . . . . . . . .
41
Métodos baseados em
Kernel
para particionamento no espaço de entrada . . . .
43
3.3.1
Método K-médias (MKM-EE) . . . . . . . . . . . . . . . . . . . . . . . .
44
3.3.2
Método c-médias difuso (McM-EE)
47
. . . . . . . . . . . . . . . . . . . . .
Capítulo 4 Apresentação e Análise dos Resultados
4.1
37
52
Cálculo do Índice de Validação . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.1.1
Índice Corrigido de Rand (CR)
. . . . . . . . . . . . . . . . . . . . . . .
53
4.1.2
Índice de Davies e Bouldin (DB)
. . . . . . . . . . . . . . . . . . . . . .
54
4.2
Considerações sobre o Kernel Gaussiano
. . . . . . . . . . . . . . . . . . . . . .
54
4.3
Experimentos e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
4.3.1
56
Conjunto de Dados Sintéticos
4.3.1.1
Análise dos resultados para as funções de
componentes
4.3.1.2
. . . . . . . . . . . . . . . . . . . . . . . .
xo . . . . . . . . . . .
63
Resultados dos métodos de agrupamento considerando o parâmetro
sigma
xo e calculado
. . . . . . . . . . . . . . . . . . . . . . .
68
Resultados para os métodos de agrupamento com abordagem
difusa (
4.3.2
61
Resultados dos métodos de agrupamento com abordagem rígida
hard ) considerando o parâmetro sigma
4.3.1.4
de uma e duas
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
(
4.3.1.3
kernel
fuzzy )
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Conjunto de Dados Reais do Tipo Intervalo
72
. . . . . . . . . . . . . . . .
75
4.3.2.1
Conjunto de Dados: Agaricus . . . . . . . . . . . . . . . . . . .
75
4.3.2.2
Conjunto de Dados: Fluxos de Água
. . . . . . . . . . . . . . .
77
4.3.2.3
Conjunto de Dados: Temperatura das Cidades . . . . . . . . . .
79
4.3.2.4
Conjunto de Dados: Carros
82
. . . . . . . . . . . . . . . . . . . .
Sumário
xi
4.3.2.5
Conjunto de Dados: Peixes
. . . . . . . . . . . . . . . . . . . .
Capítulo 5 Considerações Finais e Trabalhos Futuros
5.1
Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
86
88
Referências Bibliográcas
90
Apêndice A Resultados Complementares
99
Apêndice B Testes de Hipóteses
103
LISTA DE FIGURAS
1.1
Conjunto de Dados não linear descrito por duas variáveis intervalares
. . . . . .
7
1.2
Conjunto de Dados não linear descrito por três variáveis intervalares . . . . . . .
7
2.1
Mapeamento do espaço de entradas para o espaço de características
4.1
Conjunto de Dados 1 do tipo Intervalo com classes de tamanho e forma diferentes 58
4.2
Conjunto de Dados 2 do tipo Intervalo com quatro classes
4.3
Conjunto de Dados 3 do tipo Intervalo com três classes dispostos de maneira não
. . . . . . .
. . . . . . . . . . . .
20
59
linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
4.4
Conjunto de Dados 4 do tipo Intervalo com quatro classes
. . . . . . . . . . . .
60
4.5
Conjunto de Dados 5 do tipo Intervalo com quatro classes
. . . . . . . . . . . .
60
4.6
DB
Kernel
x sigma (σ ) para conjunto de dados 1 utilizando método MKM-EC .
61
4.7
DB
Kernel
x sigma (σ ) para conjunto de dados 2 utilizando método MKM-EC .
62
4.8
DB
Kernel
x sigma (σ ) para conjunto de dados 3 utilizando método MKM-EC .
62
4.9
DB
Kernel
x sigma (σ ) para conjunto de dados 4 utilizando método MKM-EC .
62
4.10 DB
Kernel
x sigma (σ ) para conjunto de dados 5 utilizando método MKM-EC .
63
4.11 Conjunto de Dados 2 com as variações de intervalo. . . . . . . . . . . . . . . . .
65
Kernel
x sigma (σ ) para conjunto de dados 1 utilizando método MKM-EC .
69
4.13 Família dos Cogumelos Agaricus . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
4.14 Conjunto de dados: Temperatura das cidades
81
4.12 DB
. . . . . . . . . . . . . . . . . . .
LISTA DE TABELAS
Kernel. .
2.1
Exemplos de Funções de
. . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
Tabela com dados clássicos (BILLARD; DIDAY, 2006)
. . . . . . . . . . . . . .
25
2.3
Descrição dos dados da Tabela 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.4
Tabela de Dados Simbólicos (Descrições dos conceitos
4.1
Resultado do Índice CR para os métodos de agrupamento baseado em
wu )
. . . . . . . . . . . .
Resultado do Índice CR para os métodos de agrupamento baseado em
Resultado do Índice CR para os métodos de agrupamento baseado em
Resultado do Índice CR para os métodos de agrupamento baseado em
Resultado do Índice CR para os métodos de agrupamento baseado em
Resultado do Índice CR para os métodos de agrupamento baseado em
Resultado do Índice CR para os métodos de agrupamento baseado em
Resultado do Índice CR para os métodos de agrupamento baseado em
70
Kernel
para abordagem DBSig: Conjunto de Dados 4 com 2 classes. . . . . . . . . . . .
4.8
67
Kernel
para abordagem DBSig: Conjunto de Dados 3 com 3 classes. . . . . . . . . . . .
4.7
67
Kernel
(rígido) e métodos adaptativos (a direita): Conjunto de Dados 5 com 2 classes. .
4.6
66
Kernel
(rígido) e métodos adaptativos (a direita): Conjunto de Dados 4 com 2 classes. .
4.5
64
Kernel
(rígido) e métodos adaptativos (a direita): Conjunto de Dados 3 com 3 classes. .
4.4
64
Kernel
(rígido) e métodos adaptativos (a direita): Conjunto de Dados 2 com 4 classes. .
4.3
26
Kernel
(rígido) e métodos adaptativos (a direita): Conjunto de Dados 1 com 4 classes. .
4.2
21
70
Kernel
(rígido): Conjunto de Dados 2 com 4 classes. . . . . . . . . . . . . . . . . . . . .
71
LISTA DE TABELAS
4.9
xiv
Resultado do Índice CR para os métodos de agrupamento baseado em
Kernel
(rígido): Conjunto de Dados 3 com 3 classes. . . . . . . . . . . . . . . . . . . . .
4.10 Resultado do Índice CR para os métodos de agrupamento baseado em
71
Kernel
(rígido): Conjunto de Dados 5 com 2 classes. . . . . . . . . . . . . . . . . . . . .
71
4.11 Resultado do Índice CR para os métodos de agrupamento difuso baseado em
Kernel
e o método c-médias difuso adaptativo (a direita): Conjunto de Dados 2
com 4 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
4.12 Resultado do Índice CR para os métodos de agrupamento difuso baseado em
Kernel
e o método c-médias difuso adaptativo (a direita): Conjunto de Dados 3
com 3 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
4.13 Resultado do Índice CR para os métodos de agrupamento difuso baseado em
Kernel
e o método c-médias difuso adaptativo (a direita): Conjunto de Dados 4
com 2 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
4.14 Resultado do Índice CR para os métodos de agrupamento difuso baseado em
Kernel
e o método c-médias difuso adaptativo (a direita): Conjunto de Dados 5
com 2 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.15 Cogumelos da família
Agaricus
. . . . . . . . . . . . . . . . . . . . . . . . . . .
74
76
4.16 Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados
Agaricus.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
4.17 Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de
Dados Agaricus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.18 Fluxo de Água da cidade de Barcelona
. . . . . . . . . . . . . . . . . . . . . . .
77
78
4.19 Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados
Fluxos de Água. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
4.20 Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de
Dados Fluxos de Água. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
4.21 Valores mínimo e máximo de temperatura de 37 cidades (em graus centígrado) .
81
LISTA DE TABELAS
xv
4.22 Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados
Temperatura das Cidades.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
4.23 Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de
Dados Temperatura das Cidades.
. . . . . . . . . . . . . . . . . . . . . . . . . .
4.24 Conjunto de Dados Carros com 8 variáveis do tipo intervalo
. . . . . . . . . . .
82
82
4.25 Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados
Carros. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
4.26 Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de
Dados Carros. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.27 Conjunto de dados de Peixes descritos por 13 variáveis intervalares.
. . . . . . .
83
84
4.28 Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados
Peixes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
4.29 Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de
Dados Peixes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1
Resultado complementares do Índice DB referente ao gráco da Figura 4.6: Conj.
de Dados 1.
A.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Resultado complementares do Índice DB referente ao gráco da Figura 4.9: Conj.
de Dados 4.
A.5
99
Resultado complementares do Índice DB referente ao gráco da Figura 4.8: Conj.
de Dados 3.
A.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resultado complementares do Índice DB referente ao gráco da Figura 4.7: Conj.
de Dados 2.
A.3
84
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Resultado complementares do Índice DB referente ao gráco da Figura 4.10:
Conj. de Dados 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
A.6
Partições geradas para o conjunto de dados Temperatura das cidades. . . . . . . 101
A.7
Partições geradas para o conjunto de dados Agaricus
A.8
Partições geradas para o conjunto de dados Carros.
. . . . . . . . . . . . . . . 101
. . . . . . . . . . . . . . . . 102
LISTA DE TABELAS
1
A.9
Partições geradas para o conjunto de dados Peixes.
B.1
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.1
B.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.8
B.9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.7
B.8
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.6
B.7
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.5
B.6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.4
B.5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.3
B.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.2
B.3
. . . . . . . . . . . . . . . . 102
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
B.10 Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
B.11 Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
B.12 Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.12
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
B.13 Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Lista de Tabelas
2
B.14 Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela
4.14
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
CAPÍTULO 1
INTRODUÇÃO
Nos últimos anos com o crescente avanço nas tecnologias de armazenamento de dados, na velocidade e capacidade dos sistemas, e uma melhoria considerável nos sistemas de gerenciamento
de banco de dados, tem possibilitado a geração de bases de dados a partir desta grande quantidade de dados. Estima-se que a cada 20 meses as empresas no mundo dobrem o volume de
dados acumulados em seus computadores e dispositivos de armazenamento. As bases de dados
nas empresas da administração pública ou da iniciativa privada são praticamente onipresentes
e aumentam de volume em um ritmo elevado (DIDAY; NOIRHOMME-FRAITURE, 2008).
A mineração desses dados no intuito de extrair conhecimento útil a serem empregados na
tomada de decisões tornou-se um fator ainda mais relevante.
No entanto, em virtude desse
crescente volume de dados, os métodos tradicionais de análise de dados têm se tornado inapropriados, pois não conseguem analisar o conteúdo das informações com a nalidade de
obter conhecimentos importantes. A necessidade de transformação desse volume de dados armazenados em informações signicativas é bastante clara, porém sua análise ainda é lenta e
dispendiosa.
Em aplicações de tomada de decisão é frequentemente necessário levar em consideração
a imprecisão, incerteza ou variabilidade presente nos dados para representar a informação
disponível. Considere, por exemplo, um paciente que tem sua pressão arterial acompanhada
pelo seu médico. Um paciente saudável pode ter o valor de sua pressão oscilando no intervalo
[115, 118].
Um outro paciente, também saudável, poderia ter sua pressão oscilando no intervalo
[114, 116].
Uma análise clássica utilizando o ponto médio dos intervalos perderia a informação
sobre a variação de pressão no estado saudável para cada paciente.
Em outra situação, uma companhia de seguros de saúde possui um banco de dados com
milhares de informações a respeito das consultas de seus segurados, onde cada entrada desse
banco armazena: o tipo de especialista consultado, o local do exame, os exames realizados, os
4
medicamentos solicitados, etc. Entretanto, a seguradora pode não estar interessada em uma
consulta em especial, mas em todas as consultas realizadas por um dado cliente. Neste caso,
todas as consultas realizadas pelo cliente podem ser agregadas, produzindo dados simbólicos.
Assim, seria extremamente atípico que o peso (kg) desse determinado cliente, em todas as suas
consultas, fosse igual a
[68kg, 73kg].
70kg .
No entanto, poderíamos observar que seu peso oscilou no intervalo
Em um outro cenário, poderíamos supor que um banco não estaria interessado no
valor monetário na conta corrente de um certo indivíduo, mas na variação desse valor ao longo
de um ano.
Observe que, nesses casos, a representação clássica de dados não é capaz de representar essas
nuances e, por isso, outros tipos de representação de dados são necessárias. A representação
de conceitos ou fenômenos do mundo real a partir de dados pontuais que representam valores
únicos, pode levar à perda de informação. Tradicionalmente, vetores de valores reais têm sido
usados para modelar características em um domínio especíco.
do mundo real sejam descritas de forma tabular considerando
n
Fazendo com que situações
indivíduos descritos por
m
variáveis. Diante desse contexto, é necessário um novo tipo de análise de dados que nos permita
representar a complexidade presente na realidade, permitindo a representação das variações
internas e incertezas presentes na estrutura dos dados.
Os dados simbólicos são adequados para lidar com dados imprecisos, resultantes de medidas
com imprecisão relativa ou estimadas por intervalos de conança, limites de um conjunto de
possíveis valores de um item ou variação da extensão de uma variável através do tempo ou
através da redução de conjuntos de dados em um número reduzido de pequenos grupos de
informação. Esses tipos de dados são objetos de estudo, principalmente, da Análise de Dados
Simbólicos (ADS) (BOCK; DIDAY, 2000).
Na análise de dados simbólicos (DIDAY; NOIRHOMME-FRAITURE, 2008) o conhecimento extraído a partir dos conjunto de dados, é representado por dados mais complexos,
chamados de dados simbólicos, uma vez que permitem levar em conta variação e/ou incerteza
presente nos dados.
Os dados simbólicos são descritos por variáveis multivaloradas que po-
dem não somente assumir um valor numérico ou categórico, mas um conjunto de categorias,
intervalos ou distribuições de pesos. A ADS fornece não somente os instrumentos adequados
para representar e analisar dados agregados, como também a possibilidade de modelar e extrair
1.1 Motivação
5
conceitos presentes no dados.
A análise de dados simbólicos tem sido uma promissora abordagem para aplicações em
tratamento de imagens, comércio eletrônico, ciências biológicas, perl de consumidores, etc
(DIDAY; NOIRHOMME-FRAITURE, 2008). A intenção da ADS é estender os métodos tradicionais com dados clássicos para métodos com dados simbólicos através da generalização ou
desenvolvimento de métodos exploratórios, estatísticos e representações grácas para esses dados (BOCK; DIDAY, 2000). Esta Tese está inserida neste contexto de adaptação de técnicas
clássicas para a Análise de Dados Simbólicos.
1.1
MOTIVAÇÃO
A sociedade humana desde os primórdios de sua existência fez uso de algum processo de
classicação ao longo da história de seu desenvolvimento (ANDERBERG, 1973).
Com isso,
é bastante comum que em um conjunto de dados de grande escala surja a necessidade de
classicá-los ou agrupá-los dentro de um conjunto de categorias. No intuito de aprender sobre um novo objeto ou compreender um novo fenômeno, as pessoas sempre tentam procurar
características que descrevem estes elementos. Em seguida, comparam com outros objetos ou
fenômenos conhecidos, baseados em alguma similaridade ou proximidade entre eles, seguindo
certos padrões ou regras.
Assim, o agrupamento de dados tornou-se um assunto muito im-
clustering )
portante e a análise de agrupamento (
tem sido utilizada em diversos domínios de
aplicações como mineração de dados, reconhecimento de padrões, bioinformática e assim por
diante (JAIN; MURTY; FLYNN, 1999) (JAIN, 2010).
A análise de agrupamento é uma técnica exploratória multivariada que se propõe a encontrar classes homogêneas a partir de um conjunto de objetos (indivíduos) (JAIN; MURTY;
FLYNN, 1999). Um dos mais populares algoritmos de agrupamento é o K-Médias, no qual grupos homogêneos são identicados, minimizando o erro do agrupamento denido como a soma
das distâncias euclidianas quadradas entre cada conjunto de dados pontuais e os correspondentes centros dos aglomerados.
Diversas extensões do algoritmo K-médias foram propostas
com diferentes enfoques (KAUFMAN; ROUSSEEUW, 2005) (HONG; KWONG, 2009) (JAIN,
2010). A simplicidade desses algoritmos de agrupamento é uma característica importante, assim
1.1 Motivação
6
como a grande variedade de problemas de particionamento não-supervisionado para os quais
são usados (JAIN, 2010).
Um dos grandes desaos em análise de agrupamento está em realizar a separação das
classes quando os dados estão distribuídos de maneira arbitrária. De um modo geral, quando
isto ocorre, costuma-se dizer que os dados são não-linearmente separáveis. O método K-médias
apresenta resultados insatisfatórios neste tipo de cenário, o que motivou a evolução de outros
métodos de agrupamento que apresentam maior eciência na separação destes tipos de grupos.
Girolami (GIROLAMI, 2002) desenvolveu um algoritmo capaz de produzir separações
não lineares entre grupos, transformando o espaço de entradas em um espaço de alta dimensão
e então executar o agrupamento neste novo espaço; este mapeamento para o novo espaço de
alta dimensão é realizado através de funções de
Kernel.
Este agrupamento baseado em
ganhou grande importância e diversos trabalhos com paradigmas rígido (
Kernel
hard ) e difuso (fuzzy )
têm sido introduzidos com esse propósito como os encontrados em (ZANG D. Q. E CHEN,
2003) (TAN; CHEN; ZHANG, 2004) (DHILLON; GUAN; KULIS, 2004) (KIM et al., 2005)
(AWAN; SAP, 2006) (FILIPPONE et al., 2008) (TZORTZIS; LIKAS, 2009).
Kernel
O métodos de
também têm sido aplicados em outras áreas como para estimação de densidade e análise
discriminante (GHOSH, 2008).
Com relação aos métodos de agrupamento para dados simbólicos, a ADS tem fornecido
técnicas para o agrupamento de dados simbólicos do tipo intervalo, principalmente no caso dos
algoritmos de agrupamento dinâmicos com distâncias adaptativas, que são capazes de reconhecer grupos de formas e tamanhos diferentes. Estes métodos de agrupamento utilizam distâncias
que mudam a cada iteração, e podem ser a mesma para todos os grupos ou não (distância
adaptativa única ou por classe). De Carvalho e Lechevalier (CARVALHO; LECHEVALLIER,
2009b) apresentaram métodos de agrupamento para os dados simbólicos do tipo intervalo para
distância adaptativa única com as medidas
City-Block e Hausdor.
Além disso, De Carvalho e
Lechevalier (CARVALHO; LECHEVALLIER, 2009a) propuseram métodos de particionamento
dinâmico para os intervalos com base em distâncias adaptativas quadráticas.
Mais recen-
temente, em (CARVALHO; SOUZA, 2010), foram propostos métodos de reconhecimento de
padrões não supervisionados para dados simbólicos mistos com base na metodologia de agrupamento dinâmico com distância adaptativa única e por classe.
1.1 Motivação
7
Figura 1.1.
Figura 1.2.
Conjunto de Dados não linear descrito por duas variáveis intervalares
Conjunto de Dados não linear descrito por três variáveis intervalares
Embora estes recentes trabalhos da literatura da análise de dados simbólicos indique avanços
nos métodos de agrupamento para intervalo, os métodos de agrupamento para dados simbólicos
existentes não são capazes de separar da maneira desejada grupos não lineares no espaço de
entrada.
Por exemplo, a Figura 1.1 exibe um conjunto de dados descrito por duas variáveis
intervalares. A Figura 1.2 exibe um conjunto de dados com espécies de uma família de cogumelos
chamadas
agaricus
e cada espécie é descrita por três atributos do tipo intervalo: largura do
píleo, espessura da estipe e largura dos esporos. Nota-se que em ambas as guras estão presentes
grupos de natureza não linear no espaço de entrada.
Para agrupar os conjuntos de dados representados pelas guras 1.1 e 1.2, são necessários
métodos com habilidade de encontrar hiperplanos capazes de separar esses dados. O uso de
Kernel
permite realizar tal separação através do mapeamento implícito do espaço de dados
originais em um espaço de alta dimensionalidade denominado espaço de características. Como
1.2 Organização da Tese
8
mencionado no parágrafo anterior, mesmo com os recentes avanços nos métodos de agrupamento
para dados simbólicos, estes ainda apresentam limitações quando se trata de separação de
grupos não lineares no espaço de entrada. Por esta razão, o principal objetivo deste trabalho é
contribuir com a literatura de ADS através da extensão de métodos de agrupamento para dados
simbólicos intervalares através do uso de funções
Kernel.
Especicamente esta tese apresentará
duas versões do método K-médias e do método difuso c-médias aplicadas a dados simbólicos
intervalares e fazendo uso de funções de
1.2
Kernel
para identicação de grupos não lineares.
ORGANIZAÇÃO DA TESE
Além deste capítulo, nesta tese é apresentada em mais quatro capítulos listados a seguir.
Capítulo 2
Este capítulo se divide em duas grandes seções sobre análise de agrupamento para dados
clássicos e para dados simbólicos.
Na primeira seção são apresentadas algumas denições e
algoritmos de agrupamento com uma maior ênfase nas extensões do método K-médias.
A
seção seguinte de análise de agrupamento para dados simbólicos apresenta a tabela de dados
simbólicos, alguns tipos de dados simbólicos existentes e uma breve descrição dos métodos de
agrupamento (particionais e hierárquico) da análise de dados simbólicos.
Capítulo 3
Neste capítulo são introduzidos os métodos de agrupamento para o particionamento de
conjunto de dados simbólicos do tipo intervalo como extensões do método K-médias utilizando
funções de
Kernel.
Capítulo 4
Este capítulo apresenta os resultados dos experimento do processo de agrupamento fornecidos pelos métodos propostos utilizando conjuntos de dados sintéticos e reais para intervalos.
1.2 Organização da Tese
9
Capítulo 5
Neste capítulo, são apresentadas as considerações nais desta tese, bem como os futuros
trabalhos que poderão ser realizados a partir das ideias aqui apresentadas.
CAPÍTULO 2
FUNDAMENTAÇÃO TEÓRICA
Neste capítulo é realizada uma revisão de análise de agrupamento para dados clássicos onde
são apresentados conceitos relacionados ao contexto deste trabalho e métodos de agrupamento,
e em seguida é apresentada brevemente a análise de agrupamento para dados simbólicos.
2.1
ANÁLISE DE AGRUPAMENTO
Uma das mais básicas habilidades dos seres vivos envolve o agrupamento de objetos similares
para produzir uma classicação. Desde os primórdios do seu surgimento, o homem, por exemplo,
obteve habilidades para identicar que muitos objetos possuíam certas propriedades, tais como
a usabilidade de ferramentas, a ferocidade de animais, entre outros. Desta forma, surge a ideia
de agrupamento (
clustering ), no qual os objetos são reunidos de modo que a semelhança entre
eles é maior do que qualquer outra classe existente.
A análise de agrupamento visa agrupar elementos de dados baseando-se na similaridade
entre eles.
Os grupos são determinados de forma a obter-se homogeneidade dentro de cada
grupo e heterogeneidade entre eles. A necessidade de classicar elementos em grupos por suas
características está presente em várias áreas do conhecimento, como nas ciências biológicas,
ciências sociais e comportamentais, ciências da terra, medicina, informática, entre outras. O
resultado nal do estudo de classicação é normalmente uma partição de um conjunto de
objetos em classes disjuntas tal que existe uma similaridade entre objetos de uma mesma classe.
Dependendo do tipo de tratamento a ser realizado nos objetos pode resultar em diferentes visões
do processo de classicação (GORDON, 1999).
Denomina-se agrupamento, a classicação não supervisionada de padrões (observações, objetos, itens, pontos num espaço multidimensional ou vetores de atributos ou de medidas) em
grupos (
clusters ou classes).
É uma das técnicas utilizadas em análise exploratória de dados, na
2.1 Análise de Agrupamento
11
qual o analista tenta familiarizar-se com os dados e descobrir estruturas de padrões intrínsecos
aos dados.
É importante entender a diferença entre análise de agrupamento (classicação não supervisionada) e análise discriminante (classicação supervisionada). Na classicação supervisionada,
há o fornecimento dos padrões e seus rótulos; o problema é então rotular um novo padrão para
o qual o rótulo não foi informado. Tipicamente, os padrões rotulados são utilizados para aprender a descrição das classes (fase de treinamento) e esta informação aprendida, por sua vez, é
usada para rotular um novo padrão. No caso da classicação não supervisionada, como já mencionado, o problema é organizar em grupos um conjunto de padrões não rotulados de modo que
os grupos tenham um signicado relevante. Sob certo ponto de vista, rótulos estão presentes
no processo de agrupamento, cada grupo formado poderia ser entendido como um rótulo, mas
estes rótulos são obtidos a partir dos próprios dados.
O objetivo do uso de métodos de agrupamento é a obtenção de uma abstração de dados,
ou seja, uma representação simples e compacta de um conjunto de dados (JAIN; MURTY;
FLYNN, 1999). Tanto as máquinas quanto as pessoas se beneciam desta representação seja
no processamento eciente, seja na compreensão da estrutura nos dados. O agrupamento é um
processo subjetivo cuja solução possível reete o conhecimento que se tem sobre os dados. O
resultado deve atender a uma aplicação denida previamente (JAIN; MURTY; FLYNN, 1999).
É por esta razão que agrupar não é uma tarefa simples e não possui um algoritmo de uso
geral. As máquinas têm desempenho menor ou igual ao dos humanos quando se trata da análise
de conjuntos de dados com uma ou duas dimensões. Entretanto, os problemas reais frequentemente envolvem muitas dimensões, situação esta em que as máquinas conseguem acessar mais
ecientemente a estrutura embutida nos conjuntos de dados. Para revelar a estrutura característica dos diferentes conjuntos de dados, há grande número de métodos e estratégias como
apresentado em (JAIN; MURTY; FLYNN, 1999).
As metodologias de agrupamento recebem diversas nomenclaturas, terminologias e suposições nas diversas áreas em que encontram aplicação.
Em todas elas, os agrupamentos
possibilitam a exploração das inter-relações dos dados através da representação de sua estrutura conforme o método escolhido.
A observação destas representações quando possível, é
avaliada internamente, externamente ou de forma relativa em relação aos métodos utilizados e
2.1 Análise de Agrupamento
ao conhecimento
a priori.
12
A estrutura verdadeira dos dados se torna cada vez mais a acessível
quanto mais informações o especialista obtiver.
Seguindo a intuição comum aos humanos (CHEN et al., 2009), muitos métodos se baseiam
na similaridade para realizar a partição dos dados em grupos. Busca-se a melhor partição com
a nalidade de que a similaridade seja maior dentro e não entre os grupos. Há muitas medidas
que expressam a similaridade entre dois pontos (ou vetores de entrada) (CHEN et al., 2009),
sendo que a maioria é sensível à distribuição espacial dos dados e à faixa de valores encontrados
nos vetores de entrada. Por esse motivo, frequentemente os dados devem passar por algum tipo
de pré-processamento, genericamente denominado de normalização ou padronização, que, de
modo geral, consiste em alterar a faixa de valores em cada atributo. Além da padronização, há
a possibilidade de avaliar a semelhança entre as amostras utilizando medidas apropriadas para
o cálculo da distância de modo coerente com a diferença de magnitude e distribuições entre os
valores dos atributos, ou ainda, o tipo desses últimos.
2.1.1
Medidas de Similaridade
Os algoritmos de agrupamento de dados identicam a semelhança entre os objetos de um
conjunto e sob algum critério determinam em que grupo cada um destes deve ser alocado. Tal
semelhança é calculada através da medição de similaridade entre os objetos.
A similaridade representa que quanto mais próximo dois indivíduos, mais elevado é o valor
da medida de similaridade entre eles. Enquanto que na dissimilaridade, quanto mais próximos
dois indivíduos, menor é o valor da medida de dissimilaridade entre eles.
A cada objeto que se quer agrupar, geralmente é associado um vetor de
tencente ao espaço
este objeto.
<n
n
dimensões per-
onde cada dimensão representa uma das características que descrevem
Deste modo, as medidas de similaridade dos objetos são calculadas em função
destes vetores de características.
Em geral, os algoritmos de agrupamento operam com os dados organizados numa matriz
de dados
n
x
p,
conforme ilustrado a seguir:
2.1 Análise de Agrupamento
13

x11 · · · x1f · · · x1p
.
.
 ..
.
.
.
.
 .

x
·
·
·
x
 i1
if
 .
.
.
.
.
 ..
.
.
.
.
.
.
.
.
· · · xip
.
.
.
.
.
.







xn1 · · · xnf · · · nip
Esta matriz é a tabela dos dados de treinamento. Cada linha desta tabela representa as
coordenadas de um i-ésimo objeto. Cada coluna representa os valores de um atributo assumidos
por cada um dos
n
objetos.
Muitos algoritmos de agrupamento organizam os dados numa matriz de dissimilaridade,
onde o elemento da coluna
entre os objetos
i
e
j
e linha
i
da matriz é o número
d(i, j)
representando a distância
j.







Para que uma função
0
d(2, 1)
0
d(3, 1) d(3, 2)
.
.
.
.
.
.

0
.
.
.
d(n, 1) d(n, 2) · · · · · · 0






d seja uma distância é necessário e suciente que as seguintes condições
sejam satisfeitas, para quaisquer objetos
1.
d(i, j) ≥ 0
2.
d(i, i) = 0
3.
d(i, j) = d(j, i)
4.
d(i, j) ≥ d(i, k) + d(k, j)
i, j , k :
(simetria)
A propriedade (1) implica que todos os elementos da matriz de dissimilaridade são nãonegativos; a propriedade (2) implica que a diagonal da matriz de dissimilaridade é formada por
zeros. A propriedade (3), por sua vez, implica que a matriz de dissimilaridade é simétrica com
relação à diagonal. A propriedade (4) diz respeito a desigualdade triangular. Assim, qualquer
função que satisfaz às quatro propriedades acima é chamada de distância.
Uma das medidas mais utilizadas para o cálculo da similaridade entre os objetos é a Distância Euclidiana (JAIN; DUBES, 1988). A Distância Euclidiana é um caso particular da medida
2.1 Análise de Agrupamento
14
de Minkowski. A distância de Minkowski, para os objetos
xi
e
xj
com
N
dimensões é denida
por:
d(xi , xj ) = (
N
X
1
|xik − xjk |p ) p
(2.1)
k=1
E a Distância Euclidiana, onde
p=2
é denida por:
v
u N
uX
d(xi , xj ) = t (xik − xjk )2
(2.2)
k=1
Uma limitação apresentada pelo uso da distância Euclidiana, é a tendência de que as características que tenham valores elevados se tornem dominantes. Uma solução para este problema
consiste na normalização dos valores das características, fazendo com que a norma Euclidiana
de cada objeto
x
seja igual a 1.
Existem, na literatura, referências ao uso de outras medidas de similaridade ou distância
usadas no agrupamento de dados:
distância de Manhattan ou City-block, que é um outro
caso particular da distância de Minkowski, onde
p = 1
(KAUFMAN; ROUSSEEUW, 1990)
(BOLSHAKOVA; AZUAJE, 2002) (FILIPPONE et al., 2008), distância de Mahalanobis (JING
L.; HUANG, 2006), Medida Correlacional de Pearson ((KAUFMAN; ROUSSEEUW, 1990) e
Divergência de Bregman (BANERJEE et al., 2005), dentre outras medidas.
2.1.2
Métodos para Agrupamento de Dados
Os algoritmos de agrupamento de dados geralmente são classicados de acordo com a abordagem utilizada para a geração de grupos e a forma como são apresentados os resultados (JAIN;
MURTY; FLYNN, 1999) (TAN; STEINBACH; KUMAR, 2005). Existem muitos algoritmos de
agrupamento disponíveis na literatura. A escolha de um algoritmo depende tanto dos tipos de
dados disponíveis quanto da aplicação desejada. Se a análise de agrupamento for usada como
uma ferramenta para exploração de dados, vários algoritmos podem ser executadas sobre o
mesmo conjunto de dados a m de avaliar os diferentes resultados de cada algoritmo e desta
forma, comparando os resultados, descobrir que informações ocultas estão embutidas nos dados.
É importante salientar que não existe uma técnica universal de agrupamento que seja capaz
de identicar grupos em qualquer tipo de dados. Os conjuntos de dados apresentam diferentes
características que determinam o comportamento das diferentes técnicas.
Três aspectos são
2.1 Análise de Agrupamento
15
determinantes: o tamanho do conjunto de dados, o número de características que cada dado
possui e a natureza geométrica da sua separabilidade. As diferentes técnicas de agrupamento
devem considerar estes aspectos.
A classicação de algoritmos de agrupamento não é uma tarefa direta ou canônica. Diversos
trabalhos na literatura categorizam os algoritmos de agrupamento (JAIN; MURTY; FLYNN,
1999) (GORDON, 1999) (XU; WUNSCH D., 2005).
A divisão mais unanimamente aceita é
classicar os algoritmos em métodos em duas categorias principais:
hierárquicos e particionais
(XU; WUNSCH D., 2005).
Os métodos hierárquicos consistem em uma série de sucessivos agrupamentos ou sucessivas
divisões de elementos. A partição gerada por métodos hierárquicos pode ser representada por
um diagrama bidimensional denominado dendrograma.
Dendrogramas são estruturas seme-
lhantes às árvores, onde os grupos estão organizados em níveis. Um grupo localizado em um
nível superior contém grupos que estão no nível inferior imediato. O nível mais baixo de um
dendrograma, as folhas das árvore, corresponde aos objetos da coleção. O nível mais alto, a raiz
da árvore, corresponde à coleção completa. Os níveis intermediários correspondem aos grupos
formados e como estão relacionados. Se um dendrograma for cortado em um determinado nível,
eliminando-se os relacionamentos entre os grupos aninhados até a raiz, obtém-se um conjunto
de grupos particionados (TAN; STEINBACH; KUMAR, 2005).
Os métodos hierárquicos podem ser subdivididos em métodos aglomerativos e divisivos. Nos
métodos aglomerativos, cada objeto inicialmente corresponde a um grupo, nos passos seguintes,
os dois grupos mais próximos são combinados em um novo grupo, desta forma, o número de
agrupamentos será reduzido geralmente em uma unidade em cada passo. As técnicas pertencentes aos processos aglomerativos, têm como objetivo nal a redução dos dados originais a
um único agrupamento, incluindo todos os indivíduos (GORDON, 1999). Nos métodos divisivos, deve-se considerar inicialmente um grande agregado, contendo todas as observações. Nos
passos subsequentes, as observações mais distintas entre si, são separadas, formando agrupamentos menores. Repete-se esse procedimento até que cada observação por si própria constitua
um agrupamento (SOUZA, 2003).
Os métodos particionais organizam grupos disjuntos dos objetos do conjunto de dados,
sem criar relacionamentos entre os grupos, como são criados nos algoritmos hierárquicos. Na
2.1 Análise de Agrupamento
16
alocação dos objetos aos grupos, a vericação de todas as possíveis combinações é computacionalmente inviável e assim esse tipo de algoritmo geralmente busca soluções de forma iterativa
(BERKHIN, 2006).
Entre os métodos de agrupamento particionais, estão os métodos que utilizam o conceito
de protótipos de grupos, que são pontos no espaço dimensional dos dados que representam
o centro de cada um dos grupos.
(i)
Os protótipos podem ser representados de duas maneiras:
centroides, os protótipos podem assumir qualquer posição no espaço e,
(ii)
medoides, os
protótipos são, necessariamente, exemplos do conjunto de dados.
A principal ideia da maioria dos métodos particionais é escolher uma partição inicial dos
elementos e, em seguida, alterar os componentes dos grupos para se obter a melhor partição
(SOUZA, 2003). Comparado com os métodos hierárquicos, os métodos particionais são mais
rápidos porque é desnecessário o cálculo e o armazenamento das amostras, durante o processamento, da matriz de similaridade. Em geral, os métodos particionais diferem entre si pela
maneira que estabelecem a melhor partição.
Os métodos mais conhecidos são o método K-
médias (que emprega o conceito de centroides) e o método K-medoides.
Alguns autores estendem a classicação proposta por (JAIN; MURTY; FLYNN, 1999)
e (XU; WUNSCH D., 2005) incluindo, ao lado dos métodos hierárquicos e particionais, os
métodos baseados na densidade de objetos (HE et al., 2002) (BERKHIN, 2006), baseados em
teoria dos grafos (HARTUV; SHAMIR, 2000); Baseados em grades (WANG; YANG; MUNTZ,
1997); Baseados em redes neurais (KOHONEN, 1989); Baseados em
Kernel
(SCHOLKOPF;
SMOLA; MULLER, 1998) (BEN-HUR et al., 2001); Baseados em computação evolucionária
(KRISHNA; MURTY, 1999) e Agrupamentos Difusos (
fuzzy ) (BEZDEK, 1981).
Como este trabalho tem como foco variantes rígida e difusa do método K-médias, para um
melhor entendimento do leitor, a seguir são apresentados o método de agrupamento K-médias
e algumas de suas extensões.
2.1 Análise de Agrupamento
2.1.3
2.1.3.1
17
K-médias e suas extensões
K-médias
O método de particionamento mais conhecido e largamente utilizado é o algoritmo Kmédias (MACQUEEN, 1967), por dois motivos principais:
o primeiro é a sua facilidade de
implementação e o segundo é o seu baixo custo computacional, uma vez que a sua complexidade
é de ordem
O(nKl),
onde
n
é o número de objetos,
K
é o número de grupos e
l
é o número de
iterações (CHOUDHARI et al., 2005).
O algoritmo K-médias promove o particionamento de um conjunto de objetos, descritos por
X = {x1 , . . . , xn },
em
por um ponto central
K
yk ,
grupos disjuntos,
P = {C1 , . . . , CK }.
Cada grupo
k
é caracterizado
denominado protótipo ou centroide. Considerando que a medida de
similaridade utilizada é a distância Euclidiana, o algoritmo K-médias procura formar os grupos
de modo que a função objetivo
J
seja minimizada:
J(P ) =
K X
X
kxi − yk k2
(2.3)
k=1 i∈Ck
Pode ser demonstrado que o protótipo
yk que otimiza o valor da função J
de pontos é a média aritmética dos vetores que pertencem ao grupo
k.
para um conjunto
Assim o protótipo é
expresso por:
yk =
1 X
xi
nk i∈C
(2.4)
k
nk
é o número de pontos (ou objetos) do grupo
k.
O algoritmo K-médias apresenta algumas limitações, dentre elas, duas podem ser destacadas. A primeira decorre que as soluções encontradas, normalmente convergem para ótimos
locais, e mesmo após múltiplas execuções não se consegue obter resultados que sejam melhores,
o que o torna extremamente sensível à escolha inicial dos centroides. A segunda limitação é
que ele só apresenta boas soluções para conjunto de dados que sejam linearmente separáveis
(JAIN, 2010).
Para contornar a primeira limitação citada, várias estratégias foram propostas para a escolha dos objetos que serão os centroides iniciais. Em (CUI; POTOK, 2005) é proposto um
algoritmo híbrido que une as funcionalidades do K-médias e do algoritmo
Particle Swarm Opti-
2.1 Análise de Agrupamento
mization
18
(PSO) (KENNEDY; EBERHART, 1995). O algoritmo PSO realiza uma busca global
no espaço de soluções e esta abordagem híbrida é utilizada para encontrar os protótipos iniciais
para o algoritmo K-médias. Uma estratégia semelhante foi proposta por (ABRAHAM; DAS;
KONAR, 2006), onde o algoritmo híbrido reúne o algoritmo K-médias e o algoritmo
Evolution
Dierential
(DE) com o mesmo propósito de encontrar protótipos iniciais.
Com relação à segunda limitação, existem estratégias como o
Kernel
K-médias, algoritmos
de agrupamento espectral e algoritmos de particionamento de grafos (FILIPPONE et al., 2008).
O
Kernel
K-médias mapeia os dados originais em um espaço
<d
com um número maior de
dimensões, de forma que esta representação se torne linearmente separável (DHILLON; GUAN;
KULIS, 2004).
Alguns algoritmos espectrais usam o espectro da matriz de anidades para
realizar o agrupamento com o K-médias. O método
2.1.3.2
Kernel
K-médias é descrito mais adiante.
c-médias Difuso
fuzzy ) foram introduzidos em 1965 por Zadeh como uma nova maneira
Os conjuntos difusos (
de representar imprecisões do cotidiano (MITRA; PAL, 2005). Esta teoria fornece um conceito
ecaz para aproximar e descrever as características de um sistema que é muito complexo ou mal
denido para admitir análise matemática precisa. Admite-se que a forma com que o pensamento
humano trabalha com conceitos-chave não são apenas números, mas também uma aproximação
de conjuntos difusos.
Abordagens tradicionais de agrupamento geram partições, onde em uma partição, cada
indivíduo pertence a um e somente um grupo.
hard ).
agrupamento rígido (
Este tipo de agrupamento é conhecido como
Em muitas aplicações é desejável que a similaridade de um indiví-
duo seja compartilhada entre os grupos. Isso permitiria uma melhor descrição de situações em
que alguns indivíduos podem pertencer a grupos sobrepostos, ou no caso de alguns indivíduos
outliers ).
não pertencerem a nenhum grupo, uma vez que são valores discrepantes (
Agrupa-
mentos difusos permitem associar um indivíduo com todos os grupos através de um parâmetro
que representa o grau de pertinência do indivíduo ao grupo, em outras palavras, a noção difusa
possibilita expressar o tipo de situação em que o indivíduo compartilha similaridade com vários
grupos.
2.1 Análise de Agrupamento
19
Os algoritmos do tipo difuso estendem o conceito de associação de cada elemento em uma
classe, isto é, um indivíduo pode pertencer a diversas classes de acordo com uma função de
pertinência capaz de associar cada padrão a cada um dos grupos assumindo valores no intervalo
[0, 1].
Neste caso, cada classe é um conjunto nebuloso de todos os objetos. Cada elemento
possui um grau de pertinência para uma classe
relativos a essa elemento
x
tem que valer
k,
x
de forma que a soma de todos os graus
1.
O algoritmo de agrupamento difuso mais popular é o c-médias difuso (
Fuzzy c-means
-
FCM), onde os elementos mais afastados do centroide possuem um menor grau de pertinência, enquanto aqueles mais próximos ao centroide têm uma pertinência maior e o centroide é
obtido fazendo-se uma média ponderada do grau de todos os indivíduos para aquele grupo. O
desenvolvimento de funções de pertinência é o problema mais importante no contexto de agrupamento difuso; diferentes escolhas incluem aquelas baseadas em decomposição de similaridade
e centroides de grupos. Uma generalização do FCM foi proposta em (BEZDEK, 1981) através
de uma família de funções objetivo (critério). FCM pode ser tomado como uma generalização
do algoritmo ISODATA (XU; WUNSCH D., 2005).
Supondo que se tem um conjunto de objetos
em
c
grupos disjuntos,
P = {C1 , . . . , Cc }.
X = {x1 , x2 , . . . , xn }
e se deseja organizá-los
O algoritmo c-médias difuso (FCM) é um algoritmo
de agrupamento não hierárquico cujo principal objetivo é fornecer uma partição difusa de um
conjunto de indivíduos em
c
grupos. A função objetivo é denida como:
J(P ) =
c X
X
(uki )m kxi − yk k2
(2.5)
k=1 i∈Ck
onde
uki
é uma matriz de pertinência, ou simplesmente, a pertinência do objeto
Ck , m ∈ (1, +∞)
ao grupo
é um parâmetro que indica uma ponderação referente a pertinência dos
objetos. Pode ser demonstrado que
J
i
yk
é um vetor de protótipos que otimiza o valor da função
(FILIPPONE et al., 2008). Assim o protótipo é expresso por:
(uki )m xi
i∈C
yk = Pk
(uki )m
P
(2.6)
i∈Ck
A matriz de pertinência é denida pela seguinte expressão (FILIPPONE et al., 2008):
1
u−1
ki
X kxi − y k2 m−1
k
=
.
2
k
x
i − yj k
j∈C
k
(2.7)
2.1 Análise de Agrupamento
20
Semelhante ao K-médias, o FCM tem problemas para lidar com ruídos e anomalias nos
dados, além de apresentar a mesma dependência do conjunto de partição inicial. Outro problema relevante é a sua complexidade que apresenta um custo computacional alto, não sendo
recomendado para grandes conjunto de dados.
2.1.3.3
Seja
Kernel K-médias
φ : X → =,
e assim o conjunto
X = {x1 , x2 , . . . , xn }
um espaço de dimensão maior. A escolha apropriada de
mapeado no espaço de características
=
φ
é mapeado em um conjunto em
faz com que o conjunto de dados
possa ser separado de maneira linear. A Figura 2.1 é
um exemplo de mapeamento do espaço de entradas não linear para um agrupamento linear no
espaço de características.
Figura 2.1.
Mapeamento do espaço de entradas para o espaço de características
O uso desse procedimento é motivado pelo teorema de Cover (HAYKIN, 1999).
um conjunto de dados não linear no espaço de entradas
ser transformado em um espaço de características
=
X,
esse teorema arma que
X
Dado
pode
com alta probabilidade dos dados serem
linearmente separáveis. Para isso duas condições devem ser satisfeitas. A primeira é que a transformação seja não linear (φ), enquanto a segunda é que a dimensão do espaço de características
seja sucientemente alta.
Como
= pode ter dimensão muito alta (até mesmo innita), a computação pode ser custosa
ou até mesmo inviável.
Porém, é possível realizar esse mapeamento através do cálculo de
produtos escalares entre os dados no espaço de características.
funções denominadas
Kernels.
Isso é obtido com o uso de
2.1 Análise de Agrupamento
Um
kernel
de dimensão
q
21
é denido como sendo uma função
K
que mapeia os pontos no espaço de entrada
para pontos correspondentes em um novo espaço de dimensão
espaço oculto ou espaço de características, onde
q ≤ m.
m
denominado
Essa função recebe dois vetores de
pontos do espaço de entradas, que podem ser representados por
xi
e
xj ,
e computa o produto
escalar desses dados no espaço de características através da expressão 2.8:
K(xi , xj ) = φ(xi )φ(xj )
Kernel
Para garantir que o
(2.8)
represente mapeamentos nos quais seja possível o cálculo de
produtos escalares conforme a Equação 2.8, utiliza-se funções
Kernel
que seguem as condições
estabelecidas pelo teorema de Mercer (FILIPPONE et al., 2008). De forma simplicada, um
Kernel
que satisfaz as condições de Mercer é caracterizado por dar origem a matrizes positivas
denidas
nxn,
K,
Kij
em que cada elemento
chamada matriz de
é denido por uma matriz
Kij = K(xi , xj )
de ordem
Kernel, cujas entradas representam produtos internos escalares entre
as observações. Em outras palavras, se
K
é positivo denido, existe um mapeamento
φ
onde
K(xi , xj ) = φ(xi )φ(xj ).
Dentre as funções disponíveis mais utilizadas para a implementação do
kernel
existem as
polinomiais, as sigmoidais e a gaussiana, apresentadas na Tabela 2.1. As matrizes geradas por
essa última (gaussiana) também são chamadas de
Kernel Radial Basis Function
(RBF). Cada
um deles apresenta parâmetros que devem ser determinados previamente, indicados também
na Tabela 2.1. O
Kernel
alguns valores de
γ
e
κ.
Sigmoidal, em particular, satisfaz as condições de Mercer apenas para
Os
Kernels
Polinomiais com d = 1 também são denominados lineares.
Tabela 2.1.
Exemplos de Funções de
Tipo de Kernel
Polinomial
Expressão
Parâmetros
K(xi , xj ) = (xi xj + κ)d
κ, d
−kxi − xj k2
)
2σ 2
Gaussiano
K(xi , xj ) = exp(
Sigmoidal
K(xh , xl ) = tanh(γ(xi xj ) + κ)
É comum empregar a função de
tamente).
Kernel.
A utilidade do
Kernel
Kernel
σ
γ, κ
sem conhecer o mapeamento
φ
(realizado implici-
está, portanto, na simplicidade de seu cálculo e em sua
capacidade de representar espaços abstratos.
2.1 Análise de Agrupamento
22
Uma extensão do algoritmo K-médias, chamada
φ
KULIS, 2004) usa uma função
Kernel
K-médias (DHILLON; GUAN;
para o mapeamento do conjunto de dados em um espaço
de alta dimensão (espaço de características). Da mesma forma que o algoritmo K-médias, este
algoritmo procura por grupos de modo que a função objetivo
J φ seja minimizada, caso a medida
de similaridade seja a distância Euclidiana.
J φ (P ) =
K X
X
kφ(xi ) − yφk k2
(2.9)
k=1 i∈Ck
yφk
O valor do centroide
é expresso por:
yφk =
1 X
φ(xi )
nk x ∈C
i
A distância de
kφ(xi )−y
φ 2
kk
φ(xi )
ao centro
yφk
é expressa por:
1 X
= kφ(xi )−
φ(xi )k2 = φ(xi )φ(xi )−
nk x ∈C
i
j∈Ck
= K(xi , xi ) −
P
2×
nk
P P
+
φ(xi )φ(xj )
j∈Ck
K(xj , xl )
j∈Ck l∈Ck
(nk )2
2×
= Kii −
P P
+
nk
k
K(xi , xj )
P
2×
(2.10)
k
P
φ(xj )φ(xl )
j∈Ck l∈Ck
(nk )2
P P
Kij
j∈Ck
+
nk
Kjl
j∈Ck l∈Ck
(nk )2
Neste caso, a função objetivo pode ser reescrita conforme a equação 2.11:
J φ (P ) =
K X
X
kφ(xi ) − yφk k2 =
k=1 xi ∈Ck
onde
K X
X

2×
Kii −
k=1 xi ∈Ck
P
P P
Kij
j∈Ck
nk
+
Kjl

j∈Ck l∈Ck
(nk )2

(2.11)
Kij = K(xi , xj ) = φ(xi )φ(xj ).
Diversos métodos de agrupamento utilizando funções de
Kernel
têm sido propostos na
literatura através da modicação de abordagens já existentes, tais como K-médias, difuso cmédias, SOM, e
neural gas, que passaram a incorporar o Kernel
em suas soluções (FILIPPONE
et al., 2008).
A escolha do
Kernel
e da medida de similaridade é crucial para estes métodos, muitas
técnicas têm sido propostas no intuito de aprender automaticamente a forma do
dos dados (CRISTIANINI et al., 2002)(BACH; JORDAN, 2006).
muitos algoritmos têm sido aplicados para
Mama e Iris (UCI, 2010).
Kernel
benchmarks
Kernel
a partir
A respeito das aplicações,
padrões como Ionosfera, Câncer de
difuso c-médias foram propostos em (ZANG D. Q. E CHEN,
2.2 Análise de Agrupamento para Dados Simbólicos
23
2003) e tem sido aplicado em problemas de segmentação de imagens e reconhecimento de
dígitos manuscritos (ZHANG et al., 2003). Há aplicações de
face utilizando
Kernel
para reconhecimento de
kernel SOM (TAN; CHEN; ZHANG, 2004), em reconhecimento de voz (SATISH;
SEKHAR, 2004) e em predição de safras a partir de dados climáticos e de plantação (AWAN;
SAP, 2006).
2.1.3.4
Kernel Difuso c-médias
Seja uma função
φ : <m → <q ,
onde
q ≥ m
e assim o conjunto
X = {x1 , x2 , . . . , xn }
é
mapeado em um conjunto em um espaço de dimensão maior. Da mesma forma que o algoritmo
Kernel K-médias, este algoritmo procura por c grupos, P = {C1 , . . . , Cc }, de modo que a função
objetivo
Jφ
seja minimizada:
φ
J (P ) =
c
X
X
(uki )m kφ(xi ) − yφk k2
(2.12)
k=1 xi ∈Ck
O protótipo
yk
no espaço de características pode ser expresso por (FILIPPONE et al.,
2008):
(uki )m φ(xi )
x ∈Ck
yφk = i P
(uki )m
P
(2.13)
xi ∈Ck
A matriz de pertinência é denida pela seguinte expressão (FILIPPONE et al., 2008):
u−1
ki =
2.2
X
kφ(xi ) − yφk k2
j∈Ck
kφ(xi ) − yφj k2
1
! m−1
(2.14)
ANÁLISE DE AGRUPAMENTO PARA DADOS SIMBÓLICOS
A Análise de Dados Simbólica (ADS) surgiu, simultaneamente, da inuência de três áreas:
Análise Exploratória de Dados (DIDAY et al., 1982)(WARWICK; MORINEAU, 1984), Inteligência Articial (MICHALSKI, 1973) e Taxonomia Numérica (HAYES-ROTH; MCDERMOTT, 1978).
A ADS constitui numa extensão de alguns métodos utilizados para análise
de dados clássicos. Os primeiros trabalhos com os princípios básicos da abordagem simbólica
apareceram no nal dos anos 80 (DIDAY, 1986) e desde então vários outros trabalhos foram
realizados em diversas direções.
Um dos objetivos da ADS é prover técnicas para redução
2.2 Análise de Agrupamento para Dados Simbólicos
24
de extensas bases de dados em bases de dados simbólicos e posterior análise exploratória dos
dados através do emprego de técnicas de mineração de dados simbólicos já desenvolvidos. A
representação de conhecimento através dos dados simbólicos permite a atribuição de múltiplos
valores e regras para cada variável. Essas novas variáveis (conjuntos, intervalos e histogramas)
tornam possível reter informações sobre a variabilidade intrínseca ou incerteza do conjunto de
dados original. Bock e Diday (BOCK; DIDAY, 2000) apresentam de maneira sólida os principais conceitos da análise de dados simbólica e os principais métodos estatísticos desenvolvidos
para manipular dados desta natureza.
2.2.1
Tabela de Dados Simbólicos
A premissa é que o processo de obtenção de dados simbólicos deve preservar o máximo de
informações possíveis sobre os dados e ao mesmo tempo diminuir consideravelmente o tamanho
da tabela de dados inicial. Como resultado dessa transformação são geradas novas tabelas de
dados, denominadas de tabelas de dados simbólicos, que possuem estrutura mais complexa,
devido a cada uma das células dessas tabelas não necessariamente conterem um valor simples
quantitativo ou qualitativo, mas podem conter informações mais complexas tais como intervalos, funções probabilísticas ou de outros tipos, ligadas eventualmente por dependências e
taxonomias. As colunas dessas tabelas são chamadas de variáveis simbólicas, que servem para
descrever os objetos, e as linhas são as descrições simbólicas desses objetos, que diferentemente
do usual, não representam vetores de valores quantitativos ou categóricos simples. Os objetos
da tabela de dados simbólicos podem descrever indivíduos ou itens mais complexos, tais como
grupos de indivíduos.
Os dados simbólicos podem ser obtidos pelo menos da seguinte maneira: através da aplicação de um algoritmo de classicação não supervisionada para simplicar grandes conjuntos
de dados e descrever, de uma maneira auto-explicativa as classes associadas aos grupos obtidos;
Como resultado da descrição de conceitos por especialistas; Ou a partir de bases de dados relacionais para estudar conjuntos de unidades cuja descrição necessita a fusão eventual de várias
relações.
Uma vez obtidas as tabelas de dados simbólicos, a fase seguinte consiste na mineração de
2.2 Análise de Agrupamento para Dados Simbólicos
25
dados visando à mineração de conhecimentos. Neste caso, para o manuseio de dados simbólicos
é necessário a extensão das ferramentas usuais de extração de conhecimentos (classicação
supervisionada e não supervisionada, métodos fatoriais, árvores de decisão, etc.), bem como a
criação de novas ferramentas.
Tabela 2.2.
Tabela com dados clássicos (BILLARD; DIDAY, 2006)
X3 X4 X5 X6
X7
X8 X9 X10
i
X1
X2
1
Boston
M
2
Boston
M
3 Chicago D
4 El Paso M
5
Byron
D
6 Concord M
7 Atlanta M
8
Boston
O
9 Lindeld D
10 Lindeld D
11 Boston
D
12 Chicago M
13 Macon
M
14 Boston
D
15 Peoria
O
16 Concord D
17 Boston
D
18 Chicago D
19
Stowe
D
20
Tara
M
21 Quincy
O
22 Atlanta O
..
.
24
56
48
47
79
12
67
73
29
44
54
12
73
48
79
20
20
17
31
83
57
86
M
M
M
F
F
M
F
F
M
M
M
F
F
M
F
M
F
M
M
M
M
M
S
C
C
C
C
S
C
C
C
C
S
S
C
C
C
S
S
S
C
C
S
C
2
1
1
0
0
2
1
0
2
1
1
2
0
0
0
2
2
2
1
0
1
0
74,9
84,4
79,5
64,0
69,0
33,1
75,4
75,0
103,1
98,1
96,7
34,1
69,0
93,5
69,5
121,7
71,3
73,1
83,1
58,1
72,1
83,4
68
84
73
78
84
69
81
77
62
71
57
69
58
73
72
79
75
69
81
80
72
72
120
130
126
121
150
126
134
121
124
125
118
115
123
113
106
123
116
114
118
108
114
114
79
90
82
86
88
85
89
81
81
79
88
81
82
72
78
80
87
78
84
80
75
72
A Tabela 2.2 (BILLARD; DIDAY, 2006), contendo dados clássicos, será utilizada auxiliar
no entendimento de dado simbólico do tipo intervalo e da tabela de dados simbólicos.
tabela é composta por
n
Essa
registros médicos de indivíduos de uma típica companhia de seguros.
A descrição dos campos da tabela (variáveis
Xj )
é apresentada na Tabela 2.3. Para cada iésimo
indivíduo há um registro composto por informações familiares (estado civil, número de lhos,
número de irmãos, etc.), informações médicas(pressão, peso, colesterol, etc.). Cada linha da
Tabela 2.2 é composta por um conjunto de dados clássicos e representa uma realização para
as variáveis aleatórias
(x = (x1 , x2 , . . . , xn ))
para um determinado indivíduo.
Para tabelas
pequenas como essa, as técnicas estatísticas clássicas podem ser empregadas satisfatoriamente.
2.2 Análise de Agrupamento para Dados Simbólicos
Contudo, quando
p
e
n
26
são muito grandes, a análise pode tornar-se impraticável.
Tabela 2.3.
Descrição dos dados da Tabela 2.2
Descrição
Xi
Domicílio
X6
Tipo: Dental(D), Médico(M), Ótico(O) X7
Idade (em Anos): ≥ 0
X8
Gênero: Masc. (M), Fem. (F)
X9
Estado civil: Solteiro (S), Casado (C)
X10
Xi
X1
X2
X3
X4
X5
Descrição
Número de pais vivos: 0, 1, 2
Peso (em Kg): > 0
Pulso: > 0
Pressão sistólica: > 0
Pressão diastólica: > 0
Os dados simbólicos podem ser extraídos a partir de bases de dados clássicas, como a
apresentada na Tabela 2.2.
Como exemplo, considere descrever as realizações para o peso
Tipo × Gênero ).
para a categoria mulheres com seguro médico (
Aplicando essa regra à
Tabela 2.2 resulta na lista {34,1, 64,0, 69,0, 75,4}. Estes valores podem ser interpretados como
realizações
ξ
no intervalo [34,1:75,4]. A categoria mulheres com seguro médico ou (Tipo
Gênero) é um exemplo de conceito simbólico.
Ótico (O)
(w )|wu
e dois gêneros:
Masc (M)
e
Fem.(F)
∈ E = {w1 , w2 , w3 , w4 , w5 , w6 },
Como há 3 tipos:
Dental
(D),
Médico (M)
×
e
na tabela, há portanto, 6 possíveis categorias
em que cada categoria consiste em um conjunto de
indivíduos que satisfazem a descrição da categoria.
realizações simbólicas para as categorias (Tipo
×
A Tabela 2.4 apresenta um grupo de
Gênero).
Esta tabela pode ser entendida
como a Tabela de Dados Simbólicos.
Tabela de Dados Simbólicos (Descrições dos conceitos wu )
X1
X2
X3
X4
X5
T ipo × Gênero nu Idade Estado Civil
Peso
Pulso Pais Vivos
Tabela 2.4.
wu ∈ E
w1
w2
w3
w4
w5
w6
Dental Masc.
Dental Fem.
Médico Masc.
Médico Fem.
Ótico Masc.
Ótico Fem.
8
2
4
4
2
2
[17:54]
[20:79]
[12:83]
[12:73]
[57:86]
[73:79]
{C,S}
{C,S}
{C,S}
{C,S}
{C,S}
{C}
[73,1:121,7]
[69,0:71,3]
[33,1:84,4]
[34,1:69,0]
[72,1:83,4]
[69,5:75,0]
[57:81]
[75:84]
[68:84]
[58:81]
[72:72]
[72:77]
{0,1,2}
{0,2}
{0,1,2}
{0,1,2}
{0,1}
{0}
Os dados simbólicos podem ser estruturados e podem registrar a variação dos valores. A
Tabela 2.4 ilustra alguns exemplos do processo de extração de dados simbólicos a partir de bases
clássicas (DIDAY; NOIRHOMME-FRAITURE, 2008). Merece destaque a variável Pulso do
conceito
w5 .
Este exemplo ilustra o caso em que um intervalo representa um ponto clássico
2.2 Análise de Agrupamento para Dados Simbólicos
x = a,
2.2.2
cuja realização simbólica
27
ξ = [a, a].
Tipos de Variáveis Simbólicas
Na análise de dados clássicos, as variáveis assumem um único valor ou categoria para um
dado indivíduo, entretanto as variáveis simbólicas podem assumir para um dado indivíduo
ou grupo de indivíduos:
conjuntos de categorias, intervalos, histogramas, etc.
As variáveis
simbólicas dividem-se basicamente em: variáveis multi-valoradas (ordenadas ou não-ordenadas),
variáveis modais e variáveis do tipo intervalo.
Variáveis simbólicas multi-valoradas não-ordinais
Y
é denido como uma variável simbólica multi-valorada se seus valores
a subconjuntos nitos do domínio
E = {s1 , . . . , sn }
é um conjunto de
bancos existentes em
Real, . . . ,
D : |Y (k)| < ∞
k
n
já para o indivíduo
k ∈ E,
Por exemplo, seja
onde
Y
os
D = { Banco do Brasil, Bradesco, Banco
Caixa Econômica}. Logo, para o indivíduo
do Brasil, Banco Real },
para todos os indivíduos
objetos a serem agrupados.
cidades brasileiras, onde
Y (k) correspondem
k = P aulista, Y (P aulista) = { Banco
k = Barreiros, Y (Barreiros) = { Banco do
Brasil,Caixa Econômica }.
Variáveis simbólicas multi-valoradas ordinais
Uma variável simbólica
de ordem
≺,
Y
é denida como multi-valorada ordinal se
tal que, para quaisquer pares de elementos,
a, b ∈ D,
D
existe a relação
caso comum é representado por uma variável qualitativa com domínio nito
onde:
b.
a ≺ b ≺ c ≺ . . . ≺ h.
Na prática,a
Assim, para dois indivíduos
k, t ∈ E ,
suporta uma relação
a ≺ b.
D = {a, b, c, . . . , h},
≺ b é interpretado como a antecede b ou a é menor que
onde observamos
a = Y (k)
e
b = Y (t)
para a variável
Y , é possível indicar qual dos indivíduos é estritamente melhor que o outro: a ≺ b ou b ≺ a.
exemplo,
Um
Por
Y = { Qualidade do produto } e D = {excelente, bom, razoavel, pobre, insuf iciente}.
2.2 Análise de Agrupamento para Dados Simbólicos
28
Variáveis simbólicas modais
A variável simbólica
Y
também pode ser denida como modal, com domínio
conjunto de objetos simbólicos
objeto
a ∈ F,
F = {a, b, . . .},
w(y),
Y (a) ⊆ D,
associado a cada categoria
quão freqüente, típico ou relevante a categoria
distribuição das agências bancárias em
k
sob o
é uma variável multi-valorada que, para cada
apresenta não apenas um conjunto de categorias
freqüência, probabilidade ou peso
D
y
é para o objeto
a.
mas também uma
y ∈ Y (a),
que indica o
Por exemplo, seja
cidades. Então, para uma cidade
Y
a
t, Y (t) = {Banco
do Brasil (0, 5), Bradesco (0, 4),Banco Real (0, 1)}.
Variáveis simbólicas do tipo intervalo
Uma variável
a≤b
e {a, b}
Y
∈ <.
wu
com
No exemplo da Tabela 2.4, os intervalos são gerados como resultado da
agregação de dados clássicos. Os valores
na categoria
ξ = [a : b] ⊂ <,
é do tipo intervalo se ela representa uma realização
auj
e
buj
do intervalo [auj :
buj ]
referentes à variável
j
são dados por:
auj = min xij
i∈Ωu
buj = max xij
i∈Ωu
onde
Ωu
é o conjunto dos
iésimos
valores
(i ∈ Ω)
que compõe a categoria
wu .
Exemplos dessa
denição podem ser obtidos do conjunto de dados simbólicos da Tabela 2.4. Considere a variável
Idade para
u = 3.
X1 (w3 ) = Idade(w3 ) = Idade(M édico × M asculino) = ξ31 = [12 : 83]
o resultado é um intervalo que cobre as idades dos homens com plano médico.
As variáveis
simbólicas do tipo intervalo também podem ocorrer quando não é possível obter uma medida
precisa das observações, como no caso dos instrumentos de medição.
2.2.3
Métodos para Agrupamento de Dados Simbólicos
Esta seção apresenta alguns métodos de agrupamento para dados simbólicos. Os métodos
de agrupamento podem ser hierárquicos e particionais (ou de particionamento) para dados
2.2 Análise de Agrupamento para Dados Simbólicos
29
expressos por intervalos, conjuntos de categorias e distribuições de pesos. Como este trabalho
tem como foco o desenvolvimento de métodos de partição, a seção sobre métodos hierárquicos
é mais breve e a de métodos de partição um pouco mais extensa.
2.2.3.1
Métodos Hierárquicos
Ichino e Yaguchi (ICHINO; YAGUCHI, 1994) propuseram medidas de Minkowski para
misturas de variáveis e apresentaram métodos de ligação simples para conjuntos de dados
representados por valores numéricos e simbólicos. Em (GOWDA; RAVI, 1995a) e (GOWDA;
RAVI, 1995b) foram introduzidos, respectivamente, algoritmos aglomerativos e divisivos para
dados simbólicos baseados em uma combinação entre medidas de similaridade e dissimilaridade.
Estas medidas são denidas levando em conta o conteúdo, posição e espalhamento de objetos
simbólicos.
Chavent (CHAVENT, 1998) apresentou um método divisivo para dados simbólicos que
fornece ao mesmo tempo uma hierarquia de um conjunto de dados simbólicos e uma caracterização monotética de cada
cluster
na hierarquia. El-Sonbaty e Ismael (EL-SONBATY; ISMAIL,
1998) introduziu uma técnica hierárquica aglomerativa baseada no conceito de métodos de ligação simples para agrupar dados numéricos e simbólicos simultaneamente.
Gowda e Ravi
(RAVI; GOWDA, 1999a) desenvolveram um algoritmo para dados simbólicos baseando-se na
abordagem gravitacional que é inspirada no movimento de partículas do espaço de acordo com
a atração gravitacional mútua das mesmas.
Em (RAVI; GOWDA, 1999b) foi apresentado uma abordagem de grupos ISODATA para
dados simbólicos usando algoritmos genéticos.
Brito (BRITO, 1994) apresentou um método
de agrupamento usando uma estrutura de classicação piramidal para dados simbólicos onde
as classes são construídas baseando-se em um conceito de objeto simbólico completo. Maiores
informações sobre métodos hierárquicos para dados simbólicos podem ser encontradas em (DIDAY; NOIRHOMME-FRAITURE, 2008).
2.2 Análise de Agrupamento para Dados Simbólicos
2.2.3.2
30
Métodos Particionais
Esta seção cita alguns métodos de particionamento para dados simbólicos existentes na
literatura e em seguida apresenta os métodos de partição do tipo nuvem dinâmica que foram
utilizados o estudo comparativo entre os métodos propostos neste trabalho.
Em (GORDON, 2000) foi apresentado um algoritmo de agrupamento de dados simbólicos
que minimiza a soma do potencial de descrição dos grupos. No trabalho (VERDE V., 2001) foi
introduzido um método agrupamento que permite obter uma tipologia dos objetos descritos por
dados simbólicos através de funções de proximidade dependentes do contexto. Em (CHAVENT
M. E LECHEVALLIER, 2002) propuseram um algoritmo de agrupamento dinâmico para dados
de tipo intervalo utilizando a distância de Hausdor. Nos trabalhos (SOUZA; CARVALHO,
2004b)(SOUZA; CARVALHO, 2004a) foram propostos algoritmos de agrupamento dinâmico
para dados simbólicos de tipo intervalo baseado em distâncias adaptativas e não adaptativas
de tipo
L1 , L2
e
LIN F .
Em (CONAN-GUEZ; ROSSI; GOLLI, 2006) foi introduzido uma
modicação do algoritmo de mapas auto-organizáveis (SOM) que estende esse método aos
dados simbólicos através da utilização de uma matriz de dissimilaridade apropriada.
O trabalho (CARVALHO et al., 2006) propôs um algoritmo de agrupamento dinâmico que
usa um critério de adequação baseado em distâncias de Hausdor adaptativas para comparar
dados simbólicos de tipo intervalo. Em (CARVALHO; BRITO; BOCK, 2006) foi introduzido
um algoritmo de agrupamento dinâmico que usa um critério de adequação baseado em uma
adaptação conveniente da distância euclidiana para comparar dados simbólicos de tipo intervalo
e considera o problema da normalização desse tipo de dados e a interpretação dos grupos e da
partição fornecida pelo algoritmo. Em (CARVALHO, 2007) foi estendido o algoritmo padrão de
agrupamento difuso usando uma versão apropriada da distância
L2
adaptativa para comparar
dados simbólicos de tipo intervalo. Mais recentemente, em (CARVALHO; SOUZA, 2010), foram
propostos métodos de reconhecimento de padrões não supervisionados para dados simbólicos
mistos com base na metodologia de agrupamento dinâmico com distância adaptativa única e por
classe. Finalmente, em (CARVALHO; TENóRIO, 2010) propõe versões difusas para distâncias
adaptativa quadráticas.
Na seção seguinte são apresentados os métodos de agrupamento dinâmico (SOUZA, 2003)
(CARVALHO; LECHEVALLIER, 2009b) (CARVALHO, 2007) que foram utilizados para estudo
2.2 Análise de Agrupamento para Dados Simbólicos
31
comparativo com os métodos propostos neste trabalho.
Métodos de Agrupamento Dinâmico para dados simbólicos intervalares
Os algoritmos de agrupamento dinâmicos compreendem diversos métodos de agrupamento
não hierárquicos. O objetivo principal é obter um particionamento em um número de classes
pré-denido a partir de um conjunto de dados de modo que o conjunto de protótipos escolhidos
minimizem um critério que mede a adequação entre esses representantes e os respectivos elementos de cada classe. O ajustamento dos elementos de acordo com o critério permite encontrar
uma solução ótima local para o problema. Outra propriedade importante desses algoritmos é
a capacidade de reconhecer classes de formas e tamanhos diferentes quando usam distâncias
adaptativas, as quais consideram a dispersão dos elementos em cada classe ou em todo o conjunto de dados. Por outro lado, existe o problema de convergência nesses algoritmos, uma vez
que a partição nal tem relação direta tanto dos protótipos escolhidos para denir o conjunto
de classes inicial quanto da distância usada para denir o representante mais próximo e o ajuste
dos grupos.
A ideia dessa abordagem de agrupamento é começar com um conjunto de protótipos escolhidos aleatoriamente, os quais denirão a conguração inicial das classes afetando cada elemento
de acordo com a distância
L2
xa encontrada entre o protótipo e o padrão. A classe perten-
cente ao elemento será a classe do protótipo que possui a menor distância caracterizando a
etapa de alocação. Em seguida, uma etapa de representação é realizada, onde os protótipos
são atualizados de acordo com os elementos pertencentes em cada classe. Essas duas etapas
prosseguem iterativamente até a convergência do algoritmo denida
a priori,
mas com uma
diferença na etapa de alocação: a distância usada não precisa ser a
L2
Uma forma de
xa.
avaliar a convergência é vericar se o valor do critério do algoritmo estabilizou, caracterizando
pouca variação entre os elementos das classes. Outra forma é vericar se todas as classes permaneceram invariantes, sem que nenhum elemento seja realocado.
seja alcançada, o ciclo de alocação e representação se repete.
Caso a convergência não
Tradicionalmente, o método é
executado diversas vezes com diferentes combinações de protótipos com o objetivo de obter a
melhor partição para a resposta nal.
2.2 Análise de Agrupamento para Dados Simbólicos
32
A seguir são apresentados três métodos de agrupamento dinâmico com distâncias adaptativas que serão utilizados neste trabalho para efeito de comparação com os métodos propostos.
Os dois primeiros usam agrupamentos rígidos e o seguinte agrupamento difuso.
O objetivo
principal desse método é associar uma distância diferente para cada classe ou elemento, a qual
muda a cada iteração do algoritmo. A partir dessas variações o algoritmo é capaz de reconhecer diferentes dispersões entre os padrões e as classes, de modo que os grupos de tamanhos
diferentes e/ou não isomorfos sejam identicados. A ideia é associar diferentes distâncias para
cada grupo de forma que, no nal de cada etapa de alocação, a distância entre os elementos e
os seus respectivos representantes seja a menor possível.
Seja uma variável
simbólica do tipo intervalo X
2008) é uma correspondência denida de
um conjunto de intervalos denidos em
Ω = {1, . . . , n}.
Cada objeto ou padrão
Ω
<.
i,
<
tal que
i ∈ Ω, X(i) = [a, b] ∈ I ,
Considere um conjunto de
descrito por
é representado como um vetor de intervalos
Seja
em
(DIDAY; NOIRHOMME-FRAITURE,
p
n
onde
I
é
objetos ou padrões
variáveis simbólicas do tipo intervalo,
xi = ([a1i , b1i ], . . . , [api , bpi ])T .
PK um conjunto de partições, onde P = (C1 , . . . , CK ) de Ω em K classes e um conjunto
LK = L×L . . .×L de K -uplas L = (L1 , . . . , LK ) com Lk ∈ L e dK = d×d . . .×d um conjunto de
K
distâncias
d = (d1 , . . . , dK )
uma partição
P∗ ∈ PK
em
um conjunto de distâncias
K
com
dk ∈ d.
O problema de agrupamento consiste em encontrar
classes, um conjunto de protótipos
d∗ ∈ dK
L∗ ∈ LK
relativo as classes e
tal que:
J(P ∗ , L∗ , d∗ ) = M in{J(P, L, d)|P ∗ ∈ PK , L∗ ∈ LK , d∗ ∈ dK }.
O critério
J
é calculado fazendo-se:
J=
K X
X
d2k (xi , yk )
(2.15)
k=1 i∈Ck
onde
d2k (xi , yk )
objeto
é uma distância quadrática adaptativa que mede a dissimilaridade entre um
xi (i = 1, . . . , n) e um protótipo do grupo yk (k = 1, . . . , K).
Os métodos de agrupamento dinâmico adaptativos consideraram um fator em cada cálculo
da distância o qual pode variar considerando a organização do particionamento.
considera as informações locais, sejam elas associadas à classe
partição
P.
Ck
Esse fator
ou a cada elemento
i
da
Dependendo da forma como esse fator é calculado, a distância adaptativa pode ser
2.2 Análise de Agrupamento para Dados Simbólicos
por
classe,
quando o fator varia por grupos, ou
33
única,
quando considera somente o elemento
em questão.
A distância Euclidiana Adaptativa Única (CARVALHO; LECHEVALLIER, 2009b) muda
a cada iteração do método, de modo que a forma e o tamanho das classes sejam identicados,
mas a distância adaptativa é a mesma para todos os grupos:
d (xi , yk ) =
2
p
X
λj (aji − αkj )2 + (bji − βkj )2 .
(2.16)
j=1
onde a distância é parametrizada pelo vetor de pesos
λk =λ= (λ1 , . . . , λp ).
A distância Euclidiana Adaptativa por classe (SOUZA, 2003) tem como ideia principal
associar a distância
dk
a cada grupo
Ck
tal que a soma das distâncias entre os elementos e os
seus respectivos protótipos seja a menor possível. Uma característica importante deste método
é que a distância não é única para todas a classes, mas sim diferente da obtida em cada iteração
do método. Em cada iteração é medida a adequação do critério do grupo
qualidade através da soma das distâncias
dk (xi , yk )
entre os objetos
Ck
que mede a sua
xi ∈ C k .
A distância é
denida pela seguinte expressão:
d2k (xi , yk ) =
p
X
λjk (aji − αkj )2 + (bji − βkj )2 .
(2.17)
j=1
onde a distância é parametrizada pelo vetor de pesos
λk = (λ1k , . . . , λpk )
O algoritmo inicia escolhendo aleatoriamente uma partição
apresentados a seguir, até a convergência quando o critério
J
P
para cada classe
Ck .
e alterna entre três passos,
alcança um estado estacionário
representando um mínimo local.
• Denição dos melhores protótipos :
. . . , [αkp , βkp ])
onde
αkj
valores do conjunto
k = 1, . . . , K
calcule os protótipos
é a média dos valores do conjunto
{aji : i ∈ Ck }
e
βkj
yk = ([αk1 , βk1 ],
é a média dos
{bji : i ∈ Ck } (j = 1, . . . , p).
• Denição das melhores distâncias :
Para
Para
k = 1, . . . , K
calcule:
Se a distância adaptativa única for usada, o vetor de pesos
λ= (λ1 , . . . , λp )
com
2.2 Análise de Agrupamento para Dados Simbólicos
λj > 0 (j = 1, . . . , p)
e
Qp
j=1
λj = 1
"
Qp
h=1 (
λj =
34
onde
λj
é expresso por:
# p1
K P
P
(aji
−
αkj )2
+
(bji
−
βkj )2 )
k=1 i∈Ck
K P
P
(aji
.
−
αkj )2
+
(bji
−
βkj )2
k=1 i∈Ck
Se a distância adaptativa por classe for utilizada, o vetor de pesos
com
λjk > 0 (j = 1, . . . , p)
Qp
e
j=1
λjk = 1
onde
λjk
λk = (λ1k , . . . , λpk )
é expresso por:
# p1
"
Qp
h=1 (
λjk =
(aji − αkj )2 + (bji − βkj )2 )
P
i∈Ck
P
.
(aji − αkj )2 + (bji − βkj )2
i∈Ck
• Denição das melhores partições :
Os
Os protótipos e os vetores de pesos
λk
ou
λ
são xados.
clusters Ck (k = 1, . . . , K) que minimizam o critério de agrupamento J, são alterados
de acordo com a seguinte regra de alocação:
Ck = {i ∈ Ω : d(xi , yk ) ≤ d(xi , yh )∀h 6=
k(h = 1, . . . , K)}.
Agora é apresentada a versão difusa do método adaptativo por classe (CARVALHO, 2007).
A formulação do problema de agrupamento é semelhante aos métodos anteriores, e consiste em
encontrar uma partição difusa
P∗ ∈ PK
em
K
relativo as classes e um conjunto de distâncias
classes, um conjunto de protótipos
d∗ ∈ dK
L∗ ∈ LK
tal que:
J2 (P ∗ , L∗ , d∗ ) = M in{J(P, L, d)|P ∗ ∈ PK , L∗ ∈ LK , d∗ ∈ dK }.
O critério
J2
é calculado agora da seguinte maneira:
J2 =
K X
X
(uki )m d2k (xi , yk )
(2.18)
k=1 i∈Ck
onde
d2k (xi , yk )
é uma distância quadrática adaptativa que mede a dissimilaridade entre um
objeto
xi (i = 1, . . . , n)
objeto
i
ao grupo
e um protótipo do grupo
yk (k = 1, . . . , K),
e
uki
é a pertinência, do
Ck , m ∈ (1, +∞).
O algoritmo inicia escolhendo aleatoriamente uma partição
apresentados a seguir, até a convergência quando o critério
representando um mínimo local.
J
P
e alterna entre três passos,
alcança um estado estacionário
2.2 Análise de Agrupamento para Dados Simbólicos
35
• Denição dos melhores protótipos : Para k = 1, . . . , K calcule os protótipos yk = ([αk1 , βk1 ],
P
P
P
P
(uki )m .
(uki )m e βkj =
(uki )m bik /
. . . , [αkp , βkp ]) onde αkj =
(uki )m aik /
i∈Ck
i∈Ck
• Denição das melhores distâncias :
Para
classe for utilizada, o vetor de pesos
Qp
j=1
λjk = 1
onde
λjk
i∈Ck
i∈Ck
k = 1, . . . , K
calcule a distância adaptativa por
λk = (λ1k , . . . , λpk )
com
λjk > 0 (j = 1, . . . , p)
e
é expresso por:
# p1
"
Qp
h=1 (
λjk =
P
(uki )m ((aji − αkj )2 + (bji − βkj )2 ))
i∈Ck
P
.
(uki )m [(aji − αkj )2 + (bji − βkj )2 ]
i∈Ck
• Denição das melhores partições :
dos. Os
Os protótipos e os vetores de pesos
λk
ou
λ
são xa-
clusters Ck (k = 1, . . . , K) que minimizam o critério de agrupamento J2
restrições
k
P
uki = 1
e
uki ≥ 0,
são alterados de acordo com a seguinte expressão:
i=1

P
p
λjk [(aji
αkj )2
(bji
βkj )2 ]
 p1
−
+
−
X
 K  j=1




uki = 
p
P

 k=1
λj [(aj − αj )2 + (bj − β j )2 ]
j=1
h
i
k
i
k
−1





sob as
CAPÍTULO 3
MÉTODOS DE AGRUPAMENTO BASEADOS EM
FUNÇÕES KERNEL PARA DADOS SIMBÓLICOS
INTERVALARES
Como abordado no capítulo anterior, os algoritmos de partição k-médias apesar de amplamente
utilizados na literatura de classicação de dados em diversos domínios de aplicação, tais como
reconhecimento de padrões, aprendizagem de máquina, mineração de dados, visão computacional, biologia computacional, classicação de resultados estatísticos em estudos sociais, dentre
outros, apresentam limitações em relação à separabilidade linear (diculdade de identicar a
não-lineariedade dos dados no espaço de entrada).
O uso de
Kernel
tem sido usado como uma poderosa ferramenta para resolver os problemas
relacionados à lineariedade. Nos últimos anos, o interesse na utilização de métodos de
em aplicações não-superviosionadas tem crescido.
Kernel
Nos métodos de particionamento usando
Kernel, o produto interno entre as variáveis não-lineares é substituído por um Kernel apropriado
denominado
Mercer Kernel.
Segundo (FILIPPONE et al., 2008), esses podem ser categorizados
em três grandes famílias: agrupamento no espaço de características (
clustering in feature space ),
agrupamento no espaço de entradas e agrupamento via máquina de vetores de suporte.
Na categoria de espaço de características, uma versão do método K-médias usando
Kernel
(DHILLON; GUAN; KULIS, 2004) procura solucionar o problema de partição encontrando
hiperespaços de
n
(tamanho do conjunto a ser particionado) dimensões que melhor separam
os objetos em grupos distintos.
Esse método é uma extensão do algoritmo de agrupamento
clássico k-médias que mapeia os dados originais em um espaço de maior dimensão, denominado
espaço de características, através de uma transformação não linear, de modo que esta nova
representação se torne linearmente separável.
O mapeamento entre os espaços não pode ser
denido explicitamente, e o ajustamento entre os grupos e seus respectivos centros é denido
em termos de uma função de
Kernel.
Na categoria agrupamento no espaço de entrada, a ideia
3.1 Funções de
Kernel
para Intervalos
é fazer uso de funções de
Kernel
37
para auxiliar a identicação dos protótipos no espaço de
entrada. Na categoria via máquina de vetores de suporte, a principal tarefa é a construção de
um hiperplano ótimo, ou seja, hiperplanos que maximizam a margem de separação das classes,
possibilitando a separação dos padrões de treinamento de diferentes classes.
Os padrões de
treinamento são mapeados em um espaço de alta dimensão e o classicador SVM encontra um
hiperplano que consegue separar o espaço linearmente com a máxima margem nesse espaço de
alta dimensão. Esse mapeamento é feito utilizando uma função
Kernel.
Este capítulo propõe um conjunto de métodos de agrupamento como extensões do método
K-médias usando
Kernel
nos espaços de características e de entrada para dados simbólicos do
tipo intervalo. Neste contexto, cada objeto é descrito por um vetor de intervalos e diferentes
funções de
Kernel
são adaptadas para tratar intervalos.
O estudo desses tipos de dados é
realizado pela Análise de Dados Simbólicos (ADS) que objetiva estender os métodos estatísticos
para dados simbólicos de tipo intervalo.
a seção 3.1 descreve funções de
Kernel
introduzidos os métodos K-médias com
O capítulo é organizado como segue.
adaptadas para tratar intervalos.
Kernel
Inicialmente,
Na seção 3.2, são
no espaço de características para os paradigmas
rígido e difuso, respectivamente. Na seção 3.3, são apresentados os correspondentes no espaço
de entrada também para os paradigmas rígido e difuso, respectivamente.
3.1
FUNÇÕES DE KERNEL PARA INTERVALOS
Uma variável
simbólica do tipo intervalo X
uma correspondência denida de
de intervalos denidos em
Cada objeto ou padrão
i,
<.
Considere
Ω em < tal que i ∈ Ω, X(i) = [a, b] ∈ I , onde I
Considere um conjunto de
descrito por
como um vetor de intervalos
ξ : xi → ξ(xi )
entrada para intervalos nito
(DIDAY; NOIRHOMME-FRAITURE, 2008) é
p
n
objetos ou padrões
é um conjunto
Ω = {1, . . . , n}.
variáveis simbólicas do tipo intervalo, é representado
xi = ([a1i , b1i ], . . . , [api , bpi ])T .
uma função não linear que realiza um mapeamento do espaço de
X
para um espaço de características de alta dimensão
A escolha adequada da função de
kernel
z.
é um fator importante para que o problema não
linear no espaço dos dados originais possa ser linearmente separável no espaço de características.
kernel
Uma escolha comum é a utilização de uma função RBF (
Gaussiano). Neste trabalho
3.1 Funções de
Kernel
para Intervalos
38
foram denidas duas funções RBF para intervalo:
1) Função RBF com
Kernel
denida por uma componente
K(xi , xl ) = exp(
onde
kxi − xl k2 =
Pp
j=1
xl = (a1l , b1l , . . . , apl , bpl )T
(aji − ajl )2 + (bji − bjl )2
Kernel
bém
kxiI − xlI k2 =
.
Considere
xi = (a1i , b1i , . . . , api , bpi )T
e
Ω.
denida por duas componentes
K(xi , xl ) = exp(
onde
(3.1)
como vetores de 2p-dimensões que descrevem, respectivamente,
o i-ésimo e l-ésimo objetos de
2) Função RBF com
−kxi − xl k2
)
2σ 2
Pp
j
j=1 (ai
xiI = (a1i , , . . . , api )T
e
−kxiI − xlI k2
−kxiS − xlS k2
)
+
exp(
)
2σ 2
2σ 2
− ajl )2
e
kxiS − xlS k2 =
xiS = (b1i , , . . . , bpi )T
Pp
j
j=1 (bi
− bjl )2 .
(3.2)
Considere tam-
como vetores de p-dimensões associados,
respectivamente, aos limites inferior e superior dos intervalos que descrevem o i-ésimo
objeto de
Ω,
e
xlS = (a1l , , . . . , apl )T
que descrevem o l-ésimo objeto de
e
xlS = (b1l , , . . . , bpl )T
como vetores de p-dimensões
Ω.
Proposição 3.1.1 A função para dados intervalares denida por duas componentes de kernel
segundo a equação 3.3, expressa por
K(xi , xl ) = ξ(xiI )ξ(xlI ) + ξ(xiS )ξ(xlS )
(3.3)
é um kernel para todo xi , xl ∈ X .
Prova.
kernel
Seguindo a denição de
kernel
para dados clássicos (CRISTIANINI; J., 2000), um
para dados intervalares pode ser denido por:
K(xi , xl ) = ξ(xi )ξ(xl )
para todo
Seja
(3.4)
xi , xl ∈ X .
K1
e
K2
duas funções de
kernel
denidas no espaço de entradas para intervalos
Respeitando a propriedade em que a soma de duas funções de
entrada representa uma função
kernel
kernel
X.
sob um mesmo espaço de
válida (CRISTIANINI; J., 2000), podemos armar que:
K(xi , xl ) = K1 (xi , xl ) + K2 (xi , xl )
(3.5)
kernel
3.2 Métodos baseados em
para todo
para particionamento no espaço de características
39
xi , xl ∈ X .
K (xiI , xlI ) é um kernel
0
Considere agora, que a função
e pode ser escrito da seguinte forma:
K (xiI , xlI ) = ξ(xiI )ξ(xlI )
0
Analogamente temos:
Temos ainda que
intervalos
X
tal que:
δ1
e
K (xiS , xlS ) = ξ(xiS )ξ(xlS )
0
δ2
são duas funções contínuas denidas sob o espaço de entrada para
xiI = δ1 (xi ) e xiS = δ2 (xi ).
Deste modo, a função
K (xi , xl ) = K (xiI , xlI ) + K (xiS , xlS )
0
0
0
pode ser reescrita como:
K (xiI , xlI ) + K (xiS , xlS ) =
0
0
(3.6)
= K (δ1 (xi ), δ1 (xl )) + K (δ2 (xi ), δ2 (xl ))
0
0
= ξ(δ1 (xi ))ξ(δ1 (xl )) + ξ(δ2 (xi ))ξ(δ2 (xl ))
= ξ1 (xi )ξ1 (xl ) + ξ2 (xi )ξ2 (xl )
= K1 (xi , xl ) + K2 (xi , xl )
Assim, comparando o resultado de 3.6 com 3.5, podemos concluir que a função
3.4 é um
3.2
kernel
K
da equação
para dados intervalares.
MÉTODOS BASEADOS EM KERNEL PARA PARTICIONAMENTO NO ESPAÇO DE CARACTERÍSTICAS
Nesta seção são apresentados dois métodos usando
para dados simbólicos do tipo intervalo.
Kernel
no espaço de características
Neste contexto, para cada elemento, os dados de
entrada (designados por atributos no espaço de dados original)são mapeados por uma função
não-linear em um espaço de características. Nesta abordagem os protótipos são implicitamente
denidos neste novo espaço, sendo necessário uma aproximação desses protótipos através de
um mapeamento inverso do espaço de características para o espaço de entrada.
Considere
ξ : xi → ξ(xi )
uma função não linear que realiza um mapeamento do espaço de
entrada para um espaço de características de alta dimensão
z.
Considere também
em um espaço de características do tipo intervalo de alta dimensão
K
Gξ = {gξ1 , . . . , gξK }.
centros
3.2 Métodos baseados em
3.2.1
kernel
para particionamento no espaço de características
Método K-médias (MKM-EC)
Ω
O problema de agrupamento consiste em encontrar uma partição de
juntos
40
P ∗ = {C1 , . . . , CK }
de modo que a função objetivo
J1ξ (P, Gξ )
=
K X
X
J1ξ
em
K
grupos dis-
seja minimizada.
kξ(xi ) − gξk k2
(3.7)
k=1 i∈CK
onde o valor do protótipo (k
th ) é expresso por:
P
g =
ξ
k
A função
ξ
ξ(xi )
|Ck |
i∈Ck
(3.8)
não está denida e, portanto, não é possível determinar explicitamente os
protótipos dos grupos através da Equação (3.8). Neste caso, a distância Euclidiana quadrática
de um objeto de
ξ(x)
gξk ,
e o centro do grupo
no espaço de características pode ser obtida da
seguinte maneira:
kξ(xi ) − gξk k2 = (ξ(xi ) − gξk )(ξ(xi ) − gξk ) = ξ(xi )ξ(xi ) − 2ξ(xi )gξk + gξk gξk
(3.9)
Substituindo a expressão do protótipo 3.8 na expressão da distância 3.9 obtém-se:
kξ(xi ) − g
ξ 2
kk
= ξ(xi )ξ(xi ) −
2×
ξ(xi )ξ(xl )
+
|Ck |
P
l∈Ck
P
kξ(xi ) − gξk k2 = K(xi , xi ) −
2×
K(xi , xl )
+
|Ck |
l∈Ck
P
l∈Ck
ξ(xi )ξ(xl )
|Ck |2
Reformulando o produto interno em termos da função de
P
i∈Ck
(3.10)
Kernel, obtém-se:
P
i∈Ck
P
x xl )
l∈Ck K( i ,
|Ck |2
(3.11)
O algoritmo K-médias no espaço de características para dados do tipo intervalo não possui
propriamente uma etapa de atualização dos protótipos, pois o protótipo não pode ser explicitamente denido. No entanto, mesmo sem a denição explícita do protótipo é possível realizar
uma etapa de alocação através do mapeamento implícito via função de
em Eq.(3.11).
O algoritmo dene uma matriz de
kernel,
kernel K = {K(xi , xl )}n×n
apresentada
e um conjunto
de partições iniciais, e executa interativamente reorganizando os indivíduos mais próximos em
grupos até que a função objetivo
J1ξ
alcance um valor estacionário, representando um mínimo
local.
O esquema do algoritmo do MKM-EC é ilustrado a seguir:
kernel
3.2 Métodos baseados em
1.
para particionamento no espaço de características
41
Etapa de Pre-processamento: denição do novo espaço de características
Calcule a matriz
K
utilizando uma função de
kernel
apropriada para
i = 1, . . . , n
e
j = 1, . . . , n.
2.
Etapa de Inicialização: obtenção da partição inicial
Selecione (aleatoriamente) uma partição inicial
selecione
K
objetos distintos
yk∗ (k∗ = arg mink=1,...,K
y1 , . . . , yK
0
}
{C10 , . . . , CK
e associe cada objeto
Pp
j
j 2
j
j 2
j=1 (ai − αk ) + (bi − βk )
i
em
Ω
de
K clusters
a uma classe
Ck∗
ou
tal que
para construir a partição inicial
0
}.
{C10 , . . . , CK
3.
Etapa de Alocação: denição da melhor partição
test ← 0
Para
i=1
até
dena o
faça
cluster
k ∗ = arg
Se
n
i ∈ Ck
vencedor
mink=1,...,K
e
Ck∗
tal que
kξ(xi ) − gξk k2
k 6= j
test ← 1
Ck ← Ck ∪ {i}
Cj ← Cj \ {i}
4.
Critério de Parada
Se
3.2.2
test = 0
então PARE, caso contrário vá para a etapa 3.
Método c-médias difuso (McM-EC)
Considere
uki ∈ [0, 1]
como o grau de pertinência de um indivíduo
i
a um grupo
k,
onde a
pertinência ou associação de um indivíduo para todos os grupos obedecem a seguinte restrição:
k
P
i=1
uki = 1 ∀k = 1, . . . , n
(3.12)
3.2 Métodos baseados em
kernel
para particionamento no espaço de características
O problema de agrupamento consiste em encontrar uma partição de
P ∗ = {C1 , . . . , CK }
de modo que a função objetivo
J2ξ (P, Gξ )
=
K X
X
J2ξ
42
Ω em K
grupos difusos
seja minimizada.
(uki )m kξ(xi ) − gξk k2
(3.13)
k=1 i∈CK
onde
m
é um coeciente que vai ponderar o quanto o grau de pertinência inuencia na medida
de distância denida. O valor do protótipo é expresso por:
g =
P
ξ
k
x
m
i∈Ck (uki ) ξ( i )
P
m
i∈Ck (uki )
(3.14)
É possível denir a matriz de pertinência que obedece a restrição 3.12 da seguinte maneira
(GRAVES; PEDRYCZ, 2010):
u−1
ki =
X
kξ(xi ) − gξk k2
j∈Ck
kξ(xi ) − gξj k2
1
! m−1
.
(3.15)
Neste caso, assim como na seção anterior, a distância Euclidiana quadrática de um objeto
de
ξ(x) e o centro do grupo gξk ,no espaço de características pode ser obtida da seguinte maneira:
kξ(xi ) − gξk k2 = (ξ(xi ) − gξk )(ξ(xi ) − gξk ) = ξ(xi )ξ(xi ) − 2ξ(xi )gξk + gξk gξk
(3.16)
Substituindo a expressão do protótipo 3.14 na expressão da distância 3.16 obtém-se:
2×
kξ(xi ) − gξk k2 = ξ(xi )ξ(xi ) −
(ukl )m ξ(xi )ξ(xl )
l∈Ck
P
+
(ukl )m
P
(uki )m (ukl )m ξ(xi )ξ(xl )
i∈Ck l∈Ck
P
(3.17)
(ukl )m )2
(
P P
l∈Ck
l∈Ck
Reformulando o produto interno em termos da função de
2×
kξ(xi ) − gξk k2 = K(xi , xi ) −
(ukl )m K(xi , xl )
l∈Ck
P
+
(ukl )m
P
Kernel, obtém-se:
(uki )m (ukl )m K(xi , xl )
i∈Ck l∈Ck
P
(
((ukl )m )2
P P
l∈Ck
(3.18)
l∈Ck
O esquema do algoritmo do McM-EC para intervalo é ilustrado a seguir:
1.
Etapa de Pre-processamento: denição do novo espaço de características
Calcule a matriz
j = 1, . . . , n.
K
utilizando uma função de
Kernel
apropriada para
i = 1, . . . , n
e
3.3 Métodos baseados em
2.
Kernel
para particionamento no espaço de entrada
Etapa de Inicialização: obtenção da partição inicial
Selecione (aleatoriamente) uma partição inicial
K
selecione
objetos distintos
yk∗ (k∗ = arg mink=1,...,K
y1 , . . . , yK
0
}
{C10 , . . . , CK
e associe cada objeto
Pp
j
j 2
j
j 2
j=1 (ai − αk ) + (bi − βk )
1, . . . , K)
em
i
Ω
de
K clusters
a uma classe
Ck∗
ou
tal que
para construir a partição inicial
0
{C10 , . . . , CK
}.
3.
43
Gere uma matriz de pertinência tal que a pertinência
k
P
do indivíduo i ao cluster Ck seja uki > 0 e
uki = 1.
i=1
uki (i = 1, . . . , n)(k =
Etapa de Alocação: denição da melhor partição e cálculo da pertinência
test ← 0
Para
i=1
até
n
faça
Calcule a pertinência através da Equação 3.15
dena o
cluster
k = arg
minj=1,...,K
Se
i ∈ Ck
e
vencedor
Ck∗
tal que
(uki )m kξ(xi ) − gξk k2
k 6= j
test ← 1
Ck ← Ck ∪ {i}
Cj ← Cj \ {i}
4.
Critério de Parada
Se
3.3
test = 0
então PARE, caso contrário vá para a etapa 3.
MÉTODOS BASEADOS EM KERNEL PARA PARTICIONAMENTO NO ESPAÇO DE ENTRADA
Nas subseções a seguir serão apresentados dois métodos K-médias usando funções de
kernel
no espaço de entradas para dados simbólicos do tipo intervalo. Neste contexto, são encontrados
os protótipos dos grupos no espaço de dados originais (espaço de entrada), e determinada a
distância entre os indivíduos e os protótipos por meio de funções de
Considere
ξ : xi → ξ(xi )
kernel.
uma função não linear que realiza um mapeamento do espaço de
entrada para um espaço de características de alta dimensão
z.
Considere também
K
centros
3.3 Métodos baseados em
Kernel
para particionamento no espaço de entrada
G = { g1 , . . . , gK }
no espaço de entradas do tipo intervalo
44
como protótipos dos grupos, onde
gk = ([αk1 , βk1 ], . . . , [αkp , βkp ]), ∀k = 1, . . . , K .
3.3.1
Método K-médias (MKM-EE)
O problema de agrupamento consiste em encontrar uma partição de
juntos
P ∗ = {C1 , . . . , CK }
de modo que a função objetivo
J3ξ (P, G) =
K X
X
J3ξ
Ω
em
K
grupos dis-
seja minimizada.
kξ(xi ) − ξ(gk )k2
(3.19)
k=1 i∈CK
A distância Euclidiana quadrática no espaço de características pode ser obtida da seguinte
maneira:
kξ(xi )−ξ(gk )k2 = (ξ(xi )−ξ(gk ))(ξ(xi )−ξ(gk )) = ξ(xi )ξ(xi )−2ξ(xi )ξ(gk )+ξ(gk )ξ(gk )
Reformulando o produto interno em termos da função de
(3.20)
Kernel, obtém-se:
kξ(yi ) − ξ(gk )k2 = K(xi , xi ) − 2K(xi , gk ) + K(gk , gk )
(3.21)
Para este caso o valor do protótipo é expresso por
P
K(xi , gk )xi
gk = Pi∈Ck
i∈Ck K(xi , gk )
(3.22)
Proposição 3.3.1 Os protótipos {g1 , . . . , gK } dos grupos CK , onde gk = (g1k , . . . g1p )(k =
1, . . . , K) com gjk = [αkj , βkj ](j = 1, . . . , p) que minimizam o critério J3ξ são atualizados de
acordo com a expressão 3.22.
Prova.
O problema é encontrar o
gk
que minimize a função
solução deste problema é encontrada derivando a função
a
gk .
J=
J3ξ .
P
Como o critério é aditivo, a
kξ(xi ) − ξ(gk )k2
em relação
i∈CK
A derivação dos protótipos depende da seleção da função de
kernel.
O Cálculo dos protóti-
3.3 Métodos baseados em
pos
gk
para
k = 1, . . . , K
Kernel
para o
para particionamento no espaço de entrada
kernel
Gaussiano procede-se da seguinte maneira:
∂J
=0
∂ gk
X ∂ kξ(xi ) − ξ(gk )k2 = 0
∂ gk
i∈Ck
X ∂
[2(1 − K(xi , gk ))] = 0
∂
g
k
i∈Ck
X ∂ −kxi − gk k2
−2 exp
=0
∂ gk
2σ 2
i∈Ck
X
−kxi − gk k2
2(xi − gk )
exp
=0
2
2
2σ
σ
i∈Ck
X
X
gk
K(xi , gk ) =
K(xi , gk )xi
i∈Ck
(3.23)
i∈Ck
P
K(xi , gk )xi
gk = Pi∈Ck
i∈Ck K(xi , gk )
O resultado demonstra que atualizando
nimo local) minimizando função
45
gk
(3.24)
pela equação 3.24 obtém um ponto crítico (mí-
J3ξ .
Proposição 3.3.2 A partição P , que minimiza o critério J3ξ , possui grupos C1 , . . . , Ck alterados
de acordo com a seguinte regra de alocação:
Ck = {i ∈ Ω : kξ(xi ) − ξ(gk )k2 ≤ kξ(xi ) − ξ(gm )k2
∀m 6= k} (m = 1, . . . , K)
Prova 1.
(3.25)
A prova da Proposição 3.3.2 é direta.
De acordo com (DIDAY; SIMON, 1976) as propriedades de convergência deste tipo de
algoritmo podem ser estudadas a partir de duas séries:
vt = (P t , Gt ) e ut = J3ξ (vt ) = J3ξ (P t , Gt ),
t = 0, 1, ...
A partir de um termo inicial
vt
v0 = (P 0 , G0 ), o algoritmo calcula os diferentes termos da série
até a convergência, quando o critério
J3ξ
alcança um valor estacionário.
Proposição 3.3.3 A série ut = J3ξ (v t ) decresce a cada iteração e converge.
Prova.
Primeiro vamos mostrar que as desigualdades (I) e (II) permanecem (ou seja, a
3.3 Métodos baseados em
Kernel
para particionamento no espaço de entrada
46
série decresce a cada iteração).
(I)
(II)
z}|{ ξ t t+1 z}|{ ξ t+1 t+1
≥ J3 (P , G ) ≥ J3 (P , G )
}
|
{z
}
J3ξ (P t , Gt )
{z
|
ut
ut+1
A desigualdade (I) permanece porque
J3ξ (P t , Gt )
=
K X
X
kξ(xi ) − ξ(gtk )k2
k=1 i∈C (t)
K
J3ξ (P t , Gt+1 )
=
K X
X
2
kξ(xi ) − ξ(gt+1
k )k
k=1 i∈C (t)
K
e de acordo com a Proposição 3.3.1,
gkt+1 = arg min
| {z }
g∈G
X
kξ(xi ) − ξ(gk )k2 (k = 1, . . . , K)
i∈Ckt
A desigualdade (II) permanece porque
J3ξ (P t+1 , Gt+1 )
=
K
X
X
2
kξ(xi ) − ξ(gt+1
k )k
k=1 i∈C (t+1)
K
e de acordo com a Proposição 3.3.2,
Ckt+1 = arg min
| {z }
X
2
kξ(xi ) − ξ(gt+1
k )k (k = 1, . . . , K)
C∈P (Ω) i∈C
Finalmente, porque a série
ut
decresce e é limitada
(J3ξ (vt ) ≥ 0),
então converge.
Proposição 3.3.4 A série vt = (P t , Gt ) converge.
Prova.
t = T.
Assumindo que a série
Então, temos que
A partir de
ut
uT = uT +1
J3ξ (vT ) = J3ξ (vT +1 ),
alcança o mínimo local (estado estacionário) na iteração
e então
J3ξ (vT ) = J3ξ (vT +1 )
temos que
J3ξ (P T , GT ) = J3ξ (P T +1 , GT +1 )
e esta igualdade,
de acordo com a proposição 3.3.3, pode ser reescrita como as igualdades (I) e (II):
(I)
(II)
ξ
T
T z}|{ ξ
T
T +1 z}|{ ξ
J3 (P , G ) = J3 (P , G ) = J3 (P T +1 , GT +1 )
A partir da igualdade (I), temos que
(e quando a partição
P
PT
é único minimizando
GT = GT +1
porque
G é único quando J3ξ
é xada). A partir da igualdade (II), temos que
J3ξ
quando o vetor de protótipos
GT +1
é xado.
é minimizado
P T = P T +1
porque
3.3 Métodos baseados em
Kernel
para particionamento no espaço de entrada
Finalmente, concluímos que
vt = vT , ∀t ≥ T
vT = vT +1 .
vt
e, portanto, a série
47
Esta conclusão permanece para todo
t ≥ T
e
converge.
O esquema do algoritmo do método MKM-EE para intervalo é ilustrado a seguir::
1.
Etapa de Pre-processamento
Calcule a matriz de
1, . . . , n
2.
K
Kernel
utilizando uma função de
kernel
apropriada para
i =
l = 1, . . . , n.
e
Etapa de Inicialização: obtenção da partição inicial
Selecione (aleatoriamente) uma partição inicial
selecione
K
objetos distintos
yk∗ (k∗ = arg mink=1,...,K
y1 , . . . , yK
0
{C10 , . . . , CK
}
e associe cada objeto
Pp
j
j 2
j
j 2
j=1 (ai − αk ) + (bi − βk )
i
em
Ω
de
K clusters
a uma classe
Ck∗
ou
tal que
para construir a partição inicial
0
{C10 , . . . , CK
}.
3.
Etapa de Representação: cálculo dos protótipos
Para
4.
k
de
1
até
K
obtenha
gk
Etapa de Alocação: denição da melhor partição
Atribua a cada elemento
xi
à classe
minimizando a função objetivo
5.
utilizando Eq. (3.22).
k
tal que a distância
kξ(xi ) − ξ(gk )k2
seja a menor
J3ξ
Critério de Parada
Caso nenhum elemento mude de classe então PARE; caso contrário vá para a etapa 3.
3.3.2
Método c-médias difuso (McM-EE)
Considere também
k,
uki ∈ [0, 1]
como o grau de pertinência de um indivíduo
i
a um grupo
onde a pertinência ou associação de um indivíduo para todos os grupos obedecem a seguinte
restrição:
k
P
uki = 1 ∀k = 1, . . . , n
(3.26)
i=1
O problema de agrupamento consiste em encontrar uma partição de
Ω em K
grupos difusos
3.3 Métodos baseados em
P ∗ = {C1 , . . . , CK }
Kernel
para particionamento no espaço de entrada
de modo que a função objetivo
J4ξ (P, G)
=
K X
X
J4ξ
48
seja minimizada.
(uki )m kξ(xi ) − ξ(gk )k2
(3.27)
k=1 i∈Ck
Para este caso o valor do protótipo é expresso por
P
(uki )m K(xi , gk )xi
gk = Pi∈Ck
m
i∈Ck (uki ) K(xi , gk )
(3.28)
A matriz de pertinência que obedece a restrição 3.26 é denida pela seguinte expressão
(GRAVES; PEDRYCZ, 2010):
u−1
ki
1
X 1 − K(xi , g ) m−1
k
=
.
1
−
K(
x
i , gj )
j∈C
(3.29)
k
Proposição 3.3.5 Os protótipos {g1 , . . . , gK } dos grupos CK , onde gk = (g1k , . . . g1p )(k =
1, . . . , K) com gjk = [αkj , βkj ](j = 1, . . . , p) que minimizam o critério J4ξ são atualizados de
acordo com a expressão 3.28.
Prova.
O problema é encontrar o
gk
solução deste problema é encontrada derivando a função
relação a
J4ξ . Como o critério é aditivo, a
P
J =
(uki )m kξ(xi ) − ξ(gk )k2 em
que minimize a função
i∈CK
gk .
A derivação dos protótipos depende da seleção da função de
pos
gk
para
k = 1, . . . , K
para o
kernel
kernel.
O Cálculo dos protóti-
Gaussiano procede-se da seguinte maneira:
∂J
=0
∂ gk
X ∂ k(uki )m ξ(xi ) − ξ(gk )k2 = 0
∂ gk
i∈Ck
X
∂
[2(1 − K(xi , gk ))] = 0
(uki )m
∂ gk
i∈Ck
X
−kxi − gk k2
m ∂
=0
(uki )
−2 exp
2
∂
g
2σ
k
i∈Ck
X
2(xi − gk )
−kxi − gk k2
m
=0
(uki ) exp
2
2
2σ
σ
i∈Ck
X
X
gk
(uki )m K(xi , gk ) =
(uki )m K(xi , gk )xi
i∈Ck
(3.30)
i∈Ck
P
m
i∈Ck (uki ) K(xi , gk )xi
gk = P
m
i∈Ck (uki ) K(xi , gk )
(3.31)
3.3 Métodos baseados em
Kernel
para particionamento no espaço de entrada
O resultado demonstra que atualizando
nimo local) minimizando função
gk
49
pela equação 3.31 obtém um ponto crítico (mí-
J4ξ .
Proposição 3.3.6 A pertinência uki de cada indivíduo i em cada grupo Ck minimiza o critério
k
P
J4ξ sob as seguintes restrições uki ≥ 0 e
uki = 1 é alterada de acordo com a expressão 3.29.
i=1
Prova.
J4ξ
A minimização de
em relação a
multiplicadores de Lagrange a cada termo
uki
pode ser obtida aplicando o método dos
uk .
Seja o lagrangiano:
L(P, G) =
K X
X
(uki ) kξ(xi ) − ξ(gk )k −
m
2
k=1 i∈Ck
Derivando
L
em relação a
uki
X
λi (1 −
K
X
i∈Ck
uki )
(3.32)
k=1
e igualando a zero, tem-se:
∂L
2
= mum−1
ki kξ(xi ) − ξ(gk )k − λi = 0
∂uki
então:
uki =
λi
mkξ(xi ) − ξ(gk )k2
A equação 3.33 pode ser reescrita utilizando um
uki =
k
P
(3.33)
kernel
λi
2m(1 − K(xi , gk ))
Substituindo a expressão 3.34 na restrição
1
m−1
Gaussiano:
1
m−1
uki = 1,
(3.34)
obtém-se:
i=1
k X
i=1
λi
2m(1 − K(xi , gk ))
1
m−1
=1
(3.35)
Com isso, obtemos os multiplicadores de Langrange:
"
λi =
k X
i=1
1
2m(1 − K(xi , gk ))
#1−m
1
m−1
(3.36)
Substituindo a equação 3.36 em 3.33, obtém-se a pertinência denida pela equação 3.29.
Assim como no método MKM-EE as propriedades de convergência deste tipo de algoritmo
podem ser estudadas a partir de duas séries:
A partir de um termo inicial
vt
vt = (P t , Gt ) e ut = J4ξ (vt ) = J4ξ (P t , Gt ), t = 0, 1, ...
v0 = (P 0 , G0 ), o algoritmo calcula os diferentes termos da série
até a convergência, quando o critério
J4ξ
alcança um valor estacionário.
3.3 Métodos baseados em
Kernel
para particionamento no espaço de entrada
50
Proposição 3.3.7 A série ut = J4ξ (v t ) decresce a cada iteração e converge.
Prova.
Primeiro vamos mostrar que as desigualdades (I) e (II) permanecem (ou seja, a
série decresce a cada iteração).
(I)
(II)
z}|{
z}|{
J4ξ (P t , Gt ) ≥ J4ξ (P t , Gt+1 ) ≥ J4ξ (P t+1 , Gt+1 )
|
| {z }
{z
}
ut
ut+1
A desigualdade (I) permanece porque
J4ξ (P t , Gt )
K X
X
=
(uki )m kξ(xi ) − ξ(gtk )k2
(t)
k=1 i∈C (t)
K
J4ξ (P t , Gt+1 )
=
K X
X
2
(uki )m kξ(xi ) − ξ(gt+1
k )k
(t)
k=1 i∈C (t)
K
e de acordo com a Proposição 3.3.5,
gkt+1 = arg min
| {z }
g∈G
(uki )m kξ(xi ) − ξ(gk )k2 (k = 1, . . . , K)
X
(t)
i∈Ckt
A desigualdade (II) permanece porque
J4ξ (P t+1 , Gt+1 )
K
X
X
=
2
) kξ(xi ) − ξ(gt+1
k )k
(t+1) m
(uki
k=1 i∈C (t+1)
K
e de acordo com a Proposição 3.3.6,
Ckt+1 = arg min
| {z }
X
2
(uki )m kξ(xi ) − ξ(gt+1
k )k (k = 1, . . . , K)
C∈P (Ω) i∈C
Finalmente, porque a série
ut
decresce e é limitada
(J4ξ (vt ) ≥ 0),
então converge.
Proposição 3.3.8 A série vt = (P t , Gt ) converge.
Prova.
t = T.
Assumindo que a série
Então, temos que
A partir de
ut
uT = uT +1
J4ξ (vT ) = J4ξ (vT +1 ),
alcança o mínimo local (estado estacionário) na iteração
e então
J4ξ (vT ) = J4ξ (vT +1 )
temos que
J4ξ (P T , GT ) = J4ξ (P T +1 , GT +1 )
e esta igualdade,
de acordo com a proposição 3.3.7, pode ser reescrita como as igualdades (I) e (II):
(I)
(II)
ξ
T
T z}|{ ξ
T
T +1 z}|{ ξ
J4 (P , G ) = J4 (P , G ) = J4 (P T +1 , GT +1 )
Kernel
3.3 Métodos baseados em
para particionamento no espaço de entrada
A partir da igualdade (I), temos que
(e quando a partição
P
PT
é único minimizando
porque
G é único quando J4ξ
é xada). A partir da igualdade (II), temos que
J4ξ
quando o vetor de protótipos
Finalmente, concluímos que
vt = vT , ∀t ≥ T
GT = GT +1
51
vT = vT +1 .
vt
e, portanto, a série
GT +1
é minimizado
P T = P T +1
porque
é xado.
Esta conclusão permanece para todo
t ≥ T
e
converge.
O esquema do algoritmo do método McM-EE é ilustrado a seguir:
1.
Etapa de Pre-processamento
Calcule a matriz de
1, . . . , n
2.
Kernel
K
utilizando uma função de
i =
Etapa de Inicialização: obtenção da partição inicial
selecione
K
objetos distintos
yk∗ (k∗ = arg mink=1,...,K
0
}.
{C10 , . . . , CK
y1 , . . . , yK
0
}
{C10 , . . . , CK
e associe cada objeto
Pp
j
j 2
j
j 2
j=1 (ai − αk ) + (bi − βk )
Os parâmetros
m (1 < m < ∞)
pertinência tal que a pertinência
k
P
Ck seja uki > 0 e
uki = 1.
i=1
e
ε>0
i
em
Ω
de
K clusters
a uma classe
Ck∗
ou
tal que
para construir a partição inicial
são xados. Gere uma matriz de
uki (i = 1, . . . , n)(k = 1, . . . , K) do indivíduo i ao cluster
Etapa de Representação: cálculo dos protótipos
Para
4.
apropriada para
l = 1, . . . , n.
e
Selecione (aleatoriamente) uma partição inicial
3.
kernel
k
de
1
até
K
obtenha
gk
utilizando Eq. (3.28).
Cálculo da matriz de pertinência
Atualize a matriz de pertinência
uik
para
(k = 1, . . . , K)
e
(i = 1, . . . , n)
com a Equação
(3.29)
5.
Critério de Parada
Caso
ξ
ξ
|J4(t+1)
− J4(t)
|≤ε
caso contrário faça
então PARE, calcule o critério
t=t+1
e vá para a etapa 3.
J4ξ
utilizando a Equação (3.27),
CAPÍTULO 4
APRESENTAÇÃO E ANÁLISE DOS RESULTADOS
Com o objetivo de validar os métodos propostos para dados do tipo intervalo, foram realizados
experimentos com conjuntos de dados simbólicos intervalares sintéticos e conjunto de dados
reais do tipo intervalo. Os conjuntos de dados articiais ou sintéticos foram gerados com diferentes graus de diculdade de classicação com grupos de formas e tamanhos diferentes e com
conjuntos que apresentam elementos dispostos de maneira não-linear, para que os experimentos
possam fornecer resultados referentes à eciência dos métodos em encontrar partições de dados
não-linearmente separáveis no espaço de entrada.
A avaliação dos resultados de classicação fornecidos pelos métodos foi baseada em índice
de validação externo e interno (GORDON, 1999): índice corrigido de Rand (CR) (HUBERT;
ARABIE, 1985) e índice de Davies e Bouldin (DB) (NASSER; HAMAD, 2007).
Para cada
conjunto de dados articiais o índice de validação é estimado no quadro de uma experiência
Monte Carlos com 100 replicações. A nalidade da aplicação do método Monte Carlo é propiciar
uma melhor avaliação quantitativa do desempenho dos métodos considerando situações com
diferentes graus de diculdades de classicação.
A primeira seção descreve as métricas utilizada para avaliação dos métodos de agrupamento,
a segunda seção descreve uma heurística para ajuste do parâmetro
σ
do Kernel Gaussiano
realizados durante a fase de experimentação, a terceira seção descreve os conjuntos de dados
utilizados na avaliação e as seções seguintes apresentam os resultados e a discussões sobre os
experimentos realizados.
4.1
CÁLCULO DO ÍNDICE DE VALIDAÇÃO
Para determinar se os grupos formados são signicativos o resultado do processo de agru-
pamento é validado para aferir a qualidade da solução encontrada. A validação dos grupos é
4.1 Cálculo do Índice de Validação
53
uma etapa muito importante no processo de análise de agrupamento, pois diferentes abordagens
de agrupamentos podem levar a formação de diferentes grupos. Além disso, para um mesmo
algoritmo a identicação dos parâmetros ou a ordem de apresentação dos padrões de entrada
podem afetar o resultado nal. Portanto, a denição de critérios e padrões de avaliação é importante para fornecer aos usuários certo grau de conança nos resultados dos agrupamentos
obtidos a partir de seus algoritmos. As avaliações devem ser objetivas e não devem privilegiar
nenhum algoritmo.
Esta avaliação pode ser baseada, de um modo geral, em índices de vali-
dação externo e interno. Um índice externo é usado para comparar a estrutura de classes obtida
por um agrupamento com uma estrutura previamente denida e um índice interno determina
se a estrutura do agrupamento está apropriada aos dados. Maiores detalhes sobre os índices
de validação podem ser encontrados em (GORDON, 1999). As seções seguintes descrevem os
dois índices (um externo e outro interno) utilizados neste trabalho para realizar o processo de
validação dos métodos de agrupamentos.
4.1.1
Índice Corrigido de Rand (CR)
A avaliação dos resultados de classicação fornecidos pelos métodos foi baseada em um
índice de validação externo conhecido como índice de Rand corrigido (CR) (HUBERT; ARABIE, 1985). A ideia deste índice é simplesmente de medir o grau de similaridade entre uma
partição a priori e uma partição fornecida pelo algoritmo de agrupamento.
Este índice foi
escolhido por não ser sensível ao número de classes e nem as distribuições dos elementos nas
classes.
Considere
U = {u1 , . . . , ui , . . . , uR }
agrupamento e
uma partição dada como resultado de um método de
V = {v1 , . . . , vj , . . . , vC }
a partição a priori, sendo as duas partições de um
mesmo conjunto de dados tendo, respectivamente,
R
e
C
grupos. O índice de Rand é denido
como:
nij
n −1 PR
ni. PC
n.j
i=1 2
j=1 2
i=1
j=1 2 − 2
PR ni. PC n.j n −1 PR
ni. PC
n.j
1
]
−
[
+
i=1 2
j=1 2
i=1 2
j=1 2
2
2
PR PC
CR =
onde
n
2
=
n(n−1)
e
2
nij
representa o número de objetos que estão nas classes
o número de objetos no grupo
ui ; n.j
indica o número de objetos no grupo
total de objetos do conjunto de dados.
(4.1)
ui
vj ;
e
e
vi ; ni.
n
indica
é o número
4.2 Considerações sobre o Kernel Gaussiano
54
O índice CR pode assumir valores no intervalo de
[−1, 1].
O valor 1 indica uma perfeita
combinação entre as partições comparadas. Em outras palavras, quanto mais próximo de 1,
melhor o processo de classicação e, consequentemente maior a similaridade entre os grupos
avaliados; quanto mais próximo de 0 (ou em caso de valores negativos) menor a similaridade
entre os grupos.
4.1.2
Índice de Davies e Bouldin (DB)
O índice de Davies e Bouldin (DB) é uma medida que indica a similaridade entre agrupamentos. Esta medida pode ser usada para a avaliação da partição dos dados e, consequentemente,
para a comparação entre diferentes grupos formados em um conjunto de dados. Este índice é
independente do número de agrupamentos e do método de particionamento dos dados, o que o
torna indicado para a avaliação de algoritmos de particionamento de dados.
O índice DB é uma função que calcula a razão entre a soma da dispersão dentro dos grupos
pela dispersão entre os grupos.
O cálculo do índice DB pode ser determinado pela equação
(4.2). O valor resultante do índice decresce conforme a qualidade da partição aumenta.
K
1 X
δi + δj
DB =
max
K k=1
d(ci , cj )
onde
K ≥ 1, δi
entre os grupos
ci
e
(4.2)
( e
δj )
cj .
Aqui, a dispersão intra-grupo é minimizada e a separação inter-grupo
representa a dispersão no grupo e
d(ci , cj )
representa a distância
é maximizada.
Como a dispersão intra-grupo e inter-grupo representam funções de distância é possível
associá-las a um
kernel
4.2
kelnel,
portanto este trabalho considera o cálculo do índice DB baseado em
conforme apresentado em (NASSER; HAMAD, 2007).
CONSIDERAÇÕES SOBRE O KERNEL GAUSSIANO
Como ilustrado no capítulo anterior, o
Kernel
Gaussiano ou função RBF, é representada
neste trabalho pela equação 4.3 de duas componentes a seguir:
K(xi , xl ) = exp(
−kxiI − xlI k2
−kxiS − xlS k2
)
+
exp(
)
2σ 2
2σ 2
(4.3)
4.2 Considerações sobre o Kernel Gaussiano
55
Esta função representa a similaridade Gaussiana entre os vetores de intervalo e tem sido utilizada amplamente em diversos trabalhos (DHILLON; GUAN; KULIS, 2004). Um parâmetro
importante nesta função é o
σ
(sigma).
A partir de outros trabalhos (FILIPPONE et al.,
2008)(GRAVES; PEDRYCZ, 2010) é possível identicar que a escolha desse parâmetro é importante e pode inuenciar no comportamento da função, e consequentemente dos métodos que
a utilizam.
Por questão de simplicidade, tipicamente, assume-se o valor do parâmetro
σ
como uma
constante. No entanto, existem na literatura algumas abordagens para ajustar o valor desse
parâmetro no
Kernel
Gaussiano na busca de similaridades e baseado nas características do
conjunto de dados (BRAND; HUANG, 2003) (ZELNIK-MANOR; PERONA, 2004).
Neste trabalho uma abordagem foi considerada para computar o valor do parâmetro
Nesta abordagem o
σ.
σ foi calculado considerando os indivíduos que compõe o conjunto de dados,
especicamente os indivíduos pertencentes a um grupo. Através da equação 4.4, observa-se que
a computação do parâmetro
σk
baseia-se em duas componentes (limites inferior e superior dos
intervalos):
vP
vP
u
u
d
dS
u
u
I
t i∈Ck
t i∈Ck
σk =
+
nk
nk
onde
nk
o número de indivíduos pertencente ao grupo
k.
(4.4)
As funções
dI
e
dS
representam a
distância Euclidiana quadrática no espaço de características entre um indivíduo e o centro do
grupo para a componente do limite inferior e superior, respectivamente. Desta forma, podemos
reescrever a equação 4.3 da seguinte maneira:
K(xi , xl ) = exp(
−kxiI − xlI k2
−kxiS − xlS k2
)
+
exp(
)
2σk2
2σk2
(4.5)
É importante destacar que essa abordagem foi adotada de maneira empírica e intuitiva,
levando em consideração, no conjunto de dados utilizado, a distância entre os elementos dos
grupos e seus protótipos. Essa computação não leva em conta um critério de otimização, em
outras palavras, ela não calcula um valor ótimo do parâmetro
σ (se trata de uma heurística).
No
entanto, o seu cálculo não é aleatório, pois a equação 4.4 considera três aspectos importante: os
indivíduos pertencentes aos grupos, a distância entre esses indivíduos e os centros dos grupos e
a variação entre esses elementos (caracterizada pela raiz quadrada). A intuição dessa heurística
é que esses aspectos combinados podem inuenciar positivamente na denição deste parâmetro,
4.3 Experimentos e Resultados
56
e consequentemente o desempenho das técnicas que a utilizam.
4.3
EXPERIMENTOS E RESULTADOS
Esta seção apresenta os experimentos realizados juntamente com os resultados e discussões.
Como mencionado no início deste capítulo, foram realizados experimentos utilizando conjunto
de dados sintéticos e conjunto de dados reais. Os resultados dos experimentos para os métodos
propostos no capítulo anterior serão comparados métodos de agrupamento para dados simbólicos intervalares amplamente aceitos na literatura de Análise de Dados Simbólicos: Método
Adaptive Dynamic Cluster )
de Agrupamento Dinâmico com distância adaptativa por classe (
- DAC, Método de Agrupamento Dinâmico com distância adaptativa única (
Single Adaptive
Dynamic Cluster ) - DAU e Método de Agrupamento Dinâmico Difuso c-médias com distância
adaptativa - FCMA.
Os resultados serão apresentados nas seções seguintes para os conjuntos de dados sintéticos
e conjunto de dados reais.
4.3.1
Conjunto de Dados Sintéticos
Para realizar os experimentos com dados sintéticos, foi implementado um sistema de
cluster
na linguagem C++ que apresenta duas grandes etapas: a simulação de dados do tipo intervalo e
o cálculo do índice de validação. Como já mencionado, as etapas deste sistema são organizadas
no quadro de uma experiência Monte Carlo. 100 replicações são consideradas para cada conjunto de dados de intervalo. A média do índice dos índices CR (HUBERT; ARABIE, 1985) e
DB são calculadas entre estas 100 replicações. Em cada replicação um método de agrupamento
é executado 150 vezes e o melhor resultado, de acordo com o critério do método em questão, é
selecionado. O experimento de Monte Carlo foi executado na maneira especicada no algoritmo
a seguir.
1.
Etapa inicial
Determine o número de replicações
Determine o número de grupos
K
R
do conjunto de dados;
desejadas no conjunto de dados;
4.3 Experimentos e Resultados
57
Determine parâmetros especícos para cada grupo do conjunto de dados para
k = 1, . . . , K ,
por exemplo, médias e variâncias;
Determine o número de indivíduos em cada grupo
Escolha o algoritmo de agrupamento
Determine os parâmetros
P
A
nk
para
k = 1, . . . , K ;
a ser aplicado no conjunto de dados;
necessários ao algoritmo de agrupamento escolhido;
Determine os índices de validação
I
a serem medidos após a execução do algoritmo de
agrupamento;
2.
Para r = 1 até R faça
Crie uma replicação aleatória
r
do conjunto de dados contendo
Execute o algoritmo de agrupamento
A
passando a replicação
K
r
grupos;
e os demais parâmetros
P;
Colete os índices de validação
I
e armazene-os;
m para
3.
Calcule a média e o desvio padrão dos índices de validação I
4.
retorne Média e desvio padrão calculada no passo anterior.
e armazene-os;
Os conjuntos de dados sintéticos do tipo intervalo foram gerados considerando cada ponto
(y1 , y2 ) como uma semente de um vetor de intervalos (retângulos) denidos por: ([y1 −γ1 /2, y1 +
γ1 /2], [y2 − γ2 /2, y2 + γ2 /2]).
Estes parâmetros
tir de um mesmo intervalo predenido.
[1, 5], [1, 10], [1, 15]
e
γ1
e
γ2
são selecionados aleatoriamente a par-
Os intervalos considerados nestes experimentos são:
[1, 20].
Neste trabalho foram utilizados três conjuntos de dados sintéticos que serão apresentados
nas subseções seguintes. Os resultados serão apresentados primeiramente para os algoritmos
de agrupamento rígidos e em seguida para os métodos difusos.
Conjunto de Dados 1
A Figura 4.1 ilustra um conjunto com 225 indivíduos distribuídos em entre quatro classes
de tamanhos e formas diferentes. O conjunto de dados intervalares foi gerado de acordo com
os seguintes parâmetros:
4.3 Experimentos e Resultados
58
a) Classe 1:
µ1 = 28, µ2 = 23, σ12 = 144, σ22 = 16
b) Classe 2:
µ1 = 62, µ2 = 30, σ12 = 81, σ22 = 49
e
ρ12 = 0;
c) Classe 3:
µ1 = 50, µ2 = 15, σ12 = 49, σ22 = 81
e
ρ12 = 0;
c) Classe 4:
µ1 = 57, µ2 = 48, σ12 = 16, σ22 = 144
Figura 4.1.
e
e
ρ12 = 0;
ρ12 = 0;
Conjunto de Dados 1 do tipo Intervalo com classes de tamanho e forma diferentes
Este conjunto é uma conguração típica utilizado na validação de métodos de agrupamento
de dados intervalares e pode ser encontrada em (CARVALHO; LECHEVALLIER, 2009a). Os
parâmetros
µ1
e
µ2
representam médias e os parâmetros
σ12
e
σ22
as variâncias. A manipulação
das médias alteram a separação dos grupos (separadas ou sobrepostas), enquanto que a manipulação das variâncias inuenciam nas formas dos grupos (elípticas ou circulares). Neste caso,
o conjunto de dados apresenta grupos com tamanhos e formas diferentes e classes separadas.
Conjunto de Dados 2
A Figura 4.2 ilustra um conjunto de dados, onde os dados seguem a formação semelhante
a espirais arquimedianas, onde cada braço da espiral é denida em coordenadas polares
(r, θ)
pela equação:
r = a + bθ
números reais e
θ
em medidas angulares. O parâmetro
enquanto que o parâmetro
b
está relacionado a distância entre os sucessivos giros. Seguindo
sendo
a
e
b
(4.6)
a
controla o giro da espiral,
4.3 Experimentos e Resultados
59
esse padrão, foi criado um conjunto de dados simbólicos com quatro classes.
Este conjunto
possui 90 indivíduos distribuídos entre as classes contendo 15, 20, 25 e 30, com ângulo total
θ = 120
graus, sendo tendo
Figura 4.2.
a = 10
e
b = 5.
Conjunto de Dados 2 do tipo Intervalo com quatro classes
Conjunto de Dados 3
A Figura 4.3 ilustra um conjunto de dados com três classes que contém 30, 40 e 20 indivíduos
em cada classe. É fácil perceber que trata-se de um conjunto onde a disposição de grupos é
não linear.
Figura 4.3.
Conjunto de Dados 3 do tipo Intervalo com três classes dispostos de maneira não linear
Conjunto de Dados 4
A Figura 4.4 ilustra um conjunto de dados, onde os dados seguem a formação semelhante
a espirais arquimedianas, onde cada braço da espiral é denida em coordenadas polares
(r, θ)
4.3 Experimentos e Resultados
60
pela equação:
r = a + bθ
números reais e
θ
em medidas angulares. O parâmetro
enquanto que o parâmetro
b
está relacionado a distância entre os sucessivos giros. Seguindo
sendo
a
e
b
(4.7)
a
controla o giro da espiral,
esse padrão, foi criado um conjunto de dados simbólicos com duas classes. Este conjunto possui
80 indivíduos distribuídos entre as classes contendo 30 e 50, com ângulo total
sendo tendo
a = 10
e
θ = 260
graus,
b = 5.
Figura 4.4.
Conjunto de Dados 4 do tipo Intervalo com quatro classes
Conjunto de Dados 5
A Figura 4.5 ilustra um conjunto de dados, onde os dados seguem a formato senoidal.
Seguindo esse padrão, foi criado um conjunto de dados simbólicos com duas classes.
conjunto possui 100 indivíduos distribuídos entre as classes cada uma 50 indivíduos.
Figura 4.5.
Conjunto de Dados 5 do tipo Intervalo com quatro classes
Este
4.3 Experimentos e Resultados
4.3.1.1
61
Análise dos resultados para as funções de
kernel
de uma e duas compo-
nentes
Nesta seção serão apresentados os resultados de experimentos realizados, com os conjuntos
de dados 1 a 5 ilustrados na seção anterior, para os métodos de agrupamento com abordagem
rígida considerando os dois tipos de funções de
kernel apresentados no capítulo 3.
Como exposto
no capítulo anterior estes métodos utilizam a metodologia K-médias e são baseadas na aplicação
de funções de
kernel
para intervalos.
Conforme apresentado no capítulo 3, neste trabalho, foram considerados, inicialmente, duas
funções de
de
kernel
kernel,
uma que considera o intervalo como informação única, chamada de função
de uma componente e outra que considera o intervalo (seu limite inferior e superior)
como duas informações separadas, denominada de função de
kernel
de duas componentes.
A primeira parte deste trabalho realiza uma comparação do desempenho dos métodos rotulados como MKM-EC considerando os dois tipos de
kernels
citados. Esta avaliação tem como
base uma adaptação do índice de validação interno de Davies e Bouldin proposto em (NASSER;
HAMAD, 2007).
As guras 4.6 a 4.10 apresentam os resultados para os conjunto de dados de 1 a 5, respectivamente. A avaliação considerou as funções de
Os grácos ilustram o índice DB
intervalo pre-denido
[1, 5],
agrupamento baseado em
Figura 4.6.
Kernel
kernel
RBF denidas pelas equações 3.1 e 3.2.
em função do parâmetro
σ
da função RBF para um
e apresentam o desempenho do método MKM-EC que considera o
kernel
no espaço de características.
DB Kernel x sigma (σ ) para conjunto de dados 1 utilizando método MKM-EC
4.3 Experimentos e Resultados
Figura 4.7.
DB Kernel x sigma (σ ) para conjunto de dados 2 utilizando método MKM-EC
Figura 4.8.
DB Kernel x sigma (σ ) para conjunto de dados 3 utilizando método MKM-EC
Figura 4.9.
DB Kernel x sigma (σ ) para conjunto de dados 4 utilizando método MKM-EC
62
4.3 Experimentos e Resultados
Figura 4.10.
DB
63
Kernel x sigma (σ) para conjunto de dados 5 utilizando método MKM-EC
É possível observar que, nos cinco grácos apresentados, com a variação do parâmetro sigma,
o índice DB
Kernel
é menor quando o método MKM-EC utiliza uma função de
kernel
componentes. Pela interpretação deste índice, um menor valor do DB indica que o
de duas
kernel
de
duas componentes fornece uma melhor qualidade no processo de agrupamento. Os valores absolutos do índice DB para os resultados apresentados podem ser encontrados no apêndice A.
O método com agrupamento rígido no espaço de entradas, rotulado como MKM-EE, obteve
na maioria dos casos valores de índice DB menores para o
kernel
de duas componentes com-
parados com a função de uma componente. Portanto, para avaliação e validação dos métodos
apresentados nesta Tese os resultados irão considerar o uso de funções de
kernel
com duas
componentes.
4.3.1.2
Resultados dos métodos de agrupamento com abordagem rígida (hard )
considerando o parâmetro
sigma xo
A tabela 4.1 apresenta os resultados da execução dos métodos de agrupamento para o
conjunto de dados 1 com base no índice CR para diferentes valores de intervalo.
Para cada
valor do índice CR, é apresentado, entre parêntesis, o valor do desvio padrão. Este conjunto
foi escolhido por ser um tipo de conguração comumente utilizada na validação de métodos de
agrupamento para intervalos, como encontradas em (SOUZA, 2003)(CARVALHO, 2007)(CARVALHO; LECHEVALLIER, 2009b) e também no intuito de mostrar que os métodos da literatura utilizados neste trabalho são ecazes neste tipo de cenário e úteis para realização do
4.3 Experimentos e Resultados
64
estudo comparativo com os métodos propostos neste trabalho.
Tabela 4.1. Resultado do Índice CR para os métodos de agrupamento baseado em Kernel (rígido) e métodos
adaptativos (a direita): Conjunto de Dados 1 com 4 classes.
Intervalo
MKM-EC
(σ = 7)
MKM-EE
(σ = 7)
Intervalo
DAU
DAC
[1, 5]
0.485
(0.064)
0.508
(0.059)
[1, 5]
0.620
(0.040)
0.612
(0.048)
[1, 10]
0.491
(0.063)
0.524
(0.062)
[1, 10]
0.623
(0.042)
0.615
(0.038)
[1, 15]
0.510
(0.063)
0.513
(0.065)
[1, 15]
0.611
(0.039)
0.605
(0.045)
[1, 20]
0.508
(0.070)
0.527
(0.058)
[1, 20]
0.612
(0.045)
0.599
(0.055)
Observa-se pela Figura 4.6 que o nível de diculdade para classicação neste cenário é
intermediário, visto que é possível perceber a separação entre os grupos e uma leve sobreposição
entre eles. Como esperado, neste cenário os métodos adaptativos apresentam, em relação ao
índice CR, valores superiores aos métodos com o uso de funções de
kernel.
Este resultado
é aceitável, pois os métodos adaptativos são mais apropriados em situações onde os grupos
apresentem formas e tamanhos diferentes e onde a separabilidade linear é possível.
Tabela 4.2. Resultado do Índice CR para os métodos de agrupamento baseado em Kernel (rígido) e métodos
adaptativos (a direita): Conjunto de Dados 2 com 4 classes.
Intervalo
MKM-EC
(σ = 6)
MKM-EE
(σ = 6)
Intervalo
DAU
DAC
[1, 5]
0.305
(0.010)
0.359
(0.027)
[1, 5]
0.103
(0.032)
0.138
(0.016)
[1, 10]
0.288
(0.017)
0.356
(0.029)
[1, 10]
0.098
(0.053)
0.136
(0.014)
[1, 15]
0.275
(0.032)
0.359
(0.029)
[1, 15]
0.092
(0.057)
0.141
(0.016)
[1, 20]
0.273
(0.025)
0.363
(0.026)
[1, 20]
0.095
(0.060)
0.139
(0.022)
A tabela 4.2 apresenta os resultados da execução dos métodos de agrupamento para o
conjunto de dados 2 com base no índice CR para diferentes valores de intervalo. Este conjunto
de dados apresenta uma disposição não linear dos dados, onde cada grupo é caracterizado
pelos braços das espirais.
Observando esta tabela, nota-se que, em relação ao índice CR, o
desempenho dos métodos baseados em funções de
kernel
MKM-EC e MKM-EE foi superior
quando comparados com os métodos adaptativos (DAU e DAC). Este resultado é esperado,
4.3 Experimentos e Resultados
Figura 4.11.
65
(a)
(b)
(c)
(d)
Conjunto de Dados 2 com as variações de intervalo: (a) [1,5], (b) [1,10], (c) [1,15], e (d) [1,20].
devido a característica não linear do conjunto de dados, mas também é um resultado importante
porque auxilia na validação do comportamento dos métodos baseados em funções de
kernel
neste tipo de cenário.
Comparando os métodos que utilizam funções de
kernel
entre si, o desempenho do método
MKM-EE foi superior ao método MKM-EC. Este resultado reforça a importância da identicação dos representantes (protótipos) dos grupos para se obter um melhor grau de exatidão
no processo de classicação. Outra observação é que o método MKM-EE foi menos sensível
a variação do intervalo comparado ao método MKM-EC. Esse comportamento é interessante,
pois o aumento do tamanho dos intervalos, por exemplo,
[1, 5]
para
[1, 20],
pode inuenciar na
4.3 Experimentos e Resultados
66
própria estrutura dos dados e consequentemente dos seus respectivos grupos, o que pode dicultar o processo de agrupamento. Observando as guras 4.11(a)-(d), é possível perceber como
a variação dos intervalos interferem na estrutura dos braços das espirais e do conjunto de dados
como um todo. No caso especíco do intervalo
[1, 20] percebe-se uma grande sobreposição entre
os grupos. Mesmo assim, o método MKM-EE conseguiu obter um desempenho semelhante ou
até mesmo superior (para o intervalo
[1, 20])
mesmo com a variação dos intervalos.
Tabela 4.3. Resultado do Índice CR para os métodos de agrupamento baseado em Kernel (rígido) e métodos
adaptativos (a direita): Conjunto de Dados 3 com 3 classes.
Intervalo
MKM-EC
(σ = 7)
MKM-EE
(σ = 7)
Intervalo
DAU
DAC
[1, 5]
0.368
(0.040)
0.178
(0.018)
[1, 5]
0.008
(0.023)
0.015
(0.011)
[1, 10]
0.359
(0.039)
0.179
(0.018)
[1, 10]
0.011
(0.027)
0.013
(0.013)
[1, 15]
0.350
(0.043)
0.179
(0.018)
[1, 15]
0.012
(0.035)
0.018
(0.015)
[1, 20]
0.338
(0.045)
0.175
(0.017)
[1, 20]
0.011
(0.013)
0.010
(0.016)
A tabela 4.3 apresenta os resultados da execução dos métodos de agrupamento para o
conjunto de dados 3 com base no índice CR para diferentes valores de intervalo. Este conjunto
de dados, assim como o anterior, apresenta uma disposição não linear dos dados formado por
três grupos, onde dois deles tem um formato semelhante e um aspecto semelhante a um semicírculo e um terceiro grupo deslocado a esquerda e com um formato que o difere dos demais.
É possível perceber que é um conjunto de difícil reconhecimento dos grupos. Observando esta
tabela, nota-se que, em relação ao índice CR, o desempenho dos métodos baseados em funções
de
kernel
MKM-EC e MKM-EE novamente foi superior quando comparados com os métodos
adaptativos (DAU e DAC), que obtiveram valores próximos a zero. Este resultado reforça a
utilidade e a melhor adequação dos métodos propostos neste tipo de cenário.
Desta vez, para o conjunto de dados 3, o desempenho dos métodos MKM-EC foi superior
ao MKM-EE, diferentemente dos resultados apresentados para os conjuntos de dados 1 e 2.
Isso demonstra que a mudança de espaço de características para realização do agrupamento é
um mecanismo útil na identicação de grupos não lineares.
A natureza dos dados pode ter
inuenciado neste resultado inferior do método MKM-EE. A tendência é que em conjunto de
dados onde o nível de separação entre os grupos seja mais complexo, o agrupamento no espaço
4.3 Experimentos e Resultados
67
de características seja mais viável.
Tabela 4.4. Resultado do Índice CR para os métodos de agrupamento baseado em Kernel (rígido) e métodos
adaptativos (a direita): Conjunto de Dados 4 com 2 classes.
Intervalo
MKM-EC
(σ = 7)
MKM-EE
(σ = 7)
Intervalo
DAU
DAC
[1, 5]
0.402
(0.122)
0.181
(0.028)
[1, 5]
−0.045
(0.018)
−0.063
(0.014)
[1, 10]
0.398
(0.118)
0.177
(0.027)
[1, 10]
−0.041
(0.020)
−0.064
(0.015)
[1, 15]
0.393
(0.126)
0.179
(0.028)
[1, 15]
−0.041
(0.018)
−0.065
(0.014)
[1, 20]
0.401
(0.142)
0.183
(0.028)
[1, 20]
−0.042
(0.021)
−0.071
(0.016)
A tabela 4.4 apresenta os resultados da execução dos métodos de agrupamento para o
conjunto de dados 4 com base no índice CR para diferentes valores de intervalo. Este conjunto
de dados se assemelha ao conjunto de dados 2, apresenta uma disposição não linear dos dados
formado por dois grupos, no entanto, é possível perceber que é um conjunto de dados com
um nível de classicação mais difícil.
Observando esta tabela, nota-se que, em relação ao
índice CR, o desempenho dos métodos baseados em funções de
kernel
MKM-EC e MKM-
EE foram superiores quando comparados com os métodos adaptativos (DAU e DAC), que
apresentaram inclusive valores negativos. Este é mais um resultado que reforça a utilidade e a
melhor adequação dos métodos propostos neste tipo de cenário.
Tabela 4.5. Resultado do Índice CR para os métodos de agrupamento baseado em Kernel (rígido) e métodos
adaptativos (a direita): Conjunto de Dados 5 com 2 classes.
Intervalo
MKM-EC
(σ = 5)
MKM-EE
(σ = 5)
Intervalo
DAU
DAC
[1, 5]
0.882
(0.142)
0.434
(0.325)
[1, 5]
−0.229
(0.214)
0.089
(0.052)
[1, 10]
0.838
(0.135)
0.456
(0.304)
[1, 10]
−0.172
(0.274)
−0.289
(0.174)
[1, 15]
0.833
(0.113)
0.501
(0.282)
[1, 15]
−0.179
(0.271)
−0.318
(0.188)
[1, 20]
0.743
(0.129)
0.461
(0.309)
[1, 20]
−0.226
(0.221)
−0.342
(0.118)
Assim como no conjunto de dados 3, o comportamento dos métodos MKM-EC e MKM-EE
foi semelhante quando comparados entre si. O método MKM-EC foi superior ao MKM-EE em
relação ao índice CR. Novamente, a natureza do conjunto de dados inuenciou no resultado,
4.3 Experimentos e Resultados
68
favorecendo o método MKM-EC para o cenário onde o nível de diculdade de separação dos
grupos é maior.
A tabela 4.5 apresenta os resultados da execução dos métodos de agrupamento para o
conjunto de dados 5 com base no índice CR. Este conjunto de dados apresenta classes em
um formato semelhante a uma função senoidal. Apesar desse conjunto apresentar grupos bem
separados, a distribuição dos indivíduos diculta a separação linear dos elementos, o que torna
o conjunto interessante para avaliação dos métodos estudados nesse trabalho. Observando esta
tabela, nota-se que, em relação ao índice CR, o desempenho dos métodos MKM-EC e MKMEE foram superiores quando comparados com os métodos adaptativos (DAU e DAC). Nota-se
também que os métodos MKM-EC e MKM-EE, principalmente o primeiro, foi menos sensível
a variação dos intervalos, o que é um comportamento interessante, pois a variação no intervalo
afeta a distribuição dos indivíduos no conjunto e em alguns casos pode afetar a qualidade dos
agrupamentos formados.
Este resultado também reforça a validação dos métodos propostos
neste trabalho. Mais uma vez, o método MKM-EC foi superior ao método MKM-EE, o que
reforça a intuição de que os métodos no espaço de características são mais apropriados para
classicar conjuntos de dados mais complexos.
4.3.1.3
Resultados dos métodos de agrupamento considerando o parâmetro sigma
xo e calculado
No estudo comparativo dos métodos baseados em função de
kernel
para intervalos e os
métodos adaptativos da literatura de ADS realizados na seção anterior, a função
foi utilizada considerando o parâmetro
σ
como um valor xo.
Gaussiana
Em geral, este parâmetro é
atribuído de maneira arbitrária. No entanto, a variação desse parâmetro pode afetar o processo
de agrupamento, como observado na seção 4.3.1.1 com os valores do índice DB e em outros
trabalhos da literatura.
Nos experimentos aqui realizados, a determinação do valor parâmetro
σ
adotou duas abor-
dagens. A primeira (aqui chamada de DBSig) considerou a escolha do parâmetro
σ
xo, mas
não arbitrário, e sim, com base na análise dos valores do índice DB. A segunda (aqui chamada
de CLSig) considera a computação do valor do
σ
com base no conjunto de dados utilizado e
4.3 Experimentos e Resultados
69
variando durante a execução do algoritmo de agrupamento.
Como mencionado, as tabelas 4.1 a 4.5 da seção anterior, apresentaram os resultados dos
métodos MKM-EC e MKM-EE para os conjuntos de dados 1 a 5 considerando o
sigma com um
valor constante. No entanto, a escolha do valor deste parâmetro não foi arbitrária, a escolha
foi baseada no valores ou na variação do índice DB calculado para cada
sigma
atribuído. Para
auxiliar o entendimento na determinação deste parâmetro, a gura 4.12 ilustra os valores do
índice DB
Kernel
em função do parâmetro
sigma
da função RBF para as quatro variações de
intervalo no conjunto de dados 1. Com base nestes valores o parâmetro
neste caso foi escolher o valor de
sigma
DB
foi escolhido. A ideia
onde a variação do índice DB é considerada pequena
para todos os intervalos, levando em conta o valor do índice DB para o
Figura 4.12.
σ
sigma atual e o anterior.
Kernel x sigma (σ) para conjunto de dados 1 utilizando método MKM-EC
Observando o gráco ilustrado na gura 4.12, as maiores variações no índice DB ocorrem
nos
sigmas
de 1 a 4, e depois disso os valores do índice DB tendem a apresentar uma variação
pequena ou até mesmo estabilizar. Neste trabalho consideramos uma variação pequena aquela
que é menor que 1 (∆DB
< 1).
Por esta razão o valor de
σ=7
foi escolhido para o método
MKM-EC no conjunto de dados 1 (Tabela 4.1). A mesma análise foi realizada para os demais
conjuntos de dados considerando o método de agrupamento no espaço de características. Para
o método MKM-EE (espaço de entradas) optou-se pela escolha do mesmo valor do
σ
do MKM-
EC para ns de comparação e também devido ao fato dos métodos terem sido menos sensíveis
a variação do
sigma
considerando a medida do índice DB. Assim mesmo, para estes casos
4.3 Experimentos e Resultados
70
as variações do índice DB consideradas foram menor que 1. É importante salientar que esta
variação pequena, pode ser adotada de maneira diferente dependendo da natureza do conjunto
de dados ou do método de agrupamento. Por exemplo, esta variação pode ser considerada em
termos percentuais ou até mesmo em valores absolutos de acordo com a observação do índice.
Resultado do Índice CR para os métodos de agrupamento baseado em
DBSig: Conjunto de Dados 3 com 3 classes.
Tabela 4.6.
Kernel
Intervalo
MKM-EC
(σ = 1)
MKM-EC
(DBSig)
Intervalo
MKM-EE
(σ = 1)
MKM-EE
(DBSig)
[1, 5]
0.191
(0.017)
0.368
(0.040)
[1, 5]
−0.103
(0.011)
0.178
(0.018)
[1, 10]
0.192
(0.017)
0.359
(0.059)
[1, 10]
−0.104
(0.013)
0.179
(0.018)
[1, 15]
0.196
(0.016)
0.350
(0.043)
[1, 15]
−0.101
(0.012)
0.179
(0.018)
[1, 20]
0.193
(0.018)
0.338
(0.045)
[1, 20]
−0.102
(0.012)
0.175
(0.017)
Resultado do Índice CR para os métodos de agrupamento baseado em
DBSig: Conjunto de Dados 4 com 2 classes.
Tabela 4.7.
Kernel
Intervalo
MKM-EC
(σ = 1)
MKM-EC
(DBSig)
Intervalo
MKM-EE
(σ = 1)
MKM-EE
(DBSig)
[1, 5]
0.182
(0.027)
0.402
(0.122)
[1, 5]
−0.135
(0.108)
0.181
(0.028)
[1, 10]
0.182
(0.042)
0.398
(0.118)
[1, 10]
−0.139
(0.107)
0.177
(0.027)
[1, 15]
0.180
(0.027)
0.393
(0.126)
[1, 15]
−0.141
(0.099)
0.179
(0.028)
[1, 20]
0.184
(0.028)
0.401
(0.142)
[1, 20]
−0.155
(0.109)
0.183
(0.028)
para abordagem
para abordagem
Para compreender melhor a utilidade desta abordagem DBSig, observe as Tabelas 4.6 e 4.7.
Estas tabelas consideram os resultados dos métodos MKM-EC e MKM-EE para os conjuntos
de dados 3 e 4.
Para cada método, na primeira coluna é apresentado o valor do índice CR
considerando uma escolha arbitrária e na segunda coluna com a abordagem DBSig. Em uma
escolha arbitrária seria comum, por questão de simplicidade, adotar, por exemplo, o valor de
1.
σ=
Observe que, nestes casos, uma escolha não criteriosa, que apenas simplica uma expressão
nem sempre pode representar uma boa escolha.
A escolha baseada em um critério, neste
caso uma medida de agrupamento interno, obteve um melhor êxito. Esta escolha utilizando a
abordagem DBSig não signica que seria o melhor resultado a ser encontrado, mas é bastante
4.3 Experimentos e Resultados
71
provável que seja uma escolha adequada e que apresenta um resultado representativo.
Resultado do Índice CR para os métodos de agrupamento baseado em Kernel (rígido): Conjunto
de Dados 2 com 4 classes.
Tabela 4.8.
Intervalo
MKM-EC
(DBSig)
MKM-EC
(CLSig)
Intervalo
MKM-EE
(DBSig)
MKM-EE
(CLSig)
[1, 5]
0.305
(0.010)
0.328
(0.034)
[1, 5]
0.359
(0.026)
0.377
(0.030)
[1, 10]
0.288
(0.017)
0.331
(0.037)
[1, 10]
0.356
(0.029)
0.371
(0.030)
[1, 15]
0.275
(0.032)
0.330
(0.034)
[1, 15]
0.359
(0.029)
0.377
(0.029)
[1, 20]
0.273
(0.025)
0.332
(0.038)
[1, 20]
0.363
(0.026)
0.381
(0.030)
Resultado do Índice CR para os métodos de agrupamento baseado em Kernel (rígido): Conjunto
de Dados 3 com 3 classes.
Tabela 4.9.
Intervalo
MKM-EC
(DBSig)
MKM-EC
(CLSig)
Intervalo
MKM-EE
(DBSig)
MKM-EE
(CLSig)
[1, 5]
0.368
(0.040)
0.378
(0.037)
[1, 5]
0.178
(0.018)
0.195
(0.015)
[1, 10]
0.359
(0.039)
0.376
(0.037)
[1, 10]
0.179
(0.018)
0.200
(0.016)
[1, 15]
0.350
(0.032)
0.379
(0.035)
[1, 15]
0.179
(0.018)
0.197
(0.018)
[1, 20]
0.338
(0.041)
0.380
(0.033)
[1, 20]
0.175
(0.017)
0.197
(0.016)
Tabela 4.10. Resultado do Índice CR para os métodos de agrupamento baseado em Kernel (rígido): Conjunto
de Dados 5 com 2 classes.
Intervalo
MKM-EC
(DBSig)
MKM-EC
(CLSig)
Intervalo
MKM-EE
(DBSig)
MKM-EE
(CLSig)
[1, 5]
0.882
(0.142)
0.882
(0.149)
[1, 5]
0.434
(0.325)
0.705
(0.133)
[1, 10]
0.838
(0.135)
0.906
(0.115)
[1, 10]
0.456
(0.304)
0.691
(0.115)
[1, 15]
0.833
(0.113)
0.879
(0.117)
[1, 15]
0.501
(0.282)
0.715
(0.118)
[1, 20]
0.743
(0.129)
0.902
(0.123)
[1, 20]
0.461
(0.309)
0.701
(0.117)
As tabelas 4.8, 4.9 e 4.10 apresentam os resultados dos métodos MKM-EC e MKM-EE
utilizando os duas abordagens (DBSig e CLSig) para determinação do parâmetro
σ
do
kernel
RBF para os conjuntos de dados 2, 3 e 5, respectivamente. Os resultados foram apresentados
4.3 Experimentos e Resultados
72
para estes conjuntos por serem sucientemente representativos para a discussão desta seção.
Observando estas tabelas, percebe-se que na abordagem CLSig os valores dos índices CR encontrados foram superiores, em sua maioria, aos correspondentes para abordagem DBSig para os
conjuntos apresentados, consequentemente se comparados aos valores de índice CR dos método
adaptativos para estes cenários, o desempenho dos métodos baseados em
kernel
permanecem
sendo superiores.
De um modo geral, é aceitável concluir que a abordagem CLSig obteve um desempenho
superior em comparação a abordagem DBSig. Este é um resultado interessante, pois reforça
a hipótese de que a escolha do parâmetro
σ
é importante e afeta o desempenho dos métodos
que utilizam a função RBF. Apesar do custo relacionado a computação do parâmetro, é uma
abordagem viável porque evita a escolha arbitrária de um parâmetro por parte do usuário do
método. Isto não signica armar que em todos os casos, em qualquer cenário ou comparado
a todo valor xo atribuído a
σ,
atribuição de vários valores de
método seja superior a um
a abordagem CLSig seja melhor. É provável que ao testar a
sigma
sigma
seja possível encontrar um valor onde o desempenho do
calculado. No entanto, a computação do parâmetro pode ser
útil para evitar essa fase de testes ou até mesmo a escolha inadequada do parâmetro em caso
de uma escolha aleatória ou simplista (que não se baseia em nenhum critério).
O mais importante nesta seção não é propriamente a comparação entre as abordagens para
determinação do parâmetro
σ,
mas sim que há abordagens alternativas e que é importante a
determinação de maneira criteriosa deste parâmetro. As duas abordagens são empíricas e não
se baseiam em um critério otimizado no ajuste do valor do
sigma.
No entanto, de acordo com os
resultados apresentados, as abordagens se mostraram úteis, viáveis e se basearam em critérios
ou aspectos relevantes para o problema.
4.3.1.4
Resultados para os métodos de agrupamento com abordagem difusa (fuzzy )
Nesta seção serão apresentados os resultados de experimentos realizados para os métodos
de agrupamento difusos rotulados neste trabalho como McM-EC e McM-EE. Esta seção vai
considerar os resultados para os conjuntos de dados 2 a 5 apresentados no inicio do capítulo.
Como exposto no capítulo anterior estes métodos utilizam a metodologia c-médias difuso e
4.3 Experimentos e Resultados
73
são baseadas na aplicação de funções de
kernel
para intervalos. O desempenho destes méto-
dos serão comparados com o método difuso c-médias adaptativo para intervalos proposto em
(CARVALHO, 2007). Consideramos o valor do parâmetro da função de pertinência
m = 2 para
todos os casos.
Tabela 4.11. Resultado do Índice CR para os métodos de agrupamento difuso baseado em Kernel e o método
c-médias difuso adaptativo (a direita): Conjunto de Dados 2 com 4 classes.
Intervalo
McM-EC
(CLSig)
McM-EE
(CLSig)
Intervalo
FCMA
[1, 5]
0.347
(0.027)
0.392
(0.030)
[1, 5]
0.297
(0.009)
[1, 10]
0.342
(0.021)
0.384
(0.038)
[1, 10]
0.310
(0.007)
[1, 15]
0.338
(0.024)
0.391
(0.031)
[1, 15]
0.318
(0.007)
[1, 20]
0.327
(0.021)
0.389
(0.038)
[1, 20]
0.346
(0.011)
Tabela 4.12. Resultado do Índice CR para os métodos de agrupamento difuso baseado em Kernel e o método
c-médias difuso adaptativo (a direita): Conjunto de Dados 3 com 3 classes.
Intervalo
McM-EC
(CLSig)
McM-EE
(CLSig)
Intervalo
FCMA
[1, 5]
0.287
(0.027)
0.250
(0.034)
[1, 5]
0.227
(0.010)
[1, 10]
0.282
(0.021)
0.253
(0.031)
[1, 10]
0.235
(0.011)
[1, 15]
0.278
(0.024)
0.249
(0.036)
[1, 15]
0.249
(0.013)
[1, 20]
0.267
(0.021)
0.256
(0.031)
[1, 20]
0.265
(0.013)
Tabela 4.13. Resultado do Índice CR para os métodos de agrupamento difuso baseado em Kernel e o método
c-médias difuso adaptativo (a direita): Conjunto de Dados 4 com 2 classes.
Intervalo
McM-EC
(CLSig)
McM-EE
(CLSig)
Intervalo
FCMA
[1, 5]
0.211
(0.046)
0.362
(0.026)
[1, 5]
−0.169
(0.015)
[1, 10]
0.215
(0.052)
0.355
(0.027)
[1, 10]
−0.171
(0.010)
[1, 15]
0.215
(0.050)
0.364
(0.026)
[1, 15]
−0.172
(0.007)
[1, 20]
0.214
(0.046)
0.355
(0.027)
[1, 20]
−0.172
(0.011)
4.3 Experimentos e Resultados
74
Tabela 4.14. Resultado do Índice CR para os métodos de agrupamento difuso baseado em Kernel e o método
c-médias difuso adaptativo (a direita): Conjunto de Dados 5 com 2 classes.
Intervalo
McM-EC
(CLSig)
McM-EE
(CLSig)
Intervalo
FCMA
[1, 5]
0.968
(0.051)
0.738
(0.098)
[1, 5]
−0.300
(0.009)
[1, 10]
0.958
(0.052)
0.742
(0.104)
[1, 10]
−0.301
(0.007)
[1, 15]
0.911
(0.087)
0.745
(0.106)
[1, 15]
−0.300
(0.008)
[1, 20]
0.843
(0.100)
0.750
(0.102)
[1, 20]
−0.294
(0.010)
A tabela 4.11 apresenta os resultados da execução dos métodos de agrupamento difusos para
o conjunto de dados 2. Com relação ao índice CR, o método McM-EE apresentou um melhor
desempenho do que o método FCMA para todos os intervalos. O método McM-EE apresentou pouca sensibilidade com as mudanças de intervalos, apresentando pequenas variações do
índice CR. O método McM-EC apresentou os valores do índice CR superiores ao FCMA para
todos os intervalos menos para o intervalo
[1, 20].
Neste sentido o método FCMA apresentou
um comportamento interessante, pois seu desempenho melhorou mesmo com o aumento dos
intervalos.
A tabela 4.12 apresenta os resultados da execução dos métodos de agrupamento difusos
para o conjunto de dados 3. Assim como abordado nas seções anteriores o conjunto apresenta
um nível de diculdade relativamente alto para identicação dos grupos. O desempenho dos
métodos McM-EC e McM-EE com relação ao índice CR, foi ligeiramente superior ao método cmédias adaptativo (FCMA), com exceção do intervalo mais alto. Mesmo com os desempenhos
aproximados entre os métodos neste cenário, a avaliação é válida e sugerem a aplicação dos
métodos neste tipo de cenário com existência de grupos não linearmente separáveis.
As tabelas 4.13 e 4.14 apresentam os resultados da execução dos métodos de agrupamento
difusos para o conjunto de dados 4 e 5. Os dois conjuntos de dados apresenta um alto nível
de diculdade para identicação dos grupos. O desempenho dos métodos McM-EC e McM-EE
com relação ao índice CR, foi bastante superior ao método c-médias adaptativo (FCMA) nos
dois cenários. Este resultado reforça a validação do métodos apresentados nesta Tese.
4.3 Experimentos e Resultados
4.3.2
75
Conjunto de Dados Reais do Tipo Intervalo
Tipicamente nos estudos de métodos de agrupamento são realizados experimentos para
tratar dados conhecidos como dados de aplicação ou dados reais (CARVALHO; BRITO; BOCK,
2006) (CARVALHO; LECHEVALLIER, 2009b).
Neste caso também foi implementado um
sistema na linguagem C++ que classica um conjunto de dados do tipo intervalo e avalia os
resultados da classicação usando o índice de Rand corrigido (CR). Cada método é executado
(até que nenhum elemento da partição mude de classe) 500 vezes variando aleatoriamente as
sementes usadas na etapa de inicialização.
O melhor critério dentre as repetições realizadas
é escolhido e o índice CR é calculado para a partição correspondente.
As seções seguintes
descreverão os dados reais utilizados e apresentarão os respectivos resultados da execução dos
métodos.
4.3.2.1
Conjunto de Dados: Agaricus
Este conjunto de dados reais do tipo intervalo avaliado denomina-se
http : //www.mykoweb.com/CAF/species/index.html,
Agaricus
extraído de
cujas informações foram extraídas a
partir de espécies de fungos presentes no estado da Califórnia, Estados Unidos.
um gênero de cogumelos, de modo que dois membros bastante conhecidos são o
conhecido como o cogumelo botão muito comum em supermercados e o
Agaricus é
A. bisporus,
A. campestris, também
chamado de cogumelo de campo, é uma espécie popular comestível comum em pastagens e
prados em áreas temperadas no mundo.
Esse conjunto possui 24 espécies do gênero
Agaricus,
onde cada uma é descrita por três
variáveis do tipo intervalo: largura do píleo, espessura do estipe e largura dos esporos.
Os
dados são distribuídos entre duas classes: comestível (classe 1) e não-comestível (classe 2). A
tabela 4.15 a seguir descreve as espécies de acordo com suas variáveis:
De forma que a distribuição dos elementos entre as duas classes é descrita como:
a) Classe 1: Albolutescens: 1, Arvensis: 2, Benesii: 3, Bernardii: 4, Bisporus: 5, Bitorquis:
6, Campestris: 8, Comtulus: 9, Cupreo-brunneus: 10, Fusco-brillosus: 11, Fuscovelatus:
12, Lilaceps: 14, Micromegathus: 15, Pattersonae: 16, Perobscurus: 17, Semotus: 19,
4.3 Experimentos e Resultados
Espécies
76
Cogumelos da família
Tabela 4.15.
1. Albolutescens
2. Arvensis
3. Benesii
4. Brnardii
5. Bisporus
6. Bitorquis
7. Californicus
8. Campestris
9. Comtulus
10. Cupreo-brunneus
11. Fusco-brillosus
12. Fuscovelatus
13. Hondensis
14. Lilaceps
15. Micromegathus
16. Pattersonae
17. Perobscurus
18. Praeclaresquamosus
19. Semotus
20. Silvicola
21. Smithii
22. Subrutilescens
23. Subrufescens
24. Xanthodermus
Figura 4.13.
largura
do píleo
espessura
do estipe
[6.00, 12.00]
[6.00, 21.00]
[4.00, 8.00]
[7.00, 16.00]
[5.00, 12.00]
[5.00, 15.00]
[4.00, 11.00]
[5.00, 10.00]
[2.50, 4.00]
[2.50, 6.00]
[4.00, 15.00]
[3.50, 8.00]
[7.00, 14.00]
[8.00, 20.00]
[2.50, 4.00]
[5.00, 15.00]
[8.00, 12.00]
[7.00, 19.00]
[2.00, 6.00]
[6.00, 12.00]
[7.00, 12.00]
[6.00, 14.00]
[6.00, 13.00]
[5.00, 17.00]
[1.50, 3.00]
[1.00, 3.50]
[1.00, 2.00]
[3.00, 4.50]
[1.50, 2.50]
[2.00, 4.00]
[0.40, 1.00]
[1.00, 2.00]
[4.00, 7.00]
[1.00, 1.50]
[1.50, 2.50]
[1.00, 2.00]
[1.50, 2.50]
[3.00, 5.00]
[4.00, 7.00]
[2.50, 3.50]
[1.50, 2.00]
[2.00, 3.50]
[0.40, 0.80]
[1.50, 2.00]
[2.00, 3.00]
[1.00, 2.00]
[1.50, 2.50]
[1.00, 3.50]
Agaricus
largura
dos esporos
[4.00, 5.00]
[4.50, 6.00]
[3.00, 4.00]
[5.50, 6.50]
[4.50, 6.00]
[4.00, 5.50]
[4.00, 5.50]
[3.50, 5.00]
[3.00, 3.50]
[5.00, 6.00]
[3.50, 4.00]
[1.00, 2.00]
[3.00, 4.50]
[4.00, 5.00]
[3.00, 3.50]
[6.00, 6.50]
[4.50, 5.00]
[3.50, 4.50]
[3.00, 3.50]
[3.50, 4.00]
[5.00, 5.50]
[3.50, 4.50]
[4.00, 4.50]
[4.00, 5.50]
Grupo
E
E
E
E
E
E
I
E
E
E
E
E
I
E
E
E
E
I
E
E
E
E
E
I
Família dos Cogumelos Agaricus
Silvicola: 20, Smithii: 21, Subrutilescens: 22 e Subrufescens: 23
b) Classe 2: Californicus: 7, Hondensis: 13, Praeclaresquamosus: 18, Xanthodermus: 24
Tabela 4.16.
Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados Agaricus.
MKM-EC
MKM-EE
DAC
DAU
0.261
0.261
−0.239
−0.084
4.3 Experimentos e Resultados
Tabela 4.17.
77
Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de Dados Agaricus.
McM-EC
McM-EE
FCMA
0.314
0.314
−0.037
Os resultados do índice CR após a aplicação dos algoritmos dos métodos adaptativos e das
variações dos métodos baseados em
kernel
propostos para dados intervalares pode ser visua-
lizado nas tabelas 4.16 e 4.17. Observa-se também pela gura 4.13 que o conjunto apresenta
um alto grau de diculdade de classicação. Mesmo assim, avaliando o índice CR, o desempenho dos métodos de agrupamentos rígidos e difusos baseados em
dos métodos de adaptativos para o conjunto
4.3.2.2
kernel
são superiores aos
Agaricus.
Conjunto de Dados: Fluxos de Água
Este conjunto de dados consiste de registros de uxos de água de 30 min coletados durante um ano (de 1 de junho de 2003 a 31 de maio de 2004) na rede de distribuição de água
da cidade de Barcelona na Espanha.
Ele contém dados referente a 316 dias do ano, con-
siderando que, em alguns dias, valores de medição foram descartados em função de problemas
de funcionamento nos sensores que coletam as informações referente aos uxos.
Este con-
junto de dados foi originalmente extraído de (QUEVEDO V. PUIG; MOLINA, 2010) e citado
na literatura de análise de dados simbólicos pela primeira vez em (HEDJAZI; AGUILARMARTIN; LANN, 2011). Uma versão para
download
deste conjunto pode ser encontrado em
http : //lhedjazi.jimdo.com/usef ul − links/.
Normalmente, os hábitos das pessoas estão associados a comportamentos periódicos semanais, o que possibilita predição de demandas dos consumidores com base nas alterações
observadas entre dias úteis e os nais de semana (QUEVEDO V. PUIG; MOLINA, 2010).
Neste conjunto de dados, cada dia é caracterizado por 48 variáveis intervalares, onde cada variável descreve a variação máxima e mínima observada com base em três medições consecutivas
de 10 min do uxo de água. Cada dia é rotulado por uma das duas classes de acordo com o
tipo do dia: nal de semana (sábados, domingos, feriados) ou dia útil.
A caracterização de
intervalos de tempo correspondentes a variação do consumo útil dos usuários durante a semana,
possibilita a empresa fornecedora de água prever o uxo a ser fornecido de acordo com cada
4.3 Experimentos e Resultados
78
tipo de dia da semana. Isso, portanto, possibilita ao tomador de decisões um certa exibilidade
para regular o uxo de água de acordo com o período associado determinado tipo de dia.
Como mencionado, o conjunto de dados originalmente possui 48 variáveis intervalares que
descrevem as característica da rede de distribuição de água de Barcelona. No entanto, neste
trabalho o conjunto foi reduzido, de modo que passou a ser descrito por 9 variáveis intervalares.
Essa redução foi necessária devido a resultados inconclusivos a partir do índice CR. De fato,
em (HEDJAZI; AGUILAR-MARTIN; LANN, 2011) é apresentado um estudo que sugere a
redução do número de variáveis neste conjunto, pois, com o número de variáveis do conjunto
original a taxa de erro é bastante elevada. No entanto, o trabalho citado não sugere a forma
de selecionar as variáveis. A tabela 4.18 apresenta um subconjunto destes dados caracterizado
pelas 9 variáveis intervalares que descreve variação dos uxos diários de água.
Tabela 4.18.
Dia
1. Domingo 06-01-2003
2. Segunda 07-01-2003
...
...
...
...
...
...
314. Sábado 05-29-2004
315. Domingo 05-30-2004
316. Segunda 05-31-2004
Fluxo de Água da cidade de Barcelona
Fluxo 1
Fluxo 2
[1.67, 1.83]
[4.17, 6.33]
[1.83, 2.17]
[4.83, 8.33]
[3.67, 6.33]
[1.33, 1.83]
[1.17, 1.50]
[5.33, 7.00]
[1.83, 3.00]
[1.17 : 1.50]
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Fluxo 9
[1.33, 1.83]
[6.67, 1.33]
...
...
...
...
...
...
[4.1, 8.00]
[0.50, 0.67]
[1.33, 1.67]
Tipo de dia
Final de Semana
Dia Útil
...
...
...
...
...
...
Final de Semana
Final de Semana
Dia Útil
Este trabalho considerou o cálculo das variâncias para as 48 variáveis para reduzir o número
de descrições. Para cada variável intervalar foram calculadas as médias das 316 ocorrências e
para cada média suas variâncias. Foram escolhidas as variáveis que apresentaram uma maior
variabilidade, de modo que essas variáveis são sucientemente representativas para realizar
a análise sobre este conjunto de dados.
As expressões 4.8 e 4.9 denem a formulação para
o cálculo das médias e variâncias para dados do tipo intervalo, respectivamente, que foram
utilizadas neste trabalho e podem ser encontradas em (DIDAY; NOIRHOMME-FRAITURE,
2008).
Z̄ =
1 X
(bi + ai )
2n i∈E
(4.8)
4.3 Experimentos e Resultados
79
"
#2
X
X
1
1
(b2 + bi ai + a2i ) − 2
(ai + bi )
S2 =
3n i∈E i
4n i∈E
Tabela 4.19.
Tabela 4.20.
de Água.
(4.9)
Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados Fluxos de Água.
MKM-EC
MKM-EE
DAC
DAU
−0.097
0.052
−0.124
−0.124
Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de Dados Fluxos
McM-EC
McM-EE
FCMA
0.011
0.052
−0.106
Os resultados do índice CR após a aplicação dos algoritmos dos métodos adaptativos e das
variações dos métodos baseados em
kernel
propostos para dados intervalares pode ser visuali-
zado nas tabelas 4.19 e 4.20. Observando os resultados percebe-se que os métodos adaptativos
obtiveram resultados negativos e os métodos baseados em
kernel
apresentaram resultados su-
periores em relação ao índice CR, com exceção do método MKM-EC que obteve um resultado
negativo. Este resultado, apesar de apresentar valores baixos do índice CR é interessante, pois,
conforme (HEDJAZI; AGUILAR-MARTIN; LANN, 2011) este conjunto tem uma tendência
a apresentar uma taxa de erro de classicação relativamente alta. Mesmo assim, os métodos
baseados em
kernel
apresentaram resultados positivos em sua maioria, e segundo (HUBERT;
ARABIE, 1985) um índice CR positivo já é considerado um bom resultado e pode representar
algum nível de reconhecimento/classicação nos padrões avaliados. Nesta avaliação em particular, o fato do índice CR ser positivo é relevante principalmente em detrimento aos métodos
da literatura de ADS que obtiveram resultados inferiores. No caso de conjuntos dessa natureza,
pode ser necessário investir em técnicas de pre-processamento para auxiliar na decisão sobre
que tipo de abordagem de agrupamento ser aplicada.
4.3.2.3
Conjunto de Dados: Temperatura das Cidades
Este conjunto de dados do tipo intervalo foi inicialmente apresentado em (GURU; KIRANAGI; NAGABHUSHAN, 2004), consiste de 37 cidades descritas por doze variáveis do tipo
4.3 Experimentos e Resultados
80
intervalo que indicam as temperaturas mínima e máxima dos doze meses do ano. A tabela 4.21
ilustra os dados contidos neste conjunto.
Neste trabalho foi realizado uma adaptação neste
conjunto, de modo que cada cidade passou a ser descrita por três variáveis que representam as
temperaturas máximas e mínimas das cidades durante um ano, com cada variável representando
um quadrimestre do ano: Janeiro a Abril, Março a Agosto e Setembro a Dezembro. Esta seção
faz uma breve descrição deste conjunto de dados reais e apresenta os resultados da aplicação
dos métodos de agrupamento sobre ele.
Este conjunto de dados estão agrupados em quatro classes a priori de tamanhos diferentes.
Abaixo segue a composição de cada classe, onde cada indivíduo é seguido de um rótulo para
identicação de cada cidade:
a) Classe 1: Bahraim: 3, Bombay: 4, Cairo: 5, Calcutta: 6, Colombo: 7, Dubal: 9, Hong
Kong: 12, Kula Lampur: 13, Madras: 16, Manila: 18, Mexico: 20, Nairobi: 23, New
Delhi: 24, Sydney: 30 and Singapore: 32
b) Classe 2: Amsterdam: 1, Athens: 2, Copenhagen: 8, Frankfurt: 10, Geneva: 11, Lisbon:
14, London: 15, Madrid: 17, Moscow: 21, Munich: 22, New York: 25, Paris: 26, Rome:
27, San Francisco: 28, Seoul: 29, Stockholm: 31, Tokyo: 34, Toronto: 35, Vienna: 36 and
Zurich: 37
c) Classe 3: Mauritius: 19
d) Classe 4: Tehran: 33
O intuito desta adaptação e redução do conjunto a três variáveis foi que o leitor possa ter
uma noção de como os dados estão espacialmente distribuídos neste conjunto através de uma
representação gráca dos dados, conforme ilustra a gura 4.14. Os elementos deste conjunto
são representados pelo cubos e as diferente tonalidades indicam o grupo a que pertencem.
Observando a gura, é possível perceber uma certa não linearidade na distribuição dos dados.
As tabelas 4.22 e 4.23 ilustram os valores do cálculo do índice CR obtidos na comparação do
conjunto de partições a priori e as partições obtidas como resultado da aplicação dos métodos
de agrupamento rígidos e difusos, respectivamente. É possível observar que o desempenho em
relação ao índice CR dos métodos baseados em
Kernel
é superior aos métodos adaptativos.
4.3 Experimentos e Resultados
Tabela 4.21.
81
Valores mínimo e máximo de temperatura de 37 cidades (em graus centígrado)
Janeiro a Abril Março A Agosto Setembro a Dezembro Grupo
Cidade
1. Amssterdam
2. Athens
3. Bahrain
4. Bombay
5. Cairo
6. Calcutta
7. Colombo
8. Copenhagen
9. Dubal
10. Frankfurt
11. Geneva
12. HongKong
13. KulaLumpur
14. Lisbon
15. London
16. Madras
17. Madrid
18. Manila
19. Mauritius
20. MexicoCity
21. Moscow
22. Munich
23. Nairobi
24. NewDelhi
25. NewYork
26. Paris
27. Rome
28. SanFrancisco
29. Seoul
30. Singapore
31. Stockholm
32. Sydney
33.Tehran
34. Tokyo
35. Toronto
36. Vienna
37.Zurich
Figura 4.14.
[13, 27]
[19, 32]
[8, 29]
[13, 36]
[22, 31]
[−3, 10]
[13, 31]
[12, 23]
[22, 33]
[20, 35]
[21, 31]
[6, 27]
[12, 26]
[6, 36]
[23, 31]
[16, 30]
[−5, 15]
[6, 19]
[−10, 24]
[−6, 13]
[8, 18]
[2, 13]
[1, 19]
[−13, 8]
[−6, 14]
[−3, 15]
[1, 16]
[4, 19]
[6, 18]
[0, 16]
[−9, 8]
[0, 18]
[−8, 11]
[−2, 14]
[−11, 21]
[21, 29]
[0, 18]
[25, 36]
[25, 33]
[17, 36]
[26, 36]
[25, 31]
[8, 22]
[22, 39]
[22, 30]
[23, 32]
[26, 39]
[23, 31]
[18, 27]
[11, 22]
[26, 40]
[24, 30]
[5, 20]
[7, 23]
[16, 32]
[3, 32]
[10, 24]
[13, 27]
[8, 22]
[9, 34]
[7, 24]
[7, 23]
[12, 29]
[8, 24]
[13, 31]
[10, 22]
[12, 31]
[6, 22]
[14, 31]
[−8, 27]
[10, 24]
[2, 31]
[17, 25]
[20, 40]
[15, 34]
[20, 32]
[10, 33]
[13, 32]
[22, 30]
[1, 18]
[14, 37]
[14, 29]
[23, 32]
[21, 34]
[22, 29]
[8, 26]
[11, 24]
[7, 34]
[23, 30]
[11, 30]
[−1, 20]
[8, 28]
[−8, 27]
[−2, 19]
[8, 24]
[3, 19]
[1, 28]
[−11, 16]
[−4, 20]
[−2, 24]
[1, 21]
[5, 27]
[6, 23]
[1, 28]
[−2, 15]
[2, 27]
[−5, 22]
[1, 19]
[−11, 23]
[17, 28]
[−5, 30]
2
2
1
1
1
1
1
2
1
2
2
1
1
2
2
1
2
1
3
1
2
2
1
1
2
2
2
2
2
1
2
1
4
2
2
2
2
Conjunto de dados: Temperatura das cidades
Os métodos com agrupamento no espaço de características apresentaram uma ligeira vantagem
sobre os métodos com agrupamento no espaço de entradas.
O intuito da avaliação destes
4.3 Experimentos e Resultados
82
métodos neste tipo de cenário é observar seu comportamento diante de cenários reais (que não
sejam gerados de maneira articial, e sim, por exemplo, de dados coletados a partir de um
contexto real), reforçando a validação de tais métodos.
Tabela 4.22.
Cidades.
Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados Temperatura das
MKM-EC
MKM-EE
DAC
DAU
0.733
0.660
0.576
0.415
Tabela 4.23. Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de Dados Temperatura das Cidades.
4.3.2.4
McM-EC
McM-EE
FCMA
0.705
0.679
0.542
Conjunto de Dados: Carros
O conjunto de dados simbólicos Carros consiste de 33 modelos descritos por oito variáveis
intervalares, duas variáveis categóricas multivaloradas e uma variável nominal. Neste conjunto
de dados de aplicação, as oito variáveis intervalares consideradas são: preço, cilindrada do motor, velocidade máxima, aceleração, passo, comprimento, largura e altura. A variável nominal,
categoria de carro foi utilizada como um rótulo para classicação
a priori.
A tabela 4.24 ilustra
os dados contidos neste conjunto. Esta seção faz uma breve descrição deste conjunto de dados
reais e apresenta os resultados da aplicação dos métodos de agrupamento sobre ele.
Tabela 4.24.
Cidade
1. Alpha 145
2. Alpha 156
...
...
...
31. Porshe 25
32. Rover 25
33. Passat
Conjunto de Dados Carros com 8 variáveis do tipo intervalo
Preço
Cilindrada do motor
[27806, 33596]
[41593, 62291]
[1370, 1910]
[1598, 2492]
[147704, 264412]
[21492, 33042]
[39676, 63455]
[3387, 3600
[1119, 1994]
[1595, 2496]
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Altura
[143, 143]
[142, 142]
...
...
...
[130, 131]
[142, 142]
[146, 146]
Categoria
Utilitário
Sedan
...
...
...
Sedan
Utilitário
Luxo
Este conjunto de dados estão agrupados em quatro classes a priori de tamanhos diferentes.
Abaixo segue a composição de cada classe, onde cada indivíduo é seguido de um rótulo para
identicação de cada categoria de carro:
4.3 Experimentos e Resultados
83
a) Utilitário (U): 1-Alfa 145/U, 5-Audi A3/U, 12-Punto/U, 13-Fiesta/U, 17-Lancia Y/U,
24-Nissan Micra/U, 25-Corsa/U, 28-Twingo/U, 29-Rover 25/U, 31-Skoda Fabia/U
b) Sedan (S): 2-Alfa 156/S, 6-Audi A6/S, 8-BMW serie 3/S, 14-Focus/S, 21-Mercedes Classe
C/S, 26-Vectra/S, 30-Rover 75/S, 32-Skoda Octavia/S
c) Luxo (L): 3-Alfa 166/L, 7-Audi A8/L, 9-BMW serie 5/L, 10-BMW serie 7/L, 18-Lancia
K/L, 22-Mercedes Classe, E/L 23-Mercedes Classe S/L, 33-Passat/L
d) Esportivo (E): 4-Aston Martin/E, 11-Ferrari/E, 15-Honda NSK/E, 16-Lamborghini/E,
19-Maserati GT/E, 20-Mercedes SL/E, 27-Porsche/E
Tabela 4.25.
Tabela 4.26.
Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados Carros.
MKM-EC
MKM-EE
DAC
DAU
0.600
0.600
0.670
0.557
Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de Dados Carros.
McM-EC
McM-EE
FCMA
0.521
0.552
0.458
As tabelas 4.25 e 4.26 ilustram os valores do cálculo do índice CR obtidos na comparação do
conjunto de partições a priori e as partições obtidas como resultado da aplicação dos métodos
de agrupamento rígidos e difusos, respectivamente.
Para este conjunto de dados, é possível
observar que o desempenho em relação ao índice CR dos métodos baseados em
Kernel
na
abordagem rígida foi superior apenas ao método adaptativo com distância única, mas foi inferior
ao método com distância adaptativa por classe.
Na abordagem difusa, os métodos com agrupamento baseados em
Kernel apresentaram uma
ligeira vantagem sobre o método adaptativo difuso. Assim, como no cenário anterior, o intuito
da avaliação destes métodos é observar seu comportamento diante de cenários reais, reforçando
a validação de tais métodos. O fato do método adaptativo por distância adaptativa por classe
ter sido superior não invalida os métodos propostos neste trabalho, pois é importante salientar
que nenhum método é infalível e existem cenários onde o uso de
menor que um método adaptativo.
kernel
tenha um impacto
Observe que este conjunto de dados possui classes mais
homogêneas, o que pode ter favorecido o método adaptativo por classe (DAC).
4.3 Experimentos e Resultados
4.3.2.5
84
Conjunto de Dados: Peixes
Diversos estudos realizados na Guyana francesa têm indicado níveis anormais de contaminação de mercúrio em algumas regiões. Esta contaminação de mercúrio é devida ao alto índice
de consumo de peixe de água doce contaminado (SOUZA, 2003). Com o objetivo de obter um
melhor conhecimento deste fenômeno, um conjunto de dados foi coletado por pesquisadores de
um laboratório (LEESA -Laboratoire d'Ecophysiologie et d'Ecotoxicologie des Systemes Aquatiques).
Este conjunto de dados consiste em 12 espécies de peixes, cada espécie sendo descrita por
treze variáveis do tipo intervalo e uma variável categórica.
Estas espécies estão agrupadas
em quatro classes a priori de tamanhos diferentes de acordo com a variável categórica: duas
classes (Carnivorous e Detritivorous) de tamanho 4 e duas classes de tamanho 2 (Omnivorous
e Herbivorous). Esta seção faz uma breve descrição deste conjunto de dados reais e apresenta
os resultados da aplicação dos métodos de agrupamento sobre ele. A tabela 4.27 ilustra parte
deste conjunto de dados.
Tabela 4.27.
Conjunto de dados de Peixes descritos por 13 variáveis intervalares.
Indivíduos/classes
Variáveis Intervalares
Comprimento
Peso
...
1. Ageneiosusbrevili
2. Cynodongibbus
3. Hopliasaimara
4. Potamotrygonhy
5. Leporinusfasciatus
6. Leporinusfrederici
7. Dorasmicropoeus
8. Platydorascostatus
9. Pseudoancistrus
10. Semaprochilodusvari
11. Acnodonoligacanthus
12. Myleusrubripinis
Tabela 4.28.
Tabela 4.29.
[1.8,7.1]
[19,32]
[25.5,63]
[20.5,45]
[18.8,25]
[23,24.5]
[19.2,31]
[13.7,25]
[13,20.5]
[22,28]
[10,16.2]
[2.7,8.4]
[2.1,7.2]
[77,59]
[340,5500]
[400,6250]
[125,273]
[290,350]
[128,505]
[60,413]
[55,210]
[330,700]
[34.9,154.7]
[2.7,8.7]
...
...
...
...
...
...
...
...
...
...
...
...
Intestino/
Músculo
[4.3,11.8]
[0.2,1.24]
[0.09,0.4]
[0,0.5]
[0.12,0.17]
[0.13,0.58]
[0,0.79]
[0,0.61]
[0.49,1.36]
[0,1.25]
[0.23,5.97]
[5.1,13.3]
Resultado do Índice CR métodos de agrupamento rígidos: Conjunto de Dados Peixes.
MKM-EC
MKM-EE
DAC
DAU
0.867
0.867
0.488
0.767
Resultado do Índice CR para os métodos de agrupamento difusos: Conjunto de Dados Peixes.
McM-EC
McM-EE
FCMA
0.488
0.578
0.522
4.3 Experimentos e Resultados
85
As tabelas 4.28 e 4.29 ilustram os valores do cálculo do índice CR obtidos na comparação do conjunto de partições a priori e as partições obtidas como resultado da aplicação
dos métodos de agrupamento rígidos e difusos, respectivamente.
É possível observar que
o desempenho em relação ao índice CR dos métodos baseados em
Kernel
é superior aos
métodos adaptativos para o paradigma rígido. No caso difuso, os desempenhos foram próximos, com uma pequena superioridade do método MKM-EE comparado ao adaptativo. Apesar de ser um conjunto pequeno, foi utilizado em trabalhos relevantes da literatura de ADS
(CARVALHO; LECHEVALLIER, 2009b)(SOUZA; CARVALHO; PIZZATO, 2007)(HEDJAZI;
AGUILAR-MARTIN; LANN, 2011), tornando a avaliação aceita na comunidade cientíca. Com
isso, os resultados apresentados reforçam a validade dos métodos apresentados nesta Tese.
CAPÍTULO 5
CONSIDERAÇÕES FINAIS E TRABALHOS FUTUROS
Neste trabalho foi apresentado um conjunto de métodos de agrupamento para dados simbólicos
intervalares baseado em funções de
Kernel.
Estes métodos são extensões do K-Médias, onde a
principal diferença ocorre na capacidade de interpretar dados do tipo intervalo e utilizar funções
de
Kernel
para auxiliar no processo de identicação de grupos não lineares. A motivação desse
estudo está relacionada justamente à investigação de métodos que possam criar uma separação
não linear de grupos de dados intervalares, uma vez que métodos presentes na literatura de
ADS, tais como os agrupamentos dinâmicos descritos nesse trabalho, não são tão ecientes
para esse propósito.
Foram introduzidos variações do método K-Médias e difuso c-médias com uso de funções
de
Kernel
para dados intervalares. O
Kernel
para intervalos foi tratado inicialmente de duas
formas: a primeira o intervalo foi considerado como uma informação única (uma componente)
e a segunda onde existe um tratamento separado para os limites inferior e superior de cada
intervalo (dois componentes). Em ambos os casos, o objetivo é identicar a não-linearidade dos
dados ao mesmo tempo em que estes são representados por meio de conjuntos de intervalos,
caracterizando a variabilidade e a incerteza das informações. Foram realizados experimentos e
com base no índice DB, para os cenários avaliados conclui-se que o
Kernel
de duas componentes
é mais apropriado por levar em consideração uma quantidade maior de informação ao processar
a distância. Além disso, os métodos foram aplicados sob duas abordagens: o agrupamento no
espaço de entrada, onde os protótipos dos grupos podem ser encontrados explicitamento no
espaço de dados e o agrupamento no espaço de características, onde não há possibilidade de
denição explicita dos protótipos.
Foram realizados experimentos com o uso da técnica de Monte Carlo com conjuntos de
dados simbólicos intervalares. Nos conjuntos sintéticos, o objetivo é que os experimentos possam
fornecer resultados referentes à eciência dos métodos em encontrar partições de dados não-
87
linearmente separáveis para o espaço de entrada.
Os métodos usados para comparação com
propostos foram métodos de agrupamento dinâmico para dados simbólicos aceitos na literatura
de ADS que utilizam distâncias adaptativas.
Também foram realizados experimentos com
dados simbólicos intervalares reais, com os conjuntos Temperaturas de cidades, Fluxo de Água,
Agaricus, Carros e Peixes. Para isto, adotou-se o índice de corrigido de Rand (CR) como forma
de avaliar os métodos.
Como conclusão principal, os métodos propostos se mostraram mais eciente do que os
métodos de agrupamento dinâmico nos cenários estudados, tanto para dados sintéticos quanto
para os cenários de dados reais, quando avaliados através do CR. Desta forma, este trabalho
contribuiu para o desenvolvimento de métodos para o reconhecimento de dados não linearmente
distribuídos, obtendo um avanço teórico no âmbito dos algoritmos de agrupamento para dados
simbólicos, podendo servir de ponto de partida para o desenvolvimento de novas técnicas de
agrupamento de dados.
As principais contribuições deste trabalho podemos citar:
•
A aplicação e extensão de métodos baseados em
Kernel
para literatura de Análise de
Dados Simbólicos;
Kernel
•
A utilização de heurísticas para determinação do parâmetro
•
Introdução dos métodos desta Tese na literatura de ADS através das seguintes publicações
σ
do
Gaussiano;
em anais de eventos:
Anderson F. B. F. da Costa, Bruno A. Pimentel, Renata M. C. R. de Souza:
kernel k-means clustering method for symbolic interval data.
A
IJCNN 2010:
1-6 (COSTA; PIMENTEL; SOUZA, 2010b) (Artigo Completo)
Bruno A. Pimentel, Anderson F. B. F. da Costa, Renata M. C. R. de Souza:
Kernel-based fuzzy clustering of interval data.
FUZZ-IEEE 2011: 497-501
(PIMENTEL; COSTA; SOUZA, 2011a) (Artigo Completo)
Bruno A. Pimentel, Anderson F. B. F. da Costa, Renata M. C. R. de Souza:
A
partitioning method for symbolic interval data based on kernelized metric.
CIKM 2011: 2189-2192 (PIMENTEL; COSTA; SOUZA, 2011b) (Artigo Curto)
5.1 Trabalhos Futuros
88
Anderson F. B. F. da Costa, Bruno A. Pimentel, Renata M. C. R. de Souza:
K-
means Clustering for Symbolic Interval Data Based on Aggregated Kernel
Functions.
ICTAI (2) 2010: 375-376 (COSTA; PIMENTEL; SOUZA, 2010a) (Re-
sumo Expandido)
5.1
TRABALHOS FUTUROS
Assim como no K-médias, um dos principais problemas encontrados no método adaptado
para dados intervalares é a sensibilidade à escolha dos protótipos para a denição da partição
inicial.
Desta forma, existe a necessidade de um número maior de execuções do algoritmo
para obter a partição de menor critério quando comparado com os métodos de agrupamento
dinâmico. Assim, é importante o estudo de novas técnicas para a denição da partição inicial
ou novas maneiras de diminuir a sensibilidade do método proposto. Uma extensão do método
Kernel
K-médias denominada
Global Kernel
K-médias (TZORTZIS; LIKAS, 2009) pode ser
adaptada para dados simbólicos de intervalo para tentar contornar essa sensibilidade na inicialização.
Outro aspecto interessante de ser analisado, é o comportamento dos métodos para diferentes
funções de
Kernel, tais como o Polinomial e o Sigmoide.
Assim, pode ser possível concluir quais
tipos de funções possuem um desempenho melhor e são mais adequadas a problemas onde os
dados são organizados de maneira linear e não linear.
Neste trabalho foram denidas heurísticas para estimar o valor do parâmetro
σ
do
Kernel
Gaussiano, então um possível trabalho futuro pode ser a implementação de técnicas para identicação do valor ótimo para o parâmetro
Maximization
σ , utilizando por exemplo, um algoritmo Expectation
(EM).
Na utilização de
Kernel
de duas componentes pode ser investigado a inuência de cada
limite inferior e superior do intervalo no desempenho do método, e a partir disso propor uma
estratégia de aplicar um fator de ponderação para os limites, tanto nas abordagens rígidas como
difusa.
Um estudo interessante seria avaliar o comportamento dos métodos desta Tese em cenários
para intervalos com a presença de
outliers e propor adaptações ou variantes para lidar com esse
5.1 Trabalhos Futuros
89
tipo de cenário.
Outro possível trabalho seria considerar no
Kernel
Gaussiano a possibilidade de utiliza-
ção de outras medidas de distâncias para intervalos, considerando na própria função RBF a
utilização de métricas como a distância de
city-block e Hausdor.
Ainda outro trabalho a ser proposto para o futuro seria denir métodos de
kernel para inter-
valos utilizando uma abordagem possibilística. Essa abordagem ainda não existe na literatura
de Análise de Dados Simbólicos.
REFERÊNCIAS BIBLIOGRÁFICAS
ABRAHAM, A.; DAS, S.; KONAR, A. Document clustering using dierential evolution.
Pro-
ceedings of the 2006 IEEE Congress on evolutionary computation, 2006.
ANDERBERG, M.
Cluster Analysis for Applications. [S.l.]:
New York: Academic, 1973.
AWAN, A. M.; SAP, M. N. M. An intelligent system based on kernel methods for crop yield
prediction. In:
PAKDD. [S.l.:
s.n.], 2006. p. 841846.
BACH, F.; JORDAN, M. Learning Spectral Clustering, with Application to Speech Separation.
Journal of Machine Learning Research, v. 7, October 2006.
BANERJEE, A. et al. Clustering with bregman divergences.
J. Mach. Learn. Res.,
v. 6, p.
17051749, December 2005. ISSN 1532-4435.
BEN-HUR, A. et al. Support vector clustering.
Journal of Machine Learning Research, v. 2, p.
125137, 2001.
BERKHIN, P. A survey of clustering data mining techniques.
Grouping Multidimensional Data,
p. 2571, 2006.
BEZDEK, J. C.
Pattern Recognition with Fuzzy Objective Function Algorithms. Norwell, MA,
USA: Kluwer Academic Publishers, 1981.
BILLARD, L.; DIDAY, E.
Symbolic Data Analysis: Conceptual Statistics and Data Mining.
England: Wiley, West Sussex, 2006. ISBN 9780470090169, 0470090162.
BOCK, H.; DIDAY, E. Analysis of symbolic data.
Study in Classication,
Data Analysis and
Knowledge Organization. Springer Verlag, 2000.
BOLSHAKOVA, N.; AZUAJE, F. Cluster validation techniques for genome expression data.
Signal Processing, v. 83, p. 825833, 2002.
Referências Bibliográficas
91
BRAND, M.; HUANG, K. A unifying theorem for spectral embedding and clustering. 2003.
BRITO, P. Order structure of symbolic assertion objects.
Eng.,
IEEE Trans. on Knowl. and Data
IEEE Educational Activities Department, Piscataway, NJ, USA, v. 6, p. 830835,
October 1994. ISSN 1041-4347.
CARVALHO, F. D.; BRITO, P.; BOCK, H.-H. Dynamic clustering for interval data based on
l2 distance.
Comput. Stat.,
Kluwer Academic Publishers, Hingham, MA, USA, v. 21, p.
231250, June 2006. ISSN 0943-4062.
CARVALHO, F. d. A. T. D. Fuzzy c-means clustering methods for symbolic interval data.
Pattern Recogn. Lett.,
Elsevier Science Inc., New York, NY, USA, v. 28, p. 423437,
March 2007. ISSN 0167-8655.
CARVALHO, F. D. A. T. D.; LECHEVALLIER, Y. Dynamic clustering of interval-valued
data based on adaptive quadratic distances.
Trans. Sys. Man Cyber. Part A, IEEE Press,
Piscataway, NJ, USA, v. 39, p. 12951306, November 2009. ISSN 1083-4427.
CARVALHO, F. d. A. T. D.; LECHEVALLIER, Y. Partitional clustering algorithms for symbolic interval data based on single adaptive distances.
Pattern Recogn.,
Elsevier Science
Inc., New York, NY, USA, v. 42, p. 12231236, July 2009. ISSN 0031-3203.
CARVALHO, F. d. A. T. D. et al. Adaptive hausdor distances and dynamic clustering of
symbolic interval data.
Pattern Recogn. Lett., Elsevier Science Inc., New York, NY, USA,
v. 27, p. 167179, February 2006. ISSN 0167-8655.
CARVALHO, F. d. A. T. D.; TENóRIO, C. P. Fuzzy k-means clustering algorithms for intervalvalued data based on adaptive quadratic distances.
Fuzzy Sets Syst.,
Elsevier North-
Holland, Inc., Amsterdam, The Netherlands, The Netherlands, v. 161, p. 29782999,
December 2010. ISSN 0165-0114.
CARVALHO, F. d. A. T. de; SOUZA, R. M. C. R. de. Unsupervised pattern recognition models
for mixed feature-type symbolic data.
Pattern Recogn. Lett.,
Elsevier Science Inc., New
York, NY, USA, v. 31, p. 430443, April 2010. ISSN 0167-8655.
CHAVENT, M. A monothetic clustering method.
1998.
Pattern Recognition Letters, v. 19, p. 989996,
Referências Bibliográficas
92
CHAVENT M. E LECHEVALLIER, Y. Dynamical clustering algorithm of interval data: Optimization of an adequacy criterion based on hausdor distance.
Classication, Clustering
and Data Analysis, Springer, p. 53 59, 2002.
CHEN, Y. et al. Similarity-based classication: Concepts and algorithms.
The Journal of Ma-
chine Learning Research, v. 10, p. 747776, June 2009.
CHOUDHARI, A. et al. Mesh based clustering without stopping criterion. In:
Annual IEEE. [S.l.:
INDICON, 2005
s.n.], 2005. p. 530 534.
CONAN-GUEZ, B.; ROSSI, F.; GOLLI, A. E. Fast algorithm and implementation of dissimilarity self-organizing maps.
Neural Netw., Elsevier Science Ltd., Oxford, UK, UK, v. 19,
p. 855863, July 2006. ISSN 0893-6080.
COSTA, A. F. B. F. da; PIMENTEL, B. A.; SOUZA, R. M. C. R. de. K-means clustering for
symbolic interval data based on aggregated kernel functions. In:
22nd IEEE International
Conference on Tools with Articial Intelligence, ICTAI 2010, Arras, France - Volume 2.
[S.l.]: IEEE Computer Society, 2010. p. 375376. ISBN 978-0-7695-4263-8.
COSTA, A. F. B. F. da; PIMENTEL, B. A.; SOUZA, R. M. C. R. de. A kernel k-means
clustering method for symbolic interval data. In:
International Joint Conference on Neural
Networks, IJCNN 2010, Barcelona, Spain. [S.l.:
s.n.], 2010. p. 16. ISBN 978-1-4244-6916-
1.
CRISTIANINI, N.; J., S.-T.
An Introduction to Support Vector Machines ans other kernl-based
learning mehtods. [S.l.]:
Cambridge University Press, 2000.
CRISTIANINI, N. et al. On kernel-target alignment. In:
cessing Systems 14. [S.l.:
Advances in Neural Information Pro-
s.n.], 2002. v. 14, p. 367373.
CUI, X.; POTOK, T. E. Document clustering analysis based on hybrid pso+k-means algorithm.
Journal of Computer Sciences, Special Issue, p. 2733, 2005.
DHILLON, I. S.; GUAN, Y.; KULIS, B. Kernel k-means: spectral clustering and normalized
cuts. In:
Proceedings of the tenth ACM SIGKDD international conference on Knowledge
discovery and data mining. New York, NY, USA: ACM, 2004. (KDD '04), p. 551556.
Referências Bibliográficas
93
DIDAY, E. Orders and overlapping clusters hi pyramids.
Multidimensional Data Analysis,
DSWO Press, Leiden,, p. 201 234, 1986.
DIDAY, E. et al.
Éléments d'analyse de données. [S.l.]:
DIDAY, E.; NOIRHOMME-FRAITURE, M.
Dunod, 1982.
Symbolic Data Analysis and the SODAS Software.
New York, NY, USA: Wiley-Interscience, 2008. ISBN 0470018836, 9780470018835.
DIDAY, E.; SIMON, J. C. Clustering analysis.
Digital Pattern Classication, 1976.
EL-SONBATY, Y.; ISMAIL, M. A. On-line hierarchical clustering.
Pattern Recogn. Lett.,
El-
sevier Science Inc., New York, NY, USA, v. 19, p. 12851291, December 1998. ISSN
0167-8655.
FILIPPONE, M. et al. A survey of kernel and spectral methods for clustering.
Pattern Recog-
nition, v. 41, n. 1, p. 176190, January 2008.
GHOSH, A. K. Kernel discriminant analysis using case-specic smoothing parameters.
IEEE
Transactions on Systems, Man, and Cybernetics, Part B, v. 38, n. 5, p. 14131418, 2008.
GIROLAMI, M. Mercer kernel-based clustering in feature space.
IEEE Transactions on Neural
Networks, v. 13, p. 780784, 2002.
GORDON, A.
Classication. London, UK: Chapman Hall, 1999.
GORDON, A. An iteractive relocation algorithm for classifying symbolic data.
Data Analysis
: Scientic Modeling and Practical Application, Springer-Verlag, Berlin, p. 17 23, 2000.
GOWDA, K. C.; RAVI, T. V. Agglomerative clustering of symbolic objects using the concepts
of both similarity and dissimilarity.
Pattern Recogn. Lett., Elsevier Science Inc., New York,
NY, USA, v. 16, p. 647652, June 1995. ISSN 0167-8655.
GOWDA, K. C.; RAVI, T. V. Divisive clustering of symbolic objects using the concepts of both
similarity and dissimilarity.
Pattern Recognition, v. 28, n. 8, p. 12771282, 1995.
GRAVES, D.; PEDRYCZ, W. Kernel-based fuzzy clustering and fuzzy clustering: A comparative experimental study.
Fuzzy Sets Syst., Elsevier North-Holland, Inc., Amsterdam, The
Netherlands, The Netherlands, v. 161, p. 522543, February 2010. ISSN 0165-0114.
Referências Bibliográficas
94
GURU, D. S.; KIRANAGI, B. B.; NAGABHUSHAN, P. Multivalued type proximity measure
and concept of mutual similarity value useful for clustering symbolic patterns.
Pattern
Recogn. Lett., Elsevier Science Inc., New York, NY, USA, v. 25, p. 12031213, July 2004.
ISSN 0167-8655.
HARTUV, E.; SHAMIR, R. A clustering algorithm based on graph connectivity.
Inf. Process.
Lett., Elsevier North-Holland, Inc., Amsterdam, The Netherlands, The Netherlands, v. 76,
p. 175181, December 2000. ISSN 0020-0190.
HAYES-ROTH, F.; MCDERMOTT, J. An interference matching technique for inducing abstractions.
Commun. ACM,
ACM, New York, NY, USA, v. 21, p. 401411, May 1978.
ISSN 0001-0782.
HAYKIN, S.
Neural Networks: A Comprehensive Foundation. [S.l.]:
Prentice Hall, 1999. 409
412 p.
HE, J. et al. On quantitative evaluation of clustering systems.
Information Retrievel and Clus-
tering, 2002.
HEDJAZI, L.; AGUILAR-MARTIN, J.; LANN, M.-V. L. Similarity-margin based feature selection for symbolic interval data.
Pattern Recognition Letters,
v. 32, n. 4, p. 578585,
March 2011.
HONG, Y.; KWONG, S. Learning assignment order of instances for the constrained k-means
clustering algorithm.
Trans. Sys. Man Cyber. Part B, Institute of Electrical and Electron-
ics Engineers Inc., The, v. 39, p. 568574, April 2009. ISSN 1083-4419.
HUBERT, L.; ARABIE, P. Comparing partitions.
Journal of Classication, 1985.
ICHINO, M.; YAGUCHI, H. Generalized minkowski metrics for mixed feature-type data analysis.
Systems, Man and Cybernetics, IEEE Transactions on, v. 24, n. 4, p. 698 708, abr.
1994. ISSN 0018-9472.
JAIN, A. K. Data clustering: 50 years beyond K-means.
Pattern Recognition Letters,
n. 8, p. 651666, June 2010. ISSN 01678655.
JAIN, A. K.; DUBES, R. C.
Algorithms for Clustering Data. [S.l.]:
Prentice Hall, 1988.
v. 31,
Referências Bibliográficas
95
JAIN, A. K.; MURTY, M. N.; FLYNN, P. J. Data clustering: A review.
ACM Comput. Surv.,
1999.
JING L., Z. L. N. M. K.; HUANG, Z. Ontology-based distance measure for text clustering.
Proc. of SIAM SDM workshop on text mining, April 2006.
KAUFMAN, L.; ROUSSEEUW, P. J.
Analysis. 9th. ed. [S.l.]:
Finding Groups in Data: An Introduction to Cluster
Wiley-Interscience, 1990. Hardcover. ISBN 0471878766.
KAUFMAN, L.; ROUSSEEUW, P. J.
Finding Groups in Data: An Introduction to Cluster
Analysis (Wiley Series in Probability and Statistics). [S.l.]:
Wiley-Interscience, 2005. Pa-
perback. ISBN 0471735787.
KENNEDY, J.; EBERHART, R. Particle swarm optimization. In:
Proceedings., IEEE International Conference on.
Neural Networks, 1995.
[S.l.: s.n.], 1995. v. 4, p. 1942 1948
vol.4.
KIM, D. W. et al. Evaluation of the performance of clustering algorithms in kernel-induced
feature space.
KOHONEN, T.
Pattern Recognition, v. 38, n. 4, p. 607611, abr. 2005.
Self-organization and associative memory.
[S.l.]: Springer-Verlag New York,
Inc. New York, NY, USA, 1989.
KRISHNA, K.; MURTY, M. N. Genetic k-means algorithm.
Part B: Cybernetics, IEEE Transactions on,
Systems, Man, and Cybernetics,
v. 29, n. 3, p. 433 439, jun. 1999. ISSN
1083-4419.
MACQUEEN, J. B. Some methods for classication and analysis of multivariate observations.
In: CAM, L. M. L.; NEYMAN, J. (Ed.).
ematical Statistics and Probability.
Proc. of the fth Berkeley Symposium on Math-
[S.l.]: University of California Press, 1967. v. 1, p.
281297.
MICHALSKI, R. Aqval/1computer implementation of a variable-valued logic system vl/1
and examples of its application to pattern recognition.
Pattern Recognition, Washington, D. C., 1973.
Proc. First Int. Joint Conf. on
Referências Bibliográficas
96
MITRA, S.; PAL, S. K. Fuzzy sets in pattern recognition and machine intelligence.
Fuzzy Sets
and Systems, v. 156, n. 3, p. 381386, 2005.
NASSER, P.-A. H. A.; HAMAD, D. Clustering evaluation in feature space.
Articial Neural
Networks ICANN 2007, Lecture Notes in Computer Science, v. 4669, p. 321354, 2007.
PIMENTEL, B. A.; COSTA, A. F. B. F. da; SOUZA, R. M. C. R. de. Kernel-based fuzzy
clustering of interval data. In:
FUZZ-IEEE 2011, Proceedings of IEEE International
Conference on Fuzzy Systems, Taipei, Taiwan. [S.l.]:
IEEE, 2011. p. 497501.
PIMENTEL, B. A.; COSTA, A. F. B. F. da; SOUZA, R. M. C. R. de. A partitioning method
for symbolic interval data based on kernelized metric. In:
Proceedings of the 20th ACM
Conference on Information and Knowledge Management, CIKM 2011, Glasgow, United
Kingdom. [S.l.]:
ACM, 2011. p. 21892192. ISBN 978-1-4503-0717-8.
QUEVEDO V. PUIG, G. C. J. B. J. A. D. S. G. B. M. H. J.; MOLINA, A. Validation and
reconstruction of ow meter data in the barcelona water distribution network.
Control
Engineering Practice, n. 18, p. 640651, April 2010.
RAVI, T. V.; GOWDA, K. C. Clustering of symbolic objects using gravitational approach.
IEEE Transactions on Systems, Man, and Cybernetics, Part B,
v. 29, n. 6, p. 888894,
1999.
RAVI, T. V.; GOWDA, K. C. An isodata clustering procedure for symbolic objects using a
distributed genetic algorithm.
Pattern Recogn. Lett., Elsevier Science Inc., New York, NY,
USA, v. 20, p. 659666, July 1999. ISSN 0167-8655.
SATISH, D.; SEKHAR, C. Kernel based clustering and vector quantization for speech recognition. In:
Machine Learning for Signal Processing, 2004. Proceedings of the 2004 14th
IEEE Signal Processing Society Workshop. [S.l.:
s.n.], 2004.
SCHOLKOPF, B.; SMOLA, A.; MULLER, K.-R. Nonlinear Component Analysis as a Kernel
Eigenvalue Problem.
SOUZA, R. M. C. R. D.
Dinâmicas.
Neural Comp., v. 10, n. 5, p. 12991319, July 1998.
Métodos de Cluster para Intervalos usando Algoritmos do tipo Nuvens
[S.l.]: Tese de Doutorado. Centro de Informática, Universidade Federal de
Pernambuco, 2003.
Referências Bibliográficas
97
SOUZA, R. M. C. R. D.; CARVALHO, F. d. A. T. D. Dynamic clustering of interval data based
on adaptive chebyshev distances.
Electronics Letters, v. 40, n. 11, p. 658 660, maio 2004.
ISSN 0013-5194.
SOUZA, R. M. C. R. D.; CARVALHO, F. d. A. T. de. Clustering of interval data based on
city-block distances.
Pattern Recogn. Lett.,
Elsevier Science Inc., New York, NY, USA,
v. 25, p. 353365, February 2004. ISSN 0167-8655.
SOUZA, R. M. C. R. de; CARVALHO, F. d. A. T. de; PIZZATO, D. F. A partitioning method
for mixed feature-type symbolic data using a squared euclidean distance. Springer-Verlag,
Berlin, Heidelberg, p. 260273, 2007.
TAN, P.-N.; STEINBACH, M.; KUMAR, V.
Introduction to Data Mining. Us ed. [S.l.]:
Addison
Wesley, 2005. Hardcover. ISBN 0321321367.
TAN, X.; CHEN, S.; ZHANG, Z. hua Z. F. Robust face recognition from a single training image
per person with kernel-based som-face. In:
In ISNN. [S.l.:
s.n.], 2004. p. 858863.
TZORTZIS, G. F.; LIKAS, A. C. The global kernel k-means algorithm for clustering in feature
space.
Trans. Neur. Netw.,
Institute of Electrical and Electronics Engineers Inc., The,
v. 20, p. 11811194, July 2009. ISSN 1045-9227.
UCI.
UCI
Machine
Learning
databases.
In:
.
[s.n.],
2010.
Disponível
em:
<ftp://ftp.ics.uci.edu/pub/machine-learningdatabases>.
VERDE V., C. F. A. T. d. L. Y. A dynamical clustering algorithm for symbolic data.
25th An-
nual Conference of the German Classication Society, Tutorial on Symbolic Data Analysis, Munich, p. 59 71, 2001.
WANG, W.; YANG, J.; MUNTZ, R. R. Sting:
A statistical information grid approach to
spatial data mining. In: JARKE, M. et al. (Ed.).
on Very Large Data Bases. Athens, Greece:
WARWICK, K. M.; MORINEAU, A.
Twenty-Third International Conference
Morgan Kaufmann, 1997. p. 186195.
Multivariate Descriptive Statistical Analysis. New York,
NY, USA: John Wiley & Sons, Inc., 1984. ISBN 0471867438.
Referências Bibliográficas
XU, R.; WUNSCH D., I. Survey of clustering algorithms.
98
Neural Networks, IEEE Transactions
on, v. 16, n. 3, p. 645 678, maio 2005. ISSN 1045-9227.
ZANG D. Q. E CHEN, S. C. Kernel based fuzzy and possibilistic c-means clustering. In:
ceedings of the International Conference Articial Neural Network.
Pro-
Turkey: [s.n.], 2003.
p. 122125.
ZELNIK-MANOR, L.; PERONA, P. Self-tuning spectral clustering. MIT Press, p. 16011608,
2004.
ZHANG, D.-Q. et al. Kernel-based fuzzy clustering incorporating spatial constraints for image
segmentation. In:
Machine Learning and Cybernetics, 2003 International Conference on.
[S.l.: s.n.], 2003. v. 4, p. 2189 2192 Vol.4.
APÊNDICE A
RESULTADOS COMPLEMENTARES
Tabela A.1.
Resultado complementares do Índice DB referente ao gráco da Figura 4.6: Conj. de Dados 1.
Kernel de uma componente
Kernel de duas componentes
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
1
54.4753
58.4978
59.4639
59.9240
1
35.5763
36.5643
37.8064
39.2405
2
31.6759
42.6151
49.2456
53.0851
2
16.4238
17.0580
18.0034
19.3041
3
17.4878
24.1607
31.7093
38.1288
3
8.8864
9.2036
9.8937
10.7022
4
10.7174
13.9467
18.7025
24.0085
4
5.6022
5.7738
6.1858
6.8166
5
7.2656
8.9731
11.5873
15.0144
5
3.8377
3.9993
4.3144
4.6923
6
5.3287
6.1875
7.8041
9.8919
6
2.8875
2.9797
3.1864
3.4959
7
4.0425
4.6548
5.5806
6.9426
7
2.2476
2.3481
2.4820
2.7168
8
3.2357
3.6211
4.2330
5.1371
8
1.8259
1.9059
2.0435
2.2070
9
2.6662
2.9046
3.3460
4.0026
9
1.5345
1.6046
1.7223
1.8739
10
2.2479
2.4455
2.7609
3.2461
10
1.3249
1.3854
1.5069
1.6022
Tabela A.2.
Resultado complementares do Índice DB referente ao gráco da Figura 4.7: Conj. de Dados 2.
Kernel de uma componente
Kernel de duas componentes
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
1
20.4239
22.5530
23.2103
23.3312
1
13.4413
15.6641
17.3722
18.2817
2
11.8087
16.2980
19.2079
20.7095
2
7.0043
8.2563
9.6000
10.7750
3
7.2928
10.2508
13.4312
16.0829
3
4.3628
4.8974
5.5760
6.3912
4
5.0402
6.6643
8.9050
11.5124
4
2.9931
3.2478
3.6203
4.1690
5
3.7138
4.6332
6.1243
8.0421
5
2.1688
2.3342
2.5916
2.9740
6
2.8655
3.4189
4.3347
5.6474
6
1.6934
1.8014
1.9849
2.2449
7
2.2693
2.6345
3.2568
4.1092
7
1.3604
1.4426
1.5785
1.7960
8
1.8472
2.1200
2.5726
3.1443
8
1.1210
1.1872
1.3057
1.4763
9
1.5982
1.7611
2.0709
2.5009
9
0.9519
1.0151
1.1121
1.2622
10
1.3618
1.4954
1.7309
2.0620
10
0.8320
0.8860
0.9731
1.1024
100
Resultado complementares do Índice DB referente ao gráco da Figura 4.8: Conj. de Dados 3.
Tabela A.3.
Kernel de uma componente
Kernel de duas componentes
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
1
27.4191
29.2518
29.6976
29.9139
1
20.9350
22.0070
22.7733
23.6719
2
19.4094
23.5534
26.0380
27.4276
2
12.8379
13.6544
14.5450
15.6834
3
13.3028
16.8104
20.1276
22.4557
3
8.3246
9.2321
9.8638
10.6120
4
9.5927
11.8589
14.5710
17.0426
4
6.6225
6.9531
7.4344
7.9586
5
7.7061
8.8982
10.5197
12.7325
5
5.0770
5.2896
5.6602
6.0897
6
6.3962
7.2923
8.5196
9.8054
6
4.0750
4.1981
4.4350
4.7945
7
5.2756
5.8580
6.8664
7.9860
7
3.2109
3.2758
3.5369
3.7430
8
4.4673
4.8728
5.5982
6.4656
8
2.6561
2.6928
2.8931
3.0770
9
3.7688
4.0894
4.6989
5.4198
9
2.2140
2.2749
2.4535
2.6968
10
3.2269
3.4754
3.9551
4.5103
10
1.9352
1.9414
2.0691
2.2525
Resultado complementares do Índice DB referente ao gráco da Figura 4.9: Conj. de Dados 4.
Tabela A.4.
Kernel de uma componente
Kernel de duas componentes
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
1
22.1843
22.7497
22.5958
22.9081
1
19.4775
19.9944
20.2579
19.6886
2
17.0747
17.5378
17.7956
17.2816
2
13.6347
13.7792
13.9074
13.8074
3
13.2458
13.3999
13.5456
13.3929
3
9.8853
9.9945
10.1105
9.9485
4
10.4769
10.5964
10.8007
10.5874
4
7.8321
7.9341
7.9174
7.9675
5
8.6483
8.7304
8.8969
8.7545
5
6.6543
6.6576
6.5790
6.5889
6
7.5320
7.5938
7.5597
7.6529
6
5.5586
5.5771
5.5826
5.5780
7
6.7619
6.7386
6.6397
6.6719
7
4.6992
4.7748
4.7020
4.7170
8
5.9628
5.9556
5.8889
5.9330
8
3.9051
3.8650
3.9145
3.9133
9
5.2455
5.2809
5.2973
5.2753
9
3.6946
3.6908
3.6935
3.6771
10
4.6420
4.7041
4.6574
4.6668
10
3.4995
3.5300
3.4978
3.5160
Tabela A.5.
Resultado complementares do Índice DB referente ao gráco da Figura 4.10: Conj. de Dados 5.
Kernel de uma componente
Kernel de duas componentes
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
Sigma
(σ )
[1, 5]
[1, 10]
[1, 15]
[1, 20]
1
24.9819
24.9953
25.0524
25.1993
1
15.7072
15.7371
15.7341
15.7064
2
11.3155
11.3528
11.3621
11.3004
2
7.3774
7.3770
7.4208
7.3353
3
7.0447
7.0527
7.0650
7.0278
3
4.7265
4.7241
4.7115
4.7404
4
5.0579
5.0724
5.0634
5.0767
4
3.7473
3.7479
3.7394
3.7391
5
4.1093
4.1114
4.0993
4.0990
5
3.3678
3.3626
3.3515
3.3498
6
3.6275
3.6303
3.6225
3.6184
6
3.2107
3.2044
3.2059
3.1949
7
3.3858
3.3826
3.3696
3.3685
7
2.9870
3.0453
3.0280
3.0748
8
3.2420
3.2432
3.2485
3.2402
8
2.6345
2.7703
2.6223
2.8316
9
3.1370
3.1688
3.1529
3.1631
9
2.2173
2.2472
2.3670
2.4431
10
2.9828
3.0399
2.9427
3.0333
10
1.9767
2.0500
1.9887
2.1449
101
Tabela A.6.
Partições geradas para o conjunto de dados Temperatura das cidades.
Método
DAU
Classe 1
3 4 6 7 13
16 18 19 30
DAC
2356
9 12 20 24
33
MKM-EC
34567
9 12 13 16
18 19 20 23
24 30 32
MKM-EE
3 4 7 12
13 16 18 30
FCMA
3456
7 9 12 13
16 18 24 30
McM-EC
3456
7 9 12 13
16 18 24 30
33
McM-EE
3456
7 9 13 17
18 24 30
Tabela A.7.
Método
DAU.
DAC
MKM-EC
MKM-EE
FCMA
McM-EC
McM-EE
Classe 2
1 8 10 11 15
17 21 22 24
26 29 31 34
35 36 37
1 8 10 11
14 15 17 21
22 25 26 27
28 29 31 34
35 36 37
1 2 8 10
11 14 15 17
22 25 26 27
28 29 33 34
36 37
1 2 8 10
11 14 15 17
21 22 25 26 27
28 29 31 33 34
35 36 37
2 9 11 12
15 16 22 23
26 27 29 32
36 37 38
Classe 3
15 23
20 23 27 28
Classe 4
25
9 12 24 33
19 23 32
4 7 13 16
18 30
21 31
34
5 6 9 20 24
19 23 32
19 20 23 32
2 17 27 29
33 34
1 2 8 10
11 14 15 17
22 25 26 27
28 29 34 35
36 37
1 8 10 11
14 15 21 22
25 26 27 28
29 31 34 35
36 37
21 31
19 20 23 32
17 33
2 12 19 20
23 32
Partições geradas para o conjunto de dados Agaricus
Classe E
1 2 3 4 5 6 7 8 10 11 12 13
14 16 17 18 19 20 21 22 23 24
1 3 5 7 8 9 10 11 12 13 15 17
19 20 21 22 23
1 3 4 5 6 7 8 9 10 11 12 13 15 16 17
19 20 21 22 23
1 3 4 5 6 7 8 9 10 11 12 13 15 16 17
19 20 21 22 23
2 4 6 11 13 14 16 17 18 20
21 22 23 24
1 2 3 5 6 7 8 9 10 11 12 13 15 16 17
19 20 21 22 23
1 2 3 5 6 7 8 9 10 11 12 13 15 16 17
19 20 21 22 23
Classe I
9 15
2 4 6 14 16 18 24
2 14 18 24
2 14 18 24
13578
9 10 12 15 19
4 7 14 18 24
4 7 14 18 24
102
Tabela A.8.
Método
DAU
DAC
MKM-EC
MKM-EE
FCMA
Partições geradas para o conjunto de dados Carros.
Utilitário
1 12 13 14
17 24 25 28
29 31
12 13 17 24
25 28 29 31
1235
8 14 18 21
26 30 32 33
1 12 13 14
17 24 25 28
29 31
12 13 17 24
25 28 29 31
McM-EC
12 13 17 24
25 28 29 31
McM-EE
12 13 17 24
25 28 29 31
Tabela A.9.
Sedan
2385
18 21 26 30
32 33
1235
8 14 21 26
30 32
12 13 17 24
25 28 29 31
2356
8 18 21 26
30 32 33
1235
8 14 18 21
26 30 32 33
1235
8 14 18 21
26 30 32 33
1 2 5 14
26 30 32 33
Luxo
6 7 9 10
22 23
Esportivo
4 11 15 16
19 20 27
6 7 9 10
18 22 23 33
4 11 15 16
19 20 27
6 7 9 10
22 23
4 11 15 16
19 20 27
7 9 10 22
23
4 11 15 16
19 20 27
6 7 9 10
20 22 23
4 11 15 16
19 27
6 7 9 10
22 23
4 11 15 16
19 20 27
3678
9 10 18 21
22 23
4 11 15 16
19 20 27
Partições geradas para o conjunto de dados Peixes.
Método
DAU
Classe 1
1234
Classe 2
789
Classe 3
569
Classe 4
11 12
DAC
234
1 7 8 10
56
9 11 12
MKM-EC
1234
7 8 9 10
5 6 12
11
MKM-EE
1234
7 8 9 10
5 6 12
11
FCMA
123
789
456
9 11 12
McM-EC
123
789
456
9 11 12
McM-EE
1234
5678
12
11
APÊNDICE B
TESTES DE HIPÓTESES
As tabelas presente neste anexo, apresentam as hipóteses nulas e alternativa e os valores observados das estatísticas de testes seguindo distribuição t-Student com
99 graus de liberdade.
valores das estatísticas de teste apresentam um nível de conança de
95%.
Estes
Foram realizados
quatorze testes independentes para cada conguração de dados articiais ou sintéticos.
Nas tabelas B.1 a B.5 considere
µ1 , µ2 , µ3
e
µ4
como as médias dos índices CR para os
métodos MKM-EC, MKM-EE, DAU e DAC, respectivamente.
Nas tabelas B.6 e B.7 considere
µ5 , µ6 , µ7
métodos MKM-EC (DBSig), MKM-EC (σ
e
µ8
= 1),
como as médias dos índices CR para os
MKM-EE (DBSig) e MKM-EE (σ
= 1),
respectivamente.
Nas tabelas B.8 a B.10 considere
µ9 , µ10 , µ11
e
µ12
como as médias dos índices CR para
os métodos MKM-EC (CLSig), MKM-EC (DBSig), MKM-EE (CLSig) e MKM-EE (DBSig),
respectivamente.
Nas tabelas B.11 a B.14 considere
µ13 , µ14
e
µ15
como as médias dos índices CR para os
métodos McM-EC, McM-EE e FCMA, respectivamente.
Tabela B.1.
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.1
Intervalo
H0 : µ1 = µ2
H1 : µ1 > µ2
H0 : µ1 = µ3
H1 : µ1 > µ3
H0 : µ1 = µ4
H1 : µ1 > µ4
t
t
t
[1, 5]
−2.6290
−17.7978
−15.7954
[1, 10]
−3.7147
−17.3460
−16.7695
[1, 15]
−0.3298
−13.5629
−12.20912
[1, 20]
−2.0796
−12.4349
−10.1709
104
Tabela B.2.
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.2
Intervalo
Tabela B.3.
H0 : µ1 = µ2
H1 : µ1 > µ2
H0 : µ1 = µ3
H1 : µ1 > µ3
H0 : µ1 = µ4
H1 : µ1 > µ4
t
t
t
[1, 5]
−18.6610
59.9495
88.0662
[1, 10]
−20.1274
33.9649
68.6737
[1, 15]
−19.3534
27.8549
37.2664
[1, 20]
−24.8268
27.2473
40.0365
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.3
Intervalo
Tabela B.4.
H0 : µ1 = µ2
H1 : µ1 > µ2
H0 : µ1 = µ3
H1 : µ1 > µ3
H0 : µ1 = µ4
H1 : µ1 > µ4
t
t
t
[1, 5]
43.0992
77.6305
84.6646
[1, 10]
41.6958
72.9971
83.7434
[1, 15]
36.4992
60.6572
72.5356
[1, 20]
33.7150
69.4620
68.3327
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.4
Intervalo
Tabela B.5.
H0 : µ1 = µ2
H1 : µ1 > µ2
H0 : µ1 = µ3
H1 : µ1 > µ3
H0 : µ1 = µ4
H1 : µ1 > µ4
t
t
t
[1, 5]
36.0653
77.6305
37.6764
[1, 10]
36.4964
72.9971
38.6453
[1, 15]
33.9273
60.6572
35.9458
[1, 20]
30.7068
69.4620
32.8649
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.5
Intervalo
H0 : µ1 = µ2
H1 : µ1 > µ2
H0 : µ1 = µ3
H1 : µ1 > µ3
H0 : µ1 = µ4
H1 : µ1 > µ4
t
t
t
[1, 5]
12.5682
43.0419
52.1767
[1, 10]
11.4268
32.9000
50.9174
[1, 15]
10.8408
34.2941
52.2110
[1, 20]
8.3796
37.6774
61.7497
105
Tabela B.6.
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.6
Intervalo
Tabela B.7.
H0 : µ5 = µ6
H1 : µ5 > µ6
H0 : µ7 = µ8
H1 : µ7 > µ8
t
t
[1, 5]
40.5205
132.5391
[1, 10]
39.0566
126.8179
[1, 15]
33.3974
128.7813
[1, 20]
29.7676
132.4504
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.7
Intervalo
Tabela B.8.
H0 : µ5 = µ6
H1 : µ5 > µ6
H0 : µ7 = µ8
H1 : µ7 > µ8
t
t
[1, 5]
7.3881
28.1809
[1, 10]
4.9263
28.4916
[1, 15]
7.1129
30.9473
[1, 20]
6.8773
29.8835
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.8
Intervalo
Tabela B.9.
H0 : µ9 = µ10
H1 : µ9 > µ10
H0 : µ11 = µ12
H1 : µ11 > µ12
t
t
[1.5]
6.4573
4.4374
[1.10]
10.5074
3.5769
[1.15]
11.7207
4.3669
[1.20]
12.9059
4.5114
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.9
Intervalo
H0 : µ9 = µ10
H1 : µ9 > µ10
H0 : µ11 = µ12
H1 : µ11 > µ12
t
t
[1.5]
1.8260
7.2191
[1.10]
3.1464
8.6761
[1.15]
5.2043
7.0356
[1.20]
7.4887
9.3765
106
Tabela B.10.
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.10
Intervalo
Tabela B.11.
H0 : µ9 = µ10
H1 : µ9 > µ10
H0 : µ11 = µ12
H1 : µ11 > µ12
t
t
[1.5]
0.0000
7.6786
[1.10]
3.8152
7.1940
[1.15]
2.8138
6.9329
[1.20]
8.8758
7.2273
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.11
Intervalo
Tabela B.12.
H0 : µ13 = µ14
H1 : µ13 > µ14
H0 : µ13 = µ15
H1 : µ13 > µ15
t
t
[1, 5]
−7.8887
17.4801
[1, 10]
−9.6252
14.3837
[1, 15]
−13.4511
7.9599
[1, 20]
−14.2087
−7.9745
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.12
Intervalo
Tabela B.13.
H0 : µ13 = µ14
H1 : µ13 > µ14
H0 : µ13 = µ15
H1 : µ13 > µ15
t
t
[1.5]
8.4794
20.7344
[1.10]
7.7062
19.7264
[1.15]
6.6690
10.5715
[1.20]
2.9231
0.8057
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.13
Intervalo
H0 : µ13 = µ14
H1 : µ13 > µ14
H0 : µ13 = µ15
H1 : µ13 > µ15
t
t
[1, 5]
−28.4339
78.1449
[1, 10]
−23.7744
72.5297
[1, 15]
−26.3065
76.2682
[1, 20]
−22.5664
67.2970
107
Tabela B.14.
Estatísticas de teste t-Student emparelhados referentes aos resultados da Tabela 4.14
Intervalo
H0 : µ13 = µ14
H1 : µ13 > µ14
H0 : µ13 = µ15
H1 : µ13 > µ15
t
t
[1.5]
20.8008
248.3378
[1.10]
18.4834
238.7483
[1.15]
12.0445
137.9158
[1.20]
6.4780
112.5686