KOLMOGOROV-SMIRNOV TEST

Ultimamente, al lavoro, abbiamo dovuto fare un sacco di classificazione non supervisionata. In pratica dovevamo distinguere N classi da una popolazione campione. Avevamo un’idea approssimativa di quante classi fossero presenti ma niente era sicuro, abbiamo scoperto il test di Kolmogorov-Smirnov un modo molto efficiente per determinare se due campioni sono significativamente diversi l’uno dall’altro.

Vi darò un po’ di contesto sul test di Kolmogorov-Smirnov e vi accompagnerò attraverso un problema che abbiamo risolto con esso.

Post originale su coffeeanddata.ca

Rifiutare l’ipotesi nulla. Sembra un ricordo doloroso delle lezioni universitarie di statistica, ma in realtà è esattamente quello che vogliamo fare qui. Vogliamo rifiutare la possibilità che i due campioni provengano esattamente dalla stessa distribuzione. Diamo un’occhiata a una panoramica di alto livello, non matematica, di alcuni test disponibili. Se volete avere una buona comprensione della matematica dietro tutti questi test, usate il link di Wikipedia fornito in tutte le sezioni.

STUDENT’S T-TEST

Il test T di Student è probabilmente il modo più conosciuto per rifiutare l’ipotesi nulla. Questo test calcola il valore P di un campione contro una popolazione normale o contro un altro campione. Il risultato, il valore P, vi dice quanto è probabile che questi campioni provengano esattamente dalla stessa distribuzione.

Una volta ottenuto, il valore P può essere confrontato con una soglia di significatività statistica (ad esempio .05), se il valore P è più piccolo, possiamo rifiutare l’ipotesi nulla.

C’è un problema con il T-Test di Student, i campioni devono essere normali (con forma in una distribuzione normale). Questo è un problema per noi perché lavoriamo molto con le distribuzioni di Poisson.

KOLMOGOROV-SMIRNOV TEST

Il test di Kolmogorov-Smirnov (KS Test) è un po’ più complesso e ti permette di rilevare modelli che non puoi rilevare con il T-Test di Student.

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. In altre parole:

• Il test T di Student dice che c’è il 79,3% di possibilità che i due campioni provengano dalla stessa distribuzione.
• Il test KS dice che c’è l’1,6% di possibilità che i due campioni provengano dalla stessa distribuzione.

Altri test

Ci sono molti altri test e algoritmi per fare questo tipo di lavoro. Il test di Shapiro-Wilk e il test di Anderson-Darling sono due test considerati più potenti del test KS. C’è un grande svantaggio con questi due test, non permettono di confrontare due campioni, ma sempre un campione con una distribuzione standard.

Modifica: Un mio collega mi ha mostrato che Anderson-Darling potrebbe anche essere usato per test a due vie (Confronto tra campioni).

“Il test K-S a due campioni è uno dei metodi non parametrici più utili e generali per confrontare due campioni” – Wikipedia.

DETECT DEVICE USER

Per questo compito specifico abbiamo dovuto rilevare quale utente stava usando un dispositivo specifico. Ogni dispositivo era usato da uno o molti utenti diversi e dovevamo trovare una tecnica per identificare se c’erano uno o più utenti. Nel caso di utenti multipli volevamo identificare quale uso veniva fatto da quale utente.

LA NOSTRA STRATEGIA

Abbiamo deciso di usare un mix di graph network e KS Test per identificare potenziali cluster. L’idea alla base di questa demo è quella di immaginare una rete a grafo dove ogni nodo (campione) è collegato ad ogni altro nodo (campione). I vertici o i collegamenti tra questi nodi sarebbero io KS Test, in altre parole, quanto sono vicini questi due nodi. Quindi due nodi con un basso valore KS P sarebbero vicini e due con un alto valore P sarebbero lontani. Si spera che questo crei dei cluster distinguibili.

SET DI DATI

Ecco come si presentano i nostri dati:

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.Una rapida visualizzazione della mappa di calore della matrice KS non rivela risultati evidenti (Come potete vedere nella figura alla vostra destra).

Dopo il clustering gerarchico, otteniamo già alcuni risultati migliori (come potete vedere nella figura seguente).)

In queste due visualizzazioni di dendrogrammi, possiamo vedere alcuni potenziali (3) cluster. Dopo la revisione questi cluster sono risultati insignificanti.

NETWORK GRAPH

Dopo il clustering dendrogramma senza successo, abbiamo provato l’approccio Graph proposto. L’obiettivo qui, come spiegato in precedenza, è quello di graficare tutti i possibili nodi e vertici. La lunghezza dei vertici è il valore del test KS. Abbiamo dovuto rimuovere l’autoreferenza (che era sempre 0 (ovviamente sei perfettamente simile a te stesso).

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. In altre parole, non ha risolto il nostro problema ma ha effettivamente trovato un altro modello, che potrebbe essere utile in un altro contesto.

CONCLUSIONE

Dopo questo lavoro, abbiamo concluso che il test di KS è un modo molto potente per differenziare automaticamente i campioni da distribuzioni diverse. Non ha risolto esattamente il nostro problema, ma ha dimostrato che può essere facilmente utilizzato in un contesto di Data Science.

Oggi vi ho presentato uno dei problemi che abbiamo risolto con KS Test, ma lo abbiamo anche usato per altri problemi. KS Test sta davvero diventando un buon test nel nostro coltellino svizzero della scienza dei dati.

Vuoi saperne di più

Seguimi sul mio blog: coffeeanddata.ca