IF67B C71 aula24

Prévia do material em texto

IF71B-C71 - Inteligeˆncia Artificial
Aula 24 - Aprendizado de Ma´quina
Aprendizado Na˜o Supervisionado
Agrupamento (Clustering)
Profa. Dra. Priscila T iemi çaeda Saito
k psaito@utfpr.edu.br
2o Semestre 2016
09/11/16
Roteiro
1 Aprendizado de Ma´quina
Formas de Aprendizado
Tipos de algoritmos de agrupamento (clustering)
Algoritmos de Agrupamento (k-means e k-medoid)
Problemas
Concluso˜es
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 2 / 37
Formas de Aprendizado
Aprendizado Supervisionado
Aprendizado Na˜o-Supervisionado
Aprendizado Semi-Supervisionado
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 3 / 37
Aprendizado Supervisionado
No aprendizado supervisionado, todas as amostras de treinamento
sa˜o rotuladas
vetor de atributos classe
0.51 0.14 0.12 0.04 0.65 0.01 0.08 2
Estas amostras sa˜o ditas “supervisionadas”, pois conte´m tanto a
entrada (atributos), quanto a sa´ıda (classe)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 4 / 37
Aprendizado Supervisionado - Dificuldades
No entanto, muitas vezes temos que lidar com amostras
“na˜o-supervisionadas”, i.e., amostras na˜o rotuladas
Por que?
I coletar e rotular um grande conjunto de amostras pode custar muito
tempo, esforc¸o, dinheiro, ...
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 5 / 37
Aprendizado Na˜o-Supervisionado
Podemos utilizar grandes quantidades de dados na˜o rotulados para
encontrar padro˜es existentes nestes dados
Em seguida, supervisionar a rotulac¸a˜o dos agrupamentos encontrados
Esta abordagem e´ bastante utilizada em aplicac¸o˜es de minerac¸a˜o de
dados (data mining), onde o conteu´do de grandes bases de dados
na˜o e´ conhecido antecipadamente
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 6 / 37
Aprendizado Na˜o-Supervisionado
O principal interesse do aprendizado na˜o-supervisionado e´
desvendar a organizac¸a˜o dos padro˜es existentes nos dados por meio
de clusters (agrupamentos) encontrados
Com isso, e´ poss´ıvel descobrir similaridades e diferenc¸as entre os
padro˜es existentes, assim como derivar concluso˜es u´teis a respeito
deles
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 7 / 37
Aprendizado Na˜o-Supervisionado
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 8 / 37
Aprendizado Na˜o-Supervisionado
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 8 / 37
Aprendizado Na˜o-Supervisionado
Exemplos de agrupamentos (clusters)
Depende do atributo escolhido!
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 9 / 37
Aprendizado Na˜o-Supervisionado
Crite´rio de similaridade
I similaridade e´ dif´ıcil de ser definida
Depende do crite´rio de similaridade!
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 10 / 37
Aprendizado Na˜o-Supervisionado
Etapas do processo de aprendizado na˜o supervisionado
1 selec¸a˜o de atributos
2 medida de proximidade
3 crite´rio de agrupamento
4 algoritmo de agrupamento
5 verificac¸a˜o e interpretac¸a˜o dos resultados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 11 / 37
Aprendizado Na˜o-Supervisionado
Selec¸a˜o de atributos
I atributos devem ser adequadamente selecionados de forma a codificar a
maior quantidade poss´ıvel de informac¸o˜es relacionada a` tarefa de
interesse
I atributos devem ter tambe´m uma redundaˆncia m´ınima entre eles
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 12 / 37
Aprendizado Na˜o-Supervisionado
Medida de Proximidade
I medida para quantificar qua˜o similar ou dissimilar sa˜o dois vetores de
atributos
I e´ ideal que todos os atributos contribuam de maneira igual no
ca´lculo da medida de proximidade
F um atributo na˜o pode ser dominante sobre o outro, ou seja, e´
importante normalizar os dados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 13 / 37
Aprendizado Na˜o-Supervisionado
Diferentes te´cnicas de normalizac¸a˜o
Min-Max
ni =
xi−min(x)
max(x)−min(x)
Z-Score
ni =
xi−mean(x)
std(x)
Soma
ni =
xi∑
x
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 14 / 37
Aprendizado Na˜o-Supervisionado
Crite´rio de agrupamento
I depende da interpretac¸a˜o que o especialista da´ ao termo sens´ıvel com
base no tipo de cluster que sa˜o esperados
I por exemplo, um cluster compacto de vetores de atributos pode ser
sens´ıvel de acordo com um crite´rio enquanto outro cluster alongado,
pode ser sens´ıvel de acordo com outro crite´rio
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 15 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo de agrupamento
I adotada uma medida de proximidade e um crite´rio de agrupamento,
deve-se escolher um algoritmo de agrupamento que revele a
estrutura agrupada do conjunto de dados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 16 / 37
Aprendizado Na˜o-Supervisionado
Verificac¸a˜o e interpretac¸a˜o dos resultados
I uma vez obtidos os resultados do algoritmo de agrupamento, deve-se
verificar se o resultado esta´ correto
I isto geralmente e´ realizado por meio de testes apropriados
I em geral, os resultados do agrupamento devem ser integrados com
outras evideˆncias experimentais e ana´lises para chegar a`s concluso˜es
corretas
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 17 / 37
Aprendizado Na˜o-Supervisionado
Diferentes escolhas de atributos, medidas de proximidade,
crite´rios de agrupamento e algoritmos de agrupamento levam a
resultados totalmente diferentes
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 18 / 37
Aprendizado Na˜o-Supervisionado
Tarefa de agrupamento
I dado um conjunto de dados x
x = {x1, x2, ..., xn}
I define-se como um m-agrupamento de x, a partic¸a˜o de x em m grupos
(clusters), c1, c2, ..., cm, tal que as treˆs condic¸o˜es seguintes sejam
satisfeitas:
F nenhum cluster pode ser vazio (ci 6= ∅)
F a unia˜o de todos os clusters deve ser igual ao conjunto de dados que
gerou os clusters, ou seja, x
F a intersecc¸a˜o de dois clusters deve ser vazio, ou seja, dois clusters
na˜o podem conter vetores em comum (ci ∩ cj = ∅)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 19 / 37
Aprendizado Na˜o-Supervisionado
Os vetores contidos em um cluster ci devem ser mais similares uns
aos outros (intra) e menos similares aos vetores presentes nos outros
clusters (inter)
Tipos de clusters: clusters compactos, alongados, esfe´ricos e
elipsoidais
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 20 / 37
Aprendizado Na˜o-Supervisionado
Medidas de Proximidade
I medidas de dissimilaridade
F ↑ o valor, ↓ semelhanc¸a
F me´tricas: mahalanobis, manhattan, ...
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 21 / 37
Aprendizado Na˜o-Supervisionado
Algoritmos de agrupamento (clustering)
I buscam identificar padro˜es existentes em conjuntos de dados
I podem ser divididos em va´rias categorias
F particionais ou sequenciais
F hiera´rquicos
F baseados em otimizac¸a˜o de func¸o˜es de custo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 22 / 37
Aprendizado Na˜o-Supervisionado
Algoritmos Particionais
I Divide o conjunto de dados em k partes disjuntas, satisfazendo:
F amostras em uma mesma parte esta˜o pro´ximos (de acordo com um
crite´rio dado)
F amostras de partes distintas esta˜o longe, de acordo com este mesmo
crite´rio
I Para obter tal subdivisa˜o, os me´todospor particionamento operam do
seguinte modo:
F cria-se uma partic¸a˜o inicial aleato´ria de k partes e posteriormente, em
um processo iterativo, as amostras das partes va˜o sendo realocados
para outras partes de tal modo a melhorar o particionamento a cada
iterac¸a˜o
F de tal modo que cada parte realmente contenha amostras que esta˜o
pro´ximas e amostras em partes distintas estejam longe uma da outra
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 23 / 37
Aprendizado Na˜o-Supervisionado
Algoritmos Hiera´rquicos
I Podem ser divididos em 2 subcategorias
I Aglomerativos
F produzem uma sequeˆncia de agrupamentos com um nu´mero
d
¯
ecrescente de clusters a cada passo
F agrupamentos produzidos em cada passo resultam da fusa˜o de dois
clusters em um
I Divisivos
F atuam na direc¸a˜o oposta, isto e´, eles produzem uma sequeˆncia de
agrupamentos com um nu´mero crescente de clusters a cada passo
F agrupamentos produzidos em cada passo resultam da partic¸a˜o de um
u´nico cluster em dois
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 24 / 37
Aprendizado Na˜o-Supervisionado
Agrupamento hiera´rquico
I aglomerativo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 25 / 37
Aprendizado Na˜o-Supervisionado
Agrupamento hiera´rquico
I aglomerativo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 25 / 37
Aprendizado Na˜o-Supervisionado
Agrupamento hiera´rquico
I aglomerativo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 25 / 37
Aprendizado Na˜o-Supervisionado
Agrupamento hiera´rquico
I aglomerativo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 25 / 37
Aprendizado Na˜o-Supervisionado
Agrupamento hiera´rquico
I aglomerativo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 25 / 37
Aprendizado Na˜o-Supervisionado
Agrupamento hiera´rquico
I aglomerativo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 25 / 37
Aprendizado Na˜o-Supervisionado
Agrupamento hiera´rquico
I aglomerativo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 25 / 37
Aprendizado Na˜o-Supervisionado
Agrupamento hiera´rquico
I divisivo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 26 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I e´ a te´cnica mais simples de aprendizado na˜o-supervisionada
I consiste em fixar k centro´ides (de maneira aleato´ria)
I associar cada indiv´ıduo ao seu centro´ide mais pro´ximo
I recalcular os centro´ides com base nos indiv´ıduos classificados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 27 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
1 selecione k centro´ides iniciais
2 forme k clusters associando cada amostra ao seu centro´ide mais
pro´ximo
3 recalcule a posic¸a˜o dos centro´ides com base no centro de gravidade do
cluster
4 repita os passos 2 e 3 ate´ que os centro´ides na˜o sejam mais
movimentados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 28 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → seleciona k centro´ides iniciais
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → 1a iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → 2a iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → 3a iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → 4a iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → 5a iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → na iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → repete os passos anteriores ate´ que os centro´ides na˜o se
movam mais
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → 1a iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → 2a iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-means
I k = 3 → 3a iterac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 29 / 37
Aprendizado Na˜o-Supervisionado
Problemas do k-means
I o principal problema do k-means e´ a dependeˆncia de uma boa
inicializac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 30 / 37
Aprendizado Na˜o-Supervisionado
Problemas do k-means
I o principal problema do k-means e´ a dependeˆncia de uma boa
inicializac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 30 / 37
Aprendizado Na˜o-Supervisionado
Problemas do k-means
I o principal problema do k-means e´ a dependeˆncia de uma boa
inicializac¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 30 / 37
Aprendizado Na˜o-Supervisionado
Crite´rios de Otimizac¸a˜o
I o problema consiste em encontrar os clusters que
minimizam/maximizam um dado crite´rio
I alguns crite´rios de otimizac¸a˜o
F soma dos erros quadrados
F crite´rios de dispersa˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 31 / 37
Aprendizado Na˜o-Supervisionado
Crite´rio de otimizac¸a˜o - Soma dos Erros Quadrados
I e´ o mais simples e usado crite´rio de otimizac¸a˜o em clustering
I seja ni o nu´mero de amostras no cluster Di e seja mi a me´dia dessas
amostras
mi =
1
ni
∑
x∈Di x
I a soma dos erros quadrados e´ definida
Je =
∑c
i=1
∑
x∈Di ||x −mi ||2
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 32 / 37
Aprendizado Na˜o-Supervisionado
Crite´rio de otimizac¸a˜o - Soma dos Erros Quadrados
I adequado para dados menos dispersos
F separac¸a˜o natural
I na˜o e´ muito adequado para dados mais dispersos
F outliers podem afetar bastante os vetores me´dios m
dados menos dispersos
dados mais dispersos
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 33 / 37
Aprendizado Na˜o-Supervisionado
Crite´rio de otimizac¸a˜o - Crite´rios de Dispersa˜o
I relac¸a˜o within-between
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 34 / 37
Aprendizado Na˜o-Supervisionado
Algoritmo k-medoids
I diferenc¸a para o k-means e´ que o representante do grupo e´ uma
instaˆncia do pro´prio grupo e na˜o mais um centro´ide (ponto me´dio)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 35 / 37
Aprendizado Na˜o-Supervisionado
Caracter´ısticas deseja´veis
I descobrir clusters com forma arbitra´ria
I identificar clusters de tamanhos variados
I trabalhar com amostras com qualquer nu´mero de atributos (dimenso˜es)
I ser escala´vel para lidarcom qualquer quantidade de amostras
I exigir o m´ınimo de conhecimento para determinar os paraˆmetros de
entrada
I encontrar o nu´mero adequado de clusters
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 36 / 37
Aprendizado Na˜o-Supervisionado
Considerac¸o˜es finais
I o aprendizado na˜o-supervisionado ou agrupamento (clustering)
busca extrair informac¸a˜o relevante de dados na˜o rotulados
I existem va´rios algoritmos para agrupamento de dados
I diferentes escolhas de atributos, medidas de proximidade, crite´rios de
agrupamento e algoritmos de agrupamento levam a resultados
totalmente diferentes
I etapa de pre´-processamento para outros algoritmos
F tais como: caracterizac¸a˜o e classificac¸a˜o, que ira˜o enta˜o operar nos
clusters detectados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula24-AprendizadoMaquina 37 / 37
	Aprendizado de Máquina
	Formas de Aprendizado
	Tipos de algoritmos de agrupamento (clustering)
	Algoritmos de Agrupamento (k-means e k-medoid)
	Problemas
	Conclusões