摘要：機(jī)器學(xué)習(xí)派是后起之秀，而相似度派則是泰山北斗，以致?lián)纹饋?lái)推薦系統(tǒng)的半壁江山。純來(lái)做推薦基本不靠譜，所以我們來(lái)試一下基于和相似度來(lái)實(shí)現(xiàn)一個(gè)推薦系統(tǒng)。

對(duì)于內(nèi)容類網(wǎng)站或者APP，搜索和推薦已經(jīng)是標(biāo)配。搜索相對(duì)容易，使用Elasticsearch簡(jiǎn)單配置一下就可以做出一個(gè)性能還不錯(cuò)效果也還可以的搜索引擎，然而，推薦系統(tǒng)的話，沒(méi)有專門的團(tuán)隊(duì)實(shí)踐起來(lái)還挺困難的。

網(wǎng)上推薦系統(tǒng)相關(guān)的理論非常多，但可用的實(shí)踐卻少見(jiàn)，要么是介紹相似度算法的demo，要么是講高大上架構(gòu)的文章，看懂這些離真正實(shí)現(xiàn)一個(gè)推薦系統(tǒng)還差著十萬(wàn)八千里。本文的重點(diǎn)不是介紹原理，也不是探討算法優(yōu)劣，側(cè)重點(diǎn)在于如何基于Postgres快速落地一個(gè)性能還不錯(cuò)的推薦系統(tǒng)。

通過(guò)movielens.sql創(chuàng)建一個(gè)movielens數(shù)據(jù)庫(kù)

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

主要包含以下關(guān)系表，其中ratings表大概10w左右的數(shù)據(jù)：

    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) |

另外還需要一個(gè)Rails項(xiàng)目：https://github.com/hooopo/movielens-rails-app

“推薦系統(tǒng)中，推薦算法分為兩個(gè)門派，一個(gè)是機(jī)器學(xué)習(xí)派，另一個(gè)就是相似度門派。機(jī)器學(xué)習(xí)派是后起之秀，而相似度派則是泰山北斗，以致?lián)纹饋?lái)推薦系統(tǒng)的半壁江山?！?

相似度的算法非常多，下面來(lái)介紹一下常用的相似度算法以及Ruby代碼實(shí)現(xiàn)。

Jaccard相似度，是兩個(gè)集合的交集元素個(gè)數(shù)在并集中所占的比例。由于集合非常適用于布爾向量表示，所以Jaccard相似度簡(jiǎn)直就是為布爾值向量私人定做的，即Jaccard相似度非常適合做隱式反饋數(shù)據(jù)，比如收藏行為、加購(gòu)物車行為、點(diǎn)擊行為等。

      def jaccard_sim(other_movie)
        # 假設(shè)評(píng)分大于等于3的為喜歡
        other_user_ids = other_movie.ratings.where("rating >= 3").pluck(:user_id)
        user_ids       = self.ratings.where("rating >= 3").pluck(:user_id)
        
        # 交集數(shù)量
        intersection = (other_user_ids & user_ids).count
    
        # 并集數(shù)量
        union        = (other_user_ids | user_ids).count
    
        return 0 if union.zero?
        intersection.to_f / union.to_f
      end

余弦相似度在度量文本相似度、用戶相似度、物品相似度的時(shí)候都較為常用，它與向量的長(zhǎng)度無(wú)關(guān)。

      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
    
        # 有共同評(píng)價(jià)的用戶
        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

皮爾遜相關(guān)度，實(shí)際上也是一種余弦相似度，不過(guò)先對(duì)向量做了中心化，向量 p 和 q 各自減去向量的均值后，再計(jì)算余弦相似度。皮爾遜相關(guān)度和修正后的余弦相似度很像，但其實(shí)是有差別的，主要區(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
        
        # 有共同評(píng)價(jià)的用戶
        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)

上面代碼的目的是為了學(xué)習(xí)三種算法的實(shí)現(xiàn)，所以沒(méi)有復(fù)用，也沒(méi)有性能方面的優(yōu)化。純Ruby來(lái)做推薦基本不靠譜，所以我們來(lái)試一下基于Posgres和Jaccard相似度來(lái)實(shí)現(xiàn)一個(gè)推薦系統(tǒng)。

首先上面Ruby代碼里假設(shè)rating大于3就是喜歡，這并不十分準(zhǔn)確，有些人評(píng)分可能非常嚴(yán)格，他只打1-3分，那么對(duì)于他來(lái)說(shuō)，其實(shí)3分就算喜歡了。

為了應(yīng)對(duì)這種情況，我們用用戶均值來(lái)推斷他是否喜歡一部電影。另外我們要便于以后計(jì)算方便，把計(jì)算結(jié)果先緩存到movies的like_user_ids字段上。

      # 增加緩存字段like_user_ids，存儲(chǔ)喜歡這部電影的用戶ID
      def change
        add_column :movies, :like_user_ids, :integer, :array => true, :default => "{}"
      end
    
      # 使用PG內(nèi)置擴(kuò)展intarray：https://www.postgresql.org/docs/current/static/intarray.html
      # 對(duì)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字段，單條記錄更新可以實(shí)時(shí)計(jì)算出來(lái)填充進(jìn)去。

    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

由于排序字段是一個(gè)動(dòng)態(tài)計(jì)算值，所以這個(gè)語(yǔ)句無(wú)法利用索引，效率由movies表大小決定，但其實(shí)比Ruby版的已經(jīng)快很多了。

基于相似度的推薦算法的目標(biāo)就是產(chǎn)生一個(gè)Item-Item或User-User的相似度矩陣。用關(guān)系型數(shù)據(jù)庫(kù)的表示方法為：

    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)

假設(shè)movies表的數(shù)量是N，這個(gè)矩陣的條目數(shù)最大情況是 N*N，但實(shí)際并不需要全部Item之間的相似度都計(jì)算一遍：

相同ID的Item相似度一定是1，不需要計(jì)算和存儲(chǔ)

相似度為0的并不需要存儲(chǔ)

通過(guò)設(shè)置一個(gè)閾值score，過(guò)濾掉相似度很小的，比如score 小于0.2的就丟棄

通過(guò)設(shè)置一個(gè)閾值limit，過(guò)濾掉相關(guān)度排在后面的部分，比如一個(gè)Item最多存儲(chǔ)相關(guān)度最高的10個(gè)Item

經(jīng)過(guò)上面的步驟，相關(guān)度矩陣的存儲(chǔ)可以優(yōu)化到10*N左右，即10w個(gè)電影的話，相似度矩陣?yán)镏恍枰鎯?chǔ)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已經(jīng)預(yù)先計(jì)算好，這個(gè)查詢直接可以index only，記錄條數(shù)再多也是非常快的。不管是TopN推薦還是評(píng)分預(yù)測(cè)，只要相似度矩陣計(jì)算好了，之后的事情易如反掌。

下面就來(lái)預(yù)計(jì)算相似度。

    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    /* 過(guò)濾掉相似度太小的值 */
      ) 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只需要計(jì)算一次，但存儲(chǔ)兩份，為了查詢方便高效 */
      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;

上面已經(jīng)把相似度矩陣初始化完畢，對(duì)于新增數(shù)據(jù)，我們只需要把發(fā)生變化的數(shù)據(jù)重新計(jì)算一遍插入到item item matrix表里，這個(gè)代價(jià)非常小，可以bulk，也可以離線。對(duì)于數(shù)量大的系統(tǒng)，初始化步驟也是可以分步批量插入的。由于基于Postgres，對(duì)于超大量數(shù)據(jù)的情況，也可以平滑遷移到greemplum和citus或redshift這種可以并行查詢計(jì)算的存儲(chǔ)。

另外，也有一些基于postgres的推薦擴(kuò)展，不過(guò)版本都不是很新：

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

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