PDF de programación - Data Mining - Extracción de Conocimiento en Grandes Bases de Datos

Data Mining.

Extracción de Conocimiento en

Grandes Bases de Datos

http://etsiso2.macc.unican.es/~meteo

José M. Gutiérrez
Dpto. de Matemática Aplicada,
Universidad de Cantabria, Santander

http://personales.unican.es/gutierjm

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i



i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



m

/

i

.

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

l

.

/
/
:
p
t
t
h

El Mundo de la Información y sus Problemas.
• Cada vez se genera más información y se hace más fácil el acceso
masivo a la misma (existen gran cantidad de bases de datos on-line)

¸ Transacciones bancarias, Internet y la Web, observaciones científicas

•

(biología, altas energías, etc. ) "tranNASA’s EOS (Earth Observation System)".
La tecnología es barata y los sistemas de gestión de bases de datos
son capaces de trabjar con cantidades masivas de datos (Terabytes).

Los datos contienen información útil "CONOCIMIENTO" !!!

• Necesitamos extraer información (conocimiento) de estos datos:

¸Rapidez y confiabilidad.

¸Capacidad de modelización y escalabilidad.

¸Explicación e Interpretación de los resultados (visualización, …).

WalMart captura transacciones de 2900 tiendas en 6 países. Esta información e acumula en
una base de datos masiva de 7.5 terabyte. WalMart permite que más de 3500 proveedores
accedan a los datos relativos a sus productos para realizar distintos análisis. Así pueden
identificar clientes, patrones de compras, etc. En 1995, WalMart computers procesó más de
un millón de consultas complejas.

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i



i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



m

/

i

.

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

l

.

/
/
:
p
t
t
h

Datos, Información y Conocimiento.

¿Qué diferencias hay entre información, datos y conocimiento?

¸ Informalmente se utilizan indistintamente, con pequeños matices.

¸ información y datos se pueden referir a cualquier cosa, aunque
“Datos” suele referir a la “evidencia”.

¸ Conocimiento es subjetivo:

depende de las intenciones (objetivo del aprendizaje).

debe ser inteligible para el que aprende o el que encarga el aprendizaje (usuario).

¿Qué es aprendizaje?

¸ (visión genérica, Mitchell 1997) es mejorar el comportamiento a partir de la
experiencia. Aprendizaje = Inteligencia.

¸ (visión más estática) es la identificación de patrones , de regularidades,
existentes en la evidencia.

¸ (visión externa) es la predicción de observaciones futuras con plausibilidad.

¸ (visión teórico- informacional, Solomonoff 1966) es

eliminación de redundancia = compresión de información .

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i



i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



m

/

.

i

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

l

.

/
/
:
p
t
t
h

Acceso a los Datos. Evolución histórica.

La necesidad de almacenar información ha motivado históricamente el desarrollo de
sistemas más eficientes, con mayor capacidad y más baratos de almacenamiento.

m

/

i

.

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

l

.

/
/
:
p
t
t
h

• Bases de datos relacionales.
• DBMS (Data Base Management Systems) y repositorios de información:

– Bases de datos orientadas a objetos y objeto-relacionales.
– Bases de datos espaciales (geográficas).
– Bases de datos de texto y multimedia.
– WWW.

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i



i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



OLAP (On-Line Analytical Processing)

Sobre estas mismas bases de datos de trabajo ya se puede extraer conocimiento
(visión tradicional).

¸Se mantiene el trabajo transaccional diario de los sistemas de información
originales (conocido como OLTP, On- Line Transactional Processing ).

¸Se hace análisis de los datos en tiempo real sobre la misma base de
datos( conocido como OLAP, On- Line Analytical Processing ),

Según la organización de la información copiada se distingue:

¸ROLAP (Relational OLAP): el almacén de datos es relacional.

¸MOLAP (Multidim OLAP): el almacén de datos es una matriz multidimensional.

Cada atributo relevante se establece en una dimensión, que se puede agregar o desagregar.

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U



i

i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



m

/

i

.

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

l

.

/
/
:
p
t
t
h

Data Warehouses. Génesis.

PROBLEMAS:

¸ Disturba el trabajo transaccional diario de los sistemas de información originales
(“ killer queries ”). Se debe hacer por la noche o en fines de semana.

¸ La base de datos está diseñada para el trabajo transaccional, no para el análisis
de los datos. Generalmente no puede ser en tiempo real (era AP pero no OLAP).

Para poder operar eficientemente con esos datos y debido a que los
costes de almacenamiento masivo y conectividad se han reducido
drásticamente en los últimos años, parece razonable recoger (copiar) los
datos en un sistema unificado.

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i



i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



m

i

.

/

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

.

l

/
/
:
p
t
t
h

Data Warehouses

DATA-WAREHOUSES (Almacenes de Datos): Se separan de los datos a
analizar con respecto a sus fuentes transaccionales (se copia/ almacena toda
la información histórica).

Existe toda una tecnología creciente de cómo organizarlos y sobretodo de cómo
tenerlos actualizados (cargas periódicas) respecto a los datos originales

VENTAJAS:

¸Facilita el análisis de los datos en tiempo real (OLAP),

¸No disturba el OLTP de las bases de datos originales.

A partir de ahora
diferenciaremos
entre bases de
datos para OLTP
(tradicional) y
almacenes de datos
(KDD sobre data
warehouses).

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i



i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



m

.

/

i

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

l

.

/
/
:
p
t
t
h

Construcción de un Data Warehouse

Data

Warehouse

Limpieza y criba selección de datos:

Se deben elmininar el mayor número posible de
datos erróneos o inconsistentes (limpieza) e
irrelevantes (criba).

Data Cleaning

m

Databases

Se aplican métodos estadísticos:

-Histogramas (detección de datos anómalos).
- Redefinición de atributos (agrupación o separación).

Muy relacionado con la disciplina de “Calidad de Datos”.

/

i

.

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

l

.

/
/
:
p
t
t
h

Acciones ante datos anómalos (outliers):

- Ignorar: algunos algoritmos son robustos a datos anómalos.
- Filtrar (eliminar o reemplazar) la columna: solución extrema.
- Discretizar: transformar un valor continuo en uno discreto (p. ej. muy alto, alto, etc.)
hace que los outliers caigan en ‘muy alto’ o ‘muy bajo’ sin mayores problemas.

Acciones ante datos faltantes (missing values):

- Ignorar: algunos algoritmos son robustos a datos faltantes.
- Filtrar (eliminar o reemplazar) la columna
- Reemplazar el valor: por medias. A veces se puede predecir a partir de otros datos,
utilizando cualquier técnica de ML.

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i



i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



¿Qué es Data Mining (minería de datos)?

the non trivial extraction of implicit,
previously unknown, and potentially
useful information from data
W. Frawley and G. Piatetsky-Shapiro and C. Matheus,
Knowledge Discovery in Databases: An Overview.

CONOCIMIENTO

Pattern

Evaluation

AI Magazine, Fall 1992, 213-228.

Data Mining

Task-relevant

Data

Selection

Data

Warehouse

Data Cleaning

Data Integration

Databases

Datos imprecisos e
incompletos

almacenados en
múltiples fuentes

Heterogéneos y
mezclados.

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U



i

i


,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



m

i

.

/

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

l

.

/
/
:
p
t
t
h

Diferencias entre DBMS y Data Mining

En los sistemas estándar de gestión de bases de datos las
consultas se resuelven accediendo a distintos conjuntos de
datos almacenados:

¸Ventas del último mes de un producto.

¸Ventas agrupadas por la edad del comprador.

Los sistemas de data mining infieren conocimiento de la base
de datos en forma de estructuras y patrones. Este
conocimiento supone un nuevo conjunto de información en
base a la cual se responden las consultas:

¸por qué es tan rentable la división Iberoamericana de Telefónica?

¸¿qué clientes son potenciales compradores de un producto?

¸¿cuál será el beneficio de la compañía el mes próximo?

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i

i



,
z
e
r
r
é

i
t
u
G


l

e
u
n
a
M
é
s
o
J



m

i

.

/

j
r
e
i
t
u
g
s
e
n
a
c
n
u
s
e
a
n
o
s
r
e
p

.

l

/
/
:
p
t
t
h

Acceso a Datos vs. Acceso a Conocimiento

http://www.datamining.com

Paradigma de Acceso a Datos:
El usuario solicita datos y procesa los datos
recibidos en busca de "conocmiento".
SQL + algoritmos de data mining.

Paradigma de Acceso a Conocimiento:
El sistema genera automáticamente patrones de
conocimiento refinados y el usuario accede
directamente a los mismos.
PQL = Pattern Query Languaje

PQL was designed to access patterns just as SQL was
designed to access data. PQL resembles SQL, works atop
existing SQL engines.
Information Discovery uses a Pattern WarehouseTM of refined
information and PQL works on patterns just as SQL works on a
datawarehouse. While SQL relies on the relational algebra,
PQL uses the "pattern algebra". PQL allows pattern-based
queries just as SQL allows data-based queries. And, PQL uses
SQL as part of its operation, i.e. PQL queries are
decomposed into a set of related SQL queries, the Pattern
Warehouse is accessed with these queries and the results are
re-combined for display to the user. The user accesses these
patterns using a web browser.

)
1
0
0
2
(

.



a
i
r
b
a
t
n
a
C
e
d
d
a
d
s
r
e
v
n
U

i