DevsMobile: Aplicando un algoritmo de segmentación: Clustering para newbies

Hacia mucho que no escribía en el blog y he decidido volver con un interesante ejemplo de cómo funciona un algoritmo de segmentación (también llamado de Clustering) sobre un juego de datos.

Este tipo de algoritmos son los que se emplean pero a nivel gigantesco en Big Data empleando herramientas como Hadoop, etc, pero el algoritmo es así de sencillo (o de complejo).

Lo primero decir que encontraréis todo el código disponible en Github.

Para poder seguir el tutorial necesitaréis tener instalado en vuestra máquina:

MongoDB
Ruby (He explicado dentro de algunos .rb como instalar los gem de dependencias)

Para empezar arrancaremos nuestro MongoDB. Es importante saber que en todo momento voy a emplear la base de datos: segmentationExample

Step 1

Una vez arrancado lo primero si vemos en la carpeta Step1, hay un juego de datos llamado NYC.csv que contiene unas 18000 compras ficticias de actividades de la ciudad de Nueva York:

En la primera columna aparece el identificador de la compra, en la segunda el producto, en la tercera el número de adultos, en la cuarta los niños y en la quinta el código ISO del país del que procede la compra.

Lo primero que generalmente haremos en este tipo de algoritmos es convertir todo lo que podamos a números, puesto que después vamos a operar con ellos y a crear funciones a partir de ellos. Por ello si ejecutamos el script convertCSVInKeys.rb nos genera los ficheros CSVInKeys.csv y equivalences.csv.

Estos ficheros ya tienen el formato deseado y el equivalences nos permitirá volver hacia atrás si así lo deseamos:

Step 2

Una vez tenemos nuestros datos listos, los importaremos en la base de datos Mongo. Para ello, emplearemos el script de la carpeta Step2 llamado importInMongo.bat.

Una vez ejecutado podremos ver desde la consola de mongo en la colección initial nuestros datos importados:

Step 3

Como indiqué al principio es importante jugar siempre con valores numéricos y ahora mismo nosotros tenemos el país en un código ISO. Hay dos enfoques:

Convertir el país a un número (1,2,3...) y jugar con esos números en nuestras fórmulas.
Asumir que la posición de un país y su cercanía a otros puede afectar a la segmentación (es lo que vamos a asumir) y por tanto convertirlo en latitud y longitud.

Usando la latitud y longitud, asumimos que puede que haya un tipo de producto que se dé más en países del Norte, o en países del Oeste...

Para ello usamos el script convertCountryToCoordinates.rb que se encarga de usar una base de datos en JSON de códigos de países para sacar sus coordenadas.

Además vamos a generar un índice de países presentes, para poder mostrar posteriormente la información de nuestros segmentos en el fichero countriesPresent.csv

Una vez ejecutado el script deberíamos tener en la colección geopositionated las muestras con sus latitudes y longitudes:

Step 4

En este paso haremos el proceso del algoritmo en sí mismo, para lo cual están los 4 siguientes scripts que deben ejecutarse en orden y que explicamos a continuación:

1-normalizationParams

Se encarga de encontrar los parámetros de normalización. Cuando trabajamos con números de rangos dispares, estos rangos pueden afectar a los cálculos que estemos haciendo.
Por ejemplo los adultos (1-10) es un número muy diferente de lo que puede ser una latitud (-40 - 40).
Estos parámetros serán la media de cada variable (también llamadas features) que estemos midiendo, y la diferencia entre el máximo y el mínimo.
Estos parámetros los reaprovecharemos luego cuando hagamos una demo y queramos ver en qué segmento cae uno de nuestros datos de prueba (Ver Step 5).
Al acabar de ejecutar el script los encontraremos en la colección normalizationTerms

2-normalizeData

Empleará los parámetros anteriormente encontrados y normaliza todo el juego de datos copiandolos a la colección segmented.
La formula es sencilla: (valor - media)/maxima_diferencia

3-assignInitialClusters

Inicializa cada centroid de un cluster para poder comenzar el algoritmo. Para elegir el número de clusters se puede realizar mediante iteraciones probando diferentes números y analizándolos mediante una función de coste, o "a mano". Para este ejemplo yo he usado la forma manual y he estimado unos 3 clusters por país (Ojo, eso no quiere decir que cada país vaya a acabar al final con 3 clusters, simplemente que habrá COUNTRIES*3 segmentos).
La manera de asignar el cluster, es elegir una muestra aleatoriamente y tomarla como centroid.
Generalmente si se dispone de una función de coste, se suelen realizar varias asignaciones aleatorias para ver cuál es la que mejor funciona. En este caso, no se contempla esta funcionalidad.
Una vez ejecutado tendremos en la colección centroids los centroids iniciales de cada segmento:

4-iterateAlgorithm

Se itera N veces (en nuestro caso 10) la siguiente lógica:

Cada muestra se asigna al segmento más cercano (aquel que la distancia al centroid sea la más pequeña)
Una vez agrupadas, se calcula la media de todas las muestras y el centroid se desplaza hacia esos nuevos valores.

Para observar este movimiento se generan los ficheros centroids_n.txt
Para comprender el algoritmo mejor podéis echarle un vistazo al maravilloso curso de Coursera.
Una vez acabadas las 10 iteraciones, cada muestra estará en un segmento en la colección segmented.

Step 5

El último paso va a ser mostrar los resultados de una manera clara para que podamos jugar con ella. Para lo cual lo primero sacamos los tops por cada segmento ejecutando el script buildTopsBySegment.rb que nos va a generar el fichero top.csv con el top de actividades de cada segmento (si os da problemas quitad la última línea vacía del equivalences.csv generado en el paso 1):

La primera columna es el segmento, la segunda el producto y la tercera el número de apariciones en el segmento.

Y por último generamos la web final, ejecutando el script generateJSONForWeb.rb que nos generará una web local sobre la que poder realizar peticiones y ver qué ordenación y en qué segmento caeríamos con nuestras variables: