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
  • 1
    @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

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.

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

Another answer could be Neural Gas.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.