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