散乱アルゴリズムの3つのソリューションとその選択シナリオ

背景

分割とは、推奨、広告、検索システムの結果に基づいてユーザーの視覚的なエクスペリエンスを向上させるプロセスです。主な方法は、ユーザーの疲労を避けるために、類似のカテゴリのオブジェクトが分散されるように、結果を表示順に並べ替えることです。アルゴリズムによって送信される推奨結果には、次のような問題点がよくあります。

• 類似したカテゴリの製品は、一緒に集められる傾向があります。当然のことながら、製品の機能が類似している場合、得られる推奨スコアも類似する可能性が高く、同一の製品が多数表示されることは、ユーザーが期待する結果ではありません。
• ユーザーの好みが強く反映されすぎています。心理学的な観点から見ると、ユーザーは自分のプライバシーや好みが完璧に把握されることに敏感です。過度に正確な結果は、ユーザーに嫌悪感を与えるだけでなく、ユーザーの潜在的なコンバージョンを制限する可能性もあります。
• 発生したエラーは簡単に拡大されます。使用履歴がほとんどないユーザーの場合、機能のみを強調してしまいがちで、誤った推奨につながる可能性があります。
• 表示順序を変更してアルゴリズムを分割し、類似のカテゴリを分離し、推奨システムとユーザー間のやり取りをバッファリングしてユーザー エクスペリエンスを向上させることは、アルゴリズムのエンパワーメントを実装するための最終ステップです。

問題の定義

まず、スクランブリング アルゴリズムを定義します。入力は、ユーザーの好みに応じてアルゴリズムによって並べられた順序付きリストです。各オブジェクトには区別する必要がある 1 つ以上の属性があり、出力要件は類似の属性が分散されたリストです。以下の詳細が含まれます:

• 分裂の度合い。同じカテゴリーのアイテムはできるだけ離して置いたほうが良いでしょうか、それともある程度の距離があれば十分でしょうか?
• 基底の次元を分割します。 1 つの属性に従って分離できますか、それとも分離するために考慮する必要がある複数の要素がありますか?
• パフォーマンスがばらばら。頻繁に呼び出されるインターフェースなので、パフォーマンスの最適化が進むほど良くなります。

注目すべきは、アルゴリズム側のシステムがもたらすユーザーの個性的な要素を失いたくないということであり、そのため、断片化に基づいて元のオブジェクトの順序を最大限に活用する方法も検討する価値のある問題です。

解決

3 つの異なる側面から、さらに一般的な 3 つの別れ方について説明します。 3 つの方法のうち、最も徹底的な方法は列ベース方式、複数の次元を包括的に考慮できる方法は重み分散方式、パフォーマンスを向上させるためにローカル計算のみを必要とする方法はスライディング ウィンドウ方式です。

列方向の散布

類似の属性を持つコンテンツが隣り合って表示されるのを避けたいので、最も簡単な方法は、異なる属性を持つコンテンツを異なるバケットに配置し、コンテンツを取得するたびに異なるバケットを選択するようにすることです。こうすることで、要素を可能な限り分散させることができます。下の図に示すように、この例では、初期リストには 3 つのカテゴリ (青、黄、赤) があります。

次の順序でバケット (通常は HashMap) に格納します。

このとき、各バケットから列ごとに要素を取り出すことで、要素が最大限に分散されることが保証されます。最終結果は

元のアルゴリズムの結果が確実に保持されるように、各列を元の順序で並べ替えます。このアルゴリズムの利点は次のとおりです。

• シンプルで直接的、実装が簡単
• 散乱効果は良好です。ソートにより、列の先頭と末尾で要素が偶然に隣接してしまうことがありますが、末尾の前の隣接要素の最大数は2であり、エクスペリエンスには影響しません。
• パフォーマンスは比較的安定しており、入力構造の影響を受けにくい

欠点は次のとおりです。

• 末端の分裂が失敗し、クラスター化が発生する可能性が高い
• 元の順序はあまり尊重されず、推奨係数が非常に低いオブジェクトがあっても、強制的に最前面に表示される
• 分類の1つの側面のみを考慮することができ、他の要因を包括的に考慮することはできない

同時に、このアルゴリズムはカテゴリの数に大きく依存していることがわかります。カテゴリが十分に詳細であれば、このアルゴリズムの欠点は部分的にカバーできます。パフォーマンスの面では、時間とスペースの消費はどちらも O(n) です。

重量配分方法

複数の要素を総合的に考慮したい場合、各製品を直接直感的に分類することができません。このとき、重み配分法を使用することができます。まず、各オブジェクトに新しい重みを定義します。

このうち、W は各属性に手動で割り当てられる係数で、散布の優先度を表し、Count は当該属性におけるオブジェクトのパフォーマンス（同じ属性が何回出現したか）を表します。直感的に言えば、類似の属性が出現した回数が多いほど重みの値は大きくなり、関数の計算プロセスでは、元の順序係数が自然に考慮されるため、重みを計算した後は、他の処理は必要なく、重みで並べ替えるだけです。下図を例に挙げます。フォント色の重み係数を 2、カラーブロック色の重み係数を 1 に設定すると、No. 1 と No. 2 ではフォント色とカラーブロックが一度も登場していないため、重みは 0 です。No. 3 では 1 回登場しているので、重みは 2 * 1 + 1 * 1 = 3 です。同様に、No. 8 ではフォント色が 2 回登場し、カラーブロック色が 3 回登場しているので、重みは 2 * 2 + 1 * 3 = 7 です。

この方法では、重みに応じてデータを分散させるのに必要なソート操作は 1 回だけです。

重み係数を重く設定することで、フォントの色を乱す優先度を実現していることがわかります。カラーブロック情報の係数が低いため、それらの限られた隣接性は許容できます。このアルゴリズムの利点は次のとおりです。

• 実装もシンプルで直接的である
• さまざまな要因の分散を考慮すると、重み係数を調整することで分散傾向を簡単に調整できます。
• 重量計算機能を変更することで、他の考慮事項を簡単に組み込むことができます。たとえば、元の順序をより尊重したい場合は、元の順序を重量計算に追加することもできます。

欠点は次のとおりです。

• 重み計算の累積効果により、このアルゴリズムは最終的に失敗する傾向がある。
• 最後に、全体的なソートは O(n logn) のパフォーマンスで実行され、最適化の余地が残ります。

スライディングウィンドウ方式

上記の 2 つのアルゴリズムは、全体的な状況を徹底的に考慮した後に生成されます。複雑度の計算における変数 n は、元のシーケンス全体のサイズでもあります。ただし、実際のシナリオでは、ユーザーはシーケンス全体を一度に見ることはありません。多くの場合、ユーザー ウィンドウを埋めるために、上位 N 個のシーケンスが一度に返されます。このとき、ローカル部分のみを参照する方法を検討する必要があります。基本的な考え方はスライディング ウィンドウです。

下の図に示すように、ユーザーの受信ウィンドウを模倣するために、サイズ 3 のウィンドウを開きます。ウィンドウ内に重複する要素があってはならないことが規定されています。つまり、重複のないユーザーが見る表示ページをシミュレートするためです。ウィンドウ内に重複する要素が見つかった場合、適切な要素が検出され、現在の要素と交換されます。最初のステップでは、2 と 3 が同じタイプであることが検出されたので、3 を取り除きます。その後、4 が 3 の要件を満たしていることが検出されたので、3 と 4 を交換し、ウィンドウを 1 グリッド分後ろにスライドします。 2 番目のステップでは、ウィンドウ内の 2 と 3 がまだ同じタイプであることが判明したため、3 と 5 が交換され、ウィンドウは 1 グリッド分後ろにスライドし、ウィンドウ内に競合がないことが判明したため、再び 1 グリッド分スライドします。 3番目のステップでは、5と6が同じタイプであることが判明したため、6と7が交換されます。ウィンドウは最後までスライドします。7と8は同じタイプであることが判明しましたが、その時点では交換可能な要素がないため、処理されません。

このアルゴリズムの利点は、ローカル計算のみが必要であり、完全に分散する必要がないため、topN のニーズを満たすことです。

しかし、その欠点も同様に明らかです。堅牢性が低く、シーケンス分布の影響を大きく受け、末端蓄積の欠陥を回避できません。

総合的な考慮

これまでの議論に基づいて、これらの方法について次のような結論に達しました。

3 つの方法のパフォーマンスを直感的に比較するために、完全にランダムな 100,000 個のデータを生成し、ノートブック環境でさまざまなスケールで 3 つのアルゴリズムのパフォーマンスをテストしました。横軸は出力データのサイズ、縦軸は実行時間（単位：ms）を表します。

一定のデータ範囲内では、スライディング ウィンドウ方式には大きな利点があることがわかりますが、パフォーマンスはウィンドウ サイズとも密接に関係しています。ウィンドウの範囲が大きすぎると、競合が多くなり、交換速度が大幅に低下します。

要約すると、3 つのアルゴリズムの適用可能なシナリオは次のとおりです。

• 一般的なシナリオで単一のディメンションを使用している場合は、列ベースの散布を使用することはまったく問題ありません。
• パフォーマンスを重視し、元の順列分布がすでに疎である場合は、小さな単位のスライディングウィンドウを選択することをお勧めします。
• 複数の次元を導入したい場合は、重量配分方法が必須です。

この記事で提案されているすべてのアルゴリズムのパフォーマンスは O(n) および O(nlogn) レベルであり、実際のシナリオは極めて小さいことが多いため、アプリケーションのパフォーマンスのボトルネックにならず、変更やトレードオフの余地が大きく残ります。その後、この問題は、世界的および地域的な調整、最終蓄積などの観点からさらに議論される可能性があります。

選択された例

実際に応用する場合には、いずれか 1 つだけを使うことは通常ありません。ニーズを明確にし、ニーズに基づいて分析することで、3 つすべての利点を生かす必要があります。

今回、Xianyu の Mach 製品選択システムを分散化するニーズを解決する際に、次の機能を学びました。

• 製品リストの長さは約 2000 です。ユーザーがメッセージから取得できるアイテムの数は限られており、通常は 1 桁または 2 桁のみです。
• 分割の要件：同じユーザーが投稿した商品と、同じカテゴリの商品を分け、前者が後者より優先されるようにします。係数を調整できるとベストです。
• ユーザーIDは多数あり（各ユーザーが商品を公開できる）、商品カテゴリは極めて限られている

その後、ターゲットを絞った独自のソリューションを選択できます。特徴2から、複数の要因を考慮して重み配分方法を選択する必要があることがわかります。 パフォーマンスの問題を解決するために、特徴1と3を考慮すると、一度に取得できる情報は非常に少なく、商品のカテゴリは非常に限られているため、スライディングウィンドウ方式を選択することにしました。重み配分法とスライディングウィンドウ法を組み合わせ、ウィンドウサイズが4のスライディングウィンドウを採用し、重み係数13と7（どちらもソートしやすいように素数）を使用してそれぞれユーザーとカテゴリの重み関数を計算し、ウィンドウ内の制約条件を他のすべてのオブジェクトとの重みの差が一定のしきい値未満になるように変更します。最終的には、多要素統計とパフォーマンスの統合を実現できます。

少し不十分なのは、パラメータの選択（ウィンドウサイズ、重み係数）が繰り返し実験比較されていないことです。今後は、実際のシナリオで ABtest などの方法を使用してパラメータを最適化および調整し、アルゴリズムのパフォーマンスを向上させる予定です。

要約する

この記事では、スキャタリング アルゴリズムのいくつかの実装方法について説明し、実装方法からメリットとデメリットまで詳細に説明します。この記事の方法により、特定のカテゴリの結果を散在した順序で表示できるため、ユーザーの視覚体験が向上します。分割の実際の効果と元のアルゴリズムの順次特性を尊重することの間には、避けられない矛盾があることがわかります。実際の複雑な要求の条件下で、この 2 つのバランスをより良くとり、より多くのシナリオに適用できるようにするには、今後も引き続き検討する必要があります。また、技術の進歩を活用してユーザー エクスペリエンスをより良く向上させる方法は、技術者にとって永遠の命題です。