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

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.

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 discretas configurando as propriedades DiscretizationMethod e DiscretizationBucketCount. Para obter mais informações, consulte Como 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. 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.

O algoritmo Árvores de Decisão da Microsoft oferece três fórmulas para ganho de informações de pontuação: entropia de Shannon, rede Bayesiana com K2 a priori e rede Bayesiana com uma distribuição Dirichlet uniforme a priori. 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.

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

  Use as ferramentas de exploração de dados disponíveis no SQL Server 2008 Integration Services 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 Criando perfil de dados com o visualizador e a tarefa de 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.

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 os atributos 10 a 99, 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.

  [SQL Server Enterprise]

• 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.

  [SQL Server Enterprise]

• 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.

  [SQL Server Enterprise]

• 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
  2	Bayesiano com precedência K2
  3	Bayesian Dirichlet Equivalente (BDE) anterior (padrão)

  O padrão é 3.

  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.

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).

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.

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).

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.