Forventede  trender  i  betydningen  av  foreldres  inntekt  og  utdanningslengde

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

Saída: G(K)_{= {C} 1, . . . , CN} onde Cα= (G′K(V ′_{, E}′_{); Φ} α) {Grafo K-associado} C⇐ ∅ G(K)⇐ ∅

para todovi∈ V faça

para j = 1 to K faça ∆vi,K ⇐ {vj|vj ∈ Λvi,K eyj= yi} E_{⇐ E ∪ {e}ij|vj ∈ ∆vi,K} fim para fim para C_{⇐ encontraComponentes(V ,E)}

para todoCα∈ C faça

Φα⇐ pureza(Cα)

G(K)_{⇐ G}(K)_{∪ {(C}

α(V′, E′); Φα)}

fim para

retorne G(K)

Como mencionado, o vértice virepresenta a instância xi. O algoritmo define o conjunto

∆vi,K que representa os vértices pertencentes à K-vizinhança do vértice vi que também

pertencem à mesma classe que vi. Estes conjuntos serão usados para conectar o grafo,

como mostrado no Algoritmo 3.1. Uma vez construído, a função encontraComponentes() encontra os componentes no grafo K -associado atual, por meio da busca em largura ou em profundidade. O método pureza() calcula a medida de pureza para cada componente, como será detalhada na próxima seção.

Note que cada valor de K está associado a um grafo K -associado e, como ficará claro mais adiante, diferentes valores para o parâmetro K resultará em grafos com diferentes características como, números de componentes e seus valores de pureza. Entretanto, no contexto de classificação, é desejável que cada componente apresente o mínimo de ruído, ou pureza máxima. A ideia é encontrar um grafo que consista em vários componentes sendo que cada componente mantenha a maior pureza possível, sem que dependam de um único valor de K.

3.1.1 A medida de pureza

A maneira em que o grafo K -associado é construído permite o cálculo de uma medida que reflete o quão puro ou livre de ruído é um componente. O cálculo da pureza utiliza-se da topologia do grafo para quantificar o grau de mistura em relação às diferentes classes. Seja gi o grau do vértice vi, N o número de instâncias no conjunto de treinamento e K

o tamanho da vizinhança considerada na construção do grafo. A taxa gi/2K corresponde

à fração de arestas entre o vértice vi e os vértices do mesmo componente. Assim, o total

de conexões |Eα| entre vértices no componente Cα é dado pela Equação (3.1). |Eα| = 1 2 Nα ∑ i=1 gi = Nα 2 Nα ∑ i=1 gi Nα = Nα 2 hGαi (3.1)

Na qual, Nα é o número de vértices no componente Cα e hGαi corresponde à média do

grau no componente Cα. O número máximo de arestas entre os Nα vértices do componente Cα é KNα. Dessa forma, pode-se definir uma medida de pureza ou de quão misturado

estão os componentes com relação às suas classes. Considere a medida de pureza definida pela Equação (3.2). Φα = NαhGαi 2 KNα = hGαi 2K (3.2)

Na equação, Φα é definida como a pureza do componente Cα. A Figura 3.2 ilustra

alguns exemplos do cálculo da pureza.

Φ = 2 = 6 2 × 3= 1 Φ =2 = 2,5 2 × 3= 0,416 Φ =2 = 1,5 2 × 3= 0,25 2 ₂ 2 2 2 2 2 2 2 2 2

Figura 3.2: Exemplo do cálculo da pureza para K = 3, considerando (a) componente puro, (b) componentes com pureza intermediária e (c) componente em volta a ruído.

Para um componente relativamente isolado com N instâncias de dados pertencentes a uma mesma classe, como na Figura 3.2(a), todo vértice terá conexões com todos os K outros vértices (formando um clique), o que resulta em um total de KN arestas ou 2KN na soma do grau. De modo que, o grau médio neste caso é hGi = 2K, resultando no valor máximo para a pureza, Φα = 1. Em contrapartida, quando existem ruídos ou quando

vértices de classes diferentes encontram-se misturados, os vértices não estabelecerão K conexões devido à presença de vértices de diferentes classes em suas K-vizinhanças. Nesses casos, quanto maior é a mistura dos dados, menor será o valor da pureza, como na Figura

3.2(b), onde os componentes encontram-se entrelaçados diminuindo a pureza um do outro (neste caso ambos têm pureza identica). O caso extremo, Φα = 0, refere-se a vértices

isolados no grafo que estão relacionados a dados ruidosos ou à outliers (Hodge e Austin, 2004), como por exemplo, os elementos da classe representada por retângulos azuis na Figura 3.2(c). Note que, a pureza igual a zero desconsidera o componente para ser usado na classificação de novos dados - o que significa que, por meio da pureza é possível detectar ruídos e outliers. De modo geral, Φαé definida no intervalo [0, 1], no qual, valores próximos

a 1 indicam maior interconectividade em um componente enquanto que valores menores indicam mistura entre componentes de classes diferentes ou ruído. Portanto, a relação Φα = hGαi/2K pode ser considerada como uma medida de pureza para o componente Cα. Em última análise, a pureza pode ser vista como a probabilidade a priori de conexão

na região delimitada pelo componente. Esta propriedade será explorada pelo classificador para definir as classes dos novos dados.

3.1.2 O grafo K-associado ótimo

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.