Governo do Estado do Rio Grande do Norte
Secretariado de Estado da Educação e Cultura - SEEC
UNIVERSIDADE DO ESTADO DO RIO GRANDE DO NORTE - UERN
Pró-Reitoria de Pesquisa e Pós-Graduação – PROPEG
Departamento de Pesquisa
Campus Universitário BR-110, KM-46 - Costa e Silva – Fone: (084) 3315-2180 - Ramal 52180
CEP: 59600-970 - e-mail: [email protected]
FORMULÁRIO PARA APRESENTAÇÃO DE PROJETO DE PESQUISA - PIBIC
TÍTULO DO PROJETO
Mineração de Grafos usando Ontologias
COORDENADOR
Marcelino Pereira dos Santos Silva
Co-ORIENTADOR (Opcional)
Marilyn Cristine Serafim de Oliveira
ORIENTANDO
RENOVAÇÃO DE PROJETO *
SIM
✘
NÃO
1. RESUMO DO PROJETO (até 2000 caracteres com espaço)
Um dos grandes desafios da pesquisa em computação no Brasil é a modelagem computacional de sistemas complexos
artificiais, naturais e sócio-culturais e da interação homem-natureza. Avanços relevantes nestas áreas motivam um grande leque
de pesquisas, que integram algoritmos, estruturas de dados e modelos de diferentes disciplinas para propor novas abordagens. O
aumento do volume e da complexidade das bases de dados têm motivado a pesquisa de novas técnicas de mineração de dados.
Muitas destas bases possuem características estruturais, cujos dados são compostos por segmentos e relacionamentos entre
estes, o que remete à teoria dos grafos. Nesta ótica, a mineração de grafos pode viabilizar diferentes tarefas de descoberta de
conhecimento sobre bases de dados estruturais. Este projeto visa a utilização de um relevante formalismo matemáticocomputacional (grafos) para representar sistemas, estruturas e problemas reais com o intuito de realizar busca inteligente de
padrões (mineração de dados) nestes grafos através de uma âncora semântica: ontologias.
2. INTRODUÇÃO/JUSTIFICATIVA (até 7000 caracteres com espaço)
Um dos grandes desafios da pesquisa em computação no Brasil [SBC, 2006] é a modelagem computacional de sistemas
complexos artificiais, naturais e sócio-culturais e da interação homem-natureza. Avanços econômicos e sociais oriundos destas
áreas motivam um grande leque de pesquisas, que integram algoritmos, estruturas de dados e modelos de diferentes áreas para
propor novas abordagens. Este projeto caminha nesta direção, com a intenção de utilizar um relevante formalismo matemáticocomputacional (grafos) para representar sistemas, estruturas e problemas reais com o intuito de realizar a busca inteligente de
padrões (mineração de dados) nestes grafos através de uma âncora semântica: ontologias. No que segue, é contextualizado como
a mineração de grafos aliada a recursos de ontologia de domínios constitui-se em poderosa tecnologia computacional para a
modelagem, análise e compreensão de problemas complexos.
Um grafo é uma abstração matemática apropriada para resolver diferentes tipos de problemas. Fundamentalmente, um
grafo consiste de um conjunto de vértices, e de um conjunto de arcos (um arco conecta dois vértices). Um grafo consiste de um
par (V, E), onde V é um conjunto finito de vértices, e E é uma relação binária em V [Netto, 1996]. Diferentes modelos de grafos
(grafos hierárquicos, grafos relacionais de atributos, grafos conceituais etc.) agregam recursos à representação básica,
permitindo que estes sejam utilizados para representar e manipular informações em diferentes domínios: genética, bioinformática,
imagens, redes de computadores, fluxo de tráfego urbano, rotas aéreas, dentre outros. Além de ser um formalismo computacional
bem fundamentado e pesquisado, grafos representam naturalmente objetos e relacionamentos, através de uma abstração
poderosa e detentora de um grande número de algoritmos e abordagens.
Mineração de dados é o processo não trivial de identificar em dados padrões que sejam válidos, novos (previamente
desconhecidos), potencialmente úteis e compreensivos, visando melhorar o entendimento de um problema ou um procedimento
de tomada de decisão [Fayyad et al., 1996]. O aumento do volume e da complexidade das bases de dados têm motivado a
pesquisa de novas técnicas de mineração de dados. Muitas destas bases possuem características estruturais, cujos dados são
compostos por segmentos e relacionamentos entre estes. Assim, a mineração de grafos tem contemplado diferentes tarefas sobre
bases de dados estruturais. Iniciativas relevantes neste domínio são abordadas a seguir.
A mineração de subestruturas busca subgrafos semelhantes num conjunto de grafos. Subestruturas descobertas são
utilizadas para comprimir os dados originais, permitindo abstrair estruturas detalhadas e representar conceitos estruturais nestes
dados. Assim, uma subestrutura descoberta é usada para simplificar os dados, substituindo instâncias da subestrutura por um
1
ponteiro para esta nova subestrutura descoberta. A mineração de padrões de subestruturas é proposta por [Yan & Han, 2003]
utilizando a busca em profundidade em grafos (DFS). O trabalho argumenta que uma DFS gera uma ordem linear, que pode ser
mapeada para um “código DFS”, que por sua vez é minerado por um algoritmo específico. Esta abordagem reduz a complexidade
do grafo a uma estrutura linear, passível de mineração através de técnicas já consolidadas de mineração de dados convencionais.
A detecção de anomalias possui diferentes aplicações, como identificação de fraudes e descoberta de intrusões em
redes de computadores. [Noble & Cook, 2003] introduz duas técnicas para este domínio: a detecção de subestrutura anômala e a
detecção de subgrafo anômalo. A primeira examina um grafo inteiro e indica estruturas incomuns contidas nele, utilizando uma
variante do princípio MDL, uma vez que uma anomalia pode ser encarada como o oposto de padrão (padrões ocorrem
freqüentemente num grafo, anomalias não). Isto significa que subgrafos anômalos tendem a permitir menos compressão, pois
possuem poucos padrões comuns. Já a segunda técnica consiste na partição do grafo em estruturas distintas (subgrafos)
visando determinar o quão anômalo cada subgrafo é em comparação aos outros.
Neste contexto, representar problemas reais através de grafos constitui-se em estratégia atraente, uma vez que estes
grafos possam ser minerados. Estruturas de comunidades, de uso de redes de computadores, de fenômenos naturais ou de
interações químicas podem conter informações estratégicas não explícitas. Minerar eficientemente tais grafos significa extrair
padrões novos, úteis, válidos e compreensíveis, o que é extremamente relevante na compreensão de problemas complexos e no
processo de tomada de decisão.
Entretanto, gerar conhecimento a partir de padrões descobertos demanda embasamento semântico. Os trabalhos que
envolvem mineração de grafos não contemplam esta necessidade. Padrões estruturais resultantes da mineração de grafos
precisam de um arcabouço que expresse apropriadamente o significado da estrutura minerada. Nossa abordagem, que propõe a
efetivação desta tarefa através de ontologias, avança nesta área. Uma ontologia (como artefato de engenharia) descreve uma
certa realidade com um vocabulário específico, utilizando um conjunto de hipóteses relativas ao significado intencional das
palavras deste vocabulário [Fonseca & Egenhofer, 1999]. Pode-se também definir ontologia como teorias de conteúdos, as quais
possuem um conjunto geral de fatos a serem compartilhados, cuja principal contribuição é identificar classes específicas de
objetos e relacionamentos que existam em determinado domínio [Câmara et al., 2001]. Dentre os benefícios almejados pela
utilização de ontologias, podemos citar interoperabilidade (acesso mútuo de componentes a informações e funcionalidades),
pesquisa e navegação (utilização e meta-conhecimento para auxiliar engenhos de busca e estender consultas), reuso (evitando a
reconstrução de componentes existentes), e base de estruturação (redução de prazos e investimentos na construção de novos
componentes) [Menzies, 1999].
Neste sentido, esta proposta visa investigar e aplicar métodos e tecnologias amplamente pesquisadas, propondo
representar contextos relevantes [Han, 2007] (como redes de computadores, fenômenos sociais, genética, bioinformática,
interações químicas, fluxo de tráfego) através de grafos e, a partir da mineração destes com embasamento semântico
(ontologias), permitir que informações estratégicas não explícitas dos domínios representados sejam descobertas e
transformadas em conhecimento relevante.
O desenvolvimento de tecnologias estratégicas, através da pesquisa ora proposta, demanda pesquisadores
comprometidos e colaboradores envolvidos. O aporte da bolsa de iniciação cientifica
será fundamental para que um graduando (trabalhando em sintonia com o coordenador do projeto, co-orientador e um mestrando
com pesquisa nesta área) dedique-se às atividades de pesquisa, garantindo o efetivo sucesso do projeto.
* Em caso de renovação de projeto, o coordenador deverá explicitar as razões para tal, justificando com os dados preliminares.
3. OBJETIVOS (até 2200 caracteres com espaço)
- Investigar, avaliar e propor mecanismos de representação, otimização e mineração de grafos, bem como utilizar abordagens
ontológicas
que
representem
adequadamente
a
semântica
de
domínios.
- Buscar, analisar e desenvolver componentes de software que permitam modelar e analisar processos artificiais, naturais, sociais
ou
ambientais.
- Gerar novas abordagens e tecnologias que avancem nesta área de conhecimento, agregando conhecimento científico,
permitindo o estabelecimento de novas frentes de pesquisa, bem como o fomento de novos projetos e parcerias intra e inter
institucionais.
4. METODOLOGIA (até 4000 caracteres com espaço)
Através de estudo e levantamento bibliográfico, será verificado o estado-da-arte em modelagem de processos e sistemas
através de grafos. Serão avaliadas também técnicas e softwares de mineração de grafos e, caso estes não atendam plenamente às
demandas
desta
fase
inicial,
componentes
essenciais
serão
desenvolvidos.
A partir destes estudos e avaliações, serão realizados testes com as tecnologias de modelagem e mineração. Aplicações
em problemas reais definirão a abordagem de melhor custo-benefício computacional para os objetivos do projeto.
Estes problemas reais serão selecionados e uma ontologia de domínio prototípica será construída para os mesmos.
Precedendo esta construção, haverá o estudo das técnicas e ferramentas mais apropriadas para modelagem e definição de
2
elementos
semânticos,
visando
a
apropriada
representação
ontológica
do
problema.
Permeando as fases acima, estará a investigação de mecanismos que, além de mediar o processo de mineração, realizem
a adequada interface e processamento da ontologia definida para o domínio, ponto este estratégico para o mapeamento de
padrões
descobertos
que
permitam
a
geração
do
conhecimento.
Concluída a etapa de implementação, atividades de teste e validação da tecnologia desenvolvida serão realizadas com o
intuito de verificar a adequação, usabilidade e eficiência da arquitetura para o problema proposto.
A documentação e publicação do projeto será realizada conforme o cronograma apresentado, visando harmonizar e
sincronizar as diferentes atividades. Os documentos e publicações previstos são uma uma monografia de graduação, dois artigos
científicos e os relatórios técnicos pertinentes ao projeto.
5. RESULTADOS E APLICAÇÕES ESPERADAS (até 4000 caracteres com espaço)
A
partir
do
trabalho
desenvolvido
neste
projeto,
espera-se
que:
- sejam adquiridos novos conhecimentos e competências na exigente área da modelagem computacional, abstração por grafos,
mineração de dados avançada, representação/processamento semântico e descoberta de conhecimento relevante;
- a investigação científica realizada permita sugerir melhorias e implementar avanços nesta área;
- a abordagem computacional, através dos componentes implementados, contribua efetivamente com a redução de custos e o
aumento da eficiência no que tange à representação e compreensão de sistemas/processos complexos;
- o trabalho desenvolvido possibilite novas parcerias e gere novos tópicos de pesquisa na área;
- o conjunto destas atividades permita a elaboração de trabalhos acadêmicos de qualidade, dentre os quais monografias de
graduação e artigos científicos de alto nível.
6. REFERÊNCIAS BIBLIOGRÁFICAS (até 3000 caracteres com espaço)
Bratko,
I.
Prolog
Programming
for
Artificial
Intelligence.
Addison
Wesley,
2000.
- Câmara, G.; Egenhofer, M.; Fonseca, F.; Monteiro, A. M. V. What’s In An Image?, in Conference on Spatial Information Theory,
Santa
Barbara,
2001.
Elmasri,
R.,
Navathe,
S.
Fundamentals
of
Database
Systems.
Addison
Wesley,
2006.
- Fayyad, U. M.; Piatesky-Shapiro, G.; Smith, P. Advances in Knowlege Discovery and Data Mining. Massachusetts: MIT Press,
1996.
560
p.
- Fonseca, F.; Egenhofer, M., Ontology-Driven Geographic Information Systems, ACM GIS’ 99, Kansas City, 1999.
- Gonzalez, J.; Holder, L.; Cook, D. Graph-Based Concept Learning. American Association for Artificial Intelligence, 2001.
Han,
J.,
Kamber,
M.
Data
Mining:
Concepts
and
Techniques.
Morgan
Kaufmann,
2006.
- Han, J. Research Frontiers in Advanced Data Mining Technologies and Applications. Advances in Knowledge Discovery and Data
Mining
–
LNCS,
Springer,
2007.
- Holder, L.; Cook, D.; Gonzalez, J.; Jonyer, I. Structural Pattern Recognition in Graphs, in Pattern Recognition and String Matching,
Kluwer
Academic
Publishers,
2002.
Menzies,
T.
Cost
Benefits
of
Ontologies,
in
Intelligence,
Fall
1999.
p.
27-31.
- Netto, P. O. B. Grafos: Teoria, Modelos e Algoritmos. Edgard Blucher Ed., 1996. 304 p.
- Noble, C.; Cook, D. Graph-Based Anomaly Detection, in ACM International Conference on Knowledge Discovery and Data Mining,
2003.
- Sociedade Brasileira de Computação. Grandes Desafios da Pesquisa em Computação no Brasil – 2006 – 2016. Relatório sobre o
Seminário
realizado
em
8
e
9
de
maio
de
2006
em
São
Paulo.
- Yan, X.; Han, J. GSpan: Graph-Based Substructure Pattern Mining, in International Conference on Data Mining, Japan, 2003.
7. ORÇAMENTO
RUBRICAS/DISCRIMINAÇÃO
Material de Consumo
Quantidade
Valor Individual R$
Valor Total R$
3
Serviço de Terceiros Pessoa Física
Serviço de Terceiros Pessoa Jurídica
Total de Material de Consumo
Quantidade
Valor Unitário R$
Total de Serviço de Terceiros Pessoa Física
Valor Total R$
Quantidade
Valor Unitário R$
Total de Serviço de Terceiros Pessoa Jurídica
Valor Total R$
Passagens/Trecho
Passagem Natal-Rio-Natal
Quantidade
01
Valor Unitário R$
1.000,00
Passagens – Total
Valor Total R$
1.000,00
1.000,00
Diárias
Diária para atividade técnica fora da cidade
Quantidade
05
Valor Unitário R$
100,00
Diárias - Total
Valor Total R$
500,00
500,00
4
Bolsa de iniciação científica
Quota de bolsa Pibic
Quantidade
Valor Unitário R$
12
300,00
Bolsa de Iniciação Científica - Total
VALOR TOTAL DO PROJETO
Valor Total R$
3.600,00
3.600,00
5.100,00
8. TERMO DE COMPROMISSO DO SOLICITANTE
Declaro, para fins de direito, conhecer as normas gerais fixadas pelo presente edital, pelo CNPq e pela UERN para a concessão de Bolsas
de Iniciação Científica.
Mossoró, 17 de Abril de 2009.
Assinatura do(a) Coordenador(a)
5