Com a simplificação da árvore de decisão gerada pelo algoritmo, conseguiu-se diminuir a complexidade e com isso aumentar a performance na classificação dos casos desconhecidos.Mas, mesmo depois da simplificação ainda podemos ter árvores complexas, lentas e de difícil compreenção.

Alguns desses problemas, como compreenção, aparecem apenas quando se esta trabalhando com grandes árvores de decisão, enquanto outros, como subárvores idênticas que se repetem em várias partes da árvore, são caracteristicas presentes em quase todas as árvores de decisão, como no exemplo da figura 5-1, gerada a partir de uma base de fatos artificial composta pelos atributos F, G, J, K, que podem assumir somente valores binários, 0 ou 1, e pelas classes "sim" e "não".Um caso é classificado como "sim" se F = 1 e G = 1 ou se J = 1 e K = 1.Esta árovere contém duas subárvores idênticas que testam os atributos J e K.Existem apenas duas maneiras de resolver este problema:(?) ou usar outras estruturas representando o classificador, que é o que vai ser estudado neste capítulo.

F = 0
   J = 0: não
   J = 1:
      K = 0: não
      K = 1: sim
F = 1
   G = 1: sim
   G = 0:
      J = 0: não
      J = 1:
         K = 0: não
         K = 1: sim

Figura 5-1.

Como foi visto no capítulo 1, uma regra obedece ao formato L->C, onde L é composto por um conjunto de testes e C é uma classe.Para a figura 5-1 podemos obter 7 regras, uma para cada folha, bastando seguir o caminho da raiz até cada folha para encontrá-las, uma delas é

Um caso irá satisafazer esta regra se obedecer todos os testes que estão a esquerda desta regra.

Gerando uma regra para cada folha da árvore, não estaremos conseguindo algo mais simples ou mais eficiente que uma árvore, entretanto, podemos eliminar testes na regra que sejam irrelevantes, como no caso da regra acima, para os testes nos atributos F e G.Olhando para a árvore da figura 5-1, podemos ver que independente dos valores de F e G, se J = 1 e K = 1, chegaremos a classe "sim".Portanto, podemos generalizar esta regra deletando os testes F =1 e G = 0, sem afetar a precisão da regra.

Para decidir quais destes testes devem ser deletados, o c4.5 utiliza um sistema parecido com aquele usado na simplificação das árvores de decisão.Para regras, será calculada uma estimativa pessimista de erro, antes da remoção de um teste e depois.Se a remoção do teste apresentar uma estimativa de erro menor, então a regra é generalizada.

Sendo R a regra atual e R- a regra com um teste X qualquer deletado, temos que, para R tinhamos, dos casos cobertos pela regra, Y1 casos que satisfaziam a classe C e E1 outras classes.Deletando o teste X, mais casos serão classificados por esta regra, sendo Y2 os novos casos classificados por R- associados a classe C e E2 os novos casos classificados por R- associando outras classes, portanto, o total de casos cobertos pela regra R- será Y1 + Y2 + E1 + E2.

Como foi visto no capítulo anterior, se temos N casos que chegam até uma folha, sendo E destes classificados erradamentes por esta folha, é muito pouco provável que a taxa de erro seja menor do que E/N, por isso, para se conseguir fazer a simplificação, erá feita uma estimativa pessimista para cada folha, dada por Ucf(E,N).O mesmo será usado aqui.A estimativa de erro para uma classe será dada por Ucf(E1,Y1+E1) e para R- Ucf(E1+E2,Y1+Y2+E1+E2).

O algoritmo segue os seguintes passos:

1.Calcula-se a estimativa de erro para a regra R.

2.Para cada teste X pertencente a regra R, calcula-se a estimativa de erro para a regra supondo que este teste foi removido.

3.Se alguma das estimativas calculadas no passo 2 for menor que a estimativa calculada no passo 1 a regra é generalizada, eliminando-se o teste que gerou a menor estimativa.Retorna-se então ao passo 1 com a nova regra.

Se nenhuma das estimativas de erro calculada for menor que a calculada no passo 1 o algoritmo para.

Este algoritmo pode não obter uma estimativa de erro mínima global, mas o sistema pode ser melhorado fazendo-se buscas exaustivas quando o número de testes é pequeno, e fazer alguma aproximação do ótimo usando técnicas que serão apresentadas mais adiante.

TSH <= 6 : negative (2246.8/1.0)
TSH > 6 :
|   FTI <= 64 :
|   |   TSH measured = f: negative (4.3/0.0)
|   |   TSH measured = t:
|   |   |   T4U measured = f:
|   |   |   |   TSH <= 17 : compensated hypothyroid (2.4/0.5)
|   |   |   |   TSH > 17 : primary hypothyroid (2.1/1.1)
|   |   |   T4U measured = t:
|   |   |   |   thyroid surgery = f: primary hypothyroid (59.0/1.0)   
|   |   |   |   thyroid surgery = t: negative (3.0/1.0) *
|   FTI > 64 :
|   |   on thyroxine = t: negative (35.2)
|   |   on thyroxine = f:
|   |   |   TSH measured = f: negative (21.2)
|   |   |   TSH measured = t:
|   |   |   |   thyroid surgery = t: negative (3.7)
|   |   |   |   thyroid surgery = f:
|   |   |   |   |   TT4 > 150 : negative (6.1/0.1)
|   |   |   |   |   TT4 <= 150 :
|   |   |   |   |   |   TT4 measured = f: primary hypothyroid (2.8/0.7)
|   |   |   |   |   |   TT4 measured = t: compensated hypothyroid (127.4/1.5)

Figura 5-2

Para demonstrar o algoritmo acima será utilizado o exemplo da figura 5-2, particularmente para a regra referente a folha marcada com um asterisco

Esta regra classificou três dos casos de treinamento, sendo que, dois deles satisfazem a classe negative Y1=2 e um outras classes E1=1.Calculando a estimativa de erro para esta regra

U25(1,3) = 0,69

Agora, para cada teste pertencente a esta regra, calcula-se a estimativa de erro para a regra, supondo que este teste foi removido

teste a ser deletado  	Y1+Y2     E1+E2     estimativa de erro

TSH > 6                   3         1              55%
FTI <= 64                 6         1              34%
TSH measured = t          2         1              69%
T4U measured = t          2         1              69%
thyroid surgery = t       3        59              97% 

Agora, como houve várias estimativas menores que 0,69, generaliza-se a regra eliminando aquele teste que gerou a menor estimativa de erro, no caso o teste TTI <= 64, a nova regra será

Novamente, para cada teste pertencente a esta regra, calcula-se a estimativa de erro para a regra, supondo que este teste foi removido

teste a ser deletado  	Y1+Y2     E1+E2     estimativa de erro

TSH > 6                  31         1                8% 
TSH measured = t          6         1               34%
T4U measured = t          7         1               30%
thyroid surgery = t      44       179               82%

Escolhe-se para eliminação aquele teste que gerou a menor estimativa de erro em relação a regra, no caso, o teste TSH > 6 e eliminado, sendo então a regra generalizada para

O processo de generalização irá continuar até que se chegue a regra final