Aprendizado de Máquina - Unisul

Prévia do material em texto

Aprendizado de Máquina: Simbólico
Ciências da Computação – UNISUL
Aran Bey Tcholakian Morales, Dr. Eng.
2
1. Regras de Associação
3
Visa descobrir associações importantes entre os itens (k-itemsets), tal
que, a presença de um item em uma determinada transação irá implicar
na presença de outro item na mesma transação. 
Cada registro corresponde a uma transação, com itens assumindo
valores binários (sim/não), indicando se o cliente comprou ou não o
respectivo item.
Uma regra de associação é uma implicação na forma X ⇒⇒⇒⇒ Y, e
possui dois parâmetros básicos: um suporte e uma confiança;
Regras de Associação
4
A função do Suporte é determinar a freqüência que ocorre um itemset
entre todas as transações da Base de Dados (é a porcentagem de 
transações onde este itemset aparece).
BDdatransaçõesdeTotalN
BAcomregistrosdeNBASuporte
o
o )()( ∩=⇒
Regras de Associação
A confiança mede a força da regra e determina a sua validade.
(A)quetransaçõesdeN
B)(AquetransaçõesdeNB)Conf(A
o
o
suportam
suportam ∩
=⇒
5
Regras de Associação
Id Leite Café Cerveja Pão Manteiga Arroz Feijão
1 N S N S S N N
2 S N S S S N N
3 N S N S S N N
4 S S N S S N N
5 N N S N N N N
6 N N N N S N N
7 N N N S N N N
8 N N N N N N S
9 N N N N N S S
10 N N N N N S N
Café e Pão S= 0.3 Se (Café) Então (Pão) C = 1.0
Pão e Manteiga S = 0.4 Se (Pão) Então (Manteiga) C = 0.8
Se (Manteiga) Então (Pão) C = 0.8
Café, Pão e Manteiga S = 0.3 Se (Café e Pão) Então Manteiga C = 1.0
Se (Café) Então (Pão e Manteiga) C =1.0
6
Fases do algoritmo apriori:
1. Geração dos conjuntos candidatos, com suporte acima do mínimo
estabelecido; 
2. Geração da regras de associação dos conjuntos candidatos gerados
no passo anterior com confiança superior ao mínimo estabelecido;
Regras de Associação
7
TID Items
100 1, 3, 4
200 2, 3, 5
300 1, 2, 3, 5
400 2, 5
Base de dados
L1
Itemsets So
{1, 3} 2
{2, 3} 2
{2, 5} 3
{3, 5} 2
Itemsets So
{1} 2
{2} 3
{3} 3
{5} 3
L2
Itemsets So
{1, 2} 1
{1, 3} 2
{1, 5} 1
{2, 3} 2
{2, 5} 3
{3, 5} 2
C2
Itemsets So
{2, 3, 5} 2
C3
Itemsets So
{2, 3, 5} 2
L3
Algoritmo Apriori Suporte mínimo = 2
Itemsets So
{ Null } 2
C4
FIM (Fase I)
Itemsets So
{1} 2
{2} 3
{3} 3
{4} 1
{5} 3
C1
8
Regras geradas para s >= 2 (ou 50%) e c >= 60%
Se 2 e 3 Então 5 ( s = 50%, c = 100%)
Se 2 e 5 Então 3 ( s = 50%, c = 66.7%)
Se 3 e 5 Então 2 ( s = 50%, c = 100%)
Se 2 Então 3 e 5 ( s = 50%, c = 66.7%)
Se 3 Então 2 e 5 ( s = 50%, c = 66.7%)
Se 5 Então 2 e 3 ( s = 50%, c = 66.7%)
Algoritmo Apriori
9
2. Classificação
10
Classificação
Introdução: Definição, objetivos, tarefas e características da
classificação;
Abordagem Simbólica: Árvore de decisão, teoria da informação,
algoritmos ID3 e C4.5;
Abordagem Estatística: Classificadores Bayesianos (Naive Bayes),
K-Vizinhos mais próximos (k-Nearest Neighbor);
Abordagem Biológica: Classificador baseado em Redes Neurais, e
em Algoritmos Genéticos.
11
Definição:
É determinar com que grupo de entidades, já classificadas anteriormente
um novo objeto (conjunto de dados) apresenta mais semelhanças.
É o processo pelo qual examinamos as propriedades (aspectos,
estrutura) de um objeto (dados) e atribuí-o a uma das classes
predefinidas. É aprender o mapeamento de uma função dos objetos
em uma das classes predefinidas.
Classificação
12
Objetivo: analisar os dados e desenvolver uma descrição ou modelo
para cada classe utilizando as estruturas presentes nos objetos.
Usar o relacionamento descoberto para prever a classe (o valor do
atributo meta) de um registro com classe desconhecida.
Descobrir um relacionamento entre os atributos previsores
e o atributo meta, usando registros cuja classe é conhecida, para se
construir um modelo de algum tipo que possa ser aplicado aos
objetos não classificados para classifica-os.
Classificação
13
Abordagem Simbólica
14
Árvores de Decisão
São um método de aprendizagem supervisionado que constrói
árvores de classificação a partir de exemplos.
Algoritmos : ID3, C4.5, (Quinlan), CART (Breiman)
Os métodos baseados em árvores para classificação, dividem o
espaço de entrada em regiões disjuntas para construir uma
fronteira de decisão. 
As regiões são escolhidas baseadas em uma otimização heurística
onde a cada passo os algoritmos selecionam a variável que provê
a melhor separação de classes de acordo alguma função custo.
15
Comprar ?Comprar ?
SS
SS
SS
SS
NN
NN
NN
NN
NN
NN
ID Sexo Cidade Idade
1 M Floripa 25
2 M Criciuma 21
3 F Floripa 23
4 F Criciuma 34
5 F Floripa 30
6 M Blumenau 21
7 M Blumenau 20
8 F Blumenau 18
9 F Floripa 34
10 M Floripa 55
16
CidadeCidade
IdadeIdade
Blu
me
na
u
Blu
me
na
u Crici
Criciúúmama
NãoNão SimSim
F
loripa
F
loripa
<=27
<=27> 2
7
> 2
7
SimSimNãoNão
Se (Cidade=Floripa e Idade <= 27) Então (Decisão = Sim)
Se (Cidade=Floripa e Idade > 27) Então (Decisão = Não)
Se (Cidade=Criciúma) 
Então (Decisão = Sim)
Se (Cidade=Blumenau) 
Então (Decisão = Não)
17IdadeIdade
CidadeCidade
2727
BlumenauBlumenau
CriciCriciúúmama
FloripaFloripa
SIMSIM NÂONÂO
18
Algoritmo ID3
ID3, é um algoritmo simples que construí uma árvore de decisão sob
as seguintes premissas:
Cada vértice (nodo) corresponde a um atributo, e cada aresta da
árvore a um valor possível do atributo.
Uma folha da árvore corresponde ao valor esperado da decisão
segundo os dados de treino utilizados.
A explicação de uma determinada decisão está na trajetória da raiz a
folha representativa desta decisão.
19
Algoritmo ID3
Cada vértice é associado ao atributo mais informativo que ainda não
tenha sido considerado.
Para medir o nível de informação de um atributo se utiliza o conceito
de entropia da Teoria da Informação.
Menor o valor da entropia, menor a incerteza e mais utilidade tem o
atributo para a classificação.
20
Algoritmo ID3
Passo 1: 
Se todos os dados estão classificados em alguma das classes 
Então parar ;
Senão selecionar ( utilizando alguma heurística) algum atributo A com
valores v1, v2, . . ., vn e criar um nó de decisão.
Passo 2: particionar o conjunto de dados de treino T, em
subconjuntos t1, t2, . . . , tn de acordo com os valores do atributo A
Passo 3: aplicar o algoritmo recursivamente para cada conjunto de
dados ti
21
Algoritmo ID3: Exemplo
Dia Aspecto Temperatura Umidade Vento Decisão
1 Sol Quente Alta Fraco N
2 Sol Quente Alta Forte N
3 Nublado Quente Alta Fraco S
4 Chuva Agradável Alta Fraco S
5 Chuva Fria Normal Fraco S
6 Chuva Fria Normal Forte N
7 Nublado Fria Normal Forte S
8 Sol Agradável Alta Fraco N
9 Sol Fria Normal Fraco S
10 Chuva Agradável Normal Fraco S
11 Sol Agradável Normal Forte S
12 Nublado Agradável Alta Forte S
13 Nublado Quente Normal Fraco S
14 Chuva Agradável Alta Forte N
22
SIMSIM
UnidadeUnidade
C
h
uva
C
h
uva
AspectoAspecto
SolSol NubladoNublado
AltaAlta
NormalNormal
SIMSIM
NÃONÃO
VentoVento
SIMSIM
FracoFraco
NÃONÃO
ForteForte
23
Abordagem Estatística
24
P(B|A) = P(A ∩∩∩∩ B) / P(A) (probabilidade condicional)
P(B|A) = P(A|B) . P(B) / P(A) (regra de Bayes)
P(B|A) = P(A ∩∩∩∩ B) / P(A) (1)
P(A|B) = P(A ∩∩∩∩ B) / P(B) (2) 
P(A ∩∩∩∩ B) = P(A|B) . P(B) (3)
Substituindo (3) em (1) chegamos a regra de Bayes
P(E1|A) = P(A|E1) . P(E1) / SOMAi P(A|Ei).P(Ei)
(teorema de Bayes
Classificadores Bayesianos: Naive Bayes
25
Sejam A1, ..., Ak atributos, [a1, ..., ak] uma tupla do banco de dados,
e C uma classe a ser prevista. 
A previsão ótima é umaclasse de valor c tal que: 
P(C = c | A1 = a1 ∩∩∩∩ ... ∩∩∩∩ Ak = ak) é máxima.
Transformando através da regra de Bayes, que estabelece: 
= P(A1 = a1 ∩∩∩∩ ... ∩∩∩∩ Ak = ak | C = c) * P(C = c) / P(A1 = a1 ∩∩∩∩ ... 
∩∩∩∩ Ak = ak)
Considerando independência entre os atributos:
= P(A1 = a1|C = c) *... P(Ak = ak| C = c)
* P(C = c) / P(A1 = a1) *� P(Ak = ak)
Classificadores Bayesianos: Naive Bayes
26
Dia Aspecto Temperatura Umidade Vento Decisão
1 Sol Quente Alta Fraco N
2 Sol Quente Alta Forte N
3 Nublado Quente Alta Fraco S
4 Chuva Agradável Alta Fraco S
5 Chuva Fria Normal Fraco S
6 Chuva Fria Normal Forte N
7 Nublado Fria Normal Forte S
8 Sol Agradável Alta Fraco N
9 Sol Fria Normal Fraco S
10 Chuva Agradável Normal Fraco S
11 Sol Agradável Normal Forte S
12 Nublado Agradável Alta Forte S
13 Nublado Quente Normal Fraco S
14 Chuva Agradável Alta Forte N
Classificadores Bayesianos: Naive Bayes
27
Qual será a decisão, se o dia estiver com sol, temperatura fria, umidade
alta e vento forte ?
P(Jogar = S / Aspecto = Sol ∩∩∩∩ Temperatura = Fria ∩∩∩∩ Umidade =
Alta ∩∩∩∩ Vento = Forte) = ?
P( Sol/S) * P( Fria/S) * P(Alta/S) * P(Forte/S) * P(S)
_____________________________________________________________
P( Sol) * P( Fria) * P(Alta) * P(Forte) 
(2/9 * 3/9 * 3/9 * 3/9 * 9/14) / (5/14 * 4/14 * 9/14 * 6/14) = 0,0053/0,028 = 0,189
Classificadores Bayesianos: Naive Bayes
28
P(Aspecto = Sol ) = 5/14 P(Temperatura = Fria) = 4/14
P(Umidade = Alta ) = 9/14 P(Vento = Forte ) = 6/14
P(Jogar = S) = 9/14; P(Jogar = N) = 5/14;
P(Aspecto=Sol/Jogar=S)=2/9; P(Aspecto=Sol/Jogar=N)=3/5;
P(Temperatura=Fria/Jogar=S)=3/9;
P(Temperatura=Fria/Jogar=N)=1/5;
P(Umidade=Alta/Jogar=S)=3/9; P(Umidade=Alta/Jogar=N)=4/5;
P(Vento=Forte/Jogar=S)=3/9; P(Vento=Forte/Jogar=N) = 3/5;
Classificadores Bayesianos: Naive Bayes
29
P(Jogar = N / Aspecto = Sol ∩ Temperatura = Fria ∩ Umidade = 
Alta ∩ Vento = Forte) = ?
P( Sol/N) * P( Fria/N) * P(Alta/N) *
P(Forte/N)*P(N) / P( Sol) * P( Fria) * P(Alta) * P(Forte) =
(3/5 * 1/5 * 4/5 * 3/5 * 5/14) / (5/14 * 4/14 * 9/14 * 8/14) =
0,0206/0,028 = 0,734
Classificadores Bayesianos: Naive Bayes
30
K- Nearest Neighbor
Exemplo:
A classificação de ? (F(?)), será a classificação de Xi (F(Xi)), onde Xi é
a instancia mais próxima de ?.
Se k=1, na figura ? seria classificado como O 
Se k=7, na figura ? seria classificado como #
Outra alternativa, do algoritmo, é dar peso a contribuição de cada 
um dos k-vizinhos de acordo com sua distancia.
31
x = < idade(x), altura(x), peso(x), classe(x)>, onde classe pode ser 
“sim”, “não”]
Exemplo: joão = (<36, 1.80, 76>, ???) a ser classificado
josé = (<30, 1.78, 72>, sim)
maria = (<25, 1.65, 60>, sim)
anastácia = (<28, 1.60, 68>, não)
Calculo da distância euclidiana:
d(joão,josé)=[(36-30)2+(1.80-1.78)2+(76-72)2]1/2=(36+0.0004+16)1/2= 
7,21
d(joão,maria) = (121+0.0225+256)1/2 = 19,41
d(joão, anastácia) = (64+0.04+64)1/2 = 11,32
K- Nearest Neighbor
22
22
2
11 )(...)()(),( pp yxyxyxyxd −++−+−=
32
3. Agrupamentos
33
Conjunto de métodos usados para a construção de grupos de objetos
(agrupar objetos) com base nas semelhanças e diferenças entre os
mesmos de tal maneira que os grupos obtidos são os mais homogêneos
e bem separados possíveis.
Em resumo, é colocar os iguais (ou quase iguais) juntos num mesmo
grupo e os desiguais em grupos distintos.
A clusterização é uma tarefa prévia à classificação. 
Sem classes, não podemos classificar um objeto.
A clusterização permite determinar qual o número de grupos e os
grupos existentes num conjunto de objetos.
Agrupamentos
34
Desafios 
Como medir a similaridade entre os itens? (como qualificar os itens)
Como formar os agrupamentos?
(que variáveis fazem parte da geração dos agrupamentos)
Quantos grupos devem ser formados?
(como definir o número de agrupamentos, ou o raio de abrangência do
agrupamento).
Trabalha com dados categóricos e numéricos e é de fácil aplicação;
Alta dependência na escolha da métrica de similaridade; 
Sensibilidade aos parâmetros iniciais e tipos de dados;
Pode ser difícil interpretar os resultados alcançados;
35
Desafios
Medidas de Similaridade
As medidas de similaridade fornecem valores numéricos que
expressam a “distância” entre dois objetos. Quanto menor o valor
desta, mais semelhantes serão os objetos e deverão estes ficarem no
mesmo cluster.
Não há uma medida de similaridade que sirva para todos os tipos de
variáveis que podem existir numa base de dados.
Variáveis numéricas:
As medidas que é normalmente usadas para computar as dissimilaridades
de objetos descritos por tais variáveis é a: Distancia Euclidiana
22
22
2
11 )(...)()(),( pp yxyxyxyxd −++−+−=
Métodos por particionamento
Os algoritmos por particionamento tem como entrada o número k de 
clusters e os dados a serem agrupados, e como saída os k clusters com
os dados em cada cluster. 
Inicialmente, o algoritmo escolhe k objetos como sendo os centros dos
k clusters. 
Os objetos são divididos entre os k clusters de acordo com a medida de
similaridade adotada, de modo que cada objeto fique no cluster que
forneça o menor valor de distância entre o objeto e o centro do mesmo.
Então, o algoritmo utiliza uma estratégia iterativa de controle para
determinar o centro do cluster e que objetos devem mudar de cluster.
Algoritmos
38
Observações
Item x1 x2
A 5 3
B -1 1
C 1 -2
D -3 -2
Dataset a ser clusterizado
Variáveis
Algoritmo K-means
39
Coordenadas dos centros
Cluster x1 x2
(AB) (5 + (-1)) / 2 = 2 (3 + 1) / 2 = 2
(CD) (1 + (-3)) / 2 = -1 (-2 + (-2)) / 2 = -2
Passo 1
Particiona-se os itens em dois clusters (AB) e (CD) e calcula-se a 
coordenada (x1,x2) do centróide do cluster.
Algoritmo K-means
40
Passo 2 
Calcula-se a similaridade de cada item em relação ao centróide 
e em relação a cada item no grupo mais próximo. Se um item é
movido o centróide do cluster dever ser atualizado.
10)23()25())(,( 222 =−+−=ABAd
61)23()15())(,( 222 =+++=CDAd
10)21()21())(,( 222 =−+−−=ABBd
9)21()11())(,( 222 =+++−=CDBd
Algoritmo K-means
41
Ocorre o deslocamento do item (B) para o segundo cluster e 
calcula-se novamente as coordenadas.
Coordenadas dos centros
Cluster x1 x2
A 5 3
(BCD) -1 -1
Algoritmo K-means
42
Calcula-se a distância dos itens em relação ao cluster, para verificar a 
parada do algoritmo.
 Distâncias dos centróides
 Item
Cluster A B C D
A 0 40 41 89
(BCD) 52 4 5 5
0)33()55(),( 222 =−+−=AAd
40)31()51(),( 222 =−+−−=ABd
52)13()15())(,( 222 =+++=BCDAd
Algoritmo K-means
43
Algoritmos hierárquicos criam uma decomposição hierárquica dos
dados. 
A decomposição hierárquica é representada por um dendrograma,
uma árvore que iterativamente divide os dados em subconjuntos
menores até que cada subconjunto consista de somente um objeto.
Em tais hierarquias, cada nó da árvore representa um cluster da base
de dados.
O dendrograma pode ser criado de duas formas:
Métodos Hierárquicos
44
1. Abordagem aglomerativa (bottom-up): parte-se das folhas
superiores para a raiz. Começamos por colocar cada objeto em seu
próprio cluster (ou seja, todos os objetos estão separados), totalizando
n clusters. 
Em cada etapa, calculamos a distância entre cada par de clusters
(matriz de distâncias). Então, escolhemos 2 clusters com a distância
mínima para agrupar-los. 
A seguir, atualizamos a matriz de distâncias. Este processo continua
até que todos os objetos estejam em um único cluster (o nível mais
alto da hierarquia), ou até que uma condição de término ocorra.
Na abordagem divisiva (top-down), parte-se da raiz para as folhas.
Métodos Hierárquicos
45
AlgoritmoGeral de Agrupamento Hierárquico Aglomerativo
Passo 1: Iniciar o agrupamento formado por grupos unitários
Passo 2: Encontre, no agrupamento corrente, o par de grupos de
dissimilaridade mínima
Passo 3: Construa um novo grupo pela fusão desse par de grupos de
dissimilaridade mínima
Passo 4: Atualize a matriz de dissimilaridades: suprima as linhas e as
colunas correspondentes aos grupos fusionados e adicione uma linha e
uma coluna correspondente as dissimilaridades entre o novo grupo e os
grupos antigos
Passo 5: Se todos os objetos estão grupados, pare; senão vá para o
passo 2
Métodos Hierárquicos
46
Exemplo (Matriz de dados)
Itens/Variáveis V1 V2
A 3 2
B 4 5
C 4 7
D 2 7
E 6 6
F 7 7
G 6 4
47
Exemplo (Plot inicial)
48
3,22,05,03,62,23,6G
1,45,03,03,66,4F
4,12,22,25,0E
2,02,85,1D
2,05,1C
3,2B
A
G (6;4)F (7;7)E (6;6)D (2;7)C (4;7)B (4;5)A (3;2)
Exemplo (Distâncias calculadas)
49
Exemplo (Distâncias calculadas)
2,54,52,52,95,7EF
5,03,62,23,6G
2,02,85,1D
2,05,1C
3,2B
A
EF 
(6,5;6,5)
G (6;4)D (2;7)C (4;7)B (4;5)A (3;2)
50
Exemplo (Distâncias calculadas)
3,54,22,25,0CD
2,52,95,7EF
2,23,6G
3,2B
A
CD (3;7)EF 
(6,5;6,5)
G (6;4)B (4;5)A (3;2)
51
Exemplo (Distâncias calculadas)
3,22,53,2BG
3,55,0CD
5,7EF
A
BG 
(5;4,5)
CD (3;7)EF 
(6,5;6,5)
A (3;2)
52
Exemplo (Distâncias calculadas)
3,14,4BEFG
3,2CD
A
BEFG 
(5,75;5,5)
CD (3;7)A (3;2)
4,4CDEFG
A
CDEFG 
(4,8;6)
A (3;2)
53
Exemplo (Dendrograma)
A B C D E F G 
1,414
2,0
2,236
2,5
1
2
3
4
3,135
5
4,4 6