13 Classificação com k-Vizinhos Mais Próximos (k-NN)

O algoritmo k-NN é um classificador não paramétrico baseado em instâncias. Veremos como a métrica de distância e o parâmetro ‘k’ influenciam na tomada de decisão do modelo, qual a sua fundamentação teórica (a relação com o classificador de Bayes e o resultado de Cover e Hart), por que a normalização das variáveis é indispensável, como o método se estende à regressão e por que ele sofre especialmente com a chamada maldição da dimensionalidade. Também estudaremos a geometria do método (diagramas de Voronoi), resultados teóricos de consistência e de taxas de convergência (teorema de Stone), a conexão com a regressão por núcleo de Nadaraya–Watson, o tratamento de empates e de classes desbalanceadas, e técnicas para tornar o k-NN viável em grandes bases (edição, condensação e busca aproximada).

13.1 O Conceito do Algoritmo k-NN

O algoritmo k-NN (k-Nearest Neighbors ou $k$-Vizinhos Mais Próximos), cujas propriedades formais foram extensamente analisadas por Thomas Cover e Peter Hart (Cover e Hart 1967), é um dos métodos de classificação supervisionada mais clássicos, intuitivos e fáceis de compreender. O princípio conceitual baseia-se na máxima popular “Diga-me com quem andas e te direi quem és”. O algoritmo assume que registros com características semelhantes no espaço matemático tendem a pertencer à mesma classe de classificação.

Historicamente, a regra dos vizinhos mais próximos foi proposta por Evelyn Fix e Joseph Hodges em um relatório técnico de 1951 (Fix e Hodges 1951), no contexto da discriminação não paramétrica, e ganhou fundamentação teórica sólida com o trabalho de Cover e Hart (1967).

O k-NN é classificado teoricamente como:

Não Paramétrico: O algoritmo não faz qualquer suposição rígida sobre a distribuição probabilística subjacente dos dados (como assumir normalidade).
Aprendizado Baseado em Instâncias (Lazy Learner): Diferentemente de árvores ou regressão, o k-NN não gera uma equação ou um modelo treinado matemático consolidado. Ele simplesmente memoriza todo o conjunto de treinamento. A computação e o cálculo real de classificação acontecem apenas no momento em que um novo registro de teste precisa de previsão.

Essa segunda característica tem consequências práticas importantes: o “treinamento” é instantâneo, mas a predição é cara, pois exige comparar o novo ponto com todo o conjunto de treinamento, que precisa ser mantido em memória.

13.2 Como Funciona o Algoritmo na Prática?

Quando um novo ponto de dados (registro de teste) precisa ser classificado:

Classificação baseada em vizinhança de distância no algoritmo k-NN

O algoritmo calcula a distância matemática entre o ponto de teste e todos os pontos existentes na base de dados de treinamento.
Identifica e seleciona as $k$ menores distâncias (os $k$ vizinhos geometricamente mais próximos).
Avalia as classes a que esses vizinhos pertencem.
Realiza uma votação por maioria de votos: o ponto de teste é atribuído à classe que for mais frequente entre os seus vizinhos mais próximos.

13.3 A Geometria do 1-NN: Diagramas de Voronoi

Antes de formalizar o método do ponto de vista probabilístico, vale entender a sua geometria. Para $k = 1$, a regra de classificação induz uma partição do espaço que tem nome próprio e uma longa história na matemática e na geografia: o diagrama de Voronoi (também chamado de tesselação de Dirichlet ou de Thiessen, nome com que é conhecido na hidrologia para interpolar chuvas entre pluviômetros).

Definição. Dado um conjunto de pontos $\{\mathbf{x}_1, \ldots, \mathbf{x}_n\} \subset \mathbb{R}^p$ (os “sítios”) e uma distância $d$, a célula de Voronoi do ponto $\mathbf{x}_i$ é o conjunto dos pontos do espaço que estão mais próximos de $\mathbf{x}_i$ do que de qualquer outro sítio: \[ V_i = \{\mathbf{x} \in \mathbb{R}^p : d(\mathbf{x}, \mathbf{x}_i) \leq d(\mathbf{x}, \mathbf{x}_j) \ \text{para todo } j \neq i\}. \] As células $V_1, \ldots, V_n$ cobrem todo o espaço e só se intersectam em suas fronteiras. O classificador 1-NN é simplesmente \[ \hat{f}_{1\text{-NN}}(\mathbf{x}) = y_i \quad \text{se} \quad \mathbf{x} \in V_i, \] isto é, cada célula “herda” o rótulo do seu sítio.

As células são poliedros convexos (no caso euclidiano). Com a distância euclidiana, a condição $\|\mathbf{x} - \mathbf{x}_i\| \leq \|\mathbf{x} - \mathbf{x}_j\|$ equivale, elevando ao quadrado e expandindo, a \[ \|\mathbf{x}\|^2 - 2\mathbf{x}_i^\top\mathbf{x} + \|\mathbf{x}_i\|^2 \leq \|\mathbf{x}\|^2 - 2\mathbf{x}_j^\top\mathbf{x} + \|\mathbf{x}_j\|^2 \iff 2(\mathbf{x}_j - \mathbf{x}_i)^\top \mathbf{x} \leq \|\mathbf{x}_j\|^2 - \|\mathbf{x}_i\|^2 . \] O termo quadrático $\|\mathbf{x}\|^2$ se cancela, e o que resta é um semiespaço delimitado pelo hiperplano mediador (bissetor perpendicular) do segmento entre $\mathbf{x}_i$ e $\mathbf{x}_j$. Como $V_i$ é a interseção de $n - 1$ semiespaços, é um poliedro convexo. Consequentemente:

a fronteira de decisão do 1-NN é a união das faces de Voronoi que separam células de sítios com rótulos diferentes, sendo, portanto, linear por partes;
faces entre células de mesma classe são “apagadas” e não fazem parte da fronteira;
para $k > 1$, a partição relevante é o diagrama de Voronoi de ordem $k$, no qual cada região reúne os pontos que têm o mesmo conjunto de $k$ vizinhos mais próximos; a fronteira continua linear por partes, mas com menos “dentes”.

Exemplo resolvido: uma face de Voronoi

No exemplo numérico resolvido mais adiante, os dois vizinhos mais próximos de $\mathbf{x}_0 = (3, 4)$ são P6 $= (4, 4)$, da classe B, e P2 $= (2, 3)$, da classe A. A face de Voronoi entre eles está sobre o hiperplano mediador \[ 2(\mathbf{x}_{P2} - \mathbf{x}_{P6})^\top\mathbf{x} = \|\mathbf{x}_{P2}\|^2 - \|\mathbf{x}_{P6}\|^2 \iff 2(-2, -1)^\top \mathbf{x} = 13 - 32 \iff 4x_1 + 2x_2 = 19. \] O ponto médio $(3;\, 3{,}5)$ do segmento P2–P6 satisfaz $4 \cdot 3 + 2 \cdot 3{,}5 = 19$, como esperado. Para $\mathbf{x}_0$, temos $4 \cdot 3 + 2 \cdot 4 = 20 > 19$, ou seja, $\mathbf{x}_0$ está do lado de P6, o que confere com as distâncias $d(\mathbf{x}_0, \text{P6}) = 1 < \sqrt{2} = d(\mathbf{x}_0, \text{P2})$. Como P2 e P6 têm rótulos diferentes, esse trecho de reta faz parte da fronteira de decisão do 1-NN.

Em uma dimensão a situação é ainda mais simples: com pontos de treinamento $1$ (A), $3$ (A), $4$ (B), $7$ (B) e $8$ (A), as células são intervalos delimitados pelos pontos médios $2$; $3{,}5$; $5{,}5$ e $7{,}5$, e a fronteira do 1-NN consiste apenas nos pontos médios entre vizinhos de classes diferentes: $3{,}5$ e $7{,}5$.

Essa visão geométrica explica, por exemplo, por que o 1-NN é tão sensível a ruído: um único ponto mal rotulado no interior de uma região cria uma “ilha” — a sua célula de Voronoi inteira — classificada de forma errada.

13.4 Formalização

13.4.1 O classificador de Bayes

Conforme apresentado no Capítulo de Classificação com Árvores de Decisão, o objetivo de um classificador é minimizar o risco $L(f) = P\{Y \neq f(\mathbf{X})\}$. Condicionando em $\mathbf{X} = \mathbf{x}$, a probabilidade de acerto ao prever a classe $j$ é $P(Y = j \mid \mathbf{X} = \mathbf{x})$; portanto, o risco é minimizado, ponto a ponto, escolhendo a classe com maior probabilidade a posteriori: \[ f^{*}(\mathbf{x}) = \arg\max_{j \in \{1, \ldots, c\}} P(Y = j \mid \mathbf{X} = \mathbf{x}). \] Esse é o classificador de Bayes (Bayes classifier), e o seu risco, \[ R^{*} = L(f^{*}) = 1 - \mathbb{E}\left[\max_{j} P(Y = j \mid \mathbf{X})\right], \] é a taxa de erro de Bayes: o menor erro alcançável por qualquer classificador. Ele é positivo sempre que as classes se sobrepõem no espaço de atributos, e funciona como um limite inferior teórico, análogo ao erro irredutível em regressão.

O problema é que $P(Y = j \mid \mathbf{X} = \mathbf{x})$ é desconhecida. Os métodos de classificação podem ser vistos como diferentes estratégias para estimá-la; o k-NN adota a estratégia mais direta possível.

13.4.2 A estimativa do k-NN

Seja $\mathcal{N}_k(\mathbf{x}_0)$ o conjunto dos índices das $k$ observações de treinamento mais próximas de $\mathbf{x}_0$, segundo uma distância $d$. O k-NN estima a probabilidade condicional pela fração de vizinhos de cada classe: \[ \hat{P}(Y = j \mid \mathbf{X} = \mathbf{x}_0) = \frac{1}{k}\sum_{i \in \mathcal{N}_k(\mathbf{x}_0)} \mathbb{I}\{y_i = j\}, \] e classifica $\mathbf{x}_0$ imitando o classificador de Bayes com essa estimativa: \[ \hat{f}(\mathbf{x}_0) = \arg\max_j \hat{P}(Y = j \mid \mathbf{X} = \mathbf{x}_0), \] que é exatamente o voto majoritário entre os $k$ vizinhos. A ideia subjacente é uma aproximação local: supõe-se que $P(Y = j \mid \mathbf{X} = \mathbf{x})$ varie pouco numa vizinhança de $\mathbf{x}_0$, de modo que os rótulos de pontos próximos sejam amostras aproximadamente da mesma distribuição condicional.

13.4.3 O k-NN como estimador de densidade

Há uma segunda maneira, muito instrutiva, de chegar à mesma regra, partindo do teorema de Bayes e de uma estimativa não paramétrica de densidade. Seja $V_k(\mathbf{x}_0)$ o volume da menor bola centrada em $\mathbf{x}_0$ que contém $k$ pontos de treinamento. Como a probabilidade de uma observação cair nessa bola é aproximadamente $f(\mathbf{x}_0) V_k(\mathbf{x}_0)$, e a fração observada é $k/n$, obtemos o estimador de densidade por $k$ vizinhos (Loftsgaarden e Quesenberry 1965): \[ \hat{f}(\mathbf{x}_0) = \frac{k}{n\, V_k(\mathbf{x}_0)}. \] Aplicando a mesma ideia separadamente a cada classe: se $n_j$ observações de treinamento pertencem à classe $j$ e $k_j$ delas estão entre os $k$ vizinhos de $\mathbf{x}_0$, então a densidade condicional é estimada por $\hat{f}_j(\mathbf{x}_0) = k_j / (n_j V_k(\mathbf{x}_0))$, e a probabilidade a priori por $\hat{\pi}_j = n_j/n$. Pelo teorema de Bayes, \[ \hat{P}(Y = j \mid \mathbf{X} = \mathbf{x}_0) = \frac{\hat{\pi}_j \hat{f}_j(\mathbf{x}_0)}{\sum_{l} \hat{\pi}_l \hat{f}_l(\mathbf{x}_0)} = \frac{\dfrac{n_j}{n}\cdot\dfrac{k_j}{n_j V_k}}{\sum_l \dfrac{n_l}{n}\cdot\dfrac{k_l}{n_l V_k}} = \frac{k_j}{\sum_l k_l} = \frac{k_j}{k}. \] O volume $V_k$ e os tamanhos $n_j$ se cancelam, e reencontramos exatamente a fração de vizinhos. Essa derivação deixa explícito algo que a versão “por votos” esconde: o k-NN usa implicitamente as proporções amostrais $n_j/n$ como probabilidades a priori. Esse fato será importante quando discutirmos classes desbalanceadas.

13.4.4 Consistência e o resultado de Cover e Hart

Duas perguntas teóricas surgem naturalmente: (i) o k-NN se aproxima do classificador de Bayes quando $n$ cresce? (ii) Quão ruim é a regra mais simples, com $k = 1$?

Consistência. Sob condições bastante gerais, se $k \to \infty$ e $k/n \to 0$ quando $n \to \infty$, o risco do k-NN converge para o risco de Bayes $R^{*}$ (Stone 1977). A condição $k \to \infty$ garante que a média sobre os vizinhos tenha variância cada vez menor; $k/n \to 0$ garante que os vizinhos fiquem cada vez mais próximos de $\mathbf{x}_0$, de modo que o viés também desapareça. O k-NN é, portanto, um classificador universalmente consistente.

O vizinho mais próximo (1-NN). Com $k = 1$ fixo, o método não é consistente, mas Cover e Hart (1967) demonstraram um resultado notável: quando $n \to \infty$, o risco $R$ do 1-NN satisfaz \[ R^{*} \;\leq\; R \;\leq\; R^{*}\left(2 - \frac{c}{c-1}R^{*}\right) \;\leq\; 2R^{*}. \] Em palavras: assintoticamente, o erro do 1-NN é no máximo o dobro do erro de Bayes. Informalmente, “metade da informação disponível para classificar está contida no vizinho mais próximo”.

Esboço da demonstração para o caso binário

Seja $\eta(\mathbf{x}) = P(Y = 1 \mid \mathbf{X} = \mathbf{x})$. Quando $n \to \infty$, o vizinho mais próximo $\mathbf{x}'$ de $\mathbf{x}$ converge para $\mathbf{x}$, e (com $\eta$ contínua) seu rótulo $Y'$ passa a ter distribuição Bernoulli($\eta(\mathbf{x})$), independente de $Y$. O 1-NN erra quando $Y \neq Y'$: \[ P(Y \neq Y' \mid \mathbf{x}) = \eta(\mathbf{x})[1 - \eta(\mathbf{x})] + [1 - \eta(\mathbf{x})]\eta(\mathbf{x}) = 2\eta(\mathbf{x})[1 - \eta(\mathbf{x})]. \] Seja $r(\mathbf{x}) = \min\{\eta(\mathbf{x}), 1 - \eta(\mathbf{x})\}$, o erro condicional de Bayes, de modo que $R^{*} = \mathbb{E}[r(\mathbf{X})]$ e $2\eta(1-\eta) = 2r(1-r)$. Então \[ R = \mathbb{E}[2r(1-r)] = 2R^{*} - 2\,\mathbb{E}[r^2] \leq 2R^{*} - 2(R^{*})^2 = 2R^{*}(1 - R^{*}), \] em que usamos a desigualdade de Jensen, $\mathbb{E}[r^2] \geq (\mathbb{E}[r])^2$. Esse é o limite de Cover e Hart com $c = 2$. Além disso, como $r \leq 1/2$, temos $2r(1-r) \geq r$, o que dá $R \geq R^{*}$.

Curiosamente, $2\eta(1-\eta)$ é exatamente o índice de Gini do caso binário visto no Capítulo de Classificação com Árvores de Decisão: o erro assintótico do 1-NN é o Gini esperado da distribuição condicional das classes.

Exemplo resolvido. Suponha que $\eta(\mathbf{x})$ assuma apenas dois valores: $\eta = 0{,}1$ em metade do espaço (com probabilidade $0{,}5$) e $\eta = 0{,}3$ na outra metade. Então $r(\mathbf{x}) \in \{0{,}1;\ 0{,}3\}$ e \[ R^{*} = 0{,}5 \cdot 0{,}1 + 0{,}5 \cdot 0{,}3 = 0{,}2, \qquad R_{1\text{-NN}} = 0{,}5 \cdot 2(0{,}1)(0{,}9) + 0{,}5 \cdot 2(0{,}3)(0{,}7) = 0{,}09 + 0{,}21 = 0{,}30. \] O limite de Cover e Hart dá $2R^{*}(1 - R^{*}) = 2(0{,}2)(0{,}8) = 0{,}32 \geq 0{,}30$, e o limite grosseiro $2R^{*} = 0{,}4$. O 1-NN perde $0{,}10$ em relação ao ótimo, mas permanece bem abaixo do dobro do erro de Bayes.

13.4.5 O teorema de Stone e a desigualdade do classificador plug-in

O resultado de consistência mencionado acima pode ser enunciado com precisão. Para a regressão, seja $m(\mathbf{x}) = \mathbb{E}[Y \mid \mathbf{X} = \mathbf{x}]$ e $\hat{m}_n$ o estimador k-NN construído com $n$ observações independentes.

Teorema (Stone, 1977, versão k-NN)

Se $k = k_n$ satisfaz $k_n \to \infty$ e $k_n / n \to 0$ quando $n \to \infty$, então, para toda distribuição de $(\mathbf{X}, Y)$ com $\mathbb{E}[Y^2] < \infty$ (e empates de distância desfeitos aleatoriamente), \[ \mathbb{E}\int \big(\hat{m}_n(\mathbf{x}) - m(\mathbf{x})\big)^2 \, \mu(d\mathbf{x}) \longrightarrow 0, \] em que $\mu$ é a distribuição de $\mathbf{X}$. Dizemos que o estimador é universalmente consistente em $L_2$.

O adjetivo “universal” é forte: nenhuma hipótese de continuidade, de densidade ou de forma paramétrica é feita sobre a distribuição. A prova completa (Stone 1977; Devroye, Györfi, e Lugosi 1996; Györfi et al. 2002) verifica que os pesos $W_{ni}(\mathbf{x}) = \mathbb{I}\{i \in \mathcal{N}_k(\mathbf{x})\}/k$ satisfazem três condições gerais: (i) concentram-se em uma vizinhança que encolhe; (ii) nenhum peso individual domina, pois $\max_i W_{ni} = 1/k \to 0$; e (iii) a soma dos pesos é 1.

Para passar da regressão à classificação, aplicamos o resultado a $Y' = \mathbb{I}\{Y = 1\}$, cuja regressão é $\eta(\mathbf{x})$, e usamos uma desigualdade elementar que vale para qualquer classificador plug-in $g(\mathbf{x}) = \mathbb{I}\{\hat{\eta}(\mathbf{x}) > 1/2\}$.

Lema (desigualdade plug-in). No caso binário, \[ L(g) - R^{*} \;\leq\; 2\,\mathbb{E}\,\big|\hat{\eta}(\mathbf{X}) - \eta(\mathbf{X})\big| \;\leq\; 2\sqrt{\mathbb{E}\big(\hat{\eta}(\mathbf{X}) - \eta(\mathbf{X})\big)^2}. \]

Prova. Condicionando em $\mathbf{X} = \mathbf{x}$, a probabilidade de erro de uma regra que decide pela classe 1 é $1 - \eta(\mathbf{x})$, e pela classe 0 é $\eta(\mathbf{x})$. Assim, quando $g$ e o classificador de Bayes $f^{*}$ concordam, a diferença de erro condicional é zero; quando discordam, ela vale $|\eta(\mathbf{x}) - (1 - \eta(\mathbf{x}))| = |2\eta(\mathbf{x}) - 1|$. Logo \[ L(g) - R^{*} = \mathbb{E}\big[\, |2\eta(\mathbf{X}) - 1| \;\mathbb{I}\{g(\mathbf{X}) \neq f^{*}(\mathbf{X})\}\big]. \] Se $g(\mathbf{x}) \neq f^{*}(\mathbf{x})$, então $\eta(\mathbf{x})$ e $\hat{\eta}(\mathbf{x})$ estão em lados opostos de $1/2$, e portanto $|\eta(\mathbf{x}) - 1/2| \leq |\eta(\mathbf{x}) - \hat{\eta}(\mathbf{x})|$, isto é, $|2\eta(\mathbf{x}) - 1| \leq 2|\hat{\eta}(\mathbf{x}) - \eta(\mathbf{x})|$. Substituindo, obtém-se a primeira desigualdade; a segunda é a desigualdade de Cauchy–Schwarz (ou de Jensen). $\square$

Combinando o lema com o teorema de Stone, o risco do k-NN converge para $R^{*}$, o que justifica a afirmação de consistência universal feita acima. O lema também mostra algo importante: classificar é mais fácil do que estimar probabilidades. Erros grandes em $\hat{\eta}$ só custam caro onde $\eta$ está perto de $1/2$; longe dessa região, o classificador acerta a decisão mesmo com estimativas grosseiras.

13.4.6 Taxas de convergência

Consistência não diz quão rápido o erro cai. Suponha que $m$ seja lipschitziana, $|m(\mathbf{x}) - m(\mathbf{z})| \leq L \|\mathbf{x} - \mathbf{z}\|$, que $\mathbf{X}$ tenha densidade limitada e afastada de zero em uma região compacta de $\mathbb{R}^p$ e que $\operatorname{Var}(Y \mid \mathbf{X}) \leq \sigma^2$. O raio da vizinhança que contém $k$ dos $n$ pontos é da ordem de $(k/n)^{1/p}$, pois o volume de uma bola de raio $\rho$ é proporcional a $\rho^p$. Assim, heuristicamente, \[ \text{EQM} \approx \underbrace{L^2 \left(\frac{k}{n}\right)^{2/p}}_{\text{viés}^2} + \underbrace{\frac{\sigma^2}{k}}_{\text{variância}}. \] Derivando em relação a $k$ e igualando a zero, o ótimo satisfaz $k^{(p+2)/p} \propto n^{2/p}$, isto é, \[ k^{*} \propto n^{2/(p+2)}, \qquad \text{EQM}^{*} \propto n^{-2/(p+2)}. \] Essa é a taxa minimax para funções lipschitzianas (Györfi et al. 2002): nenhum estimador consegue fazer melhor uniformemente sobre essa classe. A dependência de $p$ no expoente é a maldição da dimensionalidade em forma quantitativa. Ignorando constantes, para atingir $\text{EQM} = 0{,}01$ precisamos de $n \approx 0{,}01^{-(p+2)/2} = 10^{p+2}$ observações:

Dimensão $p$	Taxa $n^{-2/(p+2)}$	$n$ para EQM $\approx 0{,}01$
1	$n^{-0{,}67}$	$10^3$
2	$n^{-0{,}50}$	$10^4$
5	$n^{-0{,}29}$	$10^7$
10	$n^{-0{,}17}$	$10^{12}$
20	$n^{-0{,}09}$	$10^{22}$

13.5 Exemplo Numérico Resolvido à Mão

Considere o conjunto de treinamento abaixo, com duas variáveis já na mesma escala e duas classes, A e B. Queremos classificar o ponto $\mathbf{x}_0 = (3, 4)$.

Ponto	$x_1$	$x_2$	Classe
P1	1	1	A
P2	2	3	A
P3	4	2	A
P4	3	6	B
P5	6	5	B
P6	4	4	B
P7	0	4	B
P8	5	2	A

Passo 1: distâncias euclidianas até $\mathbf{x}_0$.

Ponto	Cálculo	$d(\mathbf{x}_0, \cdot)$	Classe	Posto
P6	$\sqrt{(4-3)^2 + (4-4)^2} = \sqrt{1}$	1,000	B	1º
P2	$\sqrt{(2-3)^2 + (3-4)^2} = \sqrt{2}$	1,414	A	2º
P4	$\sqrt{(3-3)^2 + (6-4)^2} = \sqrt{4}$	2,000	B	3º
P3	$\sqrt{(4-3)^2 + (2-4)^2} = \sqrt{5}$	2,236	A	4º
P8	$\sqrt{(5-3)^2 + (2-4)^2} = \sqrt{8}$	2,828	A	5º
P7	$\sqrt{(0-3)^2 + (4-4)^2} = \sqrt{9}$	3,000	B	6º
P5	$\sqrt{(6-3)^2 + (5-4)^2} = \sqrt{10}$	3,162	B	7º
P1	$\sqrt{(1-3)^2 + (1-4)^2} = \sqrt{13}$	3,606	A	8º

Passo 2: votação para diferentes valores de $k$.

$k = 1$: vizinho {P6} $\Rightarrow$ classe B, com $\hat{P}(B \mid \mathbf{x}_0) = 1$.
$k = 3$: vizinhos {P6, P2, P4} $\Rightarrow$ votos: B = 2, A = 1 $\Rightarrow$ classe B, com $\hat{P}(B \mid \mathbf{x}_0) = 2/3$.
$k = 5$: vizinhos {P6, P2, P4, P3, P8} $\Rightarrow$ votos: A = 3, B = 2 $\Rightarrow$ classe A, com $\hat{P}(A \mid \mathbf{x}_0) = 3/5$.

O exemplo mostra que a decisão pode mudar com $k$: os vizinhos imediatos são de B, mas há uma concentração de pontos de A um pouco mais distante.

13.5.1 k-NN ponderado pela distância

No voto majoritário simples, o 5º vizinho (a uma distância 2,828) tem o mesmo peso que o 1º (a uma distância 1). O k-NN ponderado (Dudani 1976) atribui a cada vizinho um peso decrescente com a distância, $w_i = g(d(\mathbf{x}_0, \mathbf{x}_i))$, e decide por \[ \hat{f}(\mathbf{x}_0) = \arg\max_j \sum_{i \in \mathcal{N}_k(\mathbf{x}_0)} w_i \,\mathbb{I}\{y_i = j\}. \] As escolhas mais comuns são $w_i = 1/d_i$ e $w_i = 1/d_i^2$ (com algum cuidado se $d_i = 0$, caso em que se atribui a classe do ponto coincidente). Retomando o exemplo com $k = 5$:

Com $w_i = 1/d_i$: B soma $1/1 + 1/2 = 1{,}500$; A soma $1/\sqrt{2} + 1/\sqrt{5} + 1/\sqrt{8} = 0{,}707 + 0{,}447 + 0{,}354 = 1{,}508$. A classe A vence por margem mínima.
Com $w_i = 1/d_i^2$: B soma $1/1 + 1/4 = 1{,}250$; A soma $1/2 + 1/5 + 1/8 = 0{,}825$. A classe B vence.

A ponderação reduz a sensibilidade à escolha de $k$, pois vizinhos distantes contribuem pouco, e também resolve a maior parte dos empates.

13.5.2 k-NN para regressão

Quando a resposta $Y$ é quantitativa, o k-NN estima a função de regressão $f(\mathbf{x}) = \mathbb{E}[Y \mid \mathbf{X} = \mathbf{x}]$ pela média das respostas dos vizinhos: \[ \hat{f}(\mathbf{x}_0) = \frac{1}{k}\sum_{i \in \mathcal{N}_k(\mathbf{x}_0)} y_i \qquad \text{ou, ponderado,} \qquad \hat{f}(\mathbf{x}_0) = \frac{\sum_{i \in \mathcal{N}_k} w_i y_i}{\sum_{i \in \mathcal{N}_k} w_i}. \] Por exemplo, se no conjunto acima os pontos P6, P2 e P4 tivessem respostas $y = 10$, $14$ e $12$, a predição com $k = 3$ seria $(10 + 14 + 12)/3 = 12$; com pesos $1/d$, seria \[ \frac{10/1 + 14/\sqrt{2} + 12/2}{1 + 1/\sqrt{2} + 1/2} = \frac{25{,}899}{2{,}207} \approx 11{,}73. \]

Para a regressão, a decomposição viés-variância do k-NN é especialmente transparente (Hastie, Tibshirani, e Friedman 2009). Supondo $Y = f(\mathbf{X}) + \varepsilon$, com $\mathbb{E}[\varepsilon] = 0$, $\operatorname{Var}(\varepsilon) = \sigma^2$ e os pontos de treinamento fixos, o erro esperado de predição em $\mathbf{x}_0$ é \[ \text{Err}(\mathbf{x}_0) = \underbrace{\sigma^2}_{\text{irredutível}} + \underbrace{\left[f(\mathbf{x}_0) - \frac{1}{k}\sum_{l=1}^{k} f(\mathbf{x}_{(l)})\right]^2}_{\text{viés}^2} + \underbrace{\frac{\sigma^2}{k}}_{\text{variância}}, \] em que $\mathbf{x}_{(l)}$ é o $l$-ésimo vizinho mais próximo. A variância cai com $k$, enquanto o viés tende a crescer, pois vizinhos mais distantes são incluídos na média. Isso formaliza a discussão sobre a escolha de $k$ apresentada adiante.

Derivação da decomposição

Seja $Y_0 = f(\mathbf{x}_0) + \varepsilon_0$ uma nova resposta em $\mathbf{x}_0$, independente dos dados de treinamento, e $\hat{f}(\mathbf{x}_0) = \frac{1}{k}\sum_{l=1}^{k} y_{(l)}$, com $y_{(l)} = f(\mathbf{x}_{(l)}) + \varepsilon_{(l)}$. Como os $\mathbf{x}_i$ são fixos, o conjunto de vizinhos não é aleatório, e \[ \mathbb{E}[\hat{f}(\mathbf{x}_0)] = \frac{1}{k}\sum_{l=1}^{k} f(\mathbf{x}_{(l)}) =: \bar{f}_k(\mathbf{x}_0), \qquad \operatorname{Var}[\hat{f}(\mathbf{x}_0)] = \frac{1}{k^2}\sum_{l=1}^{k}\operatorname{Var}(\varepsilon_{(l)}) = \frac{\sigma^2}{k}, \] em que usamos a independência dos erros. Escrevendo $Y_0 - \hat{f} = \varepsilon_0 + [f(\mathbf{x}_0) - \bar{f}_k] + [\bar{f}_k - \hat{f}]$, os três termos têm, respectivamente, média zero, valor constante e média zero, e o primeiro é independente do terceiro. Elevando ao quadrado e tomando a esperança, os produtos cruzados se anulam: \[ \mathbb{E}\big[(Y_0 - \hat{f}(\mathbf{x}_0))^2\big] = \sigma^2 + \big[f(\mathbf{x}_0) - \bar{f}_k(\mathbf{x}_0)\big]^2 + \frac{\sigma^2}{k}. \qquad \square \]

Exemplo resolvido: o viés e a variância em função de $k$. Considere $f(x) = x^2$, pontos de treinamento fixos $x = 0;\ 0{,}1;\ 0{,}2;\ \ldots;\ 1$ (11 pontos), $\sigma^2 = 0{,}01$ e o ponto de predição $x_0 = 0{,}52$, com $f(x_0) = 0{,}2704$. Os vizinhos, em ordem de distância, são $0{,}5$; $0{,}6$; $0{,}4$; $0{,}7$; $0{,}3$; $0{,}8$; $0{,}2$; $0{,}9$; $0{,}1$; … Por exemplo, para $k = 3$, $\bar{f}_3 = (0{,}25 + 0{,}36 + 0{,}16)/3 = 0{,}2567$, e o viés ao quadrado é $(0{,}2704 - 0{,}2567)^2 \approx 0{,}000189$.

$k$	$\bar{f}_k(x_0)$	Viés$^2$	Variância $\sigma^2/k$	Erro esperado
1	0,2500	0,000416	0,010000	0,020416
3	0,2567	0,000189	0,003333	0,013522
5	0,2700	0,000000	0,002000	0,012000
7	0,2900	0,000384	0,001429	0,011813
9	0,3167	0,002141	0,001111	0,013252
11	0,3500	0,006336	0,000909	0,017245

O erro esperado (que inclui o termo irredutível $\sigma^2 = 0{,}01$) desenha a curva em “U”: cai de $0{,}0204$ ($k = 1$) até o mínimo $0{,}0118$ ($k = 7$) e volta a subir. Note que o viés não é monótono em $k$ (para $k = 5$ ele é praticamente nulo, porque os vizinhos ficam quase simetricamente dispostos em torno de $x_0$ e a curvatura se compensa), mas a tendência de crescimento é nítida quando a vizinhança passa a incluir pontos distantes, onde $f$ é muito maior.

13.5.3 O k-NN como suavizador linear e os graus de liberdade efetivos

Tanto a média simples quanto a média ponderada dos vizinhos são combinações lineares das respostas. Avaliando o estimador nos próprios pontos de treinamento, podemos escrever \[ \hat{\mathbf{y}} = \mathbf{S}\,\mathbf{y}, \qquad S_{ij} = \begin{cases} 1/k, & \text{se } j \in \mathcal{N}_k(\mathbf{x}_i), \\ 0, & \text{caso contrário,} \end{cases} \] em que $\mathbf{S}$ é a matriz suavizadora (smoother matrix), análoga à matriz chapéu $\mathbf{H} = \mathbf{X}(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top$ da regressão linear. Para um suavizador linear, os graus de liberdade efetivos são definidos por \[ \text{gl} = \frac{1}{\sigma^2}\sum_{i=1}^{n} \operatorname{Cov}(\hat{y}_i, y_i) = \operatorname{tr}(\mathbf{S}), \] pois $\operatorname{Cov}(\hat{y}_i, y_i) = \sum_j S_{ij}\operatorname{Cov}(y_j, y_i) = S_{ii}\sigma^2$. Na regressão linear com $p$ coeficientes, $\operatorname{tr}(\mathbf{H}) = p$, o que justifica o nome. No k-NN, cada ponto de treinamento é o seu próprio vizinho mais próximo (distância zero), logo $S_{ii} = 1/k$ e \[ \text{gl}_{k\text{-NN}} = \operatorname{tr}(\mathbf{S}) = \sum_{i=1}^{n}\frac{1}{k} = \frac{n}{k}. \] Esta é a demonstração da afirmação, feita adiante, de que o k-NN tem “aproximadamente $n/k$ parâmetros efetivos”. Com $n = 200$ e $k = 10$, por exemplo, o k-NN tem a complexidade de um modelo com 20 parâmetros; com $k = 1$, tem 200 — tantos quantos são os dados, razão pela qual interpola o treinamento.

13.5.4 Do k-NN aos estimadores de kernel (Nadaraya–Watson)

O k-NN atribui peso $1/k$ aos $k$ vizinhos e peso zero aos demais: os pesos “saltam” abruptamente, o que torna $\hat{f}$ uma função descontínua de $\mathbf{x}_0$. Uma generalização natural, proposta independentemente por Nadaraya (1964) e Watson (1964), substitui esse corte por pesos que decaem suavemente com a distância: \[ \hat{f}_h(\mathbf{x}_0) = \frac{\sum_{i=1}^{n} K\!\left(\dfrac{\|\mathbf{x}_i - \mathbf{x}_0\|}{h}\right) y_i}{\sum_{i=1}^{n} K\!\left(\dfrac{\|\mathbf{x}_i - \mathbf{x}_0\|}{h}\right)}, \] em que $K$ é uma função núcleo (kernel) não negativa e decrescente, como a gaussiana $K(u) = e^{-u^2/2}$ ou a de Epanechnikov $K(u) = \frac{3}{4}(1 - u^2)\,\mathbb{I}\{|u| \leq 1\}$, e $h > 0$ é a largura de banda (bandwidth). Observe as relações:

com o núcleo uniforme $K(u) = \mathbb{I}\{|u| \leq 1\}$ e $h = d_{(k)}(\mathbf{x}_0)$, a distância ao $k$-ésimo vizinho, o estimador de Nadaraya–Watson é exatamente o k-NN. O k-NN é, portanto, um estimador de kernel com banda adaptativa: estreita onde os dados são densos e larga onde são esparsos;
$h$ desempenha o papel de $k$: $h$ pequeno produz baixo viés e alta variância; $h$ grande, o contrário. Quando $h \to \infty$, todos os pesos se igualam e $\hat{f}_h \to \bar{y}$;
a mesma ideia, aplicada a indicadores de classe, fornece classificadores de kernel, e o estimador de densidade correspondente é o estimador de densidade por núcleo (Silverman 1986).

Exemplo resolvido: Nadaraya–Watson com núcleo gaussiano

Dados $(x_i, y_i)$: $(1, 2)$, $(2, 4)$, $(3, 5)$, $(4, 4)$, $(5, 6)$; queremos estimar $f(2{,}5)$.

k-NN com $k = 2$: os vizinhos são $x = 2$ e $x = 3$ (empatados à distância $0{,}5$), e $\hat{f} = (4 + 5)/2 = 4{,}5$.

Nadaraya–Watson com $h = 1$: as distâncias padronizadas são $u_i = |x_i - 2{,}5| = (1{,}5;\ 0{,}5;\ 0{,}5;\ 1{,}5;\ 2{,}5)$, e os pesos $K(u_i) = e^{-u_i^2/2}$: \[ (0{,}3247;\ 0{,}8825;\ 0{,}8825;\ 0{,}3247;\ 0{,}0439), \qquad \textstyle\sum K = 2{,}4583. \] Normalizando, os pesos são $(0{,}132;\ 0{,}359;\ 0{,}359;\ 0{,}132;\ 0{,}018)$ e \[ \hat{f}_1(2{,}5) = \frac{0{,}3247 \cdot 2 + 0{,}8825 \cdot 4 + 0{,}8825 \cdot 5 + 0{,}3247 \cdot 4 + 0{,}0439 \cdot 6}{2{,}4583} \approx 4{,}131. \] Com $h = 0{,}5$, quase todo o peso fica nos dois vizinhos imediatos e $\hat{f}_{0{,}5}(2{,}5) \approx 4{,}473$, próximo do 2-NN; com $h = 3$, os pesos ficam quase uniformes e $\hat{f}_{3}(2{,}5) \approx 4{,}143$, próximo da média global $\bar{y} = 4{,}2$.

13.6 Métricas de Distância Comuns

Para calcular a proximidade física entre os pontos no espaço multidimensional dos atributos, utilizamos métricas de distância. Formalmente, uma métrica em um conjunto $\mathcal{X}$ é uma função $d: \mathcal{X} \times \mathcal{X} \to [0, \infty)$ que satisfaz, para todos $\mathbf{p}, \mathbf{q}, \mathbf{r}$: (i) $d(\mathbf{p}, \mathbf{q}) = 0 \iff \mathbf{p} = \mathbf{q}$; (ii) simetria, $d(\mathbf{p}, \mathbf{q}) = d(\mathbf{q}, \mathbf{p})$; e (iii) desigualdade triangular, $d(\mathbf{p}, \mathbf{r}) \leq d(\mathbf{p}, \mathbf{q}) + d(\mathbf{q}, \mathbf{r})$. Sejam dois pontos $p = (p_1, p_2, \dots, p_n)$ e $q = (q_1, q_2, \dots, q_n)$:

13.6.1 Distância Euclidiana

É a menor distância em linha reta entre dois pontos (métrica geométrica tradicional): \[d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}\]

13.6.2 Distância de Manhattan

Mede a distância percorrendo caminhos perpendiculares em grade (como a locomoção de táxi pelas quadras de Manhattan): \[d(p, q) = \sum_{i=1}^{n} |p_i - q_i|\]

Por somar valores absolutos em vez de quadrados, a distância de Manhattan é menos sensível a grandes diferenças em uma única coordenada.

13.6.3 Distância de Minkowski

Generaliza as anteriores por meio de um parâmetro $r \geq 1$: \[d_r(p, q) = \left(\sum_{i=1}^{n} |p_i - q_i|^r\right)^{1/r}.\] Para $r = 1$ obtemos Manhattan e, para $r = 2$, a Euclidiana. Para $0 < r < 1$, a expressão não satisfaz a desigualdade triangular e deixa de ser uma métrica.

Teorema: $d_r$ é uma métrica se, e somente se, $r \geq 1$

As propriedades (i) e (ii) são imediatas para qualquer $r > 0$. A dificuldade está na desigualdade triangular. Escrevendo $\mathbf{u} = \mathbf{p} - \mathbf{q}$ e $\mathbf{v} = \mathbf{q} - \mathbf{s}$, de modo que $\mathbf{p} - \mathbf{s} = \mathbf{u} + \mathbf{v}$, e denotando $\|\mathbf{u}\|_r = \left(\sum_i |u_i|^r\right)^{1/r}$, precisamos mostrar a desigualdade de Minkowski \[ \|\mathbf{u} + \mathbf{v}\|_r \leq \|\mathbf{u}\|_r + \|\mathbf{v}\|_r, \qquad r \geq 1. \]

Prova. Se $\mathbf{u}$ ou $\mathbf{v}$ é nulo, não há o que provar. Caso contrário, sejam $A = \|\mathbf{u}\|_r > 0$, $B = \|\mathbf{v}\|_r > 0$, $\lambda = A/(A + B) \in (0, 1)$ e os vetores unitários $\mathbf{a} = \mathbf{u}/A$ e $\mathbf{b} = \mathbf{v}/B$. Então \[ \frac{\mathbf{u} + \mathbf{v}}{A + B} = \lambda\,\mathbf{a} + (1 - \lambda)\,\mathbf{b}. \] Para $r \geq 1$, a função $t \mapsto |t|^r$ é convexa em $\mathbb{R}$; aplicando a convexidade coordenada a coordenada, \[ \sum_i \left|\lambda a_i + (1-\lambda) b_i\right|^r \leq \lambda \sum_i |a_i|^r + (1 - \lambda)\sum_i |b_i|^r = \lambda + (1 - \lambda) = 1. \] Logo $\|\mathbf{u} + \mathbf{v}\|_r^r \leq (A + B)^r$, que é a desigualdade desejada. $\square$

Contraexemplo para $r < 1$. Tome $r = 1/2$ e os pontos $\mathbf{p} = (0, 0)$, $\mathbf{q} = (1, 0)$ e $\mathbf{s} = (1, 1)$. Então \[ d_{1/2}(\mathbf{p}, \mathbf{s}) = \left(1^{1/2} + 1^{1/2}\right)^{2} = 4 \;>\; 2 = d_{1/2}(\mathbf{p}, \mathbf{q}) + d_{1/2}(\mathbf{q}, \mathbf{s}), \] pois $d_{1/2}(\mathbf{p}, \mathbf{q}) = d_{1/2}(\mathbf{q}, \mathbf{s}) = 1$: ir “pela diagonal” é mais longo do que dar a volta pelos eixos. Geometricamente, a bola unitária $\{\mathbf{u}: \|\mathbf{u}\|_r \leq 1\}$ é convexa para $r \geq 1$ (um losango para $r = 1$, um círculo para $r = 2$, um quadrado para $r = \infty$) e não convexa (uma “estrela” de lados côncavos) para $r < 1$, e a convexidade da bola unitária é exatamente o que garante a desigualdade triangular.

Mesmo sem ser uma métrica, a “distância” fracionária $d_r$ com $r < 1$ é às vezes usada no k-NN em alta dimensão, pois tende a preservar melhor o contraste entre vizinhos próximos e distantes (Aggarwal, Hinneburg, e Keim 2001). O k-NN não exige formalmente a desigualdade triangular; já as estruturas de busca como a ball tree, que a utilizam para podar a busca, deixam de ser exatas.

13.6.4 Distância de Chebyshev

É o limite da Minkowski quando $r \to \infty$, e corresponde à maior diferença entre as coordenadas: \[d_\infty(p, q) = \max_{i} |p_i - q_i|.\]

Exemplo. Para $p = (1, 2, 3)$ e $q = (4, 0, 3)$, as diferenças absolutas são $(3, 2, 0)$:

Métrica	Cálculo	Valor
Manhattan ($r = 1$)	$3 + 2 + 0$	5,000
Euclidiana ($r = 2$)	$\sqrt{9 + 4 + 0}$	3,606
Minkowski ($r = 3$)	$(27 + 8 + 0)^{1/3}$	3,271
Chebyshev ($r \to \infty$)	$\max(3, 2, 0)$	3,000

Note que $d_r$ é decrescente em $r$: quanto maior $r$, mais a distância é dominada pela maior diferença.

13.6.5 Distância de Mahalanobis

Proposta por Mahalanobis (1936), leva em conta a escala e a correlação entre as variáveis por meio da matriz de covariâncias $\boldsymbol{\Sigma}$: \[d_M(\mathbf{p}, \mathbf{q}) = \sqrt{(\mathbf{p} - \mathbf{q})^\top \boldsymbol{\Sigma}^{-1} (\mathbf{p} - \mathbf{q})}.\] Se $\boldsymbol{\Sigma} = \mathbf{I}$, ela coincide com a Euclidiana; se $\boldsymbol{\Sigma}$ é diagonal, equivale à Euclidiana após padronizar cada variável. Exemplo: com variâncias unitárias e correlação $0{,}8$, isto é, $\boldsymbol{\Sigma} = \begin{bmatrix} 1 & 0{,}8 \\ 0{,}8 & 1 \end{bmatrix}$ e $\boldsymbol{\Sigma}^{-1} = \frac{1}{0{,}36}\begin{bmatrix} 1 & -0{,}8 \\ -0{,}8 & 1 \end{bmatrix}$, as diferenças $\mathbf{u} = (1, 1)$ e $\mathbf{v} = (1, -1)$ têm a mesma norma euclidiana $\sqrt{2} \approx 1{,}414$, mas \[ d_M^2(\mathbf{u}) = \frac{1 - 0{,}8 - 0{,}8 + 1}{0{,}36} \approx 1{,}111, \qquad d_M^2(\mathbf{v}) = \frac{1 + 0{,}8 + 0{,}8 + 1}{0{,}36} = 10. \] A diferença na direção da correlação ($\mathbf{u}$) é “esperada” e conta pouco ($d_M \approx 1{,}05$); na direção contrária ($\mathbf{v}$) é atípica e conta muito ($d_M \approx 3{,}16$).

13.6.6 Aprendizado de métricas

A distância de Mahalanobis sugere uma generalização: qualquer matriz simétrica positiva definida $\mathbf{M}$ define uma distância $d_{\mathbf{M}}(\mathbf{p}, \mathbf{q}) = \sqrt{(\mathbf{p} - \mathbf{q})^\top \mathbf{M} (\mathbf{p} - \mathbf{q})}$. Escrevendo $\mathbf{M} = \mathbf{L}^\top\mathbf{L}$ (por exemplo, pela decomposição de Cholesky), temos $d_{\mathbf{M}}(\mathbf{p}, \mathbf{q}) = \|\mathbf{L}\mathbf{p} - \mathbf{L}\mathbf{q}\|$: usar $d_{\mathbf{M}}$ equivale a aplicar a transformação linear $\mathbf{L}$ aos dados e depois usar a distância euclidiana. A padronização corresponde a $\mathbf{L}$ diagonal com entradas $1/s_j$; a distância de Mahalanobis, a $\mathbf{L} = \boldsymbol{\Sigma}^{-1/2}$.

Em vez de fixar $\mathbf{L}$ a partir de estatísticas descritivas, o aprendizado de métricas (metric learning) escolhe $\mathbf{L}$ para otimizar o desempenho do k-NN nos dados de treinamento: aproximar pontos da mesma classe e afastar pontos de classes diferentes. Exemplos clássicos são a Neighbourhood Components Analysis (NCA), disponível em sklearn.neighbors.NeighborhoodComponentsAnalysis, e o Large Margin Nearest Neighbor (LMNN) de Weinberger e Saul (2009), cuja função objetivo tem estrutura de margem semelhante à do SVM (próximo capítulo). Se $\mathbf{L}$ tiver menos linhas do que colunas, a métrica aprendida também reduz a dimensão, atenuando a maldição da dimensionalidade discutida adiante.

13.6.7 Distâncias para variáveis categóricas e mistas

Distância de Hamming: para vetores de atributos categóricos, conta o número de posições em que eles diferem, $d_H(\mathbf{p}, \mathbf{q}) = \sum_i \mathbb{I}\{p_i \neq q_i\}$ (frequentemente dividida por $n$). Por exemplo, (Masculino, Solteiro, Recife, Sim) e (Feminino, Solteiro, Recife, Não) diferem em 2 das 4 posições: $d_H = 2$, ou $0{,}5$ na versão normalizada.
Distância de Gower: para dados mistos, Gower (1971) propôs combinar contribuições por variável, cada uma em $[0, 1]$: \[d_G(\mathbf{p}, \mathbf{q}) = \frac{1}{n}\sum_{i=1}^{n} \delta_i,\] em que $\delta_i = |p_i - q_i| / R_i$ se a variável $i$ é numérica ($R_i$ é a sua amplitude na base) e $\delta_i = \mathbb{I}\{p_i \neq q_i\}$ se a variável $i$ é categórica. Por exemplo, para dois clientes com idades 30 e 40 (amplitude da idade na base igual a 50), sexos diferentes e mesma cidade: $d_G = (10/50 + 1 + 0)/3 = 0{,}4$. Em R, a função daisy() do pacote cluster calcula essa distância.

Como o k-NN depende inteiramente de distâncias espaciais, as colunas preditoras que tiverem ordens de grandeza muito maiores (ex: salário de R$ 10.000,00) dominarão completamente variáveis com escalas pequenas (ex: idade de 25 anos) nos cálculos. Por isso, é obrigatório normalizar ou padronizar todas as variáveis antes de rodar o algoritmo.

13.7 Normalização e Padronização

As duas transformações mais usadas são:

Normalização min-max: leva cada variável ao intervalo $[0, 1]$, \[x'_{ij} = \frac{x_{ij} - \min_j}{\max_j - \min_j}.\] É sensível a valores extremos, pois um único outlier define o mínimo ou o máximo.
Padronização (escore z): centra cada variável na média e divide pelo desvio padrão, \[z_{ij} = \frac{x_{ij} - \bar{x}_j}{s_j}.\] É a escolha mais comum e menos sensível a outliers que a min-max (embora não seja robusta; alternativas usam mediana e amplitude interquartil).

Exemplo. Queremos saber qual cliente, B ou C, é mais parecido com A, usando idade (anos) e salário (reais):

Cliente	Idade	Salário
A	25	5.000
B	26	8.000
C	60	5.100

Sem transformação: $d(A, B) = \sqrt{1^2 + 3000^2} \approx 3000{,}0$ e $d(A, C) = \sqrt{35^2 + 100^2} \approx 105{,}9$. O cliente C é considerado muito mais próximo, apesar de ter 35 anos a mais: o salário domina a distância.
Min-max (supondo, na base de treinamento, idade entre 20 e 70 e salário entre 2.000 e 12.000): A = (0,10; 0,30), B = (0,12; 0,60), C = (0,80; 0,31). Então $d(A, B) = \sqrt{0{,}02^2 + 0{,}30^2} \approx 0{,}301$ e $d(A, C) = \sqrt{0{,}70^2 + 0{,}01^2} \approx 0{,}700$. Agora B é o mais próximo.
Escore z (supondo média 40 e desvio padrão 12 para idade; média 6.000 e desvio padrão 2.500 para salário): A = (−1,250; −0,400), B = (−1,167; 0,800), C = (1,667; −0,360). Então $d(A, B) \approx 1{,}203$ e $d(A, C) \approx 2{,}917$. Novamente B é o mais próximo.

Vazamento de dados

Os parâmetros da transformação (mínimo, máximo, média, desvio padrão) devem ser calculados apenas no conjunto de treinamento e então aplicados ao conjunto de teste. Calculá-los com todos os dados faz com que informação do teste “vaze” para o treinamento, produzindo estimativas otimistas de desempenho. Em Python, a forma mais segura de evitar isso é usar um Pipeline; em R, o argumento preProcess do caret.

13.8 A Escolha Crítica do Parâmetro $k$

A definição do hiperparâmetro $k$ determina o nível de complexidade e generalização da fronteira de decisão do modelo:

$k$ Muito Pequeno (ex: $k=1$): O modelo classifica o ponto baseando-se estritamente no vizinho mais próximo. Isso gera uma fronteira de decisão altamente complexa e recortada, tornando o algoritmo extremamente sensível a ruídos ou outliers. Apresenta alta variância (overfitting). No limite, o erro de treinamento do 1-NN é zero, pois cada ponto é seu próprio vizinho.
$k$ Muito Grande (ex: $k=100$): A fronteira de decisão torna-se excessivamente suave. Nesse caso, as classes majoritárias do banco de dados dominarão as decisões locais de vizinhança. Apresenta alto viés (underfitting). No caso extremo $k = n$, toda observação é classificada na classe mais frequente da base.

Uma prática comum para classificação binária é selecionar $k$ como um número ímpar para evitar situações de empate técnico na votação de classes. Com mais de duas classes, empates ainda podem ocorrer; as implementações os resolvem de formas diferentes (por exemplo, a função knn() do pacote class desempata aleatoriamente), e o k-NN ponderado praticamente elimina o problema.

Uma forma útil de pensar a complexidade é o número efetivo de parâmetros do k-NN, aproximadamente $n/k$ (Hastie, Tibshirani, e Friedman 2009): se as vizinhanças não se sobrepusessem, haveria $n/k$ regiões, cada uma com uma média a estimar. Assim, $1/k$ cumpre um papel análogo ao do número de parâmetros em modelos paramétricos.

13.8.1 Escolha de $k$ por validação cruzada

Na prática, $k$ é escolhido por validação cruzada com $K$ partes: para cada valor candidato de $k$ (por exemplo, $1, 3, 5, \ldots, 51$), estima-se o erro médio de classificação nas partes de validação e escolhe-se o $k$ de menor erro (ou, aplicando a regra de um erro padrão, o maior $k$ cujo erro esteja a até um erro padrão do mínimo, privilegiando a fronteira mais suave). Como o k-NN não tem etapa de treinamento propriamente dita, a validação cruzada leave-one-out é particularmente barata: basta, para cada observação, buscar seus vizinhos entre as demais (função knn.cv() do pacote class). Uma heurística frequentemente citada é $k \approx \sqrt{n}$, útil apenas como ponto de partida.

Ao representar o erro de teste contra $1/k$ (complexidade crescente), obtém-se a típica curva em “U” do dilema viés-variância discutido no Capítulo de Introdução ao Aprendizado de Máquina, enquanto o erro de treinamento decresce monotonamente até zero em $k = 1$.

13.9 Empates, Classes Desbalanceadas e Opção de Rejeição

13.9.1 Dois tipos de empate

No k-NN há dois empates distintos, que convém não confundir:

Empate de distâncias: o $k$-ésimo e o $(k+1)$-ésimo vizinhos estão à mesma distância de $\mathbf{x}_0$, de modo que o conjunto $\mathcal{N}_k(\mathbf{x}_0)$ não está bem definido. Ocorre com frequência quando as variáveis são discretas (contagens, escalas Likert, variáveis binárias). As soluções usuais são: escolher aleatoriamente entre os empatados (o que a teoria de Stone pressupõe), usar a ordem dos dados (caso do scikit-learn, que depende da ordem de armazenamento), ou incluir todos os empatados, o que faz a vizinhança ter mais de $k$ elementos (opção da função class::knn() do R, que usa todos os pontos empatados com o $k$-ésimo).
Empate de votos: duas ou mais classes recebem o mesmo número de votos. Com duas classes e $k$ ímpar isso é impossível; nos demais casos, as estratégias incluem sortear entre as classes empatadas, reduzir $k$ até o empate desaparecer, escolher a classe do vizinho mais próximo dentre as empatadas, ou usar votos ponderados pela distância, que tornam o empate um evento de probabilidade praticamente nula com variáveis contínuas.

Em análises reprodutíveis, é importante fixar a semente do gerador aleatório quando a implementação desempata por sorteio.

13.9.2 Classes desbalanceadas

Vimos que o k-NN usa implicitamente as proporções amostrais $\hat{\pi}_j = n_j/n$ como probabilidades a priori. Quando uma classe é muito mais frequente que outra (fraude, doença rara, defeito de fabricação), a classe majoritária tende a dominar quase todas as vizinhanças, e a classe minoritária raramente é prevista, ainda que a acurácia global pareça alta.

A derivação via estimação de densidade indica uma correção direta. Se quisermos usar probabilidades a priori $\pi_j$ diferentes das amostrais — por exemplo, priores iguais, ou as prevalências da população quando a amostra foi estratificada —, basta reponderar: \[ \tilde{P}(Y = j \mid \mathbf{x}_0) \;\propto\; \pi_j\, \hat{f}_j(\mathbf{x}_0) \;\propto\; \pi_j \,\frac{k_j}{n_j}. \] Com priores iguais, isso equivale a dividir cada voto pelo tamanho da classe do vizinho.

Exemplo resolvido. Uma base tem $n_1 = 900$ transações legítimas e $n_2 = 100$ fraudulentas. Para um novo ponto, entre os $k = 7$ vizinhos há $k_1 = 5$ legítimas e $k_2 = 2$ fraudes. O voto simples classifica como legítima ($5/7 \approx 0{,}71$). Com priores iguais, \[ \frac{k_1}{n_1} = \frac{5}{900} \approx 0{,}0056 \qquad \text{versus} \qquad \frac{k_2}{n_2} = \frac{2}{100} = 0{,}0200, \] e o ponto passa a ser classificado como fraude, com probabilidade reponderada $0{,}0200/(0{,}0056 + 0{,}0200) \approx 0{,}78$. Intuitivamente: encontrar 2 fraudes entre 7 vizinhos é muito mais do que o esperado ($7 \times 0{,}1 = 0{,}7$) se a região fosse “típica”.

Outras alternativas são: mudar o limiar de decisão sobre $\hat{P}(Y = 2 \mid \mathbf{x}_0)$ (escolhido, por exemplo, pela curva ROC (Fawcett 2006)); reamostrar a base de treinamento (subamostrar a classe majoritária ou sobreamostrar a minoritária; o próprio SMOTE (Chawla et al. 2002) gera exemplos sintéticos interpolando cada ponto minoritário com seus vizinhos mais próximos — uma aplicação do k-NN dentro do pré-processamento); e avaliar o modelo com métricas apropriadas, como sensibilidade, precisão, F1 ou área sob a curva ROC, em vez da acurácia.

13.9.3 Opção de rejeição

Em aplicações em que errar é caro (diagnóstico médico, por exemplo), pode ser preferível não decidir quando a evidência é fraca. Na regra $(k, l)$-NN, a classe só é atribuída se ela obtiver pelo menos $l$ dos $k$ votos, com $\lceil k/2 \rceil \leq l \leq k$; caso contrário, o caso é encaminhado a um especialista. Em termos das probabilidades estimadas, isso equivale a rejeitar quando $\max_j \hat{P}(Y = j \mid \mathbf{x}_0) < l/k$. Quanto maior $l$, menor o erro entre os casos classificados e maior a taxa de rejeição.

13.10 A Maldição da Dimensionalidade

A expressão maldição da dimensionalidade (curse of dimensionality), cunhada por Bellman (1961), designa o conjunto de fenômenos que tornam métodos locais, como o k-NN, ineficazes em dimensões altas. A ideia de “vizinhança local” que fundamenta o método simplesmente deixa de fazer sentido quando $p$ é grande. Vejamos três argumentos quantitativos (Hastie, Tibshirani, e Friedman 2009).

1. Vizinhanças locais deixam de ser locais. Suponha dados uniformemente distribuídos no hipercubo unitário $[0, 1]^p$ e que queremos uma vizinhança cúbica que capture uma fração $r$ das observações. Como o volume é $\ell^p$, o lado necessário é $\ell = r^{1/p}$:

Dimensão $p$	Lado para capturar 10%	Lado para capturar 1%
1	0,10	0,01
2	0,32	0,10
3	0,46	0,22
10	0,79	0,63
100	0,98	0,95

Em dimensão 10, para usar apenas 1% dos dados como vizinhos precisamos cobrir 63% da amplitude de cada variável: a “vizinhança” não é mais local, e o viés da estimativa aumenta.

2. O volume se concentra nos “cantos”. A razão entre o volume da bola de raio $1/2$ inscrita no cubo unitário e o volume do cubo é $V_p = \frac{\pi^{p/2}}{\Gamma(p/2 + 1)} \left(\frac{1}{2}\right)^p$, que vale $0{,}785$ para $p = 2$, $0{,}524$ para $p = 3$, $0{,}164$ para $p = 5$, $0{,}0025$ para $p = 10$ e cerca de $2{,}5 \times 10^{-8}$ para $p = 20$. Em alta dimensão, quase todos os pontos ficam longe do centro e perto da fronteira do domínio, onde a predição exige extrapolação.

3. As distâncias se concentram. Para $N = 500$ pontos uniformes na bola unitária $p$-dimensional, a mediana da distância da origem ao ponto mais próximo é $\left(1 - (1/2)^{1/N}\right)^{1/p}$, que vale cerca de $0{,}0014$ para $p = 1$, mas $0{,}52$ para $p = 10$ — o vizinho mais próximo está, tipicamente, a mais da metade do caminho até a borda. Mais geralmente, Beyer et al. (1999) mostraram que, sob condições amplas, a razão entre a distância ao ponto mais distante e ao mais próximo tende a 1 quando $p \to \infty$: todos os pontos ficam aproximadamente à mesma distância, e a noção de “mais próximo” perde significado.

Teorema (concentração de distâncias; Beyer et al., 1999)

Sejam $\mathbf{X}_{p,1}, \ldots, \mathbf{X}_{p,N}$ pontos de dados e $\mathbf{Q}_p$ um ponto de consulta em $\mathbb{R}^p$, e sejam $D_{\min,p}$ e $D_{\max,p}$ a menor e a maior distância de $\mathbf{Q}_p$ aos $N$ pontos. Se, para alguma potência $r > 0$, a distância $D_p = \|\mathbf{X}_p - \mathbf{Q}_p\|$ satisfaz \[ \lim_{p \to \infty} \operatorname{Var}\!\left(\frac{D_p^{\,r}}{\mathbb{E}[D_p^{\,r}]}\right) = 0, \] então, para todo $\epsilon > 0$ e $N$ fixo, \[ \lim_{p \to \infty} P\big(D_{\max,p} \leq (1 + \epsilon)\, D_{\min,p}\big) = 1. \]

A ideia da prova é que, se a variância relativa vai a zero, cada $D_p^{\,r}/\mathbb{E}[D_p^{\,r}]$ converge em probabilidade para 1 (desigualdade de Chebyshev); como há apenas $N$ pontos, o máximo e o mínimo dessas razões também convergem para 1, e a razão $D_{\max,p}/D_{\min,p}$ converge para 1.

Exemplo resolvido: verificando a condição para dados uniformes. Sejam $\mathbf{X}$ e $\mathbf{Q}$ independentes e uniformes em $[0, 1]^p$, e considere o quadrado da distância euclidiana ($r = 2$), $D^2 = \sum_{j=1}^{p} (X_j - Q_j)^2$, uma soma de $p$ termos independentes e identicamente distribuídos. A diferença $T = X_j - Q_j$ tem distribuição triangular em $[-1, 1]$, com densidade $1 - |t|$. Então \[ \mathbb{E}[T^2] = 2\int_0^1 t^2(1 - t)\,dt = 2\left(\frac{1}{3} - \frac{1}{4}\right) = \frac{1}{6}, \qquad \mathbb{E}[T^4] = 2\int_0^1 t^4(1 - t)\,dt = 2\left(\frac{1}{5} - \frac{1}{6}\right) = \frac{1}{15}, \] de modo que $\operatorname{Var}(T^2) = \frac{1}{15} - \frac{1}{36} = \frac{7}{180}$. Logo $\mathbb{E}[D^2] = p/6$, $\operatorname{Var}(D^2) = 7p/180$ e o coeficiente de variação de $D^2$ é \[ \frac{\sqrt{\operatorname{Var}(D^2)}}{\mathbb{E}[D^2]} = \frac{\sqrt{7p/180}}{p/6} = \sqrt{\frac{1{,}4}{p}} \xrightarrow[p \to \infty]{} 0. \] A condição do teorema vale, e a dispersão relativa das distâncias cai como $1/\sqrt{p}$:

$p$	1	10	100	1000
CV de $D^2$	1,183	0,374	0,118	0,037

Em $p = 1000$, as distâncias ao quadrado variam tipicamente apenas cerca de 4% em torno da média $p/6$: o “vizinho mais próximo” é quase tão distante quanto o mais distante. (Uma simulação com $2 \times 10^5$ pares confirma esses valores com três casas decimais.)

O teorema não se aplica quando a dimensão intrínseca dos dados é baixa (por exemplo, dados que vivem perto de uma superfície de dimensão pequena em $\mathbb{R}^p$) ou quando as coordenadas são fortemente dependentes. É por isso que o k-NN pode funcionar bem em imagens ou textos com milhares de variáveis: o que importa é a dimensão intrínseca, não o número de colunas.

Uma consequência é que, para manter a mesma densidade de amostragem, o tamanho amostral precisa crescer exponencialmente com $p$: se 100 pontos cobrem bem um intervalo, seriam necessários $100^{10}$ pontos para a mesma densidade em 10 dimensões. Na prática, o k-NN funciona bem com poucas variáveis relevantes; com muitas, recomenda-se seleção de variáveis, redução de dimensionalidade (por exemplo, componentes principais) ou métricas aprendidas. Variáveis irrelevantes são especialmente danosas, pois contribuem para a distância com puro ruído.

13.11 Custo Computacional e Estruturas de Dados

Na implementação ingênua (força bruta), classificar um ponto exige calcular $n$ distâncias em $\mathbb{R}^p$, com custo $O(np)$, e selecionar as $k$ menores, com custo $O(n)$ (ou $O(n \log k)$ com uma fila de prioridade). Para $m$ pontos de teste, o custo total é $O(mnp)$, e o armazenamento é $O(np)$. Com milhões de observações, isso se torna proibitivo, e estruturas de dados espaciais são usadas para acelerar a busca:

KD-tree (Bentley 1975): árvore binária que particiona recursivamente o espaço por hiperplanos perpendiculares aos eixos, alternando as coordenadas (em geral, cortando na mediana). A construção custa $O(n \log n)$ e, em baixa dimensão, a busca de vizinhos custa em média $O(\log n)$, pois ramos inteiros podem ser descartados quando a distância ao hiperplano de corte supera a distância ao melhor vizinho encontrado. Sua eficiência degrada com $p$; acima de algumas dezenas de dimensões, ela se aproxima da força bruta.
Ball tree: particiona os dados em hiperesferas aninhadas (cada nó guarda um centro e um raio). Usa a desigualdade triangular para descartar bolas inteiras e costuma se comportar melhor que a KD-tree em dimensões moderadas e com métricas gerais.
Busca aproximada (approximate nearest neighbors): métodos como locality-sensitive hashing e grafos de proximidade sacrificam a exatidão por grande ganho de velocidade, sendo usados em sistemas de recomendação e busca por similaridade em larga escala.

No scikit-learn, o argumento algorithm aceita "brute", "kd_tree", "ball_tree" ou "auto" (padrão, que escolhe com base nos dados), e leaf_size controla o tamanho das folhas dessas árvores.

13.11.1 Por que a KD-tree degrada com a dimensão?

Friedman, Bentley, e Finkel (1977) mostraram que, para $n$ grande e dimensão fixa, o número esperado de nós visitados pela KD-tree é $O(\log n)$, mas com uma constante que cresce exponencialmente com $p$. A razão é geométrica: a bola de busca centrada em $\mathbf{x}_0$, com raio igual à distância ao melhor vizinho encontrado, intersecta um número de células da árvore que cresce exponencialmente com $p$, e cada célula intersectada precisa ser examinada. Uma regra prática frequentemente citada é que a KD-tree só compensa quando $n \gg 2^p$; com $p = 30$, isso exigiria $n$ muito maior que $10^9$. Em dimensões maiores, a concentração de distâncias faz com que quase nenhum ramo possa ser descartado, e a busca “exata e rápida” deixa de existir.

13.11.2 Busca aproximada: locality-sensitive hashing

A saída para alta dimensão é abrir mão da exatidão. O hashing sensível à localidade (LSH) (Indyk e Motwani 1998) usa funções de hash aleatórias $h$ com a propriedade de que pontos próximos colidem (recebem o mesmo código) com probabilidade alta, e pontos distantes, com probabilidade baixa. Na busca, só se calculam distâncias para os pontos que colidem com a consulta.

Um exemplo elegante, para a similaridade do cosseno, são os hiperplanos aleatórios (Charikar 2002): sorteia-se $\mathbf{g} \sim N(\mathbf{0}, \mathbf{I}_p)$ e define-se $h(\mathbf{x}) = \operatorname{sign}(\mathbf{g}^\top\mathbf{x})$. Se o ângulo entre $\mathbf{x}$ e $\mathbf{z}$ é $\theta$, então \[ P\big(h(\mathbf{x}) = h(\mathbf{z})\big) = 1 - \frac{\theta}{\pi}. \] Justificativa. Por simetria rotacional da normal, basta olhar o plano gerado por $\mathbf{x}$ e $\mathbf{z}$: a projeção de $\mathbf{g}$ nesse plano tem direção uniforme, e o hiperplano $\{\mathbf{u}: \mathbf{g}^\top\mathbf{u} = 0\}$ separa $\mathbf{x}$ de $\mathbf{z}$ exatamente quando a reta que ele determina no plano cai dentro do ângulo entre eles, o que ocorre com probabilidade $\theta/\pi$.

Uma única função distingue mal; por isso, concatenam-se $b$ funções (o código tem $b$ bits, e uma colisão exige que todos coincidam, com probabilidade $P^b$) e repete-se o processo em $L$ tabelas independentes (basta colidir em uma). A probabilidade de um par ser examinado é \[ P_{\text{cand}} = 1 - \left(1 - P^b\right)^L. \]

Exemplo resolvido. Com $b = 10$ bits e $L = 20$ tabelas:

um par próximo, com $\theta = 15^\circ$, tem $P = 1 - 15/180 \approx 0{,}917$, $P^{10} \approx 0{,}419$ e $P_{\text{cand}} = 1 - 0{,}581^{20} \approx 0{,}99998$;
um par distante, com $\theta = 90^\circ$, tem $P = 0{,}5$, $P^{10} \approx 0{,}00098$ e $P_{\text{cand}} = 1 - 0{,}99902^{20} \approx 0{,}019$.

Ou seja, praticamente todo vizinho próximo é encontrado, enquanto apenas cerca de 2% dos pontos ortogonais à consulta precisam ter sua distância calculada. Os parâmetros $b$ e $L$ controlam a troca entre velocidade e exatidão. Métodos modernos baseados em grafos de proximidade, como o HNSW (Malkov e Yashunin 2020), dominam hoje as aplicações de busca por similaridade em grande escala (por exemplo, a recuperação de documentos por embeddings em sistemas de linguagem).

13.12 Redução do Conjunto de Treinamento: Edição e Condensação

Uma alternativa às estruturas de busca é reduzir o próprio conjunto de treinamento, guardando apenas os pontos que importam para a decisão. Duas ideias clássicas, com objetivos complementares, são a edição e a condensação.

Edição de Wilson (Wilson 1972). Objetivo: remover ruído. Para cada ponto de treinamento, classifica-se o ponto com o k-NN (tipicamente $k = 3$) usando os demais pontos; se a classificação discorda do rótulo, o ponto é marcado. Ao final, todos os pontos marcados são removidos. Pontos mal rotulados no interior de regiões de outra classe, e pontos em regiões de grande sobreposição, tendem a ser eliminados, de modo que as fronteiras ficam mais suaves e o 1-NN aplicado à base editada se comporta como um k-NN.

Condensação de Hart (CNN) (Hart 1968). Objetivo: remover redundância. Inicia-se um conjunto $S$ com um ponto; percorre-se a base, e cada ponto que o 1-NN baseado em $S$ classifica incorretamente é adicionado a $S$. Repetem-se as passagens até que uma passagem completa não adicione nenhum ponto. Ao final, o 1-NN baseado em $S$ classifica corretamente toda a base (diz-se que $S$ é consistente). Pontos no interior das regiões de cada classe são descartados, pois são classificados corretamente por protótipos já presentes; sobram, sobretudo, pontos perto da fronteira.

Os dois procedimentos são tipicamente usados em sequência: primeiro edita-se (para que a condensação não preserve pontos ruidosos, que ela trataria como “fronteira”) e depois condensa-se.

Exemplo resolvido: edição seguida de condensação

Considere dez pontos em uma dimensão:

$x$	0,9	1,9	2,5	3,2	4,0	5,1	7,2	8,1	8,9	10,0
Classe	A	A	B	A	A	A	B	B	B	B

O ponto $x = 2{,}5$ (classe B) é, visivelmente, um ruído dentro da região de A.

Edição de Wilson com $k = 3$. Para $x = 2{,}5$, os três vizinhos entre os demais pontos são $1{,}9$ (distância $0{,}6$), $3{,}2$ ($0{,}7$) e $4{,}0$ ($1{,}5$), todos da classe A: a predição A discorda do rótulo B, e o ponto é removido. Para os vizinhos do ruído, a situação é diferente: $x = 1{,}9$ tem vizinhos $2{,}5$ (B), $0{,}9$ (A) e $3{,}2$ (A), e é corretamente classificado como A, por 2 votos a 1; o mesmo ocorre com $x = 3{,}2$ (vizinhos $2{,}5$ B, $4{,}0$ A e $1{,}9$ A). Verificando os demais pontos, todos são classificados corretamente, e apenas o ruído é removido.

Condensação de Hart sobre a base editada, percorrida da esquerda para a direita, com $S = \{0{,}9\}$ inicialmente:

1ª passagem: $1{,}9$; $3{,}2$; $4{,}0$; $5{,}1$ são classificados como A pelo único protótipo, corretamente. O ponto $7{,}2$ (B) é classificado como A, erro: entra em $S$. Os pontos $8{,}1$; $8{,}9$; $10{,}0$ têm $7{,}2$ como vizinho mais próximo em $S$ e são classificados corretamente.
2ª passagem: agora $S = \{0{,}9;\ 7{,}2\}$. O ponto $5{,}1$ está a $4{,}2$ de $0{,}9$ e a $2{,}1$ de $7{,}2$, e seria classificado como B, erro: entra em $S$. Os demais estão corretos.
3ª passagem: com $S = \{0{,}9;\ 5{,}1;\ 7{,}2\}$, nenhum erro. Fim.

O conjunto condensado tem 3 dos 9 pontos e reproduz exatamente a fronteira do 1-NN da base editada, o ponto médio $(5{,}1 + 7{,}2)/2 = 6{,}15$. Observe que o protótipo $0{,}9$ é, na verdade, dispensável: o CNN garante consistência, mas não minimalidade, e o resultado depende da ordem em que os pontos são percorridos.

13.13 Vantagens e Limitações

Vantagens:

Simplicidade conceitual e de implementação; nenhuma hipótese sobre a forma da fronteira de decisão.
Fronteiras de decisão arbitrariamente complexas e consistência universal quando $k$ cresce adequadamente.
Adaptação natural a problemas multiclasse e à regressão.
Incorporação imediata de novos dados (basta adicioná-los à base).
Fundamentação teórica sólida (Cover e Hart; consistência de Stone).

Limitações:

Predição lenta e alto consumo de memória em bases grandes.
Sensibilidade à escala das variáveis, a variáveis irrelevantes e à métrica escolhida.
Forte degradação em alta dimensão.
Dificuldade com classes desbalanceadas: a classe majoritária tende a dominar as vizinhanças (o k-NN ponderado e a reamostragem ajudam).
Não fornece um modelo interpretável nem importâncias de variáveis.

13.14 Implementação em R

13.14.1 Conferindo o exemplo à mão

treino_ex <- data.frame(
  x1 = c(1, 2, 4, 3, 6, 4, 0, 5),
  x2 = c(1, 3, 2, 6, 5, 4, 4, 2),
  classe = factor(c("A", "A", "A", "B", "B", "B", "B", "A")),
  row.names = paste0("P", 1:8)
)
x0 <- c(3, 4)

d <- sqrt((treino_ex$x1 - x0[1])^2 + (treino_ex$x2 - x0[2])^2)
ordem <- order(d)
data.frame(ponto = rownames(treino_ex)[ordem], dist = round(d[ordem], 3),
           classe = treino_ex$classe[ordem])

library(class)
for (k in c(1, 3, 5)) {
  pred <- knn(train = treino_ex[, 1:2], test = matrix(x0, nrow = 1),
              cl = treino_ex$classe, k = k, prob = TRUE)
  cat("k =", k, "-> classe", as.character(pred),
      "| proporção de votos:", attr(pred, "prob"), "\n")
}
#> k = 1 -> classe B | proporção de votos: 1
#> k = 3 -> classe B | proporção de votos: 0.6666667
#> k = 5 -> classe A | proporção de votos: 0.6

13.14.2 `class::knn` com padronização e escolha de $k$ por LOOCV

library(class)

set.seed(123)
idx    <- sample(seq_len(nrow(iris)), size = 0.7 * nrow(iris))
treino <- iris[idx, ]
teste  <- iris[-idx, ]

# Padronização com parâmetros do TREINO aplicados ao teste
x_treino <- scale(treino[, 1:4])
centro   <- attr(x_treino, "scaled:center")
escala   <- attr(x_treino, "scaled:scale")
x_teste  <- scale(teste[, 1:4], center = centro, scale = escala)

# Validação cruzada leave-one-out para vários valores de k
ks <- seq(1, 31, by = 2)
erro_loo <- sapply(ks, function(k) {
  pred <- knn.cv(train = x_treino, cl = treino$Species, k = k)
  mean(pred != treino$Species)
})
plot(ks, erro_loo, type = "b", xlab = "k", ylab = "Erro LOOCV")
k_otimo <- ks[which.min(erro_loo)]
k_otimo

# Ajuste final e avaliação
pred <- knn(train = x_treino, test = x_teste, cl = treino$Species,
            k = k_otimo, prob = TRUE)
table(Predito = pred, Real = teste$Species)
mean(pred == teste$Species)

13.14.3 `caret` com pré-processamento e validação cruzada repetida

O pacote caret (Kuhn 2008) integra pré-processamento, validação cruzada e ajuste de hiperparâmetros, aplicando a padronização corretamente dentro de cada partição.

library(caret)

ctrl <- trainControl(method = "repeatedcv", number = 10, repeats = 5)

set.seed(123)
modelo_knn <- train(Species ~ ., data = treino,
                    method = "knn",
                    preProcess = c("center", "scale"),
                    tuneGrid = data.frame(k = seq(1, 31, by = 2)),
                    trControl = ctrl)

modelo_knn          # acurácia média por valor de k
plot(modelo_knn)    # acurácia de validação cruzada versus k

pred <- predict(modelo_knn, newdata = teste)
confusionMatrix(pred, teste$Species)

# Probabilidades estimadas (frações de vizinhos)
head(predict(modelo_knn, newdata = teste, type = "prob"))

13.14.4 Nadaraya–Watson e k-NN com probabilidades a priori

O código abaixo reproduz o exemplo resolvido de Nadaraya–Watson e implementa a reponderação dos votos por probabilidades a priori discutida na seção sobre classes desbalanceadas.

# Nadaraya-Watson com núcleo gaussiano
nw <- function(x, y, x0, h) {
  w <- dnorm((x - x0) / h)          # a constante 1/sqrt(2*pi) se cancela
  sum(w * y) / sum(w)
}
x <- c(1, 2, 3, 4, 5); y <- c(2, 4, 5, 4, 6)
sapply(c(0.5, 1, 3), function(h) round(nw(x, y, 2.5, h), 3))
#> [1] 4.473 4.131 4.143

# k-NN com reponderação por probabilidades a priori
knn_priores <- function(X, cl, x0, k, priores) {
  d   <- sqrt(colSums((t(X) - x0)^2))
  viz <- cl[order(d)[1:k]]
  kj  <- table(factor(viz, levels = levels(cl)))   # votos por classe
  nj  <- table(cl)                                  # tamanhos das classes
  esc <- priores * kj / nj
  esc / sum(esc)                                    # probabilidades reponderadas
}
set.seed(10)
X  <- rbind(matrix(rnorm(1800), ncol = 2), matrix(rnorm(200, mean = 1.5), ncol = 2))
cl <- factor(rep(c("legitima", "fraude"), c(900, 100)),
             levels = c("legitima", "fraude"))
knn_priores(X, cl, x0 = c(1.2, 1.2), k = 15, priores = c(0.5, 0.5))

Experimente trocar priores = c(0.5, 0.5) pelas proporções amostrais c(0.9, 0.1): o resultado volta a ser exatamente a fração de votos do k-NN usual.

13.15 Implementação em Python

13.15.1 Implementação do zero com NumPy

import numpy as np
from collections import Counter

def knn_predict(X_treino, y_treino, x0, k=3, ponderado=False):
    d = np.sqrt(((X_treino - x0) ** 2).sum(axis=1))   # distâncias euclidianas
    viz = np.argsort(d)[:k]                            # índices dos k vizinhos
    if not ponderado:
        return Counter(y_treino[viz]).most_common(1)[0][0]
    pesos = {}
    for i in viz:
        pesos[y_treino[i]] = pesos.get(y_treino[i], 0.0) + 1.0 / d[i]
    return max(pesos, key=pesos.get)

X_ex = np.array([[1, 1], [2, 3], [4, 2], [3, 6], [6, 5], [4, 4], [0, 4], [5, 2]])
y_ex = np.array(["A", "A", "A", "B", "B", "B", "B", "A"])
x0 = np.array([3, 4])
for k in (1, 3, 5):
    print(k, knn_predict(X_ex, y_ex, x0, k), knn_predict(X_ex, y_ex, x0, k, ponderado=True))
#> 1 B B
#> 3 B B
#> 5 A A

13.15.2 `KNeighborsClassifier` com `Pipeline` e `StandardScaler`

O conjunto wine tem variáveis com escalas muito diferentes (por exemplo, teor de prolina na casa das centenas e matiz em torno de 1), o que o torna ideal para ilustrar o efeito da padronização.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split, GridSearchCV, cross_val_score, StratifiedKFold
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler, MinMaxScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report

X, y = load_wine(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(
    X, y, test_size=0.3, stratify=y, random_state=42)
cv = StratifiedKFold(n_splits=10, shuffle=True, random_state=42)

# 1) Efeito da escala: sem transformação x min-max x escore z
modelos = {
    "sem escala": KNeighborsClassifier(n_neighbors=5),
    "min-max": Pipeline([("esc", MinMaxScaler()), ("knn", KNeighborsClassifier(n_neighbors=5))]),
    "escore z": Pipeline([("esc", StandardScaler()), ("knn", KNeighborsClassifier(n_neighbors=5))]),
}
for nome, m in modelos.items():
    acc = cross_val_score(m, X_tr, y_tr, cv=cv).mean()
    print(f"{nome:>10}: acurácia CV = {acc:.3f}")

# 2) Busca em grade: k, ponderação e métrica de Minkowski (p=1 Manhattan, p=2 Euclidiana)
pipe = Pipeline([("esc", StandardScaler()), ("knn", KNeighborsClassifier())])
grade = {
    "knn__n_neighbors": list(range(1, 32, 2)),
    "knn__weights": ["uniform", "distance"],
    "knn__p": [1, 2],
}
busca = GridSearchCV(pipe, grade, cv=cv, scoring="accuracy", n_jobs=-1)
busca.fit(X_tr, y_tr)
print("Melhores hiperparâmetros:", busca.best_params_)
print("Acurácia CV:", round(busca.best_score_, 3))

y_pred = busca.predict(X_te)
print("Acurácia teste:", accuracy_score(y_te, y_pred))
print(classification_report(y_te, y_pred))

# 3) Curva de erro de treino e de validação em função de k
ks = list(range(1, 52, 2))
erro_tr, erro_cv = [], []
for k in ks:
    m = Pipeline([("esc", StandardScaler()), ("knn", KNeighborsClassifier(n_neighbors=k))])
    m.fit(X_tr, y_tr)
    erro_tr.append(1 - m.score(X_tr, y_tr))
    erro_cv.append(1 - cross_val_score(m, X_tr, y_tr, cv=cv).mean())

plt.plot(ks, erro_tr, marker="o", label="Treino")
plt.plot(ks, erro_cv, marker="s", label="Validação cruzada")
plt.xlabel("k"); plt.ylabel("Taxa de erro"); plt.legend(); plt.show()

13.15.3 k-NN para regressão

import numpy as np
from sklearn.neighbors import KNeighborsRegressor
from sklearn.model_selection import GridSearchCV

rng = np.random.default_rng(0)
x = np.sort(rng.uniform(0, 2 * np.pi, 200)).reshape(-1, 1)
y = np.sin(x).ravel() + rng.normal(0, 0.3, 200)

busca = GridSearchCV(KNeighborsRegressor(),
                     {"n_neighbors": range(1, 41), "weights": ["uniform", "distance"]},
                     cv=5, scoring="neg_root_mean_squared_error")
busca.fit(x, y)
print(busca.best_params_, "RMSE CV:", round(-busca.best_score_, 3))

13.15.4 Simulando a concentração de distâncias

import numpy as np

rng = np.random.default_rng(1)
n = 1000
for p in [1, 2, 10, 100, 1000]:
    X = rng.uniform(size=(n, p))
    x0 = rng.uniform(size=p)
    d = np.sqrt(((X - x0) ** 2).sum(axis=1))
    print(f"p={p:>4}: (d_max - d_min) / d_min = {(d.max() - d.min()) / d.min():.3f}")

À medida que $p$ cresce, a razão $(d_{\max} - d_{\min})/d_{\min}$ diminui drasticamente, ilustrando o resultado de Beyer et al. (1999).

13.15.5 Edição de Wilson e condensação de Hart

A implementação a seguir reproduz o exemplo resolvido da seção de redução do conjunto de treinamento. Ela é deliberadamente simples (reajusta um k-NN a cada ponto) e serve apenas para fins didáticos; o pacote imbalanced-learn oferece versões eficientes (EditedNearestNeighbours e CondensedNearestNeighbour).

import numpy as np
from sklearn.neighbors import KNeighborsClassifier

def edicao_wilson(X, y, k=3):
    """Remove os pontos mal classificados pelo k-NN dos demais pontos."""
    manter = np.ones(len(y), dtype=bool)
    for i in range(len(y)):
        outros = np.arange(len(y)) != i
        knn = KNeighborsClassifier(n_neighbors=k).fit(X[outros], y[outros])
        manter[i] = knn.predict(X[i:i + 1])[0] == y[i]
    return X[manter], y[manter]

def condensacao_hart(X, y):
    """Condensed Nearest Neighbor: subconjunto consistente para o 1-NN."""
    S = [0]
    mudou = True
    while mudou:
        mudou = False
        for i in range(len(y)):
            if i in S:
                continue
            knn = KNeighborsClassifier(n_neighbors=1).fit(X[S], y[S])
            if knn.predict(X[i:i + 1])[0] != y[i]:
                S.append(i)
                mudou = True
    return X[S], y[S]

x = np.array([0.9, 1.9, 2.5, 3.2, 4.0, 5.1, 7.2, 8.1, 8.9, 10.0]).reshape(-1, 1)
y = np.array(list("AABAAABBBB"))
Xe, ye = edicao_wilson(x, y, k=3)
Xc, yc = condensacao_hart(Xe, ye)
print("Editado:   ", Xe.ravel(), ye)
print("Condensado:", Xc.ravel(), yc)
#> Editado:    [ 0.9  1.9  3.2  4.   5.1  7.2  8.1  8.9 10. ] ['A' 'A' 'A' 'A' 'A' 'B' 'B' 'B' 'B']
#> Condensado: [0.9 7.2 5.1] ['A' 'B' 'A']

13.15.6 Verificando por simulação a decomposição viés-variância

O código abaixo simula o exemplo resolvido de $f(x) = x^2$ com $\sigma = 0{,}1$ e confirma, por Monte Carlo, os erros esperados calculados analiticamente.

import numpy as np

rng = np.random.default_rng(42)
xs = np.round(np.arange(0, 1.01, 0.1), 1)
x0, sigma = 0.52, 0.1
ordem = np.argsort(np.abs(xs - x0), kind="stable")
for k in (1, 3, 5, 7, 9, 11):
    viz = ordem[:k]
    Y = xs[viz] ** 2 + rng.normal(0, sigma, size=(100_000, k))  # respostas dos vizinhos
    pred = Y.mean(axis=1)
    y0 = x0 ** 2 + rng.normal(0, sigma, size=100_000)          # nova observação
    print(f"k = {k:>2}: erro simulado = {np.mean((y0 - pred) ** 2):.4f}")
#> k =  1: erro simulado = 0.0206
#> k =  3: erro simulado = 0.0135
#> k =  5: erro simulado = 0.0119
#> k =  7: erro simulado = 0.0117
#> k =  9: erro simulado = 0.0132
#> k = 11: erro simulado = 0.0171

Os valores coincidem com a tabela teórica ($0{,}0204$; $0{,}0135$; $0{,}0120$; $0{,}0118$; $0{,}0133$; $0{,}0172$) a menos do erro de Monte Carlo.

13.16 Resumo do Capítulo

O k-NN estima $P(Y = j \mid \mathbf{X} = \mathbf{x}_0)$ pela fração dos $k$ vizinhos mais próximos pertencentes à classe $j$ e imita o classificador de Bayes, que escolhe a classe de maior probabilidade a posteriori e tem o menor erro possível, $R^{*}$.
O k-NN é consistente quando $k \to \infty$ e $k/n \to 0$; o 1-NN tem erro assintótico entre $R^{*}$ e $2R^{*}$ (Cover e Hart).
A escolha da métrica (Euclidiana, Manhattan, Minkowski, Chebyshev, Mahalanobis, Hamming, Gower) e a padronização das variáveis são decisivas; os parâmetros de padronização devem ser estimados apenas no treinamento.
$k$ controla o equilíbrio viés-variância (número efetivo de parâmetros $\approx n/k$) e é escolhido por validação cruzada; o k-NN ponderado reduz a sensibilidade a $k$ e os empates.
Para regressão, a predição é a média (ou média ponderada) das respostas dos vizinhos, com variância $\sigma^2/k$.
Em alta dimensão, as vizinhanças deixam de ser locais e as distâncias se concentram (maldição da dimensionalidade).
A busca de vizinhos por força bruta custa $O(np)$ por ponto; KD-trees e ball trees aceleram a busca em dimensão baixa a moderada.
Geometricamente, o 1-NN particiona o espaço em células de Voronoi; com a distância euclidiana, as células são poliedros convexos e a fronteira de decisão é linear por partes.
A distância de Minkowski $d_r$ é uma métrica se, e somente se, $r \geq 1$; a prova decorre da convexidade de $|t|^r$, e o caso $r < 1$ viola a desigualdade triangular.
O k-NN pode ser derivado como um classificador de Bayes plug-in com densidades estimadas por vizinhos; ele usa implicitamente as proporções amostrais como priores, o que explica sua dificuldade com classes desbalanceadas e sugere a correção $\pi_j k_j / n_j$.
O teorema de Stone garante consistência universal quando $k \to \infty$ e $k/n \to 0$; a desigualdade plug-in $L(g) - R^{*} \leq 2\,\mathbb{E}|\hat{\eta} - \eta|$ transfere a consistência da regressão para a classificação.
Para funções lipschitzianas, o melhor $k$ cresce como $n^{2/(p+2)}$ e o erro quadrático cai como $n^{-2/(p+2)}$: a taxa piora drasticamente com a dimensão.
Como suavizador linear, o k-NN tem $\operatorname{tr}(\mathbf{S}) = n/k$ graus de liberdade efetivos; o estimador de Nadaraya–Watson generaliza o k-NN substituindo o corte abrupto por pesos suaves.
O teorema de concentração de distâncias formaliza a perda de contraste entre vizinhos em alta dimensão; para dados uniformes, o coeficiente de variação de $D^2$ é $\sqrt{1{,}4/p}$.
A edição de Wilson remove ruído, a condensação de Hart remove redundância, e a busca aproximada (LSH, grafos de proximidade) torna o método viável em grande escala.

13.17 Exercícios Propostos

Mostre que o classificador de Bayes minimiza $P\{Y \neq f(\mathbf{X})\}$ entre todos os classificadores. (Dica: condicione em $\mathbf{X} = \mathbf{x}$.)
Considere um problema binário em que $\eta(x) = P(Y = 1 \mid X = x) = 0{,}2$ para todo $x$. Calcule a taxa de erro de Bayes e o erro assintótico do 1-NN. Verifique o limite de Cover e Hart.
Para $p = (2, -1, 4)$ e $q = (5, 3, 4)$, calcule as distâncias de Manhattan, Euclidiana, Minkowski com $r = 3$ e Chebyshev.
Prove que, para $r \geq 1$, $d_\infty(p, q) \leq d_r(p, q) \leq n^{1/r} d_\infty(p, q)$, e conclua que $d_r \to d_\infty$ quando $r \to \infty$.
No exemplo numérico do capítulo, classifique o ponto $\mathbf{x}_0 = (4, 3)$ com $k = 1, 3$ e $5$, usando voto simples e voto ponderado por $1/d$.
Mostre que, se $\boldsymbol{\Sigma}$ é diagonal, a distância de Mahalanobis equivale à distância Euclidiana calculada sobre as variáveis padronizadas.
Calcule a distância de Gower entre dois imóveis: (área = 80 m², bairro = Boa Viagem, garagem = sim) e (área = 120 m², bairro = Casa Forte, garagem = sim), sabendo que a amplitude da área na base é 200 m².
Explique por que o erro de treinamento do 1-NN é zero (na ausência de pontos repetidos com classes diferentes) e por que isso não indica um bom modelo.
Usando a decomposição $\text{Err}(\mathbf{x}_0) = \sigma^2 + \text{viés}^2 + \sigma^2/k$, discuta o que acontece com cada termo quando $k = 1$ e quando $k = n$.
Em dados uniformes no hipercubo $[0,1]^p$, qual o lado do subcubo necessário para capturar 5% dos dados quando $p = 5$ e $p = 50$? Interprete.
Por que variáveis irrelevantes prejudicam mais o k-NN do que uma árvore de decisão? Relacione sua resposta com a seleção implícita de variáveis feita pelas árvores.
(Prático, R) Usando caret, ajuste o k-NN ao conjunto Pima.tr do pacote MASS, com e sem preProcess = c("center", "scale"), e compare as acurácias de validação cruzada e os valores de $k$ escolhidos.
(Prático, Python) Adicione ao conjunto load_wine() 20 colunas de ruído uniforme e compare a acurácia de validação cruzada do k-NN com a de uma Floresta Aleatória antes e depois da inclusão. Explique o resultado à luz da maldição da dimensionalidade.
(Prático, Python) Compare o tempo de predição de KNeighborsClassifier com algorithm="brute", "kd_tree" e "ball_tree" para $n = 50.000$ pontos simulados em $p = 2$, $10$ e $50$ dimensões.
Mostre que, com a distância de Manhattan, o conjunto dos pontos equidistantes de $(0, 0)$ e $(2, 1)$ em $\mathbb{R}^2$ não é uma reta. O que isso implica sobre a forma das células de Voronoi com essa distância?
Encontre a equação da face de Voronoi entre os pontos P3 $= (4, 2)$ e P6 $= (4, 4)$ do exemplo do capítulo e verifique se ela faz parte da fronteira de decisão do 1-NN.
Use o contraexemplo do capítulo para mostrar que $d_{1/2}$ não é uma métrica e calcule a razão $d_{1/2}(\mathbf{p}, \mathbf{s}) / [d_{1/2}(\mathbf{p}, \mathbf{q}) + d_{1/2}(\mathbf{q}, \mathbf{s})]$ para um $r \in (0, 1)$ genérico. Para que valor ela tende quando $r \to 1$?
Suponha $\eta(\mathbf{x}) = 0{,}05$ em 80% do espaço e $\eta(\mathbf{x}) = 0{,}4$ nos 20% restantes. Calcule $R^{*}$, o erro assintótico do 1-NN e o limite $2R^{*}(1 - R^{*})$.
Mostre que, se $\hat{\eta}(\mathbf{x}) = \eta(\mathbf{x}) + 0{,}1$ para todo $\mathbf{x}$, a desigualdade plug-in garante $L(g) - R^{*} \leq 0{,}2$. Construa um exemplo em que o excesso de risco é de fato positivo e outro em que é zero.
A partir da aproximação $\text{EQM}(k) \approx L^2 (k/n)^{2/p} + \sigma^2/k$, encontre explicitamente o $k$ ótimo (com as constantes) e o EQM correspondente.
Mostre que a matriz suavizadora $\mathbf{S}$ do k-NN tem linhas que somam 1 e que $\operatorname{tr}(\mathbf{S}) = n/k$. O que acontece com o traço no k-NN ponderado por $1/d$? (Dica: qual é o peso do próprio ponto?)
Refaça o exemplo de Nadaraya–Watson usando o núcleo de Epanechnikov com $h = 2$.
Para coordenadas independentes $N(0, 1)$, calcule o coeficiente de variação de $D^2 = \|\mathbf{X} - \mathbf{Q}\|^2$ e compare com o caso uniforme. (Dica: $X_j - Q_j \sim N(0, 2)$, e $D^2/2$ tem distribuição qui-quadrado com $p$ graus de liberdade.)
No exemplo de LSH, encontre o número mínimo de tabelas $L$ que garante $P_{\text{cand}} \geq 0{,}99$ para pares com $\theta = 30^\circ$ usando $b = 12$ bits. Qual a probabilidade de candidatura para pares com $\theta = 90^\circ$ nesse caso?
Aplique a edição de Wilson ($k = 3$) e depois a condensação de Hart ao conjunto unidimensional $1$ (A), $2$ (A), $2{,}6$ (B), $3{,}5$ (A), $6{,}2$ (B), $7$ (B), $8{,}5$ (B), percorrendo os pontos da esquerda para a direita.
(Prático, R) Simule $n = 1000$ observações com 10% de classe positiva e compare, por validação cruzada, a sensibilidade do k-NN usual e do k-NN com priores iguais (função knn_priores do capítulo).

13.18 Leituras Recomendadas

Cover e Hart (1967) — o artigo clássico com o limite assintótico do erro do vizinho mais próximo.
Fix e Hodges (1951) — o relatório técnico que introduziu a regra dos vizinhos mais próximos.
James et al. (2013), Capítulos 2 e 4 — introdução ao classificador de Bayes, ao k-NN e à escolha de $k$, com laboratórios em R.
Hastie, Tibshirani, e Friedman (2009), Capítulos 2 e 13 — métodos locais, maldição da dimensionalidade e protótipos/vizinhos mais próximos.
Stone (1977) — resultados de consistência para estimadores de vizinhos mais próximos.
Beyer et al. (1999) — análise da perda de significado do “vizinho mais próximo” em alta dimensão.
Bentley (1975) — artigo original das KD-trees.
Devroye, Györfi, e Lugosi (1996) — tratado completo da teoria probabilística do reconhecimento de padrões, com capítulos dedicados à consistência do k-NN e à desigualdade plug-in.
Györfi et al. (2002) — teoria não paramétrica da regressão, incluindo o teorema de Stone e as taxas de convergência minimax.
Nadaraya (1964) e Watson (1964) — os artigos que introduziram a regressão por núcleo.
Hart (1968) e Wilson (1972) — os artigos originais da condensação e da edição de vizinhos.
Friedman, Bentley, e Finkel (1977) — análise do tempo esperado de busca nas KD-trees.
Indyk e Motwani (1998) e Charikar (2002) — fundamentos do locality-sensitive hashing.
Weinberger e Saul (2009) — aprendizado de métricas com margem grande para o k-NN.
Aggarwal, Hinneburg, e Keim (2001) — comportamento das normas $L_r$, incluindo as fracionárias, em alta dimensão.

Aggarwal, Charu C., Alexander Hinneburg, e Daniel A. Keim. 2001. “On the Surprising Behavior of Distance Metrics in High Dimensional Space”. Em Database Theory – ICDT 2001, 1973:420–34. Lecture Notes em Computer Science. Springer.

Bellman, Richard. 1961. Adaptive Control Processes: A Guided Tour. Princeton, NJ: Princeton University Press.

Bentley, Jon Louis. 1975. “Multidimensional binary search trees used for associative searching”. Communications of the ACM 18 (9): 509–17.

Beyer, Kevin, Jonathan Goldstein, Raghu Ramakrishnan, e Uri Shaft. 1999. “When is ‘nearest neighbor’ meaningful?” Em Database Theory – ICDT’99, 1540:217–35. Lecture Notes em Computer Science. Springer.

Charikar, Moses S. 2002. “Similarity Estimation Techniques from Rounding Algorithms”. Em Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 380–88.

Chawla, Nitesh V., Kevin W. Bowyer, Lawrence O. Hall, e W. Philip Kegelmeyer. 2002. “SMOTE: Synthetic Minority Over-sampling Technique”. Journal of Artificial Intelligence Research 16: 321–57.

Cover, Thomas, e Peter Hart. 1967. “Nearest neighbor pattern classification”. IEEE transactions on information theory 13 (1): 21–27.

Devroye, Luc, László Györfi, e Gábor Lugosi. 1996. A Probabilistic Theory of Pattern Recognition. New York: Springer.

Dudani, Sahibsingh A. 1976. “The distance-weighted k-nearest-neighbor rule”. IEEE Transactions on Systems, Man, and Cybernetics SMC-6 (4): 325–27.

Fawcett, Tom. 2006. “An Introduction to ROC Analysis”. Pattern Recognition Letters 27 (8): 861–74.

Fix, Evelyn, e Joseph L. Hodges. 1951. “Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties”. Project 21-49-004, Report 4. Randolph Field, Texas: USAF School of Aviation Medicine.

Friedman, Jerome H., Jon Louis Bentley, e Raphael Ari Finkel. 1977. “An Algorithm for Finding Best Matches in Logarithmic Expected Time”. ACM Transactions on Mathematical Software 3 (3): 209–26.

Gower, John C. 1971. “A general coefficient of similarity and some of its properties”. Biometrics 27 (4): 857–71.

Györfi, László, Michael Kohler, Adam Krzyżak, e Harro Walk. 2002. A Distribution-Free Theory of Nonparametric Regression. New York: Springer.

Hart, Peter E. 1968. “The Condensed Nearest Neighbor Rule”. IEEE Transactions on Information Theory 14 (3): 515–16.

Hastie, Trevor, Robert Tibshirani, e Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2º ed. New York: Springer.

Indyk, Piotr, e Rajeev Motwani. 1998. “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality”. Em Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 604–13.

James, Gareth, Daniela Witten, Trevor Hastie, e Robert Tibshirani. 2013. An Introduction to Statistical Learning: with Applications in R. Springer.

Kuhn, Max. 2008. “Building Predictive Models in R Using the caret Package”. Journal of Statistical Software 28 (5): 1–26.

Loftsgaarden, D. O., e C. P. Quesenberry. 1965. “A Nonparametric Estimate of a Multivariate Density Function”. The Annals of Mathematical Statistics 36 (3): 1049–51.

Mahalanobis, Prasanta Chandra. 1936. “On the generalized distance in statistics”. Proceedings of the National Institute of Sciences of India 2 (1): 49–55.

Malkov, Yu. A., e D. A. Yashunin. 2020. “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs”. IEEE Transactions on Pattern Analysis and Machine Intelligence 42 (4): 824–36.

Nadaraya, E. A. 1964. “On Estimating Regression”. Theory of Probability and Its Applications 9 (1): 141–42.

Silverman, Bernard W. 1986. Density Estimation for Statistics and Data Analysis. London: Chapman & Hall.

Stone, Charles J. 1977. “Consistent nonparametric regression”. The Annals of Statistics 5 (4): 595–620.

Watson, Geoffrey S. 1964. “Smooth Regression Analysis”. Sankhyā: The Indian Journal of Statistics, Series A 26 (4): 359–72.

Weinberger, Kilian Q., e Lawrence K. Saul. 2009. “Distance Metric Learning for Large Margin Nearest Neighbor Classification”. Journal of Machine Learning Research 10: 207–44.

Wilson, Dennis L. 1972. “Asymptotic Properties of Nearest Neighbor Rules Using Edited Data”. IEEE Transactions on Systems, Man, and Cybernetics SMC-2 (3): 408–21.

Dimensão \(p\)	Taxa \(n^{-2/(p+2)}\)	\(n\) para EQM \(\approx 0{,}01\)
1	\(n^{-0{,}67}\)	\(10^3\)
2	\(n^{-0{,}50}\)	\(10^4\)
5	\(n^{-0{,}29}\)	\(10^7\)
10	\(n^{-0{,}17}\)	\(10^{12}\)
20	\(n^{-0{,}09}\)	\(10^{22}\)

Métrica	Cálculo	Valor
Manhattan (\(r = 1\))	\(3 + 2 + 0\)	5,000
Euclidiana (\(r = 2\))	\(\sqrt{9 + 4 + 0}\)	3,606
Minkowski (\(r = 3\))	\((27 + 8 + 0)^{1/3}\)	3,271
Chebyshev (\(r \to \infty\))	\(\max(3, 2, 0)\)	3,000