Exercícios — Aula 2: Estimação de Densidade Não-Paramétrica (\(k\)-NN e KDE)

Aprendizado Não Supervisionado

Autor

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

Data de Publicação

18 de setembro de 2026

Convenções usadas nesta lista

Os itens abaixo tratam de estimação de densidade não-paramétrica (sem assumir uma família como a Gaussiana), a partir da mesma identidade geral: fixado um ponto de consulta \(\mathbf{x}\), escolhe-se uma região pequena \(R\) (uma esfera ou um cubo) ao redor dele, de volume \(V\), contendo \(K\) dos \(N\) pontos de treino disponíveis; a densidade estimada é \(p(\mathbf{x})=K/(NV)\). Dessa identidade nascem dois métodos, conforme o que se fixa e o que se deixa livre:

\(k\)-NN para densidade: fixa-se \(K\) (um número de vizinhos) e deixa-se \(V\) crescer até que a esfera capture exatamente \(K\) pontos de treino. Chama-se \(d_K(\mathbf{x})\) a distância de \(\mathbf{x}\) ao seu \(K\)-ésimo vizinho mais próximo — o raio dessa esfera. Como o volume de uma esfera de raio \(r\) em \(D\) dimensões é proporcional a \(r^D\), tem-se \(V\propto d_K(\mathbf{x})^D\) e, substituindo na identidade geral, \(p(\mathbf{x})\propto 1/d_K(\mathbf{x})^D\).
KDE / Janela de Parzen: fixa-se o volume \(V\) de antemão (via um parâmetro de largura \(h\), com \(V=h^D\) no caso de um hipercubo) e conta-se quantos pontos de treino caem dentro dele — ou, na versão suavizada (kernel gaussiano), soma-se um peso que decai suavemente com a distância de cada ponto de treino a \(\mathbf{x}\), em vez de um corte abrupto de “dentro/fora”.

Vários itens usam como exemplo recorrente a variável radius_mean do dataset Breast Cancer Wisconsin (569 pacientes) — o raio médio do tumor medido no exame, um único número por paciente. É apenas um exemplo concreto: nenhum item exige ter visto esse exemplo antes, e toda informação necessária para resolver cada item está no próprio enunciado ou no preâmbulo do bloco a que pertence.

Questões discursivas

O ajuste de uma Gaussiana multivariada por máxima verossimilhança exige \(N>d\) (mais observações do que dimensões) para que a matriz de covariância estimada \(\hat\Sigma\) seja invertível — uma exigência estrutural do método paramétrico. Explique por que \(k\)-NN e KDE não têm essa mesma exigência formal — e, ainda assim, por que isso não significa que eles “resolveram” a maldição da dimensionalidade. Use os dois resultados a seguir na sua resposta: (i) o comprimento de aresta necessário para capturar uma fração fixa \(r\) dos dados cresce como \(r^{1/p}\) conforme o número de dimensões \(p\) aumenta; (ii) a quantidade de dados necessária para manter a mesma densidade amostral local cresce como \(N^{1/p}\).
Considere \(k\)-NN e KDE ajustados à mesma variável contínua real — por exemplo, radius_mean (o raio médio de um tumor, do dataset Breast Cancer Wisconsin). Suponha que as densidades estimadas pelos dois métodos concordem visualmente no grosso da distribuição (onde há muitos pontos de treino), mas divirjam nas caudas (regiões de poucos pontos, longe do centro da distribuição). Explique, em termos da definição de cada método (fixar \(K\) e deixar \(V\) variar, vs. fixar \(V\) e deixar \(K\) variar), por que é justamente nas regiões de baixa densidade que essa divergência deveria aparecer com mais força.
Escolha uma situação prática (pode ser fora de medicina) em que usar um estimador de densidade não-paramétrico (\(k\)-NN ou KDE) seria preferível a assumir uma família paramétrica fixa (por exemplo, uma Gaussiana multivariada) — e uma situação em que o custo de armazenar todo o conjunto de dados de treino tornaria essa escolha impraticável. Justifique os dois casos.

Questões de Verdadeiro/Falso

Cada bloco de 4 itens trata do mesmo tema. A questão só é considerada correta se todos os 4 itens forem julgados corretamente (deixar em branco tem penalidade de 20% da nota da questão).

Teste 1 — Concentração de volume na hiperesfera

□ Se \(\epsilon=0{,}5\) (a casca cobre metade do raio), a fração do volume de uma esfera de raio 1 contida nessa casca, em \(D=1\) dimensão, é exatamente \(0{,}5\).
□ Para qualquer \(\epsilon\in(0,1)\) fixo, a fração do volume contida na casca de espessura \(\epsilon\) é uma função estritamente crescente de \(D\).
□ Um argumento análogo ao da hiperesfera se aplicaria a um hipercubo de lado 1 em \(D\) dimensões: a fração do volume contida numa casca de espessura relativa \(\epsilon\) próxima da superfície do cubo também tenderia a 1 conforme \(D\to\infty\).
□ Se a massa de probabilidade de uma Gaussiana multivariada se concentra numa casca fina afastada da média em alta dimensão, isso implica que a moda da distribuição (o ponto de densidade máxima) deixa de coincidir com \(\mathbf{x}\) onde a maior parte da massa de probabilidade está localizada.

Teste 2 — As fórmulas do ESL (comprimento de aresta e distância mediana)

□ Segundo \(e_p(r)=r^{1/p}\) (o comprimento de aresta de um hipercubo centrado na origem necessário para capturar uma fração \(r\) do volume total, em \(p\) dimensões), para capturar uma fração fixa \(r<1\) dos dados, o comprimento de aresta necessário aumenta conforme \(p\) aumenta.
□ A fórmula \(d(p,N)=(1-(1/2)^{1/N})^{1/p}\) (a distância mediana, em \(p\) dimensões, do ponto mais próximo da origem entre \(N\) pontos sorteados uniformemente) prevê que, mantendo \(p\) fixo e aumentando \(N\) para infinito, essa distância mediana tende a zero.
□ Se, para \(N=500\) e \(p=10\), a distância mediana ao vizinho mais próximo da origem é \(\approx 0{,}52\) (mais da metade do raio), então, necessariamente, mais da metade dos 500 pontos está a uma distância menor que \(0{,}52\) da origem.
□ O crescimento da densidade amostral necessária, \(N^{1/p}\), e o crescimento do comprimento de aresta necessário, \(r^{1/p}\), são dois sintomas independentes da maldição da dimensionalidade, sem relação matemática direta entre si.

Teste 3 — Concentração de medida e métricas de distância

□ Se o contraste relativo \((\text{dist}_{\max}-\text{dist}_{\min})/\text{dist}_{\min}\) (a diferença entre a maior e a menor distância a um ponto de consulta, dividida pela menor) tende a zero conforme o número de dimensões \(d\) cresce, isso implica que a distância absoluta entre pontos também tende a zero.
□ Num dataset em que só um pequeno subconjunto dos atributos carrega informação relevante para a tarefa e o restante é ruído independente, aumentar \(d\) usando apenas os atributos informativos NÃO deveria produzir a mesma queda no contraste relativo observada ao aumentar \(d\) com atributos aleatórios (informativos + ruído).
□ O fato de o contraste relativo cair de \(\approx 220\) (\(d=2\)) para \(\approx 10\) (\(d=30\)) no dataset Breast Cancer Wisconsin (569 pacientes, atributos contínuos de exame) depende da escolha específica desse dataset, e um dataset sintético com atributos i.i.d. uniformes mostraria, em geral, o oposto (contraste relativo crescente com \(d\)).
□ Padronizar os atributos (subtrair a média, dividir pelo desvio) antes de calcular distâncias não altera a intensidade do fenômeno de concentração de medida.

Teste 4 — O resultado geral \(p(\mathbf{x})=K/(NV)\)

□ A derivação de \(p(\mathbf{x})=K/(NV)\) depende da suposição de que \(p(\mathbf{x})\) é aproximadamente constante dentro da região \(R\) (a vizinhança de volume \(V\) ao redor do ponto de consulta) — se essa suposição falhar (por exemplo, \(R\) grande demais numa região de densidade muito variável), a estimativa fica sistematicamente distorcida mesmo com \(N\) muito grande.
□ A aproximação \(K\simeq NP\) (onde \(P\) é a massa de probabilidade verdadeira dentro de \(R\)) é uma consequência de a distribuição binomial \(\mathrm{Bin}(K\mid N,P)\) ficar mais concentrada em torno da sua média conforme \(N\) cresce — não é uma igualdade exata para qualquer \(N\) finito.
□ Se \(V\to 0\) mantendo \(N\) fixo, a estimativa \(K/(NV)\) tende, na prática, a ficar mais estável e menos ruidosa, porque \(R\) fica mais fiel à suposição de densidade constante.
□ As duas rotas — fixar \(K\) e achar \(V\) (\(k\)-NN), ou fixar \(V\) e achar \(K\) (KDE) — produzem, em geral, estimativas numericamente idênticas ponto a ponto, para o mesmo dataset e os mesmos valores nominais de “quantos pontos” ou “que tamanho de região” foram usados.

Teste 5 — \(k\)-NN para densidade

□ A relação \(p(\mathbf{x})\propto 1/d_K(\mathbf{x})^D\) implica que, para o mesmo valor de \(d_K(\mathbf{x})\), a densidade estimada em \(D=30\) dimensões é numericamente igual à densidade estimada em \(D=2\) dimensões.
□ Se dois pontos \(\mathbf{x}_1\) e \(\mathbf{x}_2\) têm o mesmo valor de \(d_K(\mathbf{x})\) para o mesmo \(K\), o modelo de \(k\)-NN atribui a eles a mesma densidade estimada, independentemente de quaisquer outras diferenças entre suas vizinhanças.
□ Aumentar \(K\) de 5 para 50 num ponto na região mais densa dos dados produz uma variação relativa menor em \(d_K(\mathbf{x})\) do que a mesma variação de \(K\) produziria num ponto na cauda da distribuição.
□ Como o \(k\)-NN não assume nenhuma forma funcional para \(p(\mathbf{x})\), ele está imune a qualquer viés sistemático — ao contrário de um ajuste paramétrico (por exemplo, uma Gaussiana), que pode enviesar a estimativa se a forma verdadeira dos dados não for a assumida.

Teste 6 — “Isto não é uma densidade de verdade”

□ O fato de a integral de \(p(\mathbf{x})\propto 1/d_K(\mathbf{x})^D\) sobre todo o espaço divergir é uma consequência de como a cauda dessa função decai com a distância, não um erro de implementação específico de algum software.
□ Ainda que o modelo de \(k\)-NN não seja uma densidade normalizada, ele pode ser usado de forma válida para ordenar pontos do menos denso ao mais denso.
□ Se o objetivo fosse calcular a probabilidade exata de um novo ponto pertencer a uma região específica do espaço (uma integral de \(p(\mathbf{x})\) sobre essa região), o modelo de \(k\)-NN, sem modificação, forneceria essa probabilidade corretamente.
□ Normalizar a saída do \(k\)-NN dividindo pelo seu valor máximo observado no conjunto de teste resolve, por si só, o problema da integral divergente e produz uma densidade de probabilidade válida.

Teste 7 — Janela de Parzen e kernel gaussiano

□ A janela de Parzen (hipercubo, que conta 1 se um ponto de treino cai dentro dele e 0 caso contrário) e o kernel gaussiano (que atribui um peso que decai suavemente com a distância) produzem a mesma estimativa de densidade sempre que a largura \(h\) é escolhida de forma equivalente nos dois casos, porque ambos implementam exatamente a mesma função de peso.
□ Um ponto de treino localizado exatamente na borda de um hipercubo de largura \(h\) centrado num ponto de consulta \(\mathbf{x}\) pode contar ou não para \(K\), dependendo de detalhes de borda (inclusão estrita ou não) que não têm análogo no kernel gaussiano, que atribui peso positivo (ainda que pequeno) a qualquer distância finita.
□ As condições que definem um kernel válido — peso sempre não-negativo e integral total igual a 1 — seriam violadas por um kernel gaussiano com \(h\) negativo, mas não por nenhuma outra escolha razoável de \(h>0\).
□ Trocar o kernel gaussiano por um kernel uniforme (janela dura) de mesma largura \(h\) elimina completamente a possibilidade de descontinuidades na densidade estimada.

Teste 8 — \(h\) como parâmetro de suavização

□ No limite \(h\to 0^+\), cada ponto de treino distinto se torna, ele mesmo, um pico isolado da densidade estimada — no limite, até \(N\) picos, um por ponto de treino.
□ Se dois datasets diferentes têm o mesmo número de pontos \(N\) mas escalas muito diferentes (um varia entre 0 e 1, outro entre 0 e 1000), usar o mesmo valor absoluto de \(h\) para os dois produzirá, em geral, graus de suavização relativa muito diferentes.
□ O trade-off entre \(h\) pequeno (estimativa ruidosa, com muitos picos espúrios) e \(h\) grande (estimativa borrada, que esconde estrutura real) é conceitualmente o mesmo trade-off entre viés e variância discutido em outros contextos de ajuste de modelo — \(h\) pequeno tende a variância alta, \(h\) grande tende a viés alto.
□ Escolher \(h\) de forma a minimizar o erro no próprio conjunto de treino (sem nenhuma validação separada) tende a favorecer valores de \(h\) artificialmente pequenos.

Teste 9 — \(k\)-NN vs. KDE: suavização adaptativa vs. fixa

□ A vantagem da suavização adaptativa do \(k\)-NN (o raio \(d_K\) cresce ou encolhe conforme a densidade local) é mais pronunciada em datasets onde a densidade real varia muito de uma região para outra do que em datasets aproximadamente uniformes.
□ Como o \(k\)-NN adapta \(d_K(\mathbf{x})\) à densidade local, ele nunca pode sofrer do mesmo problema de “borrar estrutura real” que o KDE sofre com \(h\) grande demais.
□ Se dois pontos de consulta estão na mesma região densa dos dados, mas um deles coincide exatamente com um ponto de treino e o outro não, isso não deveria, em geral, causar uma diferença grande em \(d_K(\mathbf{x})\) para \(K\) moderado ou grande.
□ Suponha que, para uma mesma variável contínua real, as curvas de densidade estimadas por KDE e por \(k\)-NN concordem visualmente no grosso da distribuição. Essa concordância entre dois métodos independentes, com mecanismos de suavização diferentes, seria esperada mesmo se um dos dois estivesse capturando um artefato espúrio (uma estrutura que não existe na população real) e o outro não.

Teste 10 — Custo computacional e armazenamento

□ A necessidade de armazenar todo o conjunto de treino, comum a \(k\)-NN e KDE, é uma consequência de esses métodos não resumirem os dados em um número fixo de parâmetros — ao contrário de um ajuste paramétrico (por exemplo, Gaussiano), que resume \(N\) pontos em um vetor de médias e uma matriz de covariância, de tamanho fixo independente de \(N\).
□ Se o objetivo fosse só classificar um único ponto novo (não estimar densidade em toda parte), o custo de avaliar \(k\)-NN ou KDE nesse único ponto ainda cresceria, em geral, com \(N\).
□ Construir uma estrutura de busca em árvore para os dados de treino (uma otimização computacional comum para acelerar a busca pelos vizinhos mais próximos) elimina completamente a necessidade de armazenar o conjunto de treino.
□ O custo de armazenamento de \(k\)-NN/KDE e a exigência \(N>d\) para que a matriz de covariância de um ajuste Gaussiano seja invertível são, ambos, formas do mesmo problema subjacente: dados insuficientes relativos à complexidade do modelo.

Teste 11 — Maldição da dimensionalidade em métodos não-paramétricos

□ Como \(k\)-NN e KDE não assumem nenhuma família paramétrica, eles não sofrem de nenhuma versão da maldição da dimensionalidade — só um ajuste paramétrico (como uma Gaussiana) sofre desse problema.
□ Manter a mesma densidade amostral (cobertura local) ao passar de \(p=1\) para \(p=10\) dimensões exigiria multiplicar o tamanho do conjunto de dados por um fator que cresce exponencialmente com \(p\) (segundo a relação densidade amostral necessária \(\propto N^{1/p}\)).
□ O fato de \(k\)-NN e KDE precisarem armazenar todo o conjunto de treino é agravado, não resolvido, pelo crescimento da quantidade de dados necessária em alta dimensão — os dois problemas se combinam.
□ Uma forma de escapar completamente da maldição da dimensionalidade, para qualquer método não-paramétrico, é aumentar \(N\) até que \(N>2^d\).

Teste 12 — \(d_K(\mathbf{x})\) como métrica reaproveitável

□ Reaproveitar \(d_K(\mathbf{x})\) (a distância de \(\mathbf{x}\) ao seu \(K\)-ésimo vizinho mais próximo) como métrica de densidade local para construir um grafo de proximidade é possível porque essa quantidade já é, por definição, inversamente relacionada à densidade local: \(d_K\) pequeno indica região densa, \(d_K\) grande indica região esparsa — a mesma quantidade, um uso diferente.
□ Se dois pontos \(\mathbf{x}_1,\mathbf{x}_2\) pertencem à mesma região de alta densidade, é razoável esperar que \(d_K(\mathbf{x}_1)\) e \(d_K(\mathbf{x}_2)\) sejam parecidos entre si, para o mesmo \(K\).
□ Usar \(d_K(\mathbf{x})\) para construir caminhos num grafo exige, necessariamente, resolver primeiro o problema de a integral de \(1/d_K(\mathbf{x})^D\) divergir — sem isso, a construção do grafo não é matematicamente válida.
□ A escolha de \(K\) que funciona bem para estimar densidade (nem pequeno, nem grande demais) é, a priori, um bom candidato para o mesmo papel de parâmetro de suavização em outro uso da mesma quantidade \(d_K(\mathbf{x})\) (por exemplo, para construir um grafo de proximidade), ainda que a validação final dependa do objetivo específico dessa outra tarefa, não só da qualidade de estimativa de densidade isolada.

Aviso

As questões de Verdadeiro/Falso e discursivas ficam sem solução neste arquivo — são para resolução autônoma do aluno, fora do horário de aula.