5
$\begingroup$

We have boring CSV with 10000 rows of ages (float), titles (enum/int), scores (float). How to select 1000 most different rows? I look for a general solution that would work for more than one case.

What do I mean by different:

  • We have N columns each with int/float values in a table.
  • You can imagine this as points in ND space
  • We want to pick K points that would have maximised distance between each other.

So if we have 100 points in a tightly packed cluster and one point in the distance we would get something like this for three points: enter image description here or this enter image description here

It looks like an ND point cloud "triangulation" with a given resolution yet not for 3d points... So how to select K most distant rows (points) from N (with any complexity)?

$\endgroup$
  • $\begingroup$ Please move this question to Stackoverflow(stackoverflow.com/questions/ask) $\endgroup$ – 10xAI Jun 25 '20 at 2:06
  • 2
    $\begingroup$ I think this is a reasonable question to keep here. There are different metrics worth considering for how different all of the rows are from one another (i.e. something like Hamming distance) which fits into data science. $\endgroup$ – Derek O Jun 25 '20 at 5:05
  • $\begingroup$ This question could be improved a lot if you clarify a) what exactly your rows represent b) what you want to achieve by selecting 'the most different rows'. $\endgroup$ – Valentas Jun 25 '20 at 7:03
  • 1
    $\begingroup$ Then you are certainly looking for Archetypal Analysis $\endgroup$ – Kasra Manshaei Jun 25 '20 at 15:40
3
$\begingroup$

To select the most different rows, you would need to define first what you consider different. For ages and scores, subtracting values would work, for example:

Row1

  • Age is 38
  • Score is 0.2

Row2

  • Age is 87
  • Score is 1.0

Difference by numeric feature:

  • Age Diff is 49
  • Score Diff is 0.8

Those values could be normalized or weighted to account for different importances between features.

For titles, you’d probably need to use a text similarity metric, such as tf-idf with cosine similarity or embedding vector distance. The most different ones are the ones with higher score/age difference and lower title similarity.

$\endgroup$
2
$\begingroup$

Welcome to the community!

There are more intuitive ways to do this like calculating pair-wise distances from vectors in the space but this is not scalable properly. The second point is that even if you want to go this way, it is better to put them in a weighted graph through e.g. Networkx library and then find longest path between two nodes or detecting communities there and take representatives from different community (the latter is a interesting way because 1000 most different items could be seen as representatives of 1000 different clusters in the data and not necessarily the furthest points)

But I would like to draw your attention to Archetypal Analysis, a matrix factorization method in which all data points are defined based on their projection on points which lie on the convex hall of the data.

Those archetypes are probably what you are looking for.

Combining two methods above, results in Community Detection using Peripheral Vertices which might be useful for your project (Disclaimer Note: I am the author of that algorithm).

Hope it helped. Good Luck!

$\endgroup$
0
$\begingroup$

You can calculate the pairwise distance among the rows, if you use python using pairwise_distances available here. Then select the first row as p1, pick the least similar column say, p2. go to a2 and select the least similar that is not p1. continue process to find x number of points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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