Tipologia dos dados de entrada
da mineração de dados
Jacques Robin
CIn-UFPE
Tipologia da fontes de dados para mineraçã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 (flat 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:
formato 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 }
@data
sunny, 85, 85, false, no
sunny, 80, 90, true, no
overcast, 83, 86, false, yes
rainy, 70, 96, false, yes
rainy, 68, 80, false, yes
rainy, 65, 70, true, no
overcast, 64, 65, true, yes
sunny, 72, 95, false, no
sunny, 69, 70, false, yes
rainy, 75, 80, false, yes
sunny, 75, 70, true, yes
overcast, 72, 90, true, yes
overcast, 81, 75, false, yes
rainy, 71, 91, true, no
Arquivo texto chato padronizado (flat 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 atributos

Binário:
•
•

Booleano, ex, Male  {True,False}
Dicotômico, ex Sex  {Male,Female}
•
•
partição finita de valores sem ordem
nem medida
são apenas = ou 
•
•


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

ex, temperatura em grau Kelvin
conjunto infinito de valores ordenadas
com medida, isomorfo a R
Probabilista:
•
•
partição finita de valor ordenada
(parcialmente ou totalmente) sem
partição com distância zero inerente
todos os operadores matemático
aplicam-se
Contínuo:
•
ex, brasileiro, francês, americano
Ordinal ou enumerado ou discreto:
Fracional ou proporcional:
•
•
Nominal ou categórico ou simbólico:
•


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 atributos
Booleanas
Discreta
Binárias
Qualitativas
Dicotômicas
Nominal
Ordinal
Quantitativas
Simples
Intervalar
Fracional
Contínua
R
[0,1]
Data
Complexos
Endereço
Objeto
Minerar arquivo flat
x minerar banco de dados

Para mineração como para
outras aplicações, BD fornece:

• aos poucos, necessidade desses
serviços reaparece
• requerendo re-implementação:
• 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:




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 x
data 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 Warehouse:
• integra e padroniza dados
• de vários:





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 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)
x processamento analítico (OLAP)
Características
Operacional-OLTP
Decisão-OLAP
Objetivo
Visão dos dados
Op. com os dados
Atualização
No de usuários
Tipo de usuário
Interação c/ usuário
Granularidade
Redundância
Volume
Histórico
Acesso a registro
Op. diárias do negócio
Relacional
Incl., Alt, Excl e Cons.
Contínua (tempo real)
Milhares
Operacional
Pré-definida
Detalhados
Não ocorre
Megabytes-Gigabytes
Até uma atualização
Dezenas
Análisar o negócio
Multidimensional
Carga e Consulta
Periódica (Bach)
Dezenas
Gerencial
Pré-definida e ad-hoc
Detalhados e Resumos
Ocorre
Gigabytes-Terabytes
5 a 10 anos
Milhares
Modelos de dados:
relacional x multidimensional
Produto
AAAA
AAAA
AAAA
AAAA
BBBB
BBBB
BBBB
BBBB
CCCC
CCCC
CCCC
CCCC
DDDD
DDDD
DDDD
DDDD
TOTAL
TOTAL
TOTAL
TOTAL
Região
Norte
Sul
Central
TOTAL
Norte
Sul
Central
TOTAL
Norte
Sul
Central
TOTAL
Norte
Sul
Central
TOTAL
Norte
Sul
Central
TOTAL
Vendas
50
60
100
210
40
70
80
190
90
120
140
350
20
10
30
60
200
260
350
810
Produto NORTE SUL CENTRAL TOTAL
210
AAAA
50
60
100
190
BBBB
40
70
80
350
CCCC
90
120
140
60
DDDD
20
10
30
TOTAL
200
260
350
810
s)
itie
c
s(
Chic ago 440
es
r
d
d
New
York 1560
a
Toronto
time (quarters)
Vanc ouver
Q1
605
825
14
< Vanc ouver,
Q1, sec urity>
400
Q2
Q3
Q4
c omputer
sec urity
home
phone
entertainment
(a)
item (types)
(b)
Drill-down
on time data for Q1
tie
ci
(
s
es
dr
Roll-up
on address
s)
ad
Chic ago
New York
c
s(
es
r
d
s)
rie
t
n
ou
USA
Canada
Toronto
Vanc ouver
time (quarters)
ad
time (m onths)
Modelo de
dado multidimensional:
dimensões
analíticas com
hierarquias
conceituais
navegáveis
395
Q2
150
Feb
100
Q3
Marc h
150
Q4
item (types)
1000
Q1
Jan
c omputer
sec urity
home
phone
entertainment
2000
c omputer
sec urity
home
phone
entertainment
item (types)
Banco de dados objeto-relacional (O-R)
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
Exemplo de BD O-R: esquema de BD
acadêmico brinquedo em SQL´99
Esquema: definição das classes
create type pessoa
as (nome varchar(20), nasc date)
instanciable not final ref pessoa_id
instance method idade returns int
instance method meiaIdade returns boolean;
create type empreg under pessoa
as (cargo varchar(20), salario real,
titulação varchar(20), depto ref(depto),
publi set(ref(publi))
instanciable not final ref empreg_id;
create type prof under empreg
as (cargo varchar(20) default professor,
salario int default 50,000,
titulação int default “PhD.”)
instanciable not final ref prof_id
instance method meiaIdade returns boolean;
create type publi
as (nome varchar(20), autores set(ref(empreg)))
instanciable not final ref publi_id;
create type depto
as(nome varchar(20), chefe ref(prof),
empregs set(ref(empreg)))
instanciable not final ref depto_id;
create table pessoas of pessoa
create table empregs of empreg
create table profs of prof
create table deptos of depto
create table publis of publi
Exemplo de BD O-R: esquema de BD
acadêmico brinquedo em SQL´99 (cont.)
Esquema: restrições de integridades
create assertion restrição_chefe
check (not exists
(select * from deptos d, empregs e,
where d.chefe->cargo <> “professor”));
create assertion restrição_prof
check (not exists
(select * from profs p where p.cargo <>
“professor”));
Esquema: definição dos métodos
create method idade of pessoa ?
begin
declare i; declare date d; set d = today();
set i = d.year - self.nasc.year;
if (d.month < self.nasc.month) ||
((d.month = self.nasc.month) &&
(d.day < self.nasc.dat)))
then return i - 1;
else return i;
endif;
end;
create method meiaIdade of pessoa
return (self.idade => 30) && (self.idade <= 60);
Exemplo de BD O-R: dados de BD acadêmico
brinquedo em SQL´99
insert into profs(nome,nasc) values(“Bob”, 01021960) ;
insert into deptos (nome, chefe) values (”DI”, select ref from profs where nome = “Bob”);
insert into profs(depto) values (select ref from deptos where nome = “DI”);
insert into empregs(nome,depto,cargo) values (”John”, select ref from deptos where nome = “DI”,”assistente”);
insert into empregs(nome,depto,cargo) values (”Sally”, select ref from deptos where nome = “DI”,”assistente”);
insert into profs(nome,depto,cargo,titulação)
values (“Mary”, select ref from deptos where nome = “DI”, ”assistente”, “mestre”);
insert into profs(nome,depto,cargo,titulação)
values (“Phil”, select ref from deptos where nome = “DI”, ”professor”);
update depto set empregs = select ref from profs where nome = “Bob” union
select ref from empregs where nome = “Mary” union
select ref from profs where nome = “Phil” union
select ref from profs where nome = “John” union
select ref from profs where nome = “Sally”
where nome = “DI”);
insert into publis(nome,autores) values (“Florid - CACM”, select ref from empregs where nome = “Phil” union
select ref from profs where nome = “Bob” union
select ref from profs where nome = “Mary”);
insert into publis(nome,autores) values (“F-Logic - JACM”, select ref from empregs where nome = “Mary” union
select ref from profs where nome = “Bob” union
select ref from profs where nome = “John” union
select ref from profs where nome = “Sally”);
Exemplo de BD O-R: : consultas a um BD
acadêmico brinquedo em SQL´99
Quem são os empregados do departamento de informática de meia idade que são
seus próprio chefe?
select e.nome from empregs
where e.meiaIdade = true and e = e.depto->chefe;
Quem publicou com Mary no JACM?
select e.nome from empregs
where “JACM” in e.publis->nome and “Mary” in e.publis->autores->nome;
Onde Mary publicou junto com Phil?
select p.nome from publis
where “Mary” in p.autores->nome and “Phil” in p.autores->nome;
Banco de dados OR e OO:
vantagens 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 reaproveitando 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 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:

correspondem a visões dos BD relacionais
 B,D,E,F chefe(D,B)  trabalha(E,D,F)  patrão(B,E)
Banco de dados dedutivo (cont.)

Consultas em um BD dedutivo:
•
•
•
•
•
predicado, com argumentos geralmente não instanciados
ex, patrão(B,B)
Semântica lógica:  B, patrão(B,B)
dispara provador automático de teorema embutido no SGBD
consegue responder a consultas sobre fatos não explicitamente
armazenados no BD pela aplicações repetida das regras de
dedução a partir dos fatos explicitamente armazenado
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
Exemplo de BD dedutivo: um BD acadêmico
brinquedo em RelationLog
Esquema:
titulacao(F,phd) :- trabalha(F,_,prof),
not titulacao(F,ms).
salario(P,50000) :- trabalha(F,_,prof),
not salario(F,_).
meiaIdade(F) :- idade(F,A), integer(A),
A >= 30, A =< 60.
meiaIdade(F) :- trabalha(F,_,prof).
trabalha(B,D,prof) :- chefe(D,B),
trabalha(E,D,prof).
patrão(B,E) :- chefe(D,B), trabalha(E,D,_).
Dados:
idade(bob,40). trabalha(bob,di,prof).
chefe(di,bob).
trabalha(john,di,assist).
trabalha(sally,di,assist).
titulacao(mary,ms). trabalha(mary,di,prof).
trabalha(phil,di,prof).
publi(jacm,{john,sally,mary,bob}).
publi(cacm,{phil,mary,bob}).
Consultas:
? meiaIdade(<B>), trabalha(<B>,di,_),
patrão(<B>,<B>).
B = {bob}.
?- publi(jacm,<F,mary>), F \= mary.
F = {bob}.
?- publi(P,<phil,mary>).
P = {cacm}.
Banco de dados dedutivo:
vantagens 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 descoberta
baseado no ciclo:
interpretação
indução
deduçã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 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 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
Download

MiningInput - Centro de Informática da UFPE