Re:Fuzzy string matching using cosine similarity
by timClicks on Monday September 21, 2015 @04:59AM
(#10251131)
Would this be able to find near matches within substrings, e.g. a search for "house" in "this is my hiuse typo" would bring back a near match result?
[ Parent
| on HN ]
Re:Fuzzy string matching using cosine similarity
by afandian on Monday September 21, 2015 @05:53AM
(#10251276)
No. The character distribution of those two strings is massively different. You'd have to tokenize the long string into words first.
EDIT: If I understood correctly and the vectors are normalised, it would match 'house' to 'hiusehiusehiuse'. Which may or may not be desirable.
Re:Fuzzy string matching using cosine similarity
by dalke on Monday September 21, 2015 @07:10AM
(#10251484)
The vectors are not normalized. That is:
from __future__ import print_function
from collections import Counter
def cosine_similarity_unweighted(a, b):
a = Counter(a)
b = Counter(b)
dotProduct = sum((c in a) * (c in b) for c in a)
magnitudeA = sum(1 for c in a)
magnitudeB = sum(1 for c in b)
return dotProduct / (magnitudeA * magnitudeB)**0.5
def cosine_similarity_weighted(a, b):
a = Counter(a)
b = Counter(b)
dotProduct = sum(a.get(c, 0) * b.get(c, 0) for c in a)
magnitudeA = sum(value**2 for value in a.values())
magnitudeB = sum(value**2 for value in b.values())
return dotProduct / (magnitudeA * magnitudeB)**0.5
print("Scores for 'hello' and 'holl'")
print("unweighted", cosine_similarity_unweighted("hello", "holl"))
print("weighted", cosine_similarity_weighted("hello", "holl"))
gives the output: Scores for 'hello' and 'holl'
unweighted 0.866025403784
weighted 0.925820099773
The article gives: holl index: 0.9258200997725514
which means the article used letter weights.That said, the scores for your example are the same, because each of the letters in 'house' is used only once (the 3 in the numerator cancels out the 3 in the denominator):
Scores for 'house' and 'hiusehiusehiuse'
unweighted 0.8
weighted 0.8
If the query had instead been 'houss', you would see a difference in the similarities: Scores for 'houss' and 'hiusehiusehiuse'
unweighted 0.67082039325
weighted 0.676123403783