KOLMOGOROV-SMIRNOV TEST

V poslední době jsme v práci museli provádět spoustu klasifikací bez dohledu. V podstatě jsme museli rozlišit N tříd ze vzorku populace. Měli jsme přibližnou představu o počtu tříd, ale nic nebylo jisté, objevili jsme Kolmogorovův-Smirnovův test velmi účinný způsob, jak určit, zda se dva vzorky od sebe významně liší.

Představím vám trochu kontextu Kolmogorovova-Smirnovova testu a provedu vás jedním problémem, který jsme s ním řešili.

Původní příspěvek na coffeeanddata.ca

Zamítnutí nulové hypotézy. Zní to jako bolestná vzpomínka z hodin statistiky na univerzitě, ale ve skutečnosti je to přesně to, co chceme udělat zde. Chceme zamítnout možnost, že oba vzorky pocházejí z úplně stejného rozdělení. Podívejme se na velmi vysoký, nematematický přehled některých dostupných testů. Pokud chcete dobře porozumět matematice, která se za všemi těmito testy skrývá, použijte odkaz na Wikipedii uvedený ve všech kapitolách.

STUDENTSKÝ T-TEST

Studentský T-test je pravděpodobně nejznámější způsob zamítnutí nulové hypotézy. Tento test vypočítá P-hodnotu vzorku oproti normální populaci nebo oproti jinému vzorku. Výsledek, P-hodnota, říká, s jakou pravděpodobností tyto vzorky pocházejí z naprosto stejného rozdělení.

Po získání P-hodnoty ji lze porovnat s prahovou hodnotou, která se nazývá statistická významnost (např. .05), pokud je P-hodnota menší, můžeme nulovou hypotézu zamítnout.

U Studentova T-testu je problém, vzorky musí být normální (mít tvar normálního rozdělení). To je pro nás problém, protože hodně pracujeme s Poissonovým rozdělením.

KOLMOGOROV-SMIRNOV TEST

Kolmogorovův-Smirnovův test (KS test) je trochu složitější a umožňuje odhalit vzory, které nelze odhalit pomocí Studentova T-testu.

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. Jinými slovy:

• Studentův T-test říká, že je 79,3% pravděpodobnost, že oba vzorky pocházejí ze stejného rozdělení.
• KS test říká, že je 1,6% pravděpodobnost, že oba vzorky pocházejí ze stejného rozdělení.

Další testy

Existuje mnoho dalších testů a algoritmů pro tento typ práce. Shapirův-Wilkův test a Andersonův-Darlingův test jsou dva testy považované za silnější než KS test. Tyto dva testy mají jednu zásadní nevýhodu, neumožňují porovnávat dva vzorky, vždy porovnávají vzorek se standardním rozdělením.

Edit: Kolega mi ukázal, že Andersonův-Darlingův test lze použít i pro obousměrné testování (porovnávání vzorků).

„Dvouvýběrový K-S test je jednou z nejužitečnějších a nejobecnějších neparametrických metod pro porovnávání dvou vzorků.“ – Wikipedie.

DETEKCE UŽIVATELE ZAŘÍZENÍ

Pro toto konkrétní zadání jsme měli zjistit, který uživatel používá konkrétní zařízení. Každé zařízení používal jeden nebo více různých uživatelů a my jsme museli vymyslet techniku, jak zjistit, zda se jedná o jednoho nebo více uživatelů. V případě více uživatelů jsme chtěli určit, které použití provedl který uživatel.

NAŠE STRATEGIE

Pro identifikaci potenciálních shluků jsme se rozhodli použít kombinaci sítě grafů a KS testu. Myšlenka této ukázky spočívá v představě sítě grafů, kde byl každý uzel (vzorek) propojen s každým jiným uzlem (vzorkem). Vrcholy nebo spojení mezi těmito uzly by mi KS Test, jinými slovy, jak blízko jsou si tyto dva uzly. Takže dva uzly s nízkou hodnotou KS P-Value by byly blízko a dva s vysokou hodnotou P-Value by byly daleko. Tím by snad vznikly rozlišitelné shluky.

SADA DAT

Tady vypadají naše data:

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.Rychlý pohled na tepelnou mapu KS matice neodhalí zřejmé výsledky (Jak můžete vidět na obrázku vpravo).

Po takovém hierarchickém shlukování již získáme o něco lepší výsledky (Jak můžete vidět na následujícím obrázku.)

V těchto dvou vizualizacích dendrogramů, můžeme vidět některé potenciální (3) shluky. Po přezkoumání se tyto shluky ukázaly jako nevýznamné.

NETWORK GRAPH

Po neúspěšném shlukování dendrogramů jsme vyzkoušeli navrhovaný přístup Graph. Zde je cílem, jak bylo vysvětleno dříve, vytvořit graf všech možných uzlů a vrcholů. Délka vrcholů je testovací hodnota KS. Museli jsme odstranit autoreferenci (která byla vždy 0 (zřejmě jste si dokonale podobní).

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. Jinými slovy, nevyřešil náš problém, ale ve skutečnosti našel jiný vzorek, který by mohl být užitečný v jiném kontextu.

ZÁVĚR

Po této práci jsme dospěli k závěru, že KS test je velmi účinný způsob automatického rozlišování vzorků z různých distribucí. Nevyřešil přesně náš problém, ale ukázal, že jej lze snadno použít v kontextu datové vědy.

Dnes jsem vám představil jeden z problémů, který jsme pomocí testu KS vyřešili, ale použili jsme jej i pro jiné problémy. KS Test se opravdu stává dobrým testem v našem švýcarském noži pro data science.

Chcete si přečíst více

Sledujte mě na mém blogu: coffeeanddata.ca