# Find representatives of vector-space in set of vectors?

Suppose I have a multi-dimensional vector space $X$, and a collection of $n$ vectors $\{x_i\}_{i=1}^n \subset X$, which are not evenly "spaced-out" in $X$. I am searching for $m<<n$ of these $x_i$ that are good representatives of $X$, or in other words, they are roughly equi-distant to each other.

How can I find these representatives? What algorithm (hopefully with an available implementation in Python) could I use? Would K-Medoids be a good choice?

• What is the dimension of $X$? – nicoguaro Aug 12 '17 at 16:34
• @nicoguaro: Not too large. A couple of dimensions. With current datasets 2 or 4 - but it should be possible to have more dimensions. – Make42 Aug 12 '17 at 16:49
• @Make42 How do you define a set of vectors as "good representatives" of a space? – Stelios Aug 12 '17 at 20:04
• @Stelios: I mentioned it in the question: roughly equi-distant, so "evenly spaced-out". So they are supposed to cover the whole space. – Make42 Aug 14 '17 at 16:06

You can think of each vector as a point in your linear space. As such, we can use a simple quadtree/octree-like algorithm to map your points into boxes, with "nearby" vectors assigned to the same or an adjacent box. With $$n$$ total vectors the vector-to-box map costs $$\mathcal{O} (n\log n)$$, and once this is done you can choose $$m$$ boxes and select the vector closest to the centroid of the box to obtain your "diverse" set of vectors.

Sounds like you want to thin your data where it is dense, and learn the support of your data summarized by data points. If you don't have too many points, you can generate a distance matrix, and prune the points with the closest neighbors. (I don't think this method has a name.)

Otherwise, if you are trying to find the extremal points, then archetypal analysis might be a better direction.

• I do have a lot of points. However, currently I use clustering to find representative points, so I guess your K-nearest neighbor (KNN) idea might not be worse. Bit I am not quite sure yet, what the idea exactly is how to prune the points, without having to recreate the distance matrix over and over again (this might get expensive after a while). – Make42 Aug 14 '17 at 16:13
• Btw: Archetypal analysis has been published at arxiv.org/abs/1405.4275 and an implementation from the authors is available at github.com/yuekai/archetypes – Make42 Aug 14 '17 at 16:14

Initialize the cluster centers as your subset $V\in X$, where $V=\{x_i\}$. Then run a couple of K-mediods iterations. After that you will see that the certain vectors will come closer, essentially trying to represent similar peaks. It is then possible to merge them.

Another way to do this is mean-shift algorithm, where the modes are being updated (I think you want to find the modes). You start by over-clustering and at a dynamic number of clusters (discovered) that best represents the modes. For discrete data such as yours the medioids variation does exist.

• Mean shift is a good idea, but it is too slow, medoid shift even slower. – Make42 Apr 10 '19 at 21:22
• I am not sure I understand your first idea. Did you mean the following? 1) Initialize k-medoids with a relatively large number of instances of $X$, but fewer than elements in $X$ and run k-medoids. 2) Prune medoids that are close to each other. – Make42 Apr 10 '19 at 21:23

Another option, in the direction of clustering, could be k-Maxoids clustering:

Another answer could be (Growing) Neural Gas.