Compartilhar via

Referência técnica do algoritmo de clustering da Microsoft

Esta seção explica a implementação do algoritmo Microsoft Clustering, incluindo os parâmetros que você pode usar para controlar o comportamento dos modelos de clustering. Ele também fornece diretrizes sobre como melhorar o desempenho ao criar e processar modelos de clustering.

Para obter informações adicionais sobre como usar modelos de clustering, consulte os seguintes tópicos:

Implementação do Algoritmo de Clustering da Microsoft

O algoritmo Clustering da Microsoft fornece dois métodos para criar clusters e atribuir pontos de dados aos clusters. O primeiro, o algoritmo K-means , é um método de clustering rígido. Isso significa que um ponto de dados pode pertencer a apenas um cluster e que uma única probabilidade é calculada para a associação de cada ponto de dados nesse cluster. O segundo método, o método EM ( Maximização de Expectativa ), é um método de clustering flexível . Isso significa que um ponto de dados sempre pertence a vários clusters e que uma probabilidade é calculada para cada combinação de ponto de dados e cluster.

Você pode escolher qual algoritmo usar definindo o parâmetro CLUSTERING_METHOD . O método padrão para clustering é EM escalonável.

Agrupamento EM

No clustering EM, o algoritmo refina iterativamente um modelo de cluster inicial para ajustar os dados e determina a probabilidade de que um ponto de dados exista em um cluster. O algoritmo encerra o processo quando o modelo probabilístico se ajusta aos dados. A função usada para determinar o ajuste é a verossimilhança logarítmica dos dados dado o modelo.

Se clusters vazios forem gerados durante o processo ou se a associação de um ou mais clusters ficar abaixo de um determinado limite, os clusters com populações baixas serão reutilizados em novos pontos e o algoritmo EM será executado novamente.

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

O algoritmo EM é o algoritmo padrão usado em modelos de clustering da Microsoft. Esse algoritmo é usado como o padrão porque oferece várias vantagens em comparação com o clustering k-means:

  • Requer, no máximo, uma verificação de banco de dados.

  • Funcionará apesar da memória limitada (RAM).

  • Tem a capacidade de usar um cursor de avanço único.

  • Supera diferentes abordagens de amostragem.

A implementação da Microsoft fornece duas opções: EM escalonável e não escalonável. Por padrão, em EM escalonável, os primeiros 50.000 registros são usados para propagar a verificação inicial. Se isso for bem-sucedido, o modelo usará apenas esses dados. Se o modelo não puder ser adequado usando 50.000 registros, mais 50.000 registros serão lidos. Em EM não escalonável, todo o conjunto de dados é lido independentemente de seu tamanho. Esse método pode criar clusters mais precisos, mas os requisitos de memória podem ser significativos. Como o EM escalonável opera em um buffer local, a iteração por meio dos dados é muito mais rápida e o algoritmo faz um uso muito melhor do cache de memória da CPU do que o EM não escalonável. Além disso, o EM escalonável é três vezes mais rápido do que o EM não escalonável, mesmo que todos os dados possam caber 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 do EM no algoritmo de Clustering da Microsoft, consulte Dimensionamento do EM (Maximização da Expectativa) para Clustering em Grandes Bancos de Dados.

Cluster K-means

O método K-means é conhecido por definir associação ao grupo minimizando as diferenças entre os itens dentro de um grupo, enquanto maximiza a distância entre os grupos. Os "meios" em k-means referem-se ao centroide do cluster, que é um ponto de dados que é escolhido arbitrariamente e, em seguida, refinado iterativamente até representar a verdadeira média de todos os pontos de dados no cluster. O "k" refere-se a um número arbitrário de pontos que são usados para iniciar o processo de clustering. O algoritmo k-means calcula as distâncias euclidianas quadradas entre os registros de dados em um cluster e o vetor que representa a média do cluster e converge em um conjunto final de k clusters quando essa soma atinge seu valor mínimo.

O algoritmo k-means atribui cada ponto de dados a exatamente um cluster e não permite a incerteza na associação. A associação em um cluster é expressa como uma distância do centroide.

Normalmente, o algoritmo k-means é usado para criar clusters de atributos contínuos, em que calcular a distância para uma média é simples. No entanto, a implementação da Microsoft adapta o método k-means aos atributos discretos do cluster usando probabilidades. Para atributos discretos, a distância de um ponto de dados de um cluster específico é calculada da seguinte maneira:

1 – P(ponto de dados, cluster)

Observação

O algoritmo de clustering da Microsoft não expõe a função de distância específica usada no cálculo do k-means, e as medidas de distância não estão disponíveis no modelo concluído. No entanto, você pode usar uma função de previsão para retornar um valor que corresponde à distância, em que a distância é computada como a probabilidade de um ponto de dados pertencer ao cluster. Para obter mais informações, consulte ClusterProbability (DMX).

O algoritmo k-means fornece dois métodos de amostragem do conjunto de dados: k-means não escalonável, que carrega todo o conjunto de dados e faz uma passagem de agrupamento, ou k-means escalonável, em que o algoritmo usa os primeiros 50.000 casos e lê mais casos somente se precisar de mais dados para alcançar um bom ajuste do modelo aos dados.

Atualizações para o Algoritmo de Clustering da Microsoft no SQL Server 2008

No SQL Server 2008, a configuração padrão do algoritmo de clustering da Microsoft foi alterada para usar o parâmetro interno, NORMALIZATION = 1. A normalização é executada usando estatísticas de pontuação z e pressupõe a distribuição normal. A intenção dessa alteração no comportamento padrão é minimizar o efeito de atributos que podem ter grandes magnitudes e muitas exceções. No entanto, a normalização da pontuação z pode alterar os resultados de clustering em distribuições que não são normais (como distribuições uniformes). Para evitar a normalização e obter o mesmo comportamento que o algoritmo de clustering K-means no SQL Server 2005, você pode usar a caixa de diálogo Configurações de Parâmetro para adicionar o parâmetro personalizado, NORMALIZATION, e definir seu valor como 0.

Observação

O parâmetro NORMALIZATION é uma propriedade interna do algoritmo Microsoft Clustering e não tem suporte. Em geral, o uso da normalização é recomendado em modelos de clustering para melhorar os resultados do modelo.

Personalizando o algoritmo de clustering da Microsoft

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

Definindo parâmetros de algoritmo

A tabela a seguir descreve os parâmetros que podem ser usados com o algoritmo de Clustering da Microsoft. Esses parâmetros afetam o desempenho e a precisão do modelo de mineração resultante.

CLUSTERING_METHOD
Especifica o método de clustering para o algoritmo a ser usado. Os seguintes métodos de clustering estão disponíveis:

Número de Identificação Método
1 EM escalonável
2 EM não escalonável
3 K-Means escalável
4 K-Means não escalável.

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

CLUSTER_COUNT
Especifica o número aproximado de clusters a serem criados pelo algoritmo. Se o número aproximado de clusters não puder ser criado a partir dos dados, o algoritmo criará o máximo possível de clusters. Definir o CLUSTER_COUNT como 0 faz com que o algoritmo use heurística para determinar melhor o número de clusters a serem compilados.

O padrão é 10.

CLUSTER_SEED
Especifica o número de semente usado para gerar clusters aleatoriamente para o estágio inicial da criação do modelo.

Ao alterar esse número, você pode alterar a forma como os clusters iniciais são criados e, em seguida, comparar modelos que foram criados usando sementes diferentes. Se a semente for alterada, mas os clusters encontrados não forem muito alterados, o modelo poderá ser considerado relativamente estável.

O padrão é 0.

SUPORTE_MÍNIMO
Especifica o número mínimo de casos necessários para criar um cluster. Se o número de casos no cluster for menor que esse número, o cluster será tratado como vazio e descartado.

Se você definir esse número muito alto, poderá perder clusters válidos.

Observação

Se você usar EM, que é o método de clustering padrão, alguns clusters poderão ter um valor de suporte menor que o valor especificado. Isso ocorre porque cada caso é avaliado para sua associação em todos os clusters possíveis e, para alguns clusters, pode haver apenas suporte mínimo.

O padrão é 1.

MODELANDO_CARDINALIDADE
Especifica o número de modelos de exemplo que são construídos durante o processo de clustering.

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

O padrão é 10.

TOLERÂNCIA_DE_PARADA
Especifica o valor usado para determinar quando a convergência é alcançada e o algoritmo termina de compilar o modelo. A convergência é alcançada quando a alteração geral nas probabilidades de cluster é menor que a taxa do parâmetro STOPPING_TOLERANCE dividido pelo tamanho do modelo.

O padrão é 10.

TAMANHO_DA_AMOSTRA
Especifica o número de casos que o algoritmo usa em cada passagem se o parâmetro CLUSTERING_METHOD for definido como um dos métodos de clustering escalonáveis. Definir o parâmetro SAMPLE_SIZE como 0 fará com que todo o conjunto de dados seja clusterizado em uma única passagem. Carregar todo o conjunto de dados em uma única passagem 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 manipular antes de invocar a seleção de recursos. Definir esse valor como 0 especifica que não há número máximo de atributos.

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

O padrão é 255.

ESTADOS_MÁXIMOS
Especifica o número máximo de estados de atributo aos quais o algoritmo dá suporte. Se um atributo tiver mais estados do que o máximo, o algoritmo usará os estados mais populares e ignorará os estados restantes.

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

O padrão é 100.

Bandeiras de modelagem

O algoritmo dá suporte aos seguintes sinalizadores de modelagem. Você define sinalizadores de modelagem ao criar a estrutura de mineração ou o modelo de mineração. Os sinalizadores de modelagem especificam como os valores em cada coluna são tratados durante a análise.

Bandeira de Modelagem Descrição
MODEL_EXISTENCE_ONLY A coluna será tratada como tendo dois estados possíveis: Ausente e Existente. Um valor nulo é um valor ausente.

Aplica-se à coluna do modelo de mineração.
NÃO NULO A coluna não pode conter um valor nulo. Um erro resultará se o Analysis Services encontrar um valor nulo durante o treinamento do modelo.

Aplica-se à coluna de estrutura de mineração.

Requisitos

Um modelo de clustering deve conter uma coluna de chave e colunas de entrada. Você também pode definir colunas de entrada como previsíveis. As colunas definidas como Predict Only não são usadas para criar clusters. A distribuição desses valores nos clusters é calculada após a criação dos clusters.

Colunas de entrada e de previsão

O algoritmo Clustering da Microsoft dá suporte às colunas de entrada específicas e colunas previsíveis listadas na tabela a seguir. Para obter mais informações sobre o que os tipos de conteúdo significam quando usados 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, discretizado, chave, tabela, ordenado
Atributo previsível Contínua, cíclica, discreta, discretizada, tabela, ordenada

Observação

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

Algoritmo de clustering da Microsoft
Exemplos de consulta de modelo de clustering
Conteúdo do modelo de mineração para modelos de agrupamento (Analysis Services – Mineração de dados)

  • Last updated on