MINERAÇÃO DE DADOS
BANCOS DE DADOS NÃO CONVENCIONAIS
BDs NÃO CONVENCIONAIS
• BDs de estrutura complexa
• BDs de Planos
• BDs Espaciais
• BDs Multimedia
• Arquivos flat
• Web
BDs DE ESTRUTURA COMPLEXA
• Aspecto relevante : GENERALIZAÇÃO
– Generalização de atributos multivalorados :
• Atributos com conjunto de valores (set-valued data)
• Atributos com lista de valores (list-valued data)
• Atributos com estruturas aninhadas (nested
structured data)
Atributos com conjunto de valores
(set-valued data)
• Generalização de cada valor do conjunto para
hierarquia de nível mais alto
ex : alimento = {maçã, uva, couve-flor, cebola, arroz}
generalização pode ser {frutas, verduras, cereais}
ou
• Derivação do comportamento geral do conjunto
– Número de elementos, tipos ou intervalos de valores,
média para dados numéricos ;
Atributos com lista de valores
(list-valued data)
• Generalização semelhante à de atributos com conjunto de
valores, exceto que a ordem dos elementos deve ser
mantida na generalização ;
• Uma lista pode ser generalizada excluindo-se os elementos
menos importantes ou mantendo apenas o mais importante:
ex: Atributo historico_escolar =((Tecnico em contabilidade,
Esc.Tecnica, 1990),(Mestrado em Matemática, UFPE,
1994),(Doutorado em Matemática, UFPE, 1998)) ;
Manter, por exemplo : (Doutorado em Matemática, UFPE, 1998)
Atributos com estruturas aninhadas
(nested structured data)
• Um atributo complexo pode conter conjuntos,
listas, registros, árvores, e a combinação destes,
onde uma estrutura pode estar aninhada em outra.
Generalização :
1. Generalizar cada atributo da estrutura e manter o
formato da estrutura ;
2. Transformar a estrutura num flat file e generalizá-la a
partir daí ;
3. Retornar o tipo da estrutura ;
Generalização em BDs Espaciais
• Agregação e aproximação :
– Generalização de pontos geográficos em grupos de
regiões tais como regiões de negócio, residencial,
agricultura ou indústria de acordo com o uso da terra ;
Generalização em BDs Multimidia
• Reconhecimento e extração de características
essenciais ou padrões gerais ;
– Imagem :
Tamanho, cor, formato podem ser extraídos por agregação
ou aproximação ;
– Música :
Resumo Melodia => Padrões que ocorrem repetidamente
no segmento ;
Resumo Estilo => Baseado no tom, tempo ou principais
instrumentos tocados ;
GENERALIZAÇÃO
Identificadores de Objetos e Classes
1 - O OID é generalizado para o ID da mais baixa
subclasse à qual o objeto pertence ;
2 - O ID da subclasse é generalizado para o ID da
classe escalando-se um nível acima na hierarquia
de classes ;
3 - Similarmente, uma classe pode ser generalizada
para sua super-classe correspondente escalando-se
um nível acima na hierarquia de classes ;
Mineração de cubos de objetos
• Estende-se o Método de Indução Orientado a Atributo ,
visto em mineração de características em BDs relacionais ;
• Aplica-se uma sequência de operadores de generalização
baseado em classes ;
• Controle do limite da generalização :
– Até a classe resultante conter um número pequeno de objetos ;
• Por eficiência :
– Cada atributo multivalorado de um objeto complexo é generalizado
para conter dados simples, univalorados ;
– Constrói-se um Cubo de Objetos ;
• Problema :
– Nem sempre é desejável se generalizar dados multivalorados !
BANCOS DE DADOS DE PLANOS
• PLANO : Sequência variada de ações ;
• BD de Planos : Coleção de planos ;
• Mineração de plano : Tarefa de se minerar
conhecimento ou padrões significantes de um BD
de Planos .
Exemplo - Plano de vôo
Como minerar esta base de planos ?
Mineração da base
Passos :
(1) Generalizar a Base de planos em diferentes
direções usando o modelo multidimensional ;
(2) Observar planos generalizados que possuem
padrões em comum e sequenciais interessantes
com bom suporte ;
(3) Derivar planos concisos de alto nível ;
Visão Multidimensional
Ex : num_passageiros < 50.000 => categoria = “S”
num_passageiros > 50.000 => categoria = “L”
Generalização Multidimensional
Daí, podemos encontrar padrões sequenciais genéricos, como :
[S] - L+ - [S]
[98,5%]
Estratégia dividir pra conquistar
• Ao encontrar um padrão genérico com um suporte alto, podemos
particionar o plano base em subplanos ;
• A partir daí, mineramos cada subsequência para encontrar
características em comum ;
• Para o exemplo dado, podemos gerar a regra :
vôo(x,y) ^ categoria(x,S) ^ categoria(y,L)
=> região(x) = região(y) [75 %]
• O plano base é particionado em subplanos base e características
interessantes são descobertas pelo processo de mineração de dados .
BANCOS DE DADOS ESPACIAIS
• Armazena grande quantidade de dados
relacionados ao espaço :
–
–
–
–
Imagens médicas
Mapas
Navegação
Controle tráfego aéreo
• Armazena informações topológicas e de distância
• Desafio em mineração :
– Encontrar técnicas eficientes de mineração (grande quantidade de
dados , complexidade de tipos e de métodos de acesso)
Construção de D.W. Espacial
• Desafios :
– Integração de dados de vários sistemas e fontes
heterogêneas
• Estrutura baseada em vetores, objetos ou relacionais
• Fornecedor : Mapinfo, intergraph ...
– Realização de OLAP rápido e flexível em DW
espacial
• Algumas dimensões e medidas possuem
comportamento espacial
Cubos de dados espaciais
• Três dimensões presentes :
– Dimensão não-espacial ex: temperatura : 35 a 45 º C --> quente
– Dimensão espacial p/ não -espacial ex: Pernambuco --> “região
_nordeste”
– Dimensão espacial p/ espacial ex : Pernambuco --> Nordeste
• Dois tipos de medidas :
– Medida numérica
• Distributiva: Obtida pela aplicação da função de agregação ex: count()
• Algébrica: Obtida pela aplicação da função algébrica ex: avg =
sum()/count()
• Holística : Não deriva de função algébrica ex: Median()
– Medida espacial
• ex: Coleção de ponteiros para região de mesma temperatura
DW espacial: BC_weather
Esquema estrela :
OPERAÇÕES DE ROLL-UP
Por Temperatura
Por Precipitação
Computação de medidas espaciais em cubos
de dados
• Dilema : armazenamento x custo computacional
– Armazenamento de ponteiros para objetos sem précomputação de medidas espaciais
– Pré-computação e armazenamento aproximado de
medidas espaciais
• ex: estimativa de região
– um retângulo - MBR (min.bounding rectangle) pode ser visto
como uma estimativa grosseira do mapa de uma região
– Materialização de porções de cubos que mais se tem
acesso
• Examinar cada grupo de obj. espaciais que podem sofrer merge
Regras de associação espacial
• Forma : A => B [s%,p%]
é_uma (X,”escola”)^perto_de(X,”clube”) => perto_de(X,”parque”)
[0.5%,80%]
• Predicados espaciais :
• perto_de , longe_de (relacionado a distância)
• intercepta, sobrepõe (relacionado a topologia)
• à_esquerda, à_direita, à_oeste (orientação espacial)
Classificação e análise de tendência
• Classificação de regiões :
– rica x pobre (propriedades associadas a objetos
espaciais)
ex: possui universidade ? Shoppings ?
• Análise de tendência (espacial e temporal)
– Mudança de dados (espaciais ou não) com o espaço
ex: Distância do oceano muda clima e vegetação
– Mudança de padrões com o tempo e espaço
ex : Fluxo de tráfego em rodovias e cidades
BDs MULTIMIDIA
• Armazenam e gerenciam objetos multimídia, tais como
imagem, audio, vídeo, hipertexto
• Sistemas de recuperação de similaridades em imagens :
– Baseado em descrição :
• Manualmente : laborioso
• Automaticamente : resultado de baixa qualidade
• Ex: palavra-chave, título, tamanho, tempo de criação
– Polissemia : uma só forma com mais de um significado
– Baseado em conteúdo :
• Usa características visuais para indexar imagens e fazer a
recuperação baseada em similaridade com outras imagens
• Ex: Textura, forma, cor, objetos
MultiMediaMiner
• Sistema de mineração de dados multimídia
• Imagem : grid 8 x 8
• Cada imagem contém dois descritores :
– Descritor de características
• Imagem original não é armazenada diretamente no BD, mas
nome do arquivo, URL, tipo da imagem, URLs pais
– Descritor de layout
• Vetor de cores - cor mais frequente em cada uma das 64
células
• Vetor de margens - Número de lados em cada uma das células
MultiMediaMiner
Dimensões em cubo de dados multimídia :
MultiMediaMiner
Thumbnails
Minerando associações
Que tipos de associação podem ser mineradas em BDs
multimídia ?
• Três categorias de associação :
– Associação entre conteúdo de imagem e de não-imagem
Se 50% da parte superior da imagem é azul então é “céu”
– Associação entre conteúdo de imagens não relacionadas ao espaço
Se imagem possui dois quadrados azuis então contém círculo
vermelho
– Associação entre conteúdo de imagens relacionadas ao espaço
Se imagem possui um triângulo vermelho entre dois quadrados
então contém grande círculo abaixo
Mineração de regras de associações
BDs transacionais x BDs multimídia
• Refinamento progressivo de resolução : Uma imagem pode conter
muitos objetos com características diferentes, tais como cor, forma,
textura ... semelhança de características numa resolução baixa podem
diferir em uma resolução melhor;
• Uma figura contendo dois objetos iguais difere daquela contendo
apenas um objeto do mesmo tipo em BDs multimídia. Em BDs
transacionais, a pessoa comprar uma ou duas caixas de leite é tratado
como o mesmo atributo compra_leite ;
• Existem relações espaciais entre objetos multimídia, tais como acima,
através de , abaixo, à esquerda ...
Conclusão
• A cada dia , mais e mais dados são armazenados de forma
complexa, estruturados ou não estruturados, hipertexto e
multimídia ;
• Mineração de tipos complexos de dados, tais como objetos,
dados espaciais, multimídia, dados seriais-temporais,
textos e web tem se tornado uma tarefa muito importante ;
• Mineração de dados complexos ainda está em fase inicial,
e muitos desafios ainda terão de ser superados.
Bibliografia
• Han, Jiawei. Kamber, Micheline. Data Mining: Concepts
and Techniques - Morgan Kaufmann Publishers.
• MultiMediaMiner. Site - http://db.cs.sfu.ca/MMMiner
• Bechara, Evanildo. Moderna Gramática Portuguesa Editora Lucerna / Rj - 2000