Tabela 1 Base de Dados Censitários

Após o classificador ser construído, inicia-se a etapa de teste, que visa avaliar a sua acurácia através do emprego de um conjunto de dados de teste. O conjunto de teste contém observações que também são selecionadas aleatoriamente a partir da base de dados. No entanto, estas observações devem ser diferentes das que foram selecionadas para compor o conjunto de treinamento. A acurácia do classificador representa a porcentagem de observações do conjunto de teste que são corretamente classificadas por ele. Caso a acurácia seja alta, o modelo de classificação é considerado eficiente e pode ser utilizado para classificar novos casos.

 Diversas técnicas podem ser utilizadas para a construção de classificadores, tais como redes neurais, métodos Bayesianos e árvores de decisão, entre outros. As árvores de decisão (Figura 1) têm sido muito utilizadas pelos softwares de mineração de dados. Isto é justificado pelo fato delas possuírem uma representação intuitiva, que torna o modelo de classificação fácil de ser interpretado.

Figura 1 Árvore de decisão construída a partir do conjunto de dados da Tabela 1.

   
               A árvore de decisão apresentada na Figura 1 indica se uma pessoa é rica ou não com base nos seus outros atributos, os atributos preditivos.  A estrutura possui as seguintes características:

               - cada nó interno é um teste em um atributo preditivo;
               - uma ramificação partindo de um nó interno representa um resultado para o teste (por exemplo, Escolaridade = “Doutorado”);
            - uma folha da árvore representa um rótulo de classe (por exemplo, Rico = “Sim” ou Rico = “Não”);
            - em cada nó da árvore, um atributo deve ser escolhido para dividir as observações do conjunto de treinamento em classes, na medida do possível.
            - uma nova observação é classificada seguindo um caminho na árvore, da raiz até a folha.

            É importante observar que uma árvore de decisão pode ser utilizada com duas finalidades: previsão (exemplo: descobrir se um cliente será um bom pagador em função de suas características) e descrição (fornecer informações interessantes a respeito das relações entre os atributos preditivos e o atributo classe numa base de dados).

               Uma árvore de decisão é formada por um conjunto de regras de classificação. Cada caminho da raiz até uma folha representa uma destas regras. A árvore de decisão deve ser definida de forma que, para cada observação da base de dados, haja um e apenas um caminho da raiz até a folha. As quatro regras de classificação a seguir, compõem a árvore de decisão da Figura 1.

               Uma regra de classificação é uma expressão da forma A Þ B, onde A é denominado antecedente e B é denominado conseqüente. O antecedente deve ser formado por um ou mais atributos preditivos, enquanto o atributo classe aparece no lado do conseqüente. Uma regra do tipo A Þ B indica que a classe B pode ser determinada pelos atributos preditivos indicados no antecedente. Medidas como a probabilidade condicional podem ser utilizadas para avaliar a qualidade de uma regra de classificação.          

                Existem diversos algoritmos na literatura utilizados para a construção de árvores de decisão, tais como ID3, C4.5 e CHAID. Detalhes sobre as características e a implementação destes algoritmos podem ser obtidos em [Berry e Linoff 2004] e [Han e Kamber 2006]. De forma resumida pode-se dizer que os algoritmos para classificação são recursivos e que eles constroem a árvore utilizando uma abordagem top-down. Os algoritmos classificadores possuem como meta a construção de árvores que possuam o menor tamanho e a maior acurácia possíveis. Uma questão chave para a construção de uma árvore de decisão consiste na estratégia para a escolha dos atributos que estarão mais próximos da raiz da árvore (ou seja, os atributos que são inicialmente avaliados para determinar a classe a qual uma observação pertence). Observe que na Figura 1, o atributo “Escolaridade” encontra-se na raiz da árvore, pois foi considerado pelo algoritmo classificador como o atributo mais importante para determinar se uma pessoa é rica ou não. Geralmente são utilizadas medidas baseadas na entropia para tratar este problema.

3. Construção de uma Árvore de Decisão Utilizando a Ferramenta Weka

                  A ferramenta Weka trabalha com arquivos de entrada no formato ARFF, que corresponde a um arquivo texto contendo um conjunto de observações, precedido por um  pequeno cabeçalho. O cabeçalho é utilizado para fornecer informações a respeito dos campos que compõem o conjunto de observações. Dessa forma, antes da mineração de dados, a ferramenta pode verificar alguma inconsistência na base de dados e sinalizá-la. A Figura 2 ilustra um exemplo de arquivo ARFF, contendo um cabeçalho e um conjunto de 8 registros que representam a base de dados apresentada na Tabela 1. Observe que o cabeçalho contém a declaração da relação que o arquivo representa (comando @relation), uma lista de atributos (comando @attribute) e a relação de valores que os mesmos podem assumir. O conjunto de observações é precedido por um comando @data. Cada observação é representada por uma linha. Os valores dos campos dentro de uma observação devem ser separados utilizando a vírgula.

Figura 2  Arquivo ARFF.

    O instalador da ferramenta Weka pode ser obtido de maneira gratuita (juntamente com seu código fonte) no site http://www.cs.waikato.ac.nz/~ml/weka. Uma vez instalado, o sistema Weka pode ser utilizado para minerar árvores de decisão através da execução dos seguintes passos:

   PASSO 1: Executar o programa. A partir do menu Iniciar / Programas, selecione WEKA e clique em Weka 3-4 (versão atual do sistema). O menu principal Weka GUI Chooser será exibido na tela. Clique no botão “Explorer” (Figura 3). 

                                   Figura 3  Weka GUI Chooser

      PASSO 2: Importar o arquivo ARFF. Após iniciar o Weka Explorer, a opção “Open File” deve ser utilizada para abrir o arquivo ARFF que será minerado.    

      PASSO 3: Selecionar os Atributos. Em seguida, o Weka abrirá uma tela que permite com que o usuário possa definir qual o atributo da base que será utilizado como classe e quais os atributos que serão utilizados como preditivos (Figura 4).   No momento da importação, por default, o Weka irá considerar o último atributo especificado no cabeçalho do arquivo ARFF, como o atributo classe, enquanto os demais atributos serão tratados como atributos preditivos.  Observe que, nesta tela (aba Preprocess), também é possível consultar gráficos de barra que indicam os cruzamentos de freqüência envolvendo todos os atributos preditivos e o atributo classe.

                                   Figura 4  Seleção da Classe e dos Atributos Preditivos

                  PASSO 4: Selecionar o Algoritmo de Mineração. Clique na aba “Classify”. A partir desta tela é possível escolher e executar um algoritmo de classificação sobre a base de dados importada. Os resultados da mineração também poderão ser consultados neste mesmo local. Clique no botão "Choose". Será aberta uma janela que permitirá a escolha do algoritmo de mineração de dados. Clique na pasta "trees" (algoritmos de árvore de decisão) e selecione a opção "Id3" (Figura 5). 

                     Figura 5  Seleção do Algoritmo de Mineração de Dados

      PASSO 5: Executar o Algoritmo de Mineração. No painel “Test options” selecione a opção “Use training set”. Esta  seleção indica ao Weka que toda a base de dados será utilizada como base de treinamento durante o processo de mineração. A seguir clique no botão "Start". A árvore de decisão gerada pelo algoritmo ID3 é apresentada no canto direito da tela do Weka, conforme ilustra a área destacada no círculo vermelho da Figura 6. Na mesma tela são apresentadas algumas medidas de interesse que indicam a qualidade da árvore minerada.

                     Figura 6  Árvore de Decisão Minerada pelo Weka 

4. Conclusões

      Este artigo demonstrou os passos necessários para a extração de árvores de decisão a partir de bases de dados através da utilização da ferramenta de data mining Weka. O trabalho também apresentou conceitos introdutórios sobre a mineração de classificadores e sobre árvores de decisão.

      Como trabalho futuro pretende-se apresentar outros conceitos associados à mineração de árvores de decisão como, por exemplo, as medidas de interesse para avaliar a qualidade destas árvores. Além disso pretende-se descrever outras capacidades do sistema Weka, como a mineração de regras de associação e clusters de dados e a obtenção de modelos de classificação através de outros algoritmos diferentes do ID3. 

Referências

BERRY, M. L. A. e LINOFF, G. (2004), Data Mining Techniques: for Marketing, Sales and Customer Relationship Management, John Wiley Consumer, 2nd edition.

HAN, J. e KAMBER, M. (2006), Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers, 2nd edition.

WITTEN, I. H. e FRANK, E. (2005), Data Mining: Practical Machine Learning Tools and Techniques, Morgan Kaufmann Publishers, 2nd edition.