Import

Os m´etodos de detec¸c˜ao s˜ao utilizados para se encontrar o cluster que maximiza a estat´ıstica scan. Dado o espa¸co de busca a ser avaliado, sempre independente do m´etodo aplicado, alguma solu¸c˜ao ser´a encontrada, o cluster mais veross´ımil. Ou seja, essa solu¸c˜ao

ser´a a que, dentre todas as analisadas, apresentar a maior valor de Λ(z). Antes de podermos afirmar que essa solu¸c˜ao ´e um cluster, devemos lembrar que um cluster deve apresentar um n´umero anormal de casos, ou seja, devemos comparar o mapa estudado contra v´arios mapas aleat´orios.

No caso mono-objetivo, se fosse conhecida a distribui¸c˜ao de probabilidade da estat´ıstica de teste T sob a hip´otese de n˜ao existˆencia de cluster no mapa em estudo, poderia ser determinado um valor cr´ıtico, Tcritico, resolvendo P (T > Tcritico) = α, com

α sendo a probabilidade de que T supere o valor cr´ıtico Tcritico, chamado de n´ıvel de

significˆancia, tradicionalmente α = 0, 05. Assim, um valor de T abaixo de Tcritico pode

ocorrer por mero acaso 95% das vezes, mas um valor acima de Tcritico s´o acontece por acaso

com probabilidade menor que ou igual a 5% e, portanto, a solu¸c˜ao pode ser considerada um cluster. Essa probabilidade de que o valor observado da estat´ıstica de teste ocorra por mero acaso sob hip´otese nula ´e chamada de probabilidade de significˆancia do teste (p-valor). Se o p-valor de um cluster ´e menor que o n´ıvel de significˆancia α dizemos que a existˆencia daquele cluster ´e significativa ao n´ıvel α. Como, em princ´ıpio, essa distribui¸c˜ao de probabilidade ´e desconhecida, utiliza-se simula¸c˜oes de Monte Carlo (DWASS, 1957) para obter uma distribui¸c˜ao emp´ırica dos valores da estat´ıstica sob a hip´otese nula. Essas simula¸c˜oes s˜ao executadas v´arias vezes e os valores da estat´ıstica T obtidos s˜ao ordenados (o valor correspondente ao quantil de 95% ´e a estimativa do valor cr´ıtico a um n´ıvel de significˆancia de 5%). Dado o valor da estat´ıstica de teste dos casos observados, Tobs, a

estimativa de seu p-valor ´e nobs+1

n , em que nobs ´e n´umero de vezes de T sob a hip´otese nula

que s˜ao maiores que o valor de Tobs, em que n ´e o n´umero de simula¸c˜oes sob hip´otese nula.

Em abordagens de otimiza¸c˜ao multiobjetivo, de maneira an´aloga o c´alculo da significˆancia estat´ıstica dos clusters obtidos do mapa de casos observados ´e feita atrav´es da compara¸c˜ao com os clusters obtidos atrav´es de simula¸c˜oes de casos de v´arios mapas sob a hip´otese nula, geradas por meio de simula¸c˜oes de Monte Carlo. Sob a hip´otese nula, casos simulados s˜ao distribu´ıdos aleatoriamente ao longo do mapa em estudo conforme a distribui¸c˜ao de Poisson, de forma que cada regi˜ao receba, em m´edia, um n´umero de casos proporcional `a sua popula¸c˜ao. Com isso, a estat´ıstica de teste T ´e calculada para o conjunto Pareto e este procedimento ´e repetido n vezes (Em que n ´e o n´umero de simula¸c˜oes).

Em seguida, os conjuntos Pareto dessas simula¸c˜oes s˜ao agrupados, constituindo uma cole¸c˜ao de pontos definidos no espa¸co dos objetivos do problema ( ou seja, o valor da estat´ıstica Λ(z) e o valor da fun¸c˜ao de penaliza¸c˜ao P (z)). Ent˜ao nesse caso, devemos

encontrar uma curva cr´ıtica acima do qual consideramos que um cluster seja significativo. Essa curva cr´ıtica divide o plano em duas regi˜oes de maneira que um ponto do plano no espa¸co Λ(z) × P (z) ser´a considerado um cluster significativo se estiver acima dessa curva.

Can¸cado (2009) apresenta trˆes t´ecnicas utilizadas na estima¸c˜ao desta curva cr´ıtica, nos problemas de otimiza¸c˜ao multiobjetivo. Nesta disserta¸c˜ao adotou-se o conceito das fun¸c˜oes de aproveitamento (FONSECA; FONSECA; PAQUETE,2005) descrita na Se¸c˜ao

2.4.

2.4.1

Fun¸c˜oes de Aproveitamento

Considere um problema de otimiza¸c˜ao biobjetivo, com as fun¸c˜oes f1 e f2, e O

o conjunto das solu¸c˜oes n˜ao-dominadas definidas no espa¸co de objetivos de uma ´unica execu¸c˜ao do algoritmo (Veja a Figura 9). O conjunto O est´a associado a uma fronteira que divide o espa¸co de objetivos em duas regi˜oes R1 e R0. R1 ´e a regi˜ao de pontos dominados

por, ou iguais a, pelo menos, um ponto em O e R0 a regi˜ao dos pontos que n˜ao s˜ao

dominados por nenhum ponto em O. Uma solu¸c˜ao x que ´e dominada por pelo menos uma solu¸c˜ao de um determinado resultado O, ´e dita atingida por O. Na Figura 9, qualquer solu¸c˜ao localizada na regi˜ao R1 atingida por O.

f₁ f₂

R

R

Figura 9 – Fun¸c˜oes f1 e f2, e o conjunto O = {x1, x2, x3, x4} das solu¸c˜oes n˜ao-dominadas

Considere n execu¸c˜oes do algoritmo. Como cada execu¸c˜ao produz resultados dife- rentes podemos obter m´ultiplas fronteiras. Com isso, pode-se dividir o espa¸co objetivo em n + 1 tipos de regi˜oes de acordo com a frequˆencia com que estas regi˜oes s˜ao atingidas. Os limites dessas regi˜oes s˜ao denominadas fronteiras de aproveitamento. Estas frequˆencias s˜ao usadas para estimar a probabilidade de atingir um ponto no espa¸co de objetivos, quando um grande n´umero de execu¸c˜oes do algoritmo s˜ao realizados.

A fun¸c˜ao de aproveitamento avaliada em algum ponto O no espa¸co objetivo pode ser estimada pelos conjuntos de resultados O1,... ,On obtido atrav´es de n execu¸c˜oes

independentes do algoritmo, como:

An(O) = 1 n n X i=1 I(OiDO) (9)

Em que o s´ımbolo ”D” significa que Oi atingiu O e I ´e a fun¸c˜ao indicadora, assumindo o

valor 1 se OiDO, e 0 caso contr´ario.

No problema em estudo estamos interessados em estimar o p-valor das solu¸c˜oes n˜ao-dominadas de clusters candidatos representados por pontos (Λ(z), P (z)) no espa¸co objetivo, em que P (z) ´e uma fun¸c˜ao de penaliza¸c˜ao.

Na pr´atica, dado n conjuntos de resultados O1,... ,Onpode-se construir aproxima¸c˜oes

da isolinha de p-valor para cada p = i/(n+1), i = 1, ..., n atrav´es da estima¸c˜ao da fun¸c˜ao de aproveitamento An(O). Maiores detalhes podem ser visto em Fonseca, Fonseca e Paquete

(2005), Can¸cado et al. (2010). Esta ´e uma extens˜ao natural do conceito p-valor para problemas biobjetivo devido `a preserva¸c˜ao da dependˆencia entre os pontos dentro de uma mesma fronteira de Pareto, para todas as fronteiras de Pareto obtidas pela simula¸c˜ao de Monte Carlo.

3 Algoritmo Proposto

Este cap´ıtulo tem como objetivo apresentar o algoritmo proposto nesta disserta¸c˜ao para a aplica¸c˜ao ao problema de detec¸c˜ao e inferˆencia de clusters espaciais irregulares. Utilizou-se como base a t´ecnica de computa¸c˜ao evolucion´aria Particle Swarm Optimization adotando uma abordagem de otimiza¸c˜ao multiobjetivo visando maximizar a estat´ıstica de teste e minimizar a fun¸c˜ao de penaliza¸c˜ao por dispers˜ao. As principais estruturas e etapas do algoritmo s˜ao apresentadas ao longo das se¸c˜oes deste cap´ıtulo.