いいねの予測：単純なレコメンデーションエンジンのアルゴリズムの内部

レコメンデーションエンジン（レコメンダーシステムと呼ばれることもあります）は、アルゴリズム開発者が、特定のアイテムのリストの中でユーザーが好きなものと嫌いなものを予測できるようにするツールです。 レコメンデーションエンジンは、検索フィールドの非常に興味深い代替手段です。レコメンデーションエンジンは、他の方法では見つけられない可能性のある製品やコンテンツをユーザーが発見するのに役立ちます。 これにより、レコメンデーションエンジンは、Facebook、YouTube、AmazonなどのWebサイトやサービスの大きな部分を占めるようになります。

レコメンデーションエンジンは、2つの方法のいずれかで理想的に機能します。 ユーザーが好むアイテムのプロパティに依存することができます。これらのプロパティは、ユーザーが他に何を好むかを判断するために分析されます。 または、他のユーザーの好き嫌いに依存することもできます。これを使用して、レコメンデーションエンジンがユーザー間の類似性インデックスを計算し、それに応じてアイテムをレコメンデーションします。 これらの両方の方法を組み合わせて、はるかに堅牢なレコメンデーションエンジンを構築することもできます。 ただし、他のすべての情報関連の問題と同様に、対処する問題に適したアルゴリズムを選択することが不可欠です。

このチュートリアルでは、協調的でメモリベースのレコメンデーションエンジンを構築するプロセスについて説明します。 このレコメンデーションエンジンは、ユーザーが好きなものと嫌いなものに基づいて映画をユーザーに推薦し、前述の2番目の例のように機能します。 このプロジェクトでは、基本的なセット操作、少しの数学、およびNode.js/CoffeeScriptを使用します。 このチュートリアルに関連するすべてのソースコードは、ここにあります。

集合と方程式

協調的なメモリベースのレコメンデーションエンジンを実装する前に、まずそのようなシステムの背後にあるコアアイデアを理解する必要があります。 このエンジンにとって、各アイテムと各ユーザーは識別子に他なりません。 したがって、推奨事項を生成する際に、映画の他の属性（キャスト、監督、ジャンルなど）は考慮されません。 2人のユーザー間の類似性は、-1.0から1.0までの10進数を使用して表されます。 この番号を類似性インデックスと呼びます。 最後に、ユーザーが映画を好きになる可能性は、-1.0から1.0までの別の10進数を使用して表されます。 簡単な用語を使用してこのシステムの周りの世界をモデル化したので、これらの識別子と数値の関係を定義するために、いくつかの洗練された数学方程式を解き放つことができます。

レコメンデーションアルゴリズムでは、いくつかのセットを維持します。 各ユーザーには、ユーザーが好きな映画のセットと、ユーザーが嫌いな映画のセットの2つのセットがあります。 各映画には、映画を気に入ったユーザーのセットと、映画を嫌ったユーザーのセットの2つのセットも関連付けられます。 推奨事項が生成される段階で、いくつかのセットが作成されます。ほとんどの場合、他のセットの和集合または交差点です。 また、各ユーザーの提案と同様のユーザーのリストを注文します。

類似性指数を計算するために、Jaccard指数式のバリエーションを使用します。 元々は「coefficientdecommunaute」（Paul Jaccardによって造られた）として知られていたこの式は、2つのセットを比較し、0から1.0までの単純な10進統計を生成します。

この式には、いずれかのセットの共通要素の数を、両方のセットのすべての要素（1回だけカウント）の数で除算することが含まれます。 2つの同一セットのJaccardインデックスは常に1になりますが、共通要素のない2つのセットのJaccardインデックスは常に0になります。2つのセットを比較する方法がわかったので、2つを比較するために使用できる戦略を考えてみましょう。ユーザー。 前に説明したように、ユーザーは、システムの観点から、識別子、好きな映画のセット、嫌いな映画のセットの3つです。 ユーザーのお気に入りの映画のセットのみに基づいてユーザーの類似性インデックスを定義する場合、Jaccardインデックス式を直接使用できます。

ここで、U1とU2は比較している2人のユーザーであり、L1とL2はそれぞれU1とU2が気に入った映画のセットです。 さて、考えてみると、同じ映画が好きな2人のユーザーは似ているはずですが、同じ映画が嫌いな2人のユーザーも似ているはずです。 ここで、方程式を少し変更します。

数式の分子で一般的な好きなものだけを考慮するのではなく、一般的な嫌いなものの数も追加します。 分母には​​、ユーザーが好きまたは嫌いなすべてのアイテムの数が表示されます。 好き嫌いの両方を独立した方法で検討したので、2人のユーザーの好みが正反対である場合についても考える必要があります。 1人が映画を好きで、もう1人が映画を嫌う、2人のユーザーの類似性指数は0であってはなりません。

それは1つの長い式です！ しかし、それは簡単です、私は約束します。 これは前の式と似ていますが、分子にわずかな違いがあります。 現在、2人のユーザーの相反する好き嫌いの数を、共通の好き嫌いの数から差し引いています。 これにより、類似性インデックス式の値の範囲は-1.0〜1.0になります。 同じ趣味を持つ2人のユーザーの類似性指数は1.0ですが、映画で完全に相反する趣味を持つ2人のユーザーの類似性指数は-1.0になります。

映画の好みに基づいて2人のユーザーを比較する方法がわかったので、自家製のレコメンデーションエンジンアルゴリズムの実装を開始する前に、もう1つの式を検討する必要があります。

この方程式を少し分解してみましょう。 P(U,M)とは、ユーザーUが映画Mを気に入っている可能性を意味します。 ZLとZDは、それぞれ映画Mを好きまたは嫌いなすべてのユーザーとのユーザーUの類似性指数の合計です。 |ML|+|MD| 映画Mを好きまたは嫌いなユーザーの総数を表します。 結果のP(U,M)は、-1.0から1.0の間の数値を生成します。

それについてです。 次のセクションでは、これらの式を使用して、コラボレーティブメモリベースのレコメンデーションエンジンの実装を開始できます。

レコメンデーションエンジンの構築

このレコメンデーションエンジンを非常に単純なNode.jsアプリケーションとして構築します。 また、フロントエンドでの作業はほとんどなく、ほとんどの場合、一部のHTMLページとフォームです（ページをきれいに見せるためにBootstrapを使用します）。 サーバー側では、CoffeeScriptを使用します。 アプリケーションには、いくつかのGETルートとPOSTルートがあります。 アプリケーションにはユーザーの概念がありますが、複雑な登録/ログインメカニズムはありません。 永続性のために、NPM経由で利用可能なBourneパッケージを使用します。これにより、アプリケーションはデータをプレーンなJSONファイルに保存し、それらに対して基本的なデータベースクエリを実行できます。 Express.jsを使用して、ルートとハンドラーの管理プロセスを容易にします。

この時点で、Node.jsの開発に慣れていない場合は、GitHubリポジトリのクローンを作成して、このチュートリアルを簡単に実行できるようにすることをお勧めします。 他のNode.jsプロジェクトと同様に、まずpackage.jsonファイルを作成し、このプロジェクトに必要な依存関係パッケージのセットをインストールします。 複製されたリポジトリを使用している場合は、package.jsonファイルがすでに存在しているはずです。ここから、依存関係をインストールするには、「$npminstall」を実行する必要があります。 これにより、package.jsonファイル内にリストされているすべてのパッケージがインストールされます。

このプロジェクトに必要なNode.jsパッケージは次のとおりです。

• 非同期
• ボーン
• コーヒースクリプト
• 特急
• 翡翠
• アンダースコア

関連するすべてのメソッドを4つの別々のCoffeeScriptクラスに分割することにより、レコメンデーションエンジンを構築します。各クラスは、「lib / engine」（エンジン、評価者、類似、提案）の下に保存されます。 クラスEngineは、レコメンデーションエンジンにシンプルなAPIを提供する役割を果たし、他の3つのクラスをバインドします。 評価者は、（評価者クラスの2つの別個のインスタンスとして）好き嫌いを追跡する責任があります。 類似および提案は、それぞれ類似ユーザーおよびユーザーに推奨されるアイテムを決定および追跡する責任があります。

好き嫌いの追跡

まず、評価者クラスから始めましょう。 これは単純なものです：

 class Rater constructor: (@engine, @kind) -> add: (user, item, done) -> remove: (user, item, done) -> itemsByUser: (user, done) -> usersByItem: (item, done) ->

このチュートリアルの前半で示したように、いいね用の評価者と嫌いな人用の評価者のインスタンスが1つずつあります。 ユーザーがアイテムを気に入ったことを記録するために、それらを「Rater＃add（）」に渡します。 同様に、評価を削除するには、それらを「Rater＃remove（）」に渡します。

サーバーレスデータベースソリューションとしてBourneを使用しているため、これらの評価を「./db-#{@kind}.json」という名前のファイルに保存します。ここで、kindは「likes」または「dislikes」のいずれかです。 Raterインスタンスのコンストラクター内でデータベースを開きます。

 constructor: (@engine, @kind) -> @db = new Bourne "./db-#{@kind}.json"

これにより、「Rater＃add（）」メソッド内でBourneデータベースメソッドを呼び出すのと同じくらい簡単に評価レコードを追加できます。

 @db.insert user: user, item: item, (err) =>

そして、それらを削除するのと似ています（「db.insert」の代わりに「db.delete」）。 ただし、何かを追加または削除する前に、それがデータベースにまだ存在していないことを確認する必要があります。 理想的には、実際のデータベースを使用すると、単一の操作としてそれを実行できます。 Bourneでは、最初に手動チェックを行う必要があります。 また、挿入または削除が完了したら、このユーザーの類似性インデックスを再計算してから、一連の新しい提案を生成する必要があります。 「Rater＃add（）」メソッドと「Rater＃remove（）」メソッドは次のようになります。

 add: (user, item, done) -> @db.find user: user, item: item, (err, res) => if res.length > 0 return done() @db.insert user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done remove: (user, item, done) -> @db.delete user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done

簡潔にするために、エラーをチェックする部分はスキップします。 これは記事で行うのが合理的なことかもしれませんが、実際のコードのエラーを無視するための言い訳にはなりません。

このクラスの他の2つのメソッド「Rater＃itemsByUser（）」と「Rater＃usersByItem（）」では、名前が示すとおりに、ユーザーが評価したアイテムと、アイテムを評価したユーザーをそれぞれ検索します。 たとえば、Raterがkind = “likes”でインスタンス化されると、“ Rater＃itemsByUser（）”はユーザーが評価したすべてのアイテムを検索します。

類似ユーザーの検索

次のクラスに移ります：類似。 このクラスは、ユーザー間の類似性インデックスを計算して追跡するのに役立ちます。 前に説明したように、2人のユーザー間の類似性を計算するには、彼らが好きなアイテムと嫌いなアイテムのセットを分析する必要があります。 これを行うには、評価者インスタンスを使用して関連アイテムのセットをフェッチし、類似性インデックス式を使用して特定のユーザーペアの類似性インデックスを決定します。

前のクラスであるRaterと同様に、すべてを「./db-similars.json」という名前のBourneデータベースに配置します。これは、Raterのコンストラクターで開きます。 このクラスには「Similars＃byUser（）」メソッドがあり、単純なデータベース検索を通じて、特定のユーザーに類似したユーザーを検索できます。

 @db.findOne user: user, (err, {others}) =>

ただし、このクラスの最も重要なメソッドは「Similars＃update（）」です。これは、ユーザーを取得して類似している他のユーザーのリストを計算し、そのリストを類似性インデックスとともにデータベースに保存することで機能します。 それは、ユーザーの好き嫌いを見つけることから始まります。

 async.auto userLikes: (done) => @engine.likes.itemsByUser user, done userDislikes: (done) => @engine.dislikes.itemsByUser user, done , (err, {userLikes, userDislikes}) => items = _.flatten([userLikes, userDislikes])

これらのアイテムを評価したすべてのユーザーも見つかります。

 async.map items, (item, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.usersByItem item, done , done , (err, others) =>

次に、これらの他のユーザーのそれぞれについて、類似性インデックスを計算し、それをすべてデータベースに保存します。

 async.map others, (other, done) => async.auto otherLikes: (done) => @engine.likes.itemsByUser other, done otherDislikes: (done) => @engine.dislikes.itemsByUser other, done , (err, {otherLikes, otherDislikes}) => done null, user: other similarity: (_.intersection(userLikes, otherLikes).length+_.intersection(userDislikes, otherDislikes).length-_.intersection(userLikes, otherDislikes).length-_.intersection(userDislikes, otherLikes).length) / _.union(userLikes, otherLikes, userDislikes, otherDislikes).length , (err, others) => @db.insert user: user others: others , done

上記のスニペット内で、Jaccardインデックス式の変形である類似性インデックス式と本質的に同一の式があることに気付くでしょう。

推奨事項の生成

次のクラスであるSuggestionsは、すべての予測が行われる場所です。 類似クラスと同様に、コンストラクター内で開かれた「./db-suggestions.json」という名前の別のボーンデータベースに依存しています。

クラスには、指定されたユーザーの計算された提案を検索するためのメソッド「Suggestions＃forUser（）」があります。

 forUser: (user, done) -> @db.findOne user: user, (err, {suggestions}={suggestion: []}) -> done null, suggestions

これらの結果を計算するメソッドは「Suggestions＃update（）」です。 このメソッドは、「Similars＃update（）」のように、ユーザーを引数として取ります。 この方法は、特定のユーザーに類似するすべてのユーザーと、特定のユーザーが評価していないすべてのアイテムを一覧表示することから始まります。

 @engine.similars.byUser user, (err, others) => async.auto likes: (done) => @engine.likes.itemsByUser user, done dislikes: (done) => @engine.dislikes.itemsByUser user, done items: (done) => async.map others, (other, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.itemsByUser other.user, done , done , done , (err, {likes, dislikes, items}) => items = _.difference _.unique(_.flatten items), likes, dislikes

他のすべてのユーザーと未評価のアイテムがリストされたら、以前の推奨セットを削除し、各アイテムを繰り返し処理し、利用可能な情報に基づいてユーザーがそれを好きになる可能性を計算することで、新しい推奨セットの計算を開始できます。

 @db.delete user: user, (err) => async.map items, (item, done) => async.auto likers: (done) => @engine.likes.usersByItem item, done dislikers: (done) => @engine.dislikes.usersByItem item, done , (err, {likers, dislikers}) => numerator = 0 for other in _.without _.flatten([likers, dislikers]), user other = _.findWhere(others, user: other) if other? numerator += other.similarity done null, item: item weight: numerator / _.union(likers, dislikers).length , (err, suggestions) =>

それが完了したら、データベースに保存し直します。

 @db.insert user: user suggestions: suggestions , done

ライブラリAPIの公開

Engineクラス内では、すべてをきちんとしたAPIのような構造にバインドして、外部から簡単にアクセスできるようにします。

 class Engine constructor: -> @likes = new Rater @, 'likes' @dislikes = new Rater @, 'dislikes' @similars = new Similars @ @suggestions = new Suggestions @

Engineオブジェクトをインスタンス化したら、次のようにします。

 e = new Engine

好き嫌いを簡単に追加または削除できます。

 e.likes.add user, item, (err) -> e.dislikes.add user, item, (err) ->

また、ユーザー類似性インデックスと提案の更新を開始することもできます。

 e.similars.update user, (err) -> e.suggestions.update user, (err) ->

最後に、このEngineクラス（および他のすべてのクラス）をそれぞれの「.coffee」ファイルからエクスポートすることが重要です。

 module.exports = Engine

次に、1行で「index.coffee」ファイルを作成して、パッケージからエンジンをエクスポートします。

 module.exports = require './engine'

ユーザーインターフェイスの作成

このチュートリアルでレコメンデーションエンジンアルゴリズムを使用できるようにするために、Web上でシンプルなユーザーインターフェイスを提供したいと思います。 そのために、「web.iced」ファイル内にExpressアプリを生成し、いくつかのルートを処理します。

 movies = require './data/movies.json' Engine = require './lib/engine' e = new Eengine app = express() app.set 'views', "#{__dirname}/views" app.set 'view engine', 'jade' app.route('/refresh') .post(({query}, res, next) -> async.series [ (done) => e.similars.update query.user, done (done) => e.suggestions.update query.user, done ], (err) => res.redirect "/?user=#{query.user}" ) app.route('/like') .post(({query}, res, next) -> if query.unset is 'yes' e.likes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.dislikes.remove query.user, query.movie, (err) => e.likes.add query.user, query.movie, (err) => if err? return next err res.redirect "/?user=#{query.user}" ) app.route('/dislike') .post(({query}, res, next) -> if query.unset is 'yes' e.dislikes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.likes.remove query.user, query.movie, (err) => e.dislikes.add query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" ) app.route('/') .get(({query}, res, next) -> async.auto likes: (done) => e.likes.itemsByUser query.user, done dislikes: (done) => e.dislikes.itemsByUser query.user, done suggestions: (done) => e.suggestions.forUser query.user, (err, suggestions) => done null, _.map _.sortBy(suggestions, (suggestion) -> -suggestion.weight), (suggestion) => _.findWhere movies, id: suggestion.item , (err, {likes, dislikes, suggestions}) => res.render 'index', movies: movies user: query.user likes: likes dislikes: dislikes suggestions: suggestions[...4] )

アプリ内では、4つのルートを処理します。 インデックスルート「/」は、JadeテンプレートをレンダリングすることによってフロントエンドHTMLを提供する場所です。 テンプレートを生成するには、映画のリスト、現在のユーザーのユーザー名、ユーザーの好き嫌い、およびユーザーに対する上位4つの提案が必要です。 Jadeテンプレートのソースコードは記事から除外されていますが、GitHubリポジトリで入手できます。

「/like」および「/dislike」ルートは、POSTリクエストを受け入れて、ユーザーの好き嫌いを記録する場所です。 どちらのルートも、必要に応じて、最初に競合する評価を削除して評価を追加します。 たとえば、ユーザーが以前に嫌いなものを気に入った場合、ハンドラーは最初に「嫌い」の評価を削除します。 これらのルートにより、ユーザーは必要に応じてアイテムを「嫌い」または「嫌い」にすることもできます。

最後に、「/ refresh」ルートを使用すると、ユーザーはオンデマンドで一連の推奨事項を再生成できます。 ただし、このアクションは、ユーザーがアイテムに評価を付けるたびに自動的に実行されます。

試乗

この記事に従ってこのアプリケーションを最初から実装しようとした場合は、テストする前に最後の1つの手順を実行する必要があります。 「data/movies.json」に「.json」ファイルを作成し、次のような映画データを入力する必要があります。

 [ { "id": "1", "name": "Transformers: Age of Extinction", "thumb": { "url": "//upload.wikimedia.org/wikipedia/en/7/7f/Inception_ver3.jpg" } }, // … ]

いくつかの映画名とサムネイルURLが事前に入力されているGitHubリポジトリで利用可能なものをコピーすることをお勧めします。

すべてのソースコードの準備が整い、相互に接続されたら、サーバープロセスを開始するには、次のコマンドを呼び出す必要があります。

 $ npm start

すべてが順調に進んだとすると、ターミナルに次のテキストが表示されます。

 Listening on 5000

真のユーザー認証システムを実装していないため、プロトタイプアプリケーションは、「http：// localhost：5000」にアクセスした後に選択されたユーザー名のみに依存します。 ユーザー名を入力してフォームを送信すると、「おすすめの映画」と「すべての映画」の2つのセクションがある別のページに移動します。 コラボレーティブメモリベースのレコメンデーションエンジン（データ）の最も重要な要素が不足しているため、この新しいユーザーに映画をレコメンデーションすることはできません。

この時点で、「http：// localhost：5000」への別のブラウザウィンドウを開き、そこで別のユーザーとしてログインする必要があります。 この2番目のユーザーとしていくつかの映画が好きで嫌いです。 最初のユーザーのブラウザウィンドウに戻り、いくつかの映画も評価します。 両方のユーザーに少なくとも2、3の一般的な映画を評価してください。 すぐに推奨事項が表示されるようになります。

改善

このアルゴリズムのチュートリアルでは、プロトタイプのレコメンデーションエンジンを構築しました。 このエンジンを改善する方法は確かにあります。 このセクションでは、これを大規模に使用するために改善が不可欠ないくつかの領域について簡単に触れます。 ただし、スケーラビリティ、安定性、およびその他のそのようなプロパティが必要な場合は、常に、実績のある優れたソリューションを使用する必要があります。 記事の残りの部分と同様に、ここでのアイデアは、レコメンデーションエンジンがどのように機能するかについての洞察を提供することです。 現在の方法の明らかな欠陥（実装したいくつかの方法の競合状態など）を説明する代わりに、より高いレベルで改善について説明します。

ここでの非常に明白な改善の1つは、ファイルベースのソリューションではなく、実際のデータベースを使用することです。 ファイルベースのソリューションは、小規模なプロトタイプでは正常に機能する可能性がありますが、実際の使用にはまったく合理的な選択ではありません。 多くのオプションの1つはRedisです。 Redisは高速で、セットのようなデータ構造を処理するときに役立つ特別な機能を備えています。

簡単に回避できるもう1つの問題は、ユーザーが映画の評価を作成または変更するたびに、新しい推奨事項を計算しているという事実です。 リアルタイムでオンザフライで再計算を行う代わりに、ユーザーに対してこれらの推奨更新要求をキューに入れ、バックグラウンドで実行する必要があります。おそらく、時間指定の更新間隔を設定します。

これらの「技術的な」選択に加えて、推奨事項を改善するために行うことができるいくつかの戦略的な選択もあります。 アイテムとユーザーの数が増えると、推奨事項を生成するのに（時間とシステムリソースの点で）ますますコストがかかるようになります。 データベース全体を毎回処理するのではなく、推奨を生成するユーザーのサブセットのみを選択することで、これを高速化することができます。 たとえば、これがレストランのレコメンデーションエンジンである場合、同じ都市または州に住むユーザーのみを含むように同様のユーザーセットを制限できます。

その他の改善には、協調フィルタリングとコンテンツベースのフィルタリングの両方に基づいて推奨事項が生成されるハイブリッドアプローチの採用が含まれる場合があります。 これは、コンテンツのプロパティが明確に定義されている映画などのコンテンツで特に適しています。 たとえば、Netflixはこのルートを採用し、他のユーザーのアクティビティと映画の属性の両方に基づいて映画を推奨します。

結論

メモリベースの協調的レコメンデーションエンジンアルゴリズムは、非常に強力なものになる可能性があります。 この記事で実験したものは原始的かもしれませんが、それも単純です。理解しやすく、構築しやすいのです。 完璧にはほど遠いかもしれませんが、Recommendableなどの推奨エンジンの堅牢な実装は、同様の基本的な考え方に基づいて構築されています。

大量のデータを含む他のほとんどのコンピュータサイエンスの問題と同様に、正しい推奨事項を取得することは、作業するコンテンツの適切なアルゴリズムと適切な属性を選択することです。 この記事で、コラボレーティブメモリベースのレコメンデーションエンジンを使用しているときに何が起こるかを垣間見ることができたと思います。