Tipologia do conhecimento de saída
da mineração de dados
Jacques Robin
CIn-UFPE
Dimensões descritivas da tipologia
das estruturas de conhecimento a minerar
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 preditiva

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ções

Medida de similaridade ou dissimilaridade entre instâncias
•




Grupos de instâncias alta similaridade intra-grupos e alta dissimilaridade
inter-grupos (clustering)
•
ex, {fulano, sicrano, ...}, {beltrano, john, ...}, {doe}, ...
•
ex, media de venda de bebidas no Nordeste em dezembro é R$2.106
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,
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, cliente fulano parecido com sicrano e bem diferente de beltrano
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ê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 instâ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 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 conhecimento
a 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
Função de regressão numérica
PRP = - 56.1 + 0.049MYCT + 0.015MMIN + 0.006MMAX
+ 0.630CACH - 0.270CHMIN + 1.46CHMAX
Salary (in $1,000)
100
80
60
40
20
0
0
5
10
15
Years experience
20
25
Árvore de regressão
Árvore de modelo
LM1: PRP = 8.29 + 0.004 MMAX + 2.77 CHMIN
LM2: PRP = 20.3 + 0.004 MMIN – 3.99 CHMIN + 0.946 CHMAX
LM3: PRP = 38.1 + 0.012 MMIN
LM4: PRP = 19.5 + 0.002 MMAX + 0.698 CACH + 0.969 CHMAX
LM5: PRP = 285 – 1.46 MYCT + 1.02 CACH – 9.39 CHMIN
LM6: PRP = -65.8 + 0.03 MMIN – 2.94 CHMIN + 4.98 CHMAX
Regras 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. Á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ão
Exemplo de conversão árvore -> regras
X > 1.2
não
b
IF x >1.2 AND y > 2.6 THEN
class = a
sim
If x < 1.2 then class = b
Y > 2.6
não sim
b
If x > 1.2 and y < 2.6 then
class = b
a
• 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”
Vantagens de Regras de Classificação
Exemplo de conversão regra/árvore
If x=1 and y=1
x
1
2
y
1 2
3
then class = a
a
z
If z=1 and w=1
1 2
3
then class = b
w
b
b
1
3
2
a
b
b
•Árvores são redundantes e não incrementais
•Árvores não são ambíguas e não falham em
classificar
3
Regras 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 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 relacionais
Conhecimento a
priori
name1 = ann
…
name5 = tom
father11 = F
…
father31 = T
…
father54 = T
mother11 = F
…
mother55 = F
female1 = T
…
Exemplos positivos:
daughter42 = T
daughter13 = 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 relacionais
Conhecimento a priori
Intencional:
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).
Exemplos
Positivos:
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 (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
d
d
e
a
a
c
j
h
k
f
g
i
e
h
k
b
c
j
f
g
b
i
g a c i e d k b j f h
a
b
c
d
e
f
g
h
…
1
2
3
0.4
0.1
0.3
0.1
0.4
0.1
0.7
0.5
0.1
0.8
0.3
0.1
0.2
0.4
0.2
0.4
0.5
0.1
0.4
0.8
0.4
0.5
0.1
0.1
Rede bayesiana
(a)
(b)
FamilyHistory
Smoker
LungCancer
Emphysema
PositiveXRay
Dyspnea
FH, S FH, ~ S ~ FH, S~ FH, ~ S
LC 0.8
0.5
0.7
0.1
~ LC 0.2
0.5
0.3
0.9