RECOMENDAÇÃO DE CONHECIMENTO
CIENTÍFICO BASEADO NOS
INTERESSES DO USUÁRIO ATRAVÉS DE
CLUSTERING
Flávio Henrique Moura Stakoviak
Orientador: Edeílson Milhomem
Roteiro
• Sistemas de Recomendação
• Recuperação da Informação
• Clustering de Documentos
• Considerações Finais
Roteiro
• Sistemas de Recomendação
• Recuperação da Informação
• Clustering de Documentos
• Considerações Finais
Sistemas de Recomendação
• Sistemas de Recomendação
• Sistemas de recomendação (SR) são responsáveis
por identificar um usuário e lhe apresentar
conteúdo, produtos ou ofertas personalizadas
(REATEGUI, BOFF & VICCARI, 2005)
Sistemas de Recomendação (cont.)
Sistema de
Recomendação
Sistemas de Recomendação (cont.)
• Filtragem Baseada em Conteúdo
– Perfil do Usuário
– Base de Itens
• Filtragem Colaborativa
– Perfil de Todos os Usuários
– Base de Itens
Roteiro
• Sistemas de Recomendação
• Recuperação da Informação
• Clustering de Documentos
• Considerações Finais
Recuperação da Informação
• Recuperação da Informação
• A RI tem como objetivo auxiliar os usuários na
busca por informações que os interessam em uma
coleção de documentos. Tal auxílio se dá a partir
da representação, armazenamento, organização e
acesso a essas informações (RODRIGUES, 2009).
Recuperação da Informação (cont.)
• Modelos
– Modelo Vetorial
– Modelo Booleano
– Modelo Probabilístico
Recuperação da Informação (cont.)
• Etapas
– Aquisição
– Preparação
– Indexação
– Busca
– Ordenação
Recuperação da Informação (cont.)
• Aquisição de Documentos
– Web Crawler
Agendador
Web Crawler
URL
Base de
Textos
Recuperação da Informação (cont.)
• Preparação de Documentos
– Case Folding
– Stop Words
– Stemming
Recuperação da Informação (cont.)
• Indexação de Documentos
– Tipos
– Campos
– Thesaurus
Recuperação da Informação (cont.)
• Armazenamento de Documentos
– Método duplo de acesso às informações
armazenadas
– Manipulação de grandes volumes atualizações
– Controle de páginas obsoletas
Recuperação da Informação (cont.)
• Recuperação de Documentos
– Palavras-chave
– Casamento de Padrão
– Estrutura
Roteiro
• Sistemas de Recomendação
• Recuperação da Informação
• Clustering de Documentos
• Considerações Finais
Clustering de Documentos
• Clustering
• é um método de descoberta de conhecimento
que identifica agregações ou relações entre
objetos,
sendo
um
método
útil
para
o
agrupamento de documentos similares (WIVES,
1999)
Clustering de Documentos (cont.)
• Similaridade Padrão
– Métricas de Distância Convêncionais
• Similaridade Conceitual
– Hierarquia de assuntos
– Pesos
Clustering de Documentos (cont.)
• Edit Distance: Grau de similaridade entre
« Peter » e « Piotr »
Peter
Substituição 1pt
Pieter
Inserção 1pt
Pioter
Exclusão 1pt
Piotr
D(Peter, Piotr) = 3
Clustering de Documentos (cont.)
Cluster 1
Cluster 2
Ferramenta de
Clustering
Cluster 3
Cluster 4
Cluster 5
Clustering de Documentos (cont.)
• Etapas de Clustering
– Representação de Padrões
– Mediação da Proximidade
– Indentificação do Clustering
– Abstração dos Dados
– Validação dos Clusters
Clustering de Documentos (cont.)
• Representação de Padrões
– Objeto
– Documentos Textuais
– Expansão dos Termos
– Melhor Performance ou Maior Eficiência
Clustering de Documentos (cont.)
• Mediação de Proximidade
– Qualitativos
– Quantitativos
Clustering de Documentos (cont.)
• Identificação de Clusters
– Clustering Hierárquico
– Algoritmo Particional
– Density-based
– Model Based
Roteiro (Clustering)
• Clustering Hierárquico
• Algoritmos Particionais
• K-Means
• K-Means Biseccionado
• Density-Based
• Model-Based
Roteiro (Clustering)
• Clustering Hierárquico
• Algoritmos Particionais
• K-Means
• K-Means Biseccionado
• Density-Based
• Model-Based
Clustering de Documentos
Hieráquico
• Hierarquia de partições simples
• Cada cluster é uma combinação de dois outro
clusters
• Dendograma
Clustering de Documentos
Hierárquico (cont.)
• Ascendente (bottom-up)
– Começa com todos os clusters e combina pares
até a raiz;
Clustering de Documentos
Hierárquico (cont.)
• Descendente (top-down)
– Começa com um único cluster e divide-se em dois
até alcançar o nível da árvore
Roteiro (Clustering)
• Clustering Hierárquico
• Algoritmos Particionais
• K-Means
• K-Means Biseccionado
• Density-Based
• Model-Based
Roteiro (Clustering)
• Clustering Hierárquico
• Algoritmos Particionais
• K-Means
• K-Means Biseccionado
• Density-Based
• Model-Based
Clustering de Documentos
k-means
• Cria um número fixo de K clusters
• Vetores-documento
• Centróides
Clustering de Documentos
k-means (cont.)
5
4
k1
3
k2
2
1
k3
0
0
1
2
3
4
5
Clustering de Documentos
k-means (cont.)
5
4
k1
3
k2
2
1
k3
0
0
1
2
3
4
5
Clustering de Documentos
k-means (cont.)
5
4
k1
3
2
k3
k2
1
0
0
1
2
3
4
5
Clustering de Documentos
k-means (cont.)
5
4
k1
3
2
k3
k2
1
0
0
1
2
3
4
5
Roteiro (Clustering)
• Clustering Hierárquico
• Algoritmos Particionais
• K-Means
• K-Means Biseccionado
• Density-Based
• Model-Based
Clustering de Documentos
k-means biseccionado
Selecionar um cluster
Encontrar dois subgrupos
Processo do k-means
Não
Cluster produz
maior
similaridade?
Sim
No de clusters
desejado
atingido?
Não
Sim
Roteiro (Clustering)
• Clustering Hierárquico
• Algoritmos Particionais
• K-Means
• K-Means Biseccionado
• Density-Based
• Model-Based
Clustering de Documentos
Density-Based
• Características
• Encontrar clusters de forma arbitrária
• Lidar com ruídos
• Tempo de execução baseado nos parâmetros de
entrada
Roteiro (Clustering)
• Clustering Hierárquico
• Algoritmos Particionais
• K-Means
• K-Means Biseccionado
• Density-Based
• Model-Based
Clustering de Documentos
Model-Based
• Características
• Versão « probabilística » do k-means
• Pertence a um cluster conforme algum peso
• Capaz de lidar com incertezas associadas
Clustering de Documentos (cont.)
• Abstração dos Dados
– Visa a interoperabilidade
– Centróides
– Protótipos
Clustering de Documentos (cont.)
• Validação dos Clusters
– Comparação do resultado ideal com o resultado
alcançado
Roteiro
• Sistemas de Recomendação
• Recuperação da Informação
• Clustering de Documentos
• Considerações Finais
Considerações Finais
• Reduzir Sobrecarga de Informações com
Sistemas de Recomendação
• Recuperação eficiente de documentos com a
Recuperação de Dados
Considerações Finais
• Informações de importância dos textos
obtidas com a análise de dados
• Clustering mais utilizados
• Hierárquico
• K-means
Considerações Finais
• Clustering Hierárquico
• Prós: Melhor Qualidade
• Contra: Complexidade Quadrática
• K-means
• Prós: Complexidade Linear
• Contra: Pior qualidade
Considerações Finais
• K-means biseccionado
• Variante do k-means
• Mesmo tempo de execução
• Qualidade equivalente ao Hierárquico
• Trabalhos Futuros
RECOMENDAÇÃO DE CONHECIMENTO
CIENTÍFICO BASEADO NOS
INTERESSES DO USUÁRIO ATRAVÉS DE
CLUSTERING
Flávio Henrique Moura Stakoviak
Orientador: Edeílson Milhomem
Download

Clustering de Documentos