que critérios deve um algoritmo de árvore de decisão usar para dividir variáveis / colunas?

Antes de construir um algoritmo de árvore de decisão, o primeiro passo é responder a esta pergunta. Vamos dar uma olhada em uma das maneiras de responder a esta pergunta. Para isso, precisamos entender um uso de alguns conceitos chave da teoria da informação.

vamos examinar este método tomando as seguintes medidas:

1. dê uma olhada muito breve no que é uma árvore de decisão.
2. Define e examina a fórmula para a Entropia.
3. Discuss what a Bit is in information theory.Define ganho de informação e usa entropia para o calcular.
4. escreva algumas funções básicas em Python usando os conceitos acima.

na ciência dos dados, o algoritmo da árvore de decisão é um algoritmo de aprendizagem supervisionado para problemas de classificação ou regressão. Nosso objetivo final é usar dados históricos para prever um resultado. Ao contrário da regressão linear, as árvores de decisão podem captar interações não lineares entre variáveis nos dados.

vamos olhar para uma árvore de decisão muito simples. Abaixo está um fluxo de trabalho que pode ser usado para tomar uma decisão sobre se comer ou não um biscoito de manteiga de amendoim.

neste exemplo, uma árvore de decisão pode pegar no fato de que você só deve comer o cookie se determinados critérios forem atendidos. Este é o objetivo final de uma árvore de decisão. Queremos continuar a tomar decisões (splits) até que certos critérios sejam cumpridos. Uma vez que nos encontramos podemos usá-lo para classificar ou fazer uma previsão. Este exemplo é muito básico usando apenas duas variáveis (alergia, arruinando o jantar). Mas, se você tem um conjunto de dados com milhares de variáveis/colunas, como você decide quais variáveis / colunas são as mais eficientes para dividir? Uma maneira popular de resolver este problema, especialmente se usando um algoritmo ID3, é usar entropia e ganho de informação.

a tarefa

digamos que temos alguns dados e queremos usá-los para fazer um questionário online que prevê algo sobre o participante do questionário. Depois de olhar para as relações nos dados, decidimos usar um algoritmo de árvore de decisão. Se você nunca foi sugado para um questionário online, você pode ver centenas de exemplos aqui. O objetivo do questionário será adivinhar se o entrevistador é de um dos estados do midwest da América. As perguntas no questionário vão girar em torno de se eles gostam de um determinado tipo de alimento ou não. Abaixo tem um pequeno conjunto de dados fictícios com quinze entradas. Cada entrada tem respostas para uma série de perguntas. A maioria das perguntas são sobre se eles gostaram de um determinado tipo de alimento, em que o participante respondeu (1) Para sim ou (0) por enquanto. A última coluna (“midwest?”) é a nossa coluna alvo, o que significa que uma vez que a árvore de decisão é construída, esta é a classificação que estamos tentando adivinhar.

Entropia

Para começar, vamos utilizar uma teoria da informação métrica chamada entropia. Em ciência dos dados, a entropia é usada como uma forma de medir como “mista” uma coluna é. Especificamente, a entropia é usada para medir a desordem. Vamos começar por encontrar a entropia da nossa coluna alvo, ” midwest?”.

, são dez pessoas que vivem no centro-oeste e cinco pessoas que não. Se alguém ia perguntar-lhe como misto a coluna é, você poderia dizer que ele era uma espécie de misto, com a maioria(2/3) dos povos do centro-oeste. A Entropia nos dá uma maneira de quantificar a resposta “meio mista”. Quanto mais misturados os (1)s e (0)s na coluna São, maior é a Entropia. Se ” midwest?”tinha quantidades iguais de (1)s e (0) s nossa entropia seria 1. Se ” midwest?”consisted only of (1) s the entropy would be 0.

podemos usar a seguinte fórmula para calcular a entropia:

Vamos através de cada passo da fórmula e calcular a entropia para a “centro-oeste?” coluna.

1. precisamos iterar através de cada valor único em uma única coluna e atribuí-lo a I. Por exemplo, temos 2 casos (c) no ” midwest?”coluna, quer (0) quer (1).então calculamos a probabilidade desse valor ocorrer nos dados. Para o caso de (1), a probabilidade é 10/15. Para o caso de (0), a probabilidade é de 5/15.
2. tomamos a probabilidade de cada caso e a multiplicamos pela base logaritmo 2 da probabilidade. 2 é a base mais comum porque a entropia é medida em bits(mais sobre isso mais tarde). A explicação completa de por que 2 é usado está fora do escopo deste post, mas um usuário na stack exchange oferece uma boa explicação. Para o caso de(1), temos 10/15*log2 (10/15). Para o caso de (0), temos 5/15*log2(5/15). a seguir, pegamos no nosso produto de cada caso acima e somamo-lo. For this example, 10/15 * log2(10/15) + 5/15*log2 (5/15).
3. finalmente, Nós negamos a soma total de cima, — (10/15 * log2(10/15) + 5/15*log2 (5/15)).

uma Vez que colocamos os passos todos juntos temos o abaixo:

a Nossa final é a entropia .918278. Então, o que é que isso significa?

teoria da Informação e um pouco de informação

avançando será importante compreender o conceito de bit. Na teoria da informação, um bit é pensado como um número binário representando 0 para nenhuma informação e 1 para um bit completo de informação. Nós podemos representar um pouco da informação como um número binário porque ou tem o valor (1) ou (0). Suponha que haja uma probabilidade igual de chover amanhã (1) ou não chover(0). Se te disser que vai chover amanhã, dou-te um pouco de informação.também podemos pensar na entropia como informação. Suponha que temos um dado carregado de seis lados que sempre aterra em (3). Cada vez que rodamos o dado, sabemos antecipadamente que o resultado será (3). Não obtemos novas informações rodando o dado, então a entropia é 0. Por outro lado, se o dado é longe e nós rolamos a (3) havia uma chance de 1/6 em rolar o (3). Agora obtivemos informações. Assim, rolar o dado dá — nos um pouco de informação-de que lado o número aterrou.

para um mergulho mais profundo no conceito de um pouco de informação, você pode ler mais aqui.

recebemos menos de um” bit ” de informação — apenas .918278-porque há mais (1)s no “midwest?”a coluna que (0)s. Isso significa que, se estávamos prevendo um novo valor, poderíamos supor que a resposta é a (1) e ser direito mais frequentemente do que errado (porque há 2/3 de probabilidade de resposta: 1). Devido a este conhecimento prévio, ganhamos menos do que um “bit” completo de informação quando observamos um novo valor.

usando a entropia para tomar decisões

nosso objetivo é encontrar a melhor variável(s)/coluna(S) para dividir ao construir uma árvore de decisão. Eventualmente, queremos continuar a dividir as variáveis / colunas até que a nossa coluna alvo mista não seja mais misturada.por exemplo, vamos ver a entropia do ” midwest?”column after we have split our dataset on the” potato_salad?” coluna.

Above, our dataset is split in two sections. Do lado esquerdo, todos os que gostam de salada de batata. No lado direito todos os que não o fazem. nós preenchemos o foco no lado esquerdo que agora tem sete pessoas do midwest e duas pessoas que não são. usando a fórmula para entropia na coluna do midwest dividido à esquerda a nova entropia é .764204. Isto é óptimo! O nosso objectivo é baixar a entropia e partimos .918278 to .764204. Mas, não podemos parar por aí, se olharmos para a coluna direita nossa entropia subiu como há uma quantidade igual de (1)s e (0)s. O que precisamos é de uma maneira de ver como a Entropia muda em ambos os lados da divisão. A fórmula para o ganho de informação fará isso. Ele nos dá um número para quantificar quantos bits de informação ganhamos cada vez que dividimos nossos dados.

ganho de informação

Mais Cedo estabelecemos que queremos divisões que diminuam a entropia da nossa coluna-alvo. Quando nos separámos no “potato_salad”?”vimos a entropia no midwest?”caiu do lado esquerdo. Agora precisamos entender a Entropia total reduzida quando olhamos para ambos os lados da divisão. Vamos dar uma olhada no ganho de informação.

o ganho de informação utilizará a seguinte fórmula::

Vamos desagregação que está acontecendo aqui.vamos voltar à nossa “potato_ salad”?” exemplo. As variáveis na fórmula acima representarão o seguinte:

• T = alvo, o nosso ” midwest?”column
• A = the variable (column) we are testing, “potato_salad?”
• v = cada valor em a, cada valor na ” potato_salad?”column

1. First, we’ll calculate the orginal entropy for (T) before the split , .918278
2. em Seguida, para cada valor único (v) na variável (Um), podemos calcular o número de linhas em que (A) assume o valor (v), e dividir pelo número total de linhas. Para a “potato_salad”?”column we get 9/15 for the unique value of (1) and 6/15 for the unique value of (0).em seguida, multiplicamos os resultados pela entropia das linhas onde (a) é (v). Para a divisão esquerda (split on 1 para “potato_ salad?”) we get 9/15 * .764204. Para o lado direito da divisão ( split on 0 para “potato_ salad?”) we get 6/15 * 1. adicionamos todos estes produtos, 9/14*.764204 + 6/15 = .8585224.

5. Subtraímos então da entropia geral para obter ganho de informação .918278 -.8585224 = .059754

nosso ganho de informação é .059754. O que é que isso nos diz?aqui está uma explicação alternativa. Estamos a encontrar a entropia de cada conjunto post-split, ponderando-a pelo número de itens em cada divisão, e depois subtraindo da entropia actual. Se o resultado for positivo, reduzimos a Entropia com a separação. Quanto mais alto o resultado é, mais baixamos a Entropia.acabamos por ter .059754, o que significa que ganhamos .059754 bits de informação dividindo o nosso conjunto de dados na ” potato_ salad?”variável / coluna. O nosso ganho de informação é baixo, mas ainda é positivo, porque baixámos a entropia do lado esquerdo da divisão.

Agora precisamos repetir este processo para cada coluna que estamos usando. Em vez de fazer isto à mão, vamos escrever um código Python.

encerrando tudo com Python

Agora que compreendemos o ganho de informação, precisamos de uma forma de repetir este processo para encontrar a variável/coluna com o maior ganho de informação. Para isso, podemos criar algumas funções simples em Python.

importar os dados

vamos transformar a nossa tabela acima em um DataFrame usando a biblioteca Python pandas. Vamos importar pandas e usar a função read_csv () para fazer um DataFrame chamado “midwest”.

import pandas as pd
midwest = pd.read_csv('midwes.csv')

uma função Python para Entropia

para esta função, precisaremos da biblioteca NumPy para usar a função bincount() e o módulo matemático para usar a função log ().

import numpy
import math

a seguir, definiremos a nossa função com um parâmetro. O argumento dado será a série, lista ou matriz de NumPy em que estamos tentando calcular a Entropia.

def calc_entropy(column):

teremos de encontrar a percentagem de cada caso na coluna. Podemos usar o numpy.função bincount () para isso. O valor de retorno é um array NumPy que irá armazenar a contagem de cada valor único a partir da coluna que foi passada como um argumento.

counts = numpy.bincount(column)

armazenaremos as probabilidades de cada valor único dividindo a matriz “contagens” pelo comprimento da coluna.

probabilities = counts / len(column)

podemos então inicializar uma variável chamada “entropy” e configurá-la como 0.

entropy = 0

Next, we can use a “for loop” to loop through each probability in our probabilities array and multiply it by the logarithm base 2 of probability using the math.função log (). Depois, adicione cada caso à nossa variável de entropia armazenada. * certifique-se de verificar que a sua probabilidade é grande que 0 caso contrário log(0) irá retornar indefinido

for prob in probabilities:
if prob > 0:
endtropy += prob * math.log(prob,2)

finalmente, vamos retornar a nossa variável de entropia negada.

return -entropy

agora, Todos juntos:

Ótimo! Agora podemos construir uma função para calcular o ganho de informação.

uma função Python para o ganho de informação

vamos precisar de definir uma função que terá três parâmetros, um para todo o conjunto de dados, um para o nome da coluna em que queremos dividir, e um para o nome da nossa coluna-alvo.

def calc_information_gain(data, split_name, target_name):

Next, we can use the entropy function from earlier to calculate the original entropy of our target column.

orginal_entropy = calc_entropy(data)

Agora precisamos dividir a nossa coluna.

*para este exemplo, só usaremos as variáveis / colunas com duas únicas. Se você quiser dividir em uma variável/coluna como “age”, existem várias maneiras de fazer isso. Uma maneira é dividir em cada valor único. Outra forma é simplificar o cálculo do ganho de informação e tornar as divisões mais simples, não dividindo para cada valor único. Em vez disso, a mediana é encontrada para a variável/cumn sendo dividida. Qualquer linha onde o valor da variável está abaixo da mediana irá para o ramo esquerdo, e o resto das linhas irá para o ramo direito. Para calcular o ganho de informação, só teremos de calcular entropias para dois subconjuntos. Nós não estaremos andando através deste método, mas uma vez que a divisão na mediana é realizada o resto dos passos seria o mesmo que descrito abaixo.

Uma vez que as colunas com as quais estamos a trabalhar têm apenas dois valores únicos, faremos uma divisão à esquerda e uma divisão à direita.vamos começar por usar os pandas.Série.unique () to give us an array of the unique values in the column

values = data.unique()

Next, we will create a left and right split using “values”.

left_split = data == values]
right_split = data == values]

Agora podemos iniciar uma variável para subtrair da nossa entropia original.

to_subtract = 0

então vamos iterar através de cada subconjunto criado pela nossa divisão, calcular a probabilidade do subconjunto, e depois adicionar o produto da probabilidade e a entropia da coluna-alvo dos subconjuntos.

for subset in :
prob = (subset.shape / data.shape)
to_subtract += prob * calc_entropy(subset)

finalmente, podemos retornar a diferença de to_subract sendo subtraída da entropia original.

return original_entropy - to_subtract

a função inteira está abaixo.

uma função Python para o maior ganho de informação

a nossa função final será aquela que irá devolver a variável / Nome da coluna com o maior ganho de informação.

Como mencionado anteriormente, estamos apenas usando as colunas com dois valores únicos para este exemplo. Vamos guardar os nomes das colunas numa lista para usar na função. Para chegar ao ponto, vamos codificar isso para este exemplo, mas em um grande conjunto de dados, seria melhor escrever código para construir esta lista dinamicamente com base nos critérios que usamos para escolher as colunas.

columns = 

vamos embrulhar o passo final numa função para que possamos reutilizá-lo quando necessário. Ele terá um parâmetro, a lista de colunas que queremos encontrar o maior ganho de informação para.

def highest_info_gain(columns):

vamos intializar um dicionário vazio para armazenar os nossos ganhos de informação.

information_gains = {}

e então podemos iterar através da lista de colunas e armazenar o resultado em nosso dicionário information_ gains.

for col in columns:
information_gain = calc_information_gain(midwest, col, 'midwest?)
information_gains = information_gain

finalmente, podemos devolver a chave do valor mais alto em nosso dicionário.

return max(information_gains, key=information_gains.get)

agora, Todos juntos:

uma Vez que nós executemos nosso último função

print(highest_info_gain(midwest, columns, 'midwest?'))
//sushi

nós vemos a variável/coluna com a informação mais ganho é ‘sushi?’.

pode-se visualizar uma divisão no sushi abaixo:

Nossa divisão esquerda tem duas pessoas de seis do centro-oeste. A divisão da direita tem oito das nove pessoas do midwest. Esta foi uma separação eficiente e baixou a entropia de ambos os lados. Se fôssemos continuar, usaríamos a recursão para continuar dividindo cada divisão com um objetivo de terminar cada ramo com uma entropia de zero.

Conclusion

Decision trees can be a useful machine learning algorithm to pick up nonlinear interactions between variables in the data. Neste exemplo, nós olhamos para os estágios iniciais de um algoritmo de classificação de árvore de decisão. Nós então olhamos para três conceitos da teoria da informação, entropia, bit, e ganho de informação. Usando estes conceitos, conseguimos construir algumas funções em Python para decidir quais variáveis/colunas eram as mais eficientes para dividir. Com uma compreensão firme sobre estes conceitos, podemos avançar para construir uma árvore de decisão.