PublicouDiogo Eva Alterado mais de 3 anos atrás
Métodos usados para a construção de grupos de 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. Duas grandes classes de problemas em classificação: classificação supervisionada  classificação supervisionada A classificação não supervisionada se propõe a encontrar classes homogêneas a partir de um conjunto de indivíduos Objetivo: os indivíduos semelhantes devem pertencer a mesma classe É um objetivo intuitivo mas não é uma definição precisa da noção de classe
3 Agrupamento (Clustering)
Agrupar para que? Existe classes "naturais" e o desafio é encontra-las Deseja-se construir as classes segundo estruturas classificatórias (impostas) Encontrar classes úteis para o usuário Simplificação dos dados Geração de Hipóteses Predição com base nos grupos formados O que é um grupo? Não existe uma única definição satisfatória Coesão interna Isolamento externo
4 (a) (b) (c) (d) a) Grupos coesos e isolados
5 Principais Etapas da Formação de Agrupamentos
a) aquisição dos dados 1) Seleção das observações (indivíduos, objetos, casos, itens) 2) Seleção das variáveis (caracteres, descritores) e das correspondentes escalas 3) Construção da Tabela de Dados b) Pré-processamento dos dados 1) Mudança de escala 2) Normalização 3) Extração de caracteres c) Construção da Tabela de Dados d) Cálculo da Proximidade 1) Escolha de um Índice de Proximidade 2) Construção da Matriz de Proximidades e) Seleção de um Algoritmo de Formação de Grupos em função do tipo de agrupamento desejado f) Análise e Interpretação dos Resultados
6 Indivíduo Variáveis : conjunto das indivíduos (população, amostra)
  : indivíduo (especimen) ou grupo de indivíduos (espécie) Variáveis A cada característica (escolhida pelo usuário ou por um especialista), pode-se associar uma ou mais variáveis: Di: Domínio da variável yi
7 As variáveis podem ser quantitativas contínuas (ex, Peso, Altura) discretas (ex, numero de antenas, número de filhos) qualitativas (ex, sexo, grau de instrução) binárias (ex, presença de asas) com escala nominal (ex, sexo (masculino, feminino)), ordinal (ex, Grau de instrução{primário, segundário, superior}) intervalar (ex, grau celsius) proporcional (ex, grau kelvin, idade)
8 Representação do Conhecimento (lista de pares atributo-valor)
Y = {Y1, …, Yp} : Conjunto de variáveis (descritores, atributos, …) D = {D1, …, Dp} : Conjunto dos domínios das variáveis  = {1, …, p} : Conjunto das OTUs (indivíduos, casos, objetos, observações)
9 Espaço de descrição elemento de  Yj Y Yp Y1 W D + valor em D + + + +
10 Tabela de Dados N objetos ou individuos ={1,…, i ,…, N }
p descritores Y={Y1,…, Yj,…, Yp} Y1 … Yj Yp w1 wi wN A cada objeto i de  é associado um vetor de descrição representando as p medidas A cada variável ou parametro Yj é associado um vetor Que representa o conjunto de valores observados de  sobre Yj
11 Tipos de Tabelas quantitativas qualitativas binárias heterogêneas Exemplo:
12 Índices de Proximidade
Similaridade Dissimilaridade Índice de Similaridade É uma função tal que Quanto mais próximo dois indivíduos mais elevado é o valor da medida de similaridade entre eles
13 Índice de Dissimilaridade
É uma função tal que Quanto mais próximos dois indivíduos menor é o valor da medida de dissimilaridade entre eles
14 a 1 b x y z w Exemplos de Índices de Proximidade
15 Outros aspectos relativos aos índices de proximidade
16 Estruturas classificatórias
Cobertura Partição
17 Estruturas Classificatórias
Hierarquia Piramide
18 Métodos de Agrupamento Em Taxinomia Numérica distingue-se três grupos de métodos Técnicas de Otimização Objetivo: obter uma partição. Número de grupos fornecido pelo usuário Técnicas hierárquicas Objetivo: obter uma hierarquia (ou uma pirâmide) Pode-se obter uma partição "cortando-se" a hierarquia em um determinado nível. Técnicas de Cobertura Objetivo: obter grupos que eventualmente podem partilhar indivíduos.
19 Outros Aspectos Relativos aos Métodos de Agrupamento Métodos Aglomerativos versus Métodos Divisivos Métodos Monotéticos versus Métodos Politeticos Agrupamento Hard versus Agrupamento Fuzzy Métodos Incrementais versus Métodos não Incrementais Métodos Paramétricos versus Métodos não Paramétricos Métodos Geométricos versus Métodos não Geométricos
20 Classificação Hierarquica
Diagrama de Venn sobre os dados bi-dimensionais Dendograma
21 Métodos Hierárquicos Parte-se de uma tabela de dados e calcula-se uma distância entre os individuos de  Os métodos ascendentes hierárquicos tem por objetivo a construção de uma sequencia de partições encaixadas chamada hierarquia. A representação gráfica dessas hierarquias é realisada por uma arvore hierarquica ou dendrograma.
22 Hierarquia com índice Hierarquia com indice (H,f) Hierarquia H
23 Índices de agregação entre as classes
ligação minima ligação maxima Aumentação da inercia ou indice de WARD gA é o centro de gravidade da classe A m corresponde a ponderação das classes
24 Relação entre f e D f é um indice sobre a hierarquia H, D é um indice de agregação entre classes Para os indices D usuais (H,f) é uma hierarquia com indice (não há inversão) Senão, pode-se utilisar Nesse caso (H,f) é sempre uma hierarquia com indice
25 Técnicas de Hierárquicas Algoritmo Geral 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
26 Exemplo E01:(Sono=Pouco,T=Carro,Conic=Sim,Alcool=Não,Sair=Não,Fome=Sim) E02:(Sono=Pouco,T=Carona,Conic=Não,Alcool=Não,Sair=Sim,Fome=Sim) E03:(Sono=Sim,T=Carro,Conic=Não,Alcool=Sim,Sair=Sim,Fome=Não) E04:(Sono=Sim,T=Outros,Conic=Sim,Alcool=Sim,Sair=Sim,Fome=Não) Passo 1: C1={E01}, C2={E02}, C3={E03}, C4={E04} Passo 2: dmin = 2  C5= C3  C4 = {E03,E04} Passo 3:
27 Exemplo (CONT.) Passo 4: dmin = 3  C6= C1  C2 ={E01,E02} Passo Passo 6: dmin = 4  C7 = C5  C6 ={E01,E02,E03,E04} C07 C6 C5 E01 E02 E03 E04
28 Métodos de Partição A estrutura classificatória deseja é a partição. Definindo-se uma função de homogeneidade ou um critério de qualidade sobre uma partição, o problema de classificação torna-se um problema perfeitamente definido em otimização discreta. Encontrar, entre o conjunto de todas as partições possíveis, uma partição que otimize um critério definido à priori.  é finito e, portanto, existe um conjunto finito de partições. Esse problema é sempre soluvel por enumeração completa. Na pratica isso é irrealisável pois temos, com um conjunto de N objetos em K classes, aproximadamente soluções possiveis.
29 Problema de Otimização
Seja um critério U, definido de , onde é o conjunto de todas as partições em K classes não vazias . O problema de otimização se exprime sob a forma:
30 Otimização iterativa Parte-se de uma solução realizável Escolha
Na etapa t+1, tem-se uma solução realizável procura-se uma solução realizável Escolha que verifica O algoritmo para assim que
31 Algoritmo de vizinhança
Uma das estattégias mais utilisadas para contruir a função g é: associar a toda solução real'zável Q um conjunto finito de soluções realisáveis V(Q), chamada vizinhança de Q, Depois selecionar a solução ótima segundo esse critério U nessa vizinhança (solução localmente ótima). Por exemplo pode-se tomar como vizinhança de Q todas as partições obtidas a partir da partição Q mudando um só indivíduo de classe Dois exemplos bem conhecidos desse tipo de algoritmo são o algoritmo das transferências e o algoritmo k-means
32 Algoritmo das transferências
O critério U associado à partição Q é a soma das inércias de cada uma das classes, isto é, a inércia intra-classes: d é a distância euclidiana, nj representa o numero de elementos e wj é o centro de gravidade da classe Qj. Se o indivíduo ei é afetado em uma classe Ql, diferente da sua classe de afetação atual tem-se:
33 Algoritmo (a) Initialisação
No início, tem-se uma partição Q. O número de elementos nj e o centro de gravidade wj são calculados para cada uma das classes. (b) Etapa Iterativa test0 Para todo i de 1 à N faça a classe de i é s determinar l tal que test1 (c) Se test  0 então vá para (b)
34 Algoritmo k-means Com um algoritmo de vizinhança, não é necessário, para obter a diminuição do critério, de tomar sistematicamente a melhor solução, basta tomar nessa vizinhança uma solução melhor do que a solução em curso. No algoritmo k-means a etapa (b) torna-se: A diminuição do criterio U da inércia intra-classe está assegurada graças ao teorema de Huygens É impossivel demonstrar que uma das estratégias fornece sistematicamente uma melhor solução.
35 Afetação de um novo indivíduo
Uma função de afetação f de D em C={1,..,K}define uma partição do espaço de representação com Na convergência desses algoritmos, a função f é construida da seguinte maneira :
36 Algoritmos que possuem duas etapas de optimisação
A primeira etapa é a etapa de représentation, ela consiste em definir um representante ou prototipo para cada uma das classes. A segunda etapa é a etapa de afetação, ela modifica a classe de fetação de cada um dos indivíduos. Obsevações: A atualisação será realizada após a apresentação de todos os indivíduos de . A ordem de apresentação dos indivíduos não tem mais nenhuma influência sobre os resultados.
37 Algoritmo dos centros móveis
(a) initialisação No início tem-se uma partição Q ou um subconjunto de K elementos de . (b) Etapa de afetação test0 Para todo i de 1 a N faça determinar l tal que test1 (c) Etapa de representação Para todo j de 1 a K faça calcular o centro de gravidade e o efetivo da nova classe Qj (d) se test  0 vá para (b)
38 Exemplo y y Passo 1: k = 2 e G1={1,2,3} e G2={4,5,6,7} Passo2: g1 = (1.83, 2.33) e g2 = (4.13, 5.38) Passo3: d(wi,g1) d(wi,g2) Grupo	G1	G1	G2	G2	G2	G2	G2 Passo 4: G1={1,2} e G2 = {3,4,5,6,7} Houve modificação dos grupos? Sim. Vá para o passo 2 Etc.
39 Métodos Paramétricos Abordagem probabilista Os dados D são uma mistura de k distribuições normais uni-variadas de mesma variância 2 Cada observação é descrita pelo vetor (xi, zi1, …, zik), onde a) xi é o valor da i-ésima observação; b) zij = 1 se a observação é proveniente do j-ésimo grupo e zij = 0, senão Diz-se também que xi é a variável observada e zi1, …, zik são as variáveis ocultas Trata-se de estimar (aprender) as médias de cada uma das k distribuições normais: a) encontrar a hipótese h = < 1,…, k > que maximiza a verossimilhança dessa médias, isto é, encontrar a hipótese h = < 1… k > que maximiza p(D/h)
40 Métodos Paramétricos O Algoritmo EM (Expectation, Maximisation) Inicialização: h = < 1,…, k >, onde 1,…, k são valores iniciais arbitrários Etapa 1: Calcular o valor esperado E[zij] de cada variável oculta zij, supondo verdadeira a hipótese atual h = < 1,…, k > E[zij] é a probabilidade de que a observação xi tenha sido gerada pela j-ésima distribuição normal
41 O Algoritmo EM (Expectation, Maximisation) Etapa 2: Calcular a nova hipótese h' = < '1,…, 'k > de máxima verossimilhança, supondo que os valores de cada variável oculta zij é o seu valor esperado E[zij] calculado no Passo 1. Substituir a hipótese h = < 1,…, k > pela hipótese h' = < '1,…, 'k > e recomeçar. Nesse caso, a hipótese de máxima verossimilhança é dada por: Esse algoritmo converge para uma hipótese h que representa um máximo de verossimilhança local
42 Agrupamento Conceptual Um grupo pode ser descrito em:
Agrupamento Conceptual Um grupo pode ser descrito em: extensão (enumeração dos seus membros) ou em compreensão (conjunto de propriedades que definem a pertinência de um elemento à um grupo) Agrupamento não conceptual fornece: apenas descrição em extensão de cada grupo. a obtenção dos grupos leva em conta apenas as descrições dos indivíduos. Agrupamento conceptual fornece: também a descrição em compreensão (intencional) de cada grupo. formação dos grupos levam em consideração também a qualidade da descrição em compreensão de cada grupo
43 Agrupamento Conceitual funciona em 2 fases: agregação: encontrar grupos de um conjunto de indivíduos segundo uma estrutura considerada e um ou mais critérios fixados caracterização: determinar uma descrição (conceito) de cada um dos grupos obtidos na fase de agregação Em aprendizagem de máquina caracterização = aprendizagem à partir de exemplos As 2 fases podem ser: simultâneas seqüenciais (na maioria dos casos)
44 Geração de k Agrupamentos em competição
45 Tipos de abordagens em Agrupamento Conceitual: 3 dimensões Estrutura do espaço de observação: partição, hierarquia, cobertura Algoritmo: incremental (Formação de Conceitos) ou batch (Descoberta de Conceitos) Linguagem de descrição (representação do conhecimento): Lógica de Atributos (ordem 0) Lógica de Predicados de 1a Ordem Lógica de predicados de 2a Ordem
46 Caracterização (descrição) dos grupos em lógica 0
Seja  um conjunto de observações descritas por p atributos (variáveis) y1, …, yp cujos domínios são D1, …, Dp. Um objeto simbólico a = [y1  A1]  …  [y1  Ap], onde Ai  Di, i  {1, …, p}, expressa a condição "atributo y1 toma seus valores em A1 e … e atributo yp toma os seus valores em Ap" Pode-se associar a a uma função fa: {1, 0} tal que fa() = 1  yi () Ai, i  {1, …, p},   A extensão de a é definida como ext (a) = {  / fa()=1}
47 Exemplo variáveis Domínios {azul, vermelho, verde} Cor Tamanho {grande, médio, pequeno} Forma {esfera, bloco, triângulo} Considere o seguinte objeto simbólico a = [Cor  {az,vm}] [Tam {g}] [Forma {e,b}] a é uma generalização de qualquer conjunto de objetos cuja cor é azul ou vermelho, cujo tamanho é grande e cuja forma é esfera ou bloco
48   esta na extensão de a (é membro de a)se fa()=1
49 Sejam os individuos 1 = [Cor  {az}] [Tam {g}] [Forma {e}] 2 = [Cor  {az}] [Tam {m}] [Forma {e}] 3 = [Cor  {az}] [Tam {p}] [Forma {b}] Três possíveis generalizações desses conjuntos por um objeto simbólico a = [Cor  {az}] [Tam {g,m,p}] [Forma {e,b}] b = [Cor  {az}] [Tam {g,m,p}] [Forma {e,b,t}] c = [Cor  {az,vm,vd}] [Tam {g,m,p}] [Forma {e,b,t}] c é mais geral do que b que é mais geral do que a a é maximamente especifico do conjunto de indivíduos acima.
50 Um objeto simbólico a é uma descrição discriminante de um conjunto 1 de indivíduos em relação à um outro conjunto 2 de indivíduos se: a é uma generalização de 1 e não existe  2 tal que fa()=1 Um objeto simbólico a é uma descrição maximamente discriminante de um conjunto 1 de indivíduos em relação à um outro conjunto 2 de indivíduos se: a é uma descrição discriminante de 1 em relação à 2 e não existe um outro objeto b i) que seja uma descrição discriminante de 1 em relação à 2 e ii) que seja mais geral do que a (b > a)
51 Exemplo Grupo 1 (G1) 1 = [Cor  {az}] [Tam {l}] [Forma {e}] Grupo 2 (G2) 1 = [Cor  {vm}] [Tam {l}] [Forma {b}] 1 = [Cor  {vm}] [Tam {l}] [Forma {t}] Descrições maximamente discriminantes de G1 em relação à G2 a = [Cor  {az,vd}] [Tam  {l,m,p}] [Forma  {e,b,t}] b = [Cor  {az,vm,vd}] [Tam {l,m,p}] [Forma  {e}] Descrições maximamente discriminantes de G2 em relação à G1 c = [Cor  {vm,vd}] [Tam  {l,m,p}] [Forma  {e,b,t}] d = [Cor  {az,vm,vd}] [Tam  {l,m,p}] [Forma  {b,t}]
52 Atribuição de descrições maximamente discriminantes aos Grupos 1 e 2
53 Algoritmo CLUSTER/2 Descoberta de Conceitos (em batch) Dois módulos
54 Módulo partição Formando Agrupamentos inicias Semente 1  Semente 2
55 seleção de k(2) sementes aleatoriamente
56 Atribuição dos objetos à cada descrição Dij obtendo as classes Cij
57 Obtendo descrições maximamente específicas de cada grupo
58 Inserindo o primeiro objetos da lista de exceções nos grupos e obtendo descrições maximamente específicas de cada grupo a1= [Cobertura do Corpo = {pelos, penas,pele úmida}]  [Cavidades do Coração = {3,4}]  [Temperatura do Corpo = {regulada,não regulada}]  [Fertilização = {interna}] Agrupamento A (G1 + Anfíbio-1) C1 C2 Agrupamento B (G2 + Anfíbio-1) b1= [Cobertura do Corpo = {pele seca}]  [Cavidades do Coração = {4 imperfeitas}]  [Temperatura do Corpo = {não regulada}]  [Fertilização = {interna}] a2= [Cobertura do Corpo = {pelos, penas}]  [Cavidades do Coração = {4}]  [Temperatura do Corpo = {regulada}]  [Fertilização = {interna}] b2= [Cobertura do Corpo = {pele úmida, pele seca}]  [Cavidades do Coração = {3,4 imperfeitas}]  [Temperatura do Corpo = {não regulada}]  [Fertilização = {interna}]
59 Avaliação dos Agrupamentos obtidos em função da qualidade das descrições
Critério: a) para cada par de descrições de agrupamentos diferentes calcula-se o número de variáveis cuja interseção é vazia; b) faz-se a soma para cada par; o agrupamento escolhido é aquele cuja soma é máxima  o Agrupamento B é selecionado O segundo objeto da lista de exceções é inserido no agrupamento B um processo semelhante ao descrito para a incorporação de anfíbio-1 é realizado O processo descrito deve ser realizado para todas as 9 combinações de descrições maximamente discriminantes Das 9 possibilidades, escolhe-se a melhor partição em dois grupos Em seguida, novas sementes são selecionadas e o processo continua
60 Módulo Hierarquico O módulo hierárquico construi uma árvore de classificação Nessa árvore os arcos representam as descrições e nós a extensão de cada grupo {mamífero, pássaro, réptil, anfíbio-1, anfíbio-2} [Cobertura do Corpo = {pelos, penas}]  [Cavidades do Coração = {4}]  [Temperatura do Corpo = {regulada}]  [Fertilização = {interna}] [Cobertura do Corpo = {pele úmida, pele seca}]  [Cavidades do Coração = {3,4 imperfeitas}]  [Temperatura do Corpo = {não regulada}]  [Fertilização = {interna, externa}] {mamífero, pássaro} {réptil,anfíbio-1,anfíbio-2}
61 Classificação politética
Construção de árvore de cima para baixo O módulo hierárquico usa o módulo partição como uma subrotina o módulo partição fornece partições de vários tamanhos (2, 3 e 4) e seleciona a melhor O módulo hierárquico construí um nível da árvore de cada vez A construção da árvore finaliza quando a qualidade da partição obtida no nível seguinte não é melhorada
62 IFCS ••• BCS GfKl CSNA JCS SFC Congressos Bianuais da IFCS
63 Referências Fisher, D.H. and Langley, P. W., " Methods of Conceptual Clustering and their relation to Numerical Taxonomy", Technical Report 85-26, University of California, Irvine, 1985 Fisher, D. H., " Knowledg Acquisition via Incremental Conceptual Clustering", Machine Leaning, Vol2, No. 2, pp , 1987 Guenoche, ª , "Generalization and Conceptual Classification: Indices and Algorithms", Proceedings of the Conference on Data Analysis, Learning symbolic and Numeric Knowledg, pp , INRIA, Antibes, 1989 Kodratoff, Y. and Ganascia, J., "Improving the Generalization Step in Learning," Chapter in the book, Machine Learning:An Artificial Intelligence Approach, R. S. Michalski, J.G. Carbonell and T.M. Mitchell (Eds.), TIOGA Publishing Co., PaloAlto, pp , 1983.