7

問題：

何百万ものトランザクションのリストがあります。各トランザクションにはアイテム (「ニンジン」、「リンゴ」など) が含まれます。目標は、個々のトランザクションで頻繁に一緒に発生するアイテムのペアのリストを生成することです。私が知る限り、網羅的な検索を行うことは現実的ではありません。

解決策の試み:

これまでのところ、私には2つのアイデアがあります。1) トランザクションの適切な部分をランダムにサンプリングし、それらのみをチェックするか、2) 各要素が出現する頻度を数え、そのデータを使用して要素が偶然一緒に出現する頻度を計算し、それを使用して推定値を 1 から変更します。

ヒント、代替アプローチ、既製のソリューション、または一般的な読書の提案は大歓迎です。

編集：

コメントからの追加情報

異なるアイテムの数: 1,000 ～ 100,000

メモリの制約: 数時間、せいぜい数ギガの RAM。

使用頻度：多かれ少なかれ一回限り。

利用可能なリソース: 20 ～ 100 時間の初心者プログラマーの時間。

望ましい結果リスト形式: アイテムのペアと、最も頻繁に出現する n 個のペアについて、アイテムの出現頻度を測定するもの。

トランザクションごとのアイテムの配布: 現在のところ不明です。

4

2 に答える 2

7

トランザクションnの数を 、アイテムの数をk、トランザクションの平均サイズを としますd。

単純なアプローチ (すべてのレコードでペアをチェックする) でO(k^2 * n * d)解決策が得られますが、実際には最適ではありません。しかし、それを に改善することができますO(k*n*d)。また、アイテムの均一な分布 (つまり、各アイテムが平均的に繰り返される) を仮定すると、O(n*d/k)に改善できる可能性がありますO(d^2 * n + k^2)(最も可能性が高いため、これははるかに優れていますd << k)。

これは、トランザクションの逆インデックスを作成することで実行できます。つまり、項目からそれらを含むトランザクションへのマップを作成します (インデックスの作成は ですO(nd + k))。

例、トランザクションがある場合

transaction1 = ('apple','grape')
transaction2 = ('apple','banana','mango')
transaction3 = ('grape','mango')

逆索引は次のようになります。

'apple' -> [1,2]
'grape' -> [1,3]
'banana' -> [2]
'mango' -> [2,3]

したがって、逆インデックスとは何かを理解した後、解決策のガイドラインを次に示します。

  1. データの転置インデックスを作成する
  2. 各アイテム x について、それが出現するすべてのドキュメントを反復し、 と共起するようなすべてのペアのヒストグラムを作成します。(x,y)yx
  3. 完了すると、処理が必要な k^2 項目を含むヒストグラムが得られます。この質問では、ソートされていないリストから上位 k 要素を取得する方法について説明します。

複雑さの分析:

  1. 逆索引の構築はO(nd+k)
  2. O(nd/k)各要素がトランザクションで繰り返されると仮定すると、各反復にはO(nd/k * d)時間がかかり、このステップにはk反復があるため、このステップになりますO(nd^2 + k)。
  3. リストの処理は、完全な順序付けが必要な場合は O(k^2logk) で実行できます。または、上位 X 要素のみを出力したい場合は で実行できますO(k^2)。

を仮定O(nd^2 + k^2)すると、単純なアプローチよりもはるかに優れていd << kます。

さらに、必要に応じて、ボトルネック (ステップ 2) を効率的に並列化し、スレッド間で分散できることに注意してください。

于 2013-01-04T16:13:25.610 に答える
0

1 回の購入で注文するアイテムの数が少ない場合 (<10) は、これを行います:
have map of maps(dictionary of dictionaries) : 最初のマップのキーはアイテム、
最初のマップの値はキーが 2 番目のアイテム、値のマップです最初のキーで購入時に表示された回数をカウントします。

したがって、すべての注文とすべてのペアの更新マップを確認してください。最後に、マップのマップを調べて、「2 番目の値」で「大きな値」を探します。

注: 入力データのサイズと「分布」によっては、十分なメモリが不足する可能性があります

于 2013-01-04T16:36:05.277 に答える