Platform For AI:SimRank++ 類似度アルゴリズムの使用

概要

SimRank アルゴリズムは、構造的なコンテキストにおけるオブジェクト間の類似度を測定するために使用されます。その中心的な考え方は、オブジェクト a とオブジェクト b がオブジェクト c とオブジェクト d に関連し、かつオブジェクト c がオブジェクト d に類似している場合、オブジェクト a はオブジェクト b に類似していると見なされる、というものです。さらに、各オブジェクトはそれ自体と最も類似しており、その類似度は 1 です。SimRank アルゴリズムは、既存のオブジェクトの類似度を使用して、それらに関連する他のオブジェクトの類似度を計算します。

SimRank アルゴリズムは、単純で直感的なグラフ理論モデルに基づいています。これは、有向グラフ G = (V, E) 内のオブジェクト間の類似度のメジャーです。V はアプリケーションドメイン内のすべてのオブジェクトを示す頂点のコレクションであり、E はオブジェクト間の関係を示すエッジのコレクションです。グラフ内のオブジェクト について、入力エッジに関連付けられた入力近傍のコレクションは と表され、出力エッジに関連付けられた出力近傍のコレクションは と表されます。オブジェクト とオブジェクト の間の類似度は と表され、次の数式に基づいて計算されます。

この数式は、オブジェクト とオブジェクト の間の類似度が、オブジェクト とオブジェクト に関連するすべてのオブジェクト間の類似度に依存することを示しています。数式中の は定数の減衰係数です。

上記の数式は行列形式で表現できます。たとえば、S は有向グラフ G の SimRank 類似度行列を示します。 はオブジェクト とオブジェクト の間の類似度スコアを示します。P は有向グラフ G の隣接行列を示し、 は頂点 から頂点 へのエッジの数を示します。

上記の数式は、次の行列で表現できます。

行列は 列正規化行列を示します。 は の単位行列です。 は 行列の主対角要素を 1 に設定することを指定します。

SimRank++ アルゴリズムは、SimRank アルゴリズムに基づいて新しい関数 を導入し、二部グラフ内のノード間の遷移確率を示します。

次のセクションでは、新しいアルゴリズムの反復数式について説明します。

と は任意の 2 つのクエリを示します。 と は任意の 2 つの広告を示し、 と の係数は次の数式を使用して定義されます。

SimRank++ アルゴリズムは、「重み」と「証拠値」を使用して元の計算結果を改良することにより、前述の 2 つの側面で SimRank アルゴリズムを拡張します。

SimRank++ アルゴリズムは、2008 年に Antonellis によって、スポンサード広告検索ドメインにおけるクエリリライティングアプリケーションのために特別に提案されました。

推薦システムでのアルゴリズムの使用

元の SimRank++ アルゴリズムは、計算広告ドメインでクエリリライティングを実行するために使用されます。ほとんどの場合、最近の期間の累積クリック動作データを使用して、クエリ間および広告間の関係を計算します。

クエリによって表現されるクエリ意図は、短期間で安定する可能性があります。したがって、複数日の動作データを使用して類似度を計算することは合理的です。

推薦システムに明確な意図を持つクエリが存在しない場合、クリックやその他の動作に基づくユーザー-アイテム二部グラフを SimRank++ アルゴリズムの入力として使用できます。

クエリの関連性に制限がない推薦シナリオでは、ユーザーの意図が曖昧になることがあります。ユーザーは同時に複数の興味を持つことがあり、その興味は時間とともに変化する可能性があります。

さらに、ユーザー数はクエリ数よりもはるかに多く、数百万から数十億に及ぶことが多く、これは SimRank++ アルゴリズムの実装に大きな課題をもたらします。

前述の理由から、セッションベースの行動二部グラフを使用してアイテム間の類似度を計算することをお勧めします。セッション内のユーザーの興味は集中しており、複数のアイテムカテゴリにまたがることはありません。明示的なセッション ID 追跡がないシナリオでは、concat(user_id, date) をセッション ID として使用できます。

増分計算

セッション ID が多数ある場合、計算の実現可能性を確保するために、複数日のデータをマージしてアルゴリズムの入力としないことをお勧めします。

カバレッジの問題を解決するために、増分計算ソリューションが提供されています。SimRank++ アルゴリズムツールキットは、複数日にわたるアイテムの類似度データを保持します。T 日目のアイテム類似度を計算するために、アルゴリズムは T-1 日目のアイテム類似度を使用して類似度行列を初期化します。ツールキットはセッションの類似度データを保持しません。

最後に、複数日からの類似度スコアがアイテムの最終的な類似度スコア として累積されます。

は割引係数です。以前の類似度スコアが現在のスコアに累積される際に、割引が適用されます。時間が長いほど、割引が大きくなります。

注: 複数日にわたって累積された類似度スコアからの類似度スコア は保証されません。ビジネス要件に基づいてスコアを正規化する必要があります。

改善点 1: 人気度抑制

推薦シナリオでは、介入が適用されない場合、アルゴリズムは人気のあるアイテムを他の多くのアイテムと類似していると見なす可能性があります。これは、人気のあるアイテムがより多くの露出機会を得るためです。この問題を解決するために、SimRank アルゴリズムツールキットは人気度抑制メカニズムを導入しています。

具体的には、行動二部グラフから各アイテムに対応するエッジの重みを合計して、人気アイテムを特定します。 z-score 変換を、 で指定されたアイテムの人気度に適用します。

を 0 から 1 の範囲の単調減少関数に変換します。

エッジの元の重みに を乗じたものを新しい重みとして使用します。これは、ランダムウォーク中に人気のあるアイテムに向かって移動する際の抵抗を増加させることと等価です。

改善点 2: プリファレンスカテゴリによる重み付けの再設定

推薦シナリオでは、偶発的なクリックによりユーザーのクリック動作にノイズが含まれることがあります。ノイズの影響を軽減するために、行動二部グラフの重みは、アイテムカテゴリに対するユーザープリファレンスの計算に基づいて調整されます。

特定のユーザーの アイテムカテゴリに対するプリファレンスは、次の数式を使用して計算されます。

アイテム の重みは から に変更されます。アイテム は カテゴリに属します。

入力と出力のフォーマット

パーティションテーブルなどの入力テーブルには、次の列が含まれます。

• 入力テーブルには、重複する <user_id, item_id> バイナリグループを含めることはできません。事前に重みをマージする必要があります。

• カテゴリデータを使用してアルゴリズムのパフォーマンスを向上させる場合、列の値が null のレコードは削除されます。カテゴリ列に null 値が含まれていないか確認してください。

• 注: 同じクエリに対する重みの分散を特定の範囲内に維持してください。分散が非常に大きい場合、重み遷移行列の要素値が 0 になり、取得率が大幅に低下します。

  • min-max、z-score、log、または sigmoid などの変換を適用して、事前に重み列を正規化または標準化することをお勧めします。

  • また、input_weight_normalizer パラメーターを設定することもできます。

• アルゴリズムのパフォーマンスを向上させるには、二部グラフのエッジの重みを設定する必要があります。

  • ctr を重みとして使用すると、ctr の値が大きいレコードの露出回数 (pv) が非常に少なくなる可能性があるため、ノイズデータが導入される場合があります。

  • この場合、log(1+click) をエッジの重みとして使用できます。

• データをクレンジングし、特定のノイズデータをフィルターで除外することをお勧めします。

  • 特定のクエリに基づいて click/sum(click) < threshold データをフィルターで除外できます。たとえば、threshold = 3e - 5 です。

アイテム類似度の出力テーブルは次のフォーマットで、パーティション列を含むことができます。

注: $$score\in (0,1)$$および cumulative_score の値は正規化されていません。

クエリ類似度の出力テーブルは次のフォーマットで、パーティション列を含むことができます。

ジョブの送信

1. simrank_plus_plus-1.3.jar アルゴリズムパッケージをダウンロードします。

2. アルゴリズムパッケージを MaxCompute プロジェクトにアップロードします。

   

3. DataWorks で ODPS MR ノードを作成し、次のコマンドを実行してジョブを送信します。ODPS SQL ノードを作成するとエラーが発生する可能性があります。

   --@resource_reference{"simrank_plus_plus-1.3.jar"}
   jar -resources simrank_plus_plus-1.3.jar
   -classpath simrank_plus_plus-1.3.jar
   com.aliyun.pai.simrank.SimRankDriver
   -project ${max_compute_project}
   -end_point http://service.cn-hangzhou.maxcompute.aliyun.com/api
   -access_id ${access_id}
   -access_key ${access_key}
   -input_table simrank_i2i_input
   -input_table_partition ds=${bizdate}
   -output_table simrank_i2i_output
   -output_table_partition ds=${bizdate}
   -init_partition ds=${yesterday}
   -session_column device_id
   -item_column item_id
   -category_column cate_lv3_id
   -num_matmul_reducer 2000
   ;

パラメーター

クエリリライティングなどの検索シナリオでは、anti_popular パラメーターを false に設定できます。推薦シナリオでは、このパラメーターを true に設定できます。

ケース分析

検索シナリオでは、入力データ量は約 1,700 万、クエリ数は 120 万、アイテム数は 150 万です。次のパラメーターを使用すると、全体のプロセスは約 87 分で完了します。

--@resource_reference{"simrank_plus_plus-1.0.jar"}
jar -resources simrank_plus_plus-1.0.jar
-classpath simrank_plus_plus-1.0.jar
com.aliyun.pai.simrank.SimRankDriver
-project ${project}
-end_point http://service.cn-shanghai.maxcompute.aliyun.com/api
-access_id ${access_id}
-access_key ${access_key}
-input_table ${input_table}
-input_table_partition dt=20240512
-output_table simrank_i2i_score
-output_table_partition dt=20240512
-session_output_table simrank_q2q_score
-session_output_table_partition dt=20240512
-output_table_lifecycle 7
-session_column query_word
-item_column item_id
-category_column category
-anti_popular false
-num_matmul_reducer 2000
-num_evidence_reducer1 1000
-num_evidence_reducer2 200