Embed Size (px)
Citation preview
1
Mineração de Textos
Os estudos em Aprendizado de Máquina normalmente trabalham com dados estruturados
Entretanto, uma grande quantidade de informação é armazenada em textos, que são dados semiestruturados
Nesta apresentação é dava uma breve introdução à Mineração de Textos
2
Introdução
Uma grande quantidade de toda informação disponível atualmente encontra-se sob a forma de textos (ou documentos) semi-estruturados, tais como livros, artigos, manuais, e-mails e a Web
O termo semi-estruturado indica que os dados não são completamente estruturados nem completamente sem estrutura Um documento pode conter alguns atributos
estruturados: Título, autor(es), data da publicação
mas também contém alguns elementos textuais sem estrutura Resumo e conteúdo
3
Introdução
Mineração de Textos (Text Mining - TM) tem como objetivo tratar essa informação semi-estruturada
Apesar desta fonte de recursos ser atrativa e de fácil acesso, a extração automática de informação útil a partir dela é um desafio uma vez que os resumos estão em linguagem natural
4
Mineração de textos
O objetivo da Mineração de Textos é o processamento de informação textual, extraindo índices numéricos significativos a partir do texto e então tornar esta informação acessível para os programas disponíveis nos sistemas de mineração de dados.
5
Mineração de textos
Podem ser analisadas palavras, agrupamentos de palavras, ou mesmo documentos entre si através das suas similaridades ou de suas relações com outras variáveis de interesse num projeto de mineração de textos.
6
Mineração de textos
O objetivo na fase inicial do projeto é “transformar textos em números (índices significativos)” , que podem então ser incorporados em outras análises tais como classificação supervisionada ou não supervisionada.
7
Mineração de textos
Algumas aplicações típicas para mineração de textos: Análise de questões abertas
em questionários. Processamento automático
de mensagens, “e-mails”, etc...
Busca de referências em uma coleção de artigos, motores de busca.
8
Mineração de textos
Mais apropriado para um grande número de textos de tamanho médio ou pequeno.
Não deve ser tratado como uma caixa preta. A intervenção do analista é necessária.
Soluções não podem ser importadas de outra língua.
9
Mineração de textos
Pré-processamento: 1) Exclusão de palavras e números, baseada no
tamanho, nas letras inicial e final ou outros critérios.
2) Manutenção ou exclusão de palavras baseada em uma lista previamente definida.
3) Identificação de sinônimos e antônimos. 4) Determinação de radicais
10
10
Recuperação de Informação
Recuperação da informação significa a operação pela qual se seleciona documentos, sobre tópicos específicos, a partir do acervo, em função da demanda do usuário.
O processo de recuperação de informação consiste em identificar, no conjunto de documentos(corpus) de um sistema, quais atendem à necessidade de informação do usuário.
11
11
Sistemas de Recuperação de Informação
Os Sistemas de Recuperação de Informação (SRI’s) surgiram da necessidade de se extrair informações em bases de dados não estruturadas, tais como grandes coleções de documentos textuais e bibliográficos.
Os SRI’s necessitam de técnicas que agilizam o armazenamento e acesso aos dados.
12
12
Sistemas de Recuperação de Informação
A recuperação de informação é feita a partir de uma entrada do usuário, ou seja, uma consulta para que os documentos relevantes sejam encontrados.
Os SRI’s geralmente se baseiam em Busca por Palavra-Chave ou Busca por Similaridade.
13
13
Recuperação de Informação x Mineração de Texto
A informatização de diversas áreas trouxe como conseqüência um grande volume de informações sendo armazenadas em bancos de dados.
Algumas áreas surgiram para o tratamento de informações textuais, como a Recuperação de Informação e a Mineração de Textos.
Ambas utilizam técnicas avançadas para explorar uma grande coleção de dados textuais desestruturados, mas tem propósitos diferentes.
14
14
Recuperação de Informação x Mineração de Texto
Recuperação de Informação é uma tecnologia utilizada para buscar documentos, focalizando nos dados relacionados a algum tópico específico.
A Mineração de Textos, também conhecida como Descoberta de Conhecimento em Textos (KDT), visa encontrar padrões e tendências em um conjunto de documentos, realizar classificação de documentos, ou ainda comparar documentos.
15
15
Recuperação de Informação x Mineração de Texto
Em uma das etapas da Mineração de Textos, utiliza-se técnicas de R.I.
Coleção de
textos
Forma Intermediária
Mineração Conhecimento
Técnicas de RI
Técnicas de EI
Processo de Mineração de Textos (Correa, 2003)
16
Métricas Básicas
As duas métricas usualmente utilizadas para avaliar o desempenho são Precisão: porcentagem de documentos recuperados
que de fato são relevantes Recall (sensitividade): porcentagem de documentos
que são relevantes e foram, de fato, recuperados
Todos os documentos
Documentos relevantes
Documentos recuperados
Relevantes e Recuperados
17
Métricas Básicas
As duas métricas usualmente utilizadas para avaliar o desempenho são Precisão = |Relevantes ∩ Recuperados| / |
Recuperados| Recall: |Relevantes ∩ Recuperados| / |Relevantes|
Todos os documentos
Documentos relevantes
Documentos recuperados
Relevantes e Recuperados
18
Recuperação baseada em Similaridade de Palavras-Chave Em um sistema de TM baseado em
palavras-chave, um documento é representado por uma string, formada por uma conjunto de palavras-chave
O usuário fornece uma palavra-chave ou uma expressão formada por palavras-chave Chá or café Carro and oficina mecânica
19
Sinonímia & Polissemia
Um sistema de TM deve considerar a ocorrência de sinonímia e polissemia
Sinonímia: uma palavra possui vários sinônimos Carro, automóvel, veículo
Polissemia: uma mesma palavra tem diferentes significados, dependendo do contexto Mineração (textos?), mineração (carvão?) Exame (teste?), exame (médico?)
20
Recuperação baseada em Similaridade de Palavras-Chave Um sistema de TM baseado em
similaridade encontra documentos similares baseado em um conjunto de palavras-chave
A saída é um grau de relevância, onde a relevância é medida de proximidade das palavras-chave, a freqüência das palavras-chave e assim por diante
21
Stop List
Um sistema de TM geralmente associa uma stop list com um conjunto de documentos
Uma stop list é um conjunto de palavras que são consideradas “irrelevantes” Normalmente inclui artigos, preposições,
conjunções A stop list pode variar entre conjuntos de
documentos (mesma área, mesma língua)
22
Stem
Um grupo de diferentes palavras podem compartilhar um mesmo radical (stem)
Um sistema de TM precisa identificar grupos de palavras nas quais as palavras em um mesmo grupo são pequenas variações sintáticas umas das outras Droga, drogas, drogado, drogaria
Com essa identificação, é possível armazenar apenas o stem
23
Representação
Iniciando com um conjunto de n documentos e t termos, é possível modelar cada documento como um vetor v no espaço t-dimensional ℜt
Os vetores podem ser binários, onde 0 indica que um determinado termo não ocorre no documento e 1 caso contrário
Os vetores podem conter a freqüência (absoluta ou relativa) de cada termo no documento
24
Representação binária do documento como uma matriz
Cada documento é representado um vetor binário
25
Matriz de contagem de termos
Considere a representação que conta o número de ocorrências de um termo
Cada documento é representado por um vetor com o número de ocorrência de cada termo
26
Bag of words
O vetor não considera a ordem das palavras no documeto
John is quicker than Mary and Mary is quicker than John tem os mesmos vetores
Essa abordagem é chamada bag of words Estamos perdendo informação quando
fazemos isso
27
Frequência de termos tf
Número de vezes que o termo t ocorre na coleção de documentos d.
Frequência absoluta não é uma boa: Um documento com 10 ocorrências de um
termo é mais relevante quem somente uma ocorrência do termo.
Mas não 10 vezes mais relevante! Relevância não deve crescer
proporcionalmente com frequência
28
Pesagem com Log-frequencia
Pesa a frequencia usando o log
O score é 0 se nenhum dos termos está presente no documentos
0 → 0, 1 → 1, 2 → 1.3, 10 → 2, 1000 → 4, etc.
29
Frequencia na coleção
Termos raros são mais informativos que termos muito frequentes Relembre as stop words
Considere um termo que é muito raro na coleção (e.g., aracnofobia)
Um documento contendo esse termo tem grandes chances de ser relevante para aracnofobia
→ Queremos um alto peso para termos muito raros em toda a coleção, como aracnofobia.
30
Frequencia na coleção
Considere um termo que é frequente na coleção Um documento contendo esse termo tem boa chance
de ser relevante que não o tem, mas não um forte indicador de relevância
→ Para termos muito frequentes, queremos pesos positivos para esses termos, mas menores do que para termos raros
Usa-se a frequência na coleção (df) para capturar isso em no peso.
df (≤ N) é o número de documentos que contém aquele termo
31
Pesagem idf
Dft é a frequência do term t na coleção: o número de documentos que contém t df is a measure of the informativeness of t
Define-se idf (inverse document frequency) como
Usamos o logarítmo N/dft ao invés de N/dft
para “suavizar” o efeito do idf. A base do logaritmo não importa.
32
Exemplo do idf example, suponha N= 1 milhão
termo dft idft
calpurnia 1 6
animal 100 4
sunday 1,000 3
fly 10,000 2
under 100,000 1
the 1,000,000 0
Existe um valor de idf para cada termo na coleção.
33
Frequência na Coleção vs. Documento A frequencia na coleção é o número de ocorrências
de t na coleção, contando-se ocorrências múltiplases.
Example:
Qual palavra poderia ser mais relevante (e
receber mais peso)?
Palavra Collection frequency Document frequency
insurance 10440 3997
try 10422 8760
34
Pesagem tf-idf
O peso tf-idf de um termo é o produto de seu tf e de seu idf .
Muito usado em recuperação de informação! Também chamado de: tf.idf, tf x idf Aumenta com o número de de ocorrências dento
de um documento Aumenta com a raridade do term na coleção
35
Binario → countagem → weight matrix
Cada vetor é representado por um número real com o tf-idf de cada termo
36
Documentos como vetores
Agora temos um vetor |V|-dimensional Termos são eixo no espaço Documents são pontos dos vetores neste
espaço Alta dimenção: centenas/milhares de
dimensões quando você aplica a uma grande coleção de texto
Esparso – mairia das entradas é zero.
37
Identificando Documentos Similares
Uma vez obtida a matriz de freqüência (binária, absoluta ou relativa) é possível aplicar qualquer métrica de distância, uma vez que é esperado que documentos similares tenham freqüências similares
É possível medir a similaridade entre um conjunto de documentos ou entre um documento e uma query (consulta), freqüentemente definida como um conjunto de palavras-chave
38
Identificando Documentos Similares
Uma métrica representativa é o co-seno entre os vetores
Sejam v1 e v2 dois vetores de documentos; a métrica de similaridade de co-seno é definida como
onde
39
39
Similaridade
Associa pesos aos termos de indexação e aos termos da expressão de busca.
O resultado da utilização destes pesos é a ordenação dos documentos pelo grau de similaridade em relação à expressão de busca.
Cada elemento do vetor é normalizado para assumir valores entre 0 e 1.
Para o cálculo do peso é considerado o n° de vezes que o termo aparece no documento e o n° de vezes que o termo aparece no corpus de documentos.
40
40
Similaridade
A representação gráfica de dois documentos: DOC1, com termos de indexação t1 e t3, com pesos 0.3 e 0.5, e DOC2 com termos de indexação t1, t2 e t3, com pesos 0.5, 0.4 e 0.3, dá-se:
41
41
Modelo Vetorial
Se utilizarmos uma expressão de busca eBUSCA=(0.2,0.35,0.1), juntamente com os documentos DOC1 e DOC2, em um espaço vetorial formado pelos termos t1, t2 e t3, teremos a representação gráfica a seguir:
42
42
Modelo Vetorial
Para encontrar o grau de similaridade, calcula-se o co-seno do ângulo entre documentos ou entre consultas e documentos:
Onde wi,x é o peso do i-ésimo elemento do vetor x e wi,y é o peso do i-ésimo elemento do vetor y.
43
43
Modelo Vetorial
Assim, o grau de similaridade entre o documento DOC1 e o documento DOC2 é calculado:
44
44
Modelo Vetorial
Portanto, o grau de similaridade entre estes dois documentos é de 73%. Utilizando-se a mesma fórmula é possível encontrar o grau de similaridade entre a expressão eBUSCA com cada um dos documentos DOC1 e DOC2:
45
45
Modelo Vetorial
A expressão eBUSCA possui um grau de similaridade de 45% com o documento DOC1 e de 92% com o documento DOC2.
É possível restringir a quantidade de documentos recuperados definindo um limite mínimo para o valor de similaridade.
Um limite de 0.5, indica que uma expressão de busca obterá como resultado apenas os documentos cujo valor de similaridade for superior a 50%.
46
t1 t2 t3 t4 t5
d1 321 354 15 22 74 d2 84 91 32 143 87 d3 31 71 167 72 85 d4 68 56 46 203 92 d5 72 82 289 31 25 d6 15 6 225 15 54 d7 430 392 17 54 121
Identificando Documentos Similares
cos(d1,d1) = 1.0000 cos(d1,d2) = 0.6787 cos(d1,d3)=0.4363
