Referência técnica do algoritmo Árvores de Decisão da Microsoft

O algoritmo Árvores de Decisão da Microsoft é um híbrido que incorpora métodos diferentes para a criação de uma árvore e dá suporte a várias tarefas analíticas, incluindo regressão, classificação e associação. O algoritmo Árvores de Decisão da Microsoft é dá suporte à modelagem de atributos discretos e contínuos.

Este tópico explica a implementação do algoritmo, descreve como personalizar o comportamento do algoritmo para tarefas diferentes e fornece links para informações adicionais sobre como consultar modelos de árvore de decisão.

Implementação do algoritmo Árvores de Decisão

O algoritmo Árvores de Decisão da Microsoft aplica a abordagem Bayesiana para aprender os modelos de interação causal obtendo distribuições posteriores aproximadas dos modelos. Para obter uma explicação detalhada dessa abordagem, consulte o documento no site Microsoft Research de Meek e Heckerman.

A metodologia para avaliar o valor das informações a priori necessárias para o aprendizado se baseia na suposição da equivalência de probabilidade. Essa pressuposição afirma que os dados não devem ajudar a discriminar estruturas de rede que de outra forma representam as mesmas asserções de independência condicional. Pressupõe-se que cada caso tenha uma única rede Bayesiana a priori e uma única medida de confiança para essa rede.

Com o uso dessas redes a priori, o algoritmo calcula as probabilidades posteriores relativas das estruturas de rede, de acordo com os dados de treinamento atuais, e identifica as estruturas de rede que têm as probabilidades posteriores mais altas.

O algoritmo Árvores de Decisão da Microsoft usa métodos diferentes para calcular a melhor árvore. O método usado depende da tarefa que pode ser regressão linear, classificação ou análise de associação. Um único modelo pode conter várias árvores para atributos previsíveis diferentes. Além disso, cada árvore pode conter várias ramificações, de acordo com a quantidade de atributos e valores nos dados. A forma e a intensidade da árvore criada em um determinado modelo dependem do método de pontuação e de outros parâmetros utilizados. Alterações aos parâmetros também podem afetar o local em que os nós são divididos.

Criando a árvore

Quando o algoritmo Árvores de Decisão da Microsoft cria o conjunto de valores de entrada possíveis, ele executa feature selection para identificar os atributos e os valores que fornecem a maioria das informações e remove da consideração os valores que são muito raros. O algoritmo também agrupa valores em compartimentos, para criar agrupamentos de valores que podem ser processados como uma unidade para otimizar o desempenho.

Uma árvore é criada com a determinação das correlações entre uma entrada e o resultado pretendido. Depois que todos os atributos tiverem sido correlacionados, o algoritmo identificará o único atributo que separa mais claramente os resultados. Este ponto da melhor separação é medido com o uso de uma equação que calcula o ganho de informações. o atributo com a melhor pontuação de ganho de informações é usado para dividir os casos em subconjuntos, que são analisados recursivamente pelo mesmo processo, até que não seja mais possível dividir a árvore.

A equação exata usada para avaliar o ganho de informações depende dos parâmetros definidos quando você criou o algoritmo, do tipo de dados da coluna previsível e do tipo de dados da entrada.

Entradas discretas e contínuas

Quando o atributo previsível é discreto e as entradas previsíveis também, contar os resultados por entrada é uma questão de criar uma matriz e gerar pontuações para cada célula na matriz.

No entanto, quando o atributo previsível é discreto e as entradas são contínuas, a entrada das colunas contínuas é discreta automaticamente. Você pode aceitar o padrão e fazer com que o Analysis Services encontre o número ideal de compartimentos ou pode controlar a maneira pela qual as entradas contínuas são discretizadas configurando as propriedades DiscretizationMethod e DiscretizationBucketCount. Para obter mais informações, consulte Alterar a diferenciação de uma coluna em um modelo de mineração.

No caso de atributos contínuos, o algoritmo usa a regressão linear para determinar onde uma árvore de decisão se divide.

Quando o atributo previsível é um tipo de dados numérico contínuo, a seleção de recursos é aplicada às saídas também, para reduzir o número possível de resultados e criar o modelo mais rapidamente. Você pode alterar o limite de seleção de recursos e, portanto, aumentar ou diminuir o número de valores possíveis configurando o parâmetro MAXIMUM_OUTPUT_ATTRIBUTES.

Para obter uma explicação mais detalhada sobre como o algoritmo Árvores de Decisão da Microsoft funciona com colunas previsíveis distintas, consulte Learning Bayesian Networks: The Combination of Knowledge and Statistical Data (Aprendendo redes bayesianas: a combinação de dados estatísticos e conhecimento). Para obter mais informações sobre como o algoritmo Árvores de Decisão da Microsoft funciona com uma coluna previsível contínua, consulte o apêndice de Modelos de árvore de regressão automática para análise de série temporal.

Métodos de pontuação e seleção de recursos

O algoritmo Árvores de Decisão da Microsoft oferece três fórmulas para pontuar o ganho de informação: entropia de Shannon, rede bayesiana com antecedente K2 e rede bayesiana com uma distribuição Dirichlet uniforme de antecedentes. Todos os três métodos são bem-estabelecidos no campo de mineração de dados. É recomendável fazer experiências com parâmetros e métodos de pontuação diferentes para determinar aqueles que fornecem os melhores resultados. Para obter mais informações sobre esses métodos de pontuação, consulte Seleção de recursos.

Todos os algoritmos de mineração de dados Analysis Services usam seleção de recursos automaticamente para melhorar a análise e reduzir a carga de processamento. O método usado para seleção de recursos depende do algoritmo utilizado para criar o modelo. Os parâmetros de algoritmo que controlam seleção de recursos para um modelo de árvores de decisão são MAXIMUM_INPUT_ATTRIBUTES e MAXIMUM_OUTPUT.

Algoritmo	Método de análise	Comentários
Árvores de decisão	Pontuação de interesse Entropia de Shannon Bayesiano com precedência K2 Bayesiano Dirichlet com precedência uniforme (padrão)	Se qualquer coluna contiver valores contínuos não binários, a pontuação de interesse será usada em todas as colunas para garantir a consistência. Caso contrário, será usado o método padrão ou o especificado.
Regressão Linear	Pontuação de interesse	A Regressão Linear usa apenas o interesse, pois suporta apenas colunas contínuas.

Escalabilidade e desempenho

A classificação é uma estratégia de mineração de dados importante. Em geral, a quantidade de informações necessária para classificar os casos aumenta em proporção direta ao número de registros de entrada. Isso limita o tamanho dos dados que podem ser classificados. O algoritmo Árvores de Decisão da Microsoft usa os seguintes métodos para resolver esses problemas, melhorar o desempenho e eliminar as restrições de memória:

• Seleção de recursos para otimizar a seleção dos atributos.

• Pontuação Bayesiana para controlar o crescimento da árvore.

• Otimização de compartimentos para atributos contínuos.

• Agrupamento dinâmico de valores de entrada para determinar os valores mais importantes.

O algoritmo Árvores de Decisão da Microsoft é rápido e escalonável, e foi projetado para paralelização fácil, o que significa que todos os processadores funcionam em conjunto para criar um único modelo consistente. A combinação dessas características torna o classificador de árvore de decisão uma ferramenta ideal para mineração de dados.

Se as restrições de desempenho forem graves, talvez você possa melhorar o tempo de processamento durante o treinamento de um modelo de árvore de decisão usando os métodos a seguir. No entanto, se você fizer isso, saiba que eliminar atributos para melhorar o desempenho de processamento alterará os resultados do modelo e possivelmente o tornará menos representativo da população total.

• Aumente o valor do parâmetro COMPLEXITY_PENALTY para limitar o crescimento de árvore.

• Limite o número de itens em modelos de associação para limitar o número de árvores criadas.

• Aumente o valor do parâmetro MINIMUM_SUPPORT para evitar sobreajuste.

• Restrinja o número de valores discretos de qualquer atributo para 10 ou menos. Você pode tentar agrupar valores de modos diferentes em modelos diferentes.

  Observação

  É possível usar as ferramentas de exploração de dados disponíveis no SQL Server 2012 Integration Services (SSIS) para visualizar a distribuição de valores nos dados e agrupar os valores apropriadamente antes de iniciar a mineração de dados. Para obter mais informações, consulte Tarefa e visualizador da tarefa Criação de Perfil de Dados. Também é possível usar os Suplementos de Mineração de Dados para Excel 2007 para explorar, agrupar e rotular novamente os dados no Microsoft Excel.

Personalizando o algoritmo Árvores de Decisão

O algoritmo Árvores de Decisão da Microsoft tem suporte para parâmetros que afetam o desempenho e a precisão do modelo de mineração resultante. Também é possível definir sinalizadores de modelagem nas colunas do modelo de mineração ou da estrutura de mineração para controlar a maneira como os dados são processados.

Observação

O algoritmo Árvores de Decisão da Microsoft está disponível em todas as edições do SQL Server; no entanto, alguns parâmetros avançados para personalizar o comportamento do algoritmo Árvores de Decisão da Microsoft estão disponíveis para uso apenas em edições específicas do SQL Server. Para obter uma lista de recursos com suporte pelas edições do SQL Server, consulte Recursos com suporte pelas edições do SQL Server 2012 (https://go.microsoft.com/fwlink/?linkid=232473).

Definindo parâmetros de algoritmo

A tabela a seguir descreve os parâmetros que você pode usar com o algoritmo Árvores de Decisão da Microsoft.

• COMPLEXITY_PENALTY
  Controla o crescimento da árvore de decisão. Um valor baixo aumenta o número de divisões e um valor alto diminui o número de divisões. O valor padrão se baseia no número de atributos de um determinado modelo, conforme descrito na lista a seguir:

  • Para os atributos 1 a 9, o padrão é 0,5.

  • Para 10 a 99 atributos, o padrão é 0,9.

  • Para 100 ou mais atributos, o padrão é 0,99.

• FORCE_REGRESSOR
  Força o algoritmo a usar as colunas especificadas como regressores, independentemente da sua importância quando calculadas pelo algoritmo. Esse parâmetro é usado apenas para árvores de decisão que preveem um atributo contínuo.

  Observação
  Ao definir esse parâmetro, você força o algoritmo a tentar usar o atributo como um regressor. No entanto, se o atributo será realmente usado como um regressor no modelo final dependerá dos resultados da análise. Você pode descobrir quais colunas foram usadas como regressores consultando o conteúdo do modelo.

  [Disponível somente em algumas edições do SQL Server]

• MAXIMUM_INPUT_ATTRIBUTES
  Define o número de atributos de entrada que o algoritmo pode manipular antes de invocar a seleção de recurso.

  O padrão é 255.

  Defina este valor como 0 para desativar a seleção de recursos.

  [Disponível somente em algumas edições do SQL Server]

• MAXIMUM_OUTPUT_ATTRIBUTES
  Define o número de atributos de saída que o algoritmo pode manipular antes de invocar a seleção de recurso.

  O padrão é 255.

  Defina este valor como 0 para desativar a seleção de recursos.

  [Disponível somente em algumas edições do SQL Server]

• MINIMUM_SUPPORT
  Determina o número mínimo de casos folha necessário para gerar uma divisão na árvore de decisão.

  O padrão é 10.

  Talvez seja necessário aumentar esse valor se o conjunto de dados for muito grande, para evitar treinamento excessivo.

• SCORE_METHOD
  Determina o método usado para calcular a pontuação da divisão. As seguintes opções estão disponíveis:

  ID	Nome
  1	Entropia
  3	Bayesiano com precedência K2
  4	Bayesiano Dirichlet Equivalente (BDE) com uniforme a priori (padrão)

  O padrão é 4 ou BDE.

  Para obter uma explicação desses métodos de pontuação, consulte Seleção de recursos.

• SPLIT_METHOD
  Determina o método usado para dividir o nó. As seguintes opções estão disponíveis:

  ID	Nome
  1	Binary: Indica que, independentemente do número real de valores do atributo, a árvore deverá ser dividida em duas ramificações.
  2	Complete: Indica que a árvore pode criar tantas divisões quanto há valores de atributo.
  3	Both: Especifica que o Analysis Services pode determinar se uma divisão binária ou completa deve ser usada para produzir os melhores resultados.

  O padrão é 3.

Sinalizadores de modelagem

O algoritmo Árvores de Decisão da Microsoft oferece suporte aos seguintes sinalizadores de modelagem. Ao criar um modelo ou uma estrutura de mineração, você define sinalizadores de modelagem para especificar como os valores em cada coluna são manipulados durante a análise. Para obter mais informações, consulte Sinalizadores de modelagem (Mineração de Dados).

Sinalizador de modelagem	Descrição
MODEL_EXISTENCE_ONLY	Significa que a coluna será tratada como se tivesse dois estados possíveis: Missing e Existing. Nulo é um valor ausente. Aplica-se às colunas de modelo de mineração.
NOT NULL	Indica que a coluna não pode conter um nulo. Um erro ocorrerá se o Analysis Services encontrar um valor nulo durante o treinamento do modelo. Aplica-se às colunas de estrutura de mineração.

Regressores em modelos de árvore de decisão

Mesmo que você não use o algoritmo Regressão Linear da Microsoft, qualquer modelo de árvore de decisão que tenha entradas e saídas numéricas contínuas poderá incluir nós que representem uma regressão em um atributo contínuo.

Não é necessário especificar que uma coluna de dados numéricos contínuos representa um regressor. O algoritmo Árvores de Decisão da Microsoft usará automaticamente a coluna como um regressor potencial e particionará o conjunto de dados em regiões com padrões significativos, mesmo que você não defina o sinalizador REGRESSOR na coluna.

No entanto, você pode usar o parâmetro FORCE_REGRESSOR para garantir que o algoritmo utilizará um determinado regressor. Esse parâmetro só pode ser usado com os algoritmos Árvores de decisão da Microsoft e Regressão Linear da Microsoft. Quando você definir o sinalizador de modelagem, o algoritmo tentará encontrar equações de regressão no formato a*C1 + b*C2 + ... para ajustar aos padrões nos nós da árvore. A soma dos restos é calculada e, se o desvio for muito grande, será forçada uma divisão da árvore.

Por exemplo, se você estiver prevendo o comportamento de compra dos clientes usando a Renda como um atributo e definir o sinalizador de modelagem REGRESSOR na coluna, o algoritmo primeiro tentará adequar os valores de Renda usando uma fórmula de regressão padrão. Se o desvio for muito grande, a fórmula de regressão será abandonada e a árvore será dividida em outro atributo. O algoritmo de árvore de decisão tentará ajustar um regressor para renda em cada uma das ramificações após a divisão.

Requisitos

Um modelo de árvore de decisão deve conter uma coluna de chave, colunas de entrada e pelo menos uma coluna previsível.

Colunas de entrada e colunas previsíveis

O algoritmo Árvores de Decisão da Microsoft oferece suporte a colunas de entrada e colunas previsíveis específicas que são listadas na tabela a seguir. Para obter mais informações sobre o significado do tipo de conteúdo quando usado em um modelo de mineração, consulte Tipos de conteúdo (mineração de dados).

Coluna	Tipos de conteúdo
Atributo de entrada	Contínuo, cíclico, discreto, diferenciado, chave, ordenado, tabela
Atributo previsível	Contínuo, cíclico, discreto, diferenciado, ordenado, tabela

Observação
Os tipos de conteúdo Cíclico e Ordenado têm suporte, mas o algoritmo os trata como valores discretos e não executa processamento especial.

Consulte também

Referência

Conteúdo do modelo de mineração para modelos de árvore de decisão (Analysis Services – Mineração de Dados)

Conceitos

Algoritmo Árvores de Decisão da Microsoft

Exemplos de consulta de modelo de árvores de decisão