Fundamentos matemáticos da
mineração de dados
Renato Francês e Aldebaro Klautau
Universidade Federal do Pará
1
Exemplo de situações
 Quais os produtos que são comprados juntos pelos
clientes?  regras de associação
 Mala direta: enviar ou não um catálogo de produtos
a um eventual comprador?  classificação
 Diagnóstico de câncer: quais os fatores mais
importantes?  seleção de fatores (parâmetros)
 Mercado de ações: como prever uma grandeza
(número real) com base em outras?  regressão
 Eleitores: como podem ser agrupados? 
agrupamento (“clustering”)
2
Sumário




Definições e etapas do “data mining”
Pré-processamento e o pacote Weka
Minerando regras de associação
Classificação
 Ênfase: árvores de decisão, redes neurais e
SVM (“support vector machine”)
 Seleção de parâmetros ou redução da
dimensionalidade
 Predição ou regressão
 Análise de grupamentos
 “Cluster analysis”
 Conclusões
3
Data mining
 Extração (ou “mineração”) de conhecimento a partir de
grandes quantidades de dados
 “Knowledge discovery in databases” (KDD)
 Etapas do KDD:




Data
Data
Data
Data
cleaning
integration
selection
transformation
 Data mining
 Pattern evaluation
 Knowledge presentation
4
Agrega profissionais de várias áreas
Mineração de
dados
Reconhecimento
de padrões
Tecnologia de
banco de dados
Outros...
5
Aspecto prático: Weka
 Pacote “open-source”
 Escrito em Java
 Integra vários algoritmos
  Fácil de usar
  Não é o mais rápido
6
Dados ou informação “bruta”
 Assumimos estarem organizados em arquivos simples
Nome
Telefone
Peso
País
Bush
Lula
Fidel
1 43 228859
55 23 591927
34 95 499402
67
78
82
EUA
Brasil
Cuba
...
...
...
...
campo ou atributo
registros, exemplos ou “instances”
7
Atributos no Weka




Exemplo, atributos: Nome, Brasileiro, Partido, Peso, Idade
Exemplo, registros (“instance”): Lula, Sim, PT, 80.7, 58
Campo (ou atributo) pode ser:
A) Nominal ou Discreto, K possíveis valores (K é um inteiro)
 Binários, K=2 - brasileiro? sim ou não
 Multi-classe, K>2 - partido? PDT, PT, PFL,..., PMDB
 B) Contínuos
 Números reais – peso? 80.7, 23.2, 56.4, ...
 Inteiros – idade? 1, 2, 3, ...
 C) Strings
 Exemplo: nome? Bush, Saddam, Lula, ...
 D) Outros: data, etc.
8
Formato ARFF do Weka
@relation car
@attribute
@attribute
@attribute
@attribute
@attribute
@attribute
@attribute
buying
maint
doors
persons
lug_boot
safety
class
{vhigh, high, med, low}
{vhigh, high, med, low}
{2, 3, 4, 5more}
{2, 4, more}
{small, med, big}
{low, med, high}
{unacc, acc, good, vgood}
@data
vhigh,vhigh,2,2,small,low,unacc
vhigh,vhigh,2,2,small,med,unacc
...
Obs: CSV + cabeçalho (header)
9
Pré-processamento (limpeza dos dados)
 Discretizar atributos
SAÍDA
QUANTIZADOR
UNIFORME
-4
-3
-2
011
4
010
3
001
2
000
1
-1
1
-1
100
-2
101
-3
110
-4
111
2
3
4
ENTRADA
10
Histograma
 Base IDH (índice de desenvolvimento humano)
 29 exemplos ou “instances”
Analfabe.
Mortalid.
Exp. Vida
Renda
IDH
4
8
78
25880
primeira
5
6
78
19510
primeira
10
35
71
4180
segunda
55
86
57
230
Terceira
...
...
...
...
...
11
Histogramas (uniformes) do atributo “renda”
 Com 10 “bins”
 Com 3 “bins”
15
30
25
10
20
15
5
10
5
0
0
0.5
1
1.5
2
2.5
3
4
x 10
0
0.4505
1.3055
2.1605
4
x 10
12
Histograma não-uniforme
 Exemplo: 5 bins: 4 uniformes e 1 mais largo
14
12
10
8
6
4
2
0
0 0.25 0.50.75 1
3
x 10
4
13
Regras de associação
 Tabela
Idade
Jovem
Jovem
Idoso
Idoso
Renda
Alta
Baixa
Alta
Baixa
Classe
A
B
C
C
Núme.
1402
1038
786
1374
 Regras:
Idade=Jovem E Renda=Alta ==> Classe=A
Idade=Jovem E Renda=Baixa ==> Classe=B
Idade=Idoso ==> Classe=C
14
Definições úteis
 Regra A ==> B
 Confidência = P (A e B ocorrerem juntos) / P(A)
= P (B | A)
 Suporte = P (A e B ocorrerem juntos)
15
Regras de associação – venda de carro
 Exemplo (algoritmo apriori) para dataset “car”:
1. safety=low 576 ==> class=unacc 576 conf:(1)
2. persons=2 576 ==> class=unacc 576 conf:(1)
3. maint=vhigh 432 ==> class=unacc 360 conf:(0.83)
4. buying=vhigh 432 ==> class=unacc 360 conf:(0.83)
5. lug_boot=small 576 ==> class=unacc 450 conf:(0.78)
6. doors=2 432 ==> class=unacc 326 conf:(0.75)
7. buying=high 432 ==> class=unacc 324 conf:(0.75)
8. maint=high 432 ==> class=unacc 314 conf:(0.73)
9. doors=3 432 ==> class=unacc 300 conf:(0.69)
10. lug_boot=med 576 ==> class=unacc 392 conf:(0.68)
16
Dataset “futebol”
@relation futebol
@attribute
@attribute
@attribute
@attribute
@attribute
outlook {sunny, overcast, rainy}
temperature real
humidity real
outofstate {TRUE, FALSE}  joga fora?
wins {yes, no}
@data
sunny,85,85,FALSE,no
sunny,80,90,TRUE,no
overcast,83,86,FALSE,yes
...
17
Regras para “futebol”
Best rules found:
1.
2.
3.
4.
5.
outlook=overcast 4 ==> wins=yes 4 conf:(1)
outlook=rainy outofstate=FALSE 3 ==> wins=yes 3 conf:(1)
outlook=rainy wins=yes 3 ==> outofstate=FALSE 3 conf:(1)
humidity='(89.8-92.9]' 3 ==> outofstate=TRUE 3 conf:(1)
humidity='(77.4-80.5]' 2 ==> outlook=rainy outofstate=FALSE wins=yes 2
conf:(1)
6. outlook=rainy humidity='(77.4-80.5]' 2 ==> outofstate=FALSE wins=yes 2
conf:(1)
7. humidity='(77.4-80.5]' outofstate=FALSE 2 ==> outlook=rainy wins=yes 2
conf:(1)
8. humidity='(77.4-80.5]' wins=yes 2 ==> outlook=rainy outofstate=FALSE 2
conf:(1)
9. outlook=rainy humidity='(77.4-80.5]' outofstate=FALSE 2 ==> wins=yes 2
conf:(1)
10. outlook=rainy humidity='(77.4-80.5]' wins=yes 2 ==> outofstate=FALSE 2
conf:(1)
18
Classificação
 Problema:
 Dado um vetor x com parâmetros, ache sua classe y
x
 Exemplo:
Conjunto
de treino 
classificador
y
?
ou
Compr.
Peso
12
3.2
10
0.5
14
2.8
Classe y
Fase de “teste”:
x = (13, 4.2)
y=?
 Avaliação: taxa de erro
19
Métodos de avaliação
 Testar (obter taxa de erro) usando o próprio conjunto de
treino
 Testar com conjunto de “teste”, disjunto do de treino
 Validação cruzada (“cross-validation”):
 Repartir o conjunto de treino em N subconjuntos (“folds”)
 Considerar cada um o conjunto de teste e treinar com os
N-1 restantes
 Deixe um de fora (“leave-one-out”)
 Caso extremo de cross-validation: apenas 1 exemplo compõe o
conjunto de teste e todo o resto é usado para treinar
 Matriz de confusões (“confusion-matrix”)
20
“Over-fitting” e seleção dos parâmetros
21
Como projetar classificadores?
22
Piranha or Pirarucu?
 Piranha
 Pirarucu
23
Use “histogramas” obtidos
do conjunto de treinamento
Histograma
do
comprimento
24
Regiões de decisão
 No caso anterior: um único parâmetro (comprimento do
peixe)  regiões de decisão eram segmentos de uma
reta
 Caso mais geral: regiões no espaço k-dimensional
 Exemplo bidimensional: vogais de Peterson & Barney
 2 atributos contínuos F1 e F2 e 1 atributo (classe) nominal:
ER, UW, UH, AO, AA, AH, AE, EH, IH, IY
 Exemplos: 1000, 3500, AH
832, 2500, EH
...
25
 back “which part of the tongue is raised” front 
P&B vowel dataset
 close
“how far the tongue is raised”
open 
26
Exemplo de regiões de decisão
27
Árvore de decisão C4.5 (J4.8)
F2 <= 1600
| F1 <= 586
| | F2 <= 990: UW (92.0/47.0)
| | F2 > 990
| | | F2 <= 1200: UH (50.0/17.0)
| | | F2 > 1200: ER (63.0/23.0)
| F1 > 586
| | F2 <= 1250: AA (59.0/33.0)
| | F2 > 1250: AH (56.0/24.0)
F2 > 1600
| F1 <= 490
| | F1 <= 350: IY (68.0/5.0)
| | F1 > 350: IH (61.0/21.0)
| F1 > 490
| | F1 <= 652: EH (71.0/34.0)
| | F1 > 652: AE (79.0/19.0)
Tamanho: 17 nós e 9 folhas
28
Dataset IDH (índice de des. humano)

Árvore de decisão (algoritmo C4.5 / J4.8)
Analfabetismo <= 10
| Mortalidade <= 8: primeira (7.0/1.0)
| Mortalidade > 8: segunda (11.0)
Analfabetismo > 10
| Analfabetismo <= 17
| | ExpectVida <= 66: terceira (2.0)
| | ExpectVida > 66: segunda (2.0)
| Analfabetismo > 17: terceira (7.0)
Número de folhas: 5
Tamanho da árvore: 9

1.
2.
3.
...
Regras (algoritmo Apriori / requer discretização)
IDH=terceira 9 ==> Renda='(-inf-2795]' 9 conf:(1)
Mortalidade='(12.2-20.4]' 7 ==> IDH=segunda 7 conf:(1)
IDH=primeira 6 ==> Analfabetismo='(-inf-7.3]' Mortalidade='(-inf-12.2]' 6
conf:(1)
29
Weka: Algoritmos para treinamento de classificadores
backpropagation neural network
decision tree J4.8 (equivalente ao C4.5)
support vector machine (SVM)
AdaBoost
naïve Bayes
etc.
31
Redes neurais artificiais
 Tenta imitar cérebro: unidades são “neurônios”
33
Perceptron
 Precursor das redes neurais atuais
 Não há “camada escondida”: y = W x
34
Regiões de decisão para P&B: rede neural
35
Exemplo de regiões de decisão: árvore
36
Classificador moderno: SVM
 Desenvolvida por Vladimir Vapnik e
colaboradores
 Início: década de 60
 Concepção atual: [Cortes & Vapnik, 1995]
 Importantes ingredientes básicos:
 Classificadores lineares de máxima margem
 “Truque do kernel” para obtenção de
classificadores não-lineares
37
Classificadores lineares (problemas binários)
 f(x)=sgn(<x, w> + b)
 x,w є d,
f(x) є {1, 1}
e
b є  (“bias”)
d

 x, w  x w cosθ   x nw n é o produto interno
n 1
 sgn retorna o sinal, com sgn (0) = 1
 w é um vetor normal
ao hiperplano separador
Exemplo: d=2, x=(x1, x2)
38
Classificadores lineares (cont.)
 f(x)=sgn(<x, w> + b), com w=(2, 4), b=6
6
4
+1
w
hiperplano
f(x)=0
x2
2
0
-2

1
-4
-6
-6
-4
-2
0
x1
2
4
6
39
Classes “linearmente separáveis”
 Perceptron versus SVM
perceptron
SVM (hiperplano
com máxima
margem)
41
Classificadores lineares são limitados
 Exemplo clássico:
EXOR (ou exclusivo)
 Solução:
mapeamento Φ(x) não-linear
 Ex: x=(x1, x2)
(x)  (x 12 , x 22 , 2x 1x 2 )
f (x)  sgn(w 1x 12 w 2x 22 w 3 2x 1x 2  b )
f (x)  sgn(x 12  x 22  2x 1x 2  0.5)
 “Maldição da dimensionalidade”
42
“Truque do kernel”
 w é uma combinação de vetores de treinamento
N
 Não é necessário calcular
o mapeamento Φ explicitamente
w   i x i
i 1 da dimensionalidade” (“statistical
 Escapa-se da “maldição
learning theory”)“dual” do classificador
 Representação
N
 Algoritmos baseados em produtos internos podem ser 
f (x' )  sgn  w, x'  b   sgn  i  x i , x'  b 
“kernelizados”
 i 1

 Usando-se mapeamento Φ não linear

N

f (x' )  sgn   i  (x i ), (x' )  b 
 i 1

 Exemplo: EXOR
(x)  (x 12 , x 22 , 2x 1x 2 )
 (x), (x' )  (x 1x 1)2  (x 2x 2 )2  2x 1x 2x 1x 2  x, x' 2
43
“Truque do kernel” (cont.)
 Kernel: produto interno no espaço imagem de Φ
k (x' , xi )  (x' ), (xi ) 
 Kernels mais usados:
 Polinomial
k (x' , xi )  x' , xi p
SVM linear, p=1
 Gaussiano
k ( x ' , x i )  exp(  x ' x i
2
/c )
 Vetores de suporte: exemplos xi para os quais λi ≠ 0
N

f (x' )  sgn   i k (x' , x i )  b 
 i 1

44
SVM não-linear - exemplo
 2 classes:
“círculos” o - mistura de 2 Gaussianas
“pontos” ● - mistura de 3 Gaussianas
 SVM com kernel Gaussiano
 Médias marcadas com “x”
 5 vetores de suporte:
marcados com círculo extra
 Não “modela”, concentra-se
nas regiões de decisão
45
Classificador “support vector machine”
pesos
kernel
“compara” x e xi
vetores de suporte: x1, x2, x3 e x4
entrada x
46
SVM (cont.)
B classificadores binários SVM
f1 ( x)

f B ( x)
entrada x
Combina decisões f1(x),...,fB(x) via matriz ECOC
47
Classificadores: ANN versus SVM
 Rede neural
 SVMs
48
Problema do Weka/SVM: tempo de treinamento
 Usamos 4 pacotes SVM “open source”
Weka (Java)
SVMTorch (C++)
SVMLight (C)
SvmFu (C++)
maior conjunto de treino
isolet
6238
26
e-set
2160
9
letter
16000
26
satimage
4435
6
pendigits
7494
10
timitplp40
138839
39
pe
nd
ig
it s
-a
pe
nd
ig
it s
-o
t im
it p
lp
40
-a
t im
it p
lp
40
-o
ag
eo
sa
tim
r-o
sa
tim
le
tte
r-a
le
tte
ese
t-o
ese
t-a
le
t- o
iso
le
t- a
Weka*
SVMLight
SvmFu
iso
outros
Torch
20
18
16
14
12
10
8
6
4
2
0
dim.
ag
ea




# treino
“dataset”
49
Redução da dimensionalidade
 Métodos “filters”
 Ganho de informação
 AdaBoost
 Métodos “wrappers”
 Depende dos classificadores
 Problema: complexidade computacional
50
“Breast-cancer” dataset
Atributos
1. Class: no-recurrence-events, recurrence-events
2. age: 10-19, 20-29, 30-39, 40-49, 50-59, 60-69, 70-79,
80-89, 90-99.
3. menopause: lt40, ge40, premeno.
4. tumor-size: 0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-34,
35-39, 40-44, 45-49, 50-54, 55-59.
5. inv-nodes: 0-2, 3-5, 6-8, 9-11, 12-14, 15-17, 18-20, 2123, 24-26, 27-29, 30-32, 33-35, 36-39.
6. node-caps: yes, no.
7. deg-malig: 1, 2, 3.
8. breast: left, right.
9. breast-quad: left-up, left-low, right-up, right-low, central.
10. irradiat: yes, no.
51
Atributos selecionados
 Método 1
Selected attributes: 3,4,5,6,9 : 5
tumor-size
inv-nodes
node-caps
deg-malig
irradiat
 Método 2
Selected attributes: 6,4,3,5,9,1,8,7,2 : 9
0.07701 6 deg-malig
0.069
4 inv-nodes
0.05717 3 tumor-size
0.05126 5 node-caps
0.02582 9 irradiat
0.01061 1 age
0.00885 8 breast-quad
0.00249 7 breast
0.002
2 menopause
52
Exemplo de experimento prático
 3 x 253 + 1 = 760 “features”
 SVMs com kernel linear (perceptron)
 Algoritmo de seleção:
 AdaBoost vs. ganho de informação (“info gain”)
45
40
35
30
25
20
15
10
5
0
info gain
boosting
others
5
25
40
100
all 760
plp 118
53
Histograma dos parâmetros selecionados
F0, voicing, 4 formants
PLP (39)
Seneff’s synchrony (40)
Seneff’s envelope (40)
MFCC (39)
RASTA (39)
Filter-bank (50)
54
Predição (ou regressão)
 Regressão linear
 Regressão não-linear
55
Regressão linear
 Código Matlab
N=100; a=3;
t=rand(1,N);
x=a*t+rand(1,N);
plot(t,x,'o');
4
3
2
1
 Linear Regression Model (Weka)
0
0
0.2
0.4
0.6
0.8
1
0.2
0.4
0.6
0.8
1
4
Y = 2.9974 * X + 0.4769
Correlation coefficient
Mean absolute error
3
0.9358
0.2744
2
1
0
0
56
Regressão não-linear
 Código Matlab
N=100;
a=3;
x=rand(1,N);
y=a*cos(2*pi*x)+rand(1,N);
plot(x,y,'o');
4
3
2
1
0
-1
 Problema:
 Linear não resolve
-2
-3
0
0.2
0.4
0.6
0.8
1
 Solução:
 Redes neurais
 SVM
57
Análise de grupamentos
 Algoritmos:
 K-means
 EM (“expectation maximization”)
58
Weka avançado
 Usando Weka da linha de comando
 PATH
 DOS: set
 Linux: bash (export), tcsh (setenv)
 CLASSPATH
 Modificando o código fonte do Weka
 Compilador JBuilder
59
Conclusões
 Mineração de dados é uma área
multidisciplinar que se beneficia, dentre
outras, de técnicas de “reconhecimento de
padrões”
 Discutimos: regras, classificação, regressão,
agrupamentos
 Reconhecimento de padrões exige alguma
matemática para se entender os algoritmos
 Weka é ideal para iniciantes, ou pessoas que
desenvolvam algoritmos na área
 A competência do profissional é fator
essencial para “bamburrar” em conhecimento
60
Para ler mais:
 Data mining: Concepts
and techniques. Jiawei Han
e Micheline Kamber, Morgan
Kaufmann, 2001
 Data mining: Practical
machine learning tools
and techniques with Java
implementations. Ian
Witten e Eibe Frank, Morgan
Kaufmann
 http://www.laps.ufpa.br
61