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

Salar

y (in

$1,0

00)

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 relacionaisConhecimento a priori

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

Exemplos positivos:daughter42 = Tdaughter13 = TExemplo negativos:daughter11 = F…daughter44 = FAprende: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 )