Knowledge Acquisition Via
Incrementa Conceptual Clustering
DOUGLAS H. FISHER
Machine Learning 2: 139-172, 1987
Apresentação: Mário Machado e Otavio Acosta
Sumário


Background
Cobweb


Utilidade de Categoria
Operadores





Inclusão de objeto em cluster existente;
Criação de novo cluster
Intercalação
Divisão
Avaliação do Cobweb
2
Background

Clusterização Conceitual


Paradigma para aprendizagem de máquina que se
distingue das demais pela geração de uma descrição
de conceito para cada classe gerada. A maioria
destes métodos (incluindo o COBWEB) são capazes
de gerar estruturas de categorias hierarquicas.
Fisher caracteriza o processo de aprendizagem
como um processo de busca, no qual o espaço
de possíveis modelos de representação é
percorrido em busca daquele que se ajuste
melhor aos dados de entrada.
3
Background


De maneira geral, os métodos de busca
podem ser caracterizados pelo mecanismo
de controle da busca (exaustivo ou
heurístico) e pela direção da busca
(generalização ou especialização).
Quanto ao uso das entradas, os sistemas
podem ser não-incrementais (empregando
todas as entradas desde o princípio), ou
incrementais (assimilando um fluxo de
objetos, um por vez).
4
COBWEB


COBWEB é um sistema de clusterização
hierárquica conceitual. Ele executa um
processo de subida de encosta através de
um espaço de esquemas de classificação
hierárquica usando operadores que permitem
deslocamento bidirecional neste espaço.
COBWEB incorpora objetos em uma árvore
de classificação de forma incremental, onde
cada nó é um conceito probabilístico que
representa uma classe (ou agregado) de
objetos.
5
COBWEB – Utilidade de
Categoria


Para que possa aplicar a subida de encosta,
o COBWEB emprega uma heurística
chamada “utilidade de categoria”. Esta
heurística foi criada como um meio de
predizer o nível básico em hierarquias de
classificação humanas.
De acordo com Fisher, utilidade de categoria
é um tradeoff entre a similaridade intraclasse e a dissimilaridade inter-classe dos
objetos.
6
COBWEB – Utilidade de
Categoria



Objetos são definidos por pares atributo-valor
(restrito a valores nominais).
Similaridade intra-classe é refletida por
probabilidades condicionais na forma P(Ai=Vij|Ck),
onde Ai=Vij é um par atributo-valor e Ck uma classe.
Quanto maior esta probabilidade, maior a proporção
de membros da classe compartilhando este valor de
atributo, e mais previsível ele é para os membros
desta classe.
7
COBWEB – Utilidade de
Categoria



Dissimilaridade inter-classe é uma função de
P(Ck|Ai=Vij).
Quanto maior esta probabilidade, menor o
número de objetos em classes contrastantes que
compartilham este mesmo valor para o atributo,
e mais preditivo este valor é para esta classe.
Estas probabilidades são disposições de valores
individuais, mas elas podem ser combinadas
para dar uma medida aproximada da qualidade
da partição, onde uma partição é um conjunto de
classes de objetos mutuamente exclusivos (C1,
C2, ... Cn)
8
COBWEB – Utilidade de
Categoria


A probabilidade P(Ai=Vij) pondera a importância
dos valores individuais, fazendo com que
valores mais freqüentes tenham mais
importância.
De acordo com Fisher, Gluck e Corter definem
utilidade de categoria como o incremento no
número esperado de valores de atributo que
podem ser adivinhados corretamente, dada uma
partição, sobre o numero esperado de palpites
sem tal conhecimento. Formalmente, temos:
9
COBWEB – Utilidade de
Categoria
Utilidade de Categoria
10
COBWEB – Representação de
Conceitos


O mecanismo de representação de conceitos
pelo COBWEB é baseado no
armazenamento dos valores de atributos e
suas respectivas probabilidades (tal forma de
representação é denominada conceito
probabilístico).
As probabilidades de valor de atributo são
computadas a partir do número de objetos
que apresentam aquele valor para o atributo,
dividido pelo número total de objetos.
11
COBWEB – Representação de
Conceitos


No COBWEB, um conceito probabilístico etiqueta
cada nó na árvore de classifcação e sumariza os
objetos classificados sob o nó. Árvores de conceitos
probabilísticos são, diferentemente de redes
discriminatórias ou árvores de decisão no sentido em
que descritores probabilísticos (e não lógicos)
etiquetam nós (e não arcos) da árvore.
Classificação usando uma árvore de conceitos
probabilística é feita usando uma função de matching
parcial para descer a árvore pelo caminho dos nós
com "melhor casamento".
12
COBWEB – Exemplo
13
COBWEB – Operadores

Para a incorporação de um novo objeto na
árvore de classificação gerada, cada novo
objeto passa por um processo no qual
percorre um dado caminho na árvore,
atualizando contagens no meio do
caminho e executando UM dos possíveis
operadores a seguir em cada nível.
14
COBWEB – Operadores

Os operadores utilizados pelo COBWEB são:





Classificação de um objeto com relação a uma
dada classe;
Criação de uma nova classe;
Combinação de duas classes em uma só;
Divisão de uma classe em k classes.
A estratégia de busca emergente da
aplicação destes operadores é uma subida
de encosta no espaço de árvores de
classificação.
15
COBWEB – Colocação do
Objeto em uma Dada Classe

Esta é a maneira mais fácil de atualizar uma
árvore de classificação. A partição que
resulta da adição do objeto a uma dada
classe é avaliada usando utilidade de
categoria. O nó que resultar na melhor
partição é identificado como o melhor
hospedeiro existente para o novo objeto.
16
COBWEB - Criação de uma
Nova Classe


Ainda, é avaliado o que gera a melhor partição, se
é a introdução do novo objeto em um nó existente
ou a criação de um novo nó.
Assim, a qualidade da partição resultante da
colocação de um objeto no melhor hospedeiro é
comparada com a partição resultante da criação de
um novo conjunto unitário contendo o objeto.
Dependendo de qual partição é melhor com
respeito a utilidade de categoria, o objeto é
colocado na melhor classe existente ou uma nova
classe é criada.
17
COBWEB - Merging & Splitting



Os dois operadores vistos anteriormente têm o
defeito de ser sensíveis ao ordenamento dos dados.
Para evitar que isto ocorra, COBWEB disponibiliza
outros dois operadores, para combinação e divisão
de nós.
A combinação consiste na criação de um novo nó, e
na tomada de 2 (de n) nós de um nível, com a soma
as contagens de atributo-valor dos nós sendo
combinados. A seguir, os nós originais são
adicionados como filhos do novo nó.
18
COBWEB - Merging & Splitting

Embora possa ser aplicada todos os pares
de nós possíveis, isto seria desnecessário e
excessivamente custoso. Desta forma,
quando um objeto é incorporado, apenas os
dois melhores hospedeiros (indicados pela
utilidade de categoria) são considerados para
merging.
19
COBWEB - Merging & Splitting



No splitting, o melhoramento na qualidade da
partição é obtido a partir da remoção de um nó e
promoção de seus nós filhos.
Dada uma partição (com n nós), a remoção de um
de seus filhos resultará em uma partição com n+m1 nós (considerando como “m” o número de filhos
do nó removido.
Merging e splitting são aproximadamente inversos
um do outro, permitindo ao COBWEB um
movimento bidirecional no espaço de possíveis
hierarquias.
20
COBWEB - Merging & Splitting


Geralmente, o merging é acionado para
desfazer os efeitos de um splitting anterior,
caso necessário, e vice-versa.
Fisher cita ainda um quinto operador, de
promoção, empregado para promover um nó
sem a remoção do nó-mãe deste.
21
COBWEB - Algoritmo
FUNCTION COBWEB (Object, Root { of a classification tree })
1) Update counts of the Root
2) IF Root is a leaf
THEN Return the expanded leaf to accommodate the new object
ELSE Find that child of Root that best hosts Object and
perform one of the following
a) Consider creating a new class and do so if appropriate
b) Consider node merging and do so if appropriate and
call COBWEB (Object, Merged node)
c) Consider node splitting and do so if appropriate and
call COBWEB (Object, Root)
d) IF none of the above (a, b, or c) were performed
THEN call COBWEB (Object, Best child of Root)
22
COBWEB - Avaliação

A avaliação do COBWEB é baseada em um
modelo de aprendizagem (Dietterich).
23
COBWEB - Avaliação

Árvore Classificação  Base de
Conhecimento

Utilidade de adquirir conhecimento para
inferências  Tarefa de Desempenho

Eficácia na aprendizagem incremental 
Ambiente
24
COBWEB – Árvore de Classificação

A partir de uma seqüência de objetos,
COBWEB cria uma árvore de classificação
que resume e organiza os objetos.

Ex.: dada a descrição de animais, o sistema
forma uma árvore com conceitos probabilísticos
para cada nodo.
25
COBWEB – Árvore de Classificação

Exemplo: U.S. Senate



14 atributos para voto
2 possibilidades para cada atributo (sim/não)
afiliação de partidos descartada
[P(predictable), P(predictive)]
26
COBWEB – Árvore de Classificação

COBWEB faz uma abordagem diferente para
a identificação de “valores normativos”,
observando o tradeoff entre valores de
predição e previsibilidade.

Um valor só é considerado normativo com a
condição de ser independente de outros
valores atributo.
27
COBWEB – Árvore de Classificação

Exemplo: pragas em soja



47 históricos de casos de pragas
cada caso é descrito por 35 atributos
4 classificadas de pragas são classificadas pelos
dados, porém não incluídas no experimento
28
COBWEB – Árvore de Classificação

Após a execução do experimento às 4
classes são “redescobertas”
29
COBWEB – Árvore de Classificação

Valores necessários e valores suficientes

Ex.:


P(valor|Charcoal Rot = 1.0)  valor necessário
P(Charcoal Rot|valor = 1.0)  valor suficiente
Classes com valores necessários e suficientes
30
COBWEB – Classificação por Inferência

Uma característica do COBWEB é a criação
de inferências.

Para isso o sistema dá preferência para
categorias que podem ser preditivas.
31
COBWEB – Classificação por Inferência

Para avaliação foi utilizado o domínio das
“Pragas da Soja”

A doença diagnosticada, por determinado
caso, foi inserido como o 36o atributo. Porém
na construção da árvore de classificação ele
não foi utilizado para classificar os objetos
(apenas no treinamento).
32
COBWEB – Classificação por Inferência

Após algumas instâncias, os casos restantes
que ainda não tinham sido analisados foram
classificados corretamente, de acordo com o
diagnóstico.

O objetivo do experimento era provar se a
inserção do diagnóstico prévio no conjunto
de treinamento iria aprimorar a inferência do
conjunto de teste para a classificação.
33
COBWEB – Classificação por Inferência
34
COBWEB – Sistema Incremental

COBWEB não adota um sistema somente
aglomerativo ou divisivo durante sua
clusterização. (Splitting e Merging)

Avaliação de sistemas incrementais:



Custo de incorporar uma instância
Qualidade da árvore de classificação
Número de objetos para estabilidade
35
COBWEB – Sistema Incremental

Custo de incorporar uma nova instância é
definido por:
cost = O (B2 logB n x AV)
B  ramificação média
n  número de objetos já classificados
A  número de atributos
V  média do número de valores por atributo
36
COBWEB – Considerações Finais

COBWEB consiste em um sistema de
clusterização incremental, econômico e
robusto.

As classificações produzidas pelo COBWEB
são instrumentos eficazes para a inferência.
37
COBWEB – Considerações Finais

Mesmo utilizando uma função de avaliação
consistente,
dando
preferência
a
categorização humana, não deve ser
considerado como um modelo cognitivo, mas
como um método de agrupamento.
38
COBWEB – Trabalhos Futuros

Valores numéricos

Valores estruturados

Estratégia Hill-Climbing
39
COBWEB
WEKA
40
COBWEB
Dúvidas?
- FIM -
41