Mundo-Contact
Agrupamiento de usuarios de Internet según los patrones de acceso
Yongjian Fu*
Resumen
Se estudia el agrupamiento de usuarios de la red basado en sus patrones de acceso. Los patrones de acceso de los usuarios de la Red se extraen de los archivos de visitantes de los servidores de la Red, y después se organizan en sesiones que representan episodios de interacción entre los usuarios de la Red y el servidor. Al emplear la iniciación mediante atributos, las sesiones se generalizan, pues dependiendo de la jerarquía de página que organiza las páginas dependiendo de sus generalidades. Por último, las sesiones generalizadas se agrupan utilizando un método de agrupamiento jerárquico. Nuestros experimentos en un amplio conjunto de datos reales muestran que el método es eficiente y práctico para las aplicaciones de explotación de la Red.
1. Introducción
Debido al rápido desarrollo de la World Wide Web (WWW), o simplemente la Red, muchas organizaciones introducen ahora su información en ell y proporcionan servicios tales como la compra on-line, respuesta del usuario, soporte técnico, etc. La explotación de la Red, y el descubrimiento del conocimiento, se ha convertido en un importante campo de investigación.
Un asunto importante dentro de la explotación del uso de la Red es el agrupamiento de sus usuarios según sus características comunes. Analizando las características de los grupos, los administradores de sitios Web pueden comprender mejor a los usuarios y proporcionarles servicios más adecuados y personalizados.
En este artículo se estudia el agrupamiento de los usuarios de la Red basado en sus actividades de navegación o patrones de acceso. Los usuarios con actividades de navegación son agrupados o reunidos en clases (grupos). Por ejemplo, si un número de clientes emplea mucho tiempo en navegar por páginas sobre "artículos de bebé", "juguetes de bebé" y "pañales", pueden incluirse en un grupo que más tarde será analizado por administradores de sitios Web o expertos de ese campo como "supuestos padres". Entonces, el administrador de sitios Web puede, por ejemplo, organizar las páginas de la Red para que las páginas anteriormente mencionadas se interrelacionen. También, cuando un usuario ha navegado por las páginas de "artículos de bebé" y "juguetes de bebé", un enlace con la página "pañales" puede crearse de forma dinámica e insertarse en la página actual.
En primer lugar los datos del archivo de visitantes del servidor se procesan para identificar las sesiones de los usos de la Red. Básicamente, una sesión es una unidad de interacción entre el usuario y el servidor de la Red. Entonces, las sesiones se generalizan utilizando el método de iniciación mediante atributos que reducirá en gran medida la dimensión de los datos. Por último, los datos generalizados se agrupan utilizando el BIRCH [10], un algoritmo eficiente de agrupamiento jerárquico. La solicitud se comprueba en un conjunto de amplios datos reales. Nuestros experimentos muestran que el método es eficiente y hemos encontrado varios grupos interesantes dentro del conjunto de datos.
2. Antecedentes
Estudios anteriores sobre los usos de la Red, tales como las estadísticas de acceso, carecen de la comprensión en profundidad de los patrones de navegación del usuario, incluidas las páginas visitadas y el tiempo empleado en cada una. Estos patrones de navegación del usuario proporcionan información precisa, activa y objetiva sobre los usos de la Red por parte de los usuarios. Además, la mayoría de servidores, p. ej. el HTTPD de NCSA [3] y el IIS de Microsoft [5], contienen tal información en su archivo de visitantes de solicitud de páginas.
Un archivo de visitantes de un servidor de Red contendrá los registros de los accesos del usuario. Cada registro representa una petición de página de un usuario de la Red (denominado cliente). Un registro típico contiene la dirección IP del cliente, la fecha y la hora en la que se recibe la petición, el URL de la página pedida, el protocolo de la petición, el código de regreso del servidor indicando el estado del tratamiento de la petición y el tamaño de la página si se acepta dicha petición. Se da un ejemplo más abajo, tomado del sistema del servidor de la Red de la Universidad de Missouri-Rolla (UMR) que ejecuta HTTPD 1.0. Las direcciones IP se han modificado por razones de privacidad. Los URL de las páginas están relacionados con la dirección de la página principal de la UMR: http://www.umr.edu.
smith.cs.umr.edu – – [01/Apr/1997:00:03:24 -06000]
"GET / ~amigos/Virtual1/cosas2.html HTTP/1.0"200 11746
Desde tal archivo de visitantes del servidor de la Red se pueden extraer los patrones de acceso del usuario. Un patrón de acceso del usuario está formado por las páginas visitadas y el tiempo empleado en cada una. Así pues, cada usuario puede representarse mediante un conjunto de parejas(página-id, tiempo).
Recientemente se ha propuesto un algoritmo de agrupamiento: Balanced Iterative Reducing and Clustering using Hierarchies (BIRCH) [10]. Por lo general, se crea un buen agrupamiento en una pantalla solamente del conjunto de datos por lo que se amplía considerablemente un vasto conjunto de datos. Además, BIRCH es un algoritmo jerárquico y capaz de aumentar lo que es conveniente para nuestro propósito. Sin embargo, la aplicación directa de BIRCH en los primeros datos de acceso del usuario tal y como se ha descrito anteriormente es muy poco eficiente y no puede encontrar grupos interesantes como los explicados más abajo.
Normalmente, un servidor de la Red contiene miles, millones de páginas. Obviamente, es poco práctico representar a cada usuario como un vector dimensional alto en el que cada dimensión representa una página. La representación escasa provocará que la dimensión de grupos cambie de forma dinámica, es decir, los elementos que no sean escasos en el centro de un grupo pueden aumentar al añadirse nuevos vectores. Esto implica un gran gasto de memoria y de gestión de almacenamiento además de en el manejo de la estructura de datos.
Nuestro objetivo es agrupar a usuarios de la Red con patrones de acceso similares. Sin embargo, no es fácil encontrar muchos usuarios que accedan a páginas comunes debido a la diversidad de usuarios de la Red. Esto tampoco conducirá a otros grupos pequeños o grupos de usuarios con algo de frecuencia. Es más probable que podamos encontrar grupos que compartan los intereses comunes en los temas de las páginas. Por ejemplo, no podemos encontrar un gran número de usuarios que visiten las páginas "Oklahoma Homer Smith Mavado cuna con acabado en blanco", "Móviles Musicales para Niños II que comienzan con luz" y "12-unidades de pañales Arco Iris de algodón", pero probablemente encontremos muchos usuarios que naveguen por las páginas "artículos de bebé", "juguetes de bebé" y "pañales".
Basándonos en las observaciones anteriores, proponemos una solicitud de agrupamiento basado en la generalización que combine la iniciación mediante atributos [4] y el BIRCH para generar un agrupamiento jerárquico de usuarios de la Red basado en sus patrones de acceso.
3. Identificación de la sesión
Un usuario puede visitar un sitio Web de vez en cuando y emplear arbitrariamente un espacio de tiempo entre las visitas consecutivas. Para dar con la imprevisible naturaleza de la navegación por la Red y disminuir el problema, se introduce el concepto de sesión: la unidad de interacción entre un usuario y un servidor de la Red. Una sesión está formada por las páginas a las que accede un usuario en un determinado espacio de tiempo. Los grupos se encuentran en las sesiones en vez de los listados completos de los usuarios. Puede justificarse el hecho de que agrupemos a las sesiones en vez de a los usuarios ya que nuestro objetivo es comprender el uso de la Red y las diferentes sesiones de un usuario que pueden corresponder a las visitas del usuario con diferentes propósitos en mente. Además, varios usuarios de un mismo ordenador pueden ser representados mediante diferentes sesiones. En el presente artículo, emplearemos los términos de sesión y de usuario de manera intercambiable.
Figura 1 – Un ejemplo de jerarquía de página
Las sesiones se identifican mediante el agrupamiento de páginas consecutivas pedidas todas ellas por el mismo usuario. Los datos en un archivo de visitantes del servidor de la Red se transforman en un conjunto de sesiones con la forma de (sesión-id, {}, en la que sesión-id y página-id son únicas. Los ID designan a las sesiones y a las páginas. Una sesión (sid0, p0, 10,.p1, 30, p2, 20) nos indica que un usuario emplea 10 segundos en la página p0, 30 segundos en la página p1 y 20 segundos en la página p2.
Se explora el archivo de visitantes de los servidores de la Red para identificar las sesiones. Cuando una nueva dirección IP se introduce en el archivo de visitantes se crea una sesión. Las peticiones posteriores desde las direcciones IP se añaden a su sesión siempre que la elipsis de tiempo entre peticiones consecutivas no supere un parámetro predefinido tiempo_máximo_parado. Si no, la sesión en curso se cierra y se crea una nueva.
4. Agrupamiento de Sesiones basado en la Generalización
Como se dijo en el Apartado 3, una sesión se representa como un vector del tiempo empleado en las páginas; así como que una representación funciona correctamente cuando el número de páginas es pequeño. Sin embargo, cuando existe un gran número de páginas, tal delicada granulación provoca el deterioro en la calidad de los grupos así como de la eficiencia del algoritmo de agrupamiento. Además, agrupar consiste en localizar grupos con patrones de acceso similares, lo que no se corresponde necesariamente con el nivel de página. Los grupos que no son obvios en el nivel de página pueden aparecer al ser considerados en una página superior.
Al analizar las páginas, nos dimos cuenta de que éstas no estaban distribuidas al azar, sino que estaban organizadas en una estructura jerárquica denominada jerarquía de página. Una jerarquía de página es un orden parcial de las páginas Web en el que un nodo con hojas representa una página Web correspondiente a un fichero en el servidor. Un nodo sin hojas en una jerarquía de página representa una página Web correspondiente a un directorio en el servidor. Un enlace entre el nodo madre y el nodo hijo representa la coherencia de la relación entre las páginas correspondientes. Para distinguir estos dos tipos de páginas, una página representada por un nodo con hojas se denomina página simple; mientras que una página representada por un nodo sin hojas, una página general. Por ejemplo, una jerarquía de página para algunas páginas en el servidor UMR de la Red se muestra en la Figura 1 que tiene cuatro páginas simples y tres páginas generales.
La jerarquía de página puede crearse de forma automática basándose en los URL de las páginas. Por ejemplo, la jerarquía de página en la Figura 1 puede construirse desde las cuatro páginas simples (los nombres mnemotécnicos de las páginas generales son opcionales). La raíz de la jerarquía que es la página principal de la UMR no se muestra en la Figura uno para simplificar.
http://www.umr.edu/~regwww/ugcr97/ee.html
http://www.umr.edu/~regwww/ugcr97/em.html
http://www.umr.edu/~regwww/graduatecat/ee.html
http://www.umr.edu/~regwww/graduatecat/em.html
Las sesiones encontradas en el Apartado 3 se generalizan utilizando el método de iniciación mediante atributos, la página simple es reemplazada en cada sesión por su página general correspondiente basada en la jerarquía de página. Entonces, los duplicados se borran junto con su tiempo añadido.
La generalización de las sesiones conlleva dos pasos: la construcción de la jerarquía de página y la iniciación mediante atributos de las sesiones que se explican a continuación.
• La construcción de la jerarquía de la página. Una jerarquía de página se inicia con tan solo la raíz que representa la página principal del servidor de la Red. Para cada URL en la tabla URL realizada en el apartado 3 se crea un nodo para la página, si no existía anteriormente en la jerarquía de página. A continuación, el URL es analizado sintácticamente y para cada prefijo que es un URL legal se crea un nodo para la página general si no existía en la jerarquía de página. Se añade un enlace para cada pareja de nodos en el que un URL es un prefijo más próximo al otro. Por ejemplo para el URL http://www.umr.edu/~regwww/ugcr97/ee.html pueden crearse los nodos para él desde su primer prefijo :http://www.umr.edu/~regwww/ugcr97/ y su segundo prefijo http://www.umr.edu/~regwww/ y se añade un enlace entre él mismo y su primer prefijo, entre su primer prefijo y su segundo prefijo y entre su segundo prefijo y la raíz.
• La iniciación mediante atributos de las sesiones. Para cada sesión encontrada en el Apartado 3 se sustituyen sus páginas por sus páginas generales correspondientes en la jerarquía de página denominada árbol ascendente en la iniciación mediante atributos. El nivel de las páginas generales para ascender lo decide el usuario o es inferido desde el umbral de un usuario dado que especifica el número máximo de páginas generales en resultados. Si dos páginas durante una sesión tienen la misma página general de nivel más alto, se extrae una de ellas y su tiempo se añade a las demás. La sesión comienza a generalizarse y se denomina sesión generalizada a una sesión así obtenida. Por ejemplo, para una sesión de páginas simples en la Figura 1, (Cursos de Ingeniería Eléctrica para Universitarios, 25), ( Cursos de Ingeniería Mecánica para Universitarios, 48), (Cursos de Ingeniería Eléctrica para Postgraduados, 32), (Cursos de Ingeniería Mecánica para Postgraduados, 19), el método de iniciación mediante atributos la generalizará para una sesión generalizada (Cursos para Universitarios, 78), (Cursos para Postgraduados, 51) en el nivel 2.
Ya que el número de la página general es mucho menor que el de las páginas simples, la generalización de la sesión disminuye mucho la dimensión. Como resultado, una sesión generalizada puede representarse entonces como un vector regular (sesión-id, t1, t2…, tn) en el que t1 es el tiempo total que el usuario emplea en la página general i-th y sus descendientes. Fíjese que los ID de la página de estas páginas generales no están incluidos en el vector ya que toda sesión se encuentra en el mismo conjunto de páginas generales.
Otra ventaja de la generalización de las sesiones utilizando la jerarquía de página es que la representación de los datos resultantes puede albergar las actualizaciones de las páginas Web, así como la suma y supresión de páginas siempre que la estructura del nivel superior sea estable.
Las sesiones generalizadas se agrupan utilizando el algoritmo BIRCH [10]. BIRCH elabora un árbol de Características de Agrupamiento [Clustering Feature: CF] como resultado del agrupamiento mediante los objetos insertados de forma incrementada (representados por vectores) en el árbol CF. Un árbol CF es una estructura multidimensional como B+ árbol en el que un nodo sin hojas almacena las entradas de (CF1, indicador_del_hijo_i) y un nodo con hojas guarda las entradas de (CF1), en el que CF1 es un vector CF. Un vector CF es un triple que contiene el número, la suma lineal y la cuadrada de los vectores en el subárbol procedente de un hijo.
Cuando se inserta un nuevo vector en el árbol CF, éste desciende desde la raíz hasta un nodo con hojas al elegir el hijo más próximo dependiendo de la cantidad de distancia, como la distancia euclidiana. Si ninguna entrada del nodo con hojas puede incorporarse al objeto nuevo sin un límite T de diámetro, se actualiza dicho vector CF de entrada. Por lo demás, el objeto se introduce en una entrada vacía en el nodo con hojas. En este último caso, si no existe una entrada vacía, se deja en el nodo con hoja y este es dividido en dos. En el caso de que haya una división, una entrada vacía en el nodo madre se utiliza para registrar al nuevo nodo con hojas. El nodo madre se divide de forma parecida si no hay una entrada vacía y asciende hacia la raíz, el árbol está en un nivel más profundo. Cuando el árbol aumenta demasiado como para ser guardado en la memoria, el límite T aumenta y el árbol en curso se convierte en un nuevo árbol al insertar las entradas de nodos con hojas en el árbol en curso dentro del nuevo árbol que se garantiza que es más pequeño.
5. Experimentos
Los algoritmos han sido implementados y probados en un conjunto de datos recogidos del archivo de visitantes del servidor de la Red de la UMR (http://www.umr.edu). Contiene más de 2 millones y medio de registros con un tamaño total de 270MB. Los experimentos han sido realizados en una Sun SparcStation Ultra 1 con una memoria de 64MB ejecutando Solaris 2.5.
Probamos los algoritmos en varios grupos de pruebas que son subconjuntos del conjunto de datos que contiene desde 50.000 hasta 500.000 registros. El tiempo_máximo_parado se fija en 30 minutos. El número de sesiones identificadas en los grupos de pruebas se muestra en la Tabla 1, que también muestra el número de páginas diferentes y el número de hosts distintos en los grupos de pruebas. A partir de la figura, queda demostrado que el número de sesiones es lineal respecto del número de registros en los grupos de prueba.
Tabla 1 – Número de sesiones en los equipos de prueba
Grupo de prueba archivos páginas distintas hosts distintos sesiones
50k 50.000 5.731 3.694 18.184
100K 100.000 8.168 6.304 35.665
200K 200.000 12.191 11.473 70.702
300K 300.000 15.201 16.498 107.322
400K 400.000 17.574 21.153 142.457
500K 500.000 21.308 26.107 178.655
Entonces las sesiones se generalizan al nivel 2 que es el nivel inmediatamente inferior a la raíz. Lo elegimos así para ver el efecto de una iniciación mediante atributos en una reducción de la dimensión. Las sesiones generalizadas tienen una dimensión de 1.628 excepto en el caso del grupo de pruebas de 50K que es de 1.194. Fundamentalmente, la generalización redujo ampliamente la dimensión, dos tercios en el grupo de prueba de 50K y nueve décimas partes en el grupo de prueba de 500K.
También encontramos que el tiempo total de ejecución en la identificación de la sesión y la generalización de la sesión es casi lineal respecto al número de registros en los grupos de pruebas.
Los agrupamientos resultantes se analizan examinando las páginas generales en el agrupamiento. La mayoría de los agrupamientos con hoja en el agrupamiento jerárquico contiene sólo unas pocas páginas generales que se consideran como de interés general para el grupo. Por ejemplo, hay un grupo interesado en las páginas Web de la secretaría de admisiones. A veces, las páginas en un agrupamiento son demasiado generales y hay que examinar las páginas simples en el conjunto de datos para evaluar la validez del agrupamiento. Por ejemplo, hay un grupo que contiene la página principal del departamento de ingeniería mecánica. Un análisis detallado revela un grupo de usuarios interesado en las páginas principales de los profesores de ingeniería mecánica.
Resumiendo, el método que proponemos en el presente artículo amplía bastante los vastos conjuntos de datos: Además, pueden encontrarse grupos significativos en las sesiones generalizadas.
6. Conclusión y Trabajo Futuro
Se ha estudiado el agrupamiento de los usuarios de la Red basado en sus patrones de acceso. Se propone un método de agrupamiento basado en la generalización que utiliza el método de iniciación mediante atributos en el agrupamiento para reducir la amplia dimensión de los datos. Nuestros experimentos en un amplio conjunto de datos reales muestra que el método es eficiente y práctico para las aplicaciones de explotación de la Red.
Durante la generalización de las sesiones, se da un nivel que determina las páginas generales que serán reemplazadas por las páginas simples. Dicho nivel desempeña un importante papel creando las sesiones generalizadas así como el agrupamiento definitivo. Si el nivel se sitúa demasiado alto, puede producirse un exceso de generalización en el que se pierdan demasiados detalles y se cuestione la validez de los grupos. Por otra parte, si el nivel se sitúa demasiado bajo, puede no reducirse mucho la dimensión. Es necesario realizar más experimentos para comprender mejor esta cuestión.
Se ha encontrado que incluso tras la iniciación mediante atributos, la dimensión de las sesiones generalizadas seguía siendo demasiado amplia. Una posible vía para solucionarlo consistiría en agrupar primero las páginas Web [9] y luego organizarlas en la jerarquía de página.
La construcción de la jerarquía de página basada en los URL de las páginas implica que la organización de la página inferior refleje la semántica de las páginas. En el caso de que no pueda adoptarse, se podría construir la jerarquía de página de acuerdo con las semánticas de las páginas, p. ej., utilizando un agrupamiento de un documento o método de categorización.
Muchos sitios Web exigen el registro de sus usuarios. Una extensión natural de nuestro método consiste en combinar la información del registro de usuario, como edad, nivel de ingresos, dirección, etc., con sus patrones de acceso en el agrupamiento.
Agradecimientos
El presente trabajo está respaldado por la Universidad de Missouri Research Board Grant R-3-42434. Damos las gracias al Dr. Tian Zhang por el código fuente de BIRCH y a Meg Brady por el grupo de datos de la prueba.
* Yongjian Fu, Kanwalpreet Sandhu, Min-Yi Shih
Departamento de Informática de la Universidad de Missouri-Roll
