Aula_KNN.knit

class: inverse, middle

## Método do k-ésimo vizinho mais próximo

.large[#### Agatha Rodrigues
]

---
class: middle, inverse

---
class: middle

# Contexto

- O método dos `\(k\)` vizinhos mais próximos - em inglês k-nearest neighbours (KNN)

- Útil tanto em problema de regressão quanto em problema de classificação.

- Talvez seja o método não paramétrico mais simples e mais conhecido na área de ML.

-  O método tem como base estimar a função de regressão (ou de classificação) para uma dada configuração das covariáveis `\({\bf x}\)` com base nas respostas `\(Y\)` dos `\(k\)`-vizinhos mais próximos a `\({\bf x}\)`.

- Vamos primeiro tratar no contexto de problema de regressão:

---
class: middle

# KNN em regressão

Formalmente, temos que
`\begin{align*}
  \widehat{f}({\bf x}) = \frac{1}{k}\sum_{i \in N_x}y_i,
\end{align*}`
em que `\(N_x\)` é o conjunto das `\(k\)` observações mais próximas de `\({\bf x}\)`, isto é, 
`\begin{align*}
  N_x = \{ i\in \{1,\ldots,m\}: d({\bf x}_i, {\bf x}) \leq d_x^k \}
\end{align*}`
e `\(d_x^k\)` é a distância do `\(k\)`-ésimo vizinho mais próximo.

Em outras palavras, a função de regressão avaliada em `\({\bf x}\)` é estimada utilizando-se uma média local das respostas dos `\(k\)` vizinhos mais próximos a `\({\bf x}\)` no espaço das covariáveis. 
 
---
class: middle

# KNN em regressão

O **tuning parameter** `\(k\)` pode ser escolhido por validação cruzada.

Balanço viés-variância:

-- Um valor alto de `\(k\)` leva a um modelo muito simples (uma constante quando `\(k \rightarrow \infty\)` ) e, assim, um viés alto, mas uma variância baixa.

-- Um valor baixo para `\(k\)` leva a um estimador com variância alta, mas viés baixo.

---
class:middle

---
class: middle

# Observações importantes:

-- Como medir a distância? Por distância Euclidiana, distância de Mahalanobis, entre outras na literatura.

-- É necessário guardar todas as observações para se fazer as predições.

---
class: middle

# KNN em classificação

Análogo ao KNN em regressão, mas ao invés de ser a média local, a predição é a moda de `\(Y\)` ao considerar os `\(k\)` vizinhos mais próximos de `\({\bf x}\)`.

# Observação

No R, tem algumas funções que realizam KNN. Sugestões: função knn() do pacote caret e pacote FNN (Fast Nearest Neighbor Search Algorithms and Applications
).

---
class: middle

# Nadaraya-Watson

O método de Nadaraya-Watson é uma variação do método ods `\(k\)`-vizinhos mais próximos bastante difundida na comunidade estatística.

Esse método consiste em estimar a função de regressão em um dado ponto `\({\bf x}\)` utilizando-se uma média ponderada das observações do conjunto de dados:

`\begin{align*}
  \widehat{f}({\bf x}) = \sum_{i = 1}^m w_i({\bf x})y_i,
\end{align*}`
em que `\(w_i({\bf x})\)` é um peso atribuído à `\(i\)`-ésima observação e que mede o quão similar `\({\bf x}_i\)` é a `\({\bf x}\)`.

Inicialmente, consideramos que
`\begin{align*}
  w_i = \frac{{\rm I}(x_i \in [x-h, x+h])}{\sum_{j=1}^m{\rm I}(x_j \in [x-h, x+h])},
\end{align*}`
em que `\(h\)` é definido por validação cruzada.

Em um cenário de classificação, o método funciona de forma análoga.

---
class: middle

# Nadaraya-Watson

De forma mais geral, `\(w_i({\bf x})\)` tem a forma:

`\begin{align*}
  w_i = \frac{K({\bf x}, {\bf x}_i)}{\sum_{j=1}^mK({\bf x}, {\bf x}_j)},
\end{align*}`
em que `\(K({\bf x}, {\bf x}_i)\)` é um kernel de suavização para medir a similaridade entre as observações. Algumas escolhas populares para `\(K({\bf x}, {\bf x}_i)\)` são:

- **kernel uniforme:** `\(K({\bf x}, {\bf x}_i)={\rm I}(d({\bf x}, {\bf x}_i) \leq h)\)`.

- **kernel gaussiano:** `\(K({\bf x}, {\bf x}_i)= (\sqrt{2\pi h^2})^{-1}\exp\{-d^2({\bf x}, {\bf x}_i)/2h^2\}\)`.

- **kernel triangular:** `\(K({\bf x}, {\bf x}_i)=(1-d({\bf x}, {\bf x}_i)/h){\rm I}(d({\bf x}, {\bf x}_i) \leq h)\)`.

- **kernel de Epanechnikov:** `\(K({\bf x}, {\bf x}_i)=(1-d^2({\bf x}, {\bf x}_i)/h^2){\rm I}(d({\bf x}, {\bf x}_i) \leq h)\)`.

---
class:middle

Influência da escolha de `\(h\)` no estimador de Nadaraya-Watson. Utilizado o kernel uniforme.

---
class:middle

Influência da escolha do Kernel no estimador de Nadaraya-Watson.

---
class:middle

**Observação:**

Uma forma de ajustar o estimador de Nadaraya-Watson é usando o pacote `\({\it locfit}\)`.