SIN5001 Parte3 aula3

Prévia do material em texto

Mineração de Dados 
Material extraído do minicurso: “Uma introdução à 
Mineração de Dados (Data Mining) – com Inteligência 
Artificial” ministrado pelos docentes: Prof. Dr. Clodoaldo 
Aparecido de Moraes Lima e Profa. Dra. Sarajane 
Marques Peres na Segunda Semana de Sistemas de 
Informação 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Introdução 
2 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
A Evolução 
3 
Sistemas de Gerenciamento 
de Dados em Arquivos (1960) 
Sistemas de Gerenciamento de Banco de Dados 
(SGBD – SQL – OLTP) (1970-1980) 
 
 
 
 
 
 
 
 
Nova Geração de Sistemas de Informação e Dados Integrados 
(Presente e Futuro) 
Sistemas de 
Gerenciamento de 
Banco de Dados 
Avançados (OR – OO – 
Espacial – Temporal – 
Baseado em 
Conhecimento ...) 
(1980- atual) 
Análise de Dados 
Avançada (Data 
Warehouse, OLAP, 
KDD, Data Mining) 
(1980- atual) 
Sistemas de Banco de 
Dados baseados em 
Tecnologia WEB (XML – 
Integração e 
Recuperação da 
Informação ) 
 (1990- atual) 
Adaptado de Han & Kamber (2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Tarefas de Mineração de Dados 
• Mineração de Dados: 
 
– Tarefas Preditivas 
• Classificação  incluindo Descoberta de Desvios e 
 Previsão de Séries 
• Regressão 
 
– Tarefas Descritivas 
• Regras de Associação  incluindo Associações 
 Temporais 
• Agrupamentos 
• Sumarização 
4 Obs: Predição com Agrupamento !!! 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Mineração de Dados : interdisciplinaridade 
5 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
A tarefa de Associação 
6 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
Padrão Itens frequentes 
7 
Padrão sequencial Padrão estruturado 
frequente (grafo) 
S 
A 
B 
à 
O 
A 
M 
A 
C 
I 
A 
N 
T 
E 
S 
A 
B 
à 
O 
A 
M 
A 
C 
I 
A 
N 
T 
E 
pizza 
chocolate 
Consumo: 
caipirinha  feijoada  laranja 
Compra: 
carro  seguro teclado 
mouse 
monitor 
CPU 
Comportamento: 
ingresso  pipoca 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
Exemplo (Han & Kamber, 2006) 
 
 Como gerente da marca AllElectronics, você gostaria de saber mais sobre os hábitos 
de compras de seus clientes. Mais especificamente, você gostaria de saber quais 
grupos ou conjuntos de items os clientes geralmente compram em uma visita à sua 
loja. 
 Para responder a essa pergunta é necessário fazer uma análise (de mercado) das 
compras realizadas, observando os dados provenientes das transações (compras) dos 
clientes na loja. 
 Você poderia usar os resultados dessa análise para planejar estratégias de marketing, 
através de anúncios, projeto de novos catálogos, rearranjo do layout da loja. 
 Por exemplo, itens que são comprados “juntos” (em uma mesma compra) podem ser 
colocados em lugares próximos de forma a encorajar a venda de tais items. 
8 
Continua ... 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
Exemplo (Han & Kamber, 2006) 
 
 Se clientes que compram computadores também tendem a comprar 
antivírus (na mesma compra). Então colocá-los em lugares próximos pode 
ajudar a aumentar as vendas dos dois produtos. 
 Alternativamente, a estratégia pode ser colocá-los em lados opostos da loja 
de forma a forçar o cliente andar por toda a loja e, eventualmente, escolher 
outros produtos para comprar. 
 Análise de mercado também pode suportar a decisão sobre quais produtos 
colocar em liquidação ou retirar do mercado. 
9 
Esta seção (teoria sobre Regras de Associação) do 
minicurso é baseada no Capítulo 5 de Han & Kamber 
(2006). 
Fraldas e cervejas: 
uma lenda urbana?!?! 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Representação: considere seu universo como sendo o 
conjunto de produtos (itens) vendidos na loja. 
 
– A existência ou ausência de cada um desses itens pode ser 
representada por uma variável booleana. 
– Cada compra pode ser representada por um vetor de variáveis 
booleanas, sendo que, de fato, nesta compra (transação) foram 
comprados apenas os itens valorados com verdadeiro. 
– Analisando esses vetores, é possível descobrir itens que 
frequentemente aparecem juntos (estão associados), constituindo um 
padrão de comportamento. 
– Esse “padrão” pode ser representado por meio de uma regra de 
associação. 
 
10 
computador  antivirus 
 fralda  cerveja 
(Han & Kamber, 2006) 
antecedente  consequente 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
Formalizando .... 
 
Seja L = {I1, I2, ..., Im} um conjunto de itens. 
Seja D, um conjunto de dados relevantes para a tarefa constituído de 
transações de banco de dados, onde cada transação T é um conjunto 
de itens tal que T L. 
Cada transação é associada a um identificador (TID). 
Seja A e B subconjuntos de itens. 
A transação T contém A se e somente se A T. 
 
 
 
 Uma regra de associação é uma implicação da 
 forma A  B, onde A L, B L e A B = . 
 
11 


  

(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Medidas de “interessabilidade” 
 
 
Suporte = utilidade da regra 
Confiança = certeza sobre a regra 
 
O suporte de 2% para a regra acima significa que 2% de todas as transações 
analisadas mostram que computadores e antivirus são comprados juntos. 
 
A confiança de 60% da regra acima significa que 60% dos fregueses que 
compram um computador também compram um antivirus. 
 
 Regras de associação interessantes são aquelas que possuem um suporte 
e uma confiança mínimos (de acordo com um limite inferior pré- 
 estabelecido) !! 
12 
computador  antivirus [ suporte = 2%, confiança = 60%] 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
Uma regra A  B existe em um conjunto de transações D com suporte 
s, onde s é a porcentagem de transações em D que contém A U B. 
– Contém tanto A quanto B 
– É calculado como a probabilidade P(AUB), a probabilidade da 
transação conter a união do subconjunto A e do subconjunto B. 
 
suporte (A  B) = P(AUB) 
 
 
13 
Uma regra A  B tem confiança c no conjunto de transações D, onde 
c é a porcentagem de transações em D contendo B dado que contém 
 A. 
 - É calculada como a probabilidade condicional P(B|A). 
 
 confiança (A  B) = P(B|A) 
 
 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
Definições 
 
• Itemset: um conjunto de itens. 
• k-itemset: um conjunto de k itens. 
– 2-itemset: um conjunto de 2 itens 
{computador, antivirus} 
• Frequencia de ocorrência de um itemset (suporte do itemset): número 
de transaçõesque contém o itemset. 
• Itemset frequente: um conjunto de itens que satisfaz a um suporte 
mínimo. 
 
 
 O conjunto de k-itemsets frequentes é denotado por Lk. 
 
14 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
 
confiança (AB) = 
P(B|A) = 
suporte (AUB) / suporte (A) = 
suporte do itemset (AUB) / suporte do itemset (A) 
 
Obs.: uma vez que a frequencia dos itemsets foram calculadas, os cálculos do 
suporte e da confiança de uma regra podem ser facilmente realizados. 
 
 Assim, o problema de minerar regras de associação pode ser reduzido ao 
problema de minerar os itemsets frequentes. 
15 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
Processo de mineração de regras de associação: 
16 
Encontrar todos 
os itemsets 
frequentes 
Gerar regras de 
associação 
fortes a partir 
destes itemsets 
Determine o limite mínimo para o 
suporte (min-sup) 
(varia para cada aplicação e é 
uma decisão de projeto) 
Regras de associação fortes são aquelas 
que satisfazem ao min-sup e ao min-conf. 
Determine o limite mínimo para a 
confiança (min-conf) 
(varia para cada aplicação e é uma 
decisão de projeto) 
Passo 
mais 
custoso!!! 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Principal desafio: encontrar uma maneira eficiente para calcular os 
itemsets frequentes de um grande conjunto de dados. 
 
• Observe o seguinte exemplo (Han & Kamber, 2006, p. 231): 
17 
Um 100-itemset frequente {a1, a2, ..., a100}, contém = 100 1-itemset 
frequentes: {a1}, {a2}, ..., {a100}, 2-itemset frequentes: {a1,a2}, {a1,a3}, 
..., {a99,a100}, e assim por diante. 
O número total de itemsets frequentes que ele contém é: 
 
 
 
 
 
 
• Esse problema é resolvido com a definição de 
fechamento (clausura) de itemsets frequentes. 






1
100






2
100
.1027.112
100
100
2
100
1
100
30100 


















(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Um itemset X é fechado em um conjunto de dados S se não existe nenhum 
super-itemset Y tal que Y tenha o mesmo suporte que X em S. 
• Um itemset X é um itemset frequente fechado em um conjunto S se X é tanto 
fechado quanto frequente em S. 
• Um item itemset X é um itemset frequente máximo em um conjunto S se X é 
frequente, e não existe nenhum super-itemset tal que X Y e Y é frequente 
em S. 
• Seja C o conjunto de itemsets frequentes fechados para um conjunto de 
dados S, que satisfaz um limite mínimo para suporte, min-sup. Seja M o 
conjunto de itemsets frequentes máximos para S satisfazendo min-sup. 
 
– C e a informação sobre suporte de itemsets podem ser usados para 
derivar todo o conjunto de itemsets frequentes. 
– M registra somente o suporte dos itemsets máximo. 
18 
Exemplo! 

(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
Han & Kamber, 2006, p. 232 
 
 
Supondo um banco de dados com apenas duas transações: 
{<a1, a2, ..., a100>};{<a1, a2, ..., a50>}. 
Seja sup-min = 1. 
Encontramos dois itemsets frequentes fechados e seu suporte: 
C = {{a1, a2, ..., a100} : 1; {a1, a2, ..., a50} : 2} 
Existe um itemset frequente máximo: 
M = {{a1, a2, ..., a100} : 1}. 
De C é possível derivar, por exemplo, que: 
19 
{a2,a45 : 2} desde que {a2,a45} é um sub-itemset de 
 {a1, a2, ..., a50} : 2 
 {a2,a55 : 1} desde que {a2,a55 } é um sub-itemset de 
{a1, a2, ..., a100} : 1 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
 
 
Regras de Associação 
 
O algoritmo Apriori 
 
20 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori 
• Proposto por R. Agrawal e R. Srikant, em 1994. 
 
– Objetiva encontrar itemsets frequentes para descobrir regras de 
associação. 
– Usa conhecimento apriori referente a propriedades de itemsets 
frequentes. 
– Implementa uma abordagem iterativa. 
21 
Resumo... 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori 
• Resumo: 
– k-itemsets são usados para analisar (k+1)-itemsets 
• O conjunto de 1-itemsets e o seu suporte são encontrados 
em uma análise do banco de dados de transações. 
• Mantém-se aqueles itemsets que satisfazem o sup-min, no 
conjunto denominado L1. 
• L1 é usado para encontrar L2, e assim por diante, até que 
não seja possível encontrar mais k-itemsets. 
• A composição de cada Lk exige uma análise completa do 
banco de dados de transações. 
 
22 
Melhora de eficiência 
Propriedade Apriori 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Propriedade Apriori 
• Propriedade Apriori 
 
Todos os subconjuntos não vazios de um itemset 
frequente deve também ser frequente. 
 
• Analise: 
– Se um itemset l não satisfaz o limite mínimo para o suporte, min-
sup, então I não é frequente; 
– Se um item A é adicionado ao itemset I, então o itemset 
resultante (I U A) não pode ocorrer mais frequentemente do que 
I. 
23 
(Han & Kamber, 2006) 
É uma propriedade de 
antimonotonicidade! 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori: ilustrando 
24 
• Etapa 1: 
 
C1(s=1) C1(k=1) L1 
http://www.icmc.usp.br/~biblio/BIBLIOTECA/rel_tec/RT_308.pdf 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori: ilustrando 
• Etapa 2: 
 
25 
C2(k=2) 
C2(s=2) 
L2 
http://www.icmc.usp.br/~biblio/BIBLIOTECA/rel_tec/RT_308.pdf 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori: ilustrando 
• Etapa 3: 
 
 
 
 
• Etapa 4: 
 
26 
C3(k=3) L3 
Conjunto Resposta L – 
união dos Lks 
http://www.icmc.usp.br/~biblio/BIBLIOTECA/rel_tec/RT_308.pdf 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori: algoritmo 
27 
Algoritmo Apriori: encontrar itemsets frequentes usando uma abordagem 
level-wise iterativa baseada em geração candidata. 
(Han & Kamber, 2006, p. 239) 
 
Input: 
 D, uma base de dados de transações 
 min-sup, limite mínimo para o suporte de itemsets 
 
Output: 
 L, itemsets frequentes em D 
 
 
 corpo principal 
 procedure apriori_gen 
 procedure has_infrequent_subset 
Próximos slides !! 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori: corpo principal 
28 
(1) L1 = find_frequent_1-itemset(D); 
(2) for (k = 2; Lk-1 = {}, k++) { 
(3) Ck = apriori_gen(Lk-1); 
(4) for each transaction t ϵ D {// scan D for counts 
(5) Ct = subset(Ck,t);// get the subsets of t that are candidates 
(6) for each candidate c ϵ Ct 
(7) c.count++; 
(8) } 
(9) Lk = {c ϵ Ck | c.count ≥ min_sup} 
(10) } 
(11) return L = kLk; 
(Han & Kamber,2006) 
Encontra os 1-itemsets frequentes. 
Gera Ck candidatos para 
encontrar o Lk para k>1. 
Conjunto de itemsets frequentes. 

Função subset: encontra todos os subconjuntos de 
transações que são candidatas. E para cada 
subconjunto, o suporte é calculado (count ++). 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori: apriori_gen 
procedure apriori_gen (Lk-1:frequent (k-1)-itemsets) 
(1) for each itemset l1 ϵ Lk-1 
(2) for each itemset l2 ϵ Lk-1 
(3) if (l1[1] = l2[1]) ᴧ (l1[2] = l2[2]) ᴧ ... ᴧ 
 (l1[k-2] = l2[k-2]) ᴧ (l1[k-1] = l2[k-1]) 
 then { 
(4) c = l1 |X| l2; // join step: generate candidates 
(5) if has_infrequente_subset(c,Lk-1) then 
(6) delete c; // prune step: remove unfruitiful candidate 
(7) else add c to Ck; 
(8) } 
(9) return Ck; 
29 
(Han & Kamber, 2006) 
Gera os candidatos e então usa a propriedade Apriori para 
eliminar aqueles que tem um subconjunto que não é frequente. 
Aplicação da Propriedade Apriori. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori: has_infrequent_subset 
procedure has_infrequent_subset (c:candidate k-itemset; 
 Lk-1: frequent (k-1)-itemsets); // use prior knowledge 
(1) for each (k-1)-subset s of c 
(2) if s ¬ϵ lk-1 then 
(3) return TRUE; 
(4) return FALSE; 
30 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Assumindo o conjunto de itemsets frequentes encontrados nas transações 
de um banco de dados D, é possível gerar regras de associações fortes. 
31 
Que satisfazem sup_min e conf_min 
)(etorte_itemssup
)(etorte_itemssup
)|()(confiança
A
BA
ABPBA


(Han & Kamber, 2006) 
• Para cada itemset l, gerar todos os subconjuntos não vazios de l. 
 
• Para todo subconjunto não vazio s de l, retorne a regra “s  (l-s)” se 
 
 
min_conf
emset(s)suporte_it
emset(l)suporte_it

Como os itemsets são frequentes, as regras 
geradas, automaticamente, atendem ao 
sup_min. 
>= 2 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Apriori: ilustrando 
32 
camiseta  tênis 
 
50 / 50 = 1 (todas as vezes que camiseta foi 
 vendida, tênis também foi vendido) 
 
 
tênis  camiseta 
 
 
50 / 75 = 0,66 ( em 66% das compras nas quais 
 tênis foi vendido, camiseta também 
 foi vendida) 
 
 
 
 
 
 
http://www.icmc.usp.br/~biblio/BIBLIOTECA/rel_tec/RT_308.pdf 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Regras de Associação Multinível 
 
Para muitas aplicações, é difícil encontrar associações fortes entre itens de 
dados de baixos níveis de abstração, ou primitivos, devido a esparsidade 
dos dados nestes níveis. Associações fortes descobertas em altos níveis 
de abstração podem representar conhecimento de senso comum (Han & 
Kamber, 2006). 
 
• As regras são mineradas usando hierarquias de conceito, sob uma 
estrutura de suporte-confiança. 
– Estratégia top-down 
– Suportes são acumulados 
• Calculados a partir dos itemsets frequentes em a cada nível de 
conceito. 
• Em cada nível, o Apriori ou outro algoritmo de mesmo propósito, 
pode ser usado. 
 
 
33 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Regras de Associação Multinível (exemplos) 
34 
(Han & Kamber, 2006) 
Exemplo de Hierarquia de Conceitos 
All 
Laptop 
Microsoft Dell IBM 
Antivirus Office Desktop Printer Mouse Wrist pad Dig.Camera 
Computer Computer Accessory Printer & Camera Software 
Fellowes Canon HP LogiTech 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Regras de Associação Multinível (exemplos) 
35 
(Han & Kamber, 2006) 
Computer [support = 10%] 
Laptop computer [support = 6%] Desktop Computer [support = 4%] 
Nível 1 
Nível 2 
Nível 1 
min_sup = 5% 
Nível 2 
min_sup = 3% 
Nível 1 
min_sup = 5% 
Nível 2 
min_sup = 5% 
Abordagem de suporte 
uniforme 
Abordagem de suporte 
reduzido 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Regras de Associação Multinível (exemplos) 
 
buys(X,”laptop computer”)  buys(X,”HP printer”) 
[suporte = 8%, confiança = 70%] 
 
buys(X,”IBM laptop computer”)  buys(X,”HP printer”) 
[suporte = 2%, confiança = 72%] 
 
• Problema: uma regra pode ser considerada redundante se seu suporte e confiança 
estão próximos de seus valores “esperados”, baseado-se no ancestral da regra. 
 
 
 
 
 
36 
(Han & Kamber, 2006) 
1 
2 
Suponha que a regra 1 tenha 70% de confiança e 8% de suporte, e que cerca de um 
quarto (¼) de todas as vendas de “laptop computer” são de “IBM laptop computer”. 
É esperado que a regra 2 tenha uma confiança de cerca de 70% (já que todos os itens 
“IBM laptop computer” são também “laptop computer”) e um suporte de cerca de 2% 
(isto é, 8% * ¼). 
Se esse é realmente o caso, então a regra 2 não é interessante porque ela não traz 
informações adicionais e é menos genérica que a regra 1. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Minerando em um Banco de Dados Relacional ou em um Datawarehouse 
– Além de manter a informação sobre quais produtos foram comprados, um 
banco de dados relacional ou o datawarehouse também mantém informações 
associadas a estes itens: quantidade comprada e/ou preço, idade e/ou 
ocupação do comprador, data e/ou hora da compra, compras anteriores, etc. 
 
 age (X,”20 ... 29”) AND occupation(X,”student”)  buys(X, “laptop”) 
37 
(Han & Kamber, 2006) 
Regra multidimensional - INTERDIMENSIONAL 
Regra multidimensional – HÍBRIDA-DIMENSIONAL 
 age (X,”20 ... 29”) AND buys(X, “laptop”)  buys(X, “HP printer”) 
Os algoritmos são baseados em Predicados, ao 
invés de Itemsets! 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Como nós podemos dizer quais regras de associação fortes são realmente 
interessantes? (Han & Kamber, 2006, pg 260) 
 
• Exemplo (Han & Kamber, 2006, pg 260) : 
– De 10.000 transações analisadas, 6.000 incluem venda de jogos de computador, 7.500 
incluem venda de videos, e 4.000 incluem ambos. 
– Minerando regras de associação com sup_min = 30% e conf_min = 60%, a seguinte regra é 
descoberta. 
 
 
 
– A regra é, de certa forma, ilusória, porque a probabilidade de comprar vídeos é de 75%, a 
qual é bem maior do que 66%. 
– Jogos de computadores e videos estão negativamente associados porque a compra de um 
“inibe” a compra do outro. 
38 
(Han & Kamber, 2006) 
buys(X, “computer games”)  buys(X, “videos”) [suporte = 40% , confiança 66%] 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Análise de Correlação 
 
A  B [suporte, confiança, correlação] 
 
• Lift (medida de correlação) 
– A ocorrência de um itemset A é independente da ocorrência do itemset B se P(A B) = 
P(A)P(B); caso contrário, os itemsets A e B são dependentes e correlacionados, enquanto 
eventos. 
– A medida é dada por 
 
 
 
– Se o valor resultante para amedida é menor do que 1, então a ocorrência de A está 
negativamente correlacionada com a ocorrência de B. 
– Se o valor resultante para a medida é maior do que 1, então A e B estão positivamente 
correlacionados, significando que a ocorrência de um implica na ocorrência do outro. 
– Se o resultado é igual a 1, então A e B são independentes e não há correlação entre eles. 
39 
(Han & Kamber, 2006) 

.
)()(
)(
),(
BPAP
BAP
BAlift


L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras de Associação 
• Análise de Correlação – exemplo (Han & Kamber, 2006, pg. 261) 
 
– Seja NOT-GAME referente às transações que não contem “computer games”, e 
NOT-VIDEO referente às transações que não contém “videos”. 
– Se a probabilidade de comprar: 
• Um jogo de computador: P({game}) = 0,60 
• Um vídeo: P({video}) = 0,75 
• Ambos: P({game, video}) = 0,40 
– Pela medida de correlação (Lift) 
• O lift da regra do slide anterior é P({game, video}) / P({game}) * P({video}) = 0,40 / (0,60 * 0,75) = 0,89. 
– Como o valor é menor do que 1, então existe uma correlação negativa entre a 
ocorrência de {game} e {video} 
 
40 
(Han & Kamber, 2006) 
Outras medidas de correlação poderiam 
ser usadas. Veja (Han & Kamber, 2006). 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
WEKA 
41 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Sobre o WEKA 
• Weka (Waikato Environment for Knowledge Analysis)é uma coleção de algoritmos 
de aprendizado de máquina que podem ser usados na implementação de tarefas de 
mineração de dados. 
• Possui uma interface que permite que os algoritmos seja executados diretamente 
sobre o conjunto de dados, ou que eles sejam chamados a partir de algum código 
Java. 
• Dentre as funcionalidades que podem ser realizadas nestes software, incluem-se: 
– Pré processamento de dados / Classificação / Regressão / Agrupamento / Regras de Associação / 
Visualização 
• Weka encontra-se em sua versão 3, e também permite que novos algoritmos sejam 
implementados a partir dos recursos que oferece. 
• E um software de código aberto, publicado sob a 
licença GNU General Public License 
(http://www.gnu.org/copyleft/gpl.html). 
 
• Trata-se de uma iniciativa da Universidade de 
Waikato, Nova Zelândia. 
 
• Homepage: http://www.cs.waikato.ac.nz/ml/weka/ 
 
42 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Sobre o WEKA 
• Os algoritmos implementados no WEKA esperam um 
formato padrão para os conjuntos de dados que serão 
explorados. 
• Trata-se do formato ARFF. 
• É uma forma de representar dados que contém 
instâncias de dados não ordenadas, independentes e 
não envolve relacionamento entre elas. 
 
 
43 
Exemplo 
(Witten & Frank, 2005) 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
% ARFF file for weather data with some numeric features 
% 
@relation weather 
 
@attribute outlook { sunny, overcast, rainy } 
@attribute temperature numeric 
@attribute humidity numeric 
@attribute windy { true, false } 
@attribute play? { yes, no } 
 
@data 
% 
% 14 instances 
% 
sunny, 85, 85, false, no 
sunny, 80, 90, true, no 
overcast, 83, 86, false, yes 
rainy, 70, 96, false, yes 
rainy, 68, 80, false, yes 
rainy, 65, 70, true, no 
overcast, 64, 65, true, yes 
sunny, 72, 95, false, no 
sunny, 69, 70, true, no 
rainy, 75, 80, false, yes 
sunny, 75, 70, true, yes 
overcast, 72, 90, true, yes 
overcast, 81, 75, false, yes 
rainy, 71, 91, true, no 44 
comentário 
atributo nominal e os valores 
possíveis que os instanciam 
nome da relação 
bloco de definição 
de atributos 
atributo de classe 
início das instâncias 
instâncias são escritas uma por linha, com 
valores para cada atributo separados por 
vírgula 
valores perdidos são representados por “?” 
Também admite atributos do tipo: 
string: @attribute description string 
date: @attribute today date 
 
Formato para data/hora: yyyy-MM-ddTHH:mm:ss 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Weka: criando o nosso .arff 
• Conjunto de dados: Congressional Voting Records Data Set 
• (Frank & Asuncion, 2010) 
– Origem: Congressional Quarterly Almanac, 98th Congress, 2nd session 1984, Volume XL: 
Congressional Quarterly Inc. Washington, D.C., 1985. 
– Doador: Jeff Schlimmer (Jeffrey.Schlimmer '@' a.gp.cs.cmu.edu) 
 
• This data set includes votes for each of the U.S. House of Representatives 
Congressmen on the 16 key votes identified by the CQA. The CQA lists nine different 
types of votes: voted for, paired for, and announced for (these three simplified to 
yea), voted against, paired against, and announced against (these three simplified to 
nay), voted present, voted present to avoid conflict of interest, and did not vote or 
otherwise make a position known (these three simplified to an unknown disposition). 
 
45 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
46 
% 1984 United States Congressional Voting Records Database 
% 
@relation voting 
 
@attribute handicapped-infants {y,n} 
@attribute water-project-cost-sharing {y,n} 
@attribute adoption-of-the-budget-resolution {y,n} 
@attribute physician-fee-freeze {y,n} 
@attribute el-salvador-aid {y,n} 
@attribute religious-groups-in-schools {y,n} 
@attribute anti-satellite-test-ban {y,n} 
@attribute aid-to-nicaraguan-contras {y,n} 
@attribute mx-missile {y,n} 
@attribute immigration {y,n} 
@attribute synfuels-corporation-cutback {y,n} 
@attribute education-spending {y,n} 
@attribute superfund-right-to-sue {y,n} 
@attribute crime {y,n} 
@attribute duty-free-exports {y,n} 
@attribute export-administration-act-south-africa {y,n} 
@attribute class? {democrat, republican} 
 
@data 
% 
% 435 instances 
% 
 
n,y,n,y,y,y,n,n,n,y,?,y,y,y,n,y,republican 
n,y,n,y,y,y,n,n,n,n,n,y,y,y,n,?,republican 
?,y,y,?,y,y,n,n,n,n,y,n,y,y,n,n,democrat 
n,y,y,n,?,y,n,n,n,n,y,n,y,n,n,y,democrat 
y,y,y,n,y,y,n,n,n,n,y,?,y,y,y,y,democrat 
n,y,y,n,y,y,n,n,n,n,n,n,y,y,y,y,democrat 
n,y,n,y,y,y,n,n,n,n,n,n,?,y,y,y,democrat 
n,y,n,y,y,y,n,n,n,n,n,n,y,y,?,y,republican 
n,y,n,y,y,y,n,n,n,n,n,y,y,y,n,y,republican 
 
... continua .... 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Sobre o WEKA 
• Usos do WEKA (Witten & Frank, 2005) 
– Aplicação de um método de aprendizado em um conjunto de 
dados e analisar as saídas produzidas para aprender mais 
sobre os dados; 
– Criação de modelos para gerar predições de novas instâncias 
(de dados); 
– Aplicação de vários e diferentes métodos de aprendizado e 
comparação de seus desempenhos a fim de escolher um deles 
para a realização da tarefa. 
 
47 
• O Weka ainda fornece: 
• um módulo de avaliação comum para 
medir o desempenho dos algoritmos; 
• Ferramentas de pré-processamento, 
chamadas filtros. 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Weka 
48 
Primeiras opções: acesso à interfaces gráficas, 
visualizadores e informações sobre a ferramenta. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Sobre o WEKA 
• Possui interfaces gráficas 
– Explorer: fornece acesso a todas as funcionalidades doWEKA 
por meio de menus. 
– Knowledge Flow: permite projetar configurações para 
processamento de dados streamed, ideal para processar 
grandes conjuntos de dados e usar, de maneira combinada, 
diversas funcionalidades do WEKA. 
– Experimenter: facilita a experimentação de vários métodos 
diferentes, usando um corpus de conjuntos de dados, coletando 
informações estatísticas e executando diferentes tipos de testes. 
 
49 
Uso via linha de comando também 
está disponível. 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Weka: explorer 
50 
Carregando o arquivo 
com os dados a serem 
analisados ... 
Tela inicial do Explorer: 
6 abas com as tarefas que 
podemos executar (pre-
processamento, classificação, 
agrupamento, associação, seleção 
de atributos e visualização. 
Neste ponto apenas o pré-
processamento está 
disponível. É preciso 
carregar um arquivo .arff (a 
partir de um arquivo, URL, 
banco de dados) ou gerar 
um arquivo de dados. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Weka: explorer 
51 
Para editar do arquivo de dados 
Para salvar a nova versão do 
arquivo de dados 
 
Informações sobre o atributo selecionado: quantos valores 
perdidos, quantos valores distintos, tipo dos valores, se 
existem valores únicos, quantos valores de cada tipo, e um 
histograma (veja próximo slide). 
Filtros que podem ser 
aplicados sobre os dados. 
Depois do pré-
processamento, 
as tarefas de 
análise de dados 
podem ser 
executadas. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
52 
Frequência de ocorrência cada um dos valores de 
classe (republicano - vermelho / democrata - azul) para 
cada um dos valores de cada atributo. 
Para ver o histograma relacionado todos os 
Atributos ao atributo escolhido na lista! 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
53 
Weka: explorer 
Clique para alterar os parâmetros. 
Possibilidades de 
algoritmos! 
Parâmetros para o Apriori! 
Clique em “More” para obter informações 
sobre cada parâmetro. 
 
Open: abre um arquivo de configurações 
Save: salva um arquivo de configurações 
Executa o algoritmo. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
54 
Weka: explorer 
=== Run information === 
 
Scheme: weka.associations.Apriori -N 10 -T 0 -C 0.9 -D 0.05 -U 1.0 -M 0.1 -S -1.0 -c -1 
Relation: voting 
Instances: 435 
Attributes: 17 
 handicapped-infants 
 water-project-cost-sharing 
 adoption-of-the-budget-resolution 
 physician-fee-freeze 
 el-salvador-aid 
 religious-groups-in-schools 
 anti-satellite-test-ban 
 aid-to-nicaraguan-contras 
 mx-missile 
 immigration 
 synfuels-corporation-cutback 
 education-spending 
 superfund-right-to-sue 
 crime 
 duty-free-exports 
 export-administration-act-south-africa 
 class? 
 
=== Associator model (full training set) === 
 
Resultado usando os 
parâmetros default. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
55 
Apriori 
======= 
 
Minimum support: 0.45 (196 instances) 
Minimum metric <confidence>: 0.9 
Number of cycles performed: 11 
 
Generated sets of large itemsets: 
 
Size of set of large itemsets L(1): 20 
 
Size of set of large itemsets L(2): 17 
 
Size of set of large itemsets L(3): 6 
 
Size of set of large itemsets L(4): 1 
 
 
 
Resultado usando os 
parâmetros default. 
Weka: explorer 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Melhores regras encontradas (10 + 1). 
 
 1. aprovação de orçamento = sim, congelamento de taxa médica = não 219 
 ==> classe = democrata 219 conf:(1) 
 
 2. aprovação de orçamento = sim, congelamento de taxa médica = não, auxílio aos “contras” Nicarágua= sim 198 
 ==> classe = democrata 198 conf:(1) 
 
 3. congelamento de taxa médica = não, auxílio aos “contras” Nicarágua= sim 211 
 ==> classe = democrata 210 conf:(1) 
 
 4. congelamento de taxa médica = não, gastos com educação = não 202 
 ==> classe = democrata 201 conf:(1) 
 
 5. congelamento de taxa médica = não 247 ==> classe = democrata 245 conf:(0.99) 
 
 6. auxílio para El Salvador = não, classe = democrata 200 ==> auxílio aos “contras” Nicarágua= sim 197 conf:(0.99) 
 
 7. auxílio para El Salvador = não 208 ==> auxílio aos “contras” Nicarágua= sim 204 conf:(0.98) 
 
 8. aprovação de orçamento = sim, auxílio aos “contras” Nicarágua= sim, classe = democrata 203 
 ==> congelamento de taxa médica = não 198 conf:(0.98) 
 
 9. auxílio para El Salvador = não, auxílio aos “contras” Nicarágua= sim 204 ==> classe = democrata 197 conf:(0.97) 
 
10. auxílio aos “contras” Nicarágua, classe = democrata 218 ==> congelamento de taxa médica = não 210 conf:(0.96) 
 
… 
 
20. auxílio para El Salvador = sim 212 ==> grupos religiosos nas escolas = sim 197 conf:(0.93) 
 
Weka: explorer 
Resultado usando os 
parâmetros default. 
Traduzido! 
Alterando um dos parâmetros – número de regras = 20. 
56 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
A tarefa de Classificação 
57 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
O Problema de Classificação 
(Definição Informal) 
• Dada uma coleção de dados 
detalhados, neste caso 5 
exemplos de Esperança e 5 de 
Gafanhoto, decida a qual tipos de 
inseto o exemplo não rotulado 
pertence. 
• Obs: Esperança: Tipo de 
gafanhoto verde 
 
 
 
• Esperança ou ganfanhoto? 
 
 
58 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Para qualquer domínio de interesse podemos medir 
características 
59 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Coleção de dados 
60 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Visualização gráfica 
61 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Visualização Gráfica 
62 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Joguinho 
63 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Joguinho dos pombos 
64 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Joguinho dos pombos 
65 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Joguinho dos pombos 
66 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Joguinho dos pombos 
67 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Joguinho dos Pombos 
68 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Joguinho dos pombos 
69 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Joguinho dos pombos 
70 
L
im
a
, 
C
. 
A
. 
M
.&
 P
e
re
s
, 
S
. 
M
. 
Regras - Joguinho dos pombos 
71 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras – Joguinho dos pombos 
72 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Regras – Joguinho dos pombos 
73 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Problema Inicial 
74 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Gafanhoto ou Esperança 
75 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Discriminante de Fisher 
76 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Espaço de alta dimensão 
77 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Espaço de alta dimensão 
78 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Espaço de alta dimensão 
79 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Redução da dimensionalidade 
80 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Problema do Pombo 
81 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Classificador 
• Um exemplo pode ser representado pelo 
par: (x, y) = (x, f(x)) 
• Onde 
– x é a entrada; 
– f(x) é a saída (f desconhecida!) 
– Indução ou inferência indutiva: dada uma 
coleção de exemplos de f, retornar uma 
função h que aproxima f 
– h é denominada uma hipótese sobre f 
 82 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Exemplos de Hipóteses 
• (a) dados originais 
• (b), (c), (d) possíveis hipóteses 
 
83 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Representação da Classificação 
84 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
85 
Vetor de atributos ou características 
• O que é um vetor de atributos ou características “bom” 
para uma tarefa de classificação? 
– A qualidade do vetor de atributos ou características está relacionada com 
sua habilidade de discriminar exemplos de diferentes classes 
• Exemplos da mesma classe deveriam ter valores de atributos ou características 
similares 
• Exemplos de classes diferentes deveriam ter valores de atributos ou 
características diferentes 
 
 
 
 
 
Atributos ou Características 
boas 
Atributos ou Características 
ruins 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
86 
Tipos de Problemas de Classificação 
Linearmente separável Não-Linearmente separável 
Características altamente 
correlacionadas 
Multimodal 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Treinamento e Teste 
• O desempenho de um classificador pode ser medido por 
meio da taxa de erro: 
– A taxa de erro de erro é a proporção de erros obtidos sobre um 
conjunto completo de instancias. 
 
 
 
 
 
 
– O que interessa é o desempenho do classificador mediante 
“novos” dados, e não sobre os dados velhos (usados no 
processo de treinamento). 
 
87 
O classificador prediz a classe de cada instância; se 
ela é correta, é contada como um “sucesso”; se não, 
é contada como um “erro”. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Treinamento, validação e teste 
• Frequentemente é útil dividir o conjunto de dados disponíveis em 
três partes, para três diferentes propósitos: 
– Conjunto de treinamento: usado por um ou mais métodos de 
aprendizado para construir o classificador. 
– Conjunto de validação: usado para otimizar os parâmetros do 
classificador, ou para selecionar um em particular. 
– Conjunto de teste: usado para clacular a taxa de erro final do modelo já 
otimizado. 
88 
Uma vez que a taxa de erro foi determinada, os dados de testes podem 
se juntar aos dados de treinamento para produzir um novo classificador 
para o uso real. Não há problema nisso quando usado apenas como uma 
forma de maximizar o classificador que será usado na prática. O que é 
importante é que a taxa de erro não seja calculada com base nesse último 
classificador gerado. Além disso, o mesmo pode ser feito com os dados 
de validação. (Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Análise de desempenho 
89 
Meu classificador apresentou 25% de taxa de erro (75% de taxa de 
acerto). Mas o que isso realmente significa? Quanto posso confiar 
nesta medida? 
É util determinar a taxa de sucesso com relação a um intervalo de 
confiança. 
 
Seja S a contagens de respostas corretas obtidas nos testes do 
classificador e N o número de testes realizados, então: 
 
• Se S = 750 e N = 1000, a taxa de sucesso é por volta de 75%. Se 
considerarmos 80% de confiança na medida, a taxa de sucesso fica entre 
73.2% e 76.7%. 
 
•Se S = 75 e N = 100, a taxa de sucesso é por volta de 75%. Se 
considerarmos 80% de confiança na medida, a taxa de sucesso fica entre 
69.1% e 80.1%. 
?  
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Processo de Bernoulli 
• Sucessão de eventos independentes que ou obtém sucesso ou falham. 
 
• A média e variância de uma única tentativa Bernoulli com taxa de sucesso 
p é p e p(1-p), respectivamente. Se N tentativas são executadas, a taxa de 
sucesso esperada f = S/N é uma variável randômica com a mesma média 
p; a variância é reduzida pelo fator N para p(1-p)/N. Para grandes N, a 
distribuição desta variável randômica aproxima uma distribuição normal. 
 
• A probabilidade de uma variável randômica X, com média 0, ficar entre um 
certo intervalo de confiança de largura 2z é Pr[ -z <= X <= z] = c. 
 
• Para uma distribuição normal, valores de c e z são dados em tabelas (a 
derivação de tais tabelas não está discutida aqui) apresentadas na 
literatura da área de Estatística. 
90 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
• Pr [ X >= z ] = 5% implica que existe 5% de chance que X estar em mais de 1.65 de 
desvio padrão acima da média. Como a distribuição normal é simétrica, a chance de 
X estar em mais do que 1.65 de desvio padrão da média (acima ou abaixo) é de 
10%, ou Pr [ -1.65 <= X <= 1.65 ] = 90%. 
 
• Então é necessário reduzir a variável f para ter média zero e variância 1, e Pr [ -z < 
(f-p)/ sqrt(p(1-p)/N)) < z ] = c. 
 
• Para usar a tabela é necessário subtrair c de 1 e então verificar o resultado, tal que 
para c = 90% deve-se usar a entrada de 5% da tabela. 
91 
Processo de Bernoulli 
(Witten & Frank, 2005) 
Limites de confiança para a distribuição normal 
Pr [ X >= z ] z 
0.1% 3.09 
0.5% 2.58 
1% 2.33 
5% 1.65 
10% 1.28 
20% 0.84 
40% 0.25 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
• Para encontrar p: 
 
 
 
• O +/- na expressão indica os dois valores para p que 
representam os limites superior e inferior de confiança. 
 
92 
Processo de Bernoulli 
(Witten & Frank, 2005) 















N
z
N
z
N
f
N
f
z
N
z
fp
2
2
222
1/
42
A asserção da distribuição normal é 
válida somente para grandes N (por 
exemplo, N > 100). 
Lim
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Matriz de Confusão 
• Oferece uma medida da eficácia do modelo de 
classificação,mostrando o número de classificações corretas versus 
o número de classificação prevista para cada classe. 
 
 
 
93 
Classe C1 Prevista C2 Prevista  Ck Prevista 
C1 Real M(C1,C1) M(C1,C2)  M(C1,Ck) 
C2 Real M(C2,C1) M(C2,C2)  M(C2,Ck) 
     
Ck Real M(Ck,C1) M(Ck,C2)  M(Ck,Ck) 



}:),({
)(),(
iCyTyx
jji CxhCCM
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Matriz de Confusão para duas classes 
94 
TP = True Positive (verdadeiro positivo) 
FN = False Negative(falso negativo) 
FP = False Positive (falso positivo) 
TN = True Negative (verdadeiro negativo) 
n = (TP+FN+FP+TN) 
Classe prevista C+ prevista C- Taxa de erro 
da classe 
Taxa de erro 
total 
real C+ Tp Fn Fn / (Tp + Fn) 
(Fp + Fn) / n 
real C- Fp Tn Fp/ (Fp + Tn) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Matriz de Confusão para duas classes 
• Outras métricas derivadas da tabela anterior: 
 
95 
C+ Predictive Value = Tp / (Tp + Fp) 
C- Predictive Value = Tn / (Tn + Fn) 
True C+ Rate ou Sesitivity y ou Recall = Tp / (Tp + Fn) 
True C- Rate ou Specifity = Tn / (Fp + Tn) 
Precision = (Tp + Tn) / n 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Credibilidade: avaliando o que foi aprendido 
• É possível avaliar como diferentes métodos de 
mineração de dados trabalham e é possível compará-
los. 
• É preciso implementar uma forma de predizer os limites 
de desempenho de um método, baseado em 
experimentos com os dados que estão disponíveis. 
– Quando está disponível um grande conjunto de dados a 
avaliação pode se basear em um grande conjunto de 
treinamento e um grande conjunto de teste. 
– Caso contrário, é preciso trabalhar um pouco mais. 
 
96 
(Witten & Frank, 2005) 
É um trabalho cheio de 
controvérsias e discordâncias!!! 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Diferentes formas de avaliação 
• Para problemas de classificação, pode-se medir o desempenho de 
um classificador com base na taxa de erro. 
• Regras de associação são avaliadas com base em medidas de 
suporte e confiança. 
• Tarefas de predição podem ser avaliadas por medidas tais como: 
erro quadrático médio, coeficiente de correlação, etc. 
• O princípio MDL (minimun description length) pode ser usado para 
avaliar tarefas de agrupamento. 
97 
Veja mais à frente, nestes slides, 
como tais medidas são 
aplicadas! 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Avaliação do classificador 
• Para estimar o erro verdadeiro de um classificador, a 
amostra para teste deve ser aleatoriamente escolhida 
 
• Amostras não devem ser pré-selecionadas de nenhuma 
maneira 
 
• Para problemas reais, tem-se uma amostra de uma 
única população, de tamanho n, e a tarefa é estimar o 
erro verdadeiro para essa população 
 
98 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Métodos para estimar o erro 
verdadeiro de um classificador 
– Resubstitution 
– Random 
– Holdout 
– r-fold cross-validation 
– r-fold stratified cross-validation 
– Leave-one-out 
– Bootstrap 
 
99 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Resubstitution 
• Gera o classificador e testa a sua performance 
com o mesmo conjunto de dados 
 
• Os desempenhos computados com este método 
são otimistas e tem grande bias 
 
• Desde que o bias da resubstitution foi 
descoberto, os métodos de cross-validation são 
usados 
100 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Holdout 
• Estratégia para teste de classificador que reserva um certo montante de 
dados para treino e o restante para teste (podendo ainda usar parte para 
validação). 
 
• Comumente esta estratégia uma 1/3 dos dados dados para teste e o 
restante para treinamento, escolhido randomicamente. 
 
• É interessante assegurar que a amostragem randômica seja feita de tal 
maneira que garanta que cada classe é apropriadamente representada 
tanto no conjunto de treinamento quanto no conjunto de teste. Este 
procedimento é chamado de estratificação (holdout estratificado). 
 
• Também é útil, para amenizar tendências, repetir todo o processo de treino 
e teste várias vezes com diferentes amostragens randômicas (holdout 
repetitivo/iterativo). 
101 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Random 
• I classificadores, I<<n, são induzidos de cada 
conjunto de treinamento 
 
• O erro é a média dos erros dos classificadores 
medidos por conjuntos de treinamentos gerados 
aleatória e independentemente 
 
• Pode produzir estimativas melhores que o 
holdout 
 
102 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Cross Validation 
• Trata-se de uma estratégia para lidar com um montante de dados 
limitado. 
 
• Nesta estratégia decide-se um numero fixos de folds, ou partições 
dos dados. Supondo que sejam usados três folds (3-fold cross 
validation): 
– o conjunto de dado é dividido em três partições de tamanhos aproximadamente 
iguais e, de maneira rotativa, cada uma delas é usada para teste enquanto as 
duas restantes são usadas para treinamento. 
– ou seja: use 2/3 para treinamento e 1/3 para teste e repita o processo três 
vezes, tal que, no fim, cada instância tenha sido usadas exatamente uma vez 
para teste. 
– se a estratificação é adotada, então o procedimento se chama 3-fold cross 
validation estratificado (aconselhável). 
– o padrão é executar o 10-fold cross validation, 10 vezes. 
– o erro final do classificador é a média dos erros obtidos em cada iteração da 
estratégia cross-validation 
103 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Leave-one-out 
• Leave-one-out cross-validation é um n-fold cross-validation, onde n é o 
número de instâncias no conjunto de dados. 
• A avaliação é sobre a corretude de classificação da instância em teste – um 
ou zero para sucesso ou falha, respectivamente. 
• Os resultados de todas as n avaliações, uma para cada instância do 
conjunto de dados, são analisados via média, e tal média representa o erro 
final estimado. 
 
• Motivações: 
– o maior número possível de dados é usado para treinamento em cada caso, o 
que aumenta as chance do classificador alcançar acuidade. 
– o procedimento é determinístico. 
 
• Indicado para conjunto de dados pequenos. 
• Não é possível aplicar qualquer procedimento de estratificação. 
104 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Boostrap 
• Baseado em um procedimento estatístico de amostragem com 
reposição. 
• Uma instância não é retirada do conjunto de dados original quando 
ela é escolhida para compor o conjunto de treinamento. 
– Ou seja, a mesma instância pode ser selecionada várias vezes durante 
o procedimento de amostragem. 
• As instâncias do conjunto original que não foram escolhidas para 
compor o conjunto de treinamento, comporão o conjunto de teste. 
 
• O 0,632 bootstrap: 
– a probabilidade de uma instância ser escolhida é 1/n. E de não ser escolhida é 
de 1-(1/n). Multiplicando essasprobabilidades de acordo com o número de 
oportunidades de escolha (n), tem-se (1 – (1/n))n ~ e-1 = 0,368 como a 
probabilidade de uma instância não ser escolhida. 
– assim, para um conjunto de dados grande, o conjunto de testes conterá 36,8% 
de instâncias e o conjunto de treinamento, 63,2% delas. 
 
 
 
105 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Boostrap 
• A medida de erro obtida é uma estimativa pessimista do erro verdadeiro 
porque o conjunto de treinamento, embora tenha tamanho n, contém 
somente 63% das instâncias, o que não é grande coisa se comparado com 
os 90% usados no 10-fold cross-validation. 
• Para compesar isso, pode-se combinar o erro do conjunto de teste com o 
erro de resubstituição (estimativa otimista). 
 
• O boostrap combina da seguinte forma: 
– erro = 0,632 * erro de teste + 0.368 * erro de treinamento 
 
• O procedimento deve ser repetido várias vezes, e uma média de erro final 
deve ser encontrada. 
106 
(Witten & Frank, 2005) 
O bootstrap é o procedimento mais 
indicado para estimar erro para 
conjuntos de dados muito pequenos. 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Comparando métodos 
• Encontrar a taxa de erro para as técnicas comparadas e escolher aquela 
com a menor taxa é a forma mais simples de comparação e, pode ser 
adequada para problemas isolados. 
 
• Se um novo algoritmo é proposto, seus proponentes devem mostrar que 
ele melhora o estado da arte para o problema em estudo e demonstrar que 
a melhora observada não é apenas um efeito de sorte do processo de 
estimativa do erro. 
 
• O objetivo é determinar se um esquema é melhor ou pior do que o outro, 
em média, usando todas as possibilidades de conjuntos de treinamento e 
de teste que podem ser criados a partir do domínio. Todos os conjuntos de 
dados deveriam ser do mesmo tamanho e o experimento deveria ser 
executado várias vezes, com diferentes tamanhos, para obter uma curva de 
aprendizado. 
107 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
• t-test ou Student’s test 
– seja um conjunto de amostras x1, x2, ..., xk obtidas por sucessivos 10-
fold cross validation, usando um esquema de aprendizado (um dos 
métodos sob comparação), e um segundo conjunto de amostras y1, y2, 
..., yk obtidos de sucessivos10-fold cross validation usando o outro. 
– cada estimativa cross validation é gerada usando um conjunto de 
dados diferente (mas de mesmos tamanhos e do mesmo domínio). 
– melhores resultados serão obtidos se ambos os esquemas sob 
comparação usarem exatamente as mesmas partições dos dados para 
x1 e y1, x2 e y2, e assim por diante. 
– a média da primeira amostragem é x e a média da segunda é y. 
– a pergunta é: x é significativamente diferente de y ? 
108 
Comparando métodos 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
– se existem amostras suficientes, a media (x) de um conjunto de amostras 
independente (x1, x2, ..., xk) tem uma distribuição normal, independentemente da 
distribuição subjacente à amostra em si; o valor verdadeiro de média seria μ, e a 
variância poderia ser estimada e poder-se-ia reduzir a distribuição de x para média 
zero e variância 1. 
– mas k não é grande, k = 10. 
– tem-se uma Student’s distribution com k-1 graus de liberdade. 
– a tabela de intervalos de confiança da Student’s distribution deveria ser usada ao 
invés da tabela de intervalos de confiança da distribuição normal. 
– para o caso do 10-fold cross validation, tem-se o 9 graus de liberdade. 
109 
Comparando métodos 
(Witten & Frank, 2005) 
Limites de confiança para a Student’s distribution com 9 graus de liberdade 
Pr [ X >= z] z 
0.1% 4.30 
0.5% 3.25 
1% 2.82 
5% 1.83 
10% 1.38 
20% 0.88 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
– considera-se pois as diferenças di entre observações 
correspondentes, di = xi – yi. 
– a média das diferenças é a diferença entre as médias, d = x – y, 
e como as médias, as diferenças seguem a Student’s 
distribution com k-1 graus de liberdade. 
– se a média é a mesma, a diferença é zero (hipótese nula); se 
elas são significativamente diferentes, a diferença será 
significativamente diferente de zero. 
– assim, para um dado nível de confiança, checar-se-á se a 
diferença excede um limite de confiança. 
110 
Comparando métodos 
(Witten & Frank, 2005) 
como?? 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
• reduza a diferença para média-zero e variância unitária  variável 
t-statistc, aplicando 
t = d / sqrt(σ2d/k) 
• onde σ2d é a variância das diferenças. 
• decida o nível de confiança – geralmente 5% ou 1%. 
• a partir deste limite determine z usando a tabela anterior se k = 10; 
 
• Se o valor de t é maior do que z, ou menor do que –z, a hipótese 
nula deve ser rejeitada e conclui-se que há, realmente, uma 
diferença significativa entre os dois métodos sob comparação. 
111 
Comparando métodos 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Avaliação dos classificadores 
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Taxa de Falso Positivo
T
ax
a 
de
 V
er
da
de
iro
 P
os
iti
vo
E
A
C
D
B
• Gráfico ROC com cinco classificadores discretos. 
 
– A é dito um classificador “conservador”, B é o inverso de E, D é 
um classificador perfeito e C é dito aleatório. 
112 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Avaliação dos classificadores 
• Considere as seguintes saídas de um classificador: 
 
 
 
 
 
 
 
• -0,7: TP = 1 FP = 1 ponto (1 ; 1) 
• -0,6: TP = 1 FP = 0,5 ponto (0.5 ; 1) 
• 0,8: TP = 1 FP = 0 ponto (0 ; 1) 
• 0,9: TP = 0,66 FP = 0 ponto (0 ; 0,66) 
• 1,0: TP = 0,33 FP = 0 ponto (0 ; 0,33) 
z y L (-0.7) L(-0.6) L(0.8) L(0.9) L(1.0) L(>1.0) 
-0.7 -1 1 -1 -1 -1 -1 -1 
-0.6 -1 1 1 -1 -1 -1 -1 
0.8 1 1 1 1 -1 -1 -1 
0.9 1 1 1 1 1 -1 -1 
1.0 1 1 1 1 1 1 -1 
113 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Um método para classificação 
 
Máquinas Vetores Suporte 
 
SVM – Support Vector Machine 
114 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
115 
Máquinas de Vetores Suporte 
(SVM – Support Vector Machines) 
• Máquinas de Vetores Suporte 
– Usa espaço de hipótese de funções lineares no espaço de 
característica de alta dimensionalidade, treinadas com um 
algoritmo baseado na teoria de otimização que implementa a 
teoria de aprendizado estatístico. 
• Palavras chaves 
– Maquinas de aprendizado Linear 
– Funções kernel 
• Usado para definir o espaço de característica implícito, no 
qual a máquina de aprendizado linear opera. 
• Responsável pelo uso eficiente do espaço de característica 
de alta dimensionalidade. 
– Teoria de Otimização  Representação Compacta 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
116 
x
x
x
x
x
x
x
x
x
x
o
o
o
o
o
o
(x)

(x)
(x)
(x)
(x)
(x)(x)
(x) (x)
(x)
(o)
(o)
(o)(o)
(o)
(o)
Dimensão = m Dimensão = M >> m
x
x
x
x
x
x
x
x
x
x
o
o
o
o
o
o
(x)

(x)
(x)
(x)
(x)
(x)(x)
(x) (x)
(x)
(o)
(o)
(o)
(o)
(o)
(o)
Dimensão = m Dimensão = M >> m
Mudança de Paradigma 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
117 
SVM supera dois problemas 
• 1) Problema conceitual 
– Como controlar a complexidade do conjunto de aproximação. 
 
• Funções em alta dimensão a fim de proporcionar boa capacidade 
de generalização 
 
• Usar estimadores lineares penalizados com um grande número de 
funções-base 
 
• 2) Problema Computacional 
– Como realizar otimização numérica em espaço de alta 
dimensão 
 
• Usar uma representação kernel dual de funções lineares 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
118 
Há infinitas linhas que têm erro 
de treinamento zero 
Qual delas deveremos escolher? 
Classificadores lineares sobre problema 
linearmente separável 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
119 
 
– vetores Xi 
– rótulos yi = ±1 
 
Hiperplano de separação de 
margem ótima (Vapnik) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
120 
)(sign)( bf  XwX
w
1
1).( by ii Xw
w
w
:min
Hiperplano de separação de 
margem ótima (Vapnik) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
121 
)(sign by  Xw
1)(  by ii Xw
w
w
:min
Siby ii  ,1)( Xw



Si
iii y Xw 
 
– vetores Xi 
– rótulos yi = ±1 
 
 
 
 
 
– Vetores suporte: 
 
Vetores Suporte 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
122 
 
– vetores Xi 
– rótulos yi = ±1 
 
 
 
 
 
– Vetores suporte: 
 
)(sign)( bf  XwX
1)(  by ii Xw
w
w
:min
,b
Siby ii  ,1)( Xw



Si
iii y Xw 
)(sign)( byf
Si
iii  

XXX 
Máquina de Vetores Suporte (SVM) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
123 
 
– vetores Xi 
– rótulos yi = ±1 
 
 
– Vetores suporte: 
 
(vetores da margem 
e vetores de erro) 
 
)(sign by  Xw
Siby ii  ,1)( Xw



Si
iii y Xw 
)(sign)( byf
Si
iii  

XXX 
Hiperplano de separação com 
margem suave 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
124 
x
X
)(
)(
)(
xX
xX

 ii
),( K
),()()( xxxx ii K
))x,x(()x( bKysignf
Si
iii  

))()((sign)( byf
Si
iii  

xxX 
)()( xxXX  ii
Condição de Mercer 
)(sign)( byf
Si
iii  

XXX 
Kernels 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
125 
Tipo de Kernel 
i. Linear 
 
ii. Polinomial 
 
iii. Função Gaussiana de Base 
Radial 
 
 
iv. Função Exponencial Base 
Radial 
yxyxK ),(
dyxyxK )1(),( 







 

2
2
2
)(
exp),(

yx
yxK
v. Tangente 
 
vi. Séries de Fourier 
 
vii. Linear Splines 
 
 
 
viii. Bn-splines 
 







 

22
exp),(

yx
yxK
))(tanh(),( cyxbyxK 
 )(
))((
),(
2
1
2
1
yxsin
yxNsin
yxK



 
 3
2
),max(
3
1
),min(
2
)(
),min(1),(
yx
yx
yx
yxxyxyyxK



)(),( 12 yxByxK n  
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
126 
• Problema Primal 
 
 
 
• Sujeito a 
 



N
i
iFC
1
2
)(
2
1
),(  ww
   Niby iii ,,1,1  xw
Formulação do SVM para 
classificação 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
127 
 
Tipo de Perda 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
128 
• Problema dual 
 
 
• Sujeito a 
 
 
 
• Fórmula Usual em Otimização 
 
 

 

N
i
i
N
i
N
j
jijiji KyyW
11 1
),(
2
1
)(min  xx
NiCi ,,1,0 



N
i
ii y
1
0


TT cKW 
2
1
)(min
NiCi ,,1,0 
bA 
Formulação do SVM para classificação 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
129 
 
 
0
0
0
0
0
2
1
)(
4
3
2
1
432
4
1
1
4
1,
4321
















i
ii
ji
ijjiji
ysujeito
hyyL













9111
1911
1191
1119
K
 
 

n
i i
iiii yHyf
1
4
1
2* ]1).[()125.0(),()( xxxxx 
• Problema dual 
• Utilizando o kernel polinomial de ordem 2 
 
 
 
 
 
 
• Função 
 
 
 
1x
 
2x
 
y
 
 
Exemplo – Ou Exclusivo 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Spider 
130 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Instituto Max Planck 
131 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
132 
Simulação 
• [x,y] = spir(100); 
• Ip = find(y==1); 
• In = find(y==-1) 
• plot(x(Ip,1),x(Ip,2),'r*') 
• hold on 
• plot(x(In,1),x(In,2),'b*') 
• d=data(x,y) 
• ker=kernel('rbf',0.4) 
• a1=svm({ker,'C=1e4','optimizer="decomp"'}) 
• [tr2 a2]=train(a1,d) 
• plot(a2) 
 
-1 -0.5 0 0.5 1 1.5 2 2.5 3
-1
-0.5
0
0.5
1
1.5
2
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
-0.5 0 0.5 1 1.5 2 2.5
-0.5
0
0.5
1
1.5
2
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
133 
Simulação 
• [x,y] = spir(100); 
• Ip = find(y==1); 
• In = find(y==-1) 
• plot(x(Ip,1),x(Ip,2),'r*') 
• hold on 
• plot(x(In,1),x(In,2),'b*') 
• d=data(x,y) 
• ker=kernel('rbf',0.4) 
• a1=svm({ker,'C=1e4','optimizer="decomp“,’ty
pe=“use2norm”'}) 
• [tr2 a2]=train(a1,d) 
• plot(a2) 
-0.5 0 0.5 1 1.5 2 2.5
-0.5
0
0.5
1
1.5
2
-1 -0.5 0 0.5 1 1.5 2 2.5 3
-1
-0.5
0
0.5
1
1.5
2
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
134 
Simulação 
• [x,y] = spir(100); 
• Ip = find(y==1); 
• In = find(y==-1) 
• plot(x(Ip,1),x(Ip,2),'r*') 
• hold on 
• plot(x(In,1),x(In,2),'b*') 
• d=data(x,y) 
• ker=kernel('rbf',0.4) 
• a1=lssvm({ker,'C=1e4}) 
• [tr2 a2]=train(a1,d) 
• plot(a2) 
-0.5 0 0.5 1 1.5 2 2.5
-0.5
0
0.5
1
1.5
2
-1 -0.5 0 0.5 1 1.5 2 2.5 3
-1
-0.5
0
0.5
1
1.5
2
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
135 
Simulação 
• [x,y] = spir(50); 
• d=data(x,y) 
• ker=kernel('rbf',0.4) 
• a1=lssvm({ker,'C=1e4’}) 
• a2=selparam(a1) 
• [tr3 a3]=train(a2,d) 
-10
-5
0
5
10
15
20
25
-4
-2
0
2
4
0
0.2
0.4
0.6
0.8
x
1
Optimizationgrid after first iteration
x
2
co
st
-10 -5 0 5 10 15 20 25
-3
-2
-1
0
1
2
3
4
Optimization grid after first iteration
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
136 
Simulação 
• [x,y] = spir(50); 
• d=data(x,y) 
• ker=kernel('rbf',0.4) 
• a1=lssvm({ker,'C=1e4’}) 
• a2=selparam(a1) 
• [tr3 a3]=train(a2,d) 
-4
-2
0
2
4
6
-2.5
-2
-1.5
-1
-0.5
0
0.2
0.4
0.6
0.8
log(C)
Grid Otimizacao depois da iteracao 2
co
st
-4 -3 -2 -1 0 1 2 3 4 5
-3
-2.5
-2
-1.5
-1
-0.5
Grid Otimizacao depois da iteracao 2
C= 76.0917 = 0.116834 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
137 
Simulação 
• [x,y] = spir(50); 
• d=data(x,y) 
• ker=kernel('rbf',0.116834) 
• a1=lssvm({ker,'C=76.0917’}) 
• [tr2 a2]=train(a1,d) 
• plot(a2) 
C= 76.0917 = 0.116834 
-1 -0.5 0 0.5 1 1.5 2 2.5 3
-1
-0.5
0
0.5
1
1.5
2
-1
-0.8
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
A tarefa de Predição 
138 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Um método para predição 
 
 Máquinas Vetores Suporte 
 
SVM – Support Vector Machine 
139 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Classificação e Regressão 
• Qual é a diferença entre Classificação e 
Regressão ? 
 
• Em problemas de Regressão a variável de 
saída y assume valores contínuos, 
enquanto que em problemas de 
classificação y é estritamente categórica. 
 
140 
141 
• Desenvolvido por Vapnik (1995) 
 
• Modelo: Dado um conjunto de amostras 
estimar a função: 
 
 
• Minimizando 
 
• )(2
1
),(
1
2



l
i
iFCww 
Problema de Regressão 
bxwxf  ))(()( 
RyRxyxyx nll  ,),,(,),,( 11 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
142 
• Problema Primal 
 
 
 
• Sujeito a 
 
0
0
,,1,)(
,,1,)(
*
*




i
i
iii
iii
Niybxw
Nibxwy












 

N
i
i
N
i
Cwww
1
*
1
* )(
2
1
),,( 
Formulação do SVM para 
Regressão 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
143 
Funções de penalidade para 
regressão 
• -insensível 
-0.5 -0.4 -0.3 -0.2 -0.1 0 0.1 0.2 0.3 0.4 0.5
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
e-Insentive
-0.5 -0.4 -0.3 -0.2 -0.1 0 0.1 0.2 0.3 0.4 0.5
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
e-Quadratica
-0.5 -0.4 -0.3 -0.2 -0.1 0 0.1 0.2 0.3 0.4 0.5
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
Huber
• -quadrática 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
144 
Formulação do SVM para Regressão 
NiCi ,,1,0
* 
• Problema dual 
 
 
• Sujeito a 
 
 
 
• Fórmula Usual em Otimização 
 
 

 

N
i
iii
N
i
iii
N
i
N
j
jijiji yKW
1
*
1
*
1 1
** )()())(,()(
2
1
)(min  xx
NiCi ,,1,0 


TT cHW 
2
1
)(min
NiCi ,,1,0  
bA 
Ni
N
i
N
i
ii ,,1,
1 1
*  
 

L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Predição - avaliação 
• Neste caso erros não são simplesmentes presentes ou 
ausentes, e sim de diferentes tamanhos. 
 
• Erro quadrado médio: medida mais usada. 
– as vezes a raíz quadrada é usada para trazer a medida para a mesma dimensão 
dos valores preditos. 
• Erro absoluto médio: alternativa 
– ao contrário do erro quadrado médio, não potencializa o efeito dos outliers. 
• Erro quadrado relativo: 
– toma o erro quadrado total e o normaliza dividindo-o pelo erro quadrado total do 
preditor padrão (média dos dados de treinamento). 
• Coeficiente de correlação: 
– mede a correlação estatísticas entre os valores preditos (p’s) e os valores 
esperados (a’s). 1 = correlação perfeita; 0 não há correlação; -1 correlação 
perfeita negativa. 
145 
(Witten & Frank, 2005) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
• Exemplo: 
146 
Predição - avaliação 
(Witten & Frank, 2005) 
Medidas de desempenho para modelos de predição numérica 
A B C D 
raíz do erro quadrado médio 67.8 91.7 63.3 57.4 
erro absoluto médio 41.3 38.5 33.4 29.2 
erro quadrado relativo médio 42.2% 57.2% 39.4% 35.8% 
erro absoluto médio 43.1% 40.1% 34.8% 30.4% 
coeficiente de correlação 0.88 0.88 0.89 0.91 
Melhor preditor! 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
147 
Exemplo 
 
(a) (b) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
148 
 
(c) (d) 
Figura – Aproximação com diferentes níveis de precisão requer um 
numero diferente de vetores suporte: 32 SV para  =0.01, (b) 12 SV 
para  = 0.05, (c) 10 SV para  = 0.1, (d) 6 SV para  = 0.2 para função 
de perda norma  - insensível. 
Exemplo 
L
im
a
, 
C
. 
M
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
A tarefa de Agrupamento 
149 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Agrupamento (clustering) 
• A tarefa de agrupamento consiste em agrupar um conjunto de objetos 
físicos ou abstratos em grupos de objetos similares. 
 
• Um grupo é uma coleção de objetos que são similares uns aos outros, 
dentro de um grupo, e dissimilares aos objetos de outros grupos. 
– pode ser considerada uma forma de compressão 
 
• O modelo de agrupamento não é construído com base em dados rotulados. 
Apenas a informação de similiridade entre os dados é usada. 
– após o modelo de agrupamento ser construídos, um processo de rotulação dos grupos 
formados pode ser útil. 
150 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. 
Agrupamento - aplicações 
• pesquisa de 
mercado 
 
 
 
 
• reconhecimento 
de padrões 
 
 
 
 
• análise de dados 
 
 
 
 
• processamento de 
imagens .... 
 151 
Os profissionais de marketing são apoiados pelos modelos de 
agrupamento na tarefa de descobrir grupos distintos em suas bases 
de clientes e na tarefa de caracterizá-los com base nos padrões 
descobertos. 
Em biologia, essa tarefa pode ser usada na derivação de 
taxonomias de plantas e animais, na caracterização de genes com 
funcionalidades similares e para descobrir estrutura inerentes a 
populações. 
Suportar a análise de documentos textuais e criar indexadores para 
recuperação de informação na WEB. 
Identificação de área de uso similar da terra ou identificação de 
grupos de casa em uma cidade, de acordo com a similaridade entre 
elas. 
(Han & Kamber, 2006) 
L
im
a
, 
C
. 
A
. 
M
. 
&
 P
e
re
s
, 
S
. 
M
. • Escalabilidade: trabalham muito bem em pequenos conjuntos de dados e podem 
apresentar-se “tendenciosos” em amostras de grandes conjuntos de dados. 
• Habilidade de lidar com diferentes tipos de atributos: lidam bem com atributos 
numéricos mas apresentam dificuldades com outros