Introdução e Motivação de DW, OLAP e Data Mining (baseado nos slides do livro: Data Mining: C & T)

Introdução e Motivação de Introdução e Motivação de DW, OLAP e Data MiningDW, OLAP e Data Mining

(baseado nos slides do livro: Data (baseado nos slides do livro: Data Mining: C & T)Mining: C & T)

SAD Tagus 2004/05 H. Galhardas

MotivaçãoMotivaçãoProblema:Problema: Explosão de dados Explosão de dados

As maturidade atingida pelas ferramentas de recolha automática de dados e pelas tecnologias de BD têm como consequência a existência de grandes volumes de dados armazenados em BDs, DWs e outros repositórios de informação.

“Afogados” em dados, mas “famintos” de conhecimento.

SoluçãoSolução: : Data warehousingData warehousing e e data miningdata mining Data warehousing e on-line analytical processing (OLAP) Extracção de conhecimento interessante (regras, padrões,

restrições) dos dados existentes em grandes BDs


Evolução da tecnologia de Evolução da tecnologia de BD BD

1960s1960s:: Data collection, database creation, IMS and network DBMS

1970s1970s: : Relational data model, relational DBMS implementation

1980s1980s: : RDBMS, advanced data models (extended-relational, OO, deductive,

etc.) and application-oriented DBMS (spatial, scientific, engineering, etc.)

1990s1990s—2000s—2000s: : Data mining and data warehousing, multimedia databases, Web

databases


PlanoPlano Objectivo de um DWObjectivo de um DW Operações OLTP vs OLAPOperações OLTP vs OLAP Conceito de DW: repositório e arquitecturaConceito de DW: repositório e arquitectura Interrogações OLAPInterrogações OLAP Exploração de dados (Data Mining) e aplicaçõesExploração de dados (Data Mining) e aplicações Processo de descoberta de conhecimento (KDD)Processo de descoberta de conhecimento (KDD) Arquitectura típica de um sistema de data miningArquitectura típica de um sistema de data mining Funções de data miningFunções de data mining Medidas de interesse Medidas de interesse


Objectivo Geral de um Objectivo Geral de um DWDW

Acumular Acumular informaçãoinformação para produzir para produzir indicadores de negócio indicadores de negócio que permitam que permitam

tomartomar decisões decisões


InformaçãoInformação Grandes quantidades de informação estão disponíveisGrandes quantidades de informação estão disponíveis A análise de informaçãoA análise de informação é a base da tomada de é a base da tomada de

decisãodecisão CaracterísticasCaracterísticas necessárias: necessárias:

precisa fiável actualizada relevante orientada à acção


Sistemas operacionais Sistemas operacionais (OLTP)(OLTP)

Contabilidade, compras, reservas, telecomunicações, etcContabilidade, compras, reservas, telecomunicações, etc Muitas fontes de dados dispersas (ficheiros excel, BD Muitas fontes de dados dispersas (ficheiros excel, BD

Access,etc), mtas aplicações, mtas interfacesAccess,etc), mtas aplicações, mtas interfaces ProblemasProblemas: acesso aos dados díficil, qualidade de dados : acesso aos dados díficil, qualidade de dados

duvidosa, dados estruturados à aplicação (ex: códigos duvidosa, dados estruturados à aplicação (ex: códigos específicos), suporte a interrogações simplesespecíficos), suporte a interrogações simples


Esquema TPC-C Esquema TPC-C (benchmark)(benchmark)

WarehouseWarehouseWW

LegendLegendTable NameTable Name<cardinality><cardinality>

one-to-manyone-to-manyrelationshiprelationship

secondary indexsecondary index

DistrictDistrictW*10W*10

1010

CustomerCustomerW*30KW*30K

3K3K

HistoryHistoryW*30K+W*30K+

1+1+

ItemItem100K (fixed)100K (fixed)

StockStockW*100KW*100K100K100K WW

OrderOrderW*30K+W*30K+1+1+

Order-LineOrder-LineW*300K+W*300K+

10-1510-15

New-OrderNew-OrderW*5KW*5K0-10-1


Vista detalhadaVista detalhadaCUSTOMER ORDER

ORDER-LINE

C_IDC_D_IDC_W_IDC_FIRSTC_MIDDLEC_LASTC_STREET_1C_STREET_2C_CITYC_STATEC_ZIPC_PHONEC_SINCEC_CREDITC_CREDIT_LIMC_DISCOUNTC_BALANCEC_YTD_PAYMENTC_PAYMENT_CNTC_DELIVERY_CNTC_DATA

O_IDO_D_IDO_W_IDO_C_IDO_ENTRY_DO_CARRIER_IDO_OL_CNTO_OL_CNTO_ALL_LOCAL

OL_O_IDOL_D_IDOL_C_IDOL_NUMBEROL_I_IDOL_SUPPLY_W_IDOL_DELIVERY_DOL_QUANTITYOL_AMOUNTOL_DIST_INFO


Operações OLTPOperações OLTP New-order:New-order: enter a new order from a enter a new order from a

customercustomer Payment:Payment: update customer balance to reflect update customer balance to reflect

a paymenta payment Delivery:Delivery: deliver orders (done as a batch deliver orders (done as a batch

transaction)transaction) Order-status:Order-status: retrieve status of customer’s retrieve status of customer’s

most recent ordermost recent order Stock-level:Stock-level: monitor warehouse inventory monitor warehouse inventory


Interrogações de apoio à Interrogações de apoio à decisãodecisão

Extractos de TPC-D (actualmente H e R):Extractos de TPC-D (actualmente H e R): Retrieve the 10 unshipped orders with the highest value. Report the amount of business that was billed, shipped, and

returned. Determines how well the order priority system is working and gives

an assessment of customer satisfaction. That is, count the number of orders ordered in a given quarter of a given year in which at least one lineitem was shipped by the customer later than its committed date. The query lists the count of such orders for each order priority sorted in ascending priority order.


Extracção de dados Extracção de dados operacionaisoperacionais

Para suportar aplicações de SAD, existem vários problemas:Para suportar aplicações de SAD, existem vários problemas:

Duplicação de esforço em extracções múltiplas Versões de dados incoerentes e obsoletas Qualidade de dados:falta de chave universal, entrada de dados

livre, campos c/ valores heterógeneos, normalização

ExtracçõesExtracçõesSistemas operacionaisSistemas operacionais GestoresGestores


OLTP vs. OLAPOLTP vs. OLAP OLTP OLAP users clerk, IT professional knowledge worker function day to day operations decision support DB design application-oriented subject-oriented data current, up-to-date

detailed, flat relational isolated

historical, summarized, multidimensional integrated, consolidated

usage repetitive ad-hoc access read/write

index/hash on prim. key lots of scans

unit of work short, simple transaction complex query # records accessed tens millions #users thousands hundreds DB size 100MB-GB 100GB-TB metric transaction throughput query throughput, response


Conceito de DW (1)Conceito de DW (1) Conjunto centralizado de dadosConjunto centralizado de dados::

temáticos históricosdatados integradospersistentes

que oferece um nível de qualidade adequado que oferece um nível de qualidade adequado às aplicações de decisãoàs aplicações de decisão


Dados temáticosDados temáticos Os dados estão organizados por Os dados estão organizados por processo de negócioprocesso de negócio e não por e não por

aplicação de produçãoaplicação de produção

Exemplos :Exemplos :Cliente(contratos seguros, empréstimos, contas, planos de poupança,

etc) Produto(gama, vendas, compras, custos de produção, etc)


Dados históricosDados históricos Os dados residem no DW durante um Os dados residem no DW durante um largo período largo período

de tempode tempo

É feita a adição sucessiva de incrementos de dadosÉ feita a adição sucessiva de incrementos de dadosActualizações e remoções são rarasCarregamentos sucessivos e incrementaisArquivo de dados muito antigos


Dados datadosDados datados Os dados do DW representam Os dados do DW representam imagens sucessivasimagens sucessivas do do

mundo realmundo real

São importantes os seguintes aspectos:São importantes os seguintes aspectos:Granularidade de tempoGranularidade de refrescamentoCoerência das imagens


Dados integradosDados integrados Todos os dados relativos a um processo de Todos os dados relativos a um processo de

negócio encontram-se organizados de forma negócio encontram-se organizados de forma pertinente, coerente e não redundantepertinente, coerente e não redundante

A A integração de dadosintegração de dados é obtida através de é obtida através de processos de transformação de dados: processos de transformação de dados: consolidação, agregação, interpretaçãoconsolidação, agregação, interpretação

Estes processos devem estar documentados Estes processos devem estar documentados através de metadadosatravés de metadados


Dados persistentesDados persistentes Os dados estão Os dados estão fisicamente separadosfisicamente separados dos dos

sistemas operacionaissistemas operacionais Não são necessários mecanismos de gestão Não são necessários mecanismos de gestão

de transacções, recuperação e controlo de de transacções, recuperação e controlo de concorrênciaconcorrência

As operações fundamentais são: As operações fundamentais são: carregamento inicial e incremental dos dados, carregamento inicial e incremental dos dados, e leitura dos dadose leitura dos dados


Conceito de DW (2)Conceito de DW (2)Arquitectura de integração de dadosArquitectura de integração de dados que suporta que suporta

a tomada de decisão através de:a tomada de decisão através de:Técnicas OLAP (interrogações estruturadas ou ad-

hoc, geração de relatórios analíticos) para visualização e navegação de informação segundo difs. perspectivas

Técnicas de data mining: técnicas de análise de dados mais avançadas para compreender os dados.


Arquitectura típica de Arquitectura típica de DWDW

Data Sources

Operational DBs

othersources OLAP

Ad-hoc QueryReportsData mining

Front-End ToolsOLAP Engine

Serve

OLAP Server

DataWarehouse

ExtractTransformLoadRefresh

Metadata

Data Marts

Data Storage


Interrogações OLAP (1)Interrogações OLAP (1)

Pivoting:Pivoting: Agragação por determinadas Agragação por determinadas dimensões dimensões

Ex: Pivoting on Location and Ex: Pivoting on Location and Time yields this cross-tabulation:

63 81 14438 107 145

75 35 110

WI CA Total

19951996

1997

176 223 339Total

price

category

pname

pid country

statecitylocid

sales

locidtimeid

pid

holiday_flag

weekdate

timeid month

quarter

year

(Fact table)SALES

TIMES

PRODUCTSLOCATIONS


Interrogações OLAP (2)Interrogações OLAP (2) Outra operação comum: Outra operação comum: agregar agregar uma medida uma medida

sobre uma ou mais dimensõessobre uma ou mais dimensõesFind total sales.Find total sales for each city, or for each state.Find top five products ranked by total sales.

Roll-up:Roll-up: Agregar a diferentes níveis de uma Agregar a diferentes níveis de uma hierarquia de dimensõeshierarquia de dimensõesGiven total sales by city, we can roll-up to get sales by

state.


SQL para expressar SQL para expressar interrogações OLAPinterrogações OLAP

A cross-tabulation pode ser calculada usando uma A cross-tabulation pode ser calculada usando uma colecção de interrogações SQLcolecção de interrogações SQL

SELECT SUM(S.sales)FROM Sales S, Times T, Locations LWHERE S.timeid=T.timeid AND S.timeid=L.timeidGROUP BY T.year, L.state

SELECT SUM(S.sales)FROM Sales S, Times TWHERE S.timeid=T.timeidGROUP BY T.year

SELECT SUM(S.sales)FROM Sales S, Location LWHERE S.timeid=L.timeidGROUP BY L.state


O operador CUBE O operador CUBE (SQL:1999)(SQL:1999)

Generalizando, se existirem k dimensões, Generalizando, se existirem k dimensões, existem 2^k possíveis interrogações existem 2^k possíveis interrogações GROUP GROUP BY sobre um subcjto de dimensões BY sobre um subcjto de dimensões

CUBE pid, locid, timeid BY SUM SalesCUBE pid, locid, timeid BY SUM SalesEquivalente a fazer rolling up de Sales em todos

os 8 sucjtos do conjunto {pid, locid, timeid}; cada roll-up corresponde a uma interrogação SQL da forma:

SELECT SUM(S.sales)FROM Sales SGROUP BY grouping-list


O que é O que é Data MiningData Mining??

Data miningData mining ou descoberta de conhecimento em BDs ou descoberta de conhecimento em BDs ((knowledge discoveryknowledge discovery in databases): in databases): Extracção de informação interessante (não trivial, implicita,

desconhecida ou potencialmente útil) ou padrões em grandes BDs

Nomes alternativos: Nomes alternativos: Knowledge discovery(mining) in databases (KDD),

knowledge extraction, data/pattern analysis, data archeology, data dredging, information harvesting, business intelligence, etc.


Aplicações Aplicações Análise de dados e suporte à decisão:Análise de dados e suporte à decisão:

1. Análise e gestão de mercado: target marketing, customer relation management, market basket analysis, cross selling, market segmentation

2. Análise e gestão de risco: Forecasting, customer retention, improved underwriting, quality control, competitive analysis

3. Detecção e gestão de fraudes

Outras aplicações:Outras aplicações: Text mining (news group, email, documents) and Web analysis. Intelligent query answering


1. Análise e gestão de 1. Análise e gestão de mercadomercado

Fontes de dados:Fontes de dados: Credit card transactions, loyalty cards, discount coupons, customer complaint

calls, plus (public) lifestyle studies Alvo de mercadoAlvo de mercado::

Find clusters of “model” customers who share the same characteristics: interest, income level, spending habits, etc.

Deteminar Deteminar padrões de aquisição/comprapadrões de aquisição/compra ao longo do tempo ao longo do tempo Conversão de uma conta bancária simples para uma conta conjunta quando as

pessoas se casam Cross-market analysisCross-market analysis

Associações entre compras de produtos Previsão baseada nas associações encontradas


1. Análise e gestão de 1. Análise e gestão de mercado (cont)mercado (cont)

Traçar perfil de clientesTraçar perfil de clientes Que tipos de clientes compram que tipo de produtos (clustering

e classificação)

Identificar requisitos dos clientes Identificar requisitos dos clientes Quais os melhores produtos para diferentes clientes Usar previsão para encontrar quais os factores que atraiem

novos clientes

Fornece informação sumarizadaFornece informação sumarizada Vários relatórios com informação (estatistica) sumarizadaVários relatórios com informação (estatistica) sumarizada


2. Análise e gestão de 2. Análise e gestão de riscorisco

Planeamento financeiro e avaliação de bensPlaneamento financeiro e avaliação de bens Previsão e análise de cash flow contingent claim analysis to evaluate assets cross-sectional and time series analysis (financial-ratio, trend

analysis, etc.)

Planeamento de recursos:Planeamento de recursos: Sumarizar e comparar recursos e gastos

Competição:Competição: Monitorizar a concorrência e as direcções do mercado Agrupar os clientes em classes e conceber uma estratégia de

preços baseada nessas classes


3. Detecção e gestão de 3. Detecção e gestão de fraudesfraudes

Aplicações: medicina, retalho, serviços de Aplicações: medicina, retalho, serviços de cartões de crédio, telecom (detecção de fraudes cartões de crédio, telecom (detecção de fraudes nos cartões telefónicos), etcnos cartões telefónicos), etc

Aproximação: Aproximação: Usar dados históricos para construir modelos de

comportamento fraudulento Exemplos:Exemplos:

Seguros: detectar grupos de pessoas que forjam acidentes para receber o dinheiro do seguro

Branqueamento de capital: detectar transacções bancárias suspeitas


Outras aplicaçõesOutras aplicaçõesSportsSports

IBM Advanced Scout analyzed NBA game statistics (shots blocked, assists, and fouls) to gain competitive advantage for New York Knicks and Miami Heat

AstronomyAstronomy JPL and the Palomar Observatory discovered 22 quasars with the help

of data mining

Internet Web Surf-AidInternet Web Surf-Aid IBM Surf-Aid applies data mining algorithms to Web access logs for

market-related pages to discover customer preference and behavior pages, analyzing effectiveness of Web marketing, improving Web site organization, etc.


Data Mining para KDD Data Mining para KDD

Data Cleaning

Data Integration

Databases

Data Warehouse

Task-relevant Data

Selection

Data Mining

Pattern Evaluation


Passos de um processo de KDDPassos de um processo de KDD Apreender o Apreender o domíniodomínio do problema do problema Seleccionar as Seleccionar as fontes defontes de dados relevantesdados relevantes Limpeza e pré-processamento de dadosLimpeza e pré-processamento de dados Redução e transformação de dados Redução e transformação de dados

Descobrir características úteis, reduzir as dimensões, etc Escolher Escolher funções/tarefas de data miningfunções/tarefas de data mining

Sumarização, classificação, regressão, associação, clustering Escolher e executar o Escolher e executar o algoritmo de data miningalgoritmo de data mining

Para procurar padrões de interesse Avaliar os padrõesAvaliar os padrões encontrados e aencontrados e a apresentação apresentação de de

conhecimento conhecimento Visualização, remoção de padrões redundantes, etc

Utilização do conhecimento descobertoUtilização do conhecimento descoberto


Arquitectura típica de um Arquitectura típica de um sistema de data miningsistema de data mining

Data Warehouse

Data cleaning & data integration Filtering

Databases

Database or data warehouse server

Data mining engine

Pattern evaluation

Graphical user interface

Knowledge-base


Data Mining e Business Data Mining e Business IntelligenceIntelligence

Increasing potentialto supportbusiness decisions End User

Business Analyst

DataAnalyst

DBA

MakingDecisions

Data PresentationVisualization Techniques

Data MiningInformation Discovery

Data Exploration

OLAP, MDA

Statistical Analysis, Querying and Reporting

Data Warehouses / Data Marts

Data SourcesPaper, Files, Information Providers, Database Systems, OLTP


Sobre que tipos de dados se Sobre que tipos de dados se faz data mining?faz data mining?

Relational databasesRelational databases Data warehousesData warehouses Transactional databasesTransactional databases Advanced DB and information repositoriesAdvanced DB and information repositories

Object-oriented and object-relational databases Spatial databases Time-series data and temporal data Text databases and multimedia databases Heterogeneous and legacy databases WWW


Data Mining: confluência de Data Mining: confluência de várias disciplinasvárias disciplinas

Data Mining

Database Technology Statistics

OtherDisciplines

InformationScience

MachineLearning Visualization


Funções de Data Mining Funções de Data Mining (1)(1)

Descrição de conceitosDescrição de conceitos: caracterização e : caracterização e discriminação discriminação Generalizar, sumarizar e contrastar características

dos dados

Associação (correlação e causalidade)Associação (correlação e causalidade)Associação multi-dimensional vs uni-dimensional

age(X, “20..29”) ^ income(X, “20..29K”) buys(X, “PC”) [support = 2%, confidence = 60%]

contains(T, “computer”) contains(x, “software”) [1%, 75%]



ClassificaçãoClassificação Encontrar modelos que descrevam e sejam capazes de

distinguir classes/conceitos para previsão Ex: classificar países baseado no clima, ou classificar carros

baseado na kilometragem Técnicas: árvores de decisão, regras de classificação, redes

neuronais

PrevisãoPrevisão Prever valores desconhecidos ou em falta



Análise de clustersAnálise de clusters Não existe uma catalogação apriori, logo agrupa dados para

formar novas classes Ex: agrupar casas para encontrar padrões de distribuição Principio: maximizar a semelhança dentro de uma classe e

minimizar a semelhança entre classes



Detecção de Detecção de outliersoutliers Outlier é um objecto de dados que não obedece ao

comportamento genérico dos dados Pode ser considerado como ruído ou excepção, mas

é útil em detecção de fraudes

Trend and evolution analysisTrend and evolution analysis Técnicas: análise de regressão, mining de padrões

em sequências, análise baseada em semelhança


Todos os padrões Todos os padrões descobertos são descobertos são interessantes? interessantes?

Milhares de padrões gerados, nem todos interessantes Milhares de padrões gerados, nem todos interessantes Um padrão é Um padrão é interessanteinteressante se se

fôr compreendido por humanos, fôr válido para dados de teste e novos dados com um grau de certeza fôr potencialmente útil Validar alguma hipótese procurada pelo utilizador.

Medidas de interesseMedidas de interesse: : objectivas: baseadas em estatística e estruturas de padrões (suporte,

confiança, etc) subjectivas: baseadas na crença do utilizador nos dados


Podem ser descobertos todos Podem ser descobertos todos os padrões e só os os padrões e só os

interessantes?interessantes?CompletudeCompletude: encontrar todos os padrões interessantes : encontrar todos os padrões interessantes

Association vs. classification vs. clustering

OptimizaçãoOptimização: procurar só os padrões interessantes: procurar só os padrões interessantes Todos os padrões e depois filtrar só os interessantes Optimização de interrogações de mining: encontrar só os

interessantes


OLAP Mining: integração OLAP Mining: integração de data mining e DWde data mining e DW

On-line analytical mining dataOn-line analytical mining data Integração de tecnologias de mining e OLAP

Mining interactivo de conhecimento a diferentes Mining interactivo de conhecimento a diferentes níveis níveis Explorar conhecimento e padrões a diferentes níveis de

abstracção,através das operações de drilling/rolling, pivoting, etc.

Integração de múltiplas funções de miningIntegração de múltiplas funções de mining Classificação, clustering, associação


An OLAM ArchitectureAn OLAM Architecture

Data Warehouse

Meta Data

MDDB

OLAMEngine

OLAPEngine

User GUI API

Data Cube API

Database API

Data cleaning

Data integration

Layer3

OLAP/OLAM

Layer2

MDDB

Layer1

Data Repository

Layer4

User Interface

Filtering&Integration Filtering

Databases

Mining query Mining result


Aspectos mais importantes Aspectos mais importantes em data mining em data mining

Metodologia de mining e interacção com o Metodologia de mining e interacção com o utilizador utilizador

Desempenho e escalabilidadeDesempenho e escalabilidade Lidar com diversidade de tipos de dadosLidar com diversidade de tipos de dados ......


BibliografiaBibliografia (Livro) (Livro) Data Mining: Concepts and TechniquesData Mining: Concepts and Techniques, ,

J. Han & M. Kamber, Morgan Kaufmann, 2001 J. Han & M. Kamber, Morgan Kaufmann, 2001 (Cap 1 )(Cap 1 )

(Livro) The Data Warehouse Toolkit, R. Kimball, (Livro) The Data Warehouse Toolkit, R. Kimball, Wiley 2001 (?)Wiley 2001 (?)

(Artigo) (Artigo) An Overview of Data Warehousing and An Overview of Data Warehousing and OLAP TechnologyOLAP Technology, S. Chaudhuri & U. Dayal, , S. Chaudhuri & U. Dayal, SIGMOD Record, March 1997SIGMOD Record, March 1997

Documents

Introdução e Motivação de DW, OLAP e Data Mining (baseado nos slides do livro: Data Mining: C & T)