KOLMOGOROV-SMIRNOV TEST

De laatste tijd moesten we op ons werk veel onbewaakte classificatie doen. In principe moesten we N klassen onderscheiden van een steekproefpopulatie. We hadden een ruw idee van hoeveel klassen er waren maar niets was zeker, we ontdekten de Kolmogorov-Smirnov test een zeer efficiënte manier om te bepalen of twee steekproeven significant van elkaar verschillen.

Ik zal je een beetje context geven over de Kolmogorov-Smirnov test en je door een probleem leiden dat we ermee hebben opgelost.

Oorspronkelijke post op coffeeanddata.ca

Het verwerpen van de nulhypothese. Dat klinkt als een pijnlijke herinnering uit de colleges statistiek aan de universiteit, maar het is eigenlijk precies wat we hier willen doen. We willen de mogelijkheid verwerpen dat de twee monsters uit precies dezelfde verdeling komen. Laten we eens kijken naar een zeer hoog niveau, niet-wiskundig, overzicht van enkele beschikbare tests. Als u de wiskunde achter al deze tests goed wilt begrijpen, gebruik dan de Wikipedia-link in alle paragrafen.

STUDENT’S T-TEST

De Student’s T-Test is waarschijnlijk de bekendste manier om de nulhypothese te verwerpen. Deze test berekent de P-waarde van een steekproef ten opzichte van een normale populatie of ten opzichte van een andere steekproef. Het resultaat, de P-waarde, vertelt je hoe waarschijnlijk het is dat deze steekproeven uit precies dezelfde verdeling komen.

De verkregen P-waarde kan worden vergeleken met een drempelwaarde voor statistische significantie (bijv. .05), als de P-waarde kleiner is, kunnen we de nulhypothese verwerpen.

Er is een probleem met de Student’s T-Test, de steekproeven moeten normaal zijn (de vorm van een normale verdeling hebben). Dat is voor ons een probleem omdat we veel met Poisson verdelingen werken.

KOLMOGOROV-SMIRNOV TEST

De Kolmogorov-Smirnov test (KS Test) is wat complexer en stelt je in staat patronen te ontdekken die je met een Student’s T-Test niet kunt ontdekken.

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. Met andere woorden:

• De Student’s T-Test zegt dat er 79,3% kans is dat de twee monsters uit dezelfde verdeling komen.
• KS Test zegt dat er 1,6% kans is dat de twee monsters uit dezelfde verdeling komen.

ANDERE TESTS

Er zijn vele andere tests en algoritmen om dat soort werk te doen. De Shapiro-Wilk test en de Anderson-Darling test zijn twee tests die als krachtiger worden beschouwd dan de KS Test. Er is een groot nadeel aan deze twee testen, je kunt er geen twee steekproeven mee vergelijken, ze vergelijken altijd een steekproef met een standaardverdeling.

Edit: Een collega van mij liet me zien dat Anderson-Darling ook gebruikt kan worden voor twee-weg testen (Vergelijken van steekproeven).

“De two-sample K-S test is een van de meest bruikbare en algemene niet-parametrische methoden voor het vergelijken van twee steekproeven” – Wikipedia.

DETECT DEVICE USER

Voor deze specifieke opdracht moesten we detecteren welke gebruiker een specifiek apparaat gebruikte. Elk apparaat werd door een of meerdere gebruikers gebruikt en we moesten een techniek bedenken om vast te stellen of er sprake was van een of meerdere gebruikers. In het geval van meerdere gebruikers wilden we vaststellen welk gebruik door welke gebruiker werd gedaan.

Onze STRATEGIE

We besloten een mix van grafieknetwerk en KS Test te gebruiken om potentiële clusters te identificeren. Het idee achter deze demo is om een grafieknetwerk voor te stellen waarin elk knooppunt (monster) is verbonden met elk ander knooppunt (monster). De hoekpunten of schakels tussen deze knooppunten zouden me KS Test, met andere woorden, hoe dicht zijn deze twee knooppunten bij elkaar. Dus twee knooppunten met een lage KS P-waarde zouden dichtbij zijn en twee met een hoge P-waarde zouden veraf zijn. Dit zou hopelijk onderscheidbare clusters opleveren.

GEGEVENS SET

Hier ziet onze data er uit:

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.Een snelle blik op de heat map van de KS-matrix levert geen voor de hand liggende resultaten op (zoals u op de figuur rechts kunt zien).

Na zo hiërarchisch clusteren krijgen we al wat betere resultaten.(Zoals u op de volgende figuur kunt zien.)

In deze twee dendrogram-visualisatie, kunnen we een aantal potentiële (3) clusters zien. Na beoordeling bleken deze clusters niet significant te zijn.

NETWORK GRAPH

Na de onsuccesvolle dendrogram clustering, probeerden we de voorgestelde Graph benadering. Het doel hier is, zoals eerder uitgelegd, alle mogelijke knooppunten en hoekpunten in een grafiek weer te geven. De lengte van de hoekpunten is de KS Test Waarde. We moesten de zelfverwijzing verwijderen (die was altijd 0 (uiteraard lijk je perfect op jezelf).

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. Met andere woorden, het loste ons probleem niet op, maar vond eigenlijk een ander patroon, dat nuttig zou kunnen zijn in een andere context.

CONCLUSIE

Na dit werk hebben we geconcludeerd dat de KS Test een zeer krachtige manier is om automatisch steekproeven uit verschillende distributies te onderscheiden. Het heeft niet precies ons probleem opgelost, maar het heeft wel laten zien dat het gemakkelijk kan worden gebruikt in een Data Science context.

Vandaag heb ik jullie een van de problemen laten zien die we hebben opgelost met KS Test, maar we hebben het ook voor andere problemen gebruikt. KS Test is echt een goede test aan het worden in ons data science Swiss knife.

Wil je meer lezen

Volg me op mijn blog: coffeeanddata.ca