Agrupamento Conceitual
Aprendizagem Não Supervisionada
Natasha Correia Queiroz Lino ([email protected])
2
Í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)
Anterior
Próximo
3
Aprendizagem

Michalski, 1986:
“Aprendizagem é construir ou modificar representações do que está
sendo experienciado.”
Anterior
Próximo
4
Classificação dos Métodos de Aprendizagem
CBR
Anterior
Próximo
5
Aprendizagem - 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
Anterior
Próximo
6
Aprendizagem 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)
Anterior
Próximo
7
Exemplo Inicial - Mesa de Restaurante
Objetos:
•comida em prato,
•salada,
•utensílios,
•sal,
•pimenta,
•guardanapos,
•vaso com flores,
•xícara de café
Anterior
Próximo
8
Exemplo 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
Anterior
Próximo
9
Exemplo 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?
Anterior
Próximo
10
Exemplo Inicial - Mesa de Restaurante
Utensílios
Talher
Garfo

Faca
Forma, Funcionalidade
Anterior
Próximo
Colher
Recipiente
Taça
Xícara
Prato
11
Tipos de Agrupamento
Anterior

Agrupamento Tradicional

Agrupamento Conceitual
Próximo
12
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
Anterior
Próximo
13
Agrupamento 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
Anterior
Próximo
14
Agrupamento 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
Anterior
Próximo
15
Agrupamento Conceitual - Exemplo

Considerando o exemplo:
Anterior
Próximo
16
Agrupamento 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!
Anterior
Próximo
17
Agrupamento 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
Anterior
Próximo
18
Agrupamento Conceitual - Exemplo

Descrição de animais:
Nome
mamífero
pássaro
réptil
anfíbio
peixe

Cobertura do
Corpo
pelos
penas
pele seca
pele úmida
escamas
Hierarquia de
classificação produzida:
Anterior
Próximo
Cavidades do
Coração
4
4
4 imperfeitas
3
2
Temperatura
do Corpo
regulada
regulada
não regulada
não regulada
não regulada
Fertilização
interna
interna
interna
externa
externa
19
Agrupamento Conceitual - Exemplo
Anterior
Próximo
20
Agrupamento - Métodos (Abordagens)

Baseados em Distâncias

Baseados em Probabilidades

Hierárquicos
Anterior
Próximo
21
Agrupamento - 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
Anterior
Próximo
22
Agrupamento Dinâmico - 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
Anterior
Próximo
23
Agrupamento 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 * )
Anterior
Próximo
24
Agrupamento 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
Anterior
Próximo
25
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
Anterior
Próximo
26
Agrupamento - 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
Anterior
Próximo
27
Agrupamento - 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
Anterior
Próximo
28
Agrupamento - 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
Anterior
Próximo
29
Agrupamento - 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
• Manchas no corpo
• Textura
• Tipo de calda
Anterior
Próximo
(1 parte, 2 partes, muitas partes)
(uma mancha, muitas manchas)
(em branco, listrada, quadriculada)
(nenhuma, única, múltipla)
30
Agrupamento - Componentes Independentes

Tabela:
Anterior
Próximo
31
Agrupamento - 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
Anterior
Próximo
32
Agrupamento - Componentes Independentes

Medida de similaridade
– Exemplos:
Minkowsky d(Xp, Xq) =
(quantitativa)
1

a
d(Xp, Xq) =
a +b+c+e
Russel and Rao
(qualitativa)
Anterior
 n
 xpi - xqi
 i=1

Próximo





33
Agrupamento - Componentes Independentes

Estrutura inter-classes:
– Baseada nas relações entre as classes
– Tipos de estruturas:
• Partição
• Sobreposição
• Hierárquica
• Bipolar
Anterior
Próximo
34
Agrupamento - Componentes Independentes

Estrutura inter-classes:
– Exemplos:
Estrutura de Partição
Anterior
Próximo
Estrutura de Sobreposição
35
Agrupamento - Componentes Independentes

Estrutura inter-classes:
– Exemplos:
Estrutura Hierárquica
Anterior
Próximo
Estrutura Bipolar
36
Agrupamento - Componentes Independentes

Estrutura inter-classes:
– Estrutura para o exemplo dos microorganismos:
• Estrutura de partição
Anterior
Próximo
37
Agrupamento - Componentes Dependentes

Esquema de representação de classes

Função de representação

Função de alocação

Critério de optimalidade de agrupamento
Anterior
Próximo
38
Agrupamento - 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
Função de disitribuição normal
Anterior
Próximo
Linha de menor inércia
Nós em uma árvore de classificação
39
Agrupamento - 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
Anterior
Próximo
40
Agrupamento - 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:
g:{Ck }  {Lk }
{C k } é um conjunto de classes
{Lk } é um conjunto de representações de classes
Anterior
Próximo
41
Agrupamento - 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
Anterior
Próximo
42
Agrupamento - Componentes Dependentes

Função de alocação:
– É o inverso da função de representação
f :{L }  {C }
k
– Formalmente:

k
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
Anterior
Próximo
43
Agrupamento - 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:
DF : {C } x {L }  [0, 1]
k

k
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
Anterior
Próximo
44
Resultados 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 )]
Anterior
Próximo
45
Resultados Obtidos - PAF
(Tipo Calda = 1) 
(Textura = branca ou
listrada)
(Tipo Calda = 1) 
(Textura = branca ou
listrada)

(Partes Corpo = 1, 2 )
(Tipo Calda > 1)
Anterior
Próximo
46
Conclusão dos Resultados

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)
Anterior
Próximo
47
Alguns Sistemas de Agrupamento Conceitual

CLUSTER
(Michalski - 1980)

CLUSTER/2
(Michalski)

UNIMEN
(Lebowitz - 1987)

COBWEB
(Fisher - 1987)
Anterior
Próximo
48
Sistema 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!
Anterior
Próximo
49
Sistema 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
Anterior
Próximo
50
Referê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.
Anterior
Próximo
51
Referê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.
Anterior
Próximo
52
Referê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.
Anterior
Próximo
53
Referê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
Anterior
Próximo
54
Anterior
Próximo