Deteçcão de clusters espaciais através de otimiza¸cão … · 2019. 11. 14. · Resumo Clusters espaciais irregulares ocorrem com frequência em estudos epidemiológicos,

Universidade Federal de Minas Gerais

Detecção de clusters espaciais atravésde otimização multiobjetivo

André Luiz Fernandes Cançado

Tese submetida à banca examinadora designada pelo Colegi-

ado do Programa de Pós-Graduação em Engenharia Elétrica

da Universidade Federal de Minas Gerais como parte dos re-

quisitos para a obtenção do t́ıtulo de Doutor em Engenharia

Elétrica.

Orientador: Luiz Henrique Duczmal

Co-Orientador: Ricardo Hiroshi Caldeira Takahashi

“ A meus pais, Lenira e Murilo. ”

iii

Agradecimentos

Ao professor Luiz, pela orientação e incentivo. Por ter acreditado em mim e por ter

estado sempre dispońıvel e disposto a me ajudar. Por ter me ensinado a ter uma visão

sempre voltada para os aspectos relevantes da ciência e a sempre buscar a pergunta

correta.

Ao professor Ricardo, por ter abraçado esse trabalho e por tantas contribuições.

Ao professor Carlos, pelo acolhimento na Universidade do Algarve e apoio durante

meu estágio de doutorado em Faro. Pela dedicação ao trabalho e ao nosso grupo da

UFMG. Pelas inúmeras cŕıticas, sugestões e contribuições.

Aos meus irmãos, Cláudia, Ricardo e Juliana, pelo apoio incondicional e pelos mo-

mentos de descontração.

Aos colegas do GOPAC, pela convivência.

Ao grupo de otimização, pelas cŕıticas e sugestões durante nossas reuniões semanais,

em especial aos colegas Beth, Carrano, Rodrigo e Gladston, e aos professores Oriane e

Serjão.

Aos funcionários do PPGEE, em especial à Anete e à Arlete, sempre dispostas a

quebrar qualquer galho burocrático.

Aos professores do PPGEE.

Aos colegas do Departamento de Estat́ıstica, em especial ao Anderson e ao Caicó,

parceiros e amigos.

Ao professor Sabino, pelos papos sobre trabalho e sobre música, ambos essenciais

durante o doutorado.

À CAPES por ter-me concedido uma bolsa de doutorado no Brasil e uma bolsa de

estágio de doutorado no exterior.

À Iana, pelo companheirismo, deidicação e paciência.

iv

Resumo

Clusters espaciais irregulares ocorrem com frequência em estudos epidemiológicos, mas

seu delineamento geográfico é mal definido. Os métodos atuais de detecção encontram

somente uma dentre as várias soluções posśıveis, com formas diferentes, da mais com-

pacta até a mais irregular, correspondentes ao variados graus de penalização impostos à

liberdade de forma. E mesmo quando um conjunto completo de soluções está dispońıvel,

a escolha do parâmetro mais adequado é deixada a cargo do analista, cuja decisão é sub-

jetiva. Propomos um critério quantitativo para a escolha da melhor solução através de

otimização multiobjetivo, encontrando o conjunto Pareto-ótimo. Dois objetivos confli-

tantes estão envolvidos na busca: regularidade da forma e avaliação da estat́ıstica scan.

Ao invés de executar sequencialmente um algoritmo de detecção de clusters variando o

grau de penalização, todas as soluções são encontradas em paralelo, através de um al-

goritmo genético multiobjetivo. O método é rápido e apresenta bom poder de detecção.

A introdução do conceito de conjunto de Pareto nesse problema, seguido da escolha da

solução mais significativa, permite que a escolha da melhor solução seja rigorosa, mas

sem a necessidade de nenhum parâmetro arbitrário. O conceito de significância do clus-

ter é estendido de maneira natural através do uso da função de aproveitamento, sendo

empregado como critério de decisão para escolha da melhor solução. Os modelos de

Gumbel e Weibull são utilizados para aproximar a distribuição emṕırica da estat́ıstica

scan, aumentando a velocidade de estimação da significância. Essa metodologia é com-

parada ao algoritmo genético mono-objetivo. Uma aplicação na detecção de cluster de

câncer de mama é discutida. Por fim, o problema de detecção de clusters é relaxado e

modelado como um problema knapsack, permitindo que se obtenha uma cota superior,

em contraste com a cota inferior obtida pelo algoritmo genético.

Palavras-chave: Otimização multiobjetivo, conjunto de Pareto, algoritmo genético,

estat́ıstica espacial scan, cluster espacial, compacidade, penalização geométrica, distri-

buição de Gumbel, distribuição de Weibull.

v

Abstract

Irregularly shaped spatial disease clusters occur commonly in epidemiological studies,

but their geographic delineation is poorly defined. Most current spatial scan software

usually displays only one of the many possible cluster solutions with different shapes,

from the most compact round cluster to the most irregularly shaped one, corresponding

to varying degrees of penalization parameters imposed to the freedom of shape. Even

when a fairly complete set of solutions is available, the choice of the most appropriate

parameter setting is left to the practitioner, whose decision is often subjective. We pro-

pose quantitative criteria for choosing the best cluster solution, through multi-objective

optimization, by finding the Pareto-set in the solution space. Two competing objecti-

ves are involved in the search: regularity of shape, and scan statistic value. Instead of

running sequentially a cluster finding algorithm with varying degrees of penalization, all

solutions are found in parallel, employing a genetic algorithm. The method is fast, with

good power of detection. The introduction of the concept of Pareto-set in this problem,

followed by the choice of the most significant solution, is shown to allow a rigorous sta-

tement about what is a “best solution”, without the need of any arbitrary parameter.

The cluster significance concept is extended for this set in a natural way through the use

of the attainment function, being employed as a decision criterion for choosing the op-

timal solution. The Gumbel and Weibull models are used to approximate the empirical

scan statistic distribution, speeding up the significance estimation. The multi-objective

methodology is compared with the single-objective genetic algorithm. An application to

breast cancer cluster detection is discussed. Finally, a knapsack approach is proposed for

a relaxed version of the problem, allowing an upper bound to be obtained, in contrast

with the lower bounds obtained by the genetic algorithm.

Keywords: Multi-objective optimization, Pareto set, genetic algorithm, spatial scan

statistic, spatial disease cluster, geometric compactness penalty correction, Gumbel dis-

tribution, Weibull distribution.

vii

Sumário

Agradecimentos iv

Resumo v

Abstract vi

Sumário viii

Lista de Figuras xiii

Lista de Tabelas xvii

1. Introdução 1

1.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2. Estrutura do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Detecção de clusters 5

2.1. Estat́ıstica Espacial Scan de Kulldorff . . . . . . . . . . . . . . . . . . . . . 6

2.2. Métodos de detecção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.1. O método Scan Circular . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.2. Detecção de clusters irregulares . . . . . . . . . . . . . . . . . . . . . 12

2.3. Penalização geométrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3. Algoritmo Genético para detecção de clusters 19

3.1. Aspectos estruturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2. O Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2.1. Geração da população inicial . . . . . . . . . . . . . . . . . . . . . . 23

3.2.2. O operador de cruzamento . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2.3. O operador de mutação . . . . . . . . . . . . . . . . . . . . . . . . . 28

ix

3.2.4. O operador de seleção . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2.5. Parâmetros e Estrutura do Algoritmo . . . . . . . . . . . . . . . . . 31

3.3. Abordagem multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3.1. Otimização multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3.2. Algoritmo genético multiobjetivo . . . . . . . . . . . . . . . . . . . . 36

3.4. Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4. Inferência Estat́ıstica 43

4.1. Caso mono-objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1.1. Cálculo paramétrico do p-valor . . . . . . . . . . . . . . . . . . . . . 45

4.2. Caso multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2.1. Descascamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.2.2. Faixas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.2.3. Função de aproveitamento . . . . . . . . . . . . . . . . . . . . . . . . 50

4.2.4. Cálculo paramétrico do p-valor . . . . . . . . . . . . . . . . . . . . . 52

4.3. Modelos paramétricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.3.1. Modelo Gumbel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.3.2. Modelo Weibull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.3. Estimação de parâmetros . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4. Resultados experimentais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.4.1. Scan Circular e AG mono-objetivo . . . . . . . . . . . . . . . . . . . 56

4.4.2. Caso multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.5. Avaliação do poder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5. Aplicação 71

6. Controlando o erro: Abordagem knapsack 81

6.1. Fundamentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.2. Formulação Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6.3. Resultados experimentais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.3.1. Caso mono-objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.3.2. Caso bi-objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.4. Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7. Considerações finais e trabalhos futuros 97

7.1. Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

x

7.2. Produção bibliográfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

A. Técnicas de geração de soluções eficientes 103

A.1. Problema Ponderado - Pλ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

A.2. Problema �-restrito - P� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

B. Teste de Kolmogorov-Smirnov 107

Referências Bibliográficas 109

xi

Lista de Figuras

2.1. Diferentes zonas dentro de um mapa . . . . . . . . . . . . . . . . . . . . . . 7

2.2. Maiores incidências e verossimilhanças no mapa do Nordeste dos Estados

Unidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3. Mapa, centróides e zona obtida por uma janela circular . . . . . . . . . . . 11

2.4. Superestimação e subestimação da solução . . . . . . . . . . . . . . . . . . 13

2.5. Cluster encontrado pelo simulated annealing sem penalização . . . . . . . 14

3.1. Um mapa dividido em regiões e o grafo associado . . . . . . . . . . . . . . 20

3.2. Zonas vizinhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3. Geração de um indiv́ıduo via algoritmo guloso. . . . . . . . . . . . . . . . . 24

3.4. Exemplo de cruzamento 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.5. Árvores TA e TB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27



3.8. Dominância e conjunto de Pareto. . . . . . . . . . . . . . . . . . . . . . . . . 35

3.9. Evolução da população no AG multiobjetivo . . . . . . . . . . . . . . . . . 40

4.1. p-valor alto e p-valor baixo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2. Conjunto de Pareto cŕıtico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

xiii

4.3. O espaço LLR vs. K é dividido em faixas e a análise unidimensional é

feita para cada faixa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.4. (a) A superf́ıcie de aproveitamento divide o espaço em duas regiões. (b)

A função de aproveitamento obtida por múltiplas execuções do algoritmo

biobjetivo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.5. qq-plot e histograma com o modelo de Gumbel ajustado para os dados

do Scan Circular. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.6. qq-plot e histograma com o modelo de Weibull ajustado para os dados do

Scan Circular. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.7. qq-plot e histograma com o modelo de Gumbel ajustado para os dados

do AG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.8. qq-plot e histograma com o modelo de Weibull ajustado para os dados do

AG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.9. qq-plots para o modelo Weibull em valores diferentes de K, usando a

aproximação pelo fecho convexo. . . . . . . . . . . . . . . . . . . . . . . . . 59

4.10. qq-plots para o modelo Gumbel em valores diferentes de K, usando a

aproximação pelo fecho convexo. . . . . . . . . . . . . . . . . . . . . . . . . 61

4.11. Modelos Weibull (a) e Gumbel (b) ajustados para valores de K(z) fixoscalculados usando a aproximação por fecho convexo. . . . . . . . . . . . . 61

4.12. qq-plots para o modelo Weibull para valores diferentes de K, usando apro-

ximação por fronteiras comuns. . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.13. qq-plots para o modelo Gumbel para valores diferentes de K, usando

aproximação por fronteiras comuns. . . . . . . . . . . . . . . . . . . . . . . . 64

4.14. Modelos Weibull (a) e Gumbel (b) ajustados para valores de K(z) fixoscomputados usando aproximação por fronteiras comuns. . . . . . . . . . . 64

4.15. Superf́ıcie cŕıtica encontrada pelas técnicas de descascamento, faixas e

função de aproveitamento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.16. Clusters artificiais A − F , BOS, NYC e WAS. . . . . . . . . . . . . . . . . . 68xiv

4.17. Poder para os clusters A − F , BOS, NYC e WAS. . . . . . . . . . . . . . . 695.1. População e incidência de casos de câncer de mama no nordeste dos Es-

tados Unidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.2. Conjunto Pareto-ótimo encontrado para os casos de câncer de mama do

Nordeste dos EUA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.3. Isolinhas de p-valor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.4. Clusters detectados (1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.5. Clusters detectados (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.6. Frequência de ocorrência nas soluções. . . . . . . . . . . . . . . . . . . . . . 80

6.1. Comparação entre as distribuições obtidas pelo AG e pela abordagem

knapsack exata. A distribuição obtida pelo AGI sobre a formulação knap-

sack também é mostrada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.2. Conjunto Pareto-ótimo encontrado pela abordagem knapsack e pelo AG. 92

6.3. Soluções dadas pela abordagem knapsack. . . . . . . . . . . . . . . . . . . . 93

6.4. Soluções dadas pelo AG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

A.1. Problema ponderado e problema ponderado com soluções não suportadas. 104

A.2. Abordagem P�. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

xv

Lista de Tabelas

4.1. p-valores para o teste Kolmogorov-Smirnov. . . . . . . . . . . . . . . . . . . 58

4.2. p-valores dados pelo teste Kolmogorov-Smirnov usando aproximação pelo

fecho convexo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.3. p-valores dados pelo teste Kolmogorov-Smirnov usando a aproximação por

fronteiras comuns. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.4. Poder estimado para clusters artificiais . . . . . . . . . . . . . . . . . . . . . 70

5.1. Resumo dos clusters para os casos de câncer de mama do Nordeste dos

EUA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

xvii

Caṕıtulo 1.

Introdução

Um cluster1 espacial é uma parte de um mapa em que a ocorrência de casos de um

fenômeno de interesse é discrepante do restante do mapa, isto é, alta demais ou baixa

demais. Esse fenômeno é, muitas vezes, a infecção por alguma doença ou a ocorrência

de algum crime. Dáı a importância de se ter métodos eficientes de detecção de clusters

espaciais nas áreas de epidemiologia, criminalidade e até em vigilância anti-terrorismo.

Epidemiologia e vigilância sindrômica fazem uso intensivo de técnicas para detecção e

inferência de clusters espaciais. O delineamento de clusters é uma ferramenta impor-

tante em estudos etiológicos (Lawson et al., 1999), na detecção precoce de manifestações

de doenças (Duczmal & Buckeridge, 2005, 2006; Kulldorff et al., 2005, 2006, 2007) e na

identificação de fatores ambientais relacionados à doença (Patil et al., 2006). A estat́ıs-

tica espacial scan (Kulldorff, 1997) dispońıvel nos softwares SaTScan� e ClusterSeer� é

atualmente usada em vários departamentos de saúde para detecção de clusters circulares

(Kulldorff & Nagarwalla, 1995). Em muitos cenários, no entanto, estamos interessados

em detectar clusters que não estão necessariamente restritos à forma circular. As doen-

ças podem estar concentradas ao longo de um rio, da costa do mar ou de um lago, ou

ainda ao longo de rodovias ou de regiões polúıdas. A idéia do SaTScan foi estendida para

a detecção de clusters com forma eĺıptica (Kulldorff et al., 2006), aumentando a versati-

lidade geométrica do SaTScan original e recentemente outros métodos foram propostos

para a detecção de clusters com forma irregular (Duczmal & Assunção, 2004; Duczmal

et al., 2006; Iyengar, 2004; Tango & Takahashi, 2005; Assunção et al., 2006; Neill et al.,

2005b; Patil & Taillie, 2004). Em Conley et al. (2005) foi apresentado um algoritmo

1Embora exista em português o termo conglomerado, optamos pelo termo em inglês por este já estarincorporado ao vocabulário cient́ıfico.

1

genético baseado em dados pontuais para explorar a configuração espacial de aglomera-

dos múltiplos de elipses. Em Sahajpal et al. (2004) também foi utilizado um algoritmo

genético para detecção de clusters irregulares como interseções de ćırculos com raios e

centros distintos. Em Duczmal et al. (2007) é apresentado um algoritmo genético para

detecção de clusters irregulares em um mapa dividido em um certo número de regiões,

maximizando a estat́ıstica scan com a utilização de uma penalização (Duczmal et al.,

2006) para as soluções altamente irregulares.

O delineamento geográfico de clusters irregulares apresenta algumas dificuldades. A

liberdade geométrica ilimitada para a forma do cluster diminui o poder de detecção

(Duczmal et al., 2006). Isto acontece porque o conjunto de todas as soluções conexas,

independente de forma, é muito grande. O máximo da função objetivo tende a estar

associado a um cluster em forma de árvore, que simplesmente liga as regiões do mapa

com maior verossimilhança, sem contribuir para a descoberta de soluções que fazem o

delineamento correto do cluster verdadeiro. Em outras palavras, há uma grande quan-

tidade de “rúıdo” sobre o qual o “sinal” da solução verdadeira não se sobressai. Este é

um problema que ocorre em todos os métodos de detecção de clusters irregulares e pode

ser contornado, em parte, limitando o número máximo de regiões que podem constituir

cada solução. Outra solução, mais elegante, consiste em aplicar uma penalização usando

o conceito de compacidade (Duczmal et al., 2006, 2007), penalizando a avaliação da es-

tat́ıstica scan de acordo com a irregularidade da forma da solução e generalizando uma

idéia que foi utilizada no caso das elipses (Kulldorff et al., 2006).

Variando a intensidade da penalização quanto à liberdade de forma, várias soluções-

candidatas podem ser encontradas, da circular até a mais irregular. Os algoritmos atuais

de detecção de cluster não permitem o controle da geometria e geralmente apenas uma

solução é obtida. Mesmo quando um conjunto de soluções está dispońıvel, executando o

algoritmo várias vezes e alterando os parâmetros, como em Duczmal et al. (2006, 2007),

a escolha da configuração de parâmetros mais adequada é deixada a cargo do analista,

cuja decisão é, em geral, subjetiva.

1.1. Objetivos

O foco principal deste trabalho é apresentar um novo método para detecção e inferência

de clusters espaciais, baseado em algoritmos genéticos multi-objetivo. Dois objetivos

2

estão envolvidos na busca pelo cluster verdadeiro: (i) valor da estat́ıstica scan e (ii)

regularidade da forma. Propomos um critério quantitativo para escolher a melhor solu-

ção, encontrando o conjunto Pareto-ótimo no espaço de soluções, seguido de um critério

de decisão que consiste em maximizar a significância sobre este conjunto. Dessa forma

a escolha arbitrária e subjetiva da melhor solução é deixada de lado e substitúıda por

uma metodologia teoricamente fundamentada para encontrar tal solução. O conceito de

melhor solução passa a ser bem definido no contexto de detecção de clusters espaciais.

Como subproduto dessa metodologia, um conjunto de soluções alternativas (o conjunto

Pareto-ótimo) se torna dispońıvel para o analista para efeito de comparação e análise

da estrutura intŕınseca do problema. Essas idéias são novas no contexto de detecção

de clusters espaciais, apresentando similaridades com outros problemas de aprendiza-

gem com estrutura multiobjetivo, como em Teixeira et al. (2000) e Nepomuceno et al.

(2003).

Ao invés de executar a busca pela solução várias vezes, variando o grau de penaliza-

ção, o algoritmo multiobjetivo proposto encontra um conjunto de soluções em paralelo.

Como algoritmos genéticos trabalham com populações inteiras de soluções-candidatas,

essa busca por várias soluções em uma única execução torna-se natural para essa classe

de algoritmos e é o que faz com que algoritmos genéticos sejam particularmente efici-

entes na resolução de problemas multiobjetivo (Fonseca & Fleming, 1995). Além disso,

algoritmos genéticos permitem que se consiga escapar de soluções que sejam ótimos lo-

cais, o que os torna ótimas ferramentas para a detecção de clusters (Duczmal et al.,

2007). Usando os conjuntos Pareto-ótimos, o conceito de significância dos clusters é es-

tendido de maneira natural e sem a necessidade de uma escolha arbitrária do parâmetro

de penalização.

1.2. Estrutura do texto

Esta tese está organizada em caṕıtulos. No caṕıtulo 2 introduzimos a estat́ıstica de

teste na qual é baseada a busca de clusters - a estat́ıstica espacial scan - e apresentamos

uma breve revisão dos métodos de detecção de clusters espaciais. Essa revisão abrange o

método Scan Circular clássico, bem como métodos de detecção de clusters com geometria

arbitrária. Iremos ainda dar uma motivação para o uso de uma penalização que é baseada

na geometria dos clusters.

3

No caṕıtulo 3 descrevemos uma estrutura genérica para algoritmos genéticos em ge-

ral. Em seguida o algoritmo genético utilizado para detecção de clusters espaciais é

descrito detalhadamente em termos de seus operadores. Apresentamos uma motivação

para abordar o problema de detecção de clusters espaciais como um problema de oti-

mização bi-objetivo. Faremos uma introdução aos conceitos essenciais de otimização

multi-objetivo e, em seguida, descrevemos as modificações aplicadas ao algoritmo ge-

nético para que obtivéssemos uma algoritmo capaz de atacar o problema bi-objetivo

proposto.

No caṕıtulo 4 fazemos uma discussão sobre técnicas de inferência usadas para se esti-

mar o quão significativos são os clusters detectados e essas técnicas são estendidas para o

caso bi-objetivo. Verificamos ainda a qualidade de ajuste de dois modelos paramétricos

que podem nos auxiliar nessa estimativa. Por fim, o comportamento do algoritmo gené-

tico, em suas versões mono e bi-objetivo, é avaliado em termos de poder, sensibilidade e

valor preditivo positivo.

No caṕıtulo 5 aplicamos o algoritmo genético e as técnicas de inferência descritos

nos caṕıtulos anteriores a dados reais utilizados em trabalhos anteriores, de maneira que

podemos comparar o desempenho dos métodos desenvolvidos nessa tese com resultados

da literatura.

No caṕıtulo 6 abordamos o problema tratado nessa tese sob um outro ponto de

vista. A estrutura do problema é relaxada e mostramos que, assim, o problema pode

ser reduzido a um problema clássico de otimização combinatória: o problema da mo-

chila. Obtendo soluções exatas para o problema assim formulado, teremos condições de

contrastá-las com as soluções obtidas pelo algoritmo genético, obtendo intervalos dentro

dos quais garantidamente se encontram as soluções verdadeiras.

No caṕıtulo 7 apresentamos as considerações finais desta tese e as propostas de con-

tinuidade de trabalho. São relacionadas ainda as publicações decorrentes do trabalho

desenvolvido durante o doutorado.

4

Caṕıtulo 2.

Detecção de clusters

Em muitas aplicações, como em epidemiologia, vigilância sindrômica e criminologia, é

importante levar em conta a população em questão. Ao invés de encontrar regiões com

grande número de casos, uma análise deveria encontrar regiões com número de casos

maior do que o esperado. Nessa linha o trabalho Besag & Newell (1991) utilizava um

método que localizava uma janela circular em cada região envolvida. O raio dessa janela

era então expandido para incluir regiões vizinhas até que um número cŕıtico de casos

definido pelo analista se localizasse dentro da janela. Então a população dentro dessa

janela era comparada àquela esperada sobre a frequência de casos. No entanto, levar

em conta apenas a razão entre número de casos observados e a população (ou o número

de casos esperado) pode levar ao problema de encontrar clusters que não têm nenhuma

significância do ponto de vista estat́ıstico.

Para exemplificar essa idéia, considere duas cidades A e B com populações de risco

NA = 100 e NB = 1.000.000, respectivamente, inseridas em um mapa em estudo. Con-sidere a população de risco total do mapa N = 10.000.000 e o número total de casosobservados C = 100.000. Isto quer dizer que, caso não haja cluster no mapa, a freqüên-cia de casos esperada deve ser de 1 caso para cada 100 habitantes em todas as regiões

do mapa. Logo, o número de casos esperado na cidade A deve ser μA = 1 e na cidadeB, μB = 10.000. Suponha que os casos observado nas cidades A e B sejam, respecti-vamente, cA = 2 e cB = 20.000. Nesse caso, ambas as cidades apresentam risco relativo(número observado de casos dividido pelo número esperado de casos) cA/μA = cB/μB = 2.No caso da cidade A, a probabilidade de que o risco relativo em dobro tenha ocorrido

por mero acaso é muito alta. Já na cidade B há um grande motivo para haver preo-

cupação. A chance de o número de casos passar de 10.000 para 20.000 não pode ser

5

encarada como uma simples flutuação estat́ıstica, e um estudo detalhado deve ser levado

em consideração.

Na próxima seção será apresentada uma estat́ıstica capaz de distinguir regiões como

as do exemplo anterior, a estat́ıstica espacial Scan . Nas seções seguintes apresentaremos

alguns métodos que se utilizam dessa estat́ıstica como medida na detecção de clusters

espaciais.

2.1. Estat́ıstica Espacial Scan de Kulldorff

A estat́ıstica espacial scan proposta em Kulldorff & Nagarwalla (1995) e em Kulldorff

(1997) supera o problema de considerar simplesmente o risco relativo de uma maneira

muito simples. Pelo exemplo anterior é fácil perceber que um aumento no risco relativo

é tão mais significativo quanto maior é a população na região em estudo.

Vamos considerar um mapa dividido em n regiões R1, ...,Rn, cada uma delas com

uma população Ni e um número observado de casos ci. Chamamos de zona qualquer

subconjunto conexo de regiões do mapa. A Figura 2.1 ilustra algumas zonas distintas

dentro do mesmo mapa. Denotaremos por Z o conjunto de todas as zonas do mapa.

Nesta tese de doutorado iremos adotar o modelo de Poisson1 para a distribuição de casos

no mapa. Isto quer dizer que o número de casos Ci dentro da região Ri é uma variável

aleatória com distribuição de Poisson, cuja função de probabilidade é dada por

fi(c) =⎧⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎩

e−λiλic

c!se c ≥ 0

0 caso contrário.

(2.1)

isto é, a probabilidade de que a variável aleatória Ci assuma o valor c é dada por fi(c).O parâmetro λi é a média ou valor esperado da variável. A distribuição de Poisson é

adequada para descrever o número de ocorrências de um evento em um determinado

intervalo de tempo ou em uma determinada região. Assim, assumimos que o número de

1Há ainda a possibilidade de se adotar o modelo multinomial. No entanto, os dois modelos sãoassintoticamente equivalentes.

6

casos Ci dentro da região Ri segue uma distribuição de Poisson com média proporcional

à sua população Ni, ou seja, λi = piNi, onde pi é a probabilidade de que um indiv́ıduona região Ri seja um caso. Denota-se a distribuição de Poisson por Ci ∼ Po(piNi).

(a) (b)

(c) (d)

Figura 2.1.: Quatro diferentes zonas dentro de um mapa.

Sabe-se que a soma de variáveis aleatórias independentes com distribuição de Poisson

é ainda uma variável aleatória com distribuição de Poisson cujo parâmetro é a soma dos

parâmetros das distribuições das variáveis somadas. Vamos assumir, a prinćıpio, que a

probabilidade de que um indiv́ıduo seja um caso seja a mesma em todas as regiões, isto é,

pi = p, i = 1, ..., n. Nessa situação o número de casos Cz em uma zona z será uma variávelaleatória com distribuição de Poisson com parâmetro pNz, onde Nz é a população da

zona z, ou seja, Cz ∼ Po(pNz), ∀z ∈ Z. Note que, de acordo com essa suposição, nãohá clusters no mapa, uma vez que a probabilidade de um indiv́ıduo vir a ser um caso é

igual em qualquer parte do mapa. Essa é a nossa hipótese nula h0.

7

A hipótese alternativa ha é de que exista uma zona z∗ ∈ Z que é um cluster. Nessecaso teŕıamos Cz∗ ∼ Po(pNz∗) e Cz ∼ Po(qNz), ∀z ≠ z∗, com p > q. De maneira queestamos interessados no teste que confronta as hipóteses de z∗ ser ou não um cluster, ou

seja

⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩h0 ∶ p = qha ∶ p > q

(2.2)

Sejam N a população total do mapa e C o número total de casos do mapa. Considere

ainda cz como o número observado e μz como o número esperado de casos dentro de uma

zona z. Definindo L(z) como a função de verossimilhança sob a hipótese alternativa deque exista uma zona z∗ que é um cluster, e L0 como a verossimilhança sob a hipótese

nula de que não exista um cluster, foi mostrado em Kulldorff (1997) que a razão de

verossimilhança (likelihood ratio) LR = L(z)/L0 para o modelo de Poisson pode serescrita como:

LR(z) =⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩

( czμz )cz ( C−czC−μz )C−cz se cz > μz1 caso contrário.

(2.3)

Esta razão maximizada sobre todas as zonas identifica o cluster z∗ mais verosśımil. Dáı

temos a estat́ıstica de teste, dada por T = maxz

LR(z).A função LR escrita como na equação (2.3) nos permite uma interpretação bastante

intuitiva quanto ao seu significado. Observe que o risco relativo em uma zona z é dado

por I(z) = cz/μz, e o risco relativo fora dessa zona é dado por O(z) = (C − cz)/(C −μz).Dessa forma, podemos escrever a função LR como

LR(z) = I(z)czO(z)C−cz (2.4)

8

(a) (b)

Figura 2.2.: (a) As 10% maiores incidências de câncer de mama no mapa do nordeste dosEstados Unidos e (b) as 10% maiores verossimilhanças.

e considerá-la como uma função binomial, onde os pesos são dados pelos casos dentro

e fora da zona z. Em geral é mais conveniente trabalhar com o logaritmo da razão de

verossimilhança, LLR (logarithm of likelihood ratio), já que a função LR cresce muito

rapidamente. Como o logaritmo é uma função estritamente crescente, se z∗ maximiza

LR(z), então z∗ maximiza LLR(z). Note que no caso das duas cidades A e B do exem-plo anterior, embora ambas apresentem o mesmo risco relativo, as respectivas avaliações

de LLR seriam:

LLR(A) = 2 log (21) + 99.998 log (99.99899.999) ≈ 3,8 × 10−1

LLR(B) = 20.000 log (20.00010.000) + 80.000 log (80.00090.000) ≈ 4,4 × 103

Maiores detalhes na derivação da estat́ıstica scan podem ser obtidos em Kulldorff

(1997). A Figura 2.2(a) mostra as regiões de maior incidência de casos de câncer de

mama em um mapa do nordeste dos Estados Unidos. Já a Figura 2.2(b) mostra as

regiões de maior razão de verossimilhança (Duczmal et al., 2006). Em ambas as figuras

foram escolhidas as 10% maiores (de um total de 245 regiões). Observe que as regiões

de maior incidência e maior LLR coincidem apenas algumas vezes.

9

2.2. Métodos de detecção

De posse de uma estat́ıstica que permita avaliar cada zona, nos resta encontrar aquela

que apresenta avaliação máxima. Porém, a maior dificuldade da estimação de clusters

reside exatamente na maximização da estat́ıstica LLR(z) sobre o conjunto Z de todasas zonas posśıveis. Isto porque, embora seja finito, o conjunto Z é em geral tão grande

que torna a maximização de LLR(z) impraticável através de uma busca exaustiva. Paracontornar esse problema, existem basicamente duas técnicas:

� Redução do espaço de parâmetros Z em outro espaço Z ′, onde Z ′ ⊂ Z. O conjuntoZ ′ deve ser escolhido de modo que seu tamanho permita uma busca exaustiva. Esta

técnica funciona bem se o conjunto Z ′ contém a zona z∗ que maximiza LLR(z),ou pelo menos uma boa aproximação para z∗.

� Utilização de métodos estocásticos de otimização. Ainda que esses métodos não

analisem todo o espaço de busca eles podem, sob certas condições, convergir para

o ótimo global.

Podemos ainda classificar os métodos de detecção quanto à geometria dos clusters

encontrados:

� Clusters regulares são aqueles que têm uma forma pré-determinada, em geral cir-

cular. Os métodos analisam apenas clusters que tenham essa forma. Note que

esses métodos, por definição, se utilizam da técnica de redução do espaço de pa-

râmetros, transformando-o em um espaço que só contém clusters-candidatos com

um formato espećıfico.

� Clusters irregulares, que podem apresentar formas arbitrárias. Na classe de mé-

todos que buscam clusters irregulares existem tanto aqueles que se utilizam da

redução do espaço de busca quanto aqueles que se utilizam de regras heuŕısticas

estocásticas.

Os primeiros métodos de detecção de clusters se utilizavam da técnica de redução do

espaço de busca, já que essa é uma técnica mais imediata, menos elaborada e que requer

menor esforço computacional. Os métodos estocásticos são, em geral, mais sofisticados e

se utilizam de regras e heuŕısticas mais complexas, além de fazerem uso de computação

mais intensiva. Na próxima seção faremos uma descrição do principal método de detecção

10

(a) (b)

Figura 2.3.: (a) Um mapa dividido em regiões e seus respectivos centróides e (b) uma zonaobtida por uma janela circular.

utilizando a redução do espaço de parâmetros, o método Scan Circular. Em seguida

faremos uma breve revisão dos principais métodos de detecção de clusters irregulares.

2.2.1. O método Scan Circular

O método scan circular proposto em Kulldorff (1997) pertence à primeira classe de

técnicas, restringindo o espaço de busca apenas às zonas que têm formato circular. Para

isso o método utiliza janelas circulares que varrem o mapa em busca da zona z∗. Para

cada região do mapa definimos um centróide, que é um ponto arbitrário em seu interior.

Assim, uma janela circular sobre o mapa em estudo define uma zona que é constitúıda

pelas regiões cujos centróides se encontram dentro da janela. A Figura 2.3(a) mostra

um mapa dividido em regiões e seus respectivos centróides. A janela circular ilustrada

na Figura 2.3(b) determina a zona formada pelas regiões escuras.

Considere dij a distância entre os centróides ci e cj (das regiões Ri e Rj, respecti-

vamente). O método scan circular escolhe as janelas da seguinte forma: selecione uma

região Rk, 1 ≤ k ≤ n. Ordene as demais n − 1 regiões do mapa quanto à distância aocentróide ck, em ordem crescente, obtendo a seqüência de regiões {Rl1,Rl2 , ...,Rln−1},onde dkl1 ≤ dkl2 ≤ ... ≤ dkln−1 . As janelas são escolhidas como sendo ćırculos cujos centroscoincidem com o centróide ck e com raios iguais a dkl1, dkl2, ..., dkls, onde s é tal que

11

dkls ≤ rmax < dkls+1 , sendo rmax o raio máximo permitido. Cada janela gera uma zona eo processo é repetido para k = 1, ..., n.

Para cada janela avaliamos a zona correspondente através da estat́ıstica scan. O

cluster mais verosśımil é aquele que maximiza LLR(z). Note que a quantidade de raiosutilizados é da mesma ordem de n. De fato, se rmax é maior do que a maior distância

entre centróides do mapa, o número de raios utilizado é n. Caso contrário, esse número

é menor que n. Assim, no método scan circular temos que avaliar no máximo n2 zonas

distintas, o que é computacionalmente simples.

O método scan circular é hoje amplamente utilizado na detecção de clusters espaciais

e, embora a idéia seja bastante simples, o método é eficiente e extremamente rápido. No

entanto, o método falha quando o cluster verdadeiro apresenta uma forma que não seja

circular. Imagine que o cluster verdadeiro apresente uma forma alongada, como a zona

da Figura 2.1(b). O método circular não tem como encontrar essa solução e a solução

por ele apresentada superestima ou subestima o cluster verdadeiro. No primeiro caso

a solução do scan circular contém a solução verdadeira, no sentido de que todas as

regiões que compõem o cluster verdadeiro estão também na solução encontrada. Porém,

várias outras regiões também são inclúıdas na solução, simplesmente porque não existe

um ćırculo que cubra a solução verdadeira sem que isso aconteça (Figura 2.4(a)). Por

outro lado, o método pode incluir em sua solução apenas regiões que estão no cluster

verdadeiro, mas deixar de fora outras regiões que também deveriam estar (Figura 2.4(b)).

Assim, embora em muitos casos o cluster verdadeiro possa apresentar um formato

circular, estamos interessados em métodos que nos permitam encontrar soluções com

outras formas. A próxima seção apresenta alguns métodos utilizados na detecção de

clusters de geometria arbitrária.

2.2.2. Detecção de clusters irregulares

A extensão imediata para o método scan circular é a utilização de janelas de formato

eĺıptico (Kulldorff et al., 2006). A idéia desse método é análoga à do scan circular.

Porém, ao invés de variarmos apenas o tamanho da janela, para cada centróide, podemos

variar também sua orientação e sua excentricidade. Isso faz com que aumentemos o

horizonte de soluções posśıveis, permitindo que sejam detectados clusters com formas

alongadas, por exemplo. Ainda assim, são muitos os casos em que o cluster verdadeiro

12

(a) (b)

Figura 2.4.: (a) A solução encontrada pelo Scan Circular superestima o cluster verdadeiro,incluindo regiões que não lhe pertencem. (b) A solução subestima o clusterverdadeiro, deixando de incluir regiões que pertencem ao cluster verdadeiro.

apresenta um formato que não se encaixa em nenhuma elipse. É o caso, por exemplo,

de um cluster que acompanhasse um rio em forma de “L”, ou um cluster que tenha

um “buraco” como o da Figura 2.1(d) (ver página 7). Na tentativa de solucionar esse

problema começam a surgir métodos que permitem a detecção de clusters com formato

irregular.

Ainda na linha de redução do espaço de busca, os trabalhos de Iyengar (2004) e Tango

& Takahashi (2005) propõem uma flexibilização do scan circular, utilizando janelas com

várias geometrias diferentes, além da circular e da eĺıptica. No entanto, por mais que se

flexibilize a geometria das janelas utilizadas, sempre é posśıvel que o cluster verdadeiro

não se encaixe em nenhum formato pré-determinado. Há ainda o trabalho de Patil

& Taillie (2004) que utiliza a idéia de upper level set (conjunto de ńıvel superior) que

reduz o espaço Z considerando apenas as zonas cujos riscos relativos estão acima de um

determinado ńıvel. No entanto, nenhuma discussão é feita sobre a escolha do parâmetro

ńıvel e resultados e comparações com outros métodos não são apresentados.

Como mencionado anteriormente, a maior dificuldade de se procurar clusters com

formato qualquer é que isto se torna uma tarefa computacionalmente muito complexa.

Em um mapa com n regiões, se quiséssemos verificar todas as possibilidades, teŕıamos

que descobrir quais dos 2n subconjuntos de regiões são conexos e avaliá-los. Essa ordem

de complexidade se torna proibitiva, mesmo para um mapa com poucas regiões.

13

Dáı surgem as primeiras tentativas de se partir para métodos heuŕısticos estocásticos,

que se aproximam de uma boa solução mas não garantem que a melhor solução será

encontrada. Nessa linha o trabalho Duczmal & Assunção (2004) propõe um algoritmo

simulated annealing que faz uma busca estocástica, sem limitar a geometria das soluções-

candidatas analisadas e tentando se aproximar do que seria o cluster verdadeiro. Esse

método faz uma busca aleatória em momentos em que o valor de LLR é baixo e, à medida

que a verossimilhança vai aumentando, aumenta também a chance de o algoritmo fazer

uma busca gulosa. Essas incursões aleatórias são essenciais para que o método não fique

preso em algum ótimo local. O maior problema desse algoritmo é que na maioria das

vezes ele superestima o cluster verdadeiro. Isto é, o cluster verdadeiro está inclúıdo

na solução apresentada, mas várias outras regiões que não lhe pertencem também são

inclúıdas na solução. Isto se deve justamente ao fato de o método permitir que a solução

tenha uma forma qualquer, apenas exigindo que ela seja conexa, e fazendo com que

a solução mais verosśımil encontrada pelo simulated annealing seja simplesmente uma

coleção de regiões de alta verossimilhança que se espalha em forma de árvore por todo o

mapa. A Figura 2.5 mostra o cluster encontrado pelo simulated annealing no mapa da

Nova Inglaterra, EUA, utilizando dados de câncer de mama. Obviamente não estamos

interessados em soluções dessa natureza, uma vez que isso não nos acrescenta nenhuma

informação geográfica a respeito da ocorrência do fenômeno em estudo.

Figura 2.5.: Cluster encontrado pelo simulated annealing sem penalização.

14

Um outro método, proposto em Assunção et al. (2006), utiliza o conceito de árvore

geradora para tentar estimar o cluster verdadeiro. Este método utiliza árvores gera-

doras que são cortadas em partes gerando vários candidatos a cluster. A vantagem

desse método é que encontrar árvores geradoras do grafo que representa todo o mapa

é relativamente barato, além de as partes da árvore gerarem soluções automaticamente

conexas. Porém, este método apresenta o mesmo problema do simulated annealing de

superestimação do cluster verdadeiro, encontrando clusters que se espalham por sobre

todo o mapa.

Há ainda os métodos que se utilizam de dados pontuais, ao invés de dados distribúıdos

em regiões, caracterizando um outro tipo de abordagem. Nesse contexto também existem

vários métodos, inclusive com a utilização de algoritmos genéticos. Podemos destacar os

trabalhos Openshaw & Perrée (1996), Sahajpal et al. (2004) e Conley et al. (2005). Em

todos eles foram apresentadas propostas de algoritmos genéticos onde cada indiv́ıduo é

uma janela circular ou eĺıptica e, portanto, esses algoritmos trabalham com populações

de ćırculos ou elipses (ou aglomerações desses objetos). Como veremos, isso faz com

que esses algoritmos genéticos, além de utilizarem dados pontuais, tenham estruturas e

concepções completamente diferentes do algoritmo aqui utilizado.

Nesta tese de doutorado o método de detecção utilizado foi um algoritmo genético

multiobjetivo baseado no algoritmo genético proposto em Duczmal et al. (2007). Esse

algoritmo será descrito em detalhes no caṕıtulo 3, em suas versões mono e multiobjetivo,

respectivamente.

2.3. Penalização geométrica

Para contornar o problema de superestimação da solução foi proposto por Duczmal et al.

(2006) a utilização de uma penalização geométrica que privilegia o cluster cuja forma

se aproxima da forma circular e penaliza aquele cuja forma é muito irregular. Essa

penalização é baseada no conceito de compacidade. Existem várias formas de se medir

a compacidade geográfica (Selkirk, 1982). No artigo de Duczmal et al. (2006) a área

do cluster era comparada à área do ćırculo cujo peŕımetro coincidisse com o peŕımetro

do fecho convexo do cluster. O fecho convexo foi utilizado por duas razões principais.

Muitas vezes os dados de contornos do mapa não estavam dispońıveis, inviabilizando

o cálculo do peŕımetro da região. Assim, era necessário obter-se uma estimativa do

15

peŕımetro. Essa estimativa pode ser feita baseada no fecho convexo, como a técnica

descrita por Duczmal et al. (2006), ou por outros meios (diagrama de Voronoi, por

exemplo). O segundo motivo é que o uso do peŕımetro real depende da resolução dos

dados de contorno. O contorno de regiões pode ter uma natureza fractal, o que faz com

que o peŕımetro verdadeiro seja grande demais. Uma maneira de contornar o problema

da explosão fractal do peŕımetro é utilizar uma resolução suficientemente baixa, de forma

que a região se torne um poĺıgono cujo peŕımetro seja razoável. Nesta tese utilizamos

a aproximação por fecho convexo e o peŕımetro “real” dado por uma certa resolução.

Utilizamos, então, a seguinte definição de compacidade:

Definição 1 (Compacidade) A compacidade K(z) de uma zona z é definida como

K(z) = 4πA(z)H(z)2 (2.5)

onde A(z) é a área e H(z) é o peŕımetro da zona z.

A expressão (2.5) pode ser reescrita como

K(z) = A(z)π (H(z)2π )2

(2.6)

e, assim, interpretada como a área de z dividida pela área do ćırculo cujo peŕımetro

coincide com o peŕımetro de z. Note que a compacidade de uma zona depende de sua

forma, mas não de seu tamanho. O objeto que apresenta a maior compacidade é o ćırculo,

cuja compacidade é 1. A compacidade de um quadrado é π/4 e a de um retângulo a × 1é πa/(1 + a)2, de forma que quanto mais arredondada é a forma de um objeto, maispróxima de 1 estará sua compacidade. Por outro lado, quanto mais irregular a forma,

mais próxima de 0 será a compacidade.

A penalização geométrica consiste então em substituir a avaliação LR(z) por LR(z)K(z)ou, equivalentemente, LLR(z) por K(z) ⋅LLR(z). Isso faz com que zonas cuja compa-cidade seja próxima de 1 tenham a seu valor de LLR pouco afetado, ams aquelas cujas

16

compacidades sejam muito pequenas terão seu valor bastante diminúıdo. Pode-se ainda

dar maior ou menor importância à correção exercida pela compacidade sobre o valor

de LLR(z) utilizando a penalização na forma K(z)a ⋅ LLR(z), com a ≥ 0. Se a → 0então K(z)a ⋅LLR(z) → LLR(z) e não se tem penalização. À medida que o valor de aaumenta, aumenta-se a força da penalização sobre formas que diferem da circular. Em

particular, quando a → ∞, apenas formas circulares são permitidas.Em Duczmal et al. (2006) o peŕımetro foi substitúıdo pelo peŕımetro do fecho convexo

da zona e verificou-se através de experimentos numéricos que algoritmos de detecção de

clusters irregulares se beneficiam do emprego da penalização geométrica. Essa correção

age como um filtro e restringe a presença de clusters em forma de árvore com valor de

LLR extremamente alto, permitindo a detecção de clusters com valores de LLR um

pouco menores, mas com significado geográfico real. Esses últimos são, em geral, menos

irregulares que aqueles em forma de árvore.

Podemos considerar que a penalização geométrica é uma extensão para métodos de

detecção de clusters irregulares se interpretarmos que o scan circular também aplica uma

penalização que é intŕınseca ao método. Sob esse ponto de vista, a penalização exercida

sobre os clusters não-circulares no método scan circular é alt́ıssima. De fato, é como se

no scan circular a função LLR fosse multiplicada por 1 caso o cluster seja circular, e

por zero caso contrário. Nesse sentido, o que a penalização geométrica faz é relaxar a

penalização aplicada pelo scan circular aos clusters irregulares.

17

Caṕıtulo 3.

Algoritmo Genético para detecção de

clusters

Neste caṕıtulo iremos descrever o método de detecção empregado nesta tese de douto-

rado. O método consiste de um algoritmo genético (AG) desenvolvido especificamente

para o problema de detecção de clusters. Os operadores desse AG foram desenvolvidos

especificamente para esse problema e foram propostos em Duczmal et al. (2007). Nesta

tese foi feita uma extensão multi-objetivo para esse AG e sua estrutura foi alterada de

forma a se assemelhar à estrutura de um dos algoritmos mais utilizados atualmente: o

NSGA-II (Deb et al., 2002).

3.1. Aspectos estruturais

Uma forma simples de representar o mapa em estudo é através de um grafo.

Definição 2 (Grafo) Um grafo G é um par G = (V,A), onde V ={v1, v2, ..., vn} é oconjunto de seus vértices e A é o conjunto de todas as arestas ai,j, onde vi e vj são

adjacentes, com vi, vj ∈ V .

Associamos um vértice vk, k = 1, ..., n, a cada um dos n centróides e, portanto,cada vértice está associado a uma região. Se duas regiões i e j têm uma fronteira em

19

comum1, então os vértices vi e vj correspondentes são adjacentes e, portanto, ligados

por uma aresta ai,j. A Figura 3.1 mostra um exemplo de mapa e seu respectivo grafo

associado. A representação do mapa através de um grafo apresenta algumas vantagens

sobre outros tipos de estruturas. Conceitos de caminhos e conexidade estão bem definidos

para estruturas de grafos. Além disso são conhecidos vários algoritmos de manipulação

e busca eficientes sobre essas estruturas.

(a) (b)

Figura 3.1.: (a) Um mapa dividido em regiões e (b) o grafo associado.

Uma caracteŕıstica fundamental de toda solução-candidata é que ela deve ser conexa.

Para entender o que é um grafo conexo, precisamos do conceito de caminho.

Definição 3 (Caminho) Dois vértices vi e vj estão conectados por um caminho se

existe uma sequência de p vértices vl1 , vl2 , ..., vlp tal que vi = vl1, vj = vlp e as arestasalk,lk+1 ∈ A, k = 1, ..., p − 1.

Intuitivamente, existe um caminho entre dois vértices se é possivel partir de um deles

e chegar ao outro passando somente pelas arestas existentes no grafo (e pelos vértices

intermediários). Um grafo é conexo se qualquer par de vértices distintos vi e vj está

conectado por um caminho. Assumimos que o mapa em estudo gera um grafo conexo,

isto é, para duas regiões quaisquer Ri e Rj é sempre posśıvel ir de Ri a Rj passando

pelas fronteiras das regiões do mapa.

1Por fronteira em comum entende-se que haja alguma ligação entre as regiões. Uma ilha, por exemplo,terá uma fronteira em comum com uma região continental caso haja uma ponte, um túnel ou umalinha hidroviária entre elas.

20

Dado um conjunto V1 ⊂ V diremos que o grafo G1 = (V1,A1) é um subgrafo deG = (V,A) induzido por V1 se A1 ⊂ A é o conjunto de todas as arestas de A com ambasas extremidades em V1. Logo, o mapa todo é um grafo conexo e a cada zona corresponde

um subgrafo conexo desse grafo, induzido2 pelas regiões correspondentes. Os subgrafos

G1 = (V1,A1) e G2 = (V2,A2) de G são vizinhos se o conjunto (V1 ∪V2)− (V1 ∩V2) possuiexatamente um elemento. Por simplificação, usaremos a interseção G1∩G2 para designarV1 ∩ V2. A Figura 3.2 mostra exemplos de zonas vizinhas.

(1) (2)

(3) (4)

Figura 3.2.: As zonas 2, 3 e 4 são vizinhas da zona 1, mas não são vizinhas umas das outras.

2A definição de subgrafo induzido é mais forte que a de subgrafo. Em um subgrafo G1 = (V1,A1) nãonecessariamente todas as arestas de A com ambas as extremidades em vértices de V1 precisam estarem A1. No entanto, como estamos interessados apenas em subgrafos induzidos, abandonamos essacaracterização e nos referimos às soluções apenas por subgrafos, muito embora todas as soluçõessejam, na verdade, subgrafos induzidos.

21

3.2. O Algoritmo Genético

A evolução natural dos seres vivos pode ser considerada um processo de otimização. De

fato, se indiv́ıduos que são mais bem adaptados sobrevivem, ao passo que indiv́ıduos

menos adaptados tendem a desaparecer, espera-se que, após algumas gerações, a popu-

lação seja composta por indiv́ıduos que são, em geral, melhores que os das primeiras

gerações. É essa mesma idéia que está por trás de um algoritmo genético. Ele tenta

simular os mecanismos de variação aleatória e de seleção adaptativa da evolução natu-

ral. Os mecanismos (ou operadores genéticos) que constituem a base de um algoritmo

genético são:

1. Um operador de cruzamento, que gera novos indiv́ıduos a partir da combinação da

informação contida em dois ou mais indiv́ıduos;

2. Um operador de mutação, que utiliza a informação contida em um indiv́ıduo para,

estocasticamente, gerar outro indiv́ıduo;

3. Um operador de seleção, que decide se um indiv́ıduo terá a oportunidade de gerar

descendentes para a próxima geração, baseado em sua aptidão.

Os operadores de cruzamento e mutação têm o objetivo de fazer uma “busca local”.

No entanto, o primeiro faz uma busca entre dois ou mais indiv́ıduos ao passo que o

segundo faz uma busca na vizinhança de um único indiv́ıduo. Já o operador de seleção

dá uma “direção” à busca. Muitas vezes esses operadores carregam algum componente

estocástico, fazendo com que execuções consecutivas atinjam soluções diferentes.

Partindo de uma população inicial, constitúıda de soluções-tentativas, os algoritmos

genéticos vão formando uma sequência de gerações. A cada iteração os operadores

genéticos são aplicados à população corrente, e uma nova população é obtida. Essa

estrutura faz com que os algoritmos genéticos sejam bastante robustos, no sentido de que

não há necessidade de se fazer nenhuma suposição de diferenciabilidade, continuidade,

convexidade ou unimodalidade da função a ser otimizada. Além disso, a função pode ser

definida em espaços cont́ınuos ou discretos (como no caso do estudo apresentado nessa

tese). A única suposição que se espera ser válida a respeito da função objetivo a ser

otimizada é que ela apresente uma tendência global em seu comportamento, e o desafio é

fazer com que o algoritmo consiga captar essa tendência e“aprender”onde deve procurar

as soluções.

22

Há um grande número de algoritmos genéticos conhecidos e o número de algoritmos

posśıveis pode ser bastante grande, já que cada operador genético pode ser implementado

de várias formas diferentes bem como dispostos em estruturas diferentes. No entanto

alguns algoritmos podem ser bem mais eficientes que outros sob o ponto de vista com-

putacional (Takahashi et al., 2003). Em particular, para problemas de natureza discreta

sabe-se que o emprego de operadores de cruzamento e mutação espećıficos pode ser bem

mais eficiente do que operadores genéricos que não levam em conta a estrutura espećıfica

do problema. O algoritmo genético proposto nesta tese de doutorado foi desenvolvido

com operadores espećıficos, que exploram a estrutura do problema de se encontrar o

cluster mais verosśımil, como veremos adiante.

3.2.1. Geração da população inicial

É importante que a população inicial seja capaz de captar as informações do mapa como

um todo. Não há razão para iniciarmos o algoritmo com os indiv́ıduos concentrados

em apenas uma parte do mapa, mesmo porque um cluster só pode ser identificado se

possuir valor de LLR discrepante das demais zonas, o que nos obriga a ter um mı́nimo

de conhecimento sobre zonas espalhadas pelo mapa. Por esse motivo a população inicial

deve ser constitúıda por subgrafos que estejam distribúıdos de forma bastante homogênea

dentro do mapa.

Assim, uma forma de gerar os indiv́ıduos da população inicial é, a partir de cada

vértice vi do grafo que representa todo o mapa, gerar um subgrafo conexo Gi. Aqui,

usamos a idéia de um algoritmo guloso para gerar esses Gi’s. Considere o grafo Gi0

formado apenas pelo vértice vi. Escolha dentre os grafos vizinhos de Gi0 o grafo Gi1 cuja

zona z1 correspondente possua maior valor de LLR. Depois, escolha o vizinho Gi2 de

Gi1 cuja zona z2 correspondente possua maior valor de LLR, e assim sucessivamente, até

encontrar o grafo Gin=Gi cuja zona ẑ correspondente possui valor de LLR maior que

todos os seus vizinhos, ou que tenha um número máximo de vértices pré-estabelecido.

A cada passo, avaliamos todos os vizinhos do indiv́ıduo atual (isto é, cada subgrafo que

é formado pelos vértices do indiv́ıduo atual, exceto um deles, e cada subgrafo formado

pelos vértices do indiv́ıduo atual mais alguma região vizinha). Na Figura 3.3 é posśıvel

ver a formação de um indiv́ıduo a partir de uma única região inicial.

23

Figura 3.3.: Geração de um indiv́ıduo via algoritmo guloso.

Repetindo esse procedimento a partir de cada um dos N vértices teremos, ao final,

uma população de N zonas, cada uma obtida a partir de um vértice através dessa

estratégia gulosa. É importante notar que este procedimento por si só, apesar de ser

uma estratégia de otimização, em geral não encontra a solução ótima. Os indiv́ıduos

obtidos por algoritmos gulosos geralmente encontram soluções locais pois não levam em

conta todo o espaço onde a função a ser otimizada está definida. Eventualmente, alguma

dessas soluções locais pode coincidir com a solução global, mas não há garantia de que

isso vá acontecer.

3.2.2. O operador de cruzamento

Como foi dito anteriormente, o objetivo do cruzamento é gerar novos indiv́ıduos, denomi-

nados filhos, a partir da combinação das caracteŕısticas de outros elementos, tipicamente

dois, denominados pais. Como os filhos reúnem caracteristicas de ambos os pais, é na-

tural imaginar que ele se encontra em algum ponto do “caminho” que os une. Alguns

estarão eventualmente mais próximos de um dos pais do que de outro, mas espera-se que

cada filho carregue consigo pelo menos uma pequena quantidade de caracteŕısticas de

cada um dos pais. Em problemas de variáveis cont́ınuas é comum, por exemplo, a geração

de filhos que estão no segmento de reta (o caminho mais curto, considerando a distância

24

Euclideana) que liga os dois pais. Num contexto de variáveis discretas, porém, o conceito

de caminho entre soluções não está, na maioria das vezes, definido implicitamente ou

intuitivamente, pela ausência da noção de vizinhança. Muitas vezes é necessário que se

defina uma métrica adequada à natureza do problema, para que se possa trabalhar com

o conceito de vizinhança. A partir dáı é que será posśıvel definir um caminho partindo

de um pai, saltando de um indiv́ıduo para um de seus vizinhos, e assim sucessivamente,

até que se alcance o outro pai. Nesse sentido, a noção de vizinhança descrita na seção

3.1 será aplicada. O objetivo do nosso operador de cruzamento é, então, obter uma

sequência de indiv́ıduos que se encontram no caminho entre dois subgrafos pais. Para

isso seguimos o procedimento descrito a seguir.

Dados dois subgrafos A e B, tais que A ∩ B ≠ ∅, chamados pais, sejam C = A ∩ B eD o maior subgrafo conexo cujos vértices estão em C, ou seja, D é o maior subconjunto

conexo dos vértices que formam o conjunto C. Atribuiremos um ńıvel para cada vértice

do pai A. Cada um dos nd vértices de D (que também são vértices de A) recebe o ńıvel

zero. Escolhemos aleatoriamente um vértice v1 adjacente a qualquer vértice de A0 = D,com v1 ∈ A − A0, e a ele associamos o ńıvel um. Depois, escolhemos aleatoriamenteum vértice v2 adjacente a qualquer vértice de A1 = D ∪ {v1}, com v2 ∈ A − A1, e aele associamos o ńıvel 2. No i-ésimo passo, escolhemos aleatoriamente um vértice vi

adjacente a qualquer vértice de Ai−1 = D ∪{v1, v2, ..., vi−1}, com vi ∈ A−Ai−1. Repetimosesse passo até que todos os na vértices de A−D tenham sido escolhidos e tenham recebidoseus respectivos ńıveis (veja o exemplo de atribuição de ńıveis na Figura 3.4, no meio).

Note que a escolha dos ńıveis não é única.

Os na vértices do pai A mais o nó virtual r (formado pela fusão dos vértices no

conjunto D), juntamente com os segmentos orientados (vj , vk), onde vk foi escolhidocomo adjacente a vj no k-ésimo passo (j < k), mais os segmentos orientados (r, vk), ondevk é adjacente ao conjunto D, formam a árvore TA (veja Figura 3.5) que tem a seguinte

propriedade:

Lema 1 Para cada vértice vi ∈ (A −D) existe um caminho do nó r até o vértice vi queconsiste apenas de vértices pertencentes ao conjunto {v1, ..., vi−1}.

Demonstração: Siga o caminho orientado na árvore TA, de r até vi.∎

25

a

b

c

d

e

fg

h

i0

1

4

2

3

−1−2

−3

−4

4

1 1 1 1

00

0

0 00

2 2 2

3 3

−1 −1 −1 −1−2 −2 −2

−3

−4

−3

1

2

3

4

−1 −2−3

−4

Figura 3.4.: Os pais {a, b, c, d, e} e {c, f, g, h, i} dentro do mapa (acima, à esquerda) têm aregião c em comum. A numeração dos ńıveis exemplificada (no meio, acima)gera os filhos {b, c, d, e, g}, {b, c, d, f, g} e {b, c, f, g, h} (apontados com setas pon-tilhadas). {a, b, c, d, e} e {c, f, g, h, i} (apontados com setas sólidas) são idênticosa seus pais, e, portanto, não são filhos. Outra numeração (dentre as váriasposśıveis) é exemplificada acima, à direita.

O processo descrito para determinação dos ńıveis dos vértices do pai A é feito também

para os nb vértices de B − D, porém usando ńıveis negativos ao invés de positivos. SeC − D ≠ ∅ então os vértices y ∈ C − D estão associados a dois ńıveis: um positivo e umnegativo (ver Figura 3.6).

A partir dáı contrúımos os filhos de A e B. Os ńıveis dos vértices do pai A são

{0, 1, 2, 3, ..., na} e do pai B {0, −1, −2, −3, ..., −nb}. Suponha, sem perda degeneralidade, que na ≥ nb. Então cada filho de A e B é formado pelos vértices associadosaos ńıveis de cada uma das seguintes sequências, formadas a partir do pai A e em cada

passo, retirando o vértice de ńıvel mais afastado de zero do pai A (ou seja, o mais

positivo) e adicionando o vértice de ńıvel mais próximo de zero do pai B (ou seja, o

menos negativo):

26

r r

TA

TB

Figura 3.5.: Árvores TA e TB .

{na − 1, ..., 1, 0, −1}{na − 2, ..., 1, 0, −1, −2}

⋮{na − nb, ..., 1, 0, −1, −2, ..., −nb}

{na − nb − 1, ..., 1, 0, −1, −2, ..., −nb}⋮

{2, 1, 0, −1, −2, ..., −nb}{1, 0, −1, −2, ..., −nb}

(3.1)

Se alguma sequência tem dois ńıveis correspondentes ao mesmo vértice (um positivo e

outro negativo para vértices em C−D), então basta levar em conta apenas um dos ńıveis.27

A cada vértice retirado ou adicionado saltamos de um grafo para seu vizinho. Como

os filhos sempre são obtidos retirando e adicionando um vértice, o conjunto de filhos

obtido no final constitui um caminho formado por passos de tamanho dois3. O próximo

resultado representa uma grande vantagem desse processo de cruzamento.

Lema 2 Os filhos de A e B gerados pelas sequências (3.1) são conexos.

Demonstração: Basta aplicar o lema 1 a cada vértice de cada filho e verificar que existe

um caminho daquele vértice ao nó r.∎

O fato de a transição entre a geração de um filho e outro ser apenas a retirada de

um vértice e a adição de outro faz com que a avaliação da verossimilhança seja muito

rápida: basta adicionar e subtrair a população e o número de casos das respectivas regiões

adicionada e retirada da zona anterior. Além disso, o lema 2 garante que não precisamos

verificar se os filhos gerados pelos pais A e B são conexos e, portanto, fact́ıveis.

A idéia por trás dessa operação é que os filhos formam uma transição suave entre os

pais A e B. Note que o primeiro filho se parece bastante com o pai A e que o último se

parece bastante com o pai B.

Outro exemplo de cruzamento é mostrado na Figura 3.7. Nesse caso o cruzamento é

feito entre um pai bastante alongado A e outro pai bastante compacto B.

A cada geração, o algoritmo genético faz várias tentativas de cruzamento, uma vez

que o cruzamento só é posśıvel caso haja interseção não-vazia entre os pais. Essas

tentativas cessam caso ele atinja o número máximo ctmax de cruzamentos tentados ou

cbsmax de cruzamentos bem sucedidos.

3.2.3. O operador de mutação

Operar uma mutação em um indiv́ıduo é simplesmente substitúı-lo por um de seus

vizinhos, aleatoriamente. Em outras palavras, um subgrafo que sofre uma mutação

3Obviamente podeŕıamos trabalhar com passos de tamanho 1, ou mesmo outros tamanhos. Essaescolha levou em conta que (1) a geração de todos os filhos pode nos conduzir a um número dema-siadamente grande de soluções, consumindo muito tempo e (2) a avaliação incremental permite queavaliemos mais de dois filhos, sem aumento significativo do tempo. A escolha de passos de tamanhodois parece ser um bom compromisso entre tempo e número de soluções avaliadas.

28

a

1

b

cd

e

fg

hi

jk

l

1

0

0

2/−7

3

−1

−2 −3−4

−5−6

−8

1

0

0

−1

2

0

0

1−1

−2 0

0−2

−1

−30

0−3

−1

−2−4

0

0

0

0

0

0

−1

−1

−1

−2

−2

−2

−3

−3

−3

−4

−4

−4

−5

−5

−5−6

−7

−6

Figura 3.6.: Os pais A = {a, b, c, d, e} e B = {b, c, e, f, g, h, i, j, k, l} têm a parte em comumC = {b, c, e}. O maior conjunto conexo é escolhido D = {b, c}. Observe que ovértice e, pertencente ao conjunto C−D, recebe um ńıvel positivo (2) e negativo(-7).

perde um de seus vértices, ou recebe um novo vértice, desde que permaneça conexo.

A escolha de se retirar ou acrescentar um vértice é aleatória, bem como a escolha do

vértice a ser retirado ou acrescentado. Note que a mutação constitui uma espécie de

busca aleatória, no sentido de que um indiv́ıduo que sofre uma mutação ao longo de

algumas iterações segue um processo Markoviano.

A mutação é uma operação computacionalmente cara, caso o novo indiv́ıduo seja

obtido retirando-se uma região, uma vez que é necessário verificar a conexidade do

subgrafo obtido pelo operador. Porém, em geral a mutação é aplicada apenas em uma

pequena fração da população.

29

a

b

c

d

e

f

g

h

i

j

1

2

0

0

3−1

−2−3

−4−5

0

0

0

0

0

0

0

0

0

0

0

0

1 1 1

2 2

3−1 −1 −1 −1 −1

−2 −2 −2 −2−3 −3 −3

−4 −4−5

Figura 3.7.: Cruzamento entre um pai alongado A = {a, b, c, d, e} e outro compacto B ={b, c, f, g, h, i, j}.

3.2.4. O operador de seleção

Antes de operar cruzamento e mutação, uma lista L de N indiv́ıduos é escolhida a partir

da população corrente P . Essa lista é obtida fazendo-se N torneios binários. Cada

torneio é feito sorteando-se dois indiv́ıduos aleatoriamente entre os N indiv́ıduos da

população corrente e comparando-os. Aquele com maior aptidão é adicionado à lista L.

A cada passo o sorteio é feito com reposição. Assim, um indiv́ıduo com alta aptidão tem

maior probabilidade de ser colocado na lista L mais de uma vez, enquanto os indiv́ıduos

com menor aptidão têm alta probabilidade de não aparecerem nenhuma vez na lista

L. Os indiv́ıduos da lista L são então escolhidos aleatoriamente aos pares para sofrer

cruzamento, até que se atinja o número máximo ctmax de cruzamentos tentados ou cbsmax

de cruzamentos bem sucedidos.

Após operar o cruzamento os filhos são adicionados em uma subpopulação Q, a qual

ainda sofre mutação. A partir dáı é necessário decidir, dentre os pais e os filhos, quais

30

os N indiv́ıduos que formarão a próxima população. Essa escolha deve ser baseada na

aptidão de cada indiv́ıduo. Assim, ordenamos a população formada por P ∪Q segundo aaptidão dos indiv́ıduos e escolhemos, deterministicamente, os N melhores. Esses indiv́ı-

duos formarão a próxima população. Esse critério é, como veremos na seção 3.3.2, o caso

particular do operador de seleção do algoritmo NSGA-II para problemas com apenas um

objetivo.

3.2.5. Parâmetros e Estrutura do Algoritmo

Para que se consiga chegar a um desempenho satisfatório, o algoritmo genético deve

ser ajustado através de alguns parâmetros que determinam seu funcionamento. Esses

parâmetros são:

� N : tamanho da população

� pm: probabilidade de mutação

� cbsmax: número máximo de cruzamentos bem sucedidos

� ctmax: número máximo de cruzamentos tentados

� gmax: número de gerações, utilizado como critério de parada do algoritmo

Especificamente para o algoritmo descrito nessa tese o tamanho da população N

está implicitamente definido como o número de regiões do mapa. O procedimento de

geração da população inicial gera um indiv́ıduo partindo de cada uma das N regiões. A

probabilidade de mutação pm utilizada ne maioria dos algoritmos genéticos está próxima

de 0,05. No caso do nosso algoritmo, a mutação pode não ser posśıvel, já que se a

escolha for por retirar uma região pode não haver nenhuma região pasśıvel de ser retirada

sem tornar o indiv́ıduo desconexo. Por esse motivo, escolhemos uma probabilidade

maior que 0,05. A taxa de mutação foi definida como 0,1. Um valor acima de 0,1

faria com que a busca se tornasse demasiadamente aleatória e o algoritmo se mostrou

eficiente com esse parâmetro. Para o número máximo de cruzamentos bem sucedidos

cbsmax optamos por utilizar o número de cruzamentos em um algoritmo padrão, que é

de N/2 cruzamentos. Com esse número de cruzamentos, um algoritmo normal (comum cruzamento que gerasse dois indiv́ıduos por cruzamento) obteria N novos indiv́ıduos

filhos. No nosso algoritmo, caso esse número de cruzamentos seja atingido, em geral

31

teremos mais que N indiv́ıduos filhos. Para isso, verificamos para o nosso problema

que com um número de tentativas de cruzamento ctmax = 2N raramente não atingimosN/2 cruzamentos bem sucedidos. Por fim, como critério de parada utilizamos o númeromáximo de gerações gmax que foi fixado em 40. Esse número de gerações nos pareceu

suficiente para que a população do algoritmo genético convergisse, na maioria das vezes.

Com esse conjunto de parâmetros, a estrutura do algoritmo genético pode ser descrita

da seguinte forma:

P0 ← GULOSO(N);f0 ← AVALIA(P0);i ← 0;while i < gmax do

L ← TORNEIO(Pi);ct ← 0;cbs ← 0;Qi ← ∅;while (ct ≤ ctmax) & (cbs ≤ cbsmax) do

a ← RANDi(N);b ← RANDi(N);if L(a) ∩L(b) ≠ ∅ then

Qi ← Qi∪ (CRUZAM(L(a),L(b)));cbs ← cbs + 1;

endct ← ct + 1;

endMi ← SIZE(Qi);for j = 1, ...,Mi do

p ← RAND();if p < pmut then

Qi(j) ← MUT(Qi(j));end

endPi ← SORT(Pi ∪Qi);Pi ← Pi(1...N) g ← g + 1;

end

Algoritmo 1: Algoritmo genético mono-objetivo

No algoritmo 1 aparecem as seguintes funções:

32

� GULOSO(N): gera N indiv́ıduos a partir das N regiões do mapa através de um

procedimento guloso.

� AVALIA(P ): avalia a população P segundo o critério a ser otimizado.

� TORNEIO(P ): faz N torneios binários com indiv́ıduos escolhidos aleatoriamente,

com reposição, a partir da população P .

� RANDi(N): retorna um número aleatório inteiro de 1 a N .

� CRUZAM(L(a),L(b)): opera o cruzamento entre os indiv́ıduos L(A) e L(b), re-tornando todos os filhos obtidos avaliados.

� SIZE(P): retorna o número de indiv́ıduos da população P .

� RAND(): retorna um número aleatório entre 0 e 1.

� MUT(P (i)): opera mutação no indiv́ıduo P (i) e o avalia.� SORT(P ): ordena os indiv́ıduos da população P de acordo com a aptidão.

3.3. Abordagem multiobjetivo

Nesta seção iremos introduzir alguns conceitos sobre otimização multiobjetivo e apre-

sentar a versão multiobjetivo do algoritmo genético descrito anteriormente. Como o

problema tratado nesta tese de doutorado é um problema de maximização, nossas defi-

nições levarão em conta que o problema de otimização a ser resolvido é um problema de

maximização, ao contrário do que é feito normalmente na literatura.

3.3.1. Otimização multiobjetivo

Em muitos problemas reais de otimização há a necessidade de se otimizar simultane-

amente duas ou mais funções-objetivo f1, f2, ..., fn (ou uma função-objetivo vetorial

f = (f1, f2, ..., fn)) sujeitas possivelmente às restrições gi(x) ≤ 0, i = 1, ..., r. Assim,o problema de otimização multiobjetivo pode ser escrito na forma

33

maxx

f(x) = (f1(x), f2(x), ..., fn(x))s.a. gi(x) ≤ 0, i = 1, ..., r

Na maioria das vezes os objetivos f1, f2, ..., fn são conflitantes, no sentido de que

dificilmente uma mesma escolha de parâmetros x otimiza todos os objetivos simultane-

amente. Por essa razão a busca pela melhor solução em um problema com mais de um

objetivo está intimamente ligada ao conceito de dominância, dado a seguir.

Definição 4 (Dominância) Seja f(x) = (f1(x), ..., fn(x)) uma função definida em umespaço X. Um ponto x1 ∈ X domina outro ponto x2 ∈ X (denota-se x1 ≻ x2) se fi(x1) ≥fi(x2), i = 1, ..., n e se existe pelo menos um ı́ndice k ∈ {1, ..., n} tal que fk(x1) > fk(x2).

Em outras palavras, um ponto x1 domina o ponto x2 se a avaliação de x1 for melhor

que a avaliação de x2 em um objetivo e não for pior em nenhum outro objetivo. Caso o

problema seja de minimização, a definição para x1 ≺ x2 vale trocando os sinais ≥ e > por≤ e f2(x2), portanto x1 ≻ x2. Na Figura 3.8(c)os pontos x1 e x2 são tais que f1(x1) > f1(x2) e f2(x1) < f2(x2), de modo que x1 nãodomina x2, nem x2 domina x1. Neste caso dizemos que x1 e x2 são incomparáveis, ou

indiferentes. O śımbolo “⪰” denotará “domina ou é indiferente”.Com o conceito de dominância podemos agora definir o objeto essencial na resolução

de problemas de otimização multiobjetivo, a solução Pareto-ótima.

Definição 5 (Solução Pareto-ótima) Diz-se que uma solução x∗ ∈ X é Pareto-ótimase não existe x ∈ X tal que x domina x∗.

Note que dizer que uma solução é Pareto-ótima não significa dizer que ela é melhor

que todas as (ou que algumas das) outras soluções, mas que ela não é pior que nenhuma

outra. Uma solução Pareto-ótima pode ainda ser chamada de solução não-dominada

34

f1

f 2

y1

y2

(a)

f1

f 2

y1

y2

(b)

f1

f 2

y1

y2

(c)

f1

f 2

(d)

Figura 3.8.: (a) x1 domina x2, pois f1(x1) > f1(x2) e f2(x1) > f2(x2); (b) x1 domina x2, poisf1(x1) = f1(x2) e f2(x1) > f2(x2); (c) x1 não domina x2, e x2 não domina x1pois f1(x1) > f1(x2) mas f2(x1) < f2(x2); (d) Pontos dominados (×) e conjuntode Pareto (●).

ou solução eficiente. O conjunto Pareto-ótimo é formado então por todas as soluções

Pareto-ótimas. Assim, ao contrário do que ocorre em problemas de otimização com

um único objetivo, aqui temos um conjunto de soluções que são, em um certo sentido,

ótimas. A Figura 3.8(d) apresenta um exemplo com pontos dominados (×) e os pontosque formam o conjunto de Pareto (●).

O algoritmo genético descrito neste caṕıtulo foi modificado para lidar simultanea-

mente com as duas grandezas: a compacidade K (seção 2.3) e a estat́ıstica espacial scan

(seção 2.1). A compacidade K não será mais utilizada como uma penalização geométrica,

mas como uma nova função objetivo.

35

3.3.2. Algoritmo genético multiobjetivo

Há várias formas de se tratar um problema multiobjetivo de maneira a se obter o con-

junto de Pareto. Os métodos, em geral, transformam o problema multiobjetivo em vários

sub-problemas mono-objetivo, de forma que a solução de cada sub-problema é um ponto

do conjunto de Pareto. Os algoritmos genéticos constituem um método particularmente

eficiente para lidar com otimização multiobjetivo, uma vez que trabalham com uma

população de soluções-tentativas e, assim, podem encontrar o conjunto de soluções efi-

cientes em uma única execução (Fonseca & Fleming, 1995). Isso é realizado fazendo

com que a população toda vá convergindo geração a geração em direção ao conjunto

de Pareto, de modo que a aproximação do conjunto de Pareto é obtida simplesmente

tomando todos os indiv́ıduos não-dominados encontradas em alguma altura da execução

do algoritmo. Exemplos de algoritmos genéticos desenvolvidos para aplicações diferen-

tes podem ser encontrados em Ramos et al. (2003), Takahashi et al. (2004) e Carrano

et al. (2006). Os trabalhos Takahashi et al. (2004) e Carrano et al. (2006) apresentam

situações onde o conjunto de Pareto pode ser empregado para a análise a posteriori do

problema de uma maneira que nenhum algoritmo mono-objetivo poderia fazer.

As diferenças entre os AG’s mono e multi-objetivo são muito pequenas. Os operadores

de cruzamento e de mutação funcionam da mesma maneira, sem a necessidade de nenhum

tipo de adaptação. A alteração fundamental se dá no operador de seleção, uma vez que

agora a seleção deve ser feita levando-se em conta não uma, mas duas ou mais funções-

objetivo.

No caso espećıfico do algoritmo desenvolvido nesta tese de doutorado a construção da

população inicial e os operadores de cruzamento e mutação são idênticos aos empregados

no algoritmo descrito no caṕıtulo 3. A diferença fica mesmo por conta da seleção que

foi adaptada de forma que o algoritmo se encaixasse na estrutura do NSGA-II. Para isso

vamos fazer uso de três procedimentos, descritos a seguir. A descrição detalhada desses

procedimentos encontra-se em Deb et al. (2002).

1. Ordenação por não-dominância (nondominated sorting): consiste em atribuir um

ńıvel a cada indiv́ıduo da população. Aos indiv́ıduos da primeira camada de solu-

ções não-dominadas é atribúıdo o ńıvel 1. O ńıvel 2 é atribúıdo àqueles presentes

na segunda camada de soluções não-dominadas, isto é, aqueles que são dominados

exclusivamente por indiv́ıduos do ńıvel 1, e assim sucessivamente.

36

2. Distância por ocupação (crowding distance): é baseada na soma das distâncias

entre um indiv́ıduo e seus vizinhos mais próximos em cada objetivo, sendo que os

objetivos são normalizados para o cálculo das distâncias.

3. Torneio binário (binary tournm

Documents

Deteçcão de clusters espaciais através de otimiza¸cão … · 2019. 11. 14. · Resumo Clusters espaciais irregulares ocorrem com frequência em estudos epidemiológicos,