Referência técnica do algoritmo MSC

O algoritmo MSC é um híbrido que usa a análise de cadeia Markov para identificar seqüências ordenadas e combina os resultados dessa análise com técnicas de clusterização para gerar clusters com base nas seqüências e outros atributos no modelo. Este tópico descreve a implementação do algoritmo, como personalizá-lo e os requisitos especiais para modelos de clusterização de seqüências.

Para obter mais informações gerais sobre o algoritmo, inclusive como navegar e consultar modelos de clusterização de seqüência, consulte Algoritmo MSC.

Implementação do algoritmo do MSC

O modelo MSC usa modelos Markov para identificar seqüências e determinar a probabilidade das seqüências. Um modelo Markov é um gráfico direcionado que armazena as transições entre estados diferentes. O algoritmo MSC usa cadeias Markov de n-ordem, não um modelo Markov Oculto.

O número de ordens em uma cadeia Markov informa quantos estados são usados para determinar a probabilidade dos estados atuais. Em um modelo Markov de primeira ordem, a probabilidade do estado atual depende apenas do estado anterior. Em uma cadeia Markov de segunda ordem, a probabilidade de um estado depende dos dois estados anteriores e assim por diante. Para cada cadeia Markov,uma matriz de transição armazena as transições de cada combinação de estados. À medida que o comprimento da cadeia Markov aumenta, o tamanho da matriz também aumenta exponencialmente e ela se torna extremamente esparsa. O tempo de processamento também aumenta proporcionalmente.

Talvez seja útil visualizar a cadeia usando o exemplo da análise da seqüência de cliques, que analisa as visitas às páginas da Web em um site. Cada usuário cria uma seqüência longa de cliques para cada sessão. Quando você cria um modelo para analisar o comportamento do usuário em um site, o conjunto de dados usado para treinamento é uma seqüência de URLs, convertida em um gráfico que inclui a contagem de todas as instâncias do mesmo caminho de cliques. Por exemplo, o gráfico contém a probabilidade de o usuário passar da página 1 para a página 2 (10%), a probabilidade de o usuário passar da página 1 para a página 3 (20%) etc. Quando você junta todos os caminhos e partes de caminhos possíveis, obtém um gráfico que pode ser muito maior e mais complexo do que qualquer caminho observado único.

Por padrão, o algoritmo MSC usa o método Maximização da Expectativa (ME) de clusterização. Para obter mais informações, consulte Referência técnica do algoritmo Microsoft Clustering.

Os destinos de clusterização são os atributos seqüenciais e não seqüenciais. Cada cluster é selecionado aleatoriamente com o uso de uma distribuição de probabilidade. Cada cluster tem uma cadeia Markov que representa o conjunto completo de caminhos e uma matriz que contém as transições de estado de seqüência e as probabilidades. Com base na distribuição inicial, a regra de Bayes é usada para calcular a probabilidade de qualquer atributo, inclusive uma seqüência, em um cluster específico.

O algoritmo MSC dá suporte à adição de atributos não seqüenciais ao modelo. Isso significa que esses atributos adicionais são combinados aos atributos de seqüência para criar clusters de casos com atributos similares, assim como ocorre em um modelo de clusterização típico.

Um modelo de clusterização de seqüência tende a criar muito mais clusters do que um modelo de clusterização típico. Assim, o algoritmo MSC executa a decomposição de cluster para separar clusters com base nas seqüências e em outros atributos.

Seleção de recursos em um modelo de clusterização de seqüência

A seleção de recursos não é invocada durante a criação de seqüências; no entanto, ela se aplica no estágio de clusterização.

Tipo de modelo	Método de seleção de recursos	Comentários
Agrupamento de Seqüência	Não usado	A seleção de recursos não é chamada; no entanto, você pode controlar o comportamento do algoritmo definindo o valor dos parâmetros MINIMUM_SUPPORT e MINIMUM_PROBABILIITY.
Clusterização	Pontuação de interesse	Embora o algoritmo de clusterização possa usar algoritmos discretos ou diferenciados, a pontuação de cada atributo é calculada como uma distância e é contínua; por isso, é usada a pontuação de interesse.

Para obter mais informações, consulte Seleção de recursos.

Aperfeiçoando o desempenho

O algoritmo MSC dá suporte a várias maneiras de otimizar o processamento:

• Controlar o número de clusters gerado, definindo um valor para o parâmetro CLUSTER_COUNT.

• Reduzir o número de seqüências incluídas como atributos, aumentando o valor do parâmetro MINIMUM_SUPPORT. Assim, as seqüências raras são eliminadas.

• Reduzir a complexidade antes de processar o modelo, agrupando os atributos relacionados.

Em geral, é possível otimizar o desempenho de um modo de cadeia Markov de n-ordem de várias maneiras:

• Controlando o comprimento das seqüências possíveis.

• Reduzindo programaticamente o valor de n.

• Armazenando apenas probabilidades que excedem um limite especificado.

Uma análise completa desses métodos está além do escopo deste tópico.

Personalizando o algoritmo MSC

O algoritmo Microsoft Sequence Clustering dá suporte a parâmetros que afetam o comportamento, o desempenho e a precisão do modelo de mineração resultante. Também é possível modificar o comportamento do modelo completo definindo sinalizadores de modelagem que controlam a maneira como o algoritmo processa dados de treinamento.

Definindo parâmetros de algoritmo

A tabela a seguir descreve os parâmetros que podem ser usados com o algoritmo MSC.

• CLUSTER_COUNT
  Especifica o número aproximado de clusters a serem criados pelo algoritmo. Se não for possível criar o número aproximado de clusters a partir dos dados, o algoritmo criará o máximo de clusters possível. A definição do parâmetro CLUSTER_COUNT como 0 faz com que o algoritmo use heurística para determinar melhor o número de clusters a serem criados.

  O padrão é 10.

  Observação
  A especificação de um número diferente de zero atua como uma dica para o algoritmo, que prossegue com a meta de encontrar o número especificado, mas pode acabar encontrando mais ou menos.

• MINIMUM_SUPPORT
  Especifica o número mínimo de casos necessários para dar suporte à criação de um cluster por um atributo.

  O padrão é 10.

• MAXIMUM_SEQUENCE_STATES
  Especifica o número de máximo de estados que uma seqüência pode ter.

  A definição desse valor com um número maior que 100 pode fazer com que o algoritmo crie um modelo que não fornece informações significativas.

  O padrão é 64.

• MAXIMUM_STATES
  Especifica o número máximo de estados de um atributo não seqüencial para os quais o algoritmo oferece suporte. Se o número de estados de um atributo não seqüencial for maior do que o número máximo de estados, o algoritmo usará os estados mais populares do atributo e tratará os estados restantes como Missing.

  O padrão é 100.

Sinalizadores de modelagem

Os sinalizadores de modelagem a seguir são suportados para uso com o algoritmo Microsoft Sequence Clustering.

• 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 à coluna da estrutura de mineração.

• MODEL_EXISTENCE_ONLY
  Significa que a coluna será tratada como se tivesse dois estados possíveis: Missing e Existing. Um valor nulo é tratado como Missing.

  Aplica-se à coluna do modelo de mineração.

Para obter mais informações sobre o uso de valores Ausentes em modelos de mineração e como os valores ausentes afetam as pontuações de probabilidade, consulte Valores ausentes (Analysis Services - Mineração de dados).

Requisitos

A tabela de casos deve ter uma coluna de ID de caso. Opcionalmente, a tabela de casos pode conter outras colunas que armazenam atributos sobre o caso.

O algoritmo MSC requer informações de seqüência, armazenadas como uma tabela aninhada. A tabela aninhada deve ter uma única coluna Key Sequence. Uma coluna Key Sequence pode conter qualquer tipo de dados que possa ser armazenado, inclusive tipos de dados de cadeia de caracteres, mas a coluna deve conter valores exclusivos para cada caso. Além disso, antes de processar o modelo, você deve assegurar que a tabela de casos e a tabela aninhada sejam classificadas em ordem crescente na chave que relaciona as tabelas.

Observação
Se você criar um modelo que use o algoritmo MSC, mas não use uma coluna de seqüência, o modelo resultante não conterá nenhuma seqüência, mas simplesmente clusterizará casos com base em outros atributos incluídos no modelo.

Colunas de entrada e colunas previsíveis

O algoritmo Microsoft Sequence Clustering dá 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, Key Sequence, tabela e ordenado
Atributo previsível	Contínuo, cíclico, discreto, diferenciado, tabela e ordenado

Comentários

• A previsão de seqüências, usando a função PredictSequence (DMX), está disponível apenas no SQL Server Enterprise.

• O algoritmo Microsoft Sequence Clustering não tem suporte ao uso de PMML para criar modelos de mineração.

• O algoritmo Microsoft Sequence Clustering dá suporte ao detalhamento, ao uso de modelos de mineração OLAP e ao uso de dimensões de mineração de dados.

Consulte também

Referência

Conteúdo do modelo de mineração para modelos de clustering de seqüências (Analysis Services – Mineração de Dados)

Conceitos

Algoritmo MSC

Consultando um modelo de cluster de seqüências (Analysis Services – Mineração de Dados)