KOLMOGOROV-SMIRNOV TEST

In letzter Zeit mussten wir bei der Arbeit eine Menge unüberwachter Klassifizierungen durchführen. Im Grunde mussten wir N Klassen aus einer Stichprobenpopulation unterscheiden. Wir hatten eine ungefähre Vorstellung davon, wie viele Klassen vorhanden waren, aber nichts war sicher, und so entdeckten wir den Kolmogorov-Smirnov-Test, eine sehr effiziente Methode, um festzustellen, ob sich zwei Stichproben signifikant voneinander unterscheiden.

Ich werde Ihnen ein wenig über den Kolmogorov-Smirnov-Test erzählen und Sie durch ein Problem führen, das wir damit gelöst haben.

Originalbeitrag auf coffeeanddata.ca

Die Nullhypothese abzulehnen. Das klingt wie eine schmerzhafte Erinnerung an den Statistikunterricht an der Universität, aber es ist eigentlich genau das, was wir hier tun wollen. Wir wollen die Möglichkeit ausschließen, dass die beiden Stichproben aus genau der gleichen Verteilung stammen. Schauen wir uns einen sehr einfachen, nicht-mathematischen Überblick über einige der verfügbaren Tests an. Wenn Sie die Mathematik, die hinter all diesen Tests steckt, besser verstehen wollen, verwenden Sie den Wikipedia-Link, der in allen Abschnitten angegeben ist.

STUDENT’S T-TEST

Der Student’s T-Test ist wahrscheinlich die bekannteste Methode, um die Nullhypothese zurückzuweisen. Bei diesem Test wird der P-Wert einer Stichprobe im Vergleich zu einer Normalpopulation oder zu einer anderen Stichprobe berechnet. Das Ergebnis, der P-Wert, gibt Auskunft darüber, wie wahrscheinlich es ist, dass diese Stichproben aus der gleichen Verteilung stammen.

Der P-Wert kann mit einem Schwellenwert verglichen werden, der als statistische Signifikanz bezeichnet wird (z. B. .05); wenn der P-Wert kleiner ist, kann die Nullhypothese zurückgewiesen werden.

Es gibt ein Problem mit dem Student’s T-Test: Die Stichproben müssen normal sein (in einer Normalverteilung geformt). Das ist für uns ein Problem, weil wir viel mit Poisson-Verteilungen arbeiten.

KOLMOGOROV-SMIRNOV TEST

Der Kolmogorov-Smirnov-Test (KS-Test) ist etwas komplexer und ermöglicht es, Muster zu erkennen, die mit dem Student’s T-Test nicht erkannt werden können.

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. Mit anderen Worten:

• Der Student’s T-Test besagt, dass die Wahrscheinlichkeit, dass die beiden Stichproben aus der gleichen Verteilung stammen, 79,3 % beträgt.
• Der KS-Test besagt, dass die Wahrscheinlichkeit, dass die beiden Stichproben aus der gleichen Verteilung stammen, 1,6 % beträgt.

Weitere Tests

Es gibt viele andere Tests und Algorithmen, die diese Art von Arbeit erledigen. Der Shapiro-Wilk-Test und der Anderson-Darling-Test sind zwei Tests, die als leistungsfähiger gelten als der KS-Test. Es gibt einen großen Nachteil bei diesen beiden Tests, sie erlauben es nicht, zwei Stichproben zu vergleichen, sie vergleichen immer eine Stichprobe mit einer Standardverteilung.

Edit: Ein Kollege von mir hat mir gezeigt, dass Anderson-Darling auch für Zwei-Wege-Tests verwendet werden kann (Vergleich von Stichproben).

„Der K-S-Test für zwei Stichproben ist eine der nützlichsten und allgemeinsten nichtparametrischen Methoden zum Vergleich zweier Stichproben“ – Wikipedia.

DETECT DEVICE USER

Für diese spezielle Aufgabe mussten wir feststellen, welcher Benutzer ein bestimmtes Gerät benutzt. Jedes Gerät wurde von einem oder mehreren verschiedenen Benutzern verwendet, und wir mussten eine Technik entwickeln, um zu erkennen, ob es sich um einen oder mehrere Benutzer handelte.

Unsere Strategie

Wir entschieden uns, eine Mischung aus Graphennetzwerk und KS-Test zu verwenden, um potenzielle Cluster zu identifizieren. Die Idee hinter dieser Demo ist, sich ein Graphennetzwerk vorzustellen, in dem jeder Knoten (Probe) mit jedem anderen Knoten (Probe) verbunden ist. Die Knotenpunkte oder Verbindungen zwischen diesen Knoten würden den KS-Test darstellen, mit anderen Worten, wie nahe diese beiden Knoten beieinander liegen. Zwei Knoten mit niedrigem KS P-Wert würden also nahe beieinander liegen und zwei mit hohem P-Wert weit voneinander entfernt sein. Dies würde hoffentlich zu unterscheidbaren Clustern führen.

DATENSATZ

So sehen unsere Daten aus:

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.Ein kurzer Blick auf die Heatmap der KS-Matrix zeigt keine eindeutigen Ergebnisse (wie in der Abbildung rechts zu sehen).

Nach dem hierarchischen Clustering erhalten wir bereits bessere Ergebnisse (wie in der folgenden Abbildung zu sehen ist).)

In diesen beiden Dendrogramm-Darstellungen, können wir einige potenzielle (3) Cluster sehen. Nach der Überprüfung erwiesen sich diese Cluster als unbedeutend.

NETWORK GRAPH

Nach dem erfolglosen Dendrogramm-Clustering haben wir den vorgeschlagenen Graph-Ansatz versucht. Wie bereits erläutert, besteht das Ziel hier darin, alle möglichen Knoten und Eckpunkte grafisch darzustellen. Die Länge der Scheitelpunkte ist der KS-Testwert. Wir mussten die Selbstreferenz entfernen, die immer 0 war (offensichtlich ist man sich selbst vollkommen ähnlich).

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. Mit anderen Worten, er hat unser Problem nicht gelöst, aber er hat ein anderes Muster gefunden, das in einem anderen Kontext nützlich sein könnte.

ZUSAMMENFASSUNG

Nach dieser Arbeit sind wir zu dem Schluss gekommen, dass der KS-Test ein sehr leistungsfähiges Mittel zur automatischen Unterscheidung von Stichproben aus unterschiedlichen Verteilungen ist. Er hat zwar nicht genau unser Problem gelöst, aber er hat gezeigt, dass er leicht in einem Data Science-Kontext verwendet werden kann.

Heute habe ich euch eines der Probleme vorgestellt, die wir mit dem KS Test gelöst haben, aber wir haben ihn auch für andere Probleme verwendet. KS Test wird wirklich zu einem guten Test in unserem Data Science Schweizer Messer.

Wollen Sie mehr lesen

Folgen Sie mir auf meinem Blog: coffeeanddata.ca