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çoex : 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 :

MultiMediaMinerThumbnails

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