Det andre Vatikankonsil og Sacrosanctum concilium

A primeira abordagem para a adaptação do viés indutivo apresentou limitações na caracterização das relações entre os parâmetros do algoritmo de agrupamento e a variação de comportamento do fluxo de dados devido à dificuldade de obter propriedades de convergência realistas. Esta segunda abordagem, motivada pelas limitações apresentadas pela primeira, visou prover uma abordagem de adaptação de parâmetros menos dependente das caracte- rísticas do algoritmo de agrupamento. A abordagem desenvolvida nessa segunda proposta,

4.7. Segunda abordagem para a adaptação do viés indutivo 63 denominada Data Stream Dynamic Clustering (DSDC), consiste na reunião de técnicas para a detecção de variação de comportamento e adaptação de agrupamentos.

A abordagem DSDC atua por meio de uma estratégia composta de três partes. A primeira parte consiste em definir uma partição de grupos utilizando um algoritmo de agrupa- mento para conjuntos tradicionais de dados, tal como o K-médias (Hartigan & Wong, 1979). A segunda parte consiste em descrever as relações entre os estados de comportamento ao longo do tempo. Um estado de comportamento é uma conjunção notável das variáveis de um sistema. Na segunda parte, as relações de transição entre estados são descritas por meio do modelo estatístico de cadeias de Markov (Ciuperca & Girardin, 2007). Cadeias de Mar- kov representam uma ampla gama de fenômenos com dependências temporais descritas por transições probabilísticas entre estados. Elas são destinadas a representar sistemas em que a probabilidade de transição para um próximo estado X(t + 1) depende apenas do estado atual X(t), e não dos anteriores {X(t − k), k ≥ 1}. Nesse cenário, protótipos obtidos a partir do algoritmo K-médias representam os estados de comportamento do sistema-alvo5_{. A terceira}

parte consiste na utilização de um teste de variação de comportamento do sistema para ativar um método de busca de parâmetros com o objetivo de adaptar o viés indutivo do algoritmo de agrupamento.

A abordagem DSDCconecta as duas primeiras partes de sua estratégia ao mapear os protótipos fornecidos pelo K-médias em estados de cadeias de Markov, conforme ilustrado na Figura 4.5. Nessa figura, três grupos de padrões de entrada que compõem uma partição Γ (Gama) são representados pelas letras A, B e C. Cada um dos conjuntos de dados são mapeados para a cadeia de Markov na parte direita da mesma figura. As probabilidades de transição, representadas por pesos nas arestas, são estimadas de acordo com a ordem que os dados são atribuídos, ao longo do tempo, a seus respectivos grupos utilizando um método de estimação de cadeias de Markov baseado em uma amostra longa (Ciuperca & Girardin, 2007).

A B C A B C 0,5 0,7 0,2 0,4 0,2 0,1 0,4 0,2 0,3 Cadeia de Markov M Partição Γ

Figura 4.5: Ilustração do mapeamento de uma partição de agrupamento em estados de uma cadeia de Markov

O método de estimação das probabilidades de transição de uma cadeia de Markov

64 Capítulo 4. Adaptação de Viés Indutivo de Agrupamento de Fluxos de Dados

inicia-se com o acúmulo de padrões de entrada. A quantidade necessária de amostras para estimar as probabilidades de transição de uma cadeia com k estados deve depender do erro má- ximo desejado δ e de um nível de confiança ξ para as estimativas. Infelizmente, desconhece-se um método para determinar tal quantidade para cadeias de Markov.

No entanto, um método para obter o tamanho do conjunto amostral para estimar as probabilidades de uma distribuição Multinomial pode ser utilizado na forma de uma apro- ximação (Thompson, 1987). A distribuição Multinomial pode ser considerada como um caso simplificado de cadeias de Markov. Essa distribuição apresenta categorias, diretamente relacionadas aos estados de uma cadeia de Markov cujas probabilidades de transição são tais que pi,j = pk,j, ∀i, k. Observando essa similaridade, o método de estimação do tamanho do

conjunto amostral para a distribuição Multinomial provê um limitante superior conservador para o número mínimo de padrões de entrada necessário para garantir um erro máximo na estimação das probabilidades de transição da cadeia de Markov. Esse limitante superior (Thompson, 1987, Tabela 1) relaciona a quantidade necessária de amostras para estimar as probabilidades da distribuição Multinomial, o erro máximo δ e o nível de significância ξ para garantir que esse erro máximo é respeitado.

Considerando essas condições, é possível escolher, para um erro máximo e um nível de significância, o número de padrões a ser acumulado. Para o algoritmo DSDC, escolheu-se como erro máximo de 5%, definido por δ = 0,05 e nível de significância ξ = 0,1, o que resulta em 403 · k padrões de entrada necessários para estimação das probabilidades de transição. Esse método, utilizado para determinar o número necessário de padrões para as etapas de agrupamento e estimação de cadeia de Markov, é representado no Algoritmo 1 pela função tamanho_amostral(k, δ = 0,05, ξ = 0,1).

Uma vez que um bloco de padrões de entrada é coletado, a execução do algoritmo K-médias provê ao método de estimação de probabilidades de transição de cadeias de Markov, descrito na Seção 4.5, uma partição dos dados (Ciuperca & Girardin, 2007). Uma matriz M com k × k dimensões representa essas probabilidades de transição. Adicionalmente, no processo de estimação de cadeias de Markov, cada transição entre estados é associada a uma probabilidade mínima, tipicamente 10−10_{, mesmo se tal transição não foi observada,}

permitindo a modelagem de sequências de eventos improváveis (Seneta, 2006). Como a matriz de transição M não apresenta probabilidades nulas, um resultado de Álgebra Linear conhecido como Teorema de Perron-Frobenius (Seneta, 2006) garante a existência de pelo menos um autovetor de M, que representa as probabilidades do comportamento assintótico da cadeia de Markov.

As probabilidades de comportamento assintótico representam as tendências a longo prazo do fenômeno, caso esse não varie de comportamento (Seneta, 2006). A obtenção dessas probabilidades é conduzida de acordo com a Equação 4.46, em que M é a matriz de probabilidades de transições não-nulas e p é o autovetor que representa as probabilidades

4.7. Segunda abordagem para a adaptação do viés indutivo 65 de comportamento assintótico de M (Seneta, 2006). O autovetor de probabilidades p pode ser estimado, por exemplo, multiplicando M por um número t suficientemente alto, tal que limt→∞Mt, até que todas as linhas tenham se igualado a p (Seneta, 2006).

p = Mp (4.46)

Com o intuito de detectar variações de comportamento no fenômeno observado, cada cadeia de Markov obtida é comparada à anterior por meio de suas probabilidades de com- portamento assintótico. Essa comparação permite detectar tais variações, empregando, como medida, a entropia de Shannon (1948) H, definida na Equação 4.47, em que pi representa a

probabilidade do sistema assintoticamente convergir ao estado i e k é o número de estados da cadeia de Markov. A entropia de Shannon é isomórfica, ou seja, invariante à representação de cadeias de Markov (Ornstein, 1989). Assim, se os comportamentos assintóticos de duas cadeias de Markov têm a mesma entropia, então elas têm estruturas equivalentes, diferindo apenas na sua representação, i.e., nos protótipos de grupo.

H_{(M) = −}

k

X

i=1

pilog2(pi) (4.47)

Para exemplificar a avaliação das variações de comportamento, considere duas cadeias de Markov M(0) e M(1) obtidas, respectivamente, em instantes de tempo 0 e 1. Para verificar variações comportamentais entre elas, calcula-se a entropia do comportamento assintótico de transição entre estados H(M(0)) e H(M(1)). Caso a diferença |H(M(0))−H(M(1))|

max{H(M(0)),H(M(1))} seja

superior a um limiar (próximo a zero) ˜H, sabe-se, então, que ocorreu uma variação de com- portamento.

A detecção de variações de comportamento desencadeia o processo de adaptação do algoritmo de agrupamento que, em termos de K-médias, leva a uma busca por uma partição que melhor represente o comportamento atual do fenômeno. No longo prazo, DSDC deverá produzir uma sequência de partições que representa a evolução de um fluxo de dados.