Aprendizado Através De Indução lógica De Conjunções E Disjunções

Aprendizado através de indução lógica de conjunções e disjunções

Eléia G. Mueller

Fábio M. Lopes

Universidade Federal do Paraná

Curso de Mestrado em Informática

Inteligência Artificial - 1999

1. Introdução 1

2. Indução de Conjunções Lógicas 2

2.1. Representação e uso de conjunções lógicas 2

2.2 - A tarefa de induzir conjunções lógicas 3

2.3 - Algoritmos para indução de conjunções lógicas 3

2.3.1 - Algoritmos EGS (Exaustivo Geral - Específico) 3

2.3.2 - Algoritmo HGS (heuristic general-to-specific) 6

2.3.3 - Algoritmo IGS 8

2.3.4 -Algoritmo IHC 10

3 - Indução de Disjunções Lógicas 13

3.1 - Representação e uso de disjunções lógicas 13

3.2 - A tarefa de induzir disjunções lógicas 14

3.3 - Algoritmos para indução de disjunções lógicas 15

3.3.1 - Aprendizado não incremental usando separate-and-conquer 15

3.3.2 - Aprendizado Incremental usando separate-and-conquer 18

3.3.3 - Indução de Listas de Decisão Usando Exceções 22

Conclusão 25

REFERÊNCIAS BIBLIOGRÁFICAS 27

1. Introdução

Atualmente, com o alto grau de automação na produção de dados na maioria das empresas, uma das principais dificuldades encontradas pelas mesmas é poder extrair informações úteis através destas bases de dados geradas automaticamente.

Aprendizado de máquina, um sub-campo de mineração de dados, vem justamente de encontro com esta questão. Baseado em paradigmas de representação de conhecimento em Inteligência Artificial (IA), combinado com teorias e algoritmos, extrai padrões e modelos que auxiliam na tomada de decisões.

Assim esta metodologia pode ser uma importante ferramenta em empresas, as quais possuem uma grande quantidade de dados, geralmente produzidas automaticamente, porém de difícil acesso às informações desejadas.

Em RICH (1993), podemos observar várias técnicas de aprendizado de máquina presentes na solução de problemas.

Segundo Nicoletti & Santos (1996), entre os vários paradigmas existentes para o aprendizado simbólico, tratado como área de pesquisa em Inteligência artificial, o chamado aprendizado indutivo baseado em exemplos é o que tem sido mais largamente pesquisado e o que tem mais contribuído efetivamente para a implementação de sistemas simbólicos de aprendizado de máquina. A partir de um conjunto de exemplos, conjunto treinamento, vários tipos de conceitos, ou regras de classificação, podem ser aprendidos.

Entre as várias aplicações destes aprendizados, podemos destacar sua importância entre outros ao diagnóstico de doenças, previsão de recorrência de tumores, estimativa de sobrevida de pacientes, previsão meteorológica, predição de novos compostos químicos, etc.

Assim o objetivo principal deste trabalho será fornecer uma visão geral sobre técnicas de indução, abordando especificamente a indução lógica de conjunções e disjunções. Desta forma, através dos algoritmos abordados sobre o assunto em LANGLEY (1996), tentamos fornecer ao leitor a essência dessas técnicas. Inicialmente apresentamos na seção 2 a indução lógica de conjunções e posteriormente a indução de disjunções lógicas, seção 3. Ao final, realizamos algumas considerações e conclusões a respeito dos algoritmos apresentas nas seções anteriores.

2. Indução de Conjunções Lógicas

2.1. Representação e uso de conjunções lógicas

Os algoritmos abordados nesta seção, segundo LANGLEY(1996), são projetados para encontrar a partir de um conjunto de dados de treinamento, ou seja, um conjunto de exemplos, vários tipos de conceitos ou regras de classificação. Esta descrição conjuntiva será de tal forma que todas as instâncias positivas do conjunto de treinamento serão cobertos por esta descrição, e nenhuma das instâncias negativas serão cobertas pela mesma. Elas poderão representar características Booleanas, valores de atributos nominais, valores de atributos numéricos, ou uma combinação dos mesmos. Nós iremos nos referir para cada componente da conjunção como uma condição.

Então a descrição (D) resultante a partir destes algoritmos, poderão ser utilizados para classificar novas instâncias, através de uma relação de casamento de D com a descrição da instância. Novamente, se a instância casa com todas as condições na descrição do conceito D, ela é nomeada como uma instância positiva; caso contrário é nomeada como negativa.

Considere um exemplo envolvendo um domínio com três atributos para a descrição da aparência de uma célula - o número de caudas (uma ou duas), a cor do corpo da célula (escura ou clara), e o número de núcleos (um ou dois). A Figura 1 mostra uma célula de um paciente doente (uma instância positiva do conceito), e duas células de pacientes saudáveis (instâncias negativas). Por exemplo, o caso positivo tem dois núcleos, duas caudas e cor escura, enquanto que o primeiro caso negativo tem um núcleo, duas caudas, e cor clara.

A Figura 2, descreve graficamente três conjunções que, quando combinado com uma lógica de casamento, são consistentes com as instâncias da Figura 1. Por exemplo, a célula esquerda da Figura 2, a qual não possui núcleo, corresponde a conjunção duas caudas ^ cor escura. Similarmente, a célula central, a que não possuiu coloração, especifica a conjunção dois núcleos ^ duas caudas. A descrição da direita, que inclui todos os três atributos, indica a conjunção mais específica, dois núcleos