8

I know it's possible to return how similar two strings are by using the following function:

from difflib import SequenceMatcher
def similar(a, b):
    output=SequenceMatcher(None, a, b).ratio()
    return output

In [37]: similar("Hey, this is a test!","Hey, man, this is a test, man.")
Out[37]: 0.76
In [38]: similar("This should be one.","This should be one.")
Out[38]: 1.0

But is it possible to score two dictionaries based on the similarity of keys and their corresponding values? Not a number of in common keys, or what is in common, but a score from 0 to 1, like the example above with strings.

I'm trying to find the similarity score between ratings['Shane'] and ratings['Joe'] in this dictionary:

ratings={'Shane': {'127 Hours': 3.0, 'Avatar': 4.0, 'Nonstop': 5.0}, 'Joe': {'127 Hours': 5.0, 'Taken 3': 4.0, 'Avatar': 5.0, 'Nonstop': 3.0}}

I am using Python 2.7.10

11
  • And what's the expected output? The number of common keys? (like the keys are the same except Taken 3. Or the actual values? What about multi-level dictionaries?
    – fodma1
    Commented Mar 14, 2016 at 6:36
  • Check out the en.m.wikipedia.org/wiki/Jaccard_index Pretty easy implement from a suitable set.
    – JL Peyret
    Commented Mar 14, 2016 at 6:36
  • 2
    Result will depend on your metric.
    – Lol4t0
    Commented Mar 14, 2016 at 6:37
  • @fodma1 I'm hoping to find something that takes everything into account. Commented Mar 14, 2016 at 6:37
  • Are you wanting some correlation coefficient? Commented Mar 14, 2016 at 6:43

3 Answers 3

7
import math

ratings={'Shane': {'127 Hours': 3.0, 'Avatar': 4.0, 'Nonstop': 5.0}, 'Joe': {'127 Hours': 5.0, 'Taken 3': 4.0, 'Avatar': 5.0, 'Nonstop': 3.0}}

def cosine_similarity(vec1,vec2):
        sum11, sum12, sum22 = 0, 0, 0
        for i in range(len(vec1)):
            x = vec1[i]; y = vec2[i]
            sum11 += x*x
            sum22 += y*y
            sum12 += x*y
        return sum12/math.sqrt(sum11*sum22)

list1 = list(ratings['Shane'].values())
list2 =  list(ratings['Joe'].values())

sim = cosine_similarity(list1,list2)
print(sim)

output

o/p : 0.9205746178983233

Updated When i use :

ratings={'Shane': {'127 Hours': 5.0, 'Avatar': 4.0, 'Nonstop': 5.0},
         'Joe': {'127 Hours': 5.0, 'Taken 3': 4.0, 'Avatar': 5.0, 'Nonstop': 3.0}}

output :0.9574271077563381

Update2: Normalized length and considered keys

from math import*


ratings={'Shane': {'127 Hours': 5.0, 'Avatar': 4.0, 'Nonstop': 5.0},
         'Joe': {'127 Hours': 5.0, 'Taken 3': 4.0, 'Avatar': 5.0, 'Nonstop': 3.0},
         'Bob': {'Panic Room':5.0,'Nonstop':5.0}}


def square_rooted(x):

    return round(sqrt(sum([a*a for a in x])),3)

def cosine_similarity(x,y):

    input1 = {}
    input2 = {}
    vector2 = []
    vector1 =[]

    if len(x) > len(y):
        input1 = x
        input2 = y
    else:
        input1 = y
        input2 = x


    vector1 = list(input1.values())

    for k in input1.keys():    # Normalizing input vectors. 
        if k in input2:
            vector2.append(float(input2[k])) #picking the values for the common keys from input 2
        else :
            vector2.append(float(0))


    numerator = sum(a*b for a,b in zip(vector2,vector1))
    denominator = square_rooted(vector1)*square_rooted(vector2)
    return round(numerator/float(denominator),3)


print("Similarity between Shane and Joe")
print (cosine_similarity(ratings['Shane'],ratings['Joe']))

print("Similarity between Joe and Bob")
print (cosine_similarity(ratings['Joe'],ratings['Bob']))

print("Similarity between Shane and Bob")
print (cosine_similarity(ratings['Shane'],ratings['Bob']))

output:

Similarity between Shane and Joe
0.887
Similarity between Joe and Bob
0.346
Similarity between Shane and Bob
0.615

Nice explanation between jaccurd and cosine : https://datascience.stackexchange.com/questions/5121/applications-and-differences-for-jaccard-similarity-and-cosine-similarity

i am using Python 3.4

NOTE: I have assigned 0 to missing values. But you can assign some proper values too. Refer : http://www.analyticsvidhya.com/blog/2015/02/7-steps-data-exploration-preparation-building-model-part-2/

28
  • You're not looking at values are you? Just keys. Or did I miss something?
    – JL Peyret
    Commented Mar 14, 2016 at 6:51
  • @JLPeyret, Ah, Cool Change it to values. Simple ?
    – backtrack
    Commented Mar 14, 2016 at 6:53
  • "can't multiply sequence by non-int of type 'str'" is what I keep getting on the "sum11 += x*x" line. Commented Mar 14, 2016 at 6:54
  • When changing the dictionary to this: ratings={'Shane': {'127 Hours': 5.0, 'Avatar': 4.0, 'Nonstop': 5.0}, 'Joe': {'127 Hours': 5.0, 'Taken 3': 4.0, 'Avatar': 5.0, 'Nonstop': 3.0}}, it says that they are exactly alike with the output being "1.0" when they're not. I simply changed the 127 Hours key from 3.0 to 5.0 Commented Mar 14, 2016 at 7:02
  • 1
    @TrivisionZero But that doesn't make sense. If I rate a film 5 and you rate a different film 5, there should be no similarity (unless you're comparing how enthusiastic we are). Commented Mar 14, 2016 at 8:17
4

https://en.m.wikipedia.org/wiki/Jaccard_index

and now some cleaned-up sample code.

def jac(s1,s2):
    """the jaccard index between 2 sets"""
    s_union = s1.union(s2)
    s_inter = s1.intersection(s2)

    len_union = len(s_union)
    if not len_union:
        return 0

    return len(s_inter)*1.0/len_union

from itertools import permutations

ratings={'Shane': {'127 Hours': 5.0, 'Avatar': 4.0, 'Nonstop': 5.0},
     'Joe': {'127 Hours': 5.0, 'Taken 3': 4.0, 'Avatar': 5.0, 'Nonstop': 3.0},
     'Bob': {'Panic Room':5.0,'Nonstop':5.0}}

def common_movie(dict0, dict1):
    """have we rated the same movies?"""
    set0 = set(dict0.items())
    set1 = set(dict1.items())
    return jac(set0, set1)

def movies_and_ratings(dict0, dict1):
    """how do our movies and ratings line up?"""

    set_keys0 = set(dict0.keys())
    set_keys1 = set(dict1.keys())

    key_commonality = jac(set_keys0, set_keys1)

    set0 = set(dict0.items())
    set1 = set(dict1.items())

    item_commonality = jac(set0, set1)

    #ok, so now we give a proximity on key match, even if key + data dont match
    return 0.3 * key_commonality + 0.7 * item_commonality

def common_movie_ratings(dict0, dict1):
    """how do our ratings correspond on the same movies?"""

    set_keys0 = set(dict0.keys())
    set_keys1 = set(dict1.keys())

    set_common = set_keys0.intersection(set_keys1)

    set0 = set([v for k, v in dict0.items() if k in set_common])
    set1 = set([v for k, v in dict1.items() if k in set_common])

    return jac(set0, set1)

for pair in permutations(ratings.keys(), 2):

    dict0, dict1 = ratings[pair[0]], ratings[pair[1]]
    print "\n %s vs %s" % (pair)

    #make no assumption on key/value
    #order coming out of a dictionary.  So, you need to order them. 
    li = dict0.items()
    li.sort()
    print "  %s" % (li)
    li = dict1.items()
    li.sort()
    print "  %s" % (li)

    print "     common_movie    :%s" % common_movie(dict0, dict1)
    print "     movies_and_ratings:%s" % movies_and_ratings(dict0, dict1)
    print "     common_movie_ratings  :%s" % common_movie_ratings(dict0, dict1)

The output:

 Shane vs Bob
  [('127 Hours', 5.0), ('Avatar', 4.0), ('Nonstop', 5.0)]
  [('Nonstop', 5.0), ('Panic Room', 5.0)]
     common_movie    :0.25
     movies_and_ratings:0.25
     common_movie_ratings  :1.0

 Shane vs Joe
  [('127 Hours', 5.0), ('Avatar', 4.0), ('Nonstop', 5.0)]
  [('127 Hours', 5.0), ('Avatar', 5.0), ('Nonstop', 3.0), ('Taken 3', 4.0)]
     common_movie    :0.166666666667
     movies_and_ratings:0.341666666667
     common_movie_ratings  :0.333333333333

 Bob vs Shane
  [('Nonstop', 5.0), ('Panic Room', 5.0)]
  [('127 Hours', 5.0), ('Avatar', 4.0), ('Nonstop', 5.0)]
     common_movie    :0.25
     movies_and_ratings:0.25
     common_movie_ratings  :1.0

 Bob vs Joe
  [('Nonstop', 5.0), ('Panic Room', 5.0)]
  [('127 Hours', 5.0), ('Avatar', 5.0), ('Nonstop', 3.0), ('Taken 3', 4.0)]
     common_movie    :0.0
     movies_and_ratings:0.06
     common_movie_ratings  :0.0

 Joe vs Shane
  [('127 Hours', 5.0), ('Avatar', 5.0), ('Nonstop', 3.0), ('Taken 3', 4.0)]
  [('127 Hours', 5.0), ('Avatar', 4.0), ('Nonstop', 5.0)]
     common_movie    :0.166666666667
     movies_and_ratings:0.341666666667
     common_movie_ratings  :0.333333333333

 Joe vs Bob
  [('127 Hours', 5.0), ('Avatar', 5.0), ('Nonstop', 3.0), ('Taken 3', 4.0)]
  [('Nonstop', 5.0), ('Panic Room', 5.0)]
     common_movie    :0.0
     movies_and_ratings:0.06
     common_movie_ratings  :0.0
15
  • This did not seem to work in my situation... "AttributeError: 'set' object has no attribute 'intersect'" Commented Mar 14, 2016 at 6:45
  • Not on a comp so you may need to check syntax. I did correct intersect. But I've used Jaccard before and they are pretty good at 0..1 ratings.
    – JL Peyret
    Commented Mar 14, 2016 at 6:47
  • Now it's giving a 'unsupported operand type(s) for /: 'set' and 'set'' error on the division part. Commented Mar 14, 2016 at 6:49
  • Arggg. Sorry about that. You need to look at the sizes. I added len to both. My bad.
    – JL Peyret
    Commented Mar 14, 2016 at 6:54
  • @JLPeyret integer division... need to qualify Python version Commented Mar 14, 2016 at 6:55
1

This is my implementation of the Jaccard Similarity datascience stackexchange post mentioned above.

Suppose, you have a Counter output from the collection library that counts the number of times a certain key is present in an iterable as such:

d1 = {'a': 2, 'b': 1}
d2 = {'a': 1, 'c': 1}

def get_jaccard_similarity(d1,d2):

    if not isinstance(d1, dict) or not isinstance(d2, dict):
        raise TypeError(f'd1 and d2 should be of type dict'
                    f' and not {type(d1).__name__}, {type(d2).__name__}')
    if not d1 and not d2:
        return 1
    elif (d1 and not d2) or (d2 and not d1):
        return 0
    else:
        set_of_all_keys = {*d1.keys(), *d2.keys()}
        nb_of_common_elements_dict = {k:min(d1.get(k,0),d2.get(k, 0))
                                  for k in set_of_all_keys }
        nb_of_total_elements_dict = {k: max(d1.get(k, 0), d2.get(k, 0))
                                  for k in set_of_all_keys}

        return sum(nb_of_common_elements_dict.values())/sum(nb_of_total_elements_dict.values())

Output: 0.75

The datascience stackexchange post derives a Jaccard similarity based the notion of sets. I believe this implementation will give the same result as with sets (dictionnary with values equal to 1), except that it gives the advantage to weight for the number of times a key appear in both (counter) dictionaries

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.