Capitulo 14- Analisis y Minera de Datos

8/2/2019 Capitulo 14- Analisis y Minera de Datos

1/31

Las empresas han comenzado a aprovechar los cada vez mas numerosos datos en linea para tomarmejores decisiones sobre sus actividades. como los articulos que deben tener en inventario y el modode dirigirse mejor a los clientes para aumentar las ventas. Muchas de las consultas, sin embargo, sonbastante cornplejas y algunos tipos de informaci6n no pueden extraerse ni siquiera empleando SQL.

Se encuentran disponibles varias tecnicas y herramientas de ayuda a la toma de decisiones. Existenherramientas para el analisis de datos que permiten a los analistas ver los datos de diferentes formas.Otras herramientas de analisis realizan un calculo previo de resumenes de cantidades muy grandes dedatos con objeto de dar respuestas rapidas a las consultas. Las norrnas SQL:1999y SQL:2003contienenahora constructores adicionales para soportar el analisis de datos. Otro enfoque para obtener informa-ci6n de los datos es utilizar la miner fa de datos, que pretende detectar varios tipos de estructuras engrandes volumenes de datos. La mincria de datos complementa varios tipos de tecnicas estadisticas conobjetivos parecidos.

Este capitulo trata sobre la ayuda a la toma de declsiones, incluidos el procesamiento analitico enlinea, los almacenes de datos y la mineria de datos.

14.1 Sistemas de ayuda a la toma de dedsiones

Las aplicaciones de bases de datos pueden clasificarse grosso modo en sistemas de procesarniento detransacciones y de ayuda a la toma de decisiones. Los sistemas de procesamiento de transacciones sonsistemas que registran informaci6n sobre las transacciones, como ventas de productos 0 matriculas einformaci6n de titulaciones para las universidades. Los sistemas de procesamiento de transacciones seutilizan mucho hoy en dia y las empresas han acumulado una enorme cantidad de informaci6n gene-rada por ellos. Los sistemas de ayuda a la toma de decisiones facilitan a los gestores la decisi6n de losproductos que se deben almacenar en una tienda, los productos que es necesario fabricar 0 las personasque se deberian admitir en una universidad.

Por ejemplo, las bases de datos de las empresas suelen contener enormes cantidades de informaci6nsobre los clientes y las transacciones. La cantidad de informacion necesaria puede lIegar a varios cen-tenares de gigabytes 0, incluso, a los terabytes para las cadenas de grandes almacenes. La informaci6nde las transacciones de un gran almacen puede incluir el nombre 0 identificador (como puede ser elnumero de la tarjeta de credito) del cliente, los articulos adquiridos, el precio pagado y las fechas en quese realizaron las compras. La informacion sobre los articulos adquiridos puede incluir e! nombre delarticulo, el fabricante, el numero del modele. el color y la talla. La informaci6n sobre los clientes puedeinc!uir su historial de credito, sus ingresos anuales, su domicilio, su edad e, incluso, su nivel acadernico.

Estas bases de datos de gran tarnafio pueden resultar minas de informaci6n para adoptar decisionesempresariales, como los articulos que debe haber en inventario y los descuentos que hay que ofrecer.Por ejemplo, puede que una cadena de grandes almacenes note un aumento subito de las compras de

455


2/31

456 Capitulo 14 Analisis y mineria de datos

camisas de franela en la Sierra de Guadarrama, darse cuenta de que hay una tendencia y comenzar aalmacenar un mayor numero de esas carnisas en las tiendas de esa zona. 0 puede que una empresaautomovilistica descubra, al consultar su base de datos, que la mayor parte de los coches deportivosde pequeno tamafio los compran mujeres j6venes cuyos ingresos anuales superan los 50.000 . Puedeque la empresa dirija su publicidad para que atraiga mas mujeres de esas caracterfsticas a que comprencoches deport ivos de pequefio t arnafio y evi te desperdiciar dinero intentando atraer a otras categorfasde consumidores para que compren esos coches. En ambos casos la empresa ha identificado pautas decomportamiento de los consumidores y las ha util izado para adoptar decisiones empresariales.

El almacenamiento y recuperaci6n de los datos para la ayuda a la toma de decisiones plantea variosproblemas:

Aunque muchas consultas para ayuda a la toma de decisiones pueden escribirse en SQL, o tras nopueden expresarse en SQl 0 no pueden hacerlo con facil idad. En consecuenc ia, se han propuestovarias extensiones de SQl para facilitar el analisis de los datos. El area de procesamienio anal ii icoen linea (Online Analytical Processing, OlAP) trata de las herramientas y de las tecnicas para elanalisis de datos que pueden dar respuestas casi instantaneas a las consultas de datos resumidos,aun cuando la base de datos sea extremadamente grande. En el Apartado 14.2 se estudian lasextensiones de SQL para e1 analisis de datos y las tecnicas para el procesamiento analitico enIlnea.

Los lenguajes de consultas de bases de datos no son eficaces para el analisis estadistico detalladode datos. Existen varios paquetes, como SASy S++, que ayudan en el analisis estadistico. A estospaquetes se les han ana dido interfaces con las bases de datos para permitir que se almacenen enellas grandes volumenes de datos y se recuperen de manera eficiente para su analisis. E1campodel analisis estadistico es una gran disciplina por sf misma, veanse las referencias en las notasbibliograficas para obtener mas informaci6n.

Las grandes empresas tienen varies orfgenes de datos que necesitan utilizar para adoptar deci-siones empresariales. Los ongenes pueden almacenar los datos segun diferentes esquemas. Pormotivos de rendimiento (a sf como por motivos de control de Ia organizaci6n) los origenes dedatos no suelen permitir que otras partes de la empresa recuperen datos a petici6n.

Para ejecutar de manera eficiente las consultas sobre datos tan diferentes las empresas hancreado a lmac ene s d e dat os .Los almacenes de datos reunen los datos de varios origenes bajo unesquema unificado en un solo sitio. Por tanto, ofrecen al usuario una sola interfaz uniforme paralos datos. Los problemas de la creaci6n y mantenimiento de los almacenes de datos se estudian

en el Apartado 14.3.

Las tecnicas de descubrimiento de conocirniento intentan determinar de manera automatica re-glas estadisticas y patrones a partir de los datos. El campo de la mine ri a d e d a to scombina las tee-nicas de descubrimiento de conocimiento creadas por los investigadores en inteligencia artificialy los analistas estadfst icos con las tecnicas de implementaci6n eficiente que permiten util izarlasen bases de datos extremadamente grandes. El Apartado 14.4 estudia la mineria de datos.

El area de ayuda a la toma de decisiones puede considerarse que abarca todas las areas anterio-res, aunque algunas personas utilizan el terrnino en un sentido mas restrictivo que excluye el analisisestadistico y la mineria de datos.

14.2 Analisis de datos y OLAPAunque es mejor dejar el analisis estadistico complejo a los paquetes estadisticos las bases de datos

deben soportar las formas sencillas, utilizadas frecuentemente, de analisis estadistico. Dado que losdatos almacenados en las bases de datos suelen ser de gran volumen, hay que resumirlos de algunmodo si hay que obtener informacion que puedan utilizar los usuarios.

Las herrarnientas OlAP soportan el anali si s interact ivo de la informaci6n de resumen. Se han desarro-llado varias extensiones de SQl para soportar las herramientas OlAP. Hay muchas tareas utilizadas confrecuencia que no pueden realizarse empleando las facilidades basicas de agregaci6n y agrupamiento


3/31

14.2 Analisis de datos y OLAP 457

ta lla : ~

color

nombre _ar t iculo

oscuro pastel blanco Totalfalda 8 35 1 0 53vestido 2 0 1 0 5 35camisa 1 4 7 2 8 4 9pantal6n 2 0 2 5 2 7

Total 6 2 5 4 4 8 1 6 4

Figura 14.1 Tabulaci6n cruzada de ventas con nombre_artfculoy color.

de SQL.Entre los ejemplos se hallan 1abusqueda de percentiles, las distribuciones acumulativas 0 losagregados sobre ventanas deslizantes de datos ordenados secuencialmente. Recientemente se han pro-puesto varias extensiones de SQLpara soportar estas tareas y se han implementado en productos comoOracle y DB2 de IBM.

14.2.1 Procesamiento anaHtico en linea

El analisis estadistico suele necesitar el agrupamiento de varios atributos. Considerese una aplicaci6nen que una tienda desea averiguar las prendas que son mas populares. Sup6ngase que las prendas estancaracterizadas por su nombre de articulo, su color y su talla y que se tiene la relaci6n ventas con elesquema v en ta s ( nombr e_ ar tfc ul o, c ol or , ta ila , n ume ro y.Sup6ngase que n omb re a rtic ulopuede adoptar losvalores (falda, vestido, camisa, pantalon), colorpuede adoptar los valores (oscuro, pastel, blanco) y tallapuede adoptar los valores (pequena, mediana, grande).

Dada una relaci6n utilizada para el analisis de datos se pueden identificar algunos de sus atributoscomo atributos de medida, ya que miden algun valor y pueden agregarse. Por ejemplo, el atributonumero de la relaci6n ventas es un atributo de medida, ya que mide la cantidad de unidades vendidas.Algunos de los demas atributos (0 todos ellos) de la relaci6n se identifican como atributos de dimension,ya que definen las dimensiones en las que se ven los atributos de medida y los resumenes de los atributosde medida. En la relaci6n o en ia s, n om br e a rtic uic , c olo ry talla son atributos de dimensi6n. (Una versi6nmas realist a de la relaci6n ventas tendria mas dimensiones, como tiempo 0 Ingar de venta, y mas medidascomo el valor moneta rio de la venta).

Los datos que pueden modelarse como atributos de dimensi6n y como atributos de medida se deno-minan datos multidimensionales.

Para analizar los datos multidimensionales puede que el administrador desee ver los datos dispues-tos como se encuentran en la tabla de la Figura 1 4 . 1 .La tabla muestra las cifras totales de diferentescombinaciones de nombre_artfculoy color. E l valor de taLlase especifica como todas, 10 que indica que losvalores mostrados son un resumen para todos los valores de talla.

La tabla de la Figura 1 4 . 1 es un ejemplo de tabulacion cruzada, tarnbien denominada tabla dinami-ca. En general, las tabulaciones cruzadas son tablas en las que los valores de uno de los atributos (porejemplo, A) forman las cabeceras de las filas, los valores del otro atributo (por ejemplo, B) forman lascabeceras de las columnas y los valores de cada celda se obtienen como sigue: cada celda puede identi-ficarse como (ai) b j), donde a; es un valor de A, y b j es un valor de B. Si hay como maximo una tuplacon cualquier valor de (ai) bj), el valor de la celda se obtiene de esa (mica tupla (si es que hay alguna);por ejemplo, puede ser el valor de uno 0 varios atributos de la tupla. Si puede haber varias tuplas conel valor (ai) bj), el valor de la celda debe obtenerse por agregaci6n de las tuplas con ese valor. En esteejemplo la agregaci6n utilizada es la suma de los valores del atributo numero para todos los valores detalla, como se indica por talla: all en la tabla cruzada de la Figura 1 4 . 1 .En este ejemplo la tabulaci6ncruzada tambien tiene una columna y una fila adicionales que guardan los totales de las celdas de cadafila 0 columna. Lamayor parte de las tabulaciones cruzadas tienen esas filas y columnas de resumen.

Las tabulaciones cruzadas son diferentes de las tablas relacionales que suelen guardarse en las basesde datos, ya que el numero de columnas de la tabulaci6n cruzada depende de los datos. Una modifi-caci6n en los valores de los datos puede dar lugar a que se afiadan mas columnas, 10 que no resulta


4/31


nombr e a rti cu lo I color I talla 1 numero I-falda oscuro all 8falda pastel all 3 5falda blanco all 1 0falda all all 5 3vestido oscuro all 2 0vestido pastel all 1 0vestido blanco all 5vestido all all 3 5camisa oscuro all 1 4camisa pastel all 7camisa blanco all 2 8camisa all all 4 9pantal6n oscuro all 2 0pantalon pastel all 2panta16n blanco all 5pantal6n all all 2 7

all oscuro all 6 2all pastel all 5 4all blanco all 4 8all all all 1 6 4

Figura 14.2 Representaci6n relacional de los datos de la Figura 1 4 . 1 .

deseable para el almacenamiento de los datos. No obstante, 1avista de tabulaci6n cruzada es deseablepara mostrarsela a los usuarios. La representaci6n de las tabulaciones cruzadas sin valores resumen enun formulario relacional con un numero fijode columnas es directa. La tabulaci6n cruzada con columnaso filas resumen puede representarse introduciendo el valor especial todos para representar los subto-tales, como en la Figura 1 4 . 2 .La norma SQL:1999utiliza realmente el valor null (nulo) en lugar de all;pero, para evitar confusiones con los valores nulos habituales, en ellibro se seguira utilizando all.

Considerense las tuplas (falda, all, all, 53) y (vestido, all, all, 35).Se han obtenido estas tuplas elimi-nando las tuplas individuales con diferentes valores de color y ialla, y sustituyendo el valor de numeropor un agregado-es decir, una suma. El valor all puede considerarse representante del conjunto de losvalores de un atributo. Las tuplas con el valor all para las dimensiones color y talla pueden obtenersemediante una agregaci6n de la relaci6n ventas con una agrupaci6n en la columna nombre articulo. Demanera parecida, se puede utilizar una agrupaci6n en color y talla para conseguir las tuplas con el va-lor all para nombre articulo, y se puede utilizar una agrupaci6n sin atributo alguno (que en SQLpuedeomitirse simplemente) para obtener la tupla con el valor all para n om bre ariiculo , c olo ry ialla.

La generalizaci6n de las tabulaciones cruzadas, que son bidimensionales, a ti dimensiones puedenvisualizarse como cubos n-dimensionales, denominados cubos de datos. La Figura 1 4 . 3muestra uncubo de datos para la relacion ventas. EI cubo de datos tiene tres dimensiones, a saber, nombr e a rti cu lo ,color y ialla, y el atributo de medida es numero. Cada celda se identifica por los valores de estas tresdimensiones. Cada celda del cubo de datos contiene un valor, igual que en la tabulaci6n cruzada. En laFigura 1 4 . 3 ,el valor contenido en la celda se muestra en una de las caras de la celda; las otras caras de lacelda se muestran en blanco si son visibles. Todas las celdas contienen valores, aunque no sean visibles.

El valor de una dimensi6n puede ser all, en cuyo caso la celda contiene un resumen de todos losvalores de esa dimension, como en el caso de las tabulaciones cruzadas. Elnumero de maneras diferentesen que las tuplas pueden agruparse para su agregaci6n puede ser grande. De hecho, para una tabla conn dimensiones, sepuede realizar la agregaci6n con la agrupaci6n de cada uno de los 2n subconjuntos delas n dimensiones".

El sistema de procesamiento analitico en linea 0 sistema OLAPes un sistema interactivo que permite alos analistas ver diferentes resumenes de los datos multidimensionales. Las palabras e n lin eaindican que

1. La agrupaci6n sobre elconjunto de las n dirnensiones 5610 resulta Mil si la tabla puede tener duplicados.


5/31


pastel

1 6

4

18oscuro

9

6"0" blanco

45

pequeiia

rnediana

all

falda vestido carnisa pantalon allnombreuriiculo

Figura 14.3 Cubo de datos tridimensional.

los analistas deben poder solicitar nuevos resumenes y obtener respuestas en linea, en pecos segundos,y no deberian verse obligados a esperar mucho tiempo para ver elresultado de las consultas.

Con los sistemas OLAP los analistas de datos pueden ver diferentes tabulaciones cruzadas para losmismos datos seleccionando de manera interactiva los atributos de las tabulaciones cruzadas. Cadatabulaci6n cruzada esuna vista bidimensional del cubo de datos multidimensional. Por ejemplo, el ana-lista puede seleccionar una tabulaci6n cruzada para nombr e a r ti cu loy talla 0 una tabulaci6n cruzada paracolory talla. La operaci6n de modificaci6n de las dimensiones utilizadas en las tabulaciones cruzadas sedenomina pivotaje.

Los sistemas OLAP tambien ofrecen otras funcionalidades. Por ejemplo, puede que un analista deseever una tabulaci6n cruzada de nombre_artfculoy colorpara un valor fijode talla, por ejemplo, grande, enlugar de la suma para todas las tallas. Esta operaci6n se conoce como corte, ya que puede considerarsecomo la vista de una rebanada del cubo de datos. A veces la operaci6n se denomina corte de cubos,

especialmente cuando se fijan los valores de varias dimensiones.Cuando se utilizan tabulaciones cruzadas para ver cubos multidimensionales los valores de los atri-

butos de dimensi6n que no forman parte de la tabulacion cruzada se muestran por encima de ella. EIvalor de estos atributos puede ser all, comopuede verse en la Figura 14.1,10que indica que los datos deIatabulaci6n cruzada son un resumen de todos los valores del atributo. El corte y la creaci6n de datosconsisten simplemente en la selecci6n de valores concretos de estos atributos, que se muestran luegopor encima de la tabulaci6n cruzada.

Los sistemas OLAP permiten a los usuarios examinar los datos con cualquier nivel de granularidadque se desee. La operaci6n de pasar de datos con una granularidad mas fina a una granularidad masgruesa (mediante la agregaci6n) se denomina abstracci6n. En este ejemplo, a partir del cubo de datospara Ia tabla ventas, se obtiene la tabulaci6n cruzada de ejemplo abstrayendo el atributo talla. La ope-raci6n inversa-la de pasar de datos con una granularidad mas gruesa a una mas fina-se denominaconcreci6n. Claramente, los datos con granularidad mas fina no pueden generarse a partir datos canuna granularidad rnasgruesa: deben generarse a partir de los datos originales 0 de datos resumidos degranularidad aun mas fina.

Puede que un analista desee examinar una dimensi6n con niveles diferentes de detalle. Por ejemplo,los atributos de tipo FechaHora contienen una fecha y una hora del dia. EIernpleo de horas con precisi6nde segundos (0menos) puede que no sea significativo: los analistas que esten interesados en la horaaproximada del dia puede que s610miren el valor horario. Los analistas que esten interesados en lasventas de cada dia de la semana puede que apliquen la fecha al dia de la sernana y s610se fijen en eso.Puede que otro analista este interesado en agregados mensuales, trimestrales 0 de afios enteros.

Los diferentes niveles de detalle de los atributos pueden organizarse en una jerarquia. La Figu-ra 14.4amuestra una jerarquia para el atributo FechaHora. La Figura 14.4b,que puede ser otro ejem-


6/31


Afio

ITrimestre

IDia de la semana Mes

~Hora del dia Fecha

V

Region

IPais

IEstado

ICiudadechaHora

(a) [erarquia de tiempo (b) [erarquia de ubicacion

Figura 14.4 Jerarquias de las dimensiones.

plo, muestra una jerarquia para la ubicacion, con la ciudad en la parte inferior de la jerarqufa, el estadopor encima, el pais en el nivel siguiente y la regi6n en el nivel superior. En el ejemplo anterior la ropapuede agruparse por categorias (por ejemplo, ropa de hombre 0 de mujer); la caiegoria estarfa por enci-ma de nombre-articuloen la jerarquia de la ropa. En el nivel de los valores reales las faldas y los vestidoscaerian dentro de la categoria de ropa de mujer y los pantalones y las camisas en la de ropa de hombre.

Puede que un analista este interesado en consultar las ventas de ropa divididas entre ropa de hombre

y ropa de mujer y que no este interesado en sus valores individuales. Tras ver los agregados en elnivel de ropa de hombre y ropa de mujer puede que el analista concre te l a j era rqu iapara ver los valoresindividuales. Un analista que examine el nivel detallado puede abst rae r l aierarquia y exarninar agregadosde niveles mas gruesos. Ambos niveles pueden mostrarse en la misma tabulaci6n cruzada, como en I",

Figura 14.5.

14.2.2 lmplementacion de OLAPLos primeros sistemas de OLAP utilizaban arrays de memoria multidimensionales para almacenar loscubos de datos y se denominaban sistemas OLAP multidimensionales (Multidimensional OLAP, MO-LAP). Posteriormente, los servicios OLAP se integraron en los sistemas relacionales y los datos se alma-cenaron en las bases de datos relacionales. Estos sistemas se denominan sistemas OLAP relacionales(Relational OLAP, ROLAP). Los sistemas hibridos. que almacenan algunos resumenes en la memoria ylos datos basicos y otros resumenes en bases de datos relacionales, se denominan sistemas OLAP hfbri-dos (Hybrid OLAP, HOLAp)'

talla:~

caiegoria nombre_articulo colorloscuro I pastel blanco total

ropa de mujer falda 8 8 10 53--

vestido 20 20 5 35subtotal 28 28 15 88

ropa de hombre pantal6n 14 14 28 49

carnisa 20 20 5 27

subtotal 34 34 33 76total 62 62 48 164

Figura 14.5 Tabulaci6n cruzada de tenias con la jerarquia para nombr e a ri ic ul o.


7/31


Muchos sistemas OLAP se implementan como sistemas cliente-servidcir. El servidor contiene la ba-se de datos relacional y los cubos de datos MOLAP. Los sistemas clientes obtienen vistas de los datoscomunicandose con el servidor.

Una manera ingenua de calcular todo el cubo de datos (todas las agrupaciones) de una relaci6n esutilizar cualquier algoritmo estandar para calcular las operaciones de agregaci6n, agrupaci6n a agrupa-ci6n. EI algoritmo ingenuo necesita un gran nurnero de exploraciones de la relaci6n. Una optirnizacionsencilla consiste en calcular el agregado para, por ejemplo, (nombre_art iculo , color)a partir del agregado(nombre_art iculo , color, ta lla) ,en lugar de hacerlo a partir de la relacion original.

Para las funciones de agrsgacion estandar de SQLsepueden calcular agregados con agrupaciones so-bre un conjunto de atributos A a partir de un agregado con agrupaci6n sobre un conjunto de atributos Bsi A < ; ; ;B; se puede hacer como ejercicio (vease el Ejercicio 14.1), pero hay que tener en cuenta que al cal-cular avg tambien es necesario el valor count (para algunas funciones de agregacion no estandar comola mediana, los agregados no pueden calcularse de la manera indicada; la optimizacion aqui descrita noes aplicable a estas funciones de agregacion no-descomponibles).La cantidad de datos que se lee dismi-nuye de manera significativa al calcular los agregados a partir de otros agregados, en lugar de hacerlo apartir de la relacion original. Se pueden conseguir otras mejoras; por ejemplo. se pueden calcular variasagrupaciones con una sola lectura de los datos. Veanse las notas bibliograficas para hallar referencias alos algoritmos para el calculo eficiente de cubos de datos.

Las primeras implementaciones OLAP calculaban previamente los cubos de datos completes. es decir,las agrupaciones por todos los subconjuntos de los atributos de dimension, y los almacenaban. El calculoprevio permite que las consultas OLAP se respondan en pocos segundos, incluso para conjuntos dedatos que pueden contener millones de hlp las que suponen gigabytes de datos. No obstante, hay 2 7 1

agrupaciones con n atributos de dimensi6n; las jerarquias de los atributos aumentan mas aun el numero.En consecuencia, todo el cubo de datos suele ser mayor que la relacion original que 10 genero y, enmuchos casos, no resulta posible almacenarlo entero.

En lugar de calcular previamente todas las agrupaciones posibles y almacenarlas, resulta razonablecalcular previamente algunas de las agrupaciones y almacenarlas y calcular el resto segun se soliciten.En lugar de calcular las consultas a partir de la relaci6n original, 10 que puede tardar mucho tiempo,se pueden calcular a partir de otras consultas calculadas previamente. Por ejemplo, sup6ngase que unaconsulta necesita resumenes segun (nombre_art iculo , color),que no se ha calculado con anterioridad. Elresultado de la consulta puede calcularse a partir de resumenes segun (nombre_art iculo , color, ta l la) ,si yase ha calculado. Veanse las notas bibliograficas para hallar referencias al modo de seleccionar para sucalculo previo un buen conjunto de agrupaciones, dados los lfmites de almacenamiento disponible para

los resultados calculados previamente.Los datos de los cubos no se pueden generar mediante una sola consulta SQLutilizando las estruc-

turas basicas group by, ya que los agregados se calculan para varias agrupaciones diferentes de losatributos de dimensi6n. EI Apartado 14.2.3 estudia las extensiones de SQLpara el soporte de la funcio-nalidad OLAP.

14.2.3 Agregacion extend idaLa funcionalidad de agregaci6n de SQL-92esta limitada, por 10 que diferentes sistemas de bases dedatos han implementado varias extensiones. No obstante, la norma SQL:1999define un amplio conjuntode funciones de agregaci6n, que se describen en este apartado y en los dos siguientes. Las bases de datosde Oracle y de DB2de IBM soportan la mayor parte de estas caracteristicas y, sin duda, otras bases dedatos soportaran estas caracterfsticas en un futuro pr6ximo.

Las nuevas funciones de agregaci6n para un solo atributo son la desviaci6n estandar y la varianza(stddev y variance). La desviacion estandar es la raiz cuadrada de la varianza/. Algunos sistemas de

bases de datos soportan otras funciones de agregaci6n como la mediana y la moda. Algunos sistemasde bases de datos incluso perrniten que los usuarios afiadan nuevas funciones de agregaci6n.

2. La norma SQL:1999 soporta en real idad dos t ipos de varianza , denominadas tmr ia n zu d e I II .poblacitm y u ar ia nm d e l a m ue sira y,par tanto, dos tipos de desviacion estandar, La definicion de los dos tipos difiere ligeramente; los detalles se pueden consul tar en

cualquier libro de texto de estadistica.


8/31


SQL:1999arnbien soporta una nueva clase de funciones de agregacion binarias, que pueden calcularresultados estadisticos para parejas de atributos; entre ellas estan las correlaciones, las covarianzas ylas curvas de regresion, que dan una linea que aproxima la relacion entre los valores de la pareja de

atributos. Las definiciones de estas funciones pueden hallarse en cualquier libro de texto estandar, comolos que se citan en las notas bibliograficas.SQL:1999ambien soporta generalizaciones de la estructura group by, mediante las estructuras cube

y rollup. Un uso representativo de la estructura cube es el siguiente:

select nomb re_ ar ti cu lo , c o lo r , i a ll a, s um(nume ro )from ventasgroup by cube (nomb re_ ar ti cu lo , c o lo r , t al la )

Esta consulta calcula la union de ocho agrupaciones diferentes de la relaci6n ventas:

{ ( nomb re_ ar ti cu lo , c o lo r , t al la ), ( nomb re_ ar ti cu lo , c o lo r ), ( nomb re_ ar ti cu lo , taUa ),( co lo r, t a ll a ), (nombre_a rt icu lo ) , ( co lo r ), ( ta l la ) ,0 I

donde 0 denota una lista group by vacia.Para cada agrupacion el resultado contiene el valor nulo para los atributos no presentes en la agru-

paci6n. Par ejemplo, la tabla de la Figura 14.2,sustituyendo all par null, la puede calcular la consulta

select n ombr e a rti cu lo , c o lo r, s um (n ume ro )from ventasgroup by cube (nombr e_a r ti cu lo , c o lo r )

Una estructura rollup representativa es:

select n ombr e a rti cu lo , c ol or , i all a, s um (m ime ro )from ueniasgroup by r o ll up (nomb re_ ar ti cu lo , c o lo r , t al la )

En este caso solo se han generado cuatro agrupaciones:

{ t nomb re a r ii cu lo , c o lo r , t al la ), ( nomb re_ ar ti cu lo , c o lo r ), ( nomb re_ ar ti cu lo ),0 I

Lainstrucci6n rollup puede utilizarse para generar agregados en varios niveles de una jerarquia parauna columna. Por ejemplo, supongase que se tiene la tabla c a ie go ri a ar ti cu lo tnomb re a rt ic u lo , c a ie go ri a)queda la categoria de cada articulo. La consulta

select c ai eg o ri a, n omb re a ri ic ul o, s um (n ume ro )from tenias, caiegoriaarticulowhere ventas.nombre_articulo= categoriaarticulo.nombrepriicuiogroup by ro llup (ca tegor ia , nombre_a r ti culo )

da un resumen jerarquico segun nombre_articuloy segun caiegor ia .Sepueden utilizar varios rollup y varios cube en una sola clausula group by. Por ejemplo, la consulta

siguiente:

select n omb re a rti cu lo , c ol or , ta ll a, s um (n ume ro )from ventasgroup by rollup(nombre_artfculo), roHup(color, talla)

genera las agrupaciones

{ ( nomb re_ ar ti cu lo , c o lo r , t al la ), ( nomb re_ ar ti cu lo , c o lo r ), ( nomb re_ ar ti cu lo ),( colo r, t a ll a ), ( co lo r ),0 I


9/31


Para comprender el motive hay que tener en cuenta que rollup(nombre_articulo)genera dos agrupacio-nes, ((nombre_articulo),01 ,y que r o ll up (c o lo r , t al la )genera tres agrupaciones. ( co lo r, t a ll a ), ( co lo r ),0 ). El

producto cartesiano de los dos da como resultado las seis agrupaciones mostradas.Como ya se ha mencionado en el Apartado 14.2.1, SQL:1999u tiliza el valor null para indicar el sentidohabitual de nulo as! como all. Este uso dual de null puede generar ambigiiedad si los atributos utilizadosen una clausula rollup 0 en una clausula cube contienen valores nulos. Se puede aplicar la funci6ngrouping a un atributo; devuelve 1 si el valor es un valor nulo que represente a all, y devuelve 0 en losdemas casos. Considerese la consul ta siguiente:

select nomb re a r ti cu lo , c o lo r , t a ll a, s um(nume ro ),grouping(nombre_ar t iculo)as indicador_nombre_articulo,grouping(color) as indicadorcolor,grouping(talla) as indicador_talla

from ventasgroup by cube (nombre_a r ti culo , co lor, t a ll a )

El resultado es el rnismo que en la versi6n de la consulta sin grouping, pero con tres columnas adiciona- .

les denominadas indicador_nombre_ar t fculo , indicador_colore indicador_talla.En cada tupla el valor de loscampos indicador es 1 si el campo correspondiente es un valor nulo que representa a all.

En lugar de utilizar etiquetas para indicar los valores nulos que representan a all, se pueden sustituirlos valores nulos por un valor a la elecci6n del usuario:

decode(grouping(nombre_articulo), 1, 'todos', nombre_articulo)

Esta expresi6n devuelve el valor "todos" si el valor de nombre_articuloes un valor nulo que se correspon-da con all, y devuelve el valor real de nombre articulo en caso contrario. Esta expresi6n puede utilizarseen lugar de nombre_articuloen la clausula select para obtener "todos" en el resultado de la consulta, enlugar de valores nulos que representen a all.

Ni la clausula rollup ni la clausula cube ofrecen un control completo de las agrupaciones que segeneran. Por ejemplo, no se pueden utilizar para especificar que s610 se de sean las agrupaciones (color,ta l la) , ( ia lia , nombre_ar t iculo)).Estas agrupaciones restringidas pueden generarse utilizando la estructuragrouping en la clausula having; los detalles se dejan como ejercicio para ellector.

14.2.4 Clasificaci6n

Hallar la posici6n de un valor en un conjunto mas grande es una operaci6n frecuente. Por ejernplo,puede que se desee asignar una clasificaci6n a los estudiantes de acuerdo con sus notas totales, conel puesto 1 para el estudiante con las notas mas altas, el puesto 2 para el estudiante con las segundasmejores notas, etc. Aunque estas consultas pueden expresarse en SQL-92, resultan diffciles de expresar eineficientes a la hora de la evaluaci6n. Los programadores suelen recurrir a escribir en parte la consultaen SQL y en parte en un lenguaje de programaci6n. Un tipo de consulta relacionado es la busqueda delpercentil que le corresponde a W1 valor de un (multi)conjunto, por ejemplo, el tercio inferior, el terciocentral 0 el tercio superior. Aqui se estudiara el soporte de SQL:1999 para estos tipos de consultas.

La clasificaci6n se realiza conjuntamente con una especificaci6n order by. Sup6ngase que se tiene unarelaci6n no tas_estud iante (id_es tud ian te , no tas )que almacena las notas obtenidas por cada estudiante. Laconsulta siguiente da la clasificaci6n de cada estudiante.

select id_estudiante,rankf) over (order by (notas)dese) as clasijicacionefrom notas_estudiante

Observese que el orden de las tuplas en el resultado no se ha definido, por 10 que puede que no estenordenadas segun su clasificaci6n. Se necesita una clausula order by adicional para dejarlas ordenadas,como puede verse a continuaci6n.

select id_estudiante,rank 0 over (order by (notas)dese) as clasificacionefrom notas_estudianteorder by c la si ji cacion e


10/31


11/31


funci6n resulta especialmente util para la creaci6n de histogramas basados en percentiles. Por ejemplo,se pueden ordenar los empleados por su salario y utilizar ntile(3) para hallar el rango (tercio inferior,tercio central 0 tercio superior) en el que se halla cada empleado, y para calcular el salario total ganadopor los empleados de cada rango:

select ierci l , sum(sueldo)from (

select sueldo,ntile(3) over (order by (sueldo)) as tereilfrom empleado)as s

group by tereil

La presencia de valores nulos puede complicar la definicion de la clasificacion, dado que no esta clarosi deben colocarse antes en el orden. SQL:1999 permite que el usuario especifique donde deben aparecermediante nulls first 0 nulls last, por ejemplo:

select id_estudiante, rank 0 over (order by notas desc nulls last) as clasifieaei6n_efrom notas_estudiante

14.2.5 VentanasUn ejemplo de consulta ueniana es una consulta que, dados los valores de ventas para cada fecha, calculapara cada fecha el promedio de ventas de ese dia, del dia anterior y del dia siguiente; esas consultasde media movil se utilizan para suavizar las variaciones aleatorias. Otro ejemplo de consulta ventanaes la consulta que calcula el saldo acumulado de una cuenta, dada una relacion que especifique lasimposiciones y las retiradas de fondos de la cuenta. Esas consultas resultan dificiles 0 imposibles deexpresar (depende de la consulta en concreto) en SQL basico.

SQL:1999 ofrece una caracteristica de ventanas para soportar esas consultas. A diferencia de group by,la misma tupla puede estar en varias ventanas. Sup6ngase que se tiene la relaci6n t ra n sa e ci 6n tnumero_ cu en ta , fe ch a h o ra , v alo r),donde valor es positive para las imposiciones de fondos y negativo para lasretiradas. Se da por supuesto que hay como maximo una transaccion por cada valor fecha_hora.

Considerese la consulta

select numerocuenia, [echahora,sum(valor) over

(partition by numerocueniaorder by fecha_horarows unbounded preceding)

as saldofrom transacci6norder by numerocuenia, [echa hora

La consulta da los saldos acumulados de cada cuenta justo antes de cada transacci6n en esa cuenta; elsaldo acumulado de una cuenta es la suma de valores de todas las transacciones anteriores de la cuenta.

La clausula partition by separa las tuplas por ruimero de cuenta, de modo que para cad a fila s610se consideren las tuplas de su particion. Se crea una ventana para cada tupla; las palabras clave rowsunbounded preceding especifican que la ventana de cada tupla consiste en todas las tuplas de la par-tici6n que la preceden en el orden especificado (en este caso, orden creciente de fecha_hora).La funci6n

de agregaci6n sum(valor) se aplica a todas las tuplas de la ventana. Observese que la consulta no utilizaninguna clausula group by, ya que hay una tupla de resultado por cad a tupla de la relaci6n transacci6n.

Aunque la consulta puede escribirse sin las estructuras ampliadas, sena bastante dificil de forrnu-lar. Observese tambien que se pueden superponer diferentes ventanas, es decir, una tupla puede estarpresente en mas de una ventana.

Se pueden especificar otros tipos de ventanas. Por ejemplo, para obtener una ventana que contengalas 10 filas anteriores a cada fila, se puede especificar rows 10 preceding. Para obtener una ventanaque contenga la fila actual, la anterior y la siguiente se puede utilizar between rows 1 preceding and1 following. Para obtener las filas siguientes y la fila actual se puede decir between r~ws unbounded


12/31

466 Capitulo 14 Analisis y minerfa de datos

cargadores ~de datos

8origen de datos 1

origen de datos 2 8SGBD

herramientas deconsulta y analisis

origen de datos nalmacen de datos

Figura 14.6 Arquitectura de los almacenes de datos.

preceding and current. Observese que si la ordenaci6n se realiza sobre un atributo que no sea clave el

resultado no es determinista, ya que el orden de las tuplas no esta definido completamente.Se pueden especificar ventanas mediante rangos de valores, en lugar de hacerlo mediante numero de

filas. Por ejemplo, sup6ngase que el valor de ordenaci6n de una tupla es v; entonces, range between 10preceding and current row devol vera tuplas cuyo valor de ordenaci6n se halle entre v - 10 Y v (ambosvalores inclusive). Al tratar con fechas se puede utilizar range interval 10 day preceding para obteneruna ventana que contenga tuplas con los 10 dias anteriores, pero sin incluir la fecha de la tupla.

Evidentemente, la funcionalidad de ventanas de SQL:1999 es mucho mas rica y puede utilizarse paraescribir consultas bastante complejas con poco esfuerzo.

14.3 Almacenes de datosLas grandes empresas tienen presencia en muchos lugares, cada uno de los cuales puede generar ungran volumen de datos. Por ejemplo, las cadenas de tiendas minoristas poseen centenares 0 millaresde tiendas, mientras que las compafiias de seguros pueden tener datos de mill ares de oficinas locales.

Adernas, las organizaciones grandes tienen una estructura compleja de organizaci6n interna y, por tanto,puede que los diferentes datos se hallen en ubicaciones, sistemas operativos 0 bajo esquemas diferentes.Por ejemplo, puede que los datos de los problemas de fabricaci6n y los datos sobre las quejas de losclientes estell. almacenados en diferentes sistemas de bases de datos. Los encargados de adoptar lasdecisiones empresariales necesitan tener acceso a la informaci6n de todos esos origenes. La formulaci6nde consultas a cada uno de los origenes es a la vez engorrosa e ineficiente. Ademas, puede que losorigenes de datos s6lo almacenen los datos actuales, mientras que es posible que los encargados deadoptar las decisiones empresariales necesiten tener acceso tambien a datos anteriores, por ejemplo,informacion sobre la manera en que se han modificado las pautas de compra el afio pasado puederesultar de gran importancia. Los almacenes de datos proporcionan una soluci6n a estos problemas.

Los almacenes de datos (data warehouses) son dep6sitos (0 archivos) de informaci6n reunida de va-rios origenes, almacenada bajo un esquema unificado en un solo sitio. Una vez reunida, los datos sealmacenan mucho tiempo, 10 que permite el acceso a datos hist6ricos. Asi, los almacenes de datos pro-porcionan a los usuarios una sola interfaz consolidada con los datos, por 10 que las consultas de ayudaa la toma de decisiones resultan mas faciles de escribir. Ademas, al tener acceso a la informaci6n para laayuda de la toma de decisiones desde un almacen de datos, el encargado de adoptar las decisiones seasegma de que los sistemas de procesamiento en linea de las transacciones no se yean afectados por lacarga de trabajo de la ayuda de la toma de decisiones. '

14.3.1 Componentes de los almacenes de datos

La Figura 14.6 muestra la arquitectura de un almacen de datos tipico e ilustra la recogida de los datos,su almacenamiento y el soporte de las consultas y del analisis de datos. Entre los problemas que hayq~e resolver al crear un almacen de datos estan los siguientes:


13/31

14.3 Almacenes de datos 467

Momento y modo de la recogida de datos. En una arquitectura. dirigida por los origenes para larecogida de los datos, los origenes de los datos transmiten la informaci6n nueva, bien, de maneracontinua (amedida que se produce.el procesamiento de las transacciones) 0 de manera peri6dica(de neche, por ejemplo). En una arquitectura dirigida por eldestino, el almacen de datos enviade manera peri6dica solicitudes de datos nuevos a los origenes de datos.

A menos que lasactualizaciones de los origenes de datos se repliquen en el almacen de datosmediante un compromiso de dos fases, el almacen de datos nunca estara actualizado respecto alos orfgenes de datos. El compromiso de dos fases suele resultar demasiado costoso para ser unaopci6n aceptable, por 10 que los almacenes de datos suelen tener datos ligeramente desactuali-zados. Eso, no obstante, no suele suponer un problema para los sistemas de ayuda a la toma dedecisiones.

Selecci6n del esquema. Es probable que los orfgenes de datos que se han creado de maneraindependiente tengan esquemas diferentes. De hecho, puede que utilicen diferentes modelos dedatos. Parte de la labor de los almacenes de datos es llevar a cabo la integraci6n de los esquemasy convertir los datos al esquema integrado antes de almacenarlos. En consecuencia, los datosalmacenados en el almacen de datos no son una mera copia de los datos de los origenes de datos.Por el contrario, se pueden considerar como una vista materializada de los datos de los origenesde datos.

Transformaci6n y limpieza de los datos. La labor de corregir y realizar un procesamiento previode los datos se denomina limpieza de los datos. Los origenes de datos suelen entregar datos connumerosas inconsistencias de caracter menor, que pueden corregirse. Por ejemplo, los nombressuelen estar mal escritos y pueden que las direcciones tengan mal escritos los nombres de la calle,del distrito 0 de la ciudad, 0 puede que los c6digos postales se hayan introducido de maneraincorrecta. Esto puede corregirse en un grado razonable consultando una base de datos de losnombres de las calles y de los c6digos postales de cada ciudad. El encaje aproximado de losdatos requeridos para esta tarea se conoce como busqueda difusa.

Las listas de direcciones recogidas de varios origenes pueden tener duplicados que haya queeliminar en una operaci6n de mezc1a-purga (esta operaci6n tambien se conoce como desdupli-caci6n). Los registros de varias personas de una misma casa pueden agruparse para que s610serealice a cada casa un envio de correo; esta operaci6n se denomina domiciliaci6n.

Los datos se pueden transformar de otras formas ademas de la Iimpieza, como cambiar lasunidades de medida 0 convertir los datos a un esquema diferente reuniendo datos de relacionesde varios origenes. Los almacenes de los datos tienen normalmente herramientas graficas paradar soporte a la transformaci6n de datos. Estas herramientas permiten que la transformaci6nse especifique con cuadros, y se puede crear arcos para indicar el flujo de datos. Los cuadroscondicionales pueden encaminar datos al siguiente paso apropiado en la transformaci6n. Veaseen la Figura 29.7un ejemplo de una transformaci6n especificada usando la herramienta graficaproporcionada por SQLServer de Microsoft.

Propagaci6n de las actualizaciones. Las actualizaciones de las relaciones en los origenes de datosdeben propagarse a los almacenes de datos. Si las relaciones en los almacenes de datos son exac-tamente las mismas que en los origenes de datos, la propagaci6n es directa. En caso contrario, elproblema de la propagaci6n de las actualizaciones es basicamente el problema del mantenimientod e l as v is ta sque se estudi6 en el Apartado 14.5.

Resumenes de los datos. Los datos brutos generados por un sistema de procesamiento de tran-sacciones pueden ser demasiado grandes para almacenarlos en linea. No obstante, se puedenresponder muchas consultas manteniendo unicamente datos resumen obtenidos por agregaci6nde las relaciones, en lugar de mantener las relaciones enteras. Por ejemplo, en lugar de almacenarlos datos de cada venta de ropa, se pueden almacenar las ventas totales de ropa por nombre dearticulo y por categoria.

Sup6ngase que la relaci6n r ha sido sustituida por la relaci6n resumen s. Todavia se puedepermitir a los usuarios que planteen consultas como si la relaci6n r estuviera disponible en li-


14/31

466 Capitulo 14 Analisis y minerla de datos

cargadores ~de datos

8

8

oxigen de datos 1

origen de datos 2

SGBDherramientas deconsulta y analisis

or igen de datos 17almacen de datos

Figura 14.6 Arquitectura de los almacenes de datos.

preceding and current. Observese que si la ordenaci6n se realiza sobre un atributo que no sea clave el

resultado no es determinista, ya que el orden de las tuplas no esta definido completamente.Se pueden especificar ventanas mediante rangos de valores, en lugar de hacerlo mediante numero de

filas. Por ejemplo, supongase que el valor de ordenacion de una tupla es v; entonces, range between 10preceding and current row devolvera tuplas cuyo valor de ordenaci6n se halle entre v - 10Y v (ambosvalores inclusive). Al tratar con fechas se puede utilizar range interval 10 day preceding para obteneruna ventana que contenga tuplas con los 10 dias anteriores, pero sin incluir la fecha de la tupla.

Evidentemente, la funcionalidad de ventanas de SQL:1999 es mucho mas rica y puede utilizarse paraescribir consultas bastante complejas con poco esfuerzo.

14.3 Almacenes de datos

Las grandes empresas tienen presencia en muchos lugares, cada uno de los cuales puede generar ungran volumen de datos. Por ejemplo, las cadenas de tiendas minoristas poseen centenares 0 millaresde tiendas, mientras que las compafuas de seguros pueden tener datos de millares de oficinas locales.Ademas, las organizaciones grandes tienen una estructura compleja de organizaci6n interna y,por tanto,puede que los diferentes datos se hallen en ubicaciones, sistemas operativos 0 bajo esquemas diferentes.Por ejemplo, puede que los datos de los problemas de fabricacion y los datos sobre las quejas de losclientes esten almacenados en diferentes sistemas de bases de datos. Los encargados de adoptar lasdecisiones empresariales necesitan tener acceso a la informaci6n de todos esos origenes. La formulaci6nde consultas a cada uno de los orfgenes es a la vez engorrosa e ineficiente. Ademas, puede que losorigenes de datos s6lo almacenen los datos actuales, mientras que es posible que los encargados deadoptar las decisiones empresariales necesiten tener acceso tambien a datos anteriores, por ejemplo,informacion sobre la manera en que se han modificado las pautas de compra el afio pasado puederesultar de gran importancia. Los almacenes de datos proporcionan una solucion a estos problemas.

Los almacenes de datos (data warehouses) son depositos (0 archivos) de informaci6n reunida de va-rios origenes, almacenada bajo un esquema unificado en un solo sitio. Una vez reunida, los datos sealmacenan mucho tiempo, 10 que permite el acceso a datos hist6ricos. Asi, los almacenes de datos pro-porcionan a los usuarios una sola interfaz consolidada con los datos, por 10 que las consultas de ayudaa la toma de decisiones resultan mas faciles de escribir. Ademas, al tener acceso a la informaci6n para laayuda de la toma de decisiones desde un almacen de datos, el encargado de adoptar las decisiones seasegura de que los sistemas de procesamiento en linea de las transacciones no se yean afectados por lacarga de trabajo de la ayuda de la toma de decisiones. '

14.3.1 Componentes de los almacenes de datos

La Figura 14.6muestra la arquitectura de un almacen de datos tipico e ilustra la recogida de los datos,su almacenamiento y el soporte de las consultas y del analisis de datos. Entre los problemas que hayq~e resolver al crear un almacen de datos estan los siguientes:


15/31

14.3 Almacenes de datos 467

Momento y modo de la recogida de datos. En una arquitectura. dirigida por los origenes para larecogida de los datos, los orfgenes de los datos transmiten la informaci6n nueva, bien, de maneracontinua (amedida que se produce.el procesamiento de las transacciones) 0 de manera peri6dica

(de noche, por ejemplo). Enuna arquitectura dirigida por eldestino, el almacen de datos envfade manera peri6dica solicitudes de datos nuevos a los orfgenes de datos.

A menos que lasactualizaciones de los orfgenes de datos se repliquen en el almacen de datosmediante un compromiso de dos fases, el almacen de datos nunca estara actualizado respecto alos origenes de datos. El compromiso de dos fases suele resultar demasiado costoso para ser unaopci6n aceptable, por 10que los almacenes de datos suelen tener datos ligeramente desactuali-zados. Eso, no obstante, no suele suponer un problema para los sistemas de ayuda a la toma dedecisiones.

Seleccion del esquema. Es probable que los orfgenes de datos que se han creado de maneraindependiente tengan esquemas diferentes. De hecho, puede que utilicen diferentes modelos dedatos. Parte de la labor de los almacenes de datos es llevar a cabo la integraci6n de los esquemasy convertir los datos al esquema integrado antes de almacenarlos. En consecuencia, los datosalmacenados en el almacen de datos no son una mera copia de los datos de los orfgenes de datos.

Por el contrario, se pueden considerar como una vista materializada de los datos de los ongenesde datos.

Transformacion y limpieza de los datos. La labor de corregir y realizar un procesamiento previode los datos se denomina limpieza de los datos. Los orfgenes de datos suelen entregar datos connumerosas inconsistencias de caracter menor, que pueden corregirse. Por ejemplo, los nombressuelen estar mal escritos y pueden que las direcciones tengan mal escritos los nombres de la calle,del distrito 0 de la ciudad, 0 puede que los c6digos postales se hayan introducido de maneraincorrecta. Esto puede corregirse en un grado razonable consultando una base de datos de losnombres de las calles y de los c6digos postales de cada ciudad. El encaje aproximado de losdatos requeridos para esta tarea se conoce como busqueda difusa.

Las listas de direcciones recogidas de varios origenes pueden tener duplicados que haya queeliminar en una operacion de mezc1a-purga (esta operaci6n tambien se conoce como desdupli-cacion). Los registros de varias personas de una misma casa pueden agruparse para que s610se

realice a cada casa un envfo de correo; esta operaci6n se denomina domiciliacion.Los datos se pueden transformar de otras formas adernas de la limpieza, como cambiar las

unidades de medida 0 convertir los datos a un esquema diferente reuniendo datos de relacionesde varios orfgenes. Los almacenes de los datos tienen normalmente herramientas graficas paradar soporte a la transformaci6n de datos. Estas herramientas permiten que la transformacionse especifique con cuadros, y se puede crear arcos para indicar el flujo de datos. Los cuadroscondicionales pueden encaminar datos al siguiente paso apropiado en la transformaci6n. Veaseen la F.igura29.7 un ejemplo de una transformaci6n especificada usando la herramienta graficaproporcionada por SQLServer de Microsoft.

Propagacion de las actualizaciones. Las actualizaciones de las relaciones en los orfgenes de datosdeben propagarse a los almacenes de datos. Si las relaciones en los almacenes de datos son exac-tamente las mismas que en los orfgenes de datos, la propagaci6n es directa. En caso contrario, elproblema de la propagaci6n de las actualizaciones es basicamente el problema del manienimientod e l as v is ta sque se estudi6 en el Apartado 14.5.

Resumenes de los datos. Los datos brutos generados por un sistema de procesamiento de tran-sacciones pueden ser demasiado grandes para almacenarlos en linea. No obstante, se puedenresponder muchas consultas manteniendo unicamente datos resumen obtenidos por agregaci6nde las relaciones, en lugar de mantener las relaciones enteras. Par ejemplo, en lugar de almacenarlos datos de cada venta de ropa, se pueden a1macenar las ventas totales de ropa por nombre dearticulo y par categoria.

Sup6ngase que la relaci6n T ha sido sustituida por la relaci6n resumen 8. Todavfa se puedepermitir a los usuarios que planteen consultas como si la relaci6n T estuviera disponible en 11-


16/31

468 Capitulo 14 Analisis y mineria de da tos

nea. Si la consulta s610 necesita datos resumidos, puede que sea posible transformarla en unaequivalente utilizando sen lugar de T; vease el Apartado 14.5.

Los distintos pasos implicados en obtener datos a partir de un almacen de los datos se denominan ex-tracci6n, transformaci6n y carga 0 tareas ETC;la extracci6n se refiere a conseguir datos de los origenes,mientras que la carga refiere a cargar los datos en el almacen de datos.

14.3.2 Esquemas de los almacenes de datos

Los almacenes de datos suelen tener esquemas disefiados para el analisis de los datos y emplean he-rramientas como las herramientas OLAP. Por tanto, los datos suelen ser datos multidimensionales, conatributos de dimensi6n y atributos de medida. Las tablas que contienen datos multidimensionales sedenominan tablas de hechos y suelen ser de gran tamafio. Las tablas que registran informaci6n de ven-tas de una tienda minorista, con una tupla para cada articulo a la venta, son un ejemplo tfpico de tablasde hechos. Las dimensiones de la tabla ventas incluyen 10que es el articulo (generalmente un identifica-dor del articulo como el utilizado en los c6digos de barras), la fecha en que se ha vendido, la ubicaci6n(tienda) en que se vendi6, el cliente que 10ha comprado, etc. Entre los atributos de medida pueden estarel nurnero de articulos vendidos y el precio de cada articulo.

Para minimizar los requisitos de almacenamiento los atributos de dimensiones suelen ser identifica-dores breves que actuan de c1aves externas en otras tablas denominadas tablas de dimensiones. Porejemplo, la tabla de hechos ventas tiene los atributos i d_a rt icu lo~ id_t ienda, id_c l ien tey fecha y los atributosde medida numero y precio. El atributo idiienda es una clave externa en la tabla de dimensiones t ienda,que tiene otros atributos como la ubicaci6n de la tienda (ciudad, estado, pais). El atributo idarticulo de latablaventas es una clave externa de la tabla de dimensiones info_artfculo, que contiene informaci6n comoel nombre del articulo, la categoria a la que pertenece el articulo y otros detalles del articulo como elcolor y la talla. El atributo id_cliente es una clave externa de la tabla clienie, que contiene atributos comoel nombre y la direcci6n de los clientes. Tambien se puede ver el atributo [echa como clave externa de latabla infoJecha, que da el mes, el trimestre yel ario de cada fecha.

El esquema resultante aparece en la Figura 14.7. Un esquema as1,con una tabla de hechos, variastablas de dimensiones y c1avesexternas procedentes de la tabla de hechos en las tablas de dimensiones,

se denomina esquema en estrella. Los disenos complejos de almacenes de datos pueden tener variosniveles de tablas de dimensiones; por ejemplo, la tabla infoarticulo puede tener un atributo idJabricanteque es clave externa en otra tabla que da detalles del fabricante. Estos esquemas se denominan esquemasen copo de nieve. Los disefios complejos de almacenes de datos pueden tener tambien mas de una tablade hechos.

almaceni n fo rmac ion _a rt icu lo

idolmacen

. .

id_articulo

~ventasciudad

nombre_articulo poblaci6ncolor id_articulo provinciatalla id_almacencategoria id_cliente

~cliente

;nfimn""wn_ft~

fechanumero id_clienteprecio nombre

callefechaciudadmespoblacumtrimestre

anoc6digo_postalprovincia

Figura 14.7 Esquema en estrella de un almacen de datos.


17/31

14.4 Mineria de datos 469

14.4 Mineria de datosEl terrnino mineria de datos (data mining) hace referencia vagamente al proceso de analisis semiauto-

matico de bases de datos de gran tamafio para hallar estructuras utiles. Al igua1 que 1a busqueda deconocimiento en 1ainte1igencia artificial (tambien denominada aprendizaje de 1amaquina) , 0 el anal isisestadistico, la mineria de datos intenta descubrir reglas yestructuras a partir de los datos. No obstan-te, la mineria de datos se diferencia del aprendizaje de la maquina y de la estadistica en que trata congrandes vohimenes de datos, almacenados sobre todo en disco. Es decir, la mineria de datos trata de la"busqueda de conocimiento en las bases de datos".

Algunos tipos de conocimiento descubiertos a partir de una base de datos pueden representarse porun conjunto de reglas. A continuacion se ofrece un ejemplo de regIa, formulada de manera informal:"Las mujeres jovenes con ingresos anuales superiores a 50.000 son las personas que con mayor proba-bilidad compran coches deportivos de pequefio tamafio". Por supuesto, estas reglas no son verdaderasde modo universal, y tienen grados de "soporte" y de "confianza" como se estudiara mas adelante.Otros tipos de conocimiento se representan por ecuaciones que relacionan entre S 1 diferentes variables,o mediante otros mecanismos de prediccion de resultados cuando se conocen los valores de algunas

variables.Hay gran variedad de tipos posibles de estructuras que pueden resultar utiles, y se emplean diferentes

tecnicas para hallar tipos diferentes de estructuras. Se estudiaran unos cuantos ejemplos de estructurasy se vera el modo en que pueden obtenerse de manera automatics de las bases de datos.

Suele haber una parte manual en la mineria de datos, que consiste en el preprocesamiento de los datoshasta una forma aceptable para los algoritmos, y en el posprocesamiento de las estructuras descubiertaspara hallar otras nuevas que puedan resu1tar utiles, Tambien puede haber mas de un tipo de estructuraque se pueda descubrir a partir de una base de datos dada, y puede que se necesite la interaccion ma-nual para escoger los tipos de estructuras utiles. Por este motivo, 1a mineria de datos es rea1mente unproceso semiautomatico en 1av ida reaL No obstante, la descripci6n que sigue se centrara en el aspectoautomatico de la minerfa.

14.4.1 Aplicaciones de la mineria de datos

La informaci6n hall ada tiene numerosas aplicaciones. Las aplicaciones mas utilizadas son las que ne-cesitan algun tipo de predicci6n. Por ejemplo, cuando una persona solicita una tarjeta de credito, lacompania emisora quiere predecir si la persona constituye un buen riesgo de credito. La predicci6n he-ne que basarse en los atributos conocidos de la persona, como la edad, sus ingresos, sus deudas y suhistorial de pago de deudas, Las reglas para realizar 1ap redicci6n se deducen de los mismos atributosde titulares de tarjetas de credito pasados y actuales, junto con su conducta observada, como puede sersi han dejado de pagar los cargos de su tarjeta de credito. Entre otros tipos de predicci6n esta la de losclientes que puedan elegir a un competidor (puede que se ofrezca a esos clientes descuentos especialespara intentar que no se cambien), la predicci6n de 1a gente que pueda responder a correo publicitario("correo basura") 0 la predicci6n de los us os de tarjetas telefonicas que puedan resultar fraudulentos.

Otra clase de aplicaciones busca asociaciones, por ejemplo, los libros que se suelen comprar a la vez.

Si un c1iente compra un libro, puede que la libreria en linea le sugiera otros libros asociados. Si unapersona compra una camara, puede que el sistema sugiera accesorios que suelen comprarse junto a lascamaras. Un buen vendedor esta atento a esas tendencias y las aprovecha para realizar mas ventas. Eldesafio consiste en automatizar el proceso. Puede que otros tip os de asociaci6n Ileven al descubrimientode relaciones causa -efecto. Por ejemplo, el descubrimiento de asociaciones inesperadas entre un me-dicamento recien introducido y los problemas cardiacos llevo al hallazgo de que el medicamento puedecausar problemas cardiacos en algunas personas. E1medicamento se retir6 del mercado,

Las asociaciones son un ejemplo de patrones descriptivos. Las agrupaciones son otro ejemplo deeste tipo de patrones. Por ejemplo, hace mas de un siglo se descubri6 una agrupaci6n de casos de fiebretifoidea alrededor de un pozo, 10que llevo al descubrimiento de que e1agua del pozo estaba contamina-da y estaba difundiendo la fiebre tifoidea. La detecci6n de agrupaciones de enfermedades sigue siendoimportante hoy en dfa.


18/31


14.4.2 Clasfficacion

Como ya se mencion6 en el Apartado 14.4.1, la predicci6n es uno de los tipos mas importantes de mi-neria de datos. Se describira 10que es la clasificaci6n, se estudiaran tecnicas para la creaci6n de un tipode clasificadores, denominados clasificadores de arboles de decisi6n, y se estudiaran otras tecnicas depredicci6n.

De manera abstracta, el problema de la clasificaci6n es el siguiente: dado que los elementos per-tenecen a una de las clases, y dados los casos pasados (denominados ejemplos de formaci6n) de loselementos junto con las dases a las que pertenecen, el problema es predecir la clase a la que perteneceun elemento nuevo. La clase del caso nuevo no se conoce, por 10que hay que utilizar los demas atributosdel caso para predecir la clase.

La clasificaci6n se puede llevar a cabo hallando reglas que dividan los datos dados en grupos dis-juntos. Por ejemplo, sup6ngase que una compafua de tarjetas de credito quiera decidir si debe concederuna tarjeta a un solicitante. La compafiia tiene amplia informaci6n sobre esa persona, como puede ser suedad, su nivel educative, sus ingresos anuales y sus deudas actuales, la cual puede utilizar para adoptaruna decisi6n.

Parte de esta informaci6n puede ser importante para el valor de credito del solicitante, mientras quepuede que otra parte no 10sea. Para adoptar la decisi6n la compafiia asigna un nivel de valor de creditode excelente, bueno, mediano 0 malo a cada integrante de un conjunto de muestra de clientes aciualessegun su historial de pagos. Luego, la comparua intenta hallar reglas que dasifiquen a sus clientes actua-les como excelentes, buenos, medianos 0 malos con base en la informaci6n sobre esas personas diferentede su historial de pagos actual (que no esta disponible para los clientes nuevos). Considerense 5610dosatributos: el nivel educativo (la titulaci6n mas alta conseguida) y los ingresos. Las reglas pueden ser dela forma siguiente:

'Vpe r sonaP, P. ti tu l ac ion = master and Piinqresos > 75.000=} P. cr e dito = excelente

'Vpe1"SOnaP,Piiiiulacion. = achiller or(P.i-ngresos 2 : 25.000 and P.in gTeso s ::;75.000) =} Pi c re d ito = buena

Tambien aparecen reglas parecidas para los dernas niveles de valor de credito (mediano y malo).EI proceso de creaci6n de dasificadores comienza con una muestra de los datos, denominada con-

junto de formaci6n. Para cada tupla del conjunto de formaci6n ya se conoce la clase a la que pertenece.Por ejemplo, el conjunto de formaci6n de las solicitudes de tarjetas de credito pueden ser los clientes yaexistentes, con su riesgo crediticio determinado a partir de su historial de pagos. Los datos actuales, 0poblaci6n, puede consistir en toda 1agente, induida la que no es todavia cliente. Hay varias maneras decrear clasificadores, como se vera.

14.4.2.1 Clasificadores de arboles de decision

Los clasificadores de arboles de decision son una tecnica muy utilizada para la dasificaci6n. Como sugie-re el nombre, los clasificadores de arboles de decisi6n utilizan un arbol: cad a nodo hoja tiene una claseasociada, y cada nodo interno tiene un predicado (0, de manera mas general, una funcion) asociado. LaFigura 14.8 muestra un ejemplo de arbol de decisi6n.

Para clasificar un nuevo caso se empieza por la raiz y se recorre el arbol hasta alcanzar una hoja; enlos nodos internos se evalua el predicado (0 la funci6n) para el ejemplo de datos, para hallar a que nodohijo hay que ir. El proceso continua hasta que se llega a un nodo hoja. Por ejemplo, si el nivel academicode la persona es de master y sus ingresos son de 40K, partiendo de la raiz se sigue el arco etiquetado"master", y desde alli el arco etiquetado "25K a 75K", hasta alcanzar una hoja. La clase de la hoja es"bueno", por 10que se puede predecir que la solvencia de esa persona es buena.

Creaci6n de c1asificadores de arboles de decision

La pregunta que se plantea es el modo de crear un clasificador de arboles de decisi6n, dado un conjuntode casos de formaci6n. La manera mas frecuente de hacerlo es utilizar un algoritmo impaciente, quetrabaja de manera recursiva, comenzando por la raiz y construyendo el arbol hacia abajo. Inicialrnentesolo hay un node, la raiz, y todos los casos de formaci6n estan asociados con ese nodo.


19/31


20/31


malo mediano bueno

emalo

omediano

~~ bueno

oexcelente

Figura 14.8 Arbol de c1asificaci6n.

En cada nodo, si todos 0 "casi todos" los ejemplos de formaci6n asociados con el nodo pertenecena la misma clase, el nodo se convierte en un nodo hoja asociado con esa clase. En caso contrario, hayque seleccionar un atributo de particion y condiciones de particion para crear nodos hijo. Los datosasociados can cada nodo hijo son el conjunto de ejemplos de formaci6n que satisfacen la condici6nde partici6n de ese nodo hijo. En el ejemplo elegido, se escoge el atributo i i iulacion y se crean cuatrohijos, uno por cada valor de la titulaci6n. Las condiciones para los cuatro nodos hijo son t i tulaci6n =ninguna, t i tulaci6n = bachiller, t i tulaci6n = master y t i iulacion = doctorado, respectivamente. Los datosasociados con cad a hijo son los .ejemplos de formaci6n asociados con ese hijo. En el nodo correspondientea master se escoge el atributo ingresos con el rango de valores dividido en los intervalos 0 a 25K, 25K a5DK, 5DKa 75K y mas de 75K. Los datos asociados can cada nodo son los ejemplos de formaci6n conatributo t i tulaci6n igual a master y el atributo ingresosen cada uno de los rangos, respectivamente. Comooptimizacion, ya que la dase para el rango de 25K a 5DK y el rango de SD K a 75K es el mismo bajo elnodo t i tulaci6n = master, se han unido los dos rangos en uno solo que va de 25K a 75K.

Las mejores particiones

De manera intuitive, al escoger una secuencia de atributos de particion, se comienza can el conjunto detodos los ejemplos de formacion, que es "impure" en el sentido de que contiene ejemplos de muchasclases, y se acaba con las hojas, que son "puras" en el sentido de que en cada hoja todos los ejemplosde formaci6n pertenecen a una unica dase. Se vera brevemente el modo de medir cuantitativamentela pureza. Para evaluar la ventaja de escoger un atributo concreto y la condici6n para la partici6n delos datos en un nodo se mide la pureza de los datos en los hijos resultantes de la particion segun eseatributo. Se escogen el atributo y la condici6n que producen la pureza maxima.

La pureza de un conjunto S de ejemplos de formaci6n puede medirse cuantitativamente de variasmaneras. Sup6ngase que hay k dases y que de los ejemplos en S la fracci6n de ejemplos de la clase i esPi. Una medida de pureza, la medida de Gini, se define como

k

Gini(S) = 1 - LP;i-I

Cuando todos los ejemplos estan en una sola clase, el valor de Gini es 0,mientras que alcanza su maximo(de 1 - 11k) si cada c1asetiene el mismo nurnero de ejemplos. Otra medida de la pureza es la medida dela entropia, que se define como

k

Entropia] S) = - L Pi log, Pii-I


21/31


la entropfa es 0 si todos los ejemplos estan en una sola clase y a1canza su maximo cuando cada clasetiene el mismo mimero de ejemplos. La medida de la entropfa proviene de la teoria de la informaci6n.

Cuando un conjunto S se divide en varios conjuntos Si, i = 1,2, ... .r, se puede medir la pureza delconjunto de conjuntos resultante como:

Es decir, la pureza es la media ponderada de la pureza de los conjuntos Si' La f6rmula anterior puedeutilizarse tanto con la medida de la pureza de Cini como con la medida de la pureza de la entropia.

La ganancia de informacion debida a una partici6n concreta de S en S;.,i = 1,2, .r es, entonces,

Ganimcia_informaci6n(S, {S1, 3 2 ), .. , ST'}) = pureza(S) - pureza(Sl, S2 ) ,Sr)

Las particiones en menor rnimero de conjuntos son preferibles a las particiones en muchos conjuntos,ya que llevan a arboles de decisi6n mas sencillos y significativos. El mimero de elementos en cada unode los conjuntos S, tambien puede tenerse en cuenta; en caso contrario, que un conjunto S, tenga unoo ningun elemento supondria una gran diferencia en el numero de conjuntos, aunque la partici6n fuerala misma para casi todos los elementos. El contenido de informaci6n de una particion concreta puedeexpresarse en terrninos de entropia como

C t id . C ., (S {S S S }) ~ I S i ll I S i lon em O_lIllormaClOn ) 1, 2,) r =- L S f og2 T S ft-l

Todo esto lleva a una definici6n: la mejor partici6n para un atributo es la que da el maximo indicede ganancia de informacion, definido como

Ganancia_informaci6n( S, {S1 , S2, ,Sr} )Contenido_informaci6n(S, {Sl, S2 , ,S r})

Busqueda de las mejores particiones

Hay que averiguar el modo de hallar la mejor particion para un atributo. El modo de dividir un atributodepende del tipo de atributo. Los atributos pueden tener valores continuos, es decir, los valores sepueden ordenar de manera significativa para la clasificacion, como la edad 0 los ingresos, 0 pueden serdeterminantes; es decir, no tener ningun orden significativo, como los nombres de los departamentos 0los de los paises. No se espera que el orden de los nombres de los departamentos 0 el de los paises tenganingun significado para la clasificacion.

Ceneralmente, los atributos que son numeros (enteros 0 reales) se tratan como valores continuos y losatributos de cadenas de caracteres se tratan como categ6ricos, pero esto puede controlarlo el usuario delsistema. En el ejemplo escogido se ha tratado el atributo titulaci6n como categ6rico y el atributo ingresoscomo valor continuo.

En primer lugar se consider a el modo de hallar las mejores particiones para los atributos con va-lores continuos. Por simplificar solo se consideraran particiones binarias de los atributos con valorescontinuos, es decir, particiones que den lugar ados hijos. El caso de las particiones multiples es mascomplicado; veanse las notas bibliograficas para hallar referencias sobre este asunto.

Para hallar la mejorparticion binaria de un atributo con valores continuos, en primer lugar, se orde-nan los valores del atributo en los ejemplos de formacion. Luego se ca1culala ganancia de informacionobtenida por la divisi6n en cada valor. Por ejemplo, si los ejemplos de formaci6n tienen los valores1,10,15 Y25 para un atributo, los puntos de particion considerados son 1, 10Y 15;en cada case, los va-lores menores 0 iguales que el punto de particion forman una partici6n y el resto de los valores formanla otra. La mejor particion binaria para el atributo es la particion que da la ganancia de informacionmaxima.

Para los atributos categoricos se pueden tener particiones multiples, con un hijo para cada valor delatributo. Esto funciona muy bien para los atributos categoricos con pocos valores diferentes, como latitulacion 0 el sexo. No obstante, si el atributo tiene muchos valores diferentes, como los nombres de losdepartamentos en comparuas grandes, la creacion de un hijo para cada valor no es una buena idea. En


22/31

14.4 Mineriade datos 473

procedure CultivarArbol(5)Partici6n(5);

procedure Partici6n (5)if (pul'eza(S) > o p or lS I < o s ) then

return;for each atributo A

evaluar las particiones segun el atribute A;Usar la mejor partici6n hallada (para todos los atributos) para dividir

5 into 5 1,5 2, ... ,8,.;fori = 1,2, ... .r

Particiont Si):

Figura 14.9 Construcci6n recursiva de un arbol de decision.

esos casos se procura combinar varios valores en cada hijo para crear un numero menor de hijos. Veanselas notas bibliograficas para hallar referencias al modo de hacerlo.

Algoritmo de construccion del arbol de decision

La idea principal de la construccion de arboles de decision es la evaluacion de los diferentes atributosy de las distintas condiciones de particion y la seleccion del atributo y de la condici6n de particion quegeneren el indice maximo de ganancia de informacion. El mismo procedimiento funciona de manerarecursiva en cada uno de los conjuntos resultantes de 1a particion, 10 que hace que se construya demanera recursiva el arbol de decision, Si los datos pueden clasificarse de manera perfecta, 1arecursionse detiene cuando 1apureza de un conjunto sea O.No obstante, los datos sue1entener ruido, a puede queun conjunto sea tan pequefio que no sejustifique estadfsticamente su particion. En ese caso. la particionse detiene cuando la pureza del conjunto es "bastante alta" y la clase de 1ahoja resultante se define comola clase de la rnayona de los elementos del conjunto. En general, las diferentes ramas del arbol puedencrecer hasta niveles diferentes.

La Figura 14.9muestra pseudocodigo para un procedimiento recursivo de construcci6n de un athol,que toma al conjunto de ejemplos de formaci6n S como parametro. La recursion se detiene cuando elconjunto es 10bastante puro 0 e1conjunto 5 es demasiado pequeno para que mas particiones resultenestadisticamente significativas. Los parametres o p y O s definen los valores de corte para 1apureza y eltamafio: puede que el sistema les de valores predeterminados, que los usuarios pueden cancelar.

Hay gran variedad de algoritrnos de construccion de arboles de decision y se esbozaran las caracterfs-ticas distintivas de unos cuantos. Veanse las notas bibliograficas para hallar mas detalles. Con conjuntosde datos de tamafio muy grande la realizacion de particiones puede resultar muy costosa, ya que irn-plica la realizaci6n repetida de copias. Por tanto, se han desarrollado varios algoritrnos para minirnizarel coste de E/S y el coste de computacion cuando los datos de formaci6n son mayo res que la memoriadisponible.

Varios de los algoritmos tambien podan los subarboles del arbol de decision generado para reducirel exceso de ajuste: un subarbol tiene exceso de ajuste si se ha ajustado tanto a los detalles de los datosde forrnacion que comete muchoserrores de clasificacion con otros datos. Se poda un subarbol sustitu-yendolo por un nodo hoja. Hay varias heuristic as de poda; una utiliza parte de los datos de forrnacionpara construir el arbol y otra parte para comprobarlo. La heuristic a poda el subarbol si descubre que loserrores de clasificacion de los casos de prueba se reducirian si se sustituyera por un nodo hoja.

Se pueden generar reglas de clasificaci6n a partir de los arboles de decision, si se desea. Para cada hojase genera una regIa de la manera siguiente: la parte izquierda es la conjunci6n de todas las condicionesde partici6n del camino hasta 1ahoja y 1aclase es 1aclase de 1amayoria de los ejemplos de formacion de1ahoja. Un ejemplo de estas reg1as de clasificaci6n es

titulaci on = master and imqresos > 75.000 =? excelente


23/31

14.4 Mineriade datos 475

Hay tecnicas estandar en estadfstica para hallar los coeficientes de regresi6n. Aqui no se estudiaran esastecnicas, pero las notas bibliograficas ofrecen referencias.

14.4.3 Reglas de asociaci6n

Los comercios minoristas suelen estar interesados en las asociaciones entre los diferentes articulos quecompra la gente. Ejemplos de esas asociaciones son:

Alguien que compra pan es bastante probable que compre tambien leche.

Una persona que compr6 ellibro F un da men to s de base s de da toses bastante probable que tarnbiencompre ellibro Fun damen to s d e s is tem as o pc ra tiv os .

La informaci6n de asociaci6n puede utilizarse de varias maneras. Cuando un cliente compra un libradeterminado puede que la libreria en linea le sugiera los libros asociados, Puede que la tienda de ali-mentaci6n decida colocar el pan cerca de la leche, ya que suelen comprarse juntos, para ayudar a losclientes a hacer la compra mas rapidamente. 0 puede que la tienda los coloque en extremos opuestos

del mostrador y coloque otros articulos asociados entre medias para inducir a la gente a comprar tam-bien esos articulos, mientras los clientes van de un extremo a otro del mostrador. Puede que una tiendaque ofrece descuento en un articulo asociado no 10 ofrezca en el otro, ya que, de todos modos, el clientecomprara el segundo articulo.Un ejemplo de regIa de asociaci6n es

pan =? leche

En el contexte de las compras de alimentaci6n, la regIa dice que los clientes que compran pan tambientienden a comprar leche con una probabilidad elevada. Una regIa de asociaci6n debe tener una pobla-cion asociada: la poblaci6n consiste en un conjunto de casos. En el ejemplo de la tienda de alimentaci6n,la poblaci6n puede consistir en todas las compras en la tienda de alimentaci6n; cada compra es un caso.En el caso de una libreria, la poblaci6n puede consistir en toda la gente que realiza compras, indepen-dientemente del momento en que las hayan realizado. Cada consumidor es W1 caso. Aqut, el analistaha decidido que el momenta de realizaci6n de la compra no es significativo, rnientras que, para el ejem-plo de la tienda de alimentaci6n, puede que el analista haya decidido concentrarse en cada compra,ignorando las diferentes visitas de un mismo cliente.

Las reglas tienen un soporte, as! como una confianza asociados. Los dos se definen en el contexto de lapoblaci6n:

El soporte es una medida de la fracci6n de la poblaci6n que satisface tanto el antecedente comoe1consecuente de la regIa.

Por ejemplo, sup6ngase que s6lo el 0.001 por ciento de todas las compras incluyen leche ydestornilladores. El soporte de la regIa

leche =? destornilladores

esbajo. Puede que la regIa ni siquiera sea estadisticamente significativa-e-quizas solo hubiera unaunica compra que incluyera leche y destornilladores. Las empresas no suelen estar interesadasen las reglas que tienen un soporte bajo, ya que afectan a pocos clientes y no merece la pena

prestarles atenci6n.Por otro lado, si el 50 por ciento de las comp'as implica leche y pan, el soporte de las reglasque afecten al pan y a la leche (y a ningun otro articulo) es relativamente elevado, y puede quemerezca la pena prestarles atenci6n. El grado mmimo de soporte que se considera deseable exac-tamente depende de la aplicaci6n.

La confianza es una medida de la frecuencia con que el consecuente es cierto cuando 10 es elantecedente. Por ejemplo, la regIa

pan =? leche

tiene una confianza del 80por ciento si e180por ciento de las compras que incluyen pan incluyentambien leche. Las reglas con una confianza baja no son significativas. En las aplicaciones comer-


24/31


ciales las reglas suelen tener confianzas significativamente menores del 100 por ciento, mientrasque en otros campos, como la fisica, las reglas pueden tener confianzas elevadas.

Hay que tener en cuenta que la confianza de pan =? leche puede ser muy diferente de laconfianza de leche =? pan, aunque las dos tienen el rnismo soporte.

Para descubrir reglas de asociaci6n de la forma

. en primer lugar hay que determinar los conjuntos de elementos con soporte suficiente, denominadosconjuntos grandes de elementos. En el ejemplo que se trata se hallan conjuntos de elementos que estanincluidos en un numero de casos 10bastante grande. En breve se vera el modo de calcular conjuntosgrandes de elementos.

Para cada conjunto grande de elementos se obtienen todas las reglas con confianza suficiente queafecten a todos los elementos del conjunto y s6lo a ellos. Para cada conjunto grande de elementos S seobtiene una regIa S - S =? s para cada subconjunto s c S, siempre que S - s =? s tenga confianzasuficiente; la confianza de la regIa la da el soporte de s dividido por el soporte de S. '

Ahora se considerara el modo de generar todos los conjuntos grandes de elementos. Si el numerode conjuntos de elementos posibles es pequeno, basta con un solo paso por los datos para detectar elnivel de soporte de todos los conjuntos. Se lleva una cuenta, con valor inicial 0, para cada conjunto deelementos. Cuando se captura el registro de una compra. la cuenta se incrementa para cada conjunto deelementos tal que todos los elementos del conjunto esten contenidos en la compra. Por ejernplo, si unacompra incluye los elementos a, by c, se incrernentara el contador para {a}, {b}, {c}, {a, b}, {b ,c}, {a, c}y {a , b, c}. Los conjuntos con un contador 10bastante elevado al final del pase se corresponden con loselementos que tienen un grado de asociaci6n elevado.

El numero de conjuntos crece de manera exponencial, 10que hace inviable elproceso que se acaba dedescribir si el numero de elementos es elevado. Afortunadamente, casi todos los conjuntos tienen nor-malmente un soporte muy bajo: se han desarrollado optirnizaciones para no considerar la mayor partede esos conjuntos. Estas tecnicas utilizan varios pases por la base de datos y s610consideran algunosconjuntos en cada pase.

En la tecnica a priori para la generaci6n de conjuntos de artfculos grandes s6lo se consideran en el

primer pase los conjuntos con un solo elemento. En elsegundo pase se consideran los conjuntos con dosartfculos, etc.

Al final de cada pase todos los conjuntos con soporte suficiente se consideran conjuntos grandes deelementos. Los conjuntos que se ha hallado que tienen demasiado poco soporte al final de cada pase seeliminan. Una vez eliminado un conjunto no hace falta considerar ninguno de sus superconjuntos. Enotros terrninos, en el pase i s6lo hay que contar el soporte de los conjuntos de tamafio i tales que se hayahallado que todos sus subconjuntos tienen un soporte 10bastante elevado; basta con probar todos lossubconjuntos de tamanoz - 1 para asegurase de que se cumple esta propiedad. Al final del pase i sehalla que ningun conjunto de tamano i tiene el soporte suficiente, por 10que no hace falta considerarningun conjunto de tamafio i + 1. Entonces, el calculo se termina.

14.4.4 Otros tipos de asociaci6n

El uso de meras reglas de asociaci6n tiene varios inconvenientes. Uno de los principales es que muchas

asociaciones no son muy interesantes, ya que pueden predecirse. Por ejemplo, si mucha gente compracereales y mucha gente compra pan, se puede predecir que un ruimero bastante grande de personascomprara las dos cosas, aunque no haya ninguna relaci6n entre las dos compras. De hecho, incluso sila compra de cereal tiene una influencia negativa suave en la compra de pan (es decir, los clientes quecompran cereal tienden a comprar pan menos a menudo que el cliente medic), la asociaci6n entre elcereal y el pan puede tener un soporte alto.

Lo que resultaria interesante es una desviaci6n de la ocurrencia conjunta de las dos compras. Enterminos estadfsticos, se buscan correlaciones entre los articulos; las correlaciones pueden ser positivas,en las que la ocurrencia conjunta es superior a 10esperado, 0 negativa, en la que los elementos ocurrenconjuntamente menos frecuentemente de 10predicho. Asi, si la compra de pan no se correlaciona con elcereal, no se informa, incluso si hubiese una asociaci6n fuerte entre los dos. Hay medidas estandares de


25/31


correlaci6n usadas ampliamente en el area de la estadistica. Se puede consultar cualquier libro de textoestandar de estadistica para hallar mas informaci6n sobre las correlaciones.

Otra clase importante de aplicaciones de mineria de datos son las asociaciones de secuencias (0 corre-laciones de secuencias). Las series de datos temporales, como las cotizaciones bursatiles en una serie dedias, constituyen un ejemplo de datos de secuencias. Los analistas bursa tiles desean hallar asociacionesentre las secuencias de cotizaciones. Un ejemplo de asociaci6n de este tipo es la regIa siguiente: "Siempreque las tasas de interes de los bonos sub en, las cotizaciones bursatiles bajan en un plazo de dos dias",El descubrimiento de esta asociaci6n entre secuencias puede ayudar a adoptar decisiones de inversioninteligentes. Veanse las notas bibliograficas para hallar referencias a la investigaci6n en este campo.

Las desviaciones de las estructuras temporales suelen resultar interesantes. Por ejemplo, si una em-presa ha estado creciendo a una tasa constante cada afio, una desviaci6n de la tasa de crecimiento ha-bitual resulta sorprendente. Si las ventas de ropa de invierno bajan en verano, ya que puede predecirsecon base en los afios anteriores, una desviacion que no se pudiera predecir a partir de la experiencia pa-sada se consideraria interesante. Las tecnicas de mineria pueden hallar desviaciones de 10 esperado conbase en las estructuras temporales 0 secuenciales pasadas. Veanse las notas bibliograficas para hallarreferencias a la investigaci6n en este campo.

14.4.5 Agrupamiento

De manera intuitiva, el agrupamiento hace referencia al problema de hallar agrupaciones de puntosen los datos dados. El problema del agrupamiento puede formalizarse de varias maneras a partir delas metricas de distancias. Una manera es formularlo como el problema de agrupar los puntos en kconjuntos (para un k dado) de modo que la distancia media de los puntos al centroide de su agrupaci6nasignada sea rrunima''. Otra manera es agrupar los puntos de modo que la distancia media entre cadapar de puntos de cada agrupacion sea minima. Hay otras definiciones; veanse las notas bibliograficaspara hallar mas detalles. Pero la intuici6n subyacente a todas estas definiciones es agrupar los puntosparecidos en un unico conjunto.

Otro tipo de agrupamiento aparece en los sistemas de clasificaciones de la biologia (estos sistemas

de clasificaci6n no intentan predecir las clases, sino agrupar los elementos relacionados). Por ejemplo,

los leopardos y los seres humanos se agrupan bajo la clase marniferos, mientras que los cocodrilos ylas serpientes se agrupan bajo los reptiles. Tanto los mamiferos como los reptiles estan bajo la clasecomun de los cordados. La agrupacion de los mamiferos tiene subagrupaciones, como los carnivores ylos primates. Por tanto, se tiene un agrupamiento jerarquico, Dadas las caracteristicas de las diferentesespecies, los biologos han creado un esquema complejo de agrupamiento jerarquico que agrupa lasespecies relacionadas en diferentes niveles de la jerarquia.

El agrupamiento jerarquico tarnbien resulta util en otros dominios-para agrupar documentos, porejemplo. Los sistemas de directorio de Internet (como el de Yahoo) agrupan los document os relacionadosde manera jerarquica. Los algoritmos de agrupamiento jerarquico pueden clasificarse como algoritmosde agrupamiento aglomerativo, que comienzan creando agrupaciones pequerias y luego crean los nive-les superiores, 0 como algoritmos de agrupamiento divisivo, que primero crean los niveles superioresdel agrupamiento jerarquico y luego refinan cada agrupaci6n resultante en agrupaciones de niveles in-feriores.

La comunidad estadistica ha estudiado extensamente los agrupamientos. La investigaci6n en basesde datos ha proporcionado algoritmos escalables de agrupamiento que p

Documents

Capitulo 14- Analisis y Minera de Datos