Embed Size (px)
Citation preview
- 1 -
Programa de Ciência e Tecnologia para Gestão de Ecosistemas
Ação "Métodos, modelos e geoinformação para a gestão ambiental”
“Mineração de Dados em Grandes Bancos de DadosGeográficos”
Marcos Corrêa Neves
Corina Costa Freitas
Gilberto Câmara
Relatório Técnico
Novembro, 2001
- 2 -
SUMÁRIO
TEMA.......................................................................ERRO! INDICADOR NÃO DEFINIDO.ERRO! INDICADOR NÃO DEFINIDO.
1 – INTRODUÇÃO .................................................................................................................3
2 – OBJETIVOS.......................................................................................................................5
3 – REVISÃO BIBLIOGRÁFICA..............................................................................................6
3.1 – Data Mining.................................................................................................................6
3.2 – Clustering .....................................................................................................................7
3.2.1 – Métodos hierárquicos .............................................................................................8
3.2.2 – Métodos de particionamento.................................................................................11
3.3 – Métodos para Spatial Data Mining.............................................................................17
3.3.1 - CLARA.................................................................................................................17
3.3.2 - CLARANS............................................................................................................18
3.4 – Clustering com Restrição de contiguidade ...................................................................20
4 - METODOLOGIA.............................................................................................................27
5 - RESULTADOS ESPERADOS ...........................................................................................31
6 - CRONOGRAMA..............................................................................................................32
REFERÊNCIAS BIBLIOGRÁFICAS.......................................................................................33
- 3 -
1 – INTRODUÇÃO
A disseminação do uso de meios eletrônicos na sociedade moderna tem gerado um
grande volume de dados. Sistemas gerenciadores de banco de dados estão presentes namaioria das organizações públicas e empresas de médio e grande porte, contendo osmais diferentes dados sobre produtos, fornecedores, clientes, empregados, etc. Além
disso, avanços em aquisição de dados, desde um simples leitor de código de barras atésistemas de sensoriamento remoto, geram mais e mais dados. A cada dia, mais operaçõescorriqueiras são automatizadas, e a cada nova transação, como compras com cartão de
crédito, operações bancárias, terminais de venda, novos registros correspondentes sãoarmazenados.
Todo este considerável conjunto de dados contém uma preciosa quantidade de
informação. Entretanto, muitos dos bancos de dados atuais, contém um volume tal deregistros, que inviabiliza a possibilidade de análise humana. Esta dificuldade criou anecessidade do desenvolvimento de ferramentas para auxiliar a análise, possibilitando a
transformação de grandes volumes de dados em informação útil (Goebel e Gruenwald,1999).
Este contexto, motivou a criação de um novo campo de pesquisa que busca
desenvolver meios de prospecção de conhecimento em grandes bases de dados, tambémchamado de Knowledge Discovery in Database (KDD). Fayyad et al. (1996) definiu KDDcomo sendo um processo não trivial de identificação de padrões válidos, novos, úteis e
implicitamente presentes em grandes volumes de dados. Inicialmente as ferramentas deprospecção de conhecimento foram empregadas em ambientes de pesquisa eexperimentação; atualmente já estão disponíveis no mercado vários produtos, sobretudo
voltados para aplicações comerciais (Goebel e Gruenwald, 1999) (Ester, Kriegel et al.,1999).
O núcleo central do processo de prospecção de conhecimento é composto pelos
métodos de mineração de dados (Data Mining). ). Mineração de dados consiste da busca,automática ou semi-automática, em grandes quantidades de dados com o objetivo dedescobrir padrões importantes, utilizando algoritmos com eficiência computacional
aceitável (Ng and Han, 1994; Ester et al., 1999).
Enquanto KDD é um processo interativo e iterativo, envolvendo muitos passos,Data Mining, em particular, é o passo onde são aplicados algoritmos voltados para
atingir objetivos específicos, produzindo uma enumeração particular de padrões nosdados (Goebel e Gruenwald, 1999). Portanto, em um processo completo de descobertade conhecimento, podem ser utilizados diversos algoritmos de Data Mining.
Spatial Data Mining, ou mineração de dados espaciais, é uma extensão de DataMining voltada para domínios de aplicação onde a consideração da dimensão espacial éessencial na extração de conhecimento. De forma similar, existem desenvolvimentos de
- 4 -
trabalhos considerando o contexto temporal (Temporal Data Mining) e ainda,considerando ambas as dimensões (Spatio-Temporal Data Mining). Roddick et al.(2001)apresenta uma seleção de trabalhos nestas áreas.
A principal diferença entre Data Mining e Spatial Data Mining é a consideração dosrelacionamentos espaciais existentes entre as entidades do mundo real. Ester et al. (1999)apresenta três tipos básicos de relações espaciais, as quais denomina: relações
topológicas, de distâncias e de direção. Algumas relações topológicas entre dois objetosespaciais, A e B, são: A sobrepõe B, A contém B, A está contido em B, A é disjunto de B,A igual a B e A é adjacente a B (A vizinho a B).
As relações de vizinhança são importantes em estudos onde os objetos espaciais emanálise são do tipo área. Neste tipo de dado espacial, cada objeto é representadoespacialmente por polígonos. Neste caso, as relações de vizinhança fornecem a estrutura
espacial e são utilizadas como critério de proximidade, já que a distância euclidiana, nãopode ser diretamente empregada, como no caso de objetos espaciais representados porpontos.
A importância da consideração dos relacionamentos de vizinhança, está no fato quepara processos espaciais, a medida associada a um local, ou objeto, tende a ser similar àsmedidas em locais próximos. Este fato é conhecido como a 1ª lei da geografia,
especificada por Topler (Zeitoune et al. 2001). Nos algoritmos aplicados em Spatial dataMining, para que possamos avaliar a dependência espacial, teremos que utilizar ainformação sobre os relacionamentos de vizinhança dos objetos (Ester et al. 1999).
Métodos estatísticos tradicionais presumem a independência amostral. Aoaplicarmos, por exemplo, o método estatístico de regressão linear em dados espaciais, osresultados obtidos serão falseados para o teste de ajuste do modelo, bem como, para os
intervalos de confiança dos coeficientes do modelo e das predições (Bailey e Gatrell,1995) (Anselin e Bao, 1997) (Neter et al., 1989).
Buttenfield et al. (2001) afirma que as aplicações correntes em prospecção de
conhecimento aplicados a dados geográficos (GKD), geralmente utilizam representaçõessimples para objetos geográficos e para os relacionamentos espaciais. Os métodos deSpatial Data Mining deveriam reconhecer tipos mais complexos de dados (linhas e
polígonos), uma vez que nem sempre os objetos espaciais podem ser reduzidos a umponto, e os métodos deveriam considerar os relacionamentos espaciais entre os objetos(distância não-euclidiana, direção, conectividade). Koperski et al.(1997) diz que o
crucial desafio para Spatial Data Mining é a eficiência dos algoritmos empregadosdevido ao volume de dados espaciais, complexidade dos tipos de dados e aos métodos deacesso aos dados espaciais.
Neste contexto, nosso trabalho tem a intenção de contribuir com odesenvolvimento de métodos para Spatial Data Mining que considere objetos espaciaisdo tipo área; os relacionamentos entre os objetos (especificamente, relações de
vizinhança); e a dependência espacial existente entre eles.
- 5 -
2 – OBJETIVOS
Objetivo geral do trabalho é:
Desenvolver métodos de Spatial Data Mining que sejam aplicáveis a objetos
espaciais com representação poligonal, considerando as relações de vizinhanças entres osobjetos e a dependência espacial entre os atributos.
Objetivos específicos:
Adaptar, implementar e avaliar um conjunto de algoritmos de Spatial Data Miningcombinando diferentes abordagens e métodos de clustering espacial aplicáveis a objetos
do tipo área.
- Analisar a influência da dependência espacial no comportamento dos procedimentosde Spatial Data Mining. verificando a viabilidade de utilizar medidas de
autocorrelação espacial como elemento direcional no processo de clustering, naescolha e eliminação de atributos e na avaliação dos procedimentos.
- Desenvolver um algoritmo de Spatial Data Mining que considere a informação de
dependência espacial.
- Aplicar os métodos de Spatial Data Mining a um caso prático, envolvendo grandesvolumes de dados espaciais.
- 6 -
3 – REVISÃO BIBLIOGRÁFICA
Esta seção está dividida em 4 partes. Na primeira, situamos Data Mining dentro doprocesso de prospecção de conhecimento e apresentamos o papel dos métodos de
clustering nos procedimentos de mineração. Na segunda parte, enfocamos clustering,apresentando alguns conceitos e métodos básicos. Na terceira, são mostrados osmétodos de clustering propostos para Spatial Data Mining. E por fim, na última parte,
são apresentados as diferentes abordagens para clustering com restrição espacial e ummétodo específico baseado no algoritmo da árvore geradora mínima.
3.1 – Data Mining
Para melhor situarmos Data Mining em relação a KDD, é apresentado a seguir, aseqüência completa de passos existentes em um processo de prospecção deconhecimento, conforme Goebel e Gruenwald (1999):
i) entendimento do domínio da aplicação;
ii) definição das metas do processo;
iii) seleção do conjunto de dados alvo;
iv) integração e checagem dados;
v) limpeza, pré-processamento e transformação dos dados;
vi) escolha dos algoritmos apropriados de Data Mining;
vii) interpretação e visualização dos resultados;
viii) teste dos resultados; e
ix) uso e manutenção do conhecimento descoberto.
As ferramentas correntemente disponíveis para a execução das tarefas de Data
Mining são genéricas e derivadas de outras áreas do conhecimento, em especial, da
Estatística e Inteligência Artificial. As técnicas utilizadas, podem ser classificadas como:
métodos estatísticos, redes neurais, regras de indução, árvores de decisão, séries
temporais, análise exploratória de dados, algoritmos genéticos, conjuntos nebulosos,
Rough sets. Portando, Data Mining compreende uma coleção de técnicas, capazes de
auxiliar a obtenção de informação adicional. Diferentes métodos de mineração atendem
- 7 -
a diferentes propósitos, cada qual, oferecendo vantagens e desvantagens (Goebel e
Gruenwald, 1999).
Uma das técnicas estatísticas utilizadas em Data Mining é Clustering (Análise de Cluster,ou agrupamentos). Clustering é um ramo da Estatística Multivariada que englobamétodos utilizados para descobrir estruturas em um conjunto complexo de dados. O
objetivo principal de clustering é separar objetos ou observações em classes naturais deforma que os elementos pertencentes a um mesmo grupo tenham um alto grau desemelhança ou similaridade, enquanto que, quaisquer elementos pertencentes a grupos
distintos, tenham pouca semelhança entre si (Andeberg, 1973).
O atrativo dos métodos de clustering para tarefas de mineração de dados é a suahabilidade de extrair estruturas diretamente dos dados, sem nenhum conhecimento
prévio. Métodos de clustering para Data Mining, são utilizados com modificações emrelação aos algoritmos tradicionais, sobretudo visando aumentar sua eficiência, dianteda quantidade de objetos a serem classificados no contexto de Data Mining (Ng e Han,
1994) (Koperski, et al., 1997) (Zhang et al., 2001).
Métodos de clustering também têm sido utilizados em análise exploratória de dadosespaciais (ESDA) e em procedimentos de regionalização. Nestes, os algoritmos de
clustering com restrição de contigüidade espacial são utilizados com o objetivo deagrupar áreas homogêneas em regiões contíguas (Openshaw e Wymer, 1995) (Assunção,2000). Wise et al.(1997) apresenta algumas razões para se agrupar unidades espaciais
básicas, como setores censitários, formando regiões maiores: aumento darepresentatividade nos valores dos atributos e taxas associadas; redução dos efeitos daimprecisão nos valores das variáveis; redução dos erros associados ao posicionamento
geográfico de eventos; e redução no custo de análise dos dados.
3.2 – ClusteringA tarefa básica de clustering é classificar um conjunto de objetos em subconjuntos
segundo um ou mais critérios apropriados. Os critérios mais comuns adotados emclustering são: homogeneidade e separação. A homogeneidade refere-se a objetospertencentes a um mesmo cluster, que devem ser tão similares quanto possível;
Enquanto que a separação, está relacionada a objetos de diferentes clusters, que devemser distintos entre si, tanto quanto possível (Maravalle et al., 1997).
A qualidade do resultado obtido pela utilização de técnicas de Clustering depende de
uma série de definições coerentes por parte do usuário. Alguns elementos importantes
presentes no desenvolvimento dos procedimentos de Clustering são: escolha dos
atributos; homogeneização das variáveis; medidas de dissimilaridade; critérios de
agrupamento; escolha do algoritmo; e definição do número de clusters.
- 8 -
Métodos de clustering normalmente utilizam uma medida de dissimilaridade paraavaliar o grau de semelhança entre dois objetos durante o processo de agrupamento.Muitas vezes, esta medida é apresentada como sendo a distância entre dois objetos. A
combinação entre a escolha das variáveis, transformações das variáveis(homogeneização) e as medidas de dissimilaridade escolhidas, é que traduzoperacionalmente o termo “associação natural” entre objetos (Andeberg, 1973).
Métricas comumente utilizadas são: a Distância Euclidiana, dada pela seguinte forma:
2/1
1
2)(
−= ∑=
p
kjkikij xxd ,
e a distância quarteirão (city block), dada por:
∑=
−=p
kjkikij xxd
1
,
onde: ijd é a dissimilaridade entre os objetos i e j;
ikx é o valor é o valor do atributo k para o objeto i, e
jkx é o valor é o valor do atributo k para o objeto j.
Os algoritmos de clustering podem ser classificados em duas categorias principais:métodos hierárquicos e métodos de particionamento ou relocação iterativa. A seguir,apresentaremos os principais métodos dentro destas categorias.
3.2.1 – Métodos hierárquicos
Métodos hierárquicos podem ser aglomerativos ou divisivos. Nos métodos hierárquicos
aglomerativos, inicialmente, cada objeto é um cluster e, a cada passo do procedimento,os dois clusters mais próximos (similares) são fundidos, até que, ao final, exista somenteum grande cluster, contendo todos os objetos. Este algoritmo é chamado de hierárquico
pois ele permite obter vários níveis de agrupamento. Uma informação gráfica, contendoo histórico das fusões é facilmente gerada neste método. Este dispositivo gráfico recebe onome de dendrograma (Andeberg, 1973; Gordon, 1981; Richards, 1995). A Figura 1,
mostra vários estágios para um processamento fictício. Nesta figura é possívelacompanhar o desenvolvimento do algoritmo para um caso simples, onde existemapenas duas variáveis (espaço bidimensional).
De forma análoga, métodos hierárquicos divisivos, inicia-se com todos os
objetos pertencendo a um único agrupamento, o qual vai sendo sucessivamente
dividido, até que no final, cada cluster contenha um único elemento. Esta variação é
- 9 -
mais dispendiosa computacionalmente e raramente utilizada. Em Sensoriamento
Remoto, ela é praticamente descartada pelo grande número de objetos, pixels, existentes
nas imagens de satélite (Richards, 1995).
Os passos do algoritmo hierárquico aglomerativo são:
Passo 1Passo 1: Iniciar com n clusters, cada um contendo um objeto.
Passo 2Passo 2: Calcular as dissimilaridades entre os objetos.
Passo3Passo3 : Procurar o par de clusters com menor dissimilaridade;
Passo 4Passo 4: Recalcular a dissimilaridade do cluster fundido com os demais clusters.
Passo 5Passo 5: Repete os passos 3 e 4, 1−n vezes.
- 10 -
Figura 1: Algoritmo hierárquico aglomerativo. (adaptado de Richads
- 11 -
O cálculo da dissimilaridade entre clusters no algoritmo hierárquico apresentadoacima e ilustrado na Figura 1, utiliza um ponto central para representar o cluster,definido pelos valores médios dos atributos dos objetos membros de cada cluster. No
método hierárquico chamado de Ligação Única, a dissimilaridade entre dois clusters éigual a menor dissimilaridade existente entre dois objetos quaisquer, um objetopertencente a cada um dos clusters envolvidos. Este método, elimina o cálculo das
médias dos atributos a cada passo do algoritmo, mas apresenta o inconveniente deproduzir clusters de forma alongada, efeito denominado de encadeiamento (Andeberg,1973). Outra variação do método hierárquico aglomerativo, utiliza o valor da maior
dissimilaridade entre dois objetos de clusters distintos como medida de dissimilaridadeentre estes clusters (Ligação Completa) (Andeberg, 1973; Gordon, 1981).
Embora os métodos hierárquicos sejam empregados com sucesso em aplicações
biológicas, como taxinomia de animais e plantas, existe uma deficiência inerente a estemétodo. Nele não existe uma revisão dos clusters durante a execução do procedimento,ou seja, no método hierárquico aglomerativo, uma vez realizado a fusão de dois objetos
dentro de um mesmo cluster, os objetos nunca mais são separados, permanecendo até ofinal do procedimento, sempre juntos em um mesmo cluster. De forma análoga, nohierárquico divisivo, uma vez separados dois objetos, eles nunca mais serão agrupados
em um mesmo cluster (Ng e Han, 1994).
3.2.2 – Métodos de particionamento3.2.2 – Métodos de particionamento
Os métodos de particionamento buscam encontrar, iterativamente, a melhor partição
dos n objetos em k grupos. Freqüentemente os k clusters encontrados pelos métodos departicionamento são de melhor qualidade (grupos internamente mais homogêneos) doque os k clusters produzidos pelos métodos hierárquicos. Devido a este melhor
desempenho, os algoritmos de particionamento têm sido mais investigados e utilizados(Ng e Han, 1994). Os métodos de particionamento mais utilizados são baseados em umponto central (média dos atributos dos objetos - k-médias) (Zhang et al., 2001) ou em
um objeto representativo para o cluster (k-medoids) (Kaufman e Rousseeuw, 1990).
Método de particionamento K-médias
K-médias é um método bastante difundido, existindo muitas variações propostas na
literatura, recebendo diversos nomes como, isodata ou migração de médias. Ele é muitoutilizado em Sensoriamento Remoto, com a finalidade de executar procedimentos declassificação não supervisionada de imagens de satélite (Schowengerdt, 1997). Este
método exige a definição prévia do número de clusters e do posicionamento inicial doscentros dos k clusters no espaço de atributos. As variações e melhorias propostas para ométodo ficam por conta da definição inicial dos centros dos clusters e de avaliações
realizadas no final ou durante o processo de agrupamento (Richards 1995; Zhang et al.2001).
Os passos básicos de um algoritmo baseado em k-médias, são:
- 12 -
Passo 1Passo 1: Escolha de k objetos para serem centros iniciais dos k clusters.
Passo 2Passo 2: Cada objeto é associado a um cluster, para o qual a dissimilaridade entre objeto
e o centro deste cluster é a menor que as demais.
Passo 3Passo 3: Os centros dos clusters são recalculados, redefinindo cada um, em função dos
atributos de todos os objetos pertencentes ao cluster;
Passo 4Passo 4: Volta ao passo 2, até que os centros dos clusters se estabilizem.
A cada iteração, os objetos são agrupados em função do centro do cluster mais próximoe, por conseqüência, os centros dos clusters são reavaliados (passo 3). Isto provoca noespaço de atributo um deslocamento dos centros médios. O algoritmo é interrompido
quando as médias não mais são deslocadas, ou há uma insignificante relocação deobjetos entre os clusters. A Figura 2, ilustra o desenvolvimento do método, para omesmo caso simples apresentado anteriormente.
- 13 -
Figura 2: Algoritmo k médias.
- 14 -
Método de particionamento K-medoids
Outro grupo de métodos de particionamento, são baseados k-medoids. A diferençabásica em relação ao k-médias está na utilização de um objeto representativo, chamado
de medoid, localizado mais ao centro possível do cluster, ao invés de um centro médio. Ométodo de clustering PAM (Particioning Around Medoids), baseado em k-medoid, foiproposto Kaufman and Rousseeuw (1990). Ele realiza em cada passo uma busca
exaustiva pela troca de um dos k medoids previamente selecionados por um dos demais(n-k) objetos, que minimize as dissimilaridades entre os k medoids e os membros dos kclusters.
Para apresentarmos o algoritmo PAN, passaremos a considerar o problema declassificação como a busca por uma partição ótima do conjunto de dados. Do ponto devista da otimização, temos que:
{ }nV ,,3,2,1 K= ,
{ }kCCC ,,, 21 K=π ,
)(πf ,
onde: V é o conjunto de n objetos a serem particionados em classes, iC é o cluster i, π éuma dada partição em k clusters e )(πf é uma função objetivo que fornece uma medidade qualidade da partição. A qualidade da partição está geralmente ligada aos critérios de
homogeneidade interna (referente aos elementos de um mesmo cluster), e separação(referente aos elementos de clusters distintos). Dentro do contexto de otimização, oobjetivo final é conseguir uma partição que maximize (ou minimize, dependendo do
caso) a função objetivo.
Um exemplo simples para uma função objetivo é dado por:
∑=
=k
i
Dif1
)(π .
onde, Di é a soma das distâncias euclidianas entre cada membro de um cluster i e omedoid correspondente.
Se os cluster são homogêneos e compactos, o que é desejável, os valores de Di para cadacluster tendem a ser pequenos. A função objetivo, neste caso, deve ser minimizada, paraproduzirmos um bom resultado dentro de um processo de otimização. A seguir, são
apresentados os passos do algoritmo utilizado no PAN, onde a função objetivo utilizada,é a mesma apresentada anteriormente:
Passos do algoritmo PAN:
Passo 1Passo 1: Selecionar arbitrariamente k medoids entre os n objetos.
- 15 -
PassoPasso 2: Agrupar os objetos em função do medoid mais similar, definindo a partição
corrente, correnteπ , e calcular ( )correntef π .
PassoPasso 3: Verificar todas as trocas possíveis entre um medoid e um objeto não
selecionado, escolhendo um novo conjunto de k medoids, que produza uma partição, π ,
tal que o valor para a ( )πf é o menor dentre todas as possibilidades.
PassoPasso 4: Se o ( ) ( )correnteff ππ < , efetivar a troca, ππ =corrente ; e voltar ao passo 2.
PassoPasso 5: Se não, fim do procedimento.
Ng and Han (1994) afirma que os métodos baseados em k-medoids apresentam duasvantagens em relação aos métodos baseados em centros médios: são mais robustos à
presença de outliers (objetos fora do padrão dos demais objetos) e são independentes daordem pela qual os objetos são examinados. A Figura 3, apresenta a evolução daspartições, em busca de uma partição com custo mínimo.
Por procurar exaustivamente, no passo 3, pelo conjunto que k medoids que minimiza asdissimilaridades, PAN não é eficiente, principalmente quando aplicado a grandesvolumes de dados. Para cada medoid, são investigados (n-k) possibilidades de troca;
considerando todos os medoids, temos um total de k(n-k) trocas. Como exemplo, emum caso, envolvendo 1000 objetos e 10 clusters, seriam avaliadas 9.900 trocas em cadaiteração do algoritmo.
- 16 -
Figura 3: Algoritmo PAN (k-medoids).
- 17 -
3.3 – Métodos para Spatial Data Mining
3.3.1 - CLARA
O algoritmo CLARA (Clustering Large Applications) utiliza uma amostra contendo m
dos n objetos e realiza o algoritmo PAN sobre ela, de forma a determinar os k medoidsque minimiza ( )πf utilizando apenas m objetos . Então, definidos os medoids, os (n –m) objetos restantes são agrupados, em função da menor dissimilaridade em relação ao
conjunto de medoids. Se a amostra é bem realizada, e consequentemente representativa,os medoids determinados sobre a amostra tendem a se aproximar no espaço de atributosdos medoids que seriam obtidos considerando todo o conjunto de n objetos. É sugerido
que na execução deste algoritmo, se realize múltiplas amostras para escolher dentre elas,a amostra para qual o resultado apresente uma menor dissimilaridade média entre os k-clusters (Ng e Han, 1994) (Koperski et al., 1997).
O algoritmo CLARA, obviamente, é bem mais rápido que o PAN, pois examina apenasum subconjunto de k medoids possíveis, mas a qualidade do resultado é evidentementedependente da qualidade da amostra e sua aplicabilidade cresce junto com o número de
objetos a serem analisados. Segundo Kaufman [1990 #75] (citado por (Ng and Han1994)), resultados experimentais indicam que 5 amostras contendo (40 + 2 k) objetoscada uma, produzem resultados satisfatórios.
Algoritmo CLARA:
Passo 1Passo 1: Para i = 1 até 5, repetir os seguintes passos:
PassoPasso 2: Realizar uma amostra de m objetos;
Passo 3Passo 3: Executar o algoritmo PAN, sobre os m objetos da amostra, determinando os k
medoids ótimos.
PassoPasso 4: Agrupar os demais ( mn − ) objetos restantes, em função da menor
dissimilaridade em relação aos k medoids.
PassoPasso 5: Calcular o valor de ( )if π , considerando todos os n objetos e comparar o valor
mínimo corrente;
PassoPasso 6: Retornar ao passo 1, para a próxima iteração.
Passo 7Passo 7: Escolher dentre as cinco partições, a correspondente ao mínimo corrente; fim.
- 18 -
3.3.2 - CLARANS
Ng e Han (1994) propõe um terceiro algoritmo baseado em k-medoids denominado deCLARANS (Clustering Large Applications based on Randomized Search). Assim como o
CLARA, este algoritmo realiza a procura por um conjunto ótimo de k medoids apenasem um subconjunto das possíveis combinações de objetos, porém este subconjunto nãoé fixo e nem pré-determinado por uma amostra como no CLARA, e sim, ele executa
uma busca contínua e com certa aleatoriedade por ótimos locais. Este algoritmo produzresultados melhores que o CLARA e converge para o resultado mais rapidamente que oPAN, sendo por isto indicado pelo autor como um método eficiente para Spatial Data
Mining.
Para explicar o mecanismo de busca do CLARANS e comparar sua eficiência em relaçãoao CLARA e ao PAN, (Ng e Han, 1994) faz a seguinte abstração, utilizando grafos. Cada
nó do grafo corresponde a uma partição, representada por um conjunto de k medoids.
Dois nós do grafo, iN e jN , são vizinhos se ji NN I , resultar em um conjunto com)1( −k objetos. Ou seja, dois nós são vizinhos, se eles diferem de apenas um medoid.
Desta forma, o número de vizinhos para cada nó do grafo é igual a: )( knn − vizinhos.Isto é equivalente ao número de trocas possíveis entre um dos medoids e os demaisobjetos no algoritmo PAN.
Como cada nó do grafo corresponde a uma partição, podemos atribuir um custo,calculado por uma função objetivo, como ( )πf , dada anteriormente.
Nesta abstração, o algoritmo PAN, pode ser visto como uma busca neste grafo, onde em
cada passo, a partição corrente corresponde a um nó e procuramos por um nó vizinho,dentre todos os vizinhos possíveis, que minimize ( )πf . No algoritmo CLARA, temosum subgrafo do grafo original, contendo um subconjunto de nós, determinados pela
combinação dos m objetos da amostra tomados k a k. Portando, somente uma partemenor das partições possíveis são investigadas.
De forma semelhante ao método CLARA, o CLARANS, em cada passo do algoritmo,
verifica apenas parte dos nós vizinhos. Porém, os vizinhos investigados são escolhidosaleatoriamente. Desta forma, o CLARANS não realiza uma busca em um subgraforestrito e pré-definido por uma amostra, e sim, investiga parte dos nós vizinhos
definidos dinamicamente, durante a sua execução.
Os passos do algoritmo CLARANS, são descritos a seguir:
Passo 1Passo 1: Entrar com os parâmetros: número de mínimos locais (num_min_local) e
número máximo de vizinhos avaliados por iteração (num_max_vizinhos).
Passo 2Passo 2: Fazer i = 1 e custo_mínimo = valor grande (custo mínimo. armazena menor
custo durante o procedimento).
Passo 3Passo 3: Arbitrar um nó do grafo como nó corrente.
- 19 -
Passo 4Passo 4: Fazer j = 1.
Passo 5Passo 5: Escolher aleatoriamente um nó vizinho, N, e calcular o custo diferencial entre
os dois nós.
Passo 6Passo 6: Se N tem menor custo, fazer de N o nó corrente e voltar ao passo 4.
Passo 7Passo 7: Caso contrário; incrementar j de uma unidade. Se vizinhosnumj max__≤ , ir
para o passo 5.
Passo 8Passo 8: Caso contrário (j > num_max_vizinhos); comparar custo do nó corrente com o
custo_mínimo. Se menor, fazer custo_mínimo igual ao custo do nó corrente e fazer do nó
corrente o melhor_nó (armazena a melhor partição).
Passo 9Passo 9: Incrementar i de uma unidade. Se localnumi _≤ , voltar ao passo 3; senão,
informar melho_nó, e fim do procedimento.
O algoritmo acima, procura em cada iteração por um nó vizinho de menor custo (passo4 ao passo 7), até encontrá-lo ou atingir o número máximo de tentativas dado por
num_max_vizinhos. Se um nó vizinho é encontrado, nova busca é iniciada a partir dele.Ao se verificar o número máximo de vizinhos, sem identificar um nó de menor custo, onó corrente é declarado com sendo um mínimo local e a variável i, utilizada para
contagem do número de mínimos locais, é incrementada. Atingido o número demínimos locais definido por num_min_locais, o algoritmo termina, informando o nócom a menor )(πf como a melhor partição.
A justificativa para o bom desempenho do CLARANS está no fato que o grafocorrespondente apresenta um número elevado de nós e muitas conexões entre eles,apresentado uma multiplicidade de caminhos, que levam a um mesmo nó. Assim é
muito provável que o mínimo local encontrado pelo algoritmo, seja uma solução dequalidade aceitável.
Existem estudos para definir os valores dos parâmetros de entrada do algoritmo,
num_max_vizinhos e num_min_locais, de forma a estabelecer uma relação de
compromisso entre o tempo de processamento e a qualidade do resultado (Ng e Han,
1994).
- 20 -
3.4 – Clustering com Restrição de contiguidadeNos algoritmos apresentados na seçãoseção anterior e na maioria dos estudos envolvendo ouso de métodos de clustering aplicados à Spatial Data Mining são empregados a distância
euclidiana para medir as dissimilaridades entre os objetos e são restritos à representaçãopor ponto. Para aplicarmos métodos de clustering também a objetos espaciais do tipoárea, onde a distância euclidiana não pode ser empregada diretamente, teremos que
utilizar os relacionamentos de vizinhança entre os objetos. Trabalhos envolvendoregionalização e clustering com restrição de contigüidade espacial, aplicam métodos declustering em objetos espaciais representados tanto por ponto quanto por área. Nesta
seção, veremos algumas abordagens utilizadas nestes trabalhos, além de um algoritmoespecífico, chamado de árvore geradora mínima.
Segundo Gordon (1996) existem três abordagens para a classificação com restrição de
contigüidade espacial. Na primeira delas, o procedimento de classificação é realizado emdois estágios. No primeiro estágio, não é considerada a informação espacial e umprocedimento de clustering convencional é executado, utilizando somente os atributos
não-espaciais. No segundo estágio, os clusters são reavaliados observando as relações devizinhança dos objetos. Assim, objetos similares agrupados em um cluster no primeiroestágio mas sem contigüidade espacial, serão separados no segundo estágio formando
regiões distintas.
Este tipo de abordagem permite identificar, entre os dois estágios, se objetos similaresestão ou não espalhados por toda a área de abrangência do estudo, o que pode ser
utilizado como uma rápida avaliação da dependência espacial entre os objetos. Outroaspecto positivo assinalado por Opensahw e Wymer (1995) é referente ao controle dasimilaridade entre os objetos de uma mesma região, garantido pelo primeiro estágio do
processo de regionalização. O inconveniente desta abordagem está na falta de controlesobre o número de regiões resultantes. Para os casos onde existam pequena dependênciaespacial, haverá a tendência a produzir muitas regiões (Wise et al., 1997).
Na segunda abordagem, a dissimilaridade entre os objetos é avaliada considerandosimultaneamente a posição geográfica dos objetos e seus atributos não-espaciais. Ascoordenadas do centróide são consideradas atributos adicionais. São utilizados
algoritmos convencionais de clustering, onde a avaliação da dissimilaridade contém duascomponentes ponderadas, uma para o espaço de atributos e, a outra componente, para adistância geográfica.
Se o peso dado para a componente correspondente à distância geográfica for forte osuficiente, os grupos resultantes do processo de classificação serão contíguos. Este tipode abordagem possui a dificuldade de se estabelecer os pesos ideais para as duas
componentes.
Esta abordagem é utilizada pelo sistema SAGE (Spatial Analysis in a GIS Environment)em seu algoritmo de regionalização. Ele utiliza um procedimento de clustering baseado
- 21 -
no método de particionamento k-médias, cuja a função objetivo é formada a partir detrês critérios (Wise et al., 1997): a) homogeneidade: regiões formados por objetossimilares, considerando atributos não-espaciais; campacidade: as coordenadas dos
objetos membros são próximas; igualdade: a soma do valores de um determinadoatributo, considerando todos os objetos membros (população, por exemplo), sãosemelhantes para todas as regiões.
A função objetivo ( of ) do algoritmo de regionalização do SAGE é definida como umasoma ponderada, dada por (Ma et al., 1997):
iicchho fwfwfwf ++= ,
onde:
- ich weww , são os pesos referentes às três componentes homogeneidade, compacidade eigualdade;
- hf : é uma medida da variância de um ou mais atributos dos objetos nas regiões;
- cf : é uma medida da soma das distâncias dos objetos aos centros dos clusters,considerando todas as regiões;
- if : é uma medida do desvio entre as somas dos valores de um atributo dos objetosmembros das regiões em relação ao valor médio.
A componente correspondente ao critério igualdade foi considerada no SAGE, para
estabelecer no fim do processo, regiões com valores totais próximos de um atributoqualquer, de modo a possibilitar comparações mais apropriadas entre as regiões(exemplo: taxa de mortalidade por câncer). O atributo é definido pelo usuário do SAGE.
Openshaw et al. (1998) critica a abordagem utilizada no procedimento de regionalizaçãodo sistema SAGE e em outros trabalhos anteriores que utilizam abordagens semelhantes(Cliff et al., 1975) (Martin, 1998). Nestes métodos, cada componente da função objetivo,
é uma função isolada e utilizam em seus cálculos variáveis que medem fenômenosdistintos, medido em unidades diferentes e necessitam ser apropriadamentepadronizadas. A qualidade da solução depende dos pesos atribuídos às componentes e
como cada uma delas são padronizadas.
Openshaw et al. (1998) afirma que uma estratégia melhor e mais simples éselecionar uma das funções componentes como a função objetivo e tratar os outros
critérios como restrições de igualdade ou desigualdade (maior que, menor ou igual a,etc.) definindo de forma explícita seus valores (ex.: população mínima dentro de umaregião). A forma mais simples, segundo os autores, para tratar com restrições em
problemas de otimização é a adicionar à função objetivo, funções de penalização querefletem a violação das restrições. Esta solução foi utilizada pelos autores nodesenvolvimento do seu sistema de zoneamento automático denominado de ZDES.
- 22 -
A terceira abordagem de clustering com restrição de contiguidade espacialconsiderara a informação espacial utilizando dispositivos auxiliares, grafo ou matriz,para representar a relação de vizinhança dos objetos. No caso da utilização de uma
matriz, denominada matriz de contigüidade, C, cada elemento da matriz, cij, indica se osobjetos i e j são contíguos ou não. Desta forma, cij = 0 para objetos não vizinhos, e cij = 1para objetos contíguos. De forma equivalente, quando são utilizados grafos, cada objeto
é representado por um vértice ou nó. Somente quando os objetos são vizinhos, existeuma aresta ligando os dois vértices. A Figura 4 mostra a representação da estruturaespacial pela matriz C e por meio de um grafo correspondente.
A forma pela qual as aplicações de clustering espacial usam grafos para explicitar asrelações espaciais de vizinhança é distinta da forma utilizada anteriormente, na seção3.3.2., para explicar a execução do algoritmo CLARANS. Lá, cada nó do grafo
representava uma partição (um conjunto de k medoids), enquanto que agora, cada nórepresenta um objeto espacial. Maravalle et al. (1997) destaca a utilização de grafos comoforma explicitar os relacionamentos de vizinhança nos procedimentos de clustering com
restrição de contigüidade.
Dentro desta terceira abordagem, os algoritmos de clustering tradicionais precisãoser adaptados para o uso em procedimentos com restrição de contigüidade espacial. Nos
algoritmos hierárquicos aglomerativos, por exemplo, dois clusters mais similares sãoaglutinados somente se existem, dois objetos contíguos, um em cada cluster. Nosalgoritmos de relocação iterativa adaptados para a restrição de contigüidade, um objeto
só pode ser relocado em clusters que possuam ao menos um objeto contíguo a ele(Gordon, 1996).
=
0101100100011110
C
P1
P2 P3
P4
Figura 4: Representação da relação espacial de vizinhança por matriz e grafo.
- 23 -
Do ponto de vista da implementação dos métodos com restrição de contiguidade, averificação da existência de objetos contíguos é bem mais fácil de ser executada nosalgoritmos hierárquicos. Uma vez definido os dois clusters com menor dissimilaridade,
Ci e Cj, teríamos alguns passos adicionais, procurando se nos vizinhos de cada um dosobjetos de Ci, existe um objeto pertencente a Cj. Encontrado um vizinho pertencente aCj, a busca é interrompida e a fusão efetivada. Não encontrando, o próximo par de
clusters de menor dissimilaridade é avaliado.
Nos algoritmos de particionamento, a verificação da contiguidade espacial é maiscomplexa, pois ela é dependente da ordem pela qual os objetos vão sendo associados aos
clusters, necessitando de reavaliações até que todos os objetos possam ser atribuídos aum dos clusters contíguos.
Assunção et al., (2000) também utiliza grafos para propor um método de clustering
com restrição de contiguidade espacial, dentro do contexto de otimização, econtornando o problema apontado acima. A seguir, serão apresentados, os conceitos eas idéias principais utilizadas neste trabalho.
Um conglomerado (cluster) é um subconjunto de áreas idealmente homogêneas.Um cluster pode ser formados por um único objeto. Um cluster é conectado se, para todasubdivisão do cluster, em dois subconjuntos disjuntos e complementares, existe pelo
menos uma área de um subconjunto vizinha de pelo menos uma área do outrosubconjunto. O que é equivalente ao conceito que vínhamos utilizando para um clustercontíguo. Um cluster que contenha apenas um objeto, também é considerado contíguo.
E, por fim, uma região é dita particionada em clusters espaciais, quando as áreas foramagrupadas em clusters disjuntos e internamente conectados.
Da teoria de grafos, temos que:
- Um caminho entre dois vértices (nós), 1v e kv , é uma seqüência de nós,
kvvvv ,,,, 321 K , que são conectados pelas arestas: ( ) ( ) ( )kk vvvvvv ,,,,,, 13221 −K .
- Um grafo é conexo, se existe ao menos um caminho ligando dois nós quaisquer do
grafo.
- Um circuito em um grafo, é um caminho onde os nós, inicial e final, são os mesmos.
Ou, há dois caminhos diferentes, ligando dois nós.
- Uma árvore é um grafo conexo, que não contém circuitos.
- Uma árvore geradora para um grafo G, é uma árvore que contém todos os nós de G.Logo, o número de arestas é igual ao número de nós de G, menos uma unidade (n –1).
- 24 -
Um mapa contento objetos do tipo área é representado por um grafo de forma que cadanó da árvore representa um objeto do mapa e os objetos vizinhos no mapa são nósligados por arestas no grafo. A cada aresta, é então, associado um custo, correspondendo
a dissimilaridade entre os objetos. A idéia principal é eliminar sucessivamente as arestasmais “caras”, de forma a reduzir o grafo original a uma árvore geradora, ou seja, semcircuitos, contendo as arestas de menor custo. A árvore resultante deste procedimento é
denominada árvore geradora mínima.
A principal importância da árvore geradora mínima é que, ao removermos dela qualqueraresta, o grafo é dividido em duas sub-árvores desconectadas. Portanto, a árvore
geradora mínima, representa uma condição que a partir da qual, estaremosparticionando os objetos espaciais em regiões distintas.
A Figura 5 representa a construção de uma árvore geradora mínima para um exemplo
hipotético. A largura das arestas que ligam os nós, são proporcionais às dissimilaridadesentre as áreas. Assim, do grafo original, foram eliminadas sucessivamente as arestas maislargas, até se obter um subgrafo conectado e sem circuitos de custo mínimo,
correspondente a árvore geradora mínima.
Figura 5: Construção da árvore geradora mínima.
O algoritmo para a construção da árvore geradora mínima é apresentado por Assunçãoet al. (2000). Esse algoritmo parte do grafo correspondente ao mapa de objetos, conexo e
com custos associados às arestas previamente calculados. A idéia é construir a árvoregeradora mínima de uma forma recursiva, a partir de uma árvore inicial 1T , formada deapenas um nó, e adicionando nós progressivamente, de forma que novas árvores
intermediárias vão sendo geradas ),,( 432 KTTT até chegarmos na árvore final, nT .
- 25 -
Uma versão desse algoritmo, em 3 passos, é apresentado a seguir:
Passo 1Passo 1: Escolher qualquer nó, iv , pertencente ao conjunto completo de n nós, V,fazendo:
{ }ik vTT == 1
Passo 2Passo 2: Encontrar a aresta de menor custo que ligue qualquer nó pertencente a kT a umoutro nó, não pertencente a kT , e acrescentar este nó à árvore, gerando uma nova
árvore, 1+kT .
Passo 3Passo 3: Repita o passo 2, até que todos os nós de V tenham sido incluídos.
Ao final da execução do procedimento descrito por este algoritmo, temos a árvoregeradora mínima, que contém todos os nós, representando todos os objetos. Nesteponto, cada aresta que for eliminada, dividirá a árvore em dois subgrafos desconexos,
correspondendo a dois clusters espaciais (regiões), tais como definidos anteriormente.Portanto, a classificação propriamente dita, se dará com a escolha e eliminação dedeterminadas arestas a partir da árvore geradora mínima. Este processo de escolha e
eliminação de aresta corresponde, segundo o autor, a uma “poda” da árvore geradoramínima.
Assunção et al. (2000) apresenta dois critérios para a escolha e eliminação das arestas. O
primeiro critério, que é uma escolha mais natural, é a eliminação sucessiva das arestas decusto mais elevado, até obter o número desejado de regiões. A cada eliminação é geradoum novo subgrafo conexo e desconectado dos demais. O custo do grafo particionado é a
soma dos custos de todos os subgrafos.
Este critério de poda possui o inconveniente de separar clusters contendo um númerovariável de elementos, ou seja, alguns agrupamentos numerosos e outros com poucos
objetos. No segundo critério apresentado pelo autor, o custo das arestas é alterado nafase de poda da árvore geradora mínima, passando a ser dado por:
Custo da aresta l = SSTOG – SSAl ,
onde:
1) SSTOG é soma dos quadrados dos desvios, associada a árvore, G, dada por:
( )∑∑= =
−=m
j
n
ijijG xxSSTO
1 1
2,
sendo: n, o número total de objetos (nós) em G; ijx , o atributo j do objeto i; m, o
número de atributos considerados; jx ,o valor médio do atributo j, dado por:
∑=
=n
iijj x
nx
1
1.
- 26 -
2) SSAl é a soma das duas parcelas obtidas da soma dos quadrados dos desvios dasduas sub-árvores , Ga e Gb, geradas pela retirada da aresta l da árvore G:
GbGal SSTOSSTOSSA +=
Para calcular a soma dos quadrados dos desvios para as duas sub-árvores, sãocalculados os valores médios dos m atributos, tal como feito para o cálculo de SSTOG,porém, considerando-se apenas os atributos referentes aos objetos pertencentes a cada
sub-árvore de G, Ga e Gb.
As podas seguintes são feitas de forma recursiva, escolhendo sempre a aresta de menorcusto. As Figuras 6, 7, 8 e 9 foram retiradas do exemplo de aplicação do algoritmo de
regionalização, utilizando a árvore geradora mínima apresentado em Assunção (2000).Neste exemplo, o procedimento de regionalização foi aplicado aos 353 setorescensitários do município de São João do Meriti (RJ), utilizando algumas variáveis do
censo de 1991. A Figura 6 mostra o grafo correspondente ao mapa dos setorescensitários do município, onde cada setor aparece como um nó e os setores vizinhos,conectados. A Figura 7, mostra a árvore geradora mínima. A Figura 8, mostra as diversas
sub-árvores após a retirada de 16 arestas. A Figura 9, ilustra as 17 regiões obtidas.
Nesta revisão bibliográfica, nós destacamos o algoritmo da árvore geradora mínima, porele ser aplicável a objetos do tipo área e utilizar explicitamente as relações de vizinhança
dos objetos. Além disso, o fato do processo de otimização, propriamente dito, ocorrerapós a construção da árvore geradora mínima, faz com que o número de arestasinvestigadas seja bem reduzido em comparação ao número de arestas existentes no grafo
original, diminuindo o custo computacional utilizado no processo de otimização.
No algoritmo PAN, em cada iteração eram investigadas k(n-k) possibilidades de trocaentre os k medoids e os (n-k) objetos restantes. Nós utilizamos, anteriormente, um
número fictício de objetos e clusters (1.000 objetos em 10 clusters) para compararmos aeficiência do PAN à outros métodos. Isto resultou em 9.900 possibilidades de troca emapenas uma iteração do PAN.
Se fôssemos utilizar um método baseado na árvore geradora mínima, na primeira poda,seriam investigadas 999 arestas; na segunda 998, e assim sucessivamente, resultando novalor total em 9.945 possibilidades de poda. Este valor é próximo ao número de
partições investigadas em apenas uma iteração do algoritmo PAN. Ainda que, para umacomparação precisa, tenhamos que considerar o custo computacional adicional para ageração da árvore geradora mínima e que as funções objetivo associada a cada nova
partição nos dois métodos não são iguais, a diferença na quantidade de possibilidades aserem investigadas a cada iteração, indicam que o uso da árvore geradora mínima épromissor no contexto de Spatial Data Mining.
- 27 -
coordenada x
coo
rde
na
da
y
664000 666000 668000 6700007.4
76
*10
^67
.47
8*1
0^6
7.4
80
*10
^67
.48
2*1
0^6
12
34567 8
9 101112
13141516
1718
19
20
21
2223 24252627
28293031
323334
35 3637 3839
40
41
42 4344
4546
47 484950
5152
5354 5556 57
5859
6061
6263 64 6566
6768
697071 72
73
7475
76777879 80
8182 8384 85 86 8788
899091 9293 94
959697
98
99
100101
102103
104105
106
107108109 110 111
112113 114 115116
117118
119
120121 122123
124125
126 127128129
130131
132133134 135
136137138
139140
141142
143144 145 146
147148
149150
151
152153154
155156 157 158
159
160161 162163 164165166167 168 169
170171 172
173 174175
176177178 179180 181182183184
185186
187188189190191 192
193
194195196 197198 199200 201202203204
205
206 207208209
210211 212
213214 215
216217 218
219220221222 223
224225 226227
228229
230
231232 233234
235236 237 238
239 240 241242243 244245246
247248
249250
251 252253254
255256
257258259260261 262263
264265 266267
268269
270271
272273274
275
276277
278279
280281282 283284 285
286 287288
289290
291 292
293294 295
296297
298 299300301
302303304 305306
307308 309
310 311312313314 315
316 317318 319320
321 322323 324 325326
327328 329
330331 332333334
335 336337338 339340 341342
343344 345
346 347348
349350 351
352
353
Grafo/Mapa de Sao Joao do Meriti
coordenada x
coo
rde
na
da
y
664000 666000 668000 6700007.4
76
*10
^67
.47
8*1
0^6
7.4
80
*10
^67
.48
2*1
0^6
12
34567 8
9 101112
1314
151617
18
19
20
212223 242526 27 2829
3031
323334
35 3637 3839
40
41
42 4344 45
46
47 484950
5152
5354 5556 57
58
59
6061
6263 64 6566
6768
697071 72
73
74757677
7879 80
8182 8384 85 86 8788
899091 9293 94
959697
98
99
100101
102103
104 105
106
107108109 110 111
112113 114 115116
117118
119
120121 122123
124125
126 127128129
130131
132133134
135136
137138 139140141
142143
144 145 146
147148
149150
151
152153154
155156 157 158
159
160161 162163 164165166167 168 169
170171 172
173 174175
176177178 179180 181182183184
185186
187188189190191 192
193
194195196 197198 199200 201202203204
205
206 207208209
210211 212
213214 215
216217 218
219220221222 223
224225 226227
228229
230
231232 233
234
235
236 237 238239 240 241242
243 244245246247
248249
250251 252
253254255
256257258259260
261 262263264265 266267
268269
270271
272273274
275
276277
278279
280281282 283 284 285286 287
288289
290291 292
293294 295
296 297298 299
300301
302303304 305306
307308 309310 311312
313314 315316 317
318 319320321 322
323 324 325326327
328 329330331 332333
334335 336
337338 339340 341342343
344 345346 347348
349350 351
352353
Arvore Geradora Minima Sao Joao do Meriti
Figura 6: Grafo correspondente aos setores censitários de São João do Meriti. (extraído de Assunção,
Figura 7: Árvore geradora mínima. (extraído de Assunção, 2000.)
- 28 -
Figura 8: Particionado em 17 regiões (sub-árvores). (extraído de Assunção, 2000)
Figura 7: Árvore geradora mínima. (extraído de Assunção, 2000)
coordenada x
coo
rde
na
da
y
664000 666000 668000 670000
7.4
77
*10
^67
.47
9*1
0^6
7.4
81
*10
^6
- 29 -
4 - METODOLOGIAPara atingir os objetivos deste trabalho de pesquisa, pretendemos desenvolver umambiente de experimentação, adaptar e implementar diferentes métodos de clustering
espacial, utilizando dados reais e experimentais, verificando a eficiência e ocomportamento geral dos métodos. As etapas do desenvolvimento do trabalho, bemcomo, os dados que serão utilizados, são apresentados a seguir:
i) Escolha e preparação dos dados
Um dos passos do processo de KDD, anterior ao passo de aplicação dos algoritmos demineração, propriamente dito, é a preparação dos dados. No nosso caso, estamos
desenvolvendo métodos específicos de Data Mining, e os dados serão preparados deuma forma isolada e prévia à aplicação dos procedimentos de mineração.
Os objetos espaciais utilizados neste estudo de técnicas de Spatial Data Mining, serão os
municípios brasileiros incluídos na bacia hidrográfica do Rio São Francisco. Estesmunicípios pertencem a cinco estados (Alagoas, Bahia, Minas Gerais, Pernambuco eSergipe). Os atributos não-espaciais selecionados, estão diretamente e indiretamente
ligados ao uso e demanda de água, fonte de poluição hídrica, doenças com vinculaçãohídrica e condições socioeconômicas das populações, entre outros. Estes dados sãooriundos de diferentes bases de dados: censo demográfico (Instituto Brasileiro de
Geografia e Estatística - IBGE), censo agropecuário (IBGE), divisão municipal (IBGE) edados de mortalidade por doença (Sistema Único de Saúde - SUS).
ii) Construção de um ambiente de experimentação
O ambiente de experimentação tem como objetivo suportar o desenvolvimento eavaliação dos algoritmos de clustering espacial. Ele deverá permitir a interface com ousuário, para a definição dos parâmetros e dos atributos, dados, além de dispositivos de
visualização dos dados (atributos, geometria) e dos resultados dos procedimentos.
Este ambiente será desenvolvido utilizando sistema operacional Windows, linguagem deprogramação C++ e a biblioteca TerraLIB. A TerraLib é uma biblioteca de componentes
de Sistemas de Informação Geográfica (SIG) que está sendo desenvolvida pelo INPE eparceiros. O objetivo da TerraLib é suportar desenvolvimentos de uma nova geração deaplicações em SIG (Câmara, Vinhas et al. 2001).
iii) Escolha dos métodos a serem desenvolvidos
Serão desenvolvidos um conjunto de métodos de clustering com restrição espacial,
utilizando as abordagens apresentadas em (Gordon, 1996) (em dois estágios econsideração direta das relações de vizinhança), combinando com métodos departicionamento, hierárquico aglomerativo e árvore geradora mínima. Os métodos de
- 30 -
particionamento e hierárquico, não são diretamente aplicáveis e serão adaptados para autilização em objetos-área e com restrição de contigüidade espacial.
iv) Verificação do desempenho dos métodos
Os métodos serão testados, utilizando um volume considerável de dados, tanto dadosreais como dados construídos artificialmente, buscando explorar e comparar as
características dos métodos para as diversas situações (combinação de métodos eabordagens), sendo avaliadas a eficiência dos métodos e a qualidade dos resultadosobtidos pelos diferentes procedimentos.
A qualidade da partição dos objetos, serão avaliadas utilizando medidas, relacionadascom a homogeneidade interna, entre objetos de um mesmo cluster (ex.: innerdissimilarity), e separação entre clusters (ex.: split) como definidas em Maravalle et al.
(1997).
v) Verificação do efeito da dependência espacial
Utilizando os métodos implementados, verificaremos se nos processos de agrupamentocom restrição de contigüidade espacial, os atributos com alta dependência espacial têmpredominância sobre atributos com pequena dependência espacial. Isto será feito,
submetendo os objetos a vários procedimentos de clustering, combinando atributos comdiferentes dependências espaciais, verificando os resultados para cada caso. Adependência espacial dos atributos utilizados nos experimentos serão avaliadas pela
medida de auto-correlação espacial dada pelo índice global de Moran (Anselin, 1995;Bailey e Gatrell, 1995).
vi) Proposta e desenvolvimento de um método alternativo
Dependendo dos resultados obtidos no item v), pretendemos desenvolver um novométodo de Spatial Data Mining que utilize a informação da dependência espacial em três
níveis: seleção ou desconsideração de atributos utilizados na análise; condução dosmétodos na busca da solução ótima em algoritmos iterativos; e ainda, como critério deavaliação do particionamento.
- 31 -
5 - RESULTADOS ESPERADOS
i) Ambiente de experimentação
O primeiro resultado esperado para este trabalho, é o ambiente de experimentação queserá desenvolvido para suportar a implementação e teste dos métodos de clusteringespacial. Este ambiente poderá ser utilizado no desenvolvimento de outros métodos, de
Spatial Data Mining, análise espacial e regionalização, que não estão no escopo dotrabalho aqui proposto. Este ambiente também poderá ser utilizado como base de umsistema maior de apoio a prospecção de informação espacial, incorporando outras
ferramentas de mineração de dados.
ii) Caracterização da aplicabilidade de métodos e abordagens
Os métodos usuais de Spatial Data Mining, consideram os objetos espaciais comopontos. Um outro resultado importante deste trabalho, será a avaliação da aplicabilidadede vários métodos de clustering em objetos do tipo área, com restrição de contiguidade,
dentro do contexto de grandes volumes de dados.
iii) Método alternativo para Spatial Data Mining
Pretendemos desenvolver um novo método de Spatial Data Mining, utilizando asinformações de dependência espacial para orientar o processo, eliminar e selecionaratributos, e avaliar partições resultantes do processo de clustering.
iv) Estudo de caso
Pretendemos desenvolver um estudo, envolvendo um caso real, com um númeroconsiderável de objetos espaciais e atributos, fornecendo informações importantes
(padrões e relacionamento espacial) referentes aos objetos presentes na área estudada.
- 32 -
6 - CRONOGRAMA
Jan Fev Mar Abr Mai Jun Jul Ago Set
Preparação dos dados
Ambiente de experimentação
Estudo e implementação de algoritmos
Verificação do desempenho
Análise do efeito da dependência espacial
Desenvolvimento de novo método
Estudo de caso
Elaboração do texto da tese
- 33 -
REFERÊNCIAS BIBLIOGRÁFICAS
ANDEBERG, M.R. Cluster analysis for applications. New York: Academic Press, 1973.
ANSELIN, L. Local indicators of spatial assotiation - LISA. Geographical Analysis, v. 27,n. 2, p. 93-115, 1995.
ANSELIN, L. Space Stat, version 1.80: User Guide, 1995.
ANSELIN, L.; BAO, S. Exploratory spatial data analysis linking SpaceStat and ArcView.In: FISCHER, M.M.; GETIS, A., Eds., Recent Developments in Spatial Analysis:Spatial Statistics, Behavioural Modelling, and Computational Intelligence. Berlin:
Springer, 1997, p. 35-59.
ASSUNÇÃO, R.M.; LAGE, J.P.; A.REIS, E.; SILVA, P.L.N. Análise de conglomerados
espaciais via árvore geradora mínima., 2000.
BAILEY, T.C.; GATRELL, A.C. Interactive spatial data analysis. Harlow: Longman, 1995.
BUTTENFIELD, B.; GAHEGAN, M.; MILLER, H.; YUAN, M. Geospatial Data Miningand Knowledge Discovery., 2001.
CÂMARA, G.; VINHAS, L.; SOUZA, R.C.M.D.; PAIVA, J.A.; MONTEIRO, A.M.V.;CARVALHO, M.T.D.; RAOULT, B. Design Patterns in GIS development: the
TerraLib experience. In: III WorkShop Brasileiro de GeoInformática, Rio deJaneiro, 2001.
CLIFF, A.D.; HAGGETT, P.; ORD, K.; BASSETT, K.; DAVIES, R. Elements of SpatialStructure. Cambridge, 1975.
ESTER, M.; GUNDLACH, S.; KRIEGEL, H.-P.; SANDER, J. Database primitives forSpatial Data Mining. In: International Conference on Databases in Office,Engineering and Science, Freiburg, 1999a.
- 34 -
ESTER, M.; KRIEGEL, H.-P.; SANDER, J. Knowledge Discovery in Spatial Databases.In: 23rd German Conference on Artificial Intelligence, Bonn, Germany, 1999b.
FAYYAD, U.; PIATETSKY-SHAPIRO, G.; SMYTH, P. From data mining to knowledgediscovery: an overview. In: FAYYAD, U.; PIATETSKY-SHAPIRO, G.; SMYTH,
P.; UTHURUSAMY, R., Eds., Advances in knowledge discovery. Cambridge: MITPress, 1996, p. 1-36.
GOEBEL, M.; GRUENWALD, L. A survey of data mining and knowlodge discoverysoftware tools. SIGKDD Explorations, v. 1, p. 20-33, 1999.
GORDON, A.D. Classification - methots for the exploratory analysis of multivariate data. 1ed. London: Chapmam and Hall, 1981.
GORDON, A.D. A survey of constrained classification. Computatuonal Statistics & DataAnalysis, v. 21, n., p. 17-29, 1996.
KAUFMAN, L.; ROUSSEEUW, P.J. Finding groups in data: an introduction to clusteranalysis: Jonh Wiley & Sons, 1990.
KOPERSKI, K.; ADHIKARY, J.; HAN, J. Spatial Data Mining: progress and challengessurvey paper.,,, 1997.
MARAVALLE, M.; SIMEONE, B.; NALDINI, R. Clustering on trees. Computational
Statistics & Data Analysis, v. 24, n., p. 217-234, 1997.
MARTIN, D. Optimizing census geography: the separation of collection and output
geographies. International Journal of Geographical Information Science, v. 12, n.,p. 673-685, 1998.
NETER, J.; WASSERMAN, W.; KUTNER, M.H. Applied Linear Regression Models. 2a.ed. Homewood: Irwin, 1989.
NG, R.T.; HAN, J. Efficient and effective clustering methods for Spatial Data Mining. In:Twentieth International Conference on Very Large Data Base, Santiago, 1994.
- 35 -
OPENSHAW, S.; ALVANIDES, S.; WHALLEY, S. Some further experiments withdesigning output areas for the 2001 UK census., v. 2001: University of Leeds, 1998.
OPENSHAW, S.; WYMER, C. Classifying and regionalizing census data. In:OPENSHAW, S., Ed., Census users' handbook. Cambridge: GeoInformation
International, 1995, p. 460.
RICHARDS, J.A. Remote Sensing Digital Image Analysis - An Introduction. 3 ed. Berlin:
Springer-Verlag, 1995.
RODDICK, J.F.; HORNSBY, K., Eds. Temporal, Spatial, and Spatio-Temporal Data
Mining. CARBONELL, J.G.; SIEKMANN, J. Lecture Notes in ArtificialIntelligence. Berlin: Springer, 2001.
SCHOWENGERDT, R.A. Remote Sensing, models and methods for image processing. 2a.ed. San Diego: Academic Press, 1997.
WISE, S.; HAINING, R.; MA, J. Regionalisation Tools for The Exploratory SpatialAnalysis od Health Data. In: FISCHER, M.M.; GETIS, A., Eds., RecentDevelopments in Spatial Analysis: Spatial Statistics, Behavioural Modelling, and
Computational Intelligence. Berlin: Springer, 1997, p. 83-100.
ZEITOUNE, K.; YEH, L.; AUFAURE, M.-A. Join Indices as a Tool for Spatial Data
Mining. In: RODDICK, J.F.; HORNSBY, K., Eds., Temporal, Spatial and Spatio-Temporal Data Mining, Lecture Notes in Artificial Intelligence. Berlin: Springer,2001, p. 105-116.
ZHANG, B.; HSU, M.; DAYAL, U. K-harmonic means - A spatial clustering algorithmwith bossting. In: RODDICK, J.F.; HORNSBY, K., Eds., Temporal, Spatial andSpatio-Temporal Data Mining, Lecture Notes in Artificial Intelligence. Berlin:
Springer, 2001, p. 31-45.
