Apuntes de clase de la materia Big Data dictada por Daniel Yankelevich en FCEN UBA en 2015 1C

bigdata.md

Estructuras de datos probabilísticas

• No devuelven la respuesta exacta, sino una estimación.
• En algoritmos de streaming, suele ser mejor una respuesta aproximada en el momento a una exacta mucho más tarde

Set membership

• Estructura Bloom filter para set membership, usa tiempo constante para add y query
• Hashing (tomar un fingerprint de todos los datos) suele ser mejor técnica que sampling (leer solamente algunos datos al azar), ya que genera solo falsos positivos, no negativos

Cardinality estimation

• Se busca contar cuántos elementos únicos se vieron en un stream de datos.
• Probabilistic counting
• Se considera la tira continua de ceros más larga vista hasta el momento; cuanto más larga, más probable es que haya visto más items
• Implementado con mejoras en HyperLogLog

Frequency estimation

• Estructura Count min
• Similar a bloom filter, pero el objetivo es contar frecuencia de cada item, no solamente pertenencia

Bases de datos

VoltDB

• Ejemplo de NewSQL
• Diseñada para fast data
• Procesamiento en memoria por columnas
• SQL + Windowing
• ACID
• Para analytics: small pattern big state

CEP

• Complex event processing
• Procesar stream de datos a medida que se van recibiendo
• Big pattern small state

Datos distribuidos

Big data se puede separar en:

• Analytics y modelos predictivos
• Data management (DBs)
• Drinking from the hose (algoritmos aproximados para fast data)
• Distribution y clustering (ej Hadoop)

Ej de algoritmos para datos distribuidos:

• PAXOS es una familiar de protocolos destinada a resolver consenso entre múltiples parties; es resilient contra silent crashes.
• Google spanner se basa en tener global timestamps usando relojes atómicos en cada datacenter

Visualización de datos

• Ante un nuevo set de datos, siempre empezar por graficarlo
• Graficar primero variables con mayor entropía, que ofrezcan la mayor informacion
• Cuarteto de Anscombe: 4 datasets totalmente disímiles con stats muy similares
• Las series temporales, al compartir tendencia, suelen tener una correlación fuerte; para analizar series temporales se suele analizar las primeras diferencias y'(t) = y(t) - y(t-1) que eliminan las tendencias.
• No confundir probabilidades a priori y a posteriori (las historias de éxito suelen ser un ejemplo de esto)
• Si se tortura suficiente los datos, terminan siempre diciendo algo
• Siempre buscar mejorar la calidad de los datos por sobre la calidad de los algoritmos

Bayes

• Tener en cuenta la regla de Bayes a la hora de generar conclusiones. Ej: un test positivo de una enfermedad improbable.
• Se busca distinguir una correlación del caso azaroso.

P(C|E) = P(E|C) * P(C) / P(E)

Naive Bayes

• Clasificador sencillo basado en la regla de Bayes
• Asume que los eventos de la evidencia son independientes

En la fórmula de Bayes:

• E es la evidencia
• C la pertenencia a la clase
• P(C|E) es el clasificador
• P(E|C) es fácil de determinar
• P(C) y P(E) pueden obtenerse de datos demográficos o simplemente de frecuencias sobre el dataset

El algoritmo resulta:

P(C0|E) = P(E1|C) * P(E2|C0) * ... * P(En|C0) / (P(E1|C0) * ... * P(En|C0) + P(E1|C1) * ... * P(En|C1))