Quarto Trabalho de Inteligência Artificial / Sistemas Inteligentes
Entrega: 30/05/2016
5 de Maio de 2016

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

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.



InĂªs Dutra 2016-05-05