Boletim
Ano 8 Número 16
Outubro de 2010
Informativo do Grupo de Pesquisa
Matemática Computacional
-------------------------------------------------------------------------------------------------------------PONTIFÍCIA UNIVERSIDADE CATÓLICA DE GOIÁS (PUC GOIÁS)
DEPARTAMENTO DE COMPUTAÇÃO
-------------------------------------------------------------------------------------------------------------EDITORIAL
Temos a satisfação de publicar mais um número do Boletim para os interessados em
Computação. Em particular, em Matemática Computacional.
Pensamos que através deste Boletim poderemos observar a relevância do Grupo no
País devido, principalmente, às premiações de seus membros e às nossas publicações.
A principal novidade do Grupo é a premiação de nossos pesquisadores e a
publicação de dois livros em uma semana por um de nossos pesquisadores. O pesquisador
Nelson Maculan Filho recebeu o Prêmio de Mérito Científico 2010 pela Sociedade
Brasileira de Computação (SBC) e o pesquisador Leizer de Lima Pinto será o representante
do Programa de Engenharia de Sistemas e Computação da Universidade Federal do Rio de
Janeiro (PESC/UFRJ) para concorrer ao Prêmio CAPES de Teses 2010, dentre as vinte
teses de doutorado defendidas em 2009 no PESC/UFRJ. Maiores detalhes sobre o prêmio
CAPES de Teses está na seção Perguntas e Respostas. Também, o pesquisador Marco
Antonio Figueiredo Menezes publicou um livro com o colega Antônio César Baleeiro
Alves (professor da UFG) e um segundo com o técnico Marcello Marinho Ribeiro
(mestrando na UnB). Veja na subseção Livros publicados.
Os integrantes do grupo no momento são: como pesquisadores, Clarimar José
Coelho, Marco Antonio Figueiredo Menezes, Sibelius Lellis Vieira (PUC Goiás),
Humberto José Longo, Leizer de Lima Pinto, Telma Woerle de Lima Soares (UFG),
Claudio Thomas Bornstein, Nelson Maculan Filho (COPPE-PESC/UFRJ) e Maria do
Socorro Nogueira Rangel (UNESP-São José do Rio Preto); como estudantes, Arinéia
Nogueira de Assis, Dalilla da Mota Morais, Douglas Machado de Freitas, Francisco de
Assis Rodrigues dos Anjos, Gustavo Siqueira Vinhal, Heber Valdo Nogueira, Kelligton
Fabrício de Souza Neves, Lino Lopes de Barros Filho, Paulo Henrique de Oliveira Souza,
Tiago da Silva Curtinhas (PUC Goiás) e Elivelton Ferreira Bueno (Universidade de
Montreal/Canadá); e como técnicos, Anderson da Silva Soares, Arlindo Rodrigues Galvão
Filho, Synara Rosa Gomes dos Santos (ITA), Gustavo Teodoro Laureano (USP/São
Carlos), Ivon Rodrigues Canedo (PUC Goiás) e Marcello Marinho Ribeiro (UnB).
Marco Antonio Figueiredo Menezes
Líder do Grupo
--------------------------------------------------------------------------------------------------------------
1
PERGUNTAS E RESPOSTAS: Sobre o Prêmio CAPES de Teses.
Aqui, a nossa idéia é a de levantar algumas perguntas para os alunos da Computação
que venham a esclarecer, viabilizar e integrar a sua formação. Em seguida, forneceremos as
devidas respostas através de entrevistas com responsáveis pela área.
O que é o Prêmio CAPES de Tese?
O Prêmio CAPES de Tese objetiva outorgar distinção às melhores teses de
doutorado defendidas e aprovadas nos cursos reconhecidos pelo Ministério da Educação.
Este prêmio é outorgado para a melhor tese de doutorado de cada uma das áreas do
conhecimento reconhecidas pela CAPES, onde os critérios considerados para a escolha são
a originalidade e a qualidade do trabalho.
O Grande Prêmio CAPES de Tese.
As teses premiadas no Prêmio CAPES de Tese são agrupadas pelos três grupos de
grandes áreas, que são:
• Áreas de Ciências Biológicas, Ciências da Saúde e Ciências Agrárias;
• Áreas de Engenharias e Ciências Exatas e da Terra;
• Áreas de Ciências Humanas, Lingüística, Letras e Artes, Ciências Sociais
Aplicadas e Ensino de Ciências.
Então, é selecionada a melhor tese de cada uma dessas três grandes áreas, as quais
recebem o Grande Prêmio CAPES de Tese.
Para saber mais sobre o Prêmio CAPES de Tese e o Grande Prêmio CAPES de Tese
visite a página da CAPES: http://www.capes.gov.br/premios-capes-de-teses.
----------------------------------------------------------------------------------------------------------ACONTECEU
Aconteceu informa Congressos, Simpósios, Jornadas e Encontros Científicos com a
nossa participação, de março/2010 a setembro/2010.
33ª Reunião Anual da Sociedade Brasileira de Química: 28 a 31 de maio de 2010,
Águas de Lindóia/SP.
XXX Congresso da Sociedade Brasileira de Computação: 20 a 23 de julho de 2010,
Belo Horizonte/MG.
XLI Simpósio Brasileiro de Pesquisa Operacional: 30 de agosto a 03 de setembro de
2010, Bento Gonçalves/RS.
XXXIII Congresso Nacional de Matemática Aplicada e Computacional: 20 a 23 de
setembro de 2010, Águas de Lindóia/SP.
2
-------------------------------------------------------------------------------------------------------------ACONTECENDO
Acontecendo relata as atividades do Grupo Matemática Computacional. Sugerimos
uma visita ao nosso MURAL, em frente ao Departamento de Computação e no final do
corredor em frente a sala 409, bloco F, área 3.
Seminário de Otimização: Toda sexta-feira, das 17h às 18h, na Área 3, Bloco F, Sala 409.
Coordenador: Dr. Marco Antonio Figueiredo Menezes.
Seminário de Análise Multivariada: Toda terça-feira, das 17 às 18h, na Área 3, Bloco F,
Sala 409. Coordenador: Dr. Clarimar José Coelho.
Projetos em andamento:
1.
Manutenção e desenvolvimento do LabPL (quinto ano –
http://agata.ucg.br/formularios/vpg/projeto/admin/ficha_cadastro.asp?inscricao=2513
)–
Coordenador: Marco Antonio; PROPE/PUC GOIÁS.
Desenvolvimento de aplicativo para dar apoio ao gerenciamento da grade
horária na Universidade Católica de Goiás (terceiro ano http://agata.ucg.br/formularios/vpg/projeto/admin/ficha_cadastro.asp?inscricao=3289 ) Coordenador: Marco Antonio; PROPE/PUC GOIÁS.
2.
3.
Quimiometria baseada em técnicas de processamento de sinal (terceiro
http://agata.ucg.br/formularios/vpg/projeto/admin/ficha_cadastro.asp?inscricao=3387 ) -
ano -
Coordenador Clarimar; PROPE/PUC GOIÁS.
Estudo de autenticidade de documentos por meio da análise de tintas de
canetas empregando a Micro-espectrometria no Infravermelho e Raman (primeiro
ano - http://agata.ucg.br/formularios/vpg/projeto/admin/ficha_cadastro.asp?inscricao=3834 ) Coordenador Clarimar; PROPE/PUC GOIÁS.
4.
Combustíveis Importados – Calibração por FTIR e transferência para 35
laboratórios da PF (primeiro ano http://agata.ucg.br/formularios/vpg/projeto/admin/ficha_cadastro.asp?inscricao=3835 ) Coordenador Clarimar; PROPE/PUC GOIÁS.
5.
6.
Otimização da Gestão da Cadeia de Suprimentos (primeiro ano http://agata.ucg.br/formularios/vpg/projeto/admin/ficha_cadastro.asp?inscricao=3801 ) -
Coordenador Sibelius; PROPE/PUC GOIÁS.
Orientações em andamento:
1. Sobre o problema de designação de salas de aula – Aluno Kelligton Fabrício de
Souza Neves; Orientador: Marco Antonio Figueiredo Menezes; Trabalho de
Conclusão de Curso II.
3
2. Implementação de um algoritmo randômico para programação linear – aluno Lino
Lopes de Barros filho; Orientador: Marco Antonio Figueiredo Menezes; Iniciação
Científica, Voluntário.
3. Um estudo sobre o problema designação turmas-salas – Aluna Arinéia Nogueira de
Assis; Orientador: Marco Antonio Figueiredo Menezes; Iniciação Científica,
Voluntária.
-------------------------------------------------------------------------------------------------------------ACONTECERÁ
Acontecerá informa eventos nos próximos meses no que concerne às atividades de
pesquisa.
VI Semana de Ciência e Tecnologia da PUC Goiás: 19 a 23 de outubro de 2010,
Goiânia/Goiás.
-------------------------------------------------------------------------------------------------------------PRODUÇÃO CIENTÍFICA
Divulgação da produção científica. Este Boletim divulga o período março/2010setembro/2010.
Livros publicados:
1. A. C. B. Alves e M. A. F. Menezes. Introdução à pesquisa operacional. Goiânia:
Editora da PUC Goiás, 2010, 311p.
2. M. M. Ribeiro e M. A. F. Menezes. Uma breve introdução à computação gráfica.
Rio de Janeiro: Editora Ciência Moderna, 2010, 88p.
Trabalhos publicados em revistas:
J. A. M. Brito, N. Maculan, M. Lila e F. M. T. Montenegro. An exact algorithm for
the stratification problem with proportional allocation. Optimization Letters. Vol. 4,
N. 2, p. 185-195, 2010.
2. A. P. de Lucena, N. Maculan e L. G. Simonetti. Reformulations and solution
algorithms for the maximum leaf spanning tree problem. Computational
Management Science, Vol. 7, N. 3, p. 289-311, 2010.
3. L. L. Pinto e G. Laporte. An efficient algorithm for the Steiner Tree Problem with
revenue, bottleneck and hop objective functions. European Journal of Operational
Research, Vol. 207, N. 1, p. 45-49, 2010.
4. L. L. Pinto e M. M. B. Pascoal. On algorithms for the tricriteria shortest path
problem with two bottleneck objective functions. Computers & Operations
Research, Vol. 37, N. 10, p. 1774-1779, 2010.
1.
4
Trabalhos publicados em congressos:
1.
Da Silva, A. L. B., Pedrosa, L. Vicente, S. Da C. Coelho, C. J. Emprego das
técnicas de reamostragem bagging e subbaging em calibração multivariada, I
Simpósio de Ciência e Meio Ambiente, Anápolis, 2010.
Orientações concluídas:
1. Filtro de Kalman, Aluno: Gustavo Siqueira Vinhal; Orientador: Clarimar José
Coelho, Iniciação Científica.
2. Spline Cúbica, Aluno: Tiago Curtinhas; Orientador: Clarimar José Coelho, Iniciação
Científica.
-------------------------------------------------------------------------------------------------------------ARTIGO
Métodos de Particionamento de Dados para Problemas de
Calibração Multivariada
Márcio Félix Reis
Departamento de Computação
Pontifícia Universidade Católica de Goiás (PUC Goiás)
Introdução
A Calibração Multivariada é uma área da química analítica que busca um modelo
matemático que descreva a relação entre medidas indiretas obtidas por um método
instrumental e medidas diretas obtidas por métodos convencionais [1]. As medidas indiretas
são fáceis de adquirir, mas as medidas diretas são difíceis. Por isso, criamos modelos
matemáticos para predição de medidas diretas de amostras desconhecidas a partir de
medidas indiretas. Os métodos de calibração multivariada mais usados são regressão linear
múltipla (MLR), regressão por componentes principais (PCR) e regressão por mínimos
quadrados parciais (PLS) [2].
Antes da aplicação do modelo construído, o mesmo deve ser validado com o
objetivo de testar a sua capacidade preditiva [3]. Uma boa maneira de validarmos o modelo
seria a coleta de novos dados que poderiam ser comparados com a predição do modelo, mas
isso nem sempre é possível [4]. Nesse contexto, podemos simular a coleta de novos dados
dividindo os dados em dois subconjuntos, chamados de treinamento e validação. O
conjunto de treinamento é usado para estimar os coeficientes do modelo e o de validação
para medir a previsão do modelo.
A seguir vamos descrever métodos usados para particionamento de conjuntos de
dados em subconjuntos representativos de treinamento e validação.
5
Amostragem Aleatória - RS
A Amostragem Aleatória (RS) é uma técnica popular devido à sua simplicidade e
também porque um grupo de dados extraído aleatoriamente de um conjunto maior segue a
distribuição estatística de todo o conjunto [5]. O método RS particiona o conjunto de dados
selecionando aleatoriamente as amostras de treinamento e teste. Isto não garante a
representatividade dos conjuntos [5]. Sua vantagem é a simplicidade.
Vale ressaltar que existe a possibilidade de geração de sequências aleatórias nos
computadores atuais, mas em geral usamos sequências pseudo aleatórias, que são geradas
por algoritmos determinísticos.
Nesse trabalho usamos a função rand do Matlab que gera sequências pseudo
aleatórias com distribuição uniforme.
Algoritmo
1. Selecione uma amostra aleatoriamente.
2. Volte para 1 até que o número de amostras selecionadas seja suficiente.
Kennard-Stone - KS
O algoritmo Kennard-Stone (KS) visa selecionar um subconjunto representativo de
um conjunto de N amostras. Para isso o algoritmo emprega a distância Euclidiana d x(p, q)
entre os x-vetores de cada par (p, q) de amostras calculada como
(1)
onde N é o número de amostras e J é o numero de variáveis.
A seleção começa pelo par (p1, p2) mais distantes e a cada iteração o algoritmo
seleciona mais uma amostra maximizando as distâncias mínimas entre as amostras já
selecionados e as remanescentes.
Algoritmo
1. Selecione duas amostras mais distantes usando a medida de distância Euclidiana.
2. Para cada amostra não selecionada, armazene em uma lista a menor distância
Euclidiana para uma amostra selecionada.
3. Da lista de menor distâncias, selecione a amostra com distância máxima.
4. Volte para 2 até que o número de amostras selecionadas seja suficiente.
Figura 1: Ilustração do Algoritmo KS.
6
A figura 1. a) mostra as duas amostras inicialmente selecionadas (indicadas com as
caixas) que estão mais distantes. A figura 1. b) mostra as menores distâncias euclidianas
das amostras não selecionadas para as selecionadas. A figura 1. c) mostra a seleção da
amostra com a maior distância Euclidiana.
O algoritmo KS pode ser usado para dividir o conjunto de dados em duas partes
iguais: um conjunto de treinamento (as amostras selecionadas) e um conjunto de validação
(as amostras restantes). Uma desvantagem do KS é a sensibilidade para outliers, o que pode
comprometer todo o processo de seleção de amostras: as amostras mais distantes são
selecionadas primeiro [6]. Este método provou ser útil [5, 6, 7].
Particionamento de Conjunto de Amostras Baseado em Distâncias x-y
Comuns - SPXY
O método SPXY foi proposto em [5] e consiste da inclusão na distância definida na
equação (1) da distância referente à variável dependente y. A distância d y(p, q) pode ser
calculada como
(2)
onde N é o numero de amostras.
A fim de atribuir importância igual à distribuição das amostras nos espaços x e y, as
distâncias dx(p, q) e dy(p, q) são divididas pelos seus valores máximos no conjunto de
dados. Desta forma, a uma distância xy normalizada é calculada como
(3)
Um procedimento de seleção similar ao algoritmo KS pode ser aplicado com a
distância dxy(p, q) ao invés da dx(p, q).
Em relação ao esforço computacional, SPXY é comparável com o KS, pois ambos
os algoritmos empregam simples cálculos de distância [5].
Validação Cruzada
A validação cruzada é uma técnica de validação com base apenas nos dados de
calibração [1]. Primeiro, uma amostra do conjunto de calibração é excluída. Em seguida, a
calibração é realizada sobre o resto das amostras e ela é testada na primeira amostra,
comparando y com y . A primeira amostra é então colocada de volta no conjunto de
calibração, e o procedimento é repetido excluindo a amostra dois. O processo continua até
que todas as amostras foram excluídas uma vez.
7
Uma vantagem da validação cruzada é que a validação pode ser feita sem que o
conjunto de calibração seja dividido previamente, aumentando o número de amostras
disponíveis para calibração.
Material e Métodos
Os dados usados no trabalho foram obtidos por meio de um espectrômetro. Esses
dados estão organizados na forma de uma matriz X e um vetor y. A matriz X tem 100
linhas (amostras) e 701 colunas (comprimentos de onda), onde Xi,j é a absorção da amostra
i no comprimento de onda j. O vetor y tem 100 linhas e uma coluna, onde y i é a
concentração de proteína na amostra i.
Os modelos de calibração multivariada foram obtidos utilizando o Algoritmo de
Projeções Sucessivas [2] e a MLR com diferentes subconjuntos de dados. Os dados foram
divididos em 3 subconjuntos, chamados calibração (50 amostras), validação (25 amostras) e
teste (25 amostras) utilizando os métodos RS, KS e SPXY. A calibração feita com os
subconjuntos particionados pelo RS foi repetida 10 vezes, usando diferentes sementes para
geração de números pseudo-aleatórios, e o resultado apresentado é a média dos resultados
obtidos.
A implementação foi feita utilizando o programa Matlab.
Resultados
O índice utilizado para comparar o quanto o valor predito se aproxima da
concentração esperada é a raiz quadrada do erro quadrático médio de predição (RMSEP)
que é dado por
(4)
onde y i é a i-ésima concentração predita pelo modelo de regressão.
Os resultados da predição usando os métodos de Amostragem Aleatória (RS),
Kennard-Stone (KS), Particionamento de Conjunto de Amostras Baseado em Distâncias xy Comuns (SPXY) e Validação Cruzada (CV) são apresentados na Tabela 1. A primeira
coluna da tabela 1 mostra o nome dos métodos utilizados. A segunda coluna mostra o
RMSEP. A terceira apresenta o tempo médio de execução em segundos. A quarta coluna
mostra o número de variáveis selecionadas.
Método
RMSEP
tempo (s) número de variáveis selecionadas
RS
0,62
15
22
KS
0,48
14,8
11
SPXY
0,49
14,7
22
CV
0,17
7698,8
77
Tabela 1: Resultados
8
O tempo de execução dos métodos RS, KS e SPXY são próximos de 15 segundos.
A CV apresentou o menor RMSEP e o maior tempo de execução.
Conclusão
Foi apresentado neste trabalho o uso de métodos de particionamento de dados em
problemas de calibração multivariada. Como exemplo de aplicação foi feita a determinação
da concentração de proteína em amostras de trigo. A comparação entre os métodos foi
apresentada. Conclui-se que os resultados obtidos com a Validação Cruzada em termos de
RMSEP são melhores do que os resultados obtidos com os outros métodos. Observa-se
ainda a significativa desvantagem em termos de custo computacional da Validação
Cruzada.
Referências
Tormod Naes, Tomas Isaksson, Tom Fearn, Tony Davies, A User Friendly Guide to
Multivariate Calibration and Classification - NIR Publications 2002.
[2] Mário César Ugulino Araújo, Teresa Cristina Bezerra Saldanha, Roberto Kawakami
Harrop Galvão, Takashi Yoneyama, Henrique Caldas Chame, Valeria Visani, The
successive projections algorithm for variable selection in spectroscopic
multicomponent anasysis, Chem. and Int. Lab. Syst. 57 (2001) 65 - 73.
[3] Márcia M. C. Ferreira, Alexandre M. Antunes, Marisa S. Melgo e Pedro L. O.
Volpe, Quimiometria I: calibração multivariada, um tutorial, Quím. Nova vol.22 n.5
São Paulo Sept./Oct. 1999.
[4] Ronald D. Snee, Validation of Regression Models: Methods and Examples,
Technometrics, Vol. 19, No. 4. (Nov., 1977), pp. 415-428.
[5] Roberto Kawakami Harrop Galvão, Mário César Ugulino Araujo, Gledson Emídio
José, Marcio José Coelho Pontes, Edvan Cirino Silva, Teresa Cristina Bezerra
Saldanha, A method for calibration and validation subset partitioning, Talanta 67
(2005) 736 - 740.
[6] P. J. de Groot, G. J. Postma, W. J. Melssen, L. M. C. Buydens, Selecting a
representative training set for the classification of demolition waste using remote
NIR sensing, Analytica Chimica Acta 392 (1999) 67 - 75.
[7] Karmen Rajer-Kanduˇc, Jure Zupan, Nineta Majcen, Separation of data on the
training and test set for modelling: a case study for modelling of five colour
properties of a white pigment, Chem. and Int. Lab. Syst. 65 (2003) 221 - 229.
-------------------------------------------------------------------------------------------------------------[1]
INFORMAÇÕES E CONTATO
Página Principal: http://agata.ucg.br/formularios/NPI/matematicacomp_index.htm
Página do boletim: http://agata.ucg.br/formularios/NPI/matematicacomp_boletim.htm
[email protected]
9