IF67B C71 aula20 parte1

Prévia do material em texto

IF71B-C71 - Inteligeˆncia Artificial
Aula 20 - Aprendizado de Ma´quina
Parte I
Profa. Dra. Priscila T iemi çaeda Saito
k psaito@utfpr.edu.br
2o Semestre 2016
20/10/16
Roteiro
1 Aprendizado de Ma´quina
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 2 / 33
Aprendizado de Ma´quina
k Nearest Neighbor - k-NN
consiste em atribuir a um exemplo de teste x , a classe do seu vizinho
mais pro´ximo
significado de k
I classificar x atribuindo a ele o ro´tulo representado mais frequentemente
dentre as k amostras mais pro´ximas
I contagem de votos
uma medida de proximidade bastante utilizada e´ a distaˆncia
Euclidiana
d(x , y) =
√∑n
i=1(xi − yi )2
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 3 / 33
Aprendizado de Ma´quina
k-NN - Distaˆncia Euclidiana
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 4 / 33
Aprendizado de Ma´quina
k-NN - Distaˆncia Euclidiana
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 5 / 33
Aprendizado de Ma´quina
k-NN - Exemplo
A qual classe pertence este ponto? Azul ou vermelho?
Calcule para os seguintes valores de k :
I k = 1→ na˜o se pode afirmar
I k = 3→ vermelho - 5, 2− 5, 3
I k = 5→ vermelho - 5, 2− 5, 3− 6, 2
I k = 7→ azul - 3, 2− 2, 3− 2, 2− 2, 1
A classificac¸a˜o pode mudar de acordo com a escolha de k
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 6 / 33
Aprendizado de Ma´quina
k-NN - Algumas questo˜es
Como calcular a distaˆncia entre duas tuplas?
I para atributos cont´ınuos: distaˆncia Euclidiana
d(x , y) =
√∑n
i=1 (xi − yi )2
I para atributos catego´ricos
F se xi = yi enta˜o xi − yi = 0
F se xi e yi sa˜o distintos: xi − yi = 1
Como determinar o melhor valor de k (= nu´mero de vizinhos)?
I obtido repetindo-se os experimentos
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 7 / 33
Aprendizado de Ma´quina
k-NN - Vantagens e Desvantagens
Performance
I na˜o constro´i um modelo de classificac¸a˜o
I processo de classificac¸a˜o de uma tupla e´ lento
Sens´ıvel a ru´ıdos
I k-NN faz predic¸a˜o baseando-se em informac¸o˜es locais a` tupla sendo
classificada
I a´rvores de decisa˜o, redes neurais e bayesianas encontram modelo global
que se leva em conta todo o banco de dados de treinamento
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 8 / 33
Aprendizado de Ma´quina
ID IDADE RENDA ESTUDANTE CREDITO CLASSE
1 ≤ 30 Alta Na˜o Bom Na˜o
2 ≤ 30 Alta Sim Bom Na˜o
3 31..40 Alta Na˜o Bom Sim
4 > 40 Me´dia Na˜o Bom Sim
5 > 40 Baixa Sim Bom Sim
6 > 40 Baixa Sim Excelente Na˜o
7 31..40 Baixa Sim Excelente Sim
8 ≤ 30 Me´dia Na˜o Bom Na˜o
9 ≤ 30 Baixa Sim Bom Sim
10 > 40 Me´dia Sim Bom Sim
11 ≤ 30 Me´dia Sim Excelente Sim
12 31..40 Me´dia Na˜o Excelente Sim
13 31..40 Alta Sim Bom Sim
14 > 40 Me´dia Na˜o Excelente Na˜o
X = (≤ 30, Me´dia, Sim, Bom)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 9 / 33
Aprendizado de Ma´quina
Distaˆncia Valor
d(X,1) 1,41
d(X,2) 1
d(X,3) 1,73
d(X,4) 1,41
d(X,5) 1,41
d(X,6) 1,73
d(X,7) 1,73
d(X,8) 1
d(X,9) 1
d(X,10) 1
d(X,11) 1
d(X,12) 1,74
d(X,13) 1,41
d(X,14) 1,74
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 10 / 33
Aprendizado de Ma´quina
k = 5
Os 5 vizinhos mais pro´ximos sa˜o
I X1 = (≤ 30 Alta Sim Bom) Classe = Na˜o
I X2 = (≤ 30 Me´dia Na˜o Bom) Classe = Na˜o
I X3 = (≤ 30 Baixa Sim Bom) Classe = Sim
I X4 = (> 40 Me´dia Sim Bom) Classe = Sim
I X5 = (≤ 30 Me´dia Sim Excelente Classe = Sim
Logo, X e´ classificada na classe = Sim
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 11 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
A´rvore de decisa˜o para “jogar teˆnis”
Cada no´ interno testa um atributo
Cada ramo corresponde a um valor do atributo
Cada folha representa uma classe
Instaˆncias sa˜o representadas por pares atributo-valor
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 12 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Base de treinamento e a´rvore de decisa˜o
Nome Idade Renda Profissa˜o ClasseProdEletr
Daniel ≤ 30 Me´dia Estudante Sim
Joa˜o 31..50 Me´dia-Alta Professor Sim
Carlos 31..50 Me´dia-Alta Engenheiro Sim
Maria 31..50 Baixa Vendedora Na˜o
Paulo ≤ 30 Baixa Porteiro Na˜o
Ota´vio > 60 Me´dia-Alta Aposentado Na˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 13 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Base de treinamento e a´rvore de decisa˜o
Nome Idade Renda Profissa˜o ClasseProdEletr
Daniel ≤ 30 Me´dia Estudante Sim
Joa˜o 31..50 Me´dia-Alta Professor Sim
Carlos 31..50 Me´dia-Alta Engenheiro Sim
Maria 31..50 Baixa Vendedora Na˜o
Paulo ≤ 30 Baixa Porteiro Na˜o
Ota´vio > 60 Me´dia-Alta Aposentado Na˜o
Regras de Classificac¸a˜o
I Se Idade ≤ 30 e Renda e´ Baixa enta˜o Na˜o Compra Eletroˆnico
I Se Idade = 31− 50 e Prof e´ Me´dico enta˜o Compra Eletroˆnico
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 14 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
como medir a habilidade de um dado atributo na tarefa de discriminar
as classes?
I uma divisa˜o que mante´m as proporc¸o˜es de classes em todas as
partic¸o˜es e´ inu´til
I uma divisa˜o na qual em cada partic¸a˜o todos os exemplos sa˜o da mesma
classe tem utilidade ma´xima
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 15 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Como decidir qual o melhor atributo para dividir as amostras?
↑ Ganho(No´)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 16 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Exemplo: dados sobre condic¸o˜es meteorolo´gicas
Objetivo: identificar quais as condic¸o˜es ideais para se jogar um
determinado jogo
Apareˆncia Temperatura Humidade Vento Jogo
Sol Quente Alta Falso Na˜o
Sol Quente Alta Verdade Na˜o
Encoberto Quente Alta Falso Sim
Chuvoso Agrada´vel Alta Falso Sim
Chuvoso Frio Normal Falso Sim
Chuvoso Frio Normal Verdade Na˜o
Encoberto Frio Normal Verdade Sim
Sol Agrada´vel Alta Falso Na˜o
Sol Frio Normal Falso Sim
Chuvoso Agrada´vel Normal Falso Sim
Sol Agrada´vel Normal Verdade Sim
Encoberto Agrada´vel Alta Verdade Sim
Encoberto Quente Normal Falso Sim
Chuvoso Agrada´vel Alta Verdade Na˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 17 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Possibilidades para a escolha do atributo que sera´ utilizado para
dividir os dados no primeiro n´ıvel da a´rvore
Qual e´ a melhor escolha?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 18 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Possibilidades para a escolha do atributo que sera´ utilizado para
dividir os dados no primeiro n´ıvel da a´rvore
folha apenas com “Sim”
ou
folha apenas com “Na˜o”
I na˜o sera´ mais dividida
F a´rvore menor
Qual e´ a melhor escolha?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 19 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Possibilidades para a escolha do atributo que sera´ utilizado para
dividir os dados no primeiro n´ıvel da a´rvore
Escolha aquela que
produz os no´s mais puros
Ex.: atributo Apareˆncia
Qual e´ a melhor escolha?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 20 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Grau de pureza de um atributo em um no´ → Entropia
Entropia
Medida estat´ıstica que mede o qua˜o “confusa” e´ a distribuic¸a˜o das tuplas
entre as classes
Entropia maximal
I 2 classes e metade das tuplas esta˜o em umaclasse e a outra metade na
outra classe
Entropia zero
I todas as tuplas esta˜o em uma mesma classe
↑ entropia → ↑ informac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 21 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Qual e´ o Atributo-Teste?
I divide-se o no´ segundo cada atributo
I para cada divisa˜o calcula-se a entropia (grau de pureza) produzida caso
fosse escolhido este atributo
I considera-se o atributo cuja divisa˜o resulta em uma maior reduc¸a˜o da
entropia
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 22 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
↑ entropia → ↑ informac¸a˜o
Info(No´) =
∑n
i=1
ni
N Entropia(Ai )
Ai , i = {1, ..., n} sa˜o folhas (tabelas)
ni e´ o tamanho (tuplas) de Ai
N e´ o total dos tamanhos das tabelas
Entropia(Ai ) = −
(
Si
ni
log Sini +
Ni
ni
log Nini
)
Si e´ a quantidade de tuplas classificadas como “Sim”
Ni e´ a quantidade de tuplas classificadas como “Na˜o”
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 23 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Exemplo: dados sobre condic¸o˜es meteorolo´gicas
Objetivo: identificar quais as condic¸o˜es ideais para se jogar um
determinado jogo
Apareˆncia Temperatura Humidade Vento Jogo
Sol Quente Alta Falso Na˜o
Sol Quente Alta Verdade Na˜o
Encoberto Quente Alta Falso Sim
Chuvoso Agrada´vel Alta Falso Sim
Chuvoso Frio Normal Falso Sim
Chuvoso Frio Normal Verdade Na˜o
Encoberto Frio Normal Verdade Sim
Sol Agrada´vel Alta Falso Na˜o
Sol Frio Normal Falso Sim
Chuvoso Agrada´vel Normal Falso Sim
Sol Agrada´vel Normal Verdade Sim
Encoberto Agrada´vel Alta Verdade Sim
Encoberto Quente Normal Falso Sim
Chuvoso Agrada´vel Alta Verdade Na˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 24 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Possibilidades para a escolha do atributo que sera´ utilizado para
dividir os dados no primeiro n´ıvel da a´rvore
Qual e´ a melhor escolha?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 25 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Consideremos as 4 possibilidades para o atributo do primeiro no´
Se escolhermos o atributo Apareˆncia:
Info(Apareˆncia) = 5
14
Entropia(Folha 1) + 4
14
Entropia(Folha 2) + 5
14
Entropia(Folha 3)
Info(No´) =
∑n
i=1
ni
N
Entropia(Ai )
Entropia(Ai ) = −
(
Si
ni
log Si
ni
+ Ni
ni
log Ni
ni
)
Entropia(Folha1) = 2
5
log 2
5
+ 3
5
log 3
5
= 0.971
Entropia(Folha2) = 4
4
log 5
5
+ 0
4
log 0
4
= 0
Entropia(Folha3) = 3
5
log 3
5
+ 2
5
log 2
5
= 0.971
Logo, Info(No´) = 5
14
0.971 + 4
14
0 + 5
14
0.971 = 0.693
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 26 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Consideremos as 4 possibilidades para o atributo do primeiro no´
Info(Apareˆncia) = 5
14
Entropia(Folha 1) + 4
14
Entropia(Folha 2) + 5
14
Entropia(Folha 3) = 0.693
Info(Temperatura) = 4
14
Entropia(Folha 1) + 6
14
Entropia(Folha 2) + 4
14
Entropia(Folha 3) = 0.911
Info(Humidade) = 7
14
Entropia(Folha 1) + 7
14
Entropia(Folha 2) = 0.788
Info(Vento) = 8
14
Entropia(Folha 1) + 6
14
Entropia(Folha 2) = 0.892
Info(No´) =
∑n
i=1
ni
N
Entropia(Ai )
Entropia(Ai ) = −
(
Si
ni
log
Si
ni
+
Ni
ni
log
Ni
ni
)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 27 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Ganho de Informac¸a˜o ao escolher um atributo
I diferenc¸a entre a informac¸a˜o associada ao no´ antes (Info-pre´) da
divisa˜o e a informac¸a˜o associada ao no´ apo´s a divisa˜o (Info-po´s)
Ganho(No´) = Info-pre´ − Info-po´s
Info-po´s = informac¸a˜o do no´ (Info(No´)) calculada no passo anterior, ao
escolher A como atributo divisor
Info-pre´ = entropia do no´ antes da divisa˜o = NSimN log2
NSim
N +
NNao
N log2
NNao
N
em que NSim = total de tuplas classificadas como Sim
NNao = total de tuplas classificadas como Na˜o
N = total de tuplas no no´
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 28 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Ganho de Informac¸a˜o ao escolher um atributo
Ganho(No´) = Info-pre´ − Info-po´s
Info-po´s = Info(No´)
Info-pre´ = NSimN log2
NSim
N +
NNao
N log2
NNao
N
Info-pre´ = 914 log2
9
14 +
5
14 log2
5
14 = 0.940
Ganho(Apareˆncia) = 0.940 − 0.693 = 0.247 (atributo ideal)
Ganho(Temperatura) = 0.940 − 0.911 = 0.029
Ganho(Humidade) = 0.940 − 0.788 = 0.152
Ganho(Vento) = 0.940 − 0.892 = 0.020
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 29 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Como transformar uma a´rvore de decisa˜o em regras de classificac¸a˜o
IF L1 AND L2 AND Ln THEN Classe = Valor
Em que Li sa˜o expresso˜es do tipo Atributo = Valor
Para cada caminho, da raiz ate´ uma folha, tem-se uma regra de
classificac¸a˜o
Cada par (atributo, valor) neste caminho da´ origem a um Li
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 30 / 33
Aprendizado de Ma´quina
A´rvores de Decisa˜o
Base de treinamento e a´rvore de decisa˜o
Nome Idade Renda Profissa˜o ClasseProdEletr
Daniel ≤ 30 Me´dia Estudante Sim
Joa˜o 31..50 Me´dia-Alta Professor Sim
Carlos 31..50 Me´dia-Alta Engenheiro Sim
Maria 31..50 Baixa Vendedora Na˜o
Paulo ≤ 30 Baixa Porteiro Na˜o
Ota´vio > 60 Me´dia-Alta Aposentado Na˜o
Regras de Classificac¸a˜o
IF Idade ≤ 30 AND Renda = Baixa THEN Classe = Na˜o
IF Idade ≤ 30 AND Renda = Me´dia THEN Classe = Sim
IF Idade ≤ 30 AND Renda = Me´dia-Alta THEN Classe = Sim
IF Idade ≤ 30 AND Renda = Alta THEN Classe = Sim
IF Idade 31..50 THEN Classe = Sim
IF Idade 51..60 THEN Classe = Sim
IF Idade > 60 THEN Classe = Na˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 31 / 33
Implementac¸o˜es
A´rvores de Decisa˜o
Etapa de Aprendizado
IF Idade ≤ 30 AND Renda = Baixa THEN Classe = Na˜o
IF Idade ≤ 30 AND Renda = Me´dia THEN Classe = Sim
IF Idade ≤ 30 AND Renda = Me´dia-Alta THEN Classe = Sim
IF Idade ≤ 30 AND Renda = Alta THEN Classe = Sim
IF Idade 31..50 THEN Classe = Sim
IF Idade 51..60 THEN Classe = Sim
IF Idade > 60 THEN Classe = Na˜o
Etapa de Classificac¸a˜o
Nome Idade Renda Profissa˜o ClasseProdEletr
Pedro 41..50 Me´dia-Alta Ecologista Na˜o
Jose´ 41..50 Me´dia-Alta Professor Na˜o
Luiza 41..50 Me´dia-Alta Assistente Social Na˜o
Carla ≤ 30 Baixa Vendedora Na˜o
Wanda ≤ 30 Baixa Faxineira Na˜o
Felipe > 60 Me´dia-Alta Aposentado Na˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 32 / 33
Implementac¸o˜es
Christian Borgel’s Webpages
I www.borgelt.net//software.html
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 20 - AM - Parte I 33 / 33
	Aprendizado de Máquina