¿Es el cálculo de una media móvil una buena forma de aproximarse a la regresión k-nearest neighbor?

Question

Dadas muestras i.i.d ( x ₁ , y ₁ ), ... ( x _n , y _n ) tal que y _i \= f ₀ ( x _i ) + $\epsilon$ _i , i \= 1,... n para algunos f ₀

Supongamos que quiero una estimación $\hat{f}$ de f ₀ utilizando k -regresión del vecino más próximo en la vecindad de cada x _i en mi conjunto de datos. Así, para cada x _i Debo buscar el k elementos vecinos más cercanos y tomar la media del conjunto de todos los y _j tal que j $\in$ $\mathcal{N}$ _k ( x _i ) donde $\mathcal{N}$ _k ( x ) contiene el k puntos más cercanos de x :

$$\hat{f}(x_i) = \frac{1}{k}\sum_{j\in\mathcal{N}_k(x_i)} y_j$$

Ahora bien, si mi x _i están todos espaciados uniformemente, entonces podría simplemente ordenarlos en orden ascendente y calcular una media móvil sobre los elementos correspondientes en y con tamaño de ventana k . Mi pregunta es: ¿Será esta media móvil aproximadamente equivalente a k -regresión de vecinos más próximos, incluso si ( x ₁ , ... x _n ) no están espaciados uniformemente? ¿Hay alguna prueba que pueda hacer sobre la distribución P (x) para comprobar la calidad de la aproximación?

Answer 1

Supongamos que x[i] es la entrada, e i es la posición de la entrada. El siguiente algo será muy eficiente.

sum = 0
count = 0
leftindex = i-1
rightindex = i+1
while (count < k) {
    if(abs(x[leftindex] - x[i]) > abs(x[rightindex] - x[i])) {
        sum = sum + y[rightindex]
        rightindex = rightindex + 1
    } else {
        sum = sum + y[leftindex]
        leftindex = leftindex - 1
    }
    count = count + 1
}
result = sum / k

Por supuesto, hay que hacer algunas comprobaciones adicionales de los límites a izquierda y derecha, para no caerse de los extremos. O puedes rellenar los datos con k puntos lejanos a la derecha k puntos lejanos a la izquierda antes de ejecutarlo. Además, esto no incluye el punto de entrada. Si eso es un requisito puede simplemente establecer la suma a y[i] inicialmente y contar hasta 1.