Taller de Base de Datos
Minería de Datos en la Web
Descubrimiento de patrones y modelos en la Web
• Minería de Contenido
– Contenido de páginas y fuentes de datos en la Web.
• Minería de Uso
– Registros de navegación almacenados en archivos de log en los
servidores.
• Minería de Contenido
– Estructura de enlaces entre páginas en la Web.
Taller de Base de Datos
Minería de Contenido
•Clasificación de texto
•Extracción de frases características de grupos de documentos.
•Búsqueda de patrones en textos (reglas de asociación).
•Agrupaciones de documentos
•Construcción automática de jerarquías de documentos.
Taller de Base de Datos
Minería de Uso
•Extracción de perfiles de usuario en interfaces adaptivas.
•Búsqueda de patrones de navegación.
•Personificación, segmentación y diseño de sitios.
Taller de Base de Datos
Minería de Estructura
• Algoritmos de jerarquización de páginas en motores de
búsqueda.(ejemplo Google)
• Búsqueda de comunidades en la Web.
Taller de Base de Datos
Identificación de páginas Autoridades
Un 99% de la Web es inútil para un 99% de los usuarios
[Brin98] .
• Muchos enlaces en la Web son anotaciones humanas sobre
la calidad de las páginas y recursos en general.
• Más formalmente: si una página X apunta a una página Y,
entonces el autor de X le confiere un cierto grado de
importancia a la página Y.
• Algoritmo PageRange: ordena páginas en base a la
estructura de enlace en la Web.
Taller de Base de Datos
Enfoque Ingenuo
Una página es autoridad si es apuntada por muchas páginas.
Problema:
• Fácil de falsear: basta con generar mucha páginas que
apunten a una página cuyo grado de autoridad se desea
mejorar.
• No mide calidad de las páginas que recomiendan.
Taller de Base de Datos
Cadenas de Markov
Una cadena de Markov es un proceso probabilístico sin
memoria modelada como:
• Un conjunto de estados S={s1,s2,…,sn} que representan los
posibles valores que la variable aleatoria puede tomar.
• Una colección de probabilidades de transición
representadas como una matriz P de nxn.
Pi,j=Pr( El proceso salte del estado i al estado j, dado
que está en el estado i)
• Un vector de nx1 П0, donde Пi0 es la probabilidad de la
variable de estar en el estado i en el tiempo 0.
Taller de Base de Datos
Propiedad Markoviana
Sea xt el estado del proceso en el paso t, entonces
Pr(xt |x1,…,xn)=Pr(xt|xt-1)
Notación:
• Pi,jt = probabilidad de llegar al estado j desde el estado i en
t pasos.
• Пk es el vector de probabilidad no condicional. Representa
la probabilidad de estar en k pasos en cada estado, dado
que partimos con probabilidad П0 .
Taller de Base de Datos
•
•
•
•
Propiedades de cadenas de Markov
Un estado i se comunica con un estado j, si para algún
estado t, t’ Pi,jt>0 y Pj,it’>0.
Una cadena de Markov es irreducible si todo par de
estados se comunican.
Un estado i tiene periodo d si dado que x0 = i solo podemos
tener xn=i cuando n es múltiplo de d.
Una cadena de markov es periódica si tiene algún periodo
mayor que 1.
Taller de Base de Datos
Distribución de probabilidades estacionarias
П1= П0P
…
Пt= Пt-1P
Si converge Пt tenemos distribución estacionaria
П=limt->∞Пt
O bien Пt tal que
ПP=П
Intuitivamente Пt representa la fracción en que el proceso se
encuentra en el estado i.
Taller de Base de Datos
Teorema Fundamental
Dada una cadena de Markov finita, aperiódica e
irreducible, entonces existe un estado de equilibrio o
distribución de probabilidades estacionaria П.
ПP=П
Taller de Base de Datos
PageRank
Modelemos a un navegante de la Web como una cadena de
Markov, cada página define un estado.
Enfoque Básico:
Si el navegante está en una página i, salta a una página con
probabilidad j .
Lo que es equivalente a escribir:
Taller de Base de Datos
Taller de Base de Datos
Problema de enfoque Básico
No siempre la cadena generada en el modelo básico es
irreducible y aperiódica .
Ciclotrón
Taller de Base de Datos
Enfoque de PageRank
Un navegante está en un URL i
• Hace click en una enlace i con probabilidad 1-ε
• Se aburre y se va a otro sitio con probabilidad ε
Donde M es el número de páginas que no son apuntadas por i, y ε representa la
prob. de que el navegante no siga ningún enlace de la página i.
Esta cadena de Markov es irreducible y aperiódica
Se tiene:
Taller de Base de Datos
PageRank
• Una página tiene buen ranking si es apuntada por
muchas buenas páginas.
• Funciona en la práctica: base del éxito del Google
• Resistente a spam:
– Falsear pageRank cuesta dinero: debo convencer a buenos
sitios queme apunten.
• No es costoso computarlo.
Taller de Base de Datos
Algoritmo Hits
J. Kleinberg.Authoritative Sources in a Hiperlinked Enviroment
Problemas de PageRank:
• Muchos enlaces tiene propósitos de navegación y no la intención de
conferir autoridad.
• Muchos enlaces representan publicidad pagada.
– PageRank no discrimina enlaces
• Una página muy apuntada como Hotmail, no es autoridad en
cualquier tópico.
– PageRank no discrimina tópicos (yahoo es autoridad en cualquier
tópico)
Taller de Base de Datos
Algoritmo Hits Primera Etapa
Construcción de un grafo en la Web focalizado en un tópico
Dado una consulta σ, determinamos un grafo Sσ con las
siguientes características.
• Sσ debe ser relativamente pequeño.
• Sσ debe ser rico en páginas relevantes.
• Sσ contiene muchas páginas que son autoridades.
Taller de Base de Datos
Algoritmo Hits: Primera Etapa (cont.)
Para parámetros t (t ≈ 200) y d (d ≈ 50)
• Recolectamos las t mejores páginas de σ, Rσ , entregadas
por un buscador (ej, Altavista, HotBot, Google).
• Agregamos a Sσ y Rσ y todas las páginas apuntadas por Rσ
• Agregamos a Sσ un conjunto arbitrario de d páginas que
apuntan a RΣ .
Taller de Base de Datos
Ejemplo
Usando Alta vista con t=200 y d=50, Sσ satisface las tres
condiciones y contiene de 1000 a 5000 páginas.
G[Sσ] es el grafo que se obtiene de Sσ al eliminarse grafos
intrínsecos y de travesía (en el mismo sitio).
Taller de Base de Datos
Hits: Idea
Dos páginas que son autoridades en un tópico son en general
apuntadas por la mismas páginas (Hub).
Toda página x tiene un peso por ser autoridad Aut(x) y un
peso por ser hub Hub(x). Invariante:
ΣxєSσ Aut(x)=1=ΣxєSσ Hub(x)
Una buena autoridad es apuntada por muchos buenos hubs.
Aut(x)= ΣyєIn(x) Hub(y)
Un buen hub apunta muchas buenas autoridades
Hub(x) = ΣyєOut(x) Aut(x)
Taller de Base de Datos
Algoritmo Hits
• Inicialmente para todo x Aut(x)=Hub(x)=0
• Iteramos haciendo
– Hub(x)
ΣyєOut(x) Aut(x)
– Aut(x)
ΣyєIn(x) Hub(y)
– Normalizamos Aut(x) y Hub(y)
• La iteración termina cuando Aut(x) y Hub(x) no varian
significativamente.
Taller de Base de Datos
Problema deHit
• Hub pueden contener múltiples tópicos
• Spam: Muchas páginas en un mismo sitio apuntando a un
mismo sitio popular.
Mejoras:
• Menor ponderación de páginas que apuntan a un mismo
sitio.
• Fraccionamiento de Hubs en un mismo link
• Uso de texto de ancla, etc.
Descargar

Taller de Base de Datos Minería de Contenido