摘要:機器學習派是后起之秀,而相似度派則是泰山北斗,以致撐起來推薦系統的半壁江山。純來做推薦基本不靠譜,所以我們來試一下基于和相似度來實現一個推薦系統。
對于內容類網站或者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 SimilarityJaccard相似度,是兩個集合的交集元素個數在并集中所占的比例。由于集合非常適用于布爾向量表示,所以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 endCosine 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) endPearson 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
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/38993.html
摘要:機器學習派是后起之秀,而相似度派則是泰山北斗,以致撐起來推薦系統的半壁江山。純來做推薦基本不靠譜,所以我們來試一下基于和相似度來實現一個推薦系統。 對于內容類網站或者APP,搜索和推薦已經是標配。搜索相對容易,使用Elasticsearch簡單配置一下就可以做出一個性能還不錯效果也還可以的搜索引擎,然而,推薦系統的話,沒有專門的團隊實踐起來還挺困難的。 網上推薦系統相關的理論非常多,但...
閱讀 1526·2023-04-26 00:20
閱讀 1121·2023-04-25 21:49
閱讀 803·2021-09-22 15:52
閱讀 577·2021-09-07 10:16
閱讀 972·2021-08-18 10:22
閱讀 2664·2019-08-30 14:07
閱讀 2237·2019-08-30 14:00
閱讀 2651·2019-08-30 13:00