Algoritmo de clasificación basado en las distancias medias de un punto de prueba a los puntos de cada clase

Question

¿Existe algún algoritmo de clasificación que asigne un nuevo vector de prueba al clúster de puntos cuya distancia media sea mínima?

Déjenme escribirlo mejor: Imaginemos que tenemos $K$ grupos de $T_k$ puntos cada uno. Para cada cluster k, calculo la media de todas las distancias entre $x(0)$ y $x(i)$ , donde $x(i)$ es un punto de la agrupación $k$ .

El punto de prueba se asigna al clúster con el mínimo de esas distancias.

¿Cree que es un algoritmo de clasificación válido? En teoría, si los clústeres están "bien formados" como los que se tienen después de un mapeo discriminante lineal, deberíamos ser capaces de tener una buena precisión de clasificación.

¿Qué opinas de este algo? Lo he intentado, pero el resultado es que la clasificación está fuertemente sesgada hacia el clúster con el mayor número de elementos.

def classify_avg_y_space(logging, y_train, y_tests, labels_indices):
    my_labels=[]
    distances=dict()
    avg_dist=dict()
    for key, value in labels_indices.items():
        distances[key] = sk.metrics.pairwise.euclidean_distances(y_tests, y_train[value])
        avg_dist[key]=np.average(distances[key], axis=1)

    for index, value in enumerate(y_tests):
      average_distances_test_cluster = { key : avg_dist[key][index] for key in labels_indices.keys() }
      my_labels.append(min(average_distances_test_cluster, key=average_distances_test_cluster.get))
    return my_labels

Answer 1

Es una buena idea, pero tiene un gran defecto: es demasiado sensible a la dispersión de los datos.

Para aclarar la cuestión, dado $k$ grupos disjuntos $ C_1, \ldots, C_k $ se pregunta si tiene sentido clasificar una nueva muestra $ x^* $ según la norma $$ \arg\min_{i\in \left[k\right]} \frac{1}{\left| C_i \right|} \sum_{x \in C_i } \left\Vert x - x^*\right\Vert $$

Obsérvese que esta regla es efectivamente similar a reglas que existen como algoritmos bien conocidos, como $$ \arg\min_{i\in \left[k\right]} \min_{x \in C_i } \left\Vert x- x^*\right\Vert $$ que es en realidad 1-Nearest-Neighbors, o $$ \arg\min_{i\in \left[k\right]} \left\Vert \frac{1}{\left| C_i \right|} \sum_{x \in C_i }x - x^*\right\Vert$$ que en sklearn se llama NearestCentroid pero es utilizado por k-Means para la asignación de clusters y puede ser visto en LDA en el caso en que la matriz de covarianza subyacente es la identidad (hasta el escalar). (Nótese que, en general, LDA también tiene en cuenta la forma [dispersión + orientación] de los clusters).

En muchos casos, la norma propuesta se comportará de forma similar a NearestCentroid especialmente si los conglomerados están bien separados y tienen una varianza similar (en tal caso, creo que es posible acotar la distancia media en términos de la distancia al centroide).

Sin embargo, como promedia las distancias entre todos los puntos del clúster, tiene un sesgo evidente hacia los clústeres de baja varianza. Creo que este es el verdadero origen del etiquetado erróneo que has observado.

Para ilustrar este efecto, podemos trazar el límite de decisión de nuestros clasificadores. Los gráficos se basan descaradamente en sklearn 's ejemplo .

En el gráfico anterior, he generado dos conjuntos de datos a partir de diferentes distribuciones normales. El violeta procede de $$ \mathcal{N}\left(\begin{pmatrix}0 \\ 3\end{pmatrix}, \begin{pmatrix}10 & 2 \\ 2 & 1\end{pmatrix}^2\right)$$ y el amarillo vino de $$ \mathcal{N}\left(\begin{pmatrix}0 \\ -3\end{pmatrix}, \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}\right)$$ A continuación, cada punto del espacio se colorea según la regla. La línea que separa las regiones es el límite de decisión. Hay 200 puntos en el grupo violeta y 50 en el grupo amarillo. La página web + marca el centroide de cada cluster. Obsérvese que el clúster violeta no está alineado con los ejes para resaltar la diferencia entre el LDA y el centroide más cercano.