Implementação Entropia

    Antes de iniciarmos o estudo do Ganho de Informação, vamos ver a implementação de um método mais genérico que calcula a entropia de um conjunto de valores, vamos ao código:

public class Entropy {
    /**
     * Metodo que dado um conjunto de valores calcula e entropia deste
     * conjunto.
     * 
     * @param values  - Lista de valores que se quer calcular a entropia
     * @return    - A entropia do conjunto
     */
     public static Double calculateEntropy(List values) {
         Map map = new HashMap();
  
         // Somatório para calcular a ocorrencia de cada valor
         for (String sequence : values) {
             // Preenche o mapa com a key sendo o valor e o value a quantidade
             if (!map.containsKey(sequence)) {
                 map.put(sequence, 0);
             }
             // Adiciona um a quantidade
             map.put(sequence, map.get(sequence) + 1);
         }

         // Calcula a entropia
         Double result = 0.0;
  
         // Itera pelo conjunto de possíveis valores
         for (String sequence : map.keySet()) {
             // Calcula a frequencia que o registro aparece, a probabilidade do valor
             // aparecer na base de dados informada
             Double frequency = (double) map.get(sequence) / values.size();
             // Faz o calculo da entropia
             result -= frequency * (Math.log(frequency) / Math.log(2));
         }

         // Retorna o valor
         return result;
     }

}

    Podemos ver através do código acima que a implementação do calculo de entropia é bastante simples quando se entende o funcionamento da equação e consegue ver além das notações matemáticas.

Entropia Passo a Passo

    Continuando o último post sobre as equações utilizadas no algoritmo ID3, podemos agora que conhecemos o que cada uma das equações se propõe a fazer, começar a conhecê-las melhor, vamos iniciar pela entropia, pois ela é a base do cálculo do ganho de informação e, portanto, essencial para que possamos avançar. O primeiro passo é conhecermos a fórmula da entropia:

    Sempre quando temos uma equação que não conhecemos o primeiro passo é descobrir o que cada um dos símbolos significa:

• = Representa o conjunto de dados que queremos calcular a entropia.
• = É a quantidade de possíveis valores, que os registros presentes no conjunto a ser calculado podem assumir, no atributo que classifica a base de dados.
• = É a probabilidade, de cada um dos possíveis valores que o atributo que classifica a base de dados, aparecer no conjunto em que será calculada a entropia.
• = Esse símbolo representa um somatório, que é uma operação matemática que soma os valores informados a ela n vezes. 
• = É a variável de inicialização, imagine que essa variável funcione como a primeira parte de um for.
•  = Esse símbolo representa um logaritmo na base dois.

    Após entendermos o que cada componente da equação significa, podemos tentar aplicar o conceito à um exemplo prático:

1. Considere o seguinte conjunto de dados:



    Devemos primeiro identificar qual o atributo que classifica a minha base de dados, no caso do exemplo acima é o atributo "Aproveitar". A segunda etapa é verificar quais valores o atributo classificatório da base de dados pode assumir, para esse exemplo "Sim" ou "Não".
    Apenas com esses dois passos já conseguimos saber o valor de uma das variáveis da equação , o valor atribuído será 2, pois esse é o número de valores que o atributo "Aproveitar" pode assumir.
2. Temos agora a equação:
   
    
   
   
      Note que a variável que limita a somatória foi substituída. Próximo passo é atribuirmos valores de  para os possíveis valores do atributo "Aproveitar", como no exemplos abaixo:
• = Portanto temos que quando o valor de  for igual a um  será igual a probabilidade de um registro com o atributo "Aproveitar" conter o valor "Sim".
• = Nesse caso temos que quando o valor de  for igual a dois será igual a probabilidade de um registro com o atributo "Aproveitar" conter o valor "Não".
• Esse processo se repetiria, caso o atributo tivesse um número maior de valores possíveis, até que o valor de chegasse ao número de valores.
3. Agora que sabemos o significado de podemos expandir o somatório da seguinte forma:
   
   
   
   
   
4. Podemos agora calcular as probabilidade de da seguinte forma:
   • Sabemos pela tabela apresentada anteriormente que a quantidade de total de registro é de 4.
   • Podemos observar que a quantidade de registros que a classificação é "Sim" são 3.
   • Portanto a quantidade de registros com a classificação "Não" é de 1.
   Com essas informações termos o seguinte cálculo:
   
   
   
   
   
5. Após esse cálculo podemos novamente substituir alguns termos na equação da entropia, nossa equação ficará da seguinte forma:
   
   
   
   
   
6. Próximo passo é resolvermos o logaritmo:
   
   
   
   
   
7. E agora que temos apenas operações básicas podemos calcular o resultado final:
   
   
   

   
    Basta seguir o exemplo acima e você irá conseguir calcular a entropia de qualquer conjunto de dados ou de qualquer atributo.
    No próximo post iremos ver como é possível calcular o ganho de informação de um conjunto, iremos conhecer a fórmula e fazer também um passo a passo detalhado para que todos possam entender e conseguir aplicar a seus problemas ou até mesmo implementar uma solução.

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.

ID3

Árvores de Decisão

O primeiro tópico a ser abordado aqui no blog são as árvores de decisão, sendo os mais conhecidos o algoritmo ID3 e no seu sucessor C4.5. Iremos implementar primeiramente a versão mais básica (ID3) e depois de pronto o modificaremos para que se torne o seu sucessor.

O nosso algoritmo básico constrói as árvores de decisão de uma forma top-down (de cima para baixo), fazendo uma simples pergunta: "Qual atributo deve ser usado?". Para responder isso cada atributo é testado usando um método estatístico para determinar o ganho de informação que aquele atributo gera na hora de classificar a nossa base de treinamento. Após a seleção esse atributo vira o topo da árvore e cada valor que esse atributo pode assumir vira uma folha e a base de dados é separada de acordo, o processo todo é repetido para cada folha, usando apenas os exemplos associados a ela. Iremos usar a implementação greedy desse algoritmo, pois ele nunca volta atrás para reconsiderar as escolhas feitas anteriormente.

Para a implementação de uma árvore de decisão que aceite apenas valores booleanos como saída, teremos o seguinte pseudocódigo:

IDE3 (Exemplos, atribuito_classificador, Atributos)

• Criar a folha inicial da árvore Root
• Se todos os objetos são positivos em Exemplos, retornar uma única folha com a saída verdadeira.
• Se todos os objetos são negativos em Exemplos, retornar uma única folha com a saída false.
• Se Atributos estiver vazio retornar uma única folha com a saída mais comum na base.
• Caso contrário faça:
• A recebe o atributo de Atributos que melhor classifica Exemplos.
• Root recebe A
• Para cada possível valor v de A teremos:
• Adicionar uma nova folha a A com o valor correspondente a v.
• Sendo X o resultado de Exemplos com os objetos que contenham v como atributo.

• Se o X gerado for vazio:
• Adicionar uma folha a Root com o valor mais comum da base.
• Caso contrário:
• ID3 (X, atribuito_classificador, Atributos – A).

• Término.
• Retorne Root.

Para medir qual atributo melhor classifica a base de dados vamos utilizar o cálculo de ganho de informação, você pode conferir uma descrição completa da equação nesse link.

Como todos algoritmos o ID3 possuí algumas limitações e capacidades, vamos ver abaixo algumas delas:

• O ID3 na sua forma inicial, e a que será implementada, não possui nenhuma forma de backtracking, portanto está sujeito a convergir para soluções ótimas locais. No caso do ID3, uma solução ótima local corresponde ao único caminho considerado pelo algoritmo.
• ID3 usa todos os exemplos do conjunto de treinamento a cada iteração, não importando o nível em que a árvore se encontra. Essa característica faz com que o ID3 seja muito menos suscetível a erros no conjunto de treinamento.
• O ID3 mantém apenas uma única solução, o que faz com que ele não seja capaz de otimizar os resultados obtidos.

Para encerrar esse post podemos ver abaixo um exemplo de resultado obtido com o ID3:

Introdução

Introdução

O que é Inteligência Artificial?

Inteligência Artificial (IA) é um ramo da ciência da computação que se propõe a elaborar dispositivos que simulem em computador comportamentos inteligentes e simular comportamentos humanos, como por exemplo, interpretação de imagens, conversação, raciocínio lógico, aprendizado, etc.

Quais atividades a IA cobre?

• Planejamentos
• Classificação
• Tomada de decisão
• Diagnósticos
• Sistema Especialistas
• Visão Computacional
• Aprendizado
• Entre outros

Quando começou a IA?

Após o final da Segunda Guerra Mundia, algumas pessoas passaram a trabalhar com a criação de máquinas inteligentes, o matemático inglês Alan Turing provavelmente foi o pioneiro a estudar o assunto além de ter também sido um dos primeiros a perceber que era mais prático construir softwares inteligentes para controlar as máquinas do que construir máquinas inteligentes.

AI visa atingir um nível de inteligência igual a inteligência humana?

Sim, o objetivo é construir programas capazes de resolver problemas no mundo real assim como nós humanos. 

Quais tópicos serão abordados aqui no blog?

Aqui serão discutidos tópicos de Aprendizado de Máquina, suas possíveis implementações e seus usos. No futuro também pretendo mostrar algumas integrações de Aprendizado de Máquina com o Raspberry PI.

Serão colocados os códigos fontes aqui no blog?

Sim, todos os códigos serão disponibilizados aqui no blog, assim como as massas de dados utilizadas nos testes.

Em que linguagem?

Como o nome do blog sugere, todas as implementações serão feitas em Java e em alguns casos em específico também será feito em R ou Python.

Com que frequência?

Devido ao trabalho, outros compromissos e a complexidade das implementações não vou dar prazos, mas pretendo postar aqui sempre que possível.

http://www-formal.stanford.edu/jmc/whatisai/

Machine Learning - Tom Mitchell, 1997.

von Wangenheim, Christiane Gresse; von Wangenheim, Aldo. Raciocínio Baseado em Casos. Barueri, SP: Manole, 2004. Capítulo: 10: Aplicações de RBC. , 293 p. p. 227-241

Harmon, Paul; King, David. Sistemas Especialistas: A Inteligência Artificial Chega ao Mercado. Rio de Janeiro: Campus, 1988. 304 p. p. 17-23

Durkin, John. Expert Systems: Design and Development (em inglês). New York: Macmillan, 1994. 800 p. p. 28-29

Giarratano, John; Riley, Gary. Expert Systems: Principles and Programming (em inglês). 3ª ed. Boston: PWS Publishing Company, 1998. 597 p. p. 6.

http://pages.unibas.ch/LIlab/staff/tenhacken/Applied-CL/3_Systran/3_Systran.html#history

http://www.tecmundo.com.br/intel/1039-o-que-e-inteligencia-artificial-.htm