Tipologia dos dados de entrada Tipologia dos dados de entrada da mineração de dados da mineração de dados

Jacques RobinCIn-UFPE

Tipologia da fontes de dados para Tipologia da fontes de dados para mineraçãomineração

Fontes convencionais preparadas para mineração:• Arquivo texto chato

padronizado (flat file)• Data warehouse ou data

mart relacional• Data warehouse ou data

mart multidimensional

Fontes convencionais não preparadas para mineração• Arquivos de log• BD relacional

Fontes não convencionais• BD objeto-relacional• BD orientado a objetos• BD dedutivo• BD probabilista• BD indutivo• BD espacial• BD temporal• BD de restrições• BD multimídia• BD semi-estruturado• Páginas web

Arquivo texto chato padronizado Arquivo texto chato padronizado (flat (flat file)file)

Arquivo texto :• Meta-dados do cabeçote:

1a linha = nome do conceito ou relação a minerar, depois cada linha = tipo e/ou conjunto de valores possíveis de um

atributo

• Dados no resto do arquivo: cada linha = um exemplo ou instância do conceito a aprender

um registro de uma tabela de BD relacional separadas em campos por separadores convencionais

cada campo = um atributo ou propriedade da instância campo de uma tabela de BD relacional

Exemplo de flat file: Exemplo de flat file: formato de entrada do Wekaformato de entrada do Weka

% Arff file for the weather data with some

% numeric features

@relation weather @attribute outlook { sunny, overcast,

rainy }@attribute temperature numeric@attribute humidity numeric@attribute windy { true, false }@attribute play? { yes, no } 

@datasunny, 85, 85, false, nosunny, 80, 90, true, noovercast, 83, 86, false, yesrainy, 70, 96, false, yesrainy, 68, 80, false, yesrainy, 65, 70, true, noovercast, 64, 65, true, yessunny, 72, 95, false, nosunny, 69, 70, false, yesrainy, 75, 80, false, yessunny, 75, 70, true, yesovercast, 72, 90, true, yesovercast, 81, 75, false, yesrainy, 71, 91, true, no

Arquivo texto chato padronizado Arquivo texto chato padronizado (flat (flat file)file)

Única entrada de vários ferramentas de mineração Pode ser criado a partir de BD relacional via grande Join Inadequado quando se tem naturalmente:

• muitas relações entre as instancias, ex, famílias• relações recursivas entre as instancias, ex, ancestral• dependências existenciais entre atributos, ex, casado, cônjuge• poucos atributos definidos para todas as instancias

ex, númeroDeRodas e númeroDeMastros para veículos• aninhamento ou hierarquias de valores para muitos atributos,

ex, nordeste, PE, Recife• ou seja quando o esquema de dados relevantes é não

trivial

Tipologia dos atributosTipologia dos atributos Binário:

• Booleano, ex, Male {True,False}• Dicotômico, ex Sex {Male,Female}

Nominal ou categórico ou simbólico:• partição finita de valores sem

ordem nem medida• são apenas = ou • ex, brasileiro, francês, americano

Ordinal ou enumerado ou discreto:• partição finita de valor ordenada

(parcialmente ou totalmente) sem medida

• são apenas =, , , >• ex, fraco, médio, bom, excelente

Intervalar:• partição finita de valor ordenada

com medida m definindo distância d:X,Y, d(X,Y) = |m(X)-m(Y)|

• sem zero inerente• ex, temperatura em grau Celsius

Fracional ou proporcional:• partição com distância zero

inerente• todos os operadores matemático

aplicam-se• ex, temperatura em grau Kelvin

Contínuo: • conjunto infinito de valores

ordenadas com medida, isomorfo a R

Probabilista:• contínuo entre [0,1]• apenas operadores probabilistas

aplicam-se Complexo:

• estrutura interna de sub-atributos aninhados criando tipos compostos

• possivelmente com restrições de valores particulares entre os sub-atributos

• ex, data, endereço

Tipologia dos atributosTipologia dos atributos

Simples

Complexos

BináriasDicotômicas

Booleanas

Qualitativas Nominal

Ordinal

Quantitativas Intervalar

Fracional

Discreta

Contínua

Objeto

Data

Endereço

R

[0,1]

Minerar arquivo flat Minerar arquivo flat x minerar banco de dadosx minerar banco de dados

Para mineração como para outras aplicações, BD fornece:• gerenciamento de memória

segundaria• consultas declarativas

complexas para: selecionar dados agregar dados reagrupar dados derivar novos dados estender meta-dados

• segurança de acesso com usuário múltiplos

• tolerância a falha• com tecnologia padronizada

e escalável

Minerando arquivos flat:• aos poucos, necessidade

desses serviços reaparece• requerendo re-

implementação: ad-hoc com tecnologia inapropriada por conta própria

Conclusão:• API para BD elemento chave

na utilidade prática de uma ferramenta de mineração

Banco de dado operacional xBanco de dado operacional xdata warehouse e data martdata warehouse e data mart

BD operacional:• armazena valores correntes e

atômicas resultantes direitas das últimas transações

• a fins operacionais predefinidas

ex, gerenciamento do estoque

Data Mart: • armazena réplicas históricas,

não voláteis, agregadas ao longo de várias dimensões analíticas

• as vezes limpadas, completadas e normalizadas

• de dados de um único banco operacional

• a fins analíticas abertas de escopo departamental

Data Warehouse:• integra e padroniza dados• de vários:

data marts BD operacionais BD de legado empacotados BD semi-estruturados

extraídos de páginas web

• em um único repositório coerente e limpo de dados

• a fins analíticas abertas de escopo organizacional

Processamento de transações (OLTP)Processamento de transações (OLTP)x processamento analítico (OLAP)x processamento analítico (OLAP)

Características Operacional-OLTP Decisão-OLAPObjetivo Op. diárias do negócio Análisar o negócioVisão dos dados Relacional MultidimensionalOp. com os dados Incl., Alt, Excl e Cons. Carga e ConsultaAtualização Contínua (tempo real) Periódica (Bach)No de usuários Milhares DezenasTipo de usuário Operacional GerencialInteração c/ usuário Pré-definida Pré-definida e ad-hocGranularidade Detalhados Detalhados e ResumosRedundância Não ocorre OcorreVolume Megabytes-Gigabytes Gigabytes-TerabytesHistórico Até uma atualização 5 a 10 anosAcesso a registro Dezenas Milhares

Modelos de dados:Modelos de dados:relacional x multidimensionalrelacional x multidimensional

Produto Região VendasAAAA Norte 50AAAA Sul 60AAAA Central 100AAAA TOTAL 210BBBB Norte 40BBBB Sul 70BBBB Central 80BBBB TOTAL 190CCCC Norte 90CCCC Sul 120CCCC Central 140CCCC TOTAL 350DDDD Norte 20DDDD Sul 10DDDD Central 30DDDD TOTAL 60TOTAL Norte 200TOTAL Sul 260TOTAL Central 350TOTAL TOTAL 810

Produto NORTE SUL CENTRAL TOTALAAAA 50 60 100 210BBBB 40 70 80 190CCCC 90 120 140 350DDDD 20 10 30 60TOTAL 200 260 350 810

Modelo de Modelo de dado multi-dado multi-

dimensional:dimensional:dimensõesdimensõesanalíticas analíticas

com com hierarquias hierarquias conceituaisconceituaisnavegáveisnavegáveis

6 0 5 8 2 5 1 4 4 0 0Q 1

Q 2

Q 3

Q 4

C hic a g o

N e w Yo rk

To ro nto

4 4 0

1 5 6 0

3 9 5

Va n c o u ve r

time

(qua

rters

)

a d d re ss (c

ities)

h o m e e n te rta in m e n t

c o m p u te rp h o n e

ite m (typ e s)

se c u rity

< Va n c o u ve r, Q 1 , se c urity>

Q 1

Q 2

Q 3

Q 4

USA

C a na d a

2 0 0 0

1 0 0 0

time

(qua

rters

)

a d d ress

(co un trie

s)

h o m e e n te rta in m e n t

c o m p u te rp h o n e

ite m (typ e s)

se c u rity

1 5 0

1 0 0

1 5 0

J a n

Fe b

M a rc h

C hic a g o

N e w Yo rk

To ro nto

Va n c o u ve r

time

(mo

nths

)

a d d ress

(citie

s)

h o m e e n te rta in m e n t

c o m p u te rp h o n e

ite m (typ e s)

se c u rity

D rill-d o w n o n tim e d a ta fo r Q 1

Ro ll-u p o n a d d re ss

(a )

(b )

Banco de dados objeto-relacional (O-R) Banco de dados objeto-relacional (O-R) e orientado a objetos (OO)e orientado a objetos (OO)

Objetivo de um SGBD OO ou O-R:• integrar em um único software serviços fornecidos pelos SGBD

e pelas linguagens de programação orientadas a objetos• com elegância conceptual e eficiência de execução

Porque?:• Uniformizar codificação heterogênea dos software atuais:

interface e processamento com LPOO, acesso aos dados com SGBDR

Orientação a objetos estende BD com:• Métodos codificando no próprio BD os comportamentos ligados

aos dados e propiciando completude computacional• Construtores para modelagem de estruturas complexas,

heterogêneas e definidas pelo usuário• Hierarquia de classes com herança e encapsulamento,

facilitando modularidade, reuso e interface com componentes externos

Banco de dados OR e OO: Banco de dados OR e OO: vantagens para mineração de dadosvantagens para mineração de dados

Hierarquias conceituais já fornecidas explicitamente Possibilidade de:

• definir classes de conhecimento minerado no próprio BD como novos tipos compostos

• implementar algoritmos de mineração no próprio BD como métodos

• implementar hierarquia de algoritmos de mineração re-aproveitando e especializando métodos genéricos para dados e conhecimento específicos por herança e sobre-escrita de métodos

Ao contrario dos outros modelos de dados avançados, o modelo O-R já é:• implementado em produtos comerciais de grande porte

(porém ainda não conformes ao padrão SQL´99)

Banco de dados dedutivoBanco de dados dedutivo

BD com 2 partes:• fatos ou parte extensional

predicados com argumentos instanciados em lógica da 1a ordem

ex, trabalha(bob,di,prof). chefe(di,bob). correspondem aos registros dos BD relacionais

• regras de dedução ou parte intensional implicações em lógica da 1a ordem, com uma conjunção de

predicados como premissa é um único predicado como conclusão

ex, patrão(B,E) :- chefe(D,B), trabalha(E,D,_). Semântica lógica:

B,D,E,F chefe(D,B) trabalha(E,D,F) patrão(B,E) correspondem a visões dos BD relacionais

Banco de dados dedutivo (cont.)Banco de dados dedutivo (cont.)

Um BD dedutivo é:• uma base de conhecimento persistente• um programa lógico persistente• uma especificação formal executável

O modelo de dados dedutivo:• generaliza modelo relacional• é computacionalmente completo• é baseado na hipótese de mundo fechado

declarar apenas o que é verdadeiro supor falso tudo que não poder ser provado

• autoriza negação por falha nas premissas da regras• resulta da integração de técnicas de BD e de inteligência

artificial• é ideal para implementar sistemas inteligentes de grande

porte

Banco de dados dedutivo: Banco de dados dedutivo: vantagens para mineração de dadosvantagens para mineração de dados

Deduzir conhecimento de granularidade adequada para geração de insights, antes ou depois da mineração

Representação do conhecimento prévio• Alguns métodos de mineração aproveitam de conhecimento

prévio para gerar novo conhecimento a partir de menos dados Gerenciamento do conhecimento minerado durante e depois

do processo de descoberta

Processo de descobertabaseado no ciclo:

indução dedução

interpretação

Pesquisa já consolidada com fundamentos formais abrangente Porém ainda não resultou nem em um padrão oficial nem SGBD comerciais

Banco de dados probabilistaBanco de dados probabilista

BD para gerenciamento de dados incertos BD relacional probabilista:

• cada célula de tabela contém vários valores no lugar de um• cada valor é anotado com sua probabilidade

BD dedutivo probabilista:• cada fato e cada regra anotado com sua probabilidade

Dados derivados por indução a partir de dados primitivos certos, necessariamente carregam um grau de incerteza

BD probabilista formalismo interessante para:• gerenciamento do conhecimento induzido por mineração• tanto durante o processo de descoberta• como depois, durante a utilização do conhecimento na aplicação

Pesquisa já consolidada porém ainda não resultou nem em um padrão oficial nem em SGBD comerciais

Banco de dados indutivoBanco de dados indutivo

BD incorporando conhecimento induzido a partir de dados primitivos por mineração

Ideal para:• gerenciamento de conhecimento minerado durante o

processo de descoberta• aplicação do conhecimento minerado depois do processo

Problemática:• representação da variedade das estruturas de conhecimento

mineradas• propagação da confiabilidade do conhecimento induzido

através de vários ciclos de derivação (i.e., minerar resultado de mineração)

• atualização consistente e eficiente do conhecimento induzido depois da atualização ou extensão dos dados primitivos

O futuro, porém pesquisa ainda incipiente

Jacques RobinCIn-UFPE

Tipologia do conhecimento de Tipologia do conhecimento de saídasaída

da mineração de dadosda mineração de dados

Dimensões descritivas da tipologia Dimensões descritivas da tipologia das estruturas de conhecimento a das estruturas de conhecimento a

minerarminerar

Descrição concisa de dados disponíveis x previsão de dados não disponíveis

Representações de conceitos x de instâncias Representações atributivas x relacionais Representações simbólicas x numéricas

• simbólicas: poder expressivo da lógica subjacente lógica clássica de ordem 0, 1, 2, lógicas não clássicas

• numéricas: poder expressivo da função subjacente domínio e imagem: Z x R [0,1], R2 N, etc. característica da função:

¤ propriedades matemáticas: monotonia, continuidade, etc.¤ formula analítica: linear, polinomial, exponencial, logarítmica,

trigonométrica, cônica, etc.

Mineração descritiva x mineração Mineração descritiva x mineração preditivapreditiva

Mineração descritiva:• Apenas descreve de forma concisa os dados disponíveis• A descrição minerada pode:

diretamente fornecer insight para analista humano, ou servir de passo preliminar para mineração preditiva

• Usa igualmente técnicas de banco de dados, estatística e aprendizagem de máquina

Mineração preditiva:• Prevê dados não disponíveis a partir do dos dados disponíveis• A previsão pode:

diretamente indicar uma descoberta ou decisão a tomar servir de passo intermediário para tomada de uma descoberta ou

decisão complexa estruturada por camadas

• Usa principalmente técnicas de aprendizagem de máquina

Mineração descritiva: tipos de descriçõesMineração descritiva: tipos de descrições

Medida de similaridade ou dissimilaridade entre instâncias• ex, cliente fulano parecido com sicrano e bem diferente de beltrano

Grupos de instâncias alta similaridade intra-grupos e alta dissimilaridade inter-grupos (clustering)• ex, {fulano, sicrano, ...}, {beltrano, john, ...}, {doe}, ...

Exceções (outliers), i.e., instâncias com valor altamente dissimilar com a maioria das outras instâncias, para um ou vários atributos

Valores de atributos para grupos de instâncias agregados ao longo de dimensões analíticas, • ex, media de venda de bebidas no Nordeste em dezembro é R$2.106

Atributos relevantes para caracterizar instâncias de uma classe• ex, {sexo, colégio, pais, idade, notaMédia} para alunos

Atributos relevantes para discriminar entre instâncias de 2 classes• ex, {sexo, colégio, notaMédia} entre alunos de engenharia e artes cênicos

Associações entre valores dos atributos descritivos das instâncias• age(X,[20,29]} income(X,[3000, 10000])

ownd(X,CD,[50,100]) owns(X,PC). [suport = 5%, confidence = 80%]

Mineração preditiva: tipos de inferênciaMineração preditiva: tipos de inferência

Classificação: inferir a classe de um novo indivíduo em função dos seus atributos descritivo

Regressão: inferir o valor do atributo A (geralmente numérico) desconhecido de um indivíduo em função de: • seus atributos conhecidos e,• dos valores conhecidos de A para os outros indivíduos

Análise de evolução ou previsão stricto-sensus: inferir o valor de um atributo de um indivíduo em um instante t em função dos seus atributos descritivos nos instantes anteriores

Controle: inferir a melhor ação a executar por um agente inteligente dado seus objetivos e o estado do ambiente no qual ele opera

Classificação e regressão podem servir de passo intermediário para análise de evolução

Os três podem servir de passos intermediários para controle

Representação de conceito x de Representação de conceito x de instânciainstância

Conceito: • representação em intenção via conjunto de restrições de valor

sobre alguns atributos descritivos armazenados no BD Instancia:

• indivíduo cujos dados satisfazem essas restrições Aprendizagem guloso:

• cria representação em intenção (conceito) e classifica um novo indivíduo se seus atributos casam com essa representação

Aprendizagem preguiçoso:• classifica novo indivíduo como sendo da classe do indivíduo

mais próximo dele em termos de valores de atributos• ou do centroide dos N indivíduos mais próximos• não representa conceitos em intenção• classe representada apenas pela extensão das suas instâncias

Representação atributivas x relacionaisRepresentação atributivas x relacionais

Representar propriedades de um único indivíduo• Logicamente quantificação universal limitada a uma única

variável• Equivalente a lógica proposicional (ordem 0), já que essa

variável pode ficar implícita• ex, P, quality(P,fair) price(P,low) buy(P)

fairQuality cheap buy• Representa intencionalmente conteúdo de apenas uma

tabela de BD relacional Representar relações entre vários indivíduos

• Logicamente requer quantificação universal simultânea de várias variáveis

• Requer sub-conjunto da lógica da 1a ordem• ex, P, C parent(P,C) female(P) mother(P,C).• Representa intencionalmente conteúdo de várias tabelas de

BD relacional (ou até o banco inteiro)

Tipologia das estruturas de Tipologia das estruturas de conhecimento conhecimento

a minerara minerar Paradigma simbólico:

• Árvore de decisão• Árvore de regressão• Regras de associação

atributivas• Regras de classificação

atributivas• Regras relacionais• Grupos atributivos de

instâncias

Paradigma matemático:• Função de distância numérica• Função de regressão

Paradigma probabilista:• Densidade de probabilidade

Paradigma conexionista:• Perceptrão multi-camada• Memória associativa

Paradigma evolucionário:• população de representações

simbólicas simples (bit string, árvore)

Multi-paradigma:• Árvores de modelo (simbólico e matemático)• Redes bayesianas (conexionista, simbólico e probabilista)

Árvore de decisãoÁrvore de decisão

Função de regressão numéricaFunção de regressão numérica

50

80

100

10 15

60

40

20

020 25

Ye a rs e xp e rie nc e

Sala

ry (i

n $1

,000

)

PRP = - 56.1 + 0.049MYCT + 0.015MMIN + 0.006MMAX + 0.630CACH - 0.270CHMIN + 1.46CHMAX

Árvore de regressãoÁrvore de regressão

Árvore de modeloÁrvore de modelo

LM1: PRP = 8.29 + 0.004 MMAX + 2.77 CHMINLM2: PRP = 20.3 + 0.004 MMIN – 3.99 CHMIN + 0.946 CHMAXLM3: PRP = 38.1 + 0.012 MMINLM4: PRP = 19.5 + 0.002 MMAX + 0.698 CACH + 0.969 CHMAXLM5: PRP = 285 – 1.46 MYCT + 1.02 CACH – 9.39 CHMINLM6: PRP = -65.8 + 0.03 MMIN – 2.94 CHMIN + 4.98 CHMAX

Regras atributivas de classificaçãoRegras atributivas de classificação

Mineração preditiva Implicações lógica com:

• Apenas uma variável quantificada• Premissas relacionada apenas por uma conjunção• Cada premissas apenas testa valor de um atributo de um

indivíduo• Conclusão única e positiva indica classe das instâncias

verificando a conjunção de premissas X, atr1(X,val1) ... atrn(X,valn) class(X,c) X, atr1Val1(X) ... atrnValn(X) C(X) atr1 = val1 ... atrn valn C IF atr1 = val1 AND ... AND atrn valn THEN C

ex, IF tempo = sol AND dia = Dom THEN racha

Regras de Classificação vs. ÁrvoresRegras de Classificação vs. Árvores

Regras de classificação podem ser convertidas em árvores de decisão e vice-versa

Porém:• a conversão é em geral não trivial• dependendo da estrutura do espaço de instâncias,

regras ou árvores são mais concisas ou eficientes

Regras são compactas Regras são em geral altamente modulares (mas

raramente são completamente modulares)

Vantagens de Árvores de DecisãoVantagens de Árvores de Decisão

Exemplo de conversão árvore -> regras

• Sem mecanismo de interpretação preciso regras podem ser ambíguas• Instâncias podem “passar através” de conjunto de regras não sistematicamente “fechado”

X > 1.2

Y > 2.6b

ab

simnão

simnão

IF x >1.2 AND y > 2.6 THEN class = a

If x < 1.2 then class = b

If x > 1.2 and y < 2.6 then class = b

Vantagens de Regras de ClassificaçãoVantagens de Regras de Classificação

•Árvores são redundantes e não incrementais•Árvores não são ambíguas e não falham em classificar

x

y

z

w

a

bb

a bb

1

1

1

1

2

2

2

2 3

3

3

3

If x=1 and y=1

then class = a

If z=1 and w=1

then class = b

Exemplo de conversão regra/árvore

Regras atributivas de associaçãoRegras atributivas de associação

Mineração descritiva Implicações lógica com:

• Apenas uma variável quantificada• Premissas e conclusões relacionadas apenas por uma

conjunção• Cada premissa e cada conclusão apenas testa valor de

um atributo de um indivíduo X, atr1(X,val1) ... atri(X,vali)

atrj(X,valj) ... atrn(X,valn) IF atr1 = val1 AND ... AND atri vali

THEN atrj = valj AND ... AND atrn valn ex, IF tempo = sol AND dia = domingo

THEN praia = cheia AND avenida = engarrafada

Regras relacionaisRegras relacionais

Mineração descritiva ou preditiva (classificação ou controle)

Implicações lógica com:• Várias variáveis quantificadas• Premissas relacionadas apenas por uma conjunção• Cada premissa testa valor de um atributo de um indivíduo

ou teste relação entre indivíduos• Conclusão única positiva cujo predicado pode aparecer nas

premissas (regras recursivas)• Cláusulas de Horn

X,Y,Z,... atr1(X,val1) ... reli(X,Y) atrj(Z,valj) X,Y,Z,... atr1(Y,val1) ... reli(X,Y) relj(X,Y,valj) X,Y,Z,... atr1(Z,val1) ... reli(X,Y,Z) reli(X,Y,Z) reli(X,Y,Z) :- atr1(Z,val1), ... , reli(X,Y,Z)

Necessidades das regras relacionaisNecessidades das regras relacionais

Conhecimento a priori

name1 = ann…name5 = tomfather11 = F…father31 = T…father54 = Tmother11 = F…mother55 = Ffemale1 = T…female5 = Fmale1 = F

Exemplos positivos:daughter42 = Tdaughter13 = T

Exemplo negativos:daughter11 = F…daughter44 = F

Aprende:daughter13(D,P) :- female3(D),

parent13(P,D).daughter42(D,P) :- female4(D),

parent42(P,D).

Necessidades das regras relacionaisNecessidades das regras relacionais

Conhecimento a prioriIntencional:parent(F,C) :- father(F,C). parent(M,C) :- mother(P,C).Extensional:father(pat,ann).father(tom,sue).female(ann).female(eve).female(sue).male(pat).male(tom).mother(eve,sue).mother(ann,tom).

ExemplosPositivos:daughter(sue,eve).daughter(ann,pat).Negativos:not daughter(tom,ann).not daughter(eve,ann).

Aprende:daughter(D,P) :- female(D), parent(P,D).

Grupos de instâncias Grupos de instâncias (clusters)(clusters)

Dimensões descritivas da tipologia dos grupos• disjuntos x overlapping• chatos ou hierárquicos• deterministas x probabilistas x nebulosos• baseados em distâncias x baseados em densidade• propriedades matemáticas da superfície

g a c i e d k b j f h

a

k

j

i

h

g

f

ed

c

ba

k

j

i

h

g

f

ed

c

b

1 2 3

a 0.4 0.1 0.5b 0.1 0.8 0.1c 0.3 0.3 0.4d 0.1 0.1 0.8e 0.4 0.2 0.4f 0.1 0.4 0.5g 0.7 0.2 0.1h 0.5 0.4 0.1…

Rede bayesianaRede bayesiana

Fa m ilyHisto ry

Lung C a nc e r

Po sitive XRa y

Sm o ke r FH, S FH, ~ S ~ FH, S ~ FH, ~ S0.8 0.5 0.7 0.10.2

LC~ LC 0.5 0.3 0.9

Em p hyse m a

Dysp ne a

(a ) (b )