Quarto Trabalho de Inteligência Artificial / Sistemas Inteligentes

Entrega: 07/06/2015

10 de Maio de 2015

Árvores de Decisão

Usando como base o material disponível nas seções 18.1 a 18.3 do livro texto, Artificial Intelligence: a Modern Approach, de Peter Norvig e Stuart Russell (3ed), implemente um algoritmo para indução de árvores de decisão (o ID3, mostrado no livro, na Figura 18.5), utilizando como função para seleção do nó da árvore, o ganho de informação (definido na página 704).

A entrada para o seu programa é um conjunto de exemplos (observações) com atributos e valores para os atributos, incluindo uma variável de classe. A saída do seu programa deve estar no seguinte formato:

<attribute>
    value1:
        <attribute>
            value1: class1 (counter1)
            value2: class2 (counter2)
    value2: class3 (counter3)
    value3:
        <attribute>
            value1:
               <attribute>
                   value1: class4 (counter4)
                   value2: class2 (counter5)
            value2: class3 (counter6)

Onde, attribute indica o atributo escolhido para estar naquela posição da árvore, value# é um valor de um atributo, class# é a classe atribuída àquele ramo da árvore e counter# é um contador dos vários elementos de cada classe que seguem o padrão correspondente àquele ramo da árvore.

Exemplos de dados encontram-se nos ficheiros restaurant.csv, weather.csv e iris.csv, que são descritos a seguir.

• restaurant: (exemplo do livro, página 700) contém informações sobre restaurantes (tipo de comida, tempo de espera, preço etc), e o atributo de classe diz se o cliente esperou ou não para comer no restaurante. A tarefa é gerar uma árvore de decisão que possa dar apoio á decisões futuras dizendo se um cliente vai esperar ou não para comer naquele restaurante.
• weather: contém informações sobre condições climáticas e uma variável de classe que diz se uma pessoa vai jogar tênis ou não, dadas as condições climáticas. A tarefa é gerar uma árvore de decisão que, dadas novas condições climáticas, decida se uma pessoa vai jogar ou não.
• iris: contém informações numéricas sobre plantas de três classes: iris setosa, iris virginica e iris versicolor. Os atributos são largura e comprimento da pétala e largura e comprimento da sépala. A tarefa é construir uma árvore de decisão que, dada uma nova planta, consiga categorizá-la em umas das três classes.