KOLMOGOROV-SMIRNOV TEST

Lately, at work, we had to make a lot of unsupervised classification. Basicamente, tivemos que distinguir N classes de uma população de amostra. Tivemos uma ideia aproximada de quantas classes estavam presentes mas nada era certo, descobrimos que o teste Kolmogorov-Smirnov é uma forma muito eficiente de determinar se duas amostras são significativamente diferentes uma da outra.

Dar-lhe-ei um pouco de contexto sobre o teste Kolmogorov-Smirnov e caminharei consigo através de um problema que resolvemos com ele.

Posto original em coffeeanddata.ca

Rejeitando a hipótese nula. Isso parece uma memória dolorosa da aula de estatística da universidade, mas na verdade é exatamente o que queremos fazer aqui. Queremos rejeitar a possibilidade de que as duas amostras estejam vindo exatamente da mesma distribuição. Vamos olhar para um nível muito alto, não matemático, visão geral de alguns testes disponíveis. Se você quiser ter uma boa compreensão da matemática por trás de todos estes testes, use o link da Wikipédia fornecido em todas as seções.

TESTE DO ESTUDANTE

O Teste T do Estudante é provavelmente a maneira mais bem conhecida de rejeitar a hipótese nula. Este teste calcula o valor P de uma amostra em relação a uma população normal ou em relação a outra amostra. O resultado, P-value, diz-lhe como estas amostras provêm exactamente da mesma distribuição.

Quando obtido, o P-value pode ser comparado com um limiar de significância estatística (ex. .05), se o P-value for menor, podemos rejeitar as hipóteses nulas.

Existe um problema com o Teste T de Student, as amostras devem ser normais (moldadas numa distribuição normal). Isso é um problema para nós porque trabalhamos muito com distribuições de Poisson.

KOLMOGOROV-SMIRNOV TEST

O teste Kolmogorov-Smirnov (Teste KS) é um pouco mais complexo e permite detectar padrões que você não pode detectar com um Teste T de Aluno.

From Wikipedia:

“The Kolmogorov–Smirnov statistic quantifies a distance between the empirical distribution function of the sample and the cumulative distribution function of the reference distribution, or between the empirical distribution functions of two samples.”

Here is an example that shows the difference between Student’s T-Test and KS Test.

Because the sample mean and standard deviation are highly similar the Student’s T-Test gives a very high p-value. KS Test can detect the variance. In this case the red distribution has a slightly binomial distribution which KS detect. Em outras palavras:

• Teste T do aluno diz que há 79,3% de chances das duas amostras virem da mesma distribuição.
• Teste KS diz que há 1,6% de chances das duas amostras virem da mesma distribuição.

OUTROS TESTES

Há muitos outros testes e algoritmos para fazer esse tipo de trabalho. O teste Shapiro-Wilk e o teste Anderson-Darling são dois testes considerados mais poderosos do que o teste KS. Há uma grande desvantagem com esses dois testes, eles não permitem comparar duas amostras, eles sempre comparam uma amostra com uma distribuição padrão.

Edit: Um colega meu me mostrou que Anderson-Darling também poderia ser usado para testes de duas maneiras (Comparando Amostras).

“O teste K-S de duas amostras é um dos métodos não paramétricos mais úteis e gerais para comparar duas amostras” – Wikipedia.

DETECT DEVICE USER

Para esta atribuição específica tivemos de detectar qual o utilizador que estava a utilizar um dispositivo específico. Cada dispositivo foi utilizado por um ou vários usuários diferentes e tivemos que inventar uma técnica para identificar se existiam um ou vários usuários. No caso de múltiplos usuários queríamos identificar qual o uso que era feito por qual usuário.

OUR ESTRATÉGIA

Decidimos usar uma mistura de rede gráfica e teste KS para identificar potenciais clusters. A idéia por trás desta demonstração é imaginar uma rede gráfica onde cada nó (amostra) estivesse conectado a todos os outros nós (amostra). Os vértices ou link entre esses nós me fariam o KS Test, em outras palavras, quão próximos estão esses dois nós. Assim, dois nós com baixo valor KS P-Value estariam próximos e dois com alto valor P distantes. Isto esperançosamente criaria clusters distinguíveis.

DATA SET

Aqui está o aspecto dos nossos dados:

As you can see, all our sample looks like a normal distribution with a very low standard deviation. We have sampled all the 82 different usage sessions of this device.

Strait from this picture we can see that there are different patterns. All the sample does not have the same histogram distribution. That is a very good start. After this we looked at the obvious cluster of distribution.

To do so, we did the KS matrix, which consists of a KS Two way test of every sample distribution vs every other sample.Uma vista rápida do mapa de calor da Matriz KS não revela resultados óbvios (como pode ver na figura à sua direita).

Após este agrupamento hierárquico, já obtemos alguns resultados melhores (como pode ver na figura à direita).)

Nestes dois dendrogramas de visualização, podemos ver alguns clusters potenciais (3). Após a revisão desses clusters voltaram a ser insignificantes.

NETWORK GRAPH

Após o clustering de dendrogramação mal sucedido, tentamos a abordagem proposta pelo Gráfico. O objetivo aqui, como explicado anteriormente, é fazer um gráfico de todos os nós e vértices possíveis. O comprimento dos vértices é o valor do teste KS. Tivemos que remover a auto-referência (que sempre foi 0 (obviamente você é perfeitamente semelhante a si mesmo).

We then ended up with a network graph where everybody was connected with everybody else which is not particularly useful.

The next step is to only keep the significant link (lower than a certain threshold)

As we can see on this picture, we got a very exciting result. We can clearly see two distinct clusters and three outliers.

This would perfectly fit our model, the big cluster must be the main user and the second cluster could be the alternative user.

After a validity verification, we did find out that the cluster identified some difference between the usage of clusters 1 and 2 but not the one we were looking for. Em outras palavras, não resolveu nosso problema, mas encontrou outro padrão, que poderia ser útil em outro contexto.

CONCLUSÃO

Após este trabalho, concluímos que o KS Test é uma forma muito poderosa de diferenciar automaticamente amostras de diferentes distribuições. Ele não resolveu exatamente nosso problema, mas mostrou que pode ser facilmente utilizado em um contexto de Data Science.

Hoje apresentei um dos problemas que resolvemos com o KS Test, mas também o utilizamos para outros problemas. O KS Test está realmente se tornando um bom teste em nossa faca suíça de ciência de dados.

Quero ler mais

Siga-me no meu blog: coffeeanddata.ca