Aluno: Rodrigo Estevan BelaOrientadora: Profa. Dra. Marilde T. P. SantosCo-Orientador: Prof. Dr. Mauro Biajiz

Ontologias de domínio auxiliando tarefas de mineração de dados:anotações semânticas e filtros de regras

2/42

Contextualização

Proposta

Estudo de Caso

Trabalhos Correlatos - Discussão

Conclusão

Agenda

3/42

Contextualização▪ Mineração de Dados

▪ Desafios de pesquisa

▪ Ontologias▪ Anotações

PropostaEstudo de CasoDiscussão - Trabalhos CorrelatosConclusão

Agenda

4/42

Extração de conhecimento de bases de dados é o processo de identificação de padrões válidos, novos, potencialmente úteis e compreensíveis embutidos nos dados [Fayyad, U., G.P. Shapiro, and P. Smyth, 1994]

Utiliza processos não convencionais para realizar a extração dos padrões.

Envolve técnicas de diversas áreas Banco de Dados, Estatística, Aprendizado de Máquina,

Reconhecimento de Padrões, Inteligência Artificial e outras.

Mineração de Dados

5/42

Processo iterativo e interativo

Conhecimento do domínio tem impacto em todas as etapas

O conhecimento sobre o domínio subsidia tomadas de decisão nas etapas subsequentes do processo de Mineração de Dados [Melanda, E. A., 2004] Extraído do Livro Sistemas Inteligentes. Capítulo sobre Mineração de Dados.

Rezende, S. O. 1 ed. 2003

O processo de Mineração de Dados

6/42

Tarefa de Extração de Regras de Associação

miiiiI ...,, 321 miiiiI ...,, 321 miiiiI ...,, 321

Identifica itemsets, conjuntos de itens que tendem a ocorrer juntos em transações.

Gera regras da forma: A B

Métricas de avaliação: Suporte: a porcentagem de transações, em

relação ao todo, que contém A e B; Confiança: a porcentagem de transações que

contém A que também contém B. Assim, se A B (suporte 0.4 / confiança

0.9): Então, 40% das transações contém A e B; Em 90% das vezes que a transação contém A,

ela também contém B.

7/42

Desempenho de algoritmos Avaliar automaticamente o grau de

interesse dos padrões encontrados Técnicas de visualização eficientes para

padrões mais complexos Enriquecer o processo com o

conhecimento do domínio Tratamento de informações já

conhecidas ou desinteressantes.

Desafios de Pesquisa em Mineração de Dados

8/42

Enriquecer o processo com o conhecimento do domínio

▪ Como representar o conhecimento?▪ Como utilizar o conhecimento como entrada

nos algoritmos de mineração?▪ Como e quais decisões podem ser tomadas pelo

algoritmo com base no conhecimento inserido? Tratamento de informações já conhecidas

ou desinteressantes.▪ Como tratar informações que já fazem parte do

conhecimento do domínio?

Desafios de Pesquisa em Mineração de Dados

9/42

Uma ontologia é uma especificação formal e explícita de uma conceitualização compartilhada [Gruber, T.R., 1993]

Conceitualização Explícita Formal Compartilhada

Ontologias

10/42

Uma ontologia é uma descrição explícita de um domínio, constituída por Conceitos [classes] Propriedades [atributos e relacionamentos] Axiomas [restrições sobre as propriedades] Instâncias [dos conceitos]

Uma ontologia define Um vocabulário comum Um entendimento compartilhado

Ontologias

11/42

Todo o conjunto de marcas, notas, breves comentários e explicações adicionais que são realizadas sobre algum tipo de conteúdo

O contexto e a forma de utilização definem formas especificas, como: Metadados Conteúdos Hipertexto Contexto

Anotações

12/42

Bibliotecas digitais

Web

Estratégias de busca

Banco de dados

Anotações: aplicações

13/42

ContextualizaçãoProposta

Problemas Anotações Semânticas Filtro de Regras

Estudo de CasoDiscussão - Trabalhos CorrelatosConclusão

Agenda

14/42

Problemas

Enriquecer o processo com o conhecimento do domínio Como explicitar o significado presente em

alguns conjuntos de dados brutos?

Como possibilitar a melhor visualização de dados brutos?

Tratamento de informações já conhecidas ou desinteressantes. Como tratar informações que já fazem parte do

conhecimento do domínio?

15/42

Como explicitar o significado de alguns conjuntos de dados?Anotações Semânticas!

Metadados adicionais que descrevem o significado.

Significado descrito usando termos controlados.

Utilização de ontologia de domínio para definir o significado e vocabulário.

Que possam ser geradas automaticamente.

16/42

Regras de Mapeamento1 <regra_de_mapeamento> ::= se <expressão> = verdadeiro

então <termo>

2 <termo> ::= <caractere> {<caractere>} α 3 <expressão> ::= <expressão_condicional>| <expressão_lógica>

4 <expressão_condicional> ::= <expressão_sql β> <operador> <valor_de_referência>

5 <operador> ::= = | > | < | !=

6 <valor_de_referência> ::= <caractere> {<caractere>}

7 <expressão_lógica> ::= <regra_de_mapeamento> <operador_lógico> <regra_de_mapeamento>

8 <operador_lógico> ::= AND | OR

9 <caractere>::=A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|X|Y|Z|0|1|2|3|4|5|6|7|8|9

α = o termo deve ser uma seqüência de caracteres que esteja presente na ontologia do domínio, ou seja, deve representar uma classe, propriedade ou relacionamento.β = considerar as regras de construção de expressões SQL definida pelo BNF Grammar for

ISO/IEC 9075-2:2003 – Database Language SQL (SQL-2003) - SQL/Foundation. Tabela com as regras de produção para geração de regras de mapeamento

Select avg(n.nota) as resultado from notas as n inner join aluno as a on n.aluno_id = a.id...

(Select avg(n.nota) as resultado from notas as n inner join aluno as a on n.aluno_id = a.id...) > 6.0

6,0

17/42

Semantic Annotation TOol - SATO

Representação das principais atividades realizadas na SATO

18/42

Semantic Annotation TOol – SATOcontinuação

Principais tela da SATO: A)Definição de um domínio; B) Definição de regra de mapeamento baseada em

consulta; C) Definição de regra de mapeamento lógica; D) Visualização de anotações semânticas geradas

19/42

Como tratar informações que já fazem parte do conhecimento do domínio?Utilizar conhecimento definido na

ontologia.

Considerar que termos da ontologia são um item dentro da regra

Considerar propriedades entre conceitos como associações já conhecidas.

Usuário define quais propriedades devem ser avaliadas.

20/42

Filtro de Regras

1 para cada regra

2 removerRegra verdadeiro;

3 para cada item do lado esquerdo da regra

4 para cada item do lado direito da regra

5 se item do lado esquerdo não tem relacionamento com lado direito

6 removerRegra falso;

7 fim se

8 fim para

9 fim para

10

Se removerRegra = verdadeiro então

11

listaDeRegrasASeremRemovidas regraAtual

12

fim se

13

fim para

Pseudocódigo do Filtro de Regras de Associação

maçã frango, maionese frangomaçã

associada_com

maçã frango, maionesemaçã frango, maionesemaçã frango, maionese

21/42

Algoritmo Filtered-NARFO

Aplicação de Filtro

Varrer a base

Identificar Itens Similares

Gerar Candidatos

Calcular o peso dos Candidatos

Avaliar os Candidatos

Gerar as Regras

Generalização e Tratamento de Redundância

Aplicação de FiltroGeneralização e Tratamento

de Redundância

Passos do algoritmo Filtered-NARFO.

22/42

ContextualizaçãoPropostaEstudo de Caso

Introdução – contexto Processo de Mineração de Dados

Discussão - Trabalhos CorrelatosConclusão

Agenda

23/42

Estudo de CasoIntrodução e contexto

Dados da ferramenta de ensino LECH-GEIC.

Ferramenta baseada no paradigma de Equivalência de Estímulos

Ferramenta desenvolvida no contexto do projeto TIDIA-Ae fase II.

Dados descrevem respostas dadas por estudantes durante interação com a ferramenta.

24/42

Estudo de CasoExemplo

Organização de um programa de Ensino

Exemplo dos dados coletados pela ferramenta

25/42

Estudo de CasoProcesso: Conhecimento do Domínio

Conhecimento sobre o domínioConstrução da ontologia de domínio

necessáriaDefinição dos objetivos do processo:

Verificar as relações de comportamento presentes nos dados;

Suporte e confiança como métricas de desempenho;

Conhecimento obtido deve ser claro e de fácil compreensão.

26/42

Estudo de CasoProcesso: Pré-processamento

Geração de anotações para um conjunto de 30 sessões de ensino.

Sessões referentes a um passo que ensina as relações AC (mts som-texto) e AE (cr som-texto) para as palavras: vaca, bolo e tatu.

Definição de regras de mapeamento para: Comportamentos/Termos a serem gerados:

▪ ACTreinoTatuSim, ACTreinoTatuNao e outras;

Geração de anotações para as latências observadas, como:▪ ACLatenciaMuitoBaixa, AELatenciaMuitoBaixae outras.

27/42

Estudo de CasoProcesso: Pré-processamento (2)

Redução da dimensionalidade dos dados sem perda de significado

ACTreinoTatuSIM

88 Tuplas

select if ((select count(se.id) from sessaoexec se inner join sessaoexec_passoexec sepe on se.id = sepe.sessaoexec_id inner join passoexec pe on pe.id = sepe.passosExecutados_id inner join passoexec_blocoexec pebe on pe.id = pebe.passoexec_id inner join blocoexec be on be.id = pebe.blocosExecutados_id inner join blocoexec_tentativaexec bete on be.id = bete.blocoExec_id inner join tentativaexec te on te.id = bete.tentativasExecutadas_id inner join tentativaexec_tentativainteracao teti on te.id = teti.tentativaexec_id inner join tentativainteracao ti on ti.id = teti.interacoes_id inner join blocotentativaocorrencia bto on bto.id = te.ocorrencia_id inner join passoblocoocorrencia pbo on pbo.id = be.ocorrencia_idwhere se.id = ?transacao? and bto.bloco_id = 18 and pbo.ocorrencia = 3) > 0….

28/42

Estudo de CasoProcesso: Extração de Padrões

Comparações entre 3 algoritmos de regras de associação: Apriori, NARFO e Filtered-NARFO.

Comparação de vários níveis de conhecimento.

Objetivos: Validar algoritmos; Validar filtro; Observar impacto do conhecimento no filtro; Atingir objetivos definidos pelo especialista no

processo;

29/42

Estudo de CasoProcesso: Extração de Padrões / Pós-processamento

12

5

3

4

Tabela com as interações realizadas

Versões da Ontologia de Domínio

ACLatenciaMuitoBaixa~ACLatenciaBaixaAETesteVacaNao,AETesteTatuNão sup=0.38 conf=0.85714287 (Possuindo item 'ACLatenciaBaixa' com maior relevância!!!)

ACLatenciaBaixaAETesteVacaNao,AETesteTatuNao sup=0.33333334 conf=0.90909094

AETeste->ACTreinoBoloNao sup=0.6333 conf=1.0

30/42

Estudo de CasoProcesso: Utilização do Conhecimento

Apresentação dos resultados a especialista do domínio;

Validação do filtro de regras; Validação de comportamentos

esperados; Novos indícios para pesquisa:

ACLatenciaMuitoBaixa~ACLatenciaBaixaAETesteVacaNao,AETestTatuNão sup=0.38 conf=0.85714287 (Possuindo item 'ACLatenciaBaixa' com maior relevância!!!)

31/42

ContextualizaçãoPropostaEstudo de CasoDiscussão - Trabalhos CorrelatosConclusão

Agenda

32/42

Discussão - Trabalhos Correlatos :Conhecimento do Domínio

Extraído do Livro Sistemas Inteligentes. Capítulo sobre Mineração de Dados. Rezende, S. O. 1 ed. 2003

[kuo, Y.-T., A. Lonie, and L. Sonenberg, 2007]

33/42

Discussão - Trabalhos Correlatos :Pré-processamento

Extraído do Livro Sistemas Inteligentes. Capítulo sobre Mineração de Dados. Rezende, S. O. 1 ed. 2003

[Sidhu, A.S., T.S. Dillon, and E. Chang, 2007]

[Zhou, X. and J. Geller, 2007]

[Bogorny, V., P.M. Engel, and L.O. Alvares, 2007]

34/42

Discussão - Trabalhos Correlatos :Extração de Padrões

Extraído do Livro Sistemas Inteligentes. Capítulo sobre Mineração de Dados. Rezende, S. O. 1 ed. 2003

[Khelif, K., R. Dieng-Kuntz, and P. Barbry, 2007]

[Pahm, M.H., et al, 2007]

[Miani et al, 2009]

35/42

Discussão - Trabalhos Correlatos :Pós-processamento

Extraído do Livro Sistemas Inteligentes. Capítulo sobre Mineração de Dados. Rezende, S. O. 1 ed. 2003

[STAMOU et al. 2007]

36/42

Discussão - Trabalhos Correlatos :Utilização do conhecimento

Extraído do Livro Sistemas Inteligentes. Capítulo sobre Mineração de Dados. Rezende, S. O. 1 ed. 2003

[Trousse, B., et al, 2007]

[Mothe, J. and N. Hernandez, 2007]

[Kotsifakos, E., G. Marketos, and Y. Theodoridis, 2007]

37/42

Discussão

Utilização do conhecimento em todas as etapas do processo; Identificação do problema: entendimento dos

dados, de seus significados e potenciais; Pré-processamento: explicitação do significado dos

dados por meio da geração de anotações semânticas;

Extração de padrões: redução da complexidade da tarefa,

Pós-processamento: filtro de regras já conhecidas; Utilização do conhecimento: conhecimento obtido

pode ser utilizado para atualizar a ontologia

38/42

Discussão:

ACTreinoTatuSIM

88 TuplasACLatenciaMuitoBaixa~ACLatenciaBaixaAETesteVacaNao,AETestTatuNão

sup=0.38 conf=0.85714287 (Possuindo item 'ACLatenciaBaixa' com maior relevância!!!)

39/42

Contribuições

Ontologia de Domínio para a Equivalência de Estímulos;

Uma abordagem para a geração de anotações semânticas para dados brutos;

Um protótipo de ferramenta para a geração de anotações;

Uma proposta para a realização de filtros de regras de associação;

Algoritmo Filtered-NARFO que aplica a abordagem de filtro de regras;

Um estudo de caso real que foi viabilizado pelas propostas e ferramentas apresentadas.

40/42

Trabalhos Futuros

Melhorar ferramenta SATO. Aplicação da abordagem proposta com

dados de outros domínios. Combinar conhecimento do domínio

com métricas de interesse para avaliar regras.

Identificar exceções por meio do conhecimento do domínio.

Algoritmo baseado no Filtered-NARFO para extrair padrões sequenciais.

41/42

Publicações

Pôster “Geração Automática de Anotações Semânticas para o Domínio de Controle de Estímulos” no Second Brazilian Workshop on Semantic Web and Education, workshop satélite ao Simpósio Brasileiro de Informática na Educação de 2008;

Resumo “Stimuli: uma ontologia para o paradigma de Equivalência de Estímulos” no I Portuguese and Multi-lingual Ontologies Workshop, workshop satélite ao 7th Brazilian Symposium in Information and Human Language Technology

Demo “SATO: uma ferramenta para a geração de anotações semânticas” na sessão de Demos do Simpósio Brasileiro de Banco de Dados (SBBD 2009)

42/42

Obrigado!