レコメンダー・システム: 第 1 回 手法とアルゴリズムの紹介

Web 用のレコメンデーション・エンジンの基礎となる概念について学ぶ

大規模な商用 Web サイトやソーシャル Web サイトでは、そのほとんどがユーザーに対して、おすすめの商品を紹介してくれたり、おすすめのユーザーを紹介してつながれるようにしてくれたりします。レコメンデーション・エンジンは膨大なデータを分類し、ユーザーの気に入りそうなものを特定します。この記事では全 2 回からなる連載の第 1 回として、レコメンダー・システムの基礎となる概念を説明し、レコメンダー・システムを駆動するアルゴリズムについて紹介します。第 2 回では、利用可能なオープンソースのレコメンデーション・エンジンについて説明します。

M. Tim Jones, Independent author, .

M. TIm JonesM. Tim Jones は組み込みソフトウェアのエンジニアであり、『Artificial Intelligence: A Systems Approach』、『GNU/Linux Application Programming』や『AI Application Programming』、それに『BSD Sockets Programming from a Multilanguage Perspective』などの著者でもあります。技術的な経歴は静止軌道衛星用のカーネル開発から、組み込みシステム・アーキテクチャーやネットワーク・プロトコル開発まで、広範にわたっています。彼はコロラド州ロングモン在住で、Intel に勤務するプラットフォーム・アーキテクトです。



2014年 1月 16日

レコメンダー・システムはどこで使われているのか

レコメンダー・システムは、皆さんが日々利用している Web サイトの多くで使われています。その中には、以下のようなよく知られている Web サイトも含まれています。

LinkedIn: このビジネス向けソーシャル・ネットワーキング・サイトでは、ユーザーが知っていそうな人や、気に入りそうな仕事、フォローしたそうなグループ、関心がありそうな企業などをおすすめします。

Amazon: この人気の e-コマース・サイトでは、コンテンツ・ベースのレコメンダー・システムを使用しています。購入しようとする商品をユーザーが選択すると、Amazon はその商品を購入したことがある他のユーザーが購入した別の商品を (購入しようとしている商品に対し、次に購入しそうな商品のマトリックスとして) おすすめします。このアイテム間協調フィルタリングという動作で、Amazon は特許を取得しています。

Hulu: このストリーミング動画 Web サイトでは、レコメンデーション・エンジンを使用して、ユーザーが関心を持ちそうなコンテンツを特定します。また、アイテム・ベースの協調フィルタリングと Hadoop を (オフラインで) 使用して、膨大なデータをスケーラブルに処理します。Hulu がオンラインおよびオフラインで使用しているアイテム・ベースの協調フィルタリングのアーキテクチャーは、その詳細が公開されています。

Netflix: このビデオ・レンタルとストリーミング・サービスの例は有名です。Netflix は 2006年から、同社の (Cinematch というアルゴリズムを使用した) レコメンダー・システムを改善するためのコンテストを開催するようになりました。2009年に開催されたときには、3 つのチームによる共同チームが構築した、107 種類のレコメンデーション・アルゴリズムを組み合わせて 1 つの予測を生成するシステムが、予測精度を向上させるカギとなることが証明され、この共同チームが受賞しました。

他にも、レコメンデーション・エンジンを採用しているサイトとして、Facebook、Twitter、Google、MySpace、Last.fm、Del.icio.us、Pandora、Goodreads、そして皆さんのお気に入りのオンライン・ニュース・サイトなどがあります。最近の Web では、レコメンデーション・エンジンを使用することが一般的になりつつあります。

動きのない Web サイトにおけるユーザーとサイトのコミュニケーションの方法は、レコメンダー・システムによって変わりました。ユーザーが商品を検索し、場合によっては購入まで行う際に、レコメンダー・システムは静的なエクスペリエンスを提供するのではなく、対話部分を増やすことによって、よりリッチなエクスペリエンスを提供します。また、過去の購入履歴や検索履歴、さらには他のユーザーの振る舞いを基に、個々のユーザーに対するおすすめを自動的に示します。この記事では、レコメンダー・システムを紹介するとともに、レコメンダー・システムに実装されているアルゴリズムについて説明します。第 2 回では、おすすめ機能を構築するために利用できるオープンソースの選択肢について説明します。

基本的な手法

レコメンダー・システムのほとんどが、2 つの基本的な手法 (協調フィルタリング、またはコンテンツ・ベース・フィルタリング) のいずれかを使用しています。その一方で、他の手法 (ハイブリッド手法など) もあります。

協調フィルタリング

協調フィルタリングは、ユーザーのこれまでの振る舞いモデルに基づき、おすすめを抽出します。このモデルは、1 人のユーザーの振る舞いのみから構築することも、(もっと効果的な方法として) 類似の特徴を持つ他のユーザーの振る舞いから構築することもできます。他のユーザーの振る舞いを考慮に入れる場合、協調フィルタリングではグループ・ナレッジを使用して、似たようなユーザーを基におすすめを抽出します。つまり、おすすめは複数のユーザーの自動コラボレーションに基づいており、似たような好みや振る舞いを示すユーザーを条件にフィルタリングされています。

例えば、おすすめのブログを紹介する Web サイトを構築しているとします。ブログを購読して読んでいる多くのユーザーの情報を使用することにより、これらのユーザーの好みを基にユーザーをグループ分けすることができます。グループ分けの一例として、いくつかの同じブログを読んでいるユーザーを 1 つのグループにまとめることができます。この情報から、そのグループで読まれているブログの中で最も人気のあるブログを特定し、そのグループ内の特定のユーザーに対し、それらのユーザーが読むことも購読することもしていないブログの中で、最も人気のあるブログをおすすめします。

図 1 の表は、ブログの種類で行が構成されており、列にはユーザーが定義されています。ブログとユーザーが交差するセルには、該当するブログの中でそのユーザーが読んだ記事の数が記載されています。ユーザーが読んだ記事の傾向に基づいて (例えば、最近傍探索アルゴリズムを使用して) ユーザーをクラスタリングすると、それぞれ 2 人のユーザーからなる 2 つのクラスターになります。各クラスターのメンバーが読んだ記事の傾向が似ていることに注意してください。Marc と Elise はどちらも Linux とクラウド・コンピューティングに関する記事をいくつも読んでおり、クラスター 1 を構成しています。クラスター 2 を構成している Megan と Jill は、どちらも Java とアジャイルに関する記事をいくつも読んでいます。

図 1. 協調フィルタリングの単純な例
協調フィルタリングの単純な例を示す図

これで、各クラスター内でのいくつかの違いを明らかにして、効果的なおすすめを紹介することができます。クラスター 1 では、Marc はオープンソースに関するブログ記事を 10 本読んでいますが、Elise は 1 本も読んでいません。その一方で、Elise はアジャイルに関するブログ記事を 1 本読んでいますが、Marc は 1 本も読んでいません。そこで、図 1 の場合には Elise に対してオープンソースに関するブログ記事をおすすめすることができます。Marc と Elise が読んだアジャイルに関するブログ記事の本数の差は小さく、その差はフィルタリングによって消えてしまう可能性が高いため、Marc に対しておすすめするブログ記事はありません。クラスター 2 では、Jill はオープンソースに関するブログ記事を 3 本読んでいますが、Elise は 1 本も読んでいません。その一方で、Elise は Linux に関するブログ記事を 11 本読んでいますが、Jill は 1 本も読んでいません。そこでクラスター 2 では、Jill には Linux に関するブログ記事を、Megan にはオープンソースに関するブログ記事をおすすめすることができます。

これらの関係は、図 2 のベン図に示すように、類似要素 (Similarities) と相違要素 (Differences) を基に表すこともできます。類似要素によって、同じような関心を持つユーザーをグループ化する方法が (使用される特定のアルゴリズムに基づいて) 定義されます。相違要素は、(例えば、人気によってフィルタリングすることにより) おすすめを紹介するために使用できる可能性があります。

図 2. 協調フィルタリングで使用される類似要素と相違要素
協調フィルタリングで使用される類似要素と相違要素を示す図

図 2 はあまりにも単純ですが (しかも 2 つのサンプルしか使用していないためデータが少なすぎるという問題はありますが)、便利な表現方法です。

コンテンツ・ベース・フィルタリング

コンテンツ・ベース・フィルタリングは、ユーザーの振る舞いに基づいておすすめを作成します。この手法では、ユーザーの閲覧履歴情報 (ユーザーが読んでいるブログの種類やそれらのブログの特徴など) を使用する場合があります。あるユーザーが Linux に関する記事を日常的に読んでいる場合や、ソフトウェア・エンジニアリングに関するブログ記事にコメントを残す可能性が高い場合、コンテンツ・ベース・フィルタリングはこの履歴情報を使用することにより、似たようなコンテンツ (Linux に関する記事や、ソフトウェア・エンジニアリングに関する他のブログ) を特定し、おすすめすることができます。こうしたコンテンツは手作業で定義することも、類似度法を用いた別の方法で自動抽出することもできます。

図 1 に戻って、Elise というユーザーに注目してみます。ブログ・ランキングで、Linux に関するブログ記事を読んでいるユーザーはオープンソースやクラウド・コンピューティングに関するブログ記事も読んでいる可能性があることが示される場合、Elise が現在読んでいる記事の傾向を基に、オープンソースに関する記事を読むことをおすすめすることが容易にできます。この手法は (図 3 に示すように) 1 人のユーザーがアクセスしているコンテンツのみに基づくものであり、システム内の他のユーザーの振る舞いに基づくものではありません。

図 3. コンテンツ・ベース・フィルタリングで使用される、ブログ・ランキングとの相違点
コンテンツ・ベース・フィルタリングで使用される、ブログ・ランキングとの相違点を示す図

この場合にも図 2 のベン図を使用することができます。一方の円が Elise というユーザーであり、もう一方の円は似たような一連のブログ記事をランク付けしたものだとすると、(Elise は、類似要素に含まれるブログ記事を既に読んでいるため) 類似要素を無視し、ランク付けされたブログ記事との相違要素をおすすめできる可能性があります。

ハイブリッド

協調フィルタリングとコンテンツ・ベース・フィルタリングを組み合わせたハイブリッド手法も、レコメンダー・システムの効率 (そして複雑性) を高めることができます。単純なハイブリッド・システムの例では、図 1図 3 の手法を使用することができます。協調フィルタリングの結果とコンテンツ・ベース・フィルタリングの結果を組み合わせることで、より適切なブログ記事をおすすめできる可能性があります。またハイブリッド手法を使用して、最初はコンテンツ・ベース・フィルタリングに重点を置いて結果を生成するようにし、その後ユーザー・データ・セットが充実するのに伴い、協調フィルタリングに重点を置くようにシフトすることで、スパース・データで開始される (「コールド・スタート」と呼ばれます) 協調フィルタリングに対処することができます。


レコメンダー・システムで使用されるアルゴリズム

Netflix のコンテストで受賞した手法が示しているように、レコメンデーション・エンジンではさまざまなアルゴリズムによる手法を使用することができます。レコメンデーション・エンジンが生成する結果は、そのアルゴリズムがどういう問題を解決することを目的としているか、あるいはデータ内にどのような関係が存在するかによって変わってきます。これらのアルゴリズムの多くは、機械学習の分野で生まれたものです。機械学習は人工知能の一分野であり、この分野から学習、予測、意志決定のためのアルゴリズムが生み出されています。

ピアソン相関

2 人のユーザー間の類似度 (そしてこれらのユーザーが持つ特質 (例えば、一連のブログのなかで読んだことがある記事など)) は、ピアソン相関を使用して正確に計算することができます。このアルゴリズムでは、2 つの変数 (つまり 2 人のユーザー) の間にある線形依存度を、それらのユーザーが持つ特質の関数として評価します。ただし、このアルゴリズムはユーザーの集合全体に対して依存度を計算するわけではありません。「似たようなブログ記事を読んでいる」といった大まかな類似度を基準に、ユーザーの集合全体を似通った集合にまでフィルタリングする必要があります。

ピアソン相関は、調査で広く使用されており、協調フィルタリングのアルゴリズムとしてもよく使用されています。

クラスタリング・アルゴリズム

クラスタリング・アルゴリズムは、一見ランダムな (つまり、ラベル付けされていない) 一連のデータの中で構造を見つけ出すことができる、教師なし学習の一形態です。このアルゴリズムは一般に、アイテム同士 (例えば、ブログの読者同士) の類似度を明らかにするとともに、特徴空間におけるアイテム同士の距離を計算することによって動作します (特徴空間における特徴は、一連のブログ記事の中で読まれた記事の数を表すことができます)。独立した特徴の数によって、特徴空間の次元が決まります。アイテム同士が「近い」場合には、同じクラスターの中にそれらのアイテムを含めることができます。

クラスタリング・アルゴリズムには、さまざまなものがあります。最も単純なものは、アイテムを k 個のクラスターに分ける K-means (K 平均) 法です。このアルゴリズムでは、まず各アイテムが複数のクラスターにランダムに配置されます。次に、各クラスターのセントロイド (つまり、中心) がクラスターのメンバーの関数として計算されます。続いて、セントロイドから各アイテムまでの距離が調べられ、現在配置されているクラスターよりも別のクラスターの方が近いことが判明したアイテムは、そのクラスターに移動されます。すべてのアイテムの距離を調べるたびに、セントロイドが再計算されます。安定状態に達すると (つまり、上記の動作を繰り返し行っても、もう移動されるアイテムがなくなると)、その集合は適切にクラスタリングされたことになり、このアルゴリズムは終了します。

2 つのオブジェクト間の距離の計算は、視覚化するのが難しい場合があります。よく使われる方法の 1 つは、各アイテムを多次元ベクトルとして扱い、ユークリッド・アルゴリズムを使用して距離を計算する方法です。

クラスタリングの他のバリエーションをいくつか挙げると、ART (Adaptive Resonance Theory: 適応共鳴理論) 法、FCM (Fuzzy C-means) 法、EM (Expectation-Maximization) 法 (確率的クラスタリング) などがあります。

他のアルゴリズム

レコメンデーション・エンジン用のアルゴリズムは、数多く存在しており、それらのアルゴリズムのバリエーションがさらに多く存在しています。使用され続けているアルゴリズムには、以下のようなものがあります。

  • ベイズ信頼度ネット (Bayesian Belief Net): 無閉路有向グラフとして視覚化することができ、枝によって変数同士が関連する確率を表します。
  • マルコフ連鎖 (Markov Chain): ベイズ信頼度ネットと似た手法を採りますが、おすすめの問題を単純予測ではなく逐次最適化として扱います。
  • Rocchio 分類法: ベクトル空間モデルを使用して開発されており、アイテムの関連性についてのフィードバックを利用して、おすすめの精度を高めます。

レコメンダー・システムの課題

Web からデータを収集できるおかげで、(協調フィルタリングを使用して) 「群衆の知恵」を活用することがより簡単になりました。その一方で、膨大なデータを利用できることから、データ収集が複雑な作業になっているのも事実です。例えば、一部のユーザーの振る舞いをモデル化することはできても、他のユーザーが典型的な振る舞いを示さなければ、これらのユーザーによってレコメンダー・システムの結果が歪められ、レコメンダー・システムの性能が低下する可能性があります。また、ユーザーがレコメンダー・システムを利用して、ある製品を他の製品よりもひいきするために、例えばある製品には肯定的なレビューを書き、その競合製品には否定的なレビューを書くことができます。優れたレコメンダー・システムは、これらの問題に対処しなければなりません。

レコメンダー・システムが大規模になると生じる特有の問題が、スケーラビリティーの問題です。従来のアルゴリズムは、少量のデータには有効ですが、データ・セットが大きくなると対応しきれない場合が出てきます。これはオフライン処理の場合は問題にならないかもしれませんが、リアルタイム処理の場合にはより特化した手法が必要です。

最後に挙げるのは、プライバシー保護について考慮するという課題です。レコメンダー・アルゴリズムは、ユーザー自身も気付いていないパターンの存在を明らかにすることができます。最近の例として、ある大企業が購入の傾向に基づいて妊娠予測スコアの計算を可能にしたケースがあります。ある父親は、ターゲット広告を通じて自分の十代の娘が妊娠したことを知って驚きました。この企業の予測機能は非常に正確であったため、その女性が購入した商品から出産予定日を予測することができたのです。


さらに詳しく調べてください

今やレコメンデーション・エンジンは人気のソーシャル Web サイトや商用サイトのほとんどに活用されています。レコメンデーション・エンジンはサイトの所有者やユーザーに大きな価値をもたらしますが、いくつかの欠点もあります。この記事では、レコメンダー・システムの背後にある概念と、それらのシステムを駆動するアルゴリズムについて説明しました。この連載の第 2 回では、おすすめ機能を構築するために利用可能なオープンソースのコメンデーション・エンジンをいくつか紹介します。

参考文献

学ぶために

  • レコメンダー・システムのウィキ: このサイトにアクセスして、広範なソースからレコメンダー・システムについての情報を入手してください。
  • Recommendations @ LinkedIn: Abihishek Gupta と Adil Aijaz によるこのプレゼンテーションから LinkedIn のレコメンデーション・エンジンについて学んでください。
  • Hulu 's Recommendation System」: Hulu のフレームワーク上でコンテンツ所有者が自分のコンテンツを宣伝する上で、Hulu のレコメンデーション・エンジンがどう役立つのかを調べてください。
  • Netflix Recommendations: Beyond the 5 stars」: Netflix のレコメンデーション・エンジン、Netflix 賞、Netflix 賞のコンテストで生じた問題などについて学んでください。
  • Web-Scale User Modeling for Targeting」: Yahoo! によるこの論文を読んで、Hadoop を使用してインターネット規模でユーザー向けの広告の選択を最適化するためのユーザー・モデリング・プラットフォームについて学んでください。
  • A Survey of Collaborative Filtering Techniques」: レコメンダー・システムの詳細な扱い方とレコメンダー・システムの課題、そして協調フィルタリング技術に関する有用な調査について取り上げたこの記事を読んでください。
  • AI Application Programming, 2nd edition」(M. Tim Jones 著、Cengage Learning、2005年): この本を読んで、レコメンダー・システムと人工知能についての全般を学んでください。
  • Patterns In and Across Aggregated Data — Is "Anonymous" Collaborative Filtering Really Safe?」: 協調フィルタリングが抱える脅威とプライバシーのリスクについて、Kent Anderson 氏が提起しています。
  • How Target Figured Out a Teen Girl Was Pregnant Before Her Father Did」: レコメンダー・システムの不安定な性質とアイテム・ベースの協調フィルタリングに潜在するリスクについての著者の見解を理解してください。
  • developerWorks Open source テクニカル・トピックス: オープンソース技術を使用した開発や、オープンソース技術を IBM 製品とともに使用するのに役立つ広範なハウツー情報、ツール、およびプロジェクトの更新を見つけてください。

議論するために

  • developerWorks コミュニティーに参加してください。ここでは他の developerWorks ユーザーとのつながりを持てる他、開発者によるブログ、フォーラム、グループ、Wiki を調べることができます。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Open source, Web development
ArticleID=959848
ArticleTitle=レコメンダー・システム: 第 1 回 手法とアルゴリズムの紹介
publish-date=01162014