Introdução a Descoberta de Conhecimento em Bancos de Dados Espaciais

Adaptado de material elaborado pelo Prof. Shashi Shekhar, University of Minnesotawww.cs.umn.edu/~shekhar

Exemplo Histórico

Cólera Asiática em Londres (1855): um poço identificado como a fonte do problema

Exemplos Modernos

Clusters de pessoas com cancer para investigar a influência do ambiente Locais de concentração de crimes para planejar as rotas de patrulha da políciaIdentificação de características onde certo tipo de águias fazem os ninhosPropagação do virus do Nilo do nordeste para o sul e o oeste dos EUA

Exemplos Modernos

Global Influence of El Nino duringthe Northern Hemisphere Winter(D: Dry, W: Warm, R: Rainfall)

Average Monthly Temperature(Courtsey: NASA, Prof. V. Kumar)

Aquecimento anormal de região do oceano Pacífico (El Niño) afeta o clima

O que é um padrão espacial?

• O que não é um padrão?• Aleatório, ao acaso, acidental

• O que é um padrão (pattern)?• Um arranjo frequente, configuração, regularidade• Uma regra, lei, método• Uma direção ou tendência importante• Uma irregularidade espacial importante

O que é descoberta de conhecimento em dados espaciais?

MetáforaMinerando pepitas de informação “escondidas” em grandes bancos de dados

• pepitas= padrões espaciais não conhecidos, interessantes e úteis• minerando= procurando por pepitas

Definindo Data Mining Espacial Procura por padrões espaciaisProcura não-trivial tão automática quanto possível (reduzindo o esforço humano) Padrões espaciais interessantes, úteis e inesperados (desconhecidos)

O que é data mining espacial?- 2

Busca não trivial por padrões espaciais interessantes e desconhecidosBusca não trivial

Grande (ex. exponencial) espaço de busca de hipóteses plausíveis Ex. Cólera Asiática - causas plausíveis: água, alimento, ar, insetos, …;

InteressanteÚtil em algum domínio de aplicaçãoEx. Desativando o poço identificado => salvar vidas humanas

InesperadoO padrão não é conhecimento comum Pode levar a um novo entendimento do mundo Ex. A conexão Poço - Colera levou a teoria do “germe”

O que NÃO é data mining espacial?

Consultas simples a dados espaciais Encontre os vizinhos de Porto Alegre dados os nomes e limites de todas as cidadesEncontre o menor caminho do RS a SP na malha de rodoviasO espaço de busca não é grande (não é exponencial)

Testar uma hipótese através de uma análise simples de dadosEx. O território das chimpanzes femeas é menor do que o dos machos O espaço de busca não é grande !

Padrões espaciais não interessantes ou óbvios Muita chuva em Porto Alegre está correlacionada com muita chuva em Canoas, dado que as duas cidades são vizinhas. Conhecimento comum: lugares próximos tem precipitações similares

Mineração de dados não espaciaisAs vendas de fraldas e cervejas são correlacionadas nas sextas-feiras

Porque estudar mineração de dados espaciais? Novo conhecimento dos processos geográficos para questões críticas

Ex. Como está a saúde do planeta Terra? Ex. Caracterizar os efeitos da atividade humana para o ambiente e a ecologiaEx. Predizer o efeito do El Niño no clima e na economia

Abordagem tradicional: gerar e testar hipóteses manualmente Mas os dados espaciais estão crescendo rápido demais para uma análise manual

• Imagens de satélite, trajetórias geradas por GPS, sensores em rodovias, …

Número de hipóteses geográficas possíveis é grande demais para uma análise manual

• Grande número de objetos geográficos • O número de relacionamentos entre os objetos cresce exponencialmente• Ex. Encontre correlação entre eventos climáticos oceânicos e em terra firme

Data Mining Espacial pode reduzir o conjunto de hipóteses plausíveis

Data Mining Espacial: os atores

Especialista do domínioIdentifica os objetivos da descoberta e fornece os bancos de dados espaciais Descreve o conhecimento do domínio, p.ex. padrões bem conhecidos Validação de novos padrões

Analista de DCBD EspaciaisAjuda a identificar famílias de padrões e técnicas de data mining a serem usadasExplica a saída dos algoritmos para o especialista do domínio

Esforço conjuntoSeleção de atributos Seleção de padrões para análise aprofundada (mais detalhada)

Escolha de métodos

Duas abordagens:Uso de técnicas específicas para mineração de dados espaciais Obtenção dos dados ou relacionamentos espaciais de interesse para uso com métodos de DM clássicos

Abordagem possível:Defina o problema: obtenha as necessidades particularesAnalise os dados usando mapas e outras técnicas de visualizaçãoTente usar métodos clássicos de data mining Se não obtiver resultados satisfatórios, tente novos métodosAvalie os métodos escolhidos rigorosamente

Famílias de padrões espaciais

• Familias usuais de padrões espaciais• Predição de localização (location prediction): onde um certo fenômeno ocorrerá?• Interação espacial (spatial interaction): quais subconjuntos de objetos ou fenômenos espaciais interagem? • Hot spots: quais localizações são não usuais?

•Nota: • Outras famílias de padrões espaciais podem ser definidas • Data mining espacial é um campo em desenvolvimento, que pode acomodar novas famílias de padrões

Predição de localização

• Questões a serem respondidas:• Onde um fenômeno vai ocorrer?• Que eventos espaciais são previsíveis?• Como um evento espacial pode ser predito a partir de outros eventos espaciais?

• Equações, regras, outros métodos

• Exemplos:• Onde um pássaro em extinção faz seus ninhos?• Que áreas estão mais sujeitas a incêndio florestal considerando dados de vegetação, vento, etc.?• O que poderia ser recomendado para um viajante que está em um certo local?

Hot spots

• Questões a serem respondidas:• É um fenômeno espacialmente agrupado?• Que entidade espaciais ou agrupamentos são

não usuais?• Que entidades espaciais compartilham

características comuns?

•Exemplos:• Regiões com alta incidência de cancer podem

ser usadas para iniciar investigação• Locais com alta incidência de crimes podem ser

usados para planejar rotas de patrulha para a polícia

Propriedades únicas dos padrões espaciais

Os items em dados tradicionais são independentes uns dos outros,

Enquanto propriedades de localização em um mapa são frequentemente “auto-correlacionados” (ex: ilha e recurso hídrico).

Dados tradicionais trabalham com domínios simples, p.ex. números e símbolos,

Enquanto os tipos de dados espaciais são complexos (ex: linha, polígono)

Itens em dados tradicionais descrevem objetos discretos, Enquanto dados espaciais são contínuos

Primeira lei da geografia [Tobler]:Tudo está relacionado com tudo, mas coisas próximas estão mais relacionadas que coisas distantes.

• Pessoas com background similar tendem a viver na mesma área• Economias de regiões próximas tendem a serem similares• Mudanças na temperatura ocorrem gradualmente no espaço (e tempo)

Mapeando técnicas para as famílias de padrões espaciais

• Visão geral• Existem várias técnicas para encontrar padrões espaciais de uma mesma família• A escolha da técnica depende da seleção dos atributos, dos dados espaciais, etc.

• Famílias de padrões espaciais x técnicas • Predição de localização: Classificação• Interação espacial: Correlação, Associação, Co-locations• Hot spots: Clustering, detecção de desvios

•

Given:1. Spatial dataset (nest,

vegetation, water, trees, etc..)

2. Characteristics (nests close to tree, close to water, etc)

3. A dependent class (nest)

Find: Classification model

Objective:maximizeclassification_accuracy

Constraints: Spatial Autocorrelation

exists

Nest locations Distance to open water

Vegetation durability Water depth

Location Prediction as a classification problem

Answers: and

find patterns from the following sample dataset

Co-location

Tid Itemset 1 A, C, D,T, W 2 C, D, W 3 A, D, T, W 4 A, C, D, W 5 A, C, D, T, W 6 C, D, T

Association Rules (Agrawal 1993)

Association rule is an implication of form X Y

Suport = #(XY) / #D, where #D is the number of rows in the datasetConfidence : suport(XY) / suport(X)

k Frequent itemsets with minsup 50%

k=3{A,C,D}, {A,C,W}, {A,D,T}, {A,D,W}, {A,T,W}, {C,D,T}, {C,D,W}, {D,T,W}

k=4 {A,C,D,W}, {A,D,T,W}

Extract association rules2

Generate frequent itemsets1

k=1 {A}, {C}, {D}, {T}, {W}

{C,T}, {C,W}, {D,T}, {D,W}, {T,W} k=2{A,C}, {A,D}, {A,T}, {A,W}, {C,D},

Confidence AC = 3/4 (75%)

Suport {AC} = 3/6 (50%)

Co-Location Patterns (Huang 2004, Yoo 2005)

Input: Spatial datasetDistance thresholdMinimum participation index

MethodFind neigboursFind co-location candidatesFind frequent co-location setsExtract co-location rules

Co-location Mining

B1

C2

A1C1

A4

A2A3

B2

B4B3

C3

B5

A, B, C: Spatial Feature Types

Edges: neighbor

B1 Spatial Dataset

A1, A2... Spatial Feature Instances

Co-location Mining

Set of Spatial Feature Types {A, B, C}

Candidates of size k=1A B C

1 1 12 2 23 3 34 4 5

Candidates of size k=2

A B A C B C

1 1 1 2 2 12 4 3 1 4 13 4 5 3

Co-location

instances

B1

C2

A1C1

A4

A2A3

B2

B4B3

C3

B5

B1 Spatial Dataset

Co-location Mining

Candidates of size k=2

A B A C B C

1 1 1 2 2 12 4 3 1 4 13 4 5 3

Co-location

instances

Candidates of size k=1A B C

1 1 12 2 23 3 34 4 5

3/4 2/5

2/4 2/3 3/5 2/3

Participation ratio

B1

C2

A1C1

A4

A2A3

B2

B4B3

C3

B5

B1 Spatial Dataset

Co-location Mining

Candidates of size k=2

A B A C B C

1 1 1 2 2 12 4 3 1 4 13 4 5 3

Co-location

instances

2/5 2/4

3/5 Participation IndexLowest index

B1

C2

A1C1

A4

A2A3

B2

B4B3

C3

B5

B1 Spatial Dataset

Co-location Mining

Candidates of size k=3

A B C

3 4 1

Co-location

instances

B1

C2

A1C1

A4

A2A3

B2

B4B3

C3

B5

B1 Spatial Dataset

1/4 1/5 1/3 Participation index

Cropland with RoadsRoads with Bridges

CroplandRoadsBridges

Co-location Example

Outliers?

Outliers

What is an outlier?Observations inconsistent with the rest of the dataset

Techniques for global outliers• tests based on membership in a distribution

– [item in population] is low• tests based on distance, nearest neighbors, etc.

What is a spacial outlier?Observations inconsistent with their neighborhoodsA local instability or discontinuity

Outliers

Global outliers have been defined as observations of data in databases which appear to be inconsistent with the remainder of the data in the database (Shekhar apud Barnett 1994).

The identification of global outlier can lead to the discovery of unexpected knowledge, and has a number of practical applications in areas such as credit card fraud, athlete performance analysis, voting irregularity, and severe weather prediction (SHEKHAR, 2001).

A spatial outlier is a spatially referenced object whose non-spatial attribute values are significantly different from those of other spatially referenced objects in its spatial neighborhood.

For example, a new house in an old neighborhood of a growing metropolitan area is a spatial outlier based on the non-spatial attribute house age (SHEKHAR, 2003).

Tests to detect spatial outliers separate the spatial attributes from the non-spatial attributes.

Spatial attributes are used to characterize location, neighborhood, and distance. Non-spatial attributes are used to compare a spatial referenced object to its neighbors.

Spatial Outlier Detection: Example

Outliers - Examples

Map ProductionError identificationE.g., spatial object violation

RiverRoadBridge

Road leading into waterOr missing bridge

Bridge locationerror

Summary

Patterns are opposite of randomCommon spatial patterns: location prediction, outliers, hot spots, SDM = search for unexpected interesting patterns in large spatial databasesSpatial patterns may be discovered using

Techniques like classification, associations, clustering and outlier detectionNew techniques are needed for SDM due to

• Spatial Auto-correlation• Continuity of space

References

Shekhar, S.; Huang, Y.Discovering Spatial Co-location Patterns: A Summary of Results , Proc. of 7th International Symposium on Spatial and Temporal Databases(SSTD01), L.A., CA, July 2001

HUANG, Y.; SHEKHAR, S.; XIONG, H. Discovering Co-location Patterns from Spatial Datasets: A General Approach. IEEE Transactions on Knowledge and Data Engineering, v.16, n.12, Dec. 2004.

SHEKHAR, S.; LU, C.-T.; ZHANG, P. Detecting graph-based spatial outliers: algorithms and applications (a summary of results). In: ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, KDD, 7., 2001, San Francisco. Proceedings… ACM, 2001. p.371-376.

SHEKHAR, S., CHAWLA, S. Spatial databases: a tour. Upper Saddle River, NJ: Prentice Hall, 2003.

YOO, J.S.; SHEKHAR, S; CELIK, M. A Join-less Approach for Co-location Pattern Mining: A Summary of Results. In: IEEE INTERNATIONAL CONFERENCE ON DATA MINING, ICDM, 5., 2005, Houston. Proceedings… IEEE Computer Society, 2005. p.813-816.

AGRAWAL, R.; IMIELINSKI, T.; SWAMI, A. Mining association rules between sets of items in large databases. In: ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, SIGMOD, 1993, Washington, D.C. Proceedings… New York: ACM Press, 1993. p. 207-216.

X. Zhang, N. Mamoulis, D. W. L. Cheung, and Y. Shou, "Fast Mining of Spatial Collocations," Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 384-393, Seattle, WA, August 2004.