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