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

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

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

初心者のためのモンテカルロシミュレーション

集合と方程式

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

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

類似性インデックスを計算するために、Jaccardインデックス式のバリエーションを使用します。元々は「coefficientdecomunauté」（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ユーザーの類似性インデックスの合計ですU映画を好きまたは嫌いなすべてのユーザーとそれぞれM。 |ML|+|MD|映画を好きまたは嫌いなユーザーの総数を表しますM。結果P(U,M) -1.0〜1.0の数値を生成します。

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

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

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

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

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

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

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

好き嫌いの追跡

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

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

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

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

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（）」は、名前が示すことを実行することを含みます。つまり、ユーザーによって評価されたアイテムと、アイテムを評価したユーザーをそれぞれ検索します。たとえば、評価者が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インデックス式の変形である類似性インデックス式と本質的に同一の式があることがわかります。

推奨事項の生成

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

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

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

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

sdrとの関係

@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' } }, // … ]

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

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

$ npm start

すべてが順調に進んだとすると、端末に次のテキストが表示されます。

Listening on 5000

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

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

改善点

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

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

誰かのクレジットカード番号を見つける方法

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

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

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

結論

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

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