0
$\begingroup$

How would you solve the following problem... Theres a table filled with data like this:

Data1: 50 51 48 55 50
Data2: 51 49 52 50 51
Data3: 49 53 50 51 48
Data4: 48 50 52 51 53
Data5: 47 50 51 54 49
Data6: 50 48 50 49 52
Data7: 51 50 51 49 51
Data8: 48 51 49 50 50
...

The goal is to create pairs from the table, based on similarity of the rows.

As i learned from the comments, it is matching, thx :)

A difference bigger than 3 is not allowed.

When values are close to each other, they should be paired, for example

Data2: 51 49 52 50 51
Data7: 51 50 51 49 51

have very close values and should be a paired/grouped. So if this is our first pair, what is the next one? And how to handle outliers (in the columns)? For example

Data1: 50 51 48 55 50

has in the fourth column the value 55. With the criteria no bigger difference than 3, the only possible companion is Data5:

Data5: 47 50 51 54 49
Data1: 50 51 48 55 50

But in cloumn 1 and 3 the delta is 3, so in the mean maybe it isnt such a good choice.

Outlier who couldnt be assigned because of the too big deviation, will not be considered. The algorithm has not to be efficient.

Maybe you can see that it is just not clear for me, how to check the data against each other. To match the best fitting rows together.

So to answer the question about the use: each datarow is one measured device. You need two devices for the signal reproduction. For the best reproduction result you need maximum coherence between those two. So perfect would be an ideal match. So the goal is to find the best matching devices in the table.

$\endgroup$
  • $\begingroup$ If the efficiency of the algorithm is of no concern, just compare all possible pairs. $\endgroup$ – adrianN Jan 17 '17 at 10:59
  • 2
    $\begingroup$ It is possible to create pairs and check validity. To sort by (decreasing) correlation, you need to define a measure. $\endgroup$ – greybeard Jan 17 '17 at 12:04
  • $\begingroup$ "But not just based on the average of each row, but rather in dependency of the values to one another." Is not clear. $\endgroup$ – paparazzo Jan 17 '17 at 12:16
  • $\begingroup$ I don't think this is a sort. Since your just pairing I think the Stable Marriage Problem can be used to solve this. en.wikipedia.org/wiki/Stable_marriage_problem $\endgroup$ – user3853544 Jan 17 '17 at 13:53
  • 1
    $\begingroup$ Maybe you can see that it is just not clear for me If you (who else would you expect to?) can't pin down how to define a "distance" (sum off absolute differences/squares are somewhat common), try to describe its use: what is this grouping good for? $\endgroup$ – greybeard Jan 17 '17 at 16:45
2
$\begingroup$

This isn't sorting: it's matching. The vertices of your graph are the data rows and there's an edge between two vertices if the two rows are compatible for pairing (e.g., have no difference bigger than 3, or whatever criterion you want to use). You're looking for a maximum matching, i.e., a biggest-possible pairing between compatible rows.

It's unclear in your question but you might instead want to define a weighted graph where the weight of an edge is the amount of compatibility (e.g., rows that are very close have a high weight, rows that aren't so close have a low weight, rows that are incompatible have no edge, as before) and compute a maximum-weight matching.

$\endgroup$
  • $\begingroup$ Thanks for your advice! Hmm I'm not sure if I'm skilled enough to solve this maximum weighted matching problem, since I'm an beginner in programming for 8 years now ;-). Do you think with my basic knowledge of Java and Matlab it is possible for me? And I think yes, the weighted graph in this case would be data0: 50 50 50 50 50 $\endgroup$ – eyjin Jan 19 '17 at 8:38
  • $\begingroup$ It's a standard algorithm so you'll probably find it implemented by libraries. You'll also need to set up the weights. But programming advice is off-topic, here: Stack Overflow will probably be able to help you. $\endgroup$ – David Richerby Jan 19 '17 at 8:40

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.