グラフベースの推奨システム

こんにちは！私の名前はAlexandraZenchenkoです。EPAMのリードソフトウェアエンジニアです。私は、クライアントの作業効率を向上させ、主に機械学習の一部を含むソリューションの開発に取り組んでいます。前回のプロジェクトでは、ロジスティクスの分野で推奨システムの構築に取り組みました。私の経験を共有し、アルゴリズムを使用してミュンヘンからジュネーブに貨物を輸送する方法を説明したいと思います。

レコメンダーシステムについて一言

確かに、誰もが何度も彼らに会いました。レコメンダーシステムは、特定のユーザーにとって何が興味深く、必要で、役立つかを予測し、それを示すプログラムとサービスです。「これらのランニングシューズは好きですか？また、ウィンドブレーカー、心拍数モニター、その他15のスポーツアイテムが必要になる場合があります。」近年、売り手と買い手の両方がこの決定から「利益」を得ているため、ブランドは仕事に推奨システムを非常に積極的に実装しています。消費者は、無限の種類の商品やサービスを短時間で選択するのに役立つツールを受け取り、ビジネスは売り上げと視聴者を増やします。

私たちに何が与えられましたか？

私は、顧客にSaaS貨物交換ソリューションまたは貨物交換プラットフォームを提供する大規模なグローバル企業のプロジェクトに取り組みました。



理解できないように聞こえますが、実際にどのように発生するか。一方で、ユーザーはプラットフォームに登録されており、貨物を持っていて、どこかに送る必要があります。彼らは「装飾的な化粧品のバッチがあります、それは明日アムステルダムからアントワープに持って行く必要があります」のようなアプリケーションを配置しますそして答えを待っています。一方で、トラックを持っている人や会社、つまり貨物運送業者がいます。彼らがすでに標準的な毎週のフライトを行っており、パリからブリュッセルにヨーグルトを配達しているとしましょう。彼らは戻る必要があり、空のトラックで行かないために、帰りに輸送するためのある種の貨物を見つける必要があります。これを行うには、貨物運送業者が私の顧客のプラットフォームに行き、（英語の検索から）検索を実行して、トラックに適した方向と、場合によっては貨物の種類（または英語の貨物からの貨物）を示します。システムは荷送人からアプリケーションを収集し、それらを貨物運送業者に表示します。







このようなプラットフォームでは、供給と需要のバランスが重要です。ここでは、貨物運搬船からの商品と荷送人からのトラックが需要であり、オファーとしては、逆に、運送業者からの車と企業からの商品が当てはまります。バランスを維持するのは、次のようないくつかの理由で困難です。

• キャリアとクライアント間のクローズドコミュニケーション。ドライバーが特定の顧客としか連携しないことが多い場合、プラットフォームではうまく機能しません。荷送人が市場を離れると、別の物流会社のクライアントになるため、サービスも運送業者を失う可能性があります。
• 誰も運びたくない商品の存在。これは、小規模企業が輸送を注文した後、更新されないため、アクティブなものの数をすぐに残す場合に発生します。

同社は、貨物交換プラットフォームの機能を改善し、ユーザーのユーザーエクスペリエンスを向上させて、システムのすべての機能と幅広い商品を確認し、ロイヤルティを失わないようにしたいと考えていました。これにより、ターゲットオーディエンスが競争力のあるサービスに切り替わるのを防ぎ、キャリアに、慣れ親しんだ企業だけでなく適切な注文が見つかることを示すことができます。



すべての要望を考慮して、私は課題に直面しました。プラットフォームの入り口ですぐに、現在利用可能な関連貨物を運送業者に表示し、何をどこに輸送したいかを推測する推奨システムを開発することです。このシステムは、既存の貨物交換プラットフォームに統合される予定でした。

どのように「推測」しますか？

私たちの推奨システムは、他のシステムと同様に、ユーザーデータの分析に取り組んでいます。そして、操作できるソースがいくつかあります。

• まず、商品の輸送の申請に関する情報を公開します。
• 次に、プラットフォームはキャリアに関するデータを提供します。ユーザーがお客様と契約を結ぶ際に、所有しているトラックの数と種類を指定できます。しかし、残念ながら、このデータが更新された後は。そして、私たちが信頼できる唯一のものは、キャリアの国です。それはおそらく変わらないからです。
• 第3に、システムは、最新のリクエストと1年前の両方の数年間のユーザー検索の履歴を保存します。

彼らが推薦システムを導入することを決定したアプリケーションでは、以前の要求によって商品を検索するためのメカニズムがすでにありました。そのため、ユーザーが輸送用の商品を検索するパターンを特定することに重点を置くことにしました。つまり、負荷はお勧めしませんが、現在このユーザーに最も適した方向を選択してください。そして、私たちはすでに標準の検索エンジンを使用して商品を見つけます。



一般に、人気のある検索は、地理情報と、トラックのタイプや輸送されるアイテムなどの追加パラメーターに基づいています。これらの設定はほとんど変更されないため、これは追跡するのに十分簡単です。以下に、1人のユーザーの3日間のリクエストのデータを示します。記入の順序は次のとおりです。1列-出発国、2-目的地の国、3-出発地、4-目的地の地域。







このユーザーは国や地方で特定の好みを持っていることがわかります。しかし、これはすべての人に当てはまるわけではなく、常にそうであるとは限りません。非常に多くの場合、運送業者は目的地の国のみを示しているか、出発地を示していません。たとえば、彼はベルギーにいて、貨物を受け取るためにどの州にも来ることができます。一般に、クエリにはさまざまなタイプがあります。「country-country」、「country-region」、「region-country」、または「region-region」（最適なオプション）です。

アルゴリズムサンプル

ご存知のように、レコメンデーションシステムを作成するための戦略は、主にコンテンツベースのフィルタリングとコラボレーティブフィルタリングに分けられます。この分類で、私はソリューションを構築し始めました。





私はhub.forklog.comから写真を撮りました



多くの情報筋によると、コラボレーティブフィルタリングの方が効果的です。簡単です。私たちは、私たちと同じような行動パターンを持つユーザーを見つけようとしています。私たちは、ユーザーに同じリクエストをすることをお勧めします。一般的に、このソリューションは私が顧客に提示した最初のオプションでした。しかし、彼らは彼に同意せず、それはうまくいかないと言った。結局のところ、すべては、トラックが現在どこにあるか、貨物をどこに持って行ったか、どこに住んでいるか、どこに行くのがより便利かによって大きく異なります。これらすべてについてはわかりません。そのため、他のユーザーが一見似ているとしても、他のユーザーの行動に依存することは非常に困難です。



次に、コンテンツベースのシステムについて説明します。これらは次のように機能します。最初にユーザープロファイルが決定および作成され、次にその特性に基づいて推奨事項が選択されます。かなり良いオプションですが、私たちの場合、いくつかのニュアンスがあります。まず、1人のユーザーが、多くのトラックの貨物を探しているグループ全体を非表示にして、さまざまなIPからログインできます。第二に、正確なデータからは運送業者の国のみがあり、トラックの数とそのタイプに関する情報は、ユーザーからの要求にのみほぼ「表示」されます。つまり、私たちのプロジェクトのコンテンツベースのシステムを構築するには、各ユーザーのリクエストを見て、その中で最も人気のあるものを見つけるようにする必要があります。



私たちの最初の推奨システムは、複雑なアルゴリズムを使用していませんでした。私たちはクエリをランク付けし、それらを推奨する最高のハートを見つけようとしました。コンセプトをテストするために、私たちのチームは実際のユーザーと協力して、推奨事項を送信し、フィードバックを収集しました。原則として、キャリアは結果を気に入りました。次に、推奨事項をキャリアが最近探していたものと比較したところ、システムは永続的な動作パターンを持つユーザーにとって非常にうまく機能していることがわかりました。しかし、残念ながら、より幅広いリクエストを行った人にとっては、推奨の精度はそれほど高くありませんでした。システムを改善する必要がありました。



私はここで何を扱っているのかを理解し続けました。実際、これは隠されたマルコフモデルであり、人々のグループが各ユーザーの背後にいる可能性があります。さらに、ユーザーはさまざまな隠れた状態にある可能性があります。現在トラックを持っている場所、1つのアカウントに何人いるのか、次回どこかに行く必要があるのか​​などのデータはありません。当時、私は隠されたマルコフモデルを作成するための既成の解決策を知らなかったので、もっと簡単なものを見つけることにしました。

PageRankに会う

そこで、Googleの創設者であるSergeyBrinとLarryPageによって作成されたPageRankアルゴリズムに注目しました。このアルゴリズムは、この検索エンジンでユーザーにサイトを推奨するために現在も使用されています。PageRankは、インターネット空間全体をグラフの形式で表します。各Webページはそのノードです。各ノードの「重要度」（またはランク）を計算するために使用できます。PageRankは、ページのコンテンツではなく、ページ内のリンクに基づいているため、以前から存在していた検索アルゴリズムとは根本的に異なります。つまり、各ページのランクは、そのページを指すリンクの数と品質によって異なります。ブリンとページは、このアルゴリズムの収束を証明しました。つまり、有向グラフ内の任意のノードのランクをいつでも計算して、変化しない値に到達できることを意味します。



その式を見てみましょう：

• PR(P) – rank
• N –
• i –
• O –
• d – . -, , - . , . 0 ≤ d ≤ 1 – d 0,85. .

次に、3つのノードで構成される単純なグラフのPageRankを計算する簡単な例を示します。最初は、すべてのノードに1 /ノード数に等しい同じ重みが与えられることを覚えておくことが重要です。







Cのように、ノードAが2つのノードのみを指しているにもかかわらず、ここでノードAが最も重要になっていることがわかります。ただし、Aを指すノードのランクは、Cを指すノードよりも高くなります。

仮定と解決策

したがって、PageRankは、隠れた状態のないマルコフプロセスを記述します。これを使用すると、常に各ノードの最終的な重みがわかりますが、グラフの変化を追跡することはできません。アルゴリズムは本当に良いです、私たちはそれを適応させて結果の精度を改善することができました。このために、PageRank（Personalized PageRankアルゴリズム）を変更しました。これは、遷移が常に限られた数のノードに対して実行されるという点で基本的なアルゴリズムとは異なります。つまり、ユーザーがリンクを「歩く」ことに飽きたら、ランダムノードではなく、特定のセットの1つに切り替えます。



この場合、グラフのノードはユーザーリクエストになります。私たちのアルゴリズムは翌日の推奨事項を提供することになっているので、私は各キャリアのすべてのリクエストを日ごとに分類しました。ここでグラフを作成します。ノードAはノードBに接続します。タイプBの検索がタイプAの検索に続く場合、つまり、タイプAの検索は、ルートBを探している日の前にユーザーによって実行されました。例：火曜日（A）の「パリ-ブリュッセル」、および水曜日の「ブリュッセル-ケルン」（B）。また、1日に多くのリクエストを行うユーザーもいるため、一度に複数のノードが接続され、その結果、非常に複雑なグラフが得られます。



あるハートから別のハートに移動することの重要性に関する情報を追加するために、グラフのエッジの重みを追加しました。 A-Bエッジの重みは、ユーザーがAを検索した後にBを検索した回数です。ユーザーはテンプレートを変更するため、クエリの経過時間を考慮することも非常に重要です。ユーザーは主要な種類の輸送手段を移動または再編成できます。その後、空のトラックで行きたくありません。したがって、ルートの履歴を監視する必要があります。ノードの重みにも影響するreency変数を追加します。



季節性を考慮する価値があります。たとえば、9月には運送業者がフランスに、10月にはドイツに旅行することがよくあります。したがって、特定の月に「人気のある」心臓により多くの重みを与えることができます。さらに、ユーザーが最後に検索した時間に関する情報に依存しています。これは、トラックがどこにあるかを間接的に推測するのに役立ちます。

結果

すべてがGoogleプラットフォームに実装されています。 OLTPアプリケーションがあり、そこからクエリのデータがBigQueryに出入りし、そこですでに処理された情報を含む追加のビューとテーブルが形成されます。 DASKライブラリは、大量のデータの処理を高速化および並列化するために使用されました。私たちのソリューションでは、DASKはCloud Storageでのみ機能し、BigQueryとは相互作用しないため、すべてのデータがCloudStorageに転送されます。 Kubernetesで2つのジョブが作成されました。1つはBigQueryからCloudStorageにデータを転送し、もう1つは推奨事項を作成します。これは次のように機能します。ジョブはCloudStorageからハートのペアに関するデータを取得して処理し、翌日の推奨事項を生成して、BigQueryに送り返します。そこから、すでに.json形式で、OLTPアプリケーションに推奨事項を送信できます。OLTPアプリケーションでは、推奨事項が表示されます。推奨事項の正確性はTableauで評価されます。ここでは、推奨事項が、ユーザーが実際に探していたもの、およびユーザーの反応（気に入ったかどうか）と比較されます。



もちろん、結果を共有したいと思います。たとえば、これは毎日14の国から国へのハートを作るユーザーです。私たちは彼にも同じ金額を勧めました。







私たちの選択肢は彼が探していたものと完全に一致していることがわかりました。このユーザーのグラフは約1000の異なるクエリで構成されていますが、私たちは彼の興味を引くものを非常に正確に推測することができました。



2番目のユーザーは、平均して2日ごとに8つの異なる要求を行い、「国-国」形式と特定の出発地域の表示の両方で検索します。また、出発国と配達国は完全に異なります。したがって、すべてを「推測」することはできず、結果の精度は低くなることが判明しました。







ユーザーには、重みが異なる2つのグラフがあることに注意してください。1つは、精度が38％に達したということです。これは、私たちが推奨する8つのオプションのうち3つが適切であることが判明したことを意味します。そして、おそらく、これらの方向に負荷が見つかった場合、ユーザーはそれらを選択します。



最後の最も単純な例。1人が毎日約2回検索します。それは非常に安定したパターンを持ち、あまり多くの好みがなく、単純なグラフです。その結果、予測の精度は100％です。

実際のパフォーマンス

• 当社のアルゴリズムは、4つの標準CPUと10GBのメモリで実行されます。
• データ量は最大10億レコードです。
• 約20,000人のすべてのユーザー向けの推奨事項を作成するのに18分かかります。
• DASKライブラリは並列化に使用され、NetworkXライブラリはPageRankアルゴリズムに使用されます。

私たちの検索と実験は非常に良い結果をもたらしたと言えます。貨物交換プラットフォームのユーザーの行動をグラフ形式で表示し、PageRankを使用することで、将来の好みを正確に予測し、効果的な推奨システムを構築できます。