Entropia: como as árvores de decisão tomam decisões

A lógica simples e matemática por trás de um algoritmo de aprendizado de máquina muito eficaz

Sam Blocked Unblock Seguir Seguindo 10 de janeiro

Você é um cientista de dados em treinamento. Você percorreu um longo caminho desde escrever sua primeira linha de código Python ou R. Você conhece o Scikit-Learn como a palma da sua mão. Você passa mais tempo no Kaggle do que no Facebook agora. Você não é estranho a construir florestas aleatórias impressionantes e outros modelos de conjuntos baseados em árvores que fazem o trabalho. No entanto, você não é nada se não completo. Você quer aprofundar e entender algumas das complexidades e conceitos por trás dos modelos populares de aprendizado de máquina. Bem, eu também

Neste post, apresentarei o conceito de entropia como um tópico geral em estatística que me permitirá introduzir ainda mais o conceito de ganho de informação e, subsequentemente, explicar por que esses dois conceitos fundamentais formam a base de como as árvores de decisão se constroem nos dados. nós os fornecemos.

Certo. Vamos continuar com isso então.

O que é entropia? Nos termos mais leigos, a entropia nada mais é do que a medida da desordem. (Você pode pensar nisso como uma medida de pureza também. Você vai ver. Eu gosto de desordem porque parece mais legal.)

A fórmula matemática para Entropia é a seguinte –

Entropia. Às vezes também denotado usando a letra 'H'

Onde 'Pi' é simplesmente a probabilidade frequentista de um elemento / classe 'i' em nossos dados. Para simplificar, digamos que temos apenas duas classes, uma classe positiva e uma negativa. Portanto, 'i' aqui poderia ser + ou (-). Portanto, se tivéssemos um total de 100 pontos de dados em nosso conjunto de dados com 30 pertencentes à classe positiva e 70 pertencendo à classe negativa, então 'P +' seria 3/10 e 'P-' seria 7/10. Bem direto.

Se eu fosse calcular a entropia das minhas classes neste exemplo usando a fórmula acima. Aqui está o que eu teria.

A entropia aqui é aproximadamente 0,88. Isto é considerado uma alta entropia, um alto nível de desordem (significando baixo nível de pureza). A entropia é medida entre 0 e 1. (Dependendo do número de classes no seu conjunto de dados, a entropia pode ser maior que 1, mas significa a mesma coisa, um nível muito alto de desordem. Por uma questão de simplicidade, os exemplos neste blog terá entropia entre 0 e 1).

Dê uma olhada neste gráfico abaixo.

Provost, Foster; Fawcett, Tom. Data Science for Business: o que você precisa saber sobre mineração de dados e pensamento analítico de dados

O eixo x mede a proporção de pontos de dados pertencentes à classe positiva em cada bolha e o eixo do eixo y mede suas respectivas entropias. Logo, você pode ver a forma 'U' invertida do gráfico. A entropia é menor nos extremos, quando a bolha não contém instâncias positivas ou apenas instâncias positivas. Ou seja, quando a bolha é pura, a desordem é 0. A entropia é mais alta no meio quando a bolha é dividida igualmente entre instâncias positivas e negativas. Desordem extrema, porque não há maioria.

Isso importa por que a entropia é medida usando a base de log 2 ou por que a entropia é medida entre 0 e 1 e não alguma outra faixa? Não. É apenas uma métrica. Não é importante saber como isso aconteceu. É importante saber ler e o que nos diz, o que acabamos de fazer. A entropia é uma medida de desordem ou incerteza e o objetivo dos modelos de aprendizado de máquina e dos cientistas de dados em geral é reduzir a incerteza.

Agora sabemos como medir a desordem. Em seguida, precisamos de uma métrica para medir a redução desse transtorno em nossa variável-alvo / classe, dada a informação adicional (características / variáveis independentes) sobre ela. É aqui que entra o Information Gain. Matematicamente pode ser escrito como:

Ganho de informação de X em Y

Nós simplesmente subtraímos a entropia de Y dado X da entropia de apenas Y para calcular a redução da incerteza sobre Y, dado uma informação adicional X sobre Y. Isso é chamado de Ganho de Informação. Quanto maior a redução dessa incerteza, mais informações são obtidas sobre Y de X.

Deixe-me ilustrar com um exemplo usando uma tabela de contingência simples e, em seguida, reunirei tudo como as árvores de decisões usam a entropia e o ganho de informações para decidir em qual recurso dividir seus nós à medida que estão sendo treinados em um conjunto de dados.

Exemplo: tabela de contingência

Tabela de Contingência

Aqui, nossa variável alvo é Responsabilidade, que pode assumir dois valores “Normal” e “Alta” e temos apenas um recurso chamado Rating de Crédito, que pode assumir valores “Excelente”, “Bom” e “Ruim”. Há um total de 14 observações. 7 deles pertencem à classe de Responsabilidade Normal e 7 pertencem à Classe de Alta Responsabilidade. Então é um mesmo dividido por si mesmo. Somando-se a linha superior, podemos ver que há 4 observações que têm valor Excelente para o rating de crédito do recurso. Além disso, também posso ver como minha variável de meta é dividida para o Rating de Crédito "Excelente". Para as observações que tomam o valor “Excelente” para sua classificação de crédito, existem 3 que pertencem à classe de Responsabilidade Normal e somente 1 que pertence à classe de Alta Responsabilidade. Eu posso similarmente descobrir esses valores para outros valores de Rating de Crédito da tabela de contingência.

Para esta ilustração, usarei essa tabela de contingência para calcular a entropia de nossa variável de destino sozinha e, em seguida, calcular a entropia de nossa variável de destino, com informações adicionais sobre o recurso, classificação de crédito. Isso permitirá que eu calcule quantas informações adicionais o "Rating de Crédito" fornece para minha variável-alvo "Responsabilidade".

Vamos chegar a isso então.

A entropia de nossa variável alvo é 1, no máximo, devido à divisão entre os rótulos de classe “Normal” e “High”. Nosso próximo passo é calcular a entropia de nossa variável alvo. Responsabilidade dada informações adicionais sobre a pontuação de crédito. Para isso, calcularemos a entropia de Responsabilidade para cada valor de Pontuação de Crédito e os adicionaremos usando uma média ponderada da proporção de observações que terminam em cada valor. Por que usamos uma média ponderada ficará mais clara quando discutirmos isso no contexto das árvores de decisão.

Recebemos a entropia para nossa variável de destino, dado o recurso Rating de crédito. Agora podemos calcular o ganho de informações sobre responsabilidade do Rating de crédito para ver como esse recurso é informativo.

Conhecer o Rating de Crédito nos ajudou a reduzir a incerteza em torno de nossa variável alvo, Responsabilidade! Não é isso que um bom recurso deve fazer? Fornece informações sobre nossa variável de destino? Bem, é exatamente assim e por que as árvores de decisão usam entropia e ganho de informações para determinar qual recurso dividir seus nós para se aproximar da previsão da variável de destino com cada divisão e também para determinar quando parar de dividir a árvore! (além de hiper-parâmetros como profundidade máxima do curso). Vamos ver isso em ação com outro exemplo usando árvores de decisão.

Exemplo: Árvore de Decisão

Considere um exemplo em que estamos construindo uma árvore de decisão para prever se um empréstimo concedido a uma pessoa resultaria em uma baixa ou não. Nossa população inteira é composta por 30 instâncias. 16 pertencem à classe de write-off e os outros 14 pertencem à classe de não-write-off. Temos dois recursos, a saber, "Equilíbrio", que pode assumir dois valores -> "<50K" ou "> 50K" e "Residência", que podem assumir três valores -> "OWN", "RENT" ou "OTHER". Vou mostrar a você como um algoritmo de árvore de decisão decidiria qual atributo dividir primeiro e que recurso fornece mais informações ou reduz mais incerteza sobre nossa variável de destino usando os conceitos Entropy e Information Gain.

Recurso 1: Equilíbrio

Provost, Foster; Fawcett, Tom. Data Science for Business: o que você precisa saber sobre mineração de dados e pensamento analítico de dados

Os pontos são os pontos de dados com a classe direita e as estrelas são as não-anulações. A divisão do nó pai no equilíbrio de atributos nos dá dois nós filhos. O nó da esquerda obtém 13 das observações totais com 12/13 (0,92 probabilidade) observações da classe de write-off e apenas 1/13 (0,08 probabilidade) observações da não-escrita da classe. O nó direito obtém 17 da observação total com observações de 13/17 (0,76 probabilidade) da classe não cancelável e 4/17 (probabilidade 0,24) da classe de baixa.

Vamos calcular a entropia para o nó pai e ver quanta incerteza a árvore pode reduzir dividindo no Equilíbrio.

Dividindo em recurso, "Balance" leva a um ganho de informação de 0.37 na nossa variável de destino. Vamos fazer a mesma coisa para o recurso "Residência" para ver como ele se compara.

Recurso 2: Residência

Provost, Foster; Fawcett, Tom. Data Science for Business: o que você precisa saber sobre mineração de dados e pensamento analítico de dados

Dividir a árvore na residência nos dá 3 nós filhos. O nó filho esquerdo obtém 8 das observações totais com observações de 7/8 (probabilidade de 0,88) da classe de write-off e apenas 1/8 (0.12 probabilidade) de observações da classe de não-write-off. Os nós do meio do filho obtêm 10 das observações totais com observações de 4/10 (0,4 de probabilidade) da classe de write-off e 6/10 (0,6 de probabilidade) da classe non-write-off. O nó filho direito recebe 12 das observações totais com 5/12 (0,42 probabilidade) observações da classe de write-off e 7/12 (0,58) observações da classe não write-off. Nós já sabemos a entropia para o nó pai. Nós simplesmente precisamos calcular a entropia após a divisão para computar o ganho de informação da “Residência”.

O ganho de informação do recurso, o Equilíbrio é quase 3 vezes mais que o ganho de informação da Residência! Se você voltar e dar uma olhada nos gráficos, verá que os nós filhos da divisão no Equilíbrio parecem mais puros do que os da Residência. No entanto, o nó mais à esquerda para residência também é muito puro, mas é aí que as médias ponderadas entram em jogo. Mesmo que esse nó seja muito puro, ele tem a menor quantidade de observações totais e um resultado contribui com uma pequena porção de sua pureza quando calculamos a entropia total a partir da divisão em Residence. Isso é importante porque procuramos poder informativo geral de um recurso e não queremos que nossos resultados sejam distorcidos por um valor raro em um recurso.

Por si só, o recurso Equilíbrio fornece mais informações sobre nossa variável de destino do que a Residência. Reduz mais desordem em nossa variável de destino. Um algoritmo de árvore de decisão usaria esse resultado para fazer a primeira divisão em nossos dados usando o Equilíbrio. Daqui em diante, o algoritmo da árvore de decisão usaria esse processo em cada divisão para decidir qual recurso será dividido na próxima. Em um cenário do mundo real, com mais de dois recursos, a primeira divisão é feita no recurso mais informativo e, em cada divisão, o ganho de informação para cada recurso adicional precisa ser recalculado, porque não seria o mesmo que o ganho de informação de cada recurso por si só. A entropia e o ganho de informação teriam que ser calculados após uma ou mais divisões já terem sido feitas, o que mudaria os resultados. Uma árvore de decisão repetiria esse processo à medida que ele se desenvolvesse cada vez mais até atingir uma profundidade predefinida ou se nenhuma divisão adicional pudesse resultar em um ganho de informação maior além de um certo limite, que também pode ser especificado como um hiper-parâmetro!

Lá você tem isso! Agora você sabe o que é entropia e o ganho de informação e como eles são computados. Você entende como uma árvore de decisão, por si só ou em um grupo baseado em árvores, decide sobre a melhor ordem de recursos para dividir e decide quando parar quando treina em dados específicos. Se cada um de vocês tiver que explicar as complexidades de como as árvores de decisão funcionam para alguém, espero que você não faça muito mal.

Espero que você tenha conseguido algum valor desse post. Se houver algo que eu perdi ou algo foi impreciso ou se você tiver absolutamente qualquer feedback, por favor me avise nos comentários. Eu apreciaria muito. Obrigado.