Aula 2: Vizinhos Mais Próximos, Maldição da Dimensionalidade e KDE

Aprendizado Não Supervisionado

Autor

Marcos M. Raimundo — Instituto de Computação, UNICAMP

Data de Publicação

26 de agosto de 2026

1 Abertura — O Que Fazer Sem Forma Paramétrica, e Sem \(N \gg d\)

A Aula 1 partiu de um problema sem rótulo — dado \(\mathbf{x}_1,\dots,\mathbf{x}_N\in\mathbb{R}^d\), descrever o comportamento típico de uma população para depois reconhecer o que se desvia dele (profiling). A aposta feita para resolver isso foi específica: assumir que os dados vêm de uma família teórica conhecida — a Gaussiana multivariada \(\mathcal{N}(\boldsymbol\mu,\Sigma)\) —, ajustá-la por máxima verossimilhança (\(\hat{\boldsymbol\mu}=\frac1N\sum_n\mathbf{x}_n\), \(\hat\Sigma=\frac1N\sum_n(\mathbf{x}_n-\hat{\boldsymbol\mu})(\mathbf{x}_n-\hat{\boldsymbol\mu})^T\)), e usar a distância de Mahalanobis, \(D_M(\mathbf{x})^2=(\mathbf{x}-\hat{\boldsymbol\mu})^T\hat\Sigma^{-1}(\mathbf{x}-\hat{\boldsymbol\mu})\), para decidir o que é típico — uma distância que \(\hat\Sigma^{-1}\) deforma, esticando nas direções de baixa variância e comprimindo nas de alta variância, ao contrário da distância Euclidiana ingênua. Convertendo \(D_M(\mathbf{x})^2\) (que segue \(\chi^2_d\) sob o modelo ajustado) num \(p\)-valor, a aula terminou comparando a rota conjunta (uma só matriz \(\hat\Sigma\), \(d(d+1)/2\) parâmetros, sensível a correlação) com a rota por dimensão (supor independência, \(d\) parâmetros, combinados pelo teste de Fisher) — a mesma tensão do Naive Bayes, agora em teste de hipótese.

O fechamento da Aula 1 já apontou duas rachaduras nessa receita, nenhuma resolvida ali: dados genuinamente multimodais (uma única Gaussiana “borra” duas subpopulações numa média cega) e outliers no próprio ajuste (que inflam \(\hat\Sigma\) e escondem o que se queria detectar). Mas a rachadura que abre esta aula é uma terceira, mais estrutural: \(\hat\Sigma\) só é invertível se \(N > d\) — sem isso, não há \(\hat\Sigma^{-1}\), não há Mahalanobis, a receita inteira trava antes de começar. E mesmo quando \(N>d\) vale tecnicamente, o ajuste piora conforme \(d\) cresce — o motivo exato disso ainda não foi explicado, só anunciado.

Esta aula puxa esse fio até o fim, respondendo duas perguntas:

Por que exatamente “espaço de alta dimensão” é um problema geométrico — não só um problema de contar os \(d(d+1)/2\) parâmetros de \(\Sigma\)?
Se não quisermos mais assumir nenhuma forma funcional para \(p(\mathbf{x})\) — nem Gaussiana, nem nenhuma outra família —, como estimar densidade deixando os dados “falarem por si”?

1.1 Pergunta

Se \(\hat\Sigma\) já quebra quando \(N<d\), o que exatamente quebra primeiro quando \(d\) cresce muito além disso, mesmo com \(N\) ainda maior que \(d\)?

Dica: pense no que significa “estimar uma direção de covariância” com poucos pontos por direção disponível.

□ Mesmo com \(N>d\) satisfeito, aumentar \(d\) ainda degrada a qualidade da estimativa de \(\hat\Sigma\), porque o número de parâmetros a estimar (\(d(d+1)/2\)) cresce muito mais rápido que \(d\).
□ O problema de alta dimensão é, fundamentalmente, um problema de contagem de parâmetros — resolvido bastando ter \(N\) grande o suficiente, sem nenhuma mudança qualitativa de comportamento geométrico.
□ Um método que não estima nenhuma matriz de covariância (como contar vizinhos) está, por isso, livre de qualquer versão da maldição da dimensionalidade.
□ A intuição geométrica de “perto” e “longe” formada em 2 ou 3 dimensões pode falhar quando aplicada ingenuamente a espaços de muitas dimensões.

2 Intuição — Contando e Somando Vizinhos

Antes de qualquer geometria, ataque o problema do jeito mais direto possível — quase um algoritmo, sem nenhuma fórmula ainda. O dado é radius_mean do Breast Cancer Wisconsin (o raio médio do tumor medido no exame, um único número por paciente, 569 ao todo). O desafio:

Para cada valor possível de \(x\) no eixo de radius_mean, esse valor é comum entre os pacientes reais, ou raro?

Heurística 1 — contar dentro de um raio fixo. A ideia mais literal possível: escolha um raio \(r\) (por exemplo, \(r=1\)). Para cada valor de \(x\) que você quiser testar, marque a janela \([x-r,\,x+r]\) e conte quantos dos 569 pacientes caem dentro dela. Deslize \(x\) ao longo de todo o eixo, repetindo a contagem a cada ponto: onde a contagem for alta, o valor é comum; onde for baixa (ou zero), é raro. É um algoritmo que se descreve em uma frase — para cada \(x\) da grade, uma contagem —, mas tem uma aspereza: um paciente a \(0{,}99\) de \(x\) conta como “dentro” (peso \(1\)); um paciente a \(1{,}01\) conta como “fora” (peso \(0\)) — um corte abrupto para uma diferença mínima de distância.

Heurística 2 — um peso que desconta com a distância. Em vez do corte abrupto “dentro/fora” da Heurística 1, suavize: cada paciente contribui com um peso que desconta continuamente conforme a distância até \(x\) cresce — perto de \(x\), o peso é alto; longe, cai aos poucos até quase zero, sem nenhum degrau. Some os pesos dos 569 pacientes para cada \(x\): onde há muita gente parecida por perto, os pesos se acumulam; onde há pouca, quase não sobra nada. A conta é igual em espírito à Heurística 1 — ainda é “quanta gente parecida tem aqui perto” —, só que sem o corte brusco de um raio rígido.

O gráfico abaixo aplica as duas heurísticas aos 569 pacientes reais, lado a lado — ainda sem entrar em nenhuma fórmula fechada. Repare que as duas curvas contam praticamente a mesma história:

As duas curvas concordam sobre onde radius_mean é comum (o pico mais alto, perto de 12) e onde começa a ficar raro (a cauda longa à direita, acima de 20). Os traços cinzas embaixo de cada curva são os 569 pacientes reais — repare como as duas curvas sobem exatamente onde os traços ficam mais próximos uns dos outros.

Isso já é o conteúdo inteiro desta aula. As próximas seções vão dar nome preciso a cada heurística: a Heurística 1 (raio fixo, contagem dura) é exatamente a janela de Parzen que abre a estimação por Kernel (KDE); a Heurística 2 (peso que desconta suavemente) é a versão com kernel gaussiano da mesma KDE — a suavização que resolve a aspereza da Heurística 1. E vamos ver que fixar o raio não é a única rota possível: fixar a contagem em vez do raio, e deixar o raio variar, dá o \(k\)-NN — a rota gêmea da mesma identidade geral. Falta também explicar por que “andar para os dois lados” fica geometricamente estranho quando cada paciente tem 30 atributos em vez de só 1 — a maldição da dimensionalidade, tema do próximo bloco.

2.1 Pergunta

As duas curvas do gráfico anterior quase se sobrepõem — mas vêm de contas bem diferentes. Por que elas concordam tanto?

Dica: pense no que cada uma está, no fundo, tentando responder — não em como cada conta é feita por dentro.

□ As duas curvas concordam porque as duas são formas diferentes de responder à mesma pergunta — “quantos pacientes parecidos há perto de \(x\)?” — só que uma fixa o número de vizinhos e mede a distância, e a outra fixa a distância (via peso decrescente) e soma quantos contribuem.
□ As duas curvas concordariam da mesma forma mesmo que a curva 1 fosse construída ordenando os pacientes por ordem alfabética do prontuário, em vez de por proximidade em radius_mean.
□ Se todos os 569 pacientes tivessem exatamente o mesmo valor de radius_mean, as duas curvas ainda seriam bem diferentes uma da outra nesse ponto.
□ A curva 1 (contar vizinhos) usa informação sobre a posição de cada paciente no eixo; a curva 2 (somar contribuições) também usa essa posição — nenhuma das duas ignora onde, exatamente, cada paciente está.

3 A Maldição da Dimensionalidade, Geometricamente

A resposta à primeira pergunta da abertura vem de dois livros diferentes — convergindo na mesma conclusão por caminhos distintos.

3.1 Volume que se esconde na casca

Bishop (PRML, §1.4) começa pelo problema mais ingênuo: dividir cada variável em \(M\) células e contar pontos por célula.

“Another major limitation of the histogram approach is its scaling with dimensionality. If we divide each variable in a D-dimensional space into M bins, then the total number of bins will be \(M^D\). This exponential scaling with D is an example of the curse of dimensionality.” (p. 121)

Mas o resultado mais surpreendente de PRML não é sobre células — é sobre onde mora o volume de uma esfera em alta dimensão:

“consider a sphere of radius r = 1 in a space of D dimensions, and ask what is the fraction of the volume of the sphere that lies between radius \(r=1-\epsilon\) and \(r=1\). […] the volume of a sphere of radius r in D dimensions must scale as \(r^D\) […] Thus the required fraction is given by \(\dfrac{V_D(1)-V_D(1-\epsilon)}{V_D(1)} = 1-(1-\epsilon)^D\) […] for large D, this fraction tends to 1 even for small values of \(\epsilon\). Thus, in spaces of high dimensionality, most of the volume of a sphere is concentrated in a thin shell near the surface!” (pp. 36–37)

epsilon = 0.05
for D in [1, 2, 5, 10, 30, 100]:
    frac = 1 - (1 - epsilon) ** D
    print(f"D={D:3d}: fração do volume na casca de espessura ε=0.05  ≈ {frac:.3f}")

D=  1: fração do volume na casca de espessura ε=0.05  ≈ 0.050
D=  2: fração do volume na casca de espessura ε=0.05  ≈ 0.098
D=  5: fração do volume na casca de espessura ε=0.05  ≈ 0.226
D= 10: fração do volume na casca de espessura ε=0.05  ≈ 0.401
D= 30: fração do volume na casca de espessura ε=0.05  ≈ 0.785
D=100: fração do volume na casca de espessura ε=0.05  ≈ 0.994

Para tornar isso concreto, imagine três bolas do mesmo raio — mas em \(D=1\) (um segmento de reta), \(D=2\) (um disco) e \(D=3\) (uma esfera de verdade), as três únicas dimensões que dá para desenhar sem nenhum truque. Em cada uma, sombreamos o núcleo (a região a mais de \(\epsilon=0{,}05\) do raio para dentro do centro) e deixamos a casca ao redor como o que sobra — usando o raio geométrico real \(1-\epsilon\) em cada dimensão, sem nenhuma analogia: em \(D=1\) o “volume” é comprimento (escala com \(r\)), em \(D=2\) é área (escala com \(r^2\)), em \(D=3\) é volume de verdade (escala com \(r^3\)). Já dá para ver a casca crescendo de dimensão para dimensão, mesmo nesse intervalo pequeno — o efeito só fica dramático de verdade lá na frente, com o cálculo numérico para \(D=10, 30, 100\) que vem a seguir, onde nenhum desenho literal é mais possível.

Em \(D=100\), praticamente 100% do volume de uma esfera mora nos últimos 5% do raio. A intuição de “o centro concentra a massa” — válida em 1, 2 ou 3 dimensões — se inverte por completo.

“consider the behaviour of a Gaussian distribution in a high- dimensional space. […] we see that for large D the probability mass of the Gaussian is concentrated in a thin shell.” (PRML, p. 37)

O mesmo vale para uma Gaussiana: a massa de probabilidade se afasta da média e se acumula numa casca fina — nem perto do centro, nem espalhada uniformemente.

3.2 O mesmo efeito, do ponto de vista de um vizinho mais próximo

O ESL (Hastie, Tibshirani & Friedman, §2.5 “Local Methods in High Dimensions”) chega à mesma conclusão por um caminho mais concreto, pensando diretamente em vizinhança. Imagine que você quer capturar uma fração \(r\) dos dados (digamos, \(r=0{,}10\), ou 10%) usando uma caixa (um hipercubo) centrada num ponto-alvo. A pergunta: de que tamanho precisa ser essa caixa, em cada uma das \(p\) dimensões?

Chame de \(e_p(r)\) o comprimento da aresta dessa caixa, medido como fração da amplitude total daquela variável — se \(e_p(r)=1\), a caixa já precisa cobrir a variável inteira, ponta a ponta. Supondo os dados espalhados de forma aproximadamente uniforme, uma caixa de aresta \(e\) em \(p\) dimensões captura uma fração \(e^p\) do volume total (a mesma identidade \(r^D\) vista no Bloco 2 da maldição — volume escala com a aresta elevada à dimensão). Para capturar exatamente a fração \(r\) desejada, basta resolver \(e^p=r\) para \(e\), o que dá diretamente \(e_p(r)=r^{1/p}\) — a fórmula do ESL.

“Suponha que lancemos uma vizinhança hipercúbica ao redor de um ponto- alvo para capturar uma fração \(r\) das observações. […] o comprimento de aresta esperado será \(e_p(r) = r^{1/p}\). Em dez dimensões, \(e_{10}(0{,}01) = 0{,}63\) e \(e_{10}(0{,}1) = 0{,}80\), enquanto a amplitude inteira de cada variável é apenas \(1{,}0\). Então, para capturar 1% ou 10% dos dados para formar uma média local, precisamos cobrir 63% ou 80% da amplitude de cada variável de entrada. Essas vizinhanças deixaram de ser ‘locais’.” (p. 22, tradução nossa)

for p in [1, 2, 10, 30]:
    e10 = 0.10 ** (1 / p)
    print(f"p={p:3d}: para capturar 10% dos dados, cobrir {e10:.2%} da amplitude de cada eixo")

p=  1: para capturar 10% dos dados, cobrir 10.00% da amplitude de cada eixo
p=  2: para capturar 10% dos dados, cobrir 31.62% da amplitude de cada eixo
p= 10: para capturar 10% dos dados, cobrir 79.43% da amplitude de cada eixo
p= 30: para capturar 10% dos dados, cobrir 92.61% da amplitude de cada eixo

Em \(p=1\) ou \(p=2\), a conta ainda soa razoável — uma fatia pequena do eixo já basta. Mas em \(p=30\), é preciso cobrir 93% da amplitude de cada variável só para capturar 10% dos dados: a caixa quase engole a variável inteira, e a vizinhança deixou de ser local há muito tempo. O segundo resultado do ESL é ainda mais direto:

“The median distance from the origin to the closest data point is given by the expression \(d(p,N) = \big(1-(1/2)^{1/N}\big)^{1/p}\) […]. For N = 500, p = 10, \(d(p,N)\approx 0.52\), more than halfway to the boundary. Hence most data points are closer to the boundary of the sample space than to any other data point.” (pp. 22–23)

Isso quer dizer que, com \(N=500\) pontos uniformes numa bola unitária de \(D=10\) dimensões, o ponto mais próximo da origem está, em mediana, a mais da metade do caminho até a borda — mais perto da fronteira do espaço do que de qualquer outro ponto de dado.

3.3 Consequência: distâncias deixam de discriminar

Os dois resultados acima — volume na casca, vizinhos perto da borda — apontam para o mesmo problema prático: em alta dimensão, a noção de “vizinho próximo” fica cada vez menos informativa, porque todo mundo fica a distâncias parecidas de todo mundo. Uma forma direta de medir isso é o contraste relativo: fixe um ponto de consulta, calcule a distância a todos os outros pontos, e compare a distância mínima com a máxima, \[\text{contraste} = \frac{\text{dist}_{\max}-\text{dist}_{\min}}{\text{dist}_{\min}}.\]

Sinalização de fonte

Esta métrica específica — e a comparação \(L_1\)/\(L_2\)/Cosseno em geral — não foi encontrada em PRML, ESL nem DLFC (os três livros-texto desta disciplina) apesar de busca dedicada. É um resultado padrão da literatura de busca aproximada de vizinhos (Beyer et al., 1999; Aggarwal et al., 2001), citado por atribuição de origem da ideia, não como trecho literal de um livro-fonte. A demonstração numérica a seguir é nossa, verificada por script antes de escrever esta aula.

Aplicando essa medida ao próprio Breast Cancer Wisconsin (padronizado), sorteando aleatoriamente \(d\) das 30 colunas disponíveis:

ds_list = [2, 5, 10, 20, 30]
medias, desvios = [], []
for d in ds_list:
    m, s = relative_contrast(X_std, d, n_trials=60)
    medias.append(m)
    desvios.append(s)
    print(f"d={d:2d}  contraste relativo médio = {m:6.2f}  (desvio {s:.2f})")

d= 2  contraste relativo médio = 247.61  (desvio 294.79)
d= 5  contraste relativo médio =  27.07  (desvio 19.12)
d=10  contraste relativo médio =  17.26  (desvio 9.45)
d=20  contraste relativo médio =   9.96  (desvio 5.33)
d=30  contraste relativo médio =  10.19  (desvio 3.69)

O contraste relativo desmorona de \(\approx 220\) (2 atributos) para \(\approx 10\) (30 atributos) — num dado real, não simulado. Não é só teoria de livro: a maldição da dimensionalidade aparece exatamente neste dataset, com estes 30 atributos de exame clínico.

3.4 Pergunta

Se distâncias deixam de discriminar em alta dimensão, o que isso quebra primeiro: um classificador ou um estimador de densidade?

Dica: pense em cada item separadamente — nem todos têm a mesma resposta.

□ Se a distância entre o ponto de consulta e seu vizinho mais próximo, e a distância até o ponto mais distante, convergem para o mesmo valor conforme \(d\) cresce, então a ordem dos \(k\) vizinhos mais próximos de um ponto se torna cada vez mais sensível a perturbações minúsculas nos dados.
□ No limite em que o contraste relativo é exatamente zero, todo subconjunto de \(k\) pontos escolhido por proximidade é, na prática, uma escolha tão informativa quanto um subconjunto de \(k\) pontos escolhido aleatoriamente.
□ Se um dataset tem 30 atributos mas apenas 3 deles carregam informação relevante (os outros 27 são ruído independente da variável de interesse), aumentar a dimensionalidade usada de 3 para 30 sempre melhora a qualidade da estimativa de densidade local.
□ A fórmula \(e_p(r) = r^{1/p}\) do ESL implica que, para qualquer \(r<1\) fixo, o comprimento de aresta necessário cresce (se aproxima de
1. conforme \(p\) aumenta.

4 Da Ideia Geral ao Estimador: \(p(\mathbf{x}) = K/(NV)\)

Se abandonamos a forma Gaussiana, o que resta? PRML propõe um caminho que parte de premissas explícitas, não de uma fórmula pronta. A intuição inicial é a mesma lição que o histograma já ensinava:

“First, to estimate the probability density at a particular location, we should consider the data points that lie within some local neighbourhood of that point. […] Second, the value of the smoothing parameter should be neither too large nor too small in order to obtain good results.” (PRML, pp. 121–122)

Premissas desta derivação

Ponto de consulta e vizinhança. Fixamos um ponto \(\mathbf{x}\) onde queremos estimar a densidade, e escolhemos ao redor dele uma região pequena \(R\) (uma pequena esfera ou cubo centrado em \(\mathbf{x}\)), de volume \(V\). É olhando para dentro dessa região — quantos pontos de treino caem lá — que vamos decidir se \(\mathbf{x}\) está numa parte densa ou rala do espaço.
Densidade aproximadamente constante dentro de \(R\). Supomos que, sendo \(R\) pequena o bastante, a densidade verdadeira \(p(\mathbf{x})\) não varia muito de um ponto a outro dentro dela — dá para tratá-la como um único valor constante ali (o próprio \(p(\mathbf{x})\) do ponto de consulta), em vez de uma função que muda ponto a ponto. Essa suposição é o que vai permitir, no Passo 2, trocar uma integral difícil de calcular por uma multiplicação simples.
Amostragem independente. Os \(N\) pontos de treino foram sorteados de forma independente uns dos outros, todos da mesma distribuição verdadeira \(p(\mathbf{x})\). É essa independência que permite, no Passo 3, tratar “quantos pontos caem dentro de \(R\)” como uma contagem binomial — cada ponto “decide por conta própria” se cai dentro ou fora.

Com essas três premissas, o desenvolvimento até o estimador final é direto, passo a passo:

Passo 1 — a massa de probabilidade em \(R\). Por definição, \(P=\int_R p(\mathbf{x})\,d\mathbf{x}\) — a integral da densidade verdadeira sobre a região.

Passo 2 — usando a Premissa 2. Se \(p(\mathbf{x})\) é aproximadamente constante em \(R\), a integral vira só “densidade vezes volume”: \(P\simeq p(\mathbf{x})V\).

Passo 3 — quantos pontos de treino caem em \(R\)? Pela Premissa 3, cada um dos \(N\) pontos foi sorteado independentemente da mesma \(p(\mathbf{x})\). Para cada ponto, “cair dentro de \(R\)” tem probabilidade \(P\) (a mesma massa de probabilidade do Passo 1) e “cair fora” tem probabilidade \(1-P\) — exatamente como uma moeda viciada, com probabilidade \(P\) de dar “cara”. Contar quantos de \(N\) lançamentos independentes dessa moeda dão “cara” é, por definição, uma variável binomial: \(K\sim\mathrm{Bin}(N,P)\). Não é uma aproximação nesse ponto — é só reconhecer o formato do problema.

Passo 4 — para \(N\) grande, a contagem deixa de ser incerta. Uma binomial \(\mathrm{Bin}(N,P)\) tem média \(NP\) e desvio-padrão \(\sqrt{NP(1-P)}\). A média cresce proporcionalmente a \(N\), mas o desvio-padrão cresce só com \(\sqrt{N}\) — então o desvio relativo (desvio-padrão dividido pela média) encolhe como \(1/\sqrt{N}\) conforme \(N\) aumenta. Em outras palavras: quanto mais pontos de treino, mais a contagem \(K\) se concentra perto do seu valor esperado \(NP\), em proporção — a mesma lógica de “jogar uma moeda um milhão de vezes dá uma fração de caras bem próxima de 50%, mesmo sendo uma contagem aleatória”. Por isso, para \(N\) grande, é seguro escrever \(K\simeq NP\) e tratar o resultado como se não tivesse mais aleatoriedade:

“For large N, this distribution will be sharply peaked around the mean and so \(K\simeq NP\).” (PRML, p. 122)

Passo 5 — combinando os Passos 2 e 4. \(K\simeq NP\simeq Np(\mathbf{x})V\). Isolando \(p(\mathbf{x})\): \[p(\mathbf{x}) = \frac{K}{NV}.\]

Esse resultado é o eixo de toda a aula. Ele herda uma tensão interna diretamente das premissas: a Premissa 2 pede \(R\) pequeno (densidade quase constante dentro), mas o Passo 4 (binomial concentrada) pede \(R\) grande o bastante para que \(K\) não seja um número tão pequeno que a aproximação fique ruidosa. As duas premissas puxam \(V\) em direções opostas — o que já anuncia por que qualquer técnica construída a partir daqui vai precisar de um parâmetro de suavização.

“We can exploit this result in two different ways. Either we can fix K and determine the value of V from the data, which gives rise to the K-nearest-neighbour technique […], or we can fix V and determine K from the data, giving rise to the kernel approach.” (PRML, p. 123)

Os dois métodos que vemos a seguir não são “duas técnicas parecidas” — são a mesma identidade matemática, explorada de dois lados opostos.

4.1 Pergunta

A fórmula \(p(\mathbf{x})=K/(NV)\) tem uma tensão interna: \(V\) precisa ser pequeno e grande ao mesmo tempo. Isso é uma contradição real, ou só parece uma?

Dica: pense em “pequeno o bastante para quê” e “grande o bastante para quê”, separadamente.

□ \(V\) precisa ser pequeno para que a suposição de densidade aproximadamente constante dentro da região seja razoável.
□ \(V\) precisa ser grande para que o número esperado de pontos capturados, \(K\), seja alto o suficiente para a aproximação binomial ser confiável.
□ Como as duas exigências sobre \(V\) apontam em direções opostas, não existe nenhum valor de \(V\) que funcione razoavelmente bem na prática.
□ A tensão entre “pequeno” e “grande” para \(V\) é resolvida de forma diferente pelas duas rotas (\(k\)-NN e KDE), não eliminada por nenhuma das duas.

5 \(k\)-Vizinhos-Mais-Próximos Para Densidade

Primeira rota: fixar \(K\), e deixar os dados determinarem \(V\).

Premissas desta rota

Fixamos \(K\) de antemão (um número inteiro escolhido por nós, como 5 ou 20) — em vez de fixar \(V\), como fizemos no bloco anterior para chegar em \(p(\mathbf{x})=K/(NV)\).
\(V\) passa a ser determinado pelos dados, não escolhido por nós. Para descobrir o valor de \(V\) que corresponde a esse \(K\): cresce-se uma esfera centrada em \(\mathbf{x}\), começando de raio zero, até ela conter exatamente \(K\) pontos de treino — o volume dessa esfera final é o \(V\) que entra na fórmula.

“we consider a fixed value of K and use the data to find an appropriate value for V. To do this, we consider a small sphere centred on the point x […] and we allow the radius of the sphere to grow until it contains precisely K data points. The estimate of the density \(p(x)\) is then given by [K/(NV)] with V set to the volume of the resulting sphere. This technique is known as K nearest neighbours.” (PRML, pp. 124–125)

Passo 1 — dar um nome ao raio. Chame de \(d_K(\mathbf{x})\) o raio dessa esfera — a distância ao \(K\)-ésimo vizinho mais próximo.

Passo 2 — como o volume escala com o raio. O volume de uma esfera de raio \(r\) em \(D\) dimensões escala como \(r^D\) (a mesma identidade de escala vista no bloco da maldição da dimensionalidade, PRML eq. 1.75). Logo \(V \propto d_K(\mathbf{x})^D\).

Passo 3 — substituindo na Premissa herdada do bloco anterior. Como \(p(\mathbf{x})=K/(NV)\) e \(K\) é fixo, basta substituir \(V\): \[p(\mathbf{x}) \;\propto\; \frac{1}{d_K(\mathbf{x})^D}\]

Interpretação direta: ponto num bairro denso → \(K\) vizinhos estão próximos → \(d_K\) pequeno → densidade estimada alta. Ponto isolado → \(d_K\) grande → densidade baixa. \(K\) funciona como parâmetro de suavização.

Aplicando isso a radius_mean do Breast Cancer Wisconsin, em três pontos-teste e três valores de \(K\):

for K in [5, 20, 50]:
    for x0 in [12.0, 17.5, 25.0]:
        dens = knn_density_1d(np.array([x0]), x_radius, K)[0]
        print(f"K={K:3d}  x0={x0:5.1f}  densidade estimada ≈ {dens:.4f}")
    print()

K=  5  x0= 12.0  densidade estimada ≈ 0.1098
K=  5  x0= 17.5  densidade estimada ≈ 0.0549
K=  5  x0= 25.0  densidade estimada ≈ 0.0029

K= 20  x0= 12.0  densidade estimada ≈ 0.1598
K= 20  x0= 17.5  densidade estimada ≈ 0.0399
K= 20  x0= 25.0  densidade estimada ≈ 0.0046

K= 50  x0= 12.0  densidade estimada ≈ 0.1515
K= 50  x0= 17.5  densidade estimada ≈ 0.0382
K= 50  x0= 25.0  densidade estimada ≈ 0.0083

Note o rug plot (traços cinzas no eixo x): as duas concentrações de pontos visíveis já sugerem que radius_mean não é unimodal — vamos voltar a isso no Bloco 6.

Aviso: isto não é uma densidade de verdade

“Note that the model produced by K nearest neighbours is not a true density model because the integral over all space diverges.” (PRML, p. 125)

A cauda de \(1/d_K(\mathbf{x})^D\) não decai rápido o bastante para que a integral sobre todo o espaço convirja para 1. Isso não invalida o uso de \(k\)-NN como score de densidade relativa — mas quer dizer que não se deve tratar o número produzido como uma probabilidade calibrada.

5.1 Pergunta

Se \(K\) é fixo e \(d_K(\mathbf{x})\) é o raio que cresce até capturar \(K\) pontos, o que acontece exatamente quando \(K=N\) (todos os pontos)?

Dica: pense no que acontece com \(d_K\) quando a esfera precisa englobar o conjunto de dados inteiro.

□ Se \(K=N\) (todos os pontos de treino), \(d_K(\mathbf{x})\) é a mesma para qualquer \(\mathbf{x}\) dentro do suporte dos dados, igual à distância até o ponto mais distante — e a densidade estimada por \(k\)-NN se torna praticamente constante em todo o espaço.
□ Um ponto que está exatamente na posição de um outro ponto de treino (distância zero) faria a densidade estimada por \(k\)-NN, com \(K=1\), divergir para infinito.
□ Aumentar \(K\) de 5 para 50, num ponto que já está numa região muito densa, deveria produzir uma mudança relativa muito menor em \(d_K(\mathbf{x})\) do que a mesma mudança de \(K\) produziria num ponto isolado na cauda da distribuição.
□ Como a densidade por \(k\)-NN não integra a 1, ela nunca pode ser usada para comparar, de forma válida, se um ponto é mais ou menos denso do que outro.

6 Do Histograma ao Kernel Suave: KDE

Segunda rota: fixar \(V\), e contar quantos pontos \(K\) caem dentro.

Premissas desta rota

\(V\) é fixado de antemão — a versão mais simples é um hipercubo de lado \(h\) centrado em \(\mathbf{x}\).
\(K\) passa a ser determinado pelos dados: conta-se quantos pontos de treino caem dentro desse hipercubo.

Passo 1 — a janela de Parzen. Defina uma função indicadora do hipercubo unitário:

“we take the region R to be a small hypercube centred on the point x […] \(k(u)=1\) if \(|u_i|\le 1/2\) for \(i=1,\dots,D\), 0 otherwise.” (p. 123)

Passo 2 — contar pontos dentro do hipercubo. Cada ponto de treino \(\mathbf{x}_n\) conta 1 se estiver dentro do cubo de lado \(h\) centrado em \(\mathbf{x}\): \[K=\sum_n k\big((\mathbf{x}-\mathbf{x}_n)/h\big).\]

Passo 3 — substituindo na Premissa herdada do bloco anterior. Como \(V=h^D\) (volume do hipercubo) e \(p(\mathbf{x})=K/(NV)\): \[p(\mathbf{x}) = \frac{1}{N}\sum_n \frac{1}{h^D} k\Big(\frac{\mathbf{x}-\mathbf{x}_n}{h}\Big).\]

Passo 4 — o problema desse resultado, e como resolvê-lo. A janela dura (hipercubo) herda o mesmo problema do histograma: descontinuidades artificiais nas bordas do cubo.

“We can obtain a smoother density model if we choose a smoother kernel function, and a common choice is the Gaussian […] \[p(\mathbf{x}) = \frac{1}{N}\sum_{n=1}^N \frac{1}{(2\pi h^2)^{1/2}} \exp\left(-\frac{\|\mathbf{x}-\mathbf{x}_n\|^2}{2h^2}\right)\] where h represents the standard deviation of the Gaussian components.” (p. 124)

Em palavras: trocando a função indicadora \(k(\cdot)\) por uma gaussiana no Passo 1, o mesmo Passo 3 (substituir em \(K/(NV)\)) leva direto à fórmula final acima — uma gaussiana de largura \(h\) sobre cada ponto de treino, somadas, divididas por \(N\). \(h\) é o parâmetro de suavização — o mesmo papel que \(K\) desempenhava na rota anterior.

“We see that, as expected, the parameter h plays the role of a smoothing parameter, and there is a trade-off between sensitivity to noise at small h and over-smoothing at large h.” (PRML, p. 124)

Verificando isso em radius_mean, contando picos (máximos locais) da densidade estimada para três larguras de banda:

for h in [0.3, 1.0, 3.0]:
    dens = gaussian_kde_1d(grid, x_radius, h)
    picos = ((dens[1:-1] > dens[:-2]) & (dens[1:-1] > dens[2:])).sum()
    print(f"h={h:.1f}: {picos:2d} picos detectados, densidade máxima {dens.max():.4f}")

h=0.3: 12 picos detectados, densidade máxima 0.1541
h=1.0:  3 picos detectados, densidade máxima 0.1403
h=3.0:  1 picos detectados, densidade máxima 0.0913

\(h=0.3\) (pequeno demais) produz 12 picos espúrios — ruído, não estrutura real. \(h=3.0\) (grande demais) produz 1 pico só — borra qualquer estrutura que exista. \(h=1.0\) mostra 3 picos: candidato mais plausível a capturar algo real, sem exagerar no ruído. Voltaremos a essa estrutura de 3 picos no Bloco 6.

O que muda de nome, mas não de ideia

O mesmo parâmetro de suavização, três disfarces
No histograma	No \(k\)-NN (Bloco 4)	No KDE (aqui)
largura do bin \(\Delta\)	número de vizinhos \(K\)	largura do kernel \(h\)

6.1 Pergunta

Se \(h\to\infty\) no KDE gaussiano, o que exatamente acontece com a forma da densidade estimada?

Dica: pense no que acontece com cada gaussiana individual quando sua largura cresce sem limite.

□ No limite \(h\to\infty\), a densidade estimada por KDE gaussiano se torna aproximadamente constante em qualquer região finita do espaço — a mesma degenerescência de “borrar tudo” vista no limite \(K=N\) do \(k\)-NN.
□ No limite \(h\to 0\), o KDE gaussiano converge para uma soma de funções delta centradas em cada ponto de treino, e a densidade estimada em qualquer ponto que não seja exatamente um dado de treino tende a zero.
□ Se dois conjuntos de dados têm o mesmo número de pontos \(N\), mas um deles está mais espalhado (maior variância), usar o mesmo valor fixo de \(h\) para os dois produzirá, em geral, o mesmo grau relativo de suavização nos dois casos.
□ A escolha de \(h\) no KDE é conceitualmente equivalente à escolha da largura de bin \(\Delta\) num histograma — ambas controlam o mesmo trade-off entre ruído e viés.

7 \(k\)-NN vs. KDE, Lado a Lado, no Dado Real

Os Blocos 4 e 5 construíram a mesma identidade \(p(\mathbf{x})=K/(NV)\) por lados opostos. Colocando as duas melhores versões (KDE com \(h=1.0\), \(k\)-NN com \(K=20\)) uma sobre a outra:

Concordam bastante no grosso da distribuição — mas divergem exatamente onde a teoria prevê que deveriam: nas caudas. KDE tem largura de suavização fixa (\(h\) igual em toda parte); \(k\)-NN tem largura adaptativa (\(d_K\) encolhe onde há muitos pontos, cresce onde há poucos). Veja a diferença direta:

tree = cKDTree(x_radius.reshape(-1, 1))
for x0 in [12.0, 25.0]:
    for K in [5, 20, 50]:
        dist, _ = tree.query([[x0]], k=K)
        print(f"x0={x0:5.1f}  K={K:3d}  d_K={dist[0, -1]:.3f}")

x0= 12.0  K=  5  d_K=0.040
x0= 12.0  K= 20  d_K=0.110
x0= 12.0  K= 50  d_K=0.290
x0= 25.0  K=  5  d_K=1.490
x0= 25.0  K= 20  d_K=3.840
x0= 25.0  K= 50  d_K=5.270

Em \(x_0=12\) (região densa), \(d_K\) cresce muito pouco entre \(K=5\) e \(K=50\) — a janela quase não precisa se abrir. Em \(x_0=25\) (cauda, poucos pontos), \(d_K\) cresce muito mais rápido. O KDE, com \(h\) fixo, não tem esse ajuste.

7.1 O que a estrutura de 3 picos realmente é

O Bloco 5 encontrou 3 picos com \(h=1.0\). O que são, de fato?