基于Jaccard系数的简单推荐算法

推荐系统的算法基于 Jaccard 系数,也被称为 Jaccard 相似度系数。Jaccard 系数是由植物学家 Paul Jaccard 提出的,是用来体现样本相似性和差异性的数值。

运作原理

取出当前的 item(比如博客文章)和能够很好地描述它的属性(标签、分类或单词)。然后对其它每个 item 计算出它们交集和并集的商。数学过程可以表述为以下公式。

该方程的计算结果在 0 到 1 之间。你也能够方便地用以下公式来计算项目间的差异性。

Ruby 的实现示例

下面我将使用书名中的单词来推荐书籍。使用简单的 Book 类即可。

  1. class Book < Struct.new(:title) 
  2.  
  3.     # 长度大于2的不重复的单词的数组 
  4.     # 也可以是「标签」或「分类」的数组 
  5.     def words 
  6.         @words ||= self.title.gsub(/[a-zA-Z]{3,}/).map(&:downcase).uniq.sort 
  7.     end 
  8. end 

BookRecommender 类使用当前的书籍和书籍数组进行初始化。recommendations 方法会循环数组并给每一个元素设定 jaccard_index 值,最后将书籍进行排序。

  1. class BookRecommender 
  2.  
  3.     def initialize book, books 
  4.         @book, @books = book, books 
  5.     end 
  6.  
  7.     def recommendations 
  8.  
  9.         # 计算每个元素的 jaccard_index 值并排序 
  10.         @books.map! do |this_book| 
  11.  
  12.         # 运行中定义 jaccard_index 的取值 singleton 方法 
  13.         this_book.define_singleton_method(:jaccard_index) do 
  14.             @jaccard_index 
  15.         end 
  16.  
  17.         # 还有赋值方法 
  18.         this_book.define_singleton_method("jaccard_index="do |index| 
  19.             @jaccard_index = index || 0.0 
  20.         end 
  21.  
  22.         # 计算样本的交集 
  23.         intersection = (@book.words & this_book.words).size 
  24.         # ... 和并集 
  25.         union = (@book.words | this_book.words).size 
  26.  
  27.         # 将除法运算的结果赋值,如无法计算则捕捉异常并赋值为0 
  28.         this_book.jaccard_index = (intersection.to_f / union.to_f) rescue 0.0 
  29.  
  30.         this_book 
  31.  
  32.         # 排序 
  33.         end.sort_by { |book| 1 - book.jaccard_index } 
  34.  
  35.     end 
  36. end 

演示推荐过程:

# ... # 读取数据并定义书籍数组 BOOKS = DATA.read.split("\n").map { |l| Book.new(l) }  # 定义当前书籍 current_book = Book.new("Ruby programming language")  # 进行推荐... books = BookRecommender.new(current_book, BOOKS).recommendations  books.each do |book|     puts "#{book.title} (#{'%.2f' % book.jaccard_index})" end  __END__ Finding the best language for the job Could Ruby save the day Python will rock your world Is Ruby better than Python Programming in Ruby is fun Python to the moon Programming languages of the future 

下面是名为「Ruby programming language」的书籍的输出结果,右边的数值就是 Jaccard 指数。

Programming in Ruby is fun (0.50) Programming languages of the future (0.17) Is Ruby better than Python (0.17) Could Ruby save the day (0.14) Finding the best language for the job (0.12) Python to the moon (0.00) Python will rock your world (0.00) 

总结

以上就是纯粹基于 Ruby 的解决方案,源代码在我的 gist 上。我还写了使用标签的 PostgresSQL 版本。但要注意的是,当样本变得很大以后代码的执行速度也会变慢,因此不要每次操作 item 时都运行推荐,更好的方法是定义后台服务在后台进行推荐的计算。

转载请注明:代码家园 » 基于Jaccard系数的简单推荐算法

评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)