推奨アルゴリズム集（パート1） - 協調フィルタリングアルゴリズム

【51CTO.comオリジナル記事】

1. ロングテール効果？動物の尻尾と関係があるのでしょうか？

前回の記事でレコメンデーションシステムの分類と機能について説明しましたが、その中の用語の 1 つである「ロングテール効果」について詳しく説明する必要があります。ロングテール効果は、百度百科事典では「人々のニーズから見ると、需要の大部分はヘッドに集中しており、人気があると言えるが、テールに分散している需要は個性的で、分散していて、小さい」と説明されています。しかし、テールの需要を過小評価しないでください。人気のあるヘッド製品の種類は結局のところ限られているのに対し、テール製品の種類は多いからです。たとえ需要が小さくても、組み合わせると、全体の需要は人気のあるヘッドの需要を下回らない可能性があります。何千もの小さな流れが合流すると、湖や海よりも強くなるかもしれない。ロングテール効果は、以下の図に示すように、数学モデル曲線上の正規曲線で表されます。（ここでは例を示します。ヘッドは大手の携帯電話ブランド企業で、テールは小規模の携帯電話ブランド企業です）

上図に示すように、大手ブランド（Apple、Samsung、Huaweiなど）の携帯電話販売台数はいずれも上位数位を占めていますが、総販売台数、つまり青いグラフの面積は、黄色いグラフの面積よりもはるかに小さいです。黄色のグラフは、小規模ブランド（Smartisan、OnePlus、Meizu、ZTEなど）の携帯電話の総販売台数を表しています。それらの合計販売台数は非常に印象的で、「数は力なり」という言葉も裏付けられています。したがって、レコメンデーションシステムを設計する際には、大手ブランドの売上を確保する必要がありますが、小規模ブランドを無視してはなりません。推奨される製品は大手ブランドに関連性の高いものになるかもしれませんが、顧客の潜在的な関心を引き続き掘り下げ、小規模ブランドの携帯電話のいくつかのタイプを推奨することも必要です。この方法でのみ、「ロングテール効果」を軽減または解決できます。この方法でのみ、設計された推奨システムはよりインテリジェントかつ人間味を帯びたものとなり、ユーザーの満足度と定着率を高めることができます。

2. 推奨システムとアルゴリズムの開発の歴史と研究状況はどのようなものですか?

「ロングテール効果」について説明したので、次は推奨システムの真の核心である推奨アルゴリズムについて説明します。まず、レコメンデーションシステムの開発履歴と現在の研究状況を見てみましょう。

1995年3月、アメリカ人工知能学会でパーソナライズされたナビゲーションシステムが提案され、スタンフォード大学の研究者も同会議でパーソナライズされた推薦システムLIRAを発表しました。その後、多くの企業や大学の研究機関が推薦システムの研究に投資し、パーソナライズされたポータル、協調フィルタリングに基づくパーソナライズされた推薦システム、パーソナライズされた推薦電子商取引プラットフォームを次々と立ち上げました。わが国では2009年以降に推薦の研究が始まり、国内初の推薦システム研究チームである百分店信息技術有限公司が設立されました。その後、百度世界大会2011で、百度はクラウドコンピューティングや検索エンジンとともに、推薦エンジンをインターネットの重要な戦略計画と方向性として挙げました。レコメンデーション エンジンの登場により、ユーザーが情報を取得する方法も、単純なターゲット指向のデータ検索から、人々の検索習慣に沿った情報クエリへと変化しました。現在、ほとんどの電子商取引サイトやソーシャル ネットワーキング サイトで使用されている推奨エンジンの動作原理は、類似したアイテムやユーザーのセットに基づいて推奨を行うことです。主流の推奨アルゴリズム モデルは、依然として協調フィルタリングに基づいて推奨を完了します。そのため、まず協調フィルタリング アルゴリズムから始めて、他の推奨アルゴリズムを段階的に紹介し、読者が段階的に理解し、各推奨アルゴリズムの長所と短所を基本的に把握し、各アルゴリズムと使用環境を真に区別して分析できるようにします。

3. 推奨アルゴリズムにおける「いたずらっ子」 - 協調フィルタリングアルゴリズム

なぜ協調フィルタリング アルゴリズムは「お年寄りのいたずらっ子」と呼ばれるのでしょうか。「お年寄りのいたずらっ子」の特徴は誰もが知っているはずです。まず、彼は年寄りでなければなりません。これは、協調フィルタリング アルゴリズムが推奨システムで使用される最も古いアルゴリズムであり、アルゴリズムの「古い先駆者」と見なすことができるという事実にも一致しています。次に、「お年寄りのいたずらっ子」は若い精神を維持し、時代の流れに遅れずについていき、若者と遊ぶ必要があります。これは、協調フィルタリング アルゴリズムが今でも最も人気があり、広く使用されている推奨アルゴリズムであるという事実にも一致しています。市場に出回っている推奨システムの半分以上が依然として協調フィルタリング アルゴリズムに依存していると言えます。全体的な推奨効果は他の新しく開発された推奨アルゴリズムに劣らず、協調推奨アルゴリズムのパフォーマンスは最も安定しています。推奨システムについて言及されるたびに、最初に思い浮かぶアルゴリズムは協調フィルタリングです。したがって、協調フィルタリング アルゴリズムは古典的で時代を超越しており、推奨アルゴリズムの中ではまさに「古株」であると言わざるを得ません。では、この「いたずらっ子」についてもっと詳しく知りましょう。

協調フィルタリング（CF）の主なアイデアは、現在のユーザーと同じ興味や過去の行動を持つ他のユーザーグループを使用し、これらのユーザーグループの現在の好みや行動情報を分析することで、現在のユーザーが何を好むか、どのような行動が発生する可能性があるかを予測することです。簡単に言えば、「類は友を呼ぶ」というフレーズです。例えば、ユーザーAは、キング・オブ・コメディ、リッチスト・トマト、クレイジー・ストーンなどのコメディ映画を見るのが好きで、最近も見ています。ユーザーBとユーザーCもコメディ映画を見るのが好きで、最近上記3つの映画を見ています。このとき、BとCはAと似た興味を持つユーザーグループに分けることができます。BとCが次に見る映画や、Aが見たが見ていない映画は、ユーザーAのおすすめ予測映画として使用できます。この推奨アルゴリズムは非常に直接的かつシンプルで、実際のアプリケーションでは優れた推奨結果を達成できることが多いです。このタイプの推奨アルゴリズムの主な適用シナリオは、オンライン小売システムです。私が以前勤務していたインターネット小売会社では、このアルゴリズムを使用して製品を宣伝し、商品の売上を伸ばしていました。

このタイプのアルゴリズムの入力はユーザーとアイテムの評価マトリックスであり、出力データは 2 つのカテゴリに分けられます。1 つはアイテムに対する現在のユーザーの好みの予測値であり、もう 1 つは推奨される上位 N 個のアイテムのリストです。もちろん、このリストには現在のユーザーがすでに購入したアイテムを含めることはできません。協調フィルタリング アルゴリズムを実装する主な最も基本的な方法は、ユーザー ベースの最近傍推奨とアイテム ベースの最近傍推奨の 2 つです。原理は、アイテムや情報に対するユーザーの好みに基づいて、アイテム自体の関連性、またはユーザー間の関連性を発見し、関連性スコアに基づいて並べ替えて推奨することです。

4.CFユーザ​​ーベースの最近傍推奨

4.1 ユーザーベースの最近傍推奨の主なアイデア

ユーザーベースの最近傍推奨の主な考え方は次のとおりです。

（１）入力評価データセットと現在のユーザーIDを入力として、ピアソン相関係数を使用して2人のユーザー間の相関関係を表し、現在のユーザーの過去の行動履歴に類似した行動や嗜好を持つ他のK人のユーザーを見つけます。これらのユーザーはピアユーザーまたは最近傍ユーザーとも呼ばれます。

（２）現在のユーザーと他のユーザーとの相関関係を計算した後、現在のユーザーが購入または閲覧していない各アイテムについて、ユーザーのK近傍を使用してアイテムの評価を予測し、アイテム評価ランキング表を形成する。

（３）アイテムスコアが最も高いアイテムを必要な数選択し、現在のユーザーに推奨する。

もちろん、ユーザーベースの最近傍推奨アルゴリズムにも独自の前提があります。つまり、ユーザーが過去に同様の好みを持っていた場合は、将来も同様の好みを持つはずであり、つまり、ユーザーの好みは時間の経過とともに変化しないということです。この前提の下では、ユーザーベースの最近傍推奨を使用するのが最も合理的であり、推奨効果はより満足のいくものになります。

4.2 ピアソン相関係数

現在のユーザーの最も近い隣人を取得する場合、前述のピアソン相関係数を考慮する必要があります。この係数は、以下に示すように、ユーザー間の相関関係を解決するために使用される式です。

ピアソン相関係数は 2 人のユーザー間の相関関係を表し、その値の範囲は [-1, +1] です。ここで、-1 は強い負の相関関係、+1 は強い正の相関関係、0 は相関関係がないことを示します。式は次のとおりです。

ピアソン相関係数を使用するには、2 つの変数間の標準偏差が 0 であってはなりません。この方法でのみ相関係数を定義できます。この係数は通常、次の変数環境で使用されます。

（１）２つの変数の間には線形関係があり、両方とも連続している。

（２）２つの変数の母集団は正規分布または単峰性である。

（３）２つの変数の観測値は対になっており、各観測値は互いに反対である。

ユーザーの関連性を計算した後、最も類似した N 人の近隣ユーザーを選択して、アイテムの予測評価値を計算できます。つまり、N 人の近隣ユーザー全員がアイテムの評価値を持っています。評価予測式は次のとおりです。

4.3 ユーザーの最も近い隣人に基づく推薦事例

最後に、アイテムに対するユーザーの予測スコアが取得されます。式のこの部分については、読者の理解を助けるために例を示します。

たとえば、ユーザー評価マトリックスは次の表のようになります。この評価マトリックスに基づいて、Xiao Ming のアイテム F の評価を計算してみましょう。

（１）まず、ピアソン相関係数を用いてシャオミンと他の４人のユーザーとの類似度を計算します。計算手順は同じなので、シャオミンとシャオジャオの類似度のみを計算します。興味のある読者は、シャオミンと他のユーザーとの類似度を計算する手順を真似することができます。

（２）シャオミンの平均点は（１０＋６＋８＋８）／４＝８、シャオジャオの平均点は（６＋２＋４＋６＋６）／５＝４．８である。次の式が得られる。

同様に、Xiao Ming と Xiao Li、Xiao Wang、Xiao Zhang の類似度はそれぞれ 0.71、0.00、-0.89 です。パラメータ N が 2 に選択されたと仮定すると、類似度値から、Xiao Ming に最も類似する 2 人は Xiao Zhao と Xiao Li であることがわかります。類似度は、以下に示す折れ線グラフからも直感的に確認できます。

したがって、Xiao Ming のアイテム F の評価を予測するために、Xiao Zhao と Xiao Li のアイテム F の評価を選択すると、次のようになります。

したがって、Xiao Mingの項目Fのスコアは9.75であると予測されます。

5.CF — アイテムの最近傍に基づく推奨

5.1 アイテムの最も近い近傍に基づく推奨

アイテムベースの最近傍推奨の考え方は、ユーザー間の類似性ではなく、アイテム間の類似性に基づいて評価値を予測するというものです。

5.2 コサイン類似度

アイテムベースの最近傍推奨アルゴリズムでは、通常、コサイン類似度を使用して 2 つのアイテム間の類似度を計算します。類似度値の範囲は [0,1] です。値が 1 に近いほど、類似度が高くなります。もちろん、ピアソン相関係数を使用してアイテム間の類似性を計算することもできます。そのためには、上で使用したピアソン相関係数の式の平均ユーザー評価を平均アイテム評価に変更する必要があります。計算プロセスは同じであるため、ここでは詳細には触れません。ユーザー評価の平均値の差を考慮するために、一般的には改良コサイン類似度式を使用して類似度を計算します。コサイン類似度を改良することで評価値から平均値を減算し、最終的な値の範囲がピアソン相関係数の値の範囲と一致し、これも [-1、+1] になります。改良されたコサイン類似度の式は次のとおりです。

同様に、アイテム間の類似度を計算した後、最も類似している上位 N 個のアイテムを選択し、次の式を使用してアイテムに対するユーザーの評価を予測します。

5.3 アイテム最近傍に基づく推奨事例

前回のケースの評価マトリックスを使用して同じ計算を実行します。計算の便宜上、上記のユーザー-アイテム評価マトリックスは、平均を互いに減算した評価マトリックスに調整されます。これにより、不要な計算がいくつか省略され、次の式の計算が容易になります。平均調整後のユーザー評価マトリックスを次の表に示します。

アイテム A とアイテム F の類似度は、改良されたコサイン類似度の式で計算できます。

同様に、アイテム F とアイテム B、アイテム C、アイテム D との類似度はそれぞれ -0.94、0.35、-0.48 と計算できます。

同様に、選択したパラメータ N が 2 であると仮定すると、アイテム F と他のアイテムとの類似度値を見ると、アイテム F との類似度が最も高い 2 つのアイテムはアイテム A とアイテム C であることがわかります。これらのアイテムの類似度は、折れ線グラフからも直感的に観察できます。

類似状況、折れ線グラフは次のようになります。

したがって、項目 A と項目 C のスコアを選択して、項目 F のシャオミンのスコアを予測すると、次のようになります。

したがって、Xiao Mingの項目Fのスコアは9.36であると予測できます。

5.4 ちょっとした質問ですが？

上記から、アイテム評価マトリックスによって各アイテム間の類似度を計算でき、各アイテム間の類似度マトリックスを取得できることがわかります。これは各アイテム間の類似度のオフライン計算ですが、実際のアプリケーションでは数億のアイテムが関係し、結果として得られる評価マトリックスまたは類似度マトリックスは数十億×数十億のマトリックスになります。オフライン コンピューティングを使用する場合、オフライン コンピューティングの結果を保存するために数百 GB のメモリが必要になります。また、リアルタイム計算の場合、計算プロセスは基本的にリアルタイム要件を満たすことができません。したがって、この問題を考慮する必要があります。そのため、実際のアプリケーションでは、通常、各評価マトリックスの類似度を事前に計算し、各項目と類似度の値を形式でredisに保存し、リアルタイムで呼び出します。もちろん、リレーショナル データベースに保存することも可能で、SQL ステートメントを使用して簡単にデータを照会および変更できます。どのような保管方法を採用するかについては、実際のアプリケーションシナリオに基づいて検討する必要があります。

アイテムベースの最近傍推奨は、オフライン データを使用して事前に計算できます。原則として、まずアイテム類似性マトリックスを構築して、2 つのアイテム間の類似性を説明します。オンラインで実行する場合、アイテムに最も類似する他のアイテムを決定することによって、これらの近隣アイテムに対するユーザーの評価の加重合計が計算され、それによって現在のアイテムに対するユーザーの予測評価が取得されます。近隣アイテムの数は、最初にユーザー評価のないアイテムを除外することによって排除できるため、ユーザー評価のあるアイテムの数によって制限され、予測値を計算するプロセスは、オンラインインタラクションプロセス中に短時間で完了できます。もちろん、このオフライン データ前処理方法は、ユーザーベースの最近傍推奨にも適用できますが、実際の状況では、2 人のユーザーの評価が重複することはまれであり、他の評価値が最終ユーザー間の類似度の計算に影響を与えます。つまり、アイテム間の類似性はユーザー間の類似性よりも安定しており、この方法ではアイテム間の類似性は変化しません。

6. 最近傍推薦法の利点

協調フィルタリング アルゴリズムは、ユーザーまたはアイテムのどちらに基づいていても、最近傍法を使用して推奨を完了します。この最近傍法による推奨の利点は次のとおりです。

（１）シンプルさ：アルゴリズムの実装は簡単で、計算プロセス中に調整する隣接数パラメータは１つだけなので、変更や調整が容易です。

（２）安定性：類似度マトリックスが構築された後、新規ユーザーまたは新規アイテムに評価がある場合、他のユーザーまたはアイテム間の類似度値に影響を与えることなく、新規ユーザーまたは新規アイテムと他のユーザーまたはアイテムとの類似度を計算することによって類似度マトリックスの更新操作を完了することができます。

合理性: この予測方法は解釈性が高く、予測の推奨事項の簡潔で直感的な理由を提供します。

（３）効率性：近傍法に基づく推奨効果は、オフラインでデータの前処理を行い、類似度マトリックスを事前に構築できるため、実際のアプリケーションでほぼリアルタイムの推奨結果を提供し、優れたリアルタイム性能を備えているため、比較的高い。

もちろん、最近傍推奨法には利点がある一方で、限界や欠点も確かにあります。場合によっては、推奨効果が非常に低かったり、完了不可能だったりすることもあります。以降の記事では、他の推奨アルゴリズムを紹介する際にこれらの制限と欠点について説明します。これにより、各推奨アルゴリズムの起源と用途をより明確に理解できるようになります。推奨アルゴリズムはどれも、問題に対処したり、他のアルゴリズムのギャップを埋めたりして、独自の利点をより際立たせる必要があるためです。したがって、ここでは最近傍推奨方式の欠点については詳しく説明しません。

7. 評価マトリックスと評価について教えてください。

協調フィルタリングアルゴリズムや最近傍推奨アルゴリズムについて説明した後、読者は上記のプロセスに最も基本的な計算前提、つまりユーザー評価マトリックスとアイテム評価マトリックスがあることに気づいたでしょうか。では、評価はどこから来るのでしょうか? 評価が非常に多いため、評価マトリックスを構築することは問題ではありません。そこで、ここで評価の由来を説明し、読者のいくつかの質問に答える必要があります。

協調フィルタリング（CF）アルゴリズムでは、入力はユーザー-アイテム評価マトリックスであるため、ユーザー-アイテム評価マトリックスの構築が協調フィルタリングアルゴリズムの重要なポイントとなります。スコアは通常、2 点制、5 点制、7 点制、10 点制を使用して計算されます。アイテムに対するユーザー評価を収集するには、主に 2 つの方法があります。

(1) 明示的な評価: 直接見ることができ、直感的にわかる数値評価です。アンケートを通じて収集され、特定の製品に対するユーザーの評価を収集します。たとえば、製品を閲覧したり、ブラウザにログインしたりすると、通常、製品やウェブサイトのコンテンツを評価するように求めるインターフェイスが表示されます。このようにして、製品やウェブサイトの評価が得られます。この評価は記録され、ウェブサイトで将来的に関連性の高いコンテンツや評価の高い製品を推奨するために使用されます。この種の明示的な評価データは比較的正確ですが、ほとんどのユーザーは自分にとって有益なものを見ることができず、一般的に評価を提供するために時間を無駄にしないため、入手が難しいという欠点があります。

（2）暗黙の評価：ユーザーの購入履歴や閲覧履歴を記録し、異なる値の評価の計算を完了します。ユーザーが商品を購入したり、商品を閲覧したりする場合、そのユーザーは商品に興味を持っているとみなされ、ユーザーの興味はユーザーが商品を閲覧している時間で判断できます。滞在時間が長いほど、興味が強くスコアが高くなります。逆に滞在時間が短いと、興味が弱くスコアが低くなるか、0 になることもあります。これは、確立されたルールに従ってスコア値に変換される肯定的なスコアまたは肯定的な意図です。この方法の利点は、ユーザーとアイテムの評価マトリックスを充実させるのに十分な評価データを収集できることです。欠点は、取得したユーザー評価の正確性を保証することが難しく、悪意のあるユーザーの閲覧行動の影響を受けやすく、取得した評価がユーザーの意図や興味を十分に表すことができないことです。

8. まとめ

協調フィルタリング アルゴリズムに基づいて推奨を完了する主な方法は、最近傍推奨を使用することです。最近傍選択には、最近傍ユーザー (ピア ユーザー) と最近傍アイテム (ピア アイテム) が含まれます。この方法は、市場で最も古典的で、比較的安定しており、広く使用されている推奨方法です。したがって、推奨システムを設計するには、まず協調フィルタリング アルゴリズムを理解する必要があります。ユーザーの近傍推奨に基づくか、アイテムの近傍推奨に基づくかは、読者の使用シナリオによって異なります。主に評価マトリックスのスパース性に依存します。選択された評価マトリックスが豊富であればあるほど、一般的に推奨効果は高くなります。

9. いくつかご意見は?

上記記事の伏線から、読者は協調フィルタリング アルゴリズムの欠点について検討しただろうか。あるいは、協調フィルタリング アルゴリズムが効果を発揮しないシナリオはあるだろうか。そして、前述の評価マトリックス問題では、ユーザーがアイテムにほとんど評価を与えなかったり、ほとんど評価を与えなかったりして、評価マトリックスがまばらになりすぎた場合、評価マトリックスをどのように処理して推奨を完了すればよいだろうか。同時に、評価マトリックスが密な場合、前述の Redis のキーと値のペアを使用してオフラインで前処理された類似値を保存できるため、ストレージの問題を解決できますが、リアルタイムで計算する必要がある実際のデータは依然として数億に上り、アルゴリズムの時間計算量は楽観的ではありません。この問題を解決する方法はあるのでしょうか。推奨効果を保証するだけでなく、アルゴリズムの時間計算量をさらに削減できるのでしょうか。これらの考慮事項は、推奨システムを設計する際に考慮する必要があるものです。以降の原稿で詳しく説明し、上記の問題を 1 つずつ解決するための他の推奨アルゴリズムを紹介します。

[51CTO オリジナル記事、パートナーサイトに転載する場合は、元の著者とソースを 51CTO.com として明記してください]