Skip to content

Instantly share code, notes, and snippets.

@herval
Created February 20, 2013 03:14
Show Gist options
  • Save herval/4992503 to your computer and use it in GitHub Desktop.
Save herval/4992503 to your computer and use it in GitHub Desktop.
class Entity < Struct.new(:name, :ratings)
end
@gamers = [
Entity.new('Lisa', {
'Prince of Persia' => 2.5,
'Doom' => 3.5,
'Castle Wolfenstein' => 3.0,
'Rise of the Triad' => 3.5,
'Commander Keen' => 2.5,
'Duke Nukem' => 3.0
}),
Entity.new('Larry', {
'Prince of Persia' => 3.0,
'Doom' => 3.5,
'Castle Wolfenstein' => 1.5,
'Rise of the Triad' => 5.0,
'Duke Nukem' => 3.0,
'Commander Keen' => 3.5
}),
Entity.new('Robert', {
'Prince of Persia' => 2.5,
'Doom' => 3.0,
'Rise of the Triad' => 3.5,
'Duke Nukem' => 4.0
}),
Entity.new('Claudia', {
'Doom' => 3.5,
'Castle Wolfenstein' => 3.0,
'Duke Nukem' => 4.5,
'Rise of the Triad' => 4.0,
'Commander Keen' => 2.5
}),
Entity.new('Mark', {
'Prince of Persia' => 3.0,
'Doom' => 4.0,
'Castle Wolfenstein' => 2.0,
'Rise of the Triad' => 3.0,
'Duke Nukem' => 3.0,
'Commander Keen' => 2.0
}),
Entity.new('Jane', {
'Prince of Persia' => 3.0,
'Doom' => 4.0,
'Duke Nukem' => 3.0,
'Rise of the Triad' => 5.0,
'Commander Keen' => 3.5
}),
Entity.new('John', {
'Doom' => 4.5,
'Commander Keen' => 1.0,
'Rise of the Triad' => 4.0
})
]
# Returns the euclidian distance between person1 and person2
def distance(person1, person2)
rated_by_both = person1.ratings.select { |game| person2.ratings[game] }
return 0.0 if rated_by_both.empty? # if they have no ratings in common, return 0
# add up the squares of all the differences
sum_of_squares = 0.0
person1.ratings.collect do |game, score|
person2_score = person2.ratings[game]
next if !person2_score
sum_of_squares += ((score - person2_score) ** 2)
end
1.0 / (1.0 + sum_of_squares)
end
# Returns the 5 best matching people (most similar preferences)
def top_matches(person, all_ratings)
other_people = all_ratings.select { |person2| person2.name != person.name }
other_people.collect do |other_person|
[
other_person,
distance(person, other_person) # change this to use other algorithms
]
end.sort_by { |sim| sim[1] }.reverse[0..5]
end
# Gets recommendations for a person by using a weighted average
# of every other user's ratings
def recommendations(person, other_people)
similarities = {}
other_people.each do |other_person|
similarity = distance(person, other_person)
# ignore scores of zero or lower
next if similarity <= 0
other_person.ratings.each do |other_person_game, other_person_score|
# only score what I haven't rated yet
next if person.ratings[other_person_game]
similarity_for_game = similarities[other_person_game] ||= { :weighted => 0, :sum => 0 }
# Weighted sum of rating times similarity
similarity_for_game[:weighted] += other_person.ratings[other_person_game] * similarity
# Sum of similarities
similarity_for_game[:sum] += similarity
end
end
# normalize list and sort by highest scores first
similarities.collect do |game_name, score|
[ game_name, (score[:weighted] / score[:sum]) ]
end.sort_by { |sim| sim[1] }.reverse
end
# this is very similar to the recommendations() algorithm,
# except we use a pre-calculated similar_games_matrix instead of
# calculating distances here
def recommended_games(similar_games_matrix, user)
similarities = {}
user.ratings.each do |game_name, user_rating|
# Loop over games similar to the current game
similar_games_matrix[game_name].each do |game, similarity|
# Ignore if this user has already rated this similar game
next if user.ratings[game.name]
score_for_game = similarities[game.name] ||= { :weighted => 0, :sum => 0 }
# Weighted sum of rating times similarity
score_for_game[:weighted] += similarity * user_rating
# Sum of all the similarities
score_for_game[:sum] += similarity
end
end
# Divide each total score by total weighting to get an average
# Return the rankings from highest to lowest
similarities.collect do |game_name, score|
[ game_name, (score[:weighted] / score[:sum]) ]
end.sort_by { |sim| sim[1] }.reverse
end
# invert the mapping
def transform_ratings(gamers)
results = {}
# user scored games becomes game was scored by users
gamers.each do |person|
person.ratings.each do |game, score|
results[game] ||= Entity.new(game, {})
results[game].ratings[person.name] = score
end
end
results.values
end
# Create a dictionary of games showing which other games they
# are most similar to. This should be run often and cached for reuse
def calculate_similar_games(game_ratings)
Hash[game_ratings.collect do |game|
[
game.name,
top_matches(game, game_ratings)
]
end]
end
def time
start = Time.now
yield
puts "- Elapsed time: #{((Time.now - start)*1000).to_s}s"
end
@me = @gamers.last
time do
@top = top_matches(@me, @gamers)
puts "\nPeople similar to #{@me.name}:"
@top.each { |person, similarity| puts "#{person.name} (#{(similarity*100).to_i}% match)" }
end
time do
@recommended = recommendations(@me, @gamers)
puts "\nRecommended games for #{@me.name} (method 1):"
@recommended.each { |game, similarity| puts game }
end
@game_ratings = transform_ratings(@gamers)
time do
@similar_games = calculate_similar_games(@game_ratings)
puts "\nSimilar games:"
@similar_games.each do |game, similar_games|
similars = similar_games.collect { |similar_game, score| "#{similar_game.name} (#{(score*100).to_i}%)" }
puts "#{game}: #{similars.join(', ')}"
end
end
time do
@recommended = recommended_games(@similar_games, @me)
puts "\nRecommended games for #{@me.name} (method 2):"
@recommended.each { |game, similarity| puts game }
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment