Referência técnica do Microsoft Clustering Algorithm

Aplica-se a: SQL Server 2019 e anteriores Analysis Services Azure Analysis Services Fabric/Power BI Premium

Este artigo explica a implementação do Microsoft Clustering Algorithm, incluindo os parâmetros que pode usar para controlar o comportamento dos modelos de clustering. O artigo também fornece orientações sobre como melhorar o desempenho ao criar e processar modelos de clustering.

Para mais informações sobre como usar modelos de clustering, consulte os seguintes artigos:

• Conteúdo do Modelo de Mineração para Modelos de Clustering (Serviços de Análise - Mineração de Dados)

• Exemplos de Consultas de Modelos de Agrupamento

Implementação do Algoritmo de Clusterização Microsoft

O Algoritmo de Clusterização da Microsoft fornece dois métodos para criar clusters e atribuir pontos de dados a clusters. K-means é um método de agrupamento rígido, o que significa que um ponto de dados pode pertencer apenas a um cluster, e o algoritmo calcula uma única probabilidade para a pertença a cada ponto de dados nesse cluster. A Maximização de Expectativas (EM) é um método de agrupamento suave , o que significa que um ponto de dados pertence sempre a múltiplos clusters, e o algoritmo calcula uma probabilidade para cada combinação de ponto de dados e cluster.

Escolhes qual o algoritmo a usar definindo o parâmetro CLUSTERING_METHOD . O método padrão para clusterização é o EM escalável.

Agrupamento EM

No agrupamento EM, o algoritmo refina iterativamente um modelo inicial de cluster para ajustar os dados e determina a probabilidade de existir um ponto de dados num cluster. O algoritmo termina o processo quando o modelo probabilístico se ajusta aos dados. A função usada para determinar o ajuste é a verosimilhança logarítmica dos dados dados pelo modelo.

Se o processo gerar clusters vazios, ou se a pertença a um ou mais clusters ficar abaixo de um determinado limiar, o algoritmo resemeia os clusters com populações baixas em novos pontos e repete o algoritmo EM.

Os resultados do método de agrupamento EM são probabilísticos, o que significa que cada ponto de dados pertence a todos os clusters, mas cada atribuição de um ponto de dados a um cluster tem uma probabilidade diferente. Como o método permite que clusters se sobreponham, a soma dos itens em todos os clusters pode exceder o total de itens no conjunto de treino. Nos resultados do modelo de mineração, as pontuações que indicam apoio são ajustadas para ter em conta esta sobreposição.

O algoritmo EM é o algoritmo padrão utilizado nos modelos de clustering da Microsoft. Este algoritmo é o padrão porque oferece as seguintes vantagens em comparação com o agrupamento k-means:

• Requer, no máximo, uma varredura da base de dados.

• Funciona apesar da memória limitada (RAM).

• Pode usar um cursor apenas para a frente.

• Supera os métodos de amostragem.

A implementação da Microsoft oferece duas opções: EM escalável e não escalável. No EM escalável, os primeiros 50.000 registos iniciam a varredura inicial por defeito. Se este passo for bem-sucedido, o modelo utiliza apenas esses dados. Se o modelo não conseguir caber usando 50.000 registos, o algoritmo lê mais 50.000 registos.

Em EM não escalável, o algoritmo lê todo o conjunto de dados independentemente do seu tamanho. Este método pode criar clusters mais precisos, mas pode ter necessidades significativas de memória. Como o EM escalável opera num buffer local, percorrer os dados é mais rápido e o algoritmo aproveita melhor a cache de memória da CPU do que o EM não escalável. O EM escalável é três vezes mais rápido do que o EM não escalável, mesmo que todos os dados caberem na memória principal. Na maioria dos casos, a melhoria de desempenho não leva a uma menor qualidade do modelo completo.

Para um relatório técnico que descreve a implementação de EM no Microsoft Clustering Algorithm, veja Escalar EM (Expectation Maximization) Clustering to Large Databases.

clustering K-means

O agrupamento K-means é um método bem conhecido de atribuir a pertença a um cluster, minimizando as diferenças entre os itens de um cluster enquanto maximiza a distância entre clusters. As "médias" em k-médias referem-se ao centroide do cluster, que é um ponto de dados que se escolhe arbitrariamente e depois se refina iterativamente até representar a verdadeira média de todos os pontos de dados do cluster. O "k" refere-se a um número arbitrário de pontos que iniciam o processo de agrupamento. O algoritmo k-médias calcula as distâncias euclidianas ao quadrado entre registos de dados num cluster e o vetor que representa a média do cluster, e converge para um conjunto final de k clusters quando essa soma atinge o seu valor mínimo.

O algoritmo k-means atribui cada ponto de dados a exatamente um cluster, e não permite incerteza na pertença. Expressas a pertença a um cluster como uma distância ao centroide.

Normalmente, utiliza-se o algoritmo k-means para criar agrupamentos de atributos contínuos, onde calcular a distância a uma média é simples. No entanto, a implementação da Microsoft adapta o método k-means para agrupar atributos discretos usando probabilidades. Para atributos discretos, a distância de um ponto de dados a um determinado cluster é calculada da seguinte forma:

1 - P (ponto de dados, cluster)

O algoritmo k-means fornece dois métodos de amostragem do conjunto de dados: k-means não escalável, que carrega todo o conjunto de dados e efetua uma única passagem de agrupamento, ou k-means escalável, em que o algoritmo utiliza os primeiros 50 000 casos e lê mais casos apenas se precisar de mais dados para obter um bom ajustamento do modelo aos dados.

Atualizações do Algoritmo de Clusterização Microsoft no SQL Server 2008

No SQL Server 2008, a configuração padrão do Microsoft Clustering Algorithm mudou para usar o parâmetro internoNORMALIZATION = 1. O algoritmo realiza a normalização utilizando estatísticas z-score e assume a distribuição normal. A intenção desta alteração de comportamento padrão é minimizar o efeito de atributos que têm grandes magnitudes e muitos valores atípicos. No entanto, a normalização do z-score pode alterar os resultados de agrupamento em distribuições que não são normais, como distribuições uniformes. Para evitar a normalização e obter o mesmo comportamento do algoritmo de clustering K-means no SQL Server 2005, use a caixa de diálogo Parâmetros para adicionar o parâmetro personalizado NORMALIZATION e definir o seu valor para 0.

Personalização do Algoritmo de Clusterização Microsoft

O Algoritmo de Clustering da Microsoft suporta vários parâmetros que afetam o comportamento, desempenho e precisão do modelo de mineração resultante.

Parâmetros do algoritmo

A tabela seguinte descreve os parâmetros que pode usar com o Algoritmo de Clusterização da Microsoft. Estes parâmetros afetam tanto o desempenho como a precisão do modelo de mineração resultante.

método de agrupamento
Especifica o método de agrupamento que o algoritmo deve usar. Os seguintes métodos de agrupamento estão disponíveis:

O padrão é 1 (EM escalável).

CLUSTER_COUNT
Especifica o número aproximado de clusters a construir pelo algoritmo. Se o algoritmo não conseguir construir o número aproximado de clusters a partir dos dados, constrói o máximo de clusters possível. Definir o CLUSTER_COUNT para 0 faz com que o algoritmo use heurísticas para melhor determinar o número de clusters a construir.

O padrão é 10.

CLUSTER_SEED
Especifica o número de semente que o algoritmo utiliza para gerar aleatoriamente clusters na fase inicial da construção do modelo.

Ao alterar este número, pode alterar a forma como os clusters iniciais são construídos e depois comparar modelos construídos usando diferentes seeds. Se mudares a semente mas os clusters encontrados pelo algoritmo não mudarem muito, podes considerar o modelo relativamente estável.

O padrão é 0.

MINIMUM_SUPPORT
Especifica o número mínimo de casos necessários para construir um cluster. Se o número de casos no cluster for inferior a esse número, o algoritmo trata o cluster como vazio e descarta-o. Se definir este número demasiado alto, pode perder clusters válidos.

O padrão é 1.

MODELLAGEM_CARDINALIDADE
Especifica o número de modelos de amostra que o algoritmo constrói durante o processo de agrupamento.

Reduzir o número de modelos candidatos pode melhorar o desempenho, correndo o risco de perder alguns bons modelos candidatos.

O padrão é 10.

STOPPING_TOLERANCE
Especifica o valor que o algoritmo usa para determinar quando a convergência é atingida e o algoritmo termina de construir o modelo. A convergência é alcançada quando a variação global nas probabilidades do cluster é menor do que a razão entre o parâmetro STOPPING_TOLERANCE dividido pelo tamanho do modelo.

O padrão é 10.

TAMANHO_AMOSTRA
Especifica o número de casos que o algoritmo utiliza em cada passagem se o parâmetro CLUSTERING_METHOD estiver definido para um dos métodos de agrupamento escaláveis. Definir o parâmetro SAMPLE_SIZE a 0 faz com que todo o conjunto de dados seja agrupado numa única passagem, o que pode causar problemas de memória e desempenho.

O padrão é 50000.

MAXIMUM_INPUT_ATTRIBUTES
Especifica o número máximo de atributos de entrada que o algoritmo pode gerir antes de invocar a seleção de funcionalidades. Definir este valor a 0 especifica que não existe um número máximo de atributos.

Aumentar o número de atributos pode degradar significativamente o desempenho.

O padrão é 255.

ESTADOS_MÁXIMOS
Especifica o número máximo de estados de atributos que o algoritmo suporta. Se um atributo tiver mais estados do que o máximo, o algoritmo usa os estados mais populares e ignora os restantes.

Aumentar o número de estados pode degradar significativamente o desempenho.

O padrão é 100.

Bandeiras de modelação

O algoritmo suporta as seguintes bandeiras de modelação. Defina os sinalizadores de modelação ao criar a estrutura de mineração ou o modelo de mineração. Os flags de modelação especificam como os valores em cada coluna são tratados durante a análise.

Requerimentos

Um modelo de agrupamento deve conter uma coluna chave e colunas de entrada. Também podes definir colunas de entrada como previsíveis. Colunas definidas para Prever Apenas não são usadas para construir clusters. A distribuição destes valores nos clusters é calculada após a construção dos clusters.

Colunas de entrada e de previsão

O Algoritmo de Clusterização da Microsoft suporta as colunas de entrada e as colunas previsíveis listadas na tabela seguinte. Para mais informações sobre o significado dos tipos de conteúdo quando usados num modelo de mineração, consulte Tipos de Conteúdo (Mineração de Dados).

Consulte também

Algoritmo de Clusterização Microsoft
Exemplos de Consultas de Modelos de Agrupamento
Conteúdo do Modelo de Mineração para Modelos de Clustering (Serviços de Análise - Mineração de Dados)