Introdução à Classificação Conceitual
Prof. Francisco de A. T. de Carvalho
[email protected]
Agrupamento (Clustering)
Forma de aprendizagem de máquina não supervisionada
Dado:
Um conjunto de objetos 
alguns critérios de agrupamento
Objetivo:
Formar (encontrar) grupos (clusters) C1, C2, …,
tal que o agrupamento obtido (ie, conjunto de grupos)
é considerado de alta qualidade (talvez não otimo)
em relação à qualidade dos critérios
Ck,
Os metodos usuais de agrupamento são conhecidas como
Taxinomia Numérica
Em Taxonomia Numerica, um objeto (individuo, observação)
 é descrito por p variáveis y1, yc, , yp
 = (y1(), y2(), , yp())
Uma variável y (ou descritor) é uma função
y: D
 é o conjunto de observações
y()
D é o domínio da variável y
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)
Tabelas individuos  variáveis
Nome
mamífero
pássaro
réptil
anfíbio
peixe
Cobertura do
Corpo
pelos
penas
pele seca
pele úmida
escamas
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
Taxonomia Numerica:
formar (encontrar) grupos (clusters) C1, C2, …, Ck,
tal que dissimilaridade entre os objetos:
de um mesmo grupo tende a ser minimizada
de grupos diferentes tende à ser maximizada
Um índice de dissimilaridade d é uma função
d: R+
(, ’) d(, ’)
que satisfaz as seguintes propriedades
a) , d (, ) = 0
b)  (, ’)  , d(, ’) = d(’, )
(simetria)
Exemplos de índices de dissimilaridade
a) Tabelas de variáveis quantitativas
1
 p
 
d (  a , b )   y j (  a )  y j (  b )  ,  1
 j 1

b) Tabelas de variáveis binárias
a
b
1
0
1
0
x
y
w
z
yz
d (  a ,b ) 
x yzw
Tipos de espaços de classificação (ie, estrutura a priori do espaço das
observações)
Seja  um conjunto de indivíduos à agrupar
Partição
Uma partição de  é um conjunto de subconjuntos não vazios P = (P1, , Pk) de
interseção vazia dois a dois e cuja união forma 
a) l  {1, , k}, Pl  
b) l,m  {1, , k}, l  m, Pl  Pm = 
c) l Pl = 
Partição
Observações
P1
*
*
*
*
P2
*
*
*
*
*
*
*
*
*
*
P3
Cobertura
Uma cobertura de  é um conjunto de subconjuntos não vazios P = (P1, , Pk)
cuja união forma 
a) l  {1, , k}, Pl  
b) l Pl = 
*
*
P1
*
*
*
*
P3
*
*
*
*
*
P2
*
*
*
Hierarquia
Seja H um conjunto de subconjuntos não vazios de . H é uma hierarquia se
a)   H;
b)    , {}  H
c)  h, h’  H, tem-se: h  h’ =  ou h  h’ ou h’  h
*7
*6
*
*5
*4
*
*
*
*2
*3
*1
*
*
*
1
3
2
4 5
6
7
Piramide
Seja P um conjunto de subconjuntos não vazios de de . P é uma piramide se
a)   P;
b)    , {}  P
c)  h, h’  P, tem-se: h  h’ =  ou h  h’  P
d) Existe uma ordem  tal que todo elemento de P seja um intervalo de 
*7
*6
*5
*4
*3
*2
*1
1
3
2
4 5
6
7
Em Taxonomia Numerica distingue-se tres grupos de métodos
Técnicas de Otimização
Objetivo: obter partição. Número de grupos sempre fornecido pelo usuário
Técnicas hierarquicas
Objetivo: obter uma hierarquia (ou uma piramide)
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.
Abordagens para classificação

Agrupamento conceitual (intencional)
• simbólico
• híbrido (redes bayesianas)
Nebuloso (lógica fuzzy)
 Conexionista (redes neurais)
 Evolucionista (algoritmos genéticos)
 Estatística

IFCS
•••
JCS
BCS
SFC
GfKl CSNA
Congressos Bianuais da IFCS
Congressos anuais das Associações Nacionais
http://edfu.lis.uiuc.edu/~class/ifcs
Agrupamento Conceitual
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 conceitual fornece:
apenas descrição em extensão de cada grupo.
obtenção dos grupos leva em conta apenas as descrições dos individuos.
Agrupamento conceitual 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
Agrupamento Conceitual funciona em 2 fases:
agregação: encontrar grupos de um conjunto de individuos 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 caracterização = aprendizagem à partir de exemplos
As 2 fases podem ser:
simultaneas
sequênciadas (na maioria dos casos)
Iniciar com  (Conjunto de Individuos)
Geração de k Agrupamentos
em competição
Agrupamento 1 •••
{C11, …, C1m1}
Agrupamento k
{Ck1, …, Ckmk}
Iniciar com um
Agrupamento
•••
Geração de descrições
conceituais em competição
par o Agrupamento
{D1(C1), ... D1(C1m1) ... {Dn(C1), ... Dn(C1m1)
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):
Logica de Atributos (ordem 0)
Logica de Predicados de 1a Ordem
Logica de predicados de 2a Ordem
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 dominios 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 uma função f: {1, 0} tal que
fa() = 1  yi () Ai, i  {1, …, p},  
A extensão de a é definida como ext (a) = {  / fa()=1}
Exemplo
variaveis
Dominios
Cor
Tamanho
{azul, verm, verde}
{grande, medio, pequeno}
Forma
{esfera, bloco, triangulo}
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
Da mesma forma,   esta na extensão de a (é membro de a) se
fa()=1, isto é, se sua cor é azul ou vermelha, seu tamanho é grande e sua
forma é esfera ou bloco
Dizemos que um objeto simbolico a é uma generalização de um conjunto de
individuos  se  , fa()=1
Sejam dois objetos simbólicos a = i [yi  Ai] e b = i [yi  Bi]. Diz-se que b <
a se Bi  Ai i. Nesse caso diz-se que a é mais geral do que b
e b é menos geral do que a
Diz-se que um objeto simbólico a é maximamente especifico de um conjunto
de indivíduos  se a é uma generalização de  e não existe um outro objeto
simbólico b generalização de  tal que b < a
Sejam os individuos
1 = [Cor  {az}] [Tam {g}] [Forma {e}]
2 = [Cor  {az}] [Tam {m}] [Forma {e}]
3 = [Cor  {az}] [Tam {p}] [Forma {b}]
Tres possíveis generalizações desses conjuntos pour um objeto simbolico
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.
Um objeto simbolico a é uma descrição discriminante de um conjunto 1 de
individuos em relação à um outro conjunto 2 de individuos se a é uma
generalização de 1 e não existe  2 tal que fa()=1
Um objeto simbólico a é uma descrição maximalmente 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 a) que seja uma descrição discriminante de 1 em relação à 2; b) que
seja mais geral do que a (b > a)
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 maximalmente 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 maximalmente 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}]
Atribuição de descrições maximamente discriminantes aos Grupos 1 e 2
Grupo1
Grupo 2
b = …[Forma {e}]
d = …[Forma {b,t}]
Descrições
a = [Cor  {az,vd}] …
c = [Cor  {vm,vd}] …
não disjuntas
a = [Cor  {az,vd}] …
d = …[Forma {b,t}]
b = …[Forma {e}]
c = [Cor  {vm,vd}] …
Descrições
disjuntas
Em geral conjuntos disjuntos da mesma variável implicarão em descrições
maximamente discriminantes de um grupo em relação à outros grupos
Algoritmo CLUSTER/2


Descoberta de Conceitos (em batch)
Dois módulos
•
•
Partição
Hieraráquico
Exemplo
Nome
mamífero
pássaro
réptil
Anfíbio-1
Anfibio-2
Cobertura do
Corpo
pelos
penas
pele seca
pele úmida
Pele-úmida
Cavidades do
Coração
4
4
4 imperfeitas
3
3
Temperatura
do Corpo
regulada
regulada
não regulada
não regulada
não regulada
Fertilização
interna
interna
interna
interna
externa
Módulo partição

Formando Agrupamentos inicias
Semente 1
D11
C11
Semente 2
D1 … D
1n1 D2
D2 … D
2n2
2
1
1
C12 … C1n1 C C21 … C
21
2n2

Semente k
 Encontrar descrições
maximamente discriminantes
 Atribuir os objetos à cada
descrição Dij obtendo as
classes Cij
•
seleção de k(2) sementes aleatoriamente
Nome
Semente 1
Semente 2
mamífero
réptil
Cobertura do
Corpo
pelos
pele seca
Cavidades do
Coração
4
4 imperfeitas
Temperatura
do Corpo
regulada
não regulada
Fertilização
interna
interna
encontrar descrições maximamente discriminantes de cada um dos k (2)
grupos à partir das sementes
Semente 1
Semente 2
a1=[Cobertura do Corpo={pelos,
penas, pele úmida}]
b1=[Cobertura do Corpo={penas,
pele seca, pele úmida}]
a2= [Cavidades do Coração =
{3, 4}]
a3= [Temperatura do Corpo=
{regulada}]
b2= [Cavidades do Coração
= {3, 4 imperfeitas}]
b3= [Temperatura do Corpo=
{não regulada}]
•
Atribuição dos objetos à cada descrição Dij obtendo as classes Cij
Semente 1
Semente 2
a2= [Cavidades do Coração =
{3, 4}]
b2= [Cavidades do Coração
= {3, 4 imperfeitas}]
G1=Ext(a2)={Mamífero,
Pássaro, Anfíbio-1, Anfíbio-2}
G2=Ext(a2)={Réptil, Anfíbio-1,
Anfíbio-2}
Obtendo descrições dos grupos
Tornando os grupos disjuntos
G1
G1={Mamífero, Pássaro}
G2
G2={Réptil}
Lista de exceções
{Anfíbio-1, Anfíbio-2}
•
Obtendo descrições maximamente específicas de cada grupo
G1 = {Mamífero, Pássaro}
a2= [Cobertura do Corpo =
{pelos, penas}]  [Cavidades do
Coração = {4}]  [Temperatura
do Corpo = {regulada}] 
[Fertilização = {interna}]
G2 = {Réptil}
b2= [Cobertura do Corpo = {pele
seca}]  [Cavidades do Coração
= {4 imperfeitas}] 
[Temperatura do Corpo = {não
regulada}]  [Fertilização =
{interna}]
Inserindo o primeiro objetos da lista de exceções nos grupos e obtendo
descrições maximamente específicas de cada grupo
C1
C2
Agrupamento A (G1 + Anfíbio-1)
Agrupamento B (G2 + Anfíbio-1)
a1= [Cobertura do Corpo =
{pelos, penas,pele úmida}] 
[Cavidades do Coração = {3,4}]
 [Temperatura do Corpo =
{regulada,não regulada}] 
[Fertilização = {interna}]
a2= [Cobertura do Corpo =
{pelos, penas}]  [Cavidades do
Coração = {4}]  [Temperatura
do Corpo = {regulada}] 
[Fertilização = {interna}]
b1= [Cobertura do Corpo = {pele
seca}]  [Cavidades do Coração
= {4 imperfeitas}] 
[Temperatura do Corpo = {não
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}]
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 é
relizado
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
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}]
{mamífero, pássaro}
[Cobertura do Corpo = {pele úmida,
pele seca}]  [Cavidades do Coração =
{3,4 imperfeitas}]  [Temperatura do
Corpo = {não regulada}] 
[Fertilização = {interna, externa}]
{réptil,anfíbio-1,anfíbio-2}






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 construi 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
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. 139-172, 1987
 Guenoche, ª , “Generalization and Conceptual Classification: Indices and
Algorithms”, Proceedings of the Conference on Data Analysis, Learning
symbolic and Numeric Knowledg, pp. 503-510, 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. 215-244, 1983.





Lebowitz, M., “Experiments with Incremental Concept Formulation:
UNIMEN”, Machine Learning, Vol. 2, No. 2, pp. 103-138, 1987.
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.
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.