Página Inicial

Differential Nearest Neighbors Regression

Este algoritmo foi criado por Nader, Sixt e Landgraf, que o publicaram num artigo em 2022.

Como funciona

Sejam (X_1,Y_1), \dots, (X_n,y_n) \in \mathbb{R}^d \times \mathbb{R} os nossos dados. O nosso objetivo é, dado um novo (query point), estimar o correspondente (target value). Uma boa estimativa é (que é aquilo que vamos tentar aproximar).

O Differential Nearest Neighbors Regression (DNNR) é uma generalização do kNN Regression. A maneira como o kNN regression estima o target value de um query point é simplesmente calculando a média dos target values dos k vizinhos mais próximos

( é o conjunto dos k pontos mais próximos de x)

Podemos ver Y_m como sendo a aproximação de Taylor de ordem 0 de eta(x). A ideia do DNNR é usar aproximações de Taylor de maior ordem.

Dado um ponto w próximo de x, podemos aproximar eta usando o Taylor de ordem 1

Por isso, se conhecessemos o gradiente, o DNNR de ordem 1 ficaria assim:

No entanto, não conhecemos a função eta (caso contrário o problema estaria resolvido), por isso vamos aproximar o gradiente de eta em X_m por

Onde é a matriz que tem os vetores como linhas, é o número de pontos mais próximos a X_m usados para aproximar o gradiente, e i corresponde aos indices desses t pontos. Analogamente, q é o vetor de coordenadas . Ficamos então com

Implementação

Foram precisos os seguintes packages:

import numpy as np import pandas as pd from scipy.spatial.distance import euclidean import scipy.optimize as scp

Comecei por criar a classe dnnr. No método __init__ simplesmente definimos os parametros k e t. O train tem como input dois dataframes do Pandas, correspondentes à matriz que tem os X_m com linhas, e o vetor coluna com os correspondentes target values.

class dnnr: #t é o numero de vizinhos a considerar quando se calcula a aproximação do gradiente def __init__(self, k, t): self.k = k self.t = t self.X_train = None self.y_train = None def train(self, X_train, y_train): self.X_train = X_train self.y_train = y_train

Depois a esta classe acrescentei o método predict, que tem como input um dataframe.

def predict(self, X): y = [] for row in X.values: closest_neighbors_i = closest_neighbors_indexes(row, self.X_train.values, self.k) predictions = [] for index in closest_neighbors_i: X_m = self.X_train.iloc[index].values Y_m = self.y_train.iloc[index].values closest_ineighbors_j = np.delete(closest_neighbors_indexes(X_m, self.X_train.values, self.t + 1), 0) neighbors_X_m = self.X_train.iloc[closest_neighbors_j].values neighbors_Y_m = self.y_train.iloc[closest_neighbors_j].values gamma = grad_aprox(X_m, Y_m, neighbors_X_m, neighbors_Y_m) pred = Y_m + gamma * (X_m - row) predictions.append(pred) y_m = np.mean(predictions) y.append(y_m) return pd.DataFrame(y, columns=[self.y_train.columns[0]])

E também temos as funções auxiliares que aparecem no método predict:

def distances(row, X): distances_list = [] for row_X in X: distances_list.append(euclidean(row, row_X)) return distances_list def closest_neighbors_indexes(row, X, k): d = distances(row, X) closest_neighbors_i = np.argsort(d)[:k] return closest_neighbors_i def build_A(X, x_m): A = [] for row in X: A.append((row - x_m)*(1/(euclidean(row,x_m)+.1))) return np.array(A) def grad_aprox(X_m, Y_m, neighbors_X_m, neighbors_label): A = build_A(neighbors_X_m, X_m) q = neighbors_label - Y_m q = np.transpose(q)[0] for i in range(0,len(q)): q[i] *= 1/(euclidean(X_m, neighbors_X_m[i])) gamma = scp.lsq_linear(A,q).x return gamma