Algoritmo C4.5

C4.5 é um algoritmo utilizado para criar uma árvore de decisão e foi desenvolvido por Ross Quinlan. C4.5 é uma extensão do algoritmo anterior de Quinlan's ID3. As árvores de decisão geradas pelo algoritmo C4.5 podem ser utilizadas para classificação e são portanto conhecidas como classificadores estatísticos.

Ele se tornou bastante popular após ficar posicionado entre os melhores algoritmos de mineração de dados no trabalho Top 10 Algorithms in Data Mining publicado por Springer LNCS em 2008.

Algoritmo

C4.5 constrói árvores de decisão a partir de um conjunto de dados de treinamento da mesma forma que o algoritmo ID3, utilizando o conceito de Entropia. O conjunto de dados de treinamento é um conjunto $S={s_{1},s_{2},...}$ de amostras já classificadas. Cada amostra $s_{i}$ consiste de um vetor p-dimensional $(x_{1,i},x_{2,i},...,x_{p,i})$, onde o $x_{j}$ representa valores de atributos ou características da amostra, assim como a categoria ou a classe a qual $s_{i}$ pertence.

Em cada nó da árvore, o algoritmo C4.5 escolhe o atributo dos dados que mais efetivamente particiona o seu conjunto de amostras em subconjuntos tendendo a uma categoria ou a outra. O critério de particionamento é o ganho de informação normalizado (diferença em entropia). O atributo com maior ganho de informação normalizado é escolhido para tomar a decisão. O algoritmo C4.5 então repete a etapa anterior nas partições menores.

Este algoritmo possui alguns casos básicos:

• todas as amostras do conjunto pertencem a uma mesma categoria; quando este caso ocorre, o algoritmo simplesmente cria um nó folha para a árvore de decisão e escolhe a categoria em questão;
• nenhuma das características fornece ganho de informação. Neste caso, o algoritmo C4.5 cria um nó de decisão árvore acima usando o valor esperado;
• instâncias previamente não vistas. Novamente, o algoritmo C4.5 cria um nó de decisão árvore acima usando o valor esperado.

Pseudo código

Em pseudo código, o algoritmo geral para construir árvores de decisão é:

1. Verificar por casos básicos
2. Para cada atributo a
   1. Encontrar a razão do ganho da informação normalizado pelo particionamento em a
3. Seja a_maior o atributo com maior ganho da informação normalizado
4. Criar um nó de decisão que particiona o conjunto de dados em a_maior
5. Repetir nos subconjuntos obtidos através da divisão em a_maior, e adicionar aqueles nós como filhos de nó

Implementação

J48 é uma implementação de código aberto em Java do algoritmo C4.5 no aplicativo de mineração de dados Weka.

Melhoramentos do algoritmo ID.3

C4.5 apresenta uma série de melhorias ao algoritmo ID3. Algumas destas melhorias são:

• Lidar com atributos contínuos e discretos. No intuito de lidar com atributos contínuos, o algoritmo C4.5 cria um valor limiar e então particiona o conjunto de dados em dois subconjuntos dos quais um contém valores de atributos maiores do que aquele valor limiar e o outro conjunto contém valores menores ou iguais aquele valor limiar.
• Lidar com dados de treinamento com atributos incompletos. O algoritmo C4.5 permite que atributos sejam rotulados como ? para casos onde os valores não estejam presentes. Valores de atributos que não estejam presentes não são utilizados em cálculos de entropia ou ganho de informação.
• Lidar com atributos com diferentes custos.
• Poda de árvores após a criação. O algoritmo C4.5 retrocede pela árvore quando esta é criada e tenta remover ramificações que não ajudam no processo de decisão e substitui estes ramos por nós folha.

Ligações externas

• Implementação original na página de Ross Quinlan: http://www.rulequest.com/Personal/