3
$\begingroup$

I am exploring some ideas around dating site matching, and I can do with some ideas as to which is the better solution

Senario: We have a boy and girl, the boy has completed his profile/bio thoroughly while the girl hasn't or maybe she just doesn't like a lot of things, so this is what the data looks like

Boy likes:                  Girl likes:
---------                   -----------
Painting                    Painting
Movies                      Movies
Long walks                  Long walks  
Harry Potter                Harry Potter
Dogs                        Dogs
Pizza                       Pizza
Computer Science            Computer Science
Mercedes                    Ford
Traveling                   Daisies
Diving                      Psycology
...

Total things
---------------------------------------
100                         10

They share 7 things in common. To the girl the boy is a 70% match which is great But to the boy the girl is only a 7% match

Maybe the girl would have more in common if she had more in her list of likes so maybe giving their match a 7/100 is a match missed and maybe that's all she likes and 7/100 is the best they'll ever match but even then, it still might be a good match because maybe the boy over filled his list of things he likes while the girl chose carefully what she really likes.

I am looking for ideas for an algorithm that would give the best match score to order them in lists with other people/matches who might have small percentage in matches because their lists of things they like are 1000s of entries long for example

Edit: I will not be matching strings, each of strings in the table above will have a unique ID in an RDBMS database. A table will be used to link users and topics

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Conceptually, what do you intend a match score to represent? Presumably you don't want to just match up a series of text strings, since that by itself doesn't really mean anything. You gotta figure out some consistent reason for looking at those strings of text in the first place, and then once you're able to precisely specify why they're relevant, you can construct a model and derive a method for combining 7% with 70%. $\endgroup$
    – Nat
    Commented Apr 9, 2017 at 13:06
  • 1
    $\begingroup$ I don't think this question is about 'matching', in the meaning of graph matching. The question seems to be how to determine the similarity between two lists of different length. This score can lead to the value in a weighted matching, but solving this matching is not the question here. $\endgroup$
    – Discrete lizard ♦
    Commented Apr 13, 2017 at 10:17
  • 2
    $\begingroup$ Consequently, I think this question is only tangentially related to CS, but I suppose that would depend on the type of answers. $\endgroup$
    – Discrete lizard ♦
    Commented Apr 13, 2017 at 10:20
  • $\begingroup$ First thing that comes in my mind is make a weighted list. This can certainly improve things a bit. The idea of matching string is a bit naive anyway. There may be different strings with very close semantic areas (as @Nat suggested). I bet you can find something more sophisticated in the literature. $\endgroup$
    – Manlio
    Commented Apr 13, 2017 at 11:02
  • 2
    $\begingroup$ Free clue: the reason your question has not received enough attention is that we've explained to you how it's vague and under-specified. If you want people to answer it, make the question better. $\endgroup$
    – David Richerby
    Commented Apr 13, 2017 at 11:09

2 Answers 2

Reset to default
4
+25
$\begingroup$

It seems you're looking for a symmetric set similarity measure. (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$. Set similarity since each person's preference is defined by a set of objects.)

A number of these are used in the CS literature. Probably the most common is Jaccard similarity, defined by $|A\cap B|/|A\cup B|$. In your example, $A$ and $B$ have 7 elements in common, and there are 103 elements between them, leading to a similarity of $7/103$. A similar metric is Braun-Blanquet similarity, $|A\cap B|/\max\{|A|,|B|\}$; in your example this gives $7/100$. With these as starting points you may be able to find further metrics that capture what you want better. For example, here's a list I found while writing this.

What's notable about these metrics is that they don't take each person's dislikes into account---the similarity is defined only by what's on their list, not what's not on it. (So you may think it makes a better match if two people don't like fish.) Incorporating this would require a universe of elements (so any element in the universe not on the list is considered a dislike). In this case you can use the classic Hamming Distance. You have other options as well, like Euclidean distance or even the Sørensen-Dice similarity.

One benefit of using one of the above, well-known similarity measures is that you can use known algorithms to compute nearest neighbors quickly.

Improve this answer
$\endgroup$
2
$\begingroup$

If you want to weight then cosine_similarity is an option. What this does is weight items that are not common in the population higher. Not sure how but I would base uniqueness on the two populations separately. Some very common among women but uncommon among men should still have high weighting. You could have the people rank their list and use that as the weighting.

You need to be careful that checking a small number of items or a large number of items does not produce more matches as people will cheat the system and check a lot or a few.

I think it should be symmetric. The match from A to B should equal the match from B to A.

Not weighted you take the number of matches and divide by a number. The question is what number to use to for the denominator.

  • Simple average (x+y)/2
  • Geometric mean sqrt(xy)
  • Hamonic mean 2xy/(x+y)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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