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
1
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
2
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
3
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.
4
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.
5
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.
6
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.
7
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.
8
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
9
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.
10
10
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.
11
11
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 PalavraChave ou Busca por Similaridade.
12
12
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.
13
13
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.
14
14
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.
Técnicas de
RI
Forma
Intermediária
Coleção
de
textos
Mineração
Conhecimento
Técnicas de
EI
Processo de Mineração de Textos (Correa, 2003)
15
15
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
Documentos
relevantes
Relevantes e
Recuperados
Documentos
recuperados
Todos os documentos
16
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|
Documentos
relevantes
Relevantes e
Recuperados
Documentos
recuperados
Todos os documentos
17
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 palavraschave
  Chá or café
  Carro and oficina mecânica
18
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?)
19
Recuperação baseada em
Similaridade de Palavras-Chave
 Um sistema de TM baseado em
similaridade encontra documentos similares
baseado em um conjunto de palavraschave
 A saída é um grau de relevância, onde a
relevância é medida de proximidade das
palavras-chave, a freqüência das palavraschave e assim por diante
20
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)
21
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
22
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
23
Representação binária do
documento como uma matriz
Cada documento é representado um vetor binário
24
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
25
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 
26
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
27
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.
28
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.
29
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
30
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.
31
Exemplo do idf example,
suponha N= 1 milhão
termo
calpurnia
dft
idft
1
6
animal
100
4
sunday
1,000
3
10,000
2
100,000
1
1,000,000
0
fly
under
the
Existe um valor de idf para cada termo na coleção.
32
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:
Palavra
Collection frequency
Document frequency
insurance
10440
3997
try
10422
8760
 Qual palavra poderia ser mais relevante (e
receber mais peso)?
33
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
34
Binario → countagem → weight
matrix
Cada vetor é representado por um número real com
o tf-idf de cada termo
35
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.
36
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
37
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
38
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.
39
39
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:
40
40
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:
41
41
Modelo Vetorial
Para encontrar o grau de similaridade, calcula-se o coseno do ângulo entre documentos ou entre consultas e
documentos:
Onde wi,x é o peso do i-ésimo elemento do vetor x e wi,y
42
é o peso do i-ésimo elemento do vetor y.
42
Modelo Vetorial
Assim, o grau de similaridade entre o documento DOC1
e o documento DOC2 é calculado:
43
43
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:
44
44
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%.
45
45
Identificando Documentos Similares
d1
d2
d3
d4
d5
d6
d7
t1
321
84
31
68
72
15
430
cos(d1,d1) = 1.0000
t2
354
91
71
56
82
6
392
t3
15
32
167
46
289
225
17
cos(d1,d2) = 0.6787
t4
22
143
72
203
31
15
54
t5
74
87
85
92
25
54
121
cos(d1,d3)=0.4363
46