KOLMOGOROV-SMIRNOV TEST

På jobbet var vi nyligen tvungna att göra en hel del oövervakad klassificering. Vi var i princip tvungna att särskilja N klasser från en urvalspopulation. Vi hade en ungefärlig uppfattning om hur många klasser som fanns men inget var säkert, vi upptäckte Kolmogorov-Smirnov-testet ett mycket effektivt sätt att avgöra om två prover skiljer sig signifikant från varandra.

Jag kommer att ge dig lite kontext om Kolmogorov-Smirnov-testet och gå igenom ett problem som vi löste med det.

Originalinlägget på coffeeanddata.ca

Reklamation av nollhypotesen. Det låter som ett smärtsamt minne från statistikkursen på universitetet, men det är faktiskt precis vad vi vill göra här. Vi vill förkasta möjligheten att de två proverna kommer från exakt samma fördelning. Låt oss titta på en mycket hög nivå, icke-matematisk, översikt över några tillgängliga tester. Om du vill få en god förståelse för matematiken bakom alla dessa tester kan du använda den Wikipedia-länk som finns i alla avsnitt.

STUDENTENS T-TEST

Studentens T-test är förmodligen det mest välkända sättet att förkasta nollhypotesen. Testet beräknar P-värdet för ett urval jämfört med en normal population eller ett annat urval. Resultatet, P-värdet, talar om hur sannolikt det är att dessa prover kommer från exakt samma fördelning.

När det erhållits kan P-värdet jämföras med ett tröskelvärde för statistisk signifikans (t.ex. 0,05), om P-värdet är mindre kan vi förkasta nollhypotesen.

Det finns en problematik med Studentens T-Test, proverna måste vara normala (formade i en normalfördelning). Det är ett problem för oss eftersom vi arbetar mycket med Poissonfördelningar.

KOLMOGOROV-SMIRNOV TEST

Kolmogorov-Smirnov-testet (KS-testet) är lite mer komplext och gör det möjligt att upptäcka mönster som man inte kan upptäcka med ett Student’s T-Test.

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. Med andra ord:

• Student’s T-Test säger att det finns 79,3 % chans att de två proven kommer från samma fördelning.
• KS Test säger att det finns 1,6 % chans att de två proven kommer från samma fördelning.

Övriga test

Det finns många andra test och algoritmer för att göra den typen av arbete. Shapiro-Wilk-testet och Anderson-Darling-testet är två test som anses vara mer kraftfulla än KS-testet. Det finns en stor nackdel med dessa två tester, de gör det inte möjligt att jämföra två prover, de jämför alltid ett prov med en standardfördelning.

Redigera: En kollega visade mig att Anderson-Darling också kan användas för tvåvägstest (jämförelse av prover).

”K-S-testet med två stickprov är en av de mest användbara och allmänna icke-parametriska metoderna för att jämföra två stickprov” – Wikipedia.

DETEKTERA ANORDNINGENS ANVÄNDARE

För den här specifika uppgiften var vi tvungna att detektera vilken användare som använde en specifik enhet. Varje enhet användes av en eller flera olika användare och vi var tvungna att ta fram en teknik för att identifiera om det fanns en eller flera användare. I fallet med flera användare ville vi identifiera vilken användning som gjordes av vilken användare.

VÅR STRATEGI

Vi bestämde oss för att använda en blandning av grafnätverk och KS Test för att identifiera potentiella kluster. Idén bakom den här demonstrationen är att föreställa sig ett grafnätverk där varje nod (prov) var ansluten till varje annan nod (prov). Vertikalerna eller länken mellan dessa noder skulle ge mig KS Test, med andra ord, hur nära dessa två noder står varandra. Två noder med lågt KS P-värde skulle vara nära varandra och två med högt P-värde skulle vara långt ifrån varandra. Detta skulle förhoppningsvis skapa tydliga kluster.

DATAUPPGIFTER

Här ser våra data ut:

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.En snabb titt på värmekartan för KS-matrisen avslöjar inga uppenbara resultat (Som du kan se på figuren till höger).

Efter så hierarkisk klustring får vi redan lite bättre resultat (Som du kan se på följande figur.)

I dessa två dendrogram visualisering, kan vi se några potentiella (3) kluster. Efter granskning visade sig dessa kluster vara obetydliga.

NETWORK GRAPH

Efter den misslyckade dendrogramklusteringen provade vi den föreslagna Graph-metoden. Målet här är, som tidigare förklarats, att grafera alla möjliga noder och hörn. Längden på noderna är KS-testvärdet. Vi var tvungna att ta bort självreferensen (som alltid var 0 (uppenbarligen är du helt lik dig själv).

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. Med andra ord löste det inte vårt problem utan hittade faktiskt ett annat mönster som kan vara användbart i ett annat sammanhang.

KONKLUSION

Efter detta arbete drog vi slutsatsen att KS-testet är ett mycket kraftfullt sätt att automatiskt särskilja prover från olika fördelning. Det löste inte exakt vårt problem, men det visade att det lätt kan användas i ett datavetenskapssammanhang.

I dag presenterade jag ett av de problem som vi löste med KS Test, men vi använde det även för andra problem. KS Test håller verkligen på att bli ett bra test i vår datavetenskapliga schweizerkniv.

Vill du läsa mer

Följ mig på min blogg: coffeeanddata.ca