2009-03-24 17 views
5

ここにいくつかのアドバイスをお探しですか?誰もがn次元空間でのマッチングアルゴリズムを調べ始めるのに良い場所を知っていますか?例えば、出会い系サイトは2人の人に合った何らかのアルゴリズムを使っていなければなりません。私が読んだことは、n次元配列の人物の特性を各特性のポイントシステムでマップできることです。ひとりの人のすべての(利用可能な)特徴が得られれば、この人をn次元配列内のある点で表すことができる。次に、2人の人を照合することは、このn-dim配列内の2点間の最短距離を見つけることと同じくらい簡単です。誰もこれらの種類のアルゴリズムの実装で任意の参照を持っていますか?このようなことを書くには最高の言語は何ですか?n次元マッチングアルゴリズム

答えて

1

まず、よく知っている言語を選んでください。これを処理するためのアルゴリズムはかなり簡単で、現代的な言語で動作するはずです。 (配列の概念があり、潜在的に行列ライブラリがある限り、あなたはうまくいくはずです。)私はC、C++、C#でこれらの多くを実装しましたが、Python、vb.netなどの実装を見ました。

何をしようとしているかによって、いくつかのオプションがあります。

あなたがしたいことは、あなたの目標によって異なります。最良の一致を見つけたい場合は、単純な距離計算(つまり、n次元配列の各次元/プロパティの平方和のsqrt)を使用して、オプションで各プロパティの距離を重み付けし、最も近い点を使用することができます。

人をグループにまとめたい場合は、clustering algorithmsを参照してください。このようなデータの場合、私はK-Meansクラスタリングやファジィc-meansクラスタリングのいくつかの形式が最適であると考えています。あなたは一人のために最も近いものを見つけたい場合は

5

は、ベントレー& Shamosは多次元分割統治法に公開:Oにおける分割統治を(n log n)時間:Divide-and-conquer in multidimensional spaceを議事録にコンピューティング理論の第8回ACMシンポジウム1976。コピーを入手できない場合はthisも役立つかもしれません。

しかし、実際の例では、最も近いネイバーを実際に見つけることは最大の問題ではないようです。入力をディメンションにマッピングするのがはるかに面倒です。たとえば、ある次元が「動物が好き」の場合、犬を好きな人にはどのような価値を与えますか?&猫は馬に立つことができません。馬が大好きで、犬は大丈夫だと思う人はどうですか?猫は迷惑になり、金魚については相反していますか?

+0

人を次元にマッチングさせるのに良い点。多分、次元ごとの尺度のようなものかもしれません。つまり、猫+犬が好きで馬が嫌いな人は、+ 1/+ 1/-1、つまりその次元のスコアとして+1、またはそれらの線に沿ったものです。 –

+0

@ダニオ:「動物好き」の1つのディメンションを、別々の「好きな犬」、「好きな猫」などのサイズに分割できます。 –

1

次の解決方法はどうですか。

ユーザがU1、U2、U3、U4、U5 ....であると仮定します。 U1、U2、U3 ... A2 - - 属性は

A1とA1、A2、A3、A4、A5 .....アム

ストアこれらはU4、U6、U7 ... A3 -

プロファイル属性はインデックスであり、すべてのユーザーを格納します。今、新しいユーザーが来たら、その属性を見て、その属性については一般の人を見てください。人がこれらのリストに存在する回数 - 上位です。

0

あなたの例で説明しているのは、n次元のマッチングではなく、複数の機能を持つノードのbipartite matchingです。 (2人でこの距離を計算する関数を用意する必要があります)。そのためには非常に効率的なアルゴリズムが必要です。 n次元のマッチングでは、2つ以上のセットのノードを照合しようとします(あなたの例では、人を身体、魂、音楽の好みにカットし、それらを再結合して新しい人物を作ることができます)。人々を切り離し、それらを再結合して、設計された新しい人が本当に素敵なカップルを作るようにしてください:D)wikipedia article for 3-dimentional matchingはnp-completeです。

また、他の人にも言われているように、ペアになって人を照合するのではなく、互換性のあるグループを見つけることが目標である場合、グループにグループ化することを検討する必要があります。これは、例えば、 Unsupervised Learning

関連する問題