junio 06, 2013

SAP HANA PAL – Algoritmo k-means, o cómo segmentar clientes en la industria de las telecomunicaciones

By Lucas Sparvieri

PAL es un componente opcional provisto por SAP HANA. Su propósito principal es permitir a los modeladores realizar análisis predictivos sobre grandes volúmenes de datos. Si ésta es la primera vez que oyen hablar de PAL, les recomiendo la documentación oficial. También pueden ver mi post anterior, donde hablo del Algoritmo Apriori.
En este post me voy a enfocar en cómo se usa el Algoritmo K-Means incluido en PAL, porque es uno de los más populares y más comúnmente usados en minería de datos (data mining).
Según Wikipedia, “clustering es la tarea de agrupar un conjunto de objetos de forma que los objetos de un mismo grupo (llamado cluster) sean más similares entre sí (en un sentido determinado) que respecto de los objetos de otros clusters”. En otras palabras, se trata de agrupar datos en múltiples clusters.
El caso más común para aplicar algoritmos de clustering es la segmentación de clientes, es decir, la tarea de dividir la base de clientes en grupos mediante un algoritmo que tome en cuenta cuán similares sean los clientes, o bien cuán similares sean sus comportamientos, por ejemplo, respecto de su edad, género, intereses, hábitos de consumo, etc.
El algoritmo k-means funciona de una manera muy simple -- por lo menos para mí, porque no tengo que codearlo en C++ :). El primer paso es plotear todos los objetos de la base de datos en un espacio donde cada atributo sea una dimensión. Entonces, si usamos un conjunto de datos con dos atributos, el gráfico resultante se verá más o menos así:

1.png

Cuando todos los objetos hayan sido ploteados, el algoritmo calculará la distancia entre ellos; los que estén más cerca se agruparán en el mismo cluster. Si volvemos al gráfico anterior, veremos ahora cuatro clusters diferentes:

2.png

Luego cada cluster se asocia con un centroide y a cada punto se le asigna el cluster con el centroide más cercano. El centroide es la media de los puntos del cluster. La cercanía se puede medir usando:
  • distancia de Manhattan
  • distancia euclideana
  • distancia de Minkowski
Cada vez que un punto es asignado a un cluster, el centroide se recalcula. Esto se repite durante múltiples iteraciones, hasta que los centroides ya no cambien (es decir, hasta que todos los puntos hayan sido asignados a su cluster correspondiente). En general, la mayoría de los movimientos de centroides ocurre en las primeras iteraciones.
Una de las desventajas principales del algoritmo k-means es que se necesita especificar inicialmente el número k de clusters como parámetro de entrada. Conocer este valor es, en general, muy difícil; por esta razón es importante ejecutar funciones que midan la calidad del proceso de clustering. Más adelante hablaremos de esto.
Encontré un paper muy interesante que habla sobre la segmentación en la industria de las telecomunicaciones, y pensé que sería un buen caso de uso armar una demo del algoritmo k-means en HANA (si están interesados en el tema, les recomiendo que lean el paper). He aquí los pasos que seguí:

Preparar los datos

El primer paso es crear la tabla que contendrá la información del uso de telefonía móvil de nuestros clientes. La tabla tiene la siguiente estructura:

CREATE COLUMN TABLE "TELCO" (
"ID" INTEGER NOT NULL, --> Customer ID
"AVG_CALL_DURATION" DOUBLE, --> duración promedio de la llamada
"AVG_NUMBER_CALLS_RCV_DAY" DOUBLE, --> promedio de llamadas recibidas por día
"AVG_NUMBER_CALLS_ORI_DAY" DOUBLE, --> promedio de llamadas hechas por día
"DAY_TIME_CALLS" DOUBLE, --> porcentaje de llamadas hechas durante horario laboral (9 a.m. - 6 p.m.)
"WEEK_DAY_CALLS" DOUBLE, --> porcentaje de llamadas hechas durante días de la semana (lunes a viernes)
"CALLS_TO_MOBILE" DOUBLE, --> porcentaje de llamadas hechas a teléfonos móviles
"SMS_RCV_DAY" DOUBLE, --> número de SMS recibidos por día
"SMS_ORI_DAY" DOUBLE, --> número de SMS enviados por día
PRIMARY KEY ("ID"))

Cada fila en la tabla representa un cliente único. Ahora necesito llenarla, pero no tengo acceso a datos reales, de modo que tuve que armar mi propio conjunto de datos. Creé 30 clientes distintos (30 filas) que se pueden agrupar en 3 segmentos:
  • Segmento 1: Desde el Customer ID 1 hasta el 10. En este segmento los clientes hacen y reciben pocas llamadas, de corta duración. Llaman más durante la tarde y los fines de semana, y a líneas de telefonía fija. Envían y reciben un número considerable de SMS. Este segmento podría representar a los usuarios particulares de telefonía móvil.
  • Segmento 2: Desde el Customer ID 10001 hasta el 10010. En este segmento, las llamadas de los clientes tienen una duración promedio. El número de llamadas que los clientes hacen y reciben también es promedio. En general llaman en el horario laboral, durante los días de semana. Mandan y reciben un número promedio de SMS. Este segmento podría representar a los usuarios profesionales de pequeñas empresas.
  • Segmento 3: Desde el Customer ID 20001 hasta el 20010. En este segmento los clientes tienen llamadas largas. En general llaman durante el horario laboral los días de semana, a líneas de telefonía móvil, y hacen uso intensivo de los SMS. Este segmento podría representar a los usuarios profesionales de las grandes empresas.
La tabla resultante se ve así:

3.png

Generar el procedimiento PAL

Ahora que tengo un conjunto de datos, estoy listo para empezar a codear. Lo primero que necesito es llamar al AFL Wrapper Generator para generar el procedimiento PAL. Para eso, necesitamos crear varios tipos que se usarán para definir la estructura de los datos que serán utilizados como parámetros de entrada y salida:

SET SCHEMA _SYS_AFL;

/* tipo que se usará como parámetro de salida
que contendrá el cluster al que haya sido asignado cada
cliente y cuál es la distancia a la media del cluster */
DROP TYPE PAL_KMEANS_RESASSIGN_TELCO;
CREATE TYPE PAL_KMEANS_RESASSIGN_TELCO AS TABLE(
"ID" INT,
"CENTER_ASSIGN" INT,
"DISTANCE" DOUBLE
);

/* tipo que se usará como parámetro de entrada
que contendrá los datos que quiero agrupar en clusters */
DROP TYPE PAL_KMEANS_DATA_TELCO;
CREATE TYPE PAL_KMEANS_DATA_TELCO AS TABLE(
"ID" INT,
"AVG_CALL_DURATION" DOUBLE,
"AVG_NUMBER_CALLS_RCV_DAY" DOUBLE,
"AVG_NUMBER_CALLS_ORI_DAY" DOUBLE,
"DAY_TIME_CALLS" DOUBLE,
"WEEK_DAY_CALLS" DOUBLE,
"CALLS_TO_MOBILE" DOUBLE,
"SMS_RCV_DAY" DOUBLE,
"SMS_ORI_DAY" DOUBLE,
primary key("ID")
);

/* tipo que se usará como parámetro de salida
que contendrá los centros de cada cluster */
DROP TYPE PAL_KMEANS_CENTERS_TELCO;
CREATE TYPE PAL_KMEANS_CENTERS_TELCO AS TABLE(
"CENTER_ID" INT,
"V000" DOUBLE,
"V001" DOUBLE,
"V002" DOUBLE,
"V003" DOUBLE,
"V004" DOUBLE,
"V005" DOUBLE,
"V006" DOUBLE,
"V007" DOUBLE
);

/* tipo que se usará para especificar
los diferentes parámetros para ejecutar el algoritmo k-means */
DROP TYPE PAL_CONTROL_TELCO;
CREATE TYPE PAL_CONTROL_TELCO AS TABLE(
"NAME" VARCHAR (50),
"INTARGS" INTEGER,
"DOUBLEARGS" DOUBLE,
"STRINGARGS" VARCHAR (100)
);

/* esta tabla se usa para generar el procedimiento k-means
y apuntará el AFL Wrapper Generator a los diferentes
tipos que acabamos de crear */
DROP TABLE PDATA_TELCO;
CREATE COLUMN TABLE PDATA_TELCO(
"ID" INT,
"TYPENAME" VARCHAR(100),
"DIRECTION" VARCHAR(100) );

/* llenar la tabla */
INSERT INTO PDATA_TELCO VALUES (1, '_SYS_AFL.PAL_KMEANS_DATA_TELCO', 'in');
INSERT INTO PDATA_TELCO VALUES (2, '_SYS_AFL.PAL_CONTROL_TELCO', 'in');
INSERT INTO PDATA_TELCO VALUES (3, '_SYS_AFL.PAL_KMEANS_RESASSIGN_TELCO', 'out');
INSERT INTO PDATA_TELCO VALUES (4, '_SYS_AFL.PAL_KMEANS_CENTERS_TELCO', 'out');

/* crear el procedimiento que ejecuta el algoritmo k-means */
call SYSTEM.afl_wrapper_generator('PAL_KMEANS_TELCO', 'AFLPAL', 'KMEANS', PDATA_TELCO);

Después de ejecutar este fragmento de código, deberíamos ver en el schema _SYS_AFL un nuevo procedimiento llamado PAL_KMEANS_TELCO.

4.png

Ejecutar el procedimiento k-means

Generé el procedimiento k-means, así que ahora necesito escribir el código que lo ejecutará:

/* esta tabla contendrá los parámetros que se usarán
durante la ejecución del procedimiento k-means:
por ejemplo, el número de clusters que quiera usar */
DROP TABLE PAL_CONTROL_TAB_TELCO;
CREATE COLUMN TABLE PAL_CONTROL_TAB_TELCO(
"NAME" VARCHAR (50),
"INTARGS" INTEGER,
"DOUBLEARGS" DOUBLE,
"STRINGARGS" VARCHAR (100)
);

/* llenar la tabla de parámetros */
INSERT INTO PAL_CONTROL_TAB_TELCO VALUES ('THREAD_NUMBER',2,null,null); --> número de threads a usar durante la ejecución
INSERT INTO PAL_CONTROL_TAB_TELCO VALUES ('GROUP_NUMBER',3,null,null); --> número de clusters
INSERT INTO PAL_CONTROL_TAB_TELCO VALUES ('INIT_TYPE',4,null,null); --> este parámetro especificará la manera de seleccionar el centro inicial de cada cluster
INSERT INTO PAL_CONTROL_TAB_TELCO VALUES ('DISTANCE_LEVEL',2,null,null); --> cuál distancia utilizar; en este caso, voy a usar la euclideana
INSERT INTO PAL_CONTROL_TAB_TELCO VALUES ('MAX_ITERATION',100,null,null); --> número máximo de iteraciones
INSERT INTO PAL_CONTROL_TAB_TELCO VALUES ('EXIT_THRESHOLD',null,0.000001,null); --> valor del umbral para salir de una iteración
INSERT INTO PAL_CONTROL_TAB_TELCO VALUES ('NORMALIZATION',0,null,null); --> cómo normalizar los datos; en este caso, no estoy normalizando nada

/* esta tabla contendrá el cluster resultante
con la asignación de cada cliente y la distancia al centro del cluster */
DROP TABLE PAL_KMEANS_RESASSIGN_TAB_TELCO;
CREATE COLUMN TABLE PAL_KMEANS_RESASSIGN_TAB_TELCO(
"ID" INT,
"CENTER_ASSIGN" INT,
"DISTANCE" DOUBLE,
primary key("ID")
);

/* esta tabla contendrá los centros resultantes para cada cluster */
DROP TABLE PAL_KMEANS_CENTERS_TAB_TELCO;
CREATE COLUMN TABLE PAL_KMEANS_CENTERS_TAB_TELCO(
"CENTER_ID" INT,
"V000" DOUBLE,
"V001" DOUBLE,
"V002" DOUBLE,
"V003" DOUBLE,
"V004" DOUBLE,
"V005" DOUBLE,
"V006" DOUBLE,
"V007" DOUBLE
);

/* ejecutar el procedimiento k-means */
CALL PAL_KMEANS_TELCO(TELCO, PAL_CONTROL_TAB_TELCO, PAL_KMEANS_RESASSIGN_TAB_TELCO, PAL_KMEANS_CENTERS_TAB_TELCO) with overview;

Fácil, ¿no?

Identificar el número correcto de clusters

Ok, ya tengo el código listo, pero me falta una parte muy importante: aún no sé qué k (cuántos clusters) necesito especificar como parámetro de entrada (bueno, lo sé porque creé los datos del ejemplo, pero supongamos que no lo supiera). Hay varias técnicas para averiguar cuántos grupos producen el mejor clustering; en este caso usaré el criterio del "codo". El criterio del "codo" es una regla aproximada que sugiere elegir un número de clusters tal que, si agregáramos un cluster, no obtendríamos nueva información. Voy a ejecutar el código de arriba especificando diferentes números de clusters, y para cada ejecución voy a medir la distancia total intra-cluster. Cuando la distancia no haya decrecido de una ejecución a la siguiente, entonces podré saber el número de grupos que debo usar. Armé el siguiente gráfico con los resultados:

5.png

Como se puede ver, la distancia decrece enormemente entre 2 y 3, y después de 3 la distancia sigue bajando pero a un ritmo mucho menos pronunciado. Entonces el "codo" está claramente en el cluster 3. Esto significa que debería usar k = 3 para ejecutar el algoritmo. Si lo pruebo, éste es el resultado:

6.png

La primera columna es el Customer ID y la segunda columna es el cluster al que ha sido asignado el cliente que tiene ese Customer ID. De modo que, según cómo los clientes usan sus teléfonos móviles, el algoritmo k-means los ha agrupado de la siguiente manera:
  • Customer ID 1 al 10 --> Cluster 2
  • Customer ID 10001 al 10010 --> Cluster 1
  • Customer ID 20001 al 20010 --> Cluster 0
Nótese que el proceso de clustering refleja exactamente los segmentos que definí en el conjunto de datos del ejemplo.

Medir la calidad

PAL nos da la posibilidad de medir la calidad del proceso de clustering mediante la función VALIDATEKMEANS. Esta función calcula la silueta de los clusters. Para cada punto, calcula la distancia promedio hacia el resto de los puntos del mismo cluster (lo cual constituye la llamada "diferencia promedio"). Luego calcula la diferencia promedio de cada punto respecto de todos los clusters de los cuales ese punto no es miembro. El cluster con la menor diferencia promedio se denomina "cluster vecino", porque es (después del cluster al que ha sido asignado el cliente) aquel que mejor corresponde al punto en cuestión. La distancia promedio al resto de los miembros de su propio cluster luego se compara con la distancia promedio a los miembros del cluster vecino. El valor resultante se denomina puntaje de silueta. El puntaje de silueta puede ir de -1 a 1. Un valor negativo significa que el registro es más similar a los registros de su cluster vecino que a los miembros de su propio cluster. Un puntaje cercano a 0 significa que el registro está en el borde entre clusters. Un puntaje cercano a 1 significa que el registro ha sido agrupado de manera apropiada. La silueta del conjunto de datos entero es el promedio de los puntajes de silueta de todos los registros individuales. Así que si este número es cercano a 1, significa que hemos usado el número correcto de clusters. Primero necesitamos generar, mediante el AFL Wrapper Generator, el procedimiento de validación, tal como hicimos antes para el procedimiento de clustering:

SET SCHEMA _SYS_AFL;

/* este tipo se usa como parámetro de entrada de la función PAL
que contiene la información agrupada en clusters */
DROP TYPE T_KMEANS_DATA_TELCO_S;
CREATE TYPE T_KMEANS_DATA_TELCO_S AS TABLE(
"ID" INT,
"AVG_CALL_DURATION" DOUBLE,
"AVG_NUMBER_CALLS_RCV_DAY" DOUBLE,
"AVG_NUMBER_CALLS_ORI_DAY" DOUBLE,
"DAY_TIME_CALLS" DOUBLE,
"WEEK_DAY_CALLS" DOUBLE,
"CALLS_TO_MOBILE" DOUBLE,
"SMS_RCV_DAY" DOUBLE,
"SMS_ORI_DAY" DOUBLE,
primary key("ID")
);

/* este tipo se usa como parámetro de entrada
de la tabla que contiene el resultado del proceso de clustering */
DROP TYPE T_KMEANS_TYPE_ASSIGN_TELCO_S;
CREATE TYPE T_KMEANS_TYPE_ASSIGN_TELCO_S AS TABLE(
"ID" INTEGER,
"TYPE_ASSIGN" INTEGER
);

/* éste es el tipo del parámetro de salida que
mostrará el puntaje de silueta para el conjunto de datos entero */
DROP TYPE T_KMEANS_RESULT_TELCO_S;
CREATE TYPE T_KMEANS_RESULT_TELCO_S AS TABLE(
"NAME" VARCHAR (50),
"S" DOUBLE
);

/* éste es el tipo de la tabla que contiene los parámetros de entrada y salida */
DROP TYPE CONTROL_T_TELCO_S;
CREATE TYPE CONTROL_T_TELCO_S AS TABLE(
"Name" VARCHAR(100),
"intArgs" INTEGER,
"doubleArgs" DOUBLE,
"strArgs" VARCHAR(100));

/* ésta es la tabla que contiene las tablas de entrada y salida */
DROP table PDATA_TELCO_S;
CREATE column table PDATA_TELCO_S(
"ID" INTEGER,
"TYPENAME" VARCHAR(100),
"DIRECTION" VARCHAR(100));

insert into PDATA_TELCO_S values (1,'_SYS_AFL.T_KMEANS_DATA_TELCO_S','in');
insert into PDATA_TELCO_S values (2,'_SYS_AFL.T_KMEANS_TYPE_ASSIGN_TELCO_S','in');
insert into PDATA_TELCO_S values (3,'_SYS_AFL.CONTROL_T_TELCO_S','in');
insert into PDATA_TELCO_S values (4,'_SYS_AFL.T_KMEANS_RESULT_TELCO_S','out');

/* generar la función PAL llamando al AFL Wrapper Generator */
call SYSTEM.afl_wrapper_generator('ValidateTelcoKM','AFLPAL','VALIDATEKMEANS',PDATA_TELCO_S);

Ahora deberíamos tener en el schema _SYS_AFL un procedimiento llamado ValidateTelcoKM:

7.png

El paso siguiente es escribir código que ejecute el procedimiento de validación:

/* ésta es la tabla que contiene los parámetros de entrada */
DROP TABLE #CONTROL_TAB_TELCO_S;
CREATE LOCAL TEMPORARY COLUMN TABLE #CONTROL_TAB_TELCO_S (
"Name" VARCHAR(100),
"intArgs" INT,
"doubleArgs" DOUBLE,
"strArgs" VARCHAR(100));

/* llenar la tabla de parámetros */
INSERT INTO #CONTROL_TAB_TELCO_S VALUES ('VARIABLE_NUM', 8, null, null); --> número de atributos usados para hacer la segmentación
INSERT INTO #CONTROL_TAB_TELCO_S VALUES ('THREAD_NUMBER', 2, null, null); --> número de threads a usar durante la ejecución

/* esta vista muestra el resultado del proceso de clustering */
DROP VIEW V_KMEANS_TYPE_ASSIGN_TELCO_S;
CREATE VIEW V_KMEANS_TYPE_ASSIGN_TELCO_S AS
SELECT "ID", "CENTER_ASSIGN" AS "TYPE_ASSIGN" FROM PAL_KMEANS_RESASSIGN_TAB_TELCO;

/* esta tabla contendrá el puntaje de silueta del conjunto de datos entero */
DROP TABLE KMEANS_SVALUE_TAB_TELCO_S;
CREATE COLUMN TABLE KMEANS_SVALUE_TAB_TELCO_S (
"NAME" VARCHAR (50),
"S" DOUBLE
);

/* llamar al procedimiento de validación de k-means */
CALL ValidateTelcoKM(LSPARVIERI.TELCO, V_KMEANS_TYPE_ASSIGN_TELCO_S, "#CONTROL_TAB_TELCO_S", KMEANS_SVALUE_TAB_TELCO_S) with overview;

/* mostrar los resultados */
SELECT * FROM KMEANS_SVALUE_TAB_TELCO_S;

El puntaje de silueta resultante para mi proceso de clustering es:
8.png

Como este valor es mayor que 0 y cercano a 1, esto significa que hemos usado el número correcto para el parámetro k cuando ejecutamos el proceso de clustering.

¡Espero que les haya gustado!

Síganme en Twitter: @LukiSpa


Version Original:http://scn.sap.com/community/developer-center/hana/blog/2013/03/28/sap-hana-pal-k-means-algorithm-or-how-to-do-customer-segmentation-for-the-telecommunications-industry

No hay comentarios:

Publicar un comentario