TEST DE KOLMOGOROV-SMIRNOV

Récemment, au travail, nous avons dû faire beaucoup de classification non supervisée. Nous devions essentiellement distinguer N classes à partir d’un échantillon de population. Nous avions une idée approximative du nombre de classes présentes mais rien n’était sûr, nous avons découvert le test de Kolmogorov-Smirnov un moyen très efficace de déterminer si deux échantillons sont significativement différents l’un de l’autre.

Je vais vous donner un peu de contexte sur le test de Kolmogorov-Smirnov et vous promener à travers un problème que nous avons résolu avec lui.

Poste original sur coffeeanddata.ca

Rejeter l’hypothèse nulle. Cela ressemble à un souvenir douloureux du cours de statistique universitaire, mais c’est en fait exactement ce que nous voulons faire ici. Nous voulons rejeter la possibilité que les deux échantillons proviennent exactement de la même distribution. Voyons un aperçu de très haut niveau, non mathématique, de certains tests disponibles. Si vous voulez avoir une bonne compréhension des mathématiques derrière tous ces tests, utilisez le lien Wikipedia fourni dans toutes les sections.

TEST T DE STUDENT

Le test T de Student est probablement le moyen le plus connu de rejeter l’hypothèse nulle. Ce test calcule la valeur P d’un échantillon par rapport à une population normale ou par rapport à un autre échantillon. Le résultat, la valeur P, vous indique la probabilité que ces échantillons proviennent exactement de la même distribution.

Une fois obtenue, la valeur P peut être comparée avec un seuil d’appel de signification statistique (par exemple, 0,05), si la valeur P est plus petite, nous pouvons rejeter les hypothèses nulles.

Il y a un problème avec le test T de Student, les échantillons doivent être normaux (formés dans une distribution normale). C’est un problème pour nous car nous travaillons beaucoup avec des distributions de Poisson.

TEST DE KOLMOGOROV-SMIRNOV

Le test de Kolmogorov-Smirnov (test KS) est un peu plus complexe et permet de détecter des modèles que vous ne pouvez pas détecter avec un T-Test de 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. En d’autres termes :

• Le test T de Student dit qu’il y a 79,3 % de chances que les deux échantillons proviennent de la même distribution.
• Le test KS dit qu’il y a 1,6 % de chances que les deux échantillons proviennent de la même distribution.

AUTRES TESTS

Il existe de nombreux autres tests et algorithmes pour faire ce type de travail. Le test de Shapiro-Wilk et le test d’Anderson-Darling sont deux tests considérés comme plus puissants que le test KS. Il y a un inconvénient majeur avec ces deux tests, ils ne permettent pas de comparer deux échantillons, ils comparent toujours un échantillon avec une distribution standard.

Mise à jour : Un de mes collègues m’a montré qu’Anderson-Darling pouvait également être utilisé pour des tests à deux voies (comparaison d’échantillons).

« Le test K-S à deux échantillons est l’une des méthodes non paramétriques les plus utiles et les plus générales pour comparer deux échantillons » – Wikipedia.

DETECT DEVICE USER

Pour cette mission spécifique, nous devions détecter quel utilisateur utilisait un appareil spécifique. Chaque appareil était utilisé par un ou plusieurs utilisateurs différents et nous devions trouver une technique pour identifier s’il y avait un ou plusieurs utilisateurs. Dans le cas d’utilisateurs multiples, nous voulions identifier quelle utilisation était faite par quel utilisateur.

Notre stratégie

Nous avons décidé d’utiliser un mélange de réseau de graphes et de test KS pour identifier les clusters potentiels. L’idée derrière cette démo est d’imaginer un réseau de graphes où chaque nœud (échantillon) était connecté à chaque autre nœud (échantillon). Les sommets ou les liens entre ces nœuds représenteraient le test KS, en d’autres termes, la proximité de ces deux nœuds. Ainsi, deux nœuds avec une faible valeur P KS seraient proches et deux avec une valeur P élevée seraient éloignés. Cela permettrait, on l’espère, de créer des clusters distincts.

DATA SET

Voici à quoi ressemblent nos données :

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.Une vue rapide de la carte thermique de la matrice KS ne révèle pas de résultats évidents (Comme vous pouvez le voir sur la figure de votre droite).

Après un clustering si hiérarchique, nous obtenons déjà de meilleurs résultats.(Comme vous pouvez le voir sur la figure suivante.)

Dans ces deux visualisations de dendrogrammes, nous pouvons voir quelques (3) clusters potentiels. Après examen, ces clusters se sont révélés insignifiants.

GRAPHIQUE DE RÉSEAU

Après l’échec du clustering par dendrogramme, nous avons essayé l’approche graphique proposée. L’objectif ici, comme expliqué précédemment, est de graphiser tous les nœuds et sommets possibles. La longueur des sommets étant la valeur du test KS. Nous avons dû supprimer l’autoréférence (qui était toujours 0 (évidemment vous êtes parfaitement semblable à vous-même).

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. En d’autres termes, il n’a pas résolu notre problème, mais il a en fait trouvé un autre modèle, qui pourrait être utile dans un autre contexte.

CONCLUSION

Après ce travail, nous avons conclu que le test KS est un moyen très puissant de différencier automatiquement les échantillons de différentes distributions. Il n’a pas exactement résolu notre problème, mais il a montré qu’il peut facilement être utilisé dans un contexte de Data Science.

Aujourd’hui, je vous ai présenté l’un des problèmes que nous avons résolu avec KS Test, mais nous l’avons également utilisé pour d’autres problèmes. KS Test est vraiment en train de devenir un bon test dans notre couteau suisse de la science des données.

Vous voulez en lire plus

Suivez-moi sur mon blog : coffeeanddata.ca