Baixe o app para aproveitar ainda mais
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
Compartilhar