ID3 Implementação

Implementação ID3 

Como prometido nesse post iremos analisar a implementação do algoritmo de árvore de decisão ID3, o algoritmo foi implementado em Java 7 e no final do post irei colocar o link para o repositório que contém os códigos fontes. 

A seguir iremos fazer uma análise das principais classes que compõe o algoritmo:

Start.java

Classe inicial do projeto, responsável por realizar as chamadas dos métodos de carregamento dos atributos, carregamento da base e geração da árvore, assim como impressão da árvore no arquivo de resultados.

public class Start {

 /**
  * Função main, ela que irá carregar os dados e iniciar o processamento da árvore.
  * 
  * @param args
  */
 public static void main(String[] args) {
  
  //Caminho para a pasta onde será lido o arquivo com a base de dados
  String path = "C:\\Users\\davidson.sestaro\\Dropbox\\IA\\";
  
  //Carrega os atributos da base de dados
  ListDiscreteAttributes attributes = FileReader.readAttributes(path + "PlayGolf.txt");
  
  //Carrega os registros da base de dados
  List records = FileReader.readDataset(path + "PlayGolf.txt", attributes);
  
  //Instância o primeiro ramo da nossa árvore
  Node root = new Node();
  root.setData(records);
  
  //Inicia o processamento da árvore
  ID3 id3 = new ID3();
  id3.generateTree(records, root, attributes);
  
  //Imprime a arvore resultante no arquivo Result.txt
  PrintWriter writer = null;
  
  try {
   writer = new PrintWriter(path + "Result.txt", "UTF-8");
  } catch (FileNotFoundException | UnsupportedEncodingException e) {
   e.printStackTrace();
  }
  
  FileWriter.writeTree(root, writer, 0);
  
  //Fecha o arquivo
  writer.close();
 }

}

Destacando os pontos importantes da classe que necessitam alteração para a execução, temos:

Aqui deverá estar a massa de dados que iremos usar e será o caminho em que será salvo o arquivo de retorno:

String path = "C:\\desenvolvimento\\IA\\";

Substituir o nome do arquivo com a massa de dados para o arquivo correto:

//Carrega os atributos da base de dados
ListDiscreteAttributes attributes = FileReader.readAttributes(path + "PlayGolf.txt");
//Carrega os registros da base de dados
List<record> records = FileReader.readDataset(path + "PlayGolf.txt", attributes);

Arquivo com a árvore resultante:

writer = new PrintWriter(path + "Result.txt", "UTF-8");

ID3.java

Classe core do código do algoritmo, nela são realizados toda a lógica de classificação de atributos e de divisão da massa de dados. Aqui também são gerados os ramos da árvore. Todo o processamento é realizado de forma recursiva.

public class ID3 {

 /**
  * Gera a arvore de decisao de forma recursiva.
  * 
  * @param records   - Dados a serem classificados pela arvore
  * @param root    - No da arvore do topo da arvore para essa iteracao
  * @param learningSet  - Atributos a serem utilizados pelo classificador
  * @return     - Arvore de decisao
  */
 public Node generateTree(List<Record> records, Node root, ListDiscreteAttributes learningSet) {
  
  //Inicializa as variaveis para selecionar o melhor atributp
  int bestAttribute = -1;
  double bestGain = 0.0;
  
  //Calcula a entropia para os registros a serem considerados
  root.setEntropy(Entropy.calculateEntropy(root.getData(), learningSet));
  
  //Condicao de para da arvore
  if(root.getEntropy() == 0) {
   return populateResult(root.getData(), root, learningSet);
  }
  
  //Avalia cada atributo ainda nao utilizado nesse galho da arvore
  for(int i = 0; i < learningSet.getAttributeQuantity() - 1; i++) {
   double entropy = 0;
   
   LinkedList<Double> entropies = new LinkedList<Double>();
   LinkedList<Integer> setSizes = new LinkedList<Integer>();

   //Faz um de para com a posicao do atributo no vetor de atributos com a posicao real dele na base de dados
   int attributePositionRecord = Utils.getAttributePositionOnRecords(learningSet.getAttributeInfo(i), root.getData().get(0));
   
   //Itera por cada possivel valor do atributo selecionado
   for(int j = 0; j < learningSet.getAttributeInfo(i).getListAttributes().getQuantity(); j++) {
    //Pega os registros com o valor a ser considerado
    ArrayList<Record> subset = Utils.subset(root, attributePositionRecord, j);
    //Pega o tamanho desse subset
    setSizes.add(subset.size());

    //Calcula a entropia para o subset
    if(subset.size() != 0) {
     entropy = Entropy.calculateEntropy(subset, learningSet);
     entropies.add(entropy);
    } else {
     entropies.add(0.0);
    }
   }
   
   //Calcula o ganho de informacao
   double gain = InformationGain.calculateGain(root.getEntropy(), entropies, setSizes, root.getData().size());
   
   //Se for melhor do que o melhor atributo atualiza os valores
   if(gain > bestGain) {
    bestAttribute = i;
    bestGain = gain;
   }
  }
  
  //Caso exista um atributo a ser considerado
  if(bestAttribute != -1) {
   //Preenche o no da arvore com os valores desse atributo
   AttributeInfo chosen = learningSet.getAttributeInfo(bestAttribute); 
   String testedAttributeName = root.getTestAttribute().getValue();
   
   root.setTestAttribute(chosen);
   root.setValue(testedAttributeName);
   root.children = new Node[chosen.getListAttributes().getQuantity()];
   root.setUsed(true);
   
   learningSet.removeAttribute(bestAttribute);
   
   int bestAttributePositionRecord = Utils.getAttributePositionOnRecords(chosen, records.get(0));
   
   //Preenche as folhas geradas a partir desse atributo
   for (int j = 0; j < chosen.getListAttributes().getQuantity(); j++) {
    root.children[j] = new Node();
    root.children[j].setParent(root);
    root.children[j].setData(Utils.subset(root, bestAttributePositionRecord, j));
    root.children[j].getTestAttribute().setValue(chosen.getListAttributes().getValue(j));
   }

   //Itera recursivamente pelos filhos
   for (int j = 0; j < chosen.getListAttributes().getQuantity(); j++) {
    generateTree(records, root.children[j], learningSet.clone());
   }
  }
  //Metodo de para do algoritmo
  else {
   return populateResult(root.getData(), root, learningSet);
  }
  
  return root;
 }

 /**
  * Popula as folhas durante as condicoes de para do algoritmo
  * 
  * @param records   - Registros filhos dessa folha
  * @param root    - No com o atributo que gerou a folha
  * @param learningSet  - Atributos ainda nao utilizados no ramo
  * @return
  */
 private Node populateResult(List<Record> records, Node root, ListDiscreteAttributes learningSet) {
  AttributeInfo chosen = learningSet.getAttributeInfo(learningSet.getAttributeQuantity() - 1);
  
  root.children = new Node[1];
  
  root.children[0] = new Node();
  root.children[0].setParent(root);
  
  int classAttributePositionRecord = Utils.getAttributePositionOnRecords(chosen, records.get(0));
  int resultPosition = Utils.getMajority(root.getData(), learningSet.getAttributeInfo(learningSet.getAttributeQuantity() - 1).getListAttributes(), classAttributePositionRecord);
  
  root.children[0].getTestAttribute().setValue(chosen.getListAttributes().getValue(resultPosition));   
  
  return root;
 }
}

Entropy.java

Classe que realiza o cálculo da entropia de um determinado conjunto de dados.

public class Entropy {
 /**
  * Metodo que dado um conjunto de registros e os atributos a serem calculados, calcula a entropia
  * do conjunto
  * 
  * @param data   - registros do qual sera calculado a entropia
  * @param learningSet - atributos
  * @return
  */
 public static double calculateEntropy(List<Record> data, ListDiscreteAttributes learningSet) {
  double entropy = 0;
  
  if(data.size() == 0) {
   return 0;
  }
  
  //Obtem a posicao em que se encontra a classe no conjunto de atributos
  int positionClass = learningSet.getAttributeQuantity() - 1;
  //Obtem a posicao em que se encontra a classe nos registros
  int positionClassRecord = data.get(0).getAttributes().size() - 1;
  
  //Itera pelas classes existentes
  for(int i = 0; i < learningSet.getAttributeInfo(positionClass).getListAttributes().getQuantity(); i++) {
   int count = 0;
   for(int j = 0; j < data.size(); j++) {
    Record record = data.get(j);
    
    if(record.getAttributes().get(positionClassRecord).getValue() == i) {
     count++;
    }
   }
    
   //Calcula a entropia
   double probability = count / (double)data.size();
   if(count > 0) {
    entropy += -probability * (Math.log(probability) / Math.log(2));
   }
  }
  
  return entropy;
 }
}

InformationGain.java

Classe que realiza o cálculo do ganho de informação de um determinado atributo em um determinado conjunto de dados.

public class InformationGain {
 /**
  * Calcula o ganho de informacao de determinado atributo
  * 
  * @param rootEntropy  - Entropia do conjunto como um todo
  * @param subEntropies  - Entropia dos possiveis subgrupos do atributo
  * @param setSizes   - Tamanho dos possiveis subgrupos do atributo
  * @param data    - Quantidade de registros total
  * @return
  */
 public static double calculateGain(double rootEntropy, LinkedList<Double> subEntropies, LinkedList<Integer> setSizes, int data) {
  double gain = rootEntropy; 
  
  for(int i = 0; i < subEntropies.size(); i++) {
   gain += -((setSizes.get(i) / (double)data) * subEntropies.get(i));
  }
  
  return gain;
 }
}

Essas são as principais classes que compõe o projeto para geração de árvores de decisão, o projeto se encontra no link:

https://github.com/dsestaro/Algorithms

Todos as implementações feitas aqui no blog irão ser commitadas nesse mesmo repositório.