1

ここでの私のプラットフォームは Ruby です。特に Rails 3.2 を使用する Web アプリケーションです。

特定のアイテムの評価に基づいてオブジェクト (人) を一致させようとしています。人々は、他の人々と同じ項目のすべてまたは一部を評価するか、まったく評価しない場合があります。評価は 0 から 5 までの整数です。評価できるアイテムの数とユーザーの数は、どちらも重要であると見なすことができます。

簡単なイラスト -

データ図

力ずくのアプローチは、すべての人を繰り返し処理し、各項目の違いを計算することです。Ruby風味の疑似コードでは -

MATCHES = {}
for each (PERSON in (people except USER)) do
  for each (RATING that PERSON has made) do
    if (USER has rated the item that RATING refers to) do
      MATCHES[PERSON's id] += difference between PERSON's rating and USER's rating
    end
  end
end
lowest values in MATCHES are the best matches for USER

ここでの問題は、アイテム、評価、および人の数が増えると、このコードの実行に非常に長い時間がかかることです。キャッシュを今のところ無視すると、これは多くのコードを実行する必要があります。私のアプリの機能。

私はこれを達成するために、より賢いアルゴリズムとより賢いデータベースを受け入れていますが、それをアルゴリズム的に行うことで、MySQL または PostgreSQL にすべてを保持できるようにすることで、私の人生はずっと楽になります。私が言える唯一のことは、データが持続する必要があるということです。

さらに詳細が役立つ場合は、お気軽にお問い合わせください。どんな支援も大歓迎です！

4

3 に答える 3

1

KDツリーをチェックしてください。これは、評価システムのように、N次元空間での近隣探索を高速化するように特別に設計されています（人物1はX軸に沿って3ユニット、Y軸に沿って4ユニットなど）。

これは、実際のプログラミング言語で行う必要があります。一部のDBには空間インデックスがありますが、それらは通常、PostGIS（GiSTインデックスを使用）などの地理的作業用に設計されており、2次元または3次元のみをサポートします。

そうは言っても、PostGISでこの魅力的なブログ投稿を見つけました。その後、これに関する他の参照を見つけることができませんでしたが、おそらくあなたの運は私のものよりも良いでしょう...

お役に立てば幸いです。

于 2013-02-13T22:20:58.790 に答える
0

技術的には、あなたのタスクは 5 文字のアルファベットの文字で作られた長い文字列を照合することです。この種のものは、計算生物学の分野で広く研究されています。(通常は 4 文字のアルファベット)。本http://www.amazon.com/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198を知らない場合は、コピーを入手することをお勧めします。IMHO これは、シーケンスのファジー マッチング/スコアリングに関する標準的な本です。

于 2013-02-13T22:16:09.257 に答える
0

あなたのデータはまばらですか？評価では、ほとんどの場合、すべてのユーザーがすべてのオブジェクトを評価するわけではありません。

各オブジェクトを他のすべてのオブジェクトと単純に比較すると、 は ですO(n*n*d)。ここdで、 は操作の数です。ただし、すべての Hadoop ソリューションの重要なトリックは、行列を転置し、列のゼロ以外の値に対してのみ機能することです。スパース性が であると仮定するとs=0.01、これにより実行時間が に短縮されO(d*n*s*n*s)ますs*s。したがって、スパース性が 100 分の 1 の場合、計算は理論的には 10000 倍速くなります。

結果のデータは引き続きO(n*n)距離行列になることに注意してください。厳密に言えば、問題は依然として二次です。

二次係数を打ち負かす方法は、インデックス構造を使用することです。kd-tree については既に言及されていますが、カテゴリ/離散データと欠損値のバージョンについては知りません。このようなデータのインデックス作成は、AFAICT で十分に研究されているわけではありません。

于 2013-02-14T07:11:32.770 に答える