[Artigo] Introdução a Árvores de decisão para classificação e mineração de dados

Um dos maiores dilemas enfrentados por quaisquer sistemas de tomada de decisão é determinar um meio eficiente para produzir classificadores a partir de base de dados em relação ao tempo de processamento e à forma de representação simbólica simples e compreensível que facilite a análise do problema em questão.

Este artigo introduz uma ferramenta bastante popular no processo de descoberta de conhecimento em um banco de dados e consequentemente no auxílio na tomada de decisões : as Árvores de decisão.

Os classificadores baseados na árvore de decisão são um dos ramos na área de inteligência artificial. Mais especificamente, eles pertencem ao sub-campo de aprendizagem de máquina. Isto se deve à sua habilidade de aprender através de exemplos com o objetivo de classificar registros em uma base de dados.

Irei abordar os conceitos iniciais sobre árvores de decisão e como elas podem auxiliar no processo de tomada de decisões através de um exemplo prático. Para isso, usarei uma das heurísticas mais conhecidas durante o processo de aprendizagem para construção da árvore de decisão mais eficiente. E para o desfecho deste artigo, demonstrarei através de implementação em Python uma simples árvore de decisão.

"O seu sucesso depende de fazer escolhas de forma inteligente."

O que são Árvores de decisão ?

Amplamente utilizadas em algoritmos de classificação, as árvores de decisão são representações simples do conhecimento, e um meio eficiente de construir classificadores que predizem ou revelam classes ou informações úteis baseadas nos valores de atributos de um conjunto de dados. Eles são muito úteis em atividades de mineração de dados, isto é, o processo de extração de informações previamente desconhecida, a partir de grandes bases de dados. Aplicações desta técnica podem ser vista em diversas áreas, desde cenários de negócios até sistemas de piloto automático de aeronaves e diagnósticos médicos.

Uma árvore de decisão é essencialmente uma série de declarações if-elses, que quando aplicados a um registro de uma base de dados , resultam na classificação daquele registro. O mais interessante sobre o programa de árvores de decisão não é a sua construção a partir de classificação de um conjunto de treinamento, e sim a sua habilidade de aprendizado. Quando o treinamento é finalizado, é possível alimentar sua árvore de decisão construída a partir de exemplos com novos casos a fim de classífica-los.

É uma das estruturas de dados mais fácies de entender com uma boa representação gráfica. A figura 1 abaixo ilustra um exemplo de árvore de decisão.

Figura 1. Exemplo de árvore de decisão

Observe que a estrutura realmente é na forma de árvore. Dessa maneira, é possível utilizar técnicas recursivas para criar e percorrer a árvore de decisão. Você poderá utilizar quaisquer conceitos de representação de árvores aprendidos durante o seu curso de estrutura de dados para representar sua árvore. Neste artigo, para deixar as coisas bem simples, construirei a minha árvore de decisão apenas com objetos do tipo dicionário em Python.

Entendendo o problema...

Neste exemplo, são trabalhados objetos que relatam as condições propícias de uma ação de marketing baseado em uma análise demográfica do comportamento de clientes, onde se analisa se os mesmos compram ou não compra seus produtos. Para isto, é considerado um conjunto de exemplos para treinar a árvore de decisão. Considere que, os dados vieram de uma pesquisa por e-mail anônima e que existem alguns positivos (os que compram) e outros negativos (os que não compram). Depois de organizar toda essa massa de dados, chegamos a seguinte tabela:

A partir de uma árvore de decisão é possível derivar regras. As regras são escritas considerando o trajeto do nó raiz até uma folha da árvore. Estas regras determinam como as árvores classificam os registros de uma base de dados. Com basen a árvore de decisão apresentada na figura 1, pode-se exemplificar a derivação de regras. Dois exemplos de regras obtidas a partir desta árvore são mostradas a seguir: Iniciando do nó-pai (Age), verifica que o valor do atributo do primeiro exemplo casa com o valor 36-55, o qual desce para o próximo nó da árvore (Marital Status) e repete o processo até finalmente chegar a um nó-folha (um nó sem filhos). Este nós abriga a resposta para a questão de se o cliente irá ou não comprar o produto (Neste exemplo, o cliente irá comprar, porque seu estado civil ("marital status") é solteiro.

Se Age = 36-55 e Marital Status= single então Class= will buy .

É interessante também observar que este tipo de operação de derivação de regras é feita sobre um processo recursivo (não necessariamente a mais eficiente para o programa, mas é de forma elegante).

A árvore de decisão apresentada acima é uma de várias árvores que poderiam ser construídas para solucionar o problema acima apresentado. A tarefa de achar a melhor árvore de decisão é um problema NP-completo, isto é, que o tempo de processamento necessário para achar a "melhor" árvore de decisão pode ser exponencial a medida que o número de de dados usados no treinamento da rede. Embora, pareça ser impossível encontrar a menor árvore de decisão em um tempo considerável, é possível encontrar uma que seja "pequena suficiente", satisfatória a partir do uso de heurísticas especiais. A tarefa da heurística é realizar esta tarefa escolhendo o "melhor próximo" atributo que divida o conjunto de dados baseado em um critério pré-definido.

Há vários algoritmos de construção de árvore de decisão (C4.5,CART,CHAID, entre outros). Entretanto, para este artigo escolhemos o mais popular deles: a heurística ID3, para a escolha dos "melhores próximos" atributos baseados em conceitos encontrados em teoria da informação.

O algoritmo ID3 usa o conceito de entropia para calcular qual o melhor atributo será utilizado para dividir os dados em sub-grupos. Após a construção de uma árvores de decisão é importante avaliá-la. Esta avaliação é realizada através da utilização de dados que não tenham sido usados no treinamento. Esta estratégia permite estimar como a árvore generaliza os dados e se adapta a novas situações, podendo, também, se estimar a proporção de erros e acertos ocorridos na construção da árvore .

A próxima seção fala um pouco sobre como esta heurística funciona. E posteriormente, entraremos em detalhes em como criarmos a árvore de decisão e classificar clientes existentes em seu conjunto de dados em "will buy" ou "won't buy", tornando sua companhia mais lucrativa.

A heurística ID3

A física usa o termo entropia para descrever a quantidade de desordem associada a um sistema. Na teoria da informação, este termo tem uma significado semelhante, -- ele mede o grau de desordem de um conjunto de dados. A heurística ID3 usa este conceito para encontrar o próximo melhor atributo de um dado para ser utilizado como nó de uma árvore de decisão. Logo , a idéia por trás do algoritmo ID3 é achar um atributo que reduza em maior valor a entropia de um conjunto de dados, assim reduzindo a aleatoriedade - dificuldade de previsão - da variável que define classes. Seguindo esta heurística, você estará essencialmente encontrando o melhor atributo para classificar os registros (de acordo com a redução da quantia de informação necessária para descrever a partição dos dados que foram divididos ) a fim de que os mesmos tenham utilidade máxima (exemplos são da mesma classe).

O algoritmo ID3 segue os seguintes passos:

1. Começar com todos os exemplos do treinamento
2. Escolher o atributo que melhor divide os exemplos, ou seja agrupar os exemplos da mesma classe ou exemplos semelhantes
3. Para o atributo escolhido, criar um nó filho para cada valor possível do atributo
4. Transportar os exemplos para cada filho tendo em conta o valor do filho
5. Repetir o procedimento para cada filho não "puro". Um filho é puro quando cada atributo X tem o mesmo valor para todos os exemplos.

Na etapa 2 do algoritmo, para achar o melhor atributo é necessário encontrar a entropia para cada atributo possível naquele nó. Para isto usamos a fórmula da entropia:

Onde calculamos a proporção do número de exemplos positivos e o mesmo para o número de exemplos negativos para aquele atributo em questão multiplicado pelo logaritmo destas proporções. Um exemplo prático: Considere S uma coleção de 14 exemplos, incluindo 9 positivos ("will buy") e 5 negativos ("won't buy"). Logo a entropia para esta coleção S seria :

Notação: [+9,-5]

O próximo passo na heurística ID3 é calcular o ganho de informação para cada atributo que pode ser selecionado como nó na árvore. Essencialmente é apenas calcular a entropia de todo o conjunto de dados e diminuir este da entropia do sub-conjunto particionado para tal atributo. Este processo é feito para cada atributo do conjunto de dados, e o atributo com o maior ganhor de informação será o selecionado para o próximo nó da árvore.

O raciocínio por trás do ganho de informação é semelhante ao cálculo de entropia demonstrado acima. Agora considerando os sub-conjuntos particionados de acordo com o valor do atributo em questão. Considere o atributo "Vento" que pode ter os valores "Fraco" ou "Forte". Calcula-se então a entropia para cada um desses valores e depois a diferença entre a entropia do atributo vento e a soma das entropias de cada um dos valores associados ao atributo, multiplicado pela proporção de exemplos particionados de acordo com o valor (separados de um lado os exemplos com Vento = "Weak" e do outro lado Vento = "Strong").

Depois dessa breve explicação sobre a heurística ID3, vamos ao código-fonte.

Código-Fonte
O código-fonte a seguir ilustra a função principal do programa usada na construção da árvore de decisão:

##Returns the new decision tree based on the examples given
#@param data: Copy of the data list.
#@param attributes: List of all attributes 
#@param target_attr: The targer attribute that will be the evaluated
#@param fitness_func: The target function
def create_decision_tree(data,attributes,target_attr,fitness_func):
    
    data = data[:]
    vals = [record[target_attr] for record in data]
    default = majority_value(data, target_attr)
    
    #if the dataset is empty or the attributes list is empty, return the
    #the default value. When checking the attributes list for emptiness,
    #we need to subtract 1 to account for the target attribute.
    if not data or (len(attributes)-1) <= 0:
        return default
    #if all the records in the dataset have the same classification,
    #return the classification.
    elif vals.count(vals[0]) == len(vals):
        return vals[0]
    
    else:
        #Choose the next best attribute to best classify our data
        best = choose_attribute(data,attributes,target_attr,fitness_func)
        
        #Create a new decision tree/node with the best attribute.
        tree = {best:{}}
        
        #Create a new decision tree/sub-node for each of the values in the
        #best attribute field
        for val in get_values(data,best):
            #create a subtree for the current value under the "best" field
            subtree = create_decision_tree(get_examples(data,best,val),
                [attr for attr in attributes if attr != best],
                target_attr,
                fitness_func)
        
            # Add the new subtree to the empty dictionary object in our new
            # tree/node we just created.
            tree[best][val] = subtree
        
    return tree

A heurística ID3 usa o conceito de entropia para formular o ganho de informação na escolha de um atributo particular para ser o próximo nó na árvore de decisão. Aqui segue o código da função de entropia e do ganho de informação:

##Calculates the entropy of the given data set for the target attribute.
#@param data: the data list
#@param target_attr = the target attribute
def entropy(data,target_attr):
    val_freq = {}
    data_entropy = 0.0
    
    #Calculates the frequency of each of the values in the target attribute.
    for record in data:
        if val_freq.has_key(record[target_attr]):
            val_freq[record[target_attr]] += 1.0
        else:
            val_freq[record[target_attr]] = 1.0
    
    #Calculate the entropy of the data for the target attribute
    for freq in val_freq.values():
            data_entropy += (-freq/len(data)) * math.log(freq/len(data),2)
    

    return data_entropy

##Calculates the information gain (reduction in entropy) that
##would result by splitting the data on the chosen attribute (attr).
def gain(data, attr, target_attr):
    val_freq = {}
    subset_entropy = 0.0
    
    #Calculate the frequency of each of the value in the target attribute
    for record in data:
        if val_freq.has_key(record[attr]):
            val_freq[record[attr]] += 1.0
        else:
            val_freq[record[attr]] = 1.0
    
    #Calculate the sum of the entropy for each subset of records weighted
    #by their probability of ocurring in the training set.
    for val in val_freq.keys():
        val_prob = val_freq[val] / sum(val_freq.values())
        data_subset = [record for record in data if record[attr]==val]
        subset_entropy += val_prob * entropy(data_subset,target_attr)
 
    #subtract the entropy of the chosen attribute from the entropy of the
    #whole data set with respect to the target attribute (and return it)
    return (entropy(data,target_attr) - subset_entropy)

Mineração de dados com Árvores de decisão
Além de classificação de dados, árvores de decisão são úteis para inferir padrões a partir dos dados, também referenciado como mineração de dados. Apenas dando uma observada na árvore de decisão representada pela figura 1 no início deste artigo, você pode já inferir algumas tendências a partir do conjunto de dados. A mais óbvia tendência no dados é que jovens (idades entre 18 e 35) e idosos (> 55) não compram seus produtos. Isto poderia direcionar seu foco em outro público mais jovem (<>

O ponto mais importante é que olhando por cima o conjunto de dados, mesmo com apenas 20 registros, nenhum dessas tendências ou padrões são fáceis de encontrar a olho nu. Quando esse número aumenta para centenas, milhares ou até milhões de registros, achar essas tendências pode ser impossível. Usando árvores de decisão, você não apenas pode prever os gostos do seu cliente na hora de compra do seu produto, mas como também você pode apontar tendências importantes no seu conjunto de dados de teste a fim de auxiliar na melhora de práticas de marketing, e consequentemente atingir uma nova classe de clientes.

Conclusão

Os códigos acima apresentados são os componentes principais do programa. O resto das funções auxiliares para a construção da árvore de decisão podem ser encontradas no código-fonte disponível para download. Não tentei entrar muito em detalhes no código, pois acredito que o código é auto-explicatório, já que está bem comentado.
Quando executado o programa, uma árvore de decisão é construída e os dados são classificados de acordo com a árvore moldada.
Espero ter ajudado nesse pequeno tutorial sobre árvores de decisão, quaisquer dúvidas estou à disposição.

Até a próxima e boa programação!

Marcel Pinheiro Caraciolo

Referências

Arvores de Decisão - Prof. PHD Teresa Ludermir CIN/UFPE