TEST DE KOLMOGOROV-SMIRNOV

Últimamente, en el trabajo, tuvimos que hacer mucha clasificación no supervisada. Básicamente teníamos que distinguir N clases de una población de muestra. Teníamos una idea aproximada de cuántas clases había pero nada era seguro, descubrimos el test de Kolmogorov-Smirnov una forma muy eficiente de determinar si dos muestras son significativamente diferentes entre sí.

Os daré un poco de contexto sobre el test de Kolmogorov-Smirnov y os guiaré a través de un problema que resolvimos con él.

Post original en coffeeanddata.ca

Rechazar la hipótesis nula. Eso suena como un doloroso recuerdo de la clase de estadística de la universidad, pero en realidad es exactamente lo que queremos hacer aquí. Queremos rechazar la posibilidad de que las dos muestras provengan exactamente de la misma distribución. Veamos un resumen de muy alto nivel, no matemático, de algunas pruebas disponibles. Si desea obtener una buena comprensión de las matemáticas detrás de todas estas pruebas, utilice el enlace de Wikipedia proporcionado en todas las secciones.

Prueba T de Student

La prueba T de Student es probablemente la forma más conocida de rechazar la hipótesis nula. Esta prueba calcula el valor P de una muestra frente a una población normal o frente a otra muestra. El resultado, el valor P, le indica la probabilidad de que estas muestras provengan exactamente de la misma distribución.

Cuando se obtiene, el valor P se puede comparar con un umbral llamado significación estadística (por ejemplo, 0,05), si el valor P es menor, podemos rechazar la hipótesis nula.

Hay un problema con la prueba T de Student, las muestras deben ser normales (con forma de distribución normal). Esto es un problema para nosotros porque trabajamos mucho con distribuciones de Poisson.

TEST DE KOLMOGOROV-SMIRNOV

El test de Kolmogorov-Smirnov (Test KS) es un poco más complejo y permite detectar patrones que no se pueden detectar con el Test T 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 otras palabras:

• La Prueba T de Student dice que hay un 79,3% de posibilidades de que las dos muestras provengan de la misma distribución.
• La Prueba KS dice que hay un 1,6% de posibilidades de que las dos muestras provengan de la misma distribución.

Otras Pruebas

Hay muchas otras Pruebas y algoritmos para hacer ese tipo de trabajo. La prueba de Shapiro-Wilk y la prueba de Anderson-Darling son dos pruebas consideradas más potentes que la prueba KS. Hay un inconveniente importante con estas dos pruebas, no permiten comparar dos muestras, siempre comparan una muestra con una distribución estándar.

Edición: Un colega mío me mostró que Anderson-Darling también podría ser utilizado para pruebas de dos vías (Comparación de Muestras).

«La prueba K-S de dos muestras es uno de los métodos no paramétricos más útiles y generales para comparar dos muestras» – Wikipedia.

DETECTAR USUARIO DE DISPOSITIVO

Para este encargo concreto teníamos que detectar qué usuario utilizaba un dispositivo concreto. Cada dispositivo era utilizado por uno o varios usuarios diferentes y teníamos que idear una técnica para identificar si había uno o varios usuarios. En el caso de múltiples usuarios queríamos identificar qué uso hacía cada usuario.

Nuestra estrategia

Decidimos utilizar una mezcla de grafos de red y KS Test para identificar posibles clusters. La idea detrás de esta demostración es imaginar una red de grafos donde cada nodo (muestra) estaba conectado a cada otro nodo (muestra). Los vértices o el enlace entre estos nodos serían la prueba KS, en otras palabras, lo cerca que están estos dos nodos. Así, dos nodos con un valor KS P bajo estarían cerca y dos con un valor P alto estarían lejos. Esto, con suerte, crearía clusters distinguibles.

CONJUNTO DE DATOS

Aquí se ven nuestros datos:



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.Una vista rápida del mapa de calor de la matriz KS no revela resultados obvios (Como se puede ver en la figura a su derecha).

Después de la agrupación jerárquica, ya obtenemos algunos resultados mejores (como se puede ver en la siguiente figura.)



En estas dos visualizaciones de dendrogramas, podemos ver algunos clusters potenciales (3). Después de la revisión, estos clústeres resultaron ser insignificantes.

GRÁFICO DE RED

Después del dendrograma infructuoso, probamos el enfoque gráfico propuesto. El objetivo aquí, como se explicó anteriormente, es graficar todos los posibles nodos y vértices. La longitud de los vértices es el valor de la prueba KS. Tuvimos que eliminar la autorreferencia (que siempre era 0 (obviamente eres perfectamente similar a ti mismo).



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 otras palabras, no resolvió nuestro problema pero sí encontró otro patrón, que podría ser útil en otro contexto.

CONCLUSIÓN

Después de este trabajo, concluimos que la prueba KS es una forma muy poderosa de diferenciar automáticamente muestras de diferente distribución. No resolvió exactamente nuestro problema, pero demostró que se puede utilizar fácilmente en un contexto de Ciencia de Datos.

Hoy os he presentado uno de los problemas que hemos resuelto con el KS Test, pero también lo hemos utilizado para otros problemas. Realmente el KS Test se está convirtiendo en una buena prueba en nuestra navaja suiza de ciencia de datos.

Quieres leer más

Sígueme en mi blog: coffeeanddata.ca