Link Mining
Dayvid Victor Rodrigues de Oliveira
Guilherme Ramalho Magalhães
Roteiro
• Definição
– Data Mining
– Link Mining
• Atividades envolvendo Link Mining
• Desafios de Link Mining
Dados
• Quantidade de Dados
– Evolução dos recursos computacionais
– Quantidade de informação dobra a cada 20 meses
Data Mining
• Consiste em técnicas para transformar grande
quantidade de dados em informações
consistentes, para detectar relacionamentos
sistemáticos.
Data Mining
•
•
•
•
Estatística
Recuperação da informação
Inteligência artificial
Reconhecimento de padrões
Data Mining
• Exemplo
Link Mining
• Refere-se a técnicas de mineração que
explicitamente considera os tipos de links quando
constrói modelos preditivos ou descritivos dos dados
relacionados.
Link Mining
• Conjunto de Dados do Mundo Real:
– Multi-relacionais, heterogêneos e semi-estruturado
• Link Mining
– Nova área de pesquisa emergente resultante da interseçào
de pesquisa em redes social e análise de links, hipertexto
e mineração na web, aprendizado relacional e
programação lógica indutiva e mineração de grafos.
Dados relacionados
• Dados heterogêneos, multi-relacional
representados como um grafo ou rede
– Nós são objetos
• Podemos ter diferentes tipos de objetos
• Objetos tem atributos
• Objetos podem ter rótulos ou classes
– Arestas são links
• Podemos ter diferentes tipos de links
• Links podem ter atributos
• Links podem ser direcionados e não necessariamente
precisam ser binários
Domínios de Exemplo
• Dados Web
• Dados Bibliográficos
• Dados epidemiológicos
Exemplo: Dados Bibliográficos Ligados
P1
P3
P2
I1
Objects:
Papers
A1
Authors
P4
Institutions
Attributos:
Categorias
Links:
Citação
Co-Citação
Autor de
Afiliação de autor
Atividades Link Mining
Relacionadas a Objetos
Relacionadas a Links
Relacionadas a Grafos
Ranking de objetos
baseado em links
Predição de links
Descoberta de
subgrafos
Classificação de objetos
Estimar Cardinalidade
baseado em links
Classificação de grafos
Detectão de grupos
Modelos geradores de
grafos
Resolução de entidades
(Identificação de
Objetos)
Ranking de Objetos baseado em Links
• Ordenar um Conjunto de Objetos a partir de
um grafo
• Principais algoritmos:
– Page Rank
– HITS
Ranking – Page Rank
Ranking - HITS
• Hubs e Authorities
– Hubs: Linka várias Authorities
– Authorities: São linkadas por vários Hubs
Classificação de Objetos baseada em
links
• Predizer a categoria de um objeto baseado em
seu atributos, seus links e também os
atributos dos objetos ligados.
• WEB: Predizer a categoria de uma página web,
baseada em palavras que ocorrem na página,
links entre páginas, texto principal, tags html,
etc.
Classificação de Objetos baseada em
links
• Cite: Predizer o tópico de um paper baseado
na ocorrência de palavras, citações e cocitações
• EPI: Predizer tipo de doenças baseadas em
características das pessoas; Predizer a idade
de um indivíduo baseado nas idades das
pessoas que entraram em contato com ele e o
tipo da doença.
Detecção de Grupos
• Agrupar os nós do grafo em grupos cujos
integrantes possua características em comum;
• Exemplo:
– Determinar nichos de mercado
• Técnicas:
– Blockmodeling
– Spectral graph partitioning
Produtos
Idosos
Mulheres 1417 anos
1
2
3
4
Clientes
5
Homens 18-26
anos
6
Identificação de Objeto
• Predizer quando dois objetos são o mesmo,
baseado em seus atributos a seus links (record
linkage, eliminição de duplicações)
• WEB: predizer quando dois sites são mirrors de
um outro.
• Cite: Predizer quando duas citações são
referenciadas para o mesmo paper.
• EPI: Predizer quando duas vertentes de doenças
são as mesmas.
Predizer Tipo de Link
• Predizer o tipo ou propósito do Link
• Web: Predizer links patrocinados e links de
navegação; Predizer um relacionamento
advisor-advisse
• cite: Predição se um co-autor é também um
orientador
• Epi: Predizer se o contato é familiar,
profissional ou conhecido
Predizer existência de Links
• Predizer se um Link existe entre dois objetos
• WEB: predizer se haverá um link entre duas
páginas
• Cite: predizer se um paper citará outro paper
• EPI:Predizer quem são os contatos de um
paciente
Predição de links
• Predizer a existência de um link entre duas
entidades baseado nos atributos dos objetos
e outros links observados;
• Problema de classificação binário: para
qualquer dois objetos potencialmente
linkados oi e oj, predizer quando lij é 1 ou 0.
• Abordagens:
– Propriedades estruturais da rede;
– Informações dos atributos.
25
Predição de links
• Exemplo:
– Friend Finder do
Facebook
– Prever relações de
amizade entre
membros de uma
rede social
– Relações existentes
mas não observadas
26
Predição de links
• Exemplo:
– Recomendações do
Amazon
– Prever compra de novos
produtos com base no
histórico de compras
– Relações ainda não
existentes (nesse
caso, de compra de
produtos)
27
Estimar cardinalidade de links I
• Predizer o número de links de um objeto
• WEB: predizer a authoratativeness de uma página
baseada no número de links internos;
Identificando hubs baseado no número de links
externos
• Cite: predizer o impacto de um paper baseado no
número de citações
• EPI: predizer a infecciosidade de uma doença
baseada no número de pessoas diagnosticadas
Estimar cardinalidade de links II
• Predizer o número de objetos alcançados ao longo de
um caminho a partir de um objeto
• Importante para estimar o número de objetos que será
retornado por uma consulta
• WEB: Predizer o número de páginas retornadas por
crawling um site
• Cite: predizer o número de citações de um autor
particular em um journla específico
• EPI: Predizer o número de contatos mais velhos para
um paciente particular
Descoberta de subgrafos
• Encontrar subgrafos comuns ou interessantes em
um conjunto de grafos;
• Uso
– Classificação de grupos;
– Identificação de padrões;
– Identificação de regras associadas.
• Fases:
– Geração de candidatos;
– Matching.
• Teste de isomorfismo dos subgrafos
30
Descoberta de subgrafos
• Exemplo:
– Identificação de padrões de relacionamento
31
Classificação de grafos
• Categorizar um grafo inteiro como uma
instância positiva ou negativa de um conceito;
• Um dos primeiros problemas de data mining a
empregar técnicas de AM;
• Não há necessidade de inferência coletiva ->
independentemente gerado;
• Programação lógica indutiva: mineração de
características do grafos utilizando descoberta
de subgrafos
32
Modelos geradores de grafos
• Dado um conjunto de grafos, como podemos
gerar novos grafos que são partes da
distribuição do conjunto original?
• Exemplo:
– Expressões faciais
33
Modelos geradores de grafos
• 2 passos:
1. Contrução de um modelo estatístico do conjunto
de grafos que capture as presentes variações
estruturais subjacentes;
2. A partir desse modelo, gerar novos exemplos
que são partes da distribuição do conjunto
original.
34
Desafios
• Grafos em constante mudança
Desafios
• Combinar técnicas
Clientes
Produtos
1
2
3
4
5
6
36
Desafios
• Combinar técnicas
Clientes
Produtos
1
2
3
4
Detectar
grupos
5
6
37
Desafios
• Combinar técnicas
Clientes
Idosos
Produtos
1
Mulheres 1417 anos
2
3
4
5
Homens 18-26
anos
6
38
Desafios
• Combinar técnicas
Clientes
Idosos
Produtos
1
Mulheres 1417 anos
2
3
4
Previsão de
links
5
Homens 18-26
anos
6
39
Desafios
• Análise de dados gigantescos
40
Conclusão
• Muitos domínios são melhores descritos hoje
como uma coleção de dados linkados de
objetos heterogênos relacionados;
• Link mining é uma nova e excitante área de
pesquisa em data mining que explora os links
entre as instâncias dos dados;
41
Conclusão
Relacionadas a
Objetos
Ranking de objetos
baseado em links
Relacionadas a Links
Relacionadas a Grafos
Predição de links
Descoberta de
subgrafos
Classificação de objetos
baseado em links
Classificação de grafos
Detectão de grupos
Modelos geradores de
grafos
Referências
• Link mining: a survey. Getoor L., Diehl C.
SIGKDD Explor. Newsl., Vol. 7, No. 2.
(December 2005), pp. 3-12
• M. Kuramochi and G. Karypis. Frequent
subgraph discovery.In ICDM, pages 313–320,
2001.
• http://blog.hubspot.com/blog/tabid/6307/bid
/6050/The-Ultimate-List-100-TwitterStatistics.aspx
43
Dúvidas