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.