Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

“Cleveland Heart-Disease Data" - Árvores de Decisão (Izenman, A. J. 2008)

+2 votos
198 visitas
perguntada Dez 14, 2020 em Aprendizagem de Máquinas por Lucas Lourenço (91 pontos)  
editado Dez 14, 2020 por Lucas Lourenço

Replique o exemplo que usa o “Cleveland Heart-DiseaseData" que é apresentado no Capítulo 9 do livro Modern multivariate statistical techniques - Alan Julian Izenman. Use python, interprete os resultados e documente cuidadosamente o seu material e implementação. Replique as figuras que ele encontra.

9.2.1 Example: Cleveland Heart-Disease Data

Esses dados foram obtidos de um estudo sobre doenças cardíacas conduzido pelo Cleveland Clinic Foundation. Nele, a variável de resposta é diag (diagnóstico de doença cardíaca: buff = saudável; sick = doença cardíaca). Haviam 303 pacientes no estudo, 164 deles saudáveis e 139 com doença cardíaca.
São 13 variáveis explicativas, as quais resumi na Tabela abaixo:

A imagem será apresentada aqui.

Dos 303 pacientes, 7 possuíam dados ausentes e, por isso, o número de pacientes foi reduzido para 296 (160 saudáveis, 136 com doença cardíaca).
Neste exemplo de Izenman, apenas 7 das 13 variáveis são utilizadas: thal, ca, cp, age, oldpeak, thatach, and exang.

A árvore treinada pelos autores encontra-se abaixo. São 10 divisões, com um total de 11 nós terminais. Destes, 5 estão associados à classificação “saudável” e 6 à classificação “doentes cardíacos”.

A imagem será apresentada aqui.

A seguir é feita uma discussão sobre as medidas de impureza (Gini e função entropia), a partir das quais criam-se os métodos de melhor particionamento dos dados. A partir do nó raiz, o autor faz exercícios de partição considerando a variável idade. Abaixo, na figura da esquerda, estão as impurezas dos grupos separados à esquerda (azul) e à direita (vermelho) em que o eixo x representa as idades escolhidas na partição. Na figura da direita, é mostrada o ganho de qualidade que se obtém com cada particionamento. O máximo dessa curva é em x=54, ou seja, a partir do nó principal, se fôssemos escolher idade como a primeira variável de partição, escolheríamos a idade de 54 anos.

A imagem será apresentada aqui.

Por último, ele mostra o melhor ganho \( \Delta_{i}(s,\tau) \) possível para cada variável (mais uma vez, partindo do nó raiz).

A imagem será apresentada aqui.

Compartilhe

3 Respostas

+2 votos
respondida Dez 14, 2020 por Lucas Lourenço (91 pontos)  
editado Dez 18, 2020 por Lucas Lourenço

A seguir, tentarei replicar essas imagens com um código 100% hands-on em Python. Isto é, utilizei a linguagem pura, sem auxílio dos pacotes de machine learning. Para tal, segui as equações do livro para gerar as medidas de impureza, a partição ótima e as regras de decisão a respeito de tornar um dado nó terminal.

Ao todo são 3 classes e 12 funções, divididas em funções auxiliares e funções para construção da árvore.

FUNÇÕES AUXILIARES

unique_vals:

Encontra os valores únicos em uma coluna de dados
Exemplo: a quinta coluna de dados é a variável ca e, conforme vimos na tabela acima, assume valores de a 0 a 3:

uniquevals(datacleveland,5)
{0.0, 1.0, 2.0, 3.0}

class_counts:

Armazena a contagem de observações de cada classe.
Exemplo: no caso do estudo de Cleveland, temos 160 saudáveis e 137 doentes cardíacos.

classcounts(datacleveland)
{'buff': 160, 'sick': 137}

is_numeric:
Testa se um valor é numérico
Exemplo:

is_numeric(12)
True

partition:
Particiona os dados. Para cada linha dos dados, confere a resposta para a pergunta. Se True, aloca essa linha para a 'truerows'. Se False, aloca essa linha para a 'falserows'.

gini:
Calcula o Gini de um conjunto de dados baseado na fórmula 9.4 do livro:

\[ i(\tau) = \sum_{k \neq k^{\'}} p(k|\tau)p(k^{\'}|\tau) = 1 - \sum_{k}\{p(k|\tau)\}^{2} \]

entropy:
Calcula a função entropia de um conjunto de dados baseado na fórmula 9.2 do livro:

\[ i(\tau) = - \sum_{k=1}^{K} p(k|\tau) \ log \ p(k|\tau) \]

info_gain:
Calcula o ganho de informação após uma partição. É a impureza do nó-pai menos a média ponderada das impurezas dos nós-filhos. Equação 9.9:

\[ \Delta i(s,\tau) = i(\tau) - p_{L}i(\tau_{L}) - p_{R}i(\tau_{R}) \]

findbestsplit:
Retorna a pergunta que melhor particiona um conjunto de dados. Passa por todas as variáveis (colunas) e por todos os valores de partição possíveis.

CLASSES

Question:
Uma pergunta é usada para particionar os dados.
'column' é o número da coluna da variável de interesse;
'value' é o valor de partição que se pretende utilizar;
'match' é um método que aplica a pergunta a uma linha qualquer de dados e retorna True se a resposta for afirmativa e False caso contrário

Leaf_Node:
O nó folha classifica os dados. É um ponto terminal da árvore.
'predictions' é um dicionário que mostra a contagem de classes nessa folha.
O mais comum é classificar uma nova observação a partir da classe da maioria.

Decision_Node:
Um nó de decisão basicamente faz uma pergunta e armazena os nós filhos e outros parâmetros úteis.
'question' é um objeto da classe Question;
'true_branch' é o particionamento de dados que responde True à pergunta;
'false_branch' é o particionamento de dados que responde False à pergunta;
'rows' é o conjunto de dados que chegou até esse nó (esses dados serão particionados pela pergunta);
'error' é o erro desse nó, calculado como [n de classificações erradas/n total de observações]. Representa a equação 9.14 de Izenman;
'level' é o nível da árvore, sendo 1 o root node;
'sub_tree_error' é o erro combinado das folhas da sub-árvore formada a partir desse nó de decisão; Equação 9.22:
\[ R^{re}(T_{\tau}) = \sum_{\tau \epsilon \tilde{T}_{\tau}} R^{re}(\tau) \]
Em que cada \( \tau \) é um nó terminal da sub-árvore \( T_{\tau} \).
'T' é o número de folhas (nós terminais) da sub-árvore formada a partir desse nó de decisão.
'pruning' é o cost-complexity measure que será utilizada na podagem. Veja a equação 9.23:
\[ R_{\alpha}(T_{\tau}) = R^{re}(T_{\tau}) \ + \ \alpha |\tilde{T}_{\tau}| \]
Em que \( R_{\alpha}(T_{\tau}) \) é o erro de classificação daquele nó de decisão, \( R^{re}(T_{\tau}) \) é o erro de classificação da sub-árvore abaixo desse nó, \( \alpha \) é um parâmetro de penalização e \( |\tilde{T}_{\tau}| \) é o número de nós terminais naquela sub-árvore.

FUNÇÕES PARA CONSTRUÇÃO DA ÁRVORE

build_tree:
Constrói a árvore por meio de recursão. Recebe uma série de dados e o nível da árvore em que se encontra. Se a melhor partição não traz ganhos -> chega-se a uma folha.
Caso contrário, efetua a partição, constrói os ramos da esquerda e da direita
A cada recursão:
\( i) \) guarda o erro da sub-árvore, que é a soma dos erros das folhas que estão abaixo;
\( ii) \) conta o número de folhas abaixo daquele nó.
Essas duas informações são finalmente usadas para construir o cost_complexity_measure.

pruning_tree
Podagem da árvore. Faz uma recursão parecida ao build_tree. Se o cost-complexity measure \( > \) erro do nó-pai, o nó-pai vira uma folha. O valor \( \alpha \) de penalização é definido exogenamente. Ver Izenman (2008), págs. 295 e 296.

max_depth
Permite que a árvore cresça somente até um limite \( T_{max} \). Não é um método recomendado por Izenman.

print_tree
Desenha a árvore no console do Python. Cada nó é identificado como sendo um nó de decisão ou um nó folha. Vários parâmetros são impressos, seguidos da pergunta que faremos naquele nó (caso não seja um nó terminal). Se for um nó terminal, informa qual classe devemos predizer pela regra da maioria.

+2 votos
respondida Dez 14, 2020 por Lucas Lourenço (91 pontos)  
editado Dez 18, 2020 por Lucas Lourenço

Dados

Esse código funciona com a estrutura mais simples de dados possível, que consiste em uma lista multidimensional, em que cada lista interna é uma linha de dado. As colunas são as variáveis e a última coluna é a variável de resposta (diagnóstico de doença cardíaca).

# IMPORTANDO OS DADOS #
data=pd.read_csv('Cleveland_Heart_Disease_Data.csv',sep=";")

header = []
for col in data:
    header.append(col)

data_cleveland = []
for ind in data.index:
    new_list = []
    for i in data.loc[ind]:
        new_list.append(i)
    data_cleveland.append(new_list)

É importante conferirmos se as variáveis são numéricas ou categóricas de acordo com o explicado por Izenman na seção 9.2.3. Basicamente, o número de partições possíveis é diferente se uma variável for categórica ou numérica. Se o Python importar de forma errada, as partições podem ser geradas de maneira incorreta.

Observações:

  • Importei somente as 7 variáveis utilizadas na construção da árvore.
  • No livro, ele cita a presença de 7 observações com missings. No
    entanto, só achei 6 (talvez o banco tenha sido atualizado já que
    temos mais de 10 anos desde sua publicação). Assim, nossa árvore terá um conjunto de treino de 297 em comparação aos 296 do livro.
  • Baixe o .csv aqui

Treinando a árvore:
Primeiro, vamos treinar uma árvore sem regras de paradas. Ou seja, a cada nó uma nova pergunta será feita enquanto \( i) \) tivermos observações das duas classes e \( ii) \) tivermos ganho positivo ao se fazer novo particionamento. Evidentemente, essa árvore tem problemas de overfitting e é diferente da figura 9.2 do Izenman. Ela possui 16 níveis e 61 nós-folhas, todos com erro 0.

# Construindo a árvore completa (cheia de overfitting):
if __name__ == '__main__':  
    alpha = 0 
    sub_tree_error=0
    T=0
    number_of_obs = len(data_cleveland)
    my_tree = build_tree(data_cleveland)
    print('')
    print('####### FULL TREE #######')
    print('')
    print_tree(my_tree)

A seguir, podemos utilizar três técnicas para criar regras de paradas e diminuir o tamanho da árvore. Duas delas são ad hoc e não recomendadas por Izenman, sendo a terceira a melhor. A primeira delas consiste em declarar um nó folha sempre que a melhor partição gerar um ganho muito baixo, abaixo de um valor arbitrário \( M_{min} \). Para tal, edite a função build_tree na linha em que temos:

if gain == 0:

Por exemplo, podemos testar:

if gain < 0.01

A segunda delas consiste em não deixar a árvore crescer mais que um dado nível arbitrário. Para isso, basta utilizar a árvore inteira como argumento da função max_depth, seguida da profundidade máxima desejada.

# Utilizando os métodos ad-hoc para controle do overfitting:
# O primeiro é transformar o nó em folha sempre que o ganho for menor que dado valor escolhido.
# Editar linha [if gain == 0:] na função build_tree.   
# O segundo consiste em limitar os níveis da árvore.  
if __name__ == '__main__': 
    alpha = 0 
    sub_tree_error = 0
    T = 0
    number_of_obs = len(data_cleveland)
    my_tree = build_tree(data_cleveland)
    choose_max_depth = 8
    final_tree=max_depth(my_tree, choose_max_depth) 
    print('')
    print('')
    print('#### MAX DEPTH TREE = %s ####'%(choose_max_depth))
    print('')
    print('')    
    print_tree(final_tree)

Finalmente, a terceira técnica, consiste em podar a árvore. Basta escolhermos uma medida de penalização \( \alpha > 0 \), que deixará indesejáveis aquelas árvores com muitos nós terminais. Basta inserir a árvore original como argumento da função pruning_tree.

if __name__ == '__main__': 
    alpha = 0 
    sub_tree_error=0   
    T=0
    my_tree = build_tree(data_cleveland)
    pruned_tree = pruning_tree(my_tree,3)
    print('')
    print('####### PRUNED TREE #######')
    print('')
    print_tree(pruned_tree) 

Izenman não comenta a regra de parada de crescimento utilizada em sua árvore. Note que os métodos de podagem são aplicados a outro exemplo (estudo de diabetes na Índia). Por esse motivo e pelo fato de eu não ter utilizado nenhuma ferramenta avançada de machine learning desenvolvida pela comunidade Python, não consegui replicar a árvore idêntica. No entanto, consegui uma parecida deixando \( \alpha = 0 \) e podando somente aqueles galhos em que o erro é igual ao erro do nó pai (ou seja, são galhos totalmente redundantes, pois não melhoram o erro). Fazendo isso, a árvore reduz de 61 para 12 nós (parecidos com os 11 do livro). Segue a árvore, em que a região hachurada não está na árvore do livro (além disso, existem duas ramificações que estão na árvore do livro, porém não estão na minha).

Veja a imagem com melhor resolução aqui

A imagem será apresentada aqui.

Comparando as árvores, nota-se que a do livro não "podou" galhos redundantes. Observe que a sub-árvore que parte do nó de decisão "buff 22/7" possui folhas cujos erros somados dão 7. Ou seja, tanto o nó pai quanto as folhas erram 7 classificações. Isso torna essa ramificação redundante e por esse motivo ela não apareceu na minha árvore (o que reforça a incógnita de qual regra o autor utilizou para criar seus nós-terminais).

Utilizando as funções já criadas, repliquei a figura 9.4 com o código abaixo:

if __name__ == '__main__':     
    current_uncertainty = entropy(data_cleveland)
    values = unique_vals(data_cleveland, 0)
    x_axis = []
    y_axis = []
    tau_l = []
    tau_r = []
    for val in values:
        x_axis.append(val)
        true_rows, false_rows = partition(data_cleveland,Question(0,val))
        tau_l.append(entropy(false_rows))
        tau_r.append(entropy(true_rows))
        gain = info_gain(true_rows,false_rows,current_uncertainty)
        y_axis.append(gain)
    plt.figure()
    plt.plot(x_axis[3:],tau_l[3:])
    plt.plot(x_axis[:-1],tau_r[:-1])
    plt.xlabel("Age at split")
    plt.ylabel("i(tau_L),i(tau_R)")    

    plt.figure()
    plt.plot(x_axis,y_axis)
    plt.xlabel("Age at split")
    plt.ylabel("Goodness of Split")

A imagem será apresentada aqui.

A imagem será apresentada aqui.

E, finalmente, gerei a tabela 9.3 com o código abaixo (contém somente as 7 variáveis utilizadas na árvore).

# Encontrando o melhor split para cada variável a partir do root node:
if __name__ == '__main__': 
    best_choices = {}
    n_features = len(data_cleveland[0]) - 1
    current_uncertainty = entropy(data_cleveland)
    best_question=None
    for col in range(n_features):
        best_gain=0
        best_partition=None
        values = unique_vals(data_cleveland, col)
        for val in values:
            true_rows, false_rows = partition(data_cleveland,Question(col,val))
            gain = info_gain(true_rows,false_rows,current_uncertainty)
            #print(Question(col,val),"has gain",gain)
            if gain >= best_gain:
                best_gain = gain
                choice = ("Best split is at:", val, "with gain:",gain)
                best_choices[header[col]] = choice
    best_choices

{'age': ('Best split is at:', 55.0, 'with gain:', 0.043780618281849926),
'cp': ('Best split is at:', 4, 'with gain:', 0.13453810265164307),
'thatach': ('Best split is at:', 148.0, 'with gain:', 0.09146571773179607),
'exang': ('Best split is at:', False, 'with gain:', 0.09169989289124439),
'oldpeak': ('Best split is at:', 1.8, 'with gain:', 0.0853878337236087),
'ca': ('Best split is at:', 1.0, 'with gain:', 0.12145695220293701),
'thal': ('Best split is at:', 3, 'with gain:', 0.1444316855459763)}

Observações

  • O código foi todo construído em comandos básicos, para melhor
    entendimento da ferramenta. Aplicações mais complexas devem ficar
    lentas pela quantidade de loops e ausência de processos otimizadores
    no corpo das funções.
  • No caso categórico de variáveis com mais de 3 categorias, não
    considerei a partição em que cada ramo assume um par de valores.
    Por exemplo, se cor = azul, vermelho, amarelo e verde, podemos fazer
    o ramo da direita = azul ou vermelho e o ramo da esquerda = amarelo
    ou verde. Como no exemplo das doenças cardíacas não haviam repartições desse tipo, as desconsiderei no código.
  • O valor de corte encontrado na árvore treinada é ligeiramente diferente dos valores de corte da árvore representada no livro. Porém, note que na classificação das observações usadas no treinamento da árvore, isso não faz diferença. No caso de variáveis numéricas contínuas, a pergunta 'age > 55.5?' é o mesmo que 'age >= 56?' Ambas gerarão repartições idênticas. Teríamos diferenças somente ao classificar uma nova observação com idade decimal (suponha 55 anos e 10 meses de idade, o que equivale a 55.8). O que importa aqui é que o conjunto de treinamento será repartido da mesma forma independente da escolha entre esses valores de repartição (55.5 ou 56).
  • O nó que possui 102 pacientes saudáveis e 13 doentes (12 na árvore do livro) possui repartições diferentes (age \( >= \)58 na nossa árvore e thatach \( >= \)160.5 na ávore do livro). Acredito que essa diferença tenha vindo do paciente extra que temos no banco de dados mais recente.
+2 votos
respondida Dez 14, 2020 por Lucas Lourenço (91 pontos)  
editado Dez 15, 2020 por Lucas Lourenço
# -*- coding: utf-8 -*-
# CÓDIGO COMPLETO #
"""
Created on Sat Dec 12 10:03:59 2020

@author: lucas
"""

from __future__ import print_function
import pandas as pd
import math
from matplotlib import pyplot as plt

###### IMPORTANDO OS DADOS ######

data=pd.read_csv('Cleveland_Heart_Disease_Data.csv',sep=";")

header = []
for col in data:
    header.append(col)

data_cleveland = []
for ind in data.index:
    new_list = []
    for i in data.loc[ind]:
        new_list.append(i)
    data_cleveland.append(new_list)


###### FUNÇÕES AUXILIARES ######   


def unique_vals(rows, col):
    """Encontra os valores únicos em uma coluna de dados"""
    return set([row[col] for row in rows])

unique_vals(data_cleveland,5)

def class_counts(rows):
    """Armazena a contagem de observações de cada classe"""
    counts = {}
    for row in rows:
        label = row[-1]
        if label not in counts:
            counts[label] = 0
        counts[label] += 1
    return counts

class_counts(data_cleveland)


def is_numeric(value):
    """Testa se um valor é numérico"""
    return isinstance(value, int) or isinstance(value, float)

is_numeric(12)

def partition(rows, question):
    """
    Particiona os dados.
    Para cada linha dos dados, confere a resposta para a pergunta.
    Se True, aloca essa linha para a 'true_rows'
    Se False, aloca essa linha para a 'false_rows'
    """
    true_rows, false_rows = [], []
    for row in rows:
        if question.match(row):
            true_rows.append(row)
        else:
            false_rows.append(row)
    return true_rows, false_rows

def gini(rows):
    """ 
    Calcula o Gini de um conjunto de dados 
    """
    counts = class_counts(rows)
    impurity = 1
    for lbl in counts:
        prob_of_lbl = counts[lbl] / float(len(rows))
        impurity -= prob_of_lbl**2
    return impurity

def entropy(rows):
    """ 
    Calcula a função entropia de um conjunto de dados
    """
    impurity = float()
    counts = class_counts(rows)
    for lbl in counts:
        prob_of_lbl = counts[lbl] / float(len(rows))
        impurity -= (prob_of_lbl)*(math.log(prob_of_lbl))
    return impurity    

def info_gain(left, right, current_uncertainty):
    """
    Ganho de informação
    É a impureza do nó pai menos a média ponderada das impurezas dos nós filhos
    """
    p = float(len(left)) / (len(left) + len(right))
    #return current_uncertainty - p * gini(left) - (1 - p) * gini(right)
    return current_uncertainty - (p * entropy(left)) - ((1 - p) * entropy(right))


def find_best_split(rows):
    """
    Encontra a pergunta que melhor particiona um conjunto de dados
    Passa por todas as variáveis (colunas) e por todos os valores de partição possíveis 
    """
    best_gain = 0  
    best_question = None  
    #current_uncertainty = gini(rows)
    current_uncertainty = entropy(rows)
    n_features = len(rows[0]) - 1  
    for col in range(n_features):
        values = set([row[col] for row in rows])  
        for val in values:
            question = Question(col, val)
            true_rows, false_rows = partition(rows, question)
            if len(true_rows) == 0 or len(false_rows) == 0:
                continue
            gain = info_gain(true_rows, false_rows, current_uncertainty)
            if gain >= best_gain:
                best_gain, best_question = gain, question
    return best_gain, best_question    



###### CLASSES ######

class Question:
    """ Uma pergunta é usada para particionar os dados.
    'column' é o número da coluna da variável de interesse
    'value' é o valor de partição que se pretende utilizar
    'match' é um método que aplica a pergunta a uma linha qualquer de dados
    e retorna True se a resposta for afirmativa e False caso contrário"""

    def __init__(self, column, value):
        self.column = column
        self.value = value
    def match(self, example):
        val = example[self.column]
        if is_numeric(val):
            return val >= self.value
        else:
            return val == self.value
    def __repr__(self):
        condition = "=="
        if is_numeric(self.value):
            condition = ">="
        return "Is %s %s %s?" % (
            header[self.column], condition, str(self.value))


class Leaf_Node:
    """ O nó folha classifica os dados. É um ponto terminal da árvore.
    'predictions' é um dicionário que mostra a contagem de classes nessa folha.
    O mais comum é classificar uma nova observação a partir da classe da maioria"""

    def __init__(self, rows,level):
        self.predictions = class_counts(rows)
        self.error = min(self.predictions.values())/number_of_obs if len(self.predictions.values()) > 1 else 0 
        self.level = level
        #self.T=0
class Decision_Node:
    """ Um nó de decisão basicamente faz uma pergunta e armazena os nós filhos
    além de outros parâmetros úteis.
    'question' é um objeto da classe Question
    'true_branch' é o particionamento de dados que responde True à pergunta
    'false_branch' é o particionamento de dados que responde False à pergunta
    'rows' é o conjunto de dados que chegou até esse nó (esses dados serão particionados pela pergunta)
    'error' é o erro desse nó, calculado como [n de classificações erradas/n total de observações]
    'level' é o nível da árvore, sendo 1 o root node
    'sub_tree_error' é o erro combinado das folhas da sub-árvore formada a partir desse nó de decisão
    'T' é o número de folhas (nós terminais) da sub-árvore formada a partir desse nó de decisão
    'pruning' é a cost-complexity measure que será utilizada na podagem"""

    def __init__(self,
                 question,
                 true_branch,
                 false_branch,
                 rows,
                 level,
                 sub_tree_error,
                 T,
                 cost_complexity_pruning,
                 ):
        self.question = question
        self.true_branch = true_branch
        self.false_branch = false_branch
        self.predictions = class_counts(rows)
        self.error = min(self.predictions.values())/number_of_obs if len(self.predictions.values()) > 1 else 0 
        self.level = level
        self.sub_tree_error = sub_tree_error
        self.T = T
        self.cost_complexity_pruning = cost_complexity_pruning
        self.rows = rows  



###### FUNÇÕES PARA CONSTRUÇÃO DA ÁRVORE #######


def build_tree(rows,level=0,sub_tree_error=0,T=0):
    """
    Constroi a árvore por meio de recursão
    Recebe uma série de dados e o nível da árvore em que se encontra
    Se a melhor partição não traz ganhos -> chega-se a uma folha
    Caso contrário, efetua a partição, constrói os ramos da esquerda e da direita
    A cada recursão: 
    i) guarda o erro da sub-árvore, que é a soma dos erros das folhas que estão abaixo;
    ii) conta o número de folhas abaixo daquele nó
    Essas duas informações são finalmente usadas para construir a cost_complexity_measure
    """
    global alpha
    gain, question = find_best_split(rows)
    if gain == 0:
        return Leaf_Node(rows, level+1) 
    true_rows, false_rows = partition(rows, question)
    true_branch = build_tree(true_rows,level+1)
    false_branch = build_tree(false_rows,level+1)
    if isinstance(true_branch, Leaf_Node): 
        T += 1
    else:
        T += true_branch.T 
    if isinstance(false_branch, Leaf_Node):
        T += 1
    else:
        T += false_branch.T
    sub_tree_error += true_branch.error
    sub_tree_error += false_branch.error   
    cost_complexity_pruning = sub_tree_error + alpha*T
    return Decision_Node(question, true_branch, false_branch,rows, level+1, sub_tree_error,T,cost_complexity_pruning)


def pruning_tree(node,n):
    """
    Podagem da árvore
    Faz uma recursão parecida ao build_tree
    Se cost-complexity measure > erro do nó-pai, o nó-pai passa a ser uma folha
    O valor alpha de penalização é definido exogenamente
    """   
    if isinstance(node, Leaf_Node):
        return node
    if isinstance(node.true_branch, Leaf_Node) and isinstance(node.false_branch, Leaf_Node):
        if node.cost_complexity_pruning >= node.error:
            node = Leaf_Node(node.rows,node.level)
            return node
    elif isinstance(node.true_branch, Leaf_Node) or isinstance(node.false_branch, Leaf_Node):
        if node.cost_complexity_pruning >= node.error:
            node = Leaf_Node(node.rows,node.level)
            return node
    true_branch = pruning_tree(node.true_branch,n)
    false_branch = pruning_tree(node.false_branch,n)
    """ A partir daqui, atualizamos os parâmetros após cada poda
        pois o erro da sub-árvore e o número de nós-folha mudam"""
    node.T=0
    node.sub_tree_error=0
    if isinstance(true_branch, Leaf_Node): 
        node.T += 1
        node.sub_tree_error += true_branch.error
    else:
        node.T += true_branch.T
        node.sub_tree_error += true_branch.sub_tree_error
    if isinstance(false_branch, Leaf_Node):
        node.T += 1 
        node.sub_tree_error += false_branch.error
    else:
        node.T += false_branch.T
        node.sub_tree_error += false_branch.sub_tree_error
    node.cost_complexity_pruning = node.sub_tree_error + alpha*node.T
    new_node = Decision_Node(node.question, true_branch,false_branch,node.rows,node.level,node.sub_tree_error,node.T,node.cost_complexity_pruning)
    """O processo é repetido n vezes """
    if n==0:
        return new_node
    return pruning_tree(new_node,n-1)


def max_depth(node,Tmax):
    """
    Permitindo que a árvore cresça somente até um limite Tmax
    """
    if isinstance(node, Leaf_Node):
        return node
    if node.level >= Tmax:
        node = Leaf_Node(node.rows,node.level)
        return node
    true_branch = max_depth(node.true_branch, Tmax)
    false_branch = max_depth(node.false_branch, Tmax)
    return Decision_Node(node.question, true_branch, false_branch,node.rows, node.level, node.sub_tree_error,node.T,node.cost_complexity_pruning)    


def print_tree(node, spacing=""):
    """
    Desenha a árvore no console do Python
    """
    if isinstance(node, Leaf_Node):
        print (spacing + "Leaf Node:", "Predict", node.predictions, "Error", node.error,"Level", node.level)
        return
    print (spacing + 
               "Decision Node:", node.predictions, 
               "Error:", round(node.error,5), 
               "Level:", node.level, 
               "sub-tree error:", round(node.sub_tree_error,5), 
               "Terminal nodes beyound:", node.T, 
               "Cost-complexity pruning measure:",round(node.cost_complexity_pruning,5))
    print (spacing + str(node.question))
    print (spacing + '--> True:')
    print_tree(node.true_branch, spacing + "  ")
    print (spacing + '--> False:')
    print_tree(node.false_branch, spacing + "  ")



##### EXECUTANDO O CÓDIGO #####

# Observações

# Código construído em Python puro, sem auxílio de ferramentas de Machine Learning.
# Interessante para entender os passos algorítmicos. 
# Útil em exemplos simples. Em aplicações maiores, utilizar ferramentas mais sofisticadas. 


if __name__ == '__main__':    

    # Vamos checar o tipo de cada variável.
    for i in data_cleveland[0]:
        if is_numeric(i):
            print("Numeric")
        else:
            print("Categorical")


    # Construindo a árvore completa (cheia de overfitting):
if __name__ == '__main__':  
    alpha = 0 
    sub_tree_error=0
    T=0
    number_of_obs = len(data_cleveland)
    my_tree = build_tree(data_cleveland)
    print('')
    print('####### FULL TREE #######')
    print('')
    print_tree(my_tree)


    # Segundo Izenman, existem três formas de lidar com o overfitting em decisions trees. 
    # As duas primeiras são medidas meio grosseiras e pouco técnicas:  
    # consistem em delimitar o número de observações em um leaf node a um piso Mmin ou delimitar a profundidade da árvore a um nível Tmax. 
    # A mais recomendada consiste em podar a árvore. 
    # Isto é, primeiramente construímos a árvore inteira, até que cada folha represente uma observação (ou mais de uma observação, caso nenhuma pergunta consiga separá-las).
    # Essa árvore é excelente para o conjunto de treino, mas uma catástrofe para o de testes. A partir das folhas, subimos pela árvore sempre comparando 
    # uma medida de custo-complexidade da sub-árvore com o erro do nó de decisão que é o root node dessa sub-árvore. Se o erro do root node for
    # menor que a medida de custo-complexidade, vale a pena transformar esse nó em uma folha (isto é, podar a árvore). 
    # A medida de custo-complexidade penaliza pela quantidade de nós terminais. 
if __name__ == '__main__': 
    alpha = 0 
    sub_tree_error=0   
    T=0
    my_tree = build_tree(data_cleveland)
    pruned_tree = pruning_tree(my_tree,3)
    print('')
    print('####### PRUNED TREE #######')
    print('')
    print_tree(pruned_tree) 


    # Utilizando os métodos ad-hoc para controle do overfitting:
    # O primeiro é transformar o nó em folha sempre que o ganho for menor que dado valor escolhido.
    # Editar linha 207 [if gain == 0:]   

    # O segundo consiste em limitar os níveis da árvore.      
    alpha = 0 
    trained_tree_error = 0
    T = 0
    number_of_obs = len(data_cleveland)
    my_tree = build_tree(data_cleveland)
    choose_max_depth = 8
    final_tree=max_depth(my_tree, choose_max_depth) 
    print('')
    print('')
    print('#### MAX DEPTH TREE = %s ####'%(choose_max_depth))
    print('')
    print('')    
    print_tree(final_tree)


    # Encontrando o melhor split para cada variável a partir do root node:
if __name__ == '__main__': 
    best_choices = {}
    n_features = len(data_cleveland[0]) - 1
    current_uncertainty = entropy(data_cleveland)
    best_question=None
    for col in range(n_features):
        best_gain=0
        best_partition=None
        values = unique_vals(data_cleveland, col)
        for val in values:
            true_rows, false_rows = partition(data_cleveland,Question(col,val))
            gain = info_gain(true_rows,false_rows,current_uncertainty)
            #print(Question(col,val),"has gain",gain)
            if gain >= best_gain:
                best_gain = gain
                choice = ("Best split is at:", val, "with gain:",gain)
                best_choices[header[col]] = choice
    best_choices

    # Figura 9.4:
if __name__ == '__main__':     
    current_uncertainty = entropy(data_cleveland)
    values = unique_vals(data_cleveland, 0)
    x_axis = []
    y_axis = []
    tau_l = []
    tau_r = []
    for val in values:
        x_axis.append(val)
        true_rows, false_rows = partition(data_cleveland,Question(0,val))
        tau_l.append(entropy(false_rows))
        tau_r.append(entropy(true_rows))
        gain = info_gain(true_rows,false_rows,current_uncertainty)
        y_axis.append(gain)

    plt.plot(x_axis[3:],tau_l[3:])
    plt.plot(x_axis[:-1],tau_r[:-1])
    plt.xlabel("Age at split")
    plt.ylabel("i(tau_L),i(tau_R)")  
    plt.savefig("Fig9.3.1.png")

    plt.plot(x_axis,y_axis)
    plt.xlabel("Age at split")
    plt.ylabel("Goodness of Split")
    plt.savefig("Fig9.3.2.png")
comentou Dez 15, 2020 por Carlos Alexandre (51 pontos)  
Lucas, muito interessante a abordagem raiz que você utilizou, construindo o algoritmo do zero com o mínimo de bibliotecas possíveis (pena que deve ser um tanto chato fugir do pandas na importação de csv, já que ele o faz para um dataframe em apenas um linha). Consegui executar todo o código, tendo que alterar apenas maxT para Tmax na função max_depth() (acho que é um pequeno typo), e na geração do terceiro gráfico, se não executado o segundo gráfico, tive que definir novamente number_of_obs. E os últimos dois gráficos estão com sobreposição em único gráfico, na minha máquina (a dúvida é se foi intencional ou não, já que na resposta e no livro estão separados). Mas é um detalhe bobo, de fácil resolução.

Fiquei apenas com uma dúvida: ao gerar as árvores, os valores de corte de cada critério de divisão estão um pouco diferentes da figura do livro (por exemplo, comparando 'ca' com 1.0, na segunda divisão neste implementação, ao invés de 0.5 como no livro), apesar das divisões serem em geral as mesmas. Apenas por curiosidade, saberias a razão para esses valores de cortes serem ligeiramente diferentes do livro?

Também há uma diferença no critério escolhido para decisão do nó {'buff': 102, 'sick': 13} Level: 3 -  no livro o critério de divisão é 'thatach', ao invés de 'Is age' nesta implementação... Imagino que talvez seja em função do doente a mais que tem nessa base em relação ao dataset utilizado no livro... (seria isso)? Talvez um exercício interessante, para outra hora, seria descobrir quem é esse doente e retirá-lo da base, para que os nós fiquem idênticos ao dos autores (se for esse o motivo, esse paciente a mais está entre os 13 do {'buff': 102, 'sick': 13} Level: 3).

E apenas como curiosidade, há uma biblioteca para plot de árvores de decisão no python. Chegou a verificar se seria possível utilizá-la com pouca adaptação para o seu código?

Por fim, há alguns pequenos detalhes no texto: na equação de Gini o ' está com a barra invertida na frente, \', em vermelho; Na explicação sobre Decision_Node, em 'sub_tree_error', há um menção à equação 9.22 (fiquei com a impressão que seria apresentada em seguida), e ao final do texto, em "repliquei a figura 9.3", seria na realidade a 9.4, certo?

Achei sua resposta muito bem escrita e completa, com todos os links necessários, de fácil replicação, e principalmente por ser uma implementação partindo do nada, apenas com as funções básicas do python, além de utilizar oop.
comentou Dez 17, 2020 por Lucas Lourenço (91 pontos)  
Oi Carlos, obrigado pelos ótimos comentários. Vou comentar alguns pontos:

. Sim, eu sei o porquê dessa diferença entre os valores de corte. Note primeiro que esses valores significam exatamente a mesma coisa, pois as variáveis contínuas desse banco de dados assumem valores inteiros. A variável 'ca', por exemplo, assume valores inteiros de 0 a 3. Assim, 'ca > 0.5' é o mesmo que 'ca >= 1'. O mesmo raciocínio vale para idade ('age > 55.5' é o mesmo que 'age >= 56'). O caso em que poderia aparecer diferença seria se adicionássemos observações aos dados (um conjunto de teste, por exemplo), em que a variável 'oldpeak' de uma das observações estivesse "no meio" de uma das partições. Suponha que ao ordenar os dados, tenhamos um valor para 'oldpeak' igual a 1.5 e o seguinte igual a 1.7. A repartição do livro tentaria "is oldpeak > 1.6?" enquanto a minha seria "is oldpeak >=1.7?". Se um indivíduo de fora do banco tivesse oldpeak = 1.65, teríamos uma classificação diferente. Para replicar esse exercício, esse detalhe não faz diferença. Se trouxéssemos observações novas e quiséssemos as classificar, poderíamos ter diferenças (acredito que em variáveis com variância muito alta isso seja de fato um problema relevante). Vou inserir essa observação no texto principal.

. Os plots são gerados separadamente quando executamos as linhas de código separadamente. Irei procurar uma forma de "zerar" o plot para que eles saem separados um do outro quando o código é executado por completo.

. Eu tentei achar esse paciente doente que faz com que os bancos sejam diferentes, mas infelizmente não consegui. Eu acredito que seja a explicação mais plausível para as árvores terem feito repartições diferentes nesses nós, pois os demais casos coincidiram. Também irei adicionar esse detalhe no texto principal.

. Não sabia da biblioteca em Python para construir as árvores. Vou tentar aplicar esse código, obrigado pela dica.

. Consertei os typos, com exceção desse \' em vermelho. Isso foi uma tentativa de fazer um linha ou apóstrofe na equação. Na visualização da equação aparece corretamente, mas quando posto, fica dessa forma. Estou procurando uma alternativa na linguagem do Latex. Se alguém ler e souber, agradeceria a contribuição.

. Acrescentei a equação 9.22, de fato tinha esquecido.
comentou Dez 17, 2020 por Carlos Alexandre (51 pontos)  
Oi Lucas! Eu que agradeço! Ficou tudo bem claro! Sobre desenho das árvores, neste link tem algumas opções:
https://towardsdatascience.com/visualizing-decision-trees-with-python-scikit-learn-graphviz-matplotlib-1c50b4aa68dc. Grande abraço!
...