Algoritmo ID3 - ID3 algorithm

Árvore de decisão potencial gerada por ID3. Os atributos são organizados como nós pela capacidade de classificar exemplos. Os valores dos atributos são representados por ramos.

Na aprendizagem da árvore de decisão , ID3 ( Dicotomizador Iterativo 3 ) é um algoritmo inventado por Ross Quinlan usado para gerar uma árvore de decisão a partir de um conjunto de dados. ID3 é o precursor do algoritmo C4.5 e é normalmente usado nos domínios de aprendizado de máquina e processamento de linguagem natural .

Algoritmo

O algoritmo ID3 começa com o conjunto original como o nó raiz . Em cada iteração do algoritmo, ele itera por meio de cada atributo não utilizado do conjunto e calcula a entropia ou o ganho de informação desse atributo. Em seguida, ele seleciona o atributo que possui o menor valor de entropia (ou maior ganho de informação). O conjunto é então dividido ou particionado pelo atributo selecionado para produzir subconjuntos dos dados. (Por exemplo, um nodo pode ser dividida em nós filhos com base nas sub-grupos da população com idades são menos do que 50, entre 50 e 100, e maior do que 100.) O algoritmo continua a recursividade em cada subconjunto, considerando apenas os atributos Nunca selecionado antes. ${\ displaystyle S}$${\ displaystyle S}$ ${\ displaystyle \ mathrm {H} {(S)}}$ ${\ displaystyle IG (S)}$${\ displaystyle S}$

A recursão em um subconjunto pode parar em um destes casos:

• cada elemento do subconjunto pertence à mesma classe; nesse caso, o nó é transformado em um nó folha e rotulado com a classe dos exemplos.
• não há mais atributos a serem selecionados, mas os exemplos ainda não pertencem à mesma classe. Nesse caso, o nó é transformado em nó folha e rotulado com a classe mais comum dos exemplos no subconjunto.
• não há exemplos no subconjunto , o que acontece quando nenhum exemplo no conjunto pai foi encontrado para corresponder a um valor específico do atributo selecionado. Um exemplo pode ser a ausência de uma pessoa na população com idade superior a 100 anos. Em seguida, um nó folha é criado e rotulado com a classe mais comum dos exemplos no conjunto do nó pai.

Ao longo do algoritmo, a árvore de decisão é construída com cada nó não terminal (nó interno ) representando o atributo selecionado no qual os dados foram divididos e nós terminais (nós folha) representando o rótulo de classe do subconjunto final desta ramificação.

Resumo

1. Calcule a entropia de cada atributo do conjunto de dados . ${\ displaystyle a}$${\ displaystyle S}$
2. Particionar ("dividir") o conjunto em subconjuntos usando o atributo para o qual a entropia resultante após a divisão é minimizada ; ou, equivalentemente, o ganho de informação é máximo . ${\ displaystyle S}$
3. Faça um nó da árvore de decisão contendo esse atributo.
4. Recurse em subconjuntos usando os atributos restantes.

Pseudo-código

ID3 (Examples, Target_Attribute, Attributes)
    Create a root node for the tree
    If all examples are positive, Return the single-node tree Root, with label = +.
    If all examples are negative, Return the single-node tree Root, with label = -.
    If number of predicting attributes is empty, then Return the single node tree Root,
    with label = most common value of the target attribute in the examples.
    Otherwise Begin
        A ← The Attribute that best classifies examples.
        Decision Tree attribute for Root = A.
        For each possible value, vi, of A,
            Add a new tree branch below Root, corresponding to the test A = vi.
            Let Examples(vi) be the subset of examples that have the value vi for A
            If Examples(vi) is empty
                Then below this new branch add a leaf node with label = most common target value in the examples
            Else below this new branch add the subtree ID3 (Examples(vi), Target_Attribute, Attributes – {A})
    End
    Return Root

Propriedades

Árvore de decisão gerada por ID3 usada para determinar se um par de nucleotídeos específico dentro de uma sequência de pré-mRNA corresponde a um local de splice de mRNA. Esta árvore demonstrou ter uma taxa de previsão correta de 95%.

ID3 não garante uma solução ideal. Pode convergir para ótimos locais . Ele usa uma estratégia gananciosa, selecionando o melhor atributo localmente para dividir o conjunto de dados em cada iteração. A otimização do algoritmo pode ser melhorada usando backtracking durante a busca pela árvore de decisão ótima ao custo de possivelmente demorar mais.

ID3 pode sobrecarregar os dados de treinamento. Para evitar overfitting, árvores de decisão menores devem ser preferidas a árvores maiores. Esse algoritmo geralmente produz pequenas árvores, mas nem sempre produz a menor árvore de decisão possível.

ID3 é mais difícil de usar em dados contínuos do que em dados fatorados (os dados fatorados têm um número discreto de valores possíveis, reduzindo assim os possíveis pontos de ramificação). Se os valores de qualquer atributo fornecido forem contínuos , então haverá muitos mais lugares para dividir os dados neste atributo e procurar o melhor valor para dividir pode ser demorado.

Uso

O algoritmo ID3 é usado pelo treinamento em um conjunto de dados para produzir uma árvore de decisão que é armazenada na memória . Em tempo de execução , essa árvore de decisão é usada para classificar novos casos de teste ( vetores de recursos ) ao percorrer a árvore de decisão usando os recursos do datum para chegar a um nó folha. A classe deste nó terminal é a classe em que o caso de teste é classificado. ${\ displaystyle S}$

As métricas ID3

Entropia

Entropia é uma medida da quantidade de incerteza no conjunto ( dados) (isto é, a entropia caracteriza o conjunto (dados) ). ${\ displaystyle \ mathrm {H} {(S)}}$${\ displaystyle S}$${\ displaystyle S}$

${\ displaystyle \ mathrm {H} {(S)} = \ sum _ {x \ in X} {- p (x) \ log _ {2} p (x)}}$

Onde,

• ${\ displaystyle S}$ - O conjunto de dados atual para o qual a entropia está sendo calculada
  • Isso muda em cada etapa do algoritmo ID3, seja para um subconjunto do conjunto anterior no caso de divisão em um atributo ou para uma partição "irmã" do pai no caso de a recursão ter terminado anteriormente.
• ${\ displaystyle X}$ - O conjunto de classes em ${\ displaystyle S}$
• ${\ displaystyle p (x)}$ - A proporção do número de elementos na classe para o número de elementos no conjunto ${\ displaystyle x}$${\ displaystyle S}$

Quando , o conjunto está perfeitamente classificado (ou seja, todos os elementos em são da mesma classe). ${\ displaystyle \ mathrm {H} {(S)} = 0}$${\ displaystyle S}$${\ displaystyle S}$

Em ID3, a entropia é calculada para cada atributo restante. O atributo com a menor entropia é usado para dividir o conjunto nesta iteração. A entropia na teoria da informação mede a quantidade de informação que se espera obter ao medir uma variável aleatória ; como tal, também pode ser usado para quantificar a quantidade para a qual a distribuição dos valores da quantidade é desconhecida. Uma quantidade constante tem entropia zero, pois sua distribuição é perfeitamente conhecida . Em contraste, uma variável aleatória uniformemente distribuída ( discreta ou continuamente uniforme) maximiza a entropia. Portanto, quanto maior a entropia em um nó, menos informações são conhecidas sobre a classificação dos dados neste estágio da árvore; e, portanto, quanto maior o potencial para melhorar a classificação aqui. ${\ displaystyle S}$

Como tal, ID3 é uma heurística gananciosa que realiza uma busca "best-first" para valores de entropia localmente ideais . Sua precisão pode ser melhorada com o pré-processamento dos dados.

Ganho de informação

O ganho de informação é a medida da diferença na entropia de antes para depois que o conjunto é dividido em um atributo . Em outras palavras, quanta incerteza foi reduzida após a divisão definida no atributo . ${\ displaystyle IG (A)}$${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle A}$

${\ displaystyle IG (S, A) = \ mathrm {H} {(S)} - \ sum _ {t \ in T} p (t) \ mathrm {H} {(t)} = \ mathrm {H} {(S)} - \ mathrm {H} {(S | A)}.}$

Onde,

• ${\ displaystyle \ mathrm {H} (S)}$ - Entropia do conjunto ${\ displaystyle S}$
• ${\ displaystyle T}$ - Os subconjuntos criados a partir da divisão definida por atributo de forma que ${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle S = \ bigcup _ {t \ in T} t}$
• ${\ displaystyle p (t)}$ - A proporção do número de elementos em relação ao número de elementos no conjunto ${\ displaystyle t}$${\ displaystyle S}$
• ${\ displaystyle \ mathrm {H} (t)}$ - Entropia do subconjunto ${\ displaystyle t}$

Em ID3, o ganho de informação pode ser calculado (em vez da entropia) para cada atributo restante. O atributo com o maior ganho de informação é usado para dividir o conjunto nesta iteração. ${\ displaystyle S}$

Veja também

• Árvore de classificação e regressão (CART)
• Algoritmo C4.5
• Aprendizagem da árvore de decisão
  • Modelo de árvore de decisão

Referências

Leitura adicional

• Mitchell, Tom Michael (1997). Aprendizado de máquina . New York, NY: McGraw-Hill. pp.  55 -58. ISBN   0070428077 . OCLC   36417892 .
• Grzymala-Busse, Jerzy W. (fevereiro de 1993). "Algoritmos selecionados de aprendizado de máquina a partir de exemplos" (PDF) . Fundamenta Informaticae . 18 (2): 193–207 - via ResearchGate.

links externos

• Seminários - http://www2.cs.uregina.ca/
• Descrição e exemplos - http://www.cise.ufl.edu/
• Descrição e exemplos - http://www.cis.temple.edu/
• Árvores de decisão e classificação dos partidos políticos