View
109
Download
2
Category
Preview:
Citation preview
Natasha Correia Queiroz Lino (ncql@di.ufpe.br)
Agrupamento ConceitualAgrupamento Conceitual
Aprendizagem Não Supervisionada
Próximo
2
Anterior
ÍndiceÍndice
Introdução - Aprendizagem Tipos Aprendizagem Exemplo Inicial Agrupamento Tradicional x Agrupamento Conceitual Métodos e seus componentes
– Método Tradicional
– Método Conceitual
Resultados Conclusão dos resultados Alguns Sistemas de Agrupamento Conceitual (COBWEB)
Próximo
3
Anterior
AprendizagemAprendizagem
Michalski, 1986:
“Aprendizagem é construir ou modificar representações do que está sendo experienciado.”
Próximo
4
Anterior
Classificação dos Métodos de AprendizagemClassificação dos Métodos de Aprendizagem
CBR
Próximo
5
Anterior
Aprendizagem - TiposAprendizagem - Tipos
Aprendizagem Supervisionada– Dado um conjunto de exemplos pré-classificados, aprender uma
descrição geral que encapsula a informação contida nesses exemplos - e que pode ser usada para prever casos futuros
Aprendizagem Não Supervisionada– Dada uma coleção de dados não classificados, agrupá-los por
regularidades
Próximo
6
Anterior
Aprendizagem Não SupervisionadaAprendizagem Não Supervisionada
Aprendiz não recebe nenhuma informação explícita sobre a classificação dos exemplos de entrada
Informação está implícita
O objetivo do processo de aprendizagem é descobrir regularidades nos dados de entrada
Consiste em particionar instâncias em classes, baseada em alguma métrica de similaridade
(encontrar agrupamento das instâncias no espaço de instâncias)
Próximo
7
Anterior
Exemplo Inicial - Mesa de RestauranteExemplo Inicial - Mesa de Restaurante
Objetos:
•comida em prato, •salada, •utensílios, •sal,•pimenta, •guardanapos, •vaso com flores, •xícara de café
Próximo
8
Anterior
Exemplo Inicial - Mesa de RestauranteExemplo Inicial - Mesa de Restaurante
Possível classificação dada por uma pessoa:– Encadeamento de Inferências (conceito de comestível):
• Sal e pimenta são temperos
Temperos são usados para dar gosto a comida
Comida temperada é algo para ser comido
Coisas que são para serem comidas são comestíveis
Sal e pimenta são comestíveis
• Salada é vegetal
Vegetais são comida
Comida é algo para ser comido
Coisas que são para serem comidas são comestíveis
Salada é comestível
Próximo
9
Anterior
Exemplo Inicial - Mesa de RestauranteExemplo Inicial - Mesa de Restaurante
Possível classificação dada por uma pessoa (cont.):– Encadeamento de Inferências (conceito de comestível):
• Guardanapo não é comida
Guardanapo não é comestível
• Vaso com flores não é comida
Vaso com flores não é comestível
Problema: – Existem outras classificações que podem até ser hierárquicas
– Como decidir qual classificação é melhor ou mais apropriada?
Próximo
10
Anterior
Exemplo Inicial - Mesa de RestauranteExemplo Inicial - Mesa de Restaurante
Utensílios
Talher Recipiente
Garfo Faca Colher Taça Xícara Prato
Forma, Funcionalidade
Próximo
11
Anterior
Tipos de AgrupamentoTipos de Agrupamento
Agrupamento Tradicional
Agrupamento Conceitual
Próximo
12
Anterior
Agrupamento Tradicional - O que éAgrupamento Tradicional - O que é
Técnica tradicional
Construção de classificações significativas de objetos ou situações observadas
Conhecido como Taxonomia Numérica, pois envolve a produção de uma hierarquia de classe, usando medida matemática de similaridade entre as instâncias
Próximo
13
Anterior
Agrupamento Tradicional - DesvantagensAgrupamento Tradicional - Desvantagens
Algoritmos são incapazes de considerar as relações semânticas entre os atributos das instâncias ou conceitos globais que podem ter relevância na formação do esquema de classificação
A informação usada é apenas a que está contida nas instâncias
Geralmente inadequado
Próximo
14
Anterior
Agrupamento Conceitual - IdéiaAgrupamento Conceitual - Idéia
Introduzido inicialmente por R. S. Michalski - 1980
Um processo de construção de uma rede de conceitos
Caracteriza uma coleção de objetos com nós associados a conceitos, descrevendo classes de objetos e links associados às relações entre as classes
Próximo
15
Anterior
Agrupamento Conceitual - ExemploAgrupamento Conceitual - Exemplo
Considerando o exemplo:
Próximo
16
Anterior
Agrupamento Conceitual - ExemploAgrupamento Conceitual - Exemplo
Pessoas não agrupariam A e B juntos, mas sim dentro de dois losangos
Particionamento é feito usando o conceito de membro ao invés de distância
Os pontos são colocados no mesmo grupo se coletivamente eles representam o mesmo conceito– Isto é a base do agrupamento conceitual!
Próximo
17
Anterior
Agrupamento Conceitual - DefiniçãoAgrupamento Conceitual - Definição
Dado:– Um conjunto de objetos
– Um conjunto de atributos usados para caracterizar os objetos
– Um corpo de conhecimento adquirido - incluindo problemas de restrições, propriedades dos atributos, critérios para avaliação de qualidade da classificação construída
Encontrar:– Uma hierarquia de classes de objetos
• Cada nó deve formar um conceito coerente
– Compacto
– Facilmente representado em termos de uma definição ou regra que tenha uma interpretação natural para humanos
Próximo
18
Anterior
Agrupamento Conceitual - ExemploAgrupamento Conceitual - Exemplo
Descrição de animais:
Hierarquia de classificação produzida:
Nome Cobertura doCorpo
Cavidades doCoração
Temperaturado Corpo
Fertilização
mamífero pelos 4 regulada internapássaro penas 4 regulada interna
réptil pele seca 4 imperfeitas não regulada internaanfíbio pele úmida 3 não regulada externapeixe escamas 2 não regulada externa
Próximo
19
Anterior
Agrupamento Conceitual - ExemploAgrupamento Conceitual - Exemplo
Próximo
20
Anterior
Agrupamento - Métodos (Abordagens)Agrupamento - Métodos (Abordagens)
Baseados em Distâncias
Baseados em Probabilidades
Hierárquicos
Próximo
21
Anterior
Agrupamento - Método Tradicional x ConceitualAgrupamento - Método Tradicional x Conceitual
Método de Agrupamento Dinâmico (Tradicional)– Encontra classes iterativamente, aplicando alternadamente uma
função de representação e uma função de alocação, até que um ótimo local (do critério de optimalidade assumido) seja atingido.
Agrupamento Conceitual Conjuntivo (Conceitual)– Pode ser visto como um Agrupamento Dinâmico, onde classes
representam um forte conceito de ligação organizando uma coleção de objetos
Próximo
22
Anterior
Agrupamento DinâmicoAgrupamento Dinâmico - Algoritmo NUMTAX- Algoritmo NUMTAX
Dado um conjunto de objetos E, e um inteiro k, o método particiona E em k classes que são ótimos locais de acordo com um critério assumido.
Inicia-se com alguma representação inicial das k classes, escolhidas randomicamente
Uma sequência de iterações é executada para:– Encontrar a classe que melhor se ajusta às representações de
classes obtidas
– Encontrar a representação que melhor se ajusta às classes obtidas
Quando não há mais melhoras, o processo termina
Próximo
23
Anterior
Agrupamento Conceitual Conjuntivo - Algoritmo PAFAgrupamento Conceitual Conjuntivo - Algoritmo PAF
Dado um conjunto de objetos E, e um inteiro k (quantidade de classes); são selecionados k protótipos de E
Para cada protótipo é determinado um conjunto (star) de expressões que contenham este protótipo, e não contenham os demais
Redução das expressões contidas nos conjuntos (star) Para cada conjunto (star), uma expressão é selecionada de
forma que as expressões obtidas sejam mutuamente disjuntas, juntas contenham todos os dados, e otimizem um critério de optimalidade assumido.
(Algoritmo de busca )A*
Próximo
24
Anterior
Agrupamento Conceitual Conjuntivo - Algoritmo PAFAgrupamento Conceitual Conjuntivo - Algoritmo PAF
Para cada expressão é selecionado um novo protótipo, e é iniciada uma nova iteração do algoritmo. – Duas técnicas de seleção de protótipos são usadas:
• Protótipos são eventos centrais
• Protótipos são eventos de fronteiras
As classes obtidas são avaliadas de acordo com o critério de optimalidade . Se for a primeira iteração, as classes são armazenadas, caso contrário, só de forem melhores do que as anteriores.
O algoritmo termina, quando após um número especificado de iterações, não é produzida uma classificação melhor
Próximo
25
Anterior
Agrupamento - Componentes Agrupamento - Componentes
Componentes independentes de método:
– Objetos
– Atributos (variáveis)
– Codificação dos atributos (domínio das variáveis e medidas de escala)
– Princípio para agrupar objetos em classes
– Estrutura inter-classe
Próximo
26
Anterior
Agrupamento - ComponentesAgrupamento - Componentes
Componentes dependentes de método:
– Esquema de representação de classes
– Função de representação
– Função de alocação
– Critério de optimalidade de agrupamento
Próximo
27
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Objetos:
– Provém de um estudo experimental de algum fenômeno
– São descritos por algum conjunto de atributos (variáveis)
– Exemplo: Conjunto de microorganismos
Próximo
28
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Atributos (Variáveis):
– Nem todos os atributos são sempre relevantes para o problema de agrupamento
– A tarefa de detectar os atributos relevantes é outro problema
– Exemplo:
• Partes do corpo
• Manchas no corpo
• Textura
• Tipo de calda
Próximo
29
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Codificação dos atributos:
– Modelo de medida / Convenção utilizada
– Atributos podem ser medidos em diferentes escalas:
• Atributos qualitativos: nominal
• Atributos quantitativos: ordinal, intervalo, razão
– Exemplo:
• Partes do corpo (1 parte, 2 partes, muitas partes)
• Manchas no corpo (uma mancha, muitas manchas)
• Textura (em branco, listrada, quadriculada)
• Tipo de calda (nenhuma, única, múltipla)
Próximo
30
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Tabela:
Próximo
31
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Princípio para agrupar objetos em classes:
– Caracterização através de um conceito simples
– Medida de similaridade
• Usualmente uma medida de distância
– Medidas quantitativas (fórmulas)
– Medidas qualitativas (binária)
– Exemplo:
• Taxonomia Numérica (Agrupamento Tradicional):
– 18 técnicas diferentes determinadas pela combinação das medidas de similaridade usadas (NUMTAX)
• Agrupamento Conceitual Conjuntivo (Agrupamento Conceitual)
– De acordo com o algoritmo PAF
Próximo
32
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Medida de similaridade– Exemplos:
Minkowsky
(quantitativa)
Russel and Rao
(qualitativa)
d(X X ) = x - xp, q pi qi
i=1
n
1
d(X X ) = a
a + b + c + ep, q
Próximo
33
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Estrutura inter-classes:
– Baseada nas relações entre as classes
– Tipos de estruturas:
• Partição
• Sobreposição
• Hierárquica
• Bipolar
Próximo
34
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Estrutura inter-classes:– Exemplos:
Estrutura de Partição Estrutura de Sobreposição
Próximo
35
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Estrutura inter-classes:– Exemplos:
Estrutura Hierárquica Estrutura Bipolar
Próximo
36
Anterior
Agrupamento - Componentes IndependentesAgrupamento - Componentes Independentes
Estrutura inter-classes:– Estrutura para o exemplo dos microorganismos:
• Estrutura de partição
Próximo
37
Anterior
Agrupamento - Componentes DependentesAgrupamento - Componentes Dependentes
Esquema de representação de classes
Função de representação
Função de alocação
Critério de optimalidade de agrupamento
Próximo
38
Anterior
Agrupamento - Componentes DependentesAgrupamento - Componentes Dependentes
Esquema de representação de classes:– Construção matemática ou geométrica que caracteriza objetos na
classe
– Exemplos:
Objeto no centro de massa Os três objetos mais distantes Linha de menor inércia
Função de disitribuição normal Nós em uma árvore de classificação
Próximo
39
Anterior
Agrupamento - Componentes DependentesAgrupamento - Componentes Dependentes
Esquema de representação de classes (cont.):
– Agrupamento Conceitual Conjuntivo (utiliza dois esquemas):
• Objeto único (central ou extremo) - protótipo da classe
• Esquema final da classe - expressão
Próximo
40
Anterior
Agrupamento - Componentes DependentesAgrupamento - Componentes Dependentes
Função de representação:
– Determina a melhor representação para as classes de acordo com o critério de representação assumido
– Formalmente a função é um mapeamento:
Onde: é um conjunto de classes
é um conjunto de representações de classes
g C Lk k:{ } { }
{ }Ck
{ }Lk
Próximo
41
Anterior
Agrupamento - Componentes DependentesAgrupamento - Componentes Dependentes
Função de representação (g) - Agrupamento Conceitual Conjuntivo (cont):
– Procedure que, dado um conjunto de k classes, seleciona k protótipos para cada classe, e determina um conjunto de k expressões disjuntas, 1, 2, ..., k, tais que:
• A expressão i contém o protótipo ei,
• A união das expressões contém o conjunto completo de objetos
• Todos as k expressões juntas maximiza o critério de optimalidade do agrupamento
Próximo
42
Anterior
Agrupamento - Componentes DependentesAgrupamento - Componentes Dependentes
Função de alocação:
– É o inverso da função de representação
– Formalmente:
Função de alocação (f) - Agrupamento Conceitual Conjuntivo:
– Procedure que, dada uma representação consistindo de k expressões 1, 2, ..., k, forma um agrupamento Ck = {E1, E2, ..., Ek}, onde a classe Ei contém exemplos observados em i
f L Ck k:{ } { }
Próximo
43
Anterior
Agrupamento - Componentes DependentesAgrupamento - Componentes Dependentes
Critério de optimalidade de agrupamento:– Especifica as propriedades desejadas em uma classe
– Mede o ajuste entre as classes e as representações das classes
• Medida simples ou medida ponderada
• Formalmente pode ser definido como:
Critérios elementares - Agrupamento Conceitual Conjuntivo:• Ajuste entre as classes e os dados
• Diferenças inter-classes
• Dimensão essencial
• Simplicidade de representação das classes
DF : C } x {L } [0, 1]k k{
Próximo
44
Anterior
Resultados Obtidos - NUMTAXResultados Obtidos - NUMTAX
(Partes Corpo = 1) (Tipo Calda = 0 ou 1)
(Partes Corpo > 1) (Tipo Calda = 0)
[Tipo Calda > 1] [(Partes Corpo > 1) (Tipo Calda = 0, >1 )]
Próximo
45
Anterior
Resultados Obtidos - PAFResultados Obtidos - PAF
(Tipo Calda = 1) (Textura = branca ou listrada)
(Tipo Calda = 1) (Textura = branca ou listrada) (Partes Corpo = 1, 2 )
(Tipo Calda > 1)
Próximo
46
Anterior
Para a subjetividade humana as soluções mais comuns são:– 3 Classes (k=3):
• [Tipo de calda = nenhuma] x [Tipo de calda = única] x
[Tipo de calda = múltipla]
NUMTAX é mais arbitrário, complexo e possui disjunção
(Agrupamento Tradicional)
PAF corresponde mais aos conceitos humanos de classificação
(Agrupamento Conceitual Conjuntivo)
Conclusão dos ResultadosConclusão dos Resultados
Próximo
47
Anterior
Alguns Sistemas de Agrupamento ConceitualAlguns Sistemas de Agrupamento Conceitual
CLUSTER (Michalski - 1980)
CLUSTER/2 (Michalski)
UNIMEN (Lebowitz - 1987)
COBWEB (Fisher - 1987)
Próximo
48
Anterior
Sistema COBWEBSistema COBWEB
Baseado no princípio de que um bom agrupamento deve:– Minimizar a distância entre objetos em um grupo
(Similaridade inter-grupo)
– Maximizar a distância entre objetos de grupos diferentes
(Similaridade intra-grupo)
Objetivo do COBWEB:– Encontrar bom tradeoff!
Próximo
49
Anterior
Sistema COBWEBSistema COBWEB
Características:
– Função de avaliação heurística para guiar a busca
– Estrutura de Representação:
• Estrutura de hierárquica com representação de conceitos
– Esquemas de Classificação:
• Utilização de operadores
– Estratégias de Controle
Próximo
50
Anterior
ReferênciasReferências
Michalski, R. S., Stepp, R., and Diday, E., "A Recent Advance in Data Analysis: Clustering Objects into Classes Characterized by Conjunctive Concepts," Chapter in the book Progress in Pattern Recognition, Vol. 1, L. Kanal and A. Rosenfeld (Editors), North-Holland, pp. 33-55, 1981.
Michalski, R. S. and Stepp, R., "Learning from Observation: Conceptual Clustering," 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. 331-363, 1983.
Próximo
51
Anterior
ReferênciasReferências
Stepp, R. and Michalski, R. S., "Conceptual Clustering: Inventing Goal-Oriented Classifications of Structured Objects,” Reports of the Intelligent Systems Group, ISG 85-10, UIUCDCS-F-85-940, Department of Computer Science, University of Illinois, Urbana, February 1985.
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. 215-244, 1983.
Próximo
52
Anterior
ReferênciasReferências
Michalski, R.S. and Kaufman, K.A., "Data Mining and Knowledge Discovery: A Review of Issues and a Multistrategy Approach," Reports of the Machine Learning and Inference Laboratory, MLI 97-2, George Mason University, Fairfax, VA, 1997.
Próximo
53
Anterior
ReferênciasReferências
URLs:
– http://www.mli.gmu.edu/~sfischt/cluster2.html
– http://www.csd.abdn.ac.uk/~pedwards/CS5505/slides.html
– http://www.swi.psy.uva.nl/mlteach/courses/courses.htm
– http://yake.ecn.purdue.edu/~brodley/courses/695C/ overheads/overheads.html
Próximo
54
Anterior
Recommended