Classification algorithm based on average distances from a test point to the points in each class

Question

Is there any classification algorithm that assign a new test vector to the cluster of points whose average distance is minimum?

Let me write it better: Let's imagine that we have $K$ clusters of $T_k$ points each. For each cluster k, I calculate the average of all the distances between $x(0)$ and $x(i)$, where $x(i)$ is a point in the cluster $k$.

The test point is assigned to the cluster with minimum of such distances.

Do you think this is a valid classification algorithm? In theory, if the cluster are "well-formed" like you have after a linear fished discriminant mapping, we should be able to have good classification accuracy.

What do you think of this algo? I've tried but the result is that the classification is strongly biased towards the cluster with the biggest number of elements.

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

It is a nice idea, but has one major flaw - it is too sensitive to the spread of the data.

To clarify the question, given $k$ disjoint clusters $ C_1, \ldots, C_k $, you ask whether it makes sense to classify a new sample $ x^* $ according to the rule $$ \arg\min_{i\in \left[k\right]} \frac{1}{\left| C_i \right|} \sum_{x \in C_i } \left\Vert x - x^*\right\Vert $$

Note that this rule is indeed similar to rules that exist as well known algorithms, like $$ \arg\min_{i\in \left[k\right]} \min_{x \in C_i } \left\Vert x- x^*\right\Vert $$ which is in fact 1-Nearest-Neighbors, or $$ \arg\min_{i\in \left[k\right]} \left\Vert \frac{1}{\left| C_i \right|} \sum_{x \in C_i }x - x^*\right\Vert$$ which in sklearn is called NearestCentroid, but is used by k-Means for cluster assignment and can be seen in LDA in the case where the underlying covariance matrix is the identity (up to scalar). (Note that in general, LDA also takes into account the shape [spread + orientation] of the clusters).

In many cases, the proposed rule will behave similarly to NearestCentroid, especially if the clusters are well separated and have similar variance (in such case, I think it is possible to bound the average distance in terms of the distance from the centroid).

However, as it averages distances over all the points in the cluster, it is blatantly biased toward low-variance clusters. I believe is the true source of the mislabelling you noticed.

To illustrate this effect, we can plot the decision boundary of our classifiers. Plots are shamelessly based on sklearn's example.

In the preceding plot, I generated two datasets from different normal distributions. The violet came from $$ \mathcal{N}\left(\begin{pmatrix}0 \\ 3\end{pmatrix}, \begin{pmatrix}10 & 2 \\ 2 & 1\end{pmatrix}^2\right)$$ and the yellow came from $$ \mathcal{N}\left(\begin{pmatrix}0 \\ -3\end{pmatrix}, \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}\right)$$ Then, each point in the space is colored according to the rule. The line separating the regions is the decision boundary. There are 200 points in the violet cluster and 50 in the yellow cluster. The + marks the centroid of each cluster. Note that the violet cluster is not aligned with the axes in order to emphasize the difference between LDA and Nearest Centroid.