PDF de programación - Un método de optimización lineal entera para el análisis de sesiones de usuarios web

Revista Ingeniería de Sistemas

Volumen XXIII, Septiembre 2009

Un método de optimización lineal entera
para el análisis de sesiones de usuarios

web.

Resumen

Pablo E. Román*
Juan D. Velásquez*
Robert F. Dell**

“Web usage mining” es una nueva área de investigación que ha pro-
ducido importantes avances en la industria del e-Business, mediante la
entrega de patrones de comportamiento de compra y sugerencias de na-
vegación que mejoran la experiencia del usuario web en el sitio. Una de
las principales fuentes de datos usadas en web mining, son las sesiones
(secuencias de páginas) de los usuarios web que deben ser reconstruidas
a partir de los archivos de Log. El problema con los archivos de Logs es
que incluyen una componente de ruido al no identificar explícitamente a
los usuarios que generan los registros. Con este trabajo, se desarrolla una
aplicación basada en modelos de optimización como el como el problema
de “maximum cardinality matching” y programación entera, que compa-
ramos con una heurística comúnmente usada. Se analizan variaciones de
los modelos de optimización presentados para explorar la verosimilitud
de sesiones específicas y características de las sesiones. Se obtiene como
resultado sesiones de mejor calidad que las obtenidas con los métodos
tradicionales, además de una metodología de análisis de ellas.

Palabras Clave: Web Usage Mining, Web User Session, Maximum Cardinality
Matching, Network Flow Model, Integer Programming, Web Logs.

*Departamento Ingeniería Industrial, Universidad de Chile, Santiago, Chile
**Operations Research Department, Naval Postgraduate School, Monterey, California,

USA

109

P. Román, J. D. Velásquez, R. Dell

Análisis de sesiones de usuarios Web

1.

Introducción

Los archivos de Log de un servidor web contienen registros de las operaciones
que realizan los usuarios al navegar por un sitio web, convirtiéndose en una
potencial gran fuente de datos acerca de sus preferencias [23]. Un Log [2] es
un gran archivo de texto donde cada línea (registro) contiene los siguientes
campos: Tiempo de acceso al objeto web (Ej. página web), la dirección IP del
usuario, el agente que es la identificación del navegador usado, y el objeto web.
También contiene evidencia de las actividades de de los usuarios web y se le
puede considerar como una gran encuesta sobre sus preferencias en relación a
la información que aparece en el sitio web. Lo anterior ha motivado gran parte
de la investigación que se realiza en web mining, y define un nuevo campo de
investigación denominado Web Usage Mining [23].

Un archivo de Log por si mismo no necesariamente refleja las secuencias
de páginas que acceden los usuarios web i.e., se registra cada acceso pero sin
un único identificador que represente al cliente. Esto se debe a que muchos
usuarios distintos pueden compartir la misma dirección IP y tipo de nave-
gador (agente), generando la necesidad de reconstruir las sesiones de usuario
usando los datos disponibles. En la actualidad se utilizan métodos heurísticos
para reconstruir las sesiones desde los archivos de Logs, las que se basan prin-
cipalmente en limitar la duración de las sesiones [3], [6] y [20]. Este trabajo
se centra en proponer modelos de optimización para recuperar las sesiones y
estudiar sus propiedades.

El presente artículo se organiza de la siguiente manera: La sección 2 re-
sume el estado del arte en relación a la sesionización. La sección 3 presenta
nuestro modelo de optimización. La sección 4 muestra variaciones del modelo
de optimización para explorar la verosimilitud y propiedades específicas de
las sesiones. La sección 5 describe los datos experimentales usados. La sección
6 presenta los resultados. La sección 7 concluye el trabajo y sugiere futuras
investigaciones.

2. Estado del Arte

Las estrategias de sesionización, pueden ser clasificadas en reactivas y proac-
tivas [20]. La sesionización proactiva captura todas las actividades realizadas
por los usuarios durante su visita al sitio web, sin embargo, son invasivas y
en general con poco resguardo a la privacidad de los usuarios. El uso de estas
estrategias se encuentra regulado por ley en algunos países [20] de forma de
proteger la privacidad de las personas [15]. Un ejemplo corresponde al uso

110

Revista Ingeniería de Sistemas

Volumen XXIII, Septiembre 2009

de cookie1 [4] que registran las actividades del cliente de las cuales se puede
extraer la sesión exacta del usuario. Otra técnica usada es la re-escritura de
URL2 [7], donde se incluye información en el URL que se envía al servidor que
reconstruye la sesión. La forma mas invasiva de obtener sesiones es a través
de los llamados Spyware, que son programas que registran cualquier actividad
del usuario (Teclado, Mouse, etc.). Sin embargo son actualmente considerados
como una actividad criminal en la mayoría de los países [16].

Las estrategias de sesionización reactivas tienen un alto nivel de resguardo
a la privacidad de los usuarios ya que sólo usan los registros de Log y no
manejan explícitamente los datos personales de los usuarios [20]. Sin embargo,
los archivos de Log son una forma aproximada de obtener las sesiones por
muchas razones. Los usuarios pueden tener el mismo IP debido a que los ISP
comparten un limitado número de direcciones entre sus clientes. Los usuarios
web pueden también hacer uso de los botones back y forward que en la mayoría
de las veces no producen registros en los Logs del servidor. Otro factor que
introduce ruido en los datos son los servidores Proxy3 [9] que mantienen en
cache un cierto numero de páginas frecuentemente visitadas para optimizar
las velocidades de acceso, por lo cual nunca son registrados en los archivos de
los del sitio web.

Los métodos que se manejan en la actualidad para reconstruir sesiones des-
de los archivos de Logs están basados en heurísticas que consideran un límite
de tiempo para la duración de las sesiones (30 minutos) [20]. Otras heurísticas
se basan en la estructura semántica del sitio y las sesiones se construyen de
forma de seguir una semántica común [13].

(nα/

Se han realizados estudios empíricos en relación al comportamiento es-
tadístico de las sesiones. La función de probabilidad de distribución del largo
n (número de saltos entre páginas) tiene un buen ajuste con un ley de potencia
k kα) [10][22]. La distribución parece ajustarse a una variedad de sitios
web, aunque con cambio en el parámetro α. Nosotros usamos esta propiedad
que parece universal de las sesiones como una medida de calidad de éstas [18].
Existe una gran variedad de literatura para el minado de las sesiones una
vez que estas han sido identificadas. Técnicas como análisis estadístico, reglas
de asociación, clustering, clasificación, patrones secuenciales y modelamiento
de dependencias han sido usados para descubrir patrones de comportamiento
de usuarios web [12][14][21].

1Archivos que se almacenan en el computador del cliente que almacenan datos
2Dirección web de la página, e.g. http://www.dii.uchile.cl
3Servidor que almacena copias de páginas mas acezadas por los usuarios de una red, de

forma distribuirlas en forma más rápida.

111

P. Román, J. D. Velásquez, R. Dell

Análisis de sesiones de usuarios Web

3. Modelos de optimización para la sesionización

Se presentan dos modelos de optimización para la sesionización, los cuales
agrupan registros de Logs de un mismo IP y agente, así como también con-
sideran la estructura de links del sitio web. A diferencia de la heurística, que
construye las sesiones una por una, los algoritmos de optimización propues-
tos construyen en forma simultánea. Cada sesión así construida es una lista
de registros de Logs, donde cada registro es usado una sola vez en una única
sesión. En la misma sesión, un registro r1 puede ser un predecesor inmediato
de r2 si: los dos registros poseen la misma IP y agente, un link existe desde la
página asociada al registro r1 hasta la página del registro r2, y el registro r2
se encuentra en una ventana de tiempo permitida según el registro r1.

3.1. Bipartite Cardinality Matching

El primer modelo de optimización que presentamos está basado en el co-
nocido problema “Bipartite Cardinality Matching” (BCM) (e.g. [1]), el cual
consiste en encontrar en un grafo no dirigido el subconjunto de máxima cardi-
nalidad que tenga la propiedad de “matching” (no hay 2 vértices que compar-
tan la misma arista). Existen varios algoritmos especializados para resolver
√
el problema BCM en un tiempo de computación O (
nm) donde “n” es el
número de vértices y “m” es el número de arcos (e.g. [1]). En nuestra red, ca-
da registro es representado por dos nodos, unos que representan el predecesor
inmediato y otros a los sucesores inmediatos. La figura 1 muestra un ejemplo
con 6 registros.

Figura 1: BCM: Cada registro es representado por dos nodos. Un arco existe
si un nodo puede ser predecesor (from) de un vértice que puede ser su sucesor,
según las restricciones del problema.

112

Revista Ingeniería de Sistemas

Volumen XXIII, Septiembre 2009

En cada lado, se ordenan los nodos (registros) en orden creciente de tiempo
de acceso en los Logs del servidor web. Un arco existe de un nodo r1 (from)
a un nodo r2 (to) si el registro correspondiente a r1 puede ser un inmediato
predecesor de r2. Para el caso de la figura 1 asumimos que existen siete arcos.
Dada una solución, se construyen las sesiones de acuerdo al “matching”
encontrado. Un vértice que no es sucesor de otro vértice, es el primer registro
de la sesión. El resto de la secuencia de registros se reconstruye identificando
los pares de vértices que corresponden a un mismo registro y siguiendo con-
secutivamente los sucesores habilitados por un arco. La figura 2 provee una
solución factible de acuerdo a la figura 1. Los vértices 4 y 6 son los últimos en
una sesión (no tienen sucesores), los vértices 1