taller de base de datos

23
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.

Upload: duyen

Post on 19-Mar-2016

59 views

Category:

Documents


2 download

DESCRIPTION

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 - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Taller de Base de Datos

Taller de Base de Datos

Minería de Datos en la WebDescubrimiento 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.

Page 2: Taller de Base de Datos

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.

Page 3: Taller de Base de Datos

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.

Page 4: 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

Page 5: Taller de Base de Datos

Identificación de páginas AutoridadesUn 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

Page 6: 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

Page 7: 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

Page 8: 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,j

t = 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

Page 9: 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,i

t’>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

Page 10: Taller de Base de Datos

Distribución de probabilidades estacionarias

П1= П0P…

Пt= Пt-1PSi 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

Page 11: 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

Page 12: 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

Page 13: Taller de Base de Datos

Taller de Base de Datos

Page 14: 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

Page 15: 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

Page 16: 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

Page 17: 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

Page 18: Taller de Base de Datos

Algoritmo Hits Primera Etapa

Construcción de un grafo en la Web focalizado en un tópicoDado 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

Page 19: 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

Page 20: 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

Page 21: 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 autoridadesHub(x) = ΣyєOut(x) Aut(x)

Taller de Base de Datos

Page 22: 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

Page 23: 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.

Taller de Base de Datos