Marcus Sampaio
DSC/UFCG
6.1 O Que É Mineração
de Texto?
Marcus Sampaio
DSC/UFCG
• É a expressão que se dá para a tarefa de
classificar documentos
– Por exemplo: classificação por tópico  esporte,
economia, “spam e-mail”, etc
• ‘esporte’, ‘economia’, ‘spam’ são classes
– No mundo de documentos, usa-se mais rótulo (“label”)
• Documento: texto não-estruturado (sem meta
dados), em oposição a texto semi-estruturado
e estruturado (com meta dados)
– Mineração de Texto  Classificação de
Documentos
Marcus Sampaio
DSC/UFCG
• Classificação de documentos estruturados
– Classificação de Documentos Estruturados
• Cada documento é representado por uma linha (ou registro, ou
instância) de uma tabela não-normalizada
– Exemplo: os prontuários dos pacientes de nossa clínica
oftalmológica  exemplo de motivação  foram transformados
em estruturas (linhas de tabela)
– Tipos de classificação
• Supervisionada
• Não-Supervisionada
• Classificação de documentos não-estruturados
– A idéia é a mesma: representar um documento por uma
estrutura
Marcus Sampaio
DSC/UFCG
• Classificação Supervisionada de Documentos
– Um documento é representado como um vetor
numérico
– Uma função mapeia a representação numérica
estruturada para um rótulo
• f:wL
w é um vetor em que cada célula indica a presença, ou
quantidade, de uma palavra  vetor numérico
L é um rótulo (“label”)
6.2 Representação de
Documentos como Vetores Numéricos
Marcus Sampaio
DSC/UFCG
word1
word2
word3
word4
word5
...
wordN
label
0
1
0
1
0
...
1
1
1
0
1
0
0
...
0
0
1
0
0
1
1
...
0
1
0
1
0
0
1
...
1
0
1
0
0
1
0
...
1
1
0
1
0
0
1
...
0
1
0
0
1
1
0
...
0
0
0
0
1
0
1
...
0
1
Marcus Sampaio
DSC/UFCG
• No exemplo, os números representam a
presença  1  ou ausência  0  de uma
palavra wordi
• Podia ser também um contador de freqüência
de wordi
– Daí porque é mais apropriado referir-se a vetor
numérico
• O que são as wordi?
• O que dizer sobre a célula label?
Marcus Sampaio
DSC/UFCG
• Dicionário (“dictionary”, “feature”)
– Palavras relevantes que podem estar presentes em um
documento
• word1, word3, word6, ..., wordN
• Escolhidas pelo usuário, por exclusão de stop words
• Dado um dicionário e um documento, o documento é
representado por um vetor de números
– Na forma mais simples, vetor de 1s e 0s, representando a
presença ou ausência de palavras individuais
– Mas os números podem ser quaisquer, desde que
semanticamente válidos
• No slide (“spreadsheet”) do exemplo, cada linha é um
vetor representando um documento, por exemplo, um
artigo financeiro
Marcus Sampaio
DSC/UFCG
• “Label”
– Representa um atributo de classificação
• Binário
– 1 (positivo), Financeiro
– 0 (negativo), ñ Financeiro
• Note que a estratégia é aproximar o problema
para uma tarefa de classificação ‘clássica’
– Instâncias positivas e negativas
• Mais de um “label”?
– Dicionários temáticos, ou locais
– n “spreadsheets”, um para cada “label”
6.3 Geração de Vetores
Marcus Sampaio
DSC/UFCG
• “Tokenizaton”
– Cada palavra relevante para o dicionário é um “token”
• Para vetores binários, é assinalada a presença ou não de um
“token” (palavra)
• Para vetores não-binários, a freqüência do “token” é a métrica
– Há vários modelos de freqüência (ver o livro “Text Mining”, na
Bibliografia)
– “Stemming” ou “Lemmatization”
• “Tokens” sinônimos  “Token”
• Note que, se o dicionário for grande, e geralmente o
é, os vetores tendem a ser esparsos
– Necessidade de técnicas de compressão de vetores
6.3.1 Vetores Esparsos
0
15
0
3
12
0
0
0
8
0
5
2
Marcus Sampaio
DSC/UFCG
(2,15) (4,3)
(1,12)
(1,8) (3,5) (4,2)
6.4 Técnicas de Classificação
de Documentos
• Similaridade
• Modelagem Estatística
• Regras de Decisão
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
6.4.1 Similaridade
Labeled
Spreadsheet
1
0
1
0
Similarity
Scores
1
0
0
0
1
0
1
0
0
1
0
1
0
0
0
1
1
0
0
1
0
0
1
0
1
0
1
0
0
1
1
0
0
1
Vector
1
0
2
1
New
Document
1
Measure
Similarity
1
1
2
A resposta é o “label” que
ocorre mais frequentemente
nos k documentos mais
similares
Marcus Sampaio
DSC/UFCG
1. Compute the similarity of newDoc to all
documents in collection C
2. Select the k documents that are most similar
to newDoc
3. The answer is the label that occurs most
frequently in the k selected documents
Marcus Sampaio
DSC/UFCG
•
•
O novo documento do exemplo é
classificado como 1, significando um
documento sobre economia, ou sobre
fofocas, etc.
Note que o algoritmo se baseia unicamente
na ‘sintaxe’ do documento
– Recorde-se das vantagens e desvantagens de
consultas abertas
•
Vejamos um algoritmo mais sofisticado
– Ainda consulta aberta
Marcus Sampaio
DSC/UFCG
• Métodos Lineares de Escore (“Linear Scoring
Methods”)
– Cada palavra do dicionário tem um peso
• O peso de um atributo indica quão distinguível é o
atributo para rotular o documento
– Se um atributo é muito freqüente em todos os documentos
do conjunto-treinamento, então não é significativo, e seu
peso deve ser comparativamente pequeno
• Os pesos são induzidos do conjunto-treinamento
Marcus Sampaio
DSC/UFCG
Linear Model
New Document
Words
dividend,
payout, rose
Score
1.4629
O escore positivo indica que
se trata de um documento sobre
bolsas de valores
Word
Weight
dividend
0.8741
earnings
0.4988
eight
-0.0866
extraordinary
-0.0267
months
-0.1801
payout
0.6141
rose
-0.0253
split
0.9050
york
-0.14629
...
...
Marcus Sampaio
DSC/UFCG
– O problema é distinguir entre duas classes
• Escore positivo prediz a classe positiva (rótulo = ‘sim’)
• Escore negativo prediz a classe negativa (rótulo = ‘não’)
Score( D)   w j x j  b
j
D é o documento
wj é o peso para a j-ésima palavra do dicionário
b é uma constante
xj é 1 ou 0, dependendo da presença ou não da j-ésima palavra
Marcus Sampaio
DSC/UFCG
• Família “k-Nearest-Neighbor”
– O método básico
• Mede a distância entre dois vetores, representando
respectivamente dois documentos
• Distância(x,y)=(x1-y1)2 + ... + (xm-ym)2
• Quanto maior a distância, mais fraca a conexão entre os
documentos
– Note que a idéia central é a mesma do “k-means”
Marcus Sampaio
DSC/UFCG
– Contagem de palavras, com bonificação
O documento D(i) de uma coleção (conjunto-treinamento) é
comparado com o novo documento, com k palavras
k
Sim ilarity( D(i))   w( j )
j 1
w( j )  1  1 / df ( j ), if word ( j ) occursin bothdocum ents
0
df ( j )
No. de documentos em que a palavra j ocorre na coleção
O inverso é o bonus
Marcus Sampaio
DSC/UFCG
– “Cosine Similarity”
• O método clássico de comparar documentos no campo
de “Information Retrieval”
w( j )  tf ( j )  log2 ( N / df ( j ))
norm( D) 
2
w
(
j
)

cosine(d1, d 2)   (wd1 ( j ) * wd 2 ( j )) /(norm(d1)  norm(d 2))
tf ( j )
Freqüência da palavra j em um documento
N No. De documentos do conjunto-treinamento
Marcus Sampaio
DSC/UFCG
• Sobre o desempenho de algoritmos de
similaridade
– Listas invertidas
List of
Words
Documents
6.4.2 Modelagem
Estatística
Marcus Sampaio
DSC/UFCG
• Naïve Bayes
w1 w2 w3 w4 class
Class=1 Class=0
1
0
0
1
1
P(Class)
0.40
0.60
0
0
0
1
0
P(w1)
0.75
0.50
1
1
0
1
0
P(w2)
0.25
0.67
1
0
1
1
1
P(w3)
0.50
0.33
0
1
1
0
0
P(w4)
0.50
0.50
1
0
0
0
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
1
1
0
0
Pr(w1Class) = Probabilidade
de w1 = 1 quando Class = 1 (0) )
Marcus Sampaio
DSC/UFCG
– Considere um novo documento D
0
1
1
1
– P(Class=1D)=((1-.75)x.25x.5x.5)x.4=.00625
– P(Class=0D)=((1-.5)x.67x.33x.5)x.6=.03333
– P(Class=1D)=.00625/(.00625+.03333)=16%
– P(Class=0D)=.03333/(.00625+.03333)=84%
6.4.3 Regras de
Decisão
Marcus Sampaio
DSC/UFCG
• Regras induzidas de relatórios de ganhos em
bolsas de valores, fornecidos pela agência
Reuters
shr  earn
div  earn
dividend  earn
payout  earn
qtr  earn
earnings & sees  earn
quarter & cts  earn
split  earn
profit  earn
TRUE  ~earn
Marcus Sampaio
DSC/UFCG
• Cada regra é uma frase, ou simplesmente
uma conjunção de palavras
• Dado um novo documento D
– Se qualquer das frases ...  earn, na ordem,
é encontrada, D é classificado como um relatório
de ganho na Bolsa
• Diz-se também que o rótulo (“label”) do documento é
positivo (em relação a ganhos na Bolsa)
– Se nenhuma das frases é encontrada no
documento, então D não é um relatório de ganho
na Bolsa  TRUE  ~earn (última regra a ser
testada)
• Diz-se também que o rótulo do documento é negativo
Biblioteca
WEKA?
Marcus Sampaio
DSC/UFCG
• Algoritmos WEKA, de Classificação
Supervisionada
– ID3, J48, Prism, ...
– Problemas
• Não trabalham com vetores esparsos
• Não se dão bem com alta dimensionalidade
• Inferem ... Wordi = ‘0’ ..., o que não queremos
• Necessidade de novos algoritmos
Qualidade de Regras
de Decisão
Marcus Sampaio
DSC/UFCG
• Avaliação da qualidade de modelos de regras de
decisão
RSet
1
2*
3
4
5**
6
7
Rules
9
6
5
4
3
2
1
TraiErr TstErr
TstSD
AvgW
.0000
.0337
.0787
.0899
.1011
.1910
.3820
.0349
.0320
.0349
.0349
.0335
.0417
.0515
9.9
7.0
5.0
4.0
3.0
2.0
1.0
.1236
.1011
.1236
.1236
.1124
.1910
.3820
Marcus Sampaio
DSC/UFCG
• Os melhores modelos -- conjuntos de regras (“RSet”)
– são aqueles assinalados com ‘*’ e ‘**’,
respectivamente
– Têm as melhores acurácias de teste
• Melhores estimativas de acerto em classificar novos
documentos
• Comparativo dos modelos ‘*’ e ‘**’
– As acurácias de teste são próximas, ‘*’ é um pouco melhor
– Os desvios padrão (“Standard Deviation” – SD) são
próximos, ‘*’ é um pouco melhor
– O modelo ‘**’ é bem mais acionável (média de 3 palavras,
contra média de 7 palavras)
• Note a importância, também, da métrica desvio
padrão
Sobre Métricas de Qualidade
de Classificação de Documentos
Marcus Sampaio
DSC/UFCG
• Métricas de Qualidade
– As mesmas para documentos estruturados
•
•
•
•
Acurácia de teste
Precisão
Cobertura (“Recall”)
Média Harmônica (“F-Measure”)
– O exemplo de “spam e-mail” visto é na verdade
mineração de texto
Software de Mineração
de Texto
• TMSK: Text-Miner Software Kit
– Ver a página da disciplina
• Manual
• Instalador
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• Classificadores
• Naïve Bayes (nbayes, testnbayes)
• Método Linear de Score (linear, testline)
– Parâmetros para testnbayes
• Limiar de probabilidade (“Probability-threshold”)
– Deve ser excedido para uma classificação positiva
– Default: 0.5
• Limiar de rejeição (“Reject-threshold”)
– Deve ser excedido para qualquer classificação (positiva ou
negativa)
– Default: 0.5
– Parâmetros para linear
• Feature-type: binary, tf, tf*df
• Default: tf
– Parâmetros para testline
• Decision-threshold
Marcus Sampaio
DSC/UFCG
– testnbayes
• Probability-threshold: 70%
– Se classificação positiva > 70% OK senão classificação
negativa
• Reject-threshold: 60%
– Classificação positiva: 45%
– Classificação negativa: 55%
– Decisão: documento não-classificado
Marcus Sampaio
DSC/UFCG
• Outro clasificador: matcher
– Dado um novo documento e uma coleção de
documentos  conjunto-treinamento  escolhe
os documentos da coleção mais similares ao
primeiro
• k-Nearest-Neighbor
Marcus Sampaio
DSC/UFCG
• RIKTEXT: Rule Induction Kit for Text
– Ver a página
• Manual
• Instalador
Marcus Sampaio
DSC/UFCG
– Induz Regras de Classificação de documentos em
Positivos e Negativos
– O modelo é uma lista ordenada de regras
<conjunçao-de-palavras-do-dicionário>  positivo
– A última regra da lista ordenada é TRUE 
negativo
– O algoritmo de predição pára na primeira regra
casada
Marcus Sampaio
DSC/UFCG
• Entradas para TMSK e RIKTEXT
– Dicionário
– Documentos XML
• Ver detalhes no manual do usuário
– Representações vetoriais de documentos