6
\$\begingroup\$

I wrote the following code using Ruby to compute item-based collaborative filtering (using Jaccard coefficient of similarity).

I would appreciate feedback about any potential issues with the code and tips to make the code better comply with the best practices.

require 'json'
require 'set'

def compute_jaccard_coefficients(users_for_activities)
    jaccard_coefficient_hash = {}
    all_activities = Set.new
    users_for_activities.each do |key1, array1|
        users_for_activities.each do |key2, array2|
            if key1 != key2
                all_activities.add key1
                all_activities.add key2
                intersected_users = array1 & array2
                unioned_users = array1 | array2
                if unioned_users.length > 0
                    jaccard_coefficient_hash[[key1, key2]] = intersected_users.length.fdiv(unioned_users.length)
                    else
                    jaccard_coefficient_hash[[key1, key2]] = 0
                end
            end
        end
    end
    return [jaccard_coefficient_hash, all_activities]
end

data = '[
{"user": "1", "activities": ["running", "swimming", "rowing"]},
{"user": "2", "activities": ["tennis", "rowing"]},
{"user": "3", "activities": ["swimming", "running"]},
{"user": "4", "activities": ["tennis", "swimming"]}
]'

parsed_data = JSON.parse(data)

users_for_activities = Hash.new{|h,k| h[k] = []}

parsed_data.each do |child|
    child["activities"].each do |activity|
        users_for_activities[activity] << child["user"]
    end
end

all_activities = Set.new
jaccard_coefficient_hash, all_activities = compute_jaccard_coefficients(users_for_activities)

parsed_data.each do |child|
    activities_to_recommend = {}
    child["activities"].each do |user_activity|
        all_activities.each do |generic_activity|
            if user_activity != generic_activity
                if activities_to_recommend.has_key?(generic_activity)
                    if jaccard_coefficient_hash[[user_activity, generic_activity]] > activities_to_recommend[generic_activity]
                        unless child["activities"].include?(generic_activity)
                            activities_to_recommend[generic_activity] = jaccard_coefficient_hash[[user_activity, generic_activity]]
                        end
                    end
                    else
                    unless child["activities"].include?(generic_activity)
                        activities_to_recommend[generic_activity] = jaccard_coefficient_hash[[user_activity, generic_activity]]
                    end
                end
            end
        end
    end
    print "User " + child["user"] + ": "
    print activities_to_recommend.sort_by {|k,v| v}.reverse
    print "\n"
end

Output:

User 1: [["tennis", 0.3333333333333333]]
User 2: [["running", 0.3333333333333333], ["swimming", 0.25]]
User 3: [["rowing", 0.3333333333333333], ["tennis", 0.25]]
User 4: [["running", 0.6666666666666666], ["rowing", 0.3333333333333333]]
\$\endgroup\$
4
  • \$\begingroup\$ Please provide the actual hash passed to the method. The data in your question is a) a JSON string, and b) indexed by user. Unless I'm mistaken, the method operates on the inverse: Users indexed by activity. Sure, we can write our own input, but it shouldn't really be our responsibility. We also won't know if we got it right if we just feed it stuff we make up. \$\endgroup\$
    – Flambino
    Jun 24, 2014 at 1:48
  • \$\begingroup\$ @Flambino thanks for the suggestions. The json object is a toy example of the kind of input we receive to compute our recommendations. Perhaps I can move the data transformation part into the wrapper code (not shown in this self-contained example) so that this code focuses on the actual technique. \$\endgroup\$
    – Sharon
    Jun 24, 2014 at 2:23
  • \$\begingroup\$ Actually, never mind. I goofed. I realize now that there was more to the code in the question. For whatever reason, my tablet's browser didn't let me scroll the code :P \$\endgroup\$
    – Flambino
    Jun 24, 2014 at 16:03
  • \$\begingroup\$ @Flambino that's alright :). The code in its entirety would hopefully make more sense. \$\endgroup\$
    – Sharon
    Jun 24, 2014 at 20:54

2 Answers 2

2
\$\begingroup\$
  1. It appears, that these lines of code are junk you forgot to remove:

    unless child["activities"].include?(generic_activity)  
    
  2. Instead of accumulating set, just use users_for_activities.keys.

  3. Replace:

    child["activities"].each do |user_activity|
        all_activities.each do |generic_activity|
            if user_activity != generic_activity
    

    with:

    child["activities"].product(all_activities - child["activities"]) do |user_activity, generic_activity|
    

    that saves you two levels of indentation.

  4. The same trick here to replace:

    users_for_activities.each do |key1, array1|
        users_for_activities.each do |key2, array2|
            if key1 != key2
    

    with:

    users_for_activities.to_a.permutation(2) do |(key1, array1), (key2, array2)|
    
  5. You may use .empty? instead of .length > 0 or this:

    if 0 == total_users = array1.length + array2.length
        jaccard_coefficient_hash[[key1, key2]] = 0
    else
        jaccard_coefficient_hash[[key1, key2]] = intersected_users.length.fdiv(total_users)
    end
    
  6. Since recommendations can't be negative, you may get rid of another if because of its awful code length by defaulting the result to zero in this way:

    activities_to_recommend[generic_activity] = [
        activities_to_recommend[generic_activity] || 0,
        jaccard_coefficient_hash[[user_activity, generic_activity]]
    ].max
    

    or this:

    activities_to_recommend = Hash.new 0
    
  7. By changing loops nesting order we can start using Array#max and do a step to get rid of imperativity here, since we stop walk randomly through activities_to_recommend:

    parsed_data.each do |child|
        activities_to_recommend = Hash.new 0
        (users_for_activities.keys - child["activities"]).each do |generic_activity|
            activities_to_recommend[generic_activity] =
                child["activities"].map{ |user_activity|
                    jaccard_coefficient_hash[[user_activity, generic_activity]]
                }.max || 0
        end
        puts "User #{child["user"]}: #{activities_to_recommend.sort_by{ |k,v| -v }}"
    end
    
  8. (optional) But that getting rid of imperativity isn't too nice -- most people won't like this:

    activities_to_recommend = (users_for_activities.keys - child["activities"]).map do |generic_activity| [
        generic_activity,
        child["activities"].map{ |user_activity|
            jaccard_coefficient_hash[[user_activity, generic_activity]]
        }.max || 0
    ] end
    
  9. (optional) If you try to rewrite users_for_activities creation into functional and method-chaining way, you'll get this controversial thing:

    users_for_activities = parsed_data.flat_map{ |child|
        child["activities"].map{ |activity| [activity, child["user"]] }
    }.group_by(&:first).tap{ |h| h.each{ |k,v| v.map! &:last } }
    
  10. (optional) Hash with array as a key, rather than simple scalar, like an Integer, can have sudden collisions, but since your array items are Strings, you probably can forget about that.

\$\endgroup\$
1
  • \$\begingroup\$ thanks for the detailed review and explanation about alternate techniques. \$\endgroup\$
    – Sharon
    Jun 26, 2014 at 21:34
2
\$\begingroup\$

Stuff I noticed:

  • Use next to skip an each-iteration instead of wrapping everything in an if statement

  • No need for Set. A hash's keys are already a set, so in your compute_jaccard_coefficients method you could just call all_activties = users_for_activities.keys and done. From the raw data, you could do all_activities = parsed_data.map { |user| user['activities'] }.flatten.uniq

  • I'd absolutely avoid returning a tuple from the compute_jaccard_coefficients method. As illustrated above, getting all the activities isn't difficult; you can do that anywhere. And the method itself doesn't use the set for anything; creating the set is just something it also does, even though it shouldn't be its responsibility. Your code definitely shouldn't rely on a method just randomly doing something

  • Since your method is checking combinations of activities, you might as well use Array#combination. Give it an argument of 2 and it'll give you an array of pairs activities. Note that it'll also give only unique combinations - i.e. you'll get a pair like ["tennis", "swimming"], but it'll skip ["swimming", "tennis"] since that's the same combination.

  • Favor methods like any? (or better - as Naklion points out in the comments - empty?) over checking an array's length with arr.count > 0

With the above in mind, the method can be written as

def compute_jaccard_coefficients(hash)
  coefficients = hash.keys.combination(2).map do |a, b|
    union = hash[a] | hash[b]
    weight = union.empty? ? 0 : (hash[a] & hash[b]).count / union.count.to_f
    [[a, b], weight]
  end
  Hash[coefficients]
end

Note that this implementation also gives you a cleaner result (no duplicate combinations) in fewer iterations.

I'm out of time right now, but I'll take a look at the rest of the code later.


Update: It's now "later", and Naklion has provided a very nice answer. Still, I'll give it a go too.

I used combination above, whereas Naklion used permutation. The latter gives an identical result to the original code (i.e. the coefficients hash will have keys for both tennis/rowing and rowing/tennis). Using combination you'll only get unique combinations, and thus fewer coefficient calculations, but lookup gets a bit more complex (which I wasn't considering when just looking at the Jaccard method). Still, since Naklion used permutations, I'll stick to combinations.

One addition, though, is to use Set (after all) to create the keys of the Jaccard hash:

def compute_jaccard_coefficients(hash)
  coefficients = hash.keys.combination(2).map do |a, b|
    union = hash[a] | hash[b]
    weight = union.empty? ? 0 : (hash[a] & hash[b]).count / union.count.to_f
    [Set[a, b], weight]
  end
  Hash[coefficients]
end

This allows us to look up weights without worrying bout the order of the key's elements, since Set[a, b] == Set[b, a].

Naklion provided a nice way (#9 on the list) to transpose the parsed_data from user-indexed activities to activity-indexed users, so I'll skip over that.

So starting with this (and the method above)

all_activities = users_for_activities.keys
coefficients = compute_jaccard_coefficients(users_for_activities)

you can do this

parsed_data.each do |user|
  possibles = all_activities - user['activities'] # activities the user doesn't have already
  recommendations = user['activities'].product(possibles).map do |a, b|
    # a is the user's existing activity, b is the recommended activity
    key = Set[a, b]
    [b, coefficients[key]] if coefficients[key] > 0
  end.compact.sort_by(&:last).reverse

  puts "User #{user[:user]}: #{recommendations}"
end
\$\endgroup\$
5
  • 1
    \$\begingroup\$ +1 the [[a,b],0] ; end ; Hash[...] style. -1 any? is bad way to check length. \$\endgroup\$
    – Nakilon
    Jun 25, 2014 at 12:12
  • \$\begingroup\$ @Nakilon What's the problem with any?? It reads well, and (as far as I know) is functionally equivalent to just checking that the length is greater than zero \$\endgroup\$
    – Flambino
    Jun 25, 2014 at 12:18
  • \$\begingroup\$ [].any? == [nil].any? == [false].any? == false. The proper method is .empty? \$\endgroup\$
    – Nakilon
    Jun 25, 2014 at 12:51
  • \$\begingroup\$ @Nakilon Ah, right. Wasn't thinking of nil/false values (since all we have here should be strings). Thanks \$\endgroup\$
    – Flambino
    Jun 25, 2014 at 12:55
  • \$\begingroup\$ @flambino thanks for the detailed review and comparing the approaches of the two answers. \$\endgroup\$
    – Sharon
    Jun 26, 2014 at 21:35

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.