Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

AMRHC

No description
by

Angélica Ribeiro

on 27 November 2017

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of AMRHC

Roteiro
Requisitos Funcionais
Requisitos Não Funcionais
Modelo de Caso de Uso
Diagrama Conceitual
Diagrama de Atividades

Objetivo

Criar um algoritmo de similaridade para verificar similaridade entre tipos 
diferentes de documentos em Redes de Informação Heterogênea usando
artefatos linguísticos

Quais vértices são mais similares entre si?

Roteiro
Fundamentos Teóricos
Recuperação de Informação
Processamento de Língua Natural
Redes Complexas
Artefatos linguísticos como ontologias
Informações disponíveis nos documentos (metadados)
Fundamentação Teórica
Propriedade do Documento
Fundamentação Teórica
Processamento de Língua Natural (PLN)
Conhecimento linguístico
Fonética fonologia
Morfologia
Sintáxe
Semântica
...
Representações computacionais
Máquinas de estado
Sistemas de regras formais
Lógica
Teoria da probabilidade
Aprendizado de máquinas
Fundamentação Teórica
Processamento de Língua Natural (PLN)
Extração de informação
Texto livre ou estruturado
Fala -> Escrita
Correção de ortografia
Verificação de gramática ( frases verbais, nominais... )
Extração de Part-of-Speech ( subs., verb., adj.)
Eliminação de ambiguidades
Ontologias de entidades
Tesauro de sinônimos e abreviaturas
Fundamentação Teórica
Redes Complexas
Redes Regulares
Rede Randômicas
Redes de Mundo Pequeno
Redes de livre escala
Clustered Randon Networks
Redes com Mistura de Padrões
Fundamentação Teórica
Fundamentação Teórica
Redes de Informações Heterogêneas

Fundamentação Teórica
Redes Heterogêneas
Meta-paths de uma rede de co-autoria
Referências
[1] AMANCIO, D. R. et al. Comparing intermittency and network measurements of words
and their dependence on authorship. New Journal of Physics, IOP Publishing, v. 13,
n. 12, p. 123024, 2011.

[2] BAEZA-YATES, R.; RIBEIRO-NETO, B. Modern information retrieval. 1nd. ed. [S.l.]:
ACM Press New York, 1999. v. 463.

[3] SILVA, T. C. Machine learning in complex networks: modeling, analysis, and applications.
Tese (Doutorado) | Universidade de São Paulo, 2012.

[4] SHI, C. et al. Hetesim: A general framework for relevance measure in heterogeneous
networks. IEEE Transactions on Knowledge and Data Engineering, IEEE, v. 26, n. 10, p.
2479

[5] SHI, C. et al. Relevance search in heterogeneous networks. In: ACM. Proceedings of the
15th international conference on extending database technology. [S.l.], 2012. p. 180

Validação: Dataset
Prontuários médicos
MIMIC (https://mimic.physionet.org/gettingstarted/access/)
NCBI (http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4147615/)
NLP (https://www.i2b2.org/NLP/DataSets/Main.php)
MTsamples (http://www.mtsamples.com/)
Artigos Científicos
Pubmed
Google Scholar
Dataset de Referências em Redes Heterogêneas
DBLP, Pubmed, IMBD
Flickr
Google News
Dataset de Referências do grupo de pesquisa
Estrutura da Rede Atualmente
A base do Algoritmo
1. Entrada de documentos de mídias diferentes
2.Relaciona-se os documentos entre si
1.Por meio de algoritmos de similaridade clássicos vetoriais (cosseno, jaccard, distância euclidiana)
2.E ou estendidos por artefatos linguísticos(tesauros dicionários, ontologias)
3.Retorna uma Rede de Informação Heterogêneas G=(E, V, C,W)
4.Calcula-se as similaridades dos nós de G=(E, V, C, W) por meio de:
1.Métricas de redes complexas
2.Meta-path (por links)
3.Artefatos linguísticos(tesauros dicionários, ontologias)
4.Retorna o ranqueamento dos documentos similares
O trabalho
Trabalhos de Suporte
Framework para sistemas de Vigilância para doenças crônicas (SisVidas)
Framework para redução de descontinuidade semântica em imagens médicas (FREDS)
Question-Answering surveillance framework (QASF)

Fundamentação Teórica
Problemas no estado da arte
Não consideram a dinâmica das redes
Utilizam o meta path
Custo computacional grande
Não utilizaram ontologias nem tesauros
As redes heterogêneas estudadas:
Redes pré estabelecidas (Vértices possuem uma ligação explícita.)
Nós são extraídos de apenas 1 tipo de documento.
As redes heterogêneas criadas nesse trabalho
Documentos são os vértices
As arestas entre os vértices não estão explícitas
Cosseno
Palavras chaves + ontologias + código CID
Redes isomórficas
Fundamentação Teórica
Fundamentação Teórica
Algoritmos de Similaridade
Abordagens em Características
Vetores de características
Cosseno
Coeficiente de jaccard
Distância euclidiana
Abordagens em Links
PageRank
SimRank

sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
sdfasdfasdfasdfasdfasdfasdf
asdfasdfasdfasdfasdfasdfasdfasdfasdf
Título
Autor
Co-autor
Abstract
DOI
Palavras chaves

Sintomas
Diagnósticos
Hábitos pessoais
Exames médicos
Palavras chaves
Palavras Chaves
Descritores
Posts
Relacionamentos

Medidas de grau e correlação de grau
Distâncias e métricas de caminhos na rede
Métricas estruturais da rede
Nós com várias características de cada documento
Nós são diferentes de acordo com o tipo de documento.

Redes Heterogêneas
Esquemas de Rede
Restrições
A maioria das medidas de similaridade existentes são para redes de informação homogêneas.
Texto
Links
Multimídia
Modelos Clássicos de RI
(Textos não Estruturados)
Booleano
Vetorial
Probabilístico
Textos Semi Estruturados
Nós Próximos, Outros
Modelos em XML
Web
Page Rank
Hubs & Autoridades
Recuperação de Imagens
Recuperação de Áudio e Música
Recuperação de Vídeo
Teoria dos conjuntos
Fuzzy
Booleano Estendido
Conjuntos
Algébricos
Vetorial Generalizado
Latent Semantic Analysis
Redes Neurais
Probabilísticos
BM25
Modelos de Linguagens
Divergencia da Aleatoriedade
Redes Bayesianas
Algoritmos de Similaridade
Trabalhos de Suporte
Proposta
Resultados
Introdução
Redes Sociais
Artigo
PEPs
Imagens
Medidas de centralidade
Requisitos Funcionais
Engenharia de Software
Profa: Alessandra Alaniz Macedo

Universidade de São Paulo

Requisitos de Caso de Uso
Modelo Conceitual


O algoritmo deverá fazer o uso de técnicas computacionais de reconhecimento de padrões, processamento de linguagem natural, recuperação de informação e Sistemas Complexos.

O algoritmo deverá criar uma rede de informações heterogêneas entre documentos biomédicos a partir da sililaridade ou relacionamento semântico extraído por meio de ontologias juntamente com métricas e medidas de similaridade.

O algoritmo deverá conectar os documentos biomédicos sendo eles laudos médicos, exames médicos, prontuários, artigos científicos, entre si de acordo com o grau de relacionamento semântico entre os conceitos dos documentos e/ou domínios.

O algoritmo será capaz de identificar automaticamente os tipos de atributos de cada vertice da rede. Assim como os atributos de cada aresta.

O algoritmo será capaz de extrair da rede complexa a simililaridade entre os documentos similares por meio dos caminhos formados pela construcao da rede complexas por meio da avaliação da qualidade dos relacionamentos entre os artefatos, usando medidas como graus de saída dos vértices, coeficientes de aglomeração, correlação de grau, resistência e etc.
Diagrama de Atividades
Algoritmo de Similaridade em redes de Informação Heterogênea por meio de Redes Complexas
Programa de Pós-Graduação em Computação Aplicada​
Angélica Abadia Paulista Ribeiro
Alessandra Alaniz Macedo
Orientanda:
Orientadora:

Roteiro
Introdução
Fundamentos Teóricos
Algoritmos de Similaridade
Trabalhos de Suporte
Proposta
Resultados Parciais
Contexto Atual​
 Número de dados crescentes
Redes Sociais
Artigos Científicos
Propagação muito rápida de informações
Informações relacionadas
Representação em diferentes mídias
Propagação em diferentes meios
São Informações de diferentes tipos de mídias, porém complementares
Indrodução
The Dutch Indexed Web contains at least 218.81 million pages (Thursday, 27 July, 2017).
The size of the World Wide Web (The Internet)
The Indexed Web contains at least 4.6 billion pages (Thursday, 27 July, 2017).
http://www.internetlivestats.com/
Fonte:
http://www.worldwidewebsize.com/
Fonte:


Introdução
http://www.worldwidewebsize.com/
Fonte:
http://www.worldwidewebsize.com/
Fonte:
Fonte: https://www.nlm.nih.gov/bsd/medline_lang_distr.html
Leonard Euler 1736
RedesComplexas
Grande Escala
Padrão não Trivial
Dinâmicas
Nível
◦ Individual
Coletivo
Questionamentos em Eventos
◦ “O que acontece?”
“Como acontece?”
◦ “Aconteceu antes?”
Introdução
Todo sistema que existe hoje pode ser representado por redes complexas
Pesquisas atuais:
Redes sociais
Redes de co-autoria
Redes de autores de filmes
Redes de propagação de doenças
As Redes Homogêneas ignoram os diferentes tipos de informação
Único tipo de vértice e aresta
Redes de Informação de Heterogênea são redes complexas com mistura de padrões
Tipos diferentes de vértices
Tipos diferentes de arestas
Redes Heterogêneas possuem um alto valor semântico de conteúdo
Algoritmos de Redes Complexas -> Redes Homogêneas
Introdução

Congresso
Artigo
Autor
Fonte: SUN, Y.; HAN, J. Mining heterogeneous information networks: a structural analysis approach. ACM
SIGKDD Explorations Newsletter, ACM, v. 14, n. 2, p. 20. Modificada pela Autora.
Estudio de Filme
Ator
Filme
Diretor
A Rede de Filmes IMDB
DBLP Rede Bibliográfica

Rede do Facebook
Objetivo
Criar um algoritmo de similaridade para verificar similaridade entre tipos diferentes de documentos em Redes de Informação Heterogênea usando artefatos linguísticos
Quais vertices sao mais similares entre si?
https://random-blather.com/2014/04/28/information-isnt-power/
Recuperação de Informação
Processamento de Língua Natural
Redes Complexas
Artefatos linguísticos como ontologias
Informações disponíveis nos documentos (metadados)
Document Property
Text
Links
Multimídia
Classical IR Models
(Non-Structured Texts)
Boolean
Vetorial
Probabilistic
Semi Structure Texts
Nós Próximos, Outros
XML Templates
Web
Page Rank
Hubs & Authorities
Image Recovery
Audio & Music Recovery
Video Recovery
Set theory

Fuzzy
Extended Boolean
Sets
Algebraic
Generalized Vector
Latent Semantic Analysis
Neural networks
Probabilistic
BM25
Language Models
Divergencia da Aleatoriedade
Redes Bayesianas
Fundamentação Teórica
Recuperacao de Informação
Fonte: BAEZA-YATES, R.; RIBEIRO-NETO, B. Modern information retrieval. 1nd. ed. [S.l.]: ACM Press New York, 1999. v. 463. Adaptado pela autora
Fundamentação Teórica
Processamento de Língua Natural (PLN)
Conhecimento linguístico
Fonética fonologia
Morfologia
Sintáxe
◦ Semântica
◦ Representações computacionais
Máquinas de estado
Sistemas de regras formais
Lógica
Teoria da probabilidade
Aprendizado de máquinas
Fundamentação Teóricas
Processamento de Língua Natural (PLN)
Extração de informação
Texto livre ou estruturado
◦ Fala -> Escrita
Correção de ortografia
Verificação de gramática ( frases verbais, nominais... )
Extração de Part-of-Speech ( subs., verb., adj.)
Eliminação de ambiguidades
◦ Ontologias de entidades
Tesauro de sinônimos e abreviaturas
Fundamentação Teórica
Redes Complexas
Redes Regulares
Rede Randômicas
Redes de Mundo Pequeno
◦ Redes de livre escala
Clustered Randon Networks
Redes com Mistura de Padrões
Fundamentação Teórica
Redes Heterogêneas
Esquemas de Rede
◦ Restrições
Fonte: SUN, Y.; HAN, J. Mining heterogeneous information networks: a structural analysis
approach. ACM SIGKDD Explorations Newsletter, ACM, v. 14, n. 2, p. 20
Fundamentação Teórica
Redes de Informações Heterogêneas
Fundamentação Teórica
Fundamentação Teórica
Fundamentação Teórica
Fundamentação Teórica
Trabalhos de Suporte
Esquema da Rede
Instância da Rede
Fonte: SUN, Y.; HAN, J. Mining heterogeneous information networks: a structural analysis 
approach. ACM SIGKDD Explorations Newsletter, ACM, v. 14, n. 2, p. 20
Redes Heterogêneas
Meta-paths de uma rede de co-autoria
Fonte: SUN, Y.; HAN, J. Mining heterogeneous information networks: a structural analysis
approach. ACM SIGKDD Explorations Newsletter, ACM, v. 14, n. 2, p. 20
A maioria das medidas de similaridade existentes são para redes de informação homogêneas.
Algoritmos de Similaridade
Abordagens em Características
Vetores de características
Cosseno
Coeficiente de jaccard
Distância euclidiana
Abordagens em Links
PageRank
SimRank
Abordagens de links
Medidas para redes homogêneas
PageRank
Detecções de comunidades
Medidas para redes heterogêneas
Pathsim
Outras
HeteSim , LSH-HeteSim, AvgSim, PS-Join , BPLSH
Problemas no estado da arte
Não consideram a dinâmica das redes
Utilizam o meta path
Custo computacional grande
Não utilizaram ontologias nem tesauros
As redes heterogêneas estudadas:
Redes pré estabelecidas (Vértices possuem uma ligação explícita.)
Nós são extraídos de apenas 1 tipo de documento.
As redes heterogêneas criadas nesse trabalho
Documentos são os vértices
As arestas entre os vértices não estão explícitas
Neste trabalho as redes estão sendo ligadas por um algoritmo ingênuo cosseno
Framework para sistemas de Vigilância para doenças crônicas (SisVidas)
Framework para redução de descontinuidade semântica em imagens médicas (FREDS)
Question-Answering surveillance framework (QASF)
Proposta
Criar um algoritmo de similaridade em Redes de Informação Heterogênea.
Redes Complexas
◦ Correlação de grau
Coeficientes de aglomeração
◦ Graus de saída dos vértices
◦ Resistência
◦ Etc.
Proposta do Algoritmo
Entrada de documentos de mídias diferentes
Relaciona-se os documentos entre si
Por meio de algoritmos de similaridade clássicos vetoriais (cosseno, jaccard, distância euclidiana)
E ou estendidos por artefatos linguísticos(tesauros dicionários, ontologias)
Retorna uma Rede de Informação Heterogêneas G=(E, V, C,W)
Calcula-se as similaridades dos nós de G=(E, V, C, W) por meio de:
Métricas de redes complexas
Meta-path (por links)
Artefatos linguísticos(tesauros dicionários, ontologias)
Retorna o ranqueamento dos documentos similares
Estrutura da Rede Atualmente
Para cada atributo do mesmo tipo de nó.
◦ Calcula-se a similaridade do cosseno levando em consideração as ontologias e os dicionários
Cria-se um link então com o peso da similaridade do cosseno entre esses documentos
Repete-se isso para cada atributo desses documentos
E para ligar os tipos diferentes dos documentos ?
Atributos diferentes: Doenças, Sintomas, Hábitos Alimentares …
Atributos iguais: Título, Palavra chave.
Artefatos linguísticos
Estrutura da Rede Atualmente
Medidas de centralidade
Medidas de grau e correlação de grau
Distâncias e métricas de caminhos na rede
Distâncias e métricas de caminhos na rede
Métricas estruturais da rede
Nós com várias características de cada documento
Nós são diferentes de acordo com o tipo de documento.
Validação: Dataset
◦ Prontuários médicos
MIMIC (https://mimic.physionet.org/gettingstarted/access/)
NCBI (http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4147615/)
NLP (https://www.i2b2.org/NLP/DataSets/Main.php)
MTsamples (http://www.mtsamples.com/)
Artigos Científicos
Pubmed
Google Scholar
Dataset de Referências em Redes Heterogêneas
DBLP, Pubmed, IMBD
Flickr
Dataset de Referências do grupo de pesquisa
Contribuições
•Reduzir o gap semântico
•Extrair diferentes semânticas
•Análise das relações similares
•Descobertas sobre a topologia e comportamento da Rede
Referências
[1] AMANCIO, D. R. et al. Comparing intermittency and network measurements of words and their dependence on authorship. New Journal of Physics, IOP Publishing, v. 13, n. 12, p. 123024, 2011.
[2] BAEZA-YATES, R.; RIBEIRO-NETO, B. Modern information retrieval. 1nd. ed. [S.l.]: ACM Press New York, 1999. v. 463
[3] SILVA, T. C. Machine learning in complex networks: modeling, analysis, and applications. Tese (Doutorado) Universidade de São Paulo, 2012.
[4] SHI, C. et al. Hetesim: A general framework for relevance measure in heterogeneous networks.
IEEE Transactions on Knowledge and Data Engineering, IEEE, v. 26, n. 10, p. 2479
[5] SHI, C. et al. Relevance search in heterogeneous networks. In: ACM. Proceedings of the
15th international conference on extending database technology. [S.l.], 2012. p. 180
Resultados
Aqui entram as redes complexas:
Medidas de Centralidade
Betweenness
Web page centrality – PageRank
...
Algoritmos de Similaridade
◦ Meta-path
E algoritmos com Meta-path com métricas de Redes Complexas
Python 3
NLTK, Snowball, Biopython, Networkx, Igraph, Pymnet, Scikit, Numpy, Gephi

Artigo 1
Artigo 2
Artigo 3
KDD
KDmile
Full transcript