Fagenes  historie  og  inntakspraksis

No processo descrito para a construção de um grafo K -associado, note que diferentes grafos podem ser gerados usando diferentes valores de K, e que, de acordo com a pureza, alguns dos grafos podem conter melhores componentes do que outros. No geral, raramente um grafo obtido com um único valor de K possuirá os melhores componentes dentre todos os possíveis componentes gerados, considerando os diversos valores possíveis para K. O que se observa é que, diferentes regiões do espaço de dados são melhor representadas por diferentes componentes - gerados com diferentes valores de K. Análogo à classificação realizada pelo algoritmo KNN, onde o valor de K que resulta em melhor desempenho de classificação varia de acordo com o domínio de dados. Consequentemente, uma ideia intuitiva é obter um grafo com a melhor organização dos vértices em componentes e maximizar a pureza sem depender de um único valor de K. Dessa forma, o componente

Cαtem seu próprio Kα, que é o valor de K para o qual a pureza do componente é máxima.

Portanto, para obter o grafo ótimo, aumenta-se o valor de K enquanto os melhores componentes, até então encontrados, são armazenados. Para comparar componentes obti- dos com valores diferentes de K, considere os grafos, K-associado e (K + q)-associado, para qualquer inteiro q > 1. Sejam α e β índices de componentes, um componente C(K+q)

β

pertencente ao grafo (K + q)-associado, com pureza Φ(K+q)

β , deve ser comparado, em re-

lação à pureza, a todo componente Cα, cuja pureza é Φ(K)α , de forma que, para que o

componente C(K+q)

β seja considerado mais puro que os componentes Cα(K) ⊆ C

(K+q)

β , a

Equação (3.3) deve ser satisfeita.

Φ(K+q)_{β ≥ Φ}(K)_α para todo C_α(K) _{⊆ Cβ}(K+q) (3.3) O grafo ótimo é a estrutura final e única obtida por meio do aumento de K e pela seleção dos melhores componentes ao longo de diferentes valores de K, de acordo com a

Equação (3.3). No Algoritmo 3.2 é detalhado a construção do grafo K -associado ótimo tendo como entrada um conjunto de treinamento. Note que este usa o Algoritmo 3.1 para a construção dos grafos K-associados. O grafo ótimo será usado na classificação de novos dados, como será exposto na próxima seção.

Algoritmo 3.2 Algoritmo da construção do grafo K -associado ótimo (KAOG)

Entrada: X =_{(xi, yi), ..., (xN, yN)} {Conjunto de dados vetoriais com classe associada}

Saída: G(ot)_{= {(G}′_{(V, E); Φ)}; {Grafo com os melhores componentes}}

K_{⇐ 1} G(ot) ⇐ Kac(X, K) repita ultimaT axa_{⇐ G}(K)_/K K_{⇐ K + 1} G(K)_{⇐ Kac(X, K)}

para todoC_β(K)⊂ G(K) _faça

se(Φ(K)_{β ≥ Φ}(ot)α para todo Cα(ot)⊆ C_β(K)) então

G(ot) ⇐ G(ot) − ∪ Cα(ot)⊆C (K) β C_α(ot) G(ot)_{⇐ G}(ot)_{∪ {C}(K) β } fim se fim para

até que_hG(K)_{i/K < ultimaT axa;}

retorne G(ot)

No Algoritmo 3.2, a construção do grafo ótimo é detalhada. O algoritmo tem como única entrada o conjunto de treinamento, que é representado por um conjunto de vértices, cada qual com uma classe associada. O grafo ótimo, notado por G(ot)_{, pode ser visto como}

uma lista dos melhores componentes encontrados durante este processo. Inicialmente a lista de componentes G(ot) _{é inicializada com o grafo 1-associado (K = 1), pois até então}

todos os componentes são os melhores encontrados. O algoritmo procede incrementando

K de um e, para cada K, constrói-se o grafo K-associado correspondente (por meio da

função Kac, Algoritmo 3.1), representado por G(K) _{no algoritmo. Conforme K aumenta,}

componentes de uma mesma classe tendem a unirem-se para formar componentes maiores, dado que o aumento de K pode resultar na união de alguns componentes. Cada compo- nente recém-formado, obtido da união de um ou mais componentes do grafo K-associado anterior, tem um valor de pureza próprio que depende da estrutura do componente atual. Para cada grafo K-associado, a pureza de cada componente novo é comparada com os componentes que o formaram. Portanto, se o novo componente tiver pureza maior en- tão trocam-se os componentes correspondentes, armazenados em G(ot)_{, pelo componente}

recém-formados.

A substituição de componentes ocorre para todo K > 1, e é realizada se a pureza do componente atual for maior do que a dos componentes, armazenados no grafo ótimo, que possuem os mesmos vértices. Seja o componente C(K)

β , com pureza Φ

(K)

β , um com-

ponente do grafo K -associado formado na iteração atual K. Para que este componente seja aceito e adicionado no grafo ótimo, é preciso que a pureza Φ(K)

β seja maior ou igual à

pureza de todos os componentes C(ot)

no componente C(K)

β . A propriedade de crescimento monotônico dos componentes, em

resposta ao aumento no valor de K, garante que um componente do grafo K-associado contenha todos os vértices dos componentes do grafo (K − 1)-associado que o formaram, i.e. C(K−1)

β ⊆ C

(K)

β . O que significa que as conexões estabelecidas não são desfeitas ao

longo do aumento de K, e que componentes do grafo K -associado são provenientes da adição de arestas que eventualmente unem componentes do grafo (K-1)-associado. Dessa forma, um componente do grafo K -associado irá conter todos os componentes previamente obtidos a partir dos mesmos vértices.

A ideia é que variando K e mantendo os melhores componentes encontrados durante esse processo, é possível determinar o melhor valor de K, juntamente com a pureza, do componente que representa a distribuição local dos dados. Podendo, esses valores, vari- arem para as diferentes regiões do espaço de dados. De forma que, cada componente

Cα, além de estar associado à pureza Φα, também é relacionado ao valor de K em que

foi formado, notado por Kα. O processo segue enquanto a taxa de crescimento hGi/K

continuar crescendo, ou seja, o algoritmo termina quando a taxa de crescimento, corre- spondente ao grafo K-associado, for menor do que a taxa do último grafo obtido (grafo (K − 1)-associado), pela primeira vez. Para justificar esse critério de parada, considere encontrar o valor para o grau médio de um componente do grafo K-associado, de modo que, a pureza permaneça inalterada, como mostrado na Equação (3.4). Seja Φ(K−1)_{e Φ}(K)

a pureza deste componente nos grafos (K − 1)-associado e K-associado, respectivamente e, hG(K)_{i a média do grau dos componentes do grafo K-associado.}

Φ(K) = Φ(K−1) ⇔ hG (K)_i 2K = hG(K−1)_i 2(K_{− 1)} ⇔ hG (K)_i 2K = hG(K−1)_i 2K_{− 2} ⇔ 2KhG (K)_i 2K − 2_hG(K)_i 2K = 2K_hG(K−1)_i 2K (3.4) ⇔ hG(K)i − hG (K)_i K =hG (K−1) i ⇔ hG(K)i = hG(K−1)i +hG (K)_i K

Note que, para que o valor da pureza de um componente do grafo (K − 1)-associado não sofra alterações, quando recalculada para o mesmo componente no grafo K-associado, a média do grau neste componente deve ser ao menos hG(K)_{i/K maior que a média do}

grau no grafo anterior. Como o critério depende somente da média do grau, pode-se generalizar esta análise para o grafo todo e não apenas um único componente. Dessa forma, qualquer aumento na média do grau, do grafo K-associado atual, maior que a essa taxa hG(K)_{i/K, resultante do incremento de K, significa que o grafo K-associado terá}

algum(s) componente(s) com pureza maior do que em relação ao grafo K-associado. Caso contrário, pode-se dizer que, intuitivamente, o crescimento do grafo atingiu um ponto de

saturação, onde não é mais possível manter a taxa em crescimento e como consequência a pureza máxima para cada componente já foi atingida.

O critério de parada apresentado constitui uma heurística que utiliza a taxa de cresci- mento da média do grau para interromper o processo de construção do grafo ótimo assim que esta decresce. O critério de parada que considera todos os componentes possíveis corresponde à convergência do número de componentes no grafo K-associado atual, para o número de classes do problema. No entanto, para certos domínios de dados, este critério pode levar muitas iterações para ser satisfeito, ao passo que, os componentes de maior pureza são obtidos em poucas iterações. Nos experimentos considerados neste trabalho, o uso da heurística como critério de parada diminuiu o esforço computacional sem com- prometer o desempenho do algoritmo.

Uma consequência da definição da pureza, Equação (3.2), é que vértices isolados tem pureza igual a zero, o que significa que esses vértices não serão considerados no processo de classificação. Vértices isolados podem ser encontrados no grafo ótimo como reflexo de exemplos ruidosos ou outliers. Intuitivamente, quando uma instância de dado encontra-se cercado por instâncias de classes diferente da sua na distribuição dos dados; o vértice que o representa no grafo terá dificuldade para conectar-se à vértices da mesma classe. Mesmo quando o valor de K é suficientemente grande e esse tipo de vértice conecta-se a algum componente mais longe, esta nova configuração possivelmente não será aceita, pois esta conexão provavelmente degradará a pureza do componente que o vértice isolado se conectou tardamente.