Narrativ analyse -en historiefortelling om ISO-sertifisering

Local Convex Hull (Fadel et al., 2015) ´e uma t´ecnica de proje¸c˜ao local, criada espe- cialmente para trabalhar com espa¸cos esparsos de alta dimens˜ao.

Esta abordagem ´e constitu´ıda de trˆes passos principais, conforme ilustrado na Figura 3.9. O primeiro passo consiste em encontrar os k-vizinhos mais pr´oximos de cada instˆancia. Para realizar esta tarefa os autores empregaram uma estrat´egia baseada em agrupamentos, tal que o conjunto de dados ´e particionado em √n grupos balanceados usando bisecting K-means (Steinbach et al., 2000), em seguida encontrados seus medoides. Ent˜ao os c grupos vizinhos mais pr´oximos de cada grupo s˜ao computados. Desse modo, a busca pelos vizinhos mais pr´oximos de uma dada instˆancia leva em conta somente as instˆancias no mesmo grupo a que pertence e nos c grupos mais pr´oximos, representando uma boa aproxima¸c˜ao dos verdadeiros k-vizinhos mais pr´oximos, com a diferen¸ca de que esta opera¸c˜ao tem complexidade O(n√n) para √n grupos, enquanto que as abordagens convencionais apresentam complexidade quadr´atica O(n2_).

Figura 3.9: Passos principais da t´ecnica LoCH (Retirado de Fadel et al. (2015)).

O segundo passo, sele¸c˜ao e proje¸c˜ao de amostras representativas, utiliza os medoides dos agrupamentos encontrados no passo anterior como amostras representativas, visando representar melhor os dados. Portanto, o n´umero de amostras representativas empregado no processo ´e √n. Depois que as amostras s˜ao selecionadas, elas s˜ao projetadas para o novo espa¸co usando uma t´ecnica global que preserva tanto quanto poss´ıvel os relaciona- mentos de distˆancia, denominada Force Scheme (Tejada et al., 2003). O posicionamento das amostras representativas no espa¸co de proje¸c˜ao pelo Force tende a preservar relaciona- mentos globais de distˆancia, ao passo que os relacionamentos locais s˜ao estabelecidos por um processo iterativo, descrito a seguir.

A aproxima¸c˜ao pelo fecho convexo (terceiro passo), apoia-se na seguinte ideia: rela- cionamentos locais de distˆancia s˜ao preservados se cada ponto no espa¸co transformado ´e posicionado pr´oximo ao fecho convexo de seus vizinhos mais pr´oximos, assim, cada ponto projetado estar´a igualmente pr´oximo das instˆancias mais similares a ele.

Assumindo que xi ´e um ponto no espa¸co de alta dimens˜ao e yi a sua proje¸c˜ao no espa¸co de menor dimens˜ao p, ent˜ao uma posi¸c˜ao qualquer dentro do fecho convexo no

3.1 T´ecnicas de Proje¸c˜ao de Dados Multidimensionais 61 espa¸co p-dimensional, em fun¸c˜ao dos vizinhos de xi, indicado por Ni, pode ser obtida como: ˆ yi = X xj∈Ni αjyj, (3.27) com αj ≥ 0 e P

jαj = 1. Com o interesse de encontrar a posi¸c˜ao no espa¸co transformado que melhor preserva os relacionamentos de distˆancia entre xi e seus vizinhos Ni, os autores calculam αj com base nas distˆancias a partir do espa¸co de origem.

Partindo de uma certa posi¸c˜ao inicial, move-se cada ponto yi em dire¸c˜ao a ˆyi. Por´em, fazer yi igual a ˆyi, n˜ao garante que todos os pontos ser˜ao posicionados dentro do fecho convexo de seus vizinhos mais pr´oximos. A ideia ent˜ao, ´e mover y_i com base no vetor diretor ~v que vai da posi¸c˜ao atual do ponto at´e ˆyi, obtendo assim uma nova posi¸c˜ao ˜yi, isto ´e:

˜

yi = ˆyi+ γi ~v

k~vk, (3.28)

tal que γi ´e o valor que melhor preserva as distˆancias entre xi e as instˆancias em Ni. Por simplicidade, o c´alculo dos coeficientes αj e γi presentes nas Equa¸c˜oes (3.27) e (3.28), respectivamente, foram omitidos. Ver Fadel et al. (2015) para detalhes de como obtˆe-los. Em seguida, move-se iterativamente cada ponto yi em dire¸c˜ao a ˜yi at´e que nenhum movimento seja poss´ıvel ou o n´umero m´aximo de itera¸c˜oes seja atingido. Sendo yt

i a posi¸c˜ao de xi na t-´esima itera¸c˜ao, e lembrando que a posi¸c˜ao das instˆancias mudam a cada itera¸c˜ao, uma nova atualiza¸c˜ao pode ser calculada como:

yt

i = [1− ωi(t)]yti−1+ ωi(t) ˜yi, (3.29) onde ωi(t) varia entre [0; 1] e representa a liberdade de movimento que yi apresenta na itera¸c˜ao t, tal que maiores valores permitem movimentar mais yi. Este parˆametro ´e definido pelo usu´ario e usado para diminuir a quantidade de energia a cada itera¸c˜ao, ajudando a t´ecnica a estabilizar.

O Algoritmo 3.7 descreve os passos necess´arios para projetar um conjunto de dados de alta dimens˜ao X, usando a LoCH. A inicializa¸c˜ao de Y , indicada na Linha 1, pode ocorrer de dois modos: 1) aleatoriamente, ou 2) encontrando valores iniciais que aceleram a convergˆencia. No segundo caso, a Equa¸c˜ao (3.27) ´e usada para posicionar cada ponto xi considerando somente as amostras representativas que comp˜oem a lista de seus vizinhos mais pr´oximos Ni. Fadel et al. (2015) prop˜oem um segundo algoritmo para realizar esta opera¸c˜ao e inicializar Y .

Os autores provaram, experimentalmente, que o n´umero m´aximo de itera¸c˜oes para uma boa aproxima¸c˜ao pelo fecho convexo ´e em torno de √n, normalmente tornando-se est´avel antes desse valor.

Algoritmo 3.7 Local Convex Hull (LoCH)

Entrada: Conjunto de dados X =_{x1, x2, . . . , xn} e n´umero de vizinhos k. Sa´ıda: Conjunto de dados Y.

1: Y_{← Inicializa(X)}

2: Y =ˆ _{{ ˆ}y₁, ˆy₂, ..., ˆyn} // Equa¸c˜ao (3.27)

3: para todo xi ∈ X fa¸ca

4: Ni ← VizinhosMaisProximos(xi, k)

5: fim para

6: t_{← 1}

7: repita

8: para todo yi ∈ Y fa¸ca

9: y˜i = ˆyi+ γi ~ v

k~vk // Equa¸c˜ao (3.28)

10: fim para

11: para todo yi ∈ Y fa¸ca

12: yi = [1− ωi(t)]yi+ ωi(t) ˜yi // Equa¸c˜ao (3.29)

13: fim para

14: t_{← t + 1}

15: at´e t >√n ou nenhum movimento poss´ıvel

16: retorna Y

LoCH ´e uma t´ecnica de proje¸c˜ao predominantemente local, n˜ao linear, restrita a es- pa¸cos esparsos de alta dimens˜ao. Tem complexidade O(n√n), pode ser utilizada em aplica¸c˜oes interativas, sem se destacar neste sentido, j´a que requer √n amostras repre- sentativas, assim como outras t´ecnicas anteriores a ela. Mapear uma nova instˆancia iso- ladamente, ap´os a proje¸c˜ao inicial do conjunto de dados, implica refazer o c´alculo dos k-vizinhos mais pr´oximos de cada instˆancia (primeiro passo), o qual pode produzir dife- rentes layouts, dificultando seu uso de modo incremental.

As Figuras 3.10(a) e 3.10(b) foram extra´ıdas da LoCH. Nelas, os autores enfatizam que t´ecnicas globais apresentam melhores resultados em termos de preserva¸c˜ao de distˆancia (stress) e tempo computacional, quando comparadas a t´ecnicas locais, justificando o fato da LoCH n˜ao ser t˜ao eficaz neste sentido. Contudo, merece destaque neste experimento, o desempenho apresentado pela LAMP (Cap´ıtulo 4), mostrando ser uma das mais compe- titivas em termos de stress (Figura 3.10(a)) e eficiˆencia computacional (Figura 3.10(b)).

Experimentos como o da Figura 3.10, apresentado por Fadel et al. (2015), comprovam que a LAMP (Joia et al., 2011), desenvolvida no in´ıcio deste projeto de doutorado, ainda se mant´em como uma das t´ecnicas do estado da arte com respeito `a preserva¸c˜ao de distˆancias, al´em de apresentar baixo custo computacional.

As pr´oximas se¸c˜oes revisam t´ecnicas relacionadas `a identifica¸c˜ao de agrupamentos e uso de diferentes medidas de similaridade.