Post on 13-Jan-2016
description
“Sistema de Análisis de Patrones de Navegación usando Web Mining”
IntegrantesVíctor MacasFanny Idrovo
Patricio Alcívar
Introducción Objetivo Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Introducción Objetivo Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Los miles de personas que navegan por la Web van dejando registrados todos sus accesos o visitas en archivos especiales.
El proyecto analiza el comportamiento del usuario en un sitio Web usando los conceptos Web Mining (WM).
WM genera conocimiento. El proyecto describe el proceso necesario para generar
conocimiento (patrones de navegación) Caso Real: www.sidweb.espol.edu.ec
Introducción
Qué es Web Mining?
Web Mining es el descubrimiento y análisis de información útil en la World Wide Web.
Introducción
Áreas de enfoque
Web Mining se clasifica en función de la parte de la Web que se mina, por tanto existen tres áreas o enfoques:
1. Minería del contenido de la Web
2. Minería de la estructura de la Web
3. Minería del uso de la Web
Introducción
Minería del contenido de la Web
Es el descubrimiento de información útil desde los contenidos textuales y gráficos de los documentos Web, y tiene sus orígenes en el procesamiento del lenguaje natural y en la recuperación de la información.
Introducción
Minería de la estructura de la Web
Es el proceso de descubrir el modelo subyacente a la estructura de enlaces de la Web y analiza, fundamentalmente, la topología
de los hipervínculos (con o sin descripción de los enlaces)
Introducción
Minería del uso de la Web
Es la aplicación de técnicas de minería de datos para descubrir patrones de acceso (o hábitos) desde los sitios Web. El principal objetivo es entender y servir mejor las necesidades de las aplicaciones basadas en Web.
<<Área de enfoque de la presente Tesis>>
Introducción
Problema
Los administradores o empresas que están detrás de los sitios Web no conocen la existencia de la información valiosa que se puede obtener analizando los patrones de movimiento que siguen sus usuarios dentro del sitio
Introducción
Solucion propuesta
“Sistema de análisis de patrones de navegación usando Web Mining”
Aplicacion: “MineroWeb”
Una herramienta que analiza información útil de la Web (archivos log de un servidor web) mediante el uso de técnicas de Web Mining:
Reglas de Asociacion Secuencia de Patrones Clusterizacion
Reportes estadisticos de trafico del sitio
Introducción
Introducción Objetivos Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Analizar los archivos Log de un servidor Web y así encontrar patrones de navegación de los visitantes de un sitio Web, usando técnicas de la minería de datos.
Objetivos
• Predecir la forma de navegar por el sitio (Reglas asociación)
• Predecir el posible tiempo en que los usuarios volverán a navegar por ciertas páginas (Patrones secuenciales)
• Agrupar a usuarios por la preferencia entre sus páginas (Clusterizacion)
Introducción Objetivo Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
1. In tegración y recopilación
2. Se lección , lim piezaY transform ación
D atos se leccionados(V ista m inable)
A lm acén de datos
D atos in ic ia les
- -- -
+ ++ +
3. M inería de datos
P atrones
C onocim ien to
4. Eva luación e in terpretación
5. D ifusión y uso
R esultadosR esultadosD ecis iones
Datos Iniciales
.log
Esquema básico: Minería de datos
Introducción Objetivos Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Materia prima de la Aplicacion:
Log de un servidor Web200.49.246.36 - - [01/Jan/2006:18:08:00 -0500] "GET /images/folder_icons/356.gif HTTP/1.0" 200 1447200.49.246.36 - - [01/Jan/2006:18:08:00 -0500] "GET /images/folder_icons/100.gif HTTP/1.0" 200 841200.49.246.36 - - [01/Jan/2006:18:08:00 -0500] "GET /images/lv_esquina3.gif HTTP/1.0" 200 82200.49.246.36 - - [01/Jan/2006:18:08:01 -0500] "GET /images/folder_icons/310.gif HTTP/1.0" 200 1530200.25.170.92 - - [01/Jan/2006:18:08:08 -0500] "GET /private/mycourses/website/folders/assignment/assignment_view.jsp?folderId=-2&websiteId=948 HTTP/1.1" 200 4531200.25.170.92 - - [01/Jan/2006:18:08:09 -0500] "GET /images/reply.gif HTTP/1.1" 200 154200.25.170.92 - - [01/Jan/2006:18:08:09 -0500] "GET /images/open.gif HTTP/1.1" 200 91200.25.170.92 - - [01/Jan/2006:18:08:17 -0500] "GET /private/mycourses/website/folders/link_view.jsp?folderId=19&websiteId=948 HTTP/1.1" 200 3668200.25.170.92 - - [01/Jan/2006:18:08:19 -0500] "GET /private/mycourses/website/folders/view.js HTTP/1.1" 200 406200.10.150.20 - - [01/Jan/2006:18:08:27 -0500] "GET / HTTP/1.0" 200 18223200.25.170.92 - - [01/Jan/2006:18:09:06 -0500] "GET /private/mycourses/website/folders/forums_view.jsp?folderId=20&websiteId=948 HTTP/1.1" 200 4060200.25.170.92 - - [01/Jan/2006:18:09:08 -0500] "GET /images/newdoc.gif HTTP/1.1" 200 870200.25.170.92 - - [01/Jan/2006:18:09:22 -0500] "GET /private/mycourses/website/email/index.jsp?folderId=7&websiteId=948 HTTP/1.1" 200 6978200.25.170.92 - - [01/Jan/2006:18:09:28 -0500] "GET /servlet/UserPhotoServlet?userCode=9451 HTTP/1.1" 200 6634252.113.176.247 - - [16/Feb/2006:00:06:00 -0500] "GET /images/KDnuggets_logo.gif HTTP/1.1" 200 784 "http://www.kdnuggets.com/" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; MyIE2)"
Fuente de datos
Formatos de archivo: ELF y CLF
Ejemplo: Log servidor Web
http://www.sidweb.espol.edu.ec/inicio.html
Servidor
Log servidor Web
152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET … HTTP/1.1" 200
152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /gps.html HTTP/1.1" 200
152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /inicio.html/ HTTP/1.1" 200 …
Contenido página
usuarios
Fuente de datos
Ejemplo: Una línea del Log
152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /jobs/ HTTP/1.1" 200 15140 "http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
Fuente de datos
152.152.98.11
Dirección IP del cliente que accesa
Campo: IP152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /jobs/ HTTP/1.1" 200 15140 "http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
Fuente de datos
- El nombre del usuario remoto (usualmente omitido y
reemplazado por un “-”) - Login del usuario remoto (tambien usualmente omitido y reemplazado por un “-”)
Fuente de datos
Campo: Nombre, Login152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /jobs/ HTTP/1.1" 200 15140 "http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
[16/Nov/2005:16:32:50 -0500]
Fecha: dd/mm/yyy
tiempo: Hh:mm:ss
Time Zone: (+|-)HH00 Relativo a GMT-0500 es US EST
Fuente de datos
Campo: Fecha/Tiempo/TZ152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /jobs/ HTTP/1.1" 200 15140 "http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
"GET /jobs/inicio.html/ HTTP/1.1"
Metodo: GETHEADPOST…
URL:Relativo al dominio
Protocolo HTTP:Ej:HTTP/1.0 o HTTP/1.1
Fuente de datos
Campo: Pedido152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /jobs/inicio.html HTTP/1.1" 200 15140 "http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
200 Codigo de estado (respuesta). Mas importantes son: 200 – OK (mas frecuente) 206 – acceso parcial 301 – permanentemente redireccionado 302 – temporalmente redireccionado 304 – no modificado 404 – no encontrado
Fuente de datos
Campo: Codigo estado152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /jobs/ HTTP/1.1" 200 15140 "http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N
URL del visitante desde donde vino a mi página
Fuente de datos
Campo: Referrer152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /jobs/ HTTP/1.1" 200 15140 "http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
"Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
User agent (browser)
Fuente de datos
Campo: User Agent152.152.98.11 - - [16/Nov/2005:16:32:50 -0500] "GET /jobs/ HTTP/1.1" 200 15140 "http://www.google.com/search?q=salary+for+data+mining&hl=en&lr=&start=10&sa=N" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)“
Introducción Objetivo Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Preparación de los Datos
Un registro válido debe:
Todos los campos deben ser diferente al valor null. El campo CodEstado debe tener alguno de los valores
válidos para nuestro análisis. El campo NombreArchivo debe almacenar un tipo de archivo
diferente a: jpg, bmp, gif, exe, js, css, pdf, doc, txt.
Si se considera como registro válido es almacenado en la tabla Registro_Log con su respectivo id.
Limpieza
Preparación de los Datos
Identificación de usuarios Identificación de páginas Registrar sesiones en tablas de acuerdo a usuario y tiempo.
Cada sesión tiene un usuario Un usuario puede tener varias sesiones La sesión esta limitada por el tiempo de sesionización. Formato resumido, rápida adaptación a algoritmos.
Sesionización
Introducción Objetivo Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Reglas de Asociación
Preparación Data
Generación de Matriz
Algoritmo Apriori
Reglas de Asociación
Encontrar las asociaciones que se producen entre los diferentes sitios de la página Web cuando los usuarios acceden a ésta.
X Y [/public/about.jsp ]---->/public/team.jsp
Soporte:Soporte (X Y) = Probabilidad (X U Y)
Confianza:Confianza (X Y) = Probabilidad (X / Y)
Reglas de Asociación
Reglas de Asociación
Registro_Log
Registro_Sesion
Registro_Paginas_Site
Preparación de Data
Reglas de Asociación
Sesión / Página 1 2 3 4 5 …..
# páginas
1 0 1 0 1 0 ….. 0
2 1 0 1 1 0 ….. 0
3 1 1 0 1 0 ….. 0
4 0 1 1 1 0 ….. 0
5 1 0 0 0 0 ….. 0
6 0 1 0 0 1 ….. 0
: : : : : : ….. 0
: : : : : : ….. 0
# sesiones 0 1 0 1 0 ….. 0
S1= (0+1+1+0+1+0+…+0)/# sesiones
Generación Matriz
Reglas de Asociación
20
5
3
1
Candidatos antecedentes (Sop > Soporte)
0…..01010# sesiones
0…..::::::
0…..::::::
0…..100106
0…..000015
0…..011104
0…..010113
0…..011012
0…..010101
# páginas…..54321Sesión / Página
S1 S2 ……S5 ……Sn
1
Algoritmo Apriori (matriz , soporte, confianza)
Usa conocimiento a priori de las propiedades de los ítems (páginas) frecuentes que ya se han encontrado. “Si un conjunto no puede pasar un test, todos sus súper conjuntos también fallarán el mismo test”
2
12 Solo si conf(12) > confianza confianza=Prob (X / Y)
3
2120
63
21
1
Reglas de Asociación
Preparación Data
Generación de Matriz
Algoritmo
Patrones Secuenciales
Generación FBP-Arbol
Descubrir patrones en los cuales la presencia de un conjunto de ítems es seguido por otro ítem en orden temporal. Encontrar y predecir el comportamiento de los visitantes de un sitio Web con respecto al tiempo.
Patrones Secuenciales
Patrones Secuenciales
[x1x2x3] [y1y2] en t días
Soporte:Soporte (X Y) = Probabilidad (X U Y)
Confianza:Confianza (X Y) = Probabilidad (X / Y)
[/public/team.jsp ->]---->/public/findUsers.jsp-> /private/mycourses/website/folders/assignment/assignment_view.jsp-> /public/portalDocument.js en 2 dias
Patrones Secuenciales
Patrones Secuenciales
Página / Página 1 2 3 4 5 ….. # páginas
1 0 30 0 1 0 ….. 0
2 4 0 48 34 6 ….. 0
3 5 1 0 1 40 ….. 0
4 0 32 3 0 6 ….. 0
5 27 0 0 74 0 ….. 0
6 0 1 0 0 4 ….. 0
: : : : : : ….. 0
: : : : : : ….. 0
# páginas 0 20 0 1 0 ….. 0
Generación Matriz
•TM[i,j] representa el número de veces que los usuarios han visitado la página j después de la página i.•Umbral
Página / Página 1 2 3 4 5 …..
# páginas
1 0 30 0 0 0 ….. 0
2 0 0 48 34 0 ….. 0
3 0 0 0 0 40 ….. 0
4 0 32 0 0 0 ….. 0
5 27 0 0 74 0 ….. 0
6 0 0 0 0 0 ….. 0
: : : : : : ….. 0
: : : : : : ….. 0
# páginas 0 20 0 0 0 ….. 0
•FTM caminos frecuentesSi un 2-camino(camino con 2 páginas) no es frecuente un 3-camino(camino con 3 páginas) del que sea subcamino el 2-camino tampoco lo será (propiedad Apriori).
Patrones SecuencialesGeneración FBP-Árbol (Matriz FTM, Lista de Caminos)
Pag 230
Pag 1
Pag 378
Pag 464
Pag 5118
Punto de Ruptura
Antecedente
ConsecuenteConsecuente
Patrones Secuenciales
La confianza de una regla de comportamiento-frecuente se representa como conf(PIND PDEP) y define la probabilidad de recorrer el camino PDEP una vez se ha recorrido el camino PIND.
Se recorre el árbol desde las hojas al nodo raíz. Teniendo en cuenta el soporte de cada camino las reglas se son
calculados como sigue. Buscar en hojas el punto de ruptura.
Si la hoja no es Punto ruptura, ir a hoja anterior. Si la hoja es Punto Ruptura, calcular confianza.
Si conf > confianza, genera Patrón Si conf < confianza, podar rama de árbol.
Algoritmo Patrones (FBP-Arbol, soporte, confianza)
Clusterización
Encontrar entre los distintos visitantes grupos con características similares de navegación Web.Proporciona como salida k conjuntos de patrones sobre las características similares de navegación (páginas visitadas) de los usuarios.
Preparación Data
Generación de Matriz
Algoritmo K-Medias
Grupos
Clusterización
Cluster #1/js/tiny_mce/blank.htm/js/tiny_mce/themes/advanced/color_picker.htm
Cluster #2/js/tiny_mce/profiles/blank.htm
Clusterización
Clusterización
M[i,j] representa al usuario i visitando la página j en algunas de las sesiones iniciadas por el usuario i.
Usuario / Página 1 2 3 4 5 …..
# páginas
1 0 1 0 1 0 ….. 0
2 1 0 1 1 0 ….. 0
3 1 1 0 1 0 ….. 0
4 0 1 1 1 0 ….. 0
5 1 0 0 0 0 ….. 0
6 0 1 0 0 1 ….. 0
: : : : : : ….. 0
: : : : : : ….. 0
# Usuarios 0 1 0 1 0 ….. 0
Generación Matriz
ClusterizaciónAlgoritmo K-Medias (Matriz, soporte)
Usuario / Página 1 2 3 4 5 ….. # páginas
1 0 1 0 1 0 ….. 0
2 1 0 1 1 0 ….. 0
3 1 1 0 1 0 ….. 0
4 0 1 1 1 0 ….. 0
5 1 0 0 0 0 ….. 0
6 0 1 0 0 1 ….. 0
: : : : : : ….. 0
: : : : : : ….. 0
# Usuarios 0 1 0 1 0 ….. 04. Repetir los pasos 2 y 3 hasta que los centróides no varíen
1.Seleccionar centroides aleatorios
Distancia Euclídea δ²E (Xi, Xj) = || Xi-Xj||2 = (Xi - Xj)T(Xi - Xj)
2. Asignar cada objeto al grupo cuyo centróide sea el más cercano al objeto.
3. Cuando todos los objetos hayan sido asignados, recalcular la posición de los k centróides.
Determinar la media de cada grupo
Introducción Objetivo Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Reportes EstadísticosObjetivos
Análisis del sitio Web Links o páginas mas visitados Cantidad de usuarios que visitan el sitio Web La descarga de bytes de nuestro sitio Web
Mejorar el sitio Web
Introducción Objetivo Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Tipos de Reporte
Urls externos Tiempo de visita Tipo de navegador Cantidad de usuarios que visitan el sitio Bytes de descarga de las paginas Número de visitas por página
Tipos de Reporte
Tipos de Reporte Fecha de Rango
Tipos de Reporte
Tipos de Reporte Fecha de Rango
Tipos de Reporte
Páginas mas visitadas
Tipos de Reporte
Tiempos de visita por página
Tipos de Reporte
Tiempos de visita por página
Tipos de Reporte
Tipo de navegador y Sistema operativo
Tipos de Reporte
Bytes de descarga de las páginas
Tipos de Reporte
Número de visitas por página
Introducción Objetivo Esquema Básico: Minería de Datos Fuente de Datos Preparación de los Datos Métodos de Minería Reportes Estadísticos Tipos de Reportes Conclusiones
Agenda
Conclusiones
La aplicación permite analizar los archivos log de un servidor Web encontrando patrones de navegación de los visitantes del sitio Web.
Basándose en los accesos de los usuarios se encontró asociaciones entre los diferentes sitios de la página Web definidas en las reglas encontradas.
Con los patrones secuenciales encontrados se puede predecir el comportamiento de los visitantes con respecto al tiempo.
Se encontró grupos de paginas con características similares con el método de clusterización.
Tomar decisiones Mejoras del Sitio Web Segmentación del sitio Web. Búsqueda fácil de la información
Marketing - competitivos Conocer gustos del cliente. Mejorar o crear ofertas según el cliente
GRACIAS
Demostración del Sistema