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 http://www.dcc.fc.up.pt/~ines/aulas/1516/IA/trab4/restaurant.csv, http://www.dcc.fc.up.pt/~ines/aulas/1516/IA/trab4/weather.csv e http://www.dcc.fc.up.pt/~ines/aulas/1516/IA/trab4/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.
Além de gerar a árvore no formato indicado anteriormente, o seu programa deve ser capaz de aceitar como entrada um outro ficheiro com novas instâncias, não utilizadas durante a geração da árvore, e ``prever'' a classe de cada uma destas instâncias com base no modelo de árvore que gerou.