Mineração de Bancos de Dados Não
Convencionais
André Novaes
Rafael Palermo
CIn-UFPE
Roteiro
• Bancos de dados não convencionais
• consultar BD multimídia (baseado em metadados ou contéudo)
• BD O-R e OO
• generalização por indução orientada a atributos e OLAP
• BD de planos
• BD espaciais
• generalização por indução orientada a atributos e OLAP
• regras de associação
• clustering
• classificação
• series espaço-temporais
• BD multimídia
• Generalização por indução orientada a atributos e OLAP
• regras de associação
• Classificação e predição
Roteiro
•
•
•
•
•
Bancos de dados não convencionais
BD O-R e OO
BD de planos
BD espaciais
BD multimídia
Bancos de dados não convencionais
•
•
•
•
•
•
•
•
•
•
•
BD dedutivo
BD probabilista
BD indutivo
BD temporal
BD de restrições
BD semi-estruturado
Páginas web
BD espacial
BD objeto-relacional
BD orientado a objetos
BD multimídia
Bds Multimidia
•
Armazena grande coleção de objetos multimidia
•
•
•
•
Audio
Imagem
Video
hipertexto
Revisão de alguns conceitos de
representação de imagens



Representações matriciais e vetoriais de imagens
Orientação, textura (layout, density)
Wavelet
Consultar Bds Multimidia
•
•
Recuperação baseada em descrição
–
Palavras chaves, titulos, tamanho, tempo de criação
–
Manualmente: trabalhoso
–
Automatizado: resultado de pouca qualidade
Recuperação baseada em conteudo
Histograma de cor
• Não leva em conta fatores espaciais
– Multiplas Caracteristicas
– Wavelet
–
Captura forma, textura
– Problemas
–
–
Wavelet baseada em regiões
Multi-Dimensional Search in Multimedia
Databases Color layout
Multi-Dimensional Analysis in
Multimedia Databases
Histograma de Cor
Layout de textura
Mining Multimedia Databases
Refining or combining searches
Search for “airplane in blue sky”
(top layout grid is blue and
keyword = “airplane”)
Search for “blue sky”
(top layout grid is blue)
Search for “blue sky and
green meadows”
(top layout grid is blue
and bottom is green)
Roteiro
•
•
•
•
•
Bancos de dados não convencionais
BD O-R e OO
BD de planos
BD espaciais
BD multimídia
Minerando Tipos de Dados Complexos:
Generalização de Dados Estruturados
• Set-valued
• Generalização de cada valor do conjunto em seu correspondente
um nível acima de abstração
• Derivação do comportamento geral do conjunto, tal como o
número de elementos, os tipos ou intervalo de valores, ou a
média para dados numéricos
• hobby = {tênis, hóquei, xadrez, violino, atari} pode ser genérico
para {esportes, música, vídeo_games}
• List-valued ou sequence-valued
• Igual a set-valued exceto que a ordem dos elementos deve ser
mantida na generalização
Generalizando Dados Espaciais e
Multimídia
• Dados espaciais:
• Generaliza pontos geográficos detalhados agrupados em
regiões, tal como business, residencial, industrial, ou
agricultural, de acordo com o uso
• Requer a união de um conjunto de áreas geográficas através de
operações espaciais
• Dados de imagem:
• Extraídos por agregação e/ou aproximação
• Tamanho, cor, forma, textura, orientação, e posições relativas
dos objetos contidos ou regiões na imagem
• Dados musicais:
• Resumir esta melodia: baseado nos padrões aproximados que
ocorrem repetidamente
• Resumir este estilo: baseado no tom, tempo, ou nos principais
instrumentos tocados
Generalizando Dados do Objeto
• Identificador do objeto: generaliza para um nível menor na
hierarquia de classes
• Hierarquia da composição das classes
• generaliza estruturas de dados aninhadas
• generaliza apenas objetos mais semelhantes semanticamente ao
atual
• Construção e mineração de cubos de objetos
• Estende o método de indução orientado a atributo
• Aplica uma seqüência de operadores de generalizações baseadas em
classes sobre os atributos
• Continua até conseguir um pequeno número de objetos genéricos que
podem ser resumidos e concisos em termos de alto nível
• Por uma implementação eficiente
• Examina cada atributo, generaliza para um dado simple-valued
• Constrói um cubo de dados multi-dimensional
• Problema: nem sempre é desejável generalizar um conjunto de
valores em um dado single-valued
Roteiro
•
•
•
•
•
Bancos de dados não convencionais
BD O-R e OO
BD de planos
BD espaciais
BD multimídia
Um Exemplo: Planejamento de
mineração
• Planejamento: uma seqüência variável de ações
• Viagem (vôo): <viajante, partida, chegada, hora-p, hora-c,
companhia, preço, assento>
• Planejamento de mineração: extração de padrões genéricos
mais significativos de uma base de planejamentos
• Descobrir padrões de viagens em uma base de vôos, ou
• achar padrões significativos em uma seqüência de ações no
reparo de automóveis
• Método
• Indução orientada a atributo sobre uma seqüência de dados
• Um plano de viagem genérico: <pequeno-grande*-pequeno> (tamanho
do aeroporto)
• Divide & conquer: Minera características para cada
subseqüência
• grande*: mesma companhia aérea, pequeno-grande: região próxima
Uma Base de Viagens para um
Planejamento de Mineração
•
Exemplo: Minerando uma base de planejamento de viagens
Tabela de planos de viagens
plan#
1
1
1
1
2
.
.
.
action#
1
2
3
4
1
.
.
.
departure
ALB
JFK
ORD
LAX
SPI
.
.
.
depart_time
800
1000
1300
1710
900
.
.
.
arrival
JFK
ORD
LAX
SAN
ORD
.
.
.
arrival_time
900
1230
1600
1800
950
.
.
.
airline
TWA
UA
UA
DAL
AA
.
.
.
Tabela de informações de aeroportos
airport_code
1
1
1
1
2
.
.
.
city
1
2
3
4
1
.
.
.
state
ALB
JFK
ORD
LAX
SPI
.
.
.
region
airport_size
800
1000
1300
1710
900
.
.
.
…
…
…
…
…
…
.
.
.
…
…
…
…
…
…
.
.
.
Análise Multi-dimensional
• Estratégia
• Generaliza a base
de planejamento em
diferentes direções
• Procura por padrões
seqüenciais nos
planejamentos
genéricos
• Deriva
planejamentos de
alto nível
Modelo multi-dimensional para uma base de
planejamento
tamanho_aeroporto
categoria
#_passageiros
subir hierarquicamente
cidade
companhia
parceiros
linha_aérea
estado
região
localização
Generalização Multi-dimensional
Generalização multi-dimensional de uma base de planejamento
Plan#
1
2
Loc_Seq
ALB - JFK - ORD - LAX - SAN
SPI - ORD - JFK - SYR
.
.
.
.
.
.
Size_Seq
S-L-L-L-S
S-L-L-S
State_Seq
N-N-I-C-C
I-I-N-N
.
.
.
Unindo ações idênticas e consecutivas nos planos
Plan#
1
2
.
.
.
Size_Seq
S - L+ - S
S - L+ - S
State_Seq
N+ - I - C+
I+ - N+
.
.
.
Region_Seq
E+ - M - P+
M+ - E+
…
…
…
.
.
.
Vôo(x,y) ^ tamanho_aeroporto(x,S) ^ tamanho_aeroporto(y, L)
> região(x) = região(y) [75%]
Mineração em Seqüência Baseada em
Generalização
•
•
•
•
Generaliza uma base de planejamento de forma multi-dimensional
usando tabelas dimensionais
Usa # para valores distintos (cardinalidade) a cada nível para
determinar o nível correto da generalização (planejamento de
níveis)
Usa operadores * para unir (merge) e [] (opcional) para facilitar a
generalização de padrões
Retém padrões com apoio significativo
Padrões de Seqüência Genéricos
• Numa seqüência de tamanho_aeroporto, ficará uma que
engloba todas as outras (aplicando o operador de união)
S - L* - S [35%], L* - S [30%], S - L* [24.5%], L* [9%]
• Depois de aplicar o operador opcional:
[S] - L* - [S] [98.5%]
• Na maioria das vezes, as pessoas viajam de grandes aeroportos
para chegar ao destino
• Outro planos: 1.5% de chances, existem outros padrões:
S - S, L- S - L
Roteiro
•
•
•
•
•
Bancos de dados não convencionais
BD O-R e OO
BD de planos
BD espaciais
BD multimídia
Banco de dados espacial
• Dados relacionados ao espaço
•
•
•
•
Mapas
Sensoriamento remoto
Chips VLSI
Imagens médicas
• Informações topologicas e de distancia
• Mineração:
• relações espaciais
• Padrões
Dimensões e medidas em Data
Warehouses espaciais
• Dimensões
– Não-espacial
• E.x. temperatura: 25-30
– Espacial para não espacial
• E.x. acre(objeto espacial)
generalizado para string
“região norte”
– Espacial para espacial
• e.x. acre (objeto espacial)
para região norte (objeto
espacial)
• Medidas
– numericas
• distributivo (e.x. count, sum)
• algebricas (e.x. média)
• holistica (e.x. mediana)
– espaciais
• Coleção de ponteiros para
objetos espaciais em uma
mapa (e.x. regiões com
temperatura de 25-30 graus
em julho)
Esquema estrela of the BC Weather Warehouse
•3000
•Cada
medidores do clima na Columbia Britanica(BC)
medidor mede Temperatura e Precipitação
– Dimensões
• Nome da região
• tempo
• temperatura
• precipitação
– Medidas
• Região do mapa
• area
• contador
Tabela de dimensão
Tabela de fatos
Roll-up
Por Temperatura
Por Precipitação
Metodos para computação de
cubos espaciais
•
•
•
•
Não armazenar medidas
Pré-computar todas as possiveis medidas
Pré-computar estimativas
Pré-computar apenas as mais acessadas
Regras de associação
•
Regra de associação: A  B [s%, c%]
–
–
–
–
A e B são conjuntos de predicados
•
Relações topologicas
•
Orientação espacial
•
Informação de distancia
s% suporte e c% confidencia
e_um(x,cidade) e intercepta(x,estrada) -> adjacente(x,agua)
[7%, 85%]
e_um(X,”escola”) e perto_de(X,”centro esportivo” ) ->
perto_de(X,”parque”) [0.5%,80%]
Regras de associação
•
Refinamento Progressivo
– Deve preservar todas as respostas possiveis
•
Minerar relação perto_de
– Aplicar algoritmo impreciso
– Intersecção entre retangulos
Classificação e Analise de tendencias
• Classificação
• Exemplo: regiões ricas x regiões pobres
• Determinar regiões
• Tendencias
• Espaciais
• Temporais
Roteiro
•
•
•
•
•
Bancos de dados não convencionais
BD O-R e OO
BD de planos
BD espaciais
BD multimídia
Análise Multidimensional e OLAP
• MultiMediaMiner
• Descritor de caracteristicas
• Conjunto de vetores para caracteristicas visuais
• Histograma de cores quantizado
• Cor mais frequente
• Descritor de layout
• Imagens transformadas em grade 8X8
• Armazena informações para celulas da grade
Minerando banco de dados multimidia
Minerando banco de dados multimidia
The Data Cube and
the Sub-Space Measurements
By Size
By Format
By Format & Size
RED
WHITE
BLUE
Cross Tab
JPEG GIF
By Colour
RED
WHITE
BLUE
Group By
Colour
RED
WHITE
BLUE
Measurement
Sum
By Colour & Size
Sum
By Format
Sum
By Format & Colour
By Colour
• Format of image
• Duration
• Colors
• Textures
• Keywords
• Size
• Width
• Height
• Internet domain of image
• Internet domain of parent pages
• Image popularity
Regras de associação
• Entre imagem – não imagem
• 50% de azul no topo da figura -> representa céu
• Entre imagens sem relação espacial
• figura contem dois quadrados azuis -> circulo vermelho
• Entre imagens relacionadas espacialmente
• Triangulo vermelho entre dois quadrados amarelos -> grande
circulo abaixo
• Uso de resolução progressiva
• Garantir completude
• Recorrencia
• Relações espaciais
Minerando banco e dados multimidia
Relações espaciais
property P1 on-top-of property P2
property P1 next-to property P2
Different Resolution Hierarchy
Predição e Classificação
•Pré-computação para descobrir atributos
•Exemplo de interface: