Sampling n data points from high dimensional data

Question

I have some face images(of a single person), which I ran through an embedding generator to get 128-dimensional embedding.

I have 1000 such embedding (shape of the dataset (1000, 128)). I have a restriction on the number of embeddings that can be used to train the model (100 embeddings). I want to pick 100 embeddings from all 1000 which will represent all 1000 embeddings.

My question is, how can I choose the best 100 embeddings which will represent the entire 1000 embeddings.

Some things I have tried out.

1. Picking the 100 farthest points in the cluster. (all the images are edge cases like blurred image, improper pose e.t.c)
2. Random sampling ( works ok but sometimes pick embeddings which were calculated from a face which was having some problem, like blurred e.t.c.)

There is one more thing, I have thought of but not tested. Sampling with probability. Probability = 1/(euclidean_distance of point from cluster centroid).

I wanted to know if there are any alternatives, that I can look into which can provide better results.

Answer 1

One approach will be to run an unsupervised clustering algorithm of your choosing, parameterized to return a 100-cluster solution. If there are indeed groups of images, you should see that similar images fall into the same cluster. You can then select a representative image from each cluster, perhaps identified as the image with the highest average correlation with or lowest average distance from other images in the same cluster. This will help you avoid oversampling images that have high similarity, although you may want to look out for highly distinct singleton clusters - those might be useful datapoints, or just outliers that you might not want to train on at all.

Answer 2

One option is to use something like seeding technique of k-means++ to pick representative sample of data points. K-means++ picks each subsequent cluster center from the remaining data points with probability proportional to its squared distance from the point's closest existing cluster center.

Answer 3

So this may not be as direct of an answer as you were hoping for, but the truth is that it really depends.

IF the images are properly embedded for your problem, i.e. the geometric relationship between points is truly reflective of the differences in features that you care about, then this should be simple and Nuclear Hoagie's clustering idea could work (as long as you don't have so many clusters that a number of dissimilar ones get combined when restricting the number of clusters to 100), as would a random sampling or a method that tries to find the set of 100 points that span as much of the search space as possible while remaining roughly equidistant from each other (possibly better in cases where it's very hard to define clusters due to the distribution of points).

In other words, it sounds like the issues you're having are largely due to the embeddings and the data itself (i.e. blurry images should be thrown out or heavily preprocessed and sharpened so the blurry feature isn't emphasized so heavily in the embedding). Also the number of images your working with sounds very low if you're training anything from scratch as opposed to an off the shelf embedding model or something well-trained using transfer learning).

How are you generating your embeddings and what kind of image preprocessing are you doing?