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.