Knowledge Acquisition Via Incrementa Conceptual Clustering DOUGLAS H. FISHER Machine Learning 2: 139-172, 1987 Apresentação: Mário Machado e Otavio Acosta

Knowledge Acquisition Via Incrementa Conceptual Clustering

DOUGLAS H. FISHER

Machine Learning 2: 139-172, 1987

Apresentação: Mário Machado e Otavio Acosta

2

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

3

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.

4

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).

5

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.

6

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 intra-classe e a dissimilaridade inter-classe dos objetos.

7


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.

8

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)

9


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:

10


Utilidade de Categoria

11

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.

12

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".

13

COBWEB – Exemplo

14

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.

15

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.

16

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.

17

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.

18

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ó.

19


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.

20


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+m-1 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.

21


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.

22

COBWEB - Algoritmo

FUNCTION COBWEB (Object, Root { of a classification tree })1) Update counts of the Root2) 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)

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

Exemplo: U.S. Senate 14 atributos para voto 2 possibilidades para cada atributo (sim/não) afiliação de partidos descartada

26


[P(predictable), P(predictive)]

27


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.

28


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

Após a execução do experimento às 4 classes são “redescobertas”

29


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

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


33


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.

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

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 – Sistema Incremental

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

Valores numéricos

Valores estruturados

Estratégia Hill-Climbing

39

COBWEB – Trabalhos Futuros

COBWEB

WEKA

40

COBWEB

Dúvidas?

- FIM -

41

Documents

Knowledge Acquisition Via Incrementa Conceptual Clustering DOUGLAS H. FISHER Machine Learning 2: 139-172, 1987 Apresentação: Mário Machado e Otavio Acosta