次のタスクがあります。
各ラベルについて、XI は 10 個の上位 Y ラベルを見つける必要があります。ここで、X と Y の両方がドキュメントに存在し、X と Y の両方が存在するドキュメントの数で並べ替えられます。
このタスクは、解決するのが非常に複雑に見えます。
すべての組み合わせをメモリに保持したり、並列アルゴリズム (map reduce と同様) に分割して解決したりせずに、これを解決する方法はありますか? 100% 正確である必要がない場合はどうすればよいですか?
一般的なケースでは、非常にひどいランタイムを避けることはできないと思います。各ドキュメントに 5050 のペアがあり、10M のドキュメントがある場合、すべての組み合わせが可能に見えます。
ただし、典型的な実世界のデータでは、「敵対的」な入力を処理する必要はほとんどありません。考えられる解決策の 1 つは、最初に 100K の用語すべての出現回数をカウントし、それらを並べ替えてから、用語 X ごとに次の操作を行うことです。
100K の用語がドキュメント カウントに関して対数曲線に従う適切なドキュメント セットの場合、(100)^2 * 10M よりもはるかに少ない作業で済みます。確かに、行儀の悪いドキュメント セットの場合は、さらに多くの作業を行うことになりますが、現実の世界ではそれが起こるべきではありません。
「100% 正確ではない」というのは、あまりにもあいまいな仕様です。どのようなエラーが許容されますか? どれくらい？
--- コメント応答 (コメントには大きすぎます) ---
a) 最大 1 億要素を決定することを考えてください。スキャンした時点で最高の 1 つを保存するだけで済みます。同じ原則が、N 個のアイテムの上位 X 個を決定する場合にも当てはまります。入ってくる要素をバイナリ ヒープに追加し、ヒープのサイズが X を超えたら最も弱い要素を削除します。最後を追加すると、一番上の X になります。
b) X="Elephant" である上位 10 の X&Y ペアを決定していると想像してください。1000 個の Y タームをスキャンした後、サイズ 10 のヒープがあり、最小スコア ペアのカウントが 300 であるとします。チェックする 1001 番目のタームのドキュメント カウントが 299 であるとします。Y タームを持つドキュメントはせいぜい 299 個しかないため、多くても299 個のドキュメントには X&Y も含まれているため、これまでの上位 10 組のいずれよりも優れている可能性はありません。また、すべての Y 用語はドキュメントの頻度でソートされているため、実際には、持っていないことがわかります。さらにペアをチェックするには！これは、max ステートメントが保証するものです。
c) 各 X に対して行う選択は、純粋に最適化の決定です。少数のドキュメントにのみ存在する X が多数ある場合、これは良い問題です。つまり、用語ごとの作業が少なくなります。
d) トップ 10 が (用語ごとに) 間違っている可能性が 0 でない場合は、インデックスの完全で厳密なスキャンの代わりにサンプリング方法を使用することで、おそらく実行時間を大幅に削減できます。X という用語がドキュメント インデックスで広く使用されているほど、収集した情報に基づいて X と Y の上位 10 の正しいペアを取得する前に (比例的に) スキャンする必要があるドキュメントが少なくなります。この点に関して正確な数を考え出すには、基礎となるインデックスで予想される用語の分布に関するある程度の知識が必要です。具体的には、用語はどの程度相関していますか? 数 N(X)/MAXY(X) は一般的にどのように見えますか? ここで、N(X) は用語 X を含むドキュメントの数であり、MAXY(X) は X と Y のペアを含むドキュメントの数であり、最大化されています。すべての用語 Y != X