资讯专栏INFORMATION COLUMN

基于 Postgres 实现一个推荐系统

3fuyu / 1877人阅读

摘要:机器学习派是后起之秀,而相似度派则是泰山北斗,以致撑起来推荐系统的半壁江山。纯来做推荐基本不靠谱,所以我们来试一下基于和相似度来实现一个推荐系统。

对于内容类网站或者APP,搜索和推荐已经是标配。搜索相对容易,使用Elasticsearch简单配置一下就可以做出一个性能还不错效果也还可以的搜索引擎,然而,推荐系统的话,没有专门的团队实践起来还挺困难的。

网上推荐系统相关的理论非常多,但可用的实践却少见,要么是介绍相似度算法的demo,要么是讲高大上架构的文章,看懂这些离真正实现一个推荐系统还差着十万八千里。本文的重点不是介绍原理,也不是探讨算法优劣,侧重点在于如何基于Postgres快速落地一个性能还不错的推荐系统。

准备工作

通过movielens.sql创建一个movielens数据库

    createdb movielens
    curl https://raw.githubusercontent.com/ankane/movielens.sql/master/movielens.sql | psql -d movielens

主要包含以下关系表,其中ratings表大概10w左右的数据:

    d ratings
                   Table "public.ratings"
      Column  |            Type             | Modifiers
    ----------+-----------------------------+-----------
     id       | integer                     | not null
     user_id  | integer                     |
     movie_id | integer                     |
     rating   | integer                     |
     rated_at | timestamp without time zone |
    d movies
                          Table "public.movies"
        Column     |          Type          |        Modifiers
    ---------------+------------------------+-------------------------
     id            | integer                | not null
     title         | character varying(255) |
     release_date  | date                   |
    d users;
                    Table "public.users"
        Column     |          Type          | Modifiers
    ---------------+------------------------+-----------
     id            | integer                | not null
     age           | integer                |
     gender        | character(1)           |
     occupation_id | integer                |
     zip_code      | character varying(255) |

另外还需要一个Rails项目:https://github.com/hooopo/movielens-rails-app

相似度算法

“推荐系统中,推荐算法分为两个门派,一个是机器学习派,另一个就是相似度门派。机器学习派是后起之秀,而相似度派则是泰山北斗,以致撑起来推荐系统的半壁江山。”

相似度的算法非常多,下面来介绍一下常用的相似度算法以及Ruby代码实现。

Jaccard Similarity

Jaccard相似度,是两个集合的交集元素个数在并集中所占的比例。由于集合非常适用于布尔向量表示,所以Jaccard相似度简直就是为布尔值向量私人定做的,即Jaccard相似度非常适合做隐式反馈数据,比如收藏行为、加购物车行为、点击行为等。

      def jaccard_sim(other_movie)
        # 假设评分大于等于3的为喜欢
        other_user_ids = other_movie.ratings.where("rating >= 3").pluck(:user_id)
        user_ids       = self.ratings.where("rating >= 3").pluck(:user_id)
        
        # 交集数量
        intersection = (other_user_ids & user_ids).count
    
        # 并集数量
        union        = (other_user_ids | user_ids).count
    
        return 0 if union.zero?
        intersection.to_f / union.to_f
      end
Cosine Similarity

余弦相似度在度量文本相似度、用户相似度、物品相似度的时候都较为常用,它与向量的长度无关。

      def cosine_sim(other_movie)
        other_user_ratings = other_movie.ratings.map { |r| [r.user_id, r.rating] }.to_h
        user_ratings       = self.ratings.map { |r| [r.user_id, r.rating] }.to_h
    
        # 有共同评价的用户
        union_user_ids = other_user_ratings.keys & user_ratings.keys
        return 0 if union_user_ids.count == 0
    
        u = other_user_ratings.values_at(*union_user_ids)
        v = user_ratings.values_at(*union_user_ids)
    
        dot_product = u.zip(v).map { |a, b| a*b }.sum
    
        magnitude_u = Math.sqrt(u.map { |x| x*x }.sum)
        magnitude_v = Math.sqrt(v.map { |x| x*x }.sum)
    
        cosine_similarity = dot_product.to_f / (magnitude_v * magnitude_u)
      end
Pearson Correlation

皮尔逊相关度,实际上也是一种余弦相似度,不过先对向量做了中心化,向量 p 和 q 各自减去向量的均值后,再计算余弦相似度。皮尔逊相关度和修正后的余弦相似度很像,但其实是有差别的,主要区别是均值的定义不同。

      def pearson_sim(other_movie)
        other_user_ratings = other_movie.ratings.map { |r| [r.user_id, r.rating] }.to_h
        user_ratings       = self.ratings.map { |r| [r.user_id, r.rating] }.to_h
        
        # 有共同评价的用户
        union_user_ids = other_user_ratings.keys & user_ratings.keys
        n = union_user_ids.count
        return 0 if n == 0
    
        u = other_user_ratings.values_at(*union_user_ids)
        v = user_ratings.values_at(*union_user_ids)
    
        sum_u = u.sum
        sum_v = v.sum 
    
        sum_u_sq = u.map { |x| x*x }.sum 
        sum_v_sq = v.map { |x| x*x }.sum
    
        prod_sum = u.zip(v).map { |x, y| x*y }.sum
        num = prod_sum - ((sum_u * sum_v) / n.to_f)
        den = Math.sqrt((sum_u_sq - (sum_u * sum_u) / n.to_f) * (sum_v_sq - (sum_v * sum_v) / n.to_f))
        return 0 if den == 0
        [num / den, 1].min
      end

最后,做下演示:

    movie = Movie.first
    movie.recommendation_movies(limit: 10, using: :jaccard_sim)
基于Postgres的推荐系统

上面代码的目的是为了学习三种算法的实现,所以没有复用,也没有性能方面的优化。纯Ruby来做推荐基本不靠谱,所以我们来试一下基于Posgres和Jaccard相似度来实现一个推荐系统。

首先上面Ruby代码里假设rating大于3就是喜欢,这并不十分准确,有些人评分可能非常严格,他只打1-3分,那么对于他来说,其实3分就算喜欢了。

为了应对这种情况,我们用用户均值来推断他是否喜欢一部电影。另外我们要便于以后计算方便,把计算结果先缓存到movies的like_user_ids字段上。

      # 增加缓存字段like_user_ids,存储喜欢这部电影的用户ID
      def change
        add_column :movies, :like_user_ids, :integer, :array => true, :default => "{}"
      end
    
      # 使用PG内置扩展intarray:https://www.postgresql.org/docs/current/static/intarray.html
      # 对intarray的求交集操作可以利用gin or gist索引
      def change
        enable_extension :intarray
      end
    
      def change
        execute <<-SQL
          CREATE INDEX like_user_ids_idx_2 ON movies USING gin(like_user_ids gin__int_ops);
        SQL
      end

第一次,批量初始化like_user_ids字段,单条记录更新可以实时计算出来填充进去。

    WITH avg_rating_per_user AS ( 
      SELECT movie_id, 
             user_id, 
             rating,
             AVG(rating) OVER (PARTITION BY user_id) AS avg_rating 
        FROM ratings
    ),
    rating_per_movie AS (
      SELECT movie_id, 
             array_agg(user_id) AS like_user_ids
        FROM avg_rating_per_user
       WHERE rating > avg_rating 
    GROUP BY movie_id
    )
    
    UPDATE movies AS m 
       SET like_user_ids = r.like_user_ids
      FROM rating_per_movie AS r
     WHERE r.movie_id = m.id;
实时查询方案
      def recommend_by_sql(limit: 10)
        Movie.find_by_sql(<<~SQL)
            SELECT array_length(m.like_user_ids & movies.like_user_ids, 1) / array_length(m.like_user_ids | movies.like_user_ids, 1)::float AS score,
                   m.* 
              FROM movies 
                   INNER JOIN movies AS m ON m.id != #{self.id} 
             WHERE movies.id = #{self.id}  
          ORDER BY 1 DESC 
             LIMIT #{limit}
        SQL
      end

由于排序字段是一个动态计算值,所以这个语句无法利用索引,效率由movies表大小决定,但其实比Ruby版的已经快很多了。

预计算相似度方案

基于相似度的推荐算法的目标就是产生一个Item-Item或User-User的相似度矩阵。用关系型数据库的表示方法为:

    d item_item_matrix
          Table "public.item_item_matrix"
      Column   |       Type       |  Modifiers
    -----------+------------------+-------------
     u_id      | integer          |
     v_id      | integer          |
     sim_score | double precision | default 0.0
    Indexes:
        "index_item_item_matrix_on_u_id_and_v_id" UNIQUE, btree (u_id, v_id)
        "index_item_item_matrix_on_u_id_and_sim_score_and_v_id" btree (u_id, sim_score, v_id)

假设movies表的数量是N,这个矩阵的条目数最大情况是 N*N,但实际并不需要全部Item之间的相似度都计算一遍:

相同ID的Item相似度一定是1,不需要计算和存储

相似度为0的并不需要存储

通过设置一个阈值score,过滤掉相似度很小的,比如score 小于0.2的就丢弃

通过设置一个阈值limit,过滤掉相关度排在后面的部分,比如一个Item最多存储相关度最高的10个Item

经过上面的步骤,相关度矩阵的存储可以优化到10*N左右,即10w个电影的话,相似度矩阵里只需要存储100w条记录。

    def recommend_by_matrix(limit: 10)
        Movie.find_by_sql(<<~SQL)
          SELECT m.*, matrix.sim_score
            FROM item_item_matrix AS matrix
                 INNER JOIN movies AS m ON m.id = matrix.v_id
           WHERE matrix.u_id = #{self.id}
        ORDER BY matrix.sim_score DESC
           LIMIT #{limit}
        SQL
      end

如果sim_score已经预先计算好,这个查询直接可以index only,记录条数再多也是非常快的。不管是TopN推荐还是评分预测,只要相似度矩阵计算好了,之后的事情易如反掌。

下面就来预计算相似度。

    WITH matrix AS (
      SELECT u.id AS u_id, 
             v.id as v_id, 
             array_length(v.like_user_ids & u.like_user_ids, 1) / array_length(u.like_user_ids | v.like_user_ids, 1)::float AS sim_score 
        FROM movies AS u, 
             movies AS v 
       WHERE u.id > v.id AND v.like_user_ids && u.like_user_ids
    ), matrix_trim AS (
      SELECT u_id, v_id, sim_score FROM (
        SELECT u_id,
               v_id,
               sim_score,
               row_number() OVER (partition by u_id ORDER BY sim_score desc) AS row_num
          FROM matrix 
         WHERE sim_score > 0.01    /* 过滤掉相似度太小的值 */
      ) AS tmp WHERE row_num <= 10 /* 取最相近的10条记录 */
    )
    
    INSERT INTO item_item_matrix 
    (
      SELECT u_id, v_id, sim_score FROM matrix_trim 
      UNION 
      /* u_id, v_id只需要计算一次,但存储两份,为了查询方便高效 */
      SELECT v_id AS u_id, u_id AS v_id, sim_score FROM matrix_trim
    ) 
    ON CONFLICT (u_id, v_id) DO UPDATE SET sim_score = excluded.sim_score;
增量更新和离线处理

上面已经把相似度矩阵初始化完毕,对于新增数据,我们只需要把发生变化的数据重新计算一遍插入到item item matrix表里,这个代价非常小,可以bulk,也可以离线。对于数量大的系统,初始化步骤也是可以分步批量插入的。由于基于Postgres,对于超大量数据的情况,也可以平滑迁移到greemplum和citus或redshift这种可以并行查询计算的存储。

另外,也有一些基于postgres的推荐扩展,不过版本都不是很新:

https://github.com/DataSystem...

http://sigaev.ru/git/gitweb.c...;a=summary

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/17820.html

相关文章

  • 基于 Postgres 实现一个推荐系统

    摘要:机器学习派是后起之秀,而相似度派则是泰山北斗,以致撑起来推荐系统的半壁江山。纯来做推荐基本不靠谱,所以我们来试一下基于和相似度来实现一个推荐系统。 对于内容类网站或者APP,搜索和推荐已经是标配。搜索相对容易,使用Elasticsearch简单配置一下就可以做出一个性能还不错效果也还可以的搜索引擎,然而,推荐系统的话,没有专门的团队实践起来还挺困难的。 网上推荐系统相关的理论非常多,但...

    wean 评论0 收藏0
  • 基于 Postgres 实现一个推荐系统

    摘要:机器学习派是后起之秀,而相似度派则是泰山北斗,以致撑起来推荐系统的半壁江山。纯来做推荐基本不靠谱,所以我们来试一下基于和相似度来实现一个推荐系统。 对于内容类网站或者APP,搜索和推荐已经是标配。搜索相对容易,使用Elasticsearch简单配置一下就可以做出一个性能还不错效果也还可以的搜索引擎,然而,推荐系统的话,没有专门的团队实践起来还挺困难的。 网上推荐系统相关的理论非常多,但...

    aristark 评论0 收藏0
  • 从零搭建精准运营系统

    摘要:而如何利用用户的数据来做运营消息推送触达消息优惠券发送广告位等,正是精准运营系统需要解决的问题。是一个流式系统,具有高吞吐低延迟的特点,是一套极具通用性易于使用的实时流式事件处理方案。 2018刚过去,趁着春节放假对过去一年主导开发的项目做个梳理和总结 项目背景 平台运营到一定阶段,一定会累积大批量的用户数据,这些用户数据是运营人员的黄金财产。而如何利用用户的数据来做运营(消息推送、触...

    yintaolaowanzi 评论0 收藏0
  • 从零搭建精准运营系统

    摘要:而如何利用用户的数据来做运营消息推送触达消息优惠券发送广告位等,正是精准运营系统需要解决的问题。是一个流式系统,具有高吞吐低延迟的特点,是一套极具通用性易于使用的实时流式事件处理方案。 2018刚过去,趁着春节放假对过去一年主导开发的项目做个梳理和总结 项目背景 平台运营到一定阶段,一定会累积大批量的用户数据,这些用户数据是运营人员的黄金财产。而如何利用用户的数据来做运营(消息推送、触...

    imtianx 评论0 收藏0
  • 从零搭建精准运营系统

    摘要:而如何利用用户的数据来做运营消息推送触达消息优惠券发送广告位等,正是精准运营系统需要解决的问题。是一个流式系统,具有高吞吐低延迟的特点,是一套极具通用性易于使用的实时流式事件处理方案。 2018刚过去,趁着春节放假对过去一年主导开发的项目做个梳理和总结 项目背景 平台运营到一定阶段,一定会累积大批量的用户数据,这些用户数据是运营人员的黄金财产。而如何利用用户的数据来做运营(消息推送、触...

    J4ck_Chan 评论0 收藏0

发表评论

0条评论

3fuyu

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<